\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}
\newcommand{\xx}{{\cellcolor[rgb]{0.8,0.8,0.8}}}


% *** 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, Jairus Hihn, Barry Boehm%
\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 Department of Computing, The Hong Kong Polytechnic University.
jacky.keung@comp.polyu.edu.hk.
\IEEEcompsocthanksitem Steven Williams
is with the 
School of Informatics and Computing
Indiana University, Bloomington.
E-mail:
stevencwilliams@gmail.com.
\IEEEcompsocthanksitem Jairus Hihn 
is with Caltech's Jet Propulsion Laboratory.
Email: jairus.hihn@jpl.nasa.gov.
\IEEEcompsocthanksitem Barry Boehm
is with the University of Southern California.
Email: boehm@sunset.usc.edu.}% <-this % stops a space
\thanks{ This research was conducted at West Virginia University,
University of Southern California, and NASA’s Jet Propulsion
Laboratory under a NASA sub-contract. Reference herein to any speciﬁc
commercial product, process, or service by trade name, trademark,
manufacturer, or otherwise, does not constitute or imply its
endorsement by the United States Government.}
\thanks{This research was 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
\section{Introduction}
There are many  ways a manager
might  {\em change}, and hopefully {\em improve},  their software development project.
Some changes  require
{\em tools} such as  using the new generation of functional
programming languages or execution and testing
tools~\cite{andrews07} or automated formal analysis~\cite{holzmann97}.
 Other
changes use {\em process improvement} techniques 
such as 
changing the organizational hiring practices, or a continual
renegotiation of the requirements as part of an agile software
development cycle~\cite{port08}.

Endres \& Rombach~\cite{endres03} list dozens of  {\em laws} of
software engineering which could justify a particular change
to a project. 
If a manager proposed using {\em all}
the laws, then senior management would most likely suggest they
scale back their plans to just a minimal set of most cost-effective measures.  

How to find the minimal set of most effective changes to a project?
In our previous work we attempted to address this question by combining
model-based 
methods
with
AI tools
to control  thousands of  ``What-If'' queries over
COCOMO models. In many domains, that proposed approach provides
recommendations that would reduce defects and/or months and/or development efforts~\cite{me00f,me07g,me07f,orrego09,me09a,me09e,me09f,me09i,me10f}.

%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}.
Empirical SE researchers such as Cohen~\cite{cohen95}
advise
benchmarking
supposedly sophisticated method against 
simpler alternatives.
Accordingly, we conducted a straw-man baseline study of our AI model-based methods 
against a very simple instance-based approach called {\W}2. 

For instance, given a ``What-If'' query that selects for some set of similar projects,
{\W}2 seeks a $treatment$ $R_x$, which finds the ``better'' parts of those
similar projects within the dataset:

{\small \[
\begin{array}{r@{~}rcl}
&data + WhatIf & \rightarrow& neighborhood_1\\
&neighborhood_1& \rightarrow& scores_1\\
~\\
R_x \;+&data + WhatIf & \rightarrow  & neighborhood_2\\
&neighborhood_2& \rightarrow& scores_2\\
&scores_2& >& scores_1  
\end{array}
\]}
in here $scores$ represents some business concerns; for example reduce defects before release the software product.

In the experiment, {\W}2 finds the treatment $R_x$ via a linear-time greedy search over 
ranges and then sorted by a simple Bayesian ranking algorithm.
The expectation was that {\W}2 would be {\em too} simple and would
perform poorly.
However, when compared to model-based
methods:
\bi
\item
{\W}2 found {\em similar} or {\em better} treatments.
\item
{\W}2 {\em was faster  to run:} all the experiments in this paper take 10 minutes with {\W}2, but days
for using models.
\item
{\W}2 {\em was  simpler to implement:} {\W}2's  200 lines AWK replaces thousands of lines of 
the model-based LISP.
\item
{\W}2 {\em was simpler to maintain:} with instance-based methods, ``maintenance'' implies ``adding more instances''.
\item 
{\W}2 {\em was simpler to adapt to new domains:}
{\W}2 makes no use of an underlying model and therefore it imposes no restrictions
on the data being processed.  Hence it can be quickly applied to more data sets. 
\ei
Retrospectively, we recommend the proposed instance-based method {\W}2 for finding changes to software projects.
%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 summarized contributions of this study are four-fold:
\be
\item
We demonstrate that  managers have many options for effectively changing and
improving their projects.
\item 
We enhance algorithms proposed by
other researchers.
Prior work on instance-based methods discussed ways to $generate$
estimates~\cite{shepperd97,Mendes2003,Kirsopp2002,Walkerden1999}. We show that a simple addition to standard instance-based analysis
lets us go one step further to determine how to $change$ an estimate. 
\item
We improve our prior results on instance-based methods. 
This paper reports {\W}2 which outperforms 
our model-based methods described in~\cite{me00f,me07g,me07f,orrego09,me09a,me09e,me09f,me09i,me10f}
as well as earlier versions of our
instance-based reasoner~\cite{brady10a,brady10b}.
As discussed in \tion{inst}, {\W}2
handles missing values better than {\W}1. Also, this paper is the first report
on extending any version of {\W} beyond standard COCOMO data.
\item
Results show simple instance-based methods can perform better than more
complex model-based methods.
\ee
While the first points  may be of most interest to
industrial practitioners, it is the last point  that may be most interesting to researchers.
There are many sophisticated methods for
exploring the complexities and uncertainties of 
trying to control
software engineering projects.
Based on the results of this paper,
we advise  researchers to first explore simpler method, at least for the purposes of establishing a performance baseline.




%\footnote{
%E.g. 
%Bayes nets;
%fuzzy logic;
%constraint-satisfaction
%simulated annealing; evolutionary algorithms;
%tabu search; ant-based search; various data mining tools such as
%support vector machines or random forests;
%numeric methods such as integer programming; 
%logic-based-approaches such as Davis-Putnam procedures or binary-decision diagrams; 
%or 
%any number of AI search algorithms~\cite{lessmann09,norvig03,Gu97,me09g,uribe94,harman07}.}. 


%Nevertheless, before researchers explore sophisticated methods, they should
%try a simpler
%method, at least for the purposes of establishing a performance baseline.

%Before beginning, it is important to offer the following clarification.
This paper shows that the {\W}2 instance-based method is superior to all the model-based methods explored in this study.
This does not imply that learning changes to software projects is {\em always} best achieved
using simple instance methods. For example, the next release planning problem~\cite{ruhe09,zhang07a}
is a process problem of great complexity.
For that task,
the Pareto frontier optimization methods employed by (e.g.) Ruhe~\cite{ruhe09}
is probably preferred to {\W}2.


