
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                   %                                                     %
%  #####   # #      % File:     adtree.tex                                %
%    #     # #      % Authors:  Andrew Moore + Mary Soon Lee              %
%    # ###  #       % Created:  July 1997                                 %
%    # #   # #      % Updated:  3 Oct 97: Bayes net order-independent     %
%    # ### # #      %                     search results                  %
%      #            %           16-18 Nov 97: JAIR revisions              %
%      ###          % Copyright, Andrew Moore and Mary Soon Lee, 1997     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentstyle[jair,twoside,11pt,theapa,psfig]{article}

% For some psfig examples see ~/tex/bib/include.tex
%\renewcommand{\baselinestretch}{1.875}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                   Title                  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%Volume 8
%Year 1998
%Publication date 3/98
%Start page 67
 
\jairheading{8}{1998}{67-91}{7/97}{3/98}
\ShortHeadings{Cached Sufficient Statistics for Efficient Machine Learning}
{Moore \& Lee}
\firstpageno{1}
\firstpageno{67}

\begin{document} 

\title{Cached Sufficient Statistics for Efficient Machine Learning with 
Large Datasets}
 
\author{\name Andrew Moore   \email awm@cs.cmu.edu \\
        \name Mary Soon Lee  \email mslee@cs.cmu.edu \\
        \addr School of Computer Science and Robotics Institute \\
        \addr Carnegie Mellon University, Pittsburgh PA 15213}
 
