We implemented both likelihood weighting and Gibbs sampling
techniques. To evaluate their effectiveness, we first investigated the
burn-in time for Gibbs sampling: the number of initial samples that
must be discarded before reaching the stationary distribution. We then
used this information when comparing the quality of likelihood
weighting and Gibbs sampling to the exact solution, for various
numbers of samples.

\subsection{Gibbs Sampling Burn-In Time}
\label{sec:gibbs-burnin}

The Gibbs sampling algorithm begins with a random sample that ignores
the evidence, and so requires some time for the Markov chain to
converge to its stationary distribution. Hence, the earliest samples
generated are not likely to be accurate, and we can expect that
discarding them will improve the overall accuracy of the algorithm.

To test this hypothesis, we experimented with the fraction of samples
that would be discarded. We ran experiments where 10,000 samples were
taken, and an initial prefix was discarded. Note that this means the
number of samples actually used decreases as the prefix length
increases. We tested the Gibbs sampler with varying prefix lengths on
queries in the Burglary (Figure~\ref{fig:burnin-burglary}), Insurance
(Figure~\ref{fig:burnin-insurance}), and Carpo
(Figure~\ref{fig:burnin-carpo}) networks, and plotted the
Kullback-Leibler divergence relative to the exact distribution. Each
experiment was repeated five times, and the mean and standard
deviation are shown.

\begin{figure}[tbhp]
  \centering
  \input{figures/gibbs-burnin-query12}
  \caption{Result quality vs. fraction of discarded samples, Burglary network}
  \label{fig:burnin-burglary}
\end{figure}

\begin{figure}[tbhp]
  \centering
  \input{figures/gibbs-burnin-query21}
  \caption{Result quality vs. fraction of discarded samples, Insurance network}
  \label{fig:burnin-insurance}
\end{figure}

\begin{figure}[tbhp]
  \centering
  \input{figures/gibbs-burnin-query24}
  \caption{Result quality vs. fraction of discarded samples, Carpo network}
  \label{fig:burnin-carpo}
\end{figure}

The Burglary and Carpo networks do not give interesting results: the
divergence remains very low with little variation until the burn-in
time is increased to a large fraction (0.7 or greater). This suggests
that the samples quickly converge to the stationary distribution; then
there are so few samples from before the Markov chain has converged
that they are easily outweighed by the rest of the sample, and so
discarding them has little effect. It isn't surprising that this is
the case for the Burglary and Carpo networks, since these are very
simple queries. The Burglary network is quite small, so only a few
passes will be required before all the nodes have been sampled from a
distribution that takes the evidence into account. The queries in the
Carpo network are independent of the evidence, which means both that
much of the network can be ignored, and that sampling is from the
prior distribution so there is effectively no mixing time. Finally, we
observe that with a very large fraction of samples discarded, the
divergence increases, as well as its variation between experiments ---
this is also no surprise, since the distribution is now being computed
from a smaller number of samples, increasing the error.

The Insurance network query (Figure~\ref{fig:burnin-insurance})
displays the expected pattern: if few or no samples are discarded, the
initial samples introduce error into the sampled distribution, and if
too many samples are discarded, the error increases because the
effective sample size is shrinking. The minimum error occurs somewhere
in the middle. For this query, the graph shows that discarding the
first 0.4 fraction of the samples gives the best results; the other
Insurance queries (not shown) agree with this result. There is quite a
bit of noise in the data, perhaps due to the influence that the random
starting positions have on the Markov chain's trajectory.

\subsection{Quality of Approximate Inference}
\label{sec:sampling-quality}

To evaluate the quality of these inference algorithms, we tested them
on four queries:

\begin{align*}
  \mathbf{(1)} \qquad & \text{Insurance network:} &P(PropCost | Age=Adolescent,
  Airbag=False,\\ & & Mileage=TwentyThou, MakeModel=Luxury) \\
  \mathbf{(2)} \qquad & \text{Insurance network:} & P(PropCost | Age=Adolescent,
  Airbag=False, \\ & & Mileage=TwentyThou, GoodStudent=True) \\
  \mathbf{(3)} \qquad & \text{Carpo network:} & P(N104|N41=2, N84=1, N116=0) \\
  \mathbf{(4)} \qquad & \text{Carpo network:} & P(N73|N152=1, N116=0, N43=1) 
\end{align*}

For each query, we ran both likelihood weighting and Gibbs sampling
with varying numbers of samples, and plotted the Kullback-Leibler
divergence of the sampled distribution relative to the exact
distribution. For Gibbs sampling, an initial prefix of 0.4 times the
number of samples was discarded for the burnin period, as per our
results in Section~\ref{sec:gibbs-burnin}. Likelihood weighting
results are shown in
Figures~\ref{fig:qual-lw-1},~\ref{fig:qual-lw-2},~\ref{fig:qual-lw-3},~and~\ref{fig:qual-lw-4}
(at the top of each page); Gibbs sampling results are shown in
Figures~\ref{fig:qual-gibbs-1},~\ref{fig:qual-gibbs-2},~\ref{fig:qual-gibbs-3},~and~\ref{fig:qual-gibbs-4}
(at the bottom of each page). Each experiment was performed ten times;
the individual experiment curves are shown on the left graph, and the
mean and standard deviation are plotted on the right graph.

To put the number of samples in context, we compared the runtime of
the variable elimination algorithm with the time taken for each
sample. Table~\ref{tab:sampling-runtime} shows the results. For VE,
the greedy elimination order was used, as it gave the best
performance.\footnote{Note that the runtimes for greedy VE in this
  experiment may differ from those presented in
  Section~\ref{VEAnalysis}, as they were performed on a different test
  system.} From this, we find that on the order of 500 LW samples or
5000 Gibbs samples can be performed in the same time as VE for the
Insurance network queries; for the Carpo network queries, these
numbers are approximately 250 and 2500 respectively. The tenfold
increase in sampling speed for the Gibbs sampler relative to LW comes
from the fact that the LW sampler must evaluate and resample the
entire network for each sample, while the Gibbs sample only needs to
resample one node. The Insurance network contains 27 nodes, so an
order of magnitude increase in runtime for the LW sampler is expected;
we see only a $\approx$10-fold rather 27-fold increase because the
Gibbs sampler must evaluate all the children of the selected node in
addition to the node itself.

\begin{table}[htbp]
  \centering
  \begin{tabular}{|c|ccc|}
    \hline
    \textbf{Query} & \textbf{VE runtime} & \textbf{LW time/sample} &
    \textbf{Gibbs time/sample} \\
    \hline
    1 & 149 & 0.479 & 0.0365 \\
    2 & 271 & 0.515 & 0.0397 \\
    3 & 35 & 0.151 & 0.0131 \\
    4 & 14 & 0.058 & 0.0062 \\
    \hline
  \end{tabular}
  \caption{Runtimes of sampling and VE algorithms (all times in ms)}
  \label{tab:sampling-runtime}
\end{table}

Comparing Figures~\ref{fig:qual-lw-1}--\ref{fig:qual-gibbs-2}, we gain
some insight about whether likelihood weighting or Gibbs sampling is
preferable for different kinds of queries in the Insurance network. In
query 1, Gibbs sampling is clearly preferable: with as low as 200
samples, the average KL divergence is below 5; likelihood weighting
requires 500-1000 samples to reach this level (which takes many times
longer). This means that likelihood weighting has little or no
utility for this query, since in the time required to perform 500 LW
samples, the exact solution could be computed with variable
elimination. Inspecting the network, we can see why this query is a
poor candidate for likelihood weighting: the evidence combination of
$Age = Adolescent$ and $MakeModel = Luxury$ is rare, so most samples
generated will have low weights, and there will be a large amount of
error unless many samples are used. Gibbs sampling does not have this
problem.

For query 2, likelihood weighting performs better than Gibbs
sampling. Likelihood weighting gives a divergence slightly greater than 5 with
only 20 samples, and below 1 when more than 40 samples are used. Gibbs
sampling gives reasonable results when 1000 or more samples are used
(KL divergence of about 5 with 1000 samples and less than 2 for
more than 4000). However, these results are still inferior in quality than
those from likelihood weighting, and they require more time. In
addition, Gibbs sampling has a higher variance of divergence: even
when repeating the experiment with the same number of samples, it is
possible to have an unlucky run that gives a large error. Likelihood
weighting shows much less variance. This query is well-suited for
likelihood weighting, since most of the evidence variables ($Age =
Adolescent$, $Mileage=TwentyThou$, $GoodStudent=True$) are located
near the top of the graph, so forcing them to take their observed
values does not greatly impact the particle weight.

