\documentclass[11pt]{article}

\bibliographystyle{plain}
\usepackage{epsf}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage{lscape}
\usepackage{float}
\usepackage{amsmath}
\usepackage{morefloats}

\title{6.825 Project 3, Bayes' Net Learning: \\
Parameter Estimation and Structure Search}

\pagestyle{plain}
\setlength\parskip{1ex}
\setlength\parindent{0em}

\begin{document}

\author{
  Eric Mumpower    \\
  Dan RK Ports
}

\date{November 29, 2005}

\maketitle

\section*{Task 1: Initial Networks}


Before we can proceed to implement and test greedy structure search,
we must generate initial networks. We tested our greedy search
algorithm using the following initial networks:

\begin{itemize}
\item \textbf{Given:} the initial network provided in the data files.
\item \textbf{Unconnected:} an unconnected network --- all variables
  independent
\item \textbf{Connected:} a fully connected network --- each node is a
  child of every node before it in the topological ordering
\item \textbf{Random:} a randomly generated network, produced as
  follows: on each iteration, one parent and one child node are
  chosen, and an edge is added between them if valid. It is valid to
  add an edge if the edge does not already exist, and the child is not
  an ancestor of the parent; these conditions are necessary and
  sufficient for avoiding directed cycles\footnote{This is a subset of
    the rules for which operations are valid, described in Task 2,
    since here we are only adding edges and there we also consider
    reversing edges.} This process is repeated until there are $n$
  edges in the network, where $n$ is the number of nodes in the
  network.
\end{itemize}

The initial networks used in our experiments can be found in the first
graph of
Figures~\ref{fig:struct-a-given}~and~\ref{fig:struct-b-given} for
Given networks, 
Figures~\ref{fig:struct-a-unconnected}~and~\ref{fig:struct-b-unconnected} for
Unconnected networks,
Figures~\ref{fig:struct-a-connected}~and~\ref{fig:struct-b-connected} for
Connected networks, and
Figures~\ref{fig:struct-a-random1}--~\ref{fig:struct-a-random3}~and~\ref{fig:struct-b-random1}--~\ref{fig:struct-b-random3} for
Random networks.

\section*{Task 2: Greedy Structure Search}

In this section, we discuss the implementation and results of our
local greedy structure search algorithm.

\subsection*{Structure-search Implementation Details}

In planning our structure-search implementation, we made the
observation that all our search algorithms worked via a process of
iterative refinement: at any given point there is a single ``current
network structure,'' which may be paired with a ``best known
operator'' (if one has been found). Given the potential difficulty and
inefficiency of creating deep copies of the provided BayesNet objects,
we decided to implement our structure search based on a paradigm where
there was a single ``working copy'' of the BayesNet object, which
could be temporarily transformed in order to determine the score which
would result from various strucure-search operators.

To this end, we decided to implement a BNOp (Bayes Net Operation)
object class which could be used to represent any given operation.
When created, a BNOp object specifies the structure-operator (add,
delete, reverse), a source node, and a target node. We also
implemented an operator-validity test method which, given a current
network structure, evaluates the legality of the network which would
result from the application of a given BNOp.

In order to test operation validity without actually modifying the
network structure, we introduced a couple of concepts of
node-relationship: Ancestors and GrandAncestors. $A$ is an Ancestor of
$B$ if there is a directed route from $A$ to $B$. $A$ is a
GrandAncestor of $B$ iff there is a directed route from $A$ to $B$
which contains more than one edge\footnote{I.e. regardless of whether
$A$ is a \textit{direct} parent of $B$, is $A$ an \textit{indirect}
ancestor of $B$?}.

