%This section will describe some of the more common
%techniques in the field of machine learning.
%First we will introduce the reader to some
%basic terminology that researchers in
%the field of machine learning use.
%{\it say something about the subfield of data mining, 
%or just stick to the nomeculture of machine learning?}
Since ITL utilizes a machine learning technique, a treatment learner,
this section will introduce the field of machine learning.
First some basic terminology used in the field
will be defined, as well as some common 
characteristics used to describe different learners (\tion{MLintro}).
Then two popular techniques will be discussed (\tion{treeLearning} 
and \tion{naiveBayes}).
These two techniques are described to highlight the differences
between the form and usability of their theories
and the form and usability of treatment learners.
Before treatment learners (\tion{tar3Details})
are discussed, we discuss contrast set learners (\tion{contrastSet})
since treatment learners are a type of contrast set learner.

\subsection{Introduction and Terminology}\label{sect:MLintro}
Machine learning deals with algorithmic processes
that attempt to generalize knowledge learned
form past examples to future, unseen, examples.
The past examples are often called instances,
records, or input data.
Each record has a number of {\it attributes}.
These attributes entirely describe the record,
\ie all information presented to the learner
is in the form of attributes.
Attributes can be {\it continuous}, \eg the real numbers 0 to 10, or 
{\it discrete}.
Discrete attributes can be {\it ordinal}, \eg the integers 1-10 or 
{\it categorical}, \eg the primary colors.
For many problems there is a special
attribute which labels its type.
This attribute is called the {\it class} or
the {\it target class}.
Not all problems have a target class.
The target class can also be real, ordinal
or categorical.
Learners take the input records provided
and build a {\it theory} that describes
what they learned.
The learner is said to {\it train} on the input 
data to produce a theory.
When trying to predict continuous classes 
the theory may be an equation, 
or a decision tree or probability table when
trying to predict discrete classes.
Other types of theories are possible.


Learners are often classified by what type
of inputs they can use and what type of outputs
their theories can predict for.
Some learners, \eg a \naive Bayes learner, (see \tion{naiveBayes})
only work with discrete input data and can only
predict for a discrete target class.
Any learner can be adapted to handle continuous data 
by discretizing the data in a pre-processing step.
The performance characteristics of 
different discretization methods are
an active area of research \cite{YanWeb02Comparative,dou95,me05b}
but a detailed description of these methods
is beyond the scope of this review.
Discretization is most commonly used on the independent
attributes, but can be applied to the dependent attributes as well.
Our extreme sampling discretizer, described in \tion{xsampling},
is one that works on the dependent attributes.

Another way to describe machine learners is whether
they are performance or explanatory systems.
Performance learners only attempt to maximize their 
predictive performance according to some criterion, 
such as accuracy or precision.
Explanatory learners also attempt to maximize 
their predictive performance,
but their theories are in a form that can offer insight to human users.
\Naive Bayes (\tion{naiveBayes}) are an example of
performance learners,
while decision trees (\tion{treeLearning}) are
an example of explanatory learners.
Treatment learners (\tion{tar3Details}) are also
explanatory learners.