%
%The rest of this paper justifies this recommendation.
%First, we discuss model and their application to learning changes to software projects.
%That work resulted in SEESAW, our ``best'' AI tool for conducting ``what-if''
%model-based queries.
%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.
%
%This paper extends prior work as follows. Much of our prior work on learning changes
%to software projects was based only on model-based methods 
%(see~\cite{me00f,me07g,me07f,orrego09,me09a,me09e,me09f,me09i,me10f})
%and is summarized
%in \tion{models}. 
%While earlier versions our system, called {\W}0 and {\W}1, 
%have been reported elsewhere~\cite{brady10a,brady10b},
%the sections \S2, \S4, \S5, \S6 of this paper
%have not appeared before and 
%include more details on the background to this work and the internal
%details of the code than~\cite{brady10a,brady10b}. 
%As described
%in 
%\tion{inst}, {\W}2 is a significant improvement on those earlier version.
%Also, while prior versions only studied two data sets in the COCOMO format,  here
%we add results from five more data sets in a non-COCOMO format.  Finally, the stability study
%of \tion{stable} and its connections to delta analysis in \tion{delta} is new work.
%
\section{Background}
\subsection{Definitions}
%The best changes to a particular project must be sensitive
%to the {\em context} of that project.
%It is ill-advised  to just apply standard truisms
%since
%general principles may not work best for particular projects.
%For example, 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.
%
%If locally derived changes are better than general truisms, then the research question must be 
%{\em how to 
%find useful changes for a particular project}.
Model-based methods develop a model via expert advice~\cite{fenton07}  or 
using automatic methods such as {\em data mining}~\cite{witten05}.
Once built, the model can be used for ``what-if'' queries in order to assess possible changes to a project, for example: 



%\begin{figure}[!b]
%\footnotesize
%\begin{tabular}{c@{~}p{.4\linewidth}p{.5\linewidth}}
%&{\bf 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\\\hline
%3&Improve precedentness / \newline development flexibility &
%Changing the goals
%of the project and the development method.\\\hline
%4&Increase architectural \newline analysis /  risk resolution &
%Far more elaborate early life cycle analysis.\\\hline
%5&Relax schedule  & Delivering the system later.\\\hline
%6&Improve process maturity & May be expensive in the short term.\\\hline
%7&Reduce 
%functionality & Delivering less than expected.\\\hline
%8&Improve the team & Requires effort on team building.\\\hline
%
%9&Reduce quality 
%& Less user approval, smaller market.
%\end{tabular}
%\caption{A small sample of  changes a manager might make to a project.  From~\cite{boehm99}.}\label{fig:dchange}
%\end{figure}
%

{\small \[
\begin{array}{rcl}
data&\rightarrow& model\\
model + whatIf& \rightarrow& scores
\end{array}
\]}
Instance-based methods insert the ``what-if'' query into a $n$-dimensional space populated with 
historical project cases~\cite{norvig03,She02,leake96,kol93,leake05}.
Unlike model-based methods, 
instance-based methods do not require an underlying model.
Rather, the  immediate neighborhood of the ``what-if''  
is somehow scored to find summary of those neighboring  cases: 

{\small \[
\begin{array}{rcl}
data + whatIf& \rightarrow& neighborhood\\
neighborhood& \rightarrow& scores
\end{array}
\]}
For the rest of this paper, we will say that a $whatIf$
query defines a $context$ within which a manager seeks
ways to improve their projects.
%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
%
\subsection{Software Estimation Research}
Instance-based software estimation such as {\em Case-Based Reasoning} (CBR) is a widely explored area in software engineering~\cite{shepperd97,Mendes2003,Kirsopp2002,Walkerden1999}. 
In our collective experience, when a manager sees an estimate, his/her immediate question is ``how can I change that?''.
While the effort estimation literature describes many estimation methods
(both model-based
and instance-based
~\cite{pendharkar05,Li2009,Lipowezky1998,Walkerden1999,Kirsopp2002,Mendes2003,jorgensen05,shepperd07,shepperd97})
in order to address manager's immediate concern,
we focus on how to {\em change} estimates.

%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.
{\W}2 explores multiple goals such as reducing development effort {\em and} defects {\em and} the total calendar
time to deliver the software. Instead, most other work in this area explores a single goal.
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}.
Unlike this paper,
neither of these teams links defect models to effort models. 
In addition, as mentioned above, those papers focus much
more on {\em prediction} that on the subsequent problem of learning how to {\em change} those
predictions.

\subsection{Search-Based Software Engineering}
Multi-goal optimization in search-based software engineering (SBSE) is well explored~\cite{harman04}.
SBSE 
employes optimization techniques
from
operations research and meta-heuristic search (for example in simulated annealing and genetic algorithms)
in an attempt to hunt for near-optimal
solutions.
Harman~\cite{harman04} distinguishes AI search-based methods from those seen in
standard numeric optimizations.
Such optimizers 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.
For continuous variables, there
is many work on feature selection~\cite{miller02} and
techniques like principal component analysis~\cite{Dil84} to reduce
the number of dimensions reported by a data analysis.  Some
studies report that discrete AI methods perform better at
reducing the size of the reported theory~\cite{hall03}.

The SBSE approach can and has been applied to many
domains in software engineering such as requirements engineering~\cite{jalali08},
 but most often in the field of software testing~\cite{andrews07}.
Harman's work provides the inspiration in this study in an attempt to experiment simulated annealing for our model-based methods~\cite{me07f}
(which we subsequently found performed worse than {\W}2). 



