\documentclass[acmtosem]{acmtrans2m}
%\documentclass{acmtrans2m}
\usepackage{alltt}
\usepackage{bar,ifthen,color}
%\usepackage{wrapfig}

\renewcommand{\sfdefault}{phv}
\newcounter{linecounter}
\setcounter{linecounter}{1}
\newcommand{\nm}{{\scriptsize \thelinecounter} 
\hspace{2pt} \addtocounter{linecounter}{1}}
\newcommand{\tb}{\hspace{10pt}}
\newcommand{\cm}[1]{\raisebox{-1pt}{\textit{\scriptsize /* #1 */}}}
%\newcommand{\cm}[1]{{\textit{/* #1 */}}}
\newenvironment{myalg}
  {\setcounter{linecounter}{1}  \scriptsize \sffamily \begin{tabular}{r@{}p{3.5in}}}
  {\end{tabular} \normalsize}

\usepackage{rotating}
\newcommand{\sq}[2]{%
    \definecolor{thiscol}{gray}{.#2}%
        \ifthenelse{#2<50}%
            {\color{white}}%
            {\color{black}}%
        \colorbox{thiscol}{\makebox[2em]{#1}}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newdef{definition}[theorem]{Definition}
\newdef{remark}[theorem]{Remark}

\input{../jim/tricks.sty}
\input{../tim/tricks.sty}
\input{../jeremy/tricks.sty}

           
\markboth{Menzies et.al.}{Learning Control Policies}

\title{Learning Minimal Policies for Software Projects}
            
\author{
  TIM~MENZIES, West Virginia University, WV, USA
\and
JAMES~KIPER, Miami University, Ohio, USA
\and
JEREMY GREENWALD,
MathWorks, USA
\and 
YING HU, Vancouver, BC, Canada
\and
DAVID RAFFO, and
and SIRI-ON SETAMANIT , 
Portland State University, OR, USA
}
\begin{abstract} 
Blab blah
\end{abstract}
            
\category{aa}{bb}{cc}
            
\terms{dd} 
            
\keywords{ee}
            
\begin{document}
            
\begin{bottomstuff} 
Dr. Menzies is with the Lane Department of Computer
Science, West Virginia University and can be r
eached at \protect\url{tim@menzies.us},

Dr. Kiper is with the
Computer Science and Systems Analysis Department,
School of Engineering \& Applied Science, Miami University, and can be reached
at \protect\url{kiperjd@muohio.edu}. 

Ms. Hu is a software
designer in Vancouver, British Columbia and 
can be reached at 
\protect\url{huying_ca.@yahoo.com}. 

Mr. Greenwald, formerly with
Computer Science at Portland State University,
now works at MATHWORKS
\protect\url{jegreen@cecs.pdx.edu}. 

Dr. Raffo is a Associate Professor in the School of Business
Administration, Portland State University, and can be reached at \protect\url{raffod@sba.pdx.edu}.

Ms. Setamanit is a graduate student at Portland State Universit.
and can be reached at \protect\url{sirion@pdx.edu}.

The research described in this paper
was carried out at Miami University, 
West Virginia University and Portland State University under
contracts and sub-contracts with NASA's Software Assurance Research Program.
Reference herein to any specific commercial product, process, or service
by trademark, manufacturer, or otherwise, does not constitute or imply
its endorsement by the United States Government.

Download an earlier draft from
\protect\url{http://menzies.us/pdf/07succinct.pdf}.
\end{bottomstuff}
            
\maketitle

\section{Introduction}
Consider a software manager using a software process model to control
their project. Exploring all the ``what-ifs'' within those models
can be a daunting tasks. For example, 20 binary decisions require,
in the worst case, $2^{20}>1,000,000$ what-ifs.  For another example,
after interviewing the managers of three NASA systems regarding
their process options, we found that they were considering up to
$10^9$ options\footnote{A COCOMO model with 12 unknowns was being
analyzed; each unknown has up to 6 possible values; $6^{12} >
1,000,000,000$.}.

In the $21^{st}$ century, it is possible to use standard desktop
machines to explore a very large option space.  Many businesses
under-utilize their CPUs once staff go home for the day. Those
machines can be combined into a CPU farm which. If the process
models  are not database or GUI intensive, then such  a CPU farm
can can work through billions of options in an overnight run.

However, once all those options are created, they must be summarized.
That is, it is not enough to {\em generate} a multitude of alternatives,
we must also {\em select} the subset of the possible options that
matter then most.  This paper discusses a summarization technology
that exploits two naturally occuring properties of many models:
{\em clumps} and {\em collars}

The number of 
configuration possibilities within a model can be dauntingly large. A model with
20 binary choices has $2^{20}>1,000,000$
possible configurations, far beyond the capability of human
comprehension. Standard model comprehension methods such as design
of experiments have limited utility 
when the model is non-continuous, very large, or 
contains noise. 

Hence, since 2000, we have been
exploring model comprehension using
data miners.
After randomly sampling
those configurations, running the resulting model, scoring
the output with some oracle, our data miners
are used to
configure options that  most improve model output~\cite{burk04,fea02a,gel03a,hu02,me00e,me01e,me02h,me03g,me03i,me03j,me03l,me05e,me06a,me06b,owen02a}.
This paper
synthesizes that prior work 
and presents new case studies.
Originally, our work was inspired by Bratko's combination of qualitative
modeling and data mining~\cite{bratko89}. 
We found that standard data miners 
may be
inadequate for exploring
model configuration possibilities
since they
often
yield results that 
are incomprehensible to humans:
\bi
\item
Neural nets never generate
a succinct generalization of their knowledge~\cite{hinton92};
\item
The random search of genetic algorithms can produce models that are too
complex to understand~\cite{witten99};
\item
Most decision/regression tree learners such as C4.5~\cite{quinlan86}
or CART~\cite{breiman84}
execute in local top-down
search, with no memory between different branches.  Hence, the same concept
can be needlessly repeated many times within the tree.
Consequently, such trees can be  cumbersome, needlessly large, and
difficult to understand.  \ei

The
detailed, complex and arcane output generated by standard data miners is
often superfluous. Firstly, many
human experts can not (or will not)
read complex theories learned by a data miner.
Secondly, 
numerous empirical and theoretical results argue that, in the usual case,
models are controlled by a handful of  of key variables.
If data miners are restricted to just returning models containing those keys,
then the learned model will be very small indeed.

Thus, we propose a different kind of data miner to assist analysts
in exploring the configuration possibilities within their models.
Traditional machine learners like C4.5
generate classifiers that assign a class symbol to an
example.
Our preferred method, called {\em
treatment learning} generates just the {\em differences}
in the key variables
among different outcomes.

The rest of this paper is structured as follows. 
The twin topics of
model-based SE and search-based SE are introduced.
A special case of {\em hard models} are discussed that are difficult
to manage using standard methods.
Evidence is then presented that, often,
the key variables that control a
model are few in number.
The problem of hard models therefore can be reduced to just the
problem of understanding the key variables.
This will motivate the design of the TAR2 {\em treatment learner}.
Case studies will then be presented showing that, in many domains,
TAR2 finds a small number of controlling variables.
Such succinct controllers have many
advantages:
\bi
\item
Smaller models are easier to explain (or audit).
\item 
Miller has shown that models
generally containing fewer variables
have less variance in their outputs~\cite{miller02}.
\item
The smaller the model, the fewer are the demands on interfaces 
(sensors and actuators) to the
external environment.
Hence, systems designed around 
small models
are easier to use (less to do)
and cheaper to build.
\ei

In short,  for a certain class of {\em hard modeling}
problems, the TAR2 treatment learner can dramatically simplify the
task of understanding the configuration
possibilities within model-based SE.
Hence, our conclusion will be that it is useful to augment standard modeling methods
with treatment learning.
As to other modeling problems,
TAR2 is {\em not} indicated  
for low-dimensionality
linear continuous models built in domains that have no noise or other
uncertainties, and where managers have full control over all model inputs.


\section{Related Work}
Traditional methods may not yield  succinct control
policies from software process models.
One such traditonal method is
{\em binary plotting}; i.e.
$N$ model inputs are plotted against some output score
in $N$ two-dimensional binary plots.
The best constraints on the inputs are those
that select for the best output. 
However,
if noise in a models yields plots that are not smooth,
then it becomes a time-consuming and subjective task to examine $N$ binary 
plots to detect regions of input parameters that most improves the outputs.
Also, binary plotting will not find
{\em conjunctions} of input constraints
that
contribute to better output.
Further, as the dimensionality 
of model input increases, the cognitive effort required to 
study the plots can become prohibitively expensive.

%\begin{figure}[!b]
%\centerline{\includegraphics[width=3.5in]{../tim/mat_den_SD.pdf}}
%\caption{A visualization tool for scientific data. From~\cite{treinish98}.}
%\label{fig:treinish}
%\end{figure}
Many researchers have developed impressive visual environments for
decreasing the cognitive overload associated with exploring
a multi-dimensional space. 
%For example, \fig{treinish} shows a tool
%developed at IBM that augments a standard three-dimensional display
%with visual cues relating to higher-dimensional data; e.g.,
%supplementary dimensions are shown bottom right; blue circles around
%the axle show circular motion information; and a color key, shown
%bottom left, indicates how colors in  the display relate to density
%information~\cite{treinish98}. 
%
Such visualizations help analysts
explore visual information, but they present their own challenges.
Nevertheless, there are still
limits on how many dimensions can be displayed (e.g. we have yet
to see effective visualizations for more than a ten dimensionality space).
%Also, note how the tool shown in \fig{treinish} contains
%numerous controls that allow analysts to change various visualization
%options.  
As the visualization environment grows more sophisticated,
some users find they have traded a data browsing problem with the
new problem of exploring the full range of the effects of all the
controls. 

When manual exploring of options fail, automatic methods can be
applied.  Optimization packages can be applied to data or the
equations of a system to find ``sweet spots'' that maximize the
score resulting from model outputs.  
For example, a canonical {\em sensitivity analysis}
method~\cite{saltelli00} 
might be to compute eigenvectors of a linear system in order
to understand its long-term temporal behavior~\cite{ishida89,puccia85}.
Alternatively, using
design of experiments~\cite{boning04},  we might
exercises an existing model to
shed light on the response surface of the model (DOE does
identify gradients and key parameters for a model).

While useful for some models, these automatic methods do not apply
to all models.  For example, optimization methods can fail for
non-linear models.   Any model with an ``if'' statement introduces
a ``cliff'' where the effects of inputs on outputs abruptly  changes.
For such models, there is no linear continuous solution that applies
either side of the ``cliff''.  Model uncertainty also complicates
sensitivity analysis.  For example, the eigenvector technique
described would yield spurious results if the coefficients on the
models are not known with certainty.  Lastly, a DOE analysis can
be complicated by the dimensionality, noise, and visualization
problems described above.

When sensitivity experiments and DOE are not appropriate, other
methods such  the cross-entropy method~\cite{rubinstein04};
simulated annealing~\cite{kirkpatrick93}, tabu
search~\cite{gover93tabu}, or genetic algorithms~\cite{goldberg00} might
be employed.  All these methods have been used for search-based
software engineering XXX

More generally, traditional methods 
often assume total knowledge and total control of the input
space. This is often impractical.
Consider, for example, Mintzberg~ \cite{mintz75} study of how real-world
decisions are made. He found:
\bi
\item  56 U.S. foremen who
     averaged 583 activities in an eight-hour shift (one every 48 seconds).
    \item  160 British managers who
     worked for half an hour or more without interruption only once every
     two days. \ei
These empirical observations
do
not fit a traditional optimization model of decision making
were
all options are systematically studied, organized,
co-ordinated
and controlled.
In {\em hard modeling problems}, human agents must make decisions
using:
\bi \item
limited time and computational ability; \item
 limited computational ability (or
limited time for computation); \item limited knowledge about
decision alternatives;\item uncertainty about possible outcomes of
decisions\item uncertainty about pay-offs; \item no more than a
partial ordering of preferences; \item limited information about
probabilities of outcomes. \ei 
Herbert Simon~\cite{simon82} 
defined and explored such hard modeling problems using a data structure
called {\em state space}~\cite{rosen93}.
In terms of model-based SE, state space is the set of options and option
selection operators within a model. 
Further, in hard modeling problems, large portions of the state space are uncertain.
Simon argued that in such state spaces,
searching for optimal solutions is a spurious goal.
Rather,
agents can only make just enough decisions that are just good enough.
In Simon's terminology, such decisions are {\em satisficing}.

Our contribution to hard modeling is to comment that (1)~{\em satisficing}
solutions can be achieved by
ignoring
certain irrelevant or redundant details within a model; (2)~surprisingly simple methods
can find what irrelevancies to ignore.  
Treatment learners propose ``treatments''; i.e.
constraints on a small subset of the model inputs. The other inputs
are left to vary at random. That is, apart from generating very succinct solutions,
treatment learning offers solutions that are 
stable
despite uncertainty in the  non-treated variables.






%process control is a decision intensive process.
%engineering is modeling~\cite{schmidt06}.  
%Software engineers build
%models at every phase of the life cycle.
%Some are paper-based and some are executable but all these artifacts
%are 
% \emph{models} which 
%Mellor~\cite{mellor03} defines to be
% ``elements
%describing something (for example, a
%system, bank, phone, or train) built for some
%purpose that is amenable to a particular form
%of analysis, such as
%communication of ideas between people
%and machines;
%completeness checking;
%test case generation; etc.''
%Models
%are used throughout the software development process --
% from requirements and design to testing and performance evaluation
% -- and that use models will only increase.  
%
%Even with tool support, creation of practical and
% functional models is a resource-intensive activity.
% Effective use of models requires
% that they be allowed to evolve through the software development
% process.  Other researchers  have recognized that ``designers must
% be able to examine various design alternatives quickly and easily
% among myriad and diverse {\em configuration possibilities}''\cite{gray06}.
%%Finding an appropriate and effective balance between human intelligence and automation can be a recondite task.  
%
%
%\section{Modeling and Search}
%
%Anthropologists argue that the ability to build abstract models is
%what gives homo sapiens their competitive
%edge.   In his article ``What Models Mean" \cite{seidewitz03},
%Seidewitz describes the interactions and relationships among the
%concepts of a model.  
%He asserts that ``a model's meaning has two
%aspects: the model's relationship to what's being modeled and to
%other models derivable from it.  Carefully considering both aspects
%can help us to understand how to use models to reason about the
%systems we build ..."  These are the aspects of a model's meaning on which we focus
%in \emph{model-based} software engineering.
%
%Model-based software engineering (SE) is becoming increasingly important.
%Sendall and Kozacaynski argue that
%increasing
% productivity and reduced time-to-market for software products can
% accrue when ``using concepts closer to the problem domain ..." via
% modeling~\cite{sendall03}. Hailpern and Tarr observe that
% model-driven development ``imposes structure and common vocabularies
% so that artifacts are useful for their main purpose in their
% particular stage in the life cycle." \cite{hailpern06}
%
%The utility of model-based SE is widely
%acknowledged.
%For example, the 
%Object Management Group
%(OMG) has recently adopted a \emph{model-driven architecture}
%framework with goals of ``portability, interoperability and reusability
%through architectural separation of concerns." \cite{omg03}  
%%(See also \cite{frankel03}.)  OMG uses the established standard of UML,
%%the Common Warehouse Metamodel, and the Meta-Object Facility to
%%provide system interoperability in a vendor-neutral form. \cite{brown06}.
%Also, Microsoft has been developing a \emph{Software Factory} concept
%that leverages models with the goal of automation of the software
%development process~\cite{greenfield04}.  And, at Lockheed Martin, engineers
%have developed an integrated modeling method
%called \emph{Model Centric Software Development}
%that uses ``automated generation of partial
%implementation artifacts," reverse engineering to integrate legacy
%assets, and model verification and checking~\cite{waddington03 }
% 
% The importance of models and the model-driven approach is not
% limited to software design and UML. 
%Many tools exist for 
%modeling such as distributed agent-based
%simulations~\cite{clancey96a}, discrete-event
%simulation~\cite{law00,harrell00,kelton02,raffo05b,raffo05c},
%continuous
%simulation (also called system dynamics)~\cite{hamid91,sterman00},
%state-based simulation (which includes petri net and data flow
%approaches)~\cite{akhavi93,harel90,martin00},
%hybrid-simulation (that combines discrete event simulation and systems
%dynamics)~\cite{martin01,donzelli01,setamanit07},
%logic-based and qualitative-based methods~\cite[chapter
%20]{bratko01}~\cite{iwasaki89}, and rule-based
%simulations~\cite{mi90}. 
%One can find
% models used in the requirements phase (see the DDP method and tool
% \cite{feather03} which are a risk-based approach and visual tool
% to support requirements engineering), refactoring of designs using
% patterns \cite{france03}, software integration \cite{denno03},
% model-based security \cite{jurjens06}, and performance assessment
% \cite{bals04}.
%
%
%Model are useful since
%humans can review/audit/improve an explicit representation of their
%systems. 
%%But manual inspection is often insufficient to reveal the subtleties of a model.
%%Even very simple models can hide a surprising number of errors.
%%Consider, for example, a simple mathematical model of 
%%population growth.  
%%\begin{equation} \label{eq11} \frac{dN}{dT} = rN \end{equation}
%%Here, \emph{r} is a constant reflecting environmental conditions, \emph{T} is time, and \emph{N} is the
%%population. Note that this model is not accurate since population growth must taper off as it
%%approaches \emph{c}, the maximum carrying capacity of the environment; i.e.
%%\begin{equation}
%%\label{eq2}
%%\frac{dN}{dT} = rN\left(1-\frac{N}{c}\right)
%%\end{equation}
%%Before reading further, we ask the reader to consider whether
%%equation \#\ref{eq2} is an appropriate model of population growth?
%%If the reader cannot see all the subtleties in a one-line model, then we
%%should be suspicious of claims that the truth status of larger
%%models can be accurately determined by manual analysis.
%%Although equation \#\ref{eq2} does model our intuition in some
%%cases, there is one situation in which it is clearly incorrect.
%%Consider the case of over-population in an hostile environment: $N
%%> c, r < 0$.  Our intuition is that, in that situation,
%%the population will fall.
%%However, with these assumptions $rN(1-(N/c)) > 0$.  That is, our
%%model concludes that the population will {\em increase}  (example
%%taken from \cite{puccia85}.)   
%%
%%Our experience has been that this error in this simple
%%model is not apparent to many people.  Myers~\cite{myers77} reports
%%a similar conclusion, but using  a 63 line model.  In this
%%experiment, 59 experienced IT professionals searched for errors in
%%a very simple text formatter that consisted of 63 lines of PL/1
%%code. Even with unlimited time and the use of three different
%%methods, 73 of the experts could only find (on average) 5 of the
%%15 errors in this 63 line model \cite{myers77}. This result, despite
%%its age, and the previous thought experiment do not inspire confidence
%%that experts can accurately assess larger models.
%%%
%%%This phenomenon of models hiding errors is not limited to software.  Consider the  results
%%%of the Feldman and Compton study in which 109 of 343 (32\%) of the
%%%known data points from six studied papers could not be explained
%%%using a glucose regulation model developed from international
%%%refereed publications~\cite{fecosm89a, fecosm89b, smythe89}. A
%%%subsequent study corrected some modeling errors of Feldman and
%%%Compton to increase the inexplicable percentage from 32\% to 45\%.
%%%A similar study successfully faulted another smaller published
%%%scientific theory \cite{menzies92}.
%%
%But as models grow in complexity, it becomes difficult for a manual
%analysis to reveal all their subtleties.
%Hence, many researchers propose
%support environments
%to help explore the increasingly complex models that engineers are
%developing. Gray, at al, \cite{gray06} have developed the
%Constraint-Specification Aspect Weaver (C-Saw) that uses aspect-oriented
%approaches \cite{filman04} to help engineers in the process of
%model transformation.  Cai and Sullivan \cite{cai05} describe a
%formal method and tool called \emph{Simon} that ``supports interactive
%construction of formal models, derives and displays design structure
%matrices ... and supports simple design impact analysis."  Other tools
%of note are lightweight formal methods such as ALLOY~\cite{jackson02}
%and SCR~\cite{heitmeyer02} as well as  various UML tools that
%allow for the execution of life cycle specifications (e.g.
%the
%CADENA scenario editor~\cite{child06}).
%
%Recently, AI has been successful
%applied to
%model-based SE.
%For example,
%Whittle uses deductive learners to
%generate lower-level UML designs (state charts)
%from higher-level constructs (use case diagrams)~\cite{whittle06}.
%More generally, the field of
%{\em search-based SE} augments
%model-based SE with \emph{meta-heuristic} techniques, like genetic
%algorithms, simulated annealing, etc., to explore
%a model.
%Such heuristic methods are hardly complete but, as Clarke
%et.al.~\cite{clarke03} remark: ``...software engineers face problems
%which consist, not in finding \emph{the} solution, but rather, in
%engineering an \emph{acceptable} or \emph{near optimal solution}
%from a large number of alternatives."~\cite{clarke03}.
%
%Search-based SE
%is most often used to optimizing software
%testing~\cite{jones96a, jones98, pargas99, tracey98}
%but it has
%had
%application in numerous other areas.
%With Feather, we  have used
%search-based SE for requirements analysis~\cite{feather03}.
%Other researchers~\cite{harman02, lutz01}
%use genetic algorithms to examine ways of modularizing
%software~\cite{clarke03} or developing effort
%estimators~\cite{aguilar01,dolado00, dolado01}.  
%In all,
%Rela~\cite{rela04} lists 123 publications where search-based
%methods have been applied
%to the above applications as well as
%automatic synthesis  of software defect predictors; assisting in
%component design; developing multiprocessor schedules; re-engineering
%old systems into a better one; and searching for compiler optimizations.
%
%To use a search-based approach, software engineers have to reformulate their 
%problem by:
%\bi
%\item
%Finding a {\em representation of the problem} that can be 
%symbolically manipulated (e.g. simulated or mutated). 
%Such representations always exist with model-based SE.
%\item
%Defining a {\em fitness function} (a.k.a. ``utility function'''' or
%``objective function''); i.e.
%an ``oracle'' that
%scores a model configuration. Current model-based SE methods rarely offer
%such a function (exception: formal methods that generate temporal constraints). In our experience, generating such a fitness function is
%usually possible, albeit requiring days of work with the domain experts~\cite{me99j}.
%\item 
%Determining an appropriate set of {\em manipulation operators} 
%to select future searches based on the prior
%searches~\cite{harman01}.  
%\ei
%
%Data mining is one way to implement automatic manipulation operators.
%A data miner  searches through the space of possible concepts for
%a combination of concepts that describes some target
%theory~\cite{mitchell97}.  Given, say, the output from a Monte Carlo
%simulation of  a model, a $21^{st}$ century data miner can sift
%through gigabytes of data looking for the core concepts that most
%select for preferred output.
%
%
%\section{``Hard Modeling'' Problems}\label{sec:easyhard}
%Before describing our research into data mining for automatically
%generating manipulation operators,
%we must motivate why we don't use
%traditional methods. 
%As argued in the section, we seek constraints to model inputs that
%are
%{\em satisficing} (so, not necessary optimal),
%stable in the face of uncertainty,
%automatically generated, that reduce cognitive overload, and which
%work for large non-linear and noisy models. 
%Such constraints are called ``solutions to hard modeling problems''.
%
%Traditional methods may not yield such solutions.
%For example,
%one simple traditional method is {\em binary plotting}.
%After sampling the model, all model inputs might be plotted against the output score
%in two-dimensional binary plots.
%The best constraints on the inputs are those
%that select for the best output. 
%However,
%if noise in a models yields plots that are not smooth,
%then it becomes a time-consuming and subjective task to examine binary 
%plots to detect a region of input parameters that most improves the outputs.
%Also, studying binary plotting will not find
%conjunctions of multiple input constraints
%that
%contribute to better output.
%Further, as the dimensionality 
%of model input increases, the cognitive effort required to 
%study the plots can become prohibitively expensive.
%
%\begin{figure}[!b]
%\centerline{\includegraphics[width=3.5in]{../tim/mat_den_SD.pdf}}
%\caption{A visualization tool for scientific data. From~\protect\cite{treinish98}.}
%\label{fig:treinish}
%\end{figure}
%Many researchers have developed impressive visual environments for
%decreasing the cognitive overload associated with exploring
%a multi-dimensional space. For example, \fig{treinish} shows a tool
%developed at IBM that augments a standard three-dimensional display
%with visual cues relating to higher-dimensional data; e.g.,
%supplementary dimensions are shown bottom right; blue circles around
%the axle show circular motion information; and a color key, shown
%bottom left, indicates how colors in  the display relate to density
%information~\cite{treinish98}. 
%
%Such visualizations help analysts
%explore visual information, but they present their own challenges.
%There are still
%limits on how many dimensions can be displayed (e.g. we have yet
%to see effective visualizations for more than a ten dimensionality space).
%Also, note how the tool shown in \fig{treinish} contains
%numerous controls that allow analysts to change various visualization
%options.  As the visualization environment grows more sophisticated,
%some users find they have traded a data browsing problem with the
%new problem of exploring the full range of the effects of all the
%controls. 
%
%When manual exploring of options fail, automatic methods can be
%applied.  Optimization packages can be applied to data or the
%equations of a system to find ``sweet spots'' that maximize the
%score resulting from model outputs.  
%Related methods include {\em sensitivity analysis}~\cite{saltelli00} 
%and {\em design of experiments} (DOE) methods~\cite{boning94}
%A canonical sensitivity analysis method might be to compute
%eigenvectors of a linear system in order to understand its long-term
%temporal behavior~\cite{ishida89,puccia85}. 
%As for design of experiments,  DOE exercises an                      
%existing model and helps shed light on the response surface of the            
%model. DOE does identify gradients and key parameters for a model.
%
%While useful for some models, these automatic methods do not apply to all models.
%For example,
%optimization methods can fail for non-linear models.   Any model with an
%``if'' statement introduces a ``cliff'' 
%where the effects of inputs on outputs abruptly  changes.
%For such models, there is no linear continuous solution that applies either side
%of the ``cliff''.
%Model uncertainty also complicates sensitivity analysis.
%For example, the eigenvector technique described would
%yield 
%spurious results if the coefficients on the models are not known with certainty.
%Lastly, a DOE analysis can be complicated by
%the dimensionality, noise, and visualization problems
%described above.
%
%It should be noted that DOE, sensitivity analyis, and
%all learning methods (even the treatment learning method discussed below)
%are
%limited by the input range of inputs and the outputs generated. That is
%to say that in order to detect a ``cliff'', the input range of the learning
%set must span the cliff. Some researchers have overcome this limitation of traditional
%sensitivity and DOE approaches by expanding the input range for critical
%parameters including Wakeland et. al~\cite{wakeland04}. At the same time, their
%{\em Broad Range Sensitivity Analysis} approach relies on modeler judgment to
%select the parameters for inclusion in the expanded analysis. This
%approach although informed by data and model knowledge may not be
%(guaranteed) optimal.
%Unlike traditional sensitivity analysis and
%DOE, it is usual practice in our method to expand the input range beyond that of
%traditional sensitivity analysis and DOE. Moreover, the key benefit of 
%the our
%method discussed is that
%it  extracts a more compact model that can be heuristically
%used to traverse the response surface for the subset of parameters under
%consideration.
%
%More generally, traditional methods 
%tacitly assume total knowledge and total control of the input
%space. This is often impractical.
%Consider, for example, Mintzberg~ \cite{mintz75} study of how real-world
%decisions are made. He found:
%\bi
%\item  56 U.S. foremen who
%     averaged 583 activities in an eight-hour shift (one every 48 seconds).
%    \item  160 British managers who
%     worked for half an hour or more without interruption only once every
%     two days. \ei
%These empirical observations
%do
%not fit a traditional optimization model of decision making
%were
%all options are systematically studied, organized,
%co-ordinated
%and controlled.
%In {\em hard modeling problems}, human agents must make decisions
%using:
%\bi \item
%limited time and computational ability; \item
% limited computational ability (or
%limited time for computation); \item limited knowledge about
%decision alternatives;\item uncertainty about possible outcomes of
%decisions\item uncertainty about pay-offs; \item no more than a
%partial ordering of preferences; \item limited information about
%probabilities of outcomes. \ei 
%Herbert Simon~\cite{simon82} 
%defined and explored such hard modeling problems using a data structure
%called {\em state space}~\cite{rosen93}.
%In terms of model-based SE, state space is the set of options and option
%selection operators within a model. 
%Further, in hard modeling problems, large portions of the state space are uncertain.
%Simon argued that in such state spaces,
%searching for optimal solutions is a spurious goal.
%Rather,
%agents can only make just enough decisions that are just good enough.
%In Simon's terminology, such decisions are {\em satisficing}.
%
%Our contribution to hard modeling is to comment that (1)~{\em satisficing}
%solutions can be achieved by
%ignoring
%certain irrelevant or redundant details within a model; (2)~surprisingly simple methods
%can find what irrelevancies to ignore.  
%Treatment learners propose ``treatments''; i.e.
%constraints on a small subset of the model inputs. The other inputs
%are left to vary at random. That is, apart from generating very succinct solutions,
%treatment learning offers solutions that are 
%stable
%despite uncertainty in the  non-treated variables.
%
%
\section{Collars and Clumps }\label{sec:general}

This research assumes
that many models
can be controlled by a small number of key variables
which we call {\em collars}. Collars restrict the behavior
of a model such that their state space $clumps$;
i.e.
only small number of states are used at runtime.
If so, 
the output of  a data miner could be simplified
to constrain just the collar variables that switch
the system between a few clumps.

To visualize  collars, imagine an execution trace  spreading
out across a program. Initially, the trace is very small and includes only
the inputs.
Later, the trace spreads wider as {\em upstream} variables
effect more of the {\em downstream} variables (and the inputs are the most
$upstream$ variables of all).
At some time after the appearance of the inputs,
the variables hold a set of values. Some of these values were derived from
the inputs while others may be default settings that, as yet, have not been
affected by the inputs. The union of those values at time $t$ is called
the $state$ $s_{t}$ of the program at  that time. 

Multiple execution traces are
generated when the program is run multiple times with different inputs.
These traces reach different branches of the program. Those
branches
are selected by tests on conditionals at the root of each branch.
The {\em controllers} of a program are the variables that have different
settings at the roots of different branches in different traces.
Programs have $collars$
when a handful of the controllers
in
an early state $s_t$ control the settings
of the majority  of the variables seen in later states .

A related effect to {\em collars} is {\em clumping}.
If a program
has $v$ variables
with range 
$r$, then the maximum number of states is $r^v$.  Programs $clump$ when
most of those states are never $used$ at runtime; i.e.
$|used|/\left(r^v\right)\approx 0$.  
Clumps can cause collars:
\bi
\item
The
size of  $used$ is the cardinality cross product of the ranges seen in the
controllers.
\item
If that cardinality
is large, many states will be generated 
and programs won't clump.  
\item
But if that cross product
is small, then the deltas between the states will be small -- in which case
controlling a small number of collar variables would suffice for
selecting what states are reached at runtime.
\ei

There is much theoretical and empirical evidence
for expecting that many
models often contain  \emph{collars} and \emph{clumps}.

\subsection{Theoretical Evidence}

With Singh~\cite{me03l}, we have shown
that collars are an expected property of Monte Carlo simulations where
the output has been discretized into a small number of output classes.
After such a discretization,
many of the inputs would reach the same
goal state, albeit by different routes.
The following diagram shows two possible distinct
execution paths within  a Monte Carlo simulation
both leading to the same goal; i.e.
$a \rightarrow goal$ or
$b \rightarrow goal$.

\[ \left.
\begin{array}{r}
\stackrel{a_1}{\longrightarrow} M_1\\
\stackrel{a_2}{\longrightarrow} M_2\\
 \ldots\\
\stackrel{a_m}{\longrightarrow} M_m
\end{array}
\right\} \stackrel{c}{\longrightarrow} goal_i
\stackrel{d}{\longleftarrow} \left\{
\begin{array}{r}
N_1\stackrel{b_1}{\longleftarrow} \\
N_2 \stackrel{b_2}{\longleftarrow}\\
N_3 \stackrel{b_2}{\longleftarrow}\\
N_4 \stackrel{b_2}{\longleftarrow}\\
 \ldots\\
N_n\stackrel{b_n}{\longleftarrow}
\end{array}
\right.
\]
Each of the terms in lower case in the above diagram represent a probability
of some event; i.e. $0 \le \{a_i,b_i,c,d,goal_i\} \le 1$. 
For the two pathways to reach the $goal$, they must
satisfy  the collar $M$ or the larger collar $N$ 
(each collar is a conjunction). 
As the size of $N$ grows, the product
$\prod_{j=1}^N b_j$ decreases and it
becomes less likely that a random
Monte Carlo simulation will take steps of the larger collar $N$.

The magnitude of this effect is quite remarkable.
Under a variety of conditions, the  narrower collar is thousands to millions of times
more likely.  For example, when $|M|=2$ and $N>M$, the condition for selecting
the larger collar is 
$\frac{d}{c}\ge 64$; i.e. the larger collar $N$ will be used
only when the $d$ pathway is dozens
of times more likely than $c$. The effect is more pronounced
as $|M|$ grows; at $|M|=3$ and $N>M$, the condition is $\frac{d}{c}\ge 1728$;
i.e. to select the larger collar $N$, the $d$ pathway must be thousands of
times more likely than $c$
(for more details, see~\cite{me03l}).
That is, when the output space is discretized
into a small number of outputs, and there
are multiple ways to get to
the same output,  then a randomized simulation (e.g. a Monte Carlo
simulation) will naturally select for small collars. 

While the mathematics may be arcane, the intuition is simple.  
Suppose all the power goes out in a street of hotels. If all those
hotels were designed by different architects then their internal search spaces
would be different (number of rooms per floor, distance from each room
to a flight of stairs, number of stairwells, etc).
After half an hour, some of the guests bumble around in the dark and get
outside to the street.
Amongst the
guests that have reached the street, there would be more guests from
hotels with simpler internal search spaces (fewer rooms per floor, less distance
from each room to the stairs, more stairwells).


%%%% Jim -- this seems counter intuitive.  I would have thought that the smaller collar (M) was
%%%% more likely when it was smaller.  Isn't that what you just previously argued?

As to {\em clumping},
Druzdel~\cite{druzdel94} observed this effect in
a medical monitoring system.
The system had
 525,312 possible internal states. However, at runtime, very few were ever reached.
In fact, the system remained in one
state 52\% of the time,  and a mere
49 states were used, 91\% percent of the time. 
Druzdel showed mathematically that there is nothing unusual about his application.
If a model has $n$ variables, each with its own
assignment probability distribution of $p_i$, then the probability
that  the model will fall into a particular state is
$p=p_1p_2p_3...p_n=\prod^n_{i=1} p_i$.
By taking logs of both sides, this equation becomes
\begin{equation}\label{eq:dr}
\mbox{ln}~p = \mbox{ln}\prod^n_{i=1}p_i=\sum^n_{i=1}\mbox{ln}~p_i
\end{equation}
The asymptotic behavior of such a sum of random variables
is addressed by the central limit theorem.
In the case
where we know very little about a model, $p_i$ is uniform and many
states are possible. However, the {\em more} we know about  the model,
the {\em less} likely it is that the distributions are uniform.
%%%% I don't understand this argument 
Given
enough variance
in the individual priors and conditional probabilities or
$p_i$, the expected case is that the frequency with which
we reach states will exhibit a
log-normal distribution; i.e. a small fraction of states can be
expected to cover a large portion of the total probability space; and
the remaining states have practically negligible probability.   

The assertion that many types of models display this clumping behavior
is quite important for the style of data mining (treatment learning) that we 
advocate.  In application to a clumping model with collars,
Monte Carlo simulation, followed by TAR2,
suffices to summarize that model in an effective way:
\bi
\item TAR2's rules never need to be bigger than the collars. Hence, if the collars
are small, TAR2's rules can also be small.
\item
If a model clumps, then, very quickly, a Monte Carlo simulation would sample
most of the reachable states. TAR2's summarization of that simulation would
then include most of the important details of a model.
\ei
 
\subsection{Empirical Evidence}

Empirical evidence for clumps 
first appeared in the 1950s.
Writing in 1959, Samuel
studied machine learning for the game of checkers~\cite{samuel59}.
At the heart of his program was a 32-term polynomial that scored
different
configurations. For example,     \emph{king center control} means that
a king occupies one of the center positions.  The program learned
weights for these variable coefficients.  After 42 games, the program
had learned that 12 variables were important, although only 5 of
these were of any real significance.

Decades later, we can assert that 
deleting irrelevant variable has proven to be a useful strategy in
many domains. For example, Kohavi and John report experiments on 8 real world
datasets where, on average, 81\% of the non-collar variables can
be ignored without degrading the performance of a model automatically
learned from the data~\cite{kohavi97}.

If models contain collars, or if the internal state space clumps,
then much of the reachable parts of a
program can be reached very quickly. This {\em early coverage} effect
has been observed many times.
In a
telecommunications application, Avritzer,  Ros, \& Weyuker found that
a sample of 6\% of all inputs to this system covered 99\% of all
inputs seen in about one year of operation (and a sample of just
over 12\% covered 99.9\%)~\cite{avri96}.  
Further evidence for early
coverage can be found in the mutation testing literature.  In
mutation testing, some part of a program is replaced with a
syntactically valid, but randomly selected, variant (e.g. switching
``less than'' signs to ``greater than'').  This method of testing
is useful for getting an estimate of what percentage of errors have
been discovered by testing.  
Wong compared results using X\% of a library of mutators, randomly selected \mbox{(X $\in$\{10,15,\ldots40,100\})}. Most of what could be learned from the
program could be learned using only X=10\% of the mutators; i.e.
after a very small number of mutators, new mutators acted in the
same manner as previously used mutators~\cite{wong95}. The same
observation has been made elsewhere by Budd~\cite{budd80}
and Acree~\cite{acree80}. 

If the space of possible
execution pathways within a program are limited, 
then program execution
would be observed to clump
since it could only ever
repeat a few simple patterns.
Empirically such limitations have been
observed in procedural and declarative systems.
Bieman and Schultz~\cite{bieman92}
report that 10 or fewer paths through programs explored 83\% of the
du-pathways  (a du-path is a set of statements in a computer program
from a definition to a use of a variable.  This is one common form
of structural coverage testing.) 
Harrold~\cite{harrold98}
studied the control graphs of  4000 Fortran routines and 3147 C functions.
Potentially, the size of a control graph may
grow as the square of the number of statements (in the case where
every statement was linked to every other statement.)  This research
found that, in these case studies, the size of the control graph
is a linear function of the number of statements.
In an analogous result,
Pel\'{a}nek reviewed the structures of dozens of
formal models and concluded that
the internal structure of those models
was remarkably simple:
``state spaces are
usually sparse, without hubs, with one large SCC [strongly connected
component], with small diameter \footnote{The diameter of a graph
(of a state space here) is the number of edges on the largest
shortest path between any two vertices.} 
and small SCC quotient''\footnote{SCC quotient is a measure of the complexity of a 
graph.}~\cite{pelanek04}.  This
sparseness of state spaces was observed previously by Holtzmann
where he estimate the average degree of a vertex
in a state space to be 2~\cite{holzmann90}.

Pel\'{a}nek hypotheses that
these ``observed properties of state spaces are not the result of
the way state spaces are generated nor of some features of specification
languages but rather of the way humans design/model systems"~\cite{pelanek04}.
Pel\'{a}nek does not expand on this, but we assert that generally SE models are simple enough to be controlled by treatment learning
since they were written by humans with
limited short-term memories~\cite{miller56} who have difficulty
designing overly-complex models.


%
%
%
%who
%typically
%Formal models often comprised one large
%strongly connected component (where if state $u$ connects to state
%$v$, the $v $ also connects to $u$) and small ``diameters'' (i.e.  the
%largest shortest path between two states was quite short).  
%A program
%executing around such a space would repeatedly arrive back at a small number
%of  states;
%i.e. it would clump.
%In a analogous result, 

%There is much empirical and theoretical evidence for exalt that.
%
%model checking. not the UN reached states. just summarizing the reached states.
%
%
% often, a small number of conjunctions of attribute ranges.
%
%rules with  very small number of conjunctions
%fails if the model being studied required complex control rules.
%
%weighted sum of scores seen
%
%There is a particular type of structure that we have observed in
%many SE models -- that we have labeled a \emph{saturation effect}.
%This name derives from the idea that "random search quickly yields
%all that can be found, even after a much longer search."  \cite{menzies02}
%That is, the search space has been explored to a sufficient extent
%in that longer searches will produce little or no more information.
%(We do not assert that all SE models have this property, but that,
%when a model does exhibit saturation, we can avoid the problem of
%incompleteness of a random search.)  In this subsection, will
%illustrate this effect in a number of areas of software engineering.
%
%In one study of testing of formal models \cite{menzies02}, repeated
%experiments have demonstrated the plateau that is typical of a
%saturation effect.  See figure \ref{formalTesting}.  In this
%experiment, finite state machines were translated into a particular
%variant of AND-OR graphs. Figure \ref{formalTesting} shows results
%from a random search for errors of a very large model.  (There are
%250 finite state machines in this model, each with an average of 6
%states.  This gives a total of 1,455 local states which is equivalent
%to a composite finite state machine of $2.65 x 10^{178}$ states.)
%It is clear that the marginal gain after a search of the first few
%million nodes is negligible.
%
%In some prior work, Menzies, et al, have surveyed empirical reports
%in the field of testing where this saturation effect has been
%observed, i.e., where computer programs were observed to have zones
%that were easily reachable in testing, and others that were not
%reachable at all.  Here is a survey of some of such reports.
%
%\begin{itemize} \item In \cite{bieman92}, Bieman and Schultz report
%that 10 or fewer paths through programs explored 83\% of the
%du-pathways.  (A du-path is a set of statements in a computer program
%from a definition to a use of a variable.  This is one common form
%of structural coverage testing.)
%
%\item In another study, Harrold and colleagues \cite{harrold98}
%studied over 4000 Fortran routines and 3147 C functions to look at
%their control graphs.  Potentially, the size of a control graph may
%grow as the square of the number of statements (in the case where
%every statement was linked to every other statement.)  This research
%found that, in these case studies, the size of the control graph
%is a linear function of the number of statements.
%
%\item In \cite{colomb99}, Colomb reports about the use of a medical
%expert system.  Colomb expected that, for a system with V variables
%and S state, this system should have $S^V$ states.  In this case,
%$S^V \approx 10^{14}$  However, after operation for one year, he
%found that only 4000 states had been exercise.
%
%\item In another examination of an expert system, this one in the
%telecommunications domain, Avritzer,  Ros, and Weyuker found that
%a sample of 6\% of all inputs to this expert system covered 99\%
%of all inputs seen in about one year of operation, and a sample of
%just over 12\% covered 99.9\%.
%
%\item In a study of the testing of two extensively used systems,
%the Unix report-generation language AWK and the text formatting
%language TEX.  In both cases, despite elaborate testing, various
%measures of coverage showed that large portions of these programs
%were not covered.  For example, in \emph{block coverage}, TEX testing
%had achieved 85\% coverage, and AWK had achieved only 70\%.  Since
%these programs are viewed as quite reliable, this is evidence that
%most paths get exercised early in testing with little further
%improvement with further testing.
%
%\item Another form of testing that has interested software engineers
%is mutation testing.  This method of testing is useful for getting
%an estimate of what percentage of errors have been discovered by
%testing.  Such tester have often reported that a small sample of
%mutations are as useful as a much larger number of mutations.  See
%\cite{acree80, budd80, michael97, wong95}
%
%\item A similar effect has been noted in the certification of expert
%systems.  \cite{menzies01} In this work, Menzies and Singh present
%evidence from nine empirical studies that the number of tests to
%certify an expert system is often quite low, in the range of 4 to
%200 tests.  See \cite{betta95, bobrow86, buchanan84, caraca00,
%davies94, harmon86, menzies97, ramsey89, yu79}.  Thus, the number
%of tests need to discover the errors in an expert system is often
%quite low.
%
%\end{itemize}
%
%
%\begin{figure}[htb] \begin{center}
%\includegraphics[width=3in]{figures/saturationMenzies02.pdf}
%\caption{Random search of a very large model \cite{menzies02}}
%\label{formalTesting} \end{center} \end{figure}
%
%In a comparison of a standard depth first search backtracking
%algorithm with a randomized search theorem prover, Crawford and
%Baker \cite{crawford94} found that the randomized search was able
%to reach \emph{more} scheduling solutions in \emph{less} time.  In
%speculating about the reasons for this, these researchers indicated
%that their systems had a small number of ``control" variables that
%determined the value of the much larger number of ``dependent"
%variables.
%

\section{Data Mining with Collars and Clumps}

%\begin{table}
%\center
%\caption{Experts Comprehension of Others' Models}

%\begin{tabular}{|c|c|c|} \hline
%Expert Pairs&Understanding&Agreement\\ \hline
%Expert \#1 and \#2&62.5& 33.3\\
%Expert \#2 and \#1& 61.1& 26.7\\ \hline
%Expert \#1 and \#3&31.2& 8.3\\
%Expert \#3 and \#1& 42.9& 33.3\\ \hline
%Expert \#2 and \#3&44.4& 20.0\\
%Expert \#3 and \#2& 71.4& 33.3\\ \hline
%\end{tabular}
%\label{shawTable1}
%\end{table}
%
%In a similar vein, Shaw reports an experiment in which a group of geological experts built models for the
%same domain.    Twelve weeks later they reviewed each other's knowledge bases as well as their own
%\cite{shaw88}.   These research found that experts disagree significantly with each
%other \cite{shaw88}.  (See table \ref{shawTable1}.)  More surprisingly, they found that, after twelve weeks, an expert's understandability of his/her own knowledge base and even his/her agreement with it were considerably less than total. (See table \ref{shawTable2}.) 
%
%\begin{table}
%\center
%\caption{Experts Comprehension of Their Own Models}
%\begin{tabular}{|c|c|c|} \hline
%Expert&Understanding&Agreement\\ \hline
%Expert \#1&62.5&81.2\\ \hline
%Expert \#2&77.8&94.4\\ \hline
%Expert \#3&85.7&78.6\\ \hline
%
%\end{tabular}
%\label{shawTable2}
%\end{table}

%These examples suggest that humans have considerable difficulty
%comprehending model, even an apparently simple one.
%When manual methods fail, search-based SE can serve as an automatic agent to
%find the subtleties missed by a manual analysis.
%AI
%techniques have proven useful at exploration of such models to
%provide insights that humans are not able to see.  One rising area
%of AI applied to software engineering that has proven its effectiveness
%are those techniques that are described as \emph{search-based
%software engineering.}  We describe these techniques next.
%
%These examples motivate a belief that running and watching modes
%is not enough to understand them. Instead, model comprehension is
%best conducted by teams of   human and artificial intelligences
%working together to understand a domain. In our view, humans are
%best at painting the "whole" story, the big picture, defining the
%model, specifying the range of permissible values, perhaps along
%with some biases about which values are most likely or most
%improbable. Artificial intelligence (AI) techniques and tools are
%good at filling in the "holes"; i.e., all the details that humans
%routinely miss.  
%



%%%% Jim -- Could the ranges of this figure (fig. 2) be labeled with the 
%treatment so that it is more understandable?

%%%% Tim -- hell, why not just delete the figure altogether. it dont add much

The TAR2 {\em treatment learner}~\cite{me03e} is a data miner that is specialized
for generating models containing only collar variables.
TAR2 finds the difference between
classes. Formally, the algorithm is a {\em contrast set
learner}~\cite{bay99,webb03} that uses {\em weighted
classes}~\cite{cai98} to steer the inference towards the preferred
behavior. We call TAR2's output ``treatments''  since the minimal
rules generated by the algorithm are similar to medical treatment policies
that try to achieve the most benefit, with the least intervention.
The core intuition of TAR2 is that it is unnecessary to search for the collars--
they will reveal themselves after some limited random sampling. To
see that, recall that collar variables control the settings in the rest
of the system. Any execution trace that reaches
a goal must pass through the collars (by definition). 
Therefore, to find the collars, all an algorithm needs to do is find
the attribute ranges with very different frequencies in traces that
reach different goals.

Detecting collars via this sampling method is very simple to
implement.
Consider a log of golf
playing behavior shown in \fig{golfdata}. This log contains four
attributes (outlook, temperature, humidity, wind) and 3 classes (none, some, lots) that convey the
amount of golf played. 
We recommend an exponential
scoring system for the classes,
starting at two\footnote{If the weights run, say, \{bad=0,ok=1,good=2\}
then the difference from  
{\em bad} to {\em ok} scores the same as {\em ok} to {\em good}.
An exponentially weighting scheme, starting at two, 
finds greater and greater rewards moving to better classes. For further
details, see~\cite{hu02}.}.
For example, our golfer could weight the
classes in \fig{golfdata} 
as  {\em none=2} (worst),  {\em some=4}, {\em lots=8} (best).

TAR2  seeks attribute ranges that occur frequently in the
highly weighted classes and rare in the lower weighted classes. Let $a.r$
be some attribute range e.g. {\em outlook.overcast} means that the outlook is for overcast skies.
$\Delta_{a.r}$ is a heuristic measure of the worth of $a.r$ to
improve the frequency of the $best$ class. $\Delta_{a.r}$ uses the
following definitions:
\begin{description}
\item[$X(a.r)$:] ~~~is the number of occurrences of that attribute
range in class $X$; e.g. in this data {\em lots(outlook.sunny)=2} since there are 
2 cases with outlook = {\em sunny} and class = {\em lots}.
\item[$all(a.r)$:] ~~~is the total number of occurrences of that
attribute range in all classes; e.g. {\em
all(outlook.sunny)=5}. \item[$best$:]  the highest scoring
class; e.g. $best=lots$; \item[$rest$:]   the non-best class; e.g.
$rest=\{none,some\}$; \item[$weight$:] ~~ The weight of a class $X$ is symbolized by
$\$X$;. (Thus, $\$best = 8$.)\end{description}
 $\Delta_{a.r}$ is
calculated as follows:

{\footnotesize
\[
\Delta_{a.r}=\frac{\sum_{X{\in}rest}(\$best-\$X)*
(best(a.r)-X(a.r))}{all(a.r)}
\]
}{\noindent}When {\em a.r} is {\em outlook.overcast}, then
$\Delta_{outlook.overcast}$ is calculated as follows:
\[\frac{\overbrace{((8-2)*(4-0))}^{lots \rightarrow none}+\overbrace{((8-4)*(4-0))}^{lots \rightarrow some}}{4+0+0}=\frac{40}{4}=10
\]

%\noindent The attribute ranges in our golf example generate the
%$\Delta$ histogram shown in \fig{dels}. Note that {\em
%outlook=overcast}'s $\Delta$ is the highest, potentially most
%effective, attribute range.

%-----------------------------------
% deltaf distribution of Golf data
%-----------------------------------


\begin{figure}
\renewcommand{\baselinestretch}{1}
{\small {\em
\begin{center}
\begin{tabular}{rccccl}
outlook & temp($^o$F) &  humidity & windy? & class & weight
\\\hline
sunny&  85&     86&     false&  none & 2\\
sunny&     80&     90&     true&   none& 2\\
sunny&     72&     95&     false&  none& 2\\
rain&  65&     70&     true&         none&  2\\
rain&        71&     96&     true&   none& 2\\\hline
      rain&         70&     96&     false&      some &4\\
      rain&      68&     80&     false&      some & 4\\
      rain&      75&     80&     false&  some & 4\\\hline
      sunny&    69&     70&     false&  lots &8\\
      sunny&    75&     70&     true&   lots&8\\
      overcast&  83&     88&     false&  lots&8\\
      overcast&  64&     65&     true&   lots&8\\
      overcast&  72&     90&     true&   lots&8\\
     overcast&  81&     75&     false&  lots&8\\\hline
\end{tabular}\end{center}}}
\caption{A log of some golf-playing behavior.}
\label{fig:golfdata}
\end{figure}
%-----------------------------------
% treatment of Golf data
%-----------------------------------
%\begin{figure}
%\begin{center}
%{\small
%\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{$\Delta$ distribution from \fig{golfdata}.
%High $\Delta$ values are shown in black. Y-axis is the
%number of attribute ranges that have a particular $\Delta$.}
%\label{fig:dels}
%\end{figure}
%


To {\em build} a treatment,
TAR2 explores combinations of attribute ranges up to some user-specified
maximum size $s$ (where the size $s$ is
the number of attribute ranges in  a
conjunction of attributes). Given $n$ attributes,
the size of this search is  
$\frac{n!}{s! (n - s)!}$.
To make this search feasible, TAR2 must keep $s$ small.
Therefore, TAR2 first assesses each
attribute range, in isolation, i.e., with s = 1. A preliminary pass
builds one singleton
treatment for each attribute range.  The attribute ranges are then
scored by the $\Delta$ of these singleton treatments.  Treatment
generation is constrained to just the attribute ranges with a score
greater than a user-supplied threshold (default value= 1; maximum
useful value yet found= 7). 
%In \fig{dels}, this corresponds to 
%constraining
%treatment generation to only the right-hand-side attribute ranges.
%%%% Jim --is "right-hand-side" meaningful here?  Perhaps, "larger than the threshold" is better?

\begin{figure}
\renewcommand{\baselinestretch}{1}
\begin{minipage}{.70\linewidth}
{\small\begin{center}
\begin{tabular}{p{1.1in}p{1.1in}l}
$no\; change$  & $outlook=\newline
overcast$\\~\\
\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
     \setstretch{5}
  \setyaxis{0}{6}{2}
\sethspace{1} \setnumberpos{down} \bar{5}{1}
 \bar{3}{4}
 \bar{6}{8}
\end{barenv}&
\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
 \setstretch{5}
  \setyaxis{0}{6}{2}
\sethspace{1} \setnumberpos{down} \bar{0}{1} \bar{0}{4} \bar{4}{8}
\end{barenv}
\end{tabular}
\end{center}
}\end{minipage}\hfill
\begin{minipage}{.3\linewidth}
\begin{raggedleft}
{\scriptsize
\begin{tabular}{r@{}l}
\protect\legend1{~}&\begin{raggedright}= none
(worst)\end{raggedright}
\\
\protect\legend4{~}&\begin{raggedright}= some\end{raggedright}\\
\protect\legend8{~}&\begin{raggedright}= lots
(best)\end{raggedright}
\end{tabular}}
\end{raggedleft}
\end{minipage}
\caption{Finding treatments that can improve golf playing
behavior. With no treatments, we only play lots of golf in
$\frac{6}{5+3+6}= 57\%$ of cases. However, assuming
{\em
outlook=overcast}, we play golf lots of times in 100\% of
cases. } \label{fig:golft}
\end{figure}

\begin{figure}
\renewcommand{\baselinestretch}{1}
{\small
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|} \cline{3-4}
\multicolumn{2}{c}{}&\multicolumn{2}{|c|}{\# columns}\\\hline
 domain & \# rows & \begin{sideways}\# numeric\end{sideways} & 
\begin{sideways}\# discrete\end{sideways} & \#class  & time(sec) \\\hline
iris & 150 & 4 & 0 & 3 & $<1$ \\\hline 
wine & 178 & 13 & 0 & 3 & $<1$ \\\hline 
car & 1,728 & 0 & 6 & 4  & $<1$ \\\hline
autompg & 398 & 6 & 1 & 4  & 1 \\\hline 
housing & 506 & 13 & 0 & 4  & 1 \\\hline
 pageblocks & 5,473 & 10 & 0 & 5  & 2 \\\hline
cocomo & 30,000 & 0 & 23 & 4  & 2 \\\hline 
reacheness & 25,000 & 4 & 9 & 4  & 3 \\\hline 
circuit & 35,228 & 0 & 18 & 10  & 4 \\\hline 
reacheness2 & 250,000 & 4 & 9 & 4  & 23 \\\hline
pilot & 30,000 & 0 & 99 & 9  & 86 \\\hline
\end{tabular}
\end{center}}
\caption{Runtimes for TAR2 on different domains. First 6 data sets
come from the UC Irvine machine learning data 
repository~\protect\cite{Blake+Merz:1998};
``cocomo'' comes from a COCOMO software cost estimation model
\protect\cite{me00e}; ``pilot'' comes from the NASA Jet Propulsion
Laboratory \protect\cite{fea02a}.}
\label{fig:runtime}
\end{figure}

%\subsection{Weighted Contrast Set Learning}
%
%Due to the limitations of tree-based learning,
%numerous researchers have explored
%other methods including: \begin{itemize} \item Association
%rule learners, e.g. 
%APRIORI~\cite{agrawal94};
%\item Weighted class learner,  e.g. MINWAL~\cite{cai98};
%\item Contrast set learning, e.g. STUCCO~\cite{bay99};
%\item Weighted contrast set learning, e.g. TAR2~\cite{me03c};
%\end{itemize}
%
%Association rule learners 
%seek
%attribute values that commonly
%occur together in a learning set.  If $LHS$ and $RHS$
%are set of attributes with $LHS \cap RHS = \emptyset$, a rule ($LHS \rightarrow RHS$)
%describes the set of examples in which $LHS$ and $RHS$ both appear.  For
%example, in a set of data about student behavior and grades, we
%might find that many times when the \emph{GradeA} then
%\emph{Study=EveryDay}.
%In \fig{gradesTable}, there are four rows with this association.
%\begin{figure}
%\center\scriptsize
%\begin{tabular}{|c|c|c|c|c|c|} \hline
%Student&Sleep&Study&VideoGames&Exercise&Grade\\ \hline
%1&Much&EveryDay&Some&Some&A\\ \hline
%2&Little&BeforeTest&None&Little&B\\ \hline
%3&Average&EveryDay&None&None&A\\ \hline
%4&Average&None&Much&Little&C\\ \hline
%5&Average&BeforeTest&Some&Some&C\\ \hline
%6&Much&BeforeTest&None&Some&A\\ \hline
%7&Much&Little&None&Some&B\\ \hline
%8&Average&None&Much&None&D\\ \hline
%9&Little&None&Much&Little&D\\ \hline
%10&Little&EveryDay&Much&None&C\\ \hline
%11&Average&EveryDay&None&Much&A\\ \hline
%12&Average&Little&Some&Some&C\\ \hline
%13&Little&Little&None&Much&C\\ \hline
%14&Little&EveryDay&Much&Much&A\\ \hline
%15&Little&None&Some&Some&D\\ \hline
%16&Little&Little&Much&None&C\\ \hline
%17&Average&Little&None&Much&D\\ \hline
%18&Average&BeforeTest&Some&None&B\\ \hline
%19&Average&BeforeTest&None&Some&B\\ \hline
%20&Some&BeforeTest&None&Some&A\\ \hline
%\end{tabular}
%\caption{Observations of Grades and Behavior Data of Students}
%\label{Some student grades.}\label{fig:grades}
%\end{figure}
%
%We say that the rule ($LHS \rightarrow RHS$) holds with confidence \emph{c} if
%\emph{c} percent of the examples in the learning set \emph{L} that
%contain $LHS$ also contain $RHS$.  For example, the rule
%$Grade=A \rightarrow Study=EveryData$ has the confidence 
%0.67
%since \[c = \frac {| Examples _{LHS} \cap Examples _{RHS} |}{ | Examples
%_{LHS } |} = \frac{4}{6}=0.67\]
%Also,
%a rule ($LHS \rightarrow RHS$) has \emph{support} \emph{s},
%if \emph{s} percent of all of the learning examples support this
%rule.  That is: \\
%\[s = \frac{ | Examples _{LHS} \cap Examples _{RHS} |} {  | L | }\]
%In assessing the utility of various associations, we prefer those
%with higher \emph{confidence} which is a a measure of the strength
%of this association. However, we temper this selection with the
%\emph{support}.  An association with low \emph{support} is one that
%does a poor job of selecting desired outcomes from the learning set
%(and presumably from a larger set).
%The rule
%$Grade=A \rightarrow Study=EveryData$ had adequate confidence
%($c=0.67$) but low support ($s=\frac{4}{20}=0.2$).
%
%A \emph{weighted class learner} is an association rule learner that
%focuses the learning on issues of interest to a particular stake-holder
%by the assignments of weights to certain classes.  
%Thus, in addition to assessing the value of associations with
%\emph{confidence} and \emph{support}, we value those that lead us
%to certain weighted outcomes.  Of course, these weights may vary
%from stake-holder to stake-holder.
%\emph{Contrast set learning} is another variant of association rule
%learning.  The fundamental feature of a contrast set learner is the
%search for rules that differ in their distribution across groups.
%
%
%
%
%\subsection{TAR2}
%In the language of the last section,
%TAR2 is a minimal weighted
%contrast set learner.  This tool is based on two concepts: \emph{lift} and \emph{best support}.  These concepts both are used to choose among all of the possible \emph{treatments}.  A treatment is a set of attribute choices.  \emph{Lift} is a measure of how well a particular treatment selects desired outcomes as compared to the number of outcomes in the entire learning set.  (This is analogous to the concept of \emph{confidence} discussed above.  \emph{Best support} is analogous to the concept of \emph{support}.    We illustrate these concepts with the following example.
%
%The data in Table \ref{gradesTable} gives a hypothetical report of an observation of the behavior of 20 students, and their grades.  The problem is to learn from this model behaviors that are likely to lead to success as measured in course grades.  We want to mine this data by searching for patterns of behavior that are successful ones.  Here we consider two separate \emph{treatments} form the data from this table, both of which have the effect of producing good grades.  \\ 
%
%Treatment \#1: study = ``Every Day" \par
%Treatment \#2: study = ``Before Test" $\wedge$ \par Video Games = ``None" $\wedge $ Exercise = ``Some" \par
%
%The application of Treatment \#1 results in then selection of five rows of data: four resulting in a grade of A and 1 resulting in a grade of C.  Treatment \#2 selects three rows, two resulting in A, one in a B grade.  To calculate the \emph{lift} of each of these, we first calculate the \emph{baseline} value that includes all of the data.  We assign the typical grade point averages to these grades: A = 4.0, B = 3.0, C = 2.0, D = 1.0.  (There is no reason that we are constrained to these particular values except by convention.  In fact, the treatment learning algorithm would work better if we assigned much higher values to the desired outcome values.)  Note that, in the data of Table \ref{gradesTable}, there are six rows with a grade of A, 4 with a grade of B, 6 with C, and 4 with D. Here is the baseline calculation: \\ \\
%$value(baseline) = \frac{\frac{6}{20}*4.0 + \frac{4}{20}*3.0 + \frac{6}{20}*2.0 + \frac{4}{20}*1.0} {4.0 + 3.0 + 2.0 + 1.0} = 0.26$ \\ \\
%For Treatment \#1, we first calculate the weighted value of that treatment, then the \emph{lift} which is the ration of this treatment's weighted value to that of the baseline. \\ \\
%$value( study = ``Every Day" )\\ =  \frac{\frac{4}{5}*4.0 + \frac{0}{5}*3.0 + \frac{1}{5}*2.0 + \frac{0}{5}*1.0} {4.0 + 3.0 + 2.0 + 1.0} = \frac{18}{50} = 0.36$\\ \\
%$Lift(study = ``Every Day" ) = 0.36 / 0.26 \approx 1.385$\\
%
%For Treatment \#2, the analogous calculations are as follows:
%value( study  =  ``Before Test"  $\wedge$ Video Games = ``None" $\wedge $ Exercise = ``Some" )\\ =  $\frac{\frac{2}{3}*4.0 + \frac{1}{3}*3.0 + \frac{0}{3}*2.0 + \frac{0}{3}*1.0} {4.0 + 3.0 + 2.0 + 1.0} = \frac{11}{30} \approx 0.367$\\ \\
%Lift( study = ``Before Test" $\wedge$ Video Games = ``None" \\ $\wedge $ Exercise = ``Some" ) =  $0.367 / 0.26 \approx 1.41$\\
%
%Thus, both treatments appear to have a positive effect.  Numerically, Treatment \#2 appears to be preferred.  However, our intuition tells us that Treatment \#1 is much better than Treatment \#2 since it is much simpler and has a greater effect in producing 4 A's versus the 2 produced by Treatment \#2.  Tar2 incorporates this latter intuition through its evaluation of treatment preference by using \emph{best support}.   That is, Tar2 requires that a treatment produce adequate support for the desired outcome.  If a treatment does not, then it is rejected.  This allows Tar2 to avoid the problem of \emph{over learning}.
%
%Consider the \emph{best support} of these two treatments.  Treatment \#1 found 4 of the 6 best outcomes in this data for a \emph{best support} of 4/6 = 0.67; Treatment \#2 has a \emph{best support} value of 2/6 = 0.33.  Tar2 rejects any treatment whose best support is less than its \emph{minimum best support level}.  (The default for this value in Tar2 is 0.1.  However, this is user configurable, and with this small data set a more reasonable value would be 0.5)
%
%Note that a side effect of a using the \emph{best support} value is that treatments tend to consist of fewer attribute.  The more tests that are included in a treatment, the more examples from the learning set that are rejected.  This, in turn, lowers the \emph{best support} value.  Learning very specific treatments is a common problem of learning algorithms that is called \emph{over-learning}.
%
%Discuss the efficiency of TAR2 algorithm here
%
%\subsection{Combination of Saturation Effect and Contrast Set Learning}
%In a previous section, we have described a \emph{saturation effect} that is present in many SE models.  These are models whose internal structure is typified by a few dominant parameters among a much larger collection of parameters.  We can think of these as control and dependent parameters.  The strength of contrast set learning is in finding a small number of factors (treatments) that are the most effective at driving a search to solutions that are desired outcomes.  Please note the synergy in the combination of saturation effect and contrast set learning.  When a model displays a saturation effect, contrast set learning is an efficient algorithm for find the control variables.
%
%

To {\em apply}  a treatment,   TAR2 rejects all example entries
that contradict the conjunction of the attribute ranges in the
treatment. E.g., if the treatment was 
\mbox{$ humidity \ge 85 \wedge windy = true$}, then 11 of the 
lines of \fig{golfdata} would be rejected.  The ratio of classes in the remaining examples is
compared to the ratio of classes in the original example set  (in the humidity and wind treatment just given, 
this ratio would be 3/14).
The 
{\em best treatment} is the one that most increases the relative
percentage of preferred classes. In our
golf example, a single  best treatment was generated containing
{\em outlook=overcast}. \fig{golft} shows the class distribution
before and after that treatment. That is, if we select a vacation location
with {\em overcast} weather,
then 
we
should be playing $lots$ of golf, all the time.

In practice, despite the 
$\frac{n!}{s! (n - s)!}$ search, TAR2 scales well.
\fig{runtime} shows TAR2's runtime 
on 11 data sets with varying numbers of rows and columns.
Running on a relatively slow machine 
(a 333 MHz Windows machine with 512MB
of ram),  TAR2 terminated
in tens of seconds, even on data sets with up to 250,000 rows, each with nearly 100 attributes.



\section{Case Studies}\label{sec:studies}

In theory, we expect that many models contain collars and clumps.
If so, tools like TAR2 should be able to find tiny treatments that
control the behavior of the models. This section tests
that theory on several case studies.

%In section \ref{modelingInSE}, we explore modeling in diverse areas
%of software engineering to demonstrate its ubiquity and complexity.
%In section \ref{saturation}, we describe this saturation property
%of models and illustrate its presence in a variety of domains.  In
%section \ref{modelComprehension}, we discuss and illustrate the
%difficulty in understanding models.  An explanation of search-based
%software engineering in general, and, in particular, contrast set
%learning, and our specific tool that implements this, is the subject
%of section \ref{searchBasedSE}.  Our three case studies are then
%presented and explicated in section \ref{caseStudies}.
%\subsection{Inspection Policies}\label{sec:policy}
%The first
%case study contrasts treatment learning
%with traditional learners.
%It will be seen that treatments are 
%dramatically smaller, and more understandable, than the
%model learned by standard data miners.
%
%\fig{raffo}  offers a high-level view   of a quantitative 
%software process model~\cite{raffo95}.
%\begin{figure}[!t]
%\begin{center}
%\includegraphics[width=3in]{../tim/process.pdf}
%\end{center}
%\caption{High-level block diagram of a discrete event model of one
%company's software process.}\label{fig:raffo}
%\end{figure}
%At each phase of that process,
%inspections are conducted of
%the
%functional specification (FS), high-level design (HLD), low-level design (LLD), 
%and the code (CODE).
%Raffo modeled these phases, and the inspections using
%a Statemate$^{TM}$
%state-based simulation model 
%and an Extend$^{TM}$ discrete event
%model containing 30+ process steps
%with two levels of hierarchy. Some of the
%inputs to the simulation model included
%productivity rates for various processes;
%the
%volume of
%work (i.e. KSLOC);   defect detection and injection rates for all
%phases;    effort allocation percentages across all phases of the
%project;   rework costs across all phases; parameters for process
%overlap;      the amount and effect of training provided; and
%resource constraints.
%
%Model outputs are
% the development {\em expense} (person months), product {\em quality} (number of high severity defects)
%and project {\em duration} (calendar months)
%which are combined as follows:
%\begin{equation}\label{eq:util}
%\small
%\begin{array}{rl}
%utility=&40*(14 - quality)\; +\;  320*(70 - expense)\; +\\
%        &640*(24 - duration)
%\end{array}
%\end{equation}
%The justification for this style of utility function is discussed
%in detail in~\cite{raffo95}. In summary, this function was created
%after extensive debriefing of the business users.
%
%The model has been extensively validated.
%%%%% Jim -- is "face validity" a standard term?? Do we need a footnote?
%The model's process diagrams, model inputs, model parameters and
%outputs were reviewed by members of the software engineering
%process group as well as senior developers and managers.
%In other  studies, the
%model was used to accurately predict the performance of several
%past releases of the project. Finally, in {\em special case}
%studies, the model was used to predict unanticipated special
%cases. Specifically, when predicting the impact of developing
%overly complex functionality, the model predicted that development
%would take approximately double the normal development schedule.
%Initially rejected by management,
%it was later found that this
%model's predictions corresponded quite accurately with the
%company's actual experience.
%
%In this example, we will use the model to assess different software inspection policies.
%For each phase of \fig{raffo},
%four types of inspections can potentially be applied.
%These four types are listed below, sorted by their cost and effectiveness.
%For example, {\em full Fagan inspections} are
%most expensive and find the most issues. At the other end of the scale,
%doing {\em no inspections} is cheapest but finds no issues:
%
%\bi
%\item[F:]
%A {\em full Fagan inspection}~\cite{fagan86} is 
%a seven step process with pre-determined roles for
%inspection participants.  For the company studied by Raffo,
%the {\em defect detection capability}\footnote{Defect detection
%capability is the percentage of defects that are latent in the
%artifact that is being inspected that are detected.} of their full
%Fagan inspections was $TR(0.35, 0.50, 0.65)$\footnote{ $TR(a,b,c)$
%denotes a triangular distribution with minimum, mode, max of
%$a,b,c$ respectively.}. Such studies
%use between 4 and 6 staff, plus the author of the artifact being
%inspected.
%\item[B:]
%A {\em baseline inspection} is a  continuation of current
%practice at the company under study. The baseline inspection at
%this company was essentially a poorly performed Fagan inspection,
% Historical records
%show that 
%these baseline inspections  have
%varying defect detection capabilities  of 
%$\{min,mode,max\}$ =
%$\{0.13,0.21,0.30\}$.
%%%%% Jim -- should this be TR({0.13,0.30,0.21) to match the others?
%%%%% tim- yes
%\item[W:]
%{\em Walk through} inspections conducted informally
%by an
%outside consultant.
%Historical records show
%that these inspections
%have a defect detection capability
%of
%$TR(0.07, 0.15, 0.23)$.
%\item[N:] 
%{\em  No inspection};
%\ei
%%
%%\begin{figure}
%%\begin{center}
%%\includegraphics[width=3in]{../tim/utils.pdf}
%%\end{center}
%%\caption{Sorted utilities generated in case study
%%2.}\label{fig:utils}
%%\end{figure}
%Each type of inspection can be performed at 
%each phase; i.e. there are $4^4$ possible inspection polices.
%\begin{figure}
%\begin{center}
%\includegraphics[angle=90,width=2in]{../tim/inspectlog.pdf}
%\end{center}
%\caption{Utility
%frequency 
%in 12800 samples, {\em before} and {\em after} treatment.}\label{fig:utilities}
%\label{fig:run10}
%\end{figure}
%A data set for TAR2 was prepared by running each configuration 50 times;
%i.e.
%\mbox{$50*4^4=12800$} samples.
%Each run was then tagged with its utility, using \eq{util}.
%These utilities were
%discretized into four classes, 
%of approximately equal frequency:
%\bi
%\item {\em class1} : value of \eq{util} $<$ 9843
%\item {\em class2} : 9843 $\le$ value of  \eq{util} $<$ 10698
%\item {\em class3} : 10698 $\le$ value of \eq{util} $<$ 11664
%\item {\em class4} : 11664 $\le$ value of \eq{util} $\le$ 14755
%\ei
%The $before$ bar chart in   \fig{utilities} shows
%the frequency of these classes in the untreated model.
%Note that many (40\%) of the samples generate the lowest 
%$class1$ 
%utility.
%
%
%
%%\begin{figure}
%%\footnotesize
%%\begin{center}
%%\begin{tabular}{|r|r|l@{}c@{}l|}\hline
%%ID& Frequency  &  Treatment&&\\\hline
%%A & 10 &     hidesign\_12 = F&&\\
%%B & 10   &   hidesignv2\_15 = 0.5&&\\
%%C & 10   &   hidesignv1\_14 = 0.3&&\\
%%D &  9  &    hidesignv3\_16 = 0.7&&\\\hline
%%E &  5   &   hidesign\_12 = F &{\em \&}& inspDur\_49 in 2.6 ${\ldots}$ 4.7\\
%%F &  4    &  hidesign\_12 = F &{\em \&}& hidesignv2\_15 = 0.5\\
%%G &  4     & hidesignv1\_12 = 0.3 &{\em \&}& loDist\_23 = tr\\
%%H &  4  &    codev2\_35 = 0.5 &{\em \&}& hiStaff\_17 = 4\\
%%I &  4   &   corErr\_41 in 72 ${\ldots}$ 105 &{\em \&}& loStaff\_27 = 4\\
%%J &  4    &  hidesignv1\_14 = 0.3 &{\em \&}& hidesignv3\_16 = 0.7\\
%%K &  4     & hiStaff\_17 = 4 &{\em \&}& hidesignv3\_16 = 0.7\\\hline
%%\end{tabular}
%%%%%% Jim - in this table and in the explanation in the text, it might be better to use more 
%%%%%% descriptive names.  Why do we care what column the data appeared in. However,
%%%%%% knowing what high design = 0.5 means would be useful.
%%\end{center}
%%\caption{Treatments found in the ten 90\% samples
%%of 12800 samples of the \fig{raffo} model. 
%%Each attribute is labeled with its
%%column number; e.g. $hidesign\_12$ appears in the twelfth column of the input.}\label{fig:10rx}
%%\end{figure}
%
%TAR2 was then applied to learn treatments
%that distinguish the desired $class4$ utilities
%from the rest. 
%The best treatment generated by the algorithm 
%was very small  only recommended changing one
%of the inspection processes; i.e.
%\[ hidesign\_12 = F\]
%
%The $after$ bar chart of \fig{utilities} shows the effect of imposing this
% treatment of
%{\em hidesign\_12=F}\footnote{In this data set, each attribute is labeled with its
%column number so  $hidesign\_12$ appears in the twelfth column the input.}
%(full Fagan inspections for high-level designs)
%onto the simulator. 
%The treated model is much improved:
%it generates zero $class1$ and $class2$ outputs and, in 80\% of cases,
%generates $class4$ outputs.
%Further, the improvement was achieved without having to control the inspection policies in the other phases.
%
%If we were not concerned with finding minimal solutions, TAR2 would
%have been called again on data generated from the  inspection model,
%after the inputs have been constrained 
%to {\em hidesign\_12=F}. This iterative process could repeat until it was shown that
%further constraints did not improve the output. Such {\em interactive treatment
%learning} has been applied on other models (e.g. see ~\cite{fea02a}).
%However, for the sake of exposition, 
%the execution of this model is not explored further.
%
%
%\begin{figure}[!t]
%\renewcommand{\baselinestretch}{1}
%\center\small
%\begin{tabular}{|p{.95\linewidth}|}\hline
%C4.5 and CART are 
%{\em iterative dichotomization} learners
%that seek
%the best attribute value $splitter$ that most simplifies the data that
%fall into the different splits. 
%Each such splitter becomes a root of a tree.
%Sub-trees are generated
%by 
%calling iterative dichotomization recursively
%on each of the splits.
%
%CART is defined for continuous target concepts 
%and its  $splitters$ strive to reduce the standard deviation of the data that
%falls into
%each split.
%C4.5 is defined for discrete class classification 
%and
%uses an information-theoretic measure
%to describe the diversity of classes within a data set.
%
%A
%leaf generated by CART stores the average value of the class selected
%by the branch while a leaf generated by C4.tree stores the most
%frequency  class.  Hence, C4.5 is called a {\em decision tree}
%learner while CART is called a {\em regression tree}.\\\hline
%\end{tabular}
%\caption{About C4.5 and CART}\label{fig:c45cart}
%\end{figure}\begin{figure}[!b]
%\renewcommand{\baselinestretch}{1}
%\begin{alltt}\scriptsize
%corErr\_gg50 <= 72: class1 
%corErr\_gg50 > 72
%|   corErr\_gg50 <= 154
%|   |   spec\_gg2 = b
%|   |   |   hiDist\_gg13 = 0
%|   |   |   |   corErr\_gg11 <= 17: class1 
%|   |   |   |   corErr\_gg11 > 17: class2 
%|   |   |   hiDist\_gg13 = tr
%|   |   |   |   corErr\_gg31 <= 18: class1 
%|   |   |   |   corErr\_gg31 > 18
%|   |   |   |   |   inspEff\_gg19 <= 33.742185: class1 
%|   |   |   |   |   inspEff\_gg19 > 33.742185: class2 
%|   |   spec\_gg2 = f
%|   |   |   corErr\_gg21 <= 22
%|   |   |   |   detCap\_gg38 <= 0.563188
%|   |   |   |   |   inspDur\_gg10 <= 117.043523
%|   |   |   |   |   |   corErr\_gg50 <= 120: class1 
%|   |   |   |   |   |   corErr\_gg50 > 120
%|   |   |   |   |   |   |   inspDur\_gg40 <= 292.445892: class2 
%|   |   |   |   |   |   |   inspDur\_gg40 > 292.445892: class1 
%|   |   |   |   |   inspDur\_gg10 > 117.043523: class1 
%|   |   |   |   detCap\_gg38 > 0.563188: class2 
%|   |   |   corErr\_gg21 > 22: class2 
%|   |   spec\_gg2 = n
%|   |   |   inspEff\_gg29 <= 336.924853: class2 
%|   |   |   inspEff\_gg29 > 336.924853: class1 
%|   |   spec\_gg2 = w
%|   |   |   corErr\_gg11 <= 3: class1 
%|   |   |   corErr\_gg11 > 3
%|   |   |   |   corErr\_gg11 <= 4
%|   |   |   |   |   inspEff\_gg9 <= 32.423212: class2 
%|   |   |   |   |   inspEff\_gg9 > 32.423212
%|   |   |   |   |   |   inspDur\_gg10 <= 35.939846
%|   |   |   |   |   |   |   detCap\_gg8 <= 0.110608: class2 
%|   |   |   |   |   |   |   detCap\_gg8 > 0.110608: class1 
%|   |   |   |   |   |   inspDur\_gg10 > 35.939846: class2 
%|   |   |   |   corErr\_gg11 > 4
%|   |   |   |   |   detCap\_gg8 <= 0.145107
%|   |   |   |   |   |   inspEff\_gg9 <= 49.227938: class1 
%|   |   |   |   |   |   inspEff\_gg9 > 49.227938
%|   |   |   |   |   |   |   detCap\_gg8 <= 0.131955: class2 
%|   |   |   |   |   |   |   detCap\_gg8 > 0.131955: class1 
%|   |   |   |   |   detCap\_gg8 > 0.145107
%|   |   |   |   |   |   inspEff\_gg9 <= 33.741217: class1 
%|   |   |   |   |   |   inspEff\_gg9 > 33.741217: class2 
%|   corErr\_gg50 > 154
%|   |   detCap\_gg8 <= 0.618237: class2 
%|   |   detCap\_gg8 > 0.618237
%|   |   |   inspDur\_gg30 <= 137.500433: class3 
%|   |   |   inspDur\_gg30 > 137.500433: class2 
%\end{alltt}
%\caption{A decision tree learned via C4.5.}\label{fig:dt}
%\end{figure}
%%and a 
%%very large range in the 
%%computed $utility$ was observed 
%%(5,000 to 15,000).
%%  3000|   2| 
%%  4000|   3| 
%%  5000|   9| *
%%  6000|  30| ****
%%  7000|  63| *********
%%  8000| 119| ****************
%%  9000| 210| ****************************
%% 10000| 273| *************************************
%% 11000| 296| ****************************************
%% 12000| 181| ************************
%% 13000|  88| ************
%% 14000|  23| ***
%% 15000|   3|
%
%
%%  6000|  39| ****
%%  8000| 182| ****************
%% 10000| 483| *************************************
%% 12000| 487| ************************
%% 14000|  111| ***
%%
%
%
%\begin{figure*}[!t]
%\renewcommand{\baselinestretch}{1}
%\begin{alltt}\scriptsize
%policy=NNFN,BNNF,WNNF,NNWF,BBBB,FFFF,NNNF,BFFF <= 0.5 : 
%|   policy=NNWN,NNNW,WNNW,BNNW,WNNB,BNNB,WWWW,NNNB,NNWW, FNNF,NNWB,NNFN,BNNF,WNNF,NNWF,BBBB,FFFF,NNNF,BFFF <= 0.5 : 
%|  |   policy=WNNN,NWNN,FNNW,FNNB,BNNN,NNWN,NNNW,WNNW,BNNW,WNNB,BNNB,WWWW,NNNB,NNWW,FNNF,NNWB,NNFN,BNNF,WNNF,
%              NNWF,BBBB,FFFF,NNNF,BFFF <= 0.5 : 
%|  |  |   _detCap_8 <= 0.431 : 6940 
%|  |  |   _detCap_8 >  0.431 : 8180 
%|  |   policy=WNNN,NWNN,FNNW,FNNB,BNNN,NNWN,NNNW,WNNW,BNNW,WNNB,BNNB,WWWW,NNNB,NNWW,FNNF,NNWB,NNFN,BNNF,WNNF,
%              NNWF,BBBB,FFFF,NNNF,BFFF >  0.5 : 
%|  |  |   _detCap_8 <= 0.491 : 
%|  |  |  |   _inspDur_10 <= 94 : 8780 
%|  |  |  |   _inspDur_10 >  94 : 7860 
%|  |  |   _detCap_8 >  0.491 : 9320 
%|   policy=NNWN,NNNW,WNNW,BNNW,WNNB,BNNB,WWWW,NNNB,NNWW,FNNF,NNWB,NNFN,BNNF,WNNF,NNWF,BBBB,FFFF,NNNF,BFFF >  0.5 : 
%|  |   policy=BNNB,WWWW,NNNB,NNWW,FNNF,NNWB,NNFN,BNNF,WNNF,NNWF,BBBB,FFFF,NNNF,BFFF <= 0.5 : 9750 
%|  |   policy=BNNB,WWWW,NNNB,NNWW,FNNF,NNWB,NNFN,BNNF,WNNF,NNWF,BBBB,FFFF,NNNF,BFFF >  0.5 : 10300 
%policy=NNFN,BNNF,WNNF,NNWF,BBBB,FFFF,NNNF,BFFF >  0.5 : 
%|   policy=NNWF,BBBB,FFFF,NNNF,BFFF <= 0.5 : 
%|  |   _detCap_38 <= 0.418 : 10700 
%|  |   _detCap_38 >  0.418 : 11400 
%|   policy=NNWF,BBBB,FFFF,NNNF,BFFF >  0.5 : 
%|  |   _corErr_50 <= 155 : 11900 
%|  |   _corErr_50 >  155 : 
%|  |  |   policy=NNNF,BFFF <= 0.5 : 12400 
%|  |  |   policy=NNNF,BFFF >  0.5 : 
%|  |  |  |   _detCap_38 <= 0.519 : 12500 
%|  |  |  |   _detCap_38 >  0.519 : 13600 
%\end{alltt}
%\caption{A regression tree learned by CART from data generated
%from the \fig{raffo} model.
%In this figure, and \protect\fig{lsr},
%policies are denoted as a four-part sequence
%describing the inspection policy at each phase.
%For example, ``FFFN'' denotes 
%using
%no inspections for code but
%full Fagan inspections for all earlier phases.
%}\label{fig:cart}
%
%
%\end{figure*}
%
%\begin{figure*}[!t]
%\renewcommand{\baselinestretch}{1}
%\begin{alltt}\scriptsize
%utility = 7370
% + 1220policy=WNNN,NWNN,FNNW,FNNB,BNNN,NNWN,NNNW,WNNW,BNNW,WNNB,BNNB,WWWW,
%              NNNB,NNWW,FNNF,NNWB,NNFN,BNNF,WNNF,NNWF,BBBB,FFFF,NNNF,BFFF
% + 258policy=FNNB,BNNN,NNWN,NNNW,WNNW,BNNW,WNNB,BNNB,WWWW,NNNB,NNWW, FNNF,
%             NNWB,NNFN,BNNF,WNNF,NNWF,BBBB,FFFF,NNNF,BFFF
% + 640policy=NNWN,NNNW,WNNW,BNNW,WNNB,BNNB,WWWW,NNNB,NNWW,FNNF,NNWB,NNFN,BNNF,WNNF,NNWF,BBBB,FFFF,NNNF,BFFF
% + 505policy=NNNW,WNNW,BNNW,WNNB,BNNB,WWWW,NNNB,NNWW,FNNF,NNWB,NNFN,BNNF,WNNF,NNWF,BBBB,FFFF,NNNF,BFFF
% - 190policy=WNNW,BNNW,WNNB,BNNB,WWWW,NNNB,NNWW,FNNF,NNWB,NNFN,BNNF,WNNF,NNWF,BBBB,FFFF,NNNF,BFFF
% + 206policy=BNNB,WWWW,NNNB,NNWW,FNNF,NNWB,NNFN,BNNF,WNNF,NNWF,BBBB,FFFF,NNNF,BFFF
% - 177policy=WWWW,NNNB,NNWW,FNNF,NNWB,NNFN,BNNF,WNNF,NNWF,BBBB,FFFF,NNNF,BFFF
% + 890policy=NNNB,NNWW,FNNF,NNWB,NNFN,BNNF,WNNF,NNWF,BBBB,FFFF,NNNF,BFFF
% - 296policy=NNWW,FNNF,NNWB,NNFN,BNNF,WNNF,NNWF,BBBB,FFFF,NNNF,BFFF
% + 545policy=NNFN,BNNF,WNNF,NNWF,BBBB,FFFF,NNNF,BFFF
% + 640policy=WNNF,NNWF,BBBB,FFFF,NNNF,BFFF
% + 459policy=NNWF,BBBB,FFFF,NNNF,BFFF - 143policy=BBBB,FFFF,NNNF,BFFF
% + 835policy=NNNF,BFFF - 142_spec_2=n,b + 27_spec_2=b + 3690_detCap_8
% - 135_inspEff_9 - 7320_inspDur_10 - 64400_corErr_11 - 760_detCap_18
% - 134_inspEff_19 - 7310_inspDur_20 - 64300_corErr_21 - 9100_detCap_28
% - 134_inspEff_29 - 7320_inspDur_30 - 64300_corErr_31 + 6170_detCap_38
% - 134_inspEff_39 - 7320_inspDur_40 - 64400_corErr_41
%+ 21500_inspEff_48 + 1.17e6_inspDur_49 + 64400_corErr_50
%\end{alltt}
%\caption{Linear regression learned from data generated
%from the \fig{raffo} model. }\label{fig:lsr}
%\end{figure*}
%In terms of the discussion in \tion{easyhard}, an important feature
%of to {\em hidesign\_12=F} is that it is stable despite uncertainty in other parameters.
%Despite large scale variation of all other parameters in this model,
%this treatment yielded the effect seen in \fig{utilities}.  In terms
%of supporting commercial practices, this is a very useful result.
%Large corporations may have little impact on their satellite
%organizations or contractors. Hence, they often have to carefully
%select what policies to implement across the company. 
%In terms of \eq{util},
%the treatment learned in this example representing the {\em least action}
%that offers the {\em most reward}.
%
%Also, in terms of advocating treatment learning, the most important feature
%of this example  is what is {\em missing}.  To learn its treatments,
%TAR2 imported samples with 51 variables (50 inputs and one utility
%score). It then generated treatments, the best of
%which, used only one of the inputs.
%Other data miners, such as C4.5 and CART (described in~\fig{c45cart}),
%are far less
%succinct.
%For example, \fig{dt}
%show the results of passing the inspection model data 
%to C4.5~\cite{quinlan86}. \fig{cart} and \fig{lsr} pass
%shows the  
%output from the CART and linear regression learners:
%\bi
%\item
%C4.5 and CART use the {\em iterative dichotimzation} algorithm
%described in 
%\fig{c45cart}.
%\item
%Linear regression
%tries to fit one straight line through the observed values.
%The line offers a set of predicted values and the distance from
%these predicted values to the actual values is a measure of the error
%associated with that line. Linear regression tools such as the least
%squares regression package search for a
%line that minimizes that sum of the squares of the error.
%\item
%C4.5 predicts for discrete class symbols (e.g. {\em class1, class2, class3, class4})
%so this algorithm used the same data as TAR2.
%\item
%Linear regression and CART make numeric
%predictions.
%These algorithms used the TAR2 data
%with the $classN$ symbols replaced by raw numerics of \eq{util}.
%\ei
%
%A comparison of the output from
%TAR2, C4.5 (in \fig{dt}),
%and results from CART and linear regression (in \fig{cart} and \fig{lsr})
%%%%% Jim -- Could the results of these be summarized rather than presenting the entire
%%%%% data of these figures?  That would save some space.  It seems that the details of
%%%%% the other algorithms are not as relevant to this paper.  It least, they could be moved
%%%%% to an appendix so that they don't interrupt the flow of the paper.
%demonstrate that
%standard methods of summarizing data (linear regression,  decision trees,
%regression trees)
%can generate much larger theories than treatment learning.
%The reason for this is very simple.
%Theories learned from iterative dichotomization
%describe the features that separate all of the target variables.
%However, treatments just describe
%the minimal deltas {\em between} preferred and undesirable targets. 
%
%Another advantage of treatment learning is that
%it is much easier to derive actions from treatments than from the standard
%methods shown in Figures \ref{fig:dt}, \ref{fig:lsr}, \ref{fig:cart}.
%To be sure, decision
%trees can be analyzed to find branch values
%that most selected for preferred classes while most discarding undesired classes
%(the initial TAR2 prototype
%was such a post-processor). However, TAR2 achieves the same result
%%%%% Jim -- Time, what is the best reference to tar1?
%%%%% Tim -- none. never published.
%directly without the need to interface to another learner.
%
%To complete
% a different splitter: it seeks 
% The algorithm recursively {\em splits}
%a data set according to tests on attribute values in order to
%separate the possible predictions (although attribute tests are chosen one at a
%time in a greedy manner, they are dependent on results of previous
%tests). C4.5/J48 uses information theory to assess candidate splits:
%the {\em best split} is the one that {\em most simplifies} the target
%concept.  
%Concept simplicity is measured using information theory.
%Suppose a data set has 80\% low utility inspection configurations and  20\% high utility
%inspection configurations,
%then that data set has a class distribution $C_0$ with classes $c(1)=low$ and $c(2)=high$
%with frequencies $n(1)=0.8$ and $n(2)=0.2$.
%The
%number of bits required to encode an arbitrary class distribution $C_0$ is $H(C_0)$ defined as follows:
%\begin{equation}\label{eq:ent}{
%\left.\begin{array}{rcl}
%N&=&\sum_{c{\in}C}n(c)\\
%p(c)& =& n(c)/N \\
%H(C)&=& -{\sum}_{c{\in}C} p(c)log_2p(c)
%\end{array}\right\}
%}\end{equation}
%A split divides $C_0$ (before the split) into $C_1$ and $C_2$
%(after the split). The best split leads to the simplest concepts;
%i.e. maximize $H(C_0) - (H(C_1) + H(C_2))$.
%
%
%highest utility group 
%Ta
%Five learners were applied to this data: {\em linear regression},
%{\em regression trees}, {\em model trees}, {\em entropy-based
%decision tree learners}, and the TAR2 treatment learner.  These
%learners wide spread XXX~\cite{witten99}.  Linear regression is a
%standard statistical method that fits a straight line to a set of
%points.  {\em Linear regression} packages search for lines that
%maximize the correlation between the actual and predicted values.
%A drawback with linear regression is that the {\em same} line is
%fitted through all points. That is, linear regression assumes that
%all the data comes from a single simple linear distribution. Where
%this is not true,
% it may be better to divide the space into
%different regions and then make a different decision about each
%region.  Two techniques for doing so are {\em regression trees} and
%{\em model trees}.
%
%{\em Regression tree} learners such as CART~\cite{breiman84} generate
%decision trees whose leaves are numeric values. Numeric values are
%calculated from these trees by starting at the root, and following
%the branches that are relevant to the current situation.
%
%The leaves of a regression tree are very different to the leaves of a {\em model
%tree}~\cite{quinlan92b}. 
%The leaves of a regression tree store the average value of the training
%instances that fall down the branches to that leaf.
%The leaves of a model tree, on the other hand, 
%summarize the data that falls to the leaves as one linear regression  model per leaf.
%That is, branches in a regression tree terminate on a single value while
%the branches in a model tree learner terminate on a equation.
%
%
%\subsection{Other Case Studies}
%
%
%\subsection{Sensitivity}
%
%TAR2 was used to explore the simulation data. The best treatment
%found was to use the following configuration: \bi \item No
%  functional specifications inspections; \item Baseline
%inspections for high level design; i.e. no change from current practice; \item
%Full Fagan  for low level design and
% code reviews.\ei
%
%Further experimentation showed that no larger treatment had a greater impact.
%That is, other factors in the \fig{raffo} model were not as influential as the
%selection of inspection type. Given this configuration, TAR2 predicted the
%distribution of utility values seen as the {\em best} plot of \fig{utils}.
%When compared to the {\em baseline} plot, we see that this treatment results in
%a significant improvement in model behavior. Also, the variance in the
%utilities has been greatly reduced.
%
%This treatment was assessed via {\em 10-way cross validation}. The
%{\em best} plot of \fig{utils} was observed to be the average
%improvement seen under cross validation.
%
%Note that contrary to the truism that early life cycle detection
%and error removal is valuable, this particular project was most
%impacted by spending {\em less} effort on early life cycle
%inspections and {\em more} effort on late life cycle inspections.
%
%%\begin{figure*}[!t]
%%\begin{alltt}\scriptsize
%%utility = 7290
%% + 1360policy=WNNN,NWNN,FNNW,FNNB,BNNN,NNWN,NNNW,WNNW,BNNW,WNNB,BNNB,WWWW,NNNB,NNWW,FNNF,NNWB,NNFN,BNNF,WNNF,
%%              NNWF,BBBB,FFFF,NNNF,BFFF
%% + 612policy=NNWN,NNNW,WNNW,BNNW,WNNB,BNNB,WWWW,NNNB,NNWW,FNNF,NNWB,NNFN,BNNF,WNNF,NNWF,BBBB,FFFF,NNNF,BFFF
%% + 474policy=NNNW,WNNW,BNNW,WNNB,BNNB,WWWW,NNNB,NNWW,FNNF,NNWB,NNFN,BNNF,WNNF,NNWF,BBBB,FFFF,NNNF,BFFF
%% + 544policy=NNNB,NNWW,FNNF,NNWB,NNFN,BNNF,WNNF,NNWF,BBBB,FFFF,NNNF,BFFF
%% + 1180policy=WNNF,NNWF,BBBB,FFFF,NNNF,BFFF
%% + 802policy=NNNF,BFFF + 4050_detCap_8 - 4.77_inspDur_10
%% - 79_corErr_11 - 5680_detCap_28 + 51.9_corErr_31
%% + 5810_detCap_38 - 2.26_inspDur_40 - 19.5_corErr_41
%%\end{alltt}
%%\caption{Model trees.}\label{fig:results}
%%\end{figure*}
%%
%\section{Other Case Studies}
%
%
%We have previously discussed the complexity in the DDP model that
%relates requirements to risks, and risks to mitigations.  To mine
%this complex data (as visually displayed in Figure~\ref{DDPfigure}),
%Kiper and Feather \cite{kiper04} have used simulated annealing (a
%search-based approach to SE -- see section \ref{subsection-Search-basedSE})
%to find a set of near-optimal solutions that meet a cost bound.  In
%exploring, this region of near-optimality, these researchers used
%cluster analysis to find those sets of mitigations that agree to
%within 95\%.  In the case study that they present in \cite{kiper04},
%there are 58 possible mitigations from which engineering managers
%must choose.  Thus, there are $2^{58} =  \sim10^{17}$ possible
%choices.  The simulated annealing search for near optimal solutions
%sets found about 3,400 solutions that were within 95\% of the best
%value of the objective function and satisfied the cost constraint
%of \$1,000,000.   This set of over 3000 sets of mitigations represents
%a model that is still too complex from humans to easily comprehend.
%To this set, these researchers applied a cluster analysis algorithm
%that looked for clusters of mitigation sets which were almost
%identical in that they shared 85\% of the mitigation choices.  Figure
%\ref{clusters} visual displays a group of such clusters of mitigations.
%Each row represents one mitigation; each column displays a cluster
%where the darkness of the shading gives a measure of the number of
%times that mitigation appears in this cluster.  Again, the point
%here is that, in complex data, it is common to find structure.
%
%

%\documentclass[journal]{../one/IEEEtran}
%\usepackage{alltt}
%\usepackage{syntax}
%\usepackage{bar}
%\usepackage{wrapfig}
%\usepackage{rotating}
%\usepackage{cite}      % Written by Donald Arseneau
%                        % V1.6 and later of IEEEtran pre-defines the format
%                        % of the cite.sty package \cite{} output to follow
%                        % that of IEEE. Loading the cite package will
%                        % result in citation numbers being automatically
%                        % sorted and properly "ranged". i.e.,
%                        % [1], [9], [2], [7], [5], [6]
%                        % (without using cite.sty)
%                        % will become:
%                        % [1], [2], [5]--[7], [9] (using cite.sty)
%                        % cite.sty's \cite will automatically add leading
%                        % space, if needed. Use cite.sty's no adjust option
%                        % (cite.sty V3.8 and later) if you want to turn this
%                        % off. cite.sty is already installed on most LaTeX
%                        % systems. The latest version can be obtained at:
%                        % http://www.ctan.org/tex-archive/macros/latex/contrib/supported/cite/
%
%\usepackage{graphicx}  % Written by David Carlisle and Sebastian Rahtz
%                        % Required if you want graphics, photos, etc.
%                        % graphicx.sty is already installed on most LaTeX
%                        % systems. The latest version and documentation can
%                        % be obtained at:
%                        % http://www.ctan.org/tex-archive/macros/latex/required/graphics/
%                        % Another good source of documentation is "Using
%                        % Imported Graphics in LaTeX2e" by Keith Reckdahl
%                        % which can be found as esplatex.ps and epslatex.pdf
%                        % at: http://www.ctan.org/tex-archive/info/
%
%\usepackage{subfigure} % Written by Steven Douglas Cochran
%                        % This package makes it easy to put sub figures
%                        % in your figures. i.e., "figure 1a and 1b"
%                        % Docs are in "Using Imported Graphics in LaTeX2e"
%                        % by Keith Reckdahl which also documents the graphicx
%                        % package (see above). sub figure.sty is already
%                        % installed on most LaTeX systems. The latest version
%                        % and documentation can be obtained at:
%                        % http://www.ctan.org/tex-archive/macros/latex/contrib/supported/subfigure/
%
%\usepackage{url}       % Written by Donald Arseneau
%                        % Provides better support for handling and breaking
%                        % URLs. url.sty is already installed on most LaTeX
%                        % systems. The latest version can be obtained at:
%                        % http://www.ctan.org/tex-archive/macros/latex/contrib/other/misc/
%                        % Read the url.sty source comments for usage information.
%
%%\usepackage{stfloats}  % Written by Sigitas Tolusis
%                        % Gives LaTeX2e the ability to do double column
%                        % floats at the bottom of the page as well as the top.
%                        % (e.g., "\begin{figure*}[!b]" is not normally
%                        % possible in LaTeX2e). This is an invasive package
%                        % which rewrites many portions of the LaTeX2e output
%                        % routines. It may not work with other packages that
%                        % modify the LaTeX2e output routine and/or with other
%                        % versions of LaTeX. The latest version and
%                        % documentation can be obtained at:
%                        % http://www.ctan.org/tex-archive/macros/latex/contrib/supported/sttools/
%                        % Documentation is contained in the stfloats.sty
%                        % comments as well as in the presfull.pdf file.
%                        % Do not use the stfloats baseline float ability as
%                        % IEEE does not allow \baselineskip to stretch.
%                        % Authors submitting work to the IEEE should note
%                        % that IEEE rarely uses double column equations and
%                        % that authors should try to avoid such use.
%                        % Do not be tempted to use the cited.sty or
%                        % midfloat.sty package (by the same author) as IEEE
%                        % does not format its papers in such ways.
%
%\usepackage{amsmath}   % From the American Mathematical Society
%                        % A popular package that provides many helpful commands
%                        % for dealing with mathematics. Note that the AMSmath
%                        % package sets \interdisplaylinepenalty to 10000 thus
%                        % preventing page breaks from occurring within multiline
%                        % equations. Use:
%%\interdisplaylinepenalty=2500
%                        % after loading amsmath to restore such page breaks
%                        % as IEEEtran.cls normally does. amsmath.sty is already
%                        % installed on most LaTeX systems. The latest version
%                        % and documentation can be obtained at:
%                        % http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/
%
%
%
%% Other popular packages for formatting tables and equations include:
%
%\usepackage{array}
%% Change the following for any hyphenation issues.  These are just examples. (Not actually used yet.)
%\hyphenation{op-tical net-works semi-conduc-tor}
%\input{../jim/tricks.sty}
%\input{../tim/tricks.sty}
%\input{../jeremy/tricks.sty}
%\begin{document}
%%
%% paper title
%\title{Exploiting Models in Software Engineering}
%%
%%
%% author names and IEEE memberships
%% note positions of commas and non breaking spaces ( ~ ) LaTeX will not break
%% a structure at a ~ so this keeps an author's name from being broken across
%% two lines.
%% use \thanks{} to gain access to the first footnote area
%% a separate \thanks must be used for each paragraph as LaTeX2e's \thanks
%% was not built to handle multiple paragraphs
%\author{Tim Menzies}
%% <-this % stops a space\thanks{Contact information: kiperjd@muohio.edu, timm@cs.pdx.edu, jegreen@cs.pdx.edu .}}
%% note the % following the last \IEEEmembership and also the first \thanks - 
%% these prevent an unwanted space from occurring between the last author name
%% and the end of the author line. i.e., if you had this:
%% 
%% \author{....lastname \thanks{...} \thanks{...} }
%%                     ^------------^------------^----Do not want these spaces!
%%
%% a space would be appended to the last name and could cause every name on that
%% line to be shifted left slightly. This is one of those "LaTeX things". For
%% instance, "A\textbf{} \textbf{}B" will typeset as "A B" not "AB". If you want
%% "AB" then you have to do: "A\textbf{}\textbf{}B"
%% \thanks is no different in this regard, so shield the last } of each \thanks
%% that ends a line with a % and do not let a space in before the next \thanks.
%% Spaces after \IEEEmembership other than the last one are OK (and needed) as
%% you are supposed to have spaces between the names. For what it is worth,
%% this is a minor point as most people would not even notice if the said evil
%% space somehow managed to creep in.
%%
%% The paper headers
%%\markboth{Journal of \LaTeX\ Class Files,~Vol.~1, No.~11,~November~2002}{Shell \MakeLowercase{\textit{et al.}}: Bare Demo of IEEEtran.cls for Journals}
%% The only time the second header will appear is for the odd numbered pages
%% after the title page when using the two side option.
%% 
%% *** Note that you probably will NOT want to include the author's name in ***
%% *** the headers of peer review papers.                                   ***
%
%% If you want to put a publisher's ID mark on the page
%% (can leave text blank if you just want to see how the
%% text height on the first page will be reduced by IEEE)
%%\pubid{0000--0000/00\$00.00~\copyright~2002 IEEE}
%
%% use only for invited papers
%%\specialpapernotice{(Invited Paper)}
%
%% make the title area
%
%%\footrulewidth 0.0pt\headrulewidth 0.0pt
%%\lhead{}\rhead{}\chead{}\rfoot{}\lfoot{}\cfoot{}
%%
%%\rhead{\includegraphics[height=0.5in]{ASEbiglogo.eps}}
%%\lhead{{\footnotesize { Submitted to the 16th IEEE International
%%Conference on Automated Software Engineering
%%                                                                          Nov
%%20-22, San Diego, USA.\newline
%%\url{http://sigart.acm.org/Conferences/ase/}\newline WP ref:
%%01/choices/ \today }}} \headrulewidth 0.4pt
%
%%\documentstyle[alltt,icse2000,twocolumn,url,bar,epsfig,times,alltt,array,amssymb,graphicx,ifthen,color]{article}
%
%% Changes:
%%  Page limit: 10 pages
%%  Abstract limit: 200 words
%%  Contact information is now gall@infosys.tuwien.ac.at
%%  URL for author kit changed: needs to be filled in.
%%  All other font and sizing information is the same:
%%    check whether it still applies.
%
%%\makeatletter
%%\def\fnum@figure{\sffamily\figurename~\thefigure}
%%\def\fnum@table{\sffamily\tablename~\thetable}
%%\makeatother
%
\newenvironment{code}{\begin{alltt}\small}{\normalsize\end{alltt}}
%
\newenvironment{ccode}{\begin{code}\begin{center}}{\end{center}\end{code}}
%
%
%
%
%
%\newcommand{\DO}  {{\sffamily \{}}
%\newcommand{\FOR}{{\underline {\sffamily for}}}
%\newcommand{\DONE}{ {\sffamily \}}}
%\newcommand{\IF}{{\underline {\sffamily if}}}
%\newcommand{\FI}{{\underline {\sffamily fi}}}
%\newcommand{\THEN}{{\underline {\sffamily then}}}
%\newcommand{\ELSE}{{\underline {\sffamily else}}}
%\newcommand{\WHEN}{{\underline {\sffamily when}}}
%\newcommand{\UNTIL}{{\underline {\sffamily until}}}
%\newcommand{\AND}{{\underline {\sffamily and}}}
%\newcommand{\TO}{{\underline {\sffamily to}}}
%\newcommand{\IS}{ {\sffamily $\leftarrow$}}
%
%\newcommand{\NIL}{ {\sffamily $\emptyset$}}
%\newcommand{\REPEAT}{{\underline {\sffamily repeat}}}
%\newcommand{\RETURN}{{\underline {\sffamily return}}}
%
%\shortverb{!}
%
%\copyrightspace
%
% If you want to print drafts of the paper with a draft
% notice in the copyright space, comment out the \copyrightspace
% line above and include the \submitspace line below instead.
%
%\submitspace{Draft of paper submitted to ASE 2000.
%\\WP:b/00/ase/whatif(\today).}


% Page number on the initial page can be omitted in both the review and
% final submission (and should be removed in the final submission).  The
% line below does that.


% In the review submission, page numbers should appear (they can be omitted
%  from the first page).  The page style command below puts them in.
% In the final submission of accepted papers, page numbers should be
%  omitted; remove or comment out the page style line below to omit them.


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


%program too simple? XXX space too simple? no- decision tree

\subsection{Studying the CMM}\label{sec:cmm}

The previous  studied explored a numeric
model where all the influences were precisely specified.
This second case study takes a numeric model and adds a large
degree of uncertainty in the numerics.
This second study shows that, even in presence of large degrees of uncertainty,
TAR2 can still find useful treatments.

An important feature of this second study is that it analyzes a class of models that
can defeat standard methods. The model contains dozens of if-then rules; i.e.
it is neither linear nor continuous: small changes in the environment can
lead to ``cliffs'' where the model behavior changes abruptly. Also, the model
contains nondeterministic choices (see the $rany$ operator, discussed below)
and so its behavior can be highly noisy.

This study uses a rule-based model of the costs
and 
benefits model of CMM level 2 (hereafter,
CMM2)~\cite[p125-191]{paulk95}. We elected to study CMM2 since, in our
experience, many organizations can achieve at least this level.
CMM2 is less concerned with issues of (e.g.) which design pattern
to apply, than with what overall project structure should be
implemented. Improving CMM2-style decisions is important since in
early software life cycle, many CMM2-style decisions affect the
resource allocation for the rest of the project.

CMM2 was encoded using the JANE propositional rule-based language~\cite{me01e}. 
JANE's rules take the form \mbox{$Goal\; if\; SubGoals$} such as the one
shown in \fig{jane}.
\begin{figure}[!h]
\renewcommand{\baselinestretch}{1}
\begin{code}
{\scriptsize
stableRequirements  
    if   effectiveReviews            
    and requirementsUsed            
    and sEteamParticipatesInPlanning 
    and documentedRequirements       
    and sQAactivities                
    and (reviewRequirementChanges    
          rany softwareConfigurationManagement 
          rany baselineChangesControlled      
          rany workProductsIdentified        
          rany softwareTracking
        ).
}\end{code}
\caption{Part of CMM2, encoded in the JANE language.}\label{fig:jane}
\end{figure}

JANE is a backward chaining language:
to prove a $Goal$, JANE tries to find rules that prove each of  the $SubGoals$.
Each $SubGoal$ contributes some $Cost$  and $Chances$
to the $Goal$. 
JANE's $Chances$ define the extent to which a belief in one vertex
can propagate to another. $Cost$s  let an analyst  model the
common situation where some of the $Cost$ of some procedure is
amortized by reusing its results many times. Hence, the {\em
first} time we use a proposition, we incur its $Cost$ but
afterwards, that proposition is free of charge.

The $Cost$ and  $Chances$ of  a proposition
are  either provided by the
JANE programmer or computed at runtime via a traversal of the
rules:
\bi
\item
When searching {\em X
if not A}, the $Chances$ of {\em X} are {\em 1-Chances(A)}
and $Cost(X)=Cost(A)$.
\item
When searching   {\em X if A $and$ B $and$ C}, the $Chances$ and
$Costs$ of
{\em X} are (respectively)
the product of the chances and the sum of the costs
of {\em A,B,C}. 
\item
When
searching {\em X if A $or$ B $or$ C}, then the $Cost$ and $Chances$
of {\em X} are taken from the first member of {\em A,B,C} that is
satisfied.  
\ei

These
$and, or, not$ operators can be
insufficient to capture the  decision making of business users.
For examples,
in our experience,
business users select CMM2 options, often in a somewhat 
arbitrary manner.
To model this, JANE  includes a  $rany$ operator
(short for ``random any''):
\bi
\item
The $rany$ operator is  like $or$ except that (e.g.) {\em
X if A $rany$ B $rany$ C} succeeds if some
random number of {\em A,B,C}  (greater than one) succeeds.
Unlike $and,or$ which explore their operands in a left-to-right
order, $rany$ explores its $SubGoals$ is a random order.
If at least one succeeds, then the $Cost$ 
and $Chances$ of {\em X}
is the sum and product (respectively)
of the $Cost$ and $Chances$ of
the satisfied members of {\em A,B,C}.
\ei
\begin{figure}[!b]
\renewcommand{\baselinestretch}{1}
{\small\begin{tabular}{|p{1.5in}p{1.5in}|}\hline
\begin{center}
{\em baselineAudits, baselineChangesControlled,
     changeRequestsHandled,
     changesCommunicated,
     configurationItemStatusRecorded,
     deviationsDocumented,
     documentedDevelopmentPlan,
     documentedProjectPlan,
     earlyPlanning,
     \underline{formalReviewsAtMilestones}, \underline{goodUnitTesting},
     identifiedWorkProducts,
     \underline{periodicSoftwareReviews}
     }\end{center} &  \begin{center}{\em
     planRevised, requirementsReview,
     \underline{requirementsUsed},
     reviewRequirementChanges,
     risksTracked,
     SCMplan,
     SCMplanUsed,
     SElifeCycleDefined,
     SEteamParticipatesInPlanning,
     SEteamParticipatesOnProposal,
     SQAauditsProducts,
     SQAplan,
    SQAplanUsed,
     SQAreviewActivities,
    workProductsIdentified} \end{center}\\\hline
     \end{tabular}}
\caption{Management actions in the CMM2 model.    SQA= software
quality     assurance and SCM= software configuration management)}\label{fig:actions}
     \end{figure}


\begin{figure*}
\renewcommand{\baselinestretch}{1}
\begin{minipage}{.75\linewidth}
{\small
\begin{center}
\begin{tabular}{cccc}
\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
  \setyaxis{0}{75}{10}
\sethspace{1} \setnumberpos{down} \bar{5}{1} \bar{16}{2}
\bar{5}{4} \bar{74}{8}
\end{barenv}

&

\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
  \setyaxis{0}{75}{10}
\sethspace{1} \setnumberpos{down} \bar{7}{1} \bar{13}{2}
\bar{19}{4} \bar{60}{8}
\end{barenv}

&

\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
  \setyaxis{0}{75}{10}
\sethspace{1} \setnumberpos{down} \bar{5}{1} \bar{14}{2}
\bar{26}{4} \bar{55}{8}
\end{barenv}
&

\begin{barenv}
\setstyle{\sffamily} \setwidth{8}
  \setyaxis{0}{75}{10}
\sethspace{1} \setnumberpos{down} \bar{14}{1} \bar{22}{2}
\bar{30}{4} \bar{24}{8}
\end{barenv}


\\~\\
$T_1$  &
$T_2$ & 
$T_3$ & 
baseline    
\\
  worth=1.44 &
  worth=1.31 &  worth=1.28
& current worth = 1
\end{tabular}
\end{center}
}\end{minipage}\hfill
\begin{minipage}{.25\linewidth}
\begin{raggedleft}
{\scriptsize

\begin{tabular}{|cp{1in}|}\hline
\multicolumn{2}{|p{1.5in}|}{~\newline\underline{{\bf KEY:}}
\newline Top-to-bottom = least

desirable to most desirable.\newline~\newline}\\
\protect\legend1{~}&\begin{raggedright}= high cost, low chances;
i.e. a very bad software \newline project\end{raggedright}
\\
\protect\legend2{~}&\begin{raggedright}= low cost, low
chances\end{raggedright}\\
\protect\legend4{~}&\begin{raggedright}= high cost, high
chances\end{raggedright}\\
\protect\legend8{~}&\begin{raggedright}= low cost, high chances;
i.e. a good software\newline project\end{raggedright}\\\hline
\end{tabular}}
\end{raggedleft}
\end{minipage}
\caption{ Ratios of different software project types seen in four
situations. }\label{fig:output}
\end{figure*}


$Rany$ is useful
when searching for subsets that contribute to some conclusion. For
example, the JANE rule in \fig{jane}
offers several essential features
of {\em
stableRequirements} plus several optional factors relating to
monitoring change in evolving projects -- the essential features are
$and$-ed together while the optional factors are $rany$-ed
together.

\fig{jane} includes 11 propositions.
Our model of CMM2, written in JANE, has 55 propositions 
($range=\{t,f\}$).
Of
those 55 propositions,
27 were identified by our users
as actions that
could be changed by managers  (see \fig{actions}). 


Apart from $rany$,
JANE  supports one other mechanisms for exploring the space of
possibilities within CMM2. 
When defining $Cost$s and $Chances$, the
programmer can supply a {\em range} and a {\em skew}. For example:

\begin{code}
goodUnitTesting and cost = 1 to +5
\end{code}
defines the {\em cost} of {\em goodUnitTesting} as being somewhere
in the range 1 to 5, with the mean skewed slightly towards 5
(denoted by the ``+''). 

Similarly, 
while all the $Chances$ values were based
on expert judgment, their precise value is subjective. Hence,
each such $Chances$ value $X$ was altered to be a range

\begin{code}
chances = 0.7*X to 1.3*X
\end{code}

During a simulation, the {\em first} time a $Cost$ or $Chance$
is accessed, it is assigned randomly according to the range
and skew. The assignment is cached so that all subsequent accesses
use the same randomly generated value. After each simulation, the
cache is cleared. After thousands of simulations, JANE can sample
the ``what-if'' behavior resulting from different
assignments within the range and many different $rany$ choices.

Data from 2000 simulations was passed from the CMM2 model
to TAR2.
Each simulation was classified into one of four classes:

\bi
\item
 {\em class=0}: High cost, low chance;
\item
{\em class=1}:  Low cost, low chance;
\item
{\em class=2}: High cost,  high chance;
\item
{\em class=3}: 
Low cost,  high chance.
\ei

That is, our preferred projects are cheap and highly likely while
expensive, low odds projects are to be avoided.


\fig{output} shows three sets of actions  learned by TAR2.
The right-hand-side histogram shows the baseline
distributions seen in the 2000 simulations.
The other histograms  show how those
ratios change after applying the  treatments learned by TAR2;
The {\em worth} of each option is a reflection of the
proportion of good and bad projects, compared to the baseline,
i.e.
($worth(baseline)=1$). Note that as {\em worth} increases, the
proportion of preferred projects also increases.



\fig{cmm} shows the three best treatments ($T_1, T_2,
T_3$)  found using this technique (and \fig{output} compared
the effects of these treatments to the untreated examples). Note
that the values of each attribute are reported using the tags {\em
no}, {\em lower}, {\em middle}, or {\em upper}. In treatment
learning, continuous attribute ranges are divided into N-discrete
bands based on percentile positions. For N=3, we can name the
bands {\em lower}, {\em middle}, {\em upper} for the lower,
middle, and upper  33\% percentile bands.

In \fig{cmm}, the treatments
are advising to lower the
cost of: \bi
\item {\em Using requirements:} This could be accomplished by (e.g.) 
sharing  them around the
development team in some search-able hypertext format
\item {\em Performing formal reviews at milestones:} This could be accomplished
by  (e.g.) using ultra-lightweight formal methods such as proposed
by Leveson~\cite{leveson91 }. \item {\em Performing good unit testing:}
This could be accomplished by (e.g.) hiring better test engineers.
\ei
\begin{figure}[!t]
\renewcommand{\baselinestretch}{1}
{\small
\begin{description}
\item[$T_1$:] {\em requirementsUsed.Cost=lower and\newline
                    not periodicSoftware-Reviews and\newline
                   formalReviewsAtMilestones.Cost=lower}
\item[$T_2$:]
                   {\em requirementsUsed.Cost=lower and\newline
                   goodUnitTesting.Cost=middle and\newline
                   formalReviewsAtMilestones.Cost=lower}
\item[$T_3$:]
                   {\em goodUnitTesting.Cost=lower and\newline
                   periodicSoftwareReviews.Cost=middle and\newline
                   formalReviewsAtMilestones.Cost=lower}
                   \end{description}
                   }
                   \caption{The three best treatments found in the CMM2
model.
}\label{fig:cmm}
                   \end{figure}

An interesting feature of \fig{cmm} is what is {\em missing}:
\bi
\item
None of the treatments proposed adjusting the
$Chances$ of any action. In this study, changing $Cost$ will
suffice.
\item
Of the 27 actions
listed in in \fig{actions}, only the four underlined actions
appear in the top three treatments. That is, management
commitment to undertake  27-4=23 of the actions is
less useful than changing  on
     $formalReviewsAtMilestones$, $goodUnitTesting$,
     $periodicSoftwareReviews$, and
     $requirementsUsed$
\item
   The value {\em not} in 
$T_1$
is a recommendation 
 against {\em periodicSoftwareReviews} (plus
lowering the costs of using requirements and formal reviews at
milestones). Note that if {\em periodicSoftwareReviews} are
conducted, $T_3$ is saying that there is no apparent need to
reduce the cost of such reviews.
\ei

More generally, in a result consistent with the prior studies,
despite the uncertainties introduced by $rany$
and the $cost/chances$ ranges,
TAR2 found
a small number of CMM2 process options that  
have a significant impact on the
project. 

Note that the conclusions of \fig{cmm} are not general to all
software projects. The $Chances$ values used in this study came
from some local domain knowledge about the likelihood that process
change $A$ will effect process change $B$.  
The $Cost$ values were domain-specific as well.
In other organizations,
with different work practices and staff, those $Chances$ and $Cost$
values could be
very different.

% study use
%XXX jim- some phrase about external validity. only good for the
%numbers we used in this study. blah blah blah

%\bibliographystyle{../one/IEEEtran}
%\bibliography{../one/refs,../one/miamiRefs,../jim/refs,../tim/refs,../jeremy/refs}
%\end{document}

\section{Case Study 2: Requirement Optimization} \label{sec:pilot}
This example illustrates the application of treatment learning on
requirement optimization via an iterative learning cycle.

Planning for the optimal attainment of requirements is an
important early life cycle activity. Such planning is difficult
when dealing with competing requirements, limited resources, and
the incompleteness of information available at requirements time.
The pilot study discussed here is an evaluation of a promising
piece of research-quality spacecraft technology. The purpose of
the evaluation is to identify the risks that would arise in
maturing this technology to flight readiness, and what mitigation
could be identified to address those risks in a cost-effective
manner.

\subsection{The Requirement Interaction Model}
For the pilot study, NASA experts built a real-world model
developed in the Defect Detection and Prevention (DDP) framework
~\cite{corn01}. The model is a network connecting 32 requirements,
69 risks and 99 mitigations. Risks are quantitatively related to
requirements, to indicate how much each risk, should it occur,
impacts each requirements. Mitigations are quantitatively related
to risks, to indicate how effectively each mitigation, should it
be applied, reduces each risk. A set of mitigations achieves
benefits, but incurs costs. The main purpose of the model is to
facilitate the judicious selection of a set of mitigations,
attaining requirements in a cost-effective manner. This kind of
requirements analysis seeks to maximize benefits (i.e., our
coverage of the requirements) while minimizing the costs of the
risk mitigation actions. Optimizing in this manner is complicated
by the interactions inside the model - a requirement may be
impacted by multiple risks, a risk may impact multiple
requirements, an action may mitigate multiple risks, and a risk
may be mitigated by multiple actions.

\subsection{The Iterative Learning Cycle}
\begin{figure}[!h]
\begin{center}
\includegraphics{cycle.pdf}
\end{center}
\caption{The iterative cycle of
Simulation/Summarization/Decision.} \label{fig:cycle}
\end{figure}

Our approach is to follow the iterative cycle of simulation,
summarization and decision shown in figure \ref{fig:cycle}. The
requirements interaction model is used to grow dataset
representing the space of options, treatment learner summarizes
the data and gives critical decision alternatives (e.g., the
control variables and their corresponding settings), the domain
experts review the alternatives and make final decisions. This
way, experts make more effective use of their skill and knowledge
by focusing their attention on the relatively small number of most
critical decision alternatives. Repeating this cycle leads the
iterative approach to the optimal (or near optimal) decision
within the options space.

\subsubsection{Baseline Simulation}
The model was initially executed by selecting risk mitigations at
random. This generated 30,000 instances of combinations from the
99 risk mitigations actions. Each instance of the combinations was
evaluated by the numerical cost and benefit values automatically
computed based on domain data. The study needs to identify the
optimal solutions that attain high benefit(approximately 250)
while remaining a relative low cost limit(around \$600,000). The
option space is huge: $2^{99} \thickapprox 10^{30}$ sets of
decisions are to be explored. Figure \ref{fig:jplraw} shows the
initial output of the cost-benefit distribution from the model.
The wide spread dots indicate a large variance in the possible
cost and benefit ranges.

\begin{figure}[!h]
\begin{center}
{\footnotesize
\includegraphics{jplb4.pdf}
}
\end{center}
\caption{Initial result from executing the model of pilot domain.
} \label{fig:jplraw}
\end{figure}

\subsubsection{Combining Cost and Benefit Values}
TAR2 takes dataset containing one single discrete class attribute.
We must combine the cost and benefit values into a single score
before applying TAR2 on the simulation data. This domain-specific
process was proceeded as follows:
\bi
\item Partitioning cost value into 4 regions: below \$600,000 (most desirable
region); \$600,000 to \$649,999; \$650,000 to \$699,999; at or
above \$700,000 (least desirable region).
\item  Partitioning benefit value by subdividing it into quartiles, i.e., putting the
lowest 25\% of the benefit figures into the lowest benefit range,
the next 25\% into the next, etc.
\item Ranking the 16 possible pairings of cost and benefit according to a balanced scheme
which yielded a combined score of ``goodness''. The scheme is
shown in table \ref{tbl:combine}.
\ei

\begin{table}
\renewcommand{\baselinestretch}{1}
{\footnotesize
\begin{center}
\begin{tabular}{|r|c|c|c|c|} \hline
 score & $< \$600K$ & $[\$600K,\$650K)$ & $[\$650K,\$700K)$ & $>\$700K$ \\\hline
 high 25\% & 16 & 14 & 11 & 7 \\\hline
 mid high 25\% & 15 & 12 & 8 & 4 \\\hline
 mid low 25\% & 13 & 9 & 5 & 2 \\\hline
 low 25\% & 10 & 6 & 3 & 1 \\\hline
\end{tabular}
\end{center}
\caption{Balanced score combination of cost and benefit
values}}\label{tbl:combine}
\end{table}

\subsubsection{Learning Iterations}
We used TAR2 as a knowledge acquisition tool to summarize the
simulation dataset. After ran it on the examples, a set of
treatments was discovered and the best was selected by the domain
experts. We then imposed the treatments on the model, i.e., some
mitigations were to be performed and some were not; others were
kept random. Simulating the constrained model again gave us
another example set. The whole process was repeated, each run of
TAR2 resulted in a new set of constraints, which were then imposed
on the model before the next simulation. After five iterations,
TAR2 found 30 out of 99 decisions (6 per run. 6 was the maximum
size for which it successfully terminated) that significantly
effected the cost/benefit distribution. Figure \ref{fig:jplafter}
shows the model output following the $5^{th}$ iteration. Compared
to figure \ref{fig:jplraw}, the variation among the cost-benefit
figures is relatively small. Since the model represents human
experts' estimates, the computed cost-benefit figures should not
be misinterpreted to have high precision. At the point where the
figures are so tightly clustered, it is appropriate to stop.

\begin{figure}[!h]
\begin{center}
{\footnotesize
\includegraphics{jplafter.pdf}}
\end{center}
\caption{Result from executing the model of pilot domain when it
was constrained by treatments after the $5^{th}$ iteration. }
\label{fig:jplafter}
\end{figure}
The entire series is shown in \ref{fig:jpleg}. The first
percentile matrix (called {\bf round 0}) summarizes figure
\ref{fig:jplraw}. The \textbf{round 4} corresponds to the dot
plotting in figure \ref{fig:jplafter}, in which a compact set of
points concentrated at the upper end of the benefit range (around
250), and at a cost of approximately \$6000. From {\bf round 0} to
{\bf round 4}, the variance was reduced and the mean values
improved.

\begin{figure}
\begin{center}
{\footnotesize {\bf round 0:}\setlength{\tabcolsep}{0pt}
\begin{tabular}{r@{~}|@{~}rrrr@{~}|@{~}r}\multicolumn{1}{c}{}&\multicolumn{4}{c}{Cost}\\\cline{2-5}
Benefit       &     400K    & 600K    & 800K    &  1,000K
&Totals\\\hline
 250          &             &   \sq{6}{94}     &  \sq{15}{85}     &   \sq{5}{95}    &   \sq{26}{74}    \\
 200          &   \sq{1}{99}      &  \sq{22}{78}       & \sq{27}{75}      &  \sq{4}{96}      &  \sq{54}{48}      \\
 150          &   \sq{1}{99}    &   \sq{6}{94}      &   \sq{5}{95}     &   \sq{1}{99}   &   \sq{13}{87}    \\
 100          &             &   \sq{3}{97}      &   \sq{3}{97}    &         &  \sq{6}{94}   \\
 50           &             &   1\%      &         &         &    \sq{1}{99}   \\\hline
 Totals       &   \sq{2}{98}      &  \sq{38}{62}    & \sq{50}{52}  &  \sq{10}{90} &  \sq{100}{2} \\\hline
\end{tabular}\vspace{0.25in}

{\bf round 1:}\setlength{\tabcolsep}{0pt}
\begin{tabular}{r@{~}|@{~}rrrr@{~}|@{~}r}\multicolumn{1}{c}{}&\multicolumn{4}{c}{Cost}\\\cline{2-5}
Benefit       &     400K    & 600K    & 800K    &  1,000K
&Totals\\\hline
 250          &       \sq{7}{93}      &  \sq{45}{44}    &  \sq{13}{87}      &         &    \sq{65}{35}    \\
 200          &      \sq{12}{88}      & \sq{22}{78}     &   \sq{1}{99}    &         &    \sq{35}{65}     \\
 150          &             &          &         &         &        \\
 100          &             &          &        &         &        \\
 50           &             &          &         &         &        \\\hline
 Totals       &      \sq{19}{81}      &  \sq{67}{33}       &  \sq{14}{86}   & \sq{~}{99} &   \sq{100}{1}    \\\hline
\end{tabular}\vspace{0.25in}


{\bf round 2:}\setlength{\tabcolsep}{0pt}
\begin{tabular}{r@{~}|@{~}rrrr@{~}|@{~}r}\multicolumn{1}{c}{}&\multicolumn{4}{c}{Cost}\\\cline{2-5}
Benefit       &     400K    & 600K    & 800K    &  1,000K
&Totals\\\hline
 250          &        \sq{9}{91}   &   \sq{8}{92}      & \sq{7}{93}     &         &  \sq{24}{76}      \\
 200          &     \sq{18}{82}      &  \sq{58}{41}    &       &         &      \sq{76}{23}   \\
 150          &             &          &         &         &        \\
 100          &             &          &        &         &        \\
 50           &             &          &         &         &        \\\hline
 Totals       &       \sq{27}{73}     &   \sq{66}{33}      & \sq{7}{93}    &  \sq{~}{99}  &     \sq{101}{1}  \\\hline
\end{tabular}\vspace{0.25in}


{\bf round 3:}\setlength{\tabcolsep}{0pt}
\begin{tabular}{r@{~}|@{~}rrrr@{~}|@{~}r}\multicolumn{1}{c}{}&\multicolumn{4}{c}{Cost}\\\cline{2-5}
Benefit       &     400K    & 600K    & 800K    &  1,000K
&Totals\\\hline
 250          &    \sq{9}{91}    &  \sq{70}{30}     &   \sq{11}{89}     &         & \sq{90}{10}      \\
 200          &    \sq{3}{97}      &    \sq{7}{93}      &       &         &  \sq{10}{90}       \\
 150          &             &          &         &         &        \\
 100          &             &          &        &         &        \\
 50           &             &          &         &         &        \\\hline
 Totals       &     \sq{12}{88}     &   \sq{77}{23}      & \sq{11}{89}    &  \sq{~}{99}  &   \sq{100}{1}   \\\hline
\end{tabular}\vspace{0.25in}


{\bf round
4:}\begin{tabular}{c|@{~}rrrr|@{~}r}\multicolumn{1}{c}{}&\multicolumn{4}{c}{Cost}\\\cline{2-5}
Benefit       &     400K    & 600K    & 800K    &  1,000K
&Totals\\\hline
 250          &      \sq{1}{99}       &  \sq{81}{18}     &  \sq{17}{83}      &         &  \sq{99}{1}      \\
 200          &             &   \sq{1}{99}      &       &         &       \sq{1}{99}  \\
 150          &             &          &         &         &        \\
 100          &             &          &        &         &        \\
 50           &             &          &         &         &        \\\hline
 Totals       &   \sq{1}{99} &  \sq{82}{17}     & \sq{17}{83}    &   \sq{~}{99} &     \sq{100}{1}  \\\hline
\end{tabular}
}\end{center} \caption{Percentile matrices showing four rounds of
treatment learning for the pilot study.} \label{fig:jpleg}
\end{figure}

\subsection{Compared to Simulated Annealing}

Parallel to treatment learning, a simulated annealing algorithm
(SA) was also applied to the same requirement analysis
task~\cite{fea02a}. Simulated Annealing is a commonly used search
algorithm for optimization problem. It combines random selection
and hill climbing to find global maxima. In particular, it does a
random walk, choosing neighbors at random and deciding at random
whether to visit that neighbor. The randomness is a function of a
``temperature'' variable. When $T = \infty$, it chooses neighbors
at random; in the limit as $T$ approaches zero, it chooses only
neighbors that improve the value. If the temperature is reduced
slowly enough, this guarantees to find the global optimal result.

\begin{figure}[!h]
\begin{center}
\includegraphics{costs.pdf}
\includegraphics{benefits.pdf}
\end{center}
\caption{Comparison of TAR2 and simulated
annealing.}\label{fig:comparsa}
\end{figure}

Figure \ref{fig:comparsa} compares TAR2 and simulated annealing.
At each round X (shown on the x-axis), simulated annealing or TAR2
was used to extract key decisions from a log of runs of the model.
A new log is generated, with the inputs constrained to the key
decisions found between round zero and round X. Further rounds of
learning continue until the observed changes on costs and benefits
stabilizes. The comparisons show that:
\bi
 \item As seen in \fig{comparsa}, simulated annealing and TAR2
terminate in (nearly) the same cost-benefit zone.
 \item Simulated annealing did so using only 40\% of the data needed by TAR2;
 \item However, while TAR2 proposed constraints on 33\%
of the mitigations, each SA solution specifies whether a
mitigation should be taken or not for all 99 mitigations. Hence
there was no apparent way to ascertain which of them are the most
critical decisions. This loses the main advantage of TAR2; i.e. no
drastic reduction in the space of options.
\ei
%In summary, simulated annealing needs less data than TAR2, but in
%doing so,



\section{TAR3}

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


\subsection{An Introduction to TAR3}

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

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

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

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

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




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

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

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



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


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

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


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


\subsection{TAR3 is Competent}

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

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


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

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

\subsection{TAR3 is Simple}

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

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

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

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

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


\subsection{TAR3 is Fast and Scalable}

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

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


\subsection{TAR3 is Stable}

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

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

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

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


\subsection{TAR3 and Checking for Unsafe Nondeterminism}

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

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


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

\section{Case Study: The Pilot Domain Again}
The above studies dealt with small to medium sized datasets. This
section describes an experiment with a very large dataset in which
TAR3's treatments, while similar, were not identical.

We have discussed the ``pilot'' case in requirement optimization
domain (see chapter 3). To compare both the performance and
experimental results, we ran TAR2 and TAR3 on the same ``pilot''
domain again. The model used this time is a revised version of the
original one, which contains fewer details. The data set obtained
after simulation has 58 attributes instead of 99. Each example is
also evaluated by a pair of cost and benefit figures. According to
the domain experts, we combined cost and benefit into a single
attribute using the same balanced scheme but with different
dividing thresholds. The combination resulted in 16 classes
representing 16 levels of ``goodness''.

Figure \ref{fig:cbraw} shows the initial cost-benefit distribution
from the baseline simulation. The data points are widely spread
across the possible cost and benefit ranges. Further, most low
cost points correspond to low benefit level and high benefit
points have high cost values. The desired low-cost high-benefit
points are very few: less than 3\% of the entire data.

\begin{figure}[!h]
\begin{center}
{\footnotesize
\includegraphics[width=4in]{cbraw.pdf}
\caption{The cost-benefit distribution of the initial simulation
from the pilot domain. }} \label{fig:cbraw}
\end{center}
\end{figure}
We followed the same incremental learning approach as discussed in
the last chapter, namely the following steps:
\be
 \item Ran TAR2 and TAR3 on the baseline (initial simulation) data, and generated
 two set of treatments.
 \item The top ranked treatment was chosen from each treatment
 set. For the purpose of comparison, we didn't ask domain
 experts to examine the individual treatments, we simply chose the
 top one.
 \item We then imposed the 2 chosen treatments (1 from TAR2, 1 from TAR3)
 on the model respectively; simulated it again and got another 2 sets of data
 examples.
 \item Step 1-3 were repeated until the resulting distribution was
 so tightly clustered that domain experts agreed to stop.
\ee

\subsection{Comparison of the Cost-Benefit Distribution}
\begin{figure}[!h]
\begin{center}
{\footnotesize
\includegraphics[width=3.3in]{cbfinaltar2.pdf}
}
\end{center}
\caption{The cost-benefit distribution from executing the model of
pilot domain when it was constrained after the $5^{th}$ iteration
of TAR2.} \label{fig:cbfinaltar2}
\end{figure}
\begin{figure}[!h]
\begin{center}
{\footnotesize
\includegraphics[width=3.3in]{cbfinaltar3.pdf}
}
\end{center}
\caption{The cost-benefit distribution from executing the model of
pilot domain when it was constrained after the $4^{th}$ iteration
of TAR3.} \label{fig:cbfinaltar3}
\end{figure}


Figure \ref{fig:cbfinaltar2} shows cost-benefit distribution after
the $5^{th}$ iteration of TAR2. Compared to figure
\ref{fig:cbraw}, the variation is relatively small. Most of the
data points are grouped at the upper-left corner of the graph,
indicating a tight cluster of low-cost high-benefit results.
Figure \ref{fig:cbfinaltar3} is the result from TAR3 experiments
following the $4^{th}$ iteration. The two graphs are visually the
same, indicating very similar results.

\subsection{Comparison of the Best 3 Class Distribution}
For a closer comparison, table \ref{table:compareClass} records
the best 3 class distribution of each round. The best 3 out of
total 16 classes correspond to a region of desired zone in which
domain experts interested. TAR2 reaches the stopping point after 5
rounds, fixing total 19 attributes; TAR3 reaches the stopping
point after 4 rounds, fixing total 20 attributes. At the stopping
point, both TAR2 and TAR3 achieved a similar class distribution.
Further learning didn't offer significant improvement (i.e.,
further distribution improvement is less than 5\% ).

\begin{table}[!h]
\renewcommand{\baselinestretch}{1}
{\small
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|}
 \hline
 TAR2 &baseline   &run1    &run2   &run3   &run4   &run5 \\\hline
 size(Rx)& 0       &4       &4      &4      &4      &3 \\\hline
 Class14& 3\%     & 33\%   &68\%   &22\%   & 7\%   & 2\%  \\
 Class15& 0\%     & 1\%    & 7\%   &38\%   &19\%   & 5\%  \\
 Class16& 0\%     & 0\%    & 4\%   &28\%   &74\%   &93\% \\\hline
 Total  & \textbf{3\%}     &\textbf{34\%}    &\textbf{79\%}   &\textbf{88\%}   &\textbf{100\%}  &\textbf{100\%}  \\\hline\hline
 TAR3 &baseline   &run1    &run2   &run3   &run4   &run5\\\hline
 size(T)& 0       &6       &6      &5      &4      &----- \\\hline
 Class14& 3\%     &47\%    &50\%   &11\%   & 0\%   &----- \\
 Class15& 0\%     & 2\%    &19\%   &27\%   & 7\%   &----- \\
 Class16& 0\%     & 1\%    &13\%   &60\%   &93\%   &----- \\\hline
 Total  & \textbf{3\%}     &\textbf{50\%}    &\textbf{82\%}   &\textbf{98\%}   &\textbf{100\%}  &----- \\\hline
\end{tabular}
\end{center}}
\caption{Comparison of the best 3 class distributions for TAR2 and
TAR3 experiments.}\label{table:compareClass}
\end{table}

\subsection{Comparison of Each Round}

\begin{figure}[!h]
\begin{center}
{\footnotesize
\includegraphics[width=4in]{barCost.pdf}
}
\end{center}
\caption{The mean and standard deviation of cost at each round.}
\label{fig:barCost}
\end{figure}

\begin{figure}[!h]
\begin{center}
{\footnotesize
\includegraphics[width=4in]{barBenefit.pdf}
}
\end{center}
\caption{The mean and standard deviation of benefit at each
round.} \label{fig:barBenefit}
\end{figure}

At the beginning of this experiment, TAR2 and TAR3 started from
the same point (i.e. the first baseline data) and came up with
different treatments. They later followed their own path toward
the final destination. Figure \ref{fig:barCost} compares their
performance on each round in terms of the mean and standard
deviation of the cost figure. Each round, TAR3 achieved lower mean
cost and smaller deviation, allowing it to reach the stopping
point one iteration earlier. Figure \ref{fig:barBenefit} compares
the benefit figure. Again, TAR3's deviation is smaller at each
round. It is interesting to notice the dip in the TAR2 curve,
which indicates a slowing down of the progress. But it eventually
catches up in round 4 and round 5.

\subsection{Comparison of the Final Treatments}
\begin{table}[!h]
\renewcommand{\baselinestretch}{1}
{\small
\begin{center}
\begin{tabular}{|c|l|c|c||c|l|c|c|}
 \hline
 No. &Attribute   &TAR2    &TAR3  &No. &Attribute   &TAR2  &TAR3  \\\hline
    1   &[P63=N]  &\checkmark &\checkmark  &12  &[P1310=Y] &\checkmark &\checkmark\\\hline
    2   &[P70=N]  &\checkmark &\checkmark  &13  &[P529=N]  &\checkmark &\checkmark \\\hline
    3   &[P72=N]  &\checkmark &\checkmark  &14  &[P544=N]  &\checkmark &\checkmark \\\hline
    4   &[P73=Y]  &\checkmark &\checkmark  &15  &[P551=N]  &\checkmark &\checkmark \\\hline
    5   &[P74=N]  &\checkmark &\checkmark  &16  &[P555=Y]  &\checkmark &\checkmark \\\hline
    6   &[P126=Y]  &\checkmark &\checkmark &17  &[P575=N]  &\checkmark &           \\\hline
    7   &[P135=N]  &\checkmark &\checkmark &18  &[P960=N]  &           &\checkmark \\\hline
    8   &[P137=N]  &\checkmark &\checkmark &19  &[P1047=N]  &\checkmark &\checkmark \\\hline
    9   &[P145=Y]  &           &\checkmark &20  &[P1260=Y]  &\checkmark &\checkmark \\\hline
    10  &[P154=Y]  &\checkmark &\checkmark &21  &[P1287=N]  &\checkmark &\checkmark \\\hline
    11  &[P166=N]  &\checkmark &\checkmark &Total  &           &19         &20      \\\hline
\end{tabular}
\caption{Comparison of the final treatments found by TAR2 and
TAR3, respectively.}\label{table:compareTreatment}
\end{center}}
\end{table}

TAR2 gave a final treatment of size 19 after 5 iterations, TAR3's
final treatment is of size 20 after 4 iterations. Although in each
run, they generated quite different treatments, the combined final
treatments are almost the same. Table \ref{table:compareTreatment}
compares the two final sets attribute by attribute, showing that
they have 18 items in common.


\subsection{Comparison of Runtimes}

The data size we used is $20,000$ examples $\times$ $58$
attributes at each round. Table \ref{table:compareRuntime}
compares their runtimes. For reference reasons, column 3 and 5
list the size of best treatment found at that round. The average
runtimes of TAR3 is only $\frac{1}{5}$ to $\frac{1}{3}$ TAR2's
runtime. That is, TAR3 ran much faster even with larger treatment
size.

\begin{table}[!h]
\renewcommand{\baselinestretch}{1}
{\footnotesize
\begin{center}
\begin{tabular}{|c|r|c||r|c|c|}
 \hline
 Round &TAR2(sec)   &size(T)    &TAR3(sec)  &size(T) &TAR3/TAR2 \\\hline
    1   &1243 &4   &320   &6    &$25.8\%$   \\\hline
    2   &1170 &4   &348   &6    &$29.7\%$\\\hline
    3   &927  &4   &235   &5    &$25.3\%$\\\hline
    4   &650  &4   &126   &4    &$19.4\%$\\\hline
    5   &103  &3   &---   &---  &---  \\\hline
\end{tabular}
\caption{Comparison of the runtimes of each
round.}\label{table:compareRuntime}
\end{center}}
\end{table}

\subsection{Summary}
From the above case study, we have the following observations:
\bi
\item In this domain, TAR3 achieved a better class distribution than TAR2
each run, and generated a slightly larger treatment.
\item Their own path ended up with a similar yet not identical
solution, both in terms of the cost-benefit distribution and the
treatment produced.
\item TAR2 reached the same final distribution after more
runs, but with total less attributes fixed (i.e., the size of the
final treatment is smaller in TAR2's case).
\item In this domain, TAR3's runtime is much shorter than TAR2, average
$\frac{1}{5}$ to $\frac{1}{3}$ TAR2's runtime.
\ei

\section{Conclusion}
The algorithmic evaluation on TAR2 pointed out situations where
its runtimes can grow exponentially. Our solution to this problem
is a better learner TAR3. By adopting random sampling together
with other strategies, TAR3 has made major improvement in
algorithmic efficiency. Experiments have shown that on the
datasets where TAR2 is exponential, TAR3 runs in linear time. We
have also conducted extensive comparison to survey the stability
of TAR3's treatments. It has been seen that TAR3 usually returns
identical treatments as TAR2 on small to medium datasets. On high
dimensional dataset, TAR3 followed a faster path to goal. The
resulting distribution is better, while the final treatment is
slightly different.

Specifically, the key idea to treatment learning is the
$confidence1$ evaluation of individual attributes. A different
search strategy should not change results but only affect
efficiency. The sampling method brings in a certain degree of
randomness. Still, we have shown that the controlling method we
implemented is effective in practice. Given that $confidence1$
distribution represents the probability an item could be picked up
in the treatment, there could be other ways to control the random
process: For example, some functions could added to the
distribution when computing the CDF value.
\subsection{Discussion}
The iterative treatment learning on the pilot study has
successfully arrived at a near-optimal attainment of requirements.
By identifying only one-third of the mitigations (30 out of 99),
we are able to significantly narrow the widely spread cost/benefit
distribution.

This case study also demonstrated an incremental use of TAR2: At
each iteration, users are presented with list of treatments that
have most impact on a system. They select some of theses and the
results are added to a growing set of constraints for a model
simulator. This approach has two advantages: Firstly, it narrows
down the solutions one step at a time, giving a clear statement on
which attributes are \emph{most} important; Secondly, the domain
experts found this approach user-friendly, since it provided the
opportunities for them to inject their knowledge into the process,
and allowed them to focus on only a small number of the most
critical alternatives.

\subsection{Other Case Studies}

Treatment learning has been applied to
spacecraft design to find
how to  cover more requirements,  reduce risk, at the least cost~\cite{fea02a,me03i}.
It has also been applied to  software process control using:
\bi
\item A Chung-Mypolopous soft-goal graph to find better
coverage of the  non-functional requirements~\cite{me03j}.
\item COCOMO effort and risk models models to find
options selecting for lower effort and fewer risks~\cite{me00e};
\item COCOMO effort, risk, and defect prediction models
models to find project options selecting for
lower effort and fewer threats and lower defects~\cite{me05e};
\item Qualitative inference diagrams to find requirements
selecting for higher quality~\cite{me06a}.
\item The NASA SILAP model (that selects V\&V tasks
in order to most lower risks)~\cite{me06b};
\ei
Treatment learning
has also been applied to: \bi
\item Finite state machines to find topologies
that reduce the CPU cost of applying formal methods~\cite{me02h,owen02a}.
\item Models of the global economy so study methods of extending human life
expectancy~\cite{gel03a};
\item Maximizing whiskey production~\cite{burk04};
\ei


%\input{../tim/related}

\noindent
In all the  case studies explored by TAR2,
the same three observations were made:
\bi
\item Treatment learning can find very small treatments,
even for seemingly complex models;
\item
These
treatments can be far smaller that models generated by standard data miners.
\item 
Despite uncertainties or variabilities in the model, TAR2 was able
to find effective treatments that selected for preferred model output
(but the less uncertainty or model variability, the smaller the variance
in TAR2's predicted output for the treated model).
\ei

%\section{Related Work}
%
%Elsewhere~\cite{me03l} we have discussed the connection of treatment learning to
%soft computing methods such as fuzzy logic, genetic algorithms, and
%neural nets. 
%Approximate,
%heuristically generated models would be adequate to control
%models if those models contain clumps and collars.
%That is,
%the widespread presence of clumps and collars
%would explain the success of soft computing. 
%
%Treatment learner offers coarse-grained heuristic
%controllers for models with a wide range of internal parameter settings.
%{\em Automatic formal methods},
%on the other hand, rigorously explore the structure of
%small models
%that are precisely specified (albeit with some non-determinism).
%Hence they are tools to be used for {\em different tasks} in the
%life cycle of a model.
%
%Early in the software life cycle, engineers are concerned with
%exploring a large space of possible models or possible model
%configurations. Model-based tools needed for such {\em option assessment}
%(e.g. TAR2) may be very different from model-based tools for {\em
%fine-tuning} and verifying a final model such as SPIN~\cite{spinbook}.
%Certainly, for mission and safety critical models, it is essential
%that such rare but dangerous bugs be located and fixed. However,
%while much of the model remains under debate, the rigorous
%search of, say, SPIN
%can be rendered obsolete by the next revision to the model.
%
\section{Conclusion}\label{conclusions}

Understanding model configuration options means understanding how
input choices affect output scores. That understanding is complex
for a certain class of {\em hard models}; i.e. those with high
dimensionality models that are non-linear, non-continuous and built
in domains with much noise or other uncertainties, and where managers
have limited control over all model inputs.  

Hard modeling problems may defeat standard methods.
Visualization can't handle very large dimensionality.  Analytical
methods such as an eigenvector study offer spurious results if the
parameters of the variables are uncertain. Other standard automatic
methods may be defeated by ``cliffs'' in non-linear models where the
association between inputs and outputs changes abruptly.
Data mining methods can handle non-linear models and scale to very large
dimensionality. Sadly, data mining techniques like neural nets, genetic algorithms,
C4.5 and CART  can yield models that are incomprehensible to humans.

TAR2 is a special kind of data miner that produces very succinct
output. It assumes that
within models there exists a small number of key variables that control 
the rest.
There is much evidence for this assumption.
The mathematics of clumps and collars promises that
models
naturally contain structures that
greatly restrict the space
of possible model behaviors. 
TAR2 is a data miner
designed to exploit such collars and clumps.
%\begin{wrapfigure}{r}{1.5in}
%\begin{center}
%\includegraphics[width=1.5in]{ai.pdf}
%\end{center}
%\caption{Humans assisted by AI.}\label{fig:cycle}
%\end{wrapfigure}
It is a minimal contrast set learner that returns a ``treatment'';
i.e. a minimal, most influential
set of deltas between different classes of outcome.
The case studies in this paper show that
a minimal list of the differences between concepts can
be {\em much smaller} than a detailed description of all aspects of a concept.
For models where TAR2 can generate  succinct summaries,
its algorithm can significantly improved searched-based methods of data mining.
%Human designers could avoid wasting time on superfluous details in that
%models could be iteratively built by humans, 
%then pruned by minimal contrast set learning. 
%In this way, 
%human-based design intelligence could be augmented in a cost-effective manner via
%artificial intelligence.
%

TAR2 addresses the hard modeling problems (discussed in \tion{easyhard}) 
as follows:

\bi
\item
TAR2 offers minimal constraints on the input space  and tracks the effects
of those constraints, while letting all the other variables vary randomly.
Hence, its proposed solutions are not brittle to changes outside the treatments. 
\item
Since it only references a subset of the model inputs, it is a dimensionality
reduction tool. In this report,
we offered examples where TAR2 reasoned over
100-variable inputs spaces. Elsewhere, we have run it on data sets with over 250 variables. In all cases seen to date, it reduces those spaces to a handful of variables.
\item
Such small solutions are easier to explain and audit than solutions using
all model inputs. 
\item
Further, when managers do not have the budget or authority to control all model
input variables,
TAR2 can offer them 
a minimal set which they can use to focus their resources.
\item
TAR2 has been applied to models with large amounts of noise. For example,
in a TAR2-style
analysis, we often 
explore what happens to the solutions when the variance
on the model variables increases.  Such studies return statements of the form
``the solutions offered by this analysis hold for variances up to the following
critical threshold values, after which we do not know how to control this domain''.
\ei

Treatment learning is not indicated
for low-dimensionality
linear continuous models built in domains that have no noise or other
uncertainties, and where managers have full control over all model inputs.
Other reasons not to use our tools include when where there is no
need to explain or audit models, where reducing model variance is
not valuable, and there exists budgets for building and using
maximal models.

As to further work,
there is no reason to polarize the SE modeling field into ``traditional methods''
vs ``treatment learning''. Much could be achieved by combining the two techniques.
For example, many of the methods described in \tion{easyhard} suffered
from the curse of dimensionality. 
TAR2 could be used as a fast dimensionality reduction tool
that could focus a data visualization environment or a sensitivity
analysis on the parts of the inputs space that are most crucial.
Ideally, that focusing need not wait till the simulation terminates.
In {\em incremental treatment learning},
TAR2 offers feedback during a simulation run into order the guide
the simulator into regions of interest. Before TAR2 can be deployed
in that manner, it must be optimized so that it can run fast enough
to keep up with the simulator. Currently, we are exploring stochastic
methods for that optimization.

\bibliographystyle{acmtrans} 

\bibliography{refs,miamiRefs,../jim/refs,../tim/refs,../jeremy/refs}


\begin{received}
June 30, 2007
\end{received}
\end{document}


