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

\PARstart{I}n 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| ***
%

\input{../tim/lsrcart}

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.
%
%
\input{../tim/cmmMain}
\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