\subsection{Decision Tree Learning}\label{sect:treeLearning}
Decision tree learning uses the common divide-and-conquer approach.
The ID3 decision tree learner \cite{quinlan86} is the most
common, although other tree learners include
M5 \cite{quinlan92b} and CART \cite{breiman84}.
The modern incarnations of ID3 are C4.5 
\cite{quinlan92}
and J4.8\footnote{Part of the weka project, downloadable at
\url{http://www.cs.waikato.ac.nz/ml/weka/}}.
A decision tree's leaves are classification labels
and its internal nodes are attribute-value tests.
The pseudocode in \fig{decisionTrees} describes
how to classified a new instance using a decision 
already generated.

\begin{figure}[bh]
\begin{algorithmic}[7]
\STATE start at root node
\REPEAT 
\STATE follow branch that matches the instance being classified
\UNTIL current node is a classification node
\STATE return classification in leaf node
\end{algorithmic}
\caption{Pseudocode for classifying new instances with a decision tree}
\label{fig:decisionTrees}
\end{figure}

%To classify a new instance, 
%test the instance against the test at
%the root note.
%This test will point down one of the branches.
%If the branch leads to a leaf, then the leaf
%indicates which class this instances belongs to.
%If the branch leads to another internal node,
%test the instance against the test in the node
%and follow the appropriate branch.
%Continue in this fashion until a leaf node is reached
%and the instance is classified.

\clearpage

See \fig{decisionTree} for an example of what a decision tree
might look like after training on the ubiquitous golf data set.
Note that the classification at the root nodes
does not misclassify any of the training examples.
This, of course, is not the typical performance of
machine learning algorithms.

\begin{figure}
\centering
\includegraphics[height=3.0in]{Figures/Decision_tree_model}
\caption{Example decision tree}\label{fig:decisionTree}
\end{figure}

To train a decision tree an ordering heuristic is needed
to decide which attribute to use when constructing an internal node.  
ID3 uses  information gain \cite{quinlan92}, which is an entropy based
metric.  Starting at the root node and continuing until either 
there are no attributes remaining or the instances at the current
location in the tree all belong to the same class,
the attribute that would most reduce the information in the resulting
tree is selected.
%The problem of over-fitting is often addressed by post-pruning using a 
%a data set not trained on for this purpose.

\begin{figure}
\begin{footnotesize}
\begin{verbatim}
stat <= 11.66 
| rm <= 6.54 
| | lstat <= 7.56 THEN medhigh 
| | lstat > 7.56 
| | | dis <= 3.9454 
| | | | ptratio <= 17.6 THEN medhigh 
| | | | ptratio > 17.6 
| | | | | age <= 67.6 THEN medhigh 
| | | | | age > 67.6 THEN medlow 
| | | dis > 3.9454 THEN medlow 
| rm > 6.54 
| | rm <= 7.061 
| | | lstat <= 5.39 THEN high 
| | | lstat > 5.39 
| | | | nox <= 0.435 THEN medhigh 
| | | | nox > 0.435 
| | | | | ptratio <= 18.4 THEN high 
| | | | | ptratio > 18.4 THEN medhigh 
| | rm > 7.061 THEN high 
lstat > 11.66 
| lstat <= 16.21 
| | b <= 378.95 
| | | lstat <= 14.27 THEN medlow 
| | | lstat > 14.27 THEN low 
| | b > 378.95 THEN medlow 
| lstat > 16.21 
| | nox <= 0.585 
| | | ptratio <= 20.9 
| | | | b <= 392.92 THEN low 
| | | | b > 392.92 THEN medlow 
| | | ptratio > 20.9 THEN low 
| | nox > 0.585 THEN low 
\end{verbatim}
\end{footnotesize}
\caption{Decision tree generated by J4.8 training on the Boston housing data}
\label{fig:housingJ48}
\end{figure}

The Boston housing data \cite{Blake+Merz:1998} is a frequently
used data set that describes the median value of homes
in 506 suburbs of Boston.
There are 12 continuous attributes, 1 boolean attribute,
and the target class.
\fig{housingJ48} shows a typical decision tree learned on this
data by J4.8, where {\tt \{stat, rm, lstat, dis, ptratio, nox, b\}} 
are independent variables\footnote{Where 
{\tt rm} is the average number of rooms,
{\tt ptratio} is the pupil-teacher ratio, and
{\tt nox} is the nitrogen oxide concentration, to define a few.}
and {\tt \{low, medlow, medhigh, high\}} are the target labels.
Compare the complexity of this tree to the simple treatment 
shown in \fig{housingTar}.
Also note that \fig{housingJ48} is a classifier,
which can be used to predict the class of any new instance,
whereas \fig{housingTar} is a contrast rule that
describes the biggest difference between the higher value
target classes and the lower value target classes.



\subsection{\Naive Bayes}\label{sect:naiveBayes}
Bayes theorem \cite{bayes1764} is used to calculate the
probability that a hypothesis is correct, given a set
of evidence.
It can be written as
\begin{equation*}\label{eq:bayes}
P(H|E) = \frac{P(E|H) * P(H)}{P(E)}
\end{equation*}
where $P(H|E)$ is the probability of the hypothesis given the evidence,
$P(E|H)$ is the probability of the evidence given the hypothesis,
$P(H)$ is the   probability of the hypothesis, and
$P(E)$ is the   probability of the evidence.

The difficulty in using Bayes theorem is calculating the
$P(E|H)$ term.  The theorem suggests we most observe
every possible combination of the different pieces of evidence.

Because of this difficulty, in machine learning a weaker form of 
Bayes theorem is often used called {\it \Naive Bayes}.  
\Naive Bayes assumes that the probabilities
of the different attributes are independent of one another.
This allows the $P(E|H)$ term to be calculated multiplicatively as
\begin{equation*}\label{eq:naivebayes}
P(E|H) = \prod^{n} P(E_i|H) 
\end{equation*}
where the $P(E_i|H)$ terms are the probabilities of a single
piece of evidence given $H$ and $n$ is the number of attributes
available.

To train a \naive Bayes learner, frequency tables are used
to count the number of instances with each attribute value
in each of the target classes.
The attributes and the target class must be
discrete to keep the number of tables and the number of
rows in the tables finite.
For example, if a \naive Bayes learner was trained on the 
data in \fig{rawTable}, the frequency tables might look like
\fig{freqTable}.

\begin{figure}
\begin{center}
\begin{footnotesize}
\( %F~=~\left\{
~\begin{tabular}{lr@{~:~}l@{}|lr@{~:~}l|lr@{~:~}l||r@{~:~}l}
\multicolumn{9}{c}{attributes}& \multicolumn{2}{c}{class}\\\hline
\multicolumn{1}{c}{Make}& coupe& SUV     &  Size  &coupe&SUV  &Hifi & coupe&SUV & coupe&SUV\\\hline
Mitsubishi& 1& 1   & Small  &  6&$0^*$   &   yes &6&$0^*$   &    8& 4\\
Toyota    & 2& 1   & Medium &  1&1          &   no &2&4&\multicolumn{2}{l}{}\\
Benz      & 1& 1   & Large   & 1&3&\multicolumn{3}{l||}{}&\multicolumn{2}{l}{}\\
BMW       & 2&0$^*$&\multicolumn{3}{l|}{}&\multicolumn{3}{l||}{}&\multicolumn{2}{l}{}\\
Ford      & 1& 1&\multicolumn{3}{l|}{}&\multicolumn{3}{l||}{}&\multicolumn{2}{l}{}\\
Honda     & 1&0$^*$&\multicolumn{3}{l|}{}&\multicolumn{3}{l||}{}&\multicolumn{2}{l}{}\\
\end{tabular}
%\right\} 
\)
\end{footnotesize}
\end{center}
\caption[\Naive Bayes training data]
{Training data.  Cells indicated with a $*$ have a zero cell.
In the frequency table all cells will have one added to their counts to avoid calculating any zero likelihoods.}
\label{fig:rawTable}
\end{figure}


\begin{figure}
\begin{center}
\begin{footnotesize}
\renewcommand{\arraystretch}{1.2}
\(%P(E_i|H_j)~=~\left\{~
\begin{tabular}{l@{~}r@{~:~}l@{}|l@{}r@{~:~}@{~}l|@{}lr@{~:~}l@{~}r@{~:~}l}
\multicolumn{9}{c}{attributes}& \multicolumn{2}{c}{class}\\\hline
\multicolumn{1}{c}{Make}& coupe& SUV     &  Size  &coupe&SUV   &~Hifi & coupe&SUV & \multicolumn{1}{||c}{coupe}&SUV\\\hline
Mitsubishi& $\frac{2}{9}$& $\frac{2}{5}$   & Small  &  $\frac{7}{9}$&$\frac{1}{5}$&~yes &$\frac{7}{9}$&$\frac{1}{5}$  &
\multicolumn{1}{||c}{$\frac{9}{14}$}& $\frac{5}{14}$\\
Toyota    & $\frac{3}{9}$& $\frac{2}{5}$   & Medium &  $\frac{2}{9}$&$\frac{2}{5}$     &  ~no &$\frac{3}{9}$&$\frac{5}{5}$&\multicolumn{2}{||l}{}\\
Benz      & $\frac{2}{9}$&$\frac{1}{5}$   & Large   & $\frac{2}{9}$&$\frac{4}{5}$&\multicolumn{3}{l|}{}&\multicolumn{2}{||l}{}\\
BMW       & $\frac{3}{9}$&$\frac{1}{5}$&\multicolumn{3}{l|}{}&\multicolumn{3}{l|}{}&\multicolumn{2}{||l}{}\\
Ford      & $\frac{2}{9}$&$\frac{2}{5}$&\multicolumn{3}{l|}{}&\multicolumn{3}{l|}{}&\multicolumn{2}{||l}{}\\
Honda     & $\frac{2}{9}$&$\frac{1}{5}$&\multicolumn{3}{l|}{}&\multicolumn{3}{l|}{}&\multicolumn{2}{||l}{}\\
\end{tabular}
%\right\} 
\)
\renewcommand{\arraystretch}{1}
\end{footnotesize}
\end{center}
\caption{Frequency table, $P(E_i|H_j)$}
\label{fig:freqTable}
\end{figure}

To classify a new example, \naive Bayes calculates the
likelihood of the example belonging to each target class, $L(H_i)$.
The likelihood is the similar to the probability, but
is not normalized by the $P(E)$ term.
The likelihood can be used because \naive Bayes compares
two probabilities, making the $P(E)$ terms cancel out.
The likelihood is calculated by
\begin{equation}\label{eq:likelyhood}
L(H_i) = P(E|H_i) * P(H_i)
\end{equation}
The example is classified as whichever class has the highest
likelihood.
For example, if a new instance was a medium sized Ford,
the likelihood of it being an SUV would be
\begin{eqnarray*}
L(SUV) &=& P(size = medium | SUV) * P(Make = Ford | SUV) * P(SUV) \\
       &=& \frac{2}{5} * \frac{2}{5} * \frac{5}{14} \\
       &=& 0.057
\end{eqnarray*}
while the likelihood of it being a coupe would be
\begin{eqnarray*}
L(coupe) &=& P(size = medium | coupe) * P(Make = Ford | coupe) * P(coupe) \\
       &=& \frac{2}{9} * \frac{2}{9} * \frac{9}{14} \\
       &=& 0.032
\end{eqnarray*}
For this instance, since $L(SUV) > L(coupe)$, the
\naive Bayes classifier would assign this instance to
SUV target class.



\subsection{Contrast Set Learning}\label{sect:contrastSet}
Contrast set learners are a type of association rule learners 
that find the greatest difference between the target classes.
Since treatment learning is an example of a contrast set learner,
we will discuss some research done with contrast set
learners other than treatment learners.

\paragraph{STUCCO}
STUCCO (Search and Testing for Understandable Consistent Contrasts) 
\cite{bay99} uses the algorithm in \fig{stucco} to
learn contrasting sets.

\begin{figure}
\begin{algorithmic}[5]
\STATE initialize set of candidates, $C$, to the empty set 
\STATE initialize set of deviations, $D$, to the empty set 
\STATE initialize set of pruned candidates, $P$, to the empty set 
\STATE let ${\tt prune(c)}$ return true if c should be pruned
\REPEAT 
\STATE scan data and count support $\forall c \in {\it C}$
\FORALL{$c \in C$}
\IF{ ${\tt significant(c)} \wedge {\tt large(c)}$}
\STATE $D \leftarrow D \cup c$
\ENDIF
\IF{ {\tt prune(c)} is true}
\STATE $P \leftarrow P \cup c$ 
\ELSE
\STATE $C_{new} \leftarrow C_{new} \cup {\tt GenChildren(c,P)}$
\ENDIF
\ENDFOR
\STATE $C \leftarrow C_{new}$
\UNTIL{ {\it C} is empty}
\STATE return ${\tt Surprising(D)}$
\end{algorithmic}
\caption{STUCCO algorithm}\label{fig:stucco}
\end{figure}

This algorithm builds trees (line 14) using a canonical ordering
to avoid visiting the same node twice.
The tree nodes consist of different possible attribute-value
pairs, so that a path from the root to a leaf
consists of several non-exclusive attribute-value pairs.
The {\tt prune} function (line 11) has three criteria, any one
of which causes the function to return true:
\be
{minimum deviation size}
{expected cell frequencies}
\item $\chi^2$ bounds
\ee
These rules together make it possible to do a complete search
of the remaining branches.
The functions {\tt significant} and {\tt large} ensure
that the proposed contrast set is both statistically significant,
based on the $\chi^2$ test, and large,
above a user specified threshold.
Finally, the {\tt Surprising} function ensures that
the proposed contrast set is not just the result 
of multiplicative probabilities.
For example if $P(color=red~|~shape=square) = .76$
and $P(hollow=yes~|~shape=square) = .45$, it would
not be interesting if
$P(hollow=yes \wedge color=red~ |~ shape=square) = .32$
since that probability is so close to probability 
we would expect if the attributes were independent, \ie $.76 * .45 = .34$.
This is only the basic idea behind the {\tt Surprising} function;
a more robust method based on 
{\it iterative proportional fitting}\cite{everitt77}
was actually used in STUCCO.

Using the STUCCO learner to investigated
Adult Census data \cite{Blake+Merz:1998} to answer the
question ``What are the differences between people
with Ph.\ D and Bachelor degrees?''
Bay and Pazzani \cite{bay99} found 164 rules, while
Apriori returned over 75,000 rules.
For example the two rules in \ble{stuccoRules}
were returned by STUCCO.

\begin{table}
\centering
\begin{tabular}{lcc}
& \multicolumn{2}{c}{\% holding} \\
contrast set & Ph.\ D  & Bachelor \\
\hline
workclass = State-gov & 21.0 & 5.4 \\
occupation = sales & 2.7 & 15.8 \\
\end{tabular}
\caption{Example rules learner by STUCCO from Adult Census data}
\label{table:stuccoRules}
\end{table}

\paragraph{MINWAL}
The MINWAL learners \cite{cai98}, MINWAL(O) and MINWAL(W),
extend the Apriori Gen Algorithm \cite{agrawal94}.
They are called weighted class learners, because they
allow the instances to have an extra attribute, weight, 
that records how significant the instance is.
The example used in \cite{cai98} has to do with 
analysis of supermarket checkout baskets.
If a rule learner like Apriori Gen finds the following two rules
\begin{itemize} \itemsep -14pt
\item Buys(baby food) $\Rightarrow$ Buys(diapers)
\item Buys(baby food) $\Rightarrow$ Buys(beer)
\end{itemize}
but the profit margin on beer is much higher than on
diapers, the second rule is more useful to a business user.

Webb \etal \cite{webb03} did a study comparing STUCCO
with two other rule learners, Magnum Opus, 
a commercially available tool and C4.5rules \cite{quinlan92}, 
which generates rules from a decision tree.
Although these other learners were not designed to
be contrast set learners, the authors
were able to restrict the form of their theories
to allow an almost direct comparison with STUCCO.
The learners were applied to aggregated data from
a large Australian discount department store taken
on two different days.
To their surprise they found a correspondence between
the core contrast-set-discovery task in
the Magnum and STUCCO learners.
They found that the pruning rules of the learners are responsible
for the difference in the theories returned by the two
learners.
These different pruning rules lead
the STUCCO learner to return fewer rules than Magnum.
A manual inspection of these rules found both interesting and 
spurious rules in the list
generated by Magnum, suggesting that the pruning rules
of STUCCO are possibly too strict and that the rules
of Magnum are possibly too lenient.
They did find that C4.5rules missed many of the key contrasts 
that were found by STUCCO and Magnum.

\subsection{Treatment Learners}\label{sect:tar3Details}
%Since treatment learners are a cornerstone of the ITL method,
%they will be discussed in detail here.

The tar family of learners have been developed 
by Menzies et.\ al.
The original Tarzan \cite{me00e} prototype was actually
a post-processor that worked with classification
tree generators (specifically C4.5, discussed in \tion{treeLearning}).
Tarzan constructed a set of decision trees using different 
training data sets that had been generated by applying different restrictions
to the software effort estimation model \cite{cocomoII} being studied.
Tarzan then used a set of pruning rules that
applied to the individual trees, as well as rules
that were applied to the ensemble of decision trees.
These rules vastly reduced the complexity
of the original decision trees.
This prototype was quickly discarded as it
was computationally inefficient.
Tar2 was developed \cite{hu02} to generate
treatments quicker 
by training directly on the instances
instead of constructing decision trees.
Tar3, used in the studies described in \chap{casestudies}, 
was developed to increase the efficiency
of tar2 by using stochastic sampling.
Tar4 \cite{clark06}, used by SPY in the case studies described in
\chap{properties} and \chap{others},
is the next generation treatment learner that
further increases the runtime efficiency of the
learner by using a Bayes style
frequency table to eliminate the need to run over the
data set for each proposed treatment or even store 
the training instances in memory.

The form of the treatments returned by the tar
family of learners is conjunctions of attribute-value pairs.
Each attribute-value pair consists of one
attribute and either a range restriction,
such as $6.7 \leq rooms \leq 9.8$ or a value
assignment, such as $outlook = overcast$.
Hence a treatment has the form
\begin{equation*}
pair_1 \wedge pair_2 \wedge \ldots \wedge pair_n \Rightarrow P(c_1), P(c_2), \ldots, P(c_k)
\label{eqn:rxForm}
\end{equation*}
where, typically, $1 \leq n \leq 5$ and
$P(c_k)$ is the predicted probability of class $c_k$ among
instances that pass the treatment.

The tar learners are a type of contrast set learner,
as discussed in \tion{contrastSet}.
This means they attempt to
find treatments that select for the desired class,
but do not comment on instances that don't pass the treatment.
In receiver operator characteristics,
we would say these types of learners attempt to maximize
the true positive rate of their theories, 
without penalizing theories
that have a high false negative rate.
A treatment should be interpreted as 
a region where desirable classes are more prevalent,
while the region outside the treatment may not have
significantly more instances of the undesirable classes
than the baseline.
In other words, if an unseen instance passes a treatment
returned by a treatment learner 
there is a high likelihood that the
new instance belongs to the desired class.
But if the new instance does not pass the treatment,
the treatment learner does not offer any guidance on what class
that instance belongs to.

\fig{housingTar} shows a typical treatment for the 
Boston housing market data used to build the decision tree
in \fig{housingJ48},
where {\tt \{rm, ptratio\}} 
are independent variables,
{\tt high} is the most desirable target class,
and {\tt medhigh} is the second most desirable target class.
Compare the succinctness of this theory to
the complexity of the decision tree in \fig{housingJ48}.
This is the advantage to using a treatment learner.
Treatments are a compact way to convey the differences
between the higher valued target classes and the lower valued ones.

\begin{figure}
\begin{small}
\begin{verbatim}
IF: rm >= 6.6 AND ptratio <= 15.9 
THEN: 97% of the found houses will be high quality 
      3% of the found houses will be medhigh quality
BASELINE: 29% high, 29% medhigh, 21% medlow, 21% low
\end{verbatim}
\end{small}
\caption{Treatment generated by tar3 on the Boston housing data}
\label{fig:housingTar}
\end{figure}
% support stats
% baseline: 146 high, 147 medhigh, 106 medlow, 106 low
% treated : 37 high, 1 medhigh


We will discuss the details of tar3 and tar4, 
since they are the two treatment learners utilized
by the studies presented in chapters 
4 - 6.

\paragraph{Tar3}
The first step in tar3 is to calculate the {\it baseline}.
The different possible target classes are
assigned {\it weights}.
Experience has shown that these weights should be
exponential.
For example, if there are four classes,
they might be assigned the weights
2, 4, 8, 16.
Of course, this is all done internally in the
treatment learner.  
All the user has to do
is list the possible target classes in 
the preferred order.
The baseline is a normalized weighted sum of
the proportions of the target classes in the training data.
This calculation has the following steps
\begin{enumerate} \itemsep -14pt
\item multiply the proportion of each class in the training set by its weight
\item sum the products from step 1)
\item normalize the sum from step 2) by the sum of the weights
\end{enumerate}
Hence, the baseline can be calculated as
\begin{equation*}
baseline = \frac{\sum_{i=0}^{n}(weight_i * prop_i)}{\sum_{i=0}^{n}weight_i}
\end{equation*}
where $n$ is the number of target classes,
$weight_i$ is the weight assigned to the i\super{th} class,
and $prop_i$ is the proportion of the i\super{th} class
in the training data.