\subsection{Model: Benefits}
High-level abstract models represent and transmit common and useful patterns observed in
multiple specific situations~\cite{gof95}.
At a keynote
address at PROSIM'05 Walt Scacchi noted that merely writing a model
can clarify  local business processes~\cite{pfahl05}. 
Executable software process models can be used for many purposes
including but not limited to reducing the inspection effort 
at different stages of the software life cycle~\cite{me02f}.
Even if a model lacks a sophisticated execution engine, it can be used
for what-if queries that are insightful to different business processes
(e.g. see Boehm et al.'s what-if studies in Chapter Three of~\cite{boehm00b}). 

Models can combine and summarize {\em both} expert insights {\em and} local data. Fenton~\cite{fenton07}
builds
the general structure of his  Bayes nets via workshops of business
knowledge.  The details of these structures are then tuned via local
data. Elsewhere, Boehm reports the advantages of combining local data
with model structures initialized via expert knowledge~\cite{chulani99}.
 
Another subtle advantage of models is data sharing. Schulz reports that
organizations that are reluctant
to share specific data, may be willing to share models (if those models
do not reveal
details from particular business sites)~\cite{schulz10}.

Finally, models let us extrapolate from past examples to new examples. A trend that is sampled by
$N$ historical examples can be extended to offer predictions for new examples that have not been seen previously.


\subsection{Models: Drawbacks}\label{sect:draw}
Extrapolation, while sometimes useful, may over fit the data. If so, then a model may offer unsupported recommendations.
For example,
as shown in the results below, our model-based methods were ineffective since, sometimes,
they proposed conclusions that 
 applied to {\em none}
of the test data. 

Another drawback with model-based tools is that they 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.
For example, \fig{data} shows the data sets used in this study. Our model-based methods
can only process the two data sets that conform to the COCOMO ontology of \fig{coc1}. On the other hand,
the {\W}2 instance-based method can process all of them.

%For example, prior to {\W}, all our experiments on software development effort were based on the
%restrictive ontology of COCOMO an aspect noted by other researchers such as Shepperd~\cite{shepperd07}:
%\begin{quote}
%{\em A limiting factor of this work \cite{Menzies2006} is that it 
%requires data ... to conform to the COCOMO 
%data model. }
%\end{quote}
%Yet another drawback with model-based methods is that their conclusions are only 
%as good as the underlying model.
%Models can be validated via domain data but
%if the available data is not
%relevant to some new project, then the calibrated  model
%may 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}.
%
Models need to be learned from data and
collecting that data can be difficult 
due to the business sensitivity associated with the data as 
well as differences in how the metrics are determined, collected and 
archived. In many cases the required data is not archived at 
all. In our experience, for example, after two years we were only able to add 7 records 
to our NASA wide software cost metrics repository~\cite{me07f}. 
Alternatively, open-source code repositories are a rich source of {\em product} information,
but usually lack {\em process details}
such as the descriptions of the applications
experience of the developers.
%For example,
%the experiments of this paper were conducted
%on seven projects of \fig{data}, each with less
%than, on average, just a few dozen examples or less.
\begin{figure}[!t]
\centering
{\scriptsize  
\begin{tabular}{l|rrl|l}  
 \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\\ 
COC81ii	&26 & 63 & NASA projects 		& effort, time, defects\\
NASA93ii	&26 & 93 & 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}
Other researchers also have noted similar problems with collecting process data.
%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).
Lowry~\cite{lowry10} discusses the complexities involved in calibrating his
software failire models.
Those models require 
parameters that are clearly antiquated.
For example, he mentions a
commercial model-based cost estimation tool that requires a parameter 
that rates
``the time it takes for a software 
development environment to respond to a keyboard input''. When software was written on  
remote time-shared computers, this was an important factor. However,  today 
it is irrelevant  but it is kept in 
the model for backwards compatibility and because it was 
measured in the software projects on which the model was 
calibrated. 

Baker~\cite{baker07} discusses another serious concerns with model calibration: {\em tuning instability}.
Software construction is a very human-intensive process, therefore the data collected
from that process
is as varied as the humans building the code.
Consider the following simplified COCOMO~\cite{boehm00b} model: 
\begin{equation}\footnotesize\label{eq:simp}
effort = a \cdot LOC^{b +  pmat}\cdot acap  
\end{equation}
The equation presents COCOMO's core assumption 
that software development effort is exponential on software size.
In this equation,  $a$ and $b$ control the linear and exponential
inferences (respectively) on model estimates; 
while
$pmat$ (process maturity) and $acap$ (analyst capability) are project choices
articulated by managers. 
\eq{simp} contains only two features ($acap,pmat$) and a full COCOMO model contains a set of project descriptors as shown in \fig{coc1}.

\begin{figure}[!t]
\center
{\scriptsize
\begin{tabular}{l|r@{:~}l|}\cline{2-3}
decreases      & acap & analyst capability\\
effort   & apex & applications experience\\
 & 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}
& sced & dictated development schedule\\\cline{1-3}
increases      & cplx & product complexity\\
effort   & data & database size\\
 & 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 NASA93ii COCOMO data set.}\label{fig:ab}
%\end{figure}
%

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. 
The ranges varied widely:
\begin{equation}\label{eq:ab}
\left( 3.2 \le a \le 9.4 \right) \wedge \left(0.8 \le b \le 1.12\right)
\end{equation}
Such large variation in model tunings not only violates standard gradient descent methods,
but it also obscure any
 benefits observed within a particular  project change.
Suppose a proposed technology  doubles productivity, 
but $a$ changed from 9.0 to 4.5, any improvement would be obscured by the {\em tuning instability}.

In summary, 
model-based methods can suffer from:
\bi
\item Inapprorpaite extrapolations;
\item Ontology restictions;
\item Untamed variance inside the models
\ei
Hence, in this paper, we explore alternative methods.
%XXX note all model-based vs all instance-based

\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 NASA93ii.
}\label{fig:eg} \end{figure*}


\section{Instance-based Methods}\label{sect:inst}
This section described three versions 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: NASA93ii and COC81ii.
{\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) a description of the  $context\subseteq P$ that interests them
and (b) 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.

Another important assumption made by {\W}2 is that we should not reason on {\em all} 
the data. Rather, we need to focus on the data {\em relevant} to the $context$ of the current
problem.  A mistake made by {\W}0 was to reason over all the data- which lead to problems of learning
from inappropriate examples.
{\W}0 tended to converge on nearby projects with increased productivity, but because it had (e.g.)
a lower level of complexity or required reliability, it selected for regions
containing  acceptable alternatives.
Sometimes, this is unavoidable (e.g. if all the available examples mention lower complexity or
reliabity). However, as much as possible, {\W}'s reasoning needs to respect the $context$ limitations
offered by the user.

{\W}2 finds a project treatment $R_x$ by 
studying the project similar to the context in the case library.
Formally, {\W}2 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 seven 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 Test the treatment from $Step6$ using relevant cases from the $test$ set;
i.e. find all rows in the neighborhood of the $context$ in $test$ set; then
find the subset of those rows that match  the treatment. Assess
those rows using a $value$ function like \eq{edt}.
\item 
Repeat these six 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
Note that $Step7$ is a new feature of {\W}2 ({\W}0 and {\W}1 neglected to test for treatment stability).

On 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 NASA93ii. 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$ defines ranges for 14 project descriptors.
Any training case contains ranges that overlaps with between 0 and 14 of the ranges
is $context_1$. As shown in 
\fig{eg}.a, we can use the size of this overlap to sort the cases: the neighborhood
cases are those with greatest overlap.  Appealing to the central
limit theorem, {\W}2 says the neighborhood of a query  are the $K_1=20$ training cases with largest
overlap to the query (and for very small data sets, we use all the training examples except
 the $K_2=5$ examples discussed below).
%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))$.
We set the $B$ value after experiments with one data sets, then leaving it fixed for the rest.
For all the {\W} studies in this paper, $B=5$.