Operation validity was determined as follows. Any existing graph edge
could be deleted\footnote{delete($a$, $b$) is valid IFF $a$ is a
parent of $b$}. An edge could be added if both (1) it did not already
exist and (2) it did not create any directed cycles in the
graph\footnote{add($a$, $b$) is valid IFF ($a$ is not a parent of
$b$)$\wedge$($b$ is not an Ancestor of $a$)}. Any existing graph edge
could be reversed if it did not create any directed cycles in the
graph\footnote{reverse($a$, $b$) is valid IFF ($a$ is a parent of
$b$)$\wedge$($a$ is not a GrandAncestor of $b$)}. One may note that
our Reverse-edge operator is directional -- if Reverse($A$, $B$) is
valid, Reverse($B$, $A$) is never valid; we deliberately chose to make
this adjustment so there would be no redundancy among the valid
operations\footnote{Redundancy among the structure-search operations
causes wasted work when one is exhaustively calculating the scores of
all operations. Given that scoring is relatively slow, we decided to
optimize by scoring each reversal only once. Note that this
optimization is functionally equivalent to the non-optimized form,
aside from reducing the probability of randomly selecting a Reverse
operation.}.

It can be shown that this formulation of operation validity is closed
over the set of legal network structures. (I.e., given a legal network
structure, one cannot generate a nonlegal network from the application
of BNOps which meet the above conditions for validity.)

Finally, we implemented an apply/unroll mechanism for BNOps, such that
they could be applied (and optionally later unrolled in the order of
original application) to a given BayesNet object. Thus, given a
current network structure, the BIC score of a given BNOp $X$ could be
calculated idempotently by applying $X$, calculating the MLE-based BIC
score, and then unrolling $X$.

With this framework of Bayes Net operations, it is straightforward to
implement the greedy structure search algorithm. We begin with one of
the initial networks described in Task 1. At each step, we generate
all possible valid operations, compute the CPT values that best fit
the data using maximum likelihood estimation, and determine the BIC
score. We choose the operation that leads to the highest BIC score;
ties are broken randomly. If this operation improves the BIC score, it
is applied and the process is repeated; if no operation leads to a
better BIC score, we have reached a local maximum, and stop.

Note that the random tiebreaking process means that even with the same
initial network, running the greedy structure search algorithm can
lead to two different final networks. Indeed, even though the
randomization happens only when breaking a tie, the final BIC score
can be different since the different resulting networks can lead down
different paths of operations. We did not, however, observe any
nondeterministic results given a nonrandom initialization method;
repeating the procedure with the same initialization method gave the
same results\footnote{Accordingly, we show only one set of results for
  the non-random initialization methods}. From
this we may conclude that our search process most likely did not
encounter many ties in BIC scoring. On the other hand, as is described
below, many different final networks are
possible when starting from a random initial network.
% XXX Mention whether we observed this?
% --> we do, described in 3rd paragraph of next section.

\subsection*{Greedy Structure Search Results}
\label{sec:greedresult}

In the case of the ``Data A'' network, where the supplied network
structure was presumably similar to that used in generating the data,
it is unsurprising that the very fastest search occurred when starting
with the given network configuration. Obviously, if one deliberately
starts out very close to a (local) maximum, it doesn't take many steps
to reach that maximum.

Aside from the above case, the fastest search was performed when
starting with an initially-unconnected network (regardless of which
dataset was used), as can be seen in Table~\ref{tab:runtimes}.
Similarly, the slowest search occurred when using the fully-connected
initialization method. These results should not be surprising either;
the dominating factor in our search times are the MLE/BIC
calculations, and these are fastest for small CPTs (as in the
fully/mostly disconnected case) and slowest for high-dimensional CPTs
(as occur in the fully-connected case). Furthermore, the
fully-connected initialization is also penalized by the fact that it
has to make $O(n^2)$ decisions about which edges to delete; it starts
with a heavily overspecified structure and must take many more steps
to reach a local maximum than in the case of an initially-unconnected
network. In the two experiments we ran, the fully-connected initial
network led to the best final structures, though it is not clear
whether this is just a property of the data sets we were considering,
or applied more generally. However, it took much longer than the other
methods to find a local maximum, so this extra computation time may not be
worthwhile.

