% THIS IS SIGPROC-SP.TEX - VERSION 3.1
% WORKS WITH V3.2SP OF ACM_PROC_ARTICLE-SP.CLS
% APRIL 2009
%
% It is an example file showing how to use the 'acm_proc_article-sp.cls' V3.2SP
% LaTeX2e document class file for Conference Proceedings submissions.
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V3.2SP) *DOES NOT* produce:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) Page numbering
% ---------------------------------------------------------------------------------------------------------------
% It is an example which *does* use the .bib file (from which the .bbl file
% is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission,
% you need to 'insert'  your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% Questions regarding SIGS should be sent to
% Adrienne Griscti ---> griscti@acm.org
%
% Questions/suggestions regarding the guidelines, .tex and .cls files, etc. to
% Gerald Murray ---> murray@hq.acm.org
%
% For tracking purposes - this is V3.1SP - APRIL 2009

\documentclass[10pt,compsocconf,conference]{IEEEtran}
\usepackage{bibspacing}
\usepackage{alltt,url,cite}
\usepackage{algpseudocode}
\usepackage{algorithm}

% Different font in captions
%\newcommand{\captionfonts}{\sffamily\footnotesize}

%\makeatletter  % Allow the use of @ in command names
%\long\def\@makecaption#1#2{%
%  \vskip\abovecaptionskip
%  \sbox\@tempboxa{{\captionfonts #1: #2}}%
%  \ifdim \wd\@tempboxa >\hsize
%    {\captionfonts #1: #2\par}
%  \else
%    \hbox to\hsize{\hfil\box\@tempboxa\hfil}%
%  \fi
%  \vskip\belowcaptionskip}
%\makeatother   % Cancel the effect of \makeatletter
%

\newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
\newcommand{\bi}{\begin{smallitem}}
\newcommand{\ei}{\end{smallitem}}
\newcommand{\be}{\begin{smallenum}}
\newcommand{\ee}{\end{smallenum}}
\newcommand{\tion}[1]{\S\ref{tion:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newenvironment{smallitem}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{itemize}
   \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{itemize}}
\newenvironment{smallenum}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{enumerate}
  \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{enumerate}}

\ifCLASSINFOpdf
   \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
   \graphicspath{{../pdf/}{../jpeg/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
   \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
  % \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.eps}
\fi

\newfloat{program}{thp}{lop}
\floatname{program}{Program}


\begin{document}
\title{From Effort Estimation to Effort Reduction}
%
% You need the command \numberofauthors to handle the 'placement
% and alignment' of the authors beneath the title.
%
% For aesthetic reasons, we recommend 'three authors at a time'
% i.e. three 'name/affiliation blocks' be placed beneath the title.
%
% NOTE: You are NOT restricted in how many 'rows' of
% "name/affiliations" may appear. We just ask that you restrict
% the number of 'columns' to three.
%
% Because of the available 'opening page real-estate'
% we ask you to refrain from putting more than si% More than six makes the first-page appear very cluttered indeed.
%
% Use the \alignauthor commands to handle the names
% and affiliations for an 'aesthetic maximum' of six authors.
% Add names, affiliations, addresses for
% the seventh etc. author(s) as the argument for the
% \additionalauthors command.
% These 'additional authors' will be output/set for you
% without further effort on your part as the last section in
% the body of your article BEFORE References or any Appendices.

%\numberofauthors{1} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%
\author{
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
%
% 1st. author
\IEEEauthorblockN{Adam Brady$^1$, Tim Menzies$^1$, Jacky Keung$^2$}
\IEEEauthorblockA{
$^1$Lane Department of CS\&EE, West Virginia University, USA,\\
$^2$NICTA, Australia,\\
\url{adam.m.brady@gmail.com, tim@menzies.us, Jacky.Keung@nicta.com.au}}}
% There's nothing stopping you putting the seventh, eighth, etc.
% author on the opening page (as the 'third row') but we ask,
% for aesthetic reasons that you place these 'additional authors'
% in the \additional authors block, viz.
%\date{30 July 1999}
% Just remember to make sure that the TOTAL number of authors
% is the number that will appear on the first page PLUS the
% number that will appear in the \additionalauthors section.

\maketitle
\begin{abstract}

A major hurdle still faced by data mining practitioners involves translating complex theories into actionable
items for managers. As theories and methodology becomes more complex, business users must place more faith in
the theory assumptions rather than their own intuition. To combat this we present an extremely simple effort
reduction recommendation  system called ``W'' that maintains no underlying parametric model and produces simple,
concise theories complete with explanations. ``W'' does this by extending the effort estimation of case-based
reasoning with the explanation power of contrast sets. From these contrast sets we build new queries that constrain
the original effort estimates, demonstrating a reduction in both the median effort and variance
of historically-relevant projects. 

\end{abstract}


\begin{IEEEkeywords}
software economics; artificial intelligence; case-based reasoning; CBR by analogy; explanation; effort reduction; human-in-the-loop learning
\end{IEEEkeywords}

\IEEEpeerreviewmaketitle


\section{Introduction}

\begin{quote}
"Don't tell me where I am, tell me where to go."
-A very busy user
\end{quote}

A machine learner's purpose in life is to generate theories. However, all theories must eventually be read by humans.
Therefore, we should consider what kinds of theories people like to read.

If the reader is a busy person they might not need or even be able to use the nuance of a complex theory. Rather, a busy person might instead just want to know what will bring the most benefit from the least effort and nothing more. It follows that machine learning for busy people should not strive for elaborate theories or increasing the expressive power of the theory's language. Rather, a better goal might be to find the smallest theory with the most impact.

Previous work explored minimal controllers in the context of AI search over monte-carlo analysis of software process models using STAR~\cite{me09f}. A concern with that line of research is that the more elaborate our tech, the harder it is to validate the conclusion. In particular, reproducability is hard when it takes 2-6 months to rebuild experimental rig discussed in the previo us paper. Is there a simpler way to generate simple most-effective controllers for a software project? Another problem was the conclusions were dependent on the parametric model used. For example, our previous work was based on the USC COCOMO tools. The tools were built from mostly southern-caifornia DoD aerospace contractors and it is a valid criticism of those models that the external validity of those models is an open question.

Therefore, in order to simplify the reproducibility of our work and remove our dependency of possibly inappropriate models, this paper reports an experiment in learning controllers using case-based reasoning. We report a remarkably simple CBR algorithm dubbed ``W'' that achieves all our goals. ``W'' generates recommendations that reduce both the median effort and the variance on the effort. The recommendations are very small in the case-studies shown here, they're usually one change to a project with widely varying recommendations between projects.

\section{Background}

\subsection{Modeling vs. Case-Based Reasoning by Analogy}

Much work has been put forth in developing parametric models for estimation software effort. Popular models such as USC COCOMO~\cite{boehm81} take the reductionist approach of reducing any arbitrary software project to a handful of descriptive parameters. Each parameter consists of a range of values from 1 to 6 representing ranges from very low to extremely high, respectively, mapped to regression values expressing how each attribute affects effort. The result of which can be used to model software effort using this formula:
\begin{equation}\label{cocoeffort}
effort = a * KSLOC^{b+0.01*\sum_{i=1}^5SF_i}*(\prod_{j=1}^{17}EM_j)
\end{equation}
\subsection{The Case for CBR}

Where $KSLOC$ represents thousands of lines of code, $SF$ represents exponential scale factor attributes, and $EM$ represents linear effort multipliers. While these parameters were derived from historical NASA projects and have shown their utility, an effort estimator must rely that these parameters are reflective of any given arbitrary project. As time progresses, one can speculate that the relevance of the underlying model will remain applicable to future cases. Also, such models often require careful domain-specific tuning, as is the case of the $a$ and $b$ linear and exponential tuning values in ~\ref{cocoeffort}. For the original NASA dataset~\cite{me07f}, these values can range anywhere from:

\begin{equation}\label{nasatunings}
(2.2 \le a \le 9.18) \wedge (0.88 \le b \le 1.09)
\end{equation}

Because these tunings are arbitrary, one can see how merely the tuning parameter $a$ can quadruple the effort estimation depending on its value. Given this uncertainty and reliance on establishing a general case for all software projects, another method, case-based reasoning, establishes an alternative methodology for effort estimation.

The general form of case-based reasoning differs from parametric model-based learning in that there is no attempt to reduce complex phenomena to a general-case parametric model. Rather, historical data is \emph{Retrieved, Reused, Revised, and Retained}~\cite{06mantaras} (the "4 REs") as a means of adapting the past to reason about the future.

The intuition of CBR comes from cognitive models of human behavior. That is, as humans we tend to base our decisions not on complex reductive analysis, but on an instantaneous survey of past experiences. In other words, we don't think, we remember. For example one not need consider the actuarial ramifications of a kitchen grease fire, our past experiences tells us without hesitance: Fire hot, fire bad. While the power of simulating and modeling the world has allowed for our success as a species, our abilities fall apart without historical knowledge of the world.

However, for this paper we are more interested in a subset of the CBR domain, effort estimation by analogy.

Analogy effort estimation centers around historical project data frozen in time, referred to as $cases$, to reason about new project instances. The core assumption being that given some measurement of relevancy between cases and incoming project instances, we can generate a query $q$ over the historical space that selects for the kth nearest neighbors , or \emph{knn}, most relevant to a project instance. Because the cases are analogous to the project instance being considered, CBR methodology states we can reason about the project instance by examining the analogous cases.

It is important to note, unlike established models CBR does carry the requirement of obtaining relevant and accurate historial data that represents the problem space. While this can limit the deployable situations for CBR, when this data \emph{is} available CBR offers an intrinsic justification of it's estimations that are less obvious with a parametric approach. One need only examine the analogous cases for evidence supporting a particular estimation.

Finally, an added benefit of reasoning from historical data grants CBR distinct advantages over parametric models as the learner is only exposed to conditions that happen in practice, rather than reason about all possible theoretical possibilities. This is useful when presented with data containing outlier behavior that might not map to a linear regression as easily. As long as the data collection requirements are met, CBR can be applied to any consistent and representative means of describing a software project.

For these reasons outlined above we include CBR by analogy as the foundation of our learning controller, ``W,'' as a starting point in generating useful, actionable, simple theories.

%\subsection{A Brief History of CBR Effort Estimation}

%Rather than derive regression models, a fundamental challenge in CBR is a reliable and accurate method of measuring ~\cite{shepperd97} relevant cases.
%Analogy-X
%McSherry

\subsection{From Estimation to Planning}

Upon a thorough review of CBR literature, there exists little work beyond estimation. Famous CBR systems such as Shepperd's ANGEL ~\cite{shepperd97} and more recent work such as Keung's Analogy-X ~\cite{08keung} focus their efforts on quantifying what is relevant in effort estimation, but remain limited in the scope of simply estimating. While means of deciding what cases are relevant is a fundamental problem of CBR, it is worth persuing other possible applications of this unique methodology. For instance, no where does there exist any planning in CBR literature.

Our focus of this paper and ``W'' is not to explore the effort estimation power of learning by analogy. Rather, we seek to broaden the scope of CBR to include generating theories for effort reduction. To do this, we must devise a way to exploit the knowledge gained from the attributes of the relevant neighborhood of projects, rather than merely their historical effort.

Conceptually, if we query the historical space for a set of relevant cases, we should recommend project changes that cause our project instance to be more similar to historical cases with the most favorable outcome. In the case of effort reduction, a good recommendation would drive our project away from attributes associated with worse effort outcomes and towards projects with better effort outcomes. When tested against unseen cases, a project with the previously recommended attribute constraints should demonstrate a reduction in both the effort and variance seen in its neighbors. From these test cases we can build successive queries, $q^*_i$, that incrementally apply these attribute constraints until we can no longer accurately predict a reduction on effort:

\begin{equation}\label{}
query_i^* = query + \cup_ic_i
\end{equation}

Each attribute constraint $c_i$ can then be added to the query $q_i$ in descending order of recommendation score.

\section{Deciding with ``W''}

``W'' is our implementation of a effort reduction planning system using the fundamentals of CBR. ``W'' consists of three main steps:

\begin{itemize}
\item Defining a Project Instance
\item Deciding what attributes are relevant to improving the project
\item Evaluating the effectiveness of improvements on test cases
\end{itemize}

``W'' decides based on two core assumptions: Similar projects have similar efforts, and the the attributes that drive effort reduction will occur more frequently in the best cases than the worst.

\begin{figure}[h]
\begin{center}
\begin{scriptsize}
\begin{tabular}{|p{.46\linewidth}|p{.46\linewidth}|}
\multicolumn{1}{l}{``W'' Project File Example}\\\hline
@project\newline 
@attribute ?rely 3 4 5\newline 
@attribute tool  2\newline 
@attribute cplx 4 5 6\newline 
@attribute ?time 4 5 6
\\\hline
\end{tabular}
\end{scriptsize}
\end{center}
\caption{Example project file for ``W''}
\label{fig:nasaproj}
\end{figure}

\begin{figure}[h]
\begin{center}
\begin{scriptsize}
\begin{tabular}{|p{.46\linewidth}|p{.46\linewidth}|}
\multicolumn{1}{l}{``W'' Historical Cases}\\\hline
@relation NASA93\newline 
@attribute rely 1 2 3 4 5\newline 
@attribute data 2 3 4 5\newline 
@attribute cplx 1 2 3 4 5 6\newline 
@attribute time 3 4 5 6 \newline 
@attribute stor 3 4 5 6\newline 
@attribute virt 2 3 4 5\newline 
@attribute turn 2 3 4 5\newline 
@attribute acap 1 2 3 4 5 \newline 
@attribute aexp 1 2 3 4 5\newline 
@attribute pcap 1 2 3 4 5\newline 
@attribute vexp 1 2 3 4\newline 
@attribute lexp 1 2 3 4\newline 
@attribute modp 1 2 3 4 5\newline 
@attribute tool 1 2 3 4 5\newline 
@attribute sced 1 2 3 4 5\newline
@attribute ksloc 8.4 10.8 24 25.2 31.2 36 72 117.6 360\newline
@data\newline 
4 2 4 3 3 2 2 3 3 3 3 4 4 3 2 24.6 117.6\newline 
4 2 4 3 3 2 2 3 3 3 3 4 4 3 2 7.7 31.2\newline 
4 2 4 3 3 2 2 3 3 3 3 4 4 3 2 8.2 36\newline 
4 2 4 3 3 2 2 3 3 3 3 4 4 3 2 9.7 25.2\newline 
4 2 4 3 3 2 2 3 3 3 3 4 4 3 2 2.2 8.4\newline 
4 2 4 3 3 2 2 3 3 3 3 4 4 3 2 3.5 10.8\newline 
4 2 4 3 3 2 2 3 3 3 3 4 4 3 2 66.6 352.8\newline 
3 2 4 3 3 2 2 4 5 5 3 4 3 3 3 20 72\newline 
3 2 4 3 3 2 2 4 5 4 3 4 3 3 3 6 24\newline 
3 2 4 3 3 2 2 4 5 5 3 4 3 3 3 100 360
\\\hline
\end{tabular}
\end{scriptsize}
\end{center}
\caption{Example datafile for ``W'' consisting of a sample of NASA93 data}
\label{fig:nasadata}
\end{figure}

\begin{figure}[h]
\begin{center}
\includegraphics[width=3in]{figures/osp.png}
\end{center}
\caption{Real-world project description from a NASA Orbital Space Plane}
\label{fig:osp}
\end{figure}

\subsection{Defining Projects in ``W''}

Before a we can define a potential, ``W'' must define its historical cases. Figure ~\ref{fig:nasadata} demonstrates a small example of how any arbitrary historical data is defined for use by ``W.'' The first line declares the name of the dataset, followed by all attribute (column) names and possible values. Because of this enumeration, currently ``W'' only supports discretized datasets. After the @data sigil, historical cases are defined numerically assuming the same column order as the attributes defined above.

The main interface between a user and ``W'' consists of it's project descriptions. A simple example file is given in figure ~\ref{fig:nasaproj}. When a project lead or manager wishes to know what can be done to improve the effort of a future project, ``W'' should only make recommendations that fall within actionable, feasible changes. For example, the historical projects in figure ~\ref{fig:osp} define the COCOMO attribute ranges and hard values that constrain the potential recommendations for the project. In the case of OSP, it is outside the bounds of reality to attempt to change the precedenedness (prec) of a project if the project \emph{has no precedent.}

To define an attribute range as controllable, the ``?'' character denotes this mutability. For example, in the example project in figure ~\ref{fig:nasaproj} the reliability of this project can be set anywhere from three to five, but for managerial reasons tool use is locked at two. If an attribute is defined but lacks a ``?,'' when generating samples for the knn calculations these attribute ranges will be used but not recommened.

\subsection{Finding Relevant Cases}

\begin{figure}[h]
\begin{center}
\includegraphics[width=3in]{figures/selection.pdf}

\end{center}
\caption{A simplified example of historical cases (arrows) and their relation to the defined project instance ranges (dotted box)}
\label{fig:selection}
\end{figure}

Once a project is defined, ``W'' by default generates fifty random projects consistent with the attribute constraints defined. This stoicastic sampling solves the problem of finding the nearest neighbors within a range. Using figure~\ref{fig:selection} as a simplified example, you can see how the attribute ranges defined in the project files allow for a "zone" of potential projects to exist. In the diagram the x dimension represents a continuum of schedule pressure attributes while the y dimension represents a range of managerial experience. For any case, a specific value for both of this attributes exists, as represented by the arrows. Samples generated will always fall within the bounds of the dotted "controllable zone."

From these samples, the k nearest neighbors are determined by calculating the minimum n-dimensional euclidean distance between any case $c$ and generated sample $s$:

\begin{equation}
dist(c,s) = \sqrt{(c_1-s_1)^2+(c_2-s_2)^2+\ldots+(c_n-s_n)^2}
\end{equation}

From these distances, the kth smallest distances are chosen as relevant examples. In the case of ``W'' by default the 20 nearest neighbors are chosen. These 20 nearest neighbors reprsent our query $q$ of the historical space.

\begin{program}[h]
%\footnotesize
\begin{algorithmic}
\Procedure {FindKNN}{$Samples$,$Cases$}
\ForAll {sample in samples}
\ForAll {case in cases}
\State $dist = euclidianDist(sample, case)$
\State $dist = normalize($dist)
\If{distance[case] \&\& distance[case] < dist}
\State $distance[case] = dist$
\EndIf
\EndFor
\EndFor
\State relevant = topK(distance)
\EndProcedure
\end{algorithmic}
\end{program}

\subsection{Contrasting The Neighborhood}

Now that relevant case examples to our project instance have been chosen, we can consider what causes similar projects to present varying effort measurements. One method presented by Menzies and Hu ~\cite{me03c} involves building a contrast set between attributes, separating cases into best and rest then measuring which attributes occur more freqently in best than rest, where the "best" consists of the top k1 neighbors. By default ``W'' considers the top five of twenty cases to be considered "best" and the other fifteen the "rest." 

From this dichotomy, ``W'' implements two such measurement tools for scoring attributes most likely to occur in best but not rest, Nomograms and the B-squared measure. Both allow for determining which attributes show the largest correlation with lower effort.

\subsubsection{B-squared}

A simple strategy to score more favorably towards attributes that occur most often in the best case is to square the number of times. Taking this heuristic one step further, given an attribute $x$, we can penalize $x$'s occurance in the "rest" by dividing the sum of the frequency counts in best and rest~\cite{me09f}, the ensuring rare attributes are weighted appropriately:

\begin{equation}
like = \frac{freq(x\vert best)^2}{freq(x\vert best) + freq(x\vert rest)}
%like = \frac{1}{2}
\end{equation}

From this measure we need only sort each attribute by it's $like$ score to prioritize our recommendations.

\subsubsection{Nomograms}

\begin{figure}[h]
\begin{center}
\includegraphics[width=3in]{figures/nomnom.png}
\end{center}
\label{fig:nom}
\caption{Nomogram modeling survival odds on the HMS Titanic~\cite{mozina04}}
\end{figure}

Nomograms use the simple Naive Bayesian rule to determine whether a given attribute will belong to the instance of the "best" neighbors. By taking the log of the odds ratio of an attribute appearing in best compared to rest, we are given an individual score for that attribute. That score allows us to determine what the probability of a particular attribute or combination of attributes occuring in best or rest. By taking the log, these scores have the unique property of obeying the property of addition.

%\begin{equation}
%odds = \frac{P(c)\prod_iP(a_a\vert c)}{P(\bar{c}}
%\end{equation}

In figure~\ref{fig:nom} the nomograms for survival rates of the RMS Titanic passengers are presented. Each bar represents a different attribute of a passenger, and the labelled marks along that bar represent the attribute values. By adding up the numeric values seen above each attribute value, you can determine how strongly each attribute value predicts for an ourcome of survival. After adding these "points" together, you can calculate the Bayesean probability of survival by converting "Total Points" to P(yes). As shown in figure~\ref{fig:nom}, when considering no other attributes a child has a survival chance of slightly above 50\%.

For ``W,'' nomograms represent another means to rank attributes with the future potential to combine attribute scores for ranking paired attributes.

\begin{figure*}[!t]
\begin{center}
\includegraphics[width=7in]{figures/dubya.pdf}

\end{center}
\caption{Overview of ``W''}
\label{fig:dubya}
\end{figure*}

\subsection{Generating Plans for Effort Reduction}

Now that we've determined what attribute values are important in the query $q$ for reducing effort, we can apply these attributes to an unseen testing set of data to determine whether we've managed to reduce the effort estimation. To do this, we take $q$ and build successive queries on test, incrementally constraining $q_i$ with the highest scoring attribute/value from either the Nomograms or B-squared test.

\begin{equation}\label{}
query_i^* = query + \cup_ic_i
\end{equation}

Each query will reduce the size of the testing set until 

As all positively-scoring attribute constraints are applied to $q_i^*$, depending on the available cases a decision must be made when to stop constraining the theory. While additional treatments may further reduce median effort and variance, additional constraints reduce the size of each query, reducing the historical support for the theory.

Currently, there is future work to be done on developing an automatic stopping rule for early termination of applying treatments. Figure ~\ref{fig:examplerun} demonstrates an example run of ``W.'' Currently, careful human analysis is recommended to obtain the best treatment from ``W'' as one can bias a theory towards real world actionable cost or potentially greater median effort and variance reductions. In the example run from the NASA93 dataset, applying the first constraint, $stor=5$, results in a median reduction of effort from 360 to 170, a reduction of over half. However, this constraint maintains a query with the same maximum effort value as the origial $q$. The application of the next constraint, $time=5$, may require additional resources, but the addition of this constraint historically precludes the case with an effort of 4560.

\begin{figure*}[h]
\begin{center}
\includegraphics[width=3in]{figures/w.png}

\end{center}
\caption{An example run of ``W''}
\label{fig:examplerun}
\end{figure*}

\begin{figure}[!t]
\begin{center}
\includegraphics[width=3in]{figures/reduce.pdf}

\end{center}
\caption{Median effort and median spread reduction across multiple datasets.}
\label{fig:run}
\end{figure}

\begin{figure}[!t]
\begin{center}

\begin{tabular}{|p{.30\linewidth}|p{.22\linewidth}|p{.18\linewidth}|p{.15\linewidth}|}
\multicolumn{4}{l}{Theories Generated by the NASA93 Dataset}\\\hline
Project Dataset\newline
\newline
coc81 flight\newline
coc81 ground\newline
coc81 osp\newline
coc81 osp2\newline
nasa93 flight\newline
nasa93 ground\newline
nasa93 osp\newline
nasa93 osp2
&
Effort Reduction\newline
0\%\newline
95\%\newline
-160\%\newline
31\%\newline
61\%\newline
77\%\newline
49\%\newline
27\%
&
Spread Reduction\newline
18\%\newline
83\%\newline
8\%\newline
71\%\newline
73\%\newline
15\%\newline
48\%\newline
42
&
Theory\newline
\newline
data=3\newline
pmat=2\newline
cplx=5\newline
sced=1\newline
rely=3\newline
aexp=5\newline
sced=3\newline
sced=3
\\\hline
\end{tabular}

\end{center}
\caption{Example theories generated for NASA projects, demonstrating preliminary evidence for very small, local treatments.}
\label{fig:tsize}
\end{figure}


\section{Results and Analysis}

An experiment was conducted with ``W'' across a variety of historical Software Engineering datasets from the PROMISE dataset repository. While the datasets use COCOMO's Lines of Code (KSLOC) and Function Points for quantifying project complexity, any representative discrete model can be used. The datasets used were:

\begin{itemize}
\item{NASA: effort prediction data representing 93 different NASA projects collected in the 80s and 90s. (COCOMO)}
\item{Desharnais: University of Montreal software costs (Function Points)}
\item{ISBSG: StandAlone and Client/Server software costs (Function Points)}
\item{Maxwell: Finish banking data~\cite{maxwelldata}}
\end{itemize}

For each dataset ``W'' generated 50 synthetic examples, took the 20 kth nearest neighbors, and ranked the "best" of these neighbors as being in the 5 lowest effort rankings. ``W'' trained it's theories on 67\% of each dataset and applied learned treatments to the other 33\%. Nomograms were used as a means of ranking treatments.

As shown in figure \ref{fig:run}, the upper-right quadrant of the chart consist of projects where ``W'' generated theories that reduced both the median effort and th "spread" betweeen the 25\% and 75\% quartiles. On average we show a 29\% reduction in median effort along with a 54\% reduction in spread.

While we have consistent improvements across all datasets, outliers in the Desharnais dataset present some problems. This can possibly be attributed to only having synthetic project descriptions rather than real-world representations. For the NASA datasets using USC COCOMO we see larger improvements with the majority of projects demonstrating improvements in both effort and spread reduction. Also, when a decision from ``W'' negatively impacts either effort or spread reduction, only one of these performance metrics is significantly impacted. There exist no decisions that significantly increase both the spread and effort of our results.

Finally, figure \ref{fig:tsize} contrasts the different treatments generated within the same dataset. Three interesting patterns emerge. First, the theories we generate are extremely small. For all projects in the NASA93 only a single treatment brings us the largest reduction. Second, each theory is vastly different. Using the USC COCOMO attributes no consistent pattern emerges in our recommendations, despite consistent effort reduction. Finally, the majority of theories generated include values in the middle of the possible ranges. 

\section{Future Work}

An inherit problem with case-based reasoning involves collecting enough data for a significant representation. We are always collecting data, and for ``W'' there will always be a need for larger, more relevant datasets. Also, there exist multiple schools of thought as to whether lines of code or function points offer a better measure of software complexity. With a greater varity of datasets we may be able to offer a better comparison of these metrics.  

The theories generated in figure ~\ref{fig:tsize} present an interesting case in explanation stability. Although we consistently reduced median effort and spread, the treatments that did so show no correlation in their ability to do so. Such a result points to a potential lack of generality in software engineering, or a deeper pattern in ``W'''s internal decision mechanisms. Given the stance of CBR as a sort of counter-point to the search for a general theory of software cost, the potential for a strong statement on a lack of generality may bolster the position of CBR research.

Also, given the power of contrast sets to extract relevent attributes, future work exists using ``W'' as a feature subset selector. Nomograms have proven to be a reliable bayesian means of ranking features, as shown in our effort reductions. Using this knowledge to weight the euclidean distance measure may prove a valueable tool in more accurately defining relevance of historical cases.

\section{Discussion}

With ``W'' we've demonstrated how contrast sets can be used to extend case-based reasoning by analogy into the treatment realm. Even with the simplicity of euclidian nearest-neighbors for measuring case relevancy we achieve significant and consistent software effort reduction(figure~\ref{fig:run}). We've demonstrated that even small, local theories may offer meaningful improvement for the business user (figure~\ref{fig:tsize}).

While an automatic stopping procedure is useful, business users may appreciate the ability for a human expert to sit in-the-loop with ``W'' and shape treatment options. This flexibility allows a user to easily and quickly decide themselves what theory works best for their situation, and immediately judge the effects of such a theory with historical backing. These theories are small, easy to understand, and useful for the busy reader. Compared to complex decision trees or rule learners ``W'' offers a refreshing simplicity with real results.

%business case for small, local theories


%ACKNOWLEDGMENTS are optional
%
% The following two commands are all you need in the
% initial runs of your .tex file to
% produce the bibliography for the citations in your paper.
\newpage
\bibliographystyle{IEEEtran}
%{\small
\bibliography{refs}
%}   sigproc.bib is the name of the Bibliography in this case

\begin{figure*}
\begin{center}
\includegraphics[width=7in]{figures/cocomo.png}
\end{center}
\caption{Description of COCOMO Scale Factors and Effort Multipliers}
\label{fig:cocomosfem}
\end{figure*}

% You must have a proper ".bib" file
%  and remember to run:
% latex bibtex latex latex
% to resolve all references
%
% ACM needs 'a single self-contained file'!
%
%APPENDICES are optional
%\balancecolumns
%\balancecolumns
% That's all folks!
\end{document}