$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}
The $x$ top-ranked items of \fig{eg}.c are candidate treatments:
\[\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,
$Step5$  explores $R_x$ upwards from $x=1$ while:
\bi
\item
The median $value$ of the rows selected by $R_{x+1}$ is  greater than that of $R_x$.
\item The number of selected rows $|R_x \wedge neighborhood| \ge 3$;
In the case of \fig{testing-constrained}, $Step5$ returns $R_1$ ($pmat=3$). 
\ei
\fig{testing-applied} applies $R_1$  on the test data. 
Its impact is reported as the median effort value of the cases. 
For the cases of \fig{testing-applied}, this is 81 months of effort.

{\W}2 is not a slow algorithm.
Nothing in any of these steps takes more than  log-linear time, and even that is only to
sort $K_1$ items (which is a very small list).
Even when implemented in an interpreted language  (GAWK), {\W}2 runs in less than half
a second for up to 500 cases (on a 3MHz dual core Macintosh, OS/X 10.6, 4GB of ram).

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 $as is$ values are from the neighborhood
of the $context$; e.g. the $effort$ column.
\item
The $to be$ values are from the cases selected
by a treatment; e.g. the $effort$ column.
\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. 
\item
The $improvement$ from $a=as-is$ to \mbox{$t=to be$}  is 
$100*(a - t)/a$.
$Larger$ improvements are better.
\ei
For example, consider $pmat=3$:
\bi
\item Without the $pmat=3$ restriction, the median and spread
in the test set are  235 and 633 months, respectively.
\item With $pmat=3$,
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
\begin{figure}[!t]
\center
\includegraphics[width=3.5in]{figs/noncocomo-reduce.pdf}
\caption{Effort results for five non-COCOMO datasets.
}\label{fig:other-reduce}
\end{figure}

\subsection{Example}

\fig{other-reduce} shows the results seen after apply {\W}2
to:
\bi
\item
Enhancements to a U.K. telecommunications product;
\item
Projects collected by Miyazaki et al~\cite{miyazaki94};
\item
Finnish Information Systems projects;
\item
A large dataset of Chinese software projects;
\item
Large COBOL projects, collected by Kemerer~\cite{kemerer87}.
\ei
The format of this data is highly varied and includes
number of basic logical transactions, query count and number of distinct business units serviced.
For these data sets, we did not have access to specific
case studies like \fig{cases}. Hence, these results are based on
{\em contexts} developed as follows:
\bi
\item
  The first contained
the {\em entire range} of possible project project descriptors, representing
complete freedom to recommend any change within the space. 
\item
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.
\ei
For these experiments, the $values$ function was just ``reduce effort''
(later in this article we
explore other results on COCOMO-related data, that tries to reduce effort {\em and} defects {\em and}
calendar months).

There are three noteworthy aspects of the \fig{other-reduce} results:
\bi
\item All the points in that figure are positive; i.e.
improvements were seen in all cases.
\item
The dotted lines show the 50\% percentile range of the results: 
half that results had at least
56\% and 73\% improvement in median and spread.
\item
There is no evidence that {\W}2 has problems with
smaller data sets. The two smallest examples processed by {\W}2 are Kemerer and Telecom
containing 15 and 18 examples each. The minimum improvements seen, even for these small data sets,
are 55\% (in both median and spread). 
\ei
The expected value  of the results in these examples is very high; e.g. a 56\% median improvement
in effort. 
The reason for these large improvements is that, in these examples, we focuses {\em only } on effort.
Clearly, there are many ways to cut corners in a project and some of those can have disasterous
results (e.g. allocate no effort to testing will reduce the cost, but that is clearly not a recommended
management action for  a software project). 
Later in this paper are examples where 
{\W}2 is chasing improvements to effort {\em and} defects {\em and} total calendar time to
develop the software. Optimizing for $N=3$ goals is a harder task than just the $N=1$ goal of \fig{other-reduce}.
Hence, those  
the improvements seen in those examples will be more modest (around 20\%).




\section{Model-based Methods}\label{sect:models}
 This section discusses SEESAW, our best model-based method for learning changes to a software project.
Subsequent sections will compare SEESAW to {\W}.


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

Since all our model-based methods are built around the COCOMO-suite, we must use COCOMO data
and $contexts$ written in the COCOMO ontology.
\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  (OSP);
\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 \fig{cases}  shows project features that cannot be
changed. For example in project 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 flight software varies from 
3 (nominal) to 5 (very high). 


\subsection{Handling the 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 a set of goals is traditionally resolved by
computing
partial differential equations of a model, and 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.
As shown in \eq{ab}, this premise does not hold for the COCOMO models used in this study.

\input{figs/projects.tex}
%
%
%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 NASA93ii 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 COC81ii 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 NASA93ii; 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}

If {\em tuning instability} cannot be isolated, 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}
For example,  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}
$median_n$ is the median observed 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 between 0 and 1 (\mbox{$0 \le value \le 1$}) then {\em higher} values
are {\em better}.

\eq{argmax} needs to 
sample the space of model tunings.
The appendix to this paper describes one mechanism for sampling across the space of the
tunings within Boehm's
COCOMO effort estimator and the COQUALMO defect estimator.
One thing to note with that appendix is that,
for instance-based methods, {\em none} of that machinery 
is required.
\begin{figure}[!t]
\scriptsize
\begin{center}
\includegraphics[width=2.2in]{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}


\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 (SA)  run
explores 10,000 variants on some solution~\cite{kirkpatrick83}.
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.
\fig{run} shows the treatment $R_x$ at any $x$ value is
the conjunction of ranges observed between 
1 to $x$
(see the table at the bottom of that figure).
The $y$ axis scores show 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
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, each feature is randomly selected on each iteration.  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 used in SA.

This paper also explores ithe ISAMP, BEAM, and A-STAR algorithms decribed in the appendix.
Initially, we planned  to explore more AI algorithms but
the success of {\W}'s instance-based approach has decreased our motivation
in that regard.


\subsection{Comparisons of AI Model-based Methods}
For each case study of \fig{data}, each algorithm was run 20 times (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.





%\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 NASA93ii.
%
%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}
%NASA93ii\\
%\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}
%NASA93ii\\
%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}
%
\newcommand{\xxx}{\cellcolor[gray]{.8}} 
\input{figs/w2-vs-seesaw.tex}
\begin{figure}[!b]
\center
\includegraphics[width=2.5in]{figs/changes.pdf}
\caption{Range of changes in median and spread generated by applying
the recommendations of {\W}2. The median observed
changes were (20.5, 20.5)\% for (medians, spreads), respectively. 
}\label{fig:changes}
\end{figure}

\section{Model- vs Instance-Based Methods}
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 NASA93ii and COC81ii 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.
Originally collected in the COCOMO-I format, 
JPL business experts have translated them from
their original COCOMO format to COCOMOII.

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}2 took  those $contexts$ then applied the seven step procedure described
above to  NASA93ii and COC81ii.
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 and {\W}2.
We say that $rows_1$ and $rows_2$ are the rows selected from the neighborhood after applying
SEESAW's or {\W}2's recommendations (and by ``apply'', we mean reject any row that
contradicts the ranges in the recommendation).
From $rows_i$, we applied \eq{edt} to find $values_i$. 

The NASA93ii and COC81ii results are shown in \fig{cocomo81results},
divided into the defect, effort, months
changes see in GROUND, FLIGHT, OSP2 and OSP.  
In all, we show 24 comparisons:
\[\scriptsize
\left(\begin{array}{c}
NASA93ii\\
COC81ii
\end{array}
\right)
* 
\left(
\begin{array}{c}
defects\\
effort\\months
\end{array} 
\right)
* 
\left(
\begin{array}{c}
ground\\
flight\\
OSP\\
OSP2\end{array}
\right)
\]
{\W}2 produced larger median reductions that SEESAW in
$16/24$ comparisons.
The ``Win'' column of those figures indicates when any member of a
comparison had a higher value {\em and} was  statistically significantly different
(Mann-Whitney, 95\% confidence).  In nearly half the comparisons ($11/24$),
{\W}2 results were 
statistically
different {\em and} better than SEESAW (in the remaining comparisons,
SEESAW's median
improvements were never better than {\W}2).

