
\section{TAR3}

\PARstart{T}{AR3} is a nondeterministic version of the
TAR2 data miner~\cite{me03c} that exploits narrow
funnels to learn very small theories.
This section argues that 
TAR3 is  {\em simple}, 
{\em compentent}, {\em fast}, {\em scalable} and 
a {\em stable}
nondeterministic analysis method. 
Further, TAR3 can be used to detect when {\em 
nondeterminism is unsafe}.


\subsection{An Introduction to TAR3}

Given some oracle that scores each state, it is possible
to learn some assignments to the funnel variables that
improve the average score. Better yet, if the funnels
are narrow (few in number) then those experiments won't take long
and the required assignments will only be few in number.
The key is to find the funnel
variables and this is very
simple:
just look for a small number of variable assignments that have very different
distributions assocaited with the different scores.

\begin{figure}[!t]
{\scriptsize
 {\em
\begin{center}
\begin{tabular}{rccc|ll}
outlook & temp($^o$F) &  humidity & windy? & class& score\\\hline
rain&  85&     86&     false&  none& -1\\
rain&  65&     70&     true&         none& -1\\
overcast&        71&     96&     true&   none& -1\\
\dots &\ldots & \ldots &\ldots & \ldots\\\hline
      overcast&  83&     88&     false&  lots&1\\
      overcast&  64&     65&     true&   lots&1\\
      overcast&  72&     90&     true&   lots&1\\
     overcast&  81&     75&     false&  lots&1\\
\dots &\ldots & \ldots &\ldots & \ldots\\\hline
\end{tabular}\end{center}}}
\caption{Data on some recreational activities where playing {\em lots} of
golf scores higher than playing {\em none} golf.}\label{fig:eg}
\end{figure}
TAR3 is a nondeterministic search for combinations
of variable assignments that most improve, or {\em lift}, the expected
score. 
TAR3 inputs a log of data observations $D$ of the behavior
of a system such as \fig{eg}.
Each behavior $d{\in}D$ is scored by some oracle: e.g. see the last
column of \fig{eg}.

TAR3 begins by discretizing all numeric variables into $R$ distinct
ranges.  Discrete ranges for the score are called the {\em classes}
and each class scores a number value $\$class$; i.e. 
the mean value of that range.
Next, a {\em baseline} is computed from the weighted sum
of the frequency of each class range times the mean score of that class;
i.e.

{\footnotesize
\[baseline=\sum_{c\in classes} \$c*|d \in D \wedge d.class=c|\]}

\begin{figure}
\begin{center}
\includegraphics[width=2.5in]{iris3.pdf}
\end{center}
\caption{Lift and cumulative lift.}\label{fig:lifg}
\end{figure}




