
%\documentclass[times, 11pt]{article}\renewcommand{\baselinestretch}{1.5}
\documentclass[times, twocolumn,10pt]{article}
\usepackage{times,alltt,url,graphicx,amssymb}
\usepackage{../../tex/bar,../../tex/cite}

%\usepackage{bar}



\newcommand{\ARROW}{{\sffamily $\Rightarrow$}}
\newcommand{\ATTRIBUTE}{{\sffamily $attribute$}}
\newcommand{\BANDS}{{\sffamily $bands$}}
\newcommand{\BASELINE}{{\sffamily $baseline$}}
\newcommand{\BEST}{{\sffamily $best$}}
\newcommand{\CANDIDATES}{{\sffamily $candidates$}}
\newcommand{\CC}{{\sffamily $C$}}
\newcommand{\DEEONE}{{\sffamily $D_1$}}
\newcommand{\DEETWO}{{\sffamily $treated$}}
\newcommand{\DEE}{{\sffamily $D$}}
\newcommand{\DISTRIBUTION}{{\sffamily $result$}}
\newcommand{\EN}{{\sffamily $N$}}
\newcommand{\INPUT}{{\underline {\sffamily input}}}
\newcommand{\ITEMS}{{\sffamily $items$}}
\newcommand{\LHS}{{\sffamily $lhs$}}
\newcommand{\NOE}{$\not= \emptyset$}
\newcommand{\PROMISING}{{\sffamily $promising$}}
\newcommand{\RANGES}{{\sffamily $ranges$}}
\newcommand{\RHS}{{\sffamily $rhs$}}
\newcommand{\RR}{{\sffamily $R$}}
\newcommand{\SKEW}{{\sffamily $skew$}}
\newcommand{\TEMP}{{\sffamily $temp$}}
\newcommand{\TREATED}{{\sffamily $treated$}}

\newcommand{\AND}{{\underline {\sffamily and}}}
\newcommand{\DONE}{{{\sffamily \}}}}
\newcommand{\DO}{{{\sffamily \{}}}
\newcommand{\ELSE}{{\underline {\sffamily else}}}
\newcommand{\FI}{{\underline {\sffamily fi}}}
\newcommand{\FOR}{{\underline {\sffamily for}}}
\newcommand{\GE}{{$\ge$}}
\newcommand{\IF}{{\underline {\sffamily if}}}
\newcommand{\IN}{{\underline {\sffamily in}}}
\newcommand{\IS}{{$\leftarrow$}}
\newcommand{\NIL}{ {\sffamily $\emptyset$}}
\newcommand{\OUTPUT}{{\underline {\sffamily output}}}
\newcommand{\PLUS}{{$\cap$}}
\newcommand{\REPEAT}{{\underline {\sffamily repeat}}}
\newcommand{\RETURN}{{\underline {\sffamily return}}}
\newcommand{\SOME}{{$\subseteq$}}
\newcommand{\THEN}{{\underline {\sffamily then}}}
\newcommand{\TO}{{\underline {\sffamily to}}}
\newcommand{\UNTIL}{{\underline {\sffamily until}}}
\newcommand{\WHEN}{{\underline {\sffamily when}}}
\newcommand{\WHERE}{{\underline {\sffamily where}}}

\newenvironment{smallitem}{
   \setlength{\topsep}{0pt}
   \setlength{\partopsep}{0pt}
   \setlength{\parskip}{0pt}
   \begin{itemize}
   \setlength{\leftmargin}{.2in}
   \setlength{\parsep}{0pt}
   \setlength{\parskip}{0pt}
   \setlength{\itemsep}{0pt}}{\end{itemize}}

   %! some shorthands
   \newcommand{\bi}{\begin{itemize}}
   \newcommand{\ei}{\end{itemize}}

\begin{document}
%! general comment- you wrote the paper you want to write, not
%! the paper that folks attracted to this particular workshop would
%! want to read. most of my changes are just "throw lots of references
%! to requirements engineering" to the front of the paper

%!your title was too long and not linked into this particular venue
\title{Many applications only need two association rules}

%! you did the experimental work and wrote draft one and wrote the
%! fast tar2 that makes this all possible. you be first author!
%
%  thanks! but I just can't write this beautiful paper, it is yours.

\author{Tim Menzies$^{2}$, Ying Hu$^{3}$\\
        University of British Columbia$^4$\\
        {\small \url{tim@menzies.com}, \url{yingh@ece.ubc.ca}}}
%\date{Aug 12,2001}

\newcommand{\bb}{\blacksquare\!\!}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}

\maketitle

% Use \section* instead of \section to suppress numbering for
% the abstract, acknowledgements, and references.

%!there is an abstract envrionment
\begin{abstract}


~\newline {\em KEYWORDS:}  Association rules, treatment learning,
contrast sets, validation.
\end{abstract}

%-------------------------------
% Figure of KC-1 NASA project
%-------------------------------


