%XXX contrast set learning
\documentclass[pdf,distiller]{prosper}
\usepackage[toc,highlight,HA]{HA-prosper}
\usepackage{natbib,bibentry,color,textcomp}
\usepackage{amsmath,bar}
\usepackage{alltt,wrapfig}
\newcommand{\aive}{a\"{\i}ve}
\newcommand{\aaa}{NW}
\newcommand{\bbb}{SE}

\bibliographystyle{plainnat}


\title{Next Generation ``Treatment Learning''}
\subtitle{(finding the diamonds in the dust)}
\author{Tim Menzies\\
\institution{UpLift Systems}\\
{\scriptsize \url{timm@bart-massey.com}}
}
\HAPsetup{
rf={Treatment Learning},
lf={\href{http://bart-massey.com}{Better RX}, \today},
tsnav=ShowBookmarks,
nsnav=ShowBookmarks}

%\DefaultTransition{Wipe}
%\TitleSlideNav{FullScreen}
%\NormalSlideNav{ShowBookmarks}
%\LeftFoot{
%\RightFoot{

 \newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
 \newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
 \newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\tion}[1]{\S\ref{sec:#1}}

\begin{document}
\nobibliography{../../refs}
\maketitle

\tsection{Introduction}
%% \begin{slide}{Feb 9, 2001}
%% \vspace{-5mm}
%% {\small
%% \bi
%% \item
%% A talk on self-organizing maps (Kohonen's 
%%  data visualization technique for
%%  reducing data dimensions
%% via  self-organizing neural networks).

%% \begin{center}
%% \includegraphics[width=1.4in]{some.eps}
%% \end{center}

%% \item  Bias: $good$ = pale blue \& $bad$ = dark blue
%% \item Let the bias inform the learning;
%% \bi
%% \item
%% Just model the {\em delta} between $good$ and $bad$
%% \item
%% Why model the other stuff?
%% \ei
%% \ei
%% }
%% \end{slide}

\begin{slide}{The strangest thing...}
{\footnotesize
``In any field, find the strangest thing, and explore it''
-- John Wheeler 

~\\

\begin{minipage}{2.8in}
\vspace{0pt}
\bi 
\item Q: How have dummies (like me) managed to gain (some) control over a (seemingly)
complex world?

~\\

\item A: The world is simpler than we think.
\bi
\item Models contain \underline{clumps} 
\item
A  few \underline{collar} variables 
decide which clumps to use.
\ei
~\\

\item TAR2,TAR3,TAR4: 
\bi
\item Data miners that  assume clumps/collars
\item Reports effects never seen before
\item Finds solutions faster than other methods
\item Returns tiniest theories
\item Scales to infinite data streams ($\Longleftarrow$ new result)
\ei
\ei 
\end{minipage}~~~\begin{minipage}{1.5in}
\includegraphics[width=1.2in]{strange.eps}
\end{minipage}
}
\end{slide}
\begin{slide}[toc=Complex Models?]{How Complex are our Models?}
{\scriptsize
\vspace{-11mm}
\begin{minipage}{2in}
\vspace{0pt}
{\footnotesize
\bi
\item \underline{COLLARS}-\newline
A small number few variables controls the rest:
\bi
\item \cite{deKleer86}: ``Minimal environments'' in the ATMS;
\item  \cite{me03l}: ``Tiny minimal environments'';
\item \cite{crawford94}: ``Master variables'' in scheduling;
\item \cite{williams03}: `Backdoors'' in satisfiability.
\ei

~\\

\item 
\underline{CLUMPS}-
\bi
\item
\cite{druzdel94}. Commonly, a few states; very rarely, most states;
\item 
\cite{pelanek04}. ``Straight jackets'' in formal models:
state spaces usually sparse, 
small diameter, many diamonds.
\ei



\ei
}
\end{minipage}~~~~~~~~~\begin{minipage}{2in}
\begin{center}


%\includegraphics[width=2in]{weave1.eps}

%i.e. not complex

%~\hrule~
\includegraphics[width=1.6in]{stats.eps}


%~\hrule~

\vspace{3mm}
\includegraphics[width=1.8in]{FWHalfSm.eps}

25,000 states 
in 
IEEE1394

\end{center}
\end{minipage}
}

\end{slide}
\begin{slide}{Exploiting  Simplicity}
\begin{minipage}{3in}
\vspace{0pt}
{\footnotesize
\bi
\item If clumps
\bi
\item
most of the action in a small number of states
\item
effective search space = small
\ei

\item If collars:
\bi
\item
A few variables that switch you between states
\ei
\item Treatment learning 
\bi
\item
If a few variables control the rest, then..
\bi
\item
All paths $inputs \rightarrow outputs$
use the collars (by definition).
\ei
\item
So  don't  search for the collars:
\bi
\item They'll  find you.
\item Just sample, and count frequencies $F$.
\ei

\item
Divide output $good$ and $bad$
\bi
\item
Focus on ranges $R_i$ with large  $\frac{F(R_i|good)}{F(R_i|bad)}$
\ei
\ei
\item
Great way to learn tiny theories.
\ei
}
\end{minipage}\begin{minipage}{1in}\vspace{0pt}
\includegraphics[width=1in]{stewfunnel.eps}
\end{minipage}

\end{slide}

\begin{slide}[toc=Different learners]{Learns Smaller Theories}
\vspace{-1cm}
\begin{center}
{\scriptsize
\begin{tabular}{p{2in}|p{1.6in}}
find  graphics on  a page from 11 features&
find good housing in Boston \\\hline
\\

\includegraphics[width=1.5in]{allpage-blocks.eps}

&

\includegraphics[width=1in]{bostontree.eps}\\\hline
\\


\includegraphics[width=1.5in]{block.eps} &

\includegraphics[width=1.6in]{bostonrx.eps}\\
{\scriptsize
 $34 \le height < 86\;\wedge$ \
\newline 
$3.9 \le mean\_tr <9.5$
}
&
{\scriptsize
$6.7 \le RM < 9.8\;\wedge$\newline $12.6 \le PTRATION < 15.9$}




\end{tabular}
}
\end{center}
\end{slide}

\begin{slide}{Why Learn Small Theories?}
{\footnotesize
\bd
\item[Reduce Uncertainty:]~\newline
Linear regression: $\sigma^2\;{\propto}\;|variables|$ (\cite{miller02});
\item[``Pluralitas non est ponenda sine neccesitate'':]~\newline
 MDL (\cite{wallace68}); FSS (\cite{hall03})
\item[Explanation:]~\newline
Smaller theories are easier to explain (or audit).
\item[Performance:]~\newline
The simpler the target concept, the faster the learning.
\item[Construction cost:]~\newline
Need fewer sensors and actuators.
\item[Operations cost:]~\newline
Less to do: important for manual procedures;\newline
Less to watch: important for data-intensive tasks like security monitoring.
\item[Pruning is good modeling:]~\newline
 Real world data often has noisy, irrelevant, redundant variables.
\ed
}
\end{slide}



\begin{slide}[toc=Definition]{So What is Treatment Learning?}
\vspace{-5mm}
{\footnotesize
\begin{center}
\includegraphics[width=2.4in]{block.eps}\newline
 $34 \le height < 86\;\wedge 3.9 \le mean\_tr <9.5$
\end{center}

~\hrule~

~\\

\bi
\item
$E$: training data with examples of  $R_i \rightarrow C$
\bi
\item
$R_i$:  attribute ranges
\item
$C$: classes with  utilities $\{U_1 < U_2 < .. < U_C\}$
\item
$F_1\%,F_2\%, ..., F_C\%$: frequencies of $C$ in $E$
\ei
\item
$T$ treatment of size $X$:  $\{R_1 \wedge R_ 2 ... \wedge R_X\}$;
\bi
\item 
$T \cap E \rightarrow e \subseteq E$ with frequencies
$f_1\%,f_2\%, ... f_C\%$
\item
seek smallest $T$ with largest $lift=\left(\sum_C U_Cf_C\right)/\left(\sum_C U_CF_C\right)$
\ei
\item This talk: 
\bi
\item Implementation, examples, a new scale-up method
\ei
\ei
}
\end{slide}



%% \begin{slide}{Who Cares About Minimality?}
%% {\footnotesize
%% \bi
%% \item Ockham's razor: (1280--1349):\newline
%% ``Pluralitas non est ponenda sine
%% neccesitate''.
%% \item \cite{wallace68}'s minimum descripton length (MDL)% and \cite{rissanen78}'s
%% %minimum message length (MML)
%% \bi
%% %\item (See \cite{bax95} for  MDL vs MML.)
%% \item Theory $T$ of length $L[T]$ 
%% has errors
%%  $L[E|T]$ on training data $E$   
%% \item MDL: the best theory minimizes $L[T] + L[E|T]$
%% \item So, don't complicate theories just to handle a few more examples
%% \ei
%% \item \cite{miller02}: subset selection in regression
%% \item Feature subset selection 
%%  discarding attributes improves accuracy\newline
%% (e.g. \cite{kohavi97}, \cite{hall03}):

%% ~\\

%% \begin{center}
%% \includegraphics[width=3in]{attr.eps}
%% \end{center}
%% \ei}
%% \end{slide}


\tsectionandpart{In practice...}

\begin{slide}[toc=Algorithm]{The TAR3 Treatment Learner}
{\scriptsize
\vspace{-5mm}
\begin{minipage}{1.7in}
\vspace{0pt}
\bi
\item
Assume clumps and collars
\bi
\item Just thrash around some.
\ei

~\\

\item Build treatments \newline
$\{R_1 \wedge R_ 2 ... \wedge R_X\}$
of size $X$
\bi
\item
FIRST try $X=1$
\item
THEN use the $X=1$ results\newline
to guide the $X>1$ search.
\ei

~\\

\item
\cite{ying02} :: grow {\em treatments}\newline
via a  stochastic  search.
\bi
\item Discretization: equal\newline
frequency binning
\ei

~\\
\item Empirically:
\bi
\item Run times linear on treatment\newline 
SIZE, number
of examples 
\item Works as well as TAR2's\newline complete search 
\ei
\ei
\end{minipage}~~~~~~\begin{minipage}{0.cm}\includegraphics[width=0.25pt,height=2.5in]{blackdot.eps}\end{minipage}~~~~~~~\begin{minipage}{1.9in}
\vspace{-1mm} {\fontsize{6}{6}
\begin{alltt}

{\bf function ONE}({x} = random(SIZE) ) 
   {x} timesDo
      {treatment} = {treatment} + {\bf ANYTHING()}
   {\bf return} {treatment}

{\bf function ANYTHING}() 
   {\bf return} a random range from CDF(lift1)

{\bf function SOME}()
   REPEATS timesDo 
      {treatments} = {treatments} + {\bf ONE()}
   sort {treatments} on lift
   {\bf return} ENOUGH top items

{\bf function TAR3}({lives} = LIVES )
   {\bf for} every range r {\bf do} {lift1[r]}= lift({r}) 
   {\bf repeat}
     {before} = size({temp})
     {temp}  = union({temp}, {\bf SOME()})
     {\bf if} ({before}==size({temp}))
     {\bf then} {lives}-- 
     {\bf else} {lives} = LIVES
   {\bf until} {lives} == 0
   sort {temp} on lift;
   {\bf return} ENOUGH top items
\end{alltt}}
\end{minipage}

~\\
~\hrule~\\

\begin{center}
Useful defaults: $<$SIZE=10, REPEATS=100, ENOUGH=20, LIVES=5$>$
\end{center}}
\end{slide} 

%% \begin{slide}{Some Comments}
%% {\footnotesize
%% \bi
%% \item
%% TAR3's random search finds (nearly) the same\newline treatments as TAR2's complete search
%% \item
%% TAR2:
%% \bi
%% \item tried all combinations of attributes with lift > threshold.
%% \item runtimes exponential on treatment SIZE
%% \ei
%% \item TAR3: 
%% \bi
%% \item runtimes linear on:
%% \bi
%% \item number of examples,
%% \item
%%  number of attributes,
%% \item
%%  treatment SIZE
%% \ei
%% \ei
%% \item
%% TAR2, TAR3
%% \bi
%% \item
%% Most domains have  very
%% ranges with very high/low lifts;
%% \ei
%% \ei
%% }
%% \end{slide}
\begin{slide}{Saving the World}
{\footnotesize
\vspace{-5mm}
``Limits to Growth'' ::  \cite{mead72}

A second look at ``Limits to Growth'': \cite{gel03a}

Vensim's World-3 (1991): 295 variables
 
~\\

\begin{minipage}{2.5in}\includegraphics[width=2.5in]{MODEL.eps}\end{minipage}
\begin{minipage}{1.25in}
\includegraphics[width=1.25in]{J48TREE.eps}
\includegraphics[width=1.25in]{LIFE.eps}
\end{minipage}

~\\~\\


Happily ever after if
\bi
\item
family size $\le$ 2,
menstruation onset $>$ 18,
industrial capital output = [3..5).
\item
This happy ending is {\em not} mentioned in \cite{mead72}.
\ei
}
\end{slide}
\begin{slide}[toc=Compare]{Compared with More Complete Search}
{\footnotesize
\bi
\item
DDP requirements models from deep-space missions (from JPL).
\item
Iterative learning: $simulation_i \rightarrow learn \rightarrow constrain \rightarrow simulation_{i+1}$
\ei

~\\

{\[
SA = \frac{\frac{benefit}{maxBenefit} + \left(1 - \frac{cost}{maxCost}\right)}{\left(2
*
\begin{array}{c}\mbox{number of}\\
\mbox{selected mitigations}
\end{array}\right)+1}
\]}
\begin{center}
%\begin{minipage}{.49\linewidth}
\includegraphics[width=1.6in]{../bore/june1/cobargand.eps}
%\end{minipage}
%\begin{minipage}{.49\linewidth}
%\includegraphics[width=1.6in]{cobrx.eps}
%\end{minipage}

TAR3: 7*300 samples

SA: 9*3000 samples
\end{center}

}
\end{slide}


\begin{slide}{Learns Very Tiny Theories}
{\footnotesize
\vspace{-5mm}
\bi
\item Compare with  feature subset selection: \cite{hall03}
\item
For each class $c \in C$
\bi
\item 
Give $c$ the largest utility $U_c$.
\item
Find treatments for $c$
\ei
\item
$Selected$ =
all attributes in  treatments
for all $c \in C$.
\item
$Accuracy$= $selected$'s 
performance in some {\em target learner}.
\item \cite{me03o}
\ei
}

~\\

\dualslide{colsep=20pt,lcolwidth=0.35\linewidth,rcolwidth=0.6\linewidth}{
{\tiny
\begin{tabular}{|c@{~}|c@{~}|c|}\hline
   &\% of attributes& accuracy\\
domain   &ignored     &improvement\\\hline
Anneal & 81.6\%&2.66\%\\
credit-g  &  75.0\%&2.17\%\\
Soybean &54.3\%&0.65\%\\
vote   & 62.5\%&0.21\%\\
breast-c &  77.8\%&0.00\%\\
Segment &78.9\%&-0.51\%\\
Ionosphere & 94.1\%&-0.90\%\\
Diabetes   & 87.5\%&-2.28\%\\
lymph  & 83.3\%& -2.75\%\\
HorseColic & 90.9\%& -4.45\%\\\hline
average&78.6\%&-1.13\%\\\hline
\end{tabular}
}
}{
{\tiny
\begin{tabular}{|l@{~}r@{~}|r@{~}|r@{~}|r@{~}|r@{~}|r@{~}|r@{~}|r|}\hline
\multicolumn{9}{|c|}{\#attributes selected (target learner = C4.5)}\\\hline
&original&ig&cfs&cbs&rlf&wrp&pc&select\\\hline
Soybean&35&19&24&35&32&19&30&$\blacktriangleright$ 16\\
Anneal&38&17&21&15&20&18&36&$\blacktriangleright$ 7\\
vote&16&12&10&$\blacktriangleright$ 6&11&9&11&$\blacktriangleright$ 6\\
credit-g&20&8&7&8&9&8&$\blacktriangleright$ 4&5\\
Segment&19&16&12&9&13&9&16&$\blacktriangleright$ 4\\
lymph&18&6.8&5.3&4&4&6&9&$\blacktriangleright$ 3\\
breast-c&9&4&4&7&7&4&4&$\blacktriangleright$ 2\\
Horse colic&22&4&4&$\blacktriangleright$2&3&5&3&$\blacktriangleright$ 2\\
Ionosphere&34&12&7&9&9&7&10&$\blacktriangleright$ 2\\
Diabetes&8&33&3&4&4&4&6&$\blacktriangleright$1\\
\hline
\end{tabular}
}}
\end{slide}

\tsectionandpart{Scaling Up}
\begin{slide}{TAR3 is not a Data Miner}
{\footnotesize
The data mining desiderata :: \cite{bradley98scaling}:
 \bi
\item Requires one scan, or less of the data
\item On-line, anytime algorithm
\item Suspend-able, stoppable, resumable
\item Efficiently and incrementally add new data to existing models
\item Works within the available RAM
\ei

~\\
TAR3 is {\em not} a data miner
\bi
\item Stores all examples in RAM
\item
Requires at  three scans
\be
\item
discretization
\item
 collect statistics, build treatments
\item
rank generated theories
\ee
\ei
}
\end{slide}
\begin{slide}[toc=SAWTOOTH]{SAWTOOTH is a data miner}
{\scriptsize
\begin{minipage}{2in}
\vspace{-10pt}
SAWTOOTH= incremental N\aive Bayes classifier \cite{me05b}
\bi
\item
Exploits the ``saturation effect'': 
\bi
\item
Learners performance
improves and  plateaus, after 100s of examples
\item Processes data in chunks (window = 250)
\item Disables learning while performance stable
\ei
\item One-pass through the data 
\bi
\item Incremental discretization of numeric data (SPADE)
\item Input each example, converted to frequency counts, then deletes
\ei
\item Results
\bi
\item Small memory; scales.
\item Recognizes and reacts to concept drift
\ei
\item Can we model treatment learning as a N\aive Bayes classifier?
\ei
\end{minipage}\begin{minipage}{2in}
\vspace{-10pt}
{\scriptsize
\begin{center}
\includegraphics[height=1.4in]{recurrent.eps}

\includegraphics[height=1.4in]{kdd.eps}
\end{center}
}
\end{minipage}
}
\end{slide}\begin{slide}{N\aive Bayes classifiers}

{\scriptsize
\vspace{-10mm}

\[
\mbox{evidence $E$, hypothesis $H$}\;\;\;\;\;\;\;\;\; \overbrace{P(H|E)}^{future=}
= \overbrace{\left(\prod_i{P(E_i|H)}\right)}^{now*} 
* \frac{\overbrace{P(H)}^{past}}{P(E)}
\] 
\begin{center}
{\tiny
\begin{tabular}{|c@{~}|c@{~}c@{~}c|}\hline
 & $E_1$ & $E_2$& $E_3$\\\hline 
$H=car$&job&suburb&wealthy?\\\hline
ford   &tailor&\aaa&y\\
ford&tailor&\bbb&n\\
ford&tinker&\bbb&n\\\hline
bmw    &tinker&\aaa&y\\ 
bmw&tinker&\aaa&y\\
bmw&tailor&\aaa&y\\\hline
\end{tabular}~~~~\begin{tabular}{|c@{~}|c@{~}|c@{~}|c|}\hline  
& \multicolumn{3}{c|}{$P(E_i|H)$}\\
P(H)&job&suburb&wealthy?\\\hline
ford:3=0.5 & tinker:1=0.33&\aaa:1=0.33&y:1=0.33\\
           & tailor:2=0.67&\bbb:2=0.67&n:2=0.67\\\hline
bmw:3=0.5  & tinker:2=0.67&\aaa:3=1.00&y:3=1.00\\
           & tailor:1=0.33&\bbb:0=0.00&n:0=0.00\\\hline
\end{tabular}}
\end{center}
\vspace{1mm}
\bi
\item $E$ = job=tailor \& suburb=\aaa
\item likelihood = $L(bmw|E)$ = $\prod_i P(E|bmw)*P(bmw)$ =0.33*1.00*0.5 =0.16500
\item $L(ford|E)$ = $\prod_i P(E|ford)*P(ford)$ =0.67*0.33*0.5 =0.11055
\item $Prob(bmw|E) = \frac{L(bmw|E)}{L(bmw|E) + L(ford|E)}$  = 59.9\%
\item $Prob(ford|E) = \frac{L(ford|E)}{L(bmw|E) + L(ford|E)}$ = 40.1\%
\item So our tailor drives a $bmw$
\item N{\aive}: assumes independence;  counts single attribute ranges (not combinations)
\bi
\item But optimal under the one-zero assumption \cite{domingos97optimality}.
\item Incremental
simple,  fast 
 learning/classification speed, low storage space.
\ei
\ei
}
\end{slide}

%% {\scriptsize
%% \begin{tabular}{|l@{~}|p{1.1in}|@{~}l@{~}|c@{~}|c@{~}|c@{~}|c@{~}|c}\hline
%% case&E&P(E)&P(bmw)&P(ford)&$$&$\prod_i P(E_i|ford)$\\\hline
%% 1&job=tailor \& suburb=a&?&0.50&0.50&0.33*1=0.33&0.67*0.33=0.22\\\hline
%% 2&job=tailor \& suburb=a \& wealthy?=y&?&0.50&0.50&0.33*1*1=0.33&0.67*0.33*0.33=0.07\\\hline
%% \end{tabular}

%% ~\\~\\

%% \begin{tabular}{|l@{~}|c@{~}|c@{~}|c|}
%%     &      $P(bmw|E)=$                           &        $P(ford|E)=$                  &\\
%% case&$\prod_i P(E_i|bmw)*\frac{P(bmw)}{P(E)}$&$\prod_i P(E_i|ford)*\frac{P(ford)}{P(E)}$\\\hline
%% 1&61\%&39\%\\\hline
%% 2&81\%&19\%
%% \end{tabular}

\begin{slide}{CUBE \& TAR4}
\vspace{-8mm}
{\scriptsize
\begin{center}
{\tiny
\begin{tabular}{c@{~}|c@{~}|c@{~}|c@{~}|c@{~}|c@{~}|c}\hline
%& $U_1$ &&& $U_2$\\
%& minimize & & & maximize& \\
  outlook&$U_1$: minimize temperature&humidity&windy&$U_2$: maximize play&$up_i$ & $down_i$\\\hline
  overcast&64&65&TRUE&yes=1&1.00&0\\
  rainy&68&80&FALSE&yes=1&0.87&0.13\\
    ...&...&...&...  &...  &...&...\\
  sunny&80&90&TRUE&no=0&0.11& 0.89\\
  sunny&85&85&FALSE&no=0&0.00& 1\\\hline
\end{tabular}}\end{center}
\bi
\item
Examples are placed in a $U$-dimensional
hypercube (one dimension for each utility):
\bi
\item apex = best =  \{1,1,1,1...\}; 
\item base = worst = \{0,0,0,0,...\}
\ei
\item
$example_i$ has distance $0 \le D_i \le 1$ from apex (normalized by $U^{0.5}$)
\item
Each range $R_j\in example_i$  adds  \newline $down_i=D_i$ and $up_i= 1 - D_i$ to
  $F(R_j|base)$ and $F(R_j|apex)$.
\ei
\[\begin{array}{rcl}
P(apex)& =& \sum_i up_i/\left(\sum_i up_i + \sum_i down_i\right)\\
P(base)& =& \sum_i down_i/\left(\sum_i up_i + \sum_i down_i\right)\\
P(R_j|apex)&=& F(R_j|apex)/\sum_i up_i\\
P(R_j|base)&=& F(R_j|base)/\sum_i down_i \\
L(apex|R_k \wedge R_l \wedge ...)&=&\prod_x P(R_x|apex) * P(apex)\\
L(base|R_k \wedge R_l \wedge ...)&=&\prod_x P(R_x|base) * P(base)
\end{array}\]
TAR4.0: Bayesian treatment learner = find the {\em smallest} treatment $T$ that {\em maximizes}:
\[P(apex|T)=\frac{L(apex|T)}{L(apex|T) + L(base|T)} \mbox{~~~~~~~~~~; didn't work: out-performed by TAR3}\]
}
\end{slide}


\begin{slide}{Why did TAR4.0 fail?}
{\footnotesize
\bi
\item
Hypothesis: muddled-up by dependent attributes;
\item
 ``N\aive'' Bayes: assume independence, keeps {\em singleton} counts.

{\scriptsize
\begin{tabular}{|c@{~}|c@{~}c@{~}c|}\hline
 & $E_1$ & $E_2$& $E_3$\\\hline 
$H=car$&job&suburb&wealthy?\\\hline
ford   &tailor&\aaa&y\\
ford&tailor&\bbb&n\\
ford&tinker&\bbb&n\\\hline
bmw    &tinker&\aaa&y\\ bmw&tinker&\aaa&y\\bmw&tailor&\aaa&y\\\hline
\end{tabular}~~~\begin{tabular}{|p{2cm}@{~}|c@{~}|c|}\hline
$E$                                  & P(bmw|E) & P(ford|E) \\\hline
$job=tailor$ \& \newline $suburb=\aaa$             & 59.9\%      &   40.1\%\\\hline
$job=tailor$ \& \newline $suburb=\aaa$ \& \newline $wealthy=y$ & 81\%        &   19.0\%\\\hline
\end{tabular}}

\item Adding redundant information radically changes probabilities? Bad!
\item
Note: gets class probabilities WRONG, but
RANKS  classes correctly \cite{domingos97optimality}
\item
We asked TAR4.0 to do what you must never do: 
\bi
\item
compare numeric of probabilities of the same class in N\aive Bayes.
\ei
\ei
}

\end{slide}
\begin{slide}{TAR4.1}\vspace{-10mm}
{\scriptsize
\begin{minipage}{2.5in}
\bi
\item
Prune treatments with low support in the
data.
\item What does ``support'' mean?
\bi
\item
Maximal when includes all examples from a class
\item
$0 \le support \le 1$
\item $support = likelihood =  \prod_x P(R_x|H) * P(H)$
\ei

~\\

\item $probability * support = \frac{L(apex|E)^2}{L(apex|E) + L(base|E)}$

~\\

\item Worked! 
\bi
\item Much  faster, less memory than TAR3:
\bi
\item
No need for a second scan
\item
No need to hold examples in RAM
\ei
\item Bayesian guess-timate for  $support$
of best class (almost) the same as TAR3
\item No connection treatment size to  guess-timate error.
\ei

~\\

\item But why did it work so well?
\ei
\end{minipage}\begin{minipage}{1.5in}
\vspace{0pt}
\begin{center}
less memory 

\includegraphics[height=1in]{tar3tar4mem.eps}

faster, less variance

\includegraphics[height=1in]{tar3tar4time.eps}

lift errors small
 
\includegraphics[height=0.6in]{tar3tar4error.eps}
\end{center}
\end{minipage}
%% {\tiny
%% \begin{center}
%% \begin{tabular}{|r@{~}|r@{~}|r@{~}|r@{~}|r@{~}|}\hline
%% &\multicolumn{2}{c|}{Support for}
%% &\multicolumn{2}{c|}{}\\


%% &\multicolumn{2}{c|}{best treatment}
%% &\multicolumn{2}{c|}{}\\\cline{2-5}

%% &\multicolumn{2}{c|}{$P(E|heaven)*P(heaven) *$}
%% &\multicolumn{2}{c|}{\% of best }\\

%% &\multicolumn{2}{c|}{$\#examples$}
%% &\multicolumn{2}{c|}{class selected}\\\cline{2-5}

%% dataset& TAR3 & TAR4.1 & TAR3 & TAR4.1\\\hline
%% Vote&     108&        113&	95\%&	95\%\\
%% Splice&     442&        442&	95\%&	95\%\\
%% Breast Cancer&     69&        69&	100\%&	100\%\\
%% Mushroom&      2720&        2160&	95\%&	100\%\\
%% Kr-vs-Kp&       743&        891&	100\%&	76\%\\
%% Waveform&       435&        770&	83\%&	79\%\\
%% Diabetes&       123&        46&	66\%&	85\%\\
%% Sonar&      28&        22&	89\%&	91\%\\
%% Hepatitis&     42&        47&	100\%&	98\%\\
%% Contacts&     12&        12&	100\%&	100\%\\\hline
%% \end{tabular}
%% \end{center}}
}
\end{slide}

\begin{slide}[toc=Pre-condition]{When Won't Dependencies Confuse TAR4?}
{\scriptsize
\bi
\vspace{-2mm}
\item
$T' = T + t$ where
 $t$ is an attribute dependent on members of $T$;
\item
TAR4.1 {\em not}  confused by $t$ when it ignores treatments that use it.

\[\begin{array}{rcl}
a=&L(apex|T')=& \overbrace{P(t|apex)}^{x} * \prod_i P(T_i|apex) *  P(apex)\\                                    
b=&L(base|T')=& \underbrace{P(t|base)}_{y} * \prod_i P(T_i|base) * P(base)
\end{array}\]
\item
Then  when is  $support*probability$  increased by ignoring
$x$ and $y$? \newline
{\tiny
\begin{minipage}{2in}
\[
\left(\overbrace{\frac{(a/x)^2}{a/x + b/y}}^{\mbox{ignoring $x$ and $y$}}
>
\overbrace{\frac{a^2}{a + b}}^{\mbox{using $x$ and $y$}}\right)
\Longrightarrow y >                                                                                                                    \frac{bx^2}{b+a-xa}
\]
\end{minipage}~~~~~\begin{minipage}{2in}
\includegraphics[width=2in]{plot_00001.eps}
\end{minipage}}
\item
And for TAR4.0:s pre-condition for no confusion:
$
\frac{(a/x)}{a/x + b/y}
>
\frac{a}{a + b}
$
\ei
}
\end{slide}



%XXX results assume finding both. forward select should do it
%    that forward select might be fast++ (no backtracking required)

% needs notes on the hypercube

% conclusion: best to view treatment learning as a variant of bayes classifier
%  to learn simple theories, assume data comes from models with a few
%  master variables

% leads to very simple implementations


%% \begin{minipage}{2in}
%% \begin{tabular}{l@{~}|c@{~}c@{~}|c@{~}|c}
%%          &\multicolumn{2}{c|}{attributes}\\
%% data set & discrete& continuous & instances & classes\\\hline
%% weather: & 2 & 2 & 14 & 2\\
%% iris: & 4 & 0 & 150 & 3\\
%% housing: & 1 & 12 & 506 & 2\\
%% vowel: & 3 & 10 & 990 & 11\\
%% kc2: & 0 & 17 & 520 & 2\\\hline
%% av & 2.5 & 6 & 415 & 4
%% \end{tabular}
%% \end{minipage}

\begin{slide}[toc=Typical values]{Typical  Values and Constraints:: 
$\frac{(a/x)^2}{a/x + b/y}$} 

\vspace{-12mm}{\scriptsize
\begin{center}
\[\begin{array}{cl}
0 < i \le 20 & \mbox{; treatment size}\\\hline
b <  a & \mbox{; {\em apex} is better than {\em base}}\\\hline
10^{-10} < x \le y \le 0.25 & \mbox{; see graphs}\\\hline
0 < a \le x^{i} \le x \le 0.25 & \mbox{; {\em a} combines many {\em x}-like numbers} \\\hline
0 < b \le y^{i} \le y \le 0.25 & \mbox{; {\em b} combines many {\em y}-like numbers} \\
\end{array}\]


\includegraphics[width=2.6in]{plots3.eps}

\includegraphics[width=2.6in]{plotsBL.eps}

\end{center}}
\end{slide}
\begin{slide}{TAR4.1 Works}
\vspace{-10mm}
{\scriptsize
\bi
\item Pick \{a,b,x,y,i\} at random within typical values; reject
those violate our constraints;
\item Check pre-conditions; report rounded $log_{10}$ values;
\item TAR4.0: not confused when $\left(\frac{(a/x)}{a/x + b/y} >
\frac{a}{a + b}\right)$ \newline\vspace{3mm} {\tiny
~~~~~~~~~~~~~~~~~~~~~\begin{barenv} \setstyle{\sffamily} \setwidth{10}
\sethspace{0.8}\hlineon\setlinestyle{dotted}
\setnumberpos{none} \setstretch{0.5} \setyaxis{0}{100}{25}
\setxaxis{-10}{-1}{1}
\setxname{$log_{10}(x)$}
\setyname{\% not confused (in 10,000 runs)}
\bar{100}{8} %-11                                                                                                                            
\bar{100}{8} %-10                                                                                                                            
\bar{97}{8} %-9                                                                                                                              
\bar{91}{8} %-8                                                                                                                              
\bar{81}{8} %-7                                                                                                                              
\bar{67}{8} %-6                                                                                                                              
\bar{53}{8} %5                                                                                                                               
\bar{45}{8} %4                                                                                                                               
\bar{30}{8} %3                                                                                                                               
\bar{21}{8} %8                                                                                                                               
\end{barenv}} Often confused.\vspace{10mm}

\item TAR4.1: not confused when $\left(\frac{(a/x)^2}{a/x + b/y} >
\frac{a^2}{a + b}\right)$\newline\vspace{3mm}
{\tiny~~~~~~~~~~~~~~~~~~~~~\begin{barenv}
\setstyle{\sffamily} \setwidth{10}
\sethspace{0.8}\hlineon\setlinestyle{dotted}
\setnumberpos{none} \setstretch{0.5} \setyaxis{0}{100}{25}
\setxaxis{-10}{-1}{1}
\setxname{$log_{10}(x)$}
\setyname{\% not confused (in 10,000 runs)}
\bar{100}{8} %-10                                                                                                                            
\bar{100}{8} %-9                                                                                                                             
\bar{100}{8} %-8                                                                                                                             
\bar{100}{8} %-7                                                                                                                             
\bar{100}{8} %-6                                                                                                                             
\bar{100}{8} %5                                                                                                                              
\bar{99.9}{8} %4                                                                                                                             
\bar{98.1}{8} %3                                                                                                                             
\bar{92.6}{8} %8                                                                                                                             
\bar{84.2}{8} %9                                                                                                                             
\end{barenv}} Rarely confused.
\ei





 }
 \end{slide}
\begin{slide}{So What?}
{\footnotesize
\bi
\item Mathematically, TAR4.0  will always  fails (except for  $x\ll 1$);
\item
TAR4.1 succeeds since pre-condition is usually satisfied
\bi
\item In
96.52\% of
our simulations
\ei
\item
So, theoretically and empirically:
\bi
\item Bayesian treatment learning with CUBE can guess effect of treatments
using frequency counts, 
\item
Does not need a second scan of the data (providing you use $support*probability$)
\item
Now we have a data miner TAR4.1.
\ei
\item By the way, 
\bi
\item No need for Bayes nets in this domain
\item Why doesn't this mean that treatments will {\em never} grow beyond size=1?
\ei
\ei}
\end{slide}

\begin{slide}{But Why Big Treatments?}
{\footnotesize
\vspace{-5mm}
\bi
\item When are larger treatments acceptable; i.e.  $\left(\frac{(a/x)^2}{a/x + b/y} <
\frac{a^2}{a + b}\right)$?
\item When is $y <                                                                                                                    \frac{bx^2}{b+a-xa}$.

\begin{center}
\includegraphics[width=2.5in]{plot_00001.eps}
\end{center}

\item When $x$ is large and $y$ is much smaller than $x$
\item i.e. 
when some attribute ranges has a  high frequency in the apex 
{\em and} a much lower  frequency in the base.
\item If  collars then such ranges are not common; i.e.  dependencies unlikely.
%XXX tufte
% XXX langeley forward select
\ei}
\end{slide}
%\input{part0}
%\input{part1}
%\input{part2}
%\input{part3}

%% \begin{slide}{Related Work}
%% {\scriptsize
%%  \bi
%%  \item 
%%  Data mining is a {\em huge} field. Drawn to TAR4 due to its simplicity, 
%%  fast 
%%  learning
%%  speed,fast  classification speed, low storage space, incremental nature.
%% \item TAR2: too slow; TAR3: faster, but won't scale
%%   \item
%%  Optimality of Bayes classifiers under the 0-1 assumption demonstrated previously
%% \bi
%% \item Our conclusions are more specific.
%% \item
%% I.E. a situation that might confuses TAR4 rarely happens  in practice.
%% \ei
%% \ei
%% \item
%% Our work can be framed in MDL terms (Bayes Theorem can be re-written as MDL)
%% \ei
%%  }
%% \end{slide}
\tsectionandpart{Related Work}
\begin{slide}{References}
%\vspace{-1cm}
{\scriptsize
\bi
\item SAWTOOTH
\bi
\item \bibentry{me05b}

~\\

\ei
\item Treatment learning
\bi
 \item \bibentry{clark05}
\item \bibentry{gel03a}
\item \bibentry{ying02}
\item \bibentry{me03o}
\item \bibentry{me02a}
\item \bibentry{me03c}
\ei
\ei}
\end{slide}
\begin{slide}{References (2)}
\scriptsize%\vspace{-1cm}
\bi
\item Phase transition
\bi
\item \bibentry{hoos98}
\item \bibentry{mitchell92hard}
\ei

~\\

\item Contrast set learners
\bi
 \item \bibentry{bay99}
 \item \bibentry{cai98}
\ei
\ei
\end{slide}
\begin{slide}{References (3)}
\scriptsize%\vspace{-1cm}
\bi
\item Collars and clumps
\bi
 \item \bibentry{crawford94}
 \item \bibentry{deKleer86}
\item \bibentry{druzdel94}
\item \bibentry{pelanek04}
\item \bibentry{williams03}
\ei

~\\

\item Data mining
\bi
\item \bibentry{bradley98scaling}
\item \bibentry{domingos00mining}
\ei
\ei
\end{slide}
\begin{slide}{References (4)}
\scriptsize
\bi
\item Feature subset selection
\bi
\item \bibentry{hall03}
\item \bibentry{kohavi97}
\item \bibentry{miller02}
\ei

~\\

\item Why Does N\aive Bayes Work?
\bi
\item \bibentry{langley94}
\item \bibentry{domingos97optimality}
\ei
\ei
\end{slide}

\begin{slide}{References (5)}
\scriptsize
\bi
\item Machine learning
\bi
\item \bibentry{quinlan92}
\ei

~\\

\item Misc
\bi
\item \bibentry{mead72}
\ei

~\\

\item MDL \& MML
\bi
\item \bibentry{wallace68}
 \item \bibentry{bax95}
\ei


\ei
\end{slide}

\tsectionandpart{And so...}

\begin{slide}{Success Despite Complexity}
{\footnotesize
\bi
\item Maybe....
\bi
\item  The world is not as complex as we thing
\item Real world models clump, have collars.
\item Possible to quickly search, find ways to select for preferred states.
\ei
\item Ultimately, this is an empirical study.
\bi
\item Q: When does a clumping/collaring-inspired search engine succeed?
\item A: Often
\bi
\item Reports effects never seen before (limits to growth)
\item Finds solutions faster than other methods (JPL).
\item Returns tiniest theories (fss)
\item Scales to infinite data streams (TAR4.1)\ei
\ei
\item Many applications. May I try this on your problems?
\ei
}
\end{slide}

\begin{slide}{A Final Word}
{\footnotesize
\bi
\item
Sometimes the world is complex:
\bi
\item
2\% optimizing air-flow over leading wing in trans-sonic range
\item
synthesis of optimized code for complex engineering problems
\ei
\item And sometimes it ain't.
\bi
\item Try the simple solution before the more complex.
\item Benchmark the complex against the seemingly less sophisticated.
\item Warning: your straw man may not burn
\ei
\ei
\begin{center}
\includegraphics[width=2in]{strawman.eps}
\end{center}}
\end{slide}

\tsectionandpart{Questions? Comments?}

\end{document}

\tsectionandpart{About SPOT}


\begin{slide}{Need a New Learner}
{\footnotesize
\bi
\item Learners usually optimized for {\em accuracy}.
\item {\em SPOT} is a {\em covering algorithm} optimized for $\frac{PD}{effort}$.
\item
Onion returns least effort rules (conjunctions of size one).
\ei

{\tiny\begin{center}
\begin{minipage}{.33\linewidth}
\begin{tabular}{c@{}|c@{}|c@{}|c|}
\multicolumn{2}{c}{}&\multicolumn{2}{c}{defect?}\\\cline{3-4} 
\multicolumn{2}{c|}{}&no&yes\\\cline{2-4}
 signal  &no &a &b\\\cline{2-4}
detected?&yes&c &d\\\cline{2-4}
\end{tabular}
\end{minipage}
\begin{minipage}{.74\linewidth}
\begin{tabular}{c@{}|c@{}|c@{}|c|}
\multicolumn{2}{c}{}&\multicolumn{2}{c}{defect?}\\\cline{3-4} 
\multicolumn{2}{c|}{}&no&yes\\\cline{2-4}
 signal  &no &$LOC_a$ &$LOC_b$\\\cline{2-4}
detected?&yes&$LOC_c$ &$LOC_d$\\\cline{2-4}
\end{tabular}
\begin{tabular}{l}
support~=~$\frac{c+d}{a+b+c+d}$\\~\\
effort~=~$\frac{LOC_c + LOC_d}{LOC_a + LOC_b + LOC_c + LOC_d}$
\end{tabular}
\end{minipage}
\end{center}}
{\scriptsize
\begin{alltt}


{\bf FUNCTION} best(a,b,c,d,effort) \{
  pf      =  c/(a+c)
  pd      =  d/(b+d)  
  support = (c+d)/(a+b+c+d)
  {\bf IF} ( effort >  pd  ) {\bf RETURN} 0;     #{\em avoid relatively high efforts}
  {\bf IF} ( effort >  0.1 ) {\bf RETURN} 0;     #{\em avoid high efforts}
  {\bf IF} ( pf     >  pd  ) {\bf RETURN} 0;     #{\em avoid relatively high PFs}
  {\bf IF} ( pf     >  0.1 ) {\bf RETURN} 0;     #{\em avoid high PFs}
  {\bf IF} ( !(pf+effort)  ) {\bf RETURN} 0;     #{\em avoid non-zero PFs and efforts}
  {\bf RETURN}  support*pd*(1-effort)*(1 - pf) #{\em prefer bands covering many modules}
\}                                   #{\em high pd is good, low pf/effort hell}
\end{alltt}}}
\end{slide}



\begin{slide}{Handling Numerics}
{\footnotesize
\dualslide{topsep=-0.65cm,lcolwidth=0.68\linewidth,rcolwidth=0.3\linewidth,lineheight=7.5cm}{
\bi
\item
Data skewed: small number of very large modules.
\bi
\item So replace numeric $N$ with $log(N)$
\item
Intoduces
problem with zero values
(infinitely negative log values);
\item 
So if  $N < SmallValue$ then $N\leftarrow SmallValue$\newline
(default
$SmallValue\leftarrow 0.005$).
\ei
\item
Problems with  threshold values; 
\bi
\item
e.g. $v(g)\le10$ selects
for too many big modules (large effort)
\item
So work with {\em bands}, not {\em thresholds}; 
\item e.g. 
not $v(g)\ge10$ but, e.g. $4.5 \le v(g) < 6$.
\ei
\item
Simple $N$  banding  for numeric attribute $i$.
\bi
\item band $width(i) \leftarrow \frac{log(max(i))- log(min(i))}{bins}$
(default bins=10).
\item replace numeric values $N$ for attribute $i$
with $integer\left(\frac{(log(N) - log(min(i)))}{width(i)}\right)$.
\ei
\item
Replace ``missing'' with $integer(bins/2)+1$;
\ei
}{
Before:\\~\\
\includegraphics[width=1.3in]{12before.eps}


After: logged, binned\\~\\
\includegraphics[width=1.3in]{12after.eps}
}}
\end{slide}
 
 
\begin{slide}{See SPOT Run}
{\footnotesize
\dualslide{topsep=-0.65cm,lcolwidth=0.68\linewidth,rcolwidth=0.3\linewidth}{
\be
\item Log and bin the numerics
\item Repeat
\be
\item
Find the ``best'' band;
\item
Print that band;
\item
Peel off (delete) the instances with that band
\item
Until no more best bands.
\ee
\item
Report the effects of using band 1; band 1 and 2; band 1 and 2 and 3;...
\ee
}{\includegraphics[width=1in]{Neubecker_SeeSpotRun.eps}}
{\tiny\vspace{5pt}
\hrule
\begin{verbatim}
    01.     band 1:: lOComment($14 >= 1.16 && $14 < 2.88)
    02.     band 2:: i($9 >= 0.46 && $9 < 1.44)
    03.     band 3:: branchCount($21 >= 3.25 && $21 < 5.85)
    04.     band 4:: lOComment($14 >= 7.15 && $14 < 17.74)
    05.     band 5:: ev(g)($3 >= 4.26 && $3 < 6.90)  
            ...
    17.     what,                  pf,     acc,    prec,      pd,  effort,  pd/effort
    18.     ----,                  --,     ---,    ----,      --,  ------,  ---------
    19.     use the first  1        5       78       38       11        8      132
    20.     use the first  2        5       78       39       12        8      143
    21.     use the first  3       12       74       30       19       14      138
    22.     use the first  4       13       75       37       28       21      130
    23.     use the first  5       14       76       43       40       29      139
            ...
\end{verbatim}
\hrule}
\vspace{5pt}
Note: can customize $effort$; i.e. to inspect less, use less bands.
}
\end{slide}

\begin{slide}[toc=SPOT results]{SPOT, 10-way holdouts;  4 datasets}
{\footnotesize
\dualslide{topsep=-0.65cm,lcolwidth=0.28\linewidth,rcolwidth=0.7\linewidth,lineheight=7.5cm}{
Results sorted by number of bands used in the detector,
then by effort.
~\\

\bi
\item[\ding{52}]
$\frac{PD}{effort}>1$ 
\item[\ding{52}]
effort can be tuned to available resources.
\item
PFs:
\bi
\item 
Use of more bands increases PF.
\item[\ding{56}] CM1,KC1 $PF \approx effort$
\item[\ding{52}] KC2,PC1 $PF < effort$
\ei
\ei
}{
{\tiny
\begin{tabular}{l@{}l@{}l@{}l}
\includegraphics[angle=270,width=0.7in]{datasorted/cm1costed_accpfall.eps}&
\includegraphics[angle=270,width=0.7in]{datasorted/kc1costed_accpfall.eps}&
\includegraphics[angle=270,width=0.7in]{datasorted/kc2costed_accpfall.eps}&
\includegraphics[angle=270,width=0.7in]{datasorted/pc1costed_accpfall.eps}\\
\includegraphics[angle=270,width=0.7in]{datasorted/cm1costed_all.eps}&
\includegraphics[angle=270,width=0.7in]{datasorted/kc1costed_all.eps}&
\includegraphics[angle=270,width=0.7in]{datasorted/kc2costed_all.eps}&
\includegraphics[angle=270,width=0.7in]{datasorted/pc1costed_all.eps}\\
\includegraphics[angle=270,width=0.7in]{datasorted/cm1costed_solutionpdvseffort_av_all.eps}&
\includegraphics[angle=270,width=0.7in]{datasorted/kc1costed_solutionpdvseffort_av_all.eps}&
\includegraphics[angle=270,width=0.7in]{datasorted/kc2costed_solutionpdvseffort_av_all.eps}&
\includegraphics[angle=270,width=0.7in]{datasorted/pc1costed_solutionpdvseffort_av_all.eps}
\end{tabular}}
}} 
\end{slide}

\begin{slide}[toc=SPOT results]{SPOT: try removing LOCs}
{\footnotesize
\dualslide{topsep=-0.65cm,lcolwidth=0.28\linewidth,rcolwidth=0.7\linewidth,lineheight=7.5cm}{
Results sorted by number of bands used in the detector,
then by effort.
~\\

Try removing all the lines of code measures:

\bi
\item[\ding{52}]
Some PF reduction.
\item
But it seems fundamental: the
price of higher PDs is higher PFs
\ei
}{
{\tiny
\begin{tabular}{l@{}l@{}l@{}l}
\includegraphics[angle=270,width=0.7in]{datasorted/cm1noloc_accpfall.eps}&
\includegraphics[angle=270,width=0.7in]{datasorted/kc1noloc_accpfall.eps}&
\includegraphics[angle=270,width=0.7in]{datasorted/kc2noloc_accpfall.eps}&
\includegraphics[angle=270,width=0.7in]{datasorted/pc1noloc_accpfall.eps}\\
\includegraphics[angle=270,width=0.7in]{datasorted/cm1noloc_all.eps}&
\includegraphics[angle=270,width=0.7in]{datasorted/kc1noloc_all.eps}&
\includegraphics[angle=270,width=0.7in]{datasorted/kc2noloc_all.eps}&
\includegraphics[angle=270,width=0.7in]{datasorted/pc1noloc_all.eps}\\
\includegraphics[angle=270,width=0.7in]{datasorted/cm1noloc_solutionpdvseffort_av_all.eps}&
\includegraphics[angle=270,width=0.7in]{datasorted/kc1noloc_solutionpdvseffort_av_all.eps}&
\includegraphics[angle=270,width=0.7in]{datasorted/kc2noloc_solutionpdvseffort_av_all.eps}&
\includegraphics[angle=270,width=0.7in]{datasorted/pc1noloc_solutionpdvseffort_av_all.eps}
\end{tabular}}
}} 
\end{slide}





\begin{slide}{Q: Mccabe > Halstead?}
{\footnotesize
\dualslide{lcolwidth=0.5\linewidth,colsep=2pt,rcolwidth=0.46\linewidth}{
\bi
\item[$A_1$]: it doesn't matter
\item[$A_2$]:
What's ``most important'' varies a lot.
\ei
~\\~\\
{\tiny
\begin{tabular}{r@{~}|c@{~}|r@{~}|c@{}|}
N& & N  & \\\hline
1&2.53 $\le$ ev(g) $<$ 3.44&9&2.66 $\le$ ev(g) $<$ 3.68\\
1&2.69 $\le$ ev(g) $<$ 3.74&8&2.77 $\le$ ev(g) $<$ 3.9\\
1&3.23 $\le$ ev(g) $<$ 4.78&1&3.44 $\le$ ev(g) $<$ 4.69\\
1&3.74 $\le$ ev(g) $<$ 5.2&8&3.90 $\le$ ev(g) $<$ 5.48\\
10&4.26 $\le$ ev(g) $<$ 6.9&1&4.26 $\le$ ev(g) $<$ 6.9\\
1&4.26 $\le$ ev(g) $<$ 6.9&1&5.47 $\le$ ev(g) $<$ 8.37\\
5&6.85 $\le$ ev(g) $<$ 11.09&1&6.85 $\le$ ev(g) $<$ 11.09\\
3&7.06 $\le$ ev(g) $<$ 9.78&5&11.18 $\le$ ev(g) $<$ 18.12\\
1&11.18 $\le$ ev(g) $<$ 18.12&1&11.18 $\le$ ev(g) $<$ 18.12\\
3&13.55 $\le$ ev(g) $<$ 18.77&4&15.19 $\le$ ev(g) $<$ 21.35\\
1&15.46 $\le$ ev(g) $<$ 22.87&2&17.94 $\le$ ev(g) $<$ 29.04\\
1&ev(g) $\ge$ 18.77&1&ev(g) $\ge$ 22\\
1&ev(g)$\ge$30\\
\end{tabular}}
}{
{\tiny
\begin{tabular}{r|@{~}r|@{~}r|@{~}r|@{~}r}
   &total&unique&&\\
what&thresholds&thresholds&min&max\\\cline{2-5}
ev(g)&72&24&2.53&30\\
iv(g)&49&18&1.46&21.02\\
locomment&48&7&1&56\\
branchcount&44&14&3&79\\
loc\&comment&42&8&1&19\\
v(g)&40&16&2.34&31.15\\
B&38&14&0.02&4.1\\
loblank&26&6&1&58\\
I&24&5&0.36&185.85\\
L&23&5&0.05&0.75\\
T&21&5&1&880.77\\
E&18&4&15.63&294186\\
uniq\_op&13&5&1.05&45.18\\
loc\&comment&12&3&1&5\\
uniq\_opnd&8&3&5.82&128.48\\
N&8&4&21.86&1259.92\\
V&7&5&0.32&5527.44\\
total\_op&5&4&6&237.01\\
locode&2&6&1&45\\
D&1&1&3.32&8.4\\\cline{2-5}
\end{tabular}}
}}
\end{slide}

\tsectionandpart{So\ldots}
\begin{slide}{Conclusion}
{\footnotesize
\dualslide{topsep=-0.65cm,lcolwidth=0.65\linewidth,
rcolwidth=0.34\linewidth}{
\begin{itemize}
\item
IV\&V is {\em not}  quality assurance.
\begin{itemize}
\item
Projects ensure that software works.
\item
IV\&V spot checks the projects.
\end{itemize}
\item
IV\&V is a (heavily) resource-bounded activity.
\begin{itemize}
\item
Can only review (e.g.) 25\% of the code on robotics missions.
\end{itemize}
\item Need to focus IV\&V correctly.
\bi
\item Need to perform spot checks on the things outside the focus.
\ei
\item Data miners for spot checks:
\begin{itemize}
\item Current methods demand large spot checks.
\item SPOT finds the {\em least} to review that {\em most} reveals code defects.
\end{itemize}
\item
This work:
\begin{itemize}
\item Repeatable, refutable, possibly improvable  case study
\item Focus on benefits {\em and } cost of an IV\&V tool
\item Can more research be like thiss?
\end{itemize}
\end{itemize}
}{~\\~\\~\\~\\~\\~\\~\\~\\~\\~\\
%\includegraphics[width=1.5in]{Neubecker_SeeSpotRun.eps}
}}
\end{slide}
\tsectionandpart{Questions? Comments?}



\end{document}

\begin{slide}{This talk...}
{\footnotesize
\dualslide{topsep=-0.65cm,colsep=10pt, lcolwidth=0.68\linewidth,rcolwidth=0.31\linewidth,lineheight=7.5cm}{
\bi
\item
Goal: ensure we are checking the right things.
\bi
\item Augment {\em focusing} policies (e.g. CARA)\ldots
\item \ldots with {\em spot checks} on
 rest of the system.
\ei
\item
Problem: standard data miners poor {\em spot checkers}.
\bi
\item $\uparrow$
accuracy
or $\downarrow$mis-classification cost.
\item
Not $\downarrow$ associated effort or 
$\uparrow$probability of detection (PD).
\item[\ding{56}] Often, spots too large ($effort > PD$). 
\ei 
\item Solution: SPOT, a new learner,  $\uparrow\frac{PD}{effort}$
\bi
\item
Has been tested on 40 different samples of NASA
defect data. 
\item[\ding{52}]
On average, finds small spots
($effort <0.5$ and $PD > effort$).
\item[\ding{52}]
Returns a {\em set of theories} and test engineers
can select those that best matches
the available resources.
\ei
\item
Challenge:
\bi
\item
Assess  other IV\&V methods  in the same way?
\ei
\ei}{
\begin{center}
\includegraphics[angle=270,width=1.4in]{problem_nbk_pc1.eps}\newline
e.g. Naive Bayes\newline
\includegraphics[angle=270,width=1in]{datasorted/pc1noloc_solutionpdvseffort_av_all.eps}\newline
e.g. SPOT
\end{center}
}} 
\end{slide}

\begin{slide}[toc=4 datasets * 10-way]{10-way * 4 data sets; sorted on effort}
{\footnotesize
High efforts, $average\left(\frac{PD}{effort}\right) < 1$
\begin{center}


{\tiny\begin{tabular}{llll}
PC1: & 
\includegraphics[angle=270,width=1.5in]{problem_nbk_pc1.eps}&
CM1: & \includegraphics[angle=270,width=1.5in]{problem_nbk_cm1.eps}\\
KC1: & 
\includegraphics[angle=270,width=1.5in]{problem_nbk_kc1.eps}&
KC2: & \includegraphics[angle=270,width=1.5in]{problem_nbk_kc2.eps}
\end{tabular}}
\end{center}

The above results from Naive Bayes (+ kernel estimation). 

Same seen with J48 (but lower PDs).

{\bf \underline{CONCLUSION:}} want something with $\frac{PD}{effort}>1$.
}
\end{slide}

% LocalWords:  independancy independenecy desdirata
5~


\begin{slide}{Treatments are Small}
{\footnotesize
Three requirements models from deep-space missions (from JPL).

\begin{minipage}{.49\linewidth}
\includegraphics[width=1.6in]{aerorx.eps}
\end{minipage}
\\\begin{minipage}{.49\linewidth}
\includegraphics[width=1.6in]{holorx.eps}
\end{minipage}
\begin{minipage}{.49\linewidth}
\bi
\item
Given issues A,B,...,Z
\item
 and knowledge that
D,E,..Z\newline don't matter,
\item
 then argue for D,E,..,Z
\item
and, when compromising, propose  A,B,C 
as ``after-thoughts''.
\ei
\end{minipage}

~\\
BTW, SA comments on all of A,B,...Z.
}
\end{slide}


\begin{slide}{Reducing Uncertainty}
{\tiny {\bf
\dualslide{topsep=-1cm,colsep=0pt,lcolwidth=2.1in}{
\begin{center}
\includegraphics[width=1.1in]{cirttiny.eps}
\end{center}
%% \begin{eqnarray}
%% x'\;=\;+& if & x > 0\nonumber\\
%% x'\;=\;0&if & x = 0\nonumber\\
%% x'\;=\;-&if& x < 0\nonumber
%% \end{eqnarray}
%%
\begin{alltt}{\scriptsize
\%sum(X,Y,Z).\\
sum(+,+,+). sum(+,0,+). sum(+,-,X).\\
sum(0,+,+). sum(0,0,0). sum(0,-,-).\\
sum(-,+,X). sum(-,0,-). sum(-,-,-).\\
\\
\%blub(Mode,~Light,Volts,Amps)\\
 bulb(blown, dark, ~~~~X, ~~0).\\
 bulb(ok, ~~~light, ~~~+, ~~+).\\
 bulb(ok, ~~~light, ~~~-, ~~-).\\
 bulb(ok, ~~~dark, ~~~~0, ~~0).\\

\%switch(State,Volts,Amp)\\
 switch(on, ~~~0, ~~X).\\
 switch(off, ~~X, ~~0).}
\end{alltt}
}{
\includegraphics[width=1.9in]{cirt.eps}

\begin{alltt}
  1  circuit(switch(Sw1,VSw1,C1),\\
  2          ~~~~~~~~~bulb(B1,L1,VB1,C1),\\
  3          ~~~~~~~~~switch(Sw2,VSw2,C2),\\
  4          ~~~~~~~~~bulb(B2,L2,VB2,C2),\\
  5          ~~~~~~~~~switch(Sw3,VSw3,CSw3),\\
  6          ~~~~~~~~~bulb(B3,L3,VB3,CB3), Glow) :-\\
  7      ~~~~VSw3 = VB3,\\
  8      ~~~~sum(VSw1, VB1, V1),\\
  9      ~~~~sum(V1,VB3,+),     \\
 10      ~~~sum(VSw2,VB2,VB3),  \\
 11      ~~~switch(Sw1,VSw1,C1),\\
 12      ~~~bulb(B1,L1,VB1,C1), \\
 13      ~~~switch(Sw2,VSw2,C2),\\
 14      ~~~bulb(B2,L2,VB2,C2), \\
 15      ~~~switch(Sw3,VSw3,CSw3),\\
 16      ~~~bulb(B3,L3,VB3,CB3),  \\
 17      ~~~sum(CSw3,CB3,C3),     \\
 18      ~~~sum(C2,C3,C1),        \\
 19      ~~~num(L1,N1), num(L2,N2),\\
 20      ~~~num(L3,N3), Glow is N1+N2+N3.
\end{alltt}
}}}
\end{slide}
\begin{slide}[toc=Stable conclusions]{Find Stable Conclusions}
{\scriptsize
\dualslide{rcolwidth=0.01\linewidth, colsep=0pt,lcolwidth=0.99\linewidth,topsep=-1cm}{
\begin{minipage}{.4\linewidth}
{\tiny \colorbox{black}{\mbox{\color{white}I.}}}
\underline{Simulation 1}:\newline
35,228 results
\end{minipage}\begin{minipage}{.33\linewidth}
\begin{barenv} \setstyle{\sffamily} \setwidth{5}
\setnumberpos{none} \setstretch{0.25} \setyaxis{0}{50}{33}
\setxaxis{0}{9}{1}
\bar{0}{8}  %0
\bar{22}{8} %1
\bar{43}{8} %2
\bar{21}{8} %3
\bar{6}{8}  %4
 \bar{6}{8} %5
\bar{1}{8}  %6
\bar{0}{8}  %7
\bar{0}{8}  %8
\bar{0}{8}  %9
\end{barenv}

\end{minipage}\begin{minipage}{.4\linewidth}
\end{minipage}

\vspace{6mm}

\begin{minipage}{.4\linewidth}
{\tiny \colorbox{black}{\mbox{\color{white}II.}}}
\underline{TAR2's recommendations 1:}\newline
``But we can't close Sw3C-\newline
that violates
the warranty.''
\end{minipage}\begin{minipage}{.33\linewidth}
Sw2C=off 

\begin{barenv}
\setstyle{\sffamily} \setwidth{5} \setnumberpos{none}
\setstretch{0.25} \setyaxis{0}{50}{33}
\setxaxis{0}{9}{1}
\bar{0}{8} %0
\bar{0}{8} %1
\bar{0}{8} %2
\bar{0}{8} %3
\bar{47}{8} %4
 \bar{48}{8} %5
\bar{3}{8} %6
\bar{2}{8} %7
\bar{0}{8} %8
\bar{0}{8} %9
\end{barenv}

\end{minipage}\begin{minipage}{.33\linewidth}

  Sw3C=on

\begin{barenv}
\setstyle{\sffamily} \setwidth{5} \setnumberpos{none}
\setstretch{0.25} \setyaxis{0}{50}{33}
\setxaxis{0}{9}{1}
\bar{0}{8} %0
\bar{0}{8} %1
\bar{0}{8} %2
\bar{0}{8} %3
\bar{15}{8} %4
 \bar{46}{8} %5
\bar{35}{8} %6
\bar{4}{8} %7
\bar{0}{8} %8
\bar{0}{8} %9
\end{barenv}



\end{minipage}

\vspace{6mm}

\begin{minipage}{.4\linewidth}
{\tiny \colorbox{black}{\mbox{\color{white}III.}}}
\underline{Simulation 2}:\newline
 3,264 results
\end{minipage}\begin{minipage}{.33\linewidth}

 Sw2C=off

\begin{barenv} \setstyle{\sffamily} \setwidth{5}
\setnumberpos{none} 
\setstretch{0.25} \setyaxis{0}{50}{33}
\setxaxis{0}{9}{1}
\bar{0}{8}  %0
\bar{0}{8} %1
\bar{0}{8} %2
\bar{0}{8} %3
\bar{47}{8}  %4
 \bar{48}{8} %5
\bar{3}{8}  %6
\bar{2}{8}  %7
\bar{0}{8}  %8
\bar{0}{8}  %9
\end{barenv}

\end{minipage}\begin{minipage}{.33\linewidth}
\end{minipage}

\vspace{6mm}

\begin{minipage}{.4\linewidth}
{\tiny \colorbox{black}{\mbox{\color{white}IV.}}}
\underline{TAR2's recommendations 2}:\newline
``Surge suppressor for B3C \newline
is too expensive!''
\end{minipage}\begin{minipage}{.33\linewidth}

Sw2c=off \&  Sw1C=on 

\begin{barenv}
\setstyle{\sffamily} \setwidth{5} \setnumberpos{none}
\setstretch{0.25} \setyaxis{0}{50}{33}
\setxaxis{0}{9}{1}
\bar{0}{8} %0
\bar{0}{8} %1
\bar{0}{8} %2
\bar{0}{8} %3
\bar{41}{8} %4
 \bar{42}{8} %5
\bar{9}{8} %6
\bar{8}{8} %7
\bar{0}{8} %8
\bar{0}{8} %9
\end{barenv}

\end{minipage}\begin{minipage}{.4\linewidth}

 Sw2c=off \&  B3C=ok 

\begin{barenv}
\setstyle{\sffamily} \setwidth{5} \setnumberpos{none}
\setstretch{0.25} \setyaxis{0}{50}{33}
\setxaxis{0}{9}{1}
\bar{0}{8} %0
\bar{0}{8} %1
\bar{0}{8} %2
\bar{0}{8} %3
\bar{15}{8} %4
 \bar{46}{8} %5
\bar{35}{8} %6
\bar{4}{8} %7
\bar{0}{8} %8
\bar{0}{8} %9
\end{barenv}
\end{minipage}

\vspace{6mm}

\begin{minipage}{.4\linewidth}
{\tiny \colorbox{black}{\mbox{\color{white}V.}}}
\underline{Simulation 3}:\newline
648 results
\end{minipage}\begin{minipage}{.33\linewidth}
Sw2C=off \& Sw1C=on

\begin{barenv}
\setstyle{\sffamily} \setwidth{5} \setnumberpos{none}
\setstretch{0.25} \setyaxis{0}{50}{33}
 \setxaxis{0}{9}{1}
\bar{0}{8} %0
\bar{0}{8} %1
\bar{0}{8} %2
\bar{0}{8} %3
\bar{41}{8} %4
 \bar{42}{8} %5
\bar{9}{8} %6
\bar{8}{8} %7
\bar{0}{8} %8
\bar{0}{8} %9
\end{barenv}

\end{minipage}\begin{minipage}{.33\linewidth}
\end{minipage}

\vspace{6mm}

\begin{minipage}{.4\linewidth}
{\tiny \colorbox{black}{\mbox{\color{white}VI.}}}
\underline{TAR2's simulations 3}:\newline
``Better look into that\newline
 warranty for Sw3C.''
\end{minipage}\begin{minipage}{.33\linewidth}
 Sw2C=off
\& Sw1C=on \newline
\&  B3C=ok  
\begin{barenv}
\setstyle{\sffamily} \setwidth{5} \setnumberpos{none}
\setstretch{0.25} \setyaxis{0}{50}{33}
 \setxaxis{0}{9}{1}
\bar{0}{8} %0
\bar{0}{8} %1
\bar{0}{8} %2
\bar{0}{8} %3
\bar{18}{8} %4
 \bar{21}{8} %5
\bar{32}{8} %6
\bar{29}{8} %7
\bar{0}{8} %8
\bar{0}{8} %9
\end{barenv}
\end{minipage}\begin{minipage}{.33\linewidth}
 Sw2C=off 
   \& Sw1C=on \newline
\&
  Sw3C=on 


\begin{barenv}
\setstyle{\sffamily} \setwidth{5} \setnumberpos{none}
\setstretch{0.25} \setyaxis{0}{50}{33}
 \setxaxis{0}{9}{1}
\bar{0}{8} %0
\bar{0}{8} %1
\bar{0}{8} %2
\bar{0}{8} %3
\bar{0}{8} %4
 \bar{25}{8} %5
\bar{50}{8} %6
\bar{25}{8} %7
\bar{0}{8} %8
\bar{0}{8} %9
\end{barenv}
\end{minipage}
}{}
}
\end{slide}

{\footnotesize
\bi

\item
Lift heuristic: good method for building small theories (``differences''
are shorter than ``description'');
\item
Useful in many domains for many tasks
\item
Bayesian treatment learning: 
\bi
\item
Given binary hypercube classification, treatment learning $\approx$ N\aive Bayes
\item
Fast
\item
Small memory
\item
Not confused by dependence
\item
One pass through data, incremental (a data miner)
\ei
\item The future
\bi
\item Treatment learning might disappear
\bi
\item Just become a stochastic rule-generation method for Bayesian data mining
\ei
\ei
\item 
Possibility of VERY fast rule generation using a forward select algorithm:
\bi
\item
no backtracking required
to handle dependency problems
\ei
\ei
}
\end{slide}


Randomly select an equal number of ``$<$'' and ``$>$'' cases (687 in all)
\item Sub-sample the data ten times (90\% sub-samples)
\item Run TAR3 on all samples
\item In what percent of samples do certain ranges  select for ``$>$''?
{\tiny
\begin{center}
\begin{tabular}{c@{~}|c|c|c|c|c}\cline{2-6}
          & \multicolumn{4}{c|}{treatment is a conjunction of ...}\\\cline{2-6}
frequency  & $log_{10}x$     & $log_{10}y$                          &                        $log_{10}a$ & $log_{10}b$       & size  \\\hline
  100\%       &   $   \ge -1 $  &&&\\
  100\%  &   $   \ge -1 $       &     $-6 ... -3 $&&\\
  100\%  &   $   \ge -2 $ &   $-7 ...  -6$ &&\\
  100\%  &   $   \ge -1 $ &                                             &                                   & $-18 ...  -4$   \\
  100\%  &   $   \ge -1 $       &                                       &                                   &  $-18 ... -4$     & $1... 5$\\ 
  100\%  &   $   \ge -1 $       &                                       &                                   &                   & $1 ... 8$\\
   90\% &   $   \ge -1 $ &                                              &  $ -15 ... -2 $ &\\
   90\% &   $   \ge -1 $ &                                              &  $ -15 ... - 2 $                    & $-18 ... -4$\\
   80\% &   $   \ge -1 $ &                                              &  $ -15 ... -2 $                    &  $-18 ... -4$ & $ 1 ... 5 $\\\hline
   60\% &   too infrequent\\
\end{tabular}
\emd{center}}
\item
