\subsection{Parameter Estimation} We began by implementing maximum likelihood estimation to determine CPT parameters, for a given network structure. We initially did so by computing each entry in the CPT as the observed number of samples satisfying both the appropriate assignment to the node and its parents, divided by the number of samples satisfying the appropriate assignment to the parents. We later refined this by adding the Laplacian correction to provide a prior estimation of the probability of node values that depend on parent assignments that never occur in the data. The Bayes'-net parameters for the provided dataset B, given the provided network graph, were estimated by our Parameter Estimation implementation to be: \input{estBcpts.tex} \subsection{Structure Scoring Metrics} Bayes' Net learning involves the comparison of various possible Bayes' Network graph structures. As such, a scoring metric is required; we experimented with both the Bayesian Information Criterion (BIC) and the Akaike Information Criterion (AIC). These scoring mechanisms are discussed in the following sections. \subsubsection{The Bayesian Information Criterion} We used the Bayesian Information Criterion (BIC) as a basis for evaluating the quality of network structures. The BIC is defined as follows: \begin{equation} \label{eq:bic} \textsf{BIC}(G:D) = \ell\left(\hat{\theta}_G : D\right) - \frac{\log_2 M}{2} \text{Dim}[G] \end{equation} The BIC score consists of the log-likelihood of the data given the MLE estimation, reduced by a structural penalty of $\frac{\log_2 M}{2} \text{Dim}[G]$, where $\text{Dim}[G]$ is the dimension of the network. The network dimension is the number of parameters required to specify the CPTs in the network: the sum over all nodes of the number of possible assignments for the parents (number of rows in the CPT) multiplied by the number of possible assignments minus 1 (number of columns in the CPT). We subtract 1 from the number of columns in the CPT because we use the observation that the last column can be derived from the other ones. The effect of this structure penalty is to prefer graphs with less connections, since the resulting networks are more efficient to work with and avoid overfitting the data. Here are the components of the BIC score we calcuated for our parameter estimation of dataset ``B'' given the provided network graph: \begin{tabular}{r|c|c|} \cline{2-3} $\log_2$-Likelihood & $l(\hat{\theta}_G : D)$ & -34285.24 \\ \cline{2-3} Structural Penalty & $\frac{\log_2M}{2}$Dim$[G]$ & 98.30 \\ \cline{2-3} BIC Score & $S(G : D)$ & -34383.54 \\ \cline{2-3} \end{tabular} In the above, the magnitude of the log-likelihood of our data (given the graph) is much larger than was computed for dataset ``A'', but this is due to the greater number of data points. This difference in magnitude may be plausibly explained as follows: If one makes the (unreasonable) assumption that all 5000 samples in dataset ``B'' were equally likely, then they each have probability $2^{-34285/5000} \approx 0.0086$. Given that dataset ``B'' has 8 variables, there are $2^8 = 256$ possible combinations of node values. If every possible outcome were equally likely, they would each have probability $2^{-8} \approx 0.0039$, which is not so different from the ``average'' likelihood achieved by our fit to the data. Thus, it's reasonable that such a large log-likelihood does not necessarily indicate a poor fit. However, as we will see in Section~\ref{sec:greedresult}, this is a relatively poor score. In particular, none of our Data-B search attempts achieved a BIC score worse than -31653. Additionally, the BIC scores we achieved through structure search all had standard deviations smaller than 19, suggesting that a score difference of 2600 points is a rather significant difference in fit for this data. \subsubsection{The Akaike Information Criterion} We chose to also implement the Akaike Information Criterion\footnote{Akaike, H. (1974). A new look at statistical model identification. Transaction on Automatic Control 19,716-723.} (AIC) for comparison with BIC. The AIC metric seemed appropriate for our purposes, as it has been widely cited in comparison with the BIC metric for use in scoring Bayes networks.\footnote{See, e.g. \url{http://www.cs.cmu.edu/~awm/15781/slides/Param_Struct_Learning05v1.pdf}} The AIC is calculated very similarly to the BIC: \begin{equation} \label{eq:aic} \textsf{AIC}(G:D) = \ell\left(\hat{\theta}_G : D\right) - \text{Dim}[G] \end{equation} That is, the AIC score of a particular graph structure is the log likelihood of the data under the current estimation of parameters for the graph, minus a structure penalty given simply by the dimension of the graph. This is identical to the BIC score, except that the AIC structure penalty does not have a factor of $\frac{\log_2 M}{2}$. Hence, the AIC score does not penalize the complexity of the network structure as much as the BIC score, particularly for very large data sets. As a result, we expect structure search based on the AIC metric to produce networks with more dependencies than if the BIC network is used. Though the resulting networks may produce higher likelihood of the data, they do so at the cost of a more complex network: this is undesirable both because the more complex network requires a longer description and leads to increased runtime for inference algorithms, and because it can overfit the data. As we describe in Section~\ref{sec:struct-scor-results}, we did indeed observe more complex networks when performing structure search using the AIC metric. \subsection{Structure Scoring Results and Comparison} \label{sec:struct-scor-results} Overall, we observed that AIC tends to yield more complex graphs than those found when using BIC scoring. Qualitatively, we observed that the graphs resulting from AIC are much more highly connected than those resulting from BIC. Quantitatively, one can observe this difference in ``graph complexity'' by comparing the dimension of the graphs resulting from use of both scoring metrics. To better compare our various search and scoring options, we performed the following experiment: for each of the datasets under consideration (``A'' and ``B''), we generated 200 randomly-connected initial graph structures. We then separately applied Greedy+AIC, Greedy+BIC, First-Ascent+AIC, and First-Ascent+BIC to each of these initial graph structures, recording various details about each application of all these search variants. As can be seen in Table~\ref{tab:scoredim}, the dimension of graphs produced from the above experiment vary consistently between AIC and BIC. In particular, the average dimension yielded by all the AIC data/search combinations are consistently larger than those found with BIC; similarly, the standard deviations of the graph dimension are larger for AIC than BIC. Most tellingly, in all but one case, the smallest graph dimension yielded by AIC is larger than the largest graph dimension yielded by BIC\footnote{Furthermore, in each case, the mean BIC dimension is at least 2.7 of AIC's standard devs below the mean AIC; by Chebyshev's Theorem, we have (as a lower bound) that at least $1-\frac{1}{2.7^2} \approx 86\%$ of AIC's dimensions are larger than the average BIC dimension.}. Thus, the bulk of the graphs produced by AIC have a higher dimension than any of the graphs produced when using BIC. One may also compare the runtime of the various searches, and the number of search steps taken before finding a result in each case. On average, AIC also takes more time to yield a result, and uses more search steps, than BIC (as can be seen in Table~\ref{tab:scoretime}). This is because it requires more steps to build up the complex resulting structures: AIC will continue to add new edges to the graph beyond the point at which the BIC algorithm concludes that additional edges do not provide enough of a likelihood improvement to offset the increased complexity of the structure, and considering and applying the new edges requires time. From these comparisons, one might conclude that AIC tends to overfit the given data, by producing Bayes' Net structures which are unjustifiably complex. Furthermore, searching with AIC suffers the additional cost of slightly lower efficiency than when using BIC. In contrast, on the datasets under consideration, BIC tends to produce relatively streamlined graphs; it seems likely that the structures found by BIC provide more useful approximations of the underlying Bayesian relationships which generated the data in the first place. %% This is crying out for a graph. No time. \begin{table}[ptbh] \centering \caption{Resulting graph dimensions, AIC vs. BIC} \label{tab:scoredim} \vspace{1em} \begin{tabular}{|l||c|c|c|c||c|c|c|c|} \hline & \multicolumn{4}{c||}{\textbf{AIC} dim} & \multicolumn{4}{c|}{\textbf{BIC} dim} \\ & $\mu$ & $\sigma$ & min & max & $\mu$ & $\sigma$ & min & max\\ \hline \hline \textbf{Data A, First-Ascent} & 8.674 & 0.469 & 8.000 & 9.000 & 7 & 0 & 7.000 & 7.000 \\ \hline \textbf{Data A, Greedy} & 8.421 & 0.494 & 8.000 & 9.000 & 7 & 0 & 7.000 & 7.000 \\ \hline \textbf{Data B, First-Ascent} & 51.768 & 11.264 & 28.000 & 82.000 & 21.311 & 2.239 & 19.000 & 36.000 \\ \hline \textbf{Data B, Greedy} & 51.953 & 10.768 & 31.000 & 80.000 & 20.647 & 1.226 & 19.000 & 24.000 \\ \hline \end{tabular} \end{table} \begin{table}[ptbh] \centering \caption{Runtime and search steps, AIC vs. BIC} \label{tab:scoretime} \vspace{1em} \begin{tabular}{|l||c|c||c|c|} \hline & \multicolumn{2}{c||}{\textbf{AIC}} & \multicolumn{2}{c|}{\textbf{BIC}} \\ & $\mu_{time}$ & $\mu_{steps}$ & $\mu_{time}$ & $\mu_{steps}$ \\ \hline \hline \textbf{Data A, First-Ascent} & 40.922 & 5.118 & 36.049 & 4.755 \\ \hline \textbf{Data A, Greedy} & 71.049 & 4.029 & 69.127 & 3.794 \\ \hline \textbf{Data B, First-Ascent} & 34920.358 & 24.907 & 27181.069 & 21.539 \\ \hline \textbf{Data B, Greedy} & 93357.363 & 15.623 & 78283.201 & 14.225 \\ \hline \end{tabular} \end{table} \begin{table}[ptbh] \centering \caption{Result quality, AIC vs. BIC} \label{tab:scorequal} \vspace{1em} \begin{tabular}{|l||c|c|c|c||c|c|c|c|} \hline & \multicolumn{4}{c||}{\textbf{AIC} score} & \multicolumn{4}{c|}{\textbf{BIC} score} \\ & $\mu$ & $\sigma$ & min & max & $\mu$ & $\sigma$ & min & max\\ \hline \hline \textbf{A, FA} & -201.587 & 0.403 & -202.450 & -201.236 & -220.545 & 1.476 & -222.823 & -219.493 \\ \hline \textbf{A, Gr} & -201.391 & 0.233 & -202.450 & -201.236 & -220.692 & 1.582 & -222.823 & -219.493 \\ \hline \textbf{B, FA} & -31439.454 & 3.710 & -31450.532 & -31433.896 & -31562.090 & 18.520 & -31652.759 & -31547.159 \\ \hline \textbf{B, Gr} & -31437.906 & 3.030 & -31446.883 & -31433.836 & -31557.216 & 12.737 & -31613.307 & -31547.159 \\ \hline \end{tabular} \end{table} %%% Local Variables: %%% mode: latex %%% TeX-master: "writeup" %%% End: