\subsubsection{Basic Queries\label{Discuss2a}}

Results from the suggested \textit{Insurance}-network queries can be
found in table \ref{Task2aResults}.

One might imagine that in an insurance claim, knowing the car was a
luxury vehicle might shift the probable property costs uniformly
higher (due to effects on the probable outcomes of CarValue,
ThisCarDam, and Accident). However, the network reports that this is
not the case --- the property costs merely shift away from the
low-to-mid-range (tens of thousands of dollars) into the lower and
higher cost ranges. In fact, it makes the likelihood of millions of
dollars in property damage grow by a factor of 1.5. Given these
results, one might wonder if young drivers are less likely to be
moderately-reckless when driving an especially expensive car: either
they're fairly careful, or completely throw caution to the wind.

From an inspection of the \textit{Insurance} graph, one might imagine
that knowing the driver is a good student might not have a great deal
of effect on the probable property costs. In particular, the
GoodStudent node has no descendants and only two ancestors; the value
of one of GoodStudent's ancestors (Age) is known, and is the sole
parent of GoodStudent's other ancestor (Age $\rightarrow$ SocioEcon
$\rightarrow$ GoodStudent)). The network supports this insight, as the
query results change only very slightly with the addition of
GoodStudent to the query evidence.

\begin{table}
\begin{center}
\begin{tabular}{|l|l|}
\hline
\multicolumn{2}{|c|}{\textit{P(PropCost $|$ Age = Adolescent, Airbag =
    False, Mileage = TwentyThou,}} \\
\multicolumn{2}{|l|}{\hspace{6em} \textit{MakeModel = Luxury)}} \\
\hline\hline
Thousand    & 0.5220516748791952  \\
\hline
TenThou     & 0.26169185473341977 \\
\hline
HundredThou & 0.1839241319496738  \\
\hline
Million     & 0.03233233843771127 \\
\hline
\end{tabular}

\begin{tabular}{|l|l|}
\hline
\multicolumn{2}{|c|}{\textit{P(PropCost $|$ Age = Adolescent, Airbag =
    False, Mileage = TwentyThou,}} \\
\multicolumn{2}{|l|}{\hspace{6em} \textit{GoodStudent = True)}} \\
\hline\hline
Thousand    & 0.5004883507298429 \\
\hline
TenThou     & 0.33851209276039584 \\
\hline
HundredThou & 0.1394412996694684 \\
\hline
Million     & 0.021558256840292778 \\
\hline
\end{tabular}
\end{center}
\caption{\label{Task2aResults}Results of Variable Elimination Queries:
Task 2(a)}
\end{table}

\subsubsection{Random Elimination Orderings\label{VErandom}}

We ran the Variable Elimination solver with a random-elimination-order
mechanism against the four queries from task 2; histograms of the
solver runtimes are plotted in Figures \ref{Hist21}-\ref{Hist24}.
(\textbf{Note}: due to the trivial and largely-uniform nature of the
\textit{Carpo} queries, they are plotted against a \textit{linear}
timescale, while the other queries are plotted against a
\textit{logarithmic} timescale.)

As can clearly be seen in Figures \ref{Hist23}-\ref{Hist24}, the
\textit{Carpo} queries are rather trivial to solve: in over 450 trials
per query, the solver never took more than 22 ms to answer either
query. This triviality is curious --- the other VE queries tend to be
measured in \textit{seconds}. However, an examination of the relevant
nodes on the \textit{Carpo} graph makes it clear what is happening ---
all the evidence variables are d-separated from their queries, one
query variable is a prior, and the other query has only one ancestor.
Thus, the non-ancestor pruning optimization mentioned in Section
\ref{VEExperiment} causes both the suggested \textit{Carpo} queries to
reduce to a highly trimmed graph. In the $N104$ query, the largest
possible CPT is of dimension 5, and in the $N73$ query, the largest
CPT which can be generated is of dimension 1 (!). Thus, we see that
d-separation (and network structure) can have a tremendous effect on
query complexity.

The \textit{Insurance} network queries are much more subtly
structured.\footnote{Note, the rightmost (slowest) bin in each of
Figures \ref{Hist21} and \ref{Hist22} represent trials which failed to
terminate due to exhausting the heap memory available to Java.} To
begin with, our 480 trials (per query) achieved only a rough sample of
the possible elimination orderings: there were 16-17 nodes left for
elimination after graph-pruning and evidence-assertion, yielding over
$16! \approx 10^{12}$ possible elimination orderings. Also, the
inclusion of the one extra node in the GoodStudent query increases the
mean runtime by a factor of 4 (from around 15 seconds to around 60
seconds) relative to the simpler query. Finally, these histograms have
a number of local clumpings of timings which hint at some patterns
which may relate to the sizes of computed CPTs.

\subsubsection{Greedy Elimination Ordering\label{VEgreedy}}

When querying the \textit{Insurance} network with the VE solver, using
the greedy elimination-ordering mechanism was noticeably
faster\footnote{The MakeModel query took 150 $ms$ (versus a best
time of 284 $ms$ with random ordering); the GoodStudent query took
about 310 $ms$ (versus a best time of 760 $ms$ with random
ordering).} than the fastest times achieved by the random
elimination-ordering mechanism. Given the vast size of the
optimal-elimination-ordering search space, it should come as little
surprise that random orderings were unlikely to perform as well as an
ordering which employed some kind of selection heuristic.

With the much smaller elimination-ordering space of the \textit{Carpo}
queries, however, the random orderer often matched the speed of the
greedy heuristic. In the greatly reduced universe of these queries,
there is little reward for the sort of planning represented by the
greedy heuristic.

\begin{figure}
\begin{center}
\leavevmode
%% this next line determines the size of the figure!
\epsfysize=3.5in
\epsfbox{matlab/ve_elim_random_2_1.eps}
\end{center}
\caption{\label{Hist21}Logarithmic runtimes of VE solver with random
 elimination-ordering: \textit{P(PropCost $|$ Age = Adolescent, Airbag
 = False, Mileage = TwentyThou, MakeModel = Luxury)}}
\end{figure}

\begin{figure}
\begin{center}
\leavevmode
%% this next line determines the size of the figure!
\epsfysize=3.5in
\epsfbox{matlab/ve_elim_random_2_2.eps}
\end{center}
\caption{\label{Hist22}Logarithmic runtimes of VE solver with random
 elimination-ordering, query \textit{P(PropCost $|$ Age = Adolescent,
 Airbag = False, Mileage = TwentyThou, GoodStudent = True)}}
\end{figure}

\begin{figure}
\begin{center}
\leavevmode
%% this next line determines the size of the figure!
\epsfysize=3.5in
\epsfbox{matlab/ve_elim_random_2_3.eps}
\end{center}
\caption{\label{Hist23}Runtimes of VE solver with random
 elimination-ordering, query $P(N$104 $|$ $N$41 = ``2'', $N$84 =
 ``1'', $N$116 = ``0'')}
\end{figure}

\begin{figure}
\begin{center}
\leavevmode
%% this next line determines the size of the figure!
\epsfysize=3.5in
\epsfbox{matlab/ve_elim_random_2_4.eps}
\end{center}
\caption{\label{Hist24}Runtimes of VE solver with random
 elimination-ordering, query $P(N$73 $|$ $N$152 = ``1'', $N$116 =
 ``0'', $N$43 = ``1'') }
\end{figure}