
%\Section{Learners}
\Section{Data Analysis Tools \& Methods}
\SubSection{\TAR}

This section offers our standard introduction to the \TAR treatment learner~\cite{me03c}. \TAR uses the 
\BORE classifier
to discretize the dependent variable(s).
\BORE, short for
{\em \underline{b}est} \underline{o}r {\em \underline{re}st}, converts multi-dimensional
data into a binary class problem. \TAR then finds the minimal difference between the best
and rest instances. 

\subsubsection{Multi-Dimensional Optimization using ``\BORE''}

\BORE inputs instances scored on multiple utilities and classifies 
each of them ``best'' or ``rest''.
\BORE maps the instances
outputs into a hypercube, which has  one dimension for each utility.

\BORE normalizes instances scored on $N$ dimensions into
``zero'' for ``worst'', and ``one'' for ``best''.  The corner
of the hypercube at 1,1,... is the {\em apex} of the cube and represents
the desired goal for the system.
All the examples are scored by their
normalized
Euclidean distance to the apex. 

For this study, outputs were scored on one dimension- distance to the desired
target.
Future studies will exploit more of \BORE's facilities and will score output
on other dimensions such as  average
standard deviation on attitude control;
%pitch, yaw, and roll;
minimum use of propellant; minimal maximum G-force, etc.


For each run $i$ of the simulator, the $n$ outputs are normalized to the range $0..1$ as follows:
\[\begin{array}{rcl}
N_i & = & \frac{X_i - min(X)}{max(X) - min(X)}
\end{array}
\]
The Euclidean distance of $\{N_1,N_2, ...\}$ to the ideal position of $\{N_1=1, N_2=2,...\}$
is then computed and normalized to the range $0..1$ as follows:

\[W_i= 1 - \frac{\sqrt{N_1^2 + N_2^2 + ...}}{\sqrt{n}}\]

\noindent
$W_i$ has the following properties:
\bi
\item $0 \le W_i \le 1$.
\item
The {\em higher} $W_i$, the {\em better} the run. 
\item 
That is, improving $W_i$ can only be achieved by  increasing
{\em all} of the utilities.
\ei

To determine the ``best'' and ``rest'' values,
all the $W_i$ scores were sorted.  The top BEST\% are then classified as 
``best'' and the remainder as ``rest'' for a given value of BEST. 

\begin{figure}[!t]
 {\em
\begin{center}
\begin{tabular}{rcccl}
outlook & temp($^o$F) &  humidity & windy? & class
\\\hline
sunny&  85&     86&     false&  none\\
sunny&     80&     90&     true&   none\\
sunny&     72&     95&     false&  none\\
rain&  65&     70&     true&         none\\
rain&        71&     96&     true&   none\\\hline
      rain&         70&     96&     false&      some\\
      rain&      68&     80&     false&      some\\
      rain&      75&     80&     false&  some\\\hline
      sunny&    69&     70&     false&  lots \\
      sunny&    75&     70&     true&   lots\\
      overcast&  83&     88&     false&  lots\\
      overcast&  64&     65&     true&   lots\\
      overcast&  72&     90&     true&   lots\\
     overcast&  81&     75&     false&  lots\\\hline
\end{tabular}\end{center}}
\caption{\TAR: Playing golf.}\label{fig:golfdata}
\end{figure}



\begin{figure*}
\begin{center}
{\footnotesize
\begin{tabular}{l|p{2in}|l@{~}p{1.5in}|l@{~}p{1.8in}}
input:
 &{\footnotesize
\begin{alltt}
SELECT class
FROM golf
\end{alltt}} &&
{\footnotesize
\begin{alltt}
SELECT class
FROM golf
WHERE
outlook = 'overcast'
\end{alltt}} &&
{\footnotesize
\begin{alltt}
SELECT class
FROM golf
WHERE
humidity >= 90
\end{alltt}}\\\hline
%&&&\\
output: &{\footnotesize
\begin{alltt}
none none none none none 
some some some lots lots 
lots lots lots lots
\end{alltt}}&&
{\footnotesize
\begin{alltt}
lots lots lots lots\end{alltt}} && {\footnotesize
\begin{alltt}
none none none some lots
\end{alltt}}\\\hline
&&&&&\\
distributions:&~~~~~~\begin{barenv} \setstyle{\sffamily} \setwidth{8}
     \setstretch{5}
  \setyaxis{0}{6}{2}
\sethspace{1} \setnumberpos{down} \bar{5}{1}
 \bar{3}{4}
 \bar{6}{8}
\end{barenv}&&~~~~~~
\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
 \setstretch{5}
  \setyaxis{0}{6}{2}
\sethspace{1} \setnumberpos{down} \bar{0}{1} \bar{0}{4} \bar{4}{8}
\end{barenv}&&~~~~~~
\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
 \setstretch{5}
  \setyaxis{0}{6}{2}
\sethspace{1} \setnumberpos{down} \bar{3}{1} \bar{1}{4} \bar{1}{8}
\end{barenv}~\\\\
\end{tabular}}

legend: \protect\legend1{none} \protect\legend4{some}
\protect\legend8{lots}

\end{center}

%~\\

 \caption[\TAR:
Class distributions]{\TAR: Class distributions selected by different conditions in \protect\fig{golfdata}.  }
\label{fig:golft}
\end{figure*}

\subsubsection{Treatment Learning with \TAR}


Once the above models run, and \BORE classifies the output into $best$
and $rest$, a data miner is used to find input settings that select
for the better outputs. This study uses the \TAR data miner since this
learning method returns the {\em smallest} theories that {\em most}
effect the output. In terms of software process changes, such
minimal  theories are useful since they require the fewest
management actions to improve a project.


