This project explores the use of a variety of Bayesian network
inference algorithms. We implemented a couple of heuristic variants of
an exact algorithm (variable elimination) and two different
approximate inference algorithms (likelihood weighting and Gibbs
sampling). These implementations were used to compare the accuracy and
performance of these algorithms under a variety of conditions.

In the case of the variable elimination algorithm, the heuristics we
implemented were randomized elimination ordering and greedy
elimination ordering. A number of trials were run performing the
suggested queries with each of these variants; the relative
experimental performance of these heuristics are explored in Sections
\ref{VEData} and \ref{VEAnalysis}.

The approximate inference algorithms were run in a series of
experiments using a range of different operational parameters,
comparing their accuracy to results obtained using exact methods. This
allowed us to determine what level of accuracy can be obtained from
the algorithms given a particular number of samples. We compare the
effectiveness of likelihood weighting and Gibbs sampling on four
queries in two different networks, and examine how the structure of
the network and query affects the appropriate choice of algorithm. We
also compare the runtime of the sampling algorithms to that of finding
the exact solution with variable elimination, to understand what level
of quality can be obtained from sampling algorithms in less time than
finding the exact solution.

Our experimental results and analysis are presented as follows:

Section \ref{VE} discusses our work with variable elimination, and the
initial data we obtained (\S \ref{VEData}). There, we explore the
subtle differences between some query results (\S \ref{Discuss2a}),
analyze the performance of random elimination-ordering (\S
\ref{VErandom}), and compare random elimination with a greedy
elimination-ordering heuristic (\S \ref{VEgreedy}).

In Section \ref{Sampling}, we evaluate the likelihood weighting and
Gibbs sampling solvers. We first experiment with the number of samples
that should be discarded during the burn-in period of Gibbs sampling
(\S \ref{sec:gibbs-burnin}), and then use this to compare the result
quality and runtime of likelihood weighting and Gibbs sampling for
different numbers of samples (\S \ref{sec:sampling-quality}).

Finally, Section \ref{Conclusion} gives a summary of our work on this
project.

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "report"
%%% End: