\documentclass[journal,compsoc]{IEEEtran}
%\documentclass[onecolumn,12pt,journal,compsoc]{IEEEtran}\renewcommand{\baselinestretch}{1.41}
\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}
}


\usepackage[table]{xcolor}

% *** CITATION PACKAGES ***
%
\ifCLASSOPTIONcompsoc
  % IEEE Computer Society needs nocompress option
  % requires cite.sty v4.0 or later (November 2003)
  % \usepackage[nocompress]{cite}
\else
  % normal IEEE
  % \usepackage{cite}
\fi

\usepackage{cite,url}

\ifCLASSINFOpdf
  \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
  \graphicspath{{/plots/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  \DeclareGraphicsExtensions{.pdf,.jpeg,.png, .eps}
\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


\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{verbatim}
\usepackage{fancyvrb}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{timtricks}
\usepackage{multirow}
\usepackage{rotating}
\usepackage{times}
\usepackage{cite}
\usepackage{float}
%\restylefloat{figure}


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


\definecolor{lightergray}{gray}{.7}
\newcommand*\lightergray{\color{lightergray}}


\newcommand{\W}{$\mathcal{W}$}

\begin{document}

\title{Learning Changes to Software Projects}
%to Improve ATEAK: Learning Better Case Selection Strategies for Analogy Based Software Cost Estimation}

\author{ Tim~Menzies,~\IEEEmembership{Member,~IEEE}, %
		Adam~Brady,%
        Jacky~W.~Keung,~\IEEEmembership{Member,~IEEE},\\% <-this % stops a space
		Steven Williams, Oussama El-Rawas, Phillip Green%
\IEEEcompsocitemizethanks{
\IEEEcompsocthanksitem Tim Menzies (corresponding author)
Adam Brady, Phillip Green and Oussama El-Rawas
are with the 
Lane Department of Computer Science and Electrical Engineering, West Virginia University.
E-mail: 
tim@menzies.us,
adam.m.brady@gmail.com,
deathcheese@yahoo.com,
orawas@gmail.com 
\IEEEcompsocthanksitem Jacky W. Keung is with the School of Computer Science and Engineering, University of New South Wales.
E-mail: jacky.keung@nicta.com.au.
\IEEEcompsocthanksitem Steven Williams
is with the 
School of Informatics and Computing
Indiana University, Bloomington.
E-mail:
stevencwilliams@gmail.com.}% <-this % stops a space
\thanks{This research is funded in part by NSF,CISE, project \#0810879.}}

\markboth{Journal of IEEE Transactions on Software Engineering,~Vol.~X, No.~Y, SomeMonth~201z}%
{Shell \MakeLowercase{\textit{et al.}}: Bare Demo of IEEEtran.cls for Computer Society Journals}
\IEEEcompsoctitleabstractindextext{
\begin{abstract}
\newline
BACKGROUND:
Given many possible changes to a software project, which ones are
recommended?
\newline
AIM:
To comparatively assess different decision procedures for recommending project changes.
\newline
METHOD: 
We search for project recommendations within data from eight projects using  various AI tools:
six model-based methods and one instance-based method called {\W}2.
Results were assessed by comparing effort, defects, development time values in the raw data versus the subset of the
data selected by those recommendations.  \newline
RESULTS:
In the majority case, significantly large reductions on effort, defects and development time were achieved. Further, {\W}2
performed as well, or better, than anything else in this study. {\W}2 does not rely on an underlying model
of software process so it does not demand that domain data be expressed in the terminology of that model.
Hence, it can be quickly adapted to a new domain (just change the library of training instances)
and easy to maintain (just add more instances).\newline
CONCLUSION: We recommend instance-based methods like {\W}2 for learning changes to a software project.
\end{abstract}
% Note that keywords are not normally used for peer review papers.
\begin{IEEEkeywords}
Search-based software engineering, analogy, COCOMO
\end{IEEEkeywords}}


% make the title area
\maketitle
\noindent {\em To attain knowledge, add things every day.\newline
To attain wisdom, remove things every day.\newline
                        -- Lao-tse}
\section{Introduction}
There are many  {\em technologies} that a manager
might apply  to {\em change}, and hopefully {\em improve},  their software development project.
Some technologies are {\em paper-based} methods like
the checklists proposed by orthogonal defect classification~\cite{chill92}.
Other technologies are
{\em tool-based} such as  using the new generation of functional
programming languages or execution and testing
tools~\cite{andrews07} or automated formal analysis~\cite{holzmann97}.
 Yet other
technologies are more {\em process-based} including  process improvement
initiatives, changing an organization's hiring practices, or a continual
renegotiation of the requirements as part of an agile software
development cycle~\cite{port08}.

The set of possible changes to a project is very long. 
Endres \& Rombach~\cite{endres03} list  a hundred {\em laws} of
software engineering (each law predicts a certain observation) that could be used to justify a particular change
to a project. 
Table 2 of the IEEE-1012 standard for
software V\&V offers a ``minimal list'' of 52 tasks~\cite{1012}. If a manager proposed applying {\em all}
the laws and {\em all} the V\&V tasks, then their senior management would most probably ask them to
scale back their plans to just a minimal set of most cost-effective measures.  

How to find the minimal set of useful changes to a project?
It is ill-advised  to just apply standard truisms
since
general principles may not work best for particular projects:
\bi
\item
In~\cite{me02f}, we found one project 
where allocating extra resources  to defect removal early in the life cycle (as recommended by Boehm~\cite{boehm76})
was {\em less effective} than quickly
deploying an initial working system,  then fixing the bugs identified by users of that system. 
\item
Elsewhere~\cite{me09a},
we list numerous examples were applying general principles to a project were less valuable than 
applying specific
changes selected for particular projects.
\ei
If locally derived changes are better than general truisms, then the research question becomes 
{\em what techniques
can
find useful changes for a particular project}.
In this paper, we distinguish two approaches {\em model-based} and {\em instance-based} methods.
Model-based methods build a model via expert advice~\cite{fenton07}  or 
some automatic method like data mining~\cite{witten05}.
Once the model is built, it can be used for ``what-if'' queries in order to assess possible changes to a project. 
\begin{equation}\small
\begin{array}{rcl}
data&\rightarrow& model\\
model + whatIf& \rightarrow& predictions
\end{array}
\end{equation}
Instance-based methods insert the ``what-if'' query into a n-dimensional space populated with 
historical cases~\cite{norvig03,She02,leake96,kol93,leake05}.
The  immediate neighborhood of the ``what-if''  
is surveyed and the prediction  is some summary of those neighboring  cases. 
\begin{equation}\label{eq:inst}\small
\begin{array}{rcl}
data + whatIf& \rightarrow& neighborhood\\
neighborhood& \rightarrow& predictions
\end{array}
\end{equation}
Note that, unlike model-based methods, 
this instance-based approach makes no use of an underlying model.


Previously we have studied model-based 
methods~\cite{me00f,me07g,me07f,orrego09,me09a,me09e,me09f,me09i,me10f}.
AI tools
were used to control  thousands of  ``what-if'' queries over
COCOMO models to find
recommendations that reduced defects and/or months and/or effort.

Initially, the goal was a 
generic tool which could easily accommodate different
AI tools and different models. This proved surprisingly difficult.
Our model-based methods have become so
intricate that 
subsequent modifications required elaborate background knowledge and prolonged programming.

When tools become complex, it is wise to ask if the complexity is {\em essential}
or {\em superfluous}.
Researchers into empirical methods such as Cohen~\cite{cohen95}
advise
benchmarking
supposedly more sophisticated method against a
simpler alternative. Such  ``straw-man baseline'' studies can yeild surprising results.
For example, Holte reports that for  standard data sets used in
the machine learning literature,
one-level decision trees work nearly as well as multiple-level decision trees~\cite{holte93}.
Similar results are reported by Domingos \& Pazzani for so-called Naive Bayes classifiers.
Such
classifiers ignore correlations between variables. Yet, surprisingly, they often perform as well 
as more complex learners (see Table~1 of~\cite{domingos97optimality}).

Accordingly, we conducted a straw-man baseline study of our AI model-based methods 
against a very simple instance-based approach called {\W}. 
Given a ``what-if'' query that selects for some set of similar projects,
{\W} seeks a $treatment$ $R_x$ which finds the ``better'' parts of those
similar projects:
\begin{equation}\label{eq:w}\small
\begin{array}{rcl}
data +  whatIf& \rightarrow& neighborhood_1\\
neighborhood_1& \rightarrow& predictions_1\\
~\\
R_x(neighborhood_1) & \rightarrow  & neighborhood_2\\
neighborhood_2& \rightarrow& predictions_2\\
value(predictions_2)& >& value(predictions_1)  
\end{array}
\end{equation}
Here $value$ represents  business concerns; e.g. reduce defects.

{\W} finds the treatment $R_x$ via a linear-time greedy search over 
ranges sorted by simple Bayesian ranking.
The expectation was that {\W} would be {\em too} simple and would
perform poorly.
However, when compared to model-based
methods:
\bi
\item
{\W} found {\em similar} or {\em better} treatments.
\item
{\W} {\em was faster  to run:} all the experiments of this paper take 10 minutes with {\W}2, but days
for using models.
\item
{\W} {\em was  simpler to implement:} {\W}2's  200 lines AWK replaces thousands of lines of 
the model-based LISP.
\item
{\W} {\em was simpler to maintain:} with instance-based methods, ``maintenance'' means just  ``add more instances''.
\item 
{\W} {\em was simpler to adapt to new domains:}
{\W} makes no use of an underlying model and is therefore imposes no restrictions
on the data being processed.  Hence it can be quickly applied to more data sets. 
\ei
This last point is most important.
Model-based tools only accept data that conforms to the ontology of the model
(i.e. use the input values of the model).
If local data does not conform to that  ontology, then the tool cannot be applied.
Also,
the conclusions of a model-based analysis are 
only as
good as the underlying model. Models are learned from historical data and if that data is not
relevant to some new project, then that model
will be inappropriate for the new project.
For example, Jorgensen \& Shepperd caution that
the data used to derive COCOMO may not apply to all corporations~\cite{jorgensen05}.
Since {\W} does not use models, it avoids both these problems.

The contribution of this work is three-fold.
Firstly, we demonstrate the practicality of learning changes to software
projects that select for higher quality measures:
\bi
\item
In six case studies, we show that it is possible to find changes to
projects
that reduce the development effort;
\item
In two other case studies that it is possible to find 
changes to projects that reduce development effort {\em and} delivered defects
{\em and} the development time.
\ei
Secondly, we show that a very simple instance-based method does this better than more
complex model-based methods.

Thirdly, this work offers
the software engineering community a cautionary tale. Decades
of research has offered us any number of ways to analyze project data. 
For example, consider the list of candidate methods that might be applied
to the problem of learning changes to software projects. 
From the
data mining~\cite{lessmann09}, AI~\cite{norvig03,Gu97,me09g}, 
constraint-satisfaction~\cite{uribe94}, and search-based SE literature~\cite{harman07} we see
that that list includes
simulated annealing; evolutionary algorithms;
tabu search; ant-based search; various data mining tools such as
support vector machines or random forests;
various Davis-Putnam procedures;
logic based-approaches such as binary-decision diagrams; 
numeric methods such as integer programming; or any number of AI search algorithms.
This list is hardly exhaustive (no doubt, the reader can add their own favorite analysis method).
\begin{figure}
\centering
{\scriptsize  
\begin{tabular}{l|rrl|l}  
 ~ &  & & &\textbf{Quality }\\
 \textbf{Dataset} & \textbf{Cols} & \textbf{Rows} & \textbf{Notes}&\textbf{Measures }\\\hline
Kemerer	& 7 & 15 & Large business applications	& effort \\ 
Telecom	& 3 & 18 & U.K. telecom enhancements	& effort\\ 
Finnish	& 8 & 38 & Finnish IS projects		& effort \\
Miyazaki& 8 & 48 & Japanese COBOL projects	& effort\\ 
NASA93	&26 & 93 & NASA projects 		& effort, time, defects \\
COC81	&26 & 63 & NASA projects 		& effort, time, defects\\
China	&17 &499 & Chinese software projects	& effort \\\cline{3-3}
          \multicolumn{2}{c}{~}  & Total: 774\\
\end{tabular}}
\caption{Seven data sets from \protect\url{promisedata.org/?cat=14}: {\em effort} is total staff months; {\em  time} is calendar time (start to stop);
{\em defects} is number of delivered defects.
}\label{fig:data}
\end{figure}

Given such a large and growing menagerie of candidate tools, the temptation is to always explore 
novel and more intricate tools. Certainly, some domains are inherently complex
and should be analyzed with complex tools.
For example, {\em next release planning} is a complex planning problem
requiring intricate optimization methods~\cite{zhang07a,ruhe09}.  

On the other hand, most of the data
sets explored by (say) the effort estimation literature are not
complex:
\bi
\item  The effort estimation datasets used in Mendes et
al.~\cite{Mendes2003}, Auer et al.~\cite{Auer2006}, Baker~\cite{baker07},
and Li et al.~\cite{Li2009} have a median number of rows 13,15,33,52
(respectively).  
\item
\fig{data} shows the  data explored in this study.
While one of our data sets (China) is moderately larger, most of them contain
just a few dozen rows or less.
\ei
For such small search spaces,
complex tools may be an overkill. 
To avoid superfluous complexity,
 researchers should apply Cohen's test;
i.e.
benchmark their supposedly
better tool against a simpler tool.
%this work extends prior results as follows:
%	optimization -> gives us stabilization
%	more extensive certification
%	explanation (slightly better story)
%{\scriptsize
%\begin{center}
%\begin{tabular}{rrr|r}
%\multicolumn{3}{c|}{Columns}&Qualities\\\hline
%id&changes&files& effort (months)\\\hline
%1&218&105&305.22\\
%2&357&237&330.29\\
%3&136&98&333.96\\
%4&25&24&150.4\\
%5&263&197&544.61\\
%6&39&39&117.87\\
%7&377&284&1115.54\\
%8&48&37&158.56\\
%9&118&53&573.71\\
%10&178&116&276.95\\
%11&59&38&97.45\\
%12&200&180&374.34\\
%13&53&43&168.12\\
%14&143&84&358.37\\
%15&257&257&123.1\\
%16&6&6&23.54\\
%17&5&5&34.25\\
%18&3&3&31.8
%\end{tabular}
%\end{center}
%}
%\caption{Telecom: 18 rows, 3 columns, 1 dependent quality measure (development effort). }
%\label{fig:telecom}
%\end{figure}
For learning changes to software projects,
{\W} is a candidate tool for such a comparison since:
\bi
\item
It is simple to implement and fast
to execute; 
\item
The algorithm scales well (runs in linear time);
\item
For the data studied here, it performs  as least as good (or better) than a range of model-based
methods.
\ei
%This paper is structured as follows.
%XXX  Direct Application - When a software project veers away from perceived estimates, drastic changes may be needed to get it back on track. We compare the impact of several drastic management decisions, such as reducing functionality to cut development effort, to alternative decisions learned with {\W}2.
%

%We conclude that, for the task of find best project changes optimization, 
%{\W}2 represents a significant improvement over {\W}. Also, {\W}'s instance-based approach
%Figure ~\ref{fig:bestoverlap-vs-knn}). We also recommend {\W}2's case-based reasoning over SEESAW's parametric modeling (Figure ~\ref{fig:w2-seesaw-comparison}). For instances of drastic software changes, {\W}2 offers alternatives that can be equally effective in improving software quality (Figures~\ref{fig:drastic-ground},~\ref{fig:drastic-flight},~\ref{fig:drastic-osp},~\ref{fig:drastic-osp2}). Also, across multiple datasets, {\W}2's contrast-set learning demonstrates improvements in software quality regardless of the underlying data description (Figure~\ref{fig:other-reduce-values}).
%While we offer no conclusion on the general merits of case-based reasoning compared &to parametric modeling, we offer that {\W}2, contrast-set learning, and case-based reasoning are important tools for software quality optimization.

The rest of this paper presents our model-based vs instance-based comparison.
First, our model-based results~\cite{me00f,me07g,me07f,orrego09,me09a,me09e,me09f,me09i,me10f}
are reviewed. That work resulted in SEESAW, our ``best'' AI tool for conducting ``what-if''
model-based queries for software process models.
Next, we describe {\W}2, an instance-based method that improves on
prior versions of {\W}~\cite{brady10a,brady10b}.
This is followed a comparison of  model- vs instance-based  methods for learning
software project changes.

\section{Model-based Methods}\label{sect:models}


%Before beginning, we motivate the need for tool support to recommend project changes.
%Such tools are needed due to the {\em non-linear} nature of the problem as well as {\em model instability}.
%
%\subsection{Non-linearity}
%Before some change is imposed on a project,
%it is prudent to reflect on both the {\em benefits} and {\em undesirable impacts} of that change.
%\fig{dchange} shows some changes a manager could make- along with
%their
%possible
%under-desirable impacts.
%Note that 
%some changes may achieve one goal, while hurting other desired outcomes.
%
%The rest of this paper discusses methods that tries to achieve the triple
%goal of reducing:
%\bi
%\item {\em defects}: number of delivered defects;
%\item {\em months}: calendar time to delivery;
%\item {\em  effort}: staff time, in person months, required for delivery.
%\ei
%This is a {\em non-linear} problem since  favoring one goal can  harm the others. For example,
%if management rushes projects to completion, they decrease {\em months} but can increase {\em defects}.
%Also, projects that adopt elaborate quality assurance procedures can reduce {\em defects} but 
%at the cost of increased {\em effort}.
%\begin{figure}[!h]
%\begin{center}
%\footnotesize
%\begin{tabular}{|c@{~}p{.4\linewidth}p{.43\linewidth}|}\hline
%&{\bf Drastic change} & {\bf Possible undesirable impact}\\\hline
%1&Improve personnel & Firing and re-hiring personnel leading to wide-spread union unrest.\\\hline
%2&Improve tools, techniques, or  
%development platform & Changing operating systems, IDEs, coding languages is time-consuming and challenging to staff.\\\hline
%3&Relax schedule  & Arriving  too late to market.\\\hline
%4&Improve process maturity & Requires many local changes. \\\hline
%5&Reduce 
%functionality & Delivering less than expected.\\\hline
%6&Reduce quality 
%& User unrest, smaller market.\\\hline
%\end{tabular}
%\end{center}
%\caption{Managers can change  a project in many ways.
%This figure, taken from~\cite{boehm99}, shows a small sample of those possible changes.
%}\label{fig:dchange}
%\end{figure}

The task of optimizing for a set of goals is traditionally solved by
computing
partial differential equations of a model, then exploring the surface of steepest change. A premise of this
approach is {\em tuning stability}; i.e. that the gradients at any point in the model can be determined
with certainty.
For some models, this premise does not hold.
Consider the following simplified COCOMO~\cite{boehm00b} model: 
\begin{equation}\footnotesize\label{eq:simp}
effort = a \cdot LOC^{b +  pmat}\cdot acap  
\end{equation}
While simplified, the equation presents COCOMO's core assumption 
that software development effort is exponential on program size.
In this equation,  $(a,b)$ control the linear and exponential
effects (respectively) on model estimates; 
while
$pmat$ (process maturity) and $acap$ (analyst capability) are project choices
adjusted by managers. 
\eq{simp} contains two features ($acap,pmat$) and a full COCOMO model contains many
more project descriptors (e.g. see \fig{coc1}).

Baker~\cite{baker07} learned values of $(a,b)$ for a full COCOMO model
using Boehm's local calibration method~\cite{boehm81}
from 300 random samples of 90\% of the available project data. 
As shown in \fig{ab},  the ranges varied widely and wildly:
\[
\left( 3.2 \le a \le 9.4 \right) \wedge \left(0.8 \le b \le 1.12\right)
\]
Such large variations confuse standard gradient descent methods as well
as obscuring the
 effects of project changes.
Suppose some proposed technology  doubles productivity, but $a$ moves from 9 to 4.5.
The improvement resulting from that change would be obscured by the tuning instability.

However, such uncertainty is not unique to model-based techniques like COCOMO, but to software engineering in general. While we like to think that programs built from simple, reliable machine instructions can be rigorously managed and defined, but the decades following the 1968 NATO conference tell otherwise. Projects grow into the thousands of developers across nations, modules depend on a growing number of external libraries, and software depends on a global communications network spanning the globe. We may dream of a day where such uncertainties are tightly bounded to the point of inconsequence. Until that day we should at least be mindful of these uncertainties.

%
%
%Consider, for example, Boehm's COCOMO parametric model (the 1981 version~\cite{boehm81}):
%\begin{equation}\label{eq:one}
%\small Effort = a \cdot Loc^b * \prod_i\beta_iEM_i
%\end{equation}
%where $EM_i$ are one of the {\em effort multipliers} shown in \fig{coc1} (at top) and $\beta_i$ 
%are
%coefficients  of $EM_i$. 
%The goal of data mining over parametric models like \eq{one}
%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 reported that such precision is
%optimistic since the $\beta_i$ values are highly unstable. 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\footnote{\url{http://promisedata.org/?p=35}}. 
%Prior to learning, training data was {\em linearized}
%in the manner recommended by Boehm ($x$ was changed to $log(x)$,  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 un-linearized.
%
%Note that, in \fig{coc1}, that 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}. 
%In theory, one way to reduce model instability is to reduce the size of the model.
%A standard heuristic in
%regression analysis is that 5 to 10 examples are required for
%every variable in the model~\cite{kleijnen97}. Boehm's COCOMO 81 effort estimation model has
%15 variables. This heuristic explains the instability of
%\fig{coc1}:  according to this rule, 
%75  to 150 examples are needed for COCOMO 81 effort modeling yet all the plots of \fig{coc1} were
%generated using $0.66*93=61$ examples.
%To handle this problem, Boehm proposes freezing all the {$\beta_i$}
%values of \eq{one} and just tune $(a,b)$. 
%The above heuristic results says that this {\em local calibration} methods~\cite{boehm91}
%will only require 10 to 20 examples; i.e. much less than the 75 to 150 examples needed
%for the larger COCOMO model.
%
%In practice, local calibration does not solve the instability problem for COCOMO models.
%Baker~\cite{baker07} reports a study that learned  $(a,b)$ using local calibration
%from 30 randomly selected samples of 90\% of NASA93; i.e. $0.9*93=83$ examples per sample.
%The resulting $\beta_i$ ranges were very large (to say the least):
%\begin{equation}\small
%\left( 2.2 \le a \le 9.18 \right) \wedge \left(0.88 \le b \le 1.09\right)
%\end{equation} 
%Such large variations make it possible to misunderstand the effects of project options.
%Suppose some proposed technology  doubles productivity, but $a$ moves from 9 to 4.5.
%The improvement resulting from that change would be obscured by the model instability.
%
%\subsection{Model-Based Management of Instability}

So, if tuning instability cannot be removed, it must instead be managed. Our model-based
methods assume that model
predictions 
are altered by project variables $P$ and tuning
variables $T$: \begin{equation}\label{eq:pred}\small prediction
= model(P, T) \end{equation}
E.g.  in local calibration,   the tuning
options $T$ are the ranges of $(a,b)$ while  the project options  $P$
are the $EM_i$ values.  

At any local site, 
only part of the tunings is relevant: we denote
these as $t \subseteq T$. This subset can be found in many ways
including
linear regression
or local calibration. However, if there is insufficient data for
stable tunings, then 
$T$ may as well be left unconstrained,  so $t\subseteq  T$ can be selected randomly.

While model-based methods may triumph infinite reuse after their generation, the backwards-facing nature of this generation must be considered. It is certainly a strength to be able to apply a model to any new project, but one must consider the relevance of a new project to the historical environment which built the model. Consider that two original COCOMO effort multipliers quantified CPU and memory usage in terms of a single mainframe. A project involving distributed computing would be irrelevant to classify in terms of an early time-sharing mainframe.

Managers explore a specific context (the particulars of their project)
$context \subseteq P$ and
$control$ some items of $context$ ($control \subseteq context$).
Since it is  too expensive 
to use all $control$ settings, we seek 
minimal treatments $R_x \subseteq control$; i.e.
no smaller treatment has the same (or better) effect as $R_x$.

Models assess different treatments by running 
them on the model and
returning
the one
that maximizes a model's $value$:
\begin{equation}\footnotesize \label{eq:argmax}
\overbrace{R_x \subseteq control}^{\mbox{AI search}}, 
median_n\left(\underbrace{t \subseteq T, value(model(R_x,t))}_{\mbox{random selection}}\right) 
\end{equation}
Here, $median_n$ reports the median seen in $n$ repeats
of the random selection
and {\em value} is a domain-specific function 
For example, $value$
could be computed from the difference of the  model estimates to zero (effort, defects,
development time):
\begin{equation}\small\label{eq:edt}
value = 1- \left(\sqrt{Effort^2 + Defects^2 + Time^2} / \sqrt{3} \right) 
\end{equation}
If the estimates are normalized to the range $0\ldots1$, then \mbox{$0 \le value \le 1$} and {\em higher} values
are {\em better}.

\begin{figure}[!t]
\center
{\scriptsize
\begin{tabular}{l|r@{:~}l|}\cline{2-3}
upper:      & acap & analyst capability\\
in theory   & apex & applications experience\\
$\beta < 0$ & ltex & language and tool-set experience\\
            & pcap & programmer capability\\
            & pcon & personnel continuity\\
            & plex & platform experience\\
            & site & multi-side development\\
            & tool & use of software tools\\\cline{1-3}
middle      & sced & dictated development scedule\\\cline{1-3}
lower:      & cplx & product complexity\\
in theory   & data & database size\\
$\beta > 0$ & docu & documentation\\
            & pvol & platform volatility\\
            & rely & required reliability\\
            & ruse & required reuse\\
            & stor & required \% of available RAM\\
            & time & required \% of available CPU\\\cline{2-3}
\end{tabular}}
\caption{COCOMO II effort multipliers. 
}\label{fig:coc1}
\end{figure}
\begin{figure}
\begin{center}
\includegraphics[width=2.2in]{figs/nasa93_300.pdf}
\end{center}
\caption{Learned $(a,b)$ values via local calibration on 300*90\% samples
of the NASA93 COCOMO data set.}\label{fig:ab}
\end{figure}

\subsection{Tuning Variance in COCOMO}\label{sect:vars}

\eq{argmax} requires that
we sample over the space of model tunings.
This section describes one mechanism for sampling across the space of the
tunings within Boehm's
COCOMO effort estimator and the COQUALMO defect estimator.
Perhaps the essential point of this section is that,
for instance-based methods, {\em none} of this machinery 
is required.

For COCOMO effort multipliers (the features that that affect effort/cost in a linear manner), the
off-nominal ranges \{vl=1, l=2, h=4, vh=5, xh=6\} 
change the prediction by some ratio.
The nominal range \{n=3\} corresponds to an effort multiplier of 1 (i.e. 
no change).
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.
The exponential influences on
cost/effort 
take the 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.

COQUALMO contains equations of the same syntactic form as \eq{lineem}  and \eq{linesf}, but with different
coefficients.
Using experience for 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{argmax}),
all we need to do is select $m$ values at random from the min/max $m$ values
ever seen.

In the following, $m_\alpha,m_\beta$ are COCOMO's linear,exponential
influences on effort and cost, and 
$m_\gamma,m_\delta$ are COQUALMO's linear,exponential influences on 
defects.


There are two sets of  effort/cost multipliers.
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.
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.
The $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}
There are two sets of defect multipliers and scale factors.
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.
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.

COQUALMO divides describes how defects change in requirements, design,
and coding with tuning options:
\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.

\input{figs/projects.tex}

\subsection{Case Studies}\label{sect:data}

\fig{cases} shows some real-world $context$ and $control$ information taken
from a  debrief of some NASA program managers:
\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 un$control$able  column in that figure shows project features 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 changes to that project. For instance,
the reliability of the JPL flight software can vary from a ranking
of 3 (nominal) to 5 (very high). 



\subsection{Six AI Model-Based Algorithms}
The case studies of \fig{cases} can be used to assess how well different AI
algorithms can find changes to software projects.
For example,
a typical simulated annealing~\cite{kirkpatrick83} (SA) run
explores 10,000 variants on some solution.
A side-effect of that run is 10,000 sets of inputs, each scored with the $value$
function of \eq{edt}. Our tool classified the outputs into the  90\% 
{\em rest} and the 10\% {\em best} seen during the run of the SA. All the
ranges from all the features
were then ranked 
according to how much more frequently they
appeared in {\em best} than {\em rest}. A {\em forward select} was then
called using the first  $1{\ldots}x$ ranked items.
For example, in \fig{run}, the treatment $R_x$ at any $x$ value is
the conjunction of ranges seen
one to $x$
(see the table at the bottom of that figure).
The $y$ axis scores shows median results 
in 100 runs
of  COCOMO/COQUALMO, after imposing the treatment.
The ``pruned'' range of that figure shows the results of a  {\em back select}  that
 worked backwards over the forward select ordering, deleting any 
item $x$ whose distribution of values was statistically insignificantly different to
$x-1$. 
SA's final recommendation was the treatment $1 \le x \le 13$. The $improvement$ generated by
that treatment 
can be seen
by comparing the values at $x=0$ to $x=13$.
\bi
\item Defects reduced:  350 to 75; 
\item Time reduced:  16 to 10 months;
\item Effort reduced:  170 to 80 staff months.
\ei
\begin{figure}[!t]
\footnotesize
\begin{center}
\includegraphics[width=2.5in]{figs/single-seesaw-tpts100-all-trio-2-1.pdf}

~\\

\begin{tabular}{|p{.3\linewidth}|p{.4\linewidth}|}
\multicolumn{2}{l}{Decisions made from round=1 to round=13: }\\\hline
x=0: $R_x = \emptyset$\newline
x=1 added \{pmat=3\}\newline
x=2: added  \{resl=4\} \newline
x=3: added   \{team=5\}\newline
x=4: added \{aexp=4\} \newline
x=5: added  \{docu=3\}\newline
x=6: added  \{plex=4\}
&
x=7: added \{rely=3\} \newline
x=8: added  \{stor = 3\}\newline 
x=9: added \{time = 3\}\newline
x=10: added  \{tool = 4\}\newline
x=11: added \{sced = 2\}\newline
x=12: added \{site = 4\}\newline
x=13: added  \{acap = 5\}
\\\hline
\end{tabular}
\end{center}
\caption{Example of SA's forward and back select.}
\label{fig:run}
\end{figure}
SA is just one way to generate a treatment. For our AI model-based methods, we explored five others.
Given a random selected treatment,   
{\em MaxWalkSat} tries $n$ modifications to randomly 
selected features~\cite{selman96}.
Sometimes   (controlled by the $\alpha$ parameter), 
the algorithm chooses the range
that minimizes the value of the current solution.
Other times (at probability
$1-\alpha$), a random range is chosen for the feature.
After $N$ retries, the best solution is returned.
Our implementation used $n=50$, $\alpha=0.5$, and $N=10$.

{\em SEESAW}~\cite{me09f} augments MaxWalkSat
with a search heuristic taken from simplex optimization.
SEESAW ignores all ranges except the minimum
and maximum values for a feature in $p$.   
Like MaxWalkSat, the feature chosen on each iteration
is made randomly.  However, SEESAW has the ability to delay bad decisions until the end of the algorithm
(i.e., decisions where constraining the feature to {\em either} the minimum or maximum value results in a worse solution).
Hence, SEESAW's search was followed by the same back-select process using for SA.

{\em ISAMP} is a fast stochastic iterative sampling method that extends a treatment using
randomly selected ranges.
The algorithm follows one solution, then resets to try other paths (our implementation resets 20 times).
The algorithm has proved remarkably effective 
at scheduling problems,
perhaps because it can rapidly 
explore more of the search space~\cite{craw94}.
To avoid exploring low-value regions, our version of ISAMP stores
the worst solution seen so far. Any conjunction whose $value$ exceeds that
of the worst solution is abandoned, and the new ``worst value'' is stored. If
a conjunction runs out of new ranges to add, then the ``worst value''
is slightly decreased.
This ensures that consecutive failing searches do not permanently raise the
``worst value'' by an overly permissive amount.


Our remaining algorithms use some variant of tree search. 
Each branch of the tree is a different ``what-if'' query
of size $i$.  If $i$ is less than the number of input values to COCOMO/COQUALMO, the missing values
were selected at random from the legal ranges of those inputs.


{\em BEAM search} extends search branches as follows.
Each branch forks once for every new option available to that
range.
All the new leaves are sorted by their value
and only the top $N$ ranked branches are marked for further expansion.
For this study we used $N=10$ and results scored using the
median $values$ seen in the top $N$ branches. 
 
{\em A-STAR} runs like BEAM, but the 
sort order is determined by the sum $f$ (the cost of reaching the current
solution) plus $g$ (a heuristic estimate of the cost to reach the final
solution).  
Also, unlike BEAM, the list of options is not truncated 
so
a termination criterion is needed (we stop the search if the
best solution so far has not improved after $m$ iterations).
For this study, we estimated $f$ and $g$ as follows:
\bi
\item $f$
 was estimated as the percentage of the
project descriptors with ranges in the current branch;
\item $g$ was estimated using
 $1-\eq{edt}$ (i.e. distance to the utopia of
no effort, no development time, and no defects).
\ei
Initially, we planned  to explore more methods than SA, MaxWalkSat, SEESAW, ISAMP, BEAM
and A-STAR.
However, the success of {\W}'s instance-based approach decreased our motivation
to explore other AI model-based methods.


\subsection{Comparisons of AI Model-based Methods}
The above AI algorithms implemented the ``AI search'' of \eq{argmax}
to
explore the tuning variance of the models 
in \tion{vars}
(Boehm's COCOMO effort end time estimator
and his COQUALMO defect predictor).  
In four case studies, $context$ was set to the case studies of \fig{data}.

Each algorithm was run 20 times and was guided by the 
$value$ function of \eq{edt}.
Separate statistics were
collected for the defects/effort/time predictions seen at the policy point in the 20*4 trials.
The {\em top-ranked} algorithm(s) of \fig{xper}
had statistically  different
and lower defects/effort/time predictions than any other algorithm(s). 

Note the dramatic difference between MaxWalkSat and SEESAW results. The difference between these two
algorithms is very small:  SEESAW assumed that the local search
state space was monotonic, so it only explored minimum and maximum
values for each feature. This result underscores the power of the simplex heuristic.



\begin{figure}
\begin{center}
{\footnotesize\begin{tabular}{r|rrr}
algorithm &  Defects &months &time\\\hline
SEESAW    &4  &          4 &     3\\ 
BEAM      & 0 &         3 &     3\\
A-star    &  0&           1&     1\\
SA        &  0&            1&    1\\
MaxWalkSat & 0 & 0& 0\\
ISAMP   & 0  & 0& 0
\end{tabular}}
\end{center}
\caption{Number of times algorithm were top-ranked
(largest
is 4: i.e. one for each \fig{cases} case study). }\label{fig:xper}
\end{figure}

From \fig{xper},
the 
worst algorithms are MaxWalkSat and ISAMP and the 
best algorithms are SEESAW and BEAM.
The performance of these best algorithms is sometimes equivalent
(e.g., in $time$, both algorithms achieved an equal number of top ranks). 
However, BEAM is  not recommended:
\bi
\item BEAM runs 10 times slower than SEESAW.
\item
SEESAW
performs better than BEAM in some cases (e.g. in  defects, BEAM is never top-ranked).
\ei
Since SEESAW performs best, we will use it for our subsequent comparisons with instance-based methods.

%Nevertheless,
%%Another advantage of \eq{argmax} is that it makes no commitment
%%to the tool  used to find the best ``what-if''.
%%We have explored~\cite{me07f,me09i} 
%% various tree search algorithms (Astar, Beam search, ISSAMP),
%%constraint satisfaction algorithms (MaxWalkSat, SEESAW), as well as simulated annealing
%%Other candidate methods include various Davis-Putnam procedures;
%%binary-decision diagrams; integer programming;
%%genetic programming; tabu search; or the hundreds of other AI tools
%%described in the literature (for surveys, see~\cite{Gu97,uribe94,harman07,me09g,norvig03}).
%%
%%While \eq{argmax} was successful in some
%%domains~\cite{me00f,me07g,me07f,orrego09,me09a,me09e,me09f,me09i,me10f} we
%we no longer recommend this approach since it 
%assumes that (a) constraining the project variance is enough to tame all the 
%tuning variance.
%This, in turn, assumes that
%(b) the influence of the project options {\em dominates} the influences of the tuning options.  
%Previously~\cite{me09e}, we have shown that assumptions (a,b) hold for
%for COCOMO models. However, they may not hold for other models.
%Also, as shown later in this paper, simpler
%instance-based methods achieve the same task (finding useful project
%changes) without needing these assumptions or, indeed, any underlying model at all.
%
\begin{figure*}
{\scriptsize
\begin{minipage}{.38\linewidth}
\fig{eg}.a: RELEVANT= cases nearest to $context_1$.
\end{minipage}~\begin{minipage}{.33\linewidth}
\fig{eg}.b:  $Best$ (top) \&
$rest$ (bottom).
\end{minipage}~\begin{minipage}{.29\linewidth}
\fig{eg}.c:  Rank  with \eq{ps}.
\end{minipage}
}
{\scriptsize
\begin{minipage}[t]{.38\linewidth}
\input{figs/train-filter.tex}
\end{minipage}~\begin{minipage}[t]{.33\linewidth}
\input{figs/train-contrast.tex}
\end{minipage}~\begin{minipage}{.29\linewidth}
\input{figs/train-bestrest.tex}
\end{minipage}
}
\caption{Processing $context_1$ on a training set selected from NASA93.
}\label{fig:eg} \end{figure*}


\section{Instance-based Methods}
This section described three version of the {\W} instance-based tool. Lessons learned from
{\W}0~\cite{brady10a} and {\W}1~\cite{brady10b} will 
inform the description of the current version,  {\W}2.

Like all instance-based methods, {\W}
assumes access to historical $cases$ described using $P$ project descriptors 
(e.g. 
analyst capability;  process maturity; etc).
Note that, unlike the
model-based approach, {\W} does {\em not} assume that all cases are described using the same
set of $P$ descriptors. Rather, $P$ can be varied.
For example, \fig{data} lists the data sets used in our analysis.
If {\W} was restricted to just the COCOMO ontology, then 
it could only analyze two of those seven data sets: NASA93 and COCOMO81.
{\W}'s applicability to a wide range of data sets is an important advantage over
the AI model-based methods described above.

{\W}'s next assumption is that each case is described by a set of qualities such as number of defects,
development time, total staff effort etc. All these qualities are summarized into a single value by
some $value$ function like \eq{edt}.

Like our model-based methods, {\W} assumes that a manager can offer us:
a description of the  $context\subseteq P$ that interests them
and a list of $control$able options which they can change ($control \subseteq context$).
For example, once we asked a NASA software project manager for a description of
the effects
assigning inexperienced people. The manager commented
that, at her site,
such inexperience implies low applications experience ($aexp$), low to very low platform
experience ($plex$), and language and tool experience ($ltex$) that is not high. 
Next, we asked the manager to describe the range of projects seen
at his site  (using the
COCOMO names of \fig{coc1}).
The resulting $context_1$ is shown below:
\[\small
\begin{array}{r@{~}c@{~}l}
\multicolumn{3}{l}{context_1 =}\\ 
\mbox{~~~~~~}&  & apex \in \left\{ 2 \right\}\wedge 
 plex\in \left\{  1,2\right\} \wedge
     ltex\in \left\{1,2,3 \right\} \wedge \\
& & ?pmat\in \left\{2,3   \right\} \wedge
    ?rely\in \left\{3,4,5 \right\} \wedge
 ?data\in \left\{  2,3\right\}\wedge\\
& & ?cplx\in \left\{  4,5\right\}\wedge
 ?time\in \left\{  4,5\right\}\wedge
 ?stor\in \left\{  3,4,5\right\}\wedge\\
& & ?pvol\in \left\{  2,3,4\right\}\wedge
 ?acap\in \left\{  3,4,5\right\}\wedge
 ?pcap \in \left\{ 3,4,5\right\}\wedge\\
& & ?tool \in \left\{ 3,4\right\}\wedge
 ?sced \in \left\{ 2,3 \right\}
\end{array}
\]
Here,  ``?'' are the $control$lables; for example,
this manager is senior enough adjust factors like
schedule pressure ($sced$).

Note that there is no requirement for managers to include all project descriptors in their
$context$ statement. As seen below, {\W} can handle contexts that are a  subset
of the descriptors.

{\W}  finds a project treatment $R_x$ by 
studying the project similar to the context in the case library.
Formally, {\W} explores the $neighorhood$ of the $context$, looking for ways to
select for the ``best'' cases. 
 (as determined by a $value$ functions like \eq{edt}).
In {\W}2, this is a six step procedure:
\be
\item 
Divide cases randomly into $train:test$ in the ratio 2:1.
\item
Used $context$ to find
the neighborhood within $train$.
\item
Divide neighborhood into (a)~the $best$ cases that should be emulated, and (b) the remaining
cases you should avoid (which we call $rest$).
\item
Rank all differences between  (a) and (b) according to how strongly they select for the $best$ 
cases.
\item
Using the $train$ set again, 
experiment with treatments $R_x$ built from the  top ranked items 
found in $Step4$.
Return the treatment that 
selects for the cases in the $train$ set with highest median $value$.
\item 
Repeat five steps
 $n=20$ times with other  randomly selected
$train:test$ sets. Prune $unstable$ treatments; i.e.
those not found in the majority of repeats.
\ee
{\W}0 and {\W}1 neglected to test for treatment stability; hence, $Step6$ was added.
$Step6$ is also useful to resolve another testing-related
problem.
Other learners such as  RIPPER~\cite{cohen95r}
divide the case data three ways into $train:prune:test$. In that approach,
$Step4$ would run on $train$;  $Step5$ would run on $prune$, and the final result
would be tested on a separate $test$ set.
{\W}0 tried that approach but ran into problems with very small data sets such as
the 15 rows of KEMERER or the 18 rows of TELECOM.  
{\W}2 uses the above two-way split, and uses $Step6$
to avoid recommending treatments that  are over-fitted to parts of the training data.
 

Another issue encountered with $Step2$ (finding the neighborhood)
was that the
$context$ cannot be treated as a rigid criteria.
In our experiments with {\W}0, we found that some data sets
were so small that, often, $none$ of the cases contained $all$ the ranges mentioned in the $context$.
For example,
\fig{eg}.a shows training data from NASA93. The gray cells in that figure show ranges that do not
appear in $context_1$. Note that all rows have at least one gray cell. That is, $none$ of that
data exactly matches $context_1$.
Consequently, {\W}1 used some partial match operator to compute the neighborhood.
Members of the training set were sorted according to their Euclidean distance from the $context$.
If  a $context$ only mentions a subset of the project descriptors $P$, then {\W}1's distance function
filled in $\{P - context\}$ with random values (selected from the known ranges). This was repeated
50 times to generate 50 context queries that reference all project descriptors. Next, the neighborhood
was computed using the intersection of the 20 instances closest to any of those 50 queries.


This technique solved the problem of missing parts of the $context$.
However, it created other another problem: a large variance in all the results.
Hence, {\W}2 used another method:
$context$ became a set overlap membership function.
For example, $context_1$ statement defines ranges for 14 project descriptors.
Any training case contain ranges that overlaps with between 0 and 14 of the ranges
in $context_1$. As shown in 
\fig{eg}.a, we can use the size of this overlap to sort the cases. Appealing to the central
limit theorem, {\W}2 defines the neighborhood of a query to be the $K_1=20$ training cases with largest
overlap to the query. If a $train$ set was smaller than 20 cases, all
its rows were repeatedly copied until $|rows > 20|$.


{\W}2's set overlap operator is only defined for finite ranges.
Hence,   {\W}2 adds a $Step0$: discretization of all project descriptors (but not quality
attributes) into $B$ bins. All the following experiments assume that all numbers $y$
are discretized using $round((y-min)/((max-min)/B))$, where $B=5$.
Other values for $B$ are discussed in the future work section.

$Step3$ (division into $best$ and $rest$) is
illustrated in \fig{eg}.b. 
The neighborhood is sorted by case $value$;  the top $K_2$ cases 
are $best$; and the  remaining
$K_1 - K_2$ examples are $rest$.  
While the ranking algorithm of $Step4$  works best for larger $K_2$ values,
we did not want 
to exceed accepted standards in the research
community.
After a review of the analogy-based estimation
literature~\cite{Li2009,Lipowezky1998,Walkerden1999,Kirsopp2002,Mendes2003} we noted that
 no researcher
proposed using more than five neighbors. Hence, we used
the $K_2=5$ cases with highest $value$ (in this example, $value$ means lower development effort).

$Step4$ (rank the ranges in $best$) is shown in \fig{eg}.c.
{\W}0 used the following simple Bayesian ranking method.
Observer that nominal tool ($tool=3)$ occurs 5 times in $best$
and 14  times in $rest$. Given that information,
we can rank $tool=3$ according to its ability to  select $best$ cases:

{\small
\begin{eqnarray}\nonumber
E&=& (tool=3)\\\nonumber
freq(E|best)&=&5\\\nonumber
freq(E|rest)&=&14\\\nonumber
ratio(E|best)&=&5/5 = 1\\\nonumber
ratio(E|rest)&=&10/15 = 0.93\\\nonumber
rank(E)&=& \frac{ratio(E|best)}{ratio(E|best) + ratio(E|rest)}=0.52
\end{eqnarray}}
{\W}0 encountered problems with evidence that was infrequent, but relatively more frequent in $best$ than $rest$.
To avoid this problem,  {\W}1 and {\W}2 adds a 
support term.
Support should $increase$ as the frequency of a range $increases$,  i.e. 
$ratio(E|best)$ is a valid support measure.
Hence, {\W}2's range ranking formulae is:
\begin{equation}\label{eq:ps}\small
rank(E) * support(E) = \frac{ratio(E|best)^2}{ratio(E|best) + ratio(E|rest)}
\end{equation}
We can generate candidate treatments $R_x$ by combining the top
$x$ items in the rankings of \fig{eg}.c:
\[\small
\begin{array}{rcl}
R_1 & : & pmat=3\\
R_2 & : &  pmat=3 \wedge sced=3\\
R_3 & : &  pmat=3 \wedge sced=3 \wedge tool=3\\
R_4 & : & pmat=3 \wedge sced=3 \wedge tool=3 \wedge acap=3\\
etc
\end{array}
\] 
$Step5$ (pruning the treatments) applies $R_x$ to the projects similar to the $context$;
i.e. those found in the test set's neighborhood.
For example, \fig{testing}  shows the $K_1=20$ cases closest to $context_1$ in the
train set. 

\input{figs/test-constrain.tex}

\fig{testing-constrained} shows 
the cases from this neighborhood 
that satisfy $R_1 : pmat=3$. It turns out, that for cases relevant to $context_1$
in this test set, there is some association between the ranges see in $R_1, R_2$ and $R_3$:
all these treatments select the same rows. Only when $R_4$ is 
applied does \fig{testing-constrained} shrink to the two rows containing $acap=3$. {\W}1's
results exhibited large variances if we drew conclusions from less than three rows. Hence,
{\W}2's explores $R_x$ upwards from $x=1$ while:
\bi
\item The number of selected rows $|R_x \wedge neighborhood| \ge 3$;
\item
The median $value$ of the rows selected by $R_{x+1}$ is  greater than that of $R_x$.
\ei
In the case of \fig{testing-constrained}, $Step5$ returns $R_1$ ($pmat=3$). 
\subsection{Measuring Performance}
To compare the effectiveness of different treatments,
we offer the following performance measures:
\bi
\item All our measures are taken from the test set.
\item The $baseline$ values are from the neighborhood
of the $context$; e.g. the $effort$ column of \fig{testing}. 
\item
The $treated$ values are from the cases selected
by a treatment; e.g. the $effort$ column of \fig{testing-constrained}.
\item
The $median$ of a distribution is the 50-th percentile of the sorted values in that distribution.
\item
The $spread$ of a distribution is the (75-25)th percentile of the sorted values. We use spread
rather than, say, standard deviation to avoid any parametric assumptions that our distributions
are (say) Gaussian.
\item
The $improvement$ from $b=baseline$ to \mbox{$t=treated$}  is 
$100*(b - t)/t$.
$Larger$ improvements are better.
\ei
For example, consider how $pmat=3$ effects projects similar to $context_1$:
\bi
\item Without the $pmat=3$ restriction, the median and spread of the projects similar
to $context_1$ are 235 and 633 months, respectively (see \fig{testing}).
\item After imposing the $pmat=3$ restriction,
the median and spread of  projects similar to $context_1$ are 81 and 353 months (see \fig{testing-constrained}).
\item The observed improvement in the median  is hence 66\%.
\item The observed improvement in the spread is hence 44\%.
\ei
\subsection{Complexity}



Summarizing  the above, {\W}2 studies $c$
cases which describe projects using to $p=|P|$ project
descriptors.
Much of the processing
is focused on the $K_1$ nearest neighbors to the $context$. 
{\W}2 repeats its process $n$ times (to check for stability of the
learned treatment). Prior to the repeats,
any numeric descriptors
are discretized into $B$ bins.

{\W}2 runs in six steps.
$Step0$'s discretization needs two passes of $c$ cases (one to find mins and maxs,
one to convert numerics into $B$ bins). Hence,
$Step0$ takes times $2c$.

$Step1$ also takes time $2c$ to  generate randomized train and test sets:
one pass to
randomize the order of the cases, and 
another to split into train and test.
Assuming
the use of Fisher-Yates shuffle~\cite{durstenfeld64}\footnote{
for $i$ = $n-1$  to 1:
       $j$=random in $0\le j \le i$;
       swap $item_j$ with  $item_i$
}, 
randomization takes time linear on $c$.

$Step2$ and $Step5$ requires a third  pass of the train/test set to  collect the $K_1$ neighbors.
These passes do not need to sort all cases- just those in a ``best-of'' buffer of size $K_1$.
After the $Step1$ randomization,
quicksort can sort the neighborhood in  time, on average,
$2K_1log(K_1)$ (one for train, one for test). 

$Step3$ divides the neighborhood into $best$ and $rest$- a process that takes time $K_1$.
Then  $Step4$ takes time equal to:
\bi
\item the number of ranges to be sorted; i.e.  the number of project descriptors times the
number of ranges per descriptor ($pB$);
\item
plus
the log-linear time required to sort those ranges.
\item which equals
time $pB + pB \cdot log(pB)$.
\ei
$Step5$ requires one pass thought the $K_1$ members of the train data for each candidate treatment.
Given $pB$ ranges, the maximum number of pass is $pBK_1$.

Finally, $Step6$ repeats the above steps  $n$ times to check for stability,
That is,
{\W}2 takes total time:
{\[
\begin{array}{rll}
2c + & & \mbox{; $Step0$}\\
n * ( & & \mbox{; $Step6$'s repeats}\\
              & 2c + & \mbox{; $Step1$}\\
              & 2K_1log(K_1) + & \mbox{; $Step2$}\\
              & K_1 +  & \mbox{; $Step3$} \\
              & pB + pB\cdot log(pB)  + & \mbox{; $Step4$}\\
              & pBK_1 & \mbox{; $Step5$}\\
       )\\
\end{array}\]
}
This is not a slow process.
Nothing in this expression is worse that log-linear.
Also,
typical values for the $n,c,K_1,B,p$ constants are than $20,100,20,5,20$ (respectively); i.e. not overly large.
Even when implemented in a slow interpreted language  (GAWK), {\W}2 runs in less than half
a second for data sets up to 500 cases\footnote{On a 3MHz dual core Macintosh running OS/X 10.6 with 4GB of ram.}.
%\input{figs/w2-runtimes.tex}
%\subsection{Experiments with {\W}2}
%
%As a sanity check for {\W}2, this section
%compares {\W}2's
%recommendations against the kinds of changes a human manager might recommend. 
%
%\fig{boehm99} shows some standard management actions for software projects. The list
%is not intended to be exhaustive- rather, it is
%just a sample of possible actions.
%Each of these management actions can be viewed as one $context$ of \fig{drastic-overview}.
%We used these in four case studies, as follows. Each of these contexts was added to
%the cases studies of \fig{cases} and {\W}2 was called on the results using NASA93.
%
%Twelve results are shown in
%Figures ~\ref{fig:drastic-flight},~\ref{fig:drastic-ground},~\ref{fig:drastic-osp},~\ref{fig:drastic-osp2}. 
%\[\scriptsize
%\left(\begin{array}{c}
%NASA93\\
%\end{array}
%\right)
%* 
%\left(
%\begin{array}{c}
%defects\\
%effort\\months
%\end{array} 
%\right)
%* 
%\left(
%\begin{array}{c}
%ground\\
%flight\\
%OSP\\
%OSP2\end{array}
%\right)
%\]
%The variances in this experiment are large so 
%Of the 12 comparisons, in only one case does {\W}2 perform better statistically and significantly better than the three drastic changes. However, in terms of median reductions, {\W}always performs in the top 50\% of of cases. Most importantly, even when compared to extreme project recommendations, {\W} is not constrained by the limited project attribute ranges allowed for its recommendations.
%
%\[\scriptsize
%\left(\begin{array}{c}
%NASA93\\
%COCOMO81
%\end{array}
%\right)
%* 
%\left(
%\begin{array}{c}
%defects\\
%effort\\months
%\end{array} 
%\right)
%* 
%\left(
%\begin{array}{c}
%ground\\
%flight\\
%OSP\\
%OSP2\end{array}
%\right)
%\]
%
%\begin{figure}[!h]
%\begin{center}
%\footnotesize
%\begin{tabular}{|c@{~}p{.4\linewidth}p{.43\linewidth}|}\hline
%&{\bf Drastic change} & {\bf Possible undesirable impact}\\\hline
%1&Improve personnel & Firing and re-hiring personnel leading to wide-spread union unrest.\\\hline
%2&Improve tools, techniques, or  
%development platform & Changing operating systems, IDEs, coding languages is time-consuming and challenging to staff.\\\hline
%3&Relax schedule  & Arriving  too late to market.\\\hline
%4&Improve process maturity & Requires many local changes. \\\hline
%5&Reduce 
%functionality & Delivering less than expected.\\\hline
%6&Reduce quality 
%& User unrest, smaller market.\\\hline
%\end{tabular}
%\end{center}
%\caption{Managers can change  a project in many ways.
%This figure, taken from~\cite{boehm99}, shows a small sample of those possible changes.
%}\label{fig:dchange}
%\end{figure}
%
%
%\begin{figure}[!t]
%\begin{center}\footnotesize
%\begin{tabular}{c l l}
%  & \textbf{Drastic Change}   & \textbf{Attribute Effects}\\\hline
%1 & Improve Process Maturity  & pmat = 5\\\hline
%2 & Improve Tools\&Techniques & time = 3; stor = 3;\\
%  &                           & pvol = 2; tool = 5; site = 6\\\hline
%3 & Reduce Functionality      & data = 2;\\\hline
%\end{tabular}
%\end{center}
%\caption{Examples of drastic changes to software projects.}
%\label{fig:drastic-overview}
%\end{figure}
%
%\input{figs/drastic.tex}
%

\section{Model- vs Instance-Based Methods}
{\W}2 was tested against the SEESAW model-based method as follows.
SEESAW can only handle models in the COCOMO format. Hence,  for this comparison,
we restrict ourselves to data in that format.
{\W}2 used the historical cases from
the NASA93 and COCOMO81 datasets.
These  data sets all use the features defined by Boehm~\cite{boehm81}; e.g.
analyst capability, required software reliability, memory constraints, and use of software tools.
For this study, we translated them from
Boehm original COCOMO format into COCOMOII in order to 
add estimated defect and development length data for multiple goal optimizations.

Both SEESAW and {\W}2 guided their search  using \eq{edt} and the
four $context$s of \tion{data}.
SEESAW used those $context$s to guide their ``what-if'' queries
around its COCOMO/COQUALMO models.
{\W} used those $contexts$, with NASA93 and COCOMO81, using the six step procedure described above.
Recall that, in those steps, some $R_x$ was assessed on projects similar to the $context$
in a  $test$ set; i.e. all the cases in the $context$'s neighborhood.

Our comparison rig studied that same $test$ neighborhood using SEESAW.
We say that $rows_1$ are the rows selected from the neighborhood after applying
SEESAW's recommendations 
as an SQL select statement.
Also, $rows_2$
are the rows selected by {\W}2 from the neighborhood of the $context$ in the $test$
set using the stable treatment found in $Step6$.

SEESAW and {\W}2 were then assessed according
to which method returned the better set of $values$.
That is, from $rows_i$, we applied \eq{edt} to find $values_i$. 

The NASA93 results are shown in \fig{nasa93results},  divided into the defect, effort, months
reductions see in ground, flight, OSP2 and OSP. 
The median and spread improvements are shown in the middle
columns. The left-hand-side bar chart shows the 25-th to 75-th percentile range, with a black dot marking
the median point.  
A {\em negative} improvement
denotes an failure to find an improvement.
Note that such negative results occur only in a single
result (COCOMO81, OSP2, effort).


The ``Win'' column of those figures
indicates when any member of a pair that was both statistically and significantly different. Note that for most pairs, the results are not statistically significantly different (Mann-Whitney, 95\% confidence level).
The COCOMO81 comparisons are shown in \fig{cocomo81results}. These are in the same format as \fig{nasa93results}.
Sometimes SEESAW's recommendations were unusually bad for COCOMO81, and in those circumstances,
often selected nothing from the test neighborhood. This
can we seen with  \mbox{$median=0$} improvement results seen with
OSP (defects) and OSP2  (defect and effort).
 
\input{figs/w2-vs-seesaw.tex}

Before commenting on SEESAW vs {\W}2, we first note that our results should encourage more use
of automatic tools for finding changes to software projects.
Observe that, in the majority of cases, both model-based and instance-based
methods found ways to decrease {\em both} the median and spread of
effort/months/defects.
In all but one experiment the amount of
uncertainty in the median estimates was reduced. As shown in
\fig{changes}, the reduction in the spread was usually over 34\%.
This is an advantage of these tools since uncertainty is an
serious issue that plagues the managers of software engineering
projects. As shown in \fig{changes}, the expected median reduction
in any quality estimate was  only 34\%. 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  our tools  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.
\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}2 or SEESAW. The median observed
changes were (35, 43)\% for (medians, spreads), respectively. The -51\% COC81 OSP2 outlier has been omitted for clarity.
}\label{fig:changes}
\end{figure}


In all, we show 24 results:
\[\scriptsize
\left(\begin{array}{c}
NASA93\\
COCOMO81
\end{array}
\right)
* 
\left(
\begin{array}{c}
defects\\
effort\\months
\end{array} 
\right)
* 
\left(
\begin{array}{c}
ground\\
flight\\
OSP\\
OSP2\end{array}
\right)
\]
%\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 (34, 34)\% for (medians, spreads), respectively. The -94\% COC81 OSP2 outlier has been omitted for clarity.
%}\label{fig:changes}
%\end{figure}
We conducted statistical tests on each pair of {\W}2 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}2's case-based reasoning performs as well as $SEESAW's$ parametric modeling.