\maketitle 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                Definitions               %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\amfcap}[2]{{\refstepcounter{figure} 
\label{#1}
\noindent
Figure~\arabic{figure}:
#2}}

\newcommand{\amtcap}[2]{{\refstepcounter{table} 
\label{#1}
\noindent
Table~\arabic{table}:
#2}}

\newcommand{\ourfig}[4]{\begin{figure}[ht]
\begin{center}
{\centerline{\psfig{file=../ps/#1.ps,width=#2,height=#3}}}

\vspace{2mm}

\begin{minipage}{0.8\textwidth}
\amfcap{#1}{#4}
\end{minipage}
\end{center}
\end{figure}}

\newcommand{\ourunsquishedfig}[3]{\begin{figure}[ht]
\begin{center}
{\centerline{\psfig{file=../ps/#1.ps,height=#2}}}

\vspace{2mm}

\begin{minipage}{0.8\textwidth}
\amfcap{#1}{#3}
\end{minipage}
\end{center}
\end{figure}}

\newcommand{\ttfig}[3]{
\begin{figure}
\begin{center}
\fbox{\footnotesize \tt \begin{minipage}{0.92\textwidth}
#3
\end{minipage}}

\vspace{2mm}

\begin{minipage}{0.8\textwidth}
\amfcap{#1}{#2}
\end{minipage}
\end{center}
\end{figure}}

\newcommand{\ourtab}[3]{\begin{table}
\begin{center}
{\footnotesize #3}

\vspace{2mm}

\begin{minipage}{0.8\textwidth}
\amtcap{#1}{#2}
\end{minipage}
\end{center}
\end{table}}

\newcommand{\myhead}[1]{\ \\
\noindent
{\bf #1}\\}
\newcommand{\boldthing}[1]{\mbox{\bf #1}}
\newcommand{\myindex}[1]{\mbox{\scriptsize #1}}
\newcommand{\bbeta}{\mbox{$\boldmath \beta$}}
\newcommand{\kdtree}{{\it k}d-tree}
\newcommand{\rtree}{{\it R}-tree}
\newcommand{\adtree}{{\it AD}tree}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\product}{\large \Pi}
\newcommand{\numatts}{M}
\newcommand{\arity}[1]{n_{#1}}
\newcommand{\countfun}{C}
\newcommand{\attnum}[1]{a_{#1}}
\newcommand{\atti}{\attnum{i}}
\newcommand{\attj}{\attnum{j}}
\newcommand{\attone}{\attnum{1}}
\newcommand{\atttwo}{\attnum{2}}
\newcommand{\attM}{\attnum{M}}
\newcommand{\isubx}[1]{i(#1)}
\newcommand{\attxequaly}[2]{\attnum{#1} = #2}
\newcommand{\attxequalisubx}[1]{\attxequaly{#1}{i(#1)}}
\newcommand{\mystar}{\mbox{\tt *}}
\newcommand{\attxequalstar}[1]{\attnum{#1} = \mystar}
\newcommand{\vary}{Vary}
\newcommand{\varyattx}[1]{\mbox{\mbox{Vary} \hspace{-1mm} $\attnum{#1}$}}
\newcommand{\varyattj}{\varyattx{j}}
\newcommand{\attjequalx}[1]{\attxequaly{j}{#1}}
\newcommand{\attjequalzero}{\attjequalx{0}}
\newcommand{\attjequalone}{\attjequalx{1}}
\newcommand{\attjequalstar}{\attxequalstar{j}}
\newcommand{\attnums}{S_{\myindex{attributes}}}
\newcommand{\adnode}{{\it AD}node}
\newcommand{\varname}[1]{\mbox{\it #1}}
\newcommand{\adn}{\varname{ADN}}
\newcommand{\adnk}{{\adn}_k}
\newcommand{\mcv}{\varname{MCV}}
\newcommand{\ct}{\varname{CT}}
\newcommand{\ctsum}{\varname{CTSUM}}
\newcommand{\contab}{Contab}
\newcommand{\structref}[2]{{#1}.{#2}}
\newcommand{\ctsub}[1]{{\ct}_{#1}}
\newcommand{\ctsubmcv}{{\ct}_{\myindex{MCV}}}
\newcommand{\nullnode}{\varname{NULL}}
\newcommand{\computecontab}{\mbox{\bf MakeContab}}
\newcommand{\assign}{\mbox{\tt \ := }}
\newcommand{\attisubx}[1]{\attnum{\isubx{#1}}}
\newcommand{\attisubxequaly}[2]{\attxequaly{\isubx{#1}}{#2}}
\newcommand{\rmin}{R_{\myindex{min}}}
\newcommand{\aout}{\attnum{out}}
\newcommand{\attset}{\attisubx{1} \ldots \attisubx{n}}
\newcommand{\ass}{\varname{Assign}}
\newcommand{\assk}{{\ass}_k}
\newcommand{\infogain}{\varname{InfoGain}}
\newcommand{\plogp}{f}
\newcommand{\cont}{\mbox{\bf ct}}
\newcommand{\parent}{\varname{Parent}}
\newcommand{\parentjassignments}{X_j}
\newcommand{\parentsj}{\mbox{\it Parents(j)}}
\newcommand{\numparams}{N_{\myindex{params}}}
\newcommand{\vout}{v_{\myindex{out}}}
\newcommand{\conjquery}{\attisubxequaly{1}{v_1} \ldots \attisubxequaly{n}{v_n}}
\newcommand{\smin}{S_{\myindex{min}}}
\newcommand{\attributeequalvalue}{(\mbox{\it attribute}=\mbox{\it value})}
\newcommand{\prodaritiesplusone}{{\product}_{i = 1}^{M} (\arity{i} + 1)}
\newcommand{\query}{\varname{Query}}
\newcommand{\jsubx}[1]{j(#1)}
\newcommand{\attjsubx}[1]{\attnum{\jsubx{#1}}}
\newcommand{\queryj}{\attjsubx{1} = u_1 , \ldots \attjsubx{p} = u_p}
\newcommand{\attsetfromtwo}{{\attisubx{2} \ldots \attisubx{n}}}
\newcommand{\vn}{\varname{VN}}
\newcommand{\arityisubx}[1]{\arity{\isubx{#1}}}
\newcommand{\arityisubone}{\arityisubx{1}}
\newcommand{\oneindent}{\ \hspace{1cm}}
\newcommand{\twoindent}{\ \hspace{2cm}}
\newcommand{\threeindent}{\ \hspace{3cm}}
\newcommand{\fourindent}{\ \hspace{4cm}}
\newcommand{\vsub}[1]{v_{#1}}
\newcommand{\uplogrmone}{\lfloor \log_2 R \rfloor}
\newcommand{\uplogr}{\uplogrmone + 1}
\newcommand{\uplogrmtwo}{\uplogrmone - 1}
\newcommand{\uplogminprmone}{\lfloor (\log_2 R)/(-\log_2 q) \rfloor}
\newcommand{\uplogminpr}{\uplogminprmone + 1}
\newcommand{\uplogminprmtwo}{\uplogminprmone - 1}
\newcommand{\minp}{\min(p,1-p)}
\newcommand{\asssmall}{{\mbox{\footnotesize \it Asgn}}}
\newcommand{\boundedby}{\mbox{ \footnotesize bounded above by }}
\newcommand{\mybigchoose}[2]{\left(\begin{array}{c}
#1 \\
#2
\end{array}
\right)}

\newcommand{\mysmallchoose}[2]{\mbox{\footnotesize $(\begin{array}{c}
#1 \\
#2
\end{array})$}}

%%%%%%%%%%%%%% END DEFINITIONS %%%%%%%%%%%%%%%%%%%

 
\begin{abstract} 
\noindent
This paper introduces new algorithms and data structures
for quick counting for machine learning datasets.
We focus on the counting task of constructing contingency
tables, but our approach is also applicable to counting the number of
records in a dataset that match conjunctive queries.
Subject to certain assumptions,
the costs of these operations can be shown to be independent of the
number of records in the dataset and loglinear in the number of
non-zero entries in the contingency table. 

We provide a very sparse data structure, the {\adtree}, to minimize
memory use. We provide analytical worst-case bounds for this structure
for several models of data distribution.
We empirically demonstrate that tractably-sized
data structures can be produced for large real-world datasets by (a)~using
a sparse tree structure that never allocates memory for counts of
zero, (b)~never allocating memory for counts that can be deduced from
other counts, and (c)~not bothering to expand the tree fully near its
leaves.

We show how the {\adtree} can be used to accelerate Bayes net structure
finding algorithms, rule learning algorithms, and feature selection
algorithms, and we provide a number of empirical results comparing
{\adtree} methods against traditional direct counting approaches.
We also discuss the possible uses of {\adtree}s in other machine learning
methods, and discuss the merits of {\adtree}s in comparison
with alternative representations such as {\kdtree}s, {\rtree}s 
and Frequent Sets.
\end{abstract} 
 
\section{Caching Sufficient Statistics}

Computational efficiency is an important concern for machine learning
algorithms, especially when applied to large
datasets~\cite{fyyd:data,fyyd:mini} or in real-time scenarios. In
earlier work we showed how {\kdtree}s with multiresolution cached
regression matrix statistics can enable very fast locally weighted and
instance based regression~\cite{mr:lwpr}. In this paper, we attempt to
accelerate predictions for symbolic attributes using a kind of
{\kdtree} that splits on all dimensions at all nodes.

Many machine learning algorithms operating on datasets of symbolic
attributes need to do frequent {\em counting}.  This work is also
applicable to Online Analytical Processing (OLAP) applications in data
mining, where operations on large datasets such as multidimensional
database access, DataCube operations~\cite{hrnr:impl}, and association
rule learning~\cite{agrw:assc} could be accelerated by fast counting.

Let us begin by establishing some notation.  We are given a data set
with $R$ records and $M$ attributes. The attributes are called
$\attnum{1},\attnum{2},\ldots \attnum{M}$. The value of attribute
$\atti$ in the $k$th record is a small integer lying in the range
$\{1,2, \ldots \arity{i}\}$ where $\arity{i}$ is called the {\em
arity} of attribute $i$. Figure~\ref{dataset} gives an example.

\ourfig{dataset}{3in}{1.8in}{A simple
dataset used as an example. It has $R = 6$
records and $M = 3$ attributes.}

\subsection{Queries}
A {\em query} is a set of $\attributeequalvalue$ pairs in which the
left hand sides of the pairs form a subset of $\{\attnum{1} \ldots
\attnum{M} \}$ arranged in increasing order of index. Four examples of
queries for our dataset are
\begin{equation}
(\attnum{1}=1) ; (\attnum{2}=3,\attnum{3}=1) ; () ; (\attnum{1}=2,\attnum{2}=4,\attnum{3}=2)
\end{equation}
Notice that the total number of possible queries is
$\prodaritiesplusone$.  This is because each attribute can either
appear in the query with one of the $\arity{i}$ values it may take, or
it may be omitted (which is equivalent to giving it a
$\attxequalstar{i}$ ``don't care'' value).

\subsection{Counts}
The {\em count} of a query, denoted by $\countfun(\query)$ is
simply the number of records in the dataset matching all the
$\attributeequalvalue$ pairs in $\query$. For our example dataset we find:
\begin{eqnarray*}
\countfun(\attnum{1}=1) & = & 3\\
\countfun(\attnum{2}=3,\attnum{3}=1) & = & 4\\
\countfun() & = & 6\\
\countfun(\attnum{1}=2,\attnum{2}=4,\attnum{3}=2) & = & 1
\end{eqnarray*}

\subsection{Contingency Tables}
Each subset of attributes, $\attset$, has an associated {\em
contingency table} denoted by $\cont(\attset)$. This is a table with a
row for each of the possible sets of values for $\attset$. The row
corresponding to $\conjquery$ records the count
$\countfun(\conjquery)$.  Our example dataset has 3 attributes and so
$2^3 = 8$ contingency tables exist, depicted in
Figure~\ref{contingencies}.

\ourunsquishedfig{contingencies}{2in}{The
eight possible contingency tables
for the dataset of Figure~\ref{dataset}.}

A {\em conditional contingency table}, written
\begin{equation}
\cont(\attset \mid \queryj)
\end{equation}
is the contingency table for the subset of records in the dataset that
match the query to the right of the $\mid$ symbol. For example,
\begin{center}
{\footnotesize
$\cont(\attnum{1},\attnum{3} \mid \attnum{2} = 3) = $
\begin{tabular}{|l|l|l|}
\hline
$\attnum{1}$ & $\attnum{3}$ & \# \\ \hline \hline
1         & 1         & 2  \\ \hline
1         & 2         & 0  \\ \hline
2         & 1         & 2  \\ \hline
2         & 2         & 0  \\ \hline
\end{tabular}}
\end{center}

Contingency tables are used in a variety of machine learning
applications, including building the probability tables for Bayes nets
and evaluating candidate conjunctive rules in rule learning
algorithms~\cite{qnln:lrnn2,clrk:cn2}.  It would thus be desirable to
be able to perform such counting efficiently.

If we are prepared to pay a one-time cost for building a caching data
structure, then it is easy to suggest a mechanism for doing counting
in constant time. For each possible query, we precompute the
contingency table. The total amount of numbers stored in memory for
such a data structure would be $\prodaritiesplusone$, which even for
our humble dataset of Figure~\ref{dataset} is 45, as revealed by
Figure~\ref{contingencies}. For a real dataset with more than ten
attributes of medium arity, or fifteen binary attributes, this is far
too large to fit in main memory. 

We would like to retain the speed of precomputed contingency tables without
incurring an intractable memory demand. That is the subject of this paper.

\section{Cache Reduction 1: The Dense {\adtree} for Caching 
Sufficient Statistics}
\label{dense}
First we will describe the {\adtree}, the data
structure we will use to represent the set of all possible counts. Our
initial simplified description is an obvious tree representation that
does not yield any immediate memory savings,\footnote{The
SE-tree~\cite{rymn:anst} is a similar data structure.} but will later provide
several opportunities for cutting off zero counts and redundant
counts.  This structure is shown in Figure~\ref{multi}.  An {\adtree} node
(shown as a rectangle) has child nodes called ``Vary nodes'' (shown as
ovals). Each {\adnode} represents a query and stores the number of
records that match the query (in the $C = \mbox{\#}$ field).  The
{\varyattj} child of an {\adnode} has one child for each of the
$\arity{j}$ values of attribute $\attj$.  The $k$th such child
represents the same query as {\varyattj}'s parent, with the additional
constraint that $\attj = k$.

\ourfig{multi}{4in}{2.5in}{The top {\adnode}s of an {\adtree}, described in the text.}

Notes regarding this structure:

\begin{itemize}
\item
Although drawn on the diagram, the description of the query
(e.g., $\attxequaly{1}{1} , \attxequalstar{2} , .. \attxequalstar{M}$
on the leftmost {\adnode} of the
second level) is not explicitly recorded in the {\adnode}. The contents
of an {\adnode} are simply a count and a set of pointers to the $\varyattj$
children.

The contents of a {\varyattj} node are a set of pointers to {\adnode}s.

\item
The cost of looking up a count is proportional to
the number of instantiated variables in the query. For example,
to look up 
$\countfun(
\attxequaly{7}{2},
\attxequaly{13}{1},
\attxequaly{22}{3})$
we would follow
the following path in the tree: 
$\varyattx{7} \rightarrow
\attxequaly{7}{2} \rightarrow
\varyattx{13} \rightarrow
\attxequaly{13}{1} \rightarrow
\varyattx{22} \rightarrow
\attxequaly{22}{3}$.
Then the count is obtained from the resulting node.

\item
Notice that if a node {\adn} has {\varyattx{i}} as its parent,
then {\adn}'s children are
\begin{quote}
{\varyattx{i+1}} {\varyattx{i+2}} ... {\varyattx{M}}.
\end{quote}
It is not necessary to store
Vary nodes with indices below $i+1$ because that information can be obtained
from another path in the tree.
\end{itemize}

\subsection{Cutting off nodes with counts of zero}
As described, the tree is not sparse and will contain exactly
$\prodaritiesplusone$
nodes. Sparseness is easily achieved by storing a {\nullnode} instead of
a node for any query that matches zero records. All of the specializations
of such a query will also have a count of zero and they will not
appear anywhere in the tree.
For some datasets
this can reduce the number of numbers that need to be stored.
For example, the dataset in Figure~\ref{dataset}, which previously
needed 45 numbers to represent all contingency tables, will now
only need 22 numbers.

\section{Cache Reduction II: The Sparse {\adtree}}
\label{adtree}

It is easy to devise datasets for which there is no benefit in failing
to store counts of zero. Suppose we have M binary attributes and $2^M$
records in which the $k$th record is the bits of the binary
representation of $k$. Then no query has a count of zero and the tree 
contains $3^M$ nodes.
To reduce the tree size despite this, we will take advantage
of the observation that very many of the counts stored in the above
tree are redundant.

Each {\varyattj} node in the above {\adtree} stores $\arity{j}$
subtrees---one subtree for each value of $\attj$. Instead, we will
find the most common of the values of $\attj$ (call it {\mcv}) and
store a {\nullnode} in place of the {\mcv}th subtree. The remaining
$\arity{j} - 1$ subtrees will be represented as before. An example for
a simple dataset is given in Figure~\ref{mcv}.  Each {\varyattj} node
now records which of its values is most common in a {\mcv}
field. Appendix~B describes the straightforward algorithm for building
such an {\adtree}.

\ourunsquishedfig{mcv}{3in}{A sparse {\adtree} built for the dataset shown
in the bottom right. The most common value for $\attone$ is 3, and so the
$\attone = 3$ subtree of the $\varyattx{1}$ child of the root node is
NULL. At each of the $\varyattx{2}$ nodes the most common child is also
set to NULL (which child is most common depends on the context).}

As we will see in Section~\ref{contingency}, it is still possible to
build full exact contingency tables (or give counts for specific
queries) in time that is only slightly longer than for the full
{\adtree} of Section~\ref{dense}.  But first let us examine the
memory consequences of this representation.

Appendix~A shows that for binary attributes, given
$M$ attributes and $R$ records, the number of nodes needed to store
the tree is bounded above by $2^M$ in the worst case (and much less if
$R < 2^M$).  In contrast, the amount of memory needed by the dense
tree of Section~\ref{dense} is $3^M$ in the worst case.

Notice in Figure~\ref{mcv} that the {\mcv} value is context
dependent. Depending on constraints on parent nodes, $\atttwo$'s {\mcv}
is sometimes 1 and sometimes 2. This context dependency can provide
dramatic savings if (as is frequently the case) there are correlations
among the attributes. This is discussed further in Appendix~A.

\section{Computing Contingency Tables from the Sparse {\adtree}}
\label{contingency}
Given an {\adtree}, we wish to be able to quickly construct contingency
tables for any arbitrary set of attributes $\{\attset\}$.

Notice that a conditional contingency table
$\cont(\attset \mid \query)$ can be built recursively. We first build
\begin{eqnarray*}
& \cont(\attsetfromtwo \mid \attisubx{1} = 1 , \query) & \\
& \cont(\attsetfromtwo \mid \attisubx{1} = 2 , \query) & \\
& \vdots & \\
& \cont(\attsetfromtwo \mid \attisubx{1} = \arity{\isubx{1}} , \query) &
\end{eqnarray*}
For example, to build $\cont(\attnum{1},\attnum{3})$ using the dataset in
Figure~\ref{dataset}, we can build $\cont(\attnum{3}\mid\attnum{1}=1)$ and
$\cont(\attnum{3}\mid\attnum{1}=2)$ and combine them as in
Figure~\ref{concat}.

\ourunsquishedfig{concat}{1.5in}{An example 
(using numbers from Figure~\ref{dataset})
of how contingency tables can be combined
recursively to form larger contingency tables.}

When building a conditional contingency table from an {\adtree},
we will not need to explicitly specify the query condition. Instead,
we will supply an {\adnode} of the {\adtree}, which implicitly
is equivalent information. The algorithm is:

\ \\

\oneindent{\computecontab}( \{ $\attset$ \} , \adn )

\twoindent Let $\vn \assign \mbox{The $\varyattx{\isubx{1}}$ subnode of {\adn}}$.

\twoindent Let $\mcv \assign \structref{\vn}{\mcv}$.

\twoindent For $k \assign 1 , 2 , \ldots , \arityisubone$

\threeindent If $k \neq \mcv$

\fourindent Let $\adnk \assign \mbox{The $\attisubxequaly{1}{k}$ subnode of $\vn$}$.

\fourindent $\ctsub{k} \assign \computecontab( \{ \attsetfromtwo \} , \adnk )$.

\ 

\twoindent $\ctsubmcv \assign \mbox{(calculated as explained below)}$

\ 

\twoindent Return the concatenation of \mbox{$\ctsub{1} \ldots \ctsub{\arityisubone}$}.

\ 

\noindent
The base case of this recursion occurs when the first argument is empty, in
which case we return a one-element contingency table
containing the count associated with the current {\adnode}, {\adn}.

There is an omission in the algorithm. In the 
iteration over $k \in \{ 1 , 2 , \ldots \arityisubone \}$ we are unable
to compute the conditional contingency table for $\ctsubmcv$ because
the $\attisubx{1} = \mcv$ subtree is deliberately missing 
as per Section~\ref{adtree}. What can we do instead?

We can take advantage of the following property of contingency
tables:
\begin{equation}
\cont(\attsetfromtwo \mid \query) =
\sum_{k = 1}^{\arityisubone}
\cont(\attsetfromtwo \mid \attisubx{1} = k , \query)
\end{equation}
The value $\cont(\attsetfromtwo \mid \query)$ can be 
computed from within our algorithm by calling
\begin{equation}
\computecontab( \{ \attsetfromtwo \} , \adn )
\end{equation}
and so the missing conditional contingency table in the algorithm
can be computed by the following row-wise subtraction:
\begin{equation}
\ctsubmcv \assign
\computecontab( \{ \attsetfromtwo \} , \adn )
-
\sum_{k \neq MCV}
\ctsub{k}
\end{equation}
Frequent Sets~\cite{agrw:assc}, which are traditionally used for
learning association rules, can also be used for computing counts. A
recent paper~\cite{mnnl:mltp}, which also employs a similar
subtraction trick, calculates counts from Frequent Sets. 
In Section~\ref{whynot} we will discuss
the strengths and weaknesses of Frequent Sets in comparison with
{\adtree}s.

\subsection{Complexity of building a contingency table}
What is the cost of computing a contingency table? Let us consider the
theoretical worst-case cost of computing a contingency table for $n$
attributes each of arity $k$---note that this cost is unrealistically
pessimistic (except when $k=2$), because most contingency tables are
sparse, as discussed later.  The assumption that all attributes have
the same arity, $k$, is made to simplify the calculation of the
worst-case cost, but is not needed by the code. 

A contingency table for $n$ attributes has $k^n$ entries. Write
$C(n) =$ the cost of computing such a contingency table. In the
top-level call of {\computecontab} there are $k$ calls to build
contingency tables from $n-1$ attributes: $k-1$ of these calls are to
build $\ct(\attsetfromtwo \mid \attisubx{1} = j ,
\query )$ for every $j$ in $\{1,2, \ldots k\}$ {\em except} the MCV,
and the final call is to build $\ct( \attsetfromtwo \mid \query )$.
Then there will be $k-1$ subtractions of contingency tables, which
will each require $k^{n-1}$ numeric subtractions. So we have
\begin{eqnarray}
C(0) & = & 1 \\
C(n) & = & k C(n-1) + (k-1) k^{n-1} \mbox{\ \ \ if $n > 0$}
\end{eqnarray}
The solution to this recurrence relation is $C(n) = (1 + n (k-1)) k^{n-1}$;
this cost is loglinear in the size of the contingency table. By
comparison, if we used no cached data structure, but simply counted
through the dataset in order to build a contingency table we would
need $O(nR + k^n)$ operations where $R$ is the number of records in
the dataset. We are thus cheaper than the standard counting method if
$k^n \ll R$.  We are interested in large datasets in which $R$ may
be more than $100,000$. In such a case our method will present a
several order of magnitude speedup for, say, a contingency table of
eight binary attributes.  Notice that this cost is {\bf independent of M},
the total number of attributes in the dataset, and only depends upon
the (almost always much smaller) number of attributes $n$ requested
for the contingency table.

\subsection{Sparse representation of contingency tables}
In practice, we do not represent contingency tables as
multidimensional arrays, but rather as tree structures. This gives
both the slow counting approach and the {\adtree} approach a
substantial computational advantage in cases where the contingency
table is sparse, i.e. has many zero entries. Figure~\ref{sparse} shows
such a sparse contingency table representation. This can mean
average-case behavior is much faster than worst case for contingency
tables with large numbers of attributes or high-arity attributes.

Indeed, our experiments in Section~\ref{experiments} show costs rising
much more slowly than $O(nk^{n-1})$ as $n$ increases. Note too that when
using a sparse representation, the worst-case for {\computecontab} is
now $O(\min(nR,nk^{n-1}))$ because $R$ is the maximum possible number of
non-zero contingency table entries.


\ourfig{sparse}{3.5in}{3.1in}{The right hand figure is the sparse
representation of the contingency table on the left.}

\section{Cache Reduction III: Leaf-Lists}
\label{leaflistsec}
We now introduce a scheme for further reducing memory use.
It is not worth building the {\adtree} data structure for a small
number of records. For example, suppose we have 15 records and 40 binary
attributes. Then the analysis in Appendix~A shows us that in the worst
case the {\adtree} might require 10701 nodes. But computing
contingency tables using the resulting {\adtree} would, with so few
records, be no faster than the conventional counting approach, which would
merely require us to retain the dataset in memory.

Aside from concluding that {\adtree}s are not useful for very small
datasets, this also leads to a final method for saving memory in large
{\adtree}s. Any {\adtree} node with fewer than $\rmin$ records does not
expand its subtree. Instead it maintains a list of pointers into the
original dataset, explicitly listing those records that match the
current {\adnode}. Such a list of pointers is called a {\em
leaf-list}.  Figure~\ref{leaflist} gives an example.

\ourfig{leaflist}{4in}{2.8in}{An {\adtree} built using leaf-lists
with $\rmin = 4$. Any node matching 3 or fewer records is
not expanded, but simply records a set of pointers into the
dataset (shown on the right).}

The use of leaf-lists has one minor and two major consequences.  The
minor consequence is the need to include a straightforward change in
the contingency table generating algorithm to handle leaf-list nodes.
This minor alteration is not described here.  The first major
consequence is that now the dataset itself must be retained in main
memory so that algorithms that inspect leaf-lists can access the rows
of data pointed to in those leaf-lists.  The second major consequence
is that the {\adtree} may require much less memory. This is documented
in Section~\ref{experiments} and worst-case bounds are provided in
Appendix~A.

\section{Using {\adtree}s for Machine Learning}

As we will see in Section~\ref{experiments}, the {\adtree} structure
can substantially speed up the computation of contingency tables for
large real datasets. How can machine learning and statistical
algorithms take advantage of this? Here we provide three examples:
Feature Selection, Bayes net scoring and rule learning. But it seems
likely that many other algorithms can also benefit, for example
stepwise logistic regression, GMDH~\cite{mdl:indc}, and text classification.
Even decision tree~\cite{qnln:lrnn,brmn:clss} learning may 
benefit.~\footnote{This depends on whether the cost of initially building
the {\adtree} can be amortized over many runs of the decision tree algorithm.
Repeated runs of decision tree building can occur if one is using
the wrapper model of feature selection~\cite{jhn:irrl}, or if one
is using a more intensive search over tree structures than the 
traditional greedy search~\cite{qnln:lrnn,brmn:clss}}
In future work we will also
examine ways to speed up nearest neighbor and other memory-based
queries using {\adtree}s.

\subsection{Datasets}
The experiments used the datasets in Table~\ref{datasets}. Each
dataset was supplied to us with all continuous attributes already
discretized into ranges.

\ourtab{datasets}{Datasets used in experiments.}{\begin{center}
\begin{footnotesize}
\begin{tabular}{|l|r|l|p{0.5\textwidth}|}
\hline
Name     & $R$ = Num. & $M$ = Num. &  \\
         & Records    & Attributes &             \\ \hline
ADULT1   &  15,060    & 15         & The small ``Adult Income'' dataset
                                     placed in the UCI repository by
                                     Ron Kohavi~\cite{khv:scln}. Contains
                                     census data related to job,
                                     wealth, and nationality.
                                     Attribute arities range from 2 to
                                     41.  In the UCI repository this
                                     is called the Test Set. Rows with
                                     missing values were removed. \\
                                     \hline
ADULT2   &  30,162    & 15         & The same kinds of records as above but
                                     with different data. The Training Set.
                                     \\ \hline
ADULT3   &  45,222    & 15         & ADULT1 and ADULT2 concatenated.
                                     \\ \hline
CENSUS1  & 142,421    & 13         & A larger dataset based on a
                                     different census, also
                                     provided by Ron Kohavi. \\ \hline
CENSUS2  & 142,421    & 15         & The same data as CENSUS1, but with
                                     the addition of two extra, high-arity
                                     attributes. \\ \hline
BIRTH    &   9,672    & 97         & Records concerning a very wide number
                                     of readings and factors recorded at
                                     various stages during pregnancy. 
                                     Most attributes are binary, and 70 of
                                     the attributes are very sparse, with
                                     over $95\%$ of the values being FALSE.
                                     \\ \hline
SYNTH    & 30K--500K  & 24         & Synthetic datasets of entirely binary
                                     attributes generated using the Bayes
                                     net in Figure~\ref{synth}.
                                     \\ \hline
\end{tabular}
\end{footnotesize}
\end{center}}

\ourfig{synth}{2in}{2in}{A Bayes net that generated our SYNTH
datasets. There are three kinds of nodes. The nodes marked
with triangles are generated with $P(\atti = 1) = 0.8, P(\atti = 2) = 0.2$.
The square nodes are deterministic. A square node takes value
2 if the sum of its four parents is even, else it takes
value 1. The circle nodes are probabilistic functions
of their single parent, defined by $P(\atti = 2 \mid \parent = 1) = 0$
and $P(\atti = 2 \mid \parent = 2) = 0.4$.
This provides a dataset with fairly sparse values
and with many interdependencies.}

\subsection{Using {\adtree}s for Feature Selection}

Given $M$ attributes, of which one is an output that we wish to
predict, it is often interesting to ask ``which subset of $n$ attributes,
($n < M$), is the best predictor of the output on the same distribution of
datapoints that are reflected in this dataset?'' \cite{khv:thpw}.
There are many ways of
scoring a set of features, but a particularly simple one is
{\em information gain}~\cite{cvr:infr}.

 Let $\aout$ be the attribute we wish to predict and let
 $\attset$ be the set of attributes used as inputs. 
 Let $X$ be the set of possible assignments of values to $\attset$ and write
 $\assk \in X$ as the $k$th such assignment. Then
\begin{equation}
\infogain =
   \sum_{v = 1}^{\arity{out}}
    \plogp\left(\frac{\countfun(\aout = v)}{R}\right)
  -\sum_{k = 1}^{\mid X \mid}
    \frac{\countfun(\assk)}{R}
    \sum_{v = 1}^{\arity{out}}
     \plogp\left(\frac{\countfun(\aout = v , \assk)}{\countfun(\assk)}\right)
\end{equation}
where
$R$ is the number of records in the entire dataset and
\begin{equation}
\plogp(x) = -x \log_2 x
\end{equation}
The counts needed in the above computation can be read
directly from $\cont(\aout,\attset)$.

Searching for the best subset of attributes is simply a question of
search among all attribute-sets of size $n$ ($n$ specified by the
user). This is a simple example designed to test our counting
methods: any practical feature selector would need to
penalize the number of rows in the contingency table
(else high arity attributes would tend to win).

\subsection{Using {\adtree}s for Bayes Net Structure Discovery}

There are many possible Bayes net learning tasks, all of which
entail counting, and hence might be speeded up
by {\adtree}s. In this paper we present experimental results
for the particular example of scoring the structure
of a Bayes net to decide how well it matches the data.

We will use maximum likelihood scoring with a penalty for the number
of parameters.  We first compute the probability table associated with
each node.  Write $\parentsj$ for the parent attributes of node $j$
and write $\parentjassignments$ as the set of possible assignments of
values to $\parentsj$. The maximum likelihood estimate for
\begin{equation}
P(\attj = v \mid \parentjassignments)
\end{equation}
is estimated as
\begin{equation}
\frac{\countfun(\attj = v , \parentjassignments)
     }{\countfun(\parentjassignments)}
\end{equation}
and all such estimates for node $j$'s probability tables can be
read from $\cont(\attj , \parentsj)$.

The next step in scoring a structure is to decide the likelihood of
the data given the probability tables we computed and to penalize the
number of parameters in our network (without the penalty the likelihood
would increase every time a link was added to the network).
The penalized log-likelihood score~\cite{frdm:comp} is
\begin{equation}
\label{bayeseq}
 - \numparams \log(R) / 2
 + R \sum_{j = 1}^{M} 
     \sum_{\asssmall \in \parentjassignments}
       \sum_{v = 1}^{\arity{j}}
         P(\attj = v \wedge \asssmall)
          \log P(\attj = v \mid \asssmall)
\end{equation}
where $\numparams$ is the total number of probability table entries
in the network.

We search among structures to find the best score. In these
experiments we use random-restart stochastic hill climbing in which the
operations are random addition or removal of a network link or
randomly swapping a pair of nodes. The latter operation is
necessary to allow the search algorithm to choose the best ordering of
nodes in the Bayes net.  Stochastic searches such as this are a
popular method for finding Bayes net structures~\cite{frdm:comp}. Only
the probability tables of the affected nodes are recomputed on each
step. 

Figure~\ref{bayes-output} shows the Bayes net structure returned by our
Bayes net structure finder after 30,000 iterations of hill climbing.

\ourfig{bayes-output}{4in}{1.9in}{Output from the Bayes structure
finder running on the ADULT2 dataset. {\em Score} is the contribution
to the sum in Equation~\ref{bayeseq} due to the specified
attribute. {\em np} is the number of entries in the probability table
for the specified attribute.}

\subsection{Using {\adtree}s for Rule Finding}
Given an output attribute $\aout$ and a distinguished value $\vout$,
rule finders search among conjunctive queries of the form
\begin{equation}
\ass = ( \conjquery )
\end{equation}
to find the query that maximizes the estimated value
\begin{equation}
P(\aout = \vout \mid \ass) 
=
\frac{\countfun(\aout = \vout , \ass)}{\countfun(\ass)}
\end{equation}
To avoid rules without significant support,
we also insist that $\countfun(\ass)$ (the number
of records matching the query) must be above some threshold $\smin$.

In these experiments we implement a brute force search that looks
through all possible queries that involve a user-specified number of
attributes, $n$. We build each $\cont(\aout, \attset)$ in turn (there
are $M$ {\em choose} $n$ such tables), and then look through the
rows of each table for all queries using the $\attset$ that have greater
than minimum support $\smin$. We return a priority queue of the
highest scoring rules.  For instance on the ADULT2 dataset, the
best rule for predicting ``class'' from 4 attributes was: 
\begin{quote}
score = 0.965 (218/226), workclass = Private, education-num = above12,
marital-status = Married-civ-spouse, capital-loss = above1600 $\Rightarrow$
class $\geq$ 50k
\end{quote}

\section{Experimental Results}
\label{experiments}

Let us first examine the memory required by an {\adtree} on our datasets.
Table~\ref{treesize} shows us, for example, that the ADULT2 dataset
produced an {\adtree} with 95,000 nodes. The tree required almost 11 megabytes
of memory. Among the three ADULT datasets, the size of the tree varied approximately
linearly with the number of records. 

Unless otherwise specified, in all the experiments in this section,
the ADULT datasets used no leaf-lists. The BIRTH and SYNTHETIC
datasets used leaf-lists of size $\rmin = 16$ by default. The BIRTH
dataset, with its large number of sparse attributes, required a modest 8
megabytes to store the tree---many magnitudes below the worst-case
bounds. Among the synthetic datasets, the tree size increased
sublinearly with the dataset size. This indicates that as the dataset
gets larger, novel records (which may cause new nodes to appear in the tree)
become less frequent.

\ourtab{treesize}{The size of {\adtree}s for various
datasets. $M$ is the number of attributes. $R$ is the number
of records. {\em Nodes} is the number of nodes in the {\adtree}.
{\em Megabytes} is the amount of memory needed to store
the tree. {\em Build Time} is the number of seconds needed
to build the tree (to the nearest second).}{\begin{tabular}{|l|l|r|r|r|r|}
\hline
Dataset & M & R & Nodes & Megabytes & Build Time \\ \hline
CENSUS1 & 13 & 142521 & 24007 & 1.5 & 17 \\
CENSUS2 & 15 & 142521 & 209577 & 13.2 & 32 \\
ADULT1 & 15 & 15060 & 58200 & 7.0 & 6 \\
ADULT2 & 15 & 30162 & 94900 & 10.9 & 10 \\
ADULT3 & 15 & 45222 & 162900 & 15.5 & 15 \\
BIRTH & 97 & 9672 & 87400 & 7.9 & 14 \\
SYN30K & 24 & 30000 & 34100 & 2.8 & 8 \\
SYN60K & 24 & 60000 & 59300 & 4.9 & 17 \\
SYN125K & 24 & 125000 & 95400  & 7.9 & 36 \\
SYN250K & 24 & 250000 & 150000 & 12.4 & 73 \\
SYN500K & 24 & 500000 & 219000 & 18.2 & 150 \\ \hline
\end{tabular}}

Table~\ref{bayesnet} shows the costs of performing 30,000 iterations
of Bayes net structure searching. All experiments were performed on a
200Mhz Pentium Pro machine with 192 megabytes of main memory.  Recall
that each Bayes net iteration involves one random change to the network
and so requires recomputation of one contingency table (the exception
is the first iteration, in which all nodes must be computed). This
means that the time to run 30,000 iterations is essentially the time
to compute 30,000 contingency tables.  Among the ADULT datasets, the
advantage of the {\adtree} over conventional counting ranges between a
factor of 19 to 32. Unsurprisingly, the computational costs for ADULT
increase sublinearly with dataset size for the {\adtree} but linearly
for the conventional counting. The computational advantages and the sublinear
behavior are much more pronounced for the synthetic data.

\ourtab{bayesnet}{The time (in seconds) to
perform 30,000 hill-climbing iterations searching for
the best Bayes net structure. {\em {\adtree} Time} is the time
when using the {\adtree} and {\em Regular Time} is the time
taken when using the conventional probability table
scoring method of counting through the dataset. {\em
Speedup Factor} is the number of times by which the {\adtree} method
is faster than the conventional method.
The {\adtree} times do not include the time for building the {\adtree}
in the first place (given in Table~\ref{treesize}). 
A typical use of {\adtree}s will build the tree only once and
then be able to use it for many data analysis operations, and so
its building cost can be amortized. In any case, even including
tree building cost would have only a minor impact on the results.
}{\begin{tabular}{|l|l|r|r|r|r|}
\hline
Dataset & M & R & {\adtree} Time & Regular Time & Speedup Factor \\ \hline
CENSUS1 & 13 & 142521 & 162 & 48300  & 298.1 \\
CENSUS2 & 15 & 142521 & 783 & 27000  & 34.5 \\
ADULT1  & 15 & 15060  & 150 & 2850   & 19 \\
ADULT2  & 15 & 30162  & 226 & 5160   & 22.8 \\
ADULT3  & 15 & 45222  & 220 & 7140   & 32.5 \\
BIRTH   & 97 & 9672   & 23  & 2820   & 122.6 \\
SYN30K  & 24 & 30000  & 32  & 10410  & 325.3 \\
SYN60K  & 24 & 60000  & 32  & 18360  & 573.8 \\
SYN125K & 24 & 125000 & 34  & 42840  & 1260.0 \\
SYN250K & 24 & 250000 & 35  & 88830  & 2538.0 \\
SYN500K & 24 & 500000 & 36  & 155158 & 4298.3 \\ \hline
\end{tabular}}

Next, Table~\ref{length} examines the effect of leaf-lists on the
ADULT2 and BIRTH datasets. For the ADULT dataset, the byte size of
the tree decreases by a factor of 5 when leaf-lists are increased from
1 to 64. But the computational cost of running the Bayes search
increases by only $25\%$, indicating a worth-while tradeoff if memory
is scarce.

\ourtab{length}{Investigating the effect of the $\rmin$ parameter
on the ADULT2 dataset and the BIRTH dataset.
{\em {\#}Mb} is the memory used by the {\adtree}. 
{\em {\#}nodes} is the number of nodes in the {\adtree}. 
{\em Build Secs} is the time to build the {\adtree}.
{\em Search Secs} is the time needed to perform 30,000
iterations of the Bayes net structure search.}{\begin{tabular}{|r|rrrr|rrrr|}
\hline
        & \multicolumn{4}{c|}{ADULT2} & \multicolumn{4}{c|}{BIRTH} \\
\hline
$\rmin$ & {\#}Mb & {\#}nodes    & Build    & Search   & {\#}Mb & {\#}nodes   & Build    & Search  \\
        &        &              & Secs     & Secs     &        &             & Secs     & Secs    \\
\hline
1    & 10.87 & 94,872 & 13 & 225  & & & & \\   
2    & 8.46  & 86,680 & 11 & 223  & & & & \\    
4    & 6.30  & 75,011 & 9  & 223  & 27.60 & 245,722 & 32 & 25 \\
8    & 4.62  & 62,095 & 7  & 224  & 14.90 & 152,409 & 21 & 22 \\
16   & 3.37  & 49,000 & 6  & 232  &  7.95 &  87,415 & 15 & 23 \\
32   & 2.55  & 37,790 & 5  & 245  &  4.30 &  46,777 & 11 & 26 \\
64   & 1.98  & 27,726 & 5  & 274  &  2.42 &  23,474 &  8 & 31 \\
128  & 1.59  & 18,903 & 3  & 331  &  1.48 &  11,554 &  7 & 38 \\
256  & 1.38  & 12,539 & 3  & 420  &  0.95 &   5,150 &  5 & 61 \\
512  & 1.21  & 7,336  & 3  & 586  &  0.65 &   2,237 &  4 & 100 \\
1024 & 1.05  & 3,928  & 3  & 881  &  0.45 &     887 &  3 & 170 \\
2048 & 0.95  & 1,890  & 1  & 1231 &  0.28 &     246 &  1 & 270 \\
4096 & 0.86  & 780    & 1  & 1827 &  0.28 &     201 &  2 & 303 \\
\hline
\end{tabular}}

The Bayes net scoring results involved the average cost of computing
contingency tables of many different sizes. The following results in
Tables~\ref{featsel} and~\ref{ruleq} make the savings for fixed size
attribute sets easier to discern.  These tables give results for the
feature selection and rule finding algorithms, respectively.  The
biggest savings come from small attribute sets. Computational savings
for sets of size one or two are, however, not particularly interesting
since all such counts could be cached by straightforward methods
without needing any tricks. In all cases, however, we do see large
savings, especially for the BIRTH data. Datasets with larger numbers
of rows would, of course, reveal larger savings.

\ourtab{featsel}{The time taken to search among all
attribute sets of a given size (Number Attributes) for
the set that gives the best information gain in predicting the
output attribute. The times, in seconds, are
the average evaluation times per attribute-set.}{\begin{tabular}{|l|rllr|rllr|}
\hline
           & \multicolumn{4}{c|}{ADULT2}               & \multicolumn{4}{c|}{BIRTH} \\
Number     & Number    & {\adtree} & Regular & Speedup & Number    & {\adtree} & Regular & Speedup \\
Attributes & Attribute & Time      & Time    & Factor  & Attribute & Time      & Time    & Factor  \\
           & Sets      &           &         &         & Sets      &           &         &         \\
\hline
1          & 14        & .000071   & .048    & 675.0   & 96        & .000018   & .015    & 841     \\
2          & 91        & .00054    & .067    & 124.0   & 4,560      & .000042   & .021    & 509     \\
3          & 364       & .0025     & .088    & 34.9    & 142,880    & .000093   & .028    & 298     \\
4          & 1,001      & .0083     & .11     & 13.4    & 3,321,960   & .00019    &         &         \\
5          & 2,002      & .023      & .14     &  6.0    & 61,124,064  & .00033  &  &       \\
\hline
\end{tabular}}

\ourtab{ruleq}{The time taken to search among all
rules of a given size (Number Attributes) for
the highest scoring rules for predicting the
output attribute. The times, in seconds, are the average evaluation time per rule.}{\begin{tabular}{|r|rllr|rllr|}
\hline
           & \multicolumn{4}{c|}{ADULT2}               & \multicolumn{4}{c|}{BIRTH} \\
Number     & Number    & {\adtree} & Regular & Speedup & Number    & {\adtree} & Regular & Speedup \\
Attributes & Rules     & Time      & Time    & Factor  & Rules     & Time      & Time    & Factor  \\
\hline
1          & 116       & .000019   & .0056   & 295.0   & 194       & .000025   & .0072   & 286     \\
2          & 4,251      & .000019   & .0014   & 75.3    & 17,738     & .000021   & .0055   & 259     \\
3          & 56,775     & .000024   & .00058  & 23.8    & 987,134    & .000022   & .0040   & 186     \\
4          & 378,984    & .000031   & .00030  & 9.8     & 37,824,734  & .000024   & .0030   & 127     \\
5          & 1,505,763   & .000042   & .00019 & 4.7     & 1,077,672,055  & .000026 &    &     \\
\hline
\end{tabular}}

\section{Alternative Data Structures}
\label{whynot}

\subsection{Why not use a {\kdtree}?}
{\kdtree}s can be used for accelerating learning
algorithms~\cite{omhn:effc,mr:lwpr}. The primary difference is that a
{\kdtree} node splits on only one attribute instead of all
attributes. This results in much less memory (linear in the number of
records). But counting can be expensive. Suppose, for example, that
level one of the tree splits on $\attone$, level two splits on
$\atttwo$, etc. Then, in the case of binary variables, if we have a
query involving only attributes $\attnum{20}$ and higher, we have
to explore all paths in the tree down to level 20. With datasets of
fewer than $2^{20}$ records this may be no cheaper than performing a
linear search through the records.  Another possibility,
{\rtree}s~\cite{gttm:rtrs,rssp:drct}, store databases of $M$-dimensional
geometric objects. However, in this context, they offer no advantages
over {\kdtree}s.

\subsection{Why not use a Frequent Set finder?}
Frequent Set finders~\cite{agrw:assc} are typically used with
very large databases of millions of records containing very sparse
binary attributes. Efficient algorithms exist for finding all subsets
of attributes that co-occur with value TRUE in more than a fixed
number (chosen by the user, and called the {\em support}) of records.
Recent research{\cite{mnnl:mltp}} suggests that such Frequent Sets can
be used to perform efficient counting. In the case where $\mbox{\em
support} = 1$, all such Frequent Sets are gathered and, if counts of
each Frequent Set are retained, this is equivalent to producing an
{\adtree} in which instead of performing a node cutoff for the most
common value, the cutoff always occurs for value FALSE.

The use of Frequent Sets in this way would thus be very similar
to the use of {\adtree}s, with one advantage and one  disadvantage.
The advantage is that efficient algorithms have been developed for
building Frequent Sets from a small number of sequential passes through data.
The {\adtree} requires random access to the dataset while it is being built,
and for its leaf-lists. This is impractical if the dataset is too large
to reside in main memory and is accessed through database queries.

The disadvantage of Frequent Sets in comparison with {\adtree}s is
that, under some circumstances, the former may require much more memory.
Assume the value 2 is rarer than 1 throughout all attributes in the
dataset and assume reasonably that we thus choose to find all Frequent
Sets of 2s.  Unnecessarily many sets will be produced if there are
correlations.  In the extreme case, imagine a dataset in which $30\%$
of the values are 2, $70\%$ are 1 and attributes are perfectly
correlated---all values in each record are identical. Then, with $M$
attributes there would be $2^M$ Frequent Sets of 2s. In contrast, the
{\adtree} would only contain $M+1$ nodes.  This is an extreme example,
but datasets with much weaker inter-attribute correlations can
similarly benefit from using an {\adtree}.

Leaf-lists are another technique to reduce the size of {\adtree}s further.
They could also be used for the Frequent Set representation.

\subsection{Why not use hash tables?}  
If we knew that only a small set of contingency tables would ever be
requested, instead of all possible contingency tables, then an
{\adtree} would be unnecessary. It would be better to remember this
small set of contingency tables explicitly. Then, some kind of tree
structure could be used to index the contingency tables. But a hash
table would be equally time efficient and require less space. A hash
table coding of individual counts in the contingency tables would
similarly allow us to use space proportional only to the number of
non-zero entries in the stored tables.  But for representing
sufficient statistics to permit fast solution to any contingency table
request, the {\adtree} structure remains more memory efficient than
the hash-table approach (or any method that stores all non-zero
counts) because of the memory reductions when we exploit the ignoring
of most common values.

\section{Discussion}

\subsection{What about numeric attributes?}
The {\adtree} representation is designed entirely for symbolic
attributes. When faced with numeric attributes, the simplest solution
is to discretize them into a fixed finite set of values which are then
treated as symbols, but this is of little help if the user requests
counts for queries involving inequalities on numeric attributes. In
future work we will evaluate the use of structures combining elements
from multiresolution {\kdtree}s of real attributes~\cite{mr:lwpr} with
{\adtree}s.

\subsection{Algorithm-specific counting tricks}
Many algorithms that count using the conventional ``linear'' method
have algorithm-specific ways of accelerating their performance. For
example, a Bayes net structure finder may try to remember all the
contingency tables it has tried previously in case it needs to re-evaluate
them. When it deletes a link, it can deduce the new contingency table
from the old one without needing a linear count.

In such cases, the most appropriate use of the {\adtree} may be as a lazy
caching mechanism. At birth, the {\adtree} consists only of the root
node. Whenever the structure finder needs a contingency table
that cannot be deduced from the current {\adtree} structure, the appropriate
nodes of the {\adtree} are expanded. The {\adtree} then takes on the
role of the algorithm-specific caching methods, while (in general) using
up much less memory than if all contingency tables were remembered.

\subsection{Hard to update incrementally}
Although the tree can be built cheaply (see the experimental results
in Section~\ref{experiments}), and although it can be built lazily,
the {\adtree} cannot be updated cheaply with a new record. This is
because one new record may match up to $2^M$ nodes in the tree in the
worst case.

\subsection{Scaling up}
The {\adtree} representation can be useful for datasets of the rough
size and shape used in this paper.  On the first datasets we have
looked at---the ones described in this paper---we have shown
empirically that the sizes of the {\adtree}s are tractable given real
noisy data. This included one dataset with 97 attributes.  It is the
extent to which the attributes are skewed in their values and
correlated with each other that enables the {\adtree} to avoid
approaching its worse-case bounds. The main technical contribution of
this paper is the trick that allows us to prune off
most-common-values.  Without it, skewedness and correlation would
hardly help at all.~\footnote{Without pruning, on all of our
datasets we ran out of memory on a 192 megabyte machine before we had
built even $1\%$ of the tree, and it is easy to show that the BIRTH
dataset would have needed to store more than $10^{30}$ nodes.}  The
empirical contribution of this paper has been to show that the actual
sizes of the {\adtree}s produced from real data are vastly smaller than
the sizes we would get from the worst-case bounds in Appendix~A.

But despite these savings, {\adtree}s cannot yet represent all the
sufficient statistics for huge datasets with many hundreds of
non-sparse and poorly correlated attributes.  What should we do if our
dataset or our {\adtree} cannot fit into main memory? In the latter
case, we could simply increase the size of leaf-lists, trading off
decreased memory against increased time to build contingency
tables. But if that is inadequate at least three possibilities
remain. First, we could build approximate {\adtree}s that do not store
any information for nodes that match fewer than a threshold number of
records. Then approximate contingency tables (complete with error
bounds) can be produced~\cite{mnnl:mltp}.
A second possibility is to exploit secondary storage and store deep,
rarely visited nodes of the {\adtree} on disk. This would doubtless
best be achieved by integrating the machine learning algorithms with
current database management tools---a topic of considerable interest
in the data mining community~\cite{fyyd:data}. A third possibility,
which restricts the size of contingency tables we may ask for, is to
refuse to store counts for queries with more than some threshold
number of attributes.


\subsection{What about the cost of building the tree?}
In practice, {\adtree}s could be used in two ways:
\begin{itemize}
\item
{\bf One-off.} When a traditional algorithm is required we build the
{\adtree}, run the fast version of the algorithm, discard the
{\adtree}, and return the results.

\item
{\bf Amortized.} When a new dataset becomes available, a new {\adtree}
is built for it. The tree is then shipped and re-used by anyone who
wishes to do real-time counting queries, multivariate graphs and
charts, or any machine learning algorithms on any subset of the
attributes.  The cost of the initial tree building is then amortized
over all the times it is used. In database terminology, the process is
known as materializing~\cite{hrnr:impl} and has been suggested as
desirable for datamining by several
researchers~\cite{jhn:sppn,mnnl:mltp}.
\end{itemize}
The one-off option is only useful if the cost of building the
{\adtree} plus the cost of running the {\adtree}-based algorithm is
less than the cost of the original counting-based algorithm.  For the
intensive machine learning methods studied here, this condition is
safely satisfied. But what if we decided to use a less intensive,
greedier Bayes net structure finder? Table~\ref{greedier} shows that
if we only run for 300 iterations instead of
30,000\footnote{Unsurprisingly, the resulting Bayes nets have a
highly inferior structure.}  and if we account for a one-off {\adtree}
building cost, then the relative speedup of using {\adtree}s declines
greatly.

\ourtab{greedier}{Computational economics of building {\adtree}s and
using them to search for Bayes net structures using the
experiments of Section~\ref{experiments}.
}{\begin{tabular}{|l|r|r|r|}
\hline
Dataset   & 
 \multicolumn{1}{p{3cm}|}{\raggedright Speedup ignoring build-time,
                          30,000 iterations} &
 \multicolumn{1}{p{3cm}|}{\raggedright Speedup allowing for build-time,
                          30,000 iterations} &
 \multicolumn{1}{p{3cm}|}{\raggedright Speedup allowing for build-time,
                          300 iterations} \\
\hline
  CENSUS1 &    298.15     & 269.83        & 25.94          \\
  CENSUS2 &     34.48     &  33.13        &  6.78          \\
   ADULT1 &     19.00     &  18.27        &  3.80          \\
   ADULT2 &     22.83     &  21.86        &  4.21          \\
   ADULT3 &     32.45     &  30.38        &  4.15          \\
    BIRTH &    122.61     &  76.22        &  1.98          \\
   SYN30K &    325.31     & 260.25        & 12.51          \\
   SYN60K &    573.75     & 374.69        & 10.60          \\
  SYN125K &   1260.00     & 612.00        & 11.79          \\
  SYN250K &   2538.00     & 822.50        & 12.11          \\
  SYN500K &   4309.94     & 834.18        & 10.32          \\
\hline
\end{tabular}}

To conclude: if the data analysis is intense then there is benefit to
using {\adtree}s even if they are used in a one-off fashion.  If the
{\adtree} is used for multiple purposes then its build-time is
amortized and the resulting relative efficiency gains over traditional
counting are the same for both exhaustive searches and non-exhaustive
searches. Algorithms that use non-exhaustive searches include
hill-climbing Bayes net learners, greedy rule learners such as
CN2~\cite{clrk:cn2} and decision tree
learners~\cite{qnln:lrnn,brmn:clss}.

% \myhead{{\adtree}s are algorithm and learning-task independent}
% Once an {\adtree} is built, it may be saved to disk along with the
% dataset and reused whenever an algorithm needs contingency tables.
% The tree does not treat input and output attributes any differently, so
% the same tree may be used for multiple tasks. Finally, a learning
% algorithm might wish to run over a restricted subset of the data
% specified by a query. For example we might want to run a rule learner
% restricted to the subset of records in which $\attone = 1$ and
% $\attnum{7} = 3$. In that case the same {\adtree} can also be re-used.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
\acks{This work was sponsored by a National Science Foundation Career Award
to Andrew Moore. The authors thank Justin Boyan, Scott Davies, Nir
Friedman, and Jeff Schneider for their suggestions, and Ron Kohavi for
providing the census datasets.}

\subsection*{Appendix~A: Memory Costs}
In this appendix we examine the size of the tree. For simplicity, we
restrict attention to the case of binary attributes.

\myhead{The worst-case number of nodes in an {\adtree}}
Given a dataset with $M$ attributes and $R$ records, the worst-case for
the {\adtree} will occur if all $2^M$ possible records exist in the
dataset. Then, for every subset of attributes there exists exactly one
node in the {\adtree}. For example consider the attribute set $\{ \attset \}$,
where $i(1) < i(2) < ... < i(n)$.  Suppose there is a node in the tree
corresponding to the query $\{ \conjquery \}$ for some values 
$v_1 \ldots v_n$. From the definition of an {\adtree}, and remembering we 
are only considering the case of binary attributes, we can state:
\begin{itemize}
\item
$\vsub{1}$ is the least common value of $\attisubx{1}$.
\item
$\vsub{2}$ is the least common value of $\attisubx{2}$ among those
records that match $( \attisubx{1} = v_1 )$.

$\vdots$

\item
$\vsub{k+1}$ is the least common value of $\attisubx{k+1}$ among those
records that match $( \attisubx{1} = v_1 , \ldots , \attisubx{k} = v_k )$.
\end{itemize}

So there is at most one such node.  Moreover, since our worst-case
assumption is that all possible records exist in the database, we see
that the {\adtree} will indeed contain this node.  Thus, the worst-case
number of nodes is the same as the number of possible subsets of
attributes: $2^M$.

\myhead{The worst-case number of nodes in an {\adtree} with a reasonable
number of rows}
It is frequently the case that a dataset has $R \ll 2^M$. With fewer
records, there is a much lower worst-case bound on the {\adtree} size.
A node at the $k$th level of the tree corresponds to a query involving
$k$ attributes (counting the root node as level 0). Such a node can
match at most $R 2^{-k}$ records because each of the node's ancestors up
the tree has pruned off at least half the records by choosing to expand
only the least common value of the attribute introduced by that ancestor.
Thus, there can be no tree nodes at level $\uplogr$ of the
tree, because such nodes would have to match fewer than
$R 2^{-\uplogrmtwo} < 1$ records. They would thus match no 
records, making them $\nullnode$.

The nodes in an {\adtree} must all exist at level $\uplogrmone$ or higher.
The number of nodes at level $k$ is at most $\mysmallchoose{M}{k}$, because
every node at level $k$ involves an attribute set of size $k$ and
because (given binary attributes) for every attribute set there is at
most one node in the {\adtree}.  Thus the total number of nodes in the
tree, summing over the levels is less than
\begin{equation}
\label{small}
\sum_{k = 0}^{\uplogrmone} \mybigchoose{M}{k} \boundedby O(M^{\uplogrmone} / (\uplogrmtwo)!)
\end{equation}

\myhead{The number of nodes if we assume skewed independent attribute values}
Imagine that all values of all attributes in the dataset are independent
random binary variables, taking value 2 with probability $p$ and taking
value 1 with probability $1 - p$. Then the further $p$ is from $0.5$, the
smaller we can expect the {\adtree} to be. This is because,
on average, the less common value of a Vary node will match 
fraction $\minp$ of its parent's records. And, on average,
the number of records matched at the $k$th level of the tree will be
$R (\minp)^k$. Thus, the maximum level in the tree at which we
may find a node matching one or more records is approximately
$\uplogminprmone$,
where
$q = \min(p,1-p)$. 
And so the total number of nodes in the
tree is approximately
\begin{equation}
\label{eqsparse}
\sum_{k = 0}^{\uplogminprmone} \mybigchoose{M}{k} \boundedby O(M^{\uplogminprmone} / (\uplogminprmtwo)!)
\end{equation}
Since the exponent is reduced by a factor of $\log_2(1/q)$,
skewedness among the attributes thus brings enormous savings in memory.

\myhead{The number of nodes if we assume correlated attribute values}
The {\adtree} benefits from correlations among attributes in much
the same way that it benefits from skewedness. For example, suppose
that each record was generated by the simple Bayes net in Figure~\ref{correlation},
where the random variable $B$ is hidden (not included in the record).
Then for $i \neq j$, $P(\atti \neq \attj) = 2p(1-p)$. If {\adn} is
any node in the resulting {\adtree} then the number of records
matching any other node two levels below {\adn} in the tree will be
fraction $2p(1-p)$ of the number of records matching {\adn}.
>From this we can see that the number of nodes in the tree is
approximately
\begin{equation}
\label{correlated}
\sum_{k = 0}^{\uplogminprmone} \mybigchoose{M}{k} \boundedby O(M^{\uplogminprmone} / (\uplogminprmtwo)!)
\end{equation}
where $q = \sqrt{2p(1-p)}$.
Correlation among the attributes can thus
also bring enormous savings in memory even if (as is the case
in our example) the marginal distribution of individual attributes is uniform.

\ourfig{correlation}{4.5in}{1.25in}{A Bayes
net that generates correlated boolean
attributes $\attnum{1},\attnum{2} \ldots \attnum{M}$.}

\myhead{The number of nodes for the dense {\adtree} of Section~\ref{dense}}
The dense {\adtree}s do not cut off the tree for the most common value
of a Vary node.  The worst case {\adtree} will occur if all $2^M$
possible records exist in the dataset. Then the dense {\adtree} will
require $3^M$ nodes because every possible query (with each attribute
taking values 1, 2 or $\mystar$) will have a count in the tree.  The
number of nodes at the $k$th level of the dense {\adtree} can be $2^k
\mysmallchoose{M}{k}$ in the worst case.

\myhead{The number of nodes when using Leaf-lists}
Leaf-lists were described in Section~\ref{leaflistsec}. If a 
tree is built using maximum leaf-list size of $\rmin$, then any
node in the {\adtree} matching fewer than $\rmin$ records is
a leaf node. This means that Formulae~\ref{small},
\ref{eqsparse} and~\ref{correlated} can be re-used, replacing
$R$ with $R / \rmin$. It is important to remember, however, that
the leaf nodes must now contain room for $\rmin$ numbers instead
of a single count.

\newcommand{\makeadtree}{\mbox{\bf MakeADTree}}
\newcommand{\recordnums}{\varname{RecordNums}}
\newcommand{\makevarynode}{\mbox{\bf MakeVaryNode}}
\newcommand{\childnums}{\varname{Childnums}}

\subsection*{Appendix~B: Building the {\adtree}}
We define the function {\makeadtree}($\attnum{i}$ , \recordnums) where
{\recordnums} is a subset of $\{ 1 , 2 , \ldots , R \}$ ($R$ is the
total number of records in the dataset) and where $1 \leq i \leq M$.
This makes an {\adtree} from the rows specified in
{\recordnums} in which all {\adnode}s represent queries in
which only attributes $\attnum{i}$ and higher are used.

\ \\

\oneindent {\makeadtree}($\attnum{i}$ , \recordnums)

\twoindent Make a new {\adnode} called {\adn}.

\twoindent $\structref{\adn}{\mbox{COUNT}} \assign \mid \recordnums \mid$.

\twoindent For $j \assign i , i+1 , \ldots , M$

\threeindent $\mbox{$j$th Vary node of {\adn}} \assign \makevarynode(\attnum{j},\recordnums)$.

\ \\

{\makeadtree} uses the function {\makevarynode}, which we now define:

\ \\

\oneindent {\makevarynode}($\attnum{i}$ , \recordnums)

\twoindent Make a new Vary node called {\vn}.

\twoindent For $k \assign 1 , 2 , \ldots \arity{i}$

\threeindent Let $\childnums_k \assign \{\}$.

\twoindent For each $j \in \recordnums$

\threeindent Let $v_{ij} = \mbox{Value of attribute $\atti$ in record $j$}$

\threeindent Add $j$ to the set $\childnums_{v_{ij}}$

\twoindent Let $\structref{\vn}{\mcv} \assign {\mbox{argmax}}_k \mid \childnums_k \mid$.

\twoindent For $k \assign 1 , 2 , \ldots \arity{i}$

\threeindent If $\mid \childnums_k \mid = 0$ or if $k = \mcv$

\fourindent Set the $\atti = k$ subtree of $\vn$ to NULL.

\threeindent Else

\fourindent Set the $\atti = k$ subtree of $\vn$ to ${\makeadtree}(\attnum{i+1},\childnums_k)$

\ \\

\noindent
To build the entire tree, we must call ${\makeadtree}(\attnum{1},\{1 \ldots R\})$.
Assuming binary attributes, the cost of building a tree from $R$ records and
$M$ attributes is bounded above by
\begin{equation}
\sum_{k = 0}^{\uplogrmone} \frac{R}{2^k} \mybigchoose{M}{k}
\end{equation}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bibliography{adtree}
\bibliographystyle{theapa}
 
\end{document} 