\fig{changes} shows the sorts the median and spread improvements seen
from the \fig{cocomo81results}  results.
Note that rarely were the changes to the median less than zero.
In the majority of cases, {W}2's median and spread improvements were positive (an expected
value of 20.5; sometimes ranging over 50\%).  
While occasionally the spread degraded sharply (down to 50\% $worse$),
such cases were uncommon: note that in only 10\% of our results were the spread changes below -15\%.
Also, all the cases where {\W}2 had poor spread results were in the COC81ii data set which, as discussed below,
is a data set with certain special features.

The gray cells in \fig{cocomo81results}
show optimization {\em failures}; i.e.
a zero or 
negative improvement.
{\W}2 failed less than SEESAW (had fewer gray cells).
{\W}2 showed $3/24$ and $7/24$ failures for medians and spreads (respectively)
while SEESAW showed $13/24$ and $7/24$ failures for medians and spreads (respectively).
One of SEESAW's failures was particularly
dramatic: witness the increase from 98 effort months to 447 effort months
in the OSP2 effort results. 
We conjecture that SEESAW's greater failures in median reduction are due to the over-fitting
problem discussed in \tion{draw}. SEESAW's model-based methods are free to sample increasingly
narrow segments of the internal state space of a model (``flying in'', as it were, into small
cracks between the training data).  If that sampling is taken to extreme, and the model-based
methods offer recommendations that cover a tiny part of the state space, and if the test data
does not fall into that tiny region, then the model-based recommendations will fail. 


Note that most of the gray cells occur in the COC81ii results.
Boehm assumed that this data was to be
analyzed by regression so spent much effort 
on the COC81ii data, applying his domain expertise to prune or trim outstanding values.
Curiously, {\W}2 performed best on the ``uncleansed''
data set (NASA93ii) 
than the cleaner data set (COC81ii). 
We conjecture that, sometimes, seemingly ``dirty'' data
actually contains data that is insightful in some contexts. 
While such outliers confuse regression-based methods (that try to fit one model over the entire data),
instance-based tools like {\W}2 can
exploit those less-common instances (since they build local models around each context). 

In summary:
\bi
\item {\W}2's performance was better than SEESAW;
\item {\W}2 was more effective at reducing the medians;
\item Both instance-based and model-based methods had similar issues with reducing the spread.
\item Possibly, the instance-based approach of {\W} performs better on ``dirtier'',
nosier data than model-based methods.
\ei
%\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\% COC81ii 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 NASA93ii OSP:
%{\W}2 offered median reductions of 72\%, 69\%, and 43\% compared to SEESAW's 22\%, 37\%, 13\% for defects, effort, and months respectively.
%
\section{Discussion}

\subsection{Intra- and Inter-Project Stability}\label{sect:stable}
One of the premises of instance-based methods like {\W}2 is that local reasoning
in some specific context is best that fitting one model over an entire space.
This is required if the ``best'' solutions in a one context do not hold in others.

To test this  premise, we generated a report of what treatments were found under different
conditions.
\fig{stability} shows the results of {\W}2's $Step7$ (prune all treatments
that do appear in less than 50\% of 20 repeated trials).
\begin{figure}[!t]
\begin{center}
{\footnotesize
\begin{tabular}{|r|@{\hspace{0.75mm}}c@{\hspace{0.75mm}} @{\hspace{0.75mm}}c@{\hspace{0.75mm}} @{\hspace{0.75mm}}c@{\hspace{0.75mm}} @{\hspace{0.75mm}}c@{\hspace{0.75mm}} @{\hspace{0.75mm}}c@{\hspace{0.75mm}} @{\hspace{0.75mm}}c@{\hspace{0.75mm}} @{\hspace{0.75mm}}c@{\hspace{0.75mm}} @{\hspace{0.75mm}}c@{\hspace{0.75mm}} @{\hspace{0.75mm}}c@{\hspace{0.75mm}} @{\hspace{0.75mm}}c@{\hspace{0.75mm}} @{\hspace{0.75mm}}|c@{\hspace{0.75mm}}|c|}\hline
\multicolumn{12}{|c|}{Stability Comparison for NASA93ii 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}ltex=4\end{sideways}}&
\emph{\begin{sideways}pmat=3\end{sideways}}&
\emph{\begin{sideways}pmat=4\end{sideways}}&
\emph{\begin{sideways}rely=3\end{sideways}}&
\emph{\begin{sideways}sced=2\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{12}{|c|}{Stability Comparison for NASA93ii 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}ltex=4\end{sideways}}&
\emph{\begin{sideways}pmat=3\end{sideways}}&
\emph{\begin{sideways}pmat=4\end{sideways}}&
\emph{\begin{sideways}rely=3\end{sideways}}&
\emph{\begin{sideways}sced=2\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{12}{|c|}{Stability Comparison for NASA93ii 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}ltex=4\end{sideways}}&
\emph{\begin{sideways}pmat=3\end{sideways}}&
\emph{\begin{sideways}pmat=4\end{sideways}}&
\emph{\begin{sideways}rely=3\end{sideways}}&
\emph{\begin{sideways}sced=2\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{12}{|c|}{Stability Comparison for NASA93ii 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}ltex=4\end{sideways}}&
\emph{\begin{sideways}pmat=3\end{sideways}}&
\emph{\begin{sideways}pmat=4\end{sideways}}&
\emph{\begin{sideways}rely=3\end{sideways}}&
\emph{\begin{sideways}sced=2\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}2 for reducing individual goals 
($defects$, $effort$, or $months$) as well as all goals at once ($all$).}
\label{fig:stability}
\end{figure}
The left-hand column of \fig{stability} shows the four $values$ function used
in that study:
\be
\item {\em Defects} aims at reducing just defects;
\item {\em Effort} aims at  reducing just effort;
\item {\em Months} aims at reducing
a project's total calendar time.
\item {\em All} refers to \eq{edt}; i.e. try to decrease effort {\em and} development time
{\em and} number of defects;
\ee
The last of these is a multi-objective function while the rest strive to optimize
one objective without concern to the others.
\fig{stability} shows that,
in any row, the conclusions reached by {\W}2 are stable (i.e. appear at high frequency,
across 20 random selections of $train:test$). 
That is, {\W}2's results exhibit
$intra-$project conclusion stability (when the
$context$ and $values$ function are held constant).
For project managers, this is good news since it shows that their data contains
clear signals on how to best change their particular project in order to achieve particular
goals.

However, \fig{stability}  also shows that  
if the $context$ is changed (from generalized FLIGHT systems to a specific
flight system like OSP), then the recommended changes are very different.
Similarly, the OSP results show that
altering the $values$ function also dramatically changes recommendations.