\TAR
inputs a set of training examples 
$E$. Each example maps a set of attribute
ranges  to some class symbol; i.e.,  $\{R_i,R_j,\ldots \rightarrow C\}$.
The class symbols $C_1, C_2..$ are stamped with some 
 utility score that ranks the classes; i.e., $\{U_1 < U_2 < \ldots < U_C\}$.
With $E$, these classes occur at frequencies
$F_1\%,F_2\%, \ldots, F_C\%$.
A ``treatment'' 
$T$ of size $X$ is a conjunction of attribute ranges  $\{R_1 \wedge R_ 2 \ldots \wedge R_X\}$.
Some subset of $e \subseteq E$ is consistent with the treatment.
In that subset, the classes occur at  frequencies
$f_1\%,f_2\%, ... f_C\%$.
\TAR seeks the
smallest $T$ which induces the most changes 
in the weighted sum of the utilities times frequencies
of the classes. Formally, this is called the {\em lift\/} of a treatment:
\[\mbox{\em lift}=\frac{\sum_C U_Cf_C}{\sum_C U_CF_C}\]


For example, consider the log of golf
playing behavior seen in \fig{golfdata}. In that log, we only play
{\em lots} of golf in $\frac{6}{5+3+6}= 43\%$ of cases. To improve
our game, we might search for conditions that increases our
golfing frequency. Two such conditions are shown in the {\tt
WHERE} test of the select statements  in \fig{golft}. In the case
of {\tt outlook= overcast}, we play {\em lots} of golf all the
time. In the case of {\tt humidity $\le$ 90}, we only play {\em
lots} of golf in 20\% of cases.  So one way to play lots of golf
would be to select a vacation location where it was always
overcast. While on holidays, one thing to watch for is the
humidity: if it rises over 90\%, then our frequent golf games are
threatened.


The tests in the {\tt WHERE} clause of the select statements in
\fig{golft} is a treatment. Classes in treatment learning
get a score $U_C$
and the learner uses this to assess the class
frequencies resulting from {\em applying a treatment} (i.e., using
them in a {\tt WHERE} clause). In normal operation, a treatment learner
does {\em
controller learning} that finds a treatment, which selects for
better classes and reject worse classes  By reversing the scoring
function, treatment learning can also select for the worse classes
and reject the better classes. This mode is called {\em monitor
learning} since it finds the thing we should most watch for. In
the golf example, {\em outlook = 'overcast'} was the controller
and $humidity \ge 90$ was the monitor.

Formally, treatment learning is a weighted-class minimal
contrast-set association rule learner.  The treatments are associations that occur
with preferred classes. These treatments serve to contrast undesirable situations with
desirable situation where more of the outcomes are favorable. Treatment learning
is different to other contrast set learners like
STUCCO~\cite{bay99} since those other learners don't focus on minimal theories.

Conceptually, a treatment learner explores all possible subsets of the attribute
ranges looking for good treatments. Such a search is infeasible
in practice so the art of treatment learning is quickly pruning unpromising attribute
ranges. This study uses the
\TAR treatment learner~\cite{ying02} that uses  stochastic search
to find its treatments. 

\subsubsection{\TAR: Results}
When applied to  our spacecraft re-entry simulator, \BORE/\TAR
worked as follows. Firstly, \BORE generated a {\em baseline}
distribution where the simulation output was divided into two
categories: 25\% were $best$ (closest
to the target region) while the others were $rest$ (the remaining
75\% of the examples).

{\scriptsize \begin{verbatim}
 Worth=1.000000

   rest :~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  [751 - 75%] 
   best :~~~~~~~~~                       [249 - 25%] 
\end{verbatim}}
For comparison purposes with the sequel,
we  declared that the weighted sum of $249*2+751+1$ was defined to be a $worth$ of one.

\TAR then sought the minimal delta between $best$ and $rest$. Several candidate
deltas were generated and scored according to their $worth$, i.e., the
weighted sum of their class frequencies divided by the baseline $worth$ of
$249*2+751*1$.
The top three deltas are shown below:
 
{\scriptsize \begin{verbatim}
 Worth=1.459501
 Treatment:   0.00 <= c < 0.34 and 
                0.68 <= f < 1.00
 Effect:
   rest :~~~~~~                          [17 - 18%] 
   best :~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  [79 - 82%] 
\end{verbatim}}

{\scriptsize \begin{verbatim}
 Worth=1.430270
 Treatment:   0.67 <= c < 1.00 and
              0.00 <= f < 0.34
 Effect:
    rest :~~~~~~~~                        [22 - 21%] 
    best :~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  [81 - 79%] 
\end{verbatim}}

{\scriptsize \begin{verbatim}
 Worth=1.152646
 Treatment:    0.85 <= s < 0.98
               0.67 <= f < 1.00
  Effect:
    rest :~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  [65 - 56%] 
    best :~~~~~~~~~~~~~~~~~~~~~~~         [51 - 44%] 
\end{verbatim}}

Note that:
\bi
\item
 The deltas with the highest worth have the greatest percentage
of $best$ examples. 
\item
The  top two treatments have very similar worths, and the third much less
so. 
\item
The top two treatments comment on  different extremes of the variables $c,f$.
\item
Only very few of the 24 variables in the simulation appear in the treatments.
\ei

Of these effects, the last is most important. \TAR is a focus tool
that tells an analysts ``of all the things you $might$ think about,
these few variables are all you $should$ be considering''.

%\AB was then applied to discover more about the variables selected by \TAR.