\input{figs/win-loss-tie.tex}

Also, where results differed, instance-based
methods can perform much better than model-based.
Observe the median reductions for NASA93 OSP:
{\W}2 offered median reductions of 72\%, 69\%, and 43\% compared to SEESAW's 22\%, 37\%, 13\% for defects, effort, and months respectively.

In summary, {\em a simple instance-based methods performs
as well, or better,
than our best model-based method}.


\section{Validity}


{\em Construct validity} (i.e. face validity) assures that we are measuring
what we actually intended to measure~\cite{Robson2002}.
Previous studies have concerned themselves with the construct validity of 
different performance measures for effort estimation (e.g. \cite{foss05}).
While, in theory, these performance measures have an impact on the rankings of effort
estimation algorithms, we have found that other factors dominate. In particular,
\fig{dot-plot} showed that features of the data set (whether or not it is ``weak'')
have a major impact on what could be concluded after studying a particular estimator
on a particular data set. We also show empirically the surprising result that our
results are stable across a range of performance criteria.


As to the external validity of our choice of algorithms,   recalling \fig{cbr},
it is clear that this study has not explored the full range of effort estimation algorithms.
Clearly, future work is required  to repeat this study using the ``best of breed'' found here (e.g. 
bands one and two of \fig{freq_method} as well as other algorithms).