\section{Introduction}
\footnotetext[0]{Ying- if KDD2002 is like 2001, then this
submission must be 20 pages, 1.5 lines spaced}
\footnotetext[1]{Submitted to the KDD-2002, The Eighth ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining,
July 23 - 26, 2002, Edmonton, Alberta, Canada
\url{http://www.acm.org/sigkdd/kdd2002/}. Wp ref 01/tar2/tar2}
 \footnotetext[2]{
\url{http://tim.menzies.com}, phone (604) 822-3381}
\footnotetext[3]{
\url{http://www.ece.ubc.ca/twiki/bin/view/Softeng/YingHu}.}
 \footnotetext[4]{Department of Electrical \&
Computer Engineering; 2356 Main Mall; Vancouver, B.C. Canada
V6T1Z4.}

%! in journalism, there is a problem of "burying the lead"- i.e. the key idea
%! does not appear till late in the text. much of "editing" is hunting for the
%! "lead" and just moving it to the front.
Machine learners generate summaries of   data sets. It is wise to
change those summaries, according to the audience that will read
them. For example,  a computer program can read and process a
decision tree containing hundreds, thousands, or tens of thousands
of nodes. However,   humans reading the same trees be confused by
the   knowledge overload

Assuming that  the learnt theory is to be read by some agent
seeking a {\em minimal  treatment strategy} for controlling some
system, then certain specialized summarization techniques apply.
In the context of this article, a {\em treatment} is a constraint
which, when applied, can improve the behavior of a system. An
agent seeking  such minimal treatments needs two   rules: \bi
\item
The {\em control rule} contains the
 {\em smallest number} of conjunctions that {\em most improve} the current state of the system.
 \item
 The {\em monitor rule} contains the {\em smallest number}
 of conjunctions to monitor in the system in order to best detect future faulty system behavior.
 \ei
 With these rules in-hand, our agent has a choice. The agent could apply the
 control action to most improve the current situation.
 Alternatively, a lazier agent that is content with the current
 situation might   only watch the monitor conditions to detect
 situation deterioration.

 In both these rules,
 the conjunction size should be small since, often in the real world, manipulating and
 collecting attribute ranges is very expensive. For example, when
 managing teams of software engineers, experience strongly suggests that organizational change can be very
 hard  and collecting
valid measurements is a non-trivial task~\cite{fenton94}.

Note that generating more than one  action rule and one monitoring
rule can be  superfluous. Generating more than one monitoring rule
is not recommended for the same reason that conjunction size
should be small:  data collection in the real world can be very
expensive. Also, at any point in time, agents can perform
conjunctions, not disjunctions of actions (exploring disjunctions
would  only be possible if our agents  are time travellers, and
can backtrack in time to explore alternative actions).

The extraction of the control and monitoring rules {\em
could} be implemented as a post-processor to a standard
machine learning algorithm. For example,
TARZAN~\cite{me00e} was a post-processor to
C4.5~\cite{quinlan92} that swung through the decision trees
generated by 10-way cross-validation. TARZAN returned the
smallest treatments that occurred  in most of the ensemble
that {\em increased} the percentage of branches leading to
some preferred {\em good} classes and decreased the
percentage of branches leading to undesirable {\em bad}
class.

However, a much simpler learner can be built by designing a
machine learner specifically to find a single control rule and a
single monitoring rule. This paper describes such a simpler
learner. The TAR2 treatment learner is a {\em weighted-class
minimal contrast-set association rule learner} that uses {\em
confidence measures} but not {\em support-based pruning} (these
terms are defined below). Validation studies
suggest that the algorithm is effective and is general to many domains.

TAR2 is a surprisingly  simple algorithm and
it's repeated success suggests that many
example sets have a very simple structure. Such simple structures
can be adequately probed with very simple learners.
A similar
conclusion has been reached before
regarding decision tree learners~\cite{holte93}. To our knowledge,
this paper is the first report of a similar conclusion in
the domain of association rule learning.

The rest of this paper is structured as follows XXX.
\begin{figure*}
\begin{center}
\includegraphics[height=5in,width=5in]{tree.eps}
\end{center}

\begin{center}
{\footnotesize
\begin{tabular}{|c|c|c|c|}\cline{2-4}
\multicolumn{1}{c|}{}&baseline & {\tt controller1} & {\tt monitor1}\\\hline
&&&\\
Treatment & nothing & $6.7         \leq RM       < 9.8$   & $0.6          \leq NOX   <  1.9$ \\
                &   & $\wedge 12.6 \leq PTRATION < 15.9 $ & $\wedge 17.16 \leq LSTAT < 39.0$ \\\hline
&&&\\
&&&\\
Results& ~~~~\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
 \setstretch{0.4}\sethspace{0.5} \setyaxis{0}{100}{25}
  \bar{21}{1}
 \bar{21}{2}
 \bar{29}{4}
 \bar{29}{8}
\end{barenv}
&
~\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
 \setstretch{0.4}\sethspace{0.5} \setyaxis{0}{100}{25}
   \bar{0}{1}
 \bar{0}{2}
 \bar{3}{4}
 \bar{97}{8}
\end{barenv}
&
~\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
 \setstretch{0.4}\sethspace{0.5} \setyaxis{0}{100}{25}
   \bar{98}{1}
 \bar{1}{2}
 \bar{1}{4}
 \bar{0}{8}
\end{barenv}\\&&&\\\hline
N &506& 38 & 81\\\hline
\end{tabular}}
\end{center}

\caption{~\newline
ABOVE: C4.5's learnt tree from the HOUSING domain
(described in \fig{houseattr}). Classes (right-hand-side), top-to-bottom, are
 ``high'',
``medhigh'', ``medlow'', and ``low'' which indicate
median value of owner-occupied homes in \$1000's.\newline
BELOW: ``high'',
``medhigh'', ``medlow'', and ``low''= black, hatched, stripped, white
respectively.
}\label{fig:tree}
\end{figure*}






\begin{figure}
{\footnotesize
\begin{tabular}{|r@{~}p{2.4in}|}\hline
attribute:& definition\\\hline
CRIM:      &per capita crime rate by town\\
ZN:      &proportion of residential land zoned for lots over 25,000 sq.ft.\\
INDUS:      &proportion of non-retail business acres per town\\
CHAS:      &Charles River dummy variable (= 1 if tract bounds river; 0 otherwise)\\
NOX:      &nitric oxides concentration (parts per 10 million)\\
RM:     &average number of rooms per dwelling\\
AGE:     &proportion of owner-occupied units built prior to 1940\\
DIS:     &weighted distances to five Boston employment centers\\
RAD:     &index of accessibility to radial highways\\
TAX:    &full-value property-tax rate per \$10,000\\
PTRATIO:  &pupil-teacher ratio by town\\
B:    &$1000(Bk - 0.63)^2$ where $Bk$ is the proportion of blacks by town\\
LSTAT:      &\% lower status of the population\\\hline
\end{tabular}}
\caption{Attributes in the HOUSING data set from UC Irvine. All attributes are continuous.
\protect\url{ftp://ftp.ics.uci.edu/pub/machine-learning-databases/housing/}}\label{fig:houseattr}
\end{figure}

\begin{figure}
{\small {\em
\begin{center}
\begin{tabular}{rccccc}
\multicolumn{4}{c}{Items} & & Criteria
\\\cline{1-4}\cline{6-6}
outlook & temp($^o$F) &  humidity & windy? & & class
\\\cline{1-4}\cline{6-6}
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\\\cline{1-4}\cline{6-6}
      rain&         70&     96&     false&&      some\\
      rain&      68&     80&     false&   &   some\\
      rain&      75&     80&     false& & some\\\cline{1-4}\cline{6-6}
      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\\\cline{1-4}\cline{6-6}
\end{tabular}\end{center}}}
\caption{A log of some golf-playing behavior.}
\label{fig:golfdata}
\end{figure}
\section{Treatment Learning}

TAR2 inputs a dataset of $D$ examples containing $I$ items.
Each example is assessed  according to some criteria. For
example, \fig{golfdata} shows a log of golf-playing
behavior assessed on the criteria of how much playing was
seen in each $D_i$. In this example, playing {\em lots} of
golf is the preferred "good" behavior while playing only
{\em some} or {\em none} is "bad" behavior.
%\begin{center}
%{\footnotesize
%\begin{tabular}{cccccccccc}
%    &\multicolumn{4}{c}{$I$ = Items}&&\multicolumn{4}{c}{$C$ = Criteria}\\
%$D$ & $I_1$ & $I_2$ & ... & $I_i$     & & $C_1$ & $C_2$ & ... &
%$C_c$\\\cline{2-5}\cline {7-10}
%1 & $V_x$ & ? & ... & $V_w$ & & good & med & .. & ? \\
%2 & $V_y$ & $V_z$ & ... & ? & & bad & ?  & ... & good \\
%\end{tabular}
%}
%\end{center}

TAR2 outputs a {\em control} rule and a {\em monitor} rule.
The left-hand-side of the {\em control} rule is the
learner's recommendation on what may most improve the
current situation. The left-hand-side of the {\em monitor}
rule is the set of events which, if they happened, would
most degrade the current situation. These rules take the
form:

{\footnotesize
\begin{eqnarray}\nonumber R_1&if&
Attr_1=range_1 \wedge Attr_2=range_2  \wedge ...\\\nonumber
&then& good=more \wedge bad=less \\\nonumber R_2&if&
Attr_1=range_1 \wedge Attr_2=range_2  \wedge ...\\\nonumber
&then& good=less \wedge bad=more
\end{eqnarray}}
\noindent where $R_1$ is the control rule; $R_2$ is the
monitor rule; {\em good} and {\em bad} are sets of classes
that the agent likes and dislikes respectively; and {\em
more} and {\em less} are the frequency of these classes,
compared against the current situation, which we call the
{\em baseline}. For example, the baseline class
distribution in \fig{golfdata} is that the golfers play
"lots", "some", and "none" golf in 43\%, 21\%, and 36\%
(respectively) of the dataset (as shown in the
left-hand-side histogram of \fig{golft}).

Using this
dataset, and the techniques described below, TAR2 found the
control and monitor rules of \fig{cr}.
\begin{figure}
\begin{center}
\begin{minipage}{0.8\linewidth}
{\footnotesize
\begin{verbatim}
controller2 if outlook=overcast
then (230% more "lots" and no "some"
     and no "none").

monitor2 if 90 <= humidity < 97
then (43% less "lots" and 5% less "some"
     and 167% more "none").
   \end{verbatim}}
\end{minipage}
\end{center}
\caption{Control and monitor rules found from \protect\fig{golfdata}.
To control {\em outlook}, unscrupulous owners of golf courses could (e.g.)
bribe radio announces to lie about the weather report.}\label{fig:cr}
\end{figure}
The left-hand-side of these rules can be viewed as
constraints, which, if applied to the dataset, may reject
certain examples. For example, consider the
$outlook=overcast$ constraint of {\tt controller2}. If we
reject all items in our dataset that contradicts this
constraint, then our golfers now play "lots", "some", and
"none" golf in 100\%, 0\%, and 0\% (respectively) of the
constrained dataset (as shown in the middle histogram of
\fig{golft}). The right-hand-side of the control rule is
generated by comparing the class distribution between the
baseline and the constrained dataset. The right-hand-side
of {\tt monitor2} was generated in a similar manner; i.e.
after applying the constraint $90 \le humidity < 97$, the
class distribution changed to the right-hand-side histogram
of \fig{golft}.

\begin{figure}
{\footnotesize\begin{center}
\begin{tabular}{p{0.9in}p{1.0in}p{1.1in}}
baseline: &controller2:
& monitor2:\\
  (from \fig{golfdata})          & $outlook=$
$overcast$ & $humid
=[90..97)$\\~\\
\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
     \setstretch{0.4}
    \setyaxis{0}{100}{25}
\sethspace{0.4} \setnumberpos{down} \bar{36}{1}
 \bar{21}{4}
 \bar{43}{8}
\end{barenv}&
\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
 \setstretch{0.4}
    \setyaxis{0}{100}{25}
\sethspace{0.5} \setnumberpos{down}
\bar{0}{1} \bar{0}{4} \bar{100}{8}
\end{barenv}
&
\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
 \setstretch{0.4}
  \setyaxis{0}{100}{25}
\sethspace{0.5} \setnumberpos{down}
 \bar{60}{1}
  \bar{20}{4}
   \bar{20}{8}
\end{barenv}
\end{tabular}
\end{center}
} \caption{Percentage of classes seen in different situations.
KEY:~\protect\legend1{none}; \protect\legend4{some};
\protect\legend8{lots}.} \label{fig:golft}
\end{figure}

\section{Inside TAR2}

\subsection{Generating Controllers}


The TAR2 algorithm is shown in \fig{tar2}.
The {\tt frequency} function counts the frequency of examples falling into
different criteria.  Using this function, a \BASELINE\ class distribution is  collected from
\DEE\ (this is used later to contrast different treatments)
and copied to a \TEMP\ variable (this is used to store the best
distribution seen so far).
The {\tt compare} function compares two frequencies
to generate reports like (e.g.) 43\% less "lots" and 5\% less "some"
and 167\% more "none". The {\tt discretize} function divides
the numeric ranges seen in the examples into \BANDS\ number of
groups.
Numerous discretization policies are
possible but the simplest works adequately: TAR2 sorts the
known values and divides into equal size \BANDS.

%XXX define ">" in the following

\begin{figure}
\begin{center}\begin{minipage}{1.0\linewidth}{\scriptsize
\begin{tabular}{l@{~}l@{~}p{2.5in}}
\INPUT:&   \DEE      &The examples.\\
     &   \ITEMS     & Attributes seen in the examples.\\
      &  \BEST      &The best combination of criteria.\\
      &  \EN      & Desired size of LHS.\\
      &  \PROMISING & Threshold for a
                   useful attribute range.\\
       & \SKEW      & Threshold for acceptable number
                  of \BEST\ entries in \TREATED.\\
       & \BANDS     &Number of divisions within
                  continuous ranges.\\~\\
\OUTPUT: &\LHS& A conjunction of attribute ranges\\
&\RHS& a change in the class distributions\\
\end{tabular}
\begin{alltt}
01. \DEEONE \IS discretize(\DEE, \BANDS)
02. \TEMP \IS \BASELINE \IS frequency(\DEEONE)
03. \FOR \ATTRIBUTE in \ITEMS \DO
04.     \FOR \RR \IN \ATTRIBUTE.\RANGES \DO
05.          \IF   nudge(\ATTRIBUTE.\RR) \GE \PROMISING
06.          \THEN \CANDIDATES \IS \CANDIDATES + \ATTRIBUTE.\RR\DONE\DONE
07. \FOR \CC \SOME \CANDIDATES \WHERE |\CC| = \EN \DO
08.     \DEETWO \IS \CC \PLUS \DEEONE
09.     \DISTRIBUTION \IS frequency(\DEETWO)
10.     \IF     \DISTRIBUTION>\TEMP \AND |\BEST\PLUS\DEEONE|/|\BEST\PLUS\DEETWO|>\SKEW
11.     \THEN   \DO\LHS \IS \CC
12.            \RHS \IS compare(\BASELINE, \DISTRIBUTION)
13.            \TEMP \IS \DISTRIBUTION\DONE\DONE
14. \IF (\LHS \NOE \AND \RHS \NOE) \THEN \RETURN (\LHS, \RHS)
15. \ELSE \RETURN "no treatment"
\end{alltt}}\end{minipage}\end{center}
\caption{The TAR2 algorithm.}\label{fig:tar2}
\end{figure}

%XXX missing values
% XX best classs
% skew prune


Once a treatment is found, it is applied to the example set to create
a \TREATED\ example set; i.e. all the examples that don't contradict the
proposed treatment (see line 8). A "good" treatment includes
most of the   examples that
have the \BEST\ criteria (e.g. in the golf example of \fig{golfdata}, \BEST= playing "lots" of golf).
The \SKEW parameter is used at line 10 to reject "bad"
treatments; i.e. those that don't contain enough of the \BEST\ criteria. For example,
at \SKEW=5, at least 20\% of the \BEST\ criteria must appear in the treatment.


TAR2 explores  subsets of the  \RANGES\ found in
a set of examples \DEE\ (see line 7). Since there are an
exponential number of
such subsets, TAR2 uses two mechanisms to avoid
exponential runtimes: {\em the small rule assumption} and
{\em nudging}

{\em The small rule assumption}: Recall from the
introduction that agents struggling to understand their
environment seek the {\em minimal} possible number of
control actions and monitors. Hence, the number of
attribute ranges in a control or a monitor rule should
always be small. Accordingly, the user of TAR2 constrains its learning
to rule conditions of size \EN, where  $N$ is small (see
line 7 of \fig{tar2}). Often, effective treatments can be
found using $N\le 4$. The success of the small rule assumption
is remarkable and will be explored further, later.

{\em Nudging}:
Since the size of
the rule conditions will be small, it is possible that
heuristic assessments of a single attribute range can guide
TAR2 to a good combination of \RANGES. TAR2's heuristic
measure for the worth of a single range is called the {\em nudge}
factor.
The {\em nudge} of a range is high if it occurs more frequently
in better situations than in worse situations. That is, if we were
to impose this range as a constraint, then it would tend to
"nudge"  the system into better behavior. TAR2  only explores
\RANGES\ with a \PROMISING\ {\em nudge} (see line 5 of \fig{tar2}).

The {\em nudge} of a  range is a heuristic measure of how well
a \RANGES\ can influence a system towards the \BEST\ class and is:
\bi
\item
The {\em difference} in frequency
of this range between the \BEST\ class
and  other classes
\item {\em Normalized} by the number of times the range appears in \DEE.
\item {\em Weighted} by the relative merits of the \BEST\ and the other classes,
\item
{\em Summed} over all  pairs of \BEST\ class and non-\BEST\ class.
\ei
For example, in \fig{golfdata}, let us assume that the classes have been
scored as follows: "lots"=8, "some"=4, "none"=2\footnote{Ying- why did not not score these
2,1,0?}; i.e. "lots" is the \BEST class. The  range
{\em outlook=overcast} appears four, zero, and zero
times when playing "lots", "some", and "none" golf (respectively).
The {\em nudge} of {\em outlook=overcast} is therefore:

{\small
\[\frac{\left(\underbrace{\overbrace{(\underbrace{(8-2)}_{weighting}*\underbrace{(4-0)}_{
difference})}^{lots \rightarrow none}
+\overbrace{(\underbrace{(8-4)
}_{weighting}*\underbrace{(4-0)}_{difference})}^{lots
\rightarrow some}}_{summed\;over\;all\;combinations\;with\;best\;class}\right)}{
\left(\underbrace{4+0+0}_{normalization}\right)}=10
\]
}

\begin{figure}
\begin{center}
{\footnotesize
\begin{tabular}{c}
\begin{barenv}
\setstyle{\sffamily} \setwidth{8} \setnumberpos{none}
 \setstretch{8}\sethspace{0.5} \setyaxis{0}{3}{1}
\setxaxis{-5}{10}{1}
 \bar{0}{8} % -5
 \bar{1}{1} %-4
 \bar{0}{8} % -3
 \bar{0}{8} % -2
 \bar{1}{1}  % -1
  \bar{3}{1} % 0
  \bar{3}{1} % 1
\bar{2}{1} % 2
 \bar{0}{8} %3
\bar{0}{8} %4
\bar{1}{8} %5
\bar{1}{8} %6
\bar{0}{8} %7
\bar{0}{8} %8
\bar{0}{8} %9
\bar{1}{8} %10
\end{barenv}
\end{tabular}
}
\end{center}
\caption{Frequency of $nudges$ generated from \fig{golfdata}.
Assumes that numeric ranges have been divided into 3 \BANDS.
Outstandingly high $nudges$ values shown are in black. Y-axis is the
number of  ranges that have a particular $nudge$.}
\label{fig:dels}
\end{figure}




\fig{dels} shows the range of $nudges$ see in  of \fig{golfdata}.
Assuming small rules, then TAR2 need only explore
treatments taken from the small number of \RANGES with
an outstandingly large
{\em nudge} score (see the black entries in \fig{dels}).
Applying this method:
\bi
\item
The {\tt controller2} rule of \fig{cr} was generated using
\SKEW=5, \BANDS=3, \EN=1, and \PROMISING=4.
\item
The {\tt controller1} rule shown in the middle column of the table
in \fig{tree}
was generated using
\SKEW=5, \BANDS=4, \EN=2, and \PROMISING=7.
\ei

One interesting feature of TAR2-style learning, are the attributes
never seen in the learnt
controllers. In the golf example, of the four
known attributes,
one of them {\em outlook} was deemed worthy of manipulation.

Menzies and Kiper studied a model of best practices in software engineering
(level 2 of the Software Engineering Institute's capability
maturity model, als known as CMM2~\cite{paulk93}).



\subsection{Generating Monitors}

Monitors are generated using exactly the same code as generating
controllers. However, before the monitor is generated, the
scoring function for the classes is reversed so TAR2 now seeks
\RANGES\ that {\em nudge} a system into worse behavior.

%XXX key point. the nudge distributions say that most
% attributes dont matter

%XXX refer to the monitor1 and monitor2 rules. note that
% bad <> not good




\section{Stopping Rules}

\section{Validation}

TAR2's treatments can be validated using the N-way cross
validation facility that comes with the standard
distribution\footnote{Available from
\url{http://www.ece.ubc.ca/twiki/bin/view/Softeng/TreatmentLearner}}.
TAR2's treatments can also be validated by testing if the
proposed treatments really do change the behavior of a
system. This second test only works when (i) the data sets
were generated from some model; (ii) the analysts have
access to that model.

In three studies with models generating the examples, TAR2
 generated successful control rules. In the first study,
analysts at the NASA Jet Propulsion Laboratory built a
semantic network describing the interactions between 88
features of a proposed dead space mission. Each edge was
annotated with the numeric cost and benefits of taking some
action. Some of these nodes represented base decisions
within the project (e.g. selection of  a particular type of
power supply). 42,000 times, the net was executed using
some random combination of the base decisions. The
resulting costs and benefits were collected, sorted, and
divided into three 33.3\% percentile bands. This resulted
in nine criteria scores: hH,hM,hL,  mH,mM,mL, lH,lM,lL
where h,m,l=high,medium,low costs and H,M,L=high,medium,low
benefits. The frequency of these criteria are shown as the
{\em Raw} plot of \fig{run1}. Using \EN=5 and \BANDS=2,
TAR2 found a control rule that predicted the improved distribution
of {\em Treatment1} of \fig{run1}. {\em Result1}
shows the distributions seen after 42,000 more random runs
with the constraint of {\em Treatment1} imposed. Note that
TAR2's predictions and the actual behavior were very close.


\begin{figure}[!t]
\begin{center}
\includegraphics{resultsA.eps}
\end{center}
\caption[Round1]{{\em Raw}= untreated distribution seen in
42,000 runs. {\em Treatment1}= distribution predicted by
TAR2 after learning a control rule. {\em Results1}=
distributions seen in 42,000 runs, with the constraint of
treatment1. }\label{fig:run1}
\end{figure}


\begin{figure}
{\scriptsize
\begin{alltt}
%blub(Mode,Glow,Volt,Amp)   %switch(State,Volt,Amp)
bulb(blown,dark,  Any, 0).   switch(on,    0,    Any).
bulb(ok,   light, +,   +).   switch(off,   Any,  0).
bulb(ok,   light, -,   -).
bulb(ok,   dark,  0,   0).

%sum(X,Y,Z).
sum(+,+,+).   sum(+,0,+). sum(+,-,Any).
sum(0,+,+).   sum(0,0,0). sum(0,-,-).
sum(-,+,Any). sum(-,0,-). sum(-,-,-).
\end{alltt}}
\caption{Definitions of qualitative components of an
electrical circuit and switches. Adapted from
\protect\cite{bratko01}.}\label{fig:bulb4}
\end{figure}

%XXX scale up unknown . ok if the larger data sets have a small left tail and that is future work
% all hthe exanples discssued in the

In another study~\cite{me01g}, TAR2 learnt controllers for a
qualitative description of an  electrical
circuit containing 47 wires connecting 9 light bulbs and 16 other components.
The circuit was coded in Prolog and expressed
as a set of constraints; e.g.
the sum of the voltages of components in series is the sum
of the voltage drop across each component.
The {\tt bulb} relation of \fig{bulb4} describes our qualitative knowledge of
bulbs in the circuit. For example, {\tt bulb(blown,dark,Any,0)} says that
a blown bulb is dark, has zero current across it, and can have any
voltage at all.   {\tt Switch}
describes our qualitative knowledge of
electrical switches. For example {\tt switch(on,0,Any)} says
that if a switch is on, there is zero voltage drop across it while
any current can flow throw it. {\tt Sum} describes our knowledge of qualitative
arithmetic, some of which is nondeterminate. For example, {\tt sum(-,+,Any)}
notes that the sum of a negative and a positive value is unknown. The nondeterminacy
of {\tt sum} means that the behavior of the whole circuit can vary wildly. On backtracking,
this circuit generated 35,228 runs. Each run was scored according to how many bulbs glowed
{\tt light}ly and, on average, only two bulbs glowed in each run (see the {\em raw}
distribution of \fig{run2}.
TAR2 found  a control rule comprising two changes to the circuit that tripled the
average number of bulbs glowing: see the {\em treated} run of \fig{runs2}.
The two changed required the closing of one switch, and replacing one
bulb with a longer-life bulb. On backtracking over this circuit
with TAR2's control rule imposed, the resulting distribution of glowing bulbs
matched TAR2's predicted distribution exactly.

\begin{figure}
\begin{center}
\includegraphics{circ.eps}
\end{center}
\caption[Round1]{{\em Raw}= untreated distribution seen in
35,228 solutions to some qualitative constraints about an equation.
{\em Treated}= distribution predicted by
TAR2 after learning a control rule.   }\label{fig:run2}
\end{figure}




%XXX add in the cocomo and the QR results

In other work


\begin{figure*}
\begin{center}
{\scriptsize
\begin{tabular}{p{1.5in}p{1.5in}p{1.5in}p{1.5in}}
 {\em \fig{dels}.i: housing}\newline {\tiny
\begin{barenv}
\setstretch{5.4} \setstyle{\sffamily} \setwidth{8}
\setnumberpos{none} \setyaxis{0}{10}{2} \sethspace{0.5}
 \setxaxis{-10}{22}{4}
 \bar{8}{1}

  \bar{8}{1}

 \bar{8}{1}

\bar{10}{1}

   \bar{9}{1}

   \bar{3}{1}

\bar{1}{1}

 \bar{2}{1}

 \bar{2}{1}
\end{barenv}} &
 {\em \fig{dels}.ii: page-blocks}\newline {\tiny
\begin{barenv}
\setstretch{2.7} \setstyle{\sffamily} \setwidth{8}
\setnumberpos{none} \sethspace{0.5}\setyaxis{0}{20}{4}  \setxaxis{-29}{32}{8}
\bar{20}{1}

\bar{7}{1}

 \bar{0}{1}

 \bar{1}{1}

 \bar{0}{1}

\bar{0}{1}

 \bar{1}{1}

 \bar{1}{1}
\end{barenv}}&
  {\em \fig{dels}.iii: wine}\newline {\tiny
\begin{barenv}
\setstretch{2.7} \setstyle{\sffamily} \setwidth{8}
\setnumberpos{none} \setyaxis{0}{20}{5} \sethspace{0.5}\setxaxis{-4}{11}{2}

   \bar{13}{1}

    \bar{17}{1}

\bar{15}{1}

\bar{7}{1}

 \bar{5}{1}

  \bar{3}{1}

\bar{2}{1}

 \bar{3}{1}
\end{barenv}}

&

{\em \fig{dels}.iv: car}\newline {\tiny
\begin{barenv}
\setstretch{5.4} \setstyle{\sffamily} \setwidth{8}
\setnumberpos{none} \setyaxis{0}{10}{3} \sethspace{0.5} \setxaxis{-13}{-7}{1}
\bar{5}{1} \bar{2}{1} \bar{3}{1} \bar{3}{1} \bar{6}{1} \bar{1}{1}
\bar{1}{1}
\end{barenv}}

\\~\\
 {\em \fig{dels}.v: satellite requirements}\newline {\tiny
\begin{barenv}
\setstretch{0.45}\sethspace{0.5}
\setstyle{\sffamily}
\setwidth{8}
\setnumberpos{none}
\setyaxis{0}{120}{30}
\setxaxis{-350}{0}{50}
\bar{1}{1}
 \bar{11}{1}
 \bar{46}{1}
 \bar{118}{1}
 \bar{16}{1}
 \bar{0}{1}
 \bar{4}{1}
  \bar{8}{1}
\end{barenv}} &

   {\em \fig{dels}.vi: QR circuit}\newline{\tiny
\begin{barenv}
\setstyle{\sffamily}\sethspace{0.5} \setwidth{8}
 \setnumberpos{none}
 \setstretch{0.154}
\setyaxis{0}{350}{100}
 \setxaxis{4}{9}{1}
 \bar{144}{1}
 \bar{226}{1}
 \bar{280}{1}
  \bar{104}{1}
  \bar{17}{1}
  \bar{10}{1}
\end{barenv}} &
  {\em \fig{dels}.vii: cmm2}\newline {\tiny
\begin{barenv}
\setstretch{0.25}\sethspace{0.5} \setstyle{\sffamily} \setwidth{8}
\setnumberpos{none} \setyaxis{0}{220}{50}
\setxaxis{1}{14}{2}

\bar{20}{1}
 \bar{147}{1}

\bar{213}{1}
\bar{212}{1}

 \bar{10}{1}

\bar{20}{1}
 \bar{10}{1}
\end{barenv}}
&
 {\em \fig{dels}.viii: cocomo2}\newline  {\tiny
\begin{barenv}
\setstyle{\sffamily}
\setwidth{8} \setstretch{0.72}
\setnumberpos{none} \sethspace{0.5}
 \setyaxis{0}{75}{25}
 \setxaxis{-13}{9}{4}
 \bar{1}{1}
 \bar{3}{1}
 \bar{4}{1}
 \bar{68}{1}
 \bar{49}{1}
 \bar{9}{1}
\end{barenv}}
\end{tabular}}

\end{center}
\caption{$Nudges$ distribution seen in six data sets.
 Y-axis is
the number of times
  a particular $nudges$ was seen.
 Top row comes from datasets taken from
  the UC Irvine machine learning
database at
\protect\url{http://www.ics.uci.edu/~mlearn/}. Bottom
row are datasets discussed in the text.}\label{fig:nudges}
\end{figure*}

\section{Generality}

\subsection{Empirical Results}
\begin{figure}
\begin{center}
{\small
\begin{tabular}{c}
\begin{barenv}
\setstyle{\sffamily} \setwidth{8} \setnumberpos{none}
 \setstretch{0.84}\sethspace{0.5} \setyaxis{0}{64}{15}
\setxaxis{1}{8}{1}
 \bar{5}{1} %-4
 \bar{5}{1} % -3
 \bar{5}{1} % -2
 \bar{5}{1}  % -1
  \bar{8}{1} % 0
  \bar{16}{1} % 1
\bar{32}{1}
\bar{64}{1}
\end{barenv}
\end{tabular}
}
\end{center}
\caption{A hypothetical $nudge$ frequency distribution with a large
left tail. Note: yet to be observed in any example set.}
\label{fig:badnews}
\end{figure}

The $nudge$ distribution is a  measure for the practicality of
TAR2.
Exploring all subsets of the \CANDIDATES\
could be too slow unless nudge pruning removes most
of the ranges.
For example, in the golf example,
\fig{golft} was a distribution where nudge pruning
is effective: i.e. only a few ranges
 have an outstanding nudge value.
 We say that \fig{golft} has a {\em small left tail}; i.e. the bulk
 of the distribution lies away from the maximum value.
 Distributions with a {\em large left tail} such as \fig{badnews}
 may defeat TAR2 since large left tails imply that
 TAR2 will have to search through too many \CANDIDATES\ subsets.

The generality of TAR2 can be assessed by studying the nudge
distributions seen in different domains. \fig{nudges} shows
the nudge distributions seen in eight example sets: four from the UC
Irvine repository and four from other domains we have studied.
Note that in all cases, the distribution has a small left tail; i.e.
TAR2 can ignore most of the attributes when searching the ranges.
In all, we have applied TAR2 to 20 domains (the eight shown in \fig{nudges}
and 12 more, not shown for space reasons). In none of those domains
have we observed a large left tail.


\section{Runtimes}
\begin{figure}
\begin{center}{\scriptsize
\begin{tabular}{|p{0.2in}|c|c|c|c|c|c|}\hline
        &  & \multicolumn{2}{c}{Attributes} & & &\\\cline{2-4}
     &\#&\#&\#&\#&$|lhs|$&runtimes\\
domain    &examples&continuous&discrete&classes&$|lhs|$& (secs)\\\hline
housing   & 506      & 13         &          & 4       & 2     & 1\\\hline
page\newline
blocks& 5473    & 10         &          & 5       & 2     & 2\\\hline
wine      & 178      & 13         &          & 3       & 2     & 0\\\hline
car       & 1728     &            & 6        & 4       & 2     & 0\\\hline
QR \newline circuit   &35228  & 0          & 18       & 10      & 4     & 4\\\hline
cocomoII     &30000  & 0          & 23       & 4       & 1     & 2\\\hline
satellite\newline
requirements &30000  & 0          & 99       & 9       & 5     &86\\\hline
              \end{tabular}}\end{center}
              \end{figure}


\begin{figure}
\begin{center}
\includegraphics{runt.eps}
\end{center}
\caption[Round1]{Runtimes vs number of ranges in
the left-hand-side of a control rule.}\label{fig:run3}
\end{figure}

%place all the models in a box at the start, with a reference
%at the end.

% evidence for funnels voluminous. e.g. operational profiles
% dont matter, after they are big enough to luck onto the funnel.
% single fault assugnpiton in model-based diagnosis.

\begin{figure}
\begin{center}
\includegraphics{sizet.eps}
\end{center}
\caption[Round1]{Runtimes vs number of examples, assuming
$|lhs|=5$.
{\em Setup time} covers reading data fro
from disc, and computing the nudge distributions.
{\em Total time} minus {\em setup time} is
 the time spent searching the subsets of \CANDIDATES.}\label{fig:run3}
\end{figure}

%XXX note: runtimes worse than exponential as |lhs| increases
% and less than exponential as sample size increases
% and assuming small rules, then we're in!

%not done: effect of unknowns, effects of increasing #attribtus, #classes,
%#examples. and some control for solution quality. kidna like the
% apriori paper

\section{From Classifiers to Association Rule Learning to
Treatment Learning}



A  classifier  (e.g. C4.5~\cite{quinlan92} or
CART~\cite{breiman84}) learn connections between $items$
and a classification.  These learners  input a set of
examples containing a set of items $I_i$ of the form
$attribute=value$.  Each example is classified into one and
only one class. The runtime task of a  classifier is to
find an conjunction of items that lead to a certain class.
To find this range, the learner picks one attribute range
that split the set of examples $D$ into subsets $D_1, D_2,
...$. A split is ``good'' if, for each subset $Di$, there
is an increased percentage frequency of one class (compared
to the original set $D$) . The learner then recurses into
each subset to find sub-splits. Various heuristic measures
are used to find the splitting criteria: C4.5 uses an
measure inspired by information theory. The final decision
tree is a report of the tree of recursively-generated
splitting criteria. Each branch of such a tree can be read
as a rule:
\[
Attr_1=range_1 \wedge Attr_2=range_2  \wedge ...
\Rightarrow class=X
\]
where $range$ can be a single value or some numeric
comparison such as $> number$.

Classifiers have a small number of pre-defined targets (the
classes) while,  for {\em association rule learners}, the
target of the learning is not pre-specified. Systems like
APRIORI~\cite{agrawal94} return associations between items
of the form
\[
Rule_r\;:\;X \Rightarrow Y
\]
where $X \subset I$ and $Y \subset I$ and $X \cap Y =
\emptyset$.  In the terminology of APRIORI, $Rule_r$ has
{\em support} $s$ if $s\%$ of the $D$ contains $X \cup Y$;
i.e.
\[support(rule_r)=\frac{|X \cup Y| }{|D|}\] The {\em
confidence} of $rule_r$ is the percent of transactions
containing $X$ which also contain $Y$; i.e.
\[confidence(rule_r)=\frac{|X \cap Y|}{|X|}\]
Many association rule learners use {\em support-based
pruning} i.e. when searching for rules with high
confidence, sets of items $I_i,... I_k$ are only be
examined only if all its subsets are above some minimum
support value.

A common restriction with   classifiers is that they assume
all of $D$ can fit into RAM. Most association rule learners
remove that restriction and are designed for data sets that
need not reside in main memory (exception:~\cite{webb00}).
For example, Agrawal and Srikant report experiments
association rule learning using data sets of size 843MB and
$|D|=10,000,000$~\cite{agrawal94}.

Many variants of APRIORI have been proposed. The CBA
learner finds {class association rules}; i.e. association
rules where the conclusion is restricted to the
classification class attribute~\cite{liu98}. That is, CBA
acts like a classifier, but can process larger datasets
that (e.g.) C4.5.

Another variant are the learners that reject APRIORI-style
support-based pruning. In the case of many
 highly confident rules,   learners such as the
 Wang-He-Cheung~\cite{wang00} system ignore support-based pruning to
  find
  features that apply to a small, but interesting subset
  of $D$.

  Other researchers have
  explored
  {\em weighted association rule learning} in which
     some items are given a higher priority weighting that
     others.   Learners such as MINWAL~\cite{cai98} can use
     such
      weights to focus the learning  onto issues that are of
     particular interest
     to some audience.
     MINWAL can't use APRIORI-style support-based pruning since, with
  weighted items, it is not always true that subsets of
  {\em interesting} items (i.e. where the weights are high) are also
  interesting.

{\em Contrast set} learners such as STUCCO return a
different kind of rule. Instead of finding rules that
describe the current situation, STUCCO finds rules that
differ meaningfully in their distribution across groups.
For example, in STUCCO, an analyst could ask "what are the
differences between people with Ph.D. and bachelor
degrees?"~\cite{bay99}.



\section{Treatment Learning}

 a small number of actions
Learners summarize examples into a theory. Controlling a
device implies a concept of better and worse behavior,
ranked on multiple criteria $C$. Hence, we'll say that our
agent has rankings about  $N$ examples referencing  $A$
attributes  with values $V$:

A
general form of a learnt theory is $R$ rules:
\begin{eqnarray}
\nonumber lhs_1 &\Rightarrow& rhs_1\\
\nonumber  lhs_2 &\Rightarrow& rhs_2\\
\nonumber \ldots\\
\nonumber  lhs_R &\Rightarrow& rhs_R\\
\end{eqnarray}
where $lhs_i$ and $rhs_j$ are conjunctions of some subset of our attribute ranges and $lhs_i$ is some
{\em control action} that our agent might apply if they want to achieve $rhs_i$.
Since our agent can assess the desirability of $rhs_i$ (using the criteria $C$), then
the rule base can be restricted to just the rule(s) with the most desirable right-hand-side(s).
Also, since controlling a large number of attributes is harder than controlling a small number,
the size of the conjunction $lhs_i$ should be minimized.
Further, at any point of time, only one control strategy can be applied.
Hence, in the case where there are multiple ways to achieve the same goal (i.e. $rhs_i = rhs_j$),
then our learning can discard some (?all) of the alternate ways of reaching
$rhs_i$.




The above restrictions on size of $lhs_i$ and  {\em could} be applied as a post-processor to standard association rule learners.
However, if these

Also,


Typically, agents can only control some subset of all the attributes. Also, it is often
true that it is more expensive and more time consuming to control a larger number of attributes
than a smaller number. Hence,



Further, given their opinions about
different examples,

For example, C4.5~\cite{quinlan92} and 10-way cross-validation can
generate an ensemble of classifiers from an oracle of software
project risk~\cite{madachy97}. The resulting ensemble has ten
trees of 6000 nodes each and is totally opaque to software
managers. To make the ensemble understandable, Menzies \& Sinsel
experimented with finding sets of attribute ranges that were more
frequently associated with preferred classes~\cite{me00e}. These
attribute ranges were were found and assessed via the TARZAN tree
query language. TARZAN swung through the decision trees in the
ensemble looking for {\em treatments}; i.e. a conjunction of
attribute ranges:
\[
Treatment\;:=\;  A_i=R_x \wedge A_j=R_y \wedge\ldots
\]
where $A_i=R_x$ denotes some attribute $i$ having some range $x$.
Treatments were assessed by applying them as constraints on the
decision trees in the ensemble. Decision tree branches that
contradicted the treatment were culled. A {\em candidate}
treatment
 {\em increased} the percentage of branches leading to
some preferred {\em good} classes and decreased the percentage of
branches leading to undesirable {\em bad} class. In this
experiment,  {\em good} and {\em bad} meant high/low risk
projects, respectively.
\[ Treatment
\Rightarrow good=increased \wedge bad=decreased\] A {\em good
treatment}  had certain properties: (i)~it used a small number of
attributes; (ii)~it significantly increasing the percentage of
{\em good} while significantly decreasing the percentage of {\em
bad}; (iii)~it was  found in the majority of the trees in the
ensemble. Instead of showing their business rules 60,000 nodes in
ten decision trees, Menzies \& Sinsel showed their 6 best good
treatments. In a single hour, business users could review the
results of the machine learner, debate the the merits of numerous
project management options, and decide on an action plan.

This paper generalizes the TARZAN system and introduces the TAR2
system. Both learn treatments, but using different methods. TARZAN
is a post-processor to C4.5 and is hard to analyze since two sets
of learning heuristics are required (the entropy heuristics used
in C4.5 and the tree query heuristics used in TARZAN). TAR2 is an
association rule learner that learns rules of the form:

\section{Missing attributes}
\section{Descritization}
Tried simplest first- percentile ranking. Worked fine.
\section{Class scoring}
exponential, not linear

\section{Validation}

\section{Conclusion}

One manager explained this preference using  an the analogy of a
reading a map. Standard classifiers, he said,  point to a map and
say ``you are here''. Treatments learners   offer guidance on how
to get from ``here'' to a better place, using the least effort.



 in the majority of the
decision trees in the ensemble. In this way, ten 6,000 nodes
decision trees were summarized

This paper is about  learning theories that will be used by agents
with severe resource limitations; e.g. the managers of a software
project. Such resource-limited agents seek theories that propose a
minimal number of changes that improve their current situation.



of Such theories are read by some audience. Depending on the
nature of that audience, di

\bibliographystyle{../../tex/latex8}
%! remind me to send you my refs.bib file
%! you'll have  to change this line to wherever your store your refs
%! to get the references in, you have run latex once, bibtex once, then latex twice
%! (to get the reference numbers right). so stupid...
\bibliography{../../refs}

\end{document}