\begin{figure}
{\scriptsize
\begin{tabular}{r@{~}|r@{~:~}p{2.1in}|}\cline{2-3}
&R & number of discretized ranges for numeric variables; default=5\\
&D&dataset of examples; dataset is of size $|$D$|$;
each example is
scored, e.g. \fig{eg}; these scores will be divided into R ranges; class(R)
is the highest scoring class.\\
&ENOUGH&minimum ratio of class(R) required for any treatment\\
&VARIABLES&
a set of size $|$V$|$ listing the
variables used in D;\\
inputs:&N   & maximum number of treatments to return; default=10\\
&MAXSIZE&maximum size of each treatment; default=4\\
&MAXTRIALS&build this many treatments before pausing to check if anything
new has been found; default=100\\
&MAXFUTILE&stop after this number of pauses
if nothing new found; default=5\\\cline{2-3}
outputs:&\multicolumn{2}{p{2.9in}|}{array of constraints (each constraint is a conjunction
of variable assignments)}\\\cline{2-3}
\end{tabular}}
\begin{center}
\begin{myalg}
\input{tim/tar3code}
\end{myalg}
\end{center}
\caption{TAR3}\label{fig:tar3}
\end{figure}
\begin{figure*}
{\scriptsize
\begin{minipage}{.32\linewidth}
\includegraphics[width=2.2in]{model2.pdf}
\end{minipage}\hfill
\begin{minipage}{.12\linewidth}
{\scriptsize
desired completed family size normal\\=[0..2]\\AND\\~\\
industrial Capital Output Ratio\\=[3..5]}
\end{minipage}\hfill
\begin{minipage}{.30\linewidth}
\includegraphics[width=2in]{life.pdf}
\end{minipage}\hfill
\begin{minipage}{.20\linewidth}
\includegraphics[width=1.5in,height=1.3in]{j48tree.pdf}
\end{minipage}\\
\begin{minipage}{.32\linewidth}
~\\\fig{world3}.A: part of the World model.~\\~\\~\\ 
\end{minipage}\hfill
\begin{minipage}{.12\linewidth}
~\\\fig{world3}.B: TAR3's learnt treatments. Contains
two tests.~\\
\end{minipage}\hfill
\begin{minipage}{.30\linewidth}
~\\\fig{world3}.C: World population 1900 to 2100. The unmarked
line
is the baseline from the original simulation
and the line with dots shows a  resimulation
after applying the treatments of \fig{world3}.B.~\\
\end{minipage}\hfill
\begin{minipage}{.20\linewidth}
~\\\fig{world3}.D: A decision tree learnt 
by the J4.8 leaner~\cite{witten99}.
Contains over 200 tests.~\\~\\
\end{minipage}
}\caption{Output from TAR3, using data generated from the Limits to Growth
Model.}\label{fig:world3}
\end{figure*}

After that,
the effect of each assignment (denoted $v=r$),
is determined by comparing the baseline to the weighted sum of
all the classes in  examples consistent with the assignment:

{\footnotesize
\begin{equation}\label{eq:calc}
lift=\sum_{c \in classes}\frac{
 \$c*|d \in D \wedge d.class=c  \wedge (assignment \wedge d) \not\vdash\perp|
}{baseline}
\end{equation}}



The $lift$ of a single assignment is denoted $lift1$.
If $lift$ is more or less than one then
the assignment $v=r$ improves or degrades (respectively) the expected score. For example,
in \fig{eg}, {\em outlook=overcast} occurs more frequently when we playing {\em lots}
of golf and {\em outlook=raining} occurs more frequently when we play {\em none} golf.
Hence, when we compute their {\em lift1} scores in \fig{lifg},
we see that {\em outlook=overcast} has a $lift1$ value larger
than 0 and much larger than 
{\em outlook=rain}.


The TAR3 algorithm returns {\em treatments} (i.e. assignments to the
narrow funnel variables) by selecting assignments nondeterministically from
$liftC$, i.e. the cumulative $lift1$ distribution shown in
\fig{lifg}. The distribution weights the selection process such that
assignments with higher lifts tend to be selected more often. 

After the discretizations and construction of $liftC$, the algorithm
(shown in \fig{tar3}) attempts MAXTRIALS times to find some good
treatments (see line~9 in \fig{tar3}).  Each treatment contains a
nondeterministically selected number of assignments (up to a
user-supplied MAXSIZE value- see line~11).  Each treatment is scored using
\eq{calc} (at line~13).  In order to avoid over-fitting, a treatment is
ignored if it doesn;t select for ENOUGH of the highest scoring class
(see line~14).


After MAXTRIALS attempts, the algorithms selects the N treatments with
highest lifts.  This process is repeated till no new treatments are
found after MAXFUTILE number of repeats (see lines~16,17).


\subsection{TAR3 is Competent}

Hu~\cite{hu02} describes numerous studies with TAR3 and datasets
from the standard UCI data mining data
sets~\cite{Blake+Merz:1998} plus some software engineering domains
In the usual case,
TAR3 generated treatments that greatly changed the distribution of classes
in a data set. See~\cite{hu02} for more details.