Having cast doubts on our selection of algorithms, we hasten to add that
this paper  has focused on algorithms that have been 
extensively studied in the literature~\cite{shepperd97} as well as  the commonly available datasets (that is, the ones
available in the PROMISE repository of reusable SE data).
That is, we assert that these results should apply to much to current published literature
on effort estimation.

An unexpected cause for concern with {\W} was some instability in its recommendations. After removing the nearest neighbor filtering, the {\em overlap} method for case relevancy filtering helps reduce this affect, as seen in ~\fig{stability}. Across four different goals (reducing defects only, effort only, months only, or all at once) {\W}2 returns more stable improvements, whereas {\W} tends to shift it's recommendations when changing goals.

\begin{figure}[!h]
\begin{center}
{\scriptsize
\begin{tabular}{|r|@{\hspace{0.5mm}}c@{\hspace{0.5mm}} @{\hspace{0.5mm}}c@{\hspace{0.5mm}} @{\hspace{0.5mm}}c@{\hspace{0.5mm}} @{\hspace{0.5mm}}c@{\hspace{0.5mm}} @{\hspace{0.5mm}}c@{\hspace{0.5mm}} @{\hspace{0.5mm}}c@{\hspace{0.5mm}} @{\hspace{0.5mm}}c@{\hspace{0.5mm}} @{\hspace{0.5mm}}c@{\hspace{0.5mm}} @{\hspace{0.5mm}}c@{\hspace{0.5mm}} @{\hspace{0.5mm}}c@{\hspace{0.5mm}} @{\hspace{0.5mm}}c@{\hspace{0.5mm}} @{\hspace{0.5mm}}c@{\hspace{0.5mm}} @{\hspace{0.5mm}}c@{\hspace{0.5mm}} @{\hspace{0.5mm}}c@{\hspace{0.5mm}} @{\hspace{0.5mm}}c@{\hspace{0.5mm}} @{\hspace{0.5mm}}c@{\hspace{0.5mm}} @{\hspace{0.5mm}}c@{\hspace{0.5mm}} @{\hspace{0.5mm}}c@{\hspace{0.5mm}}|c|}\hline
\multicolumn{20}{|c|}{Stability Comparision for NASA93 FLIGHT}\\\hline
\emph{\begin{sideways}goal\end{sideways}}&
\emph{\begin{sideways}acap=3\end{sideways}}&
\emph{\begin{sideways}apex=3\end{sideways}}&
\emph{\begin{sideways}apex=5\end{sideways}}&
\emph{\begin{sideways}cplx=4\end{sideways}}&
\emph{\begin{sideways}data=2\end{sideways}}&
\emph{\begin{sideways}data=3\end{sideways}}&
\emph{\begin{sideways}ltex=3\end{sideways}}&
\emph{\begin{sideways}ltex=4\end{sideways}}&
\emph{\begin{sideways}plex=3\end{sideways}}&
\emph{\begin{sideways}pmat=2\end{sideways}}&
\emph{\begin{sideways}pmat=3\end{sideways}}&
\emph{\begin{sideways}pmat=4\end{sideways}}&
\emph{\begin{sideways}rely=4\end{sideways}}&
\emph{\begin{sideways}rely=4\end{sideways}}&
\emph{\begin{sideways}sced=2\end{sideways}}&
\emph{\begin{sideways}sced=3\end{sideways}}&
\emph{\begin{sideways}stor=3\end{sideways}}&
\emph{\begin{sideways}time=3\end{sideways}}&
\emph{\begin{sideways}changes\end{sideways}}\\\hline
defects&  &  &  &  &  &  &  &  &  &  & 90 &  &  &  &  &  & 65 & 75 & 3\\
effort &  &  &  &  &  &  &  &  &  &  & 70 &  &  &  &  &  &  & 90 & 2\\
months &  &  &  &  &  &  &  &  &  &  & 70 &  &  &  &  &  & 60 & 85 & 3\\
all &  &  &  &  &  &  &  &  &  &  & 75 &  &  &  &  &  & 70 & 85 & 3\\\hline
\multicolumn{20}{|c|}{Stability Comparision for NASA93 GROUND}\\\hline
\emph{\begin{sideways}goal\end{sideways}}&
\emph{\begin{sideways}acap=3\end{sideways}}&
\emph{\begin{sideways}apex=3\end{sideways}}&
\emph{\begin{sideways}apex=5\end{sideways}}&
\emph{\begin{sideways}cplx=4\end{sideways}}&
\emph{\begin{sideways}data=2\end{sideways}}&
\emph{\begin{sideways}data=3\end{sideways}}&
\emph{\begin{sideways}ltex=3\end{sideways}}&
\emph{\begin{sideways}ltex=4\end{sideways}}&
\emph{\begin{sideways}plex=3\end{sideways}}&
\emph{\begin{sideways}pmat=2\end{sideways}}&
\emph{\begin{sideways}pmat=3\end{sideways}}&
\emph{\begin{sideways}pmat=4\end{sideways}}&
\emph{\begin{sideways}rely=4\end{sideways}}&
\emph{\begin{sideways}rely=4\end{sideways}}&
\emph{\begin{sideways}sced=2\end{sideways}}&
\emph{\begin{sideways}sced=3\end{sideways}}&
\emph{\begin{sideways}stor=3\end{sideways}}&
\emph{\begin{sideways}time=3\end{sideways}}&
\emph{\begin{sideways}changes\end{sideways}}\\\hline
defects &  &  &  &  &  &  &  &  &  &  & 80 &  &  &  &  &  & 50 &  & 2\\
effort &  &  &  &  &  &  &  &  &  &  & 60 &  &  &  &  &  &  & 75 & 2\\
months &  &  &  &  &  &  &  &  &  &  & 75 &  & 50 &  &  &  &  & 75 & 3\\
all &  &  &  &  &  &  &  &  &  &  & 85 &  &  &  &  &  &  & 80 & 2\\\hline
\multicolumn{20}{|c|}{Stability Comparision for NASA93 OSP}\\\hline
\emph{\begin{sideways}goal\end{sideways}}&
\emph{\begin{sideways}acap=3\end{sideways}}&
\emph{\begin{sideways}apex=3\end{sideways}}&
\emph{\begin{sideways}apex=5\end{sideways}}&
\emph{\begin{sideways}cplx=4\end{sideways}}&
\emph{\begin{sideways}data=2\end{sideways}}&
\emph{\begin{sideways}data=3\end{sideways}}&
\emph{\begin{sideways}ltex=3\end{sideways}}&
\emph{\begin{sideways}ltex=4\end{sideways}}&
\emph{\begin{sideways}plex=3\end{sideways}}&
\emph{\begin{sideways}pmat=2\end{sideways}}&
\emph{\begin{sideways}pmat=3\end{sideways}}&
\emph{\begin{sideways}pmat=4\end{sideways}}&
\emph{\begin{sideways}rely=4\end{sideways}}&
\emph{\begin{sideways}rely=4\end{sideways}}&
\emph{\begin{sideways}sced=2\end{sideways}}&
\emph{\begin{sideways}sced=3\end{sideways}}&
\emph{\begin{sideways}stor=3\end{sideways}}&
\emph{\begin{sideways}time=3\end{sideways}}&
\emph{\begin{sideways}changes\end{sideways}}\\\hline
defects & 95 &  & 70 &  &  &  &  &  &  &  &  &  &  &  & 50 &  &  &  & 3\\
effort & 80 & 70 &  &  &  &  &  &  &  &  &  &  &  &  & 70 &  &  &  & 3\\
months &  &  &  &  &  &  &  &  &  &  &  & 55 &  &  & 80 &  &  &  & 2\\
all & 50 &  &  &  &  &  &  &  &  &  &  &  &  &  & 85 &  & 60 &  & 3\\\hline
\multicolumn{20}{|c|}{Stability Comparision for NASA93 OSP2}\\\hline
\emph{\begin{sideways}goal\end{sideways}}&
\emph{\begin{sideways}acap=3\end{sideways}}&
\emph{\begin{sideways}apex=3\end{sideways}}&
\emph{\begin{sideways}apex=5\end{sideways}}&
\emph{\begin{sideways}cplx=4\end{sideways}}&
\emph{\begin{sideways}data=2\end{sideways}}&
\emph{\begin{sideways}data=3\end{sideways}}&
\emph{\begin{sideways}ltex=3\end{sideways}}&
\emph{\begin{sideways}ltex=4\end{sideways}}&
\emph{\begin{sideways}plex=3\end{sideways}}&
\emph{\begin{sideways}pmat=2\end{sideways}}&
\emph{\begin{sideways}pmat=3\end{sideways}}&
\emph{\begin{sideways}pmat=4\end{sideways}}&
\emph{\begin{sideways}rely=4\end{sideways}}&
\emph{\begin{sideways}rely=4\end{sideways}}&
\emph{\begin{sideways}sced=2\end{sideways}}&
\emph{\begin{sideways}sced=3\end{sideways}}&
\emph{\begin{sideways}stor=3\end{sideways}}&
\emph{\begin{sideways}time=3\end{sideways}}&
\emph{\begin{sideways}changes\end{sideways}}\\\hline
defects &  &  &  &  &  &  &  & 60 &  &  &  & 75 &  &  & 95 &  &  &  & 3\\
effort &  &  &  &  &  &  &  & 75 &  &  &  & 55 &  &  & 80 &  &  &  & 3\\
months &  &  &  &  &  &  &  & 70 &  &  &  & 80 &  &  & 90 &  &  &  & 3\\
all &  &  &  &  &  &  &  & 80 &  &  &  & 90 &  &  & 100 &  &  &  & 3\\\hline
\end{tabular}}
\end{center}
\caption{Recommendation frequency across 20 runs of {\W} and {\W}2 for reducing individual goals (defects, effort, months) as well as all goals at once (d/e/m). Recommendations that appeared less than half the time are omitted. Note that despite chaning goal functions, {\W}2 continues to make similar recommendations.}
\label{fig:stability}
\end{figure}



