\documentclass[twoside,11pt]{article}
\usepackage{jmlr2e}
\usepackage{colortbl}
\usepackage[T1]{fontenc}
\usepackage{rotating}
%\usepackage{named}
\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{float}
\usepackage{afterpage}

\newcommand{\descrsize}{\scriptsize}
\newcommand{\Int}[2]{\textstyle{\int_{#1}^{#2}}}
\newcommand{\agg}[1]{G_{#1}^{a}}
\newcommand{\sem}[1]{{\cal #1}}
\newcommand{\m}{\mc{M}}
\newcommand{\nm}{\mc{NM}}
\newcommand{\Part}[1]{\mbox{\em Part(}#1\mbox{\em )}}
\newcommand{\naiv}{na\"{i}v}
\newcommand{\naive}{na\"{i}ve }
\newcommand{\Naive}{Na\"{i}ve }

                                          %edge of page-->                |
\newtheorem{definition2}{Definition}                           %           |
%\newtheorem{theorem}{Theorem}
%\newtheorem{corollary}{Corollary}                                 %           |
%\newtheorem{lemma}{Lemma}                                     %           |
\newtheorem{result}{Result}                                   %           |
\newtheorem{postulate}{Postulate}                             %           |
\newtheorem{assumption}{Assumption}
\newtheorem{eqnsys}{System}
\newtheorem{example_thm}{Example}
\newtheorem{pre_example_thm}{Pre-example}
\newtheorem{procedure_thm}{Procedure}
\newtheorem{notation}{Notation}
\newtheorem{causal_prop}{Causality Property}
\newtheorem{question}{Question}
\newtheorem{test}{Test}
\newcommand{\denverproof}[1]{\smallskip\hfil\break{\bf Proof:~~}\em{#1}\hfill $\Box$\par}
%\newcommand{\Proof}[1]{\proof{#1}\hfill $\Box$\par}
\newcommand{\Proof}[1]{\denverproof{#1}}

%\newcommand{\example}[1]{\begin{example_thm}\hfill\break {\em #1}\hfill $\Box$\par\end{example_thm}}
\newcommand{\preexample}[1]{\begin{pre_example_thm}\hfill\break {\em #1}\hfill $\Box$\par\end{pre_example_thm}}
\newcommand{\procedure}[2]{\begin{procedure_thm}[#1]\hfill #2\end{procedure_thm}}


\newcommand{\f}[2]{\mbox{\textit{#1}\textup{(}}#2\mbox{\textup{)}}}
\newcommand{\vect}[1]{{\mbox{\boldmath $#1$}}} %\mathbf{#1}}}
\newcommand{\vectf}[2]{\mbox{{\boldmath$\mathit{#1}$}{\bf\textup{(}}$#2${\bf\textup{)}}}}
\newcommand{\mcf}[2]{\mbox{$\mc{#1}$\textup{(}}#2\mbox{\textup{)}}}
\newcommand{\notcause}{\rightarrow\hspace{-13.5pt}\scalebox{0.5}{/}\hspace{5pt}}


\newcommand{\dsep}[3]{(#1~\bot\hspace{-7pt}\bot~#2~|~#3)}
\newcommand{\indep}[3]{(#1~\bot~#2~|~#3)}

\newcommand{\pa}[1]{\vectf{\longvar{Pa}}{#1}}
\newcommand{\ch}[1]{\vectf{Ch}{#1}}
\newcommand{\fb}[1]{\vectf{Fb}{#1}}
\newcommand{\anc}[1]{\vectf{Anc}{#1}}
\newcommand{\des}[1]{\vectf{Des}{#1}}
\newcommand{\adjs}[1]{\vectf{Adj}{#1}}
\newcommand{\gammaf}[1]{\Gamma\f{}{#1}}

\newcommand{\pairs}[1]{\vectf{Pairs}{#1}}
\newcommand{\depset}[1]{\vectf{Dep}{#1}}
\newcommand{\indepset}[1]{\vectf{Indep}{#1}}
\newcommand{\deftemplate}[3]{#1\equiv\set{#2~:~#3}}


\newcommand{\pair}[2]{\langle #1,#2\rangle}
\newcommand{\triple}[3]{\langle #1,#2,#3\rangle}
\newcommand{\tuple}[1]{{\langle #1\rangle}}
%\newcommand{\equilx}{{\tilde{x}}}
%\newcommand{\equilV}{{\tilde{v}}}
\newcommand{\adj}[0]{\mbox{\bf ---}\,}

\newcommand{\manipx}{{\hat{x}}}
\newcommand{\etal}{{\em et al.} }
\newcommand{\params}[1]{\vectf{Params}{#1}}
\newcommand{\set}[1]{\{#1\}}
\newcommand{\del}{{del}}
\newcommand{\ef}[1]{e^f_{#1}}
\newcommand{\vf}[1]{v^f_{#1}}
\newcommand{\Sup}[1]{{(#1)}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\Sec}[1]{Section\,\ref{sec:#1}}
\newcommand{\give}{\mid}
\newcommand{\cp}[2]{\mbox{$\f{P}{#1~|~#2}$}}
\newcommand{\p}[1]{\f{P}{#1}}
\newcommand{\indClass}[1]{\mbox{\em IE}(#1)}
\newcommand{\V}{\vect{V}}
\newcommand{\vv}{\vect{v}}

\newcommand{\E}{\vect{E}}
\newcommand{\A}{\vect{A}}
\newcommand{\B}{\vect{B}}
\newcommand{\C}{\vect{C}}
\newcommand{\X}{\vect{X}}
\newcommand{\Y}{\vect{Y}}
\newcommand{\Z}{\vect{Z}}
\newcommand{\U}{\vect{U}}
\newcommand{\I}{\vect{I}}
\newcommand{\N}{\vect{N}}
\newcommand{\x}{\vect{x}}
\newcommand{\D}{\vect{D}}
\newcommand{\Pa}{\vect{Pa}}
\newcommand{\longvar}[1]{\mbox{\textit {#1}}}
\newcommand{\true}{\longvar{true}}
\newcommand{\false}{\longvar{false}}
\newcommand{\paramvect}{\vect{\theta}}
\newcommand{\paramvecthat}{\vect{\tilde{\theta}}}
\newcommand{\thetaij}{\vect{\theta_{ij}}}
\newcommand{\Dir}[2]{\mbox{\textup{Dir(}}#1~|~#2\mbox{\textup{)}}}
\newcommand{\Expectation}[1]{\f{E}{#1}}

\newcommand{\equilx}{{\tilde{x}}}
\newcommand{\equilV}{{\tilde{v}}}

\newcommand{\Vdel}[1]{\vectf{V\hspace{-4pt}{}_{del}}{#1}}
\newcommand{\Edel}[1]{\vectf{E_{del}}{#1}}
\newcommand{\VdelX}{\Vdel{X}}
\newcommand{\EdelX}{\Edel{X}}
\newcommand{\VequilX}{\vect{\V\hspace{-4pt}{}_\equilx}}
\newcommand{\EequilX}{\vect{\E_\equilx}}
\newcommand{\indtest}{\f{Indep-Test}{\indep{X}{Y}{\Z},~D}}
\newcommand{\bayesindtest}{\f{Bayesian-Indep-Test}{\indep{X}{Y}{\Z},~D}}
\newcommand{\chisquared}[3]{\f{Chi-Squared}{\indep{#1}{#2}{#3},~D}}
\newcommand{\range}[1]{\vectf{Rng}{#1}}
\newcommand{\bnmod}{\tuple{G,\paramvect}}
\newcommand{\argmax}{\arg\hspace{-2pt}\max}

\newcommand{\level}[1]{\f{$\pi$}{#1}}


\newcommand{\classification}[1]{\cp{\vect{X}=\vect{x}}{#1}}
\newcommand{\Ofun}[1]{\f{O}{#1}}

\newcommand{\MLiSup}[1]{\prod_{j=1}^{q_i}\frac{\gammaf{\alpha^#1_{ij}}} {\gammaf{\alpha^#1_{ij}+N^#1_{ij}}}
\cdot\prod_{k=1}^{r_i}\frac{\gammaf{\alpha^#1_{ijk}+N^#1_{ijk}}}{\gammaf{\alpha^#1_{ijk}}}}

\newcommand{\MLi}{\prod_{j=1}^{q_i}\frac{\gammaf{\alpha_{ij}}} {\gammaf{\alpha_{ij}+N_{ij}}}
\cdot\prod_{k=1}^{r_i}\frac{\gammaf{\alpha_{ijk}+N_{ijk}}}{\gammaf{\alpha_{ijk}}}}

\newcommand{\JK}{J_{\mathbf x}^S K_{\mathbf x}}%{JK}
\newcommand{\J}{J_{\mathbf x}^S}
\newcommand{\K}{K_{\mathbf x}}

\newcommand{\ML}{\prod_{i=0}^N\MLi}
\newcommand{\jk}{JK}
\newcommand{\cfun}{\rho}
\newcommand{\myclass}{{\mathcal{L}}_k^{\pi}}
\newcommand{\mc}[1]{{\mathcal{#1}}}
%\newcommand{\Lk}{\mbox{$\myclass(\pi)$}}
\newcommand{\Lk}{\mbox{$\myclass$}}
%\newcommand{\Lkn}{\mbox{$\myclass^n(\pi\give D)$}}
\newcommand{\Lkn}{{\mathcal{L}}_{kn}^{\pi}(D)}
\newcommand{\lsim}{\stackrel{<}{{}_{\,\sim}}}
\newcommand{\gsim}{\stackrel{>}{{}_{\,\sim}}}
\newcommand{\ul}[1]{\underline{#1}}

\newcommand{\spacecomplexity}{\Ofun{k \cdot {R}^k}}
\newcommand{\timecomplexity}{\Ofun{{N\choose k}\cdot N\cdot k \cdot (N_D +
{R}^k)}}
\newcommand{\KTwospacecomplexity}{\Ofun{k \cdot N_D}}
\newcommand{\KTwotimecomplexity}{\Ofun{{N\choose k}\cdot N\cdot k \cdot N_D \cdot R}}
% Heading arguments are {volume}{year}{pages}{submitted}{published}{author-full-names}

\jmlrheading{5}{2004}{1177--1203}{11/03; Revised 9/04}{9/04}{Denver Dash and Gregory F. Cooper}

% Short headings should be running head and authors last names

\ShortHeadings{Model Averaging with Discrete BNs}{Dash and Cooper}
\firstpageno{1177}
\bibpunct{(}{)}{;}{a}{,}{,}
\begin{document}

\title{Model Averaging for Prediction with Discrete Bayesian Networks}

\author{\name Denver Dash \email denver.h.dash@intel.com \\
       \addr Intel Research\\
        SC12-303\\
        3600 Juliette Lane\\
        Santa Clara, CA 95054, USA
       \AND
       \name Gregory F. Cooper \email gfc@cbmi.upmc.edu \\
       \addr Center for Biomedical Informatics\\
       University of Pittsburgh\\
       Pittsburgh, PA 15260, USA}

\editor{David Madigan}

\maketitle

%\author{Denver Dash\thanks{This work was partially
%performed during a summer internship at the Machine Learning and
%Perception group, Microsoft Research, Cambridge, UK.}\\
%Decision Systems Laboratory\\
%Intelligent Systems Program\\
%University of Pittsburgh \\
%Pittsburgh, PA 15213 \\
%\and
%Gregory F. Cooper  \\
%Center for Biomedical Informatics        \\
%University of Pittsburgh \\
%Pittsburgh, PA 15213 }
%}
%
%\maketitle
%
%
\floatstyle{plain}
\restylefloat{table}


\begin{abstract}
In this paper\footnote{This is a combined and expanded version of
previous conference and workshop papers
\citep*{dash02.icml,dash03.aistats}.} we consider the problem of
performing Bayesian model-averaging over a class of discrete
Bayesian network structures consistent with a partial ordering and
with bounded in-degree $k$. We show that for $N$ nodes this class
contains in the worst-case at least $\Omega$(${{N/2}\choose
k}^{N/2}$) distinct network structures, and yet model averaging
over these structures can be performed using $\Ofun{{N\choose
k}\cdot N}$ operations. Furthermore we show that there exists a
single Bayesian network that defines a joint distribution over the
variables that is equivalent to model averaging over these
structures. Although constructing this network is computationally
prohibitive, we show that it can be approximated by a tractable
network, allowing approximate model-averaged probability
calculations to be performed in $\Ofun{N}$ time. Our result also
leads to an exact and linear-time solution to the problem of
averaging over the $2^N$ possible feature sets in a \naive Bayes
model, providing an exact Bayesian solution to the troublesome
feature-selection problem for \naive Bayes classifiers. We
demonstrate the utility of these techniques in the context of
supervised classification, showing empirically that model
averaging consistently beats other generative
Bayesian-network-based models, even when the generating model is
not guaranteed to be a member of the class being averaged over. We
characterize the performance over several parameters on simulated
and real-world data.
\end{abstract}
\begin{keywords}
Bayesian networks, Bayesian model averaging, classification, \naive
Bayes classifiers, feature selection
\end{keywords}

\section{Introduction}
A probabilistic model $M$ over a set of variables $\X$, is a
parameterization of the joint distribution $\p{\X}$ over $\X$.
There are many practical uses for $\p{\X}$, including the ability
to calculate expectations, $E(\X)$, of configurations of
variables, the ability to calculate the {\em most likely
explanation} of some observed evidence, the ability to {\em update
beliefs} about some variables given some other variables,
$\cp{X_i,X_j}{\vect{X'}}$, etc. In short virtually any
probabilistic quantity of interest involvoing the variables $\X$
can be calculated once $\p{\X}$ is known. Bayesian networks (BNs)
\citep*[cf.,][]{pearl88} are a popular class of graphical
probabilistic models that allow $\p{\X}$ to be specified in
practice even when $|\X|$ is very large, by explicating
independence between the variables $\X$.

Many algorithms for learning BNs from data
\citep*{Verma.UAI90,cooper92,spirtes93,heckerman95,friedman97bayesianClassifiers}
have been used effectively to learn the structure of a BN model
from data, typically by performing a search over structures using
the posterior probability, $\cp{S}{D}$, of the structure given the
data as a measure of quality. While learning a particular BN
structure has shown to be useful, it suffers from the fact that a
single model makes strong independence assumptions among the
variables of interest that may not be true, or may only be
approximately true in reality. That is, the process of learning a
single network affords no way of capturing the uncertainty in the
model structure. The most principled alternative to selecting a
particular network structure, is to calculate the full joint
posterior $\cp{\X}{D}$ by averaging over all possible BN
structures. Unfortunately, the space of network structures is
super-exponential in the number of model variables, and thus an
exact method for full model-averaging is likely to be intractable.


One especially common use for learning the joint distribution from
data is {\em supervised classification}. The general supervised
classification problem seeks to create a model based on labelled
data $D$, which can be used to classify future vectors of features
$\vect{F}=\set{F_1,F_2,\ldots , F_N}$ into one of various classes
of interest.  A probabilistic model accomplishes this goal by
calculating the posterior probability, $\cp{C}{\vect{F}}$, of the
class given the features. One of the simplest probabilistic
classifiers for this task is the \naive classifier
\citep*[cf.,][]{duda73}, which, without inferring any structural
information from the database, can still perform surprisingly well
at the classification task
\citep*{domingos97,friedmanJerome97,Ng.NIPS.02}. Classification
using a single Bayesian network model and no missing
feature-vector data can be performed in $\Ofun{N}$ time. When the
feature vector is incomplete then standard algorithms (e.g.,
\citefullauthor{lauritzen88}, \citeyear{lauritzen88}) for Bayesian
network inference can be used for classification. The drawbacks of
selecting a single model for classification manifests themselves
as over-fitting of the data, leading to poor classification
accuracy on future data sets; however, model averaging has been
shown to reduce over-fitting and provide better generalization
\citep*{madigan94}.


In this paper we consider the possibility of performing exact and
approximate model-averaging (MA) over a particular class of
structures rather than over the general space of directed acyclic
graphs (DAGs).
%Recently
%\citet*{dash02.icml},
%%Dash and Cooper
%%\shortcite{dash02.icml},
%demonstrated that exact model averaging over the
%restricted class of \naive networks could be performed by a simple
%re-parameterization of a \naive network, and they showed that this
%technique consistently outperformed a single \naive classifier
%with the standard parameterization.
We show that exact model averaging over the class of BN structures
consistent with a partial ordering $\pi$ and with bounded
in-degree $k$, despite its super-exponential size, can be
performed with relatively small time and space restrictions.
% Furthermore, we show that, for multinomial BNs, a
%single DAG can be constructed that approximates the predictions of the
%full model-averaged (MA) classifier. Finally, we demonstrate with
%experimental comparisons that this single approximate MA DAG, without
%making assumptions on the generating distribution, can be used to perform
%classification for complete feature-vectors in $\Ofun{N}$ time, and we
%characterize MA performance versus that of (a) single networks learned
%from data using a greedy Bayesian learning algorithm and (b) exact MA over
%\naive classifiers.

There has been other work on making model averaging over Bayesian
network structures efficient: Methods for approximate MA
classification using both selective pruning
\citep*{madigan94,volinsky-phd-thesis} and Monte-Carlo techniques
\citep*{madigan95b} exist and have been shown to improve
performance in prediction tasks; however these methods are
approximate, and do not have the complexity guarantees that our
method possesses. \citet*{Friedman_ML2003} studied the ability to
estimate structural features of a network (for example the
probability of an arc from $X_i$ to $X_j$) by performing a MCMC
search over orderings of nodes. Their method relied on a
decomposition, which they credit to \citet*{Buntine2.UAI91}, that
we extend in order to prove our key theoretical result. We discuss
this issue in detail in
Section~\ref{sec:DAG_ma_theoretical_results}.
%
%
%
%for the posterior probability of the feature given the data, averaged over
%all structures consistent with a fixed total ordering on the nodes and
%with a bounded in-degree.
%% in closed-form the posterior
%%probability of a feature averaged over all in-degree-bounded networks
%%consistent with a fixed ordering, and their ability to average over a
%%given ordering relied on a decomposition of the posterior that is very
%%similar in form to one that we use.
Their work differs from ours in two key respects: (1) Their
approach does not capture the single-network (and thus the
efficiency of calculation) approximation to the MA problem, and
(2) They perform model averaging only to calculate the
probabilities of structural features, explicitly not for
prediction. Other work has been done
\citep*{Meila45.UAI-2000,cerquides.icml03} on performing exact
model averaging for prediction over all tree-structures in
$\Ofun{N^3}$ time. This research also uses similar assumptions and
similar decompositions used by \citet*{Friedman_ML2003} and in
this paper. Our calculation is more general in allowing nodes to
have more than one parent, but it is less general in that it
assumes a partial-ordering of the nodes.

The primary contributions in this paper are as follows: (1) we
extend the decomposition of \citet*{Buntine2.UAI91} to apply to
the task of prediction, (2) we show that MA calculations over this
class can be reproduced by a single network structure $S^*$ which,
if it can be constructed tractably, thereafter allows approximate
MA predictions to be performed using standard Bayesian network
inference, (3) we show that, for the class of \naive models,
calculation of $S^*$ (including parameters) can be performed in
linear time in the number of variables, and we demonstrate
empirically that model averaging over \naive classifiers improves
performance, and (4) we develop a technique to make model
averaging practical for arbitrary orderings, and we demonstrate
empirically that this technique can result in improved
classification (compared to other Bayesian network classifiers)
even when no ordering information is known {\em a priori}.

Aside from the practical issue of achieving accurate predictions,
our technique is interesting from an analytical perspective. As an
example, recently, \citet*{domingos.icml00} made an argument based
on empirical and theoretical grounds that Bayesian model averaging
can actually exacerbate the over-fitting problem in machine
learning. Empirically, he shows that rule-learners that
approximate pure Bayesian model averaging closer and closer
achieve successively higher error rates than a rule-learner that
uses the more {\em ad hoc} technique of bagging. He explains this
observation as a consequence of the likelihood's exponential
sensitivity to random fluctuations in the data, and surmises that
the effect will be significant even for small data sets and will
be amplified as the number of models being averaged over
increases. Our experiments here present a direct test of this
assertion, obtaining results that conflict with the conclusions of
\citeauthor*{domingos.icml00}.


In Section~\ref{sec:previousresults} we formally frame the problem
and state our assumptions and notation, and re-derive previous
results. In Section~\ref{sec:theorems} we derive the MA solution
and show that the MA predictions are approximated by those of a
single structure bearing a particular set of parameters. In
Section~\ref{sec:experiments} we present the experimental
comparisons, and in Section~\ref{sec:conclusions} we discuss our
conclusions and future directions.

\section{Previous Results}
\label{sec:previousresults} In this section we frame the problem,
introduce our notation and review relevant previous research,
re-deriving the results of \citet*{Friedman_ML2003} and
\citet*{Buntine2.UAI91} and casting them into notation that will
allow us to extend them for prediction in
Section~\ref{sec:research_ma}.
\subsection{Assumptions and Notation}
\label{sec:notation} The general supervised classification problem
can be framed as follows: Given a set of features
$\vect{F}=\set{F_1,F_2,\ldots , F_N}$, a set of classes
${\mc{C}}=\set{C_1, C_2, \ldots C_{N_c}}$, and a labelled training
data set $D=\set{D_1, D_2,\ldots , D_{N_D}}$ generated from some
distribution $P$, construct a model to predict into which class
future feature vectors sampled from $P$ are most likely to reside.
We use the notation $X_i$ to refer to the nodes when we need to
have a uniform notation; we use the convention that $X_i\equiv
F_i$ and $X_0\equiv C$, and we use $\vect{X}$ to denote the
collective set of nodes in the network. A directed graph
$\f{G}{\X}$ is defined as a pair $\pair{\X}{\E}$, where $\E$ is a
set of directed edges $X_i\rightarrow X_j$, such that
$X_i,X_j\in\X$.  If $X$ is a random variable, we let $\range{X}$
denote the range of $X$. We typically use boldface symbols to
denote sets and non-boldface type to denote elements of sets, when
possible.

We are considering the problem of averaging over the space of {\em
Bayesian network} structures. For a set of variables $\vect{X}$, a
Bayesian network on $\vect{X}$ is a graphical model which
factorizes the joint distribution $\p{\vect{X}}$ over $\vect{X}$.
In particular:
\begin{definition2}[Bayesian network]
Given a set $\X$ of $N$ variables, a Bayesian network $B$ on $\X$
is a pair $B=\tuple{S,\paramvect}$, where $S=\pair{\X}{\E}$ is a
directed acyclic graph over $\X$, and
$\paramvect=\{\vect{\theta_0},\vect{\theta_1},\ldots,\vect{\theta_N}\}$
are the parameters of the network that represent the set of
conditional probability distributions for each variable in $\X$
given its parents in $S$.
\end{definition2}



%We use $\Pa_i$ to denote the parent set of $X_i$, and we let $q_i$
%denote the number of possible joint configurations of parents for
%node $X_i$, which we enumerate as
%$\set{\vect{p_i^1},\vect{p_i^2},\ldots,\vect{p_i^{q_i}}}$. We use
%$\theta_{ijk}$ to denote a single parameter of the network:
%$\theta_{ijk}$ $=$ $\cp{X_i=x_i^k}{\Pa_i=\vect{p}_i^j}$, and the
%symbol $\vect{\theta}$ to denote the collective parameters of the
%network. In general we use the common $(ijk)$ coordinates notation
%to identify the {\em k-th} state and the {\em j-th} parent
%configuration of the {\em i-th} node in the network. We take the
%common assumptions in BN structure learning of Dirichlet priors,
%parameter independence, and parameter modularity
%\citep*{heckerman95}.  We also assume that database $D$ consists
%of complete labelled instances.

We make the following assumptions:
\begin{assumption}[Multinomial variables]
Each node $X_i$ represents a discrete random variable with $r_i$
possible states: $\range{X_i}=\set{x_i^1, x_i^2, \ldots,
x_i^{r_i}}$.
\end{assumption}
We use $\Pa_i$ to denote the parent set of $X_i$, and we let $q_i$
denote the number of possible joint configurations of parents for
node $X_i$ (defining $q_i$=1 if $\Pa_i=\emptyset$), which we
enumerate as:
$\range{\Pa_i}=\set{\vect{p_i^1},\vect{p_i^2},\ldots,\vect{p_i^{q_i}}}$;
for example, if $X_i$ has 3 binary parents then $q_i=8$.

Under the assumption of multinomial variables, a conditional
probability distribution $\vect{\theta_i}$ for variable $X_i$ will
take the form of a conditional probability table (CPT) with
components $\theta_{ijk}=\cp{X_i=x_i^k}{\Pa_i=\vect{p_i^j}}$, and
for a fixed network structure $S$, the components $\theta_{ijk}$
form the parameters of the Bayesian network model and define the
joint distribution over all variables assuming the Markov
condition holds. We use the symbol $\vect{\theta_{ij}}$ to denote
the entire conditional probability distribution function for the
$i$-th node and the $j$-th parent configuration, and the symbol
$\vect{\theta}$ to denote the collective parameters of the
network. In general we use the common $(ijk)$ coordinates notation
to identify the {\em k-th} state and the {\em j-th} parent
configuration of the {\em i-th} node in the network. We use the
shorthand that if $Q_{ijk}$ is some quantity associated with
coordinates $(ijk)$, then $Q_{ij}\equiv\sum_kQ_{ijk}$.
\begin{assumption}[Complete labelled training data]
The training data set $D$ contains no record $D_l\in D$ such that
$D_l$ has a non-observed component.
\end{assumption}
We will discuss ways to relax this assumption in
Section~\ref{sec:conclusions}. We let $N_{ijk}$ denote the
sufficient statistics of the data set (i.e., the number of times
that node $X_i$ achieved state $k$ when parent set $\Pa_i$ was in
the $j$-th configuration).
\begin{assumption}[Dirichlet priors]
The prior beliefs over parameter values are given by a Dirichlet
distribution.
\end{assumption}
We let $\alpha_{ijk}$ denote the Dirichlet hyperparameter
corresponding to the network parameter $\theta_{ijk}$. For
simplicity, we assume $\alpha_{ijk}$ can be calculated in
$\Ofun{1}$ time and space; this is the case, for example, with two
popular metrics, the K2 metric \citep*{cooper92} and the BDeu
metric \citep*{heckerman95}.
\begin{assumption}[Parameter
independence] For any given network structure $S$, each
probability distribution $\vect{\theta_{ij}}$ is independent of
any other probability distribution $\vect{\theta_{i'j'}}$:
\begin{equation}
\label{eqn:param_independence}
\cp{\vect{\theta}}{S}=\prod_{i=0}^N\prod_{j=1}^{q_i}\cp{\vect{\theta_{ij}}}{S}.
\end{equation}
\end{assumption}

Finally, we take the assumption that the priors on parameters
$\theta_{ijk}$ for a node $X_i$ depend only on the local
structure. This assumption is known as {\em parameter modularity}
\citep*{heckerman95}:
\begin{definition2}[Parameter modularity]
Let $\X$ be a set of variables with $X_i\in\X$. For any two
network structures $S_1$ and $S_2$ over $\X$, if
$\Pa_i|_{S_1}=\Pa_i|_{S_2}$ then
$\cp{\theta_{ijk}}{S_1}=\cp{\theta_{ijk}}{S_2}$.
\end{definition2}


%We assume that each node $X_i$ is a discrete multinomial variable
%with $r_i$ possible states $\set{x_i^1,x_i^2,\ldots,x_i^{r_i}}$.
%We use $\Pa_i$ to denote the parent set of $X_i$, and we let $q_i$
%denote the number of possible joint configurations of parents for
%node $X_i$, which we enumerate as
%$\set{\vect{p_i^1},\vect{p_i^2},\ldots,\vect{p_i^{q_i}}}$. We use
%$\theta_{ijk}$ to denote a single parameter of the network:
%$\theta_{ijk}$ $=$ $\cp{X_i=x_i^k}{\Pa_i=\vect{p}_i^j}$, and the
%symbol $\vect{\theta}$ to denote the collective parameters of the
%network. In general we use the common $(ijk)$ coordinates notation
%to identify the {\em k-th} state and the {\em j-th} parent
%configuration of the {\em i-th} node in the network. We take the
%common assumptions in BN structure learning of Dirichlet priors,
%parameter independence, and parameter modularity
%\citep*{heckerman95}.  We also assume that database $D$ consists
%of complete labelled instances.




%\begin{assumption}[Complete Labelled Data]
%The training data set $D$ contains no record $D_l\in D$ such that
%$D_l$ is missing data:
%\mbox{$D_l\in D~\Rightarrow~|D_l|=N+1$.}
%\end{assumption}
%We let $N_{ijk}$ denote the number of times in the database that
%the node $X_i$ achieved state $k$ when $\Pa_i$ was in the $j$-th
%configuration.
%
%\begin{assumption}[Dirichlet priors]
%The prior beliefs over parameter values are given by a Dirichlet
%distribution.
%\end{assumption}
%We let $\alpha_{ijk}$ denote the Dirichlet hyperparameters corresponding
%to the network parameter $\theta_{ijk}$. We assume the hyperparameters
%$\alpha_{ijk}^\nu$ for any parent set $\Pa_i^\nu$ can be calculated in
%constant time.  For example the K2 scoring metric \citep{cooper92}, which
%sets $\alpha_{ijk}=1$ for all $(ijk)$, will satisfy this requirement.
%
%\begin{assumption}[Parameter independence]
%For any given network structure $S$, each probability distribution
%$\vect{\theta_{ij}}$ is independent of any other probability
%distribution $\vect{\theta_{i'j'}}$:
%
%\begin{equation}
%\label{eqn:param_independence}
%\cp{\vect{\theta}}{S}=\prod_{i=0}^N\prod_{j=1}^{q_i}\cp{\vect{\theta_{ij}}}{S}
%\end{equation}
%\end{assumption}
%\begin{assumption}[Structure modularity]
%\label{ass:struct_modularity}
%We assume that the prior of a structure $S$, $P(S)$, can be factorized
%according to the network:
%\begin{equation}
%\label{eqn:struct_prior} \p{S}\propto\prod_{i=0}^N p_s(X_i,\Pa_i),
%\end{equation}
%where $p_s(X_i,\Pa_i)$ is some function that can be calculated in
%$\Ofun{|\Pa_i|}$ time.
%\end{assumption}
%This assumption was used in \citep{Meila45.UAI-2000} and
%\citep{Friedman_ML2003} the latter introducing the name that we use
%here.
%For example, any metric that scores
%$\cp{S}{K}$ based on a difference in arcs between $S$ and some
%prior network (as suggested by \citep{heckerman95}) will satisfy
%this condition.
%Obviously the uniform distribution which is $\f{O}{1}$ will
%satisfy this assumption.

\subsection{Averaging Over Parameters with a Fixed Network Structure}
One common goal in machine learning with Bayesian networks is to
calculate the probability of a configuration $\vect{X}=\vect{x}$
of a set of variables $\vect{X}$. This can be used for predicting
likely configurations of variables, or it can be queried for any
conditional probability of interest over the variables in $\X$
(e.g., $P(X_1, X_2\give X_3)$) which could be useful for
prediction. For a fixed network structure $S$ and a fixed set of
network parameters $\paramvect$, $\classification{S,\paramvect}$
can be calculated in $\Ofun{N}$ time:
\begin{equation}
\label{eqn:BN_inference}
\classification{S,\paramvect}=\prod_{i=0}^N\theta_{i\jk},
\end{equation}
where all $(j,k)$ coordinates are fixed by the configuration of
$\X$ to the value $(j,k)=(J,K)$.

When, rather than a fixed set of parameters, a database $D$ is
given, it is necessary to average over all possible configurations
of the parameters $\paramvect$: {{
%\small
\begin{eqnarray*}
%\lefteqn{\classification{S,D}}  \\
 \classification{S,D}& = & \int\classification{S,\paramvect}\cdot\cp{\paramvect}{S,D}\cdot d\paramvect  \\
 & = & \int\prod_{i=0}^N\theta_{i\jk}\cdot\cp{\paramvect}{S,D}\cdot d\paramvect, \\
\end{eqnarray*}}}where the second line follows from
Equation~\ref{eqn:BN_inference}. Given the assumption of parameter
independence and Dirichlet priors, this quantity can be written
just in terms of sufficient statistics and Dirichlet
hyperparameters \citep*{cooper92,heckerman95}:
%\footnote{This
%result was recently rederived for the class of \naive models by
%\citet*{Kontkanen98}}

\begin{eqnarray}
\label{eqn:average_over_params}
\classification{S,D}& = &
\prod_{i=0}^N\frac{\alpha_{i\jk}+N_{i\jk}}{\alpha_{iJ}+N_{iJ}},
\end{eqnarray}
where we have used the notation: $\alpha_{ij}=\sum_k
\alpha_{ijk}$. Comparing this result to
Equation~\ref{eqn:BN_inference} illustrates the well-known result
that a single network with a fixed set of parameters
$\paramvecthat$ given by
\begin{equation}
\label{eqn:parameters} \tilde{\theta}_{ijk}=
\frac{\alpha_{ijk}+N_{ijk}}{\alpha_{ij}+N_{ij}}
\end{equation}
will produce predictions equivalent to those obtained by averaging
over all parameter configurations. We refer to
Equation~\ref{eqn:parameters} as the {\em standard
parameterization}.
%Heckerman \shortcite{Heckerman98a} argued
%that these parameters represent a {\em maximum a posteriori} (MAP)
%configuration in their canonical coordinate system.


\subsection{Averaging Structural Features with a Fixed Ordering}
\label{sec:review_ma_fixed_ordering}

The decomposition by Buntine used by Friedman and Koller was a
dynamic programming solution which calculated, with relative
efficiency, for example, the posterior probability
$\cp{X_L\rightarrow X_M}{D}$ of a particular arc $X_L\rightarrow
X_M$ averaged over all in-degree-bounded networks consistent with
a fixed ordering. Friedman and Koller then showed how this
quantity could be used in a MCMC search for the most likely
structural feature, where the search went over orderings instead
of DAGs. One might be interested in this quantity, for example, if
you were interested in a Bayesian estimate for the structural
dependency relations of the system given the data; see
\citet{Friedman_ML2003} for more motivation for why this quantity
would be useful. In this section we re-derive the result of
Buntine.

The derivation required the ability to calculate efficiently the
prior probability $P(S)$ that a given structure $S$ generated the
database $D$. An additional assumption was introduced, labelled
{\em structure modularity} by Friedman and Koller:
\begin{assumption}[Structure modularity]
\label{ass:struct_modularity}
\index{zz_Assumptions@Assumptions!\ref{ass:struct_modularity}|see{structure
modularity}} \index{structure modularity|} \nonumber The prior of
a structure $S$, $P(S)$, can be factored according to the network
\begin{equation}
\label{eqn:struct_prior} \p{S}\propto\prod_{i=0}^N p_s(X_i,\Pa_i),
\end{equation}
where $p_s(X_i,\Pa_i)$ is some function that depends only on the
local structure ($X_i$ and $\Pa_i$).
\end{assumption}
Any metric that assesses the structure prior $\p{S}$ based on a
difference in arcs between $S$ and some prior network structure
$S'$ (as suggested by \citet*{heckerman95}) will satisfy this
condition. Also the uniform distribution will obviously satisfy
this assumption, and requires $\Ofun{1}$ time to assess.
Obviously, we restrict ourselves to structures that give
probability zero to a non-acyclic DAG.

The posterior probability $\cp{X_L\rightarrow X_M}{D}$ can be
written as
{%\small
\begin{eqnarray}
\lefteqn{\cp{X_L\rightarrow X_M}{D} =} \nonumber \\
& & c\sum_S\delta_K(X_L\rightarrow X_M\in
S)\cdot\cp{D}{S}\cdot\p{S}, \label{eqn:prob_Xi_to_Xj}
\end{eqnarray}
}where $c=1/\p{D}$ is a constant that depends only on the
database, and $\delta_K(Z)$ is the Kronecker delta function:
\[
\delta_K(Z)= \left\{
\begin{array}{ll}
1 & \mbox{if $Z=\true$}\\
0 & \mbox{otherwise.}
\end{array}
\right.
\]

The summation in Equation~\ref{eqn:prob_Xi_to_Xj} includes a
super-exponential number of network structures, and therefore
appears to be intractable. Buntine handled this problem by
imposing a total ordering on the nodes and restricting the maximum
number of parents, $k$, that each node can have. Generalizing his
results to a partial ordering $\pi$ instead of a total ordering is
straightforward, and we do that here. For a given partial ordering
$\pi$ and a particular node $X_i$, it is required to enumerate all
of $X_i$'s possible parent sets up to a maximum size $k$. To this
end, we will typically use the superscript $\nu$ to index the
different parent sets. For example, four nodes partitioned as
$\pi=\tuple{\set{X_1,X_3},\set{X_2,X_4}}$ and a maximum in-degree
$k=2$ would yield the following enumeration of parent sets for
$X_2$:
$\set{\Pa_2^0=\emptyset,\Pa_2^1=\set{X_1},\Pa_2^2=\set{X_3},\Pa_2^3=\set{X_1,X_3}
}$.
%We assume the
%hyperparameters $\alpha_{ijk}^\nu$ for any parent set $\Pa_i^\nu$
%can be calculated in constant time.  For example the K2 scoring
%metric
%\citep*{cooper92}, which sets $\alpha_{ijk}=1$ for all $(ijk)$, will satisfy
%this requirement.

The class of models consistent with $\pi$ with bounded in-degree
of $k$ we denote as $\myclass$:
\begin{definition2}[$\myclass$]
\label{def:multi_level_k_graph}
%\index{zz_Definitions@Definitions!\ref{def:multi_level_k_graph}|see{partially-ordered $k$-graph}}
%\index{partially-ordered $k$-graph}
%\index{L_k@$\Lk$!see partially-ordered $k$-graph}
For a given integer $k \leq N$ and a given partial ordering $\pi$
of $\X$, a DAG~~$G=\tuple{\X,\E}\in\myclass$ iff arcs are directed
from higher to lower levels and no variable has more than $k$
parents: $X_i\rightarrow X_j\in\E\Rightarrow
\level{X_i}>\level{X_j}$, and $X_i\in\X\Rightarrow |\Pa_i|\leq k$.
\end{definition2}
Note that if $D_1,D_2\in\myclass$ and $D_1\neq D_2$ then $D_1$ is
statistically distinguishable from $D_2$ because it will include a
different set of adjacencies \citep{Verma.UAI90}; so when
averaging over the class $\myclass$, we are never averaging over
equivalent DAGs.

The number of structures in $\Lk$ is still exponentially large in
the worst-case; each node at level $l$ can choose up to $k$
parents from among all the nodes in levels $l'>l$. For $k\leq
N/2$, $\myclass$ in the worst-case includes at least
$\Omega\left[{{N/2}\choose k}^{N/2}\right]$ network structures.
This result corresponds to the case where $\pi$ consists of two
levels, each with $N/2$ nodes; each of the $N/2$ nodes in the
bottom level can therefore choose up to ${{N/2} \choose k}$
possible parents.\footnote{We are not asserting that this two-level
ordering is the absolute worst-case, only that the worst-case must
have at least this many network structures.}



Given the assumptions of this paper, $\cp{D}{S}$, can be written
just in terms of hyperparameters and sufficient statistics
\citep*{cooper92,heckerman95}:
%{{\small
\begin{equation}
\cp{D}{S}= \ML. \label{eqn:marg_likelihood}
\end{equation}
%\begin{eqnarray}
%\lefteqn{\cp{D}{S}=} \nonumber \\
%& & \ML. \label{eqn:marg_likelihood}
%\end{eqnarray}
%}}
Given structure modularity
(Assumption~\ref{ass:struct_modularity}) and
Equation~\ref{eqn:marg_likelihood},
Equation~\ref{eqn:prob_Xi_to_Xj} can be written as
\begin{equation}
\label{eqn:prob_Xi_to_Xj_final} \cp{X_L\rightarrow
X_M}{D}=c\sum_S\prod_{i=0}^N\cfun^S_{iLM}.
\end{equation}
The $\cfun^S_{iLM}$ functions are given by
%{\small
%\begin{eqnarray}
%\lefteqn{\cfun^S_{iLM} = \delta_K[M\neq i \vee X_L\in\Pa_i]\cdot p_s(X_i,\Pa_i)\cdot} \nonumber \\
%& & \MLi,
%\label{eqn:prob_Xi_to_Xj_ci_funs}
%\end{eqnarray}
\begin{equation}
\cfun^S_{iLM} = \delta_K[M\neq i \vee X_L\in\Pa_i]\cdot
p_s(X_i,\Pa_i)\cdot\MLi, \label{eqn:prob_Xi_to_Xj_ci_funs}
\end{equation}
and can be calculated using information that depends only on nodes
$X_i$ and $\Pa_i$.


Even restricting structures to those in a particular $\myclass$
class, as already mentioned, the summation in
Equation~\ref{eqn:prob_Xi_to_Xj_final} still contains an
exponential number of structures in the worst-case. However, the
following theorem (similar to one from \citet{Buntine2.UAI91})
shows that $\cp{X_L\rightarrow X_M}{D,\myclass}$ can be calculated
with relative efficiency:
\begin{theorem}
Assuming $S\in\Lk$, equation~\ref{eqn:prob_Xi_to_Xj_final} can be
written as $\cp{X_L\rightarrow
X_M}{D,\myclass}=c\prod_{i=0}^N\sum_{\nu=0}^{\mu_i}\cfun^\nu_{iLM}$,
where $\cfun^\nu_{iLM}$ denotes $\cfun^S_{iLM}$ for the $\nu$th
parent set $\Pa_i^\nu$ of $X_i$ and the summation goes over all
parent sets available to node $X_i$ under the restrictions of
$\myclass$.
\Proof{ For notational simplicity, we will drop the
$LM$ subscripts on the $\cfun$ functions: $\cfun^\nu_i \equiv
\cfun^\nu_{iLM}$. Expanding the sum in
Equation~\ref{eqn:prob_Xi_to_Xj_final} yields

\[
\cp{X_L\rightarrow X_M}{D,\Lk} \propto \left.
\begin{array}{ccc}
%\lefteqn{\cp{X_L\rightarrow X_M}{D,\Lk} \propto } \\
    & \cfun^0_{0}\cdot \cfun^0_{1}\cdot\ldots\cdot \cfun^0_{N} \\
  + & \cfun^1_{0}\cdot \cfun^0_{1}\cdot\ldots\cdot \cfun^0_{N} \\
  \vdots & \vdots \\
  + & \cfun^{\mu_0}_{0}\cdot \cfun^0_{1}\cdot\ldots\cdot \cfun^0_{N} \\
  \\

  + & \cfun^0_{0}\cdot \cfun^1_{1}\cdot\ldots\cdot \cfun^0_{N} \\
  + & \cfun^1_{0}\cdot \cfun^1_{1}\cdot\ldots\cdot \cfun^0_{N} \\
  \vdots & \vdots \\
  + & \cfun^{\mu_0}_{0}\cdot \cfun^1_{1}\cdot\ldots\cdot \cfun^0_{N} \\
  \vdots & \vdots \\
  + & \cfun^0_{0}\cdot \cfun^0_{1}\cdot\ldots\cdot \cfun^1_{N} \\
  + & \cfun^1_{0}\cdot \cfun^0_{1}\cdot\ldots\cdot \cfun^1_{N} \\
  \vdots & \vdots \\
  + & \cfun^{\mu_0}_{0}\cdot \cfun^0_{1}\cdot\ldots\cdot \cfun^1_{N} \\
  \vdots & \vdots \\
  + & \cfun^{\mu_0}_{0}\cdot \cfun^{\mu_1}_{1}\cdot\ldots\cdot \cfun^{\mu_N}_{N}
\end{array}
\right\}\Omega\left[{{N/2}\choose k}^{N/2}\right] \mbox{ terms,
worst-case.}\] We define the symbol $\Sigma^{}_m$ to denote the
structure sum of the product up to and including the $m$-th node:
\[
\begin{array}{ccc}
%\lefteqn{\Sigma^{}_m  \equiv}\\
\Sigma^{}_m & \equiv & \cfun^0_{0}\cdot \cfun^0_{1}\cdot\ldots\cdot \cfun^0_{m} \\
  &+ & \cfun^1_{0}\cdot \cfun^0_{1}\cdot\ldots\cdot \cfun^0_{m} \\
  &\vdots & \vdots \\
 &+ & \cfun^{\mu_0}_{0}\cdot \cfun^{\mu_1}_{1}\cdot\ldots\cdot
 \cfun^{\mu_m}_{m}.
\end{array}
\]
Using this notation,
%%$\Sigma^{}_N$ can be written in terms of
%%$\Sigma^{}_{N-1}$:
%%\begin{eqnarray*}
%%\Sigma^{}_N & = & \Sigma^{}_{N-1}\cdot \cfun^\emptyset_{N} \\
%%         & + & \Sigma^{}_{N-1}\cdot \cfun^C_{N} \\
%%\end{eqnarray*}
%which yields the recurrence relations:
the following recursion relation can be derived:
\[
\label{eqn:sigma_recurrence} \Sigma^{}_i = \Sigma^{}_{i-1}\cdot
\sum_{\nu=1}^{\mu_i}\cfun^\nu_{i}\mbox{, }~~~~~ \Sigma^{}_{-1} =
1.
\]
Finally, expanding the recurrence relation yields the expression
for $\cp{X_L\rightarrow X_M}{D,\myclass}$:
\begin{equation}
\label{eqn:final_XL_to_XM_expression} \cp{X_L\rightarrow
X_M}{D,\myclass}=c\prod_{i=0}^N\sum_{\nu=1}^{\mu_i}\cfun^\nu_{i}.
\end{equation}}
\end{theorem}
Thus, a summation of $\Omega\left[{{N/2}\choose k}^{N/2}\right]$
terms can be performed in $O\left[{N\choose k}\cdot N\right]$
operations.



%--------------------------------------------
\section{Model Averaging for Prediction}
\label{sec:theorems}
In this section we show how to extend the results of
Section~\ref{sec:previousresults} to efficiently calculate the
quantity $\classification{D,\myclass}$ averaged over the class
$\Lk$.
%From this quantity we can readily calculate the quantity
%$\cp{C_i}{\vect{f},D}$ required for classification in $\Ofun{N_c}$ time
%using
%$\cp{C_i}{\vect{f},D}=\cp{C_i,\vect{f}}{D}/\sum_j\cp{C_j,\vect{f}}{D}$.
%\subsection{Model Averaging for Prediction}
\label{sec:research_ma}

%Here we show that a similar dynamic programming solution exists
%for model-averaging the quantity $\classification{D,\myclass}$ over the
%class $\myclass$.
%, and we propose an approximation to the full
%model-averaging that eases the computational burden for model-averaged
%classifications even further.
%\section{Theoretical Results}
\label{sec:DAG_ma_theoretical_results}

This quantity can be written as
%{\small
\begin{equation}
\classification{D,\myclass} = {1\over
P(D)}\sum_{S\in\myclass}\prod_{i=0}^N\tilde{\theta}_{i\jk}\cdot\cp{D}{S}\cdot\p{S},
\label{eqn:prediction_2nd_last_step}
\end{equation}%}
where $\tilde{\theta}_{i\jk}$ are the standard parameters given in
Equation~\ref{eqn:parameters}. Given structure modularity and
Equation~\ref{eqn:marg_likelihood},
Equation~\ref{eqn:prediction_2nd_last_step} can be written in a
form very similar to Equation~\ref{eqn:prob_Xi_to_Xj_final}:
\begin{equation}
\label{eqn:prediction_final}
\classification{D,\myclass}=c\sum_{S\in\myclass}\prod_{i=0}^N\tilde\cfun_{i\JK},
\end{equation}
where here the $\tilde\cfun_{i\JK}$ functions are given by
%\begin{eqnarray}
%\lefteqn{\tilde\cfun_{i\JK} = \tilde{\theta}_{i\JK}\cdot p_s(X_i,\Pa_i)\cdot } \nonumber \\
%& &  \MLi.
%\label{eqn:ci_functions}
%\end{eqnarray}
\begin{equation}
\tilde\cfun_{i\JK} = \tilde{\theta}_{i\JK}\cdot\MLi\cdot
p_s(X_i,\Pa_i), \label{eqn:ci_functions}
\end{equation}
and $c$ is a constant (not dependent on $S$) equal to $1/P(D)$. We
subscript the indices $J$ and $K$ from
Equation~\ref{eqn:BN_inference} with an $\x$ to indicate that they
are fixed by a particular configuration of $\X$, and $J$ is
indexed by $S$ to emphasize that the value of the parent
configuration index depends on the number of parents and therefore
the structure $S$ of the network. Although this notation may seem
cumbersome, we believe it clarifies the analysis later.


As in Section~\ref{sec:review_ma_fixed_ordering}, the worst-case
number of terms in the summation of
Equation~\ref{eqn:prediction_final} is exponential in the number
of features $N$. The $\tilde\cfun_{i\JK}$ functions again can be
calculated using only information local to node $X_i$ and $\Pa_i$.
Following a derivation identical to that for averaging
$\cp{X_L\rightarrow X_M}{D,\myclass}$ in
Section~\ref{sec:review_ma_fixed_ordering}, yields the following :
\begin{equation}
\label{eqn:final_prediction_expression}
\classification{D,\myclass}=c\prod_{i=0}^N\sum_{\nu=1}^{\mu_i}\tilde\cfun^\nu_{iJ^{\nu}_{\mathbf
x} K_{\mathbf x}}.
\end{equation}
Here the $S$ index has been replaced with a $\nu$ indicating which
parent set for node $X_i$ is being considered. The following
theorem shows that this summation can be performed in
% the $\tilde\cfun^\nu_{iJ^{\nu}_{\mathbf x} K_{\mathbf x}}$ terms
%are calculated, the product in
%Equation~\ref{eqn:final_prediction_expression} can be performed in
%$\Ofun{N\cdot{N\choose k}}$ time, and to calculate the complete set for
%all $(j,k)$ combinations requires
$\KTwotimecomplexity$ time and $\KTwospacecomplexity$ space.

\begin{theorem}
\label{thm:ma_complexity_Xi_to_Xj} For $N$ variables with a
maximum number of states per variable given by $R$ and a database
of $N_D$ records, Equation~\ref{eqn:final_prediction_expression}
can be calculated in $\KTwotimecomplexity$ time and using
$\KTwospacecomplexity$ space.
\Proof{The right-hand-side of Equation~\ref{eqn:final_prediction_expression}
includes $N$ products and ${N\choose k}$ sums. Each
$\cfun^\nu_{iLM}$ term can be calculated in $\Ofun{k\cdot N_D\cdot
R}$ time and $\Ofun{k\cdot N_D}$ space. This result follows
because all sufficient statistics for a given node $X_i$ can be
stored in a tree of depth $\Ofun{k}$ and width $\Ofun{N_D}$, with
the leaves of the tree holding the sufficient statistic for the
given configuration of $X_i$ and $\pa{X_i}$.  To fill the tree
requires $N_D$ passes of the tree, thus taking $\Ofun{k\cdot N_D}$
time. Once the tree is constructed, it can be queried for any
statistic in $\Ofun{k}$ time.

The number of possible parent configurations present in the data
are bound by the number of records $N_D$; thus the number of
$(i,j)$ configurations for which $N_{ij}\neq 0$ is $\Ofun{N_D}$.
Furthermore, all terms in the product of
Equation~\ref{eqn:final_prediction_expression} for which
$N_{ij}=0$ will equal 1 so will not contribute to the product.
Thus, the calculation of products in
Equation~\ref{eqn:ci_functions} require $\Ofun{k\cdot N_D\cdot R}$
time.

Putting all the steps together yields the claim of the theorem. }
\end{theorem}

%
%The following theorem shows that the space and time complexities
%reduce to $\Ofun{k\cdot N_D\cdot R}$ for the K2 metric:
%\begin{theorem}
%For $N$ variables with a maximum number of states per variable
%given by $R$ and a database of $N_D$ records, if $\alpha_{ijk}=1$
%for all $(ijk)$ combinations, then
%Equation~\ref{eqn:final_prediction_expression} can be calculated
%in $\KTwotimecomplexity$ time and using $\KTwospacecomplexity $
%space.
%\Proof{
%The right-hand-side of
%Equation~\ref{eqn:final_prediction_expression} includes a
%summation over $\Ofun{N\cdot{N\choose k}}$ $\cfun^\nu_{iLM}$
%terms.  Each $\cfun^\nu_{iLM}$ term can be calculated in
%$\Ofun{k(N_D + R^k)}$ time and $\Ofun{k\cdot N_D}$ space. This
%result follows because all sufficient statistics for a given node
%$X_i$ can be stored in a tree of depth $\Ofun{k}$ and width
%$\Ofun{N_D}$, with the leaves of the tree holding the sufficient
%statistic for the given configuration of $X_i$ and $\pa{X_i}$.  To
%fill the tree requires $N_D$ passes of the tree, thus taking
%$\Ofun{k\cdot N_D}$ time. Once the tree is constructed, it can be
%queried for any statistic in $\Ofun{k}$ time.
%
%The number of possible parent configurations present in the data
%are bound by the number of records $N_D$; thus the number of
%$(i,j)$ configurations for which $N_{ij}\neq 0$ is $\Ofun{N_D}$.
%Furthermore, all terms in the product of
%Equation~\ref{eqn:final_prediction_expression} for which
%$N_{ij}=0$ will equal 1 so will not contribute to the product.
%Thus, the calculation of products in
%Equation~\ref{eqn:ci_functions} require $\Ofun{k\cdot N_D\cdot R}$
%time.
%
%Putting all the steps together yields the claim of the theorem. }
%\end{theorem}

Although this result is relatively efficient, for classification
purposes it may still be too complex of a calculation. The
functional form of the above solution allows us to prove that
exact model averaging over $\Lk$ can actually be performed with a
single Bayesian network structure:
%
%A final observation about Equation~\ref{eqn:final_prediction_expression}
%is given by the following theorem:
\begin{theorem}
\label{thm:singlenet}
\index{zz_Theorems@Theorems!\ref{thm:singlenet}} There exists a
single Bayesian network model $M^* = \tuple{S^*,\paramvect^*}$
that will define a joint distribution $P(\X=\x~\give
~S^*,\paramvect^*)$ that is equivalent to that produced by model
averaging over all models in $\Lk$. \Proof{ Let $S^*$ be defined
so that each node $X_i$ has the parent set
$\Pa^*_i=\bigcup_{\nu=1}^{\mu_i}\Pa^\nu_i$, and let $\paramvect^*$
be defined by
\begin{equation}
\label{eqn:param_average} \theta^*_{ijk} =
c^{1/N}\sum_{\nu=1}^{\mu_i}\tilde\cfun^\nu_{iJ^{\nu}_j k},
\end{equation}
where the $\x$ subscript for $J^{\nu}_{\mathbf x}$ has now been
replaced with a $j$ and $\K$ has been replaced with a $k$
subscript, because we are considering a particular coordinate
$(ijk)$. It can be seen by direct comparison that substituting
$\theta^*_{ijk}$ into Equation~\ref{eqn:BN_inference} will yield
Equation~\ref{eqn:final_prediction_expression}. }
\end{theorem}

If we define functions $\f{f}{X_i,\Pa^\nu_i\give D}$ such that
$\f{f}{X_i,\Pa^\nu_i\give D}=\tilde\cfun^\nu_{iJ^{\nu}_j
k}/\tilde{\theta}^\nu_{iJ^{\nu}_j k}$, then
Equation~\ref{eqn:param_average} can be written as
\begin{equation}
\label{eqn:structure_based_smoothing} \theta^*_{ijk} =
c^{1/N}\sum_{\nu=1}^{\mu_i}\tilde{\theta}^\nu_{iJ^{\nu}_j
k}\cdot\f{f}{X_i,\Pa^\nu_i\give D}.
\end{equation}
The functions $\f{f}{X_i,\Pa^\nu_i\give D}$ do not depend on the
indices $J^{\nu}_j$ and $k$, and they can be interpreted as the
local posterior probability that the parent set of $X_i$ is in
fact $\Pa^\nu_i$. Equation~\ref{eqn:structure_based_smoothing}
thus provides the interpretation that $M^*$ represents a
structure-based smoothing where each standard parameter
$\tilde{\theta}^\nu_{ijk}$ is weighted based on the likelihood
that $\Pa^\nu_i$ is the parent set of $X_i$.  Since
$\theta^*_{ijk}$ is interpretable as a probability, the constant
$c^{1/N}$ serves as a normalization constant and need not be
calculated directly.

There are some numerical complexities with calculating the
parameters using Equation~\ref{eqn:structure_based_smoothing}. One
must essentially calculate quantities of the form
\begin{equation}
\theta^*_{i} =
c^{1/N}\sum_{\nu}\tilde{\theta}^\nu_{i}\cdot\exp{\longvar{lf}_i^\nu},
\end{equation}
where $lf_i^\nu = \log{f_i^\nu}$ is a negative number with large
absolute value. Exponentiating this value will usually be
truncated to zero using floating-point arithmetic.  In reality
however, the normalization constant $c^{1/N}$ is also very small
and in fact makes $\theta^*_{i}$ nonzero in many cases.  To get
around this problem, we use a known trick of shifting the
exponentials so the largest term is equal to 1.  The net result of
this is to change the normalization constant, which is never
calculated explicitly, i.e.
\begin{equation}
c^{1/N}\sum_{\nu}\tilde{\theta}^\nu_{i}\cdot\exp{\longvar{lf}_i^\nu}
=
{c^{1/N}\over{\exp{(-\longvar{lf}_{max}})}}\sum_{\nu}\tilde{\theta}^\nu_{i}\cdot\exp{(\longvar{lf}_i^\nu-\longvar{lf}_{max})},
\end{equation}


Theorem~\ref{thm:singlenet} implies that, rather than performing
the $\Ofun{{N\choose k}\cdot N}$ summation in
Equation~\ref{eqn:final_prediction_expression} for each case to be
classified, in principle we need only construct a single model
$M^*$ and use standard Bayesian network inference for each case.
In the case of a completely instantiated feature vector, this
inference can be completed in $\Ofun{N}$ time; otherwise BN
inference can be used. Unfortunately for almost all realistic
partial orderings $M^*$ will be a highly dense network and memory
requirements will be prohibitive. Furthermore, the network
structure $S^*$ would be non-interpretable by a human. The
intractability  of $M^*$ is a central problem with applying this
method in practice, and we devote most of the remainder of this
paper to presenting ways to remedy this problem.



\subsection{Model Averaging over \Naive structures}
\label{sec:naive_ma}
One popular class of models that fits into the $\Lk$ schema is the
class of \naive (simple) Bayes models.  The \naive classifier is a
probabilistic model that accomplishes classification by making the
assumption that any feature $F_i\in F$ is conditionally
independent of any other feature $F_j\in F$ given the value of the
class variable $C$. The \naive model can be represented by the
Bayesian network shown in Figure~\ref{fig:naiveNet}.

\begin{figure}[h]
\begin{picture}(130,80)
\put(140,0){%Just the eps file:
\scalebox{0.3}{
\includegraphics{images/naive_net.eps}
}}
\end{picture}
\caption{
\label{fig:naiveNet}
A \naive network: $C$ is the class node which can take on one
value for each possible class, and the $F_i$ denote features of
interest.}
\end{figure}

\Naive classifiers have several desirable features:  First, they
are simple to construct, requiring very little domain background
knowledge, as opposed to general Bayesian networks which can
require numerous intensive sessions with experts, or a large
real-world database to learn the dependence structure between
features. Second, \naive networks can be built with very
constrained space and time complexity: constructing a network
requires the estimation of a set of $\f{O}{N\cdot R\cdot N_c}$
parameters, where $R$ is the maximum number of feature states and
$N_c$ is the number of class states. Each of which can be
estimated from data in time $\f{O}{N_D}$, where $N_D$ is the
number of records in the database. Inference with \naive networks
is also efficient; classification of a new feature vector $F'$ can
be performed in time $\f{O}{|F'|}$, even if $F'$ is an incomplete
instantiation of features.

Despite their simplicity, these classifiers have been shown to
perform surprisingly well in practice. \citet*{domingos97} have
shown that \naive classifiers can be optimal (in terms of
classifcation accuracy) even when the underlying distribution does
not satisfy the \naive assumptions. \citet*{friedmanJerome97}
argues that the low variance of the \naive classifier can mitigate
the bias, resulting in overall accurate predictions. Finally,
\citet*{Ng.NIPS.02} show both theoretically and empirically that
the \naive classifier converges quickly to its asymptotic
error-level. These studies explain why the \naive model has
continued to compare favorably to state-of-the-art classification
algorithms.

The construction of a \naive classifier given a set $F$ of
potential attributes requires only two general steps: (1) Select
the subset of features $F'\subseteq F$ judged to be relevant to
classification, and (2) Calculate the set $\paramvecthat$ of
parameters using Equation~\ref{eqn:parameters}.  The feature
selection problem (1) is a difficult and central problem in
machine learning in general. In terms of \naive classifiers, the
selection of the appropriate subset $F'$ has been shown to be both
important to classification and non-trivial to perform in practice
\citep*{Langley.UAI94,kohavi97wrappers,friedman97bayesianClassifiers}.
Obviously eliminating features that do not bear on the
classification is important, but also important is the ability to
minimize redundant features.

Our method allows us to take a strict Bayesian approach to feature
selection; rather than finding a single ``good'' set $F'$, we can
efficiently address the problem of model averaging predictions
over all $2^N$ possible feature-set structures. An enumeration of
these different structures is illustrated in
Figure~\ref{fig:enumeration}.
\begin{figure}[h]
\begin{picture}(130,110)
\put(90,0){%Just the eps file:
\scalebox{0.5}{
\includegraphics{images/enum.eps}
} }
\end{picture}
\caption{Enumerating all the $2^N$ possible \naive Bayes net
structures.}
\label{fig:enumeration}
\end{figure}
%For example, the four possible structures of a \naive classifier
%with two features are %$\set{F_1,F_2}$ are: \mbox{$\set{F_1\leftarrow
%%C\rightarrow F_2}$}, \mbox{$\set{F_1~~~~~C\rightarrow F_2}$},
%%\mbox{$\set{F_1\leftarrow C~~~~~F_2}$}, and
%%\mbox{$\set{F_1~~~~~C~~~~~F_2}$}.
%$\set{C\rightarrow F_1,~C\rightarrow F_2}$, $\set{C\rightarrow
%F_1}$, $\set{C\rightarrow F_2}$, and $\emptyset$.

The summary model $M^*$, defined in Theorem~\ref{thm:singlenet},
for the \naive class is especially simple, itself being a \naive
network over {\em all} features.
Equation~\ref{eqn:structure_based_smoothing} for a \naive Bayes
net reduces to
\begin{equation}
\label{eqn:naive_MA_params}
\theta^*_{ijk}~\propto~\tilde{\theta}^\emptyset_{ijk}\cdot\f{$f_i$}{\emptyset\give
D}~+~\tilde{\theta}^C_{ijk}\cdot\f{$f_i$}{\{C\}\give D},
\end{equation}
where $\f{$f_i$}{\emptyset\give D}$ and $\f{$f_i$}{\{C\}\give D}$
are proportional to the local posterior probability of
$\Pa_i=\emptyset$ and $\Pa_i=\set{C}$, respectively. The
sufficient statistics and Dirichlet priors required for this
calculation are the same as those needed for calculating the
parameters of (a) a single network with no arcs present, and (b) a
single \naive network with all arcs present. This
reparameterization requires order $\Ofun{N\cdot N_D}$ time and
space requirements, which are the same that are needed to
calculate the standard parameters of a single \naive network over
all $N$ features. We call a naive structure so parameterized a
{\em\Naive model averaging} (NMA) classifier. In
Section~\ref{sec:experiments} we present empirical results showing
that this reparameterization, over a wide range of experimental
parameters, almost always produced better classification results
than a standard \naive model.


\subsection{Approximate Model Averaging}
\label{sec:approximation}

As noted in Section~\ref{sec:research_ma}, a serious practical
difficulty with constructing $M^*$ according to
Theorem~\ref{thm:singlenet} when no ordering is known, is that it
requires in the worst case the construction of a
completely-connected Bayesian network and inference can thus be
intractable for all but small $N$. An obvious pruning strategy,
however, is to truncate the sum in
Equation~\ref{eqn:param_average} to include no more than $n$
parents. Here we present one possible method for selecting the $n$
most important parents for each node.

If we reorder the possible parent sets for node $X_i$ as
$O_P\equiv\set{\Pa^1_i,\ldots,\Pa^{\mu_i}_i}$ such that
$\mbox{$\f{f}{X_i,\Pa^\nu_i\give D}$} >
\mbox{$\f{f}{X_i,\Pa^\lambda_i\give D}$}$ if and only if
$\nu<\lambda$, then an approximation for $\Pa^*_i$ can be
constructed
by the following procedure:% For $\nu=1$ to $\mu_i$, if
%$|\Pa^*_i\cup\Pa^\nu_i|<n$ add $\Pa^*_i\cap\Pa^\nu_i$ to
%$\Pa^*_i$.
\procedure{Approximate $P^*_i$ construction} {\linebreak {\bf
Given: \rm $n$ and $O_P$.} \hfill\hfill\linebreak \vspace{-.2in}
\begin{enumerate}
\item
Let $\Pa^*_i=\emptyset$
\item
For $\nu=1$ to $\mu_i$, \hfill\hfill\linebreak if
$|\Pa^*_i\cup\Pa^\nu_i|\leq n$, let $\Pa^*_i =
\Pa^*_i\cup\Pa^\nu_i$, else continue.
\end{enumerate}
} We denote the class of structures being averaged over using this
procedure as $\Lkn$, and we call the method {\em Approximate Model
Averaging} (AMA). Obviously ${\mathcal{L}}_{kN}^{\pi}(D) = \Lk$.
Furthermore, we empirically show in Section~\ref{sec:experiments}
that the loss in ROC area, $\epsilon$, due to this approximation
for $n\geq 10$ lies around $-0.6\%\leq\epsilon\leq 0.6\%$ with
99\% confidence for $N\leq 100$ and for a wide range of other
parameters. We also show empirically that classifications are not
typically sensitive to the value of $n$, so often $n$ can be made
relatively small without degrading classification results.

\section{Experimental Tests}
\label{sec:experiments} In this section we describe several
experimental investigations that were designed to test the
performance of NMA and AMA on arbitrary distributions. We first
generate synthetic data to allow us to more extensively vary
parameters, then we perform tests on several real-world machine
learning data sets. All experiments were implemented in C++ using
code that was based on the {\em Structural Modelling, Inference
and Learning Engine} (SMILE) \citep*{druzdzel99a}, a library for
constructing probabilistic decision support models.\footnote{SMILE
can be downloaded from http://www.sis.pitt.edu/\~{}genie; however
the learning functionality required for our experiments is not yet
available for public release.} Experiments were run on an 1.6 GHz
Pentium PC with 1 GB of RAM running Windows XP.

\subsection{Experimental Setup}
\label{sec:exp_setup}

There are at least five parameters for which we sought to
characterize the performance of classifier predictions: the number
of nodes $N$, the approximation limit $n$ on the size of the
maximum in-degree in the summary network, the maximum in-degree
(``density") $K$ of the {\em generating} network, the maximum
in-degree $k$ ($k\leq n$) allowed in models in $\Lk$, and the
number of records $N_D$. It is beyond the scope of this paper to
present a comprehensive comparison over this full five-dimensional
space; however, here we sample their settings to provide insight
into the dependence of the results on these parameters.

In our experiments, four classifiers were compared: AMA using a
fixed partial ordering, a NMA classifier, a single \naive network
(SNN) with the standard parameterization \citep*{domingos97}, and
a non-restricted two-stage greedy thick-thin (GTT) model selection
over the space of DAGs, which is described below.
%GTT starts
%with an empty graph and repeatedly adds the arc (without creating
%a cycle) that maximally increases the marginal likelihood
%$\cp{D}{S}$ until no arc addition will result in a positive
%increase, then it repeatedly removes arcs until no arc deletion
%will result in a positive increase in
%$\cp{D}{S}$. .

The algorithm used to generate the GTT model, which assumes no
ordering on the nodes, is as follows: \procedure{Greedy thick-thin
search} { \label{proc:gtt} \hfill\hfill\linebreak {\bf Given: \rm
a network $S$ with no arcs.} \hfill\hfill\linebreak
{}Do:
\begin{enumerate}
\item
Repeatedly add the arc whose addition maximally increases the
marginal likelihood $\cp{D}{S}$ without creating a cycle until no
increase is possible.
\item
Repeatedly delete the arc whose deletion maximally increases
$\cp{D}{S}$ until no increase is possible.
\end{enumerate}
}

The inner-loop of each test performed the same procedure: Given
the six parameters $\set{N,N_D,N_{test},K,n,k}$, we did the
following: \procedure{Basic testing loop}
{\label{proc:testing}\linebreak {\bf Given: \rm $N$, $N_D$,
$N_{test}$, $K$, $n$, $k$.} \hfill\hfill\linebreak
{}Do:
\begin{enumerate}
\item
Generate a random Bayesian network $B=\f{G}{N,K}$.
\item
Sample $N_D$ training records and $N_{test}$ test records from the
distribution defined by $B$.
\item
Train two classifiers to be compared, $M_1$ (typically the AMA
classifier) and $M_2$ (the classifier to be compared), on the
training records.
%\item
%Test both classifiers on the test data, generating the ROC curve of each.
%\item
%Calculate the percent increase $\delta$ in $M_1$ ROC area over the
%ROC area of $M_2$.
\item
Test $M_1$ and $M_2$ on the test data, measuring the ROC areas
$R_1$ and $R_2$, respectively, of each.
\item
Calculate the quantity $\delta={R_1-R_2\over 1-R_2}$.
\end{enumerate}
} The {\em ROC Area} of a classifier \citep[cf.,][]{egan75}, is
the area of the curve showing the true-positives of the classifier
versus the false-positives as the sensitivity of the classifier is
swept out from 0 to 1.  It has been used with increasing frequency
in machine learning because it provides an objective evaluation of
a classifier without requiring the specification of a particular
utility function (e.g. zero-one loss).

The performance metric $\delta$ indicates what percentage of
$M_2$'s missing ROC area ($1-R_2$) is covered by $M_1$: If $M_1$
is perfect then $\delta$ will be 1, if $M_1$ is equivalent to
$M_2$ then $\delta$ will be 0, and if $M_1$ is worse than $M_2$
then $\delta$ will be negative (see Figure~\ref{fig:ROC}).
\begin{figure}[pht]
\begin{picture}(130,130)
\put(130,0){%Just the eps file:
\scalebox{0.6}{
\includegraphics{images/ROC.eps}
}}
\end{picture}
\caption{ \label{fig:ROC} The performance metric $\delta$ used in
our experiments measures the fraction of ROC area captured by our
classifier (with ROC area $R_1$) versus some other classifier
(with ROC area $R_2$).}
\end{figure}
For each configuration of experimental parameters, this procedure
was repeated $N_{trials}$ times and $\delta$ was averaged over
these trials.

For some experiments it was necessary to generate networks
randomly. We employed a lazy data generation procedure whereby
node conditional probability distributions were generated only
when they were required by the sampling, a technique which allows
generation of data for arbitrarily dense networks. The algorithm
for selecting network structures at random is as follows:
\procedure{random structure generation} { \hfill\hfill\linebreak
{\bf Given: {\rm a set of nodes $\vect{V}$; number of records,
$N_D$; and maximum in-degree, $K$.}} \hfill\hfill\linebreak
{}Do:
\begin{enumerate}
\item Construct a total ordering $o(\vect{V})$ over the variables.
\item For each node $V_i$ do:
 \begin{enumerate}
 \item
 Choose a number of parents, $n_p$, uniformly at random from $\{1,\ldots,K\}$.
 \item
 Select, uniformly at random, ${\min(n_p,o(V_i))}$ parents $P$ such that $o(P)<o(V_i)$.
 \end{enumerate}
\end{enumerate}
}




%The second alternative method was exact model-averaging over the
%space of \naive networks (NMA). Dash and Cooper
%\shortcite{dash02.icml} showed that this method performed better over a wide
%range of parameters than a standard \naive network.

The choice of the proper set of noninformative structure priors is
non-trivial, and in these experiments we do not attempt to address
the subtle complexities inherent in this process. In all cases we
assume a uniform prior over non-forbidden structures and thus
allow $p_s(X_i,\Pa_i)=1/\mu_i$ for all $i$. These priors will put
overwhelming mass on networks with a ``medium" number of arcs
because there exist many more of these DAGs. We also adopted the
K2 parameter prior which sets $\alpha_{ijk}=1$ for all $(i,j,k)$.
This criterion has the property of weighting all local
distributions of parameters uniformly, and has been shown
empirically to be an effective non-informative prior
\citep{cooper92,heckerman95}. All variables in our synthetic tests
were binary, $N_c=R=2$, and $N_{test}=1000$, and we typically
chose an exponentially increasing sequence of values for $N$ to
test the benefits of the algorithms on a wide-range of scenarios.
In many experiments we sampled the in-degree of generating graphs
$K$ uniformly from the set $\set{1,2,\ldots, N}$; we  use the
notation $K\hookleftarrow\set{1,\ldots, N}$ to denote this
procedure.

In all experiments, $\pi$ for AMA was chosen to be a fixed total
ordering of the variables. At least three heuristics were used to
generate $\pi$: (1) generate a random ordering, (2) generate two
opposite random orderings and average predictions of each, and (3)
use a topological sort of the graph obtained by GTT. In
preliminary experiments, these methods produced comparable
results, but (2) and (3) performed a few percent better.
%; however methods (2) and (3)
%typically performed a few percent higher than method (1); furthermore once
%the greedy search was performed, method (3) was twice as fast as (2)
%because the former only required the construction of a single model.
In all results presented below, method (3) was used to generate
$\pi$.

All abbreviations and symbols are summarized in
Table~\ref{table:symbols} as a reference for the reader.
{%\scriptsize
\begin{table}[ht]
\centering
\begin{tabular}{|c|l|}\hline\hline
\emph{Symbol} & \,\,\,\,\emph{Description} \\ \hline
{}$N$ & Number of nodes \\ \hline
{}$N_D$ & Number of training records \\ \hline
{}$N_{test}$ & Number of testing records \\ \hline
{}$N_{trials}$ & Number of times Procedure~\ref{proc:testing} was repeated \\ \hline
{}$K$ & Maximum in-degree of generating graphs \\ \hline
{}$k$ & Maximum in-degree in $\myclass$ \\ \hline
{}$n$ & Maximum in-degree in summary MA network (Section~\ref{sec:approximation}) \\ \hline
{}SNN & Single \naive network (with feature selection) \\\hline
{}NMA & \Naive model averaging \\\hline
{}GTT & Greedy thick-thin \\\hline
{}AMA & Approximate model averaging \\\hline\hline
\end{tabular}
\caption{Table of symbols relevant to experiments.}
\label{table:symbols}
\end{table}
}



%We tested the MA
%classifiers using simulated data from randomly generated networks
%and from real-world benchmark networks.


\subsection{Experimental Results}
\label{sec:results}
In this section we present a range of experimental tests we
performed using data generated from random graphs, data generated
from the standard benchmark ALARM network, and data from
real-world data sets from the UCI database.


\subsubsection{\Naive Model Averaging versus a Single Naive Network}

It has been shown \citep{domingos97} that the \naive classifier
with the standard parameterization can be optimal under zero-one
loss even when the underlying independence assumptions are
incorrect.  That, together with the fact that calculating
parameters for this model can be done with a single pass through
the data, make it a useful and widely used model for
classification, and it would be interesting if we find a model
that has the same ease of calculation but performed significantly
better. There are, of course, many other classifiers that we could
compare to, in particular, optimizing the conditional likelihood
under the \naive network assumptions corresponds to a logistic
regression model which has also shown to do well for
classification.  We defer comparisons of our method to logistic
regression and other models for future work.

As Section~\ref{sec:naive_ma} shows, using NMA it is possible to
model average over all features sets for a \naive model simply by
reparametrizing a single \naive network according to
Equation~\ref{eqn:naive_MA_params}.  Because of the simplicity of
this technique (an existing \naive classifier could trivially be
replaced with a model-averaging version just by a change in
parameters), we performed an extensive set of comparisons of NMA
versus a SNN using synthetic data generated from
randomly-constructed (not necessarily \naive) Bayesian networks.


Feature selection for the SNN was performed by successively adding
the arc that maximized the posterior probability of the network
structure $S$ until no arc resulted in an increase.  Although this
is a greedy strategy, for SNN under the assumptions taken in this
paper, it results in a structure that globally maximizes the
posterior probability given the data. This can be seen because,
given structure modularity, the marginal likelihood for a given
arc is independent of all other arcs in the network.

We tested the relative performance of SNN versus a single \naive
model (SNN$_{all}$) over {\em all} features (i.e., without any
feature selection) by performing Procedure~\ref{proc:testing} with
$N$ varied over the set $\{$10, 20, 40, 80, 100, 320$\}$, with
$N_D$ varied over the set $\{$100, 200, 400, 800, 1600, 3200,
6400$\}$ and with $K\hookleftarrow[1,\ldots , N]$. We found that
for all configurations of experimental parameters, SNN dominated
SNN$_{all}$, with average $\delta=29\%\pm1\%$. Because of this, we
do not include SNN$_{all}$ in any of our comparisons to AMA, NMA
or GTT.

In the evaluation of NMA performance over SNN performance, we
simultaneously varied $N$ from the set $\{10$, $20$, $40$, $80$,
$160\}$, $N_D$ from the set $\{50$, $100$, $200$, $400$, $800$,
$1600$, $3200$, $6400\}$, and $K$ from the set $\{5$, $10, 20$,
$40, 80$, $160\}$ (obviously however $K\leq N$). We used
$N_{trials}=1000$ in order to establish clear statistical
significance. The results are shown in
Table~\ref{table:NMA_results}. The remaining area covered by NMA
ranged from a fraction of one percent to $17\%$, but in all save
one of the 160 configurations measured, the improvement of NMA was
significant at the $99\%$ level, the general trend being that NMA
performed better for smaller values of $N$ and $N_D$. The lower
and upper quartiles (i.e., the 25\% and 75\% quantiles: the values
of $\delta$ that confine the middle 50\% of the values of $\delta$
that we observed in our tests) show the true spread of the data,
i.e., because of the large number of trials, the confidence
intervals in the mean are not indicative of the widths of the
distributions.

\subsubsection{Model Averaging over $\Lkn$ versus $\Lk$}

Since, as we have already mentioned, averaging over the full class
$\myclass$ requires considerable calculation using
Equation~\ref{eqn:final_prediction_expression}, we must resort in
general to using the single summary network and instead only
averaging over the class $\Lkn$. We were interested in testing
what price we pay in terms of classification for reducing the size
of the space of models. The first set of experiments we performed
tested the degree of error incurred by model averaging over $\Lkn$
instead of the full class $\Lk$.

%The degree of error was measured in terms of the percent
%difference in ROC areas, $\Delta={R_{k}^\pi-R_{kn}^\pi\over
%R_{k}^\pi}$, where $R_{k}^\pi$ is the ROC area of the classifier

\begin{table}[H]
%\begin{picture}(400,350)
%\put(-12,170){
%\begin{minipage}{10in}
%{
\scriptsize \addtolength{\columnsep}{10mm}
\begin{tabular}
{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|}
%{|r|r||r|r|r||r|r|r||r|r|r||r|r|r|}
\hline\hline
\multicolumn{2}{|c|}{$N_D\rightarrow$} & \multicolumn{3}{c|}{50}
& \multicolumn{3}{c|}{100} & \multicolumn{3}{c|}{200} &
\multicolumn{3}{c|}{400}\\\hline
{}  $   N   $   &   $   K   $   &   $   \delta\ (\%)          $   &   $   Q_l $   &   $   Q_u     $   &   $   \delta\ (\%)          $   &   $   Q_l $   &   $   Q_u     $   &   $   \delta\ (\%)         $   &   $   Q_l $   &   $   Q_u     $   &   $   \delta\ (\%)        $   &   $    Q_l    $   &   $   Q_u $\\\hline
\rowcolor[gray]{.8}
{}  $   10  $   &   $   5   $   &   $   17.2    \pm 1.6 $   &   $   8.4 $   &   $   24.0    $   &   $   17.0    \pm 1.4 $   &   $   9.5 $   &   $   22.8    $   &   $   16.5    \pm 1.4 $   &   $   8.7 $   &   $   21.7    $   &   $   14.0    \pm 1.2 $   &   $   7.3 $   &   $   19.4    $   \\\hline
\rowcolor[gray]{.8}
{}  $   10  $   &   $   10  $   &   $   17.1    \pm 1.6 $   &   $   7.7 $   &   $   23.6    $   &   $   16.9    \pm 1.4 $   &   $   9.2 $   &   $   23.9    $   &   $   16.2    \pm 1.4 $   &   $   7.9 $   &   $   23.5    $   &   $   15.5    \pm 1.3 $   &   $   7.8 $   &   $   21.2    $   \\\hline
{}  $   20  $   &   $   5   $   &   $   8.7 \pm 1.1 $   &   $   3.1 $   &   $   12.1    $   &   $   8.7 \pm 1.0 $   &   $   3.7 $   &   $   12.2    $   &   $   8.4 \pm 0.9 $   &   $   4.1 $   &   $   11.3    $   &   $   9.0 \pm 1.0 $   &   $   3.9 $   &   $   13.3    $   \\\hline
{}  $   20  $   &   $   10  $   &   $   8.1 \pm 1.0 $   &   $   3.2 $   &   $   12.4    $   &   $   10.0    \pm 1.3 $   &   $   3.5 $   &   $   13.5    $   &   $   9.6 \pm 1.0 $   &   $   4.7 $   &   $   12.5    $   &   $   8.9 \pm 1.1 $   &   $   3.3 $   &   $   11.9    $   \\\hline
{}  $   20  $   &   $   20  $   &   $   8.5 \pm 1.0 $   &   $   3.7 $   &   $   11.9    $   &   $   9.6 \pm 1.1 $   &   $   3.8 $   &   $   13.9    $   &   $   10.1    \pm 1.1 $   &   $   4.4 $   &   $   13.7    $   &   $   9.8 \pm 1.1 $   &   $   4.2 $   &   $   13.4    $   \\\hline
\rowcolor[gray]{.8}
{}  $   40  $   &   $   5   $   &   $   3.8 \pm 0.8 $   &   $   0.3 $   &   $   7.3 $   &   $   3.5 \pm 0.6 $   &   $   0.8 $   &   $   6.2 $   &   $   4.5 \pm 0.6 $   &   $   1.7 $   &   $   6.9 $   &   $   4.6 \pm 0.6 $   &   $   1.5 $   &   $   5.7 $   \\\hline
\rowcolor[gray]{.8}
{}  $   40  $   &   $   10  $   &   $   3.0 \pm 0.6 $   &   $   0.2 $   &   $   5.5 $   &   $   4.2 \pm 0.6 $   &   $   1.3 $   &   $   6.6 $   &   $   3.8 \pm 0.6 $   &   $   0.8 $   &   $   5.7 $   &   $   4.6 \pm 0.7 $   &   $   1.5 $   &   $   6.2 $   \\\hline
\rowcolor[gray]{.8}
{}  $   40  $   &   $   20  $   &   $   3.0 \pm 0.6 $   &   $   0.2 $   &   $   4.8 $   &   $   4.6 \pm 0.7 $   &   $   1.5 $   &   $   6.9 $   &   $   4.4 \pm 0.9 $   &   $   1.1 $   &   $   6.7 $   &   $   6.1 \pm 1.0 $   &   $   2.1 $   &   $   7.9 $   \\\hline
\rowcolor[gray]{.8}
{}  $   40  $   &   $   40  $   &   $   2.2 \pm 0.5 $   &   $   -0.2    $   &   $   4.2 $   &   $   3.5 \pm 0.7 $   &   $   0.6 $   &   $   5.7 $   &   $   4.6 \pm 0.7 $   &   $   1.4 $   &   $   6.8 $   &   $   5.9 \pm 0.8 $   &   $   2.0 $   &   $   8.1 $   \\\hline
{}  $   80  $   &   $   5   $   &   $   2.8 \pm 0.7 $   &   $   -0.4    $   &   $   4.9 $   &   $   2.7 \pm 0.6 $   &   $   -0.2    $   &   $   5.0 $   &   $   2.4 \pm 0.5 $   &   $   0.1 $   &   $   4.3 $   &   $   2.1 \pm 0.4 $   &   $   0.3 $   &   $   3.8 $   \\\hline
{}  $   80  $   &   $   10  $   &   $   1.6 \pm 0.5 $   &   $   -0.6    $   &   $   2.9 $   &   $   1.5 \pm 0.5 $   &   $   -0.8    $   &   $   3.7 $   &   $   2.1 \pm 0.4 $   &   $   0.0 $   &   $   3.7 $   &   $   2.6 \pm 0.4 $   &   $   0.6 $   &   $   4.4 $   \\\hline
{}  $   80  $   &   $   20  $   &   $   1.2 \pm 0.5 $   &   $   -0.7    $   &   $   2.6 $   &   $   1.3 \pm 0.5 $   &   $   -0.7    $   &   $   2.9 $   &   $   1.9 \pm 0.4 $   &   $   -0.1    $   &   $   3.6 $   &   $   2.4 \pm 0.5 $   &   $   0.2 $   &   $   4.0 $   \\\hline
{}  $   80  $   &   $   40  $   &   $   0.7 \pm 0.5 $   &   $   -1.1    $   &   $   2.1 $   &   $   1.0 \pm 0.4 $   &   $   -1.1    $   &   $   2.8 $   &   $   1.4 \pm 0.5 $   &   $   -0.5    $   &   $   3.1 $   &   $   2.3 \pm 0.5 $   &   $   0.1 $   &   $   3.9 $   \\\hline
{}  $   80  $   &   $   80  $   &   $   0.7 \pm 0.5 $   &   $   -1.0    $   &   $   1.9 $   &   $   1.0 \pm 0.4 $   &   $   -0.8    $   &   $   2.6 $   &   $   1.8 \pm 0.4 $   &   $   -0.1    $   &   $   3.1 $   &   $   2.4 \pm 0.5 $   &   $   0.1 $   &   $   4.4 $   \\\hline
\rowcolor[gray]{.8}
{}  $   160 $   &   $   5   $   &   $   2.0 \pm 0.6 $   &   $   -0.9    $   &   $   3.6 $   &   $   2.2 \pm 0.6 $   &   $   -0.9    $   &   $   4.5 $   &   $   2.2 \pm 0.5 $   &   $   -0.1    $   &   $   4.1 $   &   $   1.6 \pm 0.4 $   &   $   -0.3    $   &   $   3.2 $   \\\hline
\rowcolor[gray]{.8}
{}  $   160 $   &   $   10  $   &   $   1.2 \pm 0.5 $   &   $   -1.0    $   &   $   2.8 $   &   $   1.8 \pm 0.5 $   &   $   -0.5    $   &   $   3.8 $   &   $   1.6 \pm 0.4 $   &   $   -0.6    $   &   $   3.8 $   &   $   1.2 \pm 0.4 $   &   $   -0.6    $   &   $   2.9 $   \\\hline
\rowcolor[gray]{.8}
{}  $   160 $   &   $   20  $   &   $   1.1 \pm 0.5 $   &   $   -0.5    $   &   $   2.2 $   &   $   0.9 \pm 0.4 $   &   $   -1.0    $   &   $   2.6 $   &   $   1.0 \pm 0.4 $   &   $   -0.7    $   &   $   2.9 $   &   $   0.9 \pm 0.4 $   &   $   -1.0    $   &   $   2.6 $   \\\hline
\rowcolor[gray]{.8}
{}  $   160 $   &   $   40  $   &   $   0.6 \pm 0.4 $   &   $   -1.0    $   &   $   1.7 $   &   $   0.5 \pm 0.4 $   &   $   -1.3    $   &   $   2.0 $   &   $   0.5 \pm 0.4 $   &   $   -1.0    $   &   $   1.9 $   &   $   0.8 \pm 0.4 $   &   $   -1.1    $   &   $   2.4 $   \\\hline
\rowcolor[gray]{.8}
{}  $   160 $   &   $   80  $   &   $   0.6 \pm 0.4 $   &   $   -1.1    $   &   $   1.6 $   &   $   0.5 \pm 0.4 $   &   $   -1.3    $   &   $   2.0 $   &   $   0.5 \pm 0.3 $   &   $   -1.2    $   &   $   1.9 $   &   $   0.7 \pm 0.4 $   &   $   -1.1    $   &   $   2.4 $   \\\hline
\rowcolor[gray]{.8}
{}  $   160 $   &   $   160 $   &   $   0.1 \pm 0.3 $   &   $   -1.4    $   &   $   1.5 $   &   $   0.7 \pm 0.4 $   &   $   -1.1    $   &   $   2.0 $   &   $   0.7 \pm 0.3 $   &   $   -0.9    $   &   $   2.3 $   &   $   0.5 \pm 0.4 $   &   $   -1.2    $   &   $   2.1 $   \\\hline
\hline \multicolumn{2}{|c|}{$N_D\rightarrow$} &
\multicolumn{3}{c|}{800}                        &
\multicolumn{3}{c|}{1600}                                       &
\multicolumn{3}{c|}{3200}                                       &
\multicolumn{3}{c|}{6400}\\\hline
{}  $   N   $   &   $   K   $   &   $   \delta\ (\%)          $   &   $   Q_l $   &   $   Q_u     $   &   $   \delta\ (\%)          $   &   $   Q_l $   &   $   Q_u     $   &   $   \delta\ (\%)         $   &   $   Q_l $   &   $   Q_u     $   &   $   \delta\ (\%)        $   &   $    Q_l    $   &   $   Q_u $\\\hline
\rowcolor[gray]{.8}
{}  $   10  $   &   $   5   $   &   $   13.8    \pm 1.3 $   &   $   6.7 $   &   $   19.2    $   &   $   11.5    \pm 1.0 $   &   $   5.2 $   &   $   15.8    $   &   $   11.5    \pm 1.2 $   &   $   4.3 $   &   $   17.1    $   &   $   10.0    \pm 1.3 $   &   $   2.9 $   &   $   14.5    $   \\\hline
\rowcolor[gray]{.8}
{}  $   10  $   &   $   10  $   &   $   12.3    \pm 1.2 $   &   $   5.5 $   &   $   18.1    $   &   $   10.5    \pm 1.2 $   &   $   3.9 $   &   $   14.3    $   &   $   8.4 \pm 1.1 $   &   $   2.9 $   &   $   11.3    $   &   $   8.4 \pm 1.1 $   &   $   2.4 $   &   $   11.9    $   \\\hline
{}  $   20  $   &   $   5   $   &   $   7.7 \pm 0.9 $   &   $   2.6 $   &   $   11.7    $   &   $   7.7 \pm 1.0 $   &   $   1.8 $   &   $   11.8    $   &   $   5.9 \pm 0.9 $   &   $   1.2 $   &   $   8.2 $   &   $   5.7 \pm 1.0 $   &   $   0.9 $   &   $   7.8 $   \\\hline
{}  $   20  $   &   $   10  $   &   $   8.2 \pm 1.0 $   &   $   2.8 $   &   $   12.6    $   &   $   6.0 \pm 0.9 $   &   $   1.6 $   &   $   8.5 $   &   $   3.4 \pm 0.7 $   &   $   0.7 $   &   $   4.0 $   &   $   3.1 \pm 0.6 $   &   $   0.4 $   &   $   3.7 $   \\\hline
{}  $   20  $   &   $   20  $   &   $   8.7 \pm 1.1 $   &   $   2.8 $   &   $   12.6    $   &   $   7.4 \pm 1.0 $   &   $   2.0 $   &   $   11.2    $   &   $   5.8 \pm 0.9 $   &   $   1.1 $   &   $   7.5 $   &   $   5.0 \pm 0.9 $   &   $   0.6 $   &   $   6.7 $   \\\hline
\rowcolor[gray]{.8}
{}  $   40  $   &   $   5   $   &   $   4.6 \pm 0.7 $   &   $   1.3 $   &   $   6.3 $   &   $   3.1 \pm 0.6 $   &   $   0.7 $   &   $   3.9 $   &   $   3.7 \pm 0.7 $   &   $   0.5 $   &   $   4.3 $   &   $   3.4 \pm 0.8 $   &   $   0.2 $   &   $   3.6 $   \\\hline
\rowcolor[gray]{.8}
{}  $   40  $   &   $   10  $   &   $   4.8 \pm 0.7 $   &   $   1.6 $   &   $   6.5 $   &   $   3.5 \pm 0.6 $   &   $   1.0 $   &   $   4.4 $   &   $   3.1 \pm 0.7 $   &   $   0.5 $   &   $   3.3 $   &   $   2.3 \pm 0.6 $   &   $   0.2 $   &   $   2.2 $   \\\hline
\rowcolor[gray]{.8}
{}  $   40  $   &   $   20  $   &   $   6.0 \pm 0.8 $   &   $   1.8 $   &   $   8.2 $   &   $   6.1 \pm 0.9 $   &   $   1.6 $   &   $   8.8 $   &   $   5.4 \pm 0.9 $   &   $   0.8 $   &   $   8.0 $   &   $   5.0 \pm 1.0 $   &   $   0.5 $   &   $   7.7 $   \\\hline
\rowcolor[gray]{.8}
{}  $   40  $   &   $   40  $   &   $   7.5 \pm 1.0 $   &   $   2.7 $   &   $   10.0    $   &   $   6.6 \pm 1.0 $   &   $   1.7 $   &   $   10.0    $   &   $   7.3 \pm 1.0 $   &   $   1.1 $   &   $   11.0    $   &   $   5.9 \pm 1.0 $   &   $   0.6 $   &   $   9.6 $   \\\hline
{}  $   80  $   &   $   5   $   &   $   2.3 \pm 0.4 $   &   $   0.5 $   &   $   3.4 $   &   $   2.0 \pm 0.5 $   &   $   0.3 $   &   $   2.7 $   &   $   2.2 \pm 0.5 $   &   $   0.2 $   &   $   2.7 $   &   $   1.8 \pm 0.5 $   &   $   0.1 $   &   $   1.8 $   \\\hline
{}  $   80  $   &   $   10  $   &   $   2.3 \pm 0.4 $   &   $   0.6 $   &   $   3.6 $   &   $   2.3 \pm 0.4 $   &   $   0.5 $   &   $   3.2 $   &   $   1.9 \pm 0.4 $   &   $   0.4 $   &   $   2.4 $   &   $   1.3 \pm 0.3 $   &   $   0.1 $   &   $   1.4 $   \\\hline
{}  $   80  $   &   $   20  $   &   $   2.7 \pm 0.5 $   &   $   0.7 $   &   $   4.5 $   &   $   3.0 \pm 0.5 $   &   $   0.8 $   &   $   4.4 $   &   $   3.9 \pm 0.6 $   &   $   0.8 $   &   $   5.1 $   &   $   3.6 \pm 0.6 $   &   $   0.6 $   &   $   5.1 $   \\\hline
{}  $   80  $   &   $   40  $   &   $   2.9 \pm 0.5 $   &   $   0.6 $   &   $   4.4 $   &   $   3.9 \pm 0.6 $   &   $   0.9 $   &   $   5.6 $   &   $   5.4 \pm 0.8 $   &   $   1.3 $   &   $   8.0 $   &   $   5.2 \pm 0.7 $   &   $   1.0 $   &   $   7.6 $   \\\hline
{}  $   80  $   &   $   80  $   &   $   3.3 \pm 0.5 $   &   $   0.9 $   &   $   5.3 $   &   $   4.0 \pm 0.6 $   &   $   1.0 $   &   $   6.3 $   &   $   4.9 \pm 0.8 $   &   $   1.0 $   &   $   7.5 $   &   $   5.2 \pm 0.7 $   &   $   0.7 $   &   $   7.9 $   \\\hline
\rowcolor[gray]{.8}
{}  $   160 $   &   $   5   $   &   $   1.3 \pm 0.4 $   &   $   -0.1    $   &   $   2.8 $   &   $   0.8 \pm 0.3 $   &   $   -0.5    $   &   $   1.9 $   &   $   0.9 \pm 0.3 $   &   $   -0.1    $   &   $   1.4 $   &   $   0.9 \pm 0.3 $   &   $   0.0 $   &   $   1.2 $   \\\hline
\rowcolor[gray]{.8}
{}  $   160 $   &   $   10  $   &   $   1.2 \pm 0.3 $   &   $   -0.6    $   &   $   2.7 $   &   $   1.2 \pm 0.3 $   &   $   0.0 $   &   $   2.6 $   &   $   0.8 \pm 0.3 $   &   $   -0.2    $   &   $   1.7 $   &   $   0.9 \pm 0.2 $   &   $   -0.1    $   &   $   1.3 $   \\\hline
\rowcolor[gray]{.8}
{}  $   160 $   &   $   20  $   &   $   1.2 \pm 0.4 $   &   $   -0.7    $   &   $   3.0 $   &   $   1.2 \pm 0.3 $   &   $   -0.4    $   &   $   2.6 $   &   $   1.7 \pm 0.4 $   &   $   0.1 $   &   $   2.4 $   &   $   2.1 \pm 0.4 $   &   $   0.1 $   &   $   3.3 $   \\\hline
\rowcolor[gray]{.8}
{}  $   160 $   &   $   40  $   &   $   1.1 \pm 0.3 $   &   $   -0.6    $   &   $   2.7 $   &   $   1.6 \pm 0.4 $   &   $   -0.4    $   &   $   2.8 $   &   $   2.6 \pm 0.5 $   &   $   0.3 $   &   $   3.9 $   &   $   2.6 \pm 0.5 $   &   $   0.3 $   &   $   3.9 $   \\\hline
\rowcolor[gray]{.8}
{}  $   160 $   &   $   80  $   &   $   0.7 \pm 0.4 $   &   $   -1.2    $   &   $   2.3 $   &   $   1.6 \pm 0.4 $   &   $   -0.4    $   &   $   3.2 $   &   $   2.2 \pm 0.5 $   &   $   -0.2    $   &   $   4.0 $   &   $   3.0 \pm 0.5 $   &   $   0.5 $   &   $   4.7 $   \\\hline
\rowcolor[gray]{.8}
{}  $   160 $   &   $   160 $   &   $   1.0 \pm 0.4 $   &   $   -0.8    $   &   $   2.5 $   &   $   1.7 \pm 0.4 $   &   $   0.0 $   &   $   3.1 $   &   $   2.6 \pm 0.5 $   &   $   0.4 $   &   $   4.0 $   &   $   3.4 \pm 0.5 $   &   $   0.6 $   &   $   5.5 $   \\\hline
\end{tabular}
%}
%end scriptsize
%\end{minipage}
%}
%\end{picture}
\caption{Exploration of NMA performance versus SNN performance as
$N_D$, $N$ and $K$ are varied. The error ranges are 99\%
confidence intervals in the mean. $Q_l$ and $Q_u$ denote the lower
and upper quartiles, respectively.} \label{table:NMA_results}
\end{table}


\noindent
%
%averaging over $\Lk$ and $R_{kn}^\pi$ is the ROC area of the
%classifier averaging over $\Lkn$. The classifications over $\Lk$
%were calculated using
%Equation~\ref{eqn:final_prediction_expression} directly, whereas
%those over $\Lkn$ were performed with the single summary network.
%$\Delta$ is a perhaps a more intuitive measure than $\delta$,
%however it is less stable (because $\Delta$ can diverge).
%Nonetheless, it is informative and we show it here rather than
%$\delta$ for convenience.

These experiments tested the sensitivity on the approximation
parameter $n$ and the number of nodes $N$. Setting $N_D=100$,
$N_{trials}=40$, varying $N$ over the values $\set{20,
 40, 80, 160}$, varying $n$ over the values $\set{1, 5, 7,
10, 12, 14}$, varying $k$ over the values $\set{1, 2, 3, 4}$, and
$K\hookleftarrow [1,\ldots, N]$. The compiled results are shown in
Table~\ref{table:approximation_error}. The ranges denote the 99\%
confidence interval of the mean.
\begin{table}[htb]
\begin{picture}(100,250)
\put(30,10)
{%everything
\put(100,110){
\begin{minipage}{4in}
%\begin{table}[H]
{%\scriptsize
\begin{tabular}{|r|r|r|r|}\hline\hline
$N$ & $k$ & $n$ & $\delta$ (\%)\,\,\,\,\,\,\,\,\\\hline\hline
{}20 & 1 & 7 & $-0.1\pm 0.4$ \\\hline
{}40 & 1 & 7 & $0.0\pm 0.5$  \\\hline
{}80 & 1 & 7 & $1\pm 1$  \\\hline
{}160 & 1 & 7 & $-2\pm 2$  \\\hline\hline
{}40 & 1 & 1 & $2\pm 2$  \\\hline
{}40 & 1 & 5 & $0.3\pm 0.8$  \\\hline
{}40 & 1 & 7 & $0.0\pm 0.5$ \\\hline
{}40 & 1 & 10 & $0.1\pm 0.6$  \\\hline
{}40 & 1 & 12 & $-0.1\pm 0.4$  \\\hline
{}40 & 1 & 14 & $-0.5\pm 0.3$  \\\hline\hline
{}20 & 1 & 7 & $-0.1\pm 0.4$  \\\hline
{}20 & 2 & 7 & $0.2\pm 0.9$  \\\hline
{}20 & 3 & 7 & $1\pm 1$  \\\hline
{}20 & 4 & 7 & $0\pm 1$  \\\hline
\hline
\end{tabular}

}%end scriptsize
\end{minipage}
} }
\end{picture}
\caption{The values of $\delta$ between model averaging over $\Lk$
and model averaging over $\Lkn$ as various parameters are varied.}
\label{table:approximation_error}
\end{table}
Table~\ref{table:approximation_error} shows that for a wide range
of sensible values for these three parameters, we pay little
classification cost by averaging over $\Lkn$ versus $\Lk$.
Especially interesting is that the difference is small even for
quite small values of the approximation level $n$.  Even for
$n\gsim 5$ the percent remaining area captured by averaging over
the full class is less than $1.1\%$ (i.e., $0.3\%+0.80\%$) with
probability $P>0.99$. Also, one might expect the approximation
error to increase as $k$ was increased, since for a fixed $n$,
$\Lk$ includes increasingly more structures than $\Lkn$ as $k$
increases. Table~\ref{table:approximation_error} shows that over
the range of $k$ considered, there is not much sensitivity in the
results to $k$. These results, although not comprehensive in
scope, support that averaging over $\Lkn$ does not severely
degrade the ROC area relative to model averaging over $\Lk$. This
result is important because only over $\Lkn$ can we select a
single tractable model to do model averaging via standard Bayesian
network inference.

\subsubsection{AMA versus GTT, NMA and SNN}
In terms of classification accuracy, a more practical test of the
benefits of AMA is to contrast its performance directly with other
algorithms. In our first set of measurements to test this, we
generated synthetic data and measured the performance of AMA
relative to GTT, NMA and SNN. We varied $N$ over the set
$\set{20,40}$ (much higher was too time-consuming for the complete
range of $k$ and $n$ below), and simultaneously varied $N_D$ from
$\set{100,1000}$, $k$ from 2--5, $n$ from 4--14 and
$K\hookleftarrow\set{1,\ldots, N}$. In these experiments,
$N_{trials}$ varied from 50 to $\sim 100$, depending on the speed
at which the AMA model could be learned. The results for $N=20$
and $40$ are shown in Table~\ref{table:AMA_results_20} and
\ref{table:AMA_results_40}, respectively. In these and all
subsequent tables (except where explicitly stated), the error
ranges represent $99\%$ confidence intervals, and $Q_l$ and $Q_u$
denote the lower and upper quartiles, respectively.

\begin{table}[pht]
\centering
%\begin{picture}(100,510)
%\put(0,220){
%\begin{minipage}{5in}
{\footnotesize
\begin{tabular}{|r|r|r||r|r|r||r|r|r||r|r|r|}\hline\hline
\multicolumn{3}{|c||}{Configuration} & \multicolumn{3}{c||}{vs.
NMA} & \multicolumn{3}{c||}{vs. GTT} & \multicolumn{3}{c|}{vs.
SNN} \\\hline
    $N_D$   &   $k$ &   $n$ &      \multicolumn{1}{c|}{$\delta\ (\%)$}             &   $Q_l$   &   $Q_u$   &       \multicolumn{1}{c|}{$\delta\ (\%)$}            &   $Q_l$   &   $Q_u$   & \multicolumn{1}{c|}{$\delta\ (\%)$} &   $Q_l$   &   $Q_u$   \\\hline
\rowcolor[gray]{.9}
{}  100 &   2   &   4   &   $   3   \pm 3   $   &   -4  &   7   &   $   9   \pm 3   $   &   0   &   18  &   $   13  \pm 3   $   &   5   &   19  \\\hline
\rowcolor[gray]{.9}
{}  100 &   2   &   6   &   $   6   \pm 3   $   &   -2  &   10  &   $   9   \pm 4   $   &   2   &   16  &   $   16  \pm 4   $   &   5   &   26  \\\hline
\rowcolor[gray]{.9}
{}  100 &   2   &   8   &   $   5   \pm 3   $   &   -2  &   8   &   $   8   \pm 3   $   &   2   &   16  &   $   14  \pm 3   $   &   5   &   20  \\\hline
\rowcolor[gray]{.9}
{}  100 &   2   &   10  &   $   7   \pm 3   $   &   -1  &   13  &   $   10  \pm 3   $   &   2   &   18  &   $   15  \pm 4   $   &   4   &   24  \\\hline
\rowcolor[gray]{.9}
{}  100 &   2   &   12  &   $   5   \pm 2   $   &   -2  &   9   &   $   11  \pm 3   $   &   4   &   18  &   $   13  \pm 3   $   &   6   &   20  \\\hline
\rowcolor[gray]{.9}
{}  100 &   2   &   14  &   $   7   \pm 3   $   &   -1  &   9   &   $   11  \pm 4   $   &   4   &   18  &   $   16  \pm 3   $   &   6   &   24  \\\hline
{}  100 &   3   &   4   &   $   4   \pm 4   $   &   -4  &   10  &   $   8   \pm 3   $   &   2   &   12  &   $   13  \pm 4   $   &   2   &   21  \\\hline
{}  100 &   3   &   6   &   $   6   \pm 4   $   &   -2  &   13  &   $   12  \pm 3   $   &   4   &   17  &   $   14  \pm 4   $   &   6   &   23  \\\hline
{}  100 &   3   &   8   &   $   9   \pm 4   $   &   -2  &   16  &   $   13  \pm 3   $   &   5   &   18  &   $   19  \pm 4   $   &   7   &   27  \\\hline
{}  100 &   3   &   10  &   $   8   \pm 4   $   &   -2  &   17  &   $   11  \pm 3   $   &   3   &   16  &   $   17  \pm 4   $   &   6   &   24  \\\hline
{}  100 &   3   &   12  &   $   7   \pm 3   $   &   -1  &   9   &   $   10  \pm 2   $   &   3   &   14  &   $   17  \pm 3   $   &   6   &   28  \\\hline
{}  100 &   3   &   14  &   $   6   \pm 4   $   &   -3  &   12  &   $   12  \pm 3   $   &   5   &   18  &   $   15  \pm 4   $   &   3   &   22  \\\hline
\rowcolor[gray]{.9}
{}  100 &   4   &   4   &   $   5   \pm 4   $   &   -4  &   14  &   $   8   \pm 3   $   &   2   &   12  &   $   15  \pm 4   $   &   4   &   22  \\\hline
\rowcolor[gray]{.9}
{}  100 &   4   &   6   &   $   5   \pm 3   $   &   -2  &   12  &   $   9   \pm 2   $   &   3   &   15  &   $   15  \pm 3   $   &   6   &   24  \\\hline
\rowcolor[gray]{.9}
{}  100 &   4   &   8   &   $   5   \pm 4   $   &   -2  &   11  &   $   10  \pm 3   $   &   3   &   14  &   $   13  \pm 4   $   &   3   &   23  \\\hline
\rowcolor[gray]{.9}
{}  100 &   4   &   10  &   $   7   \pm 3   $   &   -2  &   13  &   $   12  \pm 3   $   &   3   &   17  &   $   16  \pm 3   $   &   6   &   23  \\\hline
\rowcolor[gray]{.9}
{}  100 &   4   &   12  &   $   4   \pm 3   $   &   -3  &   8   &   $   9   \pm 2   $   &   3   &   14  &   $   13  \pm 3   $   &   4   &   21  \\\hline
\rowcolor[gray]{.9}
{}  100 &   4   &   14  &   $   8   \pm 4   $   &   -1  &   15  &   $   12  \pm 3   $   &   4   &   18  &   $   17  \pm 3   $   &   8   &   27  \\\hline
{}  100 &   5   &   6   &   $   7   \pm 4   $   &   -3  &   16  &   $   10  \pm 3   $   &   3   &   13  &   $   15  \pm 4   $   &   4   &   23  \\\hline
{}  100 &   5   &   8   &   $   5   \pm 3   $   &   -3  &   10  &   $   10  \pm 2   $   &   5   &   13  &   $   13  \pm 3   $   &   3   &   21  \\\hline
{}  100 &   5   &   10  &   $   4   \pm 4   $   &   -2  &   11  &   $   9   \pm 3   $   &   3   &   14  &   $   12  \pm 4   $   &   4   &   20  \\\hline
{}  100 &   5   &   12  &   $   6   \pm 3   $   &   -2  &   10  &   $   12  \pm 3   $   &   4   &   17  &   $   16  \pm 3   $   &   7   &   24  \\\hline
{}  100 &   5   &   14  &   $   6   \pm 3   $   &   -2  &   9   &   $   10  \pm 2   $   &   4   &   15  &   $   15  \pm 3   $   &   6   &   19  \\\hline
\hline \rowcolor[gray]{.9}
{}  1000    &   2   &   4   &   $   10  \pm 4   $   &   -2  &   18  &   $   -8  \pm 5   $   &   -21 &   10  &   $   17  \pm 3   $   &   6   &   26  \\\hline
\rowcolor[gray]{.9}
{}  1000    &   2   &   6   &   $   11  \pm 3   $   &   1   &   19  &   $   -12 \pm 7   $   &   -26 &   11  &   $   19  \pm 3   $   &   11  &   27  \\\hline
\rowcolor[gray]{.9}
{}  1000    &   2   &   8   &   $   10  \pm 3   $   &   1   &   17  &   $   -15 \pm 7   $   &   -33 &   7   &   $   17  \pm 3   $   &   7   &   24  \\\hline
\rowcolor[gray]{.9}
{}  1000    &   2   &   10  &   $   12  \pm 4   $   &   2   &   23  &   $   -8  \pm 8   $   &   -17 &   13  &   $   20  \pm 4   $   &   13  &   30  \\\hline
\rowcolor[gray]{.9}
{}  1000    &   2   &   12  &   $   10  \pm 3   $   &   2   &   18  &   $   -10 \pm 7   $   &   -23 &   10  &   $   16  \pm 3   $   &   9   &   23  \\\hline
\rowcolor[gray]{.9}
{}  1000    &   2   &   14  &   $   10  \pm 3   $   &   2   &   18  &   $   -7  \pm 5   $   &   -21 &   10  &   $   18  \pm 3   $   &   11  &   23  \\\hline
{}  1000    &   3   &   4   &   $   14  \pm 4   $   &   2   &   23  &   $   1   \pm 4   $   &   -8  &   9   &   $   23  \pm 4   $   &   11  &   34  \\\hline
{}  1000    &   3   &   6   &   $   15  \pm 4   $   &   2   &   26  &   $   -2  \pm 5   $   &   -7  &   9   &   $   21  \pm 3   $   &   11  &   31  \\\hline
{}  1000    &   3   &   8   &   $   20  \pm 4   $   &   6   &   31  &   $   2   \pm 4   $   &   -6  &   14  &   $   27  \pm 4   $   &   16  &   35  \\\hline
{}  1000    &   3   &   10  &   $   15  \pm 3   $   &   3   &   23  &   $   0   \pm 5   $   &   -9  &   13  &   $   21  \pm 3   $   &   13  &   28  \\\hline
{}  1000    &   3   &   12  &   $   18  \pm 4   $   &   5   &   29  &   $   4   \pm 4   $   &   -3  &   14  &   $   24  \pm 4   $   &   13  &   33  \\\hline
{}  1000    &   3   &   14  &   $   18  \pm 4   $   &   4   &   28  &   $   1   \pm 4   $   &   -3  &   12  &   $   24  \pm 3   $   &   13  &   33  \\\hline
\rowcolor[gray]{.9}
{}  1000    &   4   &   4   &   $   23  \pm 5   $   &   5   &   37  &   $   6   \pm 3   $   &   1   &   12  &   $   29  \pm 4   $   &   15  &   42  \\\hline
\rowcolor[gray]{.9}
{}  1000    &   4   &   6   &   $   20  \pm 5   $   &   2   &   34  &   $   8   \pm 3   $   &   2   &   13  &   $   29  \pm 4   $   &   14  &   41  \\\hline
\rowcolor[gray]{.9}
{}  1000    &   4   &   8   &   $   24  \pm 5   $   &   5   &   40  &   $   8   \pm 3   $   &   2   &   12  &   $   31  \pm 4   $   &   15  &   45  \\\hline
\rowcolor[gray]{.9}
{}  1000    &   4   &   10  &   $   21  \pm 4   $   &   8   &   32  &   $   6   \pm 3   $   &   1   &   15  &   $   28  \pm 3   $   &   18  &   37  \\\hline
\rowcolor[gray]{.9}
{}  1000    &   4   &   12  &   $   20  \pm 4   $   &   8   &   32  &   $   7   \pm 2   $   &   1   &   14  &   $   27  \pm 3   $   &   18  &   37  \\\hline
\rowcolor[gray]{.9}
{}  1000    &   4   &   14  &   $   25  \pm 4   $   &   7   &   37  &   $   8   \pm 3   $   &   1   &   14  &   $   31  \pm 4   $   &   17  &   45  \\\hline
{}  1000    &   5   &   6   &   $   23  \pm 4   $   &   6   &   38  &   $   9   \pm 3   $   &   3   &   15  &   $   28  \pm 4   $   &   16  &   39  \\\hline
{}  1000    &   5   &   8   &   $   23  \pm 5   $   &   6   &   37  &   $   10  \pm 3   $   &   3   &   14  &   $   29  \pm 4   $   &   15  &   42  \\\hline
{}  1000    &   5   &   10  &   $   26  \pm 5   $   &   9   &   40  &   $   9   \pm 2   $   &   3   &   12  &   $   32  \pm 4   $   &   18  &   45  \\\hline
{}  1000    &   5   &   12  &   $   25  \pm 4   $   &   12  &   38  &   $   10  \pm 3   $   &   2   &   16  &   $   31  \pm 4   $   &   20  &   42  \\\hline
{}  1000    &   5   &   14  &   $   23  \pm 4   $   &   8   &   38  &   $   9   \pm 3   $   &   2   &   16  &   $   28  \pm 4   $   &   15  &   42  \\\hline
\hline
\end{tabular}
}%end scriptsize
%\end{minipage}
%}
%\end{picture}
\caption{Exploration of AMA performance for $N=20$ as $N_D$, $k$
and $n$ are varied. Error ranges denote the 99\% confidence
intervals; $Q_l$ and $Q_u$ denote the lower and upper quartiles,
respectively.
\label{table:AMA_results_20}
\label{table:AMA_results_20b}
}
\end{table}


%\begin{table}[pht]
%\centering
%%\begin{picture}(100,510)
%%\put(0,220){
%%\begin{minipage}{5in}
%{%\footnotesize
%\begin{tabular}{|r|r|r||r|r|r||r|r|r||r|r|r|}\hline\hline
%\multicolumn{3}{|c||}{Configuration} & \multicolumn{3}{c||}{vs. NMA} &
%\multicolumn{3}{c||}{vs. GTT} & \multicolumn{3}{c|}{vs. SNN} \\\hline
%    $N_D$   &   $k$ &   $n$ &      \multicolumn{1}{c|}{$\delta\ (\%)$}             &   $Q_l$   &   $Q_u$   &       \multicolumn{1}{c|}{$\delta\ (\%)$}            &   $Q_l$   &   $Q_u$   & \multicolumn{1}{c|}{$\delta\ (\%)$} &   $Q_l$   &   $Q_u$   \\\hline
%\rowcolor[gray]{.9}
%{}  100 &   2   &   4   &   $   3   \pm 3   $   &   -4  &   7   &   $   9   \pm 3   $   &   0   &   18  &   $   13  \pm 3   $   &   5   &   19  \\\hline
%\rowcolor[gray]{.9}
%{}  100 &   2   &   6   &   $   6   \pm 3   $   &   -2  &   10  &   $   9   \pm 4   $   &   2   &   16  &   $   16  \pm 4   $   &   5   &   26  \\\hline
%\rowcolor[gray]{.9}
%{}  100 &   2   &   8   &   $   5   \pm 3   $   &   -2  &   8   &   $   8   \pm 3   $   &   2   &   16  &   $   14  \pm 3   $   &   5   &   20  \\\hline
%\rowcolor[gray]{.9}
%{}  100 &   2   &   10  &   $   7   \pm 3   $   &   -1  &   13  &   $   10  \pm 3   $   &   2   &   18  &   $   15  \pm 4   $   &   4   &   24  \\\hline
%\rowcolor[gray]{.9}
%{}  100 &   2   &   12  &   $   5   \pm 2   $   &   -2  &   9   &   $   11  \pm 3   $   &   4   &   18  &   $   13  \pm 3   $   &   6   &   20  \\\hline
%\rowcolor[gray]{.9}
%{}  100 &   2   &   14  &   $   7   \pm 3   $   &   -1  &   9   &   $   11  \pm 4   $   &   4   &   18  &   $   16  \pm 3   $   &   6   &   24  \\\hline
%{}  100 &   3   &   4   &   $   4   \pm 4   $   &   -4  &   10  &   $   8   \pm 3   $   &   2   &   12  &   $   13  \pm 4   $   &   2   &   21  \\\hline
%{}  100 &   3   &   6   &   $   6   \pm 4   $   &   -2  &   13  &   $   12  \pm 3   $   &   4   &   17  &   $   14  \pm 4   $   &   6   &   23  \\\hline
%{}  100 &   3   &   8   &   $   9   \pm 4   $   &   -2  &   16  &   $   13  \pm 3   $   &   5   &   18  &   $   19  \pm 4   $   &   7   &   27  \\\hline
%{}  100 &   3   &   10  &   $   8   \pm 4   $   &   -2  &   17  &   $   11  \pm 3   $   &   3   &   16  &   $   17  \pm 4   $   &   6   &   24  \\\hline
%{}  100 &   3   &   12  &   $   7   \pm 3   $   &   -1  &   9   &   $   10  \pm 2   $   &   3   &   14  &   $   17  \pm 3   $   &   6   &   28  \\\hline
%{}  100 &   3   &   14  &   $   6   \pm 4   $   &   -3  &   12  &   $   12  \pm 3   $   &   5   &   18  &   $   15  \pm 4   $   &   3   &   22  \\\hline
%\rowcolor[gray]{.9}
%{}  100 &   4   &   4   &   $   5   \pm 4   $   &   -4  &   14  &   $   8   \pm 3   $   &   2   &   12  &   $   15  \pm 4   $   &   4   &   22  \\\hline
%\rowcolor[gray]{.9}
%{}  100 &   4   &   6   &   $   5   \pm 3   $   &   -2  &   12  &   $   9   \pm 2   $   &   3   &   15  &   $   15  \pm 3   $   &   6   &   24  \\\hline
%\rowcolor[gray]{.9}
%{}  100 &   4   &   8   &   $   5   \pm 4   $   &   -2  &   11  &   $   10  \pm 3   $   &   3   &   14  &   $   13  \pm 4   $   &   3   &   23  \\\hline
%\rowcolor[gray]{.9}
%{}  100 &   4   &   10  &   $   7   \pm 3   $   &   -2  &   13  &   $   12  \pm 3   $   &   3   &   17  &   $   16  \pm 3   $   &   6   &   23  \\\hline
%\rowcolor[gray]{.9}
%{}  100 &   4   &   12  &   $   4   \pm 3   $   &   -3  &   8   &   $   9   \pm 2   $   &   3   &   14  &   $   13  \pm 3   $   &   4   &   21  \\\hline
%\rowcolor[gray]{.9}
%{}  100 &   4   &   14  &   $   8   \pm 4   $   &   -1  &   15  &   $   12  \pm 3   $   &   4   &   18  &   $   17  \pm 3   $   &   8   &   27  \\\hline
%{}  100 &   5   &   6   &   $   7   \pm 4   $   &   -3  &   16  &   $   10  \pm 3   $   &   3   &   13  &   $   15  \pm 4   $   &   4   &   23  \\\hline
%{}  100 &   5   &   8   &   $   5   \pm 3   $   &   -3  &   10  &   $   10  \pm 2   $   &   5   &   13  &   $   13  \pm 3   $   &   3   &   21  \\\hline
%{}  100 &   5   &   10  &   $   4   \pm 4   $   &   -2  &   11  &   $   9   \pm 3   $   &   3   &   14  &   $   12  \pm 4   $   &   4   &   20  \\\hline
%{}  100 &   5   &   12  &   $   6   \pm 3   $   &   -2  &   10  &   $   12  \pm 3   $   &   4   &   17  &   $   16  \pm 3   $   &   7   &   24  \\\hline
%{}  100 &   5   &   14  &   $   6   \pm 3   $   &   -2  &   9   &   $   10  \pm 2   $   &   4   &   15  &   $   15  \pm 3   $   &   6   &   19  \\\hline
%\hline
%\end{tabular}
%}%end scriptsize
%%\end{minipage}
%%}
%%\end{picture}
%\caption{Exploration of AMA performance over parameter space for $N=20$ and $N_D=100$. Error terms denote
%the 99\% confidence intervals; $Q_l$ and $Q_u$ denote the lower
%and upper quartiles, respectively.}
%\label{table:AMA_results_20}
%\end{table}
%\begin{table}[pht]
%\centering
%%\begin{picture}(100,510)
%%\put(0,220){
%%\begin{minipage}{5in}
%{%\footnotesize
%\begin{tabular}{|r|r|r||r|r|r||r|r|r||r|r|r|}\hline\hline
%\multicolumn{3}{|c||}{Configuration} & \multicolumn{3}{c||}{vs. NMA} &
%\multicolumn{3}{c||}{vs. GTT} & \multicolumn{3}{c|}{vs. SNN} \\\hline
%    $N_D$   &   $k$ &   $n$ &      \multicolumn{1}{c|}{$\delta\ (\%)$}             &   $Q_l$   &   $Q_u$   &       \multicolumn{1}{c|}{$\delta\ (\%)$}            &   $Q_l$   &   $Q_u$   & \multicolumn{1}{c|}{$\delta\ (\%)$} &   $Q_l$   &   $Q_u$   \\\hline
%\rowcolor[gray]{.9}
%{}  1000    &   2   &   4   &   $   10  \pm 4   $   &   -2  &   18  &   $   -8  \pm 5   $   &   -21 &   10  &   $   17  \pm 3   $   &   6   &   26  \\\hline
%\rowcolor[gray]{.9}
%{}  1000    &   2   &   6   &   $   11  \pm 3   $   &   1   &   19  &   $   -12 \pm 7   $   &   -26 &   11  &   $   19  \pm 3   $   &   11  &   27  \\\hline
%\rowcolor[gray]{.9}
%{}  1000    &   2   &   8   &   $   10  \pm 3   $   &   1   &   17  &   $   -15 \pm 7   $   &   -33 &   7   &   $   17  \pm 3   $   &   7   &   24  \\\hline
%\rowcolor[gray]{.9}
%{}  1000    &   2   &   10  &   $   12  \pm 4   $   &   2   &   23  &   $   -8  \pm 8   $   &   -17 &   13  &   $   20  \pm 4   $   &   13  &   30  \\\hline
%\rowcolor[gray]{.9}
%{}  1000    &   2   &   12  &   $   10  \pm 3   $   &   2   &   18  &   $   -10 \pm 7   $   &   -23 &   10  &   $   16  \pm 3   $   &   9   &   23  \\\hline
%\rowcolor[gray]{.9}
%{}  1000    &   2   &   14  &   $   10  \pm 3   $   &   2   &   18  &   $   -7  \pm 5   $   &   -21 &   10  &   $   18  \pm 3   $   &   11  &   23  \\\hline
%{}  1000    &   3   &   4   &   $   14  \pm 4   $   &   2   &   23  &   $   1   \pm 4   $   &   -8  &   9   &   $   23  \pm 4   $   &   11  &   34  \\\hline
%{}  1000    &   3   &   6   &   $   15  \pm 4   $   &   2   &   26  &   $   -2  \pm 5   $   &   -7  &   9   &   $   21  \pm 3   $   &   11  &   31  \\\hline
%{}  1000    &   3   &   8   &   $   20  \pm 4   $   &   6   &   31  &   $   2   \pm 4   $   &   -6  &   14  &   $   27  \pm 4   $   &   16  &   35  \\\hline
%{}  1000    &   3   &   10  &   $   15  \pm 3   $   &   3   &   23  &   $   0   \pm 5   $   &   -9  &   13  &   $   21  \pm 3   $   &   13  &   28  \\\hline
%{}  1000    &   3   &   12  &   $   18  \pm 4   $   &   5   &   29  &   $   4   \pm 4   $   &   -3  &   14  &   $   24  \pm 4   $   &   13  &   33  \\\hline
%{}  1000    &   3   &   14  &   $   18  \pm 4   $   &   4   &   28  &   $   1   \pm 4   $   &   -3  &   12  &   $   24  \pm 3   $   &   13  &   33  \\\hline
%\rowcolor[gray]{.9}
%{}  1000    &   4   &   4   &   $   23  \pm 5   $   &   5   &   37  &   $   6   \pm 3   $   &   1   &   12  &   $   29  \pm 4   $   &   15  &   42  \\\hline
%\rowcolor[gray]{.9}
%{}  1000    &   4   &   6   &   $   20  \pm 5   $   &   2   &   34  &   $   8   \pm 3   $   &   2   &   13  &   $   29  \pm 4   $   &   14  &   41  \\\hline
%\rowcolor[gray]{.9}
%{}  1000    &   4   &   8   &   $   24  \pm 5   $   &   5   &   40  &   $   8   \pm 3   $   &   2   &   12  &   $   31  \pm 4   $   &   15  &   45  \\\hline
%\rowcolor[gray]{.9}
%{}  1000    &   4   &   10  &   $   21  \pm 4   $   &   8   &   32  &   $   6   \pm 3   $   &   1   &   15  &   $   28  \pm 3   $   &   18  &   37  \\\hline
%\rowcolor[gray]{.9}
%{}  1000    &   4   &   12  &   $   20  \pm 4   $   &   8   &   32  &   $   7   \pm 2   $   &   1   &   14  &   $   27  \pm 3   $   &   18  &   37  \\\hline
%\rowcolor[gray]{.9}
%{}  1000    &   4   &   14  &   $   25  \pm 4   $   &   7   &   37  &   $   8   \pm 3   $   &   1   &   14  &   $   31  \pm 4   $   &   17  &   45  \\\hline
%{}  1000    &   5   &   6   &   $   23  \pm 4   $   &   6   &   38  &   $   9   \pm 3   $   &   3   &   15  &   $   28  \pm 4   $   &   16  &   39  \\\hline
%{}  1000    &   5   &   8   &   $   23  \pm 5   $   &   6   &   37  &   $   10  \pm 3   $   &   3   &   14  &   $   29  \pm 4   $   &   15  &   42  \\\hline
%{}  1000    &   5   &   10  &   $   26  \pm 5   $   &   9   &   40  &   $   9   \pm 2   $   &   3   &   12  &   $   32  \pm 4   $   &   18  &   45  \\\hline
%{}  1000    &   5   &   12  &   $   25  \pm 4   $   &   12  &   38  &   $   10  \pm 3   $   &   2   &   16  &   $   31  \pm 4   $   &   20  &   42  \\\hline
%{}  1000    &   5   &   14  &   $   23  \pm 4   $   &   8   &   38  &   $   9   \pm 3   $   &   2   &   16  &   $   28  \pm 4   $   &   15  &   42  \\\hline
%\hline
%\end{tabular}
%}%end scriptsize
%%\end{minipage}
%%}
%%\end{picture}
%\caption{Exploration of AMA performance over parameter space for $N=20$ and $N_D=1000$.}
%\label{table:AMA_results_20b}
%\end{table}
\begin{table}[pht]
\centering
%\begin{picture}(100,270)
%\put(-10,90){
%\begin{minipage}{5in}
{%\small
\begin{tabular}{|r|r|r||r|r|r||r|r|r||r|r|r|}\hline\hline
\multicolumn{3}{|c||}{Configuration} & \multicolumn{3}{c||}{vs.
NMA} & \multicolumn{3}{c||}{vs. GTT} & \multicolumn{3}{c|}{vs.
SNN} \\\hline
    $N_D$   &   $k$ &   $n$ &      \multicolumn{1}{c|}{$\delta\ (\%)$}             &   $Q_l$   &   $Q_u$   &       \multicolumn{1}{c|}{$\delta\ (\%)$}            &   $Q_l$   &   $Q_u$   & \multicolumn{1}{c|}{$\delta\ (\%)$} &   $Q_l$   &   $Q_u$   \\\hline
\rowcolor[gray]{.9}
{}  100 &   2   &   4   &   $   1   \pm 3   $   &   -5  &   5   &   $   6   \pm 4   $       &   -1   &   9   &   $   5   \pm 3   $   &   -2  &   9   \\\hline
\rowcolor[gray]{.9}
{}  100 &   2   &   6   &   $   3   \pm 3   $   &   -2  &   8   &   $   5   \pm 4   $       &   -2   &   13  &   $   6   \pm 4   $   &   0   &   13  \\\hline
\rowcolor[gray]{.9}
{}  100 &   2   &   8   &   $   3   \pm 4   $   &   -5  &   10  &   $   7   \pm 4   $       &   -1   &   10  &   $   6   \pm 4   $   &   -2  &   15  \\\hline
\rowcolor[gray]{.9}
{}  100 &   2   &   10  &   $   3   \pm 5   $   &   -4  &   4   &   $   7   \pm 4   $       &    1   &   10  &   $   8   \pm 5   $   &   1   &   11  \\\hline
{}  100 &   3   &   4   &   $   1   \pm 5   $   &   -7  &   4   &   $   6   \pm 3   $       &    0   &   6   &   $   5   \pm 5   $   &   -4  &   8   \\\hline
{}  100 &   3   &   6   &   $   1   \pm 4   $   &   -5  &   5   &   $   5   \pm 3   $       &   -2   &   9   &   $   5   \pm 4   $   &   -3  &   10  \\\hline
{}  100 &   3   &   8   &   $   1   \pm 4   $   &   -6  &   4   &   $   4   \pm 3   $       &   -1   &   9   &   $   4   \pm 4   $   &   -3  &   9   \\\hline
{}  100 &   3   &   10  &   $   3   \pm 4   $   &   -4  &   7   &   $   8   \pm 3   $       &    1   &   15  &   $   6   \pm 4   $   &   1   &   9   \\\hline
\rowcolor[gray]{.9}
{}  100 &   4   &   4   &   $   -5  \pm 5   $   &   -10 &   1   &   $   2   \pm 4   $       &   -3   &   8   &   $   -1  \pm 5   $   &   -7  &   5   \\\hline
\rowcolor[gray]{.9}
{}  100 &   4   &   6   &   $   0   \pm 5   $   &   -7  &   7   &   $   4   \pm 4   $       &   -1   &   6   &   $   3   \pm 5   $   &   -3  &   6   \\\hline
\rowcolor[gray]{.9}
{}  100 &   4   &   8   &   $   0   \pm 3   $   &   -6  &   5   &   $   5   \pm 3   $       &    0   &   11  &   $   5   \pm 4   $   &   -1  &   9   \\\hline
\rowcolor[gray]{.9}
{}  100 &   4   &   10  &   $   2   \pm 5   $   &   -4  &   3   &   $   4   \pm 2   $       &    0   &   7   &   $   6   \pm 5   $   &   -2  &   10  \\\hline
\hline
{}  1000    &   2   &   4   &   $   7   \pm 4   $   &   0   &   12  &   $   -10 \pm 8   $   &  -21   &   6   &   $   11  \pm 4   $   &   3   &   16  \\\hline
{}  1000    &   2   &   6   &   $   8   \pm 4   $   &   -1  &   12  &   $   -8  \pm 9   $   &  -22   &   7   &   $   14  \pm 4   $   &   5   &   19  \\\hline
{}  1000    &   2   &   8   &   $   11  \pm 5   $   &   1   &   19  &   $   -10 \pm 11  $   &  -38   &   13  &   $   17  \pm 5   $   &   8   &   27  \\\hline
{}  1000    &   2   &   10  &   $   5   \pm 4   $   &   -2  &   11  &   $   -15 \pm 14  $   &  -29   &   8   &   $   11  \pm 5   $   &   3   &   20  \\\hline
\rowcolor[gray]{.9}
{}  1000    &   3   &   4   &   $   14  \pm 5   $   &   2   &   26  &   $   -3  \pm 6   $   &   -9   &   7   &   $   19  \pm 5   $   &   6   &   29  \\\hline
\rowcolor[gray]{.9}
{}  1000    &   3   &   6   &   $   19  \pm 6   $   &   6   &   30  &   $   0   \pm 5   $   &   -6   &   7   &   $   23  \pm 6   $   &   11  &   32  \\\hline
\rowcolor[gray]{.9}
{}  1000    &   3   &   8   &   $   18  \pm 5   $   &   7   &   27  &   $   3   \pm 6   $   &   -4   &   14  &   $   23  \pm 4   $   &   12  &   31  \\\hline
\rowcolor[gray]{.9}
{}  1000    &   3   &   10  &   $   12  \pm 5   $   &   1   &   18  &   $   0   \pm 7   $   &   -1   &   11  &   $   18  \pm 4   $   &   8   &   25  \\\hline
{}  1000    &   4   &   4   &   $   19  \pm 6   $   &   2   &   29  &   $   10  \pm 4   $   &    2   &   17  &   $   25  \pm 5   $   &   12  &   35  \\\hline
{}  1000    &   4   &   6   &   $   20  \pm 5   $   &   6   &   33  &   $   6   \pm 4   $   &   -1   &   11  &   $   25  \pm 5   $   &   18  &   35  \\\hline
{}  1000    &   4   &   8   &   $   18  \pm 6   $   &   1   &   28  &   $   9   \pm 4   $   &    3   &   12  &   $   23  \pm 5   $   &   9   &   29  \\\hline
{}  1000    &   4   &   10  &   $   22  \pm 6   $   &   1   &   37  &   $   8   \pm 4   $   &    1   &   12  &   $   28  \pm 5   $   &   13  &   42  \\\hline
\end{tabular}
}%end scriptsize
%\end{minipage}
%}
%\end{picture}
\caption{Exploration of AMA performance over parameter space for
$N=40$.}
\label{table:AMA_results_40}
\end{table}


%\begin{table}[pht]
%\centering
%%\begin{picture}(100,400)
%%\put(-10,240){
%%\begin{minipage}{5in}
%{%\small
%\begin{tabular}{|r|r|r||r|r|r||r|r|r||r|r|r|}\hline\hline
%\multicolumn{3}{|c||}{Configuration} & \multicolumn{3}{c||}{vs. NMA} &
%\multicolumn{3}{c||}{vs. GTT} & \multicolumn{3}{c|}{vs. SNN} \\\hline
%    $N_D$   &   $k$ &   $n$ &      \multicolumn{1}{c|}{$\delta\ (\%)$}             &   $Q_l$   &   $Q_u$   &       \multicolumn{1}{c|}{$\delta\ (\%)$}            &   $Q_l$   &   $Q_u$   & \multicolumn{1}{c|}{$\delta\ (\%)$} &   $Q_l$   &   $Q_u$   \\\hline
%\rowcolor[gray]{.9}
%{}  100 &   2   &   2   &   $   -4  \pm 2   $   &   -10 &   1   &   $   3   \pm 3   $   &   -6  &   10  &   $   -1  \pm 2   $   &   -6  &   4   \\\hline
%\rowcolor[gray]{.9}
%{}  100 &   2   &   4   &   $   0   \pm 3   $   &   -7  &   3   &   $   6   \pm 3   $   &   -1  &   12  &   $   3   \pm 3   $   &   -3  &   7   \\\hline
%\rowcolor[gray]{.9}
%{}  100 &   2   &   6   &   $   1   \pm 2   $   &   -2  &   4   &   $   8   \pm 3   $   &   -1  &   13  &   $   3   \pm 2   $   &   -1  &   8   \\\hline
%\rowcolor[gray]{.9}
%{}  100 &   2   &   8   &   $   4   \pm 3   $   &   -3  &   5   &   $   8   \pm 3   $   &   0   &   14  &   $   6   \pm 3   $   &   -2  &   7   \\\hline
%\rowcolor[gray]{.9}
%{}  100 &   2   &   10  &   $   0   \pm 2   $   &   -3  &   3   &   $   8   \pm 3   $   &   0   &   10  &   $   2   \pm 2   $   &   -1  &   7   \\\hline
%\rowcolor[gray]{.9}
%{}  100 &   2   &   12  &   $   3   \pm 2   $   &   -2  &   4   &   $   7   \pm 3   $   &   1   &   11  &   $   6   \pm 2   $   &   1   &   8   \\\hline
%{}  100 &   3   &   4   &   $   -6  \pm 4   $   &   -12 &   2   &   $   4   \pm 3   $   &   -3  &   9   &   $   -3  \pm 5   $   &   -7  &   6   \\\hline
%{}  100 &   3   &   6   &   $   1   \pm 4   $   &   -6  &   5   &   $   4   \pm 4   $   &   0   &   8   &   $   4   \pm 4   $   &   -5  &   8   \\\hline
%{}  100 &   3   &   8   &   $   2   \pm 4   $   &   -6  &   4   &   $   9   \pm 3   $   &   1   &   13  &   $   5   \pm 4   $   &   -3  &   8   \\\hline
%{}  100 &   3   &   10  &   $   0   \pm 4   $   &   -3  &   4   &   $   5   \pm 3   $   &   1   &   9   &   $   3   \pm 4   $   &   -2  &   8   \\\hline
%\hline
%\rowcolor[gray]{.9}
%{}  1000    &   2   &   2   &   $   6   \pm 4   $   &   -4  &   14  &   $   -16 \pm 7   $   &   -28 &   5   &   $   10  \pm 4   $   &   1   &   17  \\\hline
%\rowcolor[gray]{.9}
%{}  1000    &   2   &   4   &   $   7   \pm 3   $   &   -1  &   12  &   $   -11 \pm 8   $   &   -22 &   6   &   $   12  \pm 3   $   &   3   &   20  \\\hline
%\rowcolor[gray]{.9}
%{}  1000    &   2   &   6   &   $   8   \pm 3   $   &   0   &   15  &   $   -14 \pm 7   $   &   -34 &   7   &   $   13  \pm 3   $   &   5   &   20  \\\hline
%\rowcolor[gray]{.9}
%{}  1000    &   2   &   8   &   $   6   \pm 2   $   &   0   &   11  &   $   -7  \pm 6   $   &   -16 &   9   &   $   12  \pm 2   $   &   5   &   18  \\\hline
%\rowcolor[gray]{.9}
%{}  1000    &   2   &   10  &   $   12  \pm 3   $   &   2   &   19  &   $   -8  \pm 6   $   &   -18 &   9   &   $   17  \pm 3   $   &   7   &   24  \\\hline
%\rowcolor[gray]{.9}
%{}  1000    &   2   &   12  &   $   6   \pm 3   $   &   0   &   11  &   $   -5  \pm 7   $   &   -9  &   10  &   $   11  \pm 3   $   &   4   &   18  \\\hline
%{}  1000    &   3   &   4   &   $   14  \pm 5   $   &   1   &   24  &   $   2   \pm 5   $   &   -3  &   10  &   $   19  \pm 4   $   &   7   &   25  \\\hline
%{}  1000    &   3   &   6   &   $   14  \pm 6   $   &   1   &   22  &   $   3   \pm 6   $   &   0   &   11  &   $   20  \pm 5   $   &   9   &   27  \\\hline
%{}  1000    &   3   &   8   &   $   17  \pm 6   $   &   0   &   30  &   $   -2  \pm 6   $   &   -12 &   8   &   $   21  \pm 5   $   &   7   &   33  \\\hline
%{}  1000    &   3   &   10  &   $   11  \pm 4   $   &   1   &   22  &   $   -2  \pm 8   $   &   -7  &   12  &   $   17  \pm 4   $   &   8   &   26  \\\hline
%\end{tabular}
%}%end scriptsize
%%\end{minipage}
%%}
%%\end{picture}
%\caption{Exploration of AMA performance over parameter space for $N=50$.}
%\label{table:AMA_results_50}
%\end{table}



These results illustrate several points.  First is that AMA
performance is relatively insensitive to the value of $n$. This is
an encouraging result, because an approximation network with a
large maximum in-degree can result in slow inference when the
feature vector to be classified is not complete and $N$ is large.
Next we note the evident complementarity between the \naive
classifiers (both NMA and SNN) versus GTT. The \naive classifiers
perform consistently better at low $N_D$; whereas GTT does better
at high values of $N_D$. This effect may be due to the difficulty
of reliably extracting structural information from very small
databases; in which case GTT is not able to generalize well. A
final observation about these tables is that for high $N_D$, GTT
can achieve statistically significant and large gains compared to
AMA when $k$ is sufficiently small. This effect is more important
as $N$ increases because it becomes more difficult to average over
$\Lkn$ for a fixed $k$ as $N$ is increased. For example, in our
experiments it was too computationally costly for us to repeatedly
apply AMA enough to get statistically significant measurements for
($N=40$, $k=5$). A similar but weaker effect is seen for the
\naive classifiers. As $N$ gets large the benefits of AMA appear
to lose statistical significance at low $N_D$; however rarely did
the \naive classifiers outperform AMA in a statistically
significant sense.

Figure~\ref{fig:qualitative_k3} summarizes the results of
Tables~\ref{table:AMA_results_20}--\ref{table:AMA_results_40} by
showing the qualitative rankings of each algorithm as various
parameters are varied.  These rankings were derived by examining
the results in
Tables~\ref{table:AMA_results_20}--\ref{table:AMA_results_40} and
for each classifier $C_i\in\{$NMA, GTT, SNN $\}$, calculating
$\bar{\delta}_i$ which is the average over all values of $n$ for
the particular configuration being considered in
Figure~\ref{fig:qualitative_k3}. The following rules were applied
to determine the rankings:
\begin{enumerate}
\item
If AMA scored significantly better than $C_i$ for a majority of
runs, then AMA is ranked higher than $C_i$, and visa-versa.
\item
If $\bar{\delta}_i < \bar{\delta}_j$ then $C_i$ is ranked above
$C_j$.
\end{enumerate}
It is clear from this figure that the quality of AMA
classifications depends strongly on both $k$ and $N_D$.
\begin{figure}[pht]
\begin{picture}(130,130)
\put(-30,-130){%all 3 eps files:
\put(-20,0){%Just the eps file:
\scalebox{0.35}{
\includegraphics{images/qualitative_k2.eps}
}}
\put(140,0){%Just the eps file:
\scalebox{0.35}{
\includegraphics{images/qualitative_k3.eps}
}}
\put(300,0){%Just the eps file:
\scalebox{0.35}{
\includegraphics{images/qualitative_k4.eps}
}}}
\end{picture}
\caption{
\label{fig:qualitative_k3}
Qualitative comparison showing the ranking of the four algorithms
as the number of nodes, the number of records and $k$ are varied.}
\end{figure}
\noindent



While synthetic experiments are attractive because they allow us
to systematically vary parameters and generate enough samples to
achieve statistical significance, they do not necessary reflect
performance in the real world.  Also, our synthetic data
generation process assumed no hidden variables, a fact which might
bias our results. To this end we tested the four classifiers on 34
data sets taken from the UCI online database \citep{uci_database}.
These results are shown in Table~\ref{table:UCI}.
\begin{table}[pht]
\centering
%begin{picture}(100,400)
%\put(-10,160)
%{\begin{minipage}{5in}
\begin{tabular}{|l|c|c|c|c|r|r|r|c|}\hline\hline
Data set &  $\delta^{SNN}$ & $\delta^{GTT}$ & $\delta^{NMA}$ & $\delta^{AMA}$ & $N$ &  $k$ &  $N_D$ & method\\
\hline \rowcolor[gray]{.9}
{}haberman         &     0.35     &     0.35     & \ul{\bf0.00}    & \ul{\bf0.00}    &  4 &  4 &   306 & LOO\\ \hline
{}servo            &     0.56     &     0.66     & {\bf0.15} & \ul{\bf0.00}    &  5 &  5 &   167 & LOO\\ \hline
\rowcolor[gray]{.9}
{}lenses           &     0.37     &     0.45     & \ul{\bf0.00}    & {\bf0.03} &  6 &  6 &   24  & LOO\\ \hline
{}hayes-roth       &     0.32     &     0.32     & \ul{\bf0.00}    & {\bf0.01} &  6 &  6 &   132 & LOO\\ \hline
\rowcolor[gray]{.9}
{}liver-disorders  &     0.14     &     0.07     & \ul{\bf0.00}    & {\bf0.03} &  7 &  7 &   345 & LOO\\ \hline
{}monks-3          &     0.83     & {\bf0.24} &     0.82     & \ul{\bf0.00}    &  7 &  7 &   552 & T\&T\\ \hline
\rowcolor[gray]{.9}
{}monks-1          &     0.98     & \ul{\bf0.00}    &     0.98     & \ul{\bf0.00}    &  7 &  7 &   554 & T\&T\\ \hline
{}monks-2          &     0.48     &     0.48     & {\bf0.21} & \ul{\bf0.00}    &  7 &  7 &   600 & T\&T\\ \hline
\rowcolor[gray]{.9}
{}chess krkopt     &     0.54     & \ul{\bf0.00}    &     0.54     & {\bf0.32} &  7 &  7 & 28055 & CV2\\ \hline
{}ecoli            &     0.03     & {\bf0.01} &     0.02     & \ul{\bf0.00}    &  8 &  8 &   336 & LOO\\ \hline
\rowcolor[gray]{.9}
{}yeast            & \ul{\bf0.04} &     0.11     & \ul{\bf0.04} &     0.07     &  8 &  8 &  1484 & CV2\\ \hline
{}post-operative   & {\bf0.08} &     0.46     & \ul{\bf0.01} &     0.09     &  9 &  9 &    90 & LOO\\ \hline
\rowcolor[gray]{.9}
{}prima-indian diab& \ul{\bf0.01} & \ul{\bf0.01} & \ul{\bf0.01} &     0.02     &  9 &  9 &   768 & CV2\\ \hline
{}abalone          &     0.12     &     0.08     & {\bf0.05} & \ul{\bf0.00}    &  9 &  9 &  4176 & CV2\\ \hline
\rowcolor[gray]{.9}
{}cpu-performance  &     0.13     &     0.31     & \ul{\bf0.01} & {\bf0.11} & 10 & 10 &   209 & CV2\\ \hline
{}glass            & {\bf0.10} & \ul{\bf0.04} &     0.15     &     0.13     & 10 & 10 &   214 & CV2\\ \hline
\rowcolor[gray]{.9}
{}cmc              & \ul{\bf0.01} &     0.07     & \ul{\bf0.01} &     0.04     & 10 & 10 &  1473 & CV2\\ \hline
{}sol-flare-C      &     0.03     &     0.09     & {\bf0.02} & \ul{\bf0.01} & 11 & 11 &   322 & CV2\\ \hline
\rowcolor[gray]{.9}
{}sol-flare-M      & \ul{\bf0.00}    &     0.44     & {\bf0.17} &     0.20     & 11 & 11 &   322 & CV2\\ \hline
{}sol-flare-X      & {\bf0.06} & \ul{\bf0.01} &     0.18     &     0.33     & 11 & 11 &   322 & CV2\\ \hline
\rowcolor[gray]{.9}
{}page-blocks      &     0.30     & {\bf0.12} &     0.23     & \ul{\bf0.02} & 11 & 11 &  5473 & CV2\\ \hline
{}wine             &     0.14     & \ul{\bf0.01} &     0.16     & {\bf0.06} & 14 &  7 &   177 & CV2\\ \hline
\rowcolor[gray]{.9}
{}heart-disease    & \ul{\bf0.00}    & {\bf0.07} &     0.11     &     0.19     & 14 &  6 &   294 & CV2\\ \hline
{}housing          &     0.20     & {\bf0.06} &     0.22     & \ul{\bf0.00}    & 14 &  5 &   506 & CV2\\ \hline
\rowcolor[gray]{.9}
{}credit-screening & \ul{\bf0.00}    &     0.12     &     0.09     & {\bf0.02} & 16 &  5 &   652 & CV2\\ \hline
{}pendigits        &     0.58     & \ul{\bf0.00}    &     0.58     & \ul{\bf0.00}    & 17 &  6 &  7495 & T\&T \\ \hline
\rowcolor[gray]{.9}
{}letter-recognit  &     0.38     & \ul{\bf0.00}    &     0.38     & {\bf0.01} & 17 &  5 & 20000 & T\&T \\ \hline
{}thyroid-disease  &     0.17     &     0.28     & \ul{\bf0.00}    & {\bf0.11} & 21 &  5 &  7200 & T\&T \\ \hline
\rowcolor[gray]{.9}
{}soybean-small    & \ul{\bf0.00}    & \ul{\bf0.00}    & \ul{\bf0.00}    & \ul{\bf0.00}    & 22 &  4 &    47 & CV4\\ \hline
{}mushroom         &     0.86     & \ul{\bf0.00}    &     0.89     & {\bf0.03} & 22 &  4 &  8124 & CV2\\ \hline
\rowcolor[gray]{.9}
{}spect            &     0.18     &     0.38     & {\bf0.16} & \ul{\bf0.00}    & 23 &  4 &   267 & T\&T \\ \hline
{}brst-canc-wisc   &     0.28     & \ul{\bf0.00}    &     0.29     & {\bf0.23} & 32 &  3 &   569 & CV2\\ \hline
\rowcolor[gray]{.9}
{}connect-4  & {\bf0.49} & \ul{\bf0.00}    & {\bf0.49} &     0.52     & 43 &  2 & 67557 & CV2\\ \hline
{}spambase   &     0.24     &     0.25     & \ul{\bf0.00}    & {\bf0.10} & 58 &  2 &  4600 & CV2 \\ \hline\hline
\end{tabular}
%\end{minipage}}
%\end{picture}
\caption{ Experimental results for 34 UCI data sets. The top
scoring classifier for each data set is underlined, the top two
are shown in bold. AMA scored in the top one 13 of 34 times
compared to 7, 12 and 12 for SNN, GTT and NMA, respectively. It
scored in the top two 25 times compared to 11, 17, and 19 for NMA,
GTT and SNN, respectively.  } \label{table:UCI}
\end{table}
%\hspace{-.23in}

%\scriptsize
Here the score $\delta^i_d$ for classifier $C_i$ was calculated
according to Procedure~\ref{proc:testing}, where $M_2=C_i$ and
$M_1$ was taken to be the maximum scoring classifier for the data
set $d$. For example, in the monks-2 database, AMA was the highest
scoring classifier and covered $48\%$ of the remaining area for
SNN and GTT and $21\%$ of the remaining area for NMA. The ROC area
will in general depend on which state of the classification
variable is considered to be the ``positive" state. The scores in
Table~\ref{table:UCI} are average scores for all ROC curves
associated with a particular classification variable; therefore
some data sets (e.g., wine) have no zero entries when two or more
classifiers score highest on different curves.

The average difference $\Delta^i$ between classifier $i$ and AMA:
$\Delta^i\equiv{1\over 34}\sum_{d}(\delta^{AMA}_d - \delta^i_d)$,
was calculated to gauge the statistical significance of these
experiments. The results are shown in
Table~\ref{table:uci_compiled}. AMA benefits over the \naive
models were significant at the 99\% level, but only at the 95\%
level for GTT.
\begin{table}[htb]
\centering
\begin{tabular}{|c||r|r|r|}\hline\hline
$i$ & $\Delta^i$ (\%) & $Q_l$ & $Q_u$ \\\hline
{} SNN & $19\pm 5$ & 0 & 33 \\\hline
{} NMA & $13\pm 5$ & 0 & 23 \\\hline
{} GTT & $8\pm 4$  & 0 & 20\\\hline
\hline
\end{tabular}
\caption{Compiled UCI results. The error ranges denote the error
of the mean.}
\label{table:uci_compiled}
\end{table}

Finally, the performance of AMA was also tested by generating
training and test data with the benchmark ALARM network. In this
case, $N=36$ and $K=4$ were fixed by the network, and a test was
performed with $k=3$, $n=10$, and $N_D$ systematically varied. The
results in Table~\ref{table:alarm_results} are shown for
classification on the {\em kinked tube (kt)} and {\em anaphylaxis
(an)} diagnostic nodes.
\begin{table}[htb]
\centering
%\begin{picture}(100,60)
%\put(30,40){
%\begin{minipage}{3in}
{%\scriptsize
\begin{tabular}{|r||r|r|r||r|r|r|}\hline\hline
$N_D$ & $\delta^{\longvar{kt}}$ (\%) & $Q_l^{\longvar{kt}}$ &
$Q_u^{\longvar{kt}}$ & $\delta^{\longvar{an}}$ (\%) &
$Q_l^{\longvar{an}}$ & $Q_u^{\longvar{an}}$
\\\hline
{}50   & $32  \pm 13$  & 24   & 55 & $3  \pm 3$ & -9   & 17\\\hline
{}100  & $23  \pm 11$  & 9  & 53 & $1  \pm 3$ & -11  & 16\\\hline
{}200  & $13  \pm 9$   & -1   & 32 & $-3 \pm 4$ & -17  & 16\\\hline
{}400  & $12  \pm 7$   & -1   & 34 & $-3 \pm 5$ & -21  & 18\\\hline
{}800  & $4   \pm 7$   & -9   & 23 & $2  \pm 5$ & -11  & 21\\\hline
{}3200 & $0   \pm 14$  & -19  & 15 & $6  \pm 7$ & -8   & 19\\\hline\hline
\end{tabular}
}%end scriptsize
%\end{minipage}
%}
%\end{picture}
\caption{AMA performance v.s. GTT on synthetic data generated
using the ALARM network and classifying on {\em kinked tube} (kt)
and {\em anaphylaxis} (an).}
\label{table:alarm_results}
\end{table}
Here, for small number of records, AMA outperformed GTT at the
$99\%$ significance level classifying on the {\em kinked tube}
node; however, it showed no improvement when classifying on the
{\em anaphylaxis} node. These results are notable because they
demonstrate that the qualitative performance of the AMA classifier
depends not just on global network features but also on features
specific to the classification node. Precisely what features of
the classification node are important is an open question for
future research. The prior probability of {\em anaphylaxis} was
about 4 times smaller than that of {\em kinked tube}; however, the
local topology of the network may play a factor as well.

Obviously, using AMA was not without cost.  The time to construct
the models (and memory requirements) appeared to grow
exponentially with $k$, as shown in Table~\ref{table:time} for
$N=40$.
\begin{table}[pht]
\center
\begin{tabular}{|c|c|r|r|}\hline\hline
{}$N_D$   & Algorithm & train time &    test time   \\\hline
{}        & AMA-4 & 330  & 0.101   \\ \cline{2-4}
{}        & AMA-3 &  27  & 0.038   \\ \cline{2-4}
{}$100$   & AMA-2 & 2.6  & 0.033   \\ \cline{2-4}
{}        & GTT   & 0.3  & 0.025   \\ \cline{2-4}
{}        & NMA   & 0.2  & 0.021   \\ \cline{2-4}
{}        & SNN   & 0.02 & 0.017   \\\hline\hline
{}        & AMA-4 & 1000 & 0.113   \\ \cline{2-4}
{}        & AMA-3 & 96   & 0.035   \\ \cline{2-4}
{}$1000$  & AMA-2 & 8.9  & 0.033   \\ \cline{2-4}
{}        & GTT   & 1.2  & 0.024   \\ \cline{2-4}
{}        & NMA   & 0.2  & 0.022   \\ \cline{2-4}
{}        & SNN   & 0.04 & 0.017   \\ \hline
\hline
\end{tabular}
\caption{Average training and testing times in seconds for the
different algorithms with $N=40$. ``AMA-$m$" refers to the average
over all runs with $k=m$.}
\label{table:time}
\end{table}
%These results, in light of the fact that for large $N$ AMA can
%often be equalled or bettered by GTT or NMA, depending on $N_D$


\section{Discussion}
\label{sec:conclusions} We have shown that, under certain
assumptions, it is possible to construct a single Bayesian network
model, $M$, whose joint distribution will be identical to exact
model averaging over the class, $\Lk$, of models consistent with a
partial ordering $\pi$ and having in-degree bounded by $k$.
Although for most partial orderings, $M$ will be intractable to
build and use for inference, we have demonstrated two ways of
putting this technique to practical use: first, by constructing a
single network with a particular parameterization that produces
approximate model averaged predictions, and second by applying the
method to the class of \naive Bayes models, leading to a simple
re-parameterization that produces predictions equivalent to model
averaging over all feature sets, effectively solving the feature
selection problem for \naive models in a Bayesian framework.

As an example of the utility of this method, we performed some
empirical studies in a classification context, and showed that on
both synthetic and UCI datasets, even with relatively little
effort in choosing a good value for $\pi$ and with simple
noninformative priors, classifications can be beneficial compared
to other common BN classifiers. We have also demonstrated
empirically that classifications obtained by model averaging over
all \naive features sets is very likely to be beneficial over a
single \naive model chosen by selecting the MAP feature set. It
can be expected that these results would improve in real-world
situations when expert knowledge about realistic node-orderings
and structure and parameter priors can be brought to bear.

Our empirical results provide evidence that Bayesian model
averaging can improve prediction over model selection, in contrast
to the conclusions drawn by \citet*{domingos.icml00} that Bayesian
learning exacerbates the over-fitting problem. First, in our
experiments with \naive classifiers, model averaging clearly
produced better predictions compared to model selection in terms
of the ROC area. Second, in our experiments with approximate
model-averaged (AMA) classifiers, we observed the trend that AMA
classifications performed successively better as more and more
structures were included in the model averaging (i.e., as $k$ was
increased). This conflicts with the assertion that model
generalization suffers when more models are considered in the
averaging process.

In general, the benefits of AMA were not without cost.
Construction times for AMA models were higher than other model
types, and were observed empirically to grow exponentially as the
maximum in-degree $k$ increased. Furthermore, when the
approximation parameter $n$ is large, inference with incomplete
feature vectors can become prohibitive. The latter observation is
mitigated by the fact that the AMA classifier is generally
insensitive to the value of $n$, allowing $n$ to be minimized
without sacrificing classification accuracy. However, in cases
where the number of nodes, $N$, is very large, the cost of
building the AMA classifier might outweigh the benefits: in this
case, if the number of records, $N_D$, is small then a \naive
model-averaged (NMA) classifier would probably be the most
attractive since it performed comparably to AMA with orders of
magnitude faster training time.

Once the model-averaging model is built, however, the technique
has an advantage because of its simplicity of implementation.
Existing systems that use Bayesian network classifiers can
trivially be adapted to use model averaging by replacing their
existing model with a single summary model. This is especially
relevant in cases where a \naive classifier is currently being
employed, as building a NMA classifier retains the same linear
time and space complexity required for building a \naive model.

As already stated, when $n$ is large enough the approximation
network can be extremely dense, thus making inference difficult
when the feature-vector is incomplete.  One way to get around this
issue, when the incompleteness of the feature-vector is regular,
is to learn separate model-averaging models on subsets of data in
which the same set of features is missing. Thus a one-time
investment of building several feature-vector-specific models
would allow us to do $\Ofun{N}$ inference even for large
$n$-values.

Future work includes finding a better method for optimizing the
ordering $\pi$, possibly by doing a search over orderings as in
\citep*{Friedman_ML2003}, and perhaps using cached sufficient
statistics with advanced data structures such as ADTrees
\citep*{moore-cached} to increase the practical limits of $k$.
There are a wealth of other classifiers that it would be
interesting to compare with our approach: both non-probabilistic
based models such as C4.5, neural networks, support-vector
machines, etc., and other model-averaging techniques such as those
presented in \citet{madigan94} and \citet{cerquides.phd}


It should also be possible to relax the assumption of complete
training data by using the EM algorithm or MCMC sampling to
estimate parameters from data. Finally, the identification of
other classes of BN models that easily fit within the $\Lk$ class
could lead to other especially efficient solutions such as that
obtained with the \naive Bayes model.



%\section{Acknowledgements}
%{%\footnotesize
%This work was
%supported in part by grant number S99-GSRP-085 from the National
%Aeronautics and Space Administration under the Graduate Students
%Research Program, by grant IIS-9812021 from the National Science
%Foundation and by grants LM06696 from the National Library of
%Medicine.
%}

\acks{We would like to acknowledge the reviewers for their very thorough
comments of this paper. This research was supported in part by
grant RO1-GM61992-01A1 from the National Institutes of Health and
by grant IIS-0325581 from the National Science Foundation. }
{
%\footnotesize
\bibliographystyle{named}
%\bibliographystyle{mlapa}
\bibliography{main,books,marek,learning,qr,uai88,uai90,uai91,uai92,uai93,uai94,uai95,uai96,se,uai98,uai99,uai2000,denver,causality,abduction}
}
\end{document}