Other researchers have found TAR3 to be competent at controlling a simulation.
\fig{world3}.A shows 
part of the Limits to
Growth model of global economy~\cite{mead72}.
This model studies the
effects of the world's exponentially growing population and economy.
The full model contains
 295 variables and over 100 nodes (for space reasons, only a small
portion of that model is shown in \fig{world3}.A).   
MIT faculty studied this model for several years to
find factors that prevented global population
over-shoot and collapse.  TAR3 found the same factors (shown in
\fig{world3}.B) in a 30 minute run. Most of that time was spent
generating the example data from the model- the learning only took
seconds. To check TAR3's conclusions, another simulation was conducted where the inputs were
constrained according to TAR3's recommendation.
The results are shown in \fig{world3}.C)~\cite{gel03a}:
average life
expectancy in the year 2100 increased from 30 to 80 years and appears to be stable from that time onwards.


\begin{figure}[!t]
\begin{center}
\includegraphics[width=3in]{tree.pdf}
\end{center}
\caption{A decision tree learnt by 
J4.8~\cite{witten99} decision tree learner from
the same data set as \protect\fig{tar3tree}.
Classes (right-hand-side),
top-to-bottom, are
 ``high'',
``medhigh'', ``medlow'', and ``low''.
}\label{fig:tree}
\end{figure}

\begin{figure}
\includegraphics[width=2.5in]{tim/housing.pdf}
\caption{Ratio of different housing types seen before and after
applying a TAR3 treatment. Results from same 
data as used in \fig{trree}.}\label{fig:tar3tree}
\end{figure}

\subsection{TAR3 is Simple}