The above comparison was restricted to data sets with the COCOMO ontology. This section
shows that {\W}2 can be applied to much wider range of data sets than the model-based methods.

As shown in \fig{data}, we have access to data in a variety of formats:
\bi
\item
Enhancements to a U.K. telecommunications product.
\item
Projects collected by Miyazaki et al~\cite{miyazaki94} originally comparing ``robust regression`` to the least squares criteria.
\item
Finnish Information Systems projects collected by the TIEKE organization.
\item
A large dataset of Chinese software projects.
\item
Large COBOL projects, collected by Kemerer~\cite{kemerer87}.
\ei
The data sets use a variety of features such as  number of entities in the data model, number of basic logical transactions, query count and number of distinct business units serviced.

Given that we did not have access to specific case studies 
like \fig{cases},
synthetic queries were developed. Three queries were generated for each of the five datasets. The first contained the entire range of possible project project descriptors, representing complete freedom to recommend any change within the space. The other two queries were generated by randomly choosing 50\% of each attribute values from either the lower, middle, or upper ranges for each project descriptor. 

The only quality measures available for this data was development effort. Hence, the following results
are expressed only in terms of effort.

Effort reductions can be seen in Figure~\ref{fig:other-reduce}:
\bi
\item Overall, we say a median 56\% and 73\% improvement in median and spread, respectively
(see the dotted line of \fig{other-reduce}.
\item
Large improvement in median effort 
were seen for the TELECOM, KEMERER, and MIYAZAKI datasets, with strong median reductions (\textgreater 50\%)
and good spread reductions (\textgreater 25\%) across all datasets. 
\item
The FINNISH and CHINA datasets show good improvements to both median and spread reductions, with some projects demonstrating exceptional reductions in spread (\textgreater 75\%).
\ei
\begin{figure}[!t]
\center
\includegraphics[width=4.0in]{figs/noncocomo-reduce.pdf}
\caption{Distribution of median and spread reductions in software effort for five non-COCOMO datasets.
}\label{fig:other-reduce}
\end{figure}

Note that it would be impossible to apply our model-based methods to these data sets, since they are not expressed
in terms of the COCOMO ontology. That is, at least in our experience,
{\em instance-based methods can be applied to more data sets that effort-based methods}.

%\begin{figure}[!t]
%\begin{center}
%\begin{tabular}{|c|c|r|r|}\cline{3-4}
% \multicolumn{2}{c}{~}& \multicolumn{2}{|c|}{Improvement}\\\hline
%dataset&query $q$&median&spread\\\hline
%Telecom  & Proj1 & 96\% & 23\%\\
%Telecom  & Proj2 & 91\% & 41\%\\
%Telecom  & All   & 86\% & 28\%\\
%Miyazaki & All   & 78\% & 33\%\\
%Miyazaki & Proj2 & 69\% & 21\%\\
%Miyazaki & Proj1 & 53\% & 67\%\\
%Finnish  & All   & 22\% & 31\%\\
%Finnish  & Proj2 & 11\% & 27\%\\
%Finnish  & Proj1 & 4\% & 25\%\\
%China    &  All  & 20\% & 55\%\\
%China    & Proj2 & 14\% & 43\%\\
%China    & Proj1 & \cellcolor[rgb]{0.8,0.8,0.8}0\% & 13\%\\
%Kemerer  & Proj1 & 21\% & 61\%\\
%Kemerer  & Proj2 & \cellcolor[rgb]{0.8,0.8,0.8}0\% & 49\%\\
%Kemerer  & All   & \cellcolor[rgb]{0.8,0.8,0.8}-4\% & 53\%
%\\\hline
%\multicolumn{2}{r|}{median} & 21\% & 33\% \\\cline{3-4}
%\end{tabular}
%\end{center}
%\caption{Effort estimation improvements ($100*\frac{initial-final}{intial}$)
%for five unique datasets. Sorted by median improvement. Gray cells represent no improvement in effort estimates.}
%\label{fig:other-reduce-values}
%\end{figure}
\section{Related Work}

This paper extends prior publications on {\W}2 as follows.

Instance-based analysis of software estimation is a widely explored area~\cite{shepperd97,Mendes2003,Kirsopp2002,Walkerden1999}. We show here that a simple addition to standard instance-based analysis
can not just estimates, but also recommendations on how to {\em change} those estimated.
This is an important extension since,
in our experience,
if a manager is presented with an estimate, their very next question is ``what can I do to change this?''.
Hence, while the effort estimation literature describes many estimation methods, both model-based
and instance-based
~\cite{Li2009,Lipowezky1998,Walkerden1999,Kirsopp2002,Mendes2003,jorgensen05,shepperd07,shepperd97},
we focus more on how to {\em change} those estimates.

With the model-based methods, our challenge was to handle the uncertainty associated with 
the tuning instability discussed in \tion{models}.
Previously, we  have tried reducing that instability in various ways:
\bi
\item
Feature selection to prune spurious details~\cite{chen05}; 
\item
Instance selection to prune irrelevancies~\cite{me06d}; 
\item Extended data collection.
\ei
Despite all that work, the variance observed in our models remains very large.
Even 
the application of techniques such as instance-based learning have failed to reduce variance in our effort predictions~\cite{jalali07}.
Feature subset selection has also been disappointing: while it reduces
the median performance variance somewhat (in our experiments, from
150\% to 53\%~\cite{me06d}), the residual error rates are large enough that it is hard
to use the predictions of these models as evidence for the value of some proposed approach.
Lastly, further data collection has not proven useful.
Certainly, there is an increase
in
the availability
of
historical data on prior projects\footnote{see 
\url{http://promisedata.org.data/data}
and \url{http://www.isbsg.org/}.
}. However, Kitchenham~\cite{kitch07} cautions that the literature
is contradictory regarding the value of using
data from other companies to learn
local models.

Having failed to tame tuning variance, despite years of research, we turned to alternate methods.
Much of the related work on uncertainty in software engineering uses a Bayesian analysis.
For example,
Pendharkar et al.~\cite{pendharkar05} demonstrate the utility of Bayes networks in effort
estimation while Fenton and Neil explore Bayes nets and defect prediction~\cite{fenton99}
(but unlike this paper,
neither of these teams links defect models to effort models).

Other related work is the search-based SE approach advocated by Harman~\cite{harman04}. 
Search-Based Software Engineering (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. 
Harman takes care to distinguish AI search-based methods from those seen in
standard numeric optimizations.
Such optimizers usually offer settings to all controllables.
This may
result in needlessly complex recommendations since a repeated empirical
observation is that many model inputs are noisy or correlated in similar ways 
to model outputs~\cite{hall03}. Such noisy or correlated variables can be pruned away to
generate simpler solutions that are easier and quicker to understand.
In continuous domains, there
is much work on feature selection~\cite{miller02} and
techniques like principal component analysis~\cite{Dil84} to reduce
the number of dimensions reported by an analysis.  Comparative
studies report that discrete AI-based methods can do better at
reducing the size of the reported theory~\cite{hall03}.

The SBSE approach can and 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 for our model-based methods~\cite{me07f}
(which we subsequently found worked worse than SEESAW or {\W}2). 

\section{Future work}

The two strengths of {\W} lie with its data agnosticism and speed. While the focus of this paper rests on software quality optimization and effort estimation, {\W} presents the potential to operate on arbitrary data at very fast speeds.

One extention to {\W} is user interactivity. Currently, we only accept a binary flagging of project attributes as either controllable or not. Once a ranked list of treatments is generated, we automatically prune this list to generate the best overall improvements. 

However, such a method assumes all treatments are of equal cost to implement. Instead, an expert may prefer to adopt only a subset of the original treatments, yet seek to measure the impact of this more limited approach. 
{\W}'s speed and flexibilty opens up the opportunity to interface directly with the user with meaningful feedback. For example, if a manager omits a treatment that involves firing all senior employees, they may be delighted to view an estimation still within acceptable ranges.

Another avenue for improvment rests removing the hard-coded sizes for the $best$ and $rest$ sets as well as the cutoff between them. Currently, regardless of dataset size, the top five cases are selected as paragons examples. Because all cases contain a utility measure, through analyzing the distribution of this measure it may be possible to maximize contrast and increase the information gained between the $best$ and $rest$ sets.

Exploring software project {\em process} data may not be as complex as exploring
software project {\em product} data.
For example,
two developers, working for one year on one project, 
can generate defect data on hundreds to thousands of software {\em products} (e.g. each module they have built).
However,
that same work might contribute  only one entry  to a software {\em process} data base (e.g. one row
describing their applications experience with this kind of software, the size of the final system,
and the number of staff months required to code it all).
For example:
\bi
\item
The effort estimation datasets used in
Mendes et al.~\cite{Mendes2003}, Auer et al.~\cite{Auer2006},
Baker~\cite{baker07},  and Li et al.~\cite{Li2009} have
median number of examples 13,15,33,52 (respectively).
\item
the experiments of this paper were conducted
on seven projects containing 
15,%Kemerer
18,%telecom
38,%Finnish
48,%miya
62,%coc81 
93,%nasa93
499 %china
examples (i.e. usually less than a few dozen examples per project). 
\ei
For complex software {\em product} data, it may be advisable to apply support vector machines,
random forests, or any of the other sophisticated analysis methods surveyed in, say,~\cite{lessmann09}.
However,
for software {\em process} data, it may be overkill to apply complex
tools
like the various Davis-Putnam procedures;
binary-decision diagrams; integer programming;
genetic programming; tabu search; or the hundreds of other tools
described in the AI literature~\cite{Gu97,uribe94,harman07,me09g,norvig03}
or the search-based software engineering literature~\cite{harman07}.

This is not to say that learning changes to software projects is {\em always} best achieved
using simple instance methods. For example, the next release planning problem
studied by Ruhe~\cite{ruhe09} (and others) is a process problem of great complexity.
Hence, the Pareto frontier optimization methods employed by Ruhe may be an appropriate technology for
that domain. 

%better optimization search
%\bi
%\item
%{\em Pareto domination}~\cite{li08} that rejects point $X$ if some other point $Y$ is
%(a)~not worse on any quality dimension and (b)~better on at least one.
%\item
%Or an {\em objective function} that combines the individual qualities into a single number;
%e.g. \eq{argmax}.
%\ei

%contrast set learning, not with this simple Bayesian trick

%shown we are better than other some, not better than all

\section{Conclusion}

We've demonstrated that our simple, fast {\W}2 algorithm performs as well or better than a selection of complex, model-based methods using COCOMO. We've also shown it possible that {\W}2 can be instantly applied to arbitrary datasets without requiring calibration ~\ref{fig:other-reduce}. {\W}2 exchanges generalities for fast, local recommendations. However, to do so requires a shift from typical model-based approaches. For, say, organizations without a historical case base, it is not possible to recommend {\W}2.

Nevertheless, other areas of research advise that
researchers should at least baseline their supposedly more sophisticated method against a
simpler alternative~\cite{cohen95,holte93}. Accordingly, 
we offer  {\W}2 as a baseline device for learning changes to
software projects since.

However, instance-based methods represent a way to better certify the relevance of a recommendation. Where models tend to be generated once and rarely updated, {\W}2 offers a way to instantly conform to new software engineering techniques: simply add more cases. Therefore, the crux of recommending {\W} lies on the task at hand. For reasoning about large, static systems with an existing, well-tuned model, the burden of model generation isn't as important. However, software estimation represents a rapidly moving target, and it is difficult to claim that a single model will continue to represent rapid shifts in development environments.

In the end it is all about the data. If you have it, use it. While models can be adapted, doing so may not be necessary. Instead, we have shown success in exchanging model-based generalities for instance-based local lessons. While we cast out grand, general statements on effects in software engineering, we must ask ourselves whether we even {\em need} them. Software estimations are like a hitting a moving target. Instead of trying to deduce its exact location, perhaps we should instead look at our previous shots and adjust accordingly.


\bibliographystyle{IEEEtran}      % basic style, author-year citations
\bibliography{refs,myrefs}   % name your BibTeX data base

\begin{biography}[{\includegraphics[width=1in,keepaspectratio]
{figs/timm}}]{Tim Menzies}
is a  associate professor
at the Lane Department of Computer Science at West Virginia University
(USA), and has been working with
NASA on software quality issues since 1998. He has a CS degree and a PhD
from the University of New South Wales and is the author of over 160 publications.
His recent research concerns modeling
and learning with a particular focus on light weight modeling methods.
\end{biography}

\begin{biography}[{\includegraphics[width=1in,keepaspectratio]
{figs/timm}}]{Adam Brady}
is a  associate professor
at the Lane Department of Computer Science at West Virginia University
(USA), and has been working with
NASA on software quality issues since 1998. He has a CS degree and a PhD
from the University of New South Wales and is the author of over 160 publications.
His recent research concerns modeling
and learning with a particular focus on light weight modeling methods.
\end{biography}

\begin{biography}[{\includegraphics[width=1in,keepaspectratio]
{figs/timm}}]{Jacky W. Keung}
is a  associate professor
at the Lane Department of Computer Science at West Virginia University
(USA), and has been working with
NASA on software quality issues since 1998. He has a CS degree and a PhD
from the University of New South Wales and is the author of over 160 publications.
His recent research concerns modeling
and learning with a particular focus on light weight modeling methods.
\end{biography}

\begin{biography}[{\includegraphics[width=1in,keepaspectratio]
{figs/timm}}]{Steve Williams}
is a  associate professor
at the Lane Department of Computer Science at West Virginia University
(USA), and has been working with
NASA on software quality issues since 1998. He has a CS degree and a PhD
from the University of New South Wales and is the author of over 160 publications.
His recent research concerns modeling
and learning with a particular focus on light weight modeling methods.
\end{biography}

\begin{biography}[{\includegraphics[width=1in,clip,keepaspectratio]
{figs/timm}}]{Steven Williams }
is an undergraduate student pursuing a BS in Computer Science at                                    
Portland State University.  He is currently working as an IT Manager and                                      
Database Administrator at a large non-profit organization in Portland,                                        
Oregon.        
\end{biography}


\begin{biography}[{\includegraphics[width=1in,keepaspectratio]
{figs/timm}}]{Oussama El-Rawas}
is a  associate professor
at the Lane Department of Computer Science at West Virginia University
(USA), and has been working with
NASA on software quality issues since 1998. He has a CS degree and a PhD
from the University of New South Wales and is the author of over 160 publications.
His recent research concerns modeling
and learning with a particular focus on light weight modeling methods.
\end{biography}



\begin{biography}[{\includegraphics[width=1in,clip,keepaspectratio]
{figs/timm}}]{ Phillip Green }
is a graduate student in the Computer Science Department at
Portland State University.  He received his BS in Physics and Astronomy from
the University of Pittsburgh in 2001.  He has over six years of research
experience in numeric methods and data mining.  His master thesis focuses on
comparative study of data mining techniques and equivalences with numeric
optimization techniques.  He also has interned at a software development firm
in Beaverton, Oregon. 
\end{biography}


\end{document}
\begin{IEEEbiography}{Adam Brady }
Biography text here.
\end{IEEEbiography}

% if you will not have a photo at all:
\begin{IEEEbiographynophoto}{Tim Menzies}
Biography text here.
\end{IEEEbiographynophoto}

\begin{IEEEbiographynophoto}{Jacky W. Keung}
Biography text here.
\end{IEEEbiographynophoto}




