% 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{sig-alternate}
%\usepackage{bibspacing}
\usepackage{alltt,url,cite}
\usepackage{algpseudocode}
\usepackage{algorithm}
\usepackage{colortbl}
\usepackage{times}
% 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{\boxplot}[5]{
\begin{picture}(100, 7)
\put(#1, 2){\line(0, 1){4}}
\put(#1, 4){\line(1, 0){#2}}
\put(#3, 4){\circle*{3}}
\put(#3, 4){\line(1, 0){#4}}
\put(#5, 2){\line(0, 1){4}}
\put(50, 3){\line(0, 1){4}}
\end{picture}
}


\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}}
\DeclareMathAlphabet{\mathscr}{OT1}{pzc}%
                                 {m}{it}

\newcommand{\W}{$\mathscr{W}$}
\conferenceinfo{PROMISE}{'10  Timisoara, Romania} 

%\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{Case-Based Reasoning vs Parametric Models\\for Software Quality Optimization}
%
% 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 six authors
% (two rows with three columns) beneath the article title.
% 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{2} %  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
\alignauthor
Adam Brady\\
       \affaddr{Lane Department of CS\&EE}\\
       \affaddr{West Virginia University, USA}\\
       \email{adam.m.brady@gmail.com}
% 2nd. author
\alignauthor
Tim Menzies\\
       \affaddr{Lane Department of CS\&EE}\\
       \affaddr{West Virginia University, USA,}\\
       \email{tim@menzies.us}
}
% 3rd. author
%\alignauthor Lars Th{\o}rv{\"a}ld\titlenote{This author is the
%one who did all the really hard work.}\\
%       \affaddr{The Th{\o}rv{\"a}ld Group}\\
%       \affaddr{1 Th{\o}rv{\"a}ld Circle}\\
%       \affaddr{Hekla, Iceland}\\
%       \email{larst@affiliation.org}

\date{28 May 2010}
% 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}
%Machine learning has been incredibly successful. We are drowning in choice as to how we can infer the cost of building software. Two conflicting choices ask whether we should construct an abstract model to represent software projects, or if simply reasoning from historical cases is enough. This paper presents {\W}, a case-based reasoning algorithm, and compares it to SEESAW, a model-based method for local AI search within COCOMO. We demonstrate that a simple, calibrationless, model-agnostic algorithm such as {\W} performs just as well if not better than SEESAW for reducing software cost across multiple goals such as development effort, project defects, and completion time.

\emph{\textbf{Background:}} There are many data mining methods but few comparisons between them.
For example, there are at least two ways to build {\em quality optimizers}, programs that find 
project options that  change quality measures like defects, development effort (total staff hours), and
time (elapsed calendar months).
In the first way, we 
construct a {\em parametric model}  to represent prior software projects. In the second way,   we just apply 
{\em case-based reasoning} to reason directly from  historical cases.

\emph{\textbf{Aim:}} To assess case-based reasoning vs parametric modeling for quality optimization.

\emph{\textbf{Method:}} 
We compared the {\W}  case-based reasoner against
the SEEWAW parametric modeling tool.

\emph{\textbf{Results:}} {\W} is easy to explain and fast to build. It
makes no parametric assumptions and hence can be rapidly applied to project data in many formats.
SEESAW is an elaborate tool that can only process project data expressed in a particular ontology (i.e. just
the COCOMO attributes). It is also slower to execute than {\W}.
In 24 different tests comparing {\W} and SEESAW, {\W} always performs at least as well as SEESAW. In 6 of those tests {\W} performed statistically better (all tests used Mann-Whitney, 95\% confidence).
 Lastly, like any CBR method, it comes with a built-in 
maintenance strategy (just add more cases).

\emph{\textbf{Conclusion:}} The {\W} case-based reasoning tool is recommended over the SEESAW parametric modeling tool for purposes of quality optimization (except in the case where there is no local data).

\end{abstract}

\category{D.2.9}{Software Engineering}{Management}[Software quality assurance]
\category{D.2.9}{Software Engineering}{Management}[Time Estimation]
\category{I.2.6}{Artificial Intelligence}{Learning}[Analogies]

\keywords{Effort Estimation, Analogy, Optimization, Parametric modeling, Software Quality, COCOMO, Case Based Reasoning} % NOT required for Proceedings

%Sources:

%CBR stuff:
%CBR (4 things): ~\cite{aamodt94}
%Chris Riesbeck, anti-agent: ~\cite{antiAgent}
%CBR description: Teak: not published

%"The use of accurate, systematic, historical data for building
%useful effort prediction systems is extremely important, yet
%in practice, such data is seldom available." ~\cite{01sparse}

%"Similarity is defined as Euclidean distance in n-dimensional space where n is the number of project features" ~\cite{shepperd97}
%CBR for SE~\cite{She02}
%Dynamic memory, founding CBR ~\cite{schank83}
%Leake book, two tenants of CBR ~\cite{leake96}

%Background

%09BFC: ~\cite{me09f}
%Shepphard econ: ~\cite{shepperd07}
%Data set size (doesn't matter): ~\cite{me06f}

%SEESAW:

%Drastic (SEESAW description): ~\cite{me09a}
%Origin: ~\cite{me07g}
%Andre Reuse paper (also covers CO*) ~\cite{orrego09}

%NOVA:
%Description of NOVA, value paper: ~\cite{me09i}

%Model stuff:
%Cocomo: ~\cite{boehm81}
%COCOMOII: ~\cite{boehm00b}
%Local calibration / model variance with COCOMO: ~\cite{me09e}
\newpage
\section{Introduction}
How should we reason about software projects? Should we extrapolate from old data to build
a parametric model; e.g. using  a Bayes net~\cite{fenton07a}, or the 
linear equations of COCOMO~\cite{boehm81,boehm00b}?
Or
is it best to reason directly  from data, without an intervening parametric model,
using case-based reasoning (CBR)~\cite{shepperd97}?
 
This is a difficult question to answer, unless we restrict ourselves
to a particular context.  In this paper, we adopt the context of
{\em software quality optimization}; i.e.  adjusting a software
project such that we improve quality attributes such as  the  {\em
defects} (number of delivered defects),  the {\em months} (calendar
time to delivery) and the {\em effort} (staff time, in person months,
required for that delivery).  This {\em quality optimization} task
is different from {\em effort estimation}.  Effort estimators just
predict measures on the {\em current} project while quality optimizers
seek {\em changes} that most improve a project.

Quality optimization is a non-linear problem. Improving any one goal can  harm the others. For example:
\bi
\item If management rushes projects to completion, they decrease {\em months} but can increase {\em defects}.
\item Projects that adopt elaborate quality assurance procedures can reduce {\em defects} but 
at the cost of increased {\em effort}.
\ei
A quality optimizer must therefore  trade-off between reducing
months {\em and} defects {\em and} effort.
This paper will compare two quality optimizers:
\be
\item
SEESAW is an AI algorithm that explores parametric models of software development, based on COCOMO.
\item
{\W} is a case-based reasoning algorithm that does the same task as SEESAW, without
using  a parametric model.
\ee
SEESAW was first introduced in~\cite{me07f} and has been applied to numerous
 domains~\cite{orrego09,me09f,me08c,me09e,me09a,me09i}. 
{\W} was first introduced in~\cite{me10c} but that report 
includes no comparisons with
other quality optimizers. 
This paper compares {\W}'s
case-based reasoning  against SEESAW's parametric models.
Compared to  SEESAW:
\bi
\item
{\W} finds similar or better optimizations.
\item
{\W}  is simpler to code:
200 lines of AWK as opposed to the 5000 lines
of LISP code used in SEESAW.
\item
{\W} is
faster to run: the following experiments took minutes for {\W},
but hours for SEESAW.
\item
{\W} is simpler to maintain since, in CBR, ``maintenance'' means nothing more than  ``add more cases''.
\item {\W} makes no use of an underlying model and is therefore free of all the assumptions of parametric modeling. Hence it can be quickly applied to more data sets. For example, SEESAW requires data to be in the COCOMO format but {\W} has been applied to numerous data sets in other formats~\cite{me10c}.
\ei

We conclude from these results that,  for the task of quality optimization, 
{\W}'s case-based reasoning methodology is recommended over SEESAW's parametric modeling. The one
exception to this would be that if there is no local data, then {\W} cannot function and SEESAW
should be used. While we offer no conclusion on the general merits of case-based reasoning compared to parametric modeling, these results should encourage further experimentation on the matter.

\section{Background}
The debate between case-based reasoning and model-based methods can be conducted on 
at least two levels:
\be
\item
At one level, it is an engineering-based discussion that assesses these approaches on criteria
like
ease of implementation, runtime speed, and the observed output performance. 
\item
At another level of assessment, we can assess case-based vs model-based in terms of their cognitive
implications.
\ee
Since most of this paper is about level (1), the rest of this section discusses
level (2).

Platonic model-based reasoning 
is meant to seek out universal  truths.
For example, Newton's agenda was to find
a set of equations  (e.g. $F=ma$) that can be applied universally on earth, as well as to  well as distant planets and stars. 
He  succeeded.  In 1846,  rival
astronomers John Adams (in England) and Urbain Leverrier (in France)
raced to find  a previously unseen planet that was disturbing the orbit of Uranus. 
Neptune was first sighted by Adams, then Leverrier, after both men pointed their telescopes
at the precise point in the sky indicated by
Newton's equations.

\begin{figure}[!t]
\center
{\scriptsize
\begin{tabular}{l|r@{:~}l|}\cline{2-3}
upper:   &acap&analysts capability\\
in theory&pcap&programmers capability\\
$\beta < 0$&aexp&application experience\\
&modp&modern programming practices\\
&tool&use of software tools\\
         &vexp&virtual machine experience\\
         &lexp&language experience\\\cline{1-3}
middle   &sced&schedule constraint\\\cline{1-3}
   &data&data base size\\
lower: &turn&turnaround time\\
in theory&virt&machine volatility\\
$\beta > 0$&stor&main memory constraint\\
&time&time constraint for cpu\\
         &rely&required software reliability\\
         &cplx&process complexity\\\cline{2-3}
\end{tabular}}


\includegraphics[width=3.3in]{ranges.pdf}
\caption{COCOMO 1 effort multipliers, and the sorted coefficients found by linear regression from
twenty 66\% sub-samples (selected at random) from the NASA93 PROMISE data set; from~\cite{me05a}.
Prior to learning, training data was {\em linearized}
in the manner recommended by Boehm ($x$ was changed to $log(x)$; for details, see~\cite{me05a}).
During learning, a greedy back-select removed attributes with no impact on the estimates: hence,
some of the attributes have less than 20 results. 
After learning, the coefficients were unlinearized.
}\label{fig:coc1}
\end{figure}
We dream of the day that our SE models will achieve the 
same universality of Newton's equations. To date, we have not been successful.
Researchers like Boehm developed parametric models that predict development effort for software.
In Boehm's COCOMO parametric model (the 1981 version~\cite{boehm81}):
\begin{equation}\label{eq:one}
\small Effort = a * Loc^b * \prod_i\beta_ix_i
\end{equation}
where $x_i$ are one of the {\em effort multipliers} shown in \fig{coc1} (at top) and $\beta_i$ is a
coefficient that controls the influence of $x_i$. 

Such learning combines expert intuition with automatic reasoning. Expert intuitions define the general
form of the parametric model, while automated data mining fills in the details of that model.
For example, the goal of data mining over parametric models is to take local data and learn appropriate values
for the tunable attributes. In the above model, those tunable attributes are $(a,b,\beta_i)$.

Based on linear regression over historical data~\cite{boehm81,boehm00b}, 
Boehm offers values to $(a,b,\beta_i)$ 
to three significant figures. Previously~\cite{me05a}, we have reported
that such precision is somewhat optimistic since
$\beta_i$ has a very large variance. The plot at the bottom of \fig{coc1} shows the $\beta_i$
values learned from twenty 66\% samples (selected at random) of the NASA93 data set from the PROMISE repository.
While some of the coefficients are stable (e.g. the white circles of $loc$ remains stable around 1.1),
the coefficients of other attributes are highly unstable:
\bi
\item The $(max - min)$ range of some of the coefficients is very large; e.g. the upside down black triangles
of $stor$ ranges from $-2 \le \beta_i \le 8$.
\item Consequently, nine of the coefficients in \fig{coc1} jump from negative to positive.
\ei
We have seen instability
in other datasets, including the COC81 data used by Boehm to derive \eq{one}~\cite{me05a}. 
This is an troubling observation.
It seems that
while Newton's equations let us precisely locate Neptune,
Boehm's equations cannot point us exactly at which project attributes will lead to lower effort.

Parametric modeling assumes that (i)~one parametric form (e.g. \eq{one}) is universal across 
multiple domains
and (ii)~that form is tuned to the local situation by adjusting some tuning attributes. 
An opposite approach to  parametric models is case-based reasoning (CBR). In CBR, there are no
universally-applicable parametric models. Rather, every conclusion is dependent on the particulars
of the task at hand.
CBR
is based
on a theory of {\em reconstructive memory}.
According to this theory,
humans do not remember things as they actually happened. Rather, ``remembering'' is an inference
process, characterized by Bartlett as:
\begin{quote}
{\em ... a blend of information contained in specific traces encoded at the time it occurred, plus 
{\em (retrieval time)} inferences based on knowledge, expectations, beliefs, and attitudes derived from other sources~\cite{bartlett32}.}
\end{quote}
Bartlett's work was ignored when first published (1932) but
today it is highly influential; e.g.
experts in psychology \& law caution 
reconstructive 
memory means that {\em leading
questions} can significantly alter a report given by a human witness~\cite{loftus03}.

In AI research, Janet Kolodner~\cite{kolodner83} used reconstructive
memory to characterize expert explanations.  To support her claim,
she offered a set of transcripts of experts explaining some effect.
Her reading of those transcripts was that the experts do not use
{\em verbatim recalling}  when discussing the past. Rather, they {\em reconstruct} an account
of their expertise, on the fly, in response to a particular query.
CBR inference is usually characterized~\cite{aamod94} in four steps:
\be
\item \textit{Retrieve}: Find the most similar cases to the target problem. 
\item \textit{Reuse}: Adapt our actions conducted for the past cases to solve the new problem.
\item \textit{Revise}: Revise the proposed solution for the new problem and verify it against the case base.
\item \textit{Retain}: Retain the parts of current experience in the case base for future problem solving.
\ee
\begin{figure}[!h]
\begin{center}
         \includegraphics[scale=0.45]{figs/cbrcycle1.png}
         \caption{Four steps of CBR, from \protect\url{http://www.peerscience.com/intro_cbr.htm}.}
         \label{fig:cbr}
 \end{center}
\end{figure}
%
%Consequently, if a human software engineer reports the factors that lead to decreased defects or increased
%effort/time for development, we should that report with care and caution. 
%
%If we mistrust human reports on factors that influence software quality, we might turn to data mining
%methods for a better model. At least in our own work, we have achieved disappointing results in trying
%to tame the variance of \fig{coc1}.
%
%
%Elsewhere we have been partially successful in reducing the range of Equation 1 with feature subset selection 
%(FSS)~\cite{me05c,coseekmo  [8, 14] or more data collection. FSS reduces but does 
%not eliminate the a, b variance. Also, further data collection 
%is possible, but only at great organizational expense. This 
%is due to data not being collected or the business sensitiv- 
%ity associated with the data as well as differences in how 
%the metrics are defined, collected and archived. For exam- 
%ple, after two years we were only able to add 7 records to a 
%NASA-wide software cost metrics repository [xomo]. Having 
%failed to generate precise tunings, we developed SEESAW 
%to discover what stable conclusions we could find within the 
%space of possible tunings. 
%
%
%applied to the smallest peeble 
%Case-based reasoning was first proposed as a cognitive theory of human psychology. Based on 
%
Having verified the results from our chosen adapted action on the new case, the new case is added to the available case base. The last step allows CBR to effectively learn from new experiences. In this manner, a CBR system  is able to automatically maintain itself.

In terms of cognitive theory, CBR challenges notions of reasoning as model-building.
The mantra of CBR is ``don't
think, remember''. That is, when faced with some new situation:
\bi
\item
 Do
not reason it out using some underlying model (e.g. Newton's equations
or Boehm's parametric models).  
\item
Rather, respond to a new situation
via an
on-demand survey of past
experiences \cite{schank83}. 
\ei
CBR challenges the premise of the PROMISE conference series.
Currently, this conference bills itself as ``Predictive Models in Software Engineering''. 
This title assumes that
model building is the best way to analyze software engineering.
However, if {\em model-heavy} methods like COCOMO do worse than {\em model-lite} 
CBR methods,
then we would need to rethink
the premise of PROMISE.

(Note
that we call CBR {\em model-lite}, but not {\em model-free}.
For more
on this distinction, see the {\em Discussion } section, below.)



%Previously, we have avoided CBR and favored model-based methods~\cite{orrego09,me09f,me08c,me09e,me09a,me09i}
%for quality optimization. CBR was inferior, we believed, since human experts like to browse and critique
%models.  
%Three factors have prompted a change in this view.
%Firstly,
%even after years of work, we have been unable to reduce model variance 
%via any of feature selection~\cite{chen05}, instance selection~\cite{me06d} or further data collection.
%Feature selection reduces, not does not eliminate, the coefficient variance of \fig{coc1}.
%Further data collection is complicated by numerous factors including
%the business sensitivity associated with the data as well as differences in how
%the metrics are defined, collected and archived. For example, even
%after two years of work, we were only able to add 7 records to a
%NASA-wide
%software
%cost
%metrics
%repository~\cite{me07e}.
%
%Secondly, we found an extension to standard CBR that generates an explicit model
%that experts can browse and critique. That extension is detailed below. For now, all we need say
%is that the extension
%builds a small rule that 
%select for the {\em best} cases (i.e. those with lower defects, effort, time).
%This rule can be be interpreted as a recommendation for what should be changed in a project.
%
%Thirdly, compared against a model-based method, the extended CBR
%works as well or better. Also it is  very simple to build and runs
%faster than the model-based method. Lastly, like any CBR method, it comes with a built-in 
%maintenance strategy (just add more cases).
%


\section{Quality Optimization}
The above discussion motivates a comparison between parametric model-based methods and CBR. To make that
comparison,  we need to explore the same task with two different approaches.
Accordingly,
this section describes quality optimization using SEESAW's parametric models or {\W}'s case-based
reasoning.

One thing that may not be apparent from the following discussion is the relative complexity of the two systems.
Based on recent experience with teaching graduate AI,
we assert that building and assessing SEESAW is a term project while {\W} can be implemented in two weekly homework
assignments (week1 implements some basic data loading and nearest neighbor measures; week2 extends that code
to complete {\W}).

\subsection{SEESAW}

Since 2007, we have applied AI algorithms over parametric models of software development (based on
COCOMO)~\cite{me07f} to implement quality optimizers.
We found this to be a challenging task since it must execute over partial descriptions of projects and, in the case of parametric models,
over models with uncertain internal parameters (like the ranges shown in \fig{coc1}).

In order to address this challenge,
we need to understand the nature of those models.
In parametric modeling, the predictions of a model about a software engineering project are altered by 
project variables $P$ and {\em tunable} attribute coefficients $T$:
\begin{equation}\label{eq:pred}
prediction = model(P, T)
\end{equation}
In the simplified COCOMO model of \eq{simp}, the tuning options $T$ are the 
range of $(a,b)$ and the 
project 
options  $P$ are the range of $pmat$ (process maturity) and $acap$ 
(analyst capability). 
\begin{equation}\label{eq:simp}
effort = a \cdot LOC^{b +  pmat}\cdot acap  
\end{equation}
Based on the definitions of the COCOMO model
we can say that
the ranges of the project attributes are \mbox{$P=1 \le (pmat,acap) \le 5$}. Further, 
given the cone of uncertainty associated with a particular project $p$,
we can identify the subset of the project options $p\subseteq P$ relevant to a particular  project.
For example, a project manager may be unsure of the exact skill level of team members. However,
if she were to assert
``my analysts are better than most'', then $p$ would include $\{acap=4,acap=5\}$.

SEESAW seeks
a treatment $r_x \subseteq p$ that maximizes the $value$ of a  model's predictions where
{\em value} is a domain-specific function that scores model outputs according to user goals:
\begin{equation} \label{eq:argmin}
\arg\max_x\left( \overbrace{r_x \subseteq p}^{AI\;search}, 
\underbrace{t \subseteq T, value(model(r_x,t))}_{Monte\;Carlo} \right)
\end{equation}
The intuition of \eq{argmin} was that, when faced with tuning variance like that seen in \fig{coc1},
we should search for conclusions that are stable across the space of possible tunings.
SEESAW assumed that the dominant influences on the $prediction$ are the project options $p$ (and not the
tuning options $T$).
Under this assumption, 
the predictions can be controlled by:
\bi
\item
Constraining $p$ (using some AI tool)
\item
Leaving $T$ unconstrained (and sampling $t\in T$ using Monte Carlo methods)
\ei 
The parametric models used by SEESAW's models come from COCOMO. These
attributes
have a range taken from
\{very low, low, nominal, high, very high, extremely high\} or
\[\{vl=1, l=2, n=3, h=4, vh=5, xh=6\}\]

In COCOMO-II model~\cite{boehm00b}, Boehm divided the attributes into two sets: the {\em effort multipliers}
and the {\em scale factors}.
The effort multipliers affect effort/cost in a linear manner.
Their  
off-nominal ranges \{vl=1, l=2, h=4, vh=5, xh=6\} 
change the prediction by some ratio.
The nominal range \{n=3\}, however, corresponds to an effort multiplier of 1, causing
no change to the prediction.
Hence, these  ranges  can be modeled as straight lines $y=mx+b$
passing through the point $(x,y)$=$(3,1)$. Such a line has a y-intercept
of $b=1 - 3m$. Substituting this value of $b$ into $y=mx+b$ yields:
\begin{equation}\label{eq:lineem}\small
\begin{array}{l}
\forall x \in \{1..6\}\; EM_i=m_\alpha(x-3) + 1
\end{array}
\end{equation}
where  $m_\alpha$ is the effect of $\alpha$ on effort/cost.

We can also derive a general equation for the scale factors that influence cost/effort in an exponential manner.
These features do not ``hinge'' around (3,1) but take the following form:
\begin{equation}\label{eq:linesf}\small
 \forall x \in \{1..6\}\; SF_i=m_\beta(x - 6) 
\end{equation}
where  $m_\beta$ is the effect of factor $i$ on effort/cost.

Along with COCOMO-II, Boehm also defined the COQUALMO defect predictor.
COQUALMO contains equations of the same syntactic form as \eq{lineem}  and \eq{linesf}, but with different
coefficients.
Using experience from 161 projects~\cite{boehm00b}, we can find the
maximum and minimum values ever assigned to
$m$ for COQUALMO and COCOMO. Hence, to explore
tuning variance (the
$t\in T$ term in \eq{argmin}),
all we need to do is select $m$ values at random from the min/max $m$ values
ever seen.
An appendix to this document lists those ranges.
 
Initially, we  implemented the AI search of  \eq{argmin} using
simulated annealing~\cite{me07f,me08c,me09e}.  Subsequent work
demonstrated that the recommendations found in this way did better
than numerous  standard process improvement methods~\cite{me09a}.
Later implementations were based on a state-of-the-art theorem
prover~\cite{me09i}.  
SEESAW searches within the ranges of project attributes to find
constraints that most reduce development effort, development time (measured in calendar months),
and defects. Figure ~\ref{fig:seesaw} shows SEESAW's pseudo-code.
The code is an adaption of Kautz \& Selman's MaxWalkSat local search
procedure [13]. The main changes are that each solution is scored
via a Monte Carlo procedure (see score in Figure ~\ref{fig:seesaw})
and that SEESAW seeks to minimize that score (since, for our models
it is some combination of defects, development effort, and development
time in months).

SEESAW first combines the ranges for all project attributes. These constraints range from Low to High values. If a project does not mention a feature, then there are no constraints on that feature, and the combine function (line 4) returns the entire range of that feature. Otherwise, combine returns only the values from Low to High. In the case where a feature is fixed to a single value, then Low = High. Since there is no choice to be made for this feature, SEESAW ignores it. The algorithm explores only those features with a range of Options where Low < High (line 5). In each iteration of the algorithm, it is possible that one acceptable value for a feature X will be discovered. If so, the range for X is reduced to that single value, and the feature is not examined again (line 17). SEESAW prunes the final recommendations (line 21). This function pops off the N selections added last that do not significantly change the final score (t-tests, 95\% confidence). This culls any final irrelevancies in the selections. The score function shown at the bottom of Figure 6 calls COCOMO/COQUALMO models 100 times, each time selecting random values for each feature Options. The median value of these 100 simulations is the score for the current project settings. As SEESAW executes, the ranges in Options are removed and replaced by single values (lines 16-17), thus constraining the space of possible simulations.

\begin{figure}[!t]
{\scriptsize
\begin{verbatim}
1 function run (AllRanges, ProjectConstraints) {
2   OutScore = -1
3   P = 0.95
4   Out = combine(AllRanges, ProjectConstraints)
5   Options = all Out features with ranges low < high
6   while Options {
7     X = any member of Options, picked at random
8     {Low, High} = low, high ranges of X
9     LowScore = score(X, Low)
10    HighScore = score(X, High)
11    if LowScore < HighScore
12      then Maybe = Low; MaybeScore = LowScore
13      else Maybe = High; MaybeScore = HighScore
14    fi
15    if MaybeScore < OutScore or P < rand()
16      then delete all ranges of X except Maybe from Out
17      delete X from Options
18      OutScore = MaybeScore
19    fi
20  }
21  return backSelect(Out)
22 }
23 function score(X, Value) {
24   Temp = copy(Out) ;; don't mess up the Out global
25   from Temp, remove all ranges of X except Value
26   run monte carlo on Temp for 100 simulations
27   return median score from monte carlo simulations
28 }
\end{verbatim}
}
\caption{Pseudocode for SEESAW}
\label{fig:seesaw}
\end{figure}

While a successful prototype, SEESAW
has certain drawbacks:
\bi
\item {\em Model dependency:} 
SEESAW requires a 
model to generate the estimates. Hence,  the conclusions reached 
were only as good as this model so 
using this tool requires an initial, possibly time-consuming, model validation process.
\item {\em Data Dependency:}
SEESAW can only process project data in a format compatible with the
underlying model. In practice, this limits the scope of the tool.
\item {\em Arbitrary Design}: 
SEESAW handles two dozen cases using rules designed using ``engineering judgment''; i.e. they are
not based on any theoretical or empirical results in the literature
(for example,
``do not increase automatic tools usage without increasing  analyst capability''). The
presence of such ad hoc rules makes it harder to verify that the tool is correct.
\item {\em Performance}: SEESAW uses 
tens of
thousands of iterations,  with several
effort estimates needed calculated for each iteration. This resulted
in a performance disadvantage.  \item {\em Size and Maintainability}: Due
to all the above factors, the SEESAW code base has proved
difficult to maintain.
\ei
We have found that these factors
limit
the widespread use of quality optimizers:
\bi
\item 
In the three years since our first paper~\cite{me07f},
we have only coded one
software process model (COCOMO), which inherently limits the scope of our investigations.
\item
 No other research group
has applied these techniques.
\ei
These problems motivated an exploration of alternate approaches to quality optimization.

\subsection{{\Large {\W}}}
%
%To assist humans in creating these estimates, a torrent of machine learning research has emerged. A quick search over major journals and conferences revealed over 600 different papers on estimating software cost.~\cite{shepperd07}. Of these papers, the dominant topic was to introduce new estimation techniques. What users are left with is an abundance of choice. Without a single, unifying banner to weave together cost estimation techniques, no one method has achieved \emph{de facto} status in the cost estimate community.
%
%
%For example, the standard method of software cost estimation involves parametric model construction. A representation of a software project is generalized into a mathematical abstraction, then all future projects are estimated according to the parameters of the model. A benefit of which is that once a model can show general trends, extrapolate patterns, and generally reduce complex, human behavior into a mere formula.
%
%There several reasons for the lack of a standard software cost model. These includes generality, data islands and instability. Software models may not be general so it can be inappropriate to apply a software model learned in environment one to environment two. Also, many companies prefer to keep cost related data confidential. This data island effect has also contributed to the fragmentation of the field by preferring building private models rather than using publicly available models. This multiplicity of software effort models has lead to scarcity of the publicly available local data needed for the model based effort estimation. Without sufficient data to build, audit, and tune models, the predictions generated by these models may be highly unstable.~\cite{me09e}
%
%However, the locality of software models may not necessarily be a bad thing. Rather than attempt to generalize all software into a standard model, we can instead simply reason from the data. Case-based reasoning attempts to capitalize on two tenets of the world: similar problems have similar solutions, and that problems encountered once are likely to occur again.~\cite{leake96} As C. Riesbeck explains, "We don't think, we remember." ~\cite{antiAgent}
%
%Model-based and case-based methods represent two ends of a wide spectrum of cost estimation techniques. Rather than attempt to settle an ongoing debate, we simply offer an experiment between the two strategies. This paper introduces {\W}, a simple, case-based algorithm for software effort estimation and reduction. Competing with {\W} is SEESAW, a model-based (USC COCOMO~\cite{boehm81}) algorithm that extends from MaxWalkSat.~\cite{kautz97} {\W} is a much smaller program with hundreds of lines of Awk, whereas SEESAW exists as thousands of lines of C++/LISP. The relative complexity of these two algorithms resides not just in their languages; we will show the intrinsic simplicity of {\W} compared to the Monte Carlo simulator an AI search of SEESAW.
%
%This paper is structured in the following order: First we present a deeper look at the technical trade-offs of model-based reasoning and case-based reasoning. Second, we pose three research questions to be answered by the results of our experiment. Then, we'll explore the implementations of SEESAW and {\W}. Finally, we present an experiment that compares the software cost recommendations from {\W} with those of SEESAW.
%
%\subsection{Research Questions}
%
%\textbf{RQ1:} Can the recommendations produced by a case based reasoning system such as {\W} perfom better than a model-based approach?
%
%
%\textbf{RQ3:} In which situations should one prefer a particular method over another?
%
%\section{Background}
%
%\subsection{Estimation Techniques}
%
%Sheppherd categorizes the current landscape of software cost estimation methods into three groups.~\cite{shepperd07}
%\begin{itemize}
%\item Human-centric techniques (a.k.a. expert judgment)
%\item Algorithmic/parametric models such as COCOMO ~\cite{boehm81}~\cite{boehm00b}
%\item Induced prediction systems such as case-based reasoning.
%\end{itemize}
%\emph{Human centric techniques} are the most widely-used estimation method ~\cite{shepperd07}, but are problematic.
%If an estimate is disputed, it can be difficult to reconcile competing human intuitions (e.g.) when one estimate is generated by a manager who is senior to the other estimator. Also, Jorgensen ~\cite{jorgensen04} reports that humans are surprisingly poor at reflecting and improving on their expert judgments. For the purposes of this paper, we will set aside the comparision to human-centric techniques as another topic.
%
%%-GENERAL OVERVIEW OF 3 CLASSIFICATIONS-
%
%%Human-centric is the most widely-used(teac S2 has refs), but are problematic. In human-centric approaches...
%
%%Human factors influence bias into estimations. The choice of one manager's analysis over another may come not from the intrinsic quality of the analysis, but hierarchal factors like seniority.
%
%%Another approach is model based...
%%generate model only once (time-consuming), then no data needed. Can show general trends, extrapolate said %trends. Nice abstractions. Experts can inject knowledge.
%
%%third: CBR:
%%satisfying justifications, fewer assumptions, data-agnostic, local data might not fit the model, no %calibration
%%(cite: chris riesbeck)
%
%\subsection{Modeling Techniques}
%
%One alternative to expert judgment is a \emph{model-based} estimate. Models are a reproducible methods for generating an estimate. This is needed for (e.g.) U.S. government software contracts that require a model-based estimate at each project milestone. Such models are used to generate and audit an estimate, or to double-check a human-centric estimate. Model based estimates can be generated using an algorithmic/parametric approach or via induced prediction systems. In the former, an expert proposes a general model, then domain data is used to tune that model to specific projects. For example, Boehm's 1981 COCOMO model ~\cite{boehm81} hypothesized that development effort was exponential on LOC and linear on 15 effort multipliers such as analyst capability, product complexity, etc. Boehm defined a local calibration procedure to tune the COCOMO model to local data. Induced prediction systems are useful if the available local training data does not conform to the requirements of a pre-defined algorithmic/parametric model such as COCOMO. There are many induction methods including stepwise regression, linear regression, rule induction, neural nets, model trees, and analogy, just to name a few. All these methods have underlying assumptions.
%
%\subsection{Case Based Reasoning}
%
%Case based reasoning is a method of machine learning that seeks to emulate human recollection and adaptation of past experiences in order to find solutions to current problems. That is, as humans we tend to base our decisions not on complex reductive analysis, but on an instantaneous survey of past experiences \cite{schank83}; i.e. we don't think, we remember. CBR is purely based on this direct adaptation of previous cases based on the similarity of those cases with the current situation. Having said that, a CBR based system has no dedicated world model logic, rather that model is expressed through the available past cases in the case cache. This cache is continuously updated and appended with additional cases.
%
%Aamodt \& Plaza \cite{aamod94} describe a 4-step general CBR cycle, which consists of:
%\be
%\item \textit{Retrieve}: Find the most similar cases to the target problem. 
%\item \textit{Reuse}: Adapt our actions conducted for the past cases to solve the new problem.
%\item \textit{Revise}: Revise the proposed solution for the new problem and verify it against the case base.
%\item \textit{Retain}: Retain the parts of current experience in the case base for future problem solving.
%\ee
%Having verified the results from our chosen adapted action on the new case, the new case is added to the available case base. The last step allows CBR to effectively learn from new experiences. In this manner, a CBR system  is able to automatically maintain itself.
%As discussed below, {\W} supports $retrieve$, $reuse$, and $revise$ (as well as $retain$ if the user collecting data so decides).
%
%\begin{figure}[!ht]
%\begin{center}
%         \includegraphics[scale=0.4]{figs/cbrcycle1.png}
%         \caption{figure}{A diagram describing the steps of CBR (source: http://www.peerscience.com/Assets/cbrcycle1.gif).}
%         \label{fig:cbr}
% \end{center}
%\end{figure}
%
%This 4-stage cyclical CBR process is sometimes referred to as the R4 model \cite{She02}.
%Shepperd \cite{She02} considered the new problem as a case that comprises two parts.
%There is a description part and a solution part forming the basic data structure of the system.
%The description part is normally a vector of features that describe the case state at the point at which the problem is posed. The solution part describes the solution for the specific problem (the problem description part).
%
%The similarity between the target case and each case in the case base is determined by a similarity measure.
%Different methods of measuring similarity have been proposed for different measurement contexts.
%A similarity measure is measuring the closeness or the distance between two objects in an n-dimensional Euclidean space,
%the result is usually presented in a distance matrix (similarity matrix) identifying the similarity among all cases in the dataset.
%Although there are other different distance metrics available for different purposes, the Euclidean distance metric is probably the most commonly 
%used in CBR for its distance measures.
%
%Irrespective of the similarity measure used, the objective is to
%rank similar cases from case-base to the target case and utilize
%the known solution of the nearest $k$-cases. The value of $k$ in
%this case has been the subject of debate \cite{kadoda00,shepperd97}:
%Shepperd~\cite{shepperd97},
%Mendes~\cite{Mendes2003} argue for $k=3$ while
%Li~\cite{Li2009} propose $k=5$. 
%
%Once the actual value of the
%target case is available it can be reviewed and retained in the
%case-base for future reference. Stored cases must be maintained
%over time
% to prevent information irrelevancy and inconsistency. This is a
% typical case of incremental learning in an organization utilizing
% the techniques of CBR.
%
%Observe that these 4 general CBR application steps (retreive, reuse, revise, retain)
%do not include any explicit model based
%calculations; rather we are relying on our past experience, expressed
%through the case base, to estimate any model calculations based on the
%similarity to the cases being used. 
%This has two advantages:
%\be
%\item
%It allows us to operate independently of the models being used. 
%For example, our prior report to this
%conference~\cite{me09i}  ran over two data sets. This 
%this study, based on CBR, uses twice as many data sets.
%\item
%This improves our performance,
%since data retrieval can be  more efficient than calculation,
%especially given that many thousands of iterations of calculation
%were needed with our traditional modeling based tool. 
%As evidence of this, despite the use of a slower language, {\W}'s AWK code
% runs faster than the C++/LISP used in SEESAW.
% It takes just minutes to conduct 20 trials over 13 data sets with
%{\W}. A similar trial, conducted with SEESAW, can take hours to run.
%\ee
%
%%"Similarity is defined as Euclidean distance in n-dimensional space where n is the number of project features" ~\cite{shepperd97}
%%CBR for SE~\cite{She02}
%%Dynamic memory, founding CBR ~\cite{schank83}
%%Leake book, two tenants of CBR ~\cite{leake96}
%
%\section{Implementations}
%\subsection{W}
%
The standard procedure for CBR is to report the median class value of some local neighborhood. This neighborhood is typically defined as the Euclidean distance from a defined project in n-dimensional space with n project features~\cite{shepperd97}. {\W} works similarly, but defines a project as a range of values:
\bi
\item From a range of project values, cases are retrieved that match a specific amount of \emph{overlap} with the defined project ranges. A case's overlap is defined as the percentage of attributes that fall within the specified ranges of the defined project.
\item From these selected similar cases, the cases are sorted by a measure of utility to determine the {\em better}
examples.
\item From these sorted ranges, a \emph{contrast set} is learned. The top 5 "best" cases (those with the best utility measure) are placed into a set labeled "best". The next 15 ranked cases are placed into a set labeled "rest", for a combined total of 20 cases.
\item From the contrast set, {\W} selects the features that best select for the region with the best utility measurements.
\ei
In the above, {\em better}  is determined by some
domain-specific predicate.
 In the case of effort, defect, and month estimations, this utility is the normalized euclidean distance from the lowest possible cost for all three factors.

\subsubsection{Contrast Sets}

Once a contrast set learner is available, it is a simple matter to add {\W} to CBR.  {\W} finds contrast sets using a  greedy search, where candidate contrast sets are ranked by the frequency of which they appear in the "best" set squared divided by how often the candidate appears in both the "best" and "rest" sets. 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 occurrence 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}\label{eq:br}
like = \frac{freq(x\vert best)^2}{freq(x\vert best) + freq(x\vert rest)}
\end{equation}

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

\subsubsection{The {\W} Algorithm}


CBR systems input a query $q$ and a set of cases. They return the subset of cases $C$ that is relevant to the query.
In the case of {\W}:
\bi
\item
Each case $C_i$ is a historical record of one software project, plus the development
effort required for that project.  Within the case, the project is described
by a set of attributes which we assume have been discretized into a small
number of discrete values (e.g. analyst capability $\in \{1,2,3,4,5\}$ denoting
very low, low, nominal, high, very high respectively).
\item
Each query $q$ is a set of constraints describing the particulars of a project.
For example, if we are interested in a schedule over-run
for a complex, high reliability project that
has only minimal access to tools, then 
those constraints can be expressed in the syntax of \fig{nasaproj}.
\ei

{\W} seeks $q'$ (a change to the original query)
that finds another set of
cases $C'$ such that the median effort values in $C'$ are less than that of $C$ (the cases found by $q$).
{\W} finds $q'$ by first dividing the data into two-thirds training and one-third testing.
{\em Retrieve} and {\em reuse} are applied to the training set, then {\em revising}
is applied to the test set.

In the 	 {\em retrieve} step, the initial query $q$ is used
to find the $N$ training cases nearest to $q$ using a Euclidean
distance measure where all attribute values are normalized from 0 to 1.

In the 
{\em reuse}  (or adapt) step, the $N$ cases are sorted by effort and divided into
the $K_1$ best cases (with lowest efforts) and $K_2$ rest
cases. For this study, we used $K_1=5, K_2=15$.
Then we seek  the contrast
sets that select for the $K_1$ best cases with the {\em better} estimates.
All the attribute ranges that the user has marked as ``controllable'' are scored and sorted by \eq{br}.
This sorted order $S$ defines a set of candidate $q'$ queries
that use the first {\em i-th} entries in $S$:
\[
q_i' = q \cup S_1 \cup S_2 ... \cup S_i
\]


According to \fig{cbr}, after {\em retrieving} and {\em reusing} comes
{\em revising} (this is the ``verify'' step).
When revising $q'$, {\W} prunes away irrelevant ranges using the algorithm of \fig{w}.
\begin{figure}[!t]
\scriptsize
\begin{verbatim}
@project example
@attribute ?rely 3 4 5 
@attribute tool  2 
@attribute cplx 4 5 6 
@attribute ?time 4 5 6
\end{verbatim}
\caption{{\W}'s syntax for describing
the input query $q$. Here,  all the values run 1 to 6.
$4\le cplx \le 6$ denotes projects with above average complexity.
Question marks denote what can be controlled- in this
case, $rely,time$ (required reliability and development time)}
\label{fig:nasaproj}
\end{figure}

\begin{figure}
\center
\small
\begin{tabular}{|p{.95\linewidth}|}\hline
	\be
	\item Set $i=0$ and $q_i'=q$ 
	\item Let $Found_i$ be  the test cases consistent with  $q_i'$ (i.e. that
do not contradict any of the attribute ranges in $q_i'$).
	\item Let $Effort_i$ be  the median efforts seen in $Found_i$.
	\item If $Found$ is too small then terminate (due to over-fitting). 
After Shepperd~\cite{shepperd97}, we
terminated for $|Found|<3$. 
	\item If $i>1$ and $Effort_i < Effort_{i-1}$, then terminate (due to no improvement).
	\item Print $q_i'$ and $Effort_i$.
    \item Set $i=i+1$ and $q_i'= q_{i-1} \cup S_i$ 
	\item Go to step 2.
	\ee\\\hline
\end{tabular}
\caption{Revising $q$ to learn $q'$.}\label{fig:w}
\end{figure}
On termination, {\W} recommends changing a project according to the set $q'-q$.
For example, in \fig{nasaproj}, if $q' -q$ is $rely=3$ then this treatment recommends
that the best way to reduce the effort for this project is to 
reject $rely=4\;or\;5$.

%
%\subsection{Multiple Goals}
%
%Optimizing for simply effort in software cost estimation can be bad. For instance, it may require less effort to produce software with much lower quality standards, but doing so may drastically increase defects. Additionally, reducing the schedule constraints will incur larger development time. To solve this problem, {\W} bases it's recommendations on multiple goals.
%
%It does this by ranking on some measure of utility for each case. If, say, we wish to reduce the effort, defects, and months requirements, a simple utility measure can be derived from the normalized Euclidian distance from the best possible values for all goals (\textbf{E}ffort, \textbf{D}efects, \textbf{M}onths):
%
%$$score = \frac{E - E_{min}}{E_{max} - E_{min}} + \frac{D - D_{min}}{D_{max} - D_{min}} + \frac{M - M_{min}}{M_{max} - M_{min}}$$
%

Formally, the goal of {\W} is find the smallest $i$ value such that
$q_i'$ selects cases with the more of the {\em better} estimates.
The reader might protest that the generation of some succinct human-readable construct like $q_i'$ means
that {\W} is not a ``real'' case-based reasoner. In that view, the distinguishing feature of CBR
is that its reasoning is instance-based and it never generates any generalizations.

In reply, we observe that 
{\W} is not the only system that extends standard CBR with some generalization tools.
Watson~\cite{watson98} reviews numerous CBR systems that, for example, run decision tree
learners over their case library in order to automatically generate an index to the cases. 
Also, once
a system can read a case library,
compute distance calculations, and generate a sorted list of the nearest neighbors, implementing
\fig{w} and \eq{br}
is only a few dozen lines of code. That is, {\W} is such a  small extension
to standard CBR that it would be somewhat pedantic to declare that it is not ``real'' CBR.

\section{Comparing {\Large {\W}} to SEESAW}

In order to compare {\W} and SEESAW, both systems require similar inputs.
SEESAW can only handle models in the COCOMO format. Hence,  we restrict ourselves to data in that format
(see~\cite{me10c}
for examples of {\W} running on a much broader set of inputs). 

The inputs required for this study are:
\bi
\item {\W} needs a set of {\em historical cases}.
We used the 
NASA93 dataset available from \texttt{http://promisedata.org/data}. This dataset represents 93 different NASA projects collected from the 1980's and 1990's represented as feature vectors describing each project in COCOMO format.
NASA93 data only contains historical information for
project effort. Development time (measured in calendar months) and defects were added in using the COCOMO/COQUALMO models.
\item Both SEESAW and {\W} need an {\em objective function} that guides their search. 
In this study, the objective function rewarded
minimization of the sum of defects and effort and months (after these values had been normalized
to the same range).
\item Both SEESAW and {\W} need a set of {\em project constraints} that tune their conclusions to particular projects. We used the project constraints of \fig{cases}.
\ei
\fig{cases} comes from our debriefing of NASA program managers and shows
different
kinds of NASA mission:
\bi
\item \emph{Ground} and \emph{flight} represent typical ranges for most NASA projects at the Jet Propulsion Laboratory (JPL);
\item \emph{OSP} represents the guidance, navigation, and control aspects of NASA's 1990 Orbital Space Plane;
\item \emph{OSP2} represents a second, later version of OSP with a more limited scope of COCOMO attributes.
\ei
The $values$ column in that figure shows settings that cannot be
changed; e.g. for OSP, the required reliability is fixed at $rely=5$.
On the other hand, the $low$ and $high$ ranges in that figure define
the space of possible recommendations for that project. For instance,
the reliability of the JPL flight software can vary from a ranking
of 3 (nominal) to 5 (very high). 

{\W} used \fig{cases} to set its initial query $q_0$. 
SEESAW used \fig{cases} to guide a set of simulations around its parametric models. For each case
study, 1000 times, inputs were selected
at random, constrained by \fig{cases} (so the inputs 
for case study $X$ conformed to the description of $X$ shown in that figure).

\input{figs/projects.tex}



%We present an experiment to compare the effort, defects, and months reduction power of {\W} compared to SEESAW. Each algorithm will be given a set of 4 real-world projects with defined COCOMO attribute ranges. The goal of each algorithm will be to choose specific recommendations for these value ranges that will maximize the reduction the project's effort, defects, and months.
%
%Before we can measure the relative effectiveness of one effort reduction recommendation over another, we need a way to compare the recommendations from both SEESAW and {\W} in common terms. This is trivial, as once each tool generates its recommendations, these recommendations can then be applied using any model or inference prediction system. Once applied, regardless of the testing environment we can compare the relative effectiveness of each algorithm. For the sake of simplicity we have chosen to test recommendations using W.
%
%\subsection{Dataset and Project Descriptions}
%
%\subsection{Performance Metrics}

\input{figs/tops}

In order to offer a fair comparison between SEESAW and {\W}, we proceeded as follows.
Recall that {\W} has a {\em training} component that implements
 {\em retrieve}, {\em reuse}, and {\em revise} (described around \fig{w}).
A {\em test} component was implemented that copied the code used for
{\em retrieve}. This test component was modified such that it executed
on a different {\em test set} that contained no data used in {\em training}.

Given that rig, for each case study in \fig{cases}, we repeated the following process 50 times.
\bi
\item
The available data (NASA93)
was divided into a {\em train} and {\em test} sets (of sizes  66\%:33\%).
The division was random so that each time, different instances appeared in train and test.
\item
The median and spread values for effort, months, and defects were collected from the
{\em train set}. 
These medians and spreads were  recorded as  the $before$ values.
\item
Each quality optimizer ({\W} and SEESAW) was run separately.
The {\W} algorithm used the {\em train set} while SEESAW used its internal models.
In either case, the quality optimizer returned a set of recommendations on how to change the project
in order to reduce effort, defects, and development time (measured in calendar months).
\item
These recommendation were assessed in the same way: by
 passing them to {\W}'s test component which retrieved  relevant cases from the {\em test set}.
\item
The median and spread values for effort, months, and defects were collected from the
instances retrieved from the {\em test set}. These were recorded as  the $after$ values.
\ei
The results were reported in terms of {\em median} and {\em spread}.
We say that the $median$ of a set of numbers are the 50th-percentile value while
the $spread$ is difference between the 75th and 25th percentile value.
The median is a measure of central tenancy while the spread
is a measure of uncertainty around the median.
Decreasing the spread means that the predictions
fall within a narrower range. We report spread rather than other measures like standard deviation
since we wish to avoid any inappropriate assumptions of symmetrical distributions.

\section{Results}

%A detailed summary of the reductions in effort, defects, and overall "score" of the four Nasa case studies can be found in figures figures ~\ref{fig:score} ~\ref{fig:effort} ~\ref{fig:defects} ~\ref{fig:months}. 
%average-reductions.tex}


Average median and spread results over the 50 trials are shown in
\fig{results}.
The last column in each group (labeled ``Change'') shows the relative change in effort, defect, months found by {\W} or SEESAW.
A {\em negative} amount in this column denotes an optimization failure (increased defect, effort, months).
Note that such negative results occur only in a small minority of results.

The gray rows 
indicate any member of a pair that was both
statistically significantly different {\em and} had a lower 50th percentile value.
Note that for most pairs, the results are not statistically significantly different (Mann-Whitney, 95\% confidence level).

\begin{figure}[!t]
\center
\includegraphics[width=3in]{figs/changes.pdf}
\caption{Range of changes in median and spread generated by applying
the recommendations of either {\W} or SEESAW. The median observed
changes were (15, 61.5)\% for (medians, spreads), respectively. For the sake
of brevity, this
graph ignores the   -119\% outlier value seen in OSP2 defects.
}\label{fig:changes}
\end{figure}

Before commenting on SEESAW vs {\W}, we first note that our results should encourage more use
of quality optimization.
Observe that,
in the majority of cases,
{\em quality optimization works} regardless of how it is implemented (e.g. CBR vs parametric models).
In the 52 experiments of \fig{results},
positive quality improvements were seen for $49/52=94\%$ experiments
(the 3 exceptions are in the defect results of Flight and OSP2).

Another result that should encourage more use of quality optimizers is the reduction in the spreads. In
all experiments the amount of uncertainty in the median estimates was reduced.
As shown in 
\fig{changes}, the reduction in the spread was usually over
61\%.
This is a major advantage of quality optimizers since uncertainty
is an serious issue that plagues the managers of software engineering projects.

The spread reductions were larger than the median reductions.
As shown in 
\fig{changes}, the expected median reduction in any quality estimate was  only 15\%.
Note that 
if this were otherwise, then that would be a somewhat damning critique of
current software engineering
practices. To see this, consider the implications
of  quality optimizers finding recommendations that resulted in an order of magnitude
reduction in effort {\em and} defects {\em and} development time.
That would
suggest that the managers of software engineering projects are routinely missing
changes that would significantly improve their projects.

Another feature to note is that,
with only a few exceptions, the median optimizations obtained from 
case-based reasoning or parametric modeling
are very similar. 
For example,
in median MONTHS results (top right of \fig{results}),
within each pair of treatments,
the change in the median months values  is very similar: 
\bi
\item 19 vs 18\% change (for Ground)
\item 14 vs 9\% change (for Flight)
\item 11 vs 12\% change (for OSP)
\item  12 vs 14\% change (for OSP2)
\ei
That is,   projects can contain an 
an inherent set of constraints 
that cannot be changed,
even by smart algorithms. 
Certainly, we can fine tune the structure of a project to obtain
some improvements in effort, defects, and months but managers
should not expect a magic silver bullet that offers orders
of magnitude improvement in their software process.

Turning now to the main point of this paper, 
we conducted statistical tests on each pair of {\W} vs SEESAW improvements in median/spread for each query.
A Mann Whitney U test (95\% confidence)
was performed on the two sets of reduction distributions from each comparison. 
The statistical tests are summarized in  \fig{win-loss-tie}.
Note that, in the majority case ($\frac{18}{24}$), {\W}'s case-based reasoning
performs as well as $SEESAW's$ parametric modeling.
\input{figs/win-loss-tie.tex}

Also, when the performance results were different, case-based reasoning did better than 
parametric modeling ($\frac{6}{24}$)- sometimes spectacularly so,
Observe the median DEFECT OSP2 results (last line, top row, middle of \fig{results}): SEESAW's
recommendations resulted in  a dramatic increase in the number of
delivered defects (2612 to 7797). This result
shows that {\W}'s modest decrease in defects (13\%) is actually
far better than those found by the other approach. 

In summary, the simple case-based reasoning of {\W} performs just as well, or better,
than SEESAW's elaborate parametric modeling.

%\input{figs/w-vs-seesaw.tex}

\section{Discussion}
\subsection{Search-based Software Engineering}
Previously~\cite{me09i}, we have explored the connection of SEESAW to search-based SE (SBSE)~\cite{harman04}.
In summary, 
SBSE uses optimization techniques
from
operations research and meta-heuristic search (e.g., simulated annealing and genetic algorithms)
to hunt for near-optimal
solutions to complex and over-constrained
software engineering problems. 
SBSE has been applied to many
problems in software engineering (e.g., requirements engineering~\cite{jalali08})
 but most often in the field of software testing~\cite{andrews07}.
Harman's writing inspired us to try simulated annealing (SA) to search the what-ifs in untuned COCOMO
models~\cite{me07f}. 
For quality optimization, however, we found that search methods
taken from the constraint satisfaction literature
out-perform SA~\cite{me09i}.

\subsection{Model-lite}
We said above that CBR was {\em model-lite}, but not {\em model-free}.
We hesitate to call CBR {\em model-free}, lest we incur the wrath
of Janet Kolodner or Roger Shank~\cite{shank77}.
Kolodner and Shank regard CBR as a {\em model} of human cognition
where knowledge in a context-dependent
manner, according to the task at hand. This construct may differ from context to context
but the search mechanisms by which the construct is built (CBR) is constant.

To expand on that point, we note that ``model'' has at least two
definitions:
\be
\item A hypothetical description of a complex entity or process. 
\item A plan to create, according to a model or models. 
\ee 
The first definition is closest to Shepperd's definition of ``model-based systems''. According to Shepperd~\cite{shepperd07} software effort estimation methods separate into ``human-centric'' techniques and ``model-based'' techniques. In the former, humans produce their recommendations without using some externalizable representation. In the latter, a variety of techniques may be used which, according to Shepperd, divide into algorithmic/parametric models (like COCOMO) and induced prediction systems (which include regression, rule induction, CBR, and many others). 

We can marry Shepperd's view with that of Kolodner and Shank by specializing the definition
of model-based systems. Extending Shepperd's ontology, we say that model-based systems can be sorted according to how much modeling they assume prior to induction. At one end of that sort order, we have parametric models like COCOMO. We call these {\em model-heavy} since they conform to the first definition of ``model'', shown above. At the other end of that sort are  the {\em model-lite} methods like CBR. These model-lite methods conform to the second definition of ``model''. Note that this second definition is closest to Kolodner and Shank's view on CBR; i.e. the CBR model is a recipe for generating context-dependent knowledge.



\section{Conclusion}
\input{conclude}

\section*{Acknowledgments}
This work was partially funded by the United Stated National Science Foundation (CCF-1017263). 
\bibliographystyle{abbrv}
\bibliography{refs}  

\appendix
This appendix lists the minimum and maximum $m$ values used
for \eq{lineem} and \eq{linesf}.
In the following, $m_\alpha$ and $m_\beta$ denote COCOMO's linear and exponential
influences on effort/cost, and 
$m_\gamma$ and $m_\delta$ denote COQUALMO's linear and exponential influences on number of
defects.


Their are two sets of  effort/cost multipliers:
\be
\item
The {\em positive effort EM} features, with slopes $m^+_\alpha$, that are proportional to effort/cost. 
These features are:
cplx,
data,
docu,
pvol,
rely,
ruse,
stor, and
time.
\item
The
{\em negative effort EM} features, with slopes $m^-_{\alpha}$,
are inversely proportional to effort/cost.
These features are 
acap,
apex,
ltex,
pcap,
pcon,
plex,
sced,
site, and
tool.
\ee
Their $m$ ranges, as  seen in 161 projects~\cite{boehm00a}, are:
\begin{equation}
\footnotesize
\left(0.073 \le m^+_\alpha \le 0.21\right) \wedge
\left(-0.178 \le m^-_\alpha \le -0.078\right)
\end{equation}
In the same sample of projects,
the COCOMO effort/cost scale factors (prec, flex, resl, team, pmat) have
the range: 
\begin{equation}\footnotesize
-1.56 \le m_\beta \le -1.014
\end{equation}
Similarly, there are two sets of defect multipliers and scale factors:
\be
\item The {\em positive defect} features have slopes $m^+_\gamma$ and are proportional
to estimated defects.  These features are
flex,
data,
ruse,
cplx,
time,
stor, and 
pvol.
\item The {\em negative defect} features, with slopes $m^-_\gamma$, that are inversely proportional
to the estimated defects. These features are 
acap,
pcap,
pcon,
apex,
plex,
ltex,
tool,
site,
sced,
 prec,
resl,
team,
pmat,
rely, and
docu.
\ee
COQUALMO divides into three models describing how defects change in requirements, design,
and coding.
These  tunings options have the range:
\begin{equation}\label{eq:coq}\small
\begin{array}{c}
requirements\left\{
\begin{array}{c}
0 \le m^+_\gamma \le 0.112\\
-0.183 \le m^-_\gamma \le -0.035
\end{array}
\right. \\
~\\
design \left\{
\begin{array}{c}
0 \le m^+_\gamma \le 0.14\\
-0.208 \le m^-_\gamma \le -0.048
\end{array}
\right. \\
~\\
coding \left\{
\begin{array}{c}
0 \le m^+_\gamma \le  0.14\\
-0.19 \le m^-_\gamma \le -0.053
\end{array}
\right.
\end{array}
\end{equation}
The tuning options for  the  defect removal features are:
\begin{equation}\label{eq:linedefrem}\small
\begin{array}{rl}
\forall x \in \{1..6\} &SF_i=m_\delta(x - 1)\\
requirements: 	& 0.08 	\le m_\delta \le 0.14 \\
design: 		& 0.1 	\le m_\delta \le 0.156 \\
coding: 		& 0.11 	\le m_\delta \le 0.176 \\
\end{array}
\end{equation}
where  $m_\delta$ denotes the effect of  $i$ on  defect removal.




\balancecolumns

\end{document}
