% This is "sig-alternate.tex" V1.7 MARCH 2007
% This file should be compiled with V2.1 of "sig-alternate.cls" MARCH 2007
%
% This example file demonstrates the use of the 'sig-alternate.cls'
% V2.1 LaTeX2e document class file. It is for those submitting
% articles to ACM Conference Proceedings WHO DO NOT WISH TO
% STRICTLY ADHERE TO THE SIGS (PUBS-BOARD-ENDORSED) STYLE.
% The 'sig-alternate.cls' file will produce a similar-looking,
% albeit, 'tighter' paper resulting in, invariably, fewer pages.
%
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V2.1) produces:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) NO page numbers
%
% as against the acm_proc_article-sp.cls file which
% DOES NOT produce 1) thru' 3) above.
%
% Using 'sig-alternate.cls' you have control, however, from within
% the source .tex file, over both the CopyrightYear
% (defaulted to 200X) and the ACM Copyright Data
% (defaulted to X-XXXXX-XX-X/XX/XX).
% e.g.
% \CopyrightYear{2007} will cause 2007 to appear in the copyright line.
% \crdata{0-12345-67-8/90/12} will cause 0-12345-67-8/90/12 to appear in the copyright line.
%
% ---------------------------------------------------------------------------------------------------------------
% This .tex source is an example which *does* use
% the .bib file (from which the .bbl file % is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission, you *NEED* to 'insert'
% your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% ================= IF YOU HAVE QUESTIONS =======================
% Questions regarding the SIGS styles, SIGS policies and
% procedures, Conferences etc. should be sent to
% Adrienne Griscti (griscti@acm.org)
%
% Technical questions _only_ to
% Gerald Murray (murray@acm.org)
% ===============================================================
%
% For tracking purposes - this is V1.7 - MARCH 2007

\documentclass{sig-alternate}
\newcommand{\aive}{{\"aive}}

%-- Begin patch area for accents in 'Author Block' area - may be needed by some authors / but not all
\DeclareFixedFont{\auacc}{OT1}{phv}{m}{n}{12}   % Needed for "Author Block" accents - Patch by Gerry 3/21/07
\DeclareFixedFont{\afacc}{OT1}{phv}{m}{n}{10}   % Needed for "Author Block" accents in the affiliation/address line - Patch by Gerry 3/21/07
%--
\usepackage{color,cite,tricks}
\usepackage{url,amssymb}
\DeclareMathOperator*{\argmin}{arg\,min}
\newcommand{\hmm}[1]{{\underline {\bf #1}}}
\begin{document}
%
% --- Author Metadata here ---
\conferenceinfo{ASE}{'07 Altanta, Georgia, USA}
%\CopyrightYear{2007} % Allows default copyright year (200X) to be over-ridden - IF NEED BE.
%\crdata{0-12345-67-8/90/01}  % Allows default copyright data (0-89791-88-6/97/05) to be over-ridden - IF NEED BE.
% --- End of Author Metadata ---

\title{The Business Case for Automated Software Engineering}
\numberofauthors{3} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%
\author{ 
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
%
% 1st. author
\alignauthor
Tim Menzies\\Oussama Elrawas\\
       \affaddr{Lane Dept. CSEE}\\
       \affaddr{West Virginia University, USA}\\
       \email{tim@menzies.us}\\
	\email{oelrawas@mix.wvu.edu}
% 2nd. author
\alignauthor
Jairus Hihn\\Martin Feather\\
       \affaddr{Jet Propulsion Laboratory}\\
       \affaddr{California, USA}\\
       \email{mfeather@jpl.nasa.gov}\\
       \email{jairus.hihn@jpl.nasa.gov}
\alignauthor
Ray Madachy\\Barry Boehm\\
       \affaddr{Computer Science Dept. }\\
       \affaddr{Uni. Southern California, USA}\\
       \email{madachy@usc.edu}\\
       \email{boehm@sunset.usc.edu}
}
      % There's nothing stopping you putting the seventh, eighth, etc.
% author on the opening page (as the 'third row') but we ask,
% for aesthetic reasons that you place these 'additional authors'
% in the \additional authors block, viz.
\date{\today}
% Just remember to make sure that the TOTAL number of authors
% is the number that will appear on the first page PLUS the
% number that will appear in the \additionalauthors section.

\maketitle
\begin{abstract}
In theory, software process models
can 
assess the relative merits of automated software engineering tools.
In practice, such an assessment is complicated by the 
{\em tuning problem}; i.e.
it may be  hard
to collect the local data required for model tuning. 
However, while the exact tunings may not be available, the space of
possible tunings is well known.
For two NASA case studies,
we explore that space to conclude that
automated software engineering tools are crucial for reduing
project
effort and defects and threats
\end{abstract}

% A category with the (minimum) three required fields
\category{I.6}{Learning}{Machine Learning}
%\category{D.2.9}{Software Engineering}{Effort Estimation}
%A category including the fourth, optional field follows...
\category{D.2.8}{Software Engineering}{Metrics}[product metrics, process metrics]


\keywords{COCOMO, COQUALMO, meta-heuristic search, simulated annealing, feature subset selection}
\pagestyle{plain}
\section{Introduction}

Standard  software process theory does not support the thesis that automatic
tools 
(e.g. 
SPIN~\cite{holzmann97},  JPF~\cite{have00}) 
are relatively more valuable than manual methods.
Programmer talent, and not the tools they use, is often cited as 
most important for project success:
\bi
\item
At a recent
panel at ICSE 2007, Tim Lister (one of the authors of Peopleware~\cite{demarco87})
commented
that ``sociology beats technology
in terms of successfully completing projects''- a sentiment 
endorsed by other panelists.
\item
\fig{coceffects} shows relative productivity effects
of changing project features (data from
a regression analysis of 161 projects~\cite{boehm00a}).  
\fig{coceffects}
support Lister's thesis that 
the benefits of automatic tools (number nine in the list) can be equalled or bettered
via other means; e.g. any {\em one} the first eight items or any {\em pair} of items 
10 to 22.
\ei
%To be fair, apart from \fig{coceffects},
%the general software engineering literature is weak on the relative
%merits of {\em any}
%set of methods.
%We recently reviewed the (approx) 100 V\&V methods offered by
%the SE literature\footnote{
%Wallace and Fujii's classic definitions of V\&V~\cite{wallace89};
%the IEEE 2004 standard on V\&V~\cite{1012};
%NASA's recommended V\&V practices~\cite{jackson97}}. While some
%evidence was offered for the value of general techniques\footnote{
%E.g. improving
%software maturity decreases rework~\cite{king02}} there was very
%little precise evidence on the merits of a particular tool. Further, there
%was almost no comparisons of the relative effectiveness of pairs of methods applied
%to the same task.
%
\begin{figure}[!b]
\small
\begin{center}
\begin{tabular}{l@{}|l@{~}r@{~}l}
& & relative\\
id & features  & weight\\\hline
1&Personnel/team capability  & 3.53	&\rule{17mm}{2mm}\\
2&  Product complexity & 2.38&	\rule{12mm}{2mm}\\
3& Time constraint & 1.63&	\rule{8mm}{2mm}\\
4&    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&  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& Storage constraint & 1.46&	\rule{7mm}{2mm}\\
12& Process maturity  &	1.43	&\rule{7mm}{2mm}\\
13&    Language \& tools experience  &	1.43	&\rule{7mm}{2mm}\\
14&     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.
}\label{fig:coceffects}
\end{figure}
\input{cocomo}


One way to make the business case for automated
software engineering is to argue that the effort
productivity figures of \fig{coceffects} are incomplete.
Rather that focusing just on project effort (as done in
\fig{coceffects}), a complete
assessment must 
explore the relative value of automated tools
for
minimizing development {\em effort}, the {\em defects} delivered in the system, 
and any {\em threats} to the project. 
There are  many
predictors for these qualities including the COCOMO-family
of models that use
the features of \fig{cparems}:
\bi
\item
The COQUALMO defect predictor~\cite[p254-268]{boehm00b};
\item
The  COCOMO effort predictor~\cite[p29-57]{boehm00b}; 
\item
The THREAT  schedule threat predictor~\cite[284-291]{boehm00b} 
(previously known as the ``Madachy schedule risk model''~\protect\cite{me05e}).
\ei
When {\em tuned} to local data, they are quite accurate. For example,
Chulani et.al.~\cite{chulani99} reports a one study with a Bayesian
tuning algorithm using 161 projects. After tuning, a cross-validation
study showed that COCOMO produced effort estimates that are 
within 30\% of the actuals,
69\% of the time.
Also, studies with the COCOMO-81 project database have shown that
the THREAT index correlates with with the $\frac{months}{KDSI}$ (KDSI= thousand
of delivered source lines of code).
This result is consistent with the
the base premise of THREAT; i.e.  bad management can delay
software delivery.

Unfortuneately, {\em the data required for the local tuning may be incomplete}.
Software projects are notoriously difficult
to control: recall the 1995 report of the Standish group
that described a \$250 bullion dollar American software industry
where 31\% of projects were canceled and 53\% of projects incured
efforts exceeding 189\% of the originial estimate~\cite{standish95}.
Corporations are therefore reluctant to expose their own software
development record to public scrutinty.
For example, despite two years intensive effort, the authors have failed
to obtain local tuning data from NASA.

The premise of this paper is that, in terms of ranking different methods,
a {\em precise} local tuning is not required.
Based on research dating back to 1981~\cite{boehm81}, we assert that the
space of {\em
possible} tunings is well known. This space can be explored to
find features that minimize effort, defects, and threats.  

The STAR algorithm, developed for this paper,
adds a novel
back select algorithm, to a simulated annealer.
STAR
was used to  explore the space of possible tunings within
COCOMO, COQUALMO and THREAT. 
SA
offers contraints to all variables. STAR ranks and prunes those
constraints. At each step in the pruning, the COCOMO/ COQUALMO/
THREAT models are called to test the current  constraint set.
The result is an ordering on the feature ranges according to how
well they reduce
effort/ defects/ threats.

The rest of this paper details STAR,
COCOMO, COQUALMO,
and THREAT, as well as    mutators that randomly sample the internal tunings of the process
models. In two case studies with NASA projects,
the conclusions reached by STAR were useful and stable over
the space of possible tunings.
In terms of the business case for automated software engineering, the important
result will be that 
automated tools were always found in the minimum set of projects constraints
that reduced effort/defects/ threats. 

\section{Preliminaries}
Before beginning, we digress for three preliminaries
\subsection{Why Compare?}
Is this paper forcing a premature comparison between fledgling  automatic
tools and more mature manual methods that have been evolving for decades?
Perhaps
there is no need to 
compete between automatic tools and manual methods
since both have their place in the software development life cycle.
Ideally, we would defer this evaluation of automatic
tools
and manual methods since that would give time
for
more
experiments with more automatic tools, and the collection more data.
Under those conditions,
the natural best combination of automatic and
manual methods would evolve, of its own accord.

We believe that waiting is ill-advised.
The authors are part of a group of reserachers
advocating the greater use of automatic tools.
This 
group has seen dramatically less funding for their work over the last three years.
Organizations such as NASA and the U.S. National Science Foundation are 
currently reorganizing
the next generation of large government software engineering initiatives.  
Without a demonstration of the relative value of automatic tools,
this line of research may not be included in
new initiatives.

\subsection{Inherent Bias?}

As mentioned above, our research funding depends on the continued interest
of funding agencies in our work.
It might hence  be argued that the authors are the {\em worst} team to comparatively
evaluate automatic tools vs manual methods.
It is therefore prudent to question our
evaluation bias.

To enable other researchers to question our biases,
we take
care to make our case studies fully reproducible.
Reproducibility is an important methodological principle in other
disciplines since it allows a community to confirm, refute, or even
improve prior results.  In our view, in the field of software
engineering, there are all too few examples of reproduced, and
extended, results\footnote{ Exception: see  the reports of the
PROMISE workshop \url{http://promisedata.org/repository/papers.html}}.
Accordingly,
an appendix to this paper detailed how to install and run the
software required to repeat the KC1\&ARES case studies.
Such reproducibility allows other researchers to check if our advocacy
of automated tools biases our conclusions.

\subsection{Is There Really a Problem?}

Novel techology was developed for this paper. That technology is superflous
unless it is warranted by the
{\em local tuning problem}. Hence, this section documents that problem.

Consider  the COCOMO-81 development effort model~\cite{boehm81}.
This model assumes 
that the development $effort_i$ for $project_i$ is exponential on program size:
\begin{eqnarray}\label{eq:ab} 
effort_i &= &a \cdots KSLOC ^ b \cdots project_i\\
project_i &= &\prod^{15}_j EM_j
\end{eqnarray}
Here, $project_i$ is computed from 
the
15 {\em effort multipliers} $EM_i$ shown in \fig{cparems}.
{\em Local calibration} (LC)~\cite[p526-529]{boehm81} is a linear regression method 
that returns the
$a,b$ values that minimizes the difference between efforts predicted by \eq{ab} and the actual values seen in
$project_{1..i}$.

Based on historical data,
the COCOMO-81 model offered three sets of cliched $a,b$ values that varied
according to the different development {\em modes} of \fig{eso}.
\begin{figure}[!t] 
{\scriptsize 
\begin{center}
\begin{tabular}{p{0.5in}|r|r|p{1.8in}} \noindent Mode & a & b & notes\\\hline
Organic & 3.2 & 1.05 & projects from relatively small software teams
develop in-house software in a highly familiar environment.\\\hline
Embedded & 2.8& 1.2 & projects operating within (is embedded in) a
strongly coupled complex of hardware, software, regulations, and
operational procedures.\\\hline Semi-Detached & 3.0 & 1.12 & An
intermediary mode between organic and embedded.  
\end{tabular}
\end{center}} 
\caption{COCOMO-81 development modes.}\label{fig:eso} 
\end{figure}
\begin{figure}[!t]
\scriptsize
\begin{center}
\begin{tabular}{|rr|rr|}
\multicolumn{2}{c}{a}
&\multicolumn{2}{c}{b}\\\hline
$\mu$&$\sigma$  & $\mu$ & $\sigma$ \\\hline
3.72& 0.51& 1.09& 0.037\\
4.06& 0.63& 1.07& 0.04\\
4.27& 0.78& 1.02& 0.05\\
5.06& \hmm{2.08} & 1.02& 0.09\\
5.74 & \hmm{2.13}& 1.00 &0.084\\
5.78& 1.5&0.85& 0.094\\
6.28& 0.46& 0.93& 0.02\\
6.35& 1.26& 0.97& 0.05\\
6.35& 1.49& 0.92& 0.05\\
9.18& \hmm{2.97}&0.88& 0.081\\\hline
\end{tabular}
\end{center}
\caption{30 repeats of local tuning on  90\% samples. }\label{fig:lc}
\end{figure}
Subsequent work~\cite{boehm00a}
in the late 1990s updated these values using 161 
projects and,  even after that update, the $a,b$ values 
were approximately equal to \fig{eso}.

%\begin{figure}
%\scriptsize
%\begin{center}
%  \begin{tabular}{rr|rr}
%       a & b      &  a & b\\\hline
%       3.72 &1.09 &  5.45 &1.05\\
%       4.06 &1.08 &  7.92 &0.85\\
%       4.22 &1.09 &  9.18 &0.85\\
%\end{tabular}
%\end{center}
%\caption{Local tunings on $<a,b>$.}\label{fig:tune}
%\end{figure}
Reusing calibrations from other projects
can lead to very inaccurate predictions.
Off-the-shelf ``untuned'' models have 
been up to 600\% inaccurate in their estimates, e.g. ~\cite[p165]{mukho92}~\cite{kemerer87}. 
For example, \fig{lc} show 
local tuning experiments with some NASA COCOMO data\footnote{
\url{http://promisedata.org/repository/data/nasa93/nasa93.arff}}.
Local tuning was 
performed on  ten sub-domains of the NASA data (flight, ground, avionics monitoring, etc).
For each sub-domain, thirty times, 90\% of the data
was randomly selected for local tuning via LC.
The mean $<a,b>$ values are very different to the standard COCOMO-81 values of \fig{eso}.
That is, specialized organizations like NASA develop software that is very
different from the kinds of projects used to generate standard software process models.
For such organizations, models can't be reused verbatim from some prior setting.

Note the \hmm{underlined} entries
of \fig{lc}. These entries show that  
the standard deviation of the values learned from local tuning may be   very large.
That is, in these NASA COCOMO data sets,
there was insufficient data in these sub-domains to reach stable conclusions.
That is,
even if some local tuning data is available, it may still be incomplete.

Rather than rely on missing on incomplete
local data for model tuning, the rest of this paper explore how autoatic tools
and manual methods compare, over the
the space of possible tunings within the COCOMO, COQUALMO, and THREAT
 software process models.
\newpage
\input{models}

\section{Search Algorithms}
Having defined the internal space of our models, we now search it.
A simulated annealler is used to  sample that space and a back select
algorithm is used to  rank feature ranges accoring to how well they reduce effort/ defects/ 
threats.
\subsection{Simuated Anneling}
{\em Monte Carlo} alogorithms 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 some
fitness function),  it becomes the new {\em current}
state used  for future
mutations.  Otherwise, a Boltzmann acceptance
criteria is used to probablisiticly 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 mechansim. For our experiments,
we freeze $\frac{2}{3}$ of the features and
randomly  select values for the rest.

In 1983, Kirkpatrick et.el.~\cite{kirkpatrick83} 
proposed a modification to the Metropolis algorithm inspired
by a procedure used to make the strongest possible glass. Initially,
the 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. 
Hence, a {\em simulated annealing} (SA) algorithm adds
a ``tempreature'' variable to the Botzmann accept criteria
such that, at high temperatures, it is more likely that the
algorithm will jump from to a worst new 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.

\begin{figure}[!t]
\scriptsize
\begin{verbatim}
function sa(kmax) 
  s := s0; e := E(s)           // Initial state, energy.
  sb := s; eb := e             // Initial "best" solution
  k := 0                       // Energy evaluation count.
  while k < kmax and e > emax  // Loop
    sn := neighbour(s)         //   Pick some neighbour.
    en := E(sn)                //   Compute its energy.
    if en < eb then            //   Is this a new best?
      sb := sn; eb := en       //     Yes, save it.
    if random() < P(e, en, temp(k/kmax)) 
     then s := sn; e := en     //     Maybe move to a worse state
    k := k + 1                 //   One more evaluation done
  return sb                    // Return best
\end{verbatim}
\caption{Mutate an initial state $s0$ to some $neighbour$ region.
A new solution $sn$ (with new energy $en$) is the best solution $sb$ 
if it has
less energy
$or$ if it is selected by
 probability function $P$.
}\label{fig:sa}
\end{figure}

According to the annealing metaphor, better solutions have lower ``energy''
so the fitness function $E$ is defined such that $E \ge 0$ and
{\em lower} values are
$better$. 
For our purposes, we model effort ($Ef$), defects ($De$) and threats ($Th$) 
in a 3-D space where the energy
is the  distance to the origin:
\[\small
E=\left(\sqrt{\overline{Ef}^2 + \overline{De}^2 + \overline{Th}^2}\right) / \sqrt{3}
\]
Here, $\overline{x}$ is a normalized value 
$0 \le \frac{x - min(x}{max(x) - min(x)} \le 1$. 
Hence, our energy ranges $0 \le E \le 1$ and
{\em lower} energies are {\em better} (less effort, defects, threats).

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$):
\[
P(e,en,T) = e^{(e -en)/T}
\]
$T$ is defined to $decrease$ as the simualor loops through $k= 1\ldots kmax$ iterations.
We use
$T = e^{-100*k/kmax}$.

\begin{figure}
\begin{center}
\includegraphics[width=2.5in]{jpl1.pdf}
%eps/JPL.pdf}
\end{center}
\caption{Processing a JPL requirements model. }\label{fig:jpl}
\end{figure}
Two advantages of SA are their {\em implementation simplicity} and their {\em ability to handle
non-linear models}:
\bi
\item {\em Simplicity:}
\fig{sa} illustrates the simplicity of the algorithm. Memory is only required
for one current solution ($s$), one new solution ($sn$) and one best solution ($sb$) that stores
the best solution seen at any time over the simulation.
\item
{\em Non-linear models:}
 Previously~\cite{fea02a,me03i}, we have applied SA to non-linear JPL requirements models
where minimizing the cost of project mitigations can decrease the number of requirements
achieved by that project. Hence, decreasing {\em both} the cost and achieved requirements
is a non-linear problem that must trade between minimizing cost and increasing
requirements coverage.
The top-left line  of \fig{jpl} divides the behavior of the JPL requirements models
before  and after  simulated annealing. 
As shown below the line, 
initial Monte Carlo sampling of the possible mitigations lead to a large range
of costs and benefits. Simulated annealing found a set of mitigations
that lead to the small cloud of solutions above the line. Compared to the initial samples, these
new solutions had decreased cost, increased benefit (number of requirements covered), and descreased variance (shrank
the space of solutions). 
\ei
Two disadvantages of SA are their {\em incompleteness} and {\em
complexity}
of their solutions:
\bi
\item 
{\em Incompleteness:} In our domain, we have some evidence that incomplete nature of the heuristic SA
search is not a major problem.
\fig{saeg} shows a sample run of our SA tool running on our process models
for $K=10,000$ simulations. 
As $k$ increases for $1{\ldots}10,000$, it becomes less and less
likely that a better $best$ has been missed. Hence, we run our simulations
for ten times the period it takes for $best$ to stabilize (at $k\approx 1000$). 
\begin{figure}
\begin{center}
\includegraphics[width=2.7in]{saeg1.pdf}
\end{center}
\caption{Dots and lines show
SA output from current and best solution (respectively)  after $k$ simulations.
}\label{fig:saeg}
\end{figure}
\item
{\em Complexity:}
Simulated annealers offer constraints to all controllable inputs. Often this
is an over-constrained solution. 
In many domains, a repeated empirical result is a {\em feature subset selection}
effect; i.e. many features can be pruned from a model without damaging
the predictive power of that model~\cite{kohavi97,hall03}.
For example, \fig{kohavi} shows studies where using just 19\% of the available features
changed prediction accuracy by just 2.14\% (on average).
Also, 
when feature subset selection was applied to the JPL requirements model of \fig{jpl}, we found that
up to $\frac{2}{3}$-rds of the features can be left unconstrained,
without effecting the conclusions~\cite{fea02a}. 
\ei

\begin{figure}[!t]{\scriptsize\begin{center}\begin{tabular}{|l|r|r|r|p{0.95cm}|}
 \cline{2-4}\multicolumn{1}{c}{}     & \multicolumn{3}{|c|}{av.
 number of features} \\\hline    dataset         &before &after
 &$\frac{after}{before}\%$ &accuracy change\\\hline    breast cancer
 &10  &2.9 &29\% &+0.14\%   \\\hline    cleve           &13  &2.6
 &2\%  &+5.89\%   \\\hline    crx             &15  &2.9 &19\%
 &+4.49\%   \\\hline    DNA             &180 &11  &6\% &+3.63\%
 \\\hline    horse-colic     &22  &2.8 &13\% &+1.63\%   \\\hline
 Pima            &8   &1   &13\% &+0.79\%   \\\hline    sick-euthyroid
 &25  &4   &16\% &+0.38\%   \\\hline    soybean         &35  &12.7
 &36\% &+0.15\%  \\\hline\hline    average         &38.5&4.99 &19\%
 &+2.14\% \\\hline\end{tabular}\end{center}\caption{Feature subset
 selection results from~\cite{kohavi97}}}\label{fig:kohavi}\end{figure}

For the goals of this paper, exploring feature subset selection
is very important.  Before we can {\em remove} superfluous features,
we must first  {\em rank} them according to their effectiveness.
As we shall see, this ranking will be insightful to the task of
assessing the relative value of automatic tools and manual methods
for reducing effort/ defects/ threats.
We will use a novel support-based Bayesian ranking method.

\subsection{Support-Based Bayesian Ranking}

Our ranking methods takes the feature ranges found after $K$ runs of a simulated annealler
and divides them into:
\bi
\item {\em Best:} those associated with the  BEST\% solutions
(i.e. those with energies in the lower BEST\%);
\item And the {\em rest}.
\ei
It then computes the probability that a range is found in $best$.
using Bayes' Theorem.
Informally,
the
theorem says $next=old*new$ i.e. what we'll believe {\em next}
comes
from how {\em new} evidence effects {\em old} beliefs.  More
formally:\[P(H|E)=\frac{P(H)}{P(E)}\prod_iP(E_i|H)\]i.e. given
fragments of evidence $E_i$ and a prior probability for
a class
$P(H)$, the theorem lets us calculate a  posteriori  probability
$P(H|E)$. For this work, we have two classes; $H\in \{best, rest\}$.

Simple  Bayes classifiers are called ``n\aive'' since they assume
independence of each feature. While this assumption
 simplifies the implementation  
(frequency
counts are required only for each feature),
 it is possible
that
correlated events are missed by this ``n\aive'' approach.
Domingos and Pazzani show theoretically
that the independence assumption is a problem in a vanishingly small percent
of cases~\cite{domingos97optimality}. This explains the repeated
empirical result that, on average, N{\aive} Bayes classifiers perform as well
as other seemingly more sophisticated schemes (e.g. see Table~1 in~\cite{domingos97optimality}).


When applying the therom, it is standard practice to compute  {\em liklihoods}
from frequencies, then normalize these over the sum of all liklihoods to create
probabilities (this normalization cancels out $P(E)$, so we will not refer to it again).
For example, after $K=10,000$ runs, we might have 1,000 lowest 10\% {\em best} solutions and 9,000
{\em rest}. If the range $rely=vh$ appears 10 times in the $best$ solutions, but only
5 times in the $rest$, then:

{\scriptsize
\begin{eqnarray}\nonumber
x&=& (reply=vh)\\\nonumber
P(best)&=&1000/10000 = 0.1\\\nonumber
P(rest)&=&9000/10000 = 0.9\\\nonumber
freq(x|best)&=&10/1000 = 0.01\\\nonumber
freq(x|rest)&=&5/9000 = 0.00056\\\nonumber
like(x|best)&=&freq(x|best) \cdot P(best)=0.001\\\nonumber
like(x|rest)&=&freq(x|rest) \cdot P(rest)= 0.000504\\\label{eq:ten}
P(x|best)&=& \frac{like(x|best)}{like(x|best) + like(x|rest)}=0.66
\end{eqnarray}}

(Note that, since this is a two-class system, increasing the probability of $best$ also
means decreasing 
the probability of $rest$.)

\eq{ten}
is a poor ranking method. While the probability is moderately large (0.66), the {\em support}
for this range is very weak (this range was only seen in $\frac{10}{1000}=0.01=1\%$). 
Hence,
in previous studies with contrast set learning~\cite{clark05}, we have augmented \eq{ten} with a support term.
Support increases as the frequency of a range increases; i.e. 
$like(x|best)$ is a measure of support.
As we shall see below, \eq{ps} is an excellent range ranging method: 
\begin{equation}\label{eq:ps}
probability * support = \frac{like(x|best)^2}{like(x|best) + like(x|rest)}
\end{equation}
To compute \eq{ps}, STAR runs in five steps:  
\be
\item To sample the ranges from the models,
STAR runs the simulator annealler  $K_1=10,000$ times to generate results like \fig{saeg}. 
Note that this sample will include the best solutions.
\item The data seen in the $K_1$ samples is then discretized into $D=10$ bins.
Discretization converts a continuous range into a histogram
with $n$ break points $b_1\ldots b_n$ where $\left(\forall i < j : b_i \le b_j\right)$. 
After discretizaion,
many observations can fall into the same range
between $b_i$ and $b_{i+1}$
at frequency counts $c_i$. This study used equal width discretization; i.e. 
$\left(\forall i,j:
\left(b_i - b_{i-1}\right) = 
\left(b_j - b_{j-1}\right)\right)$.
\item
The ranges are then classified
into those seen in the top X=10\% {\em best} solutions and the (100-X=90\%) {\em rest};
\item
The ranges are then ranked in increasing order by their probability*support (\eq{ps}) of appearing 
in the X\% best outcomes;
\item
STAR then runs $K_2=100$ experiments with the models where the top $N$ ranges are pre-set and the
remaining ranges can be selected at random;
In terms of the business case for automated software engineering tools,
the step is crucial since it would rank automated tools alongside a variety
of manual methods. 
\item
STAR returns the $N$ value which report the least effort, defects, and threats.
\ee

To run our experiments, we had to apply our engineering judgement to set the parameters:
\[K_1=10,000, K_2=100, D=10, X=10\]Initially, we planned experiments that varied these parameters.
However, our initial results were so good (see below) that we are not currently motivated
to explore 
other parameter settings (such an exploration is planned for future work).

\begin{figure}[!t]
\begin{center}
\scriptsize
\begin{tabular}{c|lrr|lr}
       &\multicolumn{3}{c|}{ranges}      &\multicolumn{2}{c}{values}\\\hline
project&feature&low&high&feature&setting\\\hline
&prec&3&5&flex&3\\
ARES &pmat&4&5&resl&4\\
GNC&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\\\hline
&prec&1&2&data&3\\
&flex&2&5&pvol&2\\
Orbital&resl&1&3&rely&5\\
space&team&2&3&pcap&3\\
plane&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
\end{tabular}
\end{center}
\caption{Two case studies.}\label{fig:cases}
\end{figure}

\section{Case studies}

STAR was applied to the two case studies of
\fig{cases}:
\bi
\item ARES GNC: the guidance and navigation control system of NASA's ARES rocket.
\item Orbital Space Plane: a 1990s NASA prototype.
\ei
In the figure {\em settings} are fixed while {\em ranges} represent a space of options.


$KC_1=10,000$ runs of the simulated annealing were then conducted.
Feature ranges not mentioned in \tion{cases} were selected at random from \fig{lc} and \tion{models}.
The {\em controllable} project feature ranges were sorted
according to \eq{ps}. By {\em controllable}, we mean the kinds of changes
a project manager could make to her project. {\em Uncontrollable} features, on the other hand,
are features like the correlation between, say, analyst capability and development effort. 
For this study, the controllable features are listed in \fig{cparems} while the uncontrollable
features 
are the internal model parameters of \fig{lc} and \tion{models}. 

Working just with the controllable features, STAR then imposed the top $N$ ranked ranges
and conducted $K_2$ simulations of the model. In these $K_2$ simulations, the $N$ ranges
were fixed and the  remaining ranges were selected at random from
the intersection of the ranges in \fig{models}, and \fig{cases}. 
The 50\% and 75\% percentile value for defects, effort, and threats was recorded.

The results are shown in \fig{backwards}: {\em median} shows the 50\% percentile and {\em spread} shows
the 75\% minus the 50\% range.
 
\input{plots} 

\section{Related Work}

A repeated conclusion is that the behavior of a model is 
determined by a very small number of key features.
For example,
 Kohavi \& John studied a specific {\em variable subset
 selection} method. Their experiments show that, on 8 real world
 datasets, an average 81\% of features can be ignored. Further,
 ignoring those features doesn't degrade the learner's  classification
 accuracy; on the contrary, it results in an average increase of
 2.14\% \cite{kohavi97} (see
 \fig{kohavi}).TAR4: 

Fenton's bayes nets: same motivation, different
technology, no requirement for a bayesian ontology

\cite{grey03} what-if analysis of different business scenarios. Unclear
how may what-if scenarios are supported.

Long term business success is highly dependent on how fast the business reacts on the changes in the market situation. Those who want to be successful need relevant, in-time and accurate information. Balanced Scorecard Simulator is a management tool that can be used efficiently in the processes of planning, decision and controlling. Based on the Balanced Scorecard concept the program combines imprecise data of business figures with forward and backward computation. It is also possible to find out whether or not the data are consistent with the BSC model. The visualization of the simulation results is done by a Kiviat diagram. The aim of the design is a software tool based on a BSC model and MCMC methods but is easy to handle.
tar1: ase 2000 2 models, no internal poling

tar2: ase 2002 other models, no defects model

tar3: ying hu

tar4: search heuristic

xomo: too complex

\section{Conclusion}

As to future work- scalability of BEST. Use it to control mutation?

Benchmark these against some complete algorithm.
\bibliographystyle{abbrv}
{\scriptsize
\bibliography{refs}}  % sigproc.bib is the name of the Bibliography in this case
\appendix
\section{Obtaining and Using STAR}

\subsection{Caveats: Too early}
Is it too early for this analysis? wait longer? maybe not. 
anyway. needed to cost.


One For example,  the more complicated
the tool, the better the user needs to be.  This is particularly true
for tools that require temporal logic constraints such as runtime
monitoring~\cite{have00b} and model checking~\cite{clarke99}.
However, it is also true for the more complex static analysis tools
such as Polyspace~\cite{visser05a}.
Conss
In order to make a strong business case for
automated software engineering tools
\end{document}

Ideally, the analysis of this paper could wait several more years
while  more data is acquired from projects. However, recent trends
in software engineering funding suggests that some preliminary results are now
required.
While the relative merits of different model checkers (e.g. SPIN vs nuSVm

While Unless proponents of automated software engineering tools
can model
more on personnel issues or software process maturity and describe a project

\section{Simulated Annealing}

With a few exceptions, the co-effecients
of the COCOMO and COQUALMO
features are learned from a linear regression
on past data. Hence, these features
csan be be modeled as
$y=mx + b$, where:
\bi
\item $y\in \{effort, \frac{defects}{kloc}\}$
for COQUALMO and COCOMO (respectively).
\item $x \in 1..6$ representing very low, low,
nominal, high, very high, extra high (respecitvely).
Not all features range over all 1..6 (see \fig{ranges}
for details).
\ei

\begin{figure}
\scriptsize
\begin{tabular}{ccp{2in}}
min & max & features\\\hline
1 & 5 & 
acap,
apex,
docu,
flex, 
ltex,
pcaon,
pcap,
plex,
pmat, 
prec, 
rely, 
resl, 
sced 
team,
tool \\
1 & 6 & automated analysis, 
cplx,
executionTestingAndTools,
peerReviews, 
site\\
2 & 5 & data,pvol\\
2 & 6 & reuse \\
3 & 6 & stor, time
\end{tabular}
\caption{Range of features in this study.}\label{fig:ranges}
\end{figure}

By convention,
nominal values (i.e. $x=3$) have no effect on effort and
defects. Since COCOMO and COQUALMO compute effort and
defects from $\prod_ix_i$, such a nominal effect
represents the point $\{x,y\}=\{3,1\}$. Substituting
these values into $y=mx+b$ yields $b=1 - 3m$. That is,
most of the COCOMO and COQUALMO effort and defect
effects can be modeled as:
\begin{equation}\label{eq:one}
\footnotesize
y=m\cdot (x-3) + 1
\end{equation}
The COCOMO and COQUALMO features fall into 12 groups:
\bi
\item For requirements, design, and coding, the 
\begin{figure}
\begin{tabular}{r|rrrrr|}
\scriptsize
          \multicolumn{2}{c}{pos}&\multicolumn{2}{c}{neg}\cline{2-5}
              &  min& max &  min &max\\\hline
requirements  &  0.0344 &  0.0516 & -0.9120 & -0.061 \\
design        &  0.0504  & 0.0756 & -0.0960 & -0.064 \\
code          &  0.0504  & 0.0756 & -0.0996 & -0.066
\end{tabular}
\caption{Range of slopes $m$ inside COQUALMO.}\label{fig:mcoqualmo}
\end{figure}

By convention,  nominal values of
 features have no influence on defects and effort.
 is said to have no ef
	
     1	                case 25: spCoqualRSlope (rating); break;
     2	                case 26: snCoqualRSlope (rating);break;
     3	                case 27: sdfrCoqualRSlope (rating);break;
     4	                case 28: spCoqualDSlope (rating);break;
     5	                case 29: snCoqualDSlope (rating);break;
     6	                case 30: sdfrCoqualDSlope (rating);break;
     7	                case 31: spCoqualCSlope (rating);break;
     8	     case 32: snCoqualCSlope (rating);break;
     9	                case 33: sdfrCoqualCSlope (rating);break;
    10	                case 34: sSFCocomoSlope (rating);break;
    11	                case 35: sposEMCocomoSlope (rating);break;
    12	                case 36: snegEMCocomoSlope (rating);break;
    13	                case 37: sA (rating); break;
    14	                case 38: sB (rating); break;
    15	                case 39: sKsloc (rating); break;	
	
	
     1																									0.0344	0.0516
     2																									-0.0912	-0.0608
     3																									0.0784	0.1176
     4																									0.0504	0.0756
     5																									-0.096	-0.064
     6																									0.1104	0.1656
     7																									0.0504	0.0756
     8																									-0.0996	-0.0664
     9																									0.0976	0.1464
    10																									-1.5288	-1.0192
    11																									0.0896	0.1344
    12																									-0.1188	-0.0792
    13																									3.72	9.18
    14																									0.85	1.09
    15																									100	125

XXX corleigh

x=3, y=1


b = 1 -  3m 

y = mx + 1 - 3m

y = m (x-3) + 1
\[
<out_1,out_2,...> = model(in_i, in_2,....)
\]
\[
in_x \in constraint_x \subseqeq range_x 
\]
We say that if an input $x$ is {\em open} then it is unconstrained and
its value can  come from anywhere in $range_x$, selected at random.
Simulated annealing adds constraints (i.e. decreases the set of possible $in_x$ values)
while feature subset selection removes constraints (i.e. increases the set of possible $in_x$ values).

To mutate, we open $Mutate\%$ of the current $best$ solution.
New values for the openned variables are then picked at random, there by generating a new $current$
solution that retains $100-Mutate\%$ of the best values.
\[
Defaults: $Mutate=33$.
prob(e,en,t) = e^{\left(e - en)/t\right)}
discreteization:
discretize(in_x,N) = \frac{in_x - min_x}{(max_x - min_x)/N}

L(X|Class)= \frac{f(X|Class)}{f(Class)} \cdot \frac{f(Class)}{|Data|}

support(X|best) = L(X|best)
probabily(X|best) = \frac{L(X|best)}{L(X|best)+ L(X|rest)}
score(X) = probability(X|best) * support(X|best) = \frac{L(X|best)^2}{L(X|best)+ L(X|rest)}

\overline{X}= \frac{X - min(X)}{max(X) - min(X)}

E(defects, effort, threat) = \frac{ \sqrt{\overline(defects)^2 + \overline(effort}^2 + \overline(threat)^2}}{\sqrt(3)}

\begin{figure}
\begin{alltt}
\scriptsize
function sorted() {
  call sa(100,000) and collect all best solutions
  discretize the 1..r ranges seen in "all" into B bins
  best   = 1/B solutions with smallest energies
  rest   = solutions - best
  sorted = ranges sorted by probability*support of being "best"
  return $\argmin({i\in1..r} median(100 * E(sorted[1{\ldots}i])
}
\end{alltt}
I think people can be tactical for some companies                                                               
and types of sw.  at JPL it is only tactical if                                                                 
we can shaft other projects                                                                                     
                                                                                                                
site is tactical in most cases.  only startegic                                                                 
if congress or upper mgmt forces certain                                                                        
partnerships               

strategic

prec	pick partners and new projects based on doing what you alrady know how to do. For exampel JPL is the tops at EDL. 	y		
pmat	This is only changed over the longer run.  An individual project cannot really manipulate this as a variable.  It could show payoff of investment in process improvement. Or could use it to argue never higher a contractor that is not at least Level 3.	y		
acap	All the people ones can be manipualted to large extent.  However<> in a 	y		
pcap	large company often have to picj from an existing pool and problem at 	y		
pcon	JPL is that mutliple projects all fight over the top people.	y		
apex		y		
plex		y		
ltex		y		
site	colocation unless your partner is forced on you as ESA this can be controlled by project.	y		

tactical

stor			y	 
flex	negotiate for flexible requirements		y	
resl	manage your risks wel. I would argue this is process related but you could chosse to do a better job. 		y	
cplx	This largely determined by application but many people here argue that a good system architecture can greatly reduce the complexity so could be used measure payoff of spedning a bit more upfront for a better design.		y	
data	amount of test data.  I think this is application and customer dependent. 		y	
docu	This can be negotiated		y	
ruse	desing for future reuse.  This ioncreases cost.  But is suppose to save money for future developemnt projects.  Is alsoa  key variable in looking at product lines.		y	
tool	project often choose tools but if it is the very first time the model somewhat lies as they often increase cost until get through the learning curve and then save money in the long run. 		y	
sced	can be nogotiated		y	

wild

team	how well functiona s a team.  Shows value fo high quality open communication.  Cannot control this always but can seek ita nd foster it.			y
rely	usually not variable.  Determined by application for example Human is VH<> Flight is High<> Ground is Nom mostly but can be H.			y
time	these 2 depend on wether there is aconstarin on your HW which can happen on spacecraft			y

vol	Mostly becomes bad due to new major products or releases. For rexample no one wants to buy VISTA right now.			y

\section{standard theory}
\section{Conclusions}

%\end{document}  % This is where a 'short' article might terminate

%
% The following two commands are all you need in the
% initial runs of your .tex file to
% produce the bibliography for the citations in your paper.
% You must have a proper ".bib" file
%  and remember to run:
% latex bibtex latex latex
% to resolve all references
%
% ACM needs 'a single self-contained file'!
%
%APPENDICES are optional
%\balancecolumns