Due to the simplicity of the random search, \fig{tar3} is easy to implement.
For some years now we
have been building data miners. With one exception\footnote{
Our experience is that
Naive Bayes classifiers for discrete attributes are 
simpler to describe and build than TAR3~\cite{witten99}. Very simple
discretization methods allow their extension to numeric attributes~\cite{dou95}.
However, such classifiers
don't offer succinct generalizations of a data set so we prefer TAR3.},
TAR3 is the simplest data miner we have every
built. 
Before implementation, we had thought we would need to tune various aspects of the
algorithm after extensive experimentation. For example,
TAR3's discretizaion policy (see line 1 of \fig{tar3})
seemed overly-simplistic and we expected that it would have
to be replaced (perhaps  
with a state-of-the-art entrophy-based supervised discretization policy~\cite{dou95}). 
Howevere, TAR3 proved to be so competent that we were never motivated to
revisit its design.

TAR3 is not only simple to build, but it learns very simple theories.
Standard data miners are not funnel-aware and
can build uncessarily
large theories using less-influencial variables.  
On the other hand,
a learner which
that
assumes narrow funnels can generate far smaller theories than other
approaches. For example, 
when the Limits to Growth simulation
data was given to a standard decision tree learner,
the result was a decision tree with hundreds of tests (see \fig{world3}.D).
Such large trees are harder to understand than 
the small treatment found by TAR3 (e.g. \fig{world3}.B).

The Limits to Growth model is not the only dataset where TAR3's
nondetetrministic search yielded a more concise summary of a domain
than traditional approaches.  In Hu's work with dozens of examples from
the standard UCI data mining data sets~\cite{Blake+Merz:1998},
treatments of MAXSIZE$\le4$ were sufficient to effect major changes in
the distributions of classes~\cite{hu02}.  For example, \fig{tree} and
\fig{tar3tree} compares what a decision tree learner and a treatment
learner can learn from the same data set.  The data set in those
figures comes from Boston housing information.  It contains 506
examples of houses with approximately the same number of ``high'',
``medhigh'', ``medlow'', and ``low'' houses (the symbol denotes their
median value in \$1000's).  A decision tree, learnt via standard
methods, needs hundreds of tests in order to distinguish these classes
(see \fig{tree}).  However, a little meta-knowledge about class
preferences and some nondeterministic search yields a much smaller
result.  After TAR3 is told that houses score a value, highest to
lowest, ``high'', ``medhi'', ``medlow'', ``low'' (respectively), it
learnt the treatment:

\[12.6 \le ptratio < 16 \wedge 6.7 \le rooms < 9.78\]

\fig{tar3tree} shows that this simple output is a powerful
predictor for ``high'' quality houses. This treatment selects a subset
of the houses with 97\% ``high'' quality houses (and this treatment is
also seen in all sub-samples of a 10-way cross validation).


\subsection{TAR3 is Fast and Scalable}

TAR3 has been carefully benchmarked against TAR2, a deterministic
version of the sames algorithm~\cite{hu02}. TAR2 first prunes all
assignments with a $left1$ less than user-specified ``promising'' value.
Next, all the combinations of size MAXSIZE of the remaining assignments are
explored~\cite{me03c}.  In a result consistent with narrow funnels,
TAR3's partial nondeterministic search found nearly the same
treatments (identical in all cases but one) as TAR2's complete
deterministic search.

Other benchmarks
show that TAR3 is faster than TAR2, particularly on larger data sets.
Further, TAR2's runtimes increase exponentially on MAXSIZE,
while
 TAR3's runtimes increase linearly on number
of examples $|$D$|$ and number of variables $|$V$|$~\cite{hu02}.


\subsection{TAR3 is Stable}

One concern with a nondeterministic search is that it can generate
different solutions every time it runs. Paradocially, the reverse if
often true: the behaviour of a
nondeterministic algorithm can actually be {\em more stable} than a
deterministic algorithm.

It is is easy to see why this might be so.  In order to determine a
boundary on a deterministic algorithm, it is standard procedure to
construct inputs for which the algorithm runs poorly.  A
nondeterminisitc algorithm algorithms can be viewed as a {\em
probability distribution on a set of deterministics algorithms}.
Motwani and Raghavan~\cite{motwani95} argue that a nondeterministic
methods are {\em less susceptible to problem variations} than
deterministic methods.  While it may be possible to construct an input
that foils one (or a small fraction) of the available deterministic
algorithms, it is difficult to find inputs that detect a randomly
chosen algorithm.

Certain data mining algorithms are unstable; i.e. minor variations in
the order of the input examples can significantly effect the generated
theory.  Many data mining algorithms depend on this
instability. Proponents of bagging and
boosting~\cite{quinlan96,witten99} repeatedly sub-sample the available
data to generate ensembles of theories. The ensemble is then polled to
reach a consensus opinion.

TAR3, in constrast, only returns stable treatments.  The tool reports
only the treatments found in the majority of a
10-way cross-validation; i.e. are stable across multiple random sub-samples
of a dataset. 
One reason for this stability might be the
Motwani and Raghavan explanation offered above: TAR3's random search
is less suceptible to variations in the input data.  Another possibility
is that TAR3 does not generate very detailed summaries of the input
data. Recall from the above that TAR3 generally returns treatments with less than
MAXSIZE$\le4$ tests while a decision tree learner might return a tree
with hundreds of tests (recall \fig{tree}).  Hence, minor details that
vary across sub-samples 
could change the output
of a decision tree learner while
being ignored by TAR3.


\subsection{TAR3 and Checking for Unsafe Nondeterminism}

Our thesis is that deterministic analysis
is more safe than a nondeterministic one
if a nondeterministic random sampling
yields as much information as a complete deterministic
search. In some systems, making choices
at random,
will survey as mmuch of the system 
as a complete search.
Those systems are the ones with
narrow funnels since they contain
only a few key choice points (the assignments
to the funnel variables).

TAR3 is designed to failure if a small number of
outstandingly influencial variables do not reveal themselves to a
nondeterministic search.  
The only way the nondeterministic search of \fig{tar3}
will work is if a few variable settings are highly
correlated with different states of the system.


In practice, TAR3 has worked very well on all
our test domains suggesting that narrow funnels are not uncommon. 
Nevertheless, if TAR3 {\em fails} to find
influencial variables that would be an indicator that nondeterminism
is inappropriate for the current domain,