The next step is to calculate the {\it lift\sub{1}}s.
The {\it lift} for any treatment
is the ratio of the normalized weighted sum of the 
instances covered by that treatment to the baseline,
calculated as
\begin{align*}
lift &= \frac{treated~average}{baseline} \\
 &= \frac{\sum_{i=0}^{n}(weight_i * treated_i)}
         {\sum_{i=0}^{n}(weight_i * prop_i)}
\end{align*}
where $treated_i$ is the proportion of the i\super{th}
class among instances that pass the treatment.
The {\it lift\sub{1}}s are the {\it lift}s
of all possible treatments 
with only one attribute-value pair.
The number of attribute-value pairs in a treatment
is often referred to as the treatment's {\it size}.

%{\it After the {\it lift\sub{1}}s are calculated, they are sorted.}
Next {\it lift\sub{1}}s are combined to form treatments of sizes
1 to $max\_size$,which is specified by the user, but
usually 5 works well.
First the size of the treatment is picked randomly,
then different attribute-value pairs are
chosen randomly, biased according to each
attribute-value pair's {\it lift\sub{1}}.
The lift for each proposed treatment is calculated
and after tar3 has run several trials, it
returns the treatments it found ranked by their lift.
This metric might tend to produce very overfitted theories,
as treatments are learned that match only a few instances
in the most desired class.
A minimum best support term is used to counter this potential
cause of over-fitting.

\paragraph{Tar4}
Tar3 still has to run through the data to evaluate each
potential treatment.
This also requires that the instances be stored in memory.  
Tar4 was developed to generate treatments while requiring
only one pass through the data, which also 
means that the training data need not be stored in memory.
During the training stage, tar4 stores the instances
in frequency tables similar to a \naive Bayes classifier.
The major difference between tar4's frequency tables
and those found in a \naive Bayes classifier is that
tar4 uses a two-class system, regardless of how 
many target classes exist in the training set.
For example, if the target class is an integer from
the range $[1,5]$ with $5$ being the best class, 
an instance with a class of $4$
would count as $4/5$ {\it good} and $1/5$ {\it bad}.
The {\it lift\sub{1}}s
are then calculated from these tables.
The final lift of a treatment is calculated by
$P(good) * support(good)$, where $P(good)$ is calculated
in the same fashion as it would in a \naive Bayes
classifier and $support(good)$ is the unnormalized
likelihood from the frequency tables (see \eq{likelyhood}).

For more complete details on tar4 see \cite{clark06}.




%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "../thesis"
%%% End: 