Menzies \& Shull~\cite{me10b} report that many SE papers conclude that
what is ``best'' for one project may not
be ``best'' for another.
For example, Zimmermann studied 629 pairs of software development 
projects~\cite{zimmermann09}. In only 4\% of those hundreds of pairs was a 
defect prediction model learned from one project useful on 
another. 
When such {\em inter-}project conclusion instability exists,
 then
tools like {\W}2 are essential since
  it is best  to learn changes that are tuned to the specifics of particular projects (like OSP \&
OSP2) rather than on generalized descriptions of software (like FLIGHT \& GROUND).

\begin{figure}[!t]
\footnotesize
\begin{center}
\begin{tabular}{r@{~}|c|@{~}l@{~}r@{~}l}
%& & relative\\
   & appears in \\
id &\fig{stability} as& features  & \multicolumn{2}{l}{relative weight}\\\hline
1&&Personnel/team capability & 3.53	&\rule{17mm}{2mm}\\
2&&  Product complexity & 2.38&	\rule{12mm}{2mm}\\
3&time& Time constraint & 1.63&	\rule{8mm}{2mm}\\
4&rely&    Required software reliability & 1.54&	\rule{8mm}{2mm}\\
5&&    Multi-site development   &	1.53&	\rule{7mm}{2mm}\\
6&&       Doc. match to life cycle  & 	1.52	&\rule{7mm}{2mm}\\
7&&  Personnel continuity  &	1.51&	\rule{7mm}{2mm}\\
8&apex&  Applications experience & 1.51	&\rule{7mm}{2mm}\\
9&& Use of software tools & 1.50	&\rule{7mm}{2mm}\\
10&& Platform volatility & 1.49&	\rule{7mm}{2mm}\\
11&stor& Storage constraint & 1.46&	\rule{7mm}{2mm}\\
12&pmat& Process maturity  &	1.43	&\rule{7mm}{2mm}\\
13&ltex&    Language \& tools experience  &	1.43	&\rule{7mm}{2mm}\\
14&sced&     Required dev. schedule  & 1.43	&\rule{7mm}{2mm}\\
15&&Data base size & 1.42&	\rule{7mm}{2mm}\\
16&&  Platform experience & 1.40&	\rule{7mm}{2mm}\\
17&&     Arch. \& risk resolution  &	1.39&	\rule{7mm}{2mm}\\
18&&  Precedentedness  &	1.33&	\rule{6mm}{2mm}\\
19&&  Developed for reuse  	&1.31	&\rule{6mm}{2mm}\\
20&& Team cohesion  &	1.29&	\rule{6mm}{2mm}\\
21&&    Development mode   &	1.32	&\rule{6mm}{2mm}\\
22&& Development flexibility &	1.26	&\rule{6mm}{2mm}\\
\end{tabular}
\end{center}
\caption{Relative effects  on development effort. From~\cite{boehm00a}.
}\label{fig:coceffects}
\end{figure}
\subsection{When Not to Use {\W}2}\label{sect:delta}
Like any instance-based method, {\W}2 requires historical
cases. If such data is missing then {\W}2 cannot be used.

In that circumstance,
discussions about how to best change a project can use
results borrowed from other sites. For example, \fig{coceffects} show's Boehm et al.'s~\cite{boehm00b} 
analysis of the effects of changing some project attribute from its minimum
to maximum value. Based on 
data from
a regression analysis of 161 projects, this figure comments that
changing  (e.g.) personnel/team capability   can alter the effort
to build software by up to 350\%.  Using this data, the effects
of various changes can be investigated using Boehm's {\em delta} analysis technique~\cite{boehm00a}:
\bi
\item
An 
old project with known efforts is used as a baseline. A change
to a project is described as a new project, expressed in
in terms of deltas to 
the variables of \fig{cocefforts}.
\item
The new estimate is then the product 
of the baseline times the eﬀort multiplier deltas. 
\item
The ``best'' changes to a project are those that are simplest
to implement and have most positive impact on the effort (ideally, reduces it).
\ei
Column two of
\fig{coceffects} lets us compare context-independent reasoning
(e.g. delta analysis) vs context-dependent reasoning (e.g. {\W}2).  
Note  how that only a third of the \fig{coceffects} attributes appear in the ``best''
treatments of \fig{stability}. 
Curiously, the two
attributes with greatest impact (personnel/team capability and product complexity) are absent from
\fig{stability}. 

Why is {\W}2 ignoring an attribute with such a large impact (350\%)?
To answer that question, we have go to the context-dependent particulars.
Recall from \fig{cases} that in OSP2, product complexity is fixed at $cplx=4$ and personnel/team capability is
fixed at $pcap=3$.
{\W}2 does not recommend treatments for
things that cannot change. Hence, $cplx$ and $pcap$ are absent from the OSP2 results of \fig{stability}.
Similarly, OSP allows only $pcap=3$ so this attribute is also absent.

The same reasoning does not explain the other absent attributes.
To understand these,  we must look at the data.
OSP sets $cplx\in\{5,6\}$. This attribute is absent in the treatments since there is insufficient
support in NASA93ii to justify their inclusion (there  only five
$cplx=5$ examples in NASA93ii and no examples of $cplx=6$).
Similar explanations can explain all the remaining absences.

Examples such as these show how {\W}2 can provide recommendations that may go against common expert advice. This lack of a defined relationship between data attributes underscores the need for careful query construction. For example, if a query contains conflicting attributes, {\W}2 maintains no internal inconsistency check. Model-based approaches such as S-COST ~\cite{Boehm96softwarecost} can provide this sanity check, but incur the
costs associated with model-based methods discussed above
(ontology restrictions, untamed internal model variance, etc).

In summary, when data is absent, managers can debate changes to projects by reusing data like \fig{coceffects}.
However, the conclusions reached from a context-independent reasoning (like delta analysis)
can be made more specific  with local information about the kinds of projects seen in the local environment
and the kinds of changes the local managers are willing to accept. Therefore, where possible, we recommend
collecting local data and analyzing it with {\W}2.

\subsection{Scope of the Study}
%\subsubsection{External Validity}

This study use conveniently available datasets in the PROMISE repository, the result applies  within the same context of the datasets. In addition,
our evaluation compares the performance of different methods
across a finite number of problems, so it  cannot be used to predict which
method will be superior to others for some future, as yet unseen, problem. 
In fact, no method has been found so far that is universally superior to others
in all problems; indeed, the ``no-free-lunch
theorem''~\cite{wolpert94} suggests  that such an universal best method for all problems can never
exist. In practice, for a given new learning problem,
various methods need to be empirically evaluated to find the best
ones, such as the ones carried out in the study.

We have shown that some treatments identified can improve the quality measures observed in historical project datasets. Our performance measures including median and spread reductions seen in ``hold-out data'' should not be confused with practical significance in the real world. 

That being said,
we note that publications from other research communities assess their models in the same manner
 as this paper:
see the {\em effort estimation}~\cite{Li2009,Lipowezky1998,Walkerden1999,Kirsopp2002,Mendes2003}
and {\em defect prediction}~\cite{ostrand04,journals/ese/KhoshgoftaarS03,tosun10,me10a} literature.
Ideally, researchers in effort estimation, defect prediction, or learning changes to software projects
should apply their recommendations to live projects. However, hold-out tests
are widely used due to the tremendous practical
difficulties associated with performing such tests on multiple software projects.
At the very least, studies like this
paper are required to prune the space of methods to be laboriously tested on new, real-world, projects.

%Since most of the empirical studies on supervised learning in the
%literature, including this one, use conveniently available data
%sets, such as those in the PROMISE repository, rather than truly
%random samples, the generalizability of the evaluation results is
%dependent on the representativeness of these data sets. In addition,
%our evaluation compares the performance of different methods
%across a finite number of problems, so it  cannot be used to predict which
%method will be superior to others for some future, as yet unseen, problem. No
%method has been found so far that is universally superior to others
%in all problems; indeed, the ``no- free-lunch
%theorems''~\cite{wolpert94} predict  that such a universal best method for all problems can never
%exist. In practice, for a given new learning problem,
%various methods need to be empirically evaluated to find the best
%ones (e.g. as done in this paper).

%While the ultimate generalizability to all future problems is an open issue,
%what we can see with the results to hand is that of the methods studied in this
%paper, the instance-based methods
%are most general (i.e. apply to more data).
%Recall from \tion{draw} that a disadvantage of model-based methods are that
%they can only be applied to data that matches the ontology of that model. Instance-based
%methods like {\W}2 can be applied to a much larger space of data sets (caveat: the cases must
%include some project quality values which we can use to guide {\W}2's search for better treatments).
%Note that it would be impossible to apply our model-based methods to the five
%data sets of \fig{other-reduce}, since they are not expressed
%in terms of the COCOMO ontology. 

%\subsubsection{Construct Validity}

%Here we have shown that some treatments can improve the quality measures
%seen in historical record of past projects. Note that this is different
%to showing that these treatments are effective on current projects.
%Hence, our performance measures (median and spread reductions seen in ``hold-out data''
%not used during the training period)
%should not be confused with 
%practical significance in the real world. 

%The fact that the effect of some 
%technique is statistically better than some other technique shows that the 
%one technique {\W}2 is be recommended over others (all the model-based methods studied here). However,
%it does not tell whether the effect is 
%practically important, large, or even useful in a real-world 
%context. 
%That being said,
%we note that publications from other research communities assess their models in the same manner
% as this paper:
%see the {\em effort estimation}~\cite{Li2009,Lipowezky1998,Walkerden1999,Kirsopp2002,Mendes2003}
%and {\em defect prediction}~\cite{ostrand04,journals/ese/KhoshgoftaarS03,tosun10,me10a} literature.
%Ideally, researchers in effort estimation, defect prediction, or learning changes to software projects
%should apply their recommendations to live projects. However, hold-out tests
%are widely used due to the tremendous practical
%difficulties associated with performing such tests on multiple software projects.
%At the very least, studies like this
%paper are required to prune the space of methods to be laboriously tested on new, real-world, projects.

%
%{\em Internal validity} 
%claim improvements to projects when really what is being
%shown here is improvements to historical
%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.
%%\input{figs/win-loss-tie-discretize.tex}
%
%%\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{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. 
%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 flexibility 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 improvement 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.
%
%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}

\noindent {\em To attain knowledge, add things every day.\newline
To attain wisdom, remove things every day.\newline
                        -- Lao-tse}
\newline

{\em Simpler methods} may offer a baseline result that
demonstrates the value of the sophisticated approach.
Researchers into empirical methods such as Cohen~\cite{cohen95}
also suggests 
benchmarking
the supposedly sophisticated method against 
simpler alternatives.


%For learning changes to software projects,
%{\W}2  is a candidate baseline tool since:
%\bi
%\item
%It is simple to implement and fast
%to execute; 
%\item
%The algorithm scales well (runs in log-linear time);
%\item
%It can be applied to a wider variety of data sets (since it has fewer ontological restrictions);
%\item
%For the data studied here, it performs  as least as good (or better) than a range of model-based
%methods.
%\ei
%While an interesting baseline result, this paper is hardly a final result.
This paper attempts to inspire more research into instance-based planning algorithms
that learn changes within its context in order to achieve/avoid certain kinds of results.



There is much to explore. For example, there are many open issues in the above discussion:
\bi
\item Are model-based methods worse for noisier data?
\item Is ``data cleansing'' recommended for regression, but deprecated for  instance-based methods?
\item How best to reduce spread, thus increasing the confidence a user has in the results?
\ei
As to this last point, better algorithms may not be effective in reducing spread.
Elsewhere we have tried reducing estimate variance with feature
subset selection (FSS)~\cite{chen05,me06d}.  Sadly FSS only somewhat
reduces, but does not tame, the variance problem.
Nor should we look to more extensive data collection (recall the discussion in \tion{draw}
on the difficulties with getting process data).
Jorgensen~\cite{jorg04} advises that the best estimates come from combining results from multiple methods,
including human-based judgment. Accordingly,
in our own work, we have started exploring Bayesian frameworks that
combine the output of instance-based methods with that of human experts
(but
have no results to report at this time).



%Software Engineering is based on the mathematical idea that computation can be fully specified. However, software remains an essentially human process, wrought with social and creative underpinnings.  Unlike traditional engineering concerns like mechanical forces or material properties, groups of humans are (currently) much less consistent and predictable.
%
%Yet, we still seek general truisms about software just as we would a physical phenomenon. For example, models like COCOMO abstract project qualities into quantified effects on development effort. These model-based approaches can combine both expert advice and local data in order to generalize complex, human behavior to a handful of variables. However, models must be calibrated to specific institutions and respond slowly to changes in development techniques. 
%
%One may question whether it is necessary to construct the model in the first place. A project manager's concern isn't beauty in generalization, but a practical one: {\em how to find useful changes for a particular project}. The drawbacks associated with model uncertainty and relevancy offer room for alternatives to model-based methods.
%
%Instance-based methods eschew generalizations about a constantly shifting field. Instead, inferences are made from local data alone. While model-based approaches can operate without any historical data, model calibration and validation do require historical instances. If you already have the data, you might as well use it.

%{\W}2 offers a simple, fast implementation of instance-based reasoning using contrast sets. Improvements to software projects are gleaned by answering a simple question: {\em Given a set of similar projects, which attributes describe the most desirable projects but not the least desirable projects?} We set out to compare this simple learner with a related model-based algorithm called SEESAW.
%
%\fig{cocomo81results} show our results. {\W}2 delivers statistically better recommendations across multiple runs for 11 of 24 trials. More importantly, when {\W} did not statistically outperform SEESAW, it still performed no worse than SEESAW.
%
%{\W}2's instance-based approach is also data agnostic. Whereas
%SEESAW depends on data expressed in COCOMO format, we are able to
%run {\W}2 on several arbitrary effort estimation datasets
%(see~\fig{other-reduce} and ~\fig{data}). In these cases, {\W} always
%reduces median software effort and spread uncertainty by at least
%25\%, with some datasets seeing reductions of 75\% or more.
%
%From these results we conclude that {\W}2 offers better or comparable performance to a model-based method while remaining simpler and more flexible. With as few as 15 data points (see Kemerer dataset in ~\fig{data}) {\W} is able to suggest recommendations that consistently estimate effort reductions by over 50\%. 
%
%
%We conclude that:
%\be
%\item
%Often, managers have many options for effectively changing and
%improving their projects.
%\item
%Very simple instance-based methods can  do better than more
%complex model-based methods.
%\ee
%While the first point  may be of most interest to
%industrial practitioners, it is the second point  that may be most interesting to researchers.
%There are any number of sophisticated methods for
%exploring the complexities and uncertainties associated with
%controlling software engineering projects\footnote{
%E.g. 
%Bayes nets;
%fuzzy logic;
%constraint-satisfaction
%simulated annealing; evolutionary algorithms;
%tabu search; ant-based search; various data mining tools such as
%support vector machines or random forests;
%numeric methods such as integer programming; 
%logic-based-approaches such as Davis-Putnam procedures or binary-decision diagrams; 
%or 
%any number of AI search algorithms~\cite{lessmann09,norvig03,Gu97,me09g,uribe94,harman07}.}. 
%Nevertheless, before researchers explore sophisticated methods, they should
%try a simpler
%method, at least for the purposes of establishing a performance baseline.
%For learning changes to software projects,
%{\W} is a candidate baseline tool since:
%\bi
%\item
%It is simple to implement and fast
%to execute; 
%\item
%The algorithm scales well (runs in log-linear time);
%\item
%For the data studied here, it performs  as least as good (or better) than a range of model-based
%methods.
%\ei
%
%

%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{local_refs,myrefs,refs}   % name your BibTeX data base
\appendix
\subsection*{Modeling Variance in COCOMO/COQALMO}

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}
\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 {\em positive effort EM} features such as $cplx$ with slopes $m_+$, are positively correlated to effort/cost. 
The
{\em negative effort EM} features such as $acap$, with slopes $m_-$.
are negatively correlated  to effort/cost.
The $m$ ranges, as  seen in 161 projects~\cite{boehm00a}, are:

{\small
\begin{equation}\label{eq:ranges}
\left(0.073 \le m_+\le 0.21\right) \wedge
\left(-0.178 \le m_- \le -0.078\right)
\end{equation}}
To random sample the tunings, all that is required is to select $m$ at random from the ranges
of \eq{ranges}.
As shown in \cite{me09a},
similiar equations can be derived from the COCOMO scale factors and the COQUALMO model.

\subsection*{ISSAMP, BEAM, A-STAR}

{\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 observed so far. Any conjunction whose $value$ exceeds that
of the worst solution is abandoned, and the new ``worst value'' is retained. 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 value.


Our other two 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

%$(see~\cite{}).
%
%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.
%\subsection*{The Complexity of {\W}2}
%
%{\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 $Step6$ each 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,
%$K_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$.
%
%$Step6$ requires two passes of the test set: one to find and sort the neighborhood
%(which, as said above, takes like $c + K_1log(K_1)$)
%and another to apply the learned treatment to that neighborhood.
%Finally, $Step7$ 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{; $Step7$'s repeats}\\
%              & 2c + & \mbox{; $Step1$}\\
%              & c + K_1log(K_1) + & \mbox{; $Step2$}\\
%              & K_1 +  & \mbox{; $Step3$} \\
%              & pB + pB\cdot log(pB)  + & \mbox{; $Step4$}\\
%              & pBK_1 + & \mbox{; $Step5$}\\
%              & c + 2K_1log(K_1)  & \mbox{; $Step6$}\\
%       )\\
%\end{array}\]
%}
%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.
%
\begin{IEEEbiographynophoto}{Tim Menzies} 
is an 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{IEEEbiographynophoto}
\begin{IEEEbiographynophoto}{Adam Brady } is a master's student at West Virginia University. He received a B.Sc. in Computer Science from WVU in 2009. His current research focuses on instance-based reasoning, specifically its application to improving software quality. \end{IEEEbiographynophoto}
\begin{IEEEbiographynophoto}{Jacky Keung } is an assistant professor
at the Department of Computing at the Hong Kong Polytechnic University, and has been working with NICTA on empirical software engineering since 2004. 
He has a CS degree and a PhD from the University of Sydney and the University of New South Wales respectively and is the author of many top publications.
His recent research concerns applying light weight modeling techniques to emerging areas of software technologies, including adaptive elastic cloud computing.
  \end{IEEEbiographynophoto}
\begin{IEEEbiographynophoto}{Steven Williams } 
Steven Williams is a PhD student at Indiana University where he
studies cognitive science and informatics.  He holds BS degrees in
civil engineering and computer science from West Virginia University.
\end{IEEEbiographynophoto}

\begin{IEEEbiographynophoto}{Oussama El-Rawas }
Oussama "Ous" El-Rawas graduated with his Bachelors in Computer
Engineering from The American University of Beirut (AUB). He proceeded
to obtain his Masters of Science in Electrical Engineering From West
Virginia University (WVU) and is currently working at Medquist Inc. as a
researcher as well as being a part time PhD student at WVU. His current
research interests include Machine Learning, Natural Language
Processing, among others.
\end{IEEEbiographynophoto}

\begin{IEEEbiographynophoto}{Phillip Green } Biography text here.  \end{IEEEbiographynophoto}

\begin{IEEEbiographynophoto}{Jairus Hihn}
Jairus Hihn received the PhD degree in
economics from the University of Maryland. He
is a principal member of the engineering staff at
the Jet Propulsion Laboratory, California Institute
of Technology, and is currently the manager
for the Software Quality Improvement Projects
Measurement Estimation and Analysis Element,
which is establishing a laboratory-wide software
metrics and software estimation program at JPL.
M\&E’s objective is to enable the emergence of a
quantitative software management culture at JPL. He has been
developing estimation models and providing software and mission level
cost estimation support to JPL’s Deep Space Network and flight projects
since 1988. He has extensive experience in simulation and Monte Carlo
methods with applications in the areas of decision analysis, institutional
change, R\&D project selection cost modeling, and process models.
\end{IEEEbiographynophoto}


\begin{IEEEbiographynophoto}{Barry Boehm }
Barry Boehm received his B.A. degree from Harvard in 1957, and his M.S. and Ph.D. degrees from UCLA in 1961 and 1964, all in Mathematics. Between 1989 and 1992, he served within the U.S. Department of Defense (DoD) as Director of the DARPA Information Science and Technology Office, and as Director of the DDR\&E Software and Computer Technology Office. He worked at TRW from 1973 to 1989, culminating as Chief Scientist of the Defense Systems Group, and at the Rand Corporation from 1959 to 1973, culminating as Head of the Information Sciences Department. He was a Programmer-Analyst at General Dynamics between 1955 and 1959. His current research interests include software process modeling, software requirements engineering, software architectures, software metrics and cost models, software engineering environments, and knowledge-based software engineering. 
\end{IEEEbiographynophoto}



\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}