In the case of the random initialization, we observed one of a variety
of different results each time we ran the search algorithm. This is
because the randomly-generated starting structures cause the greedy
hill-climbing search to begin at randomly selected points in the
search space, and there exist multiple local maxima towards which the
greedy search ascended. It is noteworthy that, for both networks, the
random initialization led in some cases to the same best final result
that we obtained from starting with a fully-connected
network. However, it did so much faster, requiring fewer steps and
less time to reach the local maximum. This suggests that starting from
a random initial configuration is a worthwhile approach for learning a
network structure, though the nondeterminism implies that it may be
best to run the greedy search procedure more than once on different
random networks.

\begin{table}[ptbh]
  \centering

  \caption{Runtimes for greedy search}
  \label{tab:runtimes}
  \vspace{1em}

  \begin{tabular}{|r|c|c|c|}
    \hline
    \textbf{Initial network} & \textbf{Final BIC Score} &
    \textbf{Steps required} & \textbf{Time required (ms)} \\
    \hline
    Given & -219.493 & 1 & 135 \\
    Unconnected & -219.707  & 3 & 174 \\
    Connected & -219.493 & 4 & 407 \\
    Random (\#1) & -222.823 & 2 & 183 \\
    Random (\#2) & -219.707 & 3 & 265 \\
    Random (\#3) & -219.493 & 6 & 366 \\
    \hline
  \end{tabular}\\
  \textbf{Net A}

  \vspace{1em}

  \begin{tabular}{|r|c|c|c|}
    \hline
    \textbf{Initial network} & \textbf{Final BIC Score} &
    \textbf{Steps required} & \textbf{Time required (s)} \\
    \hline
    Given & -31563.286 & 18 & 660 \\
    Unconnected & -31551.473  & 8 & 193 \\
    Connected & -31547.159 & 25 & 1624 \\
    Random (\#1) & -31547.159 & 16 & 575 \\
    Random (\#2) & -31551.473 & 12 & 522 \\
    Random (\#3) & -31551.473 & 18 & 628 \\
    \hline
  \end{tabular}\\
  \textbf{Net B}
\end{table}

%
% STRUCTURES A
%

\begin{figure}[ptbh]
  \centering
  \includegraphics[scale=0.75]{figures/part2-neta-given-initial}
  \includegraphics[scale=0.75]{figures/part2-neta-given}
  \caption{Initial and final structures for Net A, Given initial network}
  \label{fig:struct-a-given}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \includegraphics[scale=0.75]{figures/part2-neta-unconnected-initial}
  \includegraphics[scale=0.75]{figures/part2-neta-unconnected}
  \caption{Initial and final structures for Net A, Unconnected initial network}
  \label{fig:struct-a-unconnected}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \includegraphics[scale=0.75]{figures/part2-neta-connected-initial}
  \includegraphics[scale=0.75]{figures/part2-neta-connected}
  \caption{Initial and final structures for Net A, Connected initial network}
  \label{fig:struct-a-connected}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \includegraphics[scale=0.75]{figures/part2-neta-random1-initial}
  \includegraphics[scale=0.75]{figures/part2-neta-random1}
  \caption{Initial and final structures for Net A, Random (\#1)
    initial network}
  \label{fig:struct-a-random1}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \includegraphics[scale=0.75]{figures/part2-neta-random2-initial}
  \includegraphics[scale=0.75]{figures/part2-neta-random2}
  \caption{Initial and final structures for Net A, Random (\#2)
    initial network}
  \label{fig:struct-a-random2}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \includegraphics[scale=0.75]{figures/part2-neta-random3-initial}
  \includegraphics[scale=0.75]{figures/part2-neta-random3}
  \caption{Initial and final structures for Net A, Random (\#3)
    initial network}
  \label{fig:struct-a-random3}
\end{figure}


%
% CPTS A
%

\begin{figure}[ptbh]
  \centering
  \input{figures/part2-neta-given}
  \caption{Learned CPTs for Net A, Given initial network}
  \label{fig:cpt-a-given}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \input{figures/part2-neta-unconnected}
  \caption{Learned CPTs for Net A, Unconnected initial network}
  \label{fig:cpt-a-unconnected}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \input{figures/part2-neta-connected}
  \caption{Learned CPTs for Net A, Connected initial network}
  \label{fig:cpt-a-connected}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \input{figures/part2-neta-random1}
  \caption{Learned CPTs for Net A, Random (\#1) initial network}
  \label{fig:cpt-a-random1}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \input{figures/part2-neta-random2}
  \caption{Learned CPTs for Net A, Random (\#2) initial network}
  \label{fig:cpt-a-random2}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \input{figures/part2-neta-random3}
  \caption{Learned CPTs for Net A, Random (\#3) initial network}
  \label{fig:cpt-a-random3}
\end{figure}

% Throw a newpage in here to keep LaTeX happy. Who knew that you could
% have too many floats in a row?
%\newpage

%
% STRUCTURES B
%

\begin{figure}[ptbh]
  \centering
  \includegraphics[scale=0.75]{figures/part2-netb-given-initial}
  \includegraphics[scale=0.75]{figures/part2-netb-given}
  \caption{Initial and final structures for Net B, Given initial network}
  \label{fig:struct-b-given}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \includegraphics[scale=0.75]{figures/part2-netb-unconnected-initial}
  \includegraphics[scale=0.75]{figures/part2-netb-unconnected}
  \caption{Initial and final structures for Net B, Unconnected initial network}
  \label{fig:struct-b-unconnected}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \includegraphics[scale=0.75]{figures/part2-netb-connected-initial}
  \includegraphics[scale=0.75]{figures/part2-netb-connected}
  \caption{Initial and final structures for Net B, Connected initial network}
  \label{fig:struct-b-connected}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \includegraphics[scale=0.75]{figures/part2-netb-random1-initial}
  \includegraphics[scale=0.75]{figures/part2-netb-random1}
  \caption{Initial and final structures for Net B, Random (\#1)
    initial network}
  \label{fig:struct-b-random1}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \includegraphics[scale=0.75]{figures/part2-netb-random2-initial}
  \includegraphics[scale=0.75]{figures/part2-netb-random2}
  \caption{Initial and final structures for Net B, Random (\#2)
    initial network}
  \label{fig:struct-b-random2}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \includegraphics[scale=0.75]{figures/part2-netb-random3-initial}
  \includegraphics[scale=0.75]{figures/part2-netb-random3}
  \caption{Initial and final structures for Net B, Random (\#3)
    initial network}
  \label{fig:struct-b-random3}
\end{figure}

% \-\\
%\newpage
% 
% CPTS B
%

\begin{figure}[ptbh]
  \centering
  \input{figures/part2-netb-given}
  \caption{Learned CPTs for Net B, Given initial network}
  \label{fig:cpt-b-given}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \input{figures/part2-netb-unconnected}
  \caption{Learned CPTs for Net B, Unconnected initial network}
  \label{fig:cpt-b-unconnected}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \input{figures/part2-netb-connected}
  \caption{Learned CPTs for Net B, Connected initial network}
  \label{fig:cpt-b-connected}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \input{figures/part2-netb-random1}
  \caption{Learned CPTs for Net B, Random (\#1) initial network}
  \label{fig:cpt-b-random1}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \input{figures/part2-netb-random2}
  \caption{Learned CPTs for Net B, Random (\#2) initial network}
  \label{fig:cpt-b-random2}
\end{figure}

\begin{figure}[ptbh]
  \centering
  \input{figures/part2-netb-random3}
  \caption{Learned CPTs for Net B, Random (\#3) initial network}
  \label{fig:cpt-b-random3}
\end{figure}


\end{document}