The Carpo queries (3 and 4) are quite a different case because the query
variables are $d$-separated from the evidence variables. Hence, we are
effectively sampling the query values from the prior
distribution. Both sampling algorithms give very good results for such
queries. Likelihood weighting works well because the query variables
are near the top of the network --- the query variable in query 3 has
only one ancestor, and the variable in query 4 has none at all!
Indeed, for query 3 likelihood weighting will give a KL divergence of
0.5 with as few as 10 samples, and a divergence below 0.1 with 100 or
more; Gibbs sampling gives a KL divergence below 0.5 with 200 samples,
and below 0.1 with 1000 samples. For query 4, the results are even
better: a divergence below 0.05 can be obtained with as few as 10 LW
samples or 100 Gibbs samples. We can conclude that queries of this
sort can be sampled very accurately without much effort --- but this
is not a particularly interesting result since the queries are so
simple, with a graph in which most of the nodes can be
ignored. Moreover, the ultimate value of sampling may be limited,
since the exact solution to these queries can be computed in less than
50 ms by variable elimination.

A final observation is that the standard deviation of the divergences
can be quite high when the number of sample is small, especially for
Gibbs sampling. In particular, looking at the graphs of individual
runs in Figures~\ref{fig:qual-gibbs-1}~and~\ref{fig:qual-gibbs-2}, we
see that some of the runs give high-quality results, while there are
some outliers with very large errors. Hence, running Gibbs sampling
with few samples may a good result or a terrible one ---
unfortunately, one cannot tell which. This suggests that if few
samples are performed, repeating the experiment multiple times and
taking the average (or otherwise eliminating outliers) might be useful
to give a better guarantee of a good result. (Of course, this
increases runtime, so it would need to be compared against simply
taking more samples in one experiment.)

\begin{landscape}
  \begin{figure}[H]
    \centering
    \begin{minipage}{4in}
      \input{figures/lw-quality-query21}
    \end{minipage}
    \begin{minipage}{4in}
      \input{figures/lw-quality-query21-agg}
    \end{minipage}
    \caption{Divergence vs number of samples for LW sampling, query 1}
    \label{fig:qual-lw-1}
  \end{figure}

  \begin{figure}[H]
    \centering
    \begin{minipage}{4in}
      \input{figures/gibbs-quality-query21}
    \end{minipage}
    \begin{minipage}{4in}
      \input{figures/gibbs-quality-query21-agg}
    \end{minipage}
    \caption{Divergence vs number of samples for Gibbs sampling, query 1}
    \label{fig:qual-gibbs-1}
  \end{figure}
\end{landscape}

\begin{landscape}
  \begin{figure}[H]
    \centering
    \begin{minipage}{4in}
      \input{figures/lw-quality-query22}
    \end{minipage}
    \begin{minipage}{4in}
      \input{figures/lw-quality-query22-agg}
    \end{minipage}
    \caption{Divergence vs number of samples for LW sampling, query 2}
    \label{fig:qual-lw-2}
  \end{figure}

  \begin{figure}[H]
    \centering
    \begin{minipage}{4in}
      \input{figures/gibbs-quality-query22}
    \end{minipage}
    \begin{minipage}{4in}
      \input{figures/gibbs-quality-query22-agg}
    \end{minipage}
    \caption{Divergence vs number of samples for Gibbs sampling, query 2}
    \label{fig:qual-gibbs-2}
  \end{figure}
\end{landscape}

\begin{landscape}
  \begin{figure}[H]
    \centering
    \begin{minipage}{4in}
      \input{figures/lw-quality-query23}
    \end{minipage}
    \begin{minipage}{4in}
      \input{figures/lw-quality-query23-agg}
    \end{minipage}
    \caption{Divergence vs number of samples for LW sampling, query 3}
    \label{fig:qual-lw-3}
  \end{figure}

  \begin{figure}[H]
    \centering
    \begin{minipage}{4in}
      \input{figures/gibbs-quality-query23}
    \end{minipage}
    \begin{minipage}{4in}
      \input{figures/gibbs-quality-query23-agg}
    \end{minipage}
    \caption{Divergence vs number of samples for Gibbs sampling, query 3}
    \label{fig:qual-gibbs-3}
  \end{figure}
\end{landscape}

\begin{landscape}
  \begin{figure}[H]
    \centering
    \begin{minipage}{4in}
      \input{figures/lw-quality-query24}
    \end{minipage}
    \begin{minipage}{4in}
      \input{figures/lw-quality-query24-agg}
    \end{minipage}
    \caption{Divergence vs number of samples for LW sampling, query 4}
    \label{fig:qual-lw-4}
  \end{figure}

  \begin{figure}[H]
    \centering
    \begin{minipage}{4in}
      \input{figures/gibbs-quality-query24}
    \end{minipage}
    \begin{minipage}{4in}
      \input{figures/gibbs-quality-query24-agg}
    \end{minipage}
    \caption{Divergence vs number of samples for Gibbs sampling, query 4}
    \label{fig:qual-gibbs-4}
  \end{figure}
\end{landscape}


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