% This is LLNCS.DEM the demonstration file of
% the LaTeX macro package from Springer-Verlag
% for Lecture Notes in Computer Science,
% version 2.3 for LaTeX2e
%
\documentclass[9pt]{llncs}
\usepackage{graphicx}
\usepackage{alltt}
\usepackage{wrapfig,pifont,url,cite,times}
%
\usepackage{makeidx}  % allows for index generation
\newenvironment{smallitem}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{itemize}
   \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{itemize}}
\newenvironment{smallenum}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{enumerate}
  \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{enumerate}}

 \newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
 \newcommand{\bi}{\begin{smallitem}}
\newcommand{\ei}{\end{smallitem}}
 \newcommand{\be}{\begin{smallenum}}
\newcommand{\ee}{\end{smallenum}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\tion}[1]{\S\ref{sec:#1}}

%
\begin{document}
%
\frontmatter          % for the preliminaries
%
%\addtocmark{Hamiltonian Mechanics} % additional mark in the TOC
%
%\chapter*{Preface}
%%
%This textbook is intended for use by students of physics, physical
%chemistry, and theoretical chemistry. The reader is presumed to have a
%basic knowledge of atomic and quantum physics at the level provided, for
%example, by the first few chapters in our book {\it The Physics of Atoms
%and Quanta}. The student of physics will find here material which should
%be included in the basic education of every physicist. This book should
%furthermore allow students to acquire an appreciation of the breadth and
%variety within the field of molecular physics and its future as a
%fascinating area of research.
%
%For the student of chemistry, the concepts introduced in this book will
%provide a theoretical framework for that entire field of study. With the
%help of these concepts, it is at least in principle possible to reduce
%the enormous body of empirical chemical knowledge to a few basic
%principles: those of quantum mechanics. In addition, modern physical
%methods whose fundamentals are introduced here are becoming increasingly
%important in chemistry and now represent indispensable tools for the
%chemist. As examples, we might mention the structural analysis of
%complex organic compounds, spectroscopic investigation of very rapid
%reaction processes or, as a practical application, the remote detection
%of pollutants in the air.
%
%\vspace{1cm}
%\begin{flushright}\noindent
%April 1995\hfill Walter Olthoff\\
%Program Chair\\
%ECOOP'95
%\end{flushright}
%%
%\chapter*{Organization}
%ECOOP'95 is organized by the department of Computer Science, University
%of \AA rhus and AITO (association International pour les Technologie
%Object) in cooperation with ACM/SIGPLAN.
%%
%\section*{Executive Committee}
%\begin{tabular}{@{}p{5cm}@{}p{7.2cm}@{}}
%Conference Chair:&Ole Lehrmann Madsen (\AA rhus University, DK)\\
%Program Chair:   &Walter Olthoff (DFKI GmbH, Germany)\\
%Organizing Chair:&J\o rgen Lindskov Knudsen (\AA rhus University, DK)\\
%Tutorials:&Birger M\o ller-Pedersen\hfil\break
%(Norwegian Computing Center, Norway)\\
%Workshops:&Eric Jul (University of Kopenhagen, Denmark)\\
%Panels:&Boris Magnusson (Lund University, Sweden)\\
%Exhibition:&Elmer Sandvad (\AA rhus University, DK)\\
%Demonstrations:&Kurt N\o rdmark (\AA rhus University, DK)
%\end{tabular}
%%
%\section*{Program Committee}
%\begin{tabular}{@{}p{5cm}@{}p{7.2cm}@{}}
%Conference Chair:&Ole Lehrmann Madsen (\AA rhus University, DK)\\
%Program Chair:   &Walter Olthoff (DFKI GmbH, Germany)\\
%Organizing Chair:&J\o rgen Lindskov Knudsen (\AA rhus University, DK)\\
%Tutorials:&Birger M\o ller-Pedersen\hfil\break
%(Norwegian Computing Center, Norway)\\
%Workshops:&Eric Jul (University of Kopenhagen, Denmark)\\
%Panels:&Boris Magnusson (Lund University, Sweden)\\
%Exhibition:&Elmer Sandvad (\AA rhus University, DK)\\
%Demonstrations:&Kurt N\o rdmark (\AA rhus University, DK)
%\end{tabular}
%%
%\begin{multicols}{3}[\section*{Referees}]
%V.~Andreev\\
%B\"arwolff\\
%E.~Barrelet\\
%H.P.~Beck\\
%G.~Bernardi\\
%E.~Binder\\
%P.C.~Bosetti\\
%Braunschweig\\
%F.W.~B\"usser\\
%T.~Carli\\
%A.B.~Clegg\\
%G.~Cozzika\\
%S.~Dagoret\\
%Del~Buono\\
%P.~Dingus\\
%H.~Duhm\\
%J.~Ebert\\
%S.~Eichenberger\\
%R.J.~Ellison\\
%Feltesse\\
%W.~Flauger\\
%A.~Fomenko\\
%G.~Franke\\
%J.~Garvey\\
%M.~Gennis\\
%L.~Goerlich\\
%P.~Goritchev\\
%H.~Greif\\
%E.M.~Hanlon\\
%R.~Haydar\\
%R.C.W.~Henderso\\
%P.~Hill\\
%H.~Hufnagel\\
%A.~Jacholkowska\\
%Johannsen\\
%S.~Kasarian\\
%I.R.~Kenyon\\
%C.~Kleinwort\\
%T.~K\"ohler\\
%S.D.~Kolya\\
%P.~Kostka\\
%U.~Kr\"uger\\
%J.~Kurzh\"ofer\\
%M.P.J.~Landon\\
%A.~Lebedev\\
%Ch.~Ley\\
%F.~Linsel\\
%H.~Lohmand\\
%Martin\\
%S.~Masson\\
%K.~Meier\\
%C.A.~Meyer\\
%S.~Mikocki\\
%J.V.~Morris\\
%B.~Naroska\\
%Nguyen\\
%U.~Obrock\\
%G.D.~Patel\\
%Ch.~Pichler\\
%S.~Prell\\
%F.~Raupach\\
%V.~Riech\\
%P.~Robmann\\
%N.~Sahlmann\\
%P.~Schleper\\
%Sch\"oning\\
%B.~Schwab\\
%A.~Semenov\\
%G.~Siegmon\\
%J.R.~Smith\\
%M.~Steenbock\\
%U.~Straumann\\
%C.~Thiebaux\\
%P.~Van~Esch\\
%from Yerevan Ph\\
%L.R.~West\\
%G.-G.~Winter\\
%T.P.~Yiou\\
%M.~Zimmer\end{multicols}
%%
%\section*{Sponsoring Institutions}
%%
%Bernauer-Budiman Inc., Reading, Mass.\\
%The Hofmann-International Company, San Louis Obispo, Cal.\\
%Kramer Industries, Heidelberg, Germany
%%
%\tableofcontents
%%
%\mainmatter              % start of the contributions
%
\title{Accurate Estimates Without Calibration?}

%
%
\author{Tim Menzies \inst{1} 
\and Steve Williams \inst{1} 
\and Oussama Elrawas  \inst{1}  
\and Daniel Baker\inst{1} 
\and Barry Boehm \inst{2}
\and Jairus Hihn\inst{3} 
\and Karen Lum\inst{3}
\and Ray Madachy \inst{4} 
\thanks{
Parts of this research as carried out at West Virginia University, the University of Southern California,
and 
the Naval Postgraduate School.
Other parts of this research was carried out at
the Jet Propulsion Laboratory, California Institute of Technology, under a contract with the National Aeronautics and Space Administration.
Reference herein to any specific commercial product, process, or service by trade name, trademark, manufacturer, or otherwise, does not constitute or imply its endorsement by the United States Government or the Jet Propulsion Laboratory, California Institute of Technology.
} }
%
\authorrunning{Menzies et.al.}   % abbreviated author list (for running head)
%
%%%% list of authors for the TOC (use if author list has to be modified)
\tocauthor{Tim Menzies,Oussama Elrawas,Barry Boehm, Ray Madachy}

%
\institute{LCSEE,
West Virginia University, 
Morgantown, WV, USA,
\email{tim@menzies.us}, \email{oelrawas@mix.wvu.edu}, 
\email{swilli12@mix.wvu.edu} \email{danielryanbaker@gmail.com}
\and
CS,
 University of Southern California,
Los Angeles, California, USA,
\email{boehm@sunset.usc.edu},
\email{madachy@usc.edu}
\and
JPL,  California, USA,
\email{jairus.hihn@jpl.nasa.gov}, \email{karen.t.lum@jpl.nasa.gov}
\and
SE, Naval Postgraduate School, San Diego CA, USA,
\email{rjmadach@nps.edu}
}
 
\pagenumbering{arabic}
\pagestyle{plain}  % switches on printing of running heads
\thispagestyle{empty}
\maketitle              % typeset the title of the contribution

\begin{abstract}
Most process models calibrate their internal settings using local data.
Collecting this data is 
expensive, tedious, and often an incomplete process.
Is it possible to make accurate process decisions without
historical data?  
Variability in model output arises from (a)~uncertainty
in model inputs and (b)~uncertainty in the internal parameters that
control the conversion of inputs to outputs. We find that, for USC
family process models such as COCOMO and COQUALMO, we can control model outputs by using an AI
search engine to adjust
the controllable project choices {\em without} requiring local tuning. 
For example, in ten case studies, we show that the estimates
generated in this manner are very similar to those
produced by traditional methods (local calibration). 
Our conclusion is that,
(a)~while local tuning is always the preferred option,
there exist some process models for which local tuning is optional; and (b)~when building
a process model, we should design it such that it is possible to  use it without tuning. 

Word length: 6525 words (4875 words of text + 7 figures at
250 words per figure).
 \end{abstract} % \section{Introduction}


 
% Consequently, for some years now, we have been exploring methods to
%% reduce the uncertainty in model
%% estimation~\cite{me04h,me05a,me05c,me05d,me06d,me06e,me06f,baker07}.  Like
%% other researchers, we have explored data pruning methods: given a
%% table of $V$ variables from $P$ projects, we find a new table $P'*V'$
%% where $P' \subseteq P$ and $V' \subseteq V$.  Pruning is useful since
%% project data collected in one context may not be relevant to another.
%% Similar projects have less variation in their data and so can make
%% better use of local data for the purposes of model calibration.  For
%% example, Chulani et.al.~\cite{chulani99} \& Shepperd and
%% Schofield~\cite{shepperd97} report that intelligently pruning project
%% data improves estimation accuracy.  Similarly, there are many
%% theoretical~\cite{miller02} and experimental
%% results~\cite{me05c,me05d,me06d} showing that intelligently pruning
%% model variables can reduce estimation variance and error.

%% While certainly useful, data pruning still assumes that there is data to prune.
%% This is not always the case.
%If enough high-quality data is available, then  
%it is good practice to tune general process models with local information.
%However, it can be  very difficult
%to find relevant data within a single organization to 
%precisely tune all the internal parameters inside a process model.
%For example:
%\bi
%\item After 26 years of trying, we have only collected less
%than 200 sample projects for the COCOMO database.
%\item
%Even after two years of effort we were only able to
%add 7 records to a NASA-wide software cost metrics repository~\cite{me07f}.
%\ei
%There are many reasons for this ``data drought'' including data not
%being collected or the business sensitivity associated with the
%data as well as differences in how the metrics are defined, collected
%and archived. For years, we have struggled with the data drought
%problem and have recommended elaborate feature subset selection
%methods to prune uninformative data~\cite{chen05,me06d}. Here, we take
%a radically different approach and explore the value of models that have
%not been tuned.

\section{Introduction}
Process models have many purposes including
estimating project parameters or conducting what-if queries to find better ways
to organize a project. Standard practice is to calibrate these models using local 
tuning data.
It can be quite difficult to access such data.
For example,
after 26 years of trying, we have only collected less
than 200 sample projects for the COCOMO database.
Also,
even after two years of effort we were only able to
add 7 records to a NASA-wide software cost metrics repository~\cite{me07f}.

There are many reasons for this ``data drought'' including data not
being collected or the business sensitivity associated with the
data, as well as differences in how the metrics are defined, collected
and archived. For years, we have struggled with the data drought
problem and have recommended elaborate feature subset selection
methods to prune uninformative data~\cite{chen05,me06d}. Here, we take
a radically different approach and explore the value of models that have
not been tuned.

Process models can be viewed
as a set of constraints between inputs and  output. In this view, tuning a model using local data
{\em constrains}
the model to reduce the  {\em variance} in the model output. 
It is useful to distinguish two classes of variables,
both of which are illustrated in the following
simplified COCOMO model:
\begin{equation}\label{eq:simp}
effort = a \cdot LOC^{b +  pmat}\cdot acap  
\end{equation}
Here, $a,b$ are {\em tuning parameters} that control the linear and exponential
effects (respectively) on model output.
These tuning parameters are adjusted using historical data.
On the other hand,
$pmat$ (process maturity) and $acap$ (analyst capability) are {\em project choices} that are adjusted by managers. 
Project choices are typically model inputs while tuning parameters typically control calculations
internal to the model.
Both classes of variables introduce variance into the estimates:
\bi
\item {\em Tuning variance:} 
variability in the tuning variables due to training data that is incomplete or noisy;
 \item {\em Project variance:}
variability in the project choices due to, say, uncertainty about the process maturity of the sub-contractors.
\ei
%This paper shows that the tuning variance is surprisingly high, even after applying historical data. 
%Since tuning variance remains an open issue, it  is prudent
%to  explore the effects
%of project choices.
Much research has explored tuning variance reduction (e.g.,\cite{boehm81,kemerer87,briand00,lum02,ferens98}).
In this paper, we take a different approach and ask
if estimation variance can be controlled by reducing {\em only} project variance.
Our tool in this study is SEESAW, an
AI search engine that 
conducts large scale what-if queries over software process models. SEEWAW
constrains  project choices, 
{\em but not
the tuning variance} in its search for options that 
reduce
effort, defects, threats, and development time 
estimates. 
The main result of this paper is that, at least for COCOMO/COQUALMO:
\begin{quote}
{\em The range of estimate errors seen after constraining the
project choices (but not the tuning variables)
is almost identical to the range seen after constraining just the
tuning variables. } 
\end{quote}
From a business perspective, this result means that certain process models can be used for decision making in one of two ways:
\be
\item 
{\em Either}
constrain the
tuning variance using historical data;
\item
{\em Or} constrain the project
choices using an AI search engine like SEESAW.
\ee
Note that this second method avoids a lengthy and expensive
data collection phase prior to decision making.
This result is of tremendous practical benefit since
it is often very difficult 
to find relevant data within a single organization to 
precisely tune all the internal parameters inside a process model.

%It is unknown if our results apply to software process models more
%complex than the COCOMO-style of models used in this study. However,
%our results to date suggest that our procedure should be applied
%to other process models:
%\bi
%\item find the key project choices  that most effect model output;
%\item constrain them;
%\item check for stable conclusions in the constrained space.
%\ei

Prior reports on our AI search methods~\cite{me07g,me07f}  were based on  limited case studies; here we report
ten new case studies showing that our main effect
holds in a wide range of cases.
Also, those prior reports
failed to check the validity of their results. The ten case studies
discussed below show that the distribution of SEESAWS's estimates  approximate those seen with
conventional methods,
despite being generated
from a large space of possible tunings.
This validity check greatly increases our confidence in the SEESAW method.

The rest of this paper describes how we arrived at our main result.
After a discussion of  related work,
we review the models used in this study
and the AI search engine that finds
useful constraints to project choices. This is followed by a description of an
experiment that compares the range of errors 
seen after constraining just the project choices (using SEESAW)
or just the
tuning variables (using linear regression).
In our future work, we explore the implications of this work for software process modeling:
if there exists a set of process models for which tuning is optional
then, where 
possible, we should favor the usage of such models.
\section{Related Work}
\eq{simp} described
a $model$ containing $tuning$
and $project$ parameters. 
Related work may be categorized
according to how they treat
($model,tuning,project$).
 \bi
 \item {\em Data Mining}:
Using different data mining techniques, generate a range of
$model$s.
\item {\em Prediction}:
 fix $model$ and $project$ and generates  fixed $estimates$.
 \item {\em Calibration}:
 import an  log of
 $estimates$ and $project$ variables, find
 changes to $model$ that best explain how $project$ inputs lead to $estimation$ outputs.
 \item {\em Monte Carlo} studies: generate estimates from
 one $model$ 
varying the $project$ choices. 
 \ei
 In the field of effort estimation:
 \bi
\item {\em Data mining} is useful when the exact best form of
the $model$ is unknown~\cite{me06d}.
 \item
 {\em Prediction} is used to create one point estimate for a project;
 e.g., COCOMO~\cite{boehm81,boehm00a},PRICE-S~\cite{park88} and 
 SEER-SEM~\cite{jensen83}.  
 \item
 {\em Calibration} is useful for learning from historical data; e.g., see Boehm's
 local calibration procedure~\cite[p526-529]{boehm81} 
 or the COSEEKMO toolkit~\cite{me06d}.
 \item
 {\em Monte Carlo} studies are useful for conducting what-if queries across a
 range of possible projects~\cite{raffo99}. Such Monte Carlo
 studies are conducted by many tools including
 COBRA~\cite{briand98},
 Crystal Ball~\cite{bailey02},
 SCAT~\cite{lum03handbook,lum05scat}, and
 2CEE~\cite{baker07}. 
 \ei
To the best of our knowledge, this work is the first to try controlling
 the $project$ variables while leaving the $tuning$ unconstrained. 
 Even in the field
 in {\em search-based software engineering}, we have not seen anything like
 this study. It is true that search-based SE often uses non-linear search
 methods like simulated annealing. A recent review of 123 search-based SE
 papers~\cite{rela04} showed that much of that work relates to testing
 (e.g., SA to minimize test suites for regression
 testing) while only a handful of those papers related to the kinds of early
 project process planning discussed here.  For example, Aguilar-Ruiz
 et.al.~\cite{aguilarevolutionary} and Alvarez
 et.al.~\cite{alvarez-data} apply search-based methods for effort
 estimation.  
One facet that distinguishes SEESAW from other methods is
 that we are searching over more than just the
 effort models explored by the 
 Aquilar-Ruiz \& Alvarez teams. 

Some researchers have explored estimation uncertainty using
a  Bayesian analysis.
For example,
Pendharkar et.al.~\cite{pendharkar05} demonstrate the utility of Bayes networks in effort
estimation while Fenton and Neil explore Bayes nets and defect prediction~\cite{fenton99}.
 Unlike this paper,
neither of these teams links defect models to effort models.
We elect to take a non-Bayesian approach since most of the industrial and government
contractors we work with use parametric models like
COCOMO. 

Other researchers use
Search-Based Software Engineering (SBSE) optimization techniques
and apply techniques taken from
operations research and meta-heuristic search (e.g., simulated annealing and genetic algorithms). 
Typically, SBSE hunts
for near
optimal solutions to complex and over-constrained
software engineering problems. 
This  approach has been applied to many
problems in software engineering (e.g., requirements engineering~\cite{jalali08b})
 but most often in the field of software testing~\cite{andrews07}.
Harmon's writing inspired us try simulated annealing to search the what-ifs in untuned COCOMO
models~\cite{me07f}. However, we found that SEESAW ran much faster and produced results with far less
variance than simulated annealing.


The process simulation community (e.g., Raffo~\cite{raffo05c}) studies
models far more elaborate than COCOMO or COQUALMO. 
For example, COCOMO \& COQUALMO assume linear parametric equations
while other researchers explore other forms:
\bi
\item
discrete-event models~\cite{law00,kelton02};
\item
system dynamics models~\cite{hamid91}; 
\item
state-based models~\cite{akhavi93,harel90,martin00};
\item
rule-based programs~\cite{mi90}; 
\item standard programming constructs
such as those used in Little-JIL~\cite{cass00,wise00}.
\ei
These rich modeling frameworks
allow the representation of 
detailed insights into an organization. However,  the effort required
to tune them is non-trivial. For example, Raffo spent two years
tuning and validation one such model to one particular site~\cite{raffo95}.

\section{Models Used in this Study}
\subsection{COCOMO, COQUALMO, THREAT}
The background to all our work are three USC 
software process models:
\bi
\item
The COQUALMO software {\em defect} predictor~\cite[p254-268]{boehm00b}.
COQUALMO models two processes (defect introduction and defect removal)
for three phases (requirements, design, and coding).  
\item
The COCOMO software {\em effort} and development {\em time} predictor~\cite[p29-57]{boehm00b}.  
COCOMO assumes that
effort is exponentially proportional to some {\em scale factors} and
linearly proportional to some {\em effort multipliers}.  COCOMO
estimates development months (225 hours) and calendar months and includes all coding,
debugging, and management activities.  \item
The THREAT predictor for  {\em project effort \& schedule
overrun}~\cite[p284-291]{boehm00b}. 
The THREAT model contains a
large set of two-dimensional tables like \fig{madeg} representing pairs of variable
settings that are problematic. For example, using the $rely$ vs $sced$
table, the THREAT model would raise an alert if our tool decides to
build a system with high $rely$ (required reliability) and low $sced$
(schedule available to the development).
\ei
\begin{figure}
{\scriptsize
\begin{center}
\begin{tabular}{|p{0.8in}|c|c|c|c|c|}\cline{2-6}
\multicolumn{1}{c|}{} &rely=&rely=&rely=&rely=&rely=\\
\multicolumn{1}{c|}{}& very & low &nominal & high & very\\
\multicolumn{1}{c|}{}&  low&  & &  &  high\\\hline sced= very
low& 0 & 0 & 0  &1  &2\\\hline sced= low     & 0 &0  & 0 &
0&1\\\hline sced= nominal& 0 & 0 & 0  &0  &0\\\hline sced= high&
0& 0 & 0  & 0 &0\\\hline sced= very high& 0 & 0 & 0  &0 &0\\\hline
\end{tabular}
\end{center}
} \caption{An example risk table}\label{fig:madeg}
\end{figure}

\noindent
From our perspective, these models have several
useful features:
\bi
\item
Unlike other models such as PRICE-S~\cite{park88}, 
SLIM~\cite{putnam92}, or SEER-SEM~\cite{jensen83},
the COCOMO family of models
is fully described in the literature. Also, at least
for the effort model, there exist  baseline results~\cite{chulani99}. 
\item
We work extensively with governemnt agencies writing software.
Amongst those agencies, these models are frequently used to generate
and justify budgets.
\item
The space of possible tunings within COCOMO \& COQUALMO
is well defined (see below). Hence, it is possible
to explore the space of possible tunings.
\item 
Even allowing for full variance in the tuning parameters,
the estimation variance of COCOMO
can be reduced via intelligent selection of input variables.
We would consider switching to other models if it could
be shown that the variance of these other models could be
controlled just as easily.
\ei



\begin{figure}[!t]
\begin{center}
{\scriptsize
\begin{tabular}{p{3cm}|r@{:~}l|c|c|}
\multicolumn{3}{c}{~}&strategic?&\multicolumn{1}{|c}{tactical?}\\\cline{2-5}
scale   &prec & have we done this before?&\ding{51}&\\
factors &flex & development flexibility &&\ding{51}\\
(exponentially        &resl & any risk resolution activities?&&\ding{51}\\ 
decrease       &team &  team cohesion&&\ding{51}\\ 
effort)       &pmat & process maturity&\ding{51}&\\\hline 
upper  &acap & analyst capability&\ding{51}&\\
(linearly       &pcap & programmer capability&\ding{51}&\\ 
decrease      &pcon & programmer continuity&\ding{51}&\\
effort)       &aexp &  analyst experience&\ding{51}&\\       
&pexp &  programmer experience&\ding{51}&\\       
&ltex &  language and tool experience&\ding{51}&\\       
&tool &  tool use&&\ding{51}\\       
&site &  multiple site development&\ding{51}&\\       
&sced & length of schedule  &&\ding{51} \\\hline 
lower &rely &    required reliability && \\
(linearly      &data &   secondary memory  storage requirements&&\ding{51}\\
increase      &cplx &  program complexity&&\ding{51}\\
effort)      &ruse &  software reuse&&\ding{51}\\      
&docu &   documentation requirements&&\ding{51}\\      
&time &   runtime pressure&&\\      
&stor &   main memory requirements&&\ding{51}\\     
&pvol &    platform volatility  &&\\\hline
COQUALMO &auto& automated analysis&\ding{51}&\ding{51}\\
defect removal&execTest & execution-based testing tools&\ding{51}&\ding{51}\\
methods&peer& peer reviews&\ding{51}&\ding{51}\\\cline{2-5}
\end{tabular}}
\end{center}
\caption{The variables of COCOMO, COQUALMO, and the THREAT model.}\label{fig:emsf2}
\end{figure}

\fig{emsf2} shows the project choices within COCOMO / COQUALMO / THREAT.
The last two columns of this figure
show the results of a Delphi panel session at the
Jet Propulsion Laboratory where the COCOMO variables
were separated into:
\bi
\item the $tactical$ variables
that can be changed within the space of one project;
\item
the  $strategic$ variables
that require higher-level institutional change (and so may take
longer to change).
\ei
For example, the panel declared that $pmat$ (process maturity)
is hard to change within the space of a single JPL project. 
Note that these definitions of $strategic$ and $tactical$ choices
are not hard-wired into our system. 
If a user disagrees with our definitions of
strategic/tactical, they can change a simple configuration file.


\subsection{Example Projects}


\begin{figure}[!t]
\begin{center}
\scriptsize
\begin{minipage}{.45\linewidth}\begin{tabular}{c|lrr|lr}
       &\multicolumn{3}{c|}{float}      &\multicolumn{2}{c}{fixed}\\\hline
project&variable&low&high&variable&setting\\\hline
&prec&1&2&data&3\\
OSP&flex&2&5&pvol&2\\
&resl&1&3&rely&5\\
&team&2&3&pcap&3\\
&pmat&1&4&plex&3\\
&stor&3&5&site&3\\
&ruse&2&4&&\\
&docu&2&4&&\\
&acap&2&3&&\\
&pcon&2&3&&\\
&apex&2&3&&\\
&ltex&2&4&&\\
&tool&2&3&&\\
&sced&1&3&&\\
&cplx&5&6\\
&KSLOC&75&125\\
\hline
&prec&3&5&flex&3\\
OSP2 &pmat&4&5&resl&4\\
&docu&3&4&team&3\\
&ltex&2&5&time&3\\
&sced&2&4&stor&3\\
&KSLOC&75&125&data&4\\
&&&&pvol&3\\
&&&&ruse&4\\
&&&&rely&5\\
&&&&acap&4\\
&&&&pcap&3\\
&&&&pcon&3\\
&&&&apex&4\\
&&&&plex&4\\
&&&&tool&5\\
&&&&cplx&4\\
&&&&site&6
\end{tabular}
\end{minipage}~~~~~~~~\begin{minipage}{.45\linewidth}
\begin{tabular}{c|lrr|lr}
       &\multicolumn{3}{c|}{float}      &\multicolumn{2}{c}{fixed}\\\hline
project&variable&low&high&variable&setting\\\hline
&rely&3&5&tool&2\\
 &data&2&3&sced&3\\
flight&cplx&3&6&&\\
&time&3&4&&\\
&stor&3&4&&\\
&acap&3&5&&\\
&apex&2&5&&\\
&pcap&3&5&&\\
&plex&1&4&&\\
&ltex&1&4&&\\
&pmat&2&3&&\\
&KSLOC&7&418&&\\
\hline
&rely&1&4&tool&2\\
 &data&2&3&sced&3\\
ground&cplx&1&4&&\\
&time&3&4&&\\
&stor&3&4&&\\
&acap&3&5&&\\
&apex&2&5&&\\
&pcap&3&5&&\\
&plex&1&4&&\\
&ltex&1&4&&\\
&pmat&2&3&&\\
&KSLOC&11&392&&\\
\multicolumn{5}{c}{~}\\
\multicolumn{5}{c}{~}\\
\multicolumn{5}{c}{~}\\
\multicolumn{5}{c}{~}\\
\multicolumn{5}{c}{~}\\
\multicolumn{5}{c}{~}\\
\multicolumn{5}{c}{~}\\
\multicolumn{5}{c}{~}\\
\multicolumn{5}{c}{~}
\end{tabular}
\end{minipage}
\end{center}
\caption{Four case studies.}\label{fig:cases}
\end{figure}

\fig{cases} summarizes four NASA case studies using the project choices of \fig{emsf2}:
\bi
\item ``OSP'' is the GNC (guidance, navigation, and control)
component of NASA's 1990s {\em Orbital Space Plane}; 
\item ``OSP2'' is a later version of OSP;
\item ``Flight'' and ``ground'' show typical ranges of NASA's Jet Propulsion Laboratory. 
\ei
Inside our model,
project choices typically range from
1 to 5 where ``3'' is the nominal
value that offers no change to the default estimate. 
Some of the project choices in \fig{cases}
are known precisely (see all the choices with single {\em values}).
But  many of the features in \fig{cases} do not
have precise values
(see all the features that {\em range} from some {\em low} to {\em high}
value).  

Sometimes the ranges of choices
are very narrow (e.g., the process maturity of JPL ground software is between 2
and 3), and  sometimes the ranges are very broad.
\fig{cases} does not mention all the  features listed in \fig{emsf2}
inputs.  For example, our defect predictor has inputs for
use of {\em automated analysis}, {\em peer
reviews}, and {\em execution-based testing tools}. During SEESAW's search,
for all project choices
not mentioned in \fig{cases}, values are picked at random from the full
range of \fig{emsf2}.


\subsection{Defining  the Space of Possible Tunings}
Many of our project choices have a linear relationship
to the output. Such linear relations form the
line
$y=mx+b$ with slope ``$m$''
passing through point $x=3,y=1$; i.e., at the nominal value of ``3'',
there are no changes to the effort estimate.  
Such a line has a y-intercept
of $b=1 - 3m$. Substituting this value of $b$ into $y=mx+b$ yields:
\[\footnotesize\begin{array}{l}
estimate = m(x-3) + 1
\end{array}\]
Over the 
history of the COCOMO project, 
it has been observed that all the linear parameters that increase/decrease
effort have the following slopes:
\begin{equation}\label{eq:cocc1}\footnotesize \begin{array}{c|c}
 increasing\; effort & decreasing\; effort\\\hline
0.073 \le m \le 0.21& -0.178 \le m \le -0.078
\end{array} \end{equation}

Similarly, the linear relations in the
COQUALMO defect model linear relationships
fall within very narrow slopes:
\begin{equation}\label{eq:cocc}\footnotesize \begin{array}{l|c|c}
phase & increasing\; defects & decreasing\; defects\\\hline
requirements&
0 \le m \le 0.112& 
-0.183 \le m \le -0.035\\
design &
0 \le m \le 0.14&
-0.208 \le m \le -0.048\\
coding & 
0 \le m\le  0.14 &
-0.19 \le m \le -0.053\\
\end{array} \end{equation}
Like COCOMO, COQUALMO also includes scale factors that affect
the estimates exponentially. These scale factors
hinge about
the origin and have the following slopes:
\begin{equation}\label{eq:coq}
\footnotesize
\begin{array}{l|c}
 phase & defect\; removal\\\hline
 requirements& 0.08 	\le m \le 0.14 \\
design	& 0.1 	\le m \le 0.156 \\
 coding & 0.11 	\le m \le 0.176 \\
\end{array}\end{equation}
Clearly,  it is possible
to sample the space of all known COCOMO / COQUALMO tunings by picking
random $m$ values from \eq{cocc1}, \eq{cocc}, and \eq{coq}.

 To sample across the space of THREAT tunings, another mechanism is required.
Tables like
\fig{madeg} can be represented as
an exponentially decaying function that peaks in one corner of the risk table
at a value between two to four. 
Since this model is heuristic in nature, the exact height of the peak is
not certain.
When we perform tuning samplings over THREAT, we vary the height of
the peak by 
a random factor $0.5 \le x \le 1$ if the peak is four, and $0.5 \le x \le 1.5$ if the peak is two.
 
\section{Searching over Tuning Variables with Local Calibration}

This paper compares estimates generated in two ways. This section describes local calibration (LC),
the standard regression procedure used by the COCOMO
community. Later, we will compare LC's results with those from SEESAW.

LC assumes that a  matrix $D_{i,j}$ 
holds:
\bi
\item
The natural log of the
$LOC$ (lines of code) estimates;
\item
The natural log of  the actual efforts
for each project $j$;
\item
The  natural logarithm of the cost drivers (the scale factors
and effort multipliers) at locations $1\le i \le 15$ (for COCOMO 81)
or $1 \le i \le 22$ (for COCOMO-II).
\ei
With those assumptions, Boehm~\cite{boehm81} shows that
for COCOMO 81,
the following calculation yields estimates
for ``$a$'' and ``$b$'' that minimize the sum of the squares of residual
errors:
\begin{equation}\label{eq:ab}{\scriptsize
\left.
\begin{array}{rcl}
EAF_i& =& \sum_j^N D_{i,j}\\
a_0  & =& t \\\
a_1  & =& \sum_i^t KLOC_i\\
a_2  & =& \sum_i^t (KLOC_i)^2\\
d_0  & =& \sum_i^t \left(actual_i - EAF_i\right)\\
d_1  & =& \sum_i^t \left((actual_i - EAF_i)*KLOC_i\right)\\
b  & =& (a_0d_1 - a_1d_0)/(a_0a_2 - a_1^2)\\
a_3    & =& (a_2d_0 - a_1d_1)/(a_0a_2 - a_1^2)\\
a    & =& e^{a_3}
\end{array}\right\}}
\end{equation}
In the case of COCOMO-I~\cite{boehm81} these $a,b$ values are used in the following equation to generate
effort estimates. In this equation, $EM_i$ are the effort multipliers from \fig{emsf2}:
\[\scriptsize effort = a \cdot KSLOC ^ b \cdot \prod^{15}_i EM_i\]
What is not widely appreciated is the size of
the
variance in the $(a,b)$ values.
The left-hand-side of
\fig{dan}  shows the COCOMO-I $(a,b)$ values learned by   Baker~\cite{baker07}
after, 300 times, extracting 10 projects at random from COCOMO data sets,
then applying \eq{ab} to the remaining data.  
The data sets used in this study contained 93 projects, so LC was applied
to  $\frac{93-10}{93}=89\%$ of the data.
A pre-experimental intuition was that we were using enough of the data to yield stable $(a,b)$ values. As can be clearly seen by the wide
variance on the $(a,b)$ values in \fig{dan},
this was not the case.
\begin{figure}[!h]
\begin{center}
\includegraphics[width=2.4in]{nasa93_300.pdf}\includegraphics[width=2.4in]{comparesReport_lc.pdf}
\end{center}
\caption{Results of
applying
LC numerous times to 90\%
of the NASA93 data sets (available from \protect\url{http://promisedata.org/data}).
Left-hand-side shows computed $(a,b)$ values. Right-hand-side shows MREs generated
in 20 repeats
over the NASA93 data set.
}\label{fig:dan}
\end{figure}

The right-hand-side of
\fig{dan} shows the magnitude of the relative error (or $MRE$)
values 
seen in Baker's study (MRE is a standard measure in the effort estimation field
as follows:
$MRE=\frac{abs(actual - predicted)}{actual}$). 
In the sequel, we will refer to Baker's results as MRE1. 

Some of the MRE1 errors
are very large (up to nearly 500\%)
suggesting that LC was incomplete or that the variance in the $(a,b)$ calculations  have significant impact on the estimation.
Note that this right-hand-side figure  is not without precedent in the estimation literature:
it is a well-established result that  initial development effort estimates may be incorrect
by a factor of four~\cite{boehm81} or even more~\cite{kemerer87}.


Elsewhere we have been partially successful in
reducing estimation variance
of \fig{dan}
using feature subset selection (FSS)~\cite{chen05,me06d}
or more data collection.
Unfortunately,
FSS reduces but does not eliminate the $a,b$ variance. Also, further
data collection is possible, but only at great organizational expense. 
Since we failed to generate precise tunings that yield exact estimates, we considered
a change  in our research goals. 
Perhaps, we argued, it was time to explore the space of possible tunings.
This line of thinking led to the SEESAW search engine.


%% %% Alexei Lapouchnian, Yijun Yu, John Mylopoulos: Requirements-Driven Design and Configuration Management of Business Processes. BPM 2007: 246-261
%% %% exploring goal graphs

%% %% Yuan An, John Mylopoulos, Alexander Borgida: Building Semantic Mappings from Databases to Ontologies. AAAI 2006
%% %% golog framework

\section{Searching over Project Choices with SEESAW}

SEESAW seeks the smallest set of project choices that minimizes a score
function that combines 
COCOMO's effort $Ef$ and time $Ti$ predictions;
the COQUALMO defect $De$ predictions; and the THREAT $Th$ prediction.
SEESAW normalizes these scores 0..100 then seeks ways to minimize the following combination
of the normalized scores:
\begin{equation}\label{eq:score}
 \sqrt{Ef^2 + Ti^2 + Th^2 + De^2} 
\end{equation}
(This is  
the Euclidean distance to minimum values for effort, time, threats, and defects.)

%// constrains ATTRIBUTE to a single RANGE and generates a score
\fig{MWF} shows SEESAW's pseudo-code. 
Before exploring the
low-level details of the algorithm (as done below),
we first remark about the main purpose of the code.
While SEESAW
staggers over the space
of possible tunings (see 
Equations \ref{eq:cocc1}, \ref{eq:cocc}, and  \ref{eq:coq}) 
and project choices (as defined by \fig{cases}),   it only constrains project choices (and not tuning variables).  
In this sense, SEESAW is the {\em opposite} of LC in that
the latter makes
 no
comment on the project choices. Rather, LC just proposes constraints
to two tuning variables.

SEESAW is an adaption
of Kautz \& Selman's MaxWalkSat local search procedure~\cite{kautz97}. 
Each solution  is scored via a Monte Carlo  procedure (see {\tt score} in \fig{MWF}), and
SEESAW seeks to {\em minimize} that score (since, for our models, it is some combination of
defects, development effort, development time, and threats).


SEESAW
first combines the ranges for 
all the COCOMO project choices
with the known project constraints of \fig{cases}.
These constraints 
range from $Low$ to $High$ values.
If a case study does not mention a project choice, then there
are no constraints on that choice, and the $combine$ function (line 4)
returns the entire range of that choice. Otherwise, $combine$
returns only the values from $Low$ to $High$.

\begin{figure}[!t]
~\hrule~
{\scriptsize
\begin{alltt}
 1 {\bf function} run (AllRanges, ProjectConstraints) \{
 2   OutScore = -1
 3   P = 0.95
 4   Out = combine(AllRanges, ProjectConstraints)
 5   Options = all Out choices with ranges low < high
 6   {\bf while} Options \{
 7     X = any member of Options, picked at random
 8     \{Low, High\} = low, high ranges of X
 9     LowScore = score(X, Low)
10     HighScore = score(X, High)
11     {\bf if} LowScore < HighScore
12       {\bf then} Maybe = Low; MaybeScore = LowScore
13       {\bf else} Maybe = High; MaybeScore = HighScore
14     {\bf fi}
15     {\bf if} MaybeScore < OutScore {\bf or} P < rand()
16       {\bf then} delete all ranges of X except Maybe from Out
17         delete X from Options
18         OutScore = MaybeScore
19     {\bf fi}
20   \}
21  {\bf return} backSelect(Out)
22 \}
23 {\bf function} score(X, Value) \{
24   Temp = copy(Out)  ;; don't mess up the Out global 
25   from Temp, remove all ranges of X except Value 
26   run monte carlo on Temp for 100 simulations, scoring each run using Equation 3.
27   {\bf return} median score of the 100 
28 \}
\end{alltt}
}
~\hrule~
\caption{Pseudocode for SEESAW.}
\label{fig:MWF}
\end{figure}
In the case where a choice is $fixed$ to a single
value, 
then $Low = High$. Since there is no decision to be made for this
choice, SEESAW ignores it. The algorithm
 explores only those
 choices with a range of $Options$ where
 $Low < High$ (line 5).
In each iteration of the algorithm, it is possible that one acceptable value
for a choice $X$ will be discovered. If so, the range for $X$
is reduced to that single
value, and the choice is not examined again (line 17).

SEESAW prunes the final  recommendations (line 21).
This function removes the $N$
selections added last that do not significantly change the final score (t-tests, 95\% confidence). This culls
any final irrelevancies in the selections.

The $score$ function shown at the bottom of
\fig{MWF} calls COCOMO / COQUALMO / THREAT models 100 times,
each time selecting:
\bi
\item
Random values for the project choices (from the  $Options$ set);
\item 
Random values for the tuning variables (as described 
in Equations \ref{eq:cocc1}, \ref{eq:cocc}, and  \ref{eq:coq}).
\ei
The median value
of the \eq{score} values seen in these runs  is the $score$ for those project choices. As SEESAW executes,
the ranges in $Options$ are removed and replaced by single values (lines 16-17),
thus constraining the space of possible simulations.


SEESAW was designed after observing experimentally
that
the most interesting ranges in $Options$
are generally the minimum and maximum values.  The reason for this is simple:
All the functions in COCOMO / COQUALMO / THREAT are  monotonic, causing
the most dramatic effects to occur at the extreme ends of the ranges.
In fact,
SEESAW takes its name from the way earlier versions
of this  algorithm tended to seesaw between extreme values.
We have conducted experiments with other approaches that allow
intermediate values.
On comparison with the simulated annealing method used
in a prior publications~\cite{me07f}, we found that
seesawing between
$\{Low,High\}$ values was adequate for our purposes.

SEESAW is a stochastic algorithm:
the selection of the next choice to explore is completely random (line 7).
We use this stochastic approach
 since much research from the 1990s showed the benefit of such search methods.
Not only can stochastic algorithms solve non-linear problems and escape from local minima/maxima, 
but they can also find solutions faster than complete search, and for larger problems~\cite{motwani95}.
For example, we have implemented a deterministic version of SEESAW that
replaces the random selection of {\em one} choice in line 7 with a search
through {\em all} choice for
the best $\{Low,High\}$ value.  That algorithm ran much slower (runtimes were 12 times greater)
with nearly identical results to those of the stochastic search. Crawford and Baker~\cite{crawford94} offer one explanation for the strange success of stochastic search.
For models
where the solutions are a small part of the total space, a complete search
wastes much time exploring uninformative areas of the problem. A stochastic search, 
on the other hand, does not get stuck in such  uninformative areas.

%SEESAW incrementally grows solutions
%from unconstrained (where all choices can take any value in $\{Low,High\}$)
%to fully constrained (where all choices are set to a single value).
%This is unlike
%simulated annealing or MaxWalkSat, which simultaneously offer settings to all choices
%at every step of their reasoning.
%\fig{run} shows a single run of SEESAW: each dot marks one selection  (lines 16,17,18 of \fig{MWF}).
%In our terminology, selecting  one value from a range  is a {\em decision} on all  
%values in the range. For example, if \fig{cases} includes a process maturity of (3,4,5)
%and SEESAW selects ``5'', then that is three decisions.
%(this is why the 29 dots of
%\fig{run} result in 100 decisions).
%Note how, as decisions are made, the score is minimized. Score minimization is desirable since
%our scores
%are calculated 
%from  a combination of project predictions that we want to reduce 
%(total effort, defects, development time). 
%\begin{figure}
%\centering
%\includegraphics[width=3in]{default.pdf}
%\caption{Single run of SEESAW, score normalized min..max to 0..1}
%\label{fig:run}
%\end{figure}
%
%Incremental decision making  is an important property of SEESAW.
%Observe how, in 
%\fig{run},
%50\% of the score reduction
%arises from around 15\% of the decisions.
%If a manager cannot implement all SEESAW's recommendations and a 50\% reduction
%is adequate,
%she might elect to  use just these top 15\% decisions.
%That is, SEESAW not only makes $R$ recommendations, it also reports on the value of
%just applying just some subset of $r \subseteq R$.
%
%
%In order to support incremental decision making, SEESAW uses
%a very large $P$ value to control its reasoning.   This
%$P$ value is used to delay ``lose-lose'' decisions until the
%later iterations of the algorithm.  Suppose our search has only constrained (say)
%$pcap=5$ so far.  Our next randomly chosen choice might be  $data$,
%so SEESAW tries $\{Low, High\}$ values of $data=2$ and
%$data=5$.  It is possible that both of these values will result in scores
%that are worse than the current score (using $pcap=5$ alone).
%This means that
%$data$ is not a valuable choice to control,
%and picking either of the $\{Low,High\}$ values would be a ``lose-lose'' decision.
%Using $P=0.95$,
%SEESAW will very likely (95\% of the time) leave $data$ unconstrained
%and pick another, potentially better,  choice to constrain on the next iteration.  The algorithm
%will eventually come back to $data$, but if SEESAW delays making
%that lose-lose decision, it has a better chance of making good
%decisions early in the search.
%
%.
\section{Experiments}
In terms of trusting SEESAW, the key question is how much SEESAW"S estimates differ from those generated by conventional methods such as LC.
To implement that comparison, we followed the procedure shown on the right-hand-side of \fig{design}.
\be
\item Two kinds of control policies were explored; i.e., the strategic and tactical choices marked
in \fig{emsf2}.
\item Five kinds of projects were created; i.e., the four projects
from \fig{cases} and one using an imaginary
project whose project choices included the entire range of all COCOMO variables.
\item
For these 2*5=10 case studies, we ran SEESAW to find the constraints that led
to minimum effort, threats, defects, and development time. 
\item
From each of the 10 sets of constraints,
we generated projects consistent with those constraints.
\item
Estimates were then added to the above randomly generated projects.
Each estimate was the median value seen in 1000 simulations  
% SCW: The data I generated for Ous had 1000 iterations of SEESAW for each case study.  Is that what this number is referring to?
% TM: yes
 of SEESAW's {\tt score} function (see line 23 of \fig{MWF}). 
That is, these estimates were generated from constrained project choices but unconstrained tuning variables.
\item
SEESAW's predicted effort estimates were then compared to those generated by conventional means;
i.e., LC learning on NASA93, then applied to the projects generated from the constraints
found by SEESAW.
\item The delta in SEESAW's and LC's estimates was computed using
$\Delta=\frac{abs(SEESAW - LC)}{SEESAW}$.  
\item
Steps 4, 5, 6, and 7 were repeated 20 times to generate the set ``MRE2''.
\ee

\fig{mre2} shows the sorted MRE2 values for 10 sets of projects (one line for each project).
The median deltas $\Delta$ seen in these ten cases studies
runs were \[
\Delta=\frac{abs(SEESAW -LC)}{SEESAW} =\{20,20,21,22,23,23,23,23,24,24,26\}\%
\]
We explain the small median delta as follows:  
the project choices found by SEESAW forced this process model
into a narrow space of behaviors. In this narrow space, the impact of the tuning variance
becomes unimportant.

\begin{figure}[!t]
\begin{center}
\includegraphics[width=4.5in]{experiment.png}
\end{center}
\caption{Experimental design.}
\label{fig:design}
\end{figure}

But there is a problem with this claim that a delta $\Delta$ value of 20 to 26 
is a ``small delta.''
Any claim that that X\% is ``small'' is spurious unless we have some other study that says ``in conventional
estimation, it is uncommon to see variance smaller than this.''
Accordingly, we return to the Baker's LC results.
\fig{mre2} displays the Baker results (MRE1: left-hand-side) and the  delta $\Delta$ values generated above
(MRE2: right-hand-side). A visual inspection shows
that the MREs generated via local calibration (MRE1)
are mostly the same size as the  the differences seen between LC's and SEESAW's predictions (MRE2).
Indeed, in a small number of cases, the MRE1 values are much larger values (see the spike, right-hand-side
of the MRE1 distribution).

\begin{figure}[!t]
\begin{center}
\includegraphics[width=2.4in]{comparesReport_lc.pdf}\includegraphics[width=2.4in]{comparesReport_star.pdf}
\end{center}
\caption{MRE2 results for \protect\fig{design}, for
ten case studies (one study per line).
The MRE1 results (left-hand-side) come from Figure 1.
}\label{fig:mre2}
\end{figure}
For the sake of completeness, we performed a statistical difference test on the MRE1 and MRE2 distributions: 
\bi
\item Since we are comparing distributions, paired tests were deemed  inappropriate. 
\item Since \fig{dan} and \fig{mre2} have a small number of large outliers, tests that make a Gaussian assumption
were also deemed inappropriate.
\item
Therefore, we compared \fig{dan} (right-hand-side) with the ten distributions 
of \fig{mre2} using Mann-Whitney tests. At the 99\% confidence level,
the distributions were indistinguishable in five out of ten of our experiments.
\ei
This test confirms our visual impression: the MRE1 distributions (obtained by controlling the tuning
variables)  are not always greatly different to MRE2 distributions (obtained without controlling the tuning
variables).

These results do {\em not} say that SEESAW produces the same estimates
as LC.  Clearly, SEESAW's Monte Carlo approach to estimation does introduce
some ``jitter'' into the estimates. The question is, is that jitter significantly large?
We would argue that it is not significantly large.
As mentioned above, the constraints on the project choices learned by SEESAW have forced
these models into a narrow space of behaviors. In that narrow space, the impact
of the tuning variance becomes unimportant:  
\bi
\item \fig{mre2} shows visually that 
that the jitter associated
with SEESAW (MRE2) is close to, and sometimes smaller than, the
jitter produced by merely changing the training sample by 10\%
(MRE1).
\item Our Mann-Whitney tests confirm this visual impression.
\ei
We conclude that the estimates generated after constraining project
choices (using SEESAW) are no more varied than the estimates
generated after constraining tuning variables (using LC). 


%\section{Discussion}
%How are we to  explain the remarkable effectiveness of SEESAW in
%managing uncertainty?
%Researchers in planning and theorem proving have
%recently shown that as model complexity grows, other constraining
%effects may appear such as ``master variables''; i.e. a small number
%of settings that control all other
%settings~\cite{crawford94,williams03}. Such master variables can
%greatly reduce the search space within large models.  
%
% We hypothesize that software process models also contain master variables;
%i.e. much 
% much of uncertainty in a model is due to the influence of a 
%small subset
%of model variables. If so, then after (a)~ranking variables
%by their ability to constrain the output; and
%(b)~applying a small number of the top-ranked variables;
%then 
%it should be possible to (c)~make
%stable predictions
%in the constrained space.
\section{Conclusion}

In prior studies with the
COCOMO / COQUALMO / THREAT models,
we have shown that 
an AI search engine can find a minimal set of constraints to project choices that
reduce  estimates for project effort, defects, time, and
threats~\cite{me07g,me07f}.  Those results were based on limited
case studies and failed to check the validity of the estimates.

In this report, we showed in ten case studies that the deltas
between ranges of estimates generated by SEESAW (without constraining
the tuning variables) form a similar distribution to those found
by traditional estimation methods (that constrain the tuning
variables). In fact, in half our experiments, there was no statistically
significant delta between the two distributions.
From a technical perspective, this means that  if estimation
variance arises from a tuning variance $T$ and project variance
$P$, then  there exists process models such as COCOMO / COQUALMO where $P \gg T$;
i.e., project choices
dominate tuning options.  

When $P \gg T$,
the estimates found by constraining project choices
will be close to estimates found via tuning on historical data.
For such models,
tuning is optional and
decision making need not wait for detailed local data collection.

\section{Future Work}

This work could lead to a 
``Goldilocks'' principle for process modeling:
\bi
\item
Very small models offer trite conclusions that are insensitive to important project features. 
\item
Very large models need extensive data collection to tune their internal structures. 
\item 
In between there may exist some models that are   ``just right'';
i.e., big enough to make interesting conclusions,
but small enough such that the internal tuning variance does not dominate
the variance results from input project choices.
\ei

We have presented here evidence that the COCOMO / COQUALMO / THREAT models are ``just right'';
i.e.,
their variance   can be reduced by constraining the project choices while leaving
the tuning variables unconstrained.

We make no claim that {\em all} process models are ``just
right'' and, hence, can be controlled by SEESAW.
Indeed, we suspect
that many process models may not be  near the right size.  However
(and this is the main point of this paper), what kind of process
model should be used? We would argue, that for data-starved domains,
we should {\em deliberately select} for ``just right'' process
models.

Based on the above, the future direction of this research is clear:
for data-starved domains, derive better design principles for process
models.  Our intuition is that this will be a search problem and
that tools like SEESAW will not only be useful for searching a fixed
model, but also for finding  revisions to current models in order
to make them ``just right''.

\bibliographystyle{plain}
\bibliography{refs}
%% \newpage
%% \appendix
%% \section{Simulated Annealing}
%% A {\em Monte Carlo} algorithms randomly sample the space
%% of possible controllable model states. 
%% A  {\em Metropolis} Monte Carlo algorithm~\cite{metropolis53}
%% creates new states
%% by  small mutations to some
%% {\em current} state. 
%% If a new state is ``better'' (as assessed via an
%% {\em energy function}),  it becomes the new {\em current}
%% state used  for future
%% mutations.  Otherwise, a Boltzmann acceptance
%% criteria is used to probabilistically decide to
%% assess the new state: the worse the new state, the less
%% likely that it becomes the new current state.
%% The algorithm is silent on the mutation mechanism.
%% In our implementation of this algorithm, we only randomized $\frac{1}{3}$ of the
%% attributes being sampled during each iteration of the algorithm. Note that
%% the attributes being randomized are different for consecutive iterations.

%% In 1983, Kirkpatrick et.el.~\cite{kirkpatrick83} 
%% proposed a modification that was
%% inspired
%% by a procedure used to make the strongest possible glass. Initially,
%% glass is heated to allow atoms to move freely. The temperature
%% is then slowly lowered such that the atoms can find the stablest
%% configuration with lowest energy. 
%% A {\em simulated annealing} (SA) algorithm adds
%% a ``temperature'' variable to the Boltzmann accept criteria
%% such that, at high temperatures, it is more likely that the
%% algorithm will jump to a  new worst current state.
%% This allows the algorithm to jump out of local minima while
%% sampling the space of options. As the temperature cools,
%% such jumps become less likely and the algorithm reverts
%% to a simple hill climber.

%% Formally, the acceptance criteria $P$ for a new state is defined using
%% the current temperature $T$, 
%% the energy of the current solution ($e$),
%% and the energy of the new mutation ($en$):
%% \begin{equation}\small
%% P(e,en,T) = e^{(e -en)/T}
%% \end{equation}
%% $T$ is defined to $decrease$ as the simulator loops through $k= 1\ldots kmax$ iterations.
%% We use
%% $T = e^{-100*k/kmax}$, where $kmax$ used in our implementation is 1000, which is a number of iterations determined to produce stable solutions in our implementation of the algorithm and for our intents and purposes.

%% The following pseudo-code {\tt sample} describes our simulated
%% annealer. 
%% A new solution $sn$ (with new energy $en$) replaces the current solution                                  
%% if (a)~it has a lower energy or (b)~the acceptance predicate $P$
%% endorses it. Only in the case of (a)
%% should the new solution
%% replaces the current best solution.

%% {\scriptsize\begin{verbatim}
%% function sample 
%%   s := s0; e := E(s)                       // Init state, energy.
%%   for t in 1 to tmax                       // temperature control
%%   do   sn = randomly change 1/3 of 's'     // Pick neighbor.
%%        en := E(sn)                         // Compute energy.
%%        for x in sn   
%%             out[x] += en                   // record project settings
%%        if P(e,en,temp(t/tmax)) > random()  // is it better?
%%        then 
%%              s := sn;                      // new solution
%%              e := en                       // new best energy
%%   done                                		 
%%   return out, sorted ascending  by en
%% \end{verbatim}}

%% The {\tt sample} function returns an array whose keys are the $Project$
%% settings and the values are the sum of the energies seen when that
%% setting was used. This array is sorted in increasing order so
%% the first entries were associated with lower (and better) energies while
%% the later entries are associated with higher (and less desirable) energies.

%% The {\tt rank} function  takes this array and experiments with 
%% using just the first $I$ items:

%% {\scriptsize\begin{verbatim}
%% function rank(order)
%%    for I in order
%%    do  cache=();                           // clear old results
%%        for n = 1 to 1000
%%        do  sn = random settings            // pick anything at all
%%       	    for j = 1 to I                  // insert the first I things
%%                sn[I] = order[I]
%%            cache[n]= E(sn)                 // score it
%%        done
%%        sort cache                          // sort
%%        print  cache[500]                   // print 50% (median)
%%        print  (cache[750] - cache[500])    // print 75% (spread)
%%    done
%% \end{verbatim}}
%% By plotting the {\tt print} statements in {\tt rank}, \fig{u} is generated.



\end{document}
This is not
to say that local tuning should not be attempted. Indeed, our strong view is that the preferred option is to use
precisely tuned models. However, in domains where sufficient tuning data
is unavailable, we recommend our AI search.

That is,
project choices dominate over tuning variables. 
that, at least for these models, decision making from process models
does not necessarily require tuned models.
.
it is possible to make decisions about
process models tuning to historical data is 
tame tuning variance.

\bi
\item The 
constrained project choices to reduce effort, 
defects, threats, and development time
estimates. For the models we explored, reducing
median estimates also reduces the variance. 
After constraining only the project choices (but not the tuning parameters),
we show that,
it is possible to constrain project choices such that 
estimation variance is ``quite low''.
We offer
\be
\item Tuning variance is surprisingly large;
\item Despite this tuning variance,
\ee
To be precise,  in ten experiments where we constrained project choices,
the range of estimation error due to project variance and tuning variance were  {\em almost the same} in $\frac{7}{10}$
experiments and {\em statistically insignificantly different} in the remaining $\frac{3}{10}$ experiments.  

end{document}
