\section{Model-based Case Studies}\label{sect:data}

\input{figs/projects.tex}

Since the presented model-based methods are built around the COCOMO-suite, we must use COCOMO data and $contexts$ written in the COCOMO ontology. An example of such data is the NASA93 dataset found in \tion{dataset} and is available at \texttt{promisedata.org}. \fig{cases} shows some real-world $context$ and $control$ information taken from a  debrief of some NASA program managers:
\bi
\item \emph{Ground} and \emph{flight} represent typical ranges for most NASA projects at the Jet Propulsion Laboratory (JPL);
\item \emph{OSP} represents the guidance, navigation, and control aspects of NASA's 1990 Orbital Space Plane  (OSP);
\item \emph{OSP2} represents a second, later version of OSP with a more limited scope of COCOMO attributes.
\ei
The un$control$able  column in \fig{cases}  shows project features that cannot be changed. For example in project OSP, the required reliability is fixed at $rely=5$. On the other hand, the $low$ and $high$ ranges in that figure define the space of possible changes to that project. For instance, the reliability of flight software varies from 3 (nominal) to 5 (very high). 

\section{SEESAW}

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

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

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

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

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

Along with COCOMO-II, Boehm also defined the COQUALMO defect predictor. COQUALMO contains equations of the same syntactic form as \eq{lineem}  and \eq{linesf}, but with different coefficients. Using experience from 161 projects~\cite{boehm00b}, one can find the maximum and minimum values ever assigned to $m$ for COQUALMO and COCOMO. Hence, to explore tuning variance (the $t\in T$ term in \eq{argmin}), all we need to do is select $m$ values at random from the min/max $m$ values ever seen.

Initially, prior work implemented the AI search of  \eq{argmin} using simulated annealing~\cite{me07f,me08c,me09e}.  Subsequent work demonstrated that the recommendations found in this way did better than numerous  standard process improvement methods~\cite{me09a}. Later implementations were based on a state-of-the-art theorem prover~\cite{me09i}. SEESAW searches within the ranges of project attributes to find constraints that most reduce development effort, development time (measured in calendar months), and defects. Figure ~\ref{fig:seesaw} shows SEESAW's pseudo-code. The code is an adaption of Kautz \& Selman's MaxWalkSat local search procedure [13]. The main changes are that each solution is scored via a Monte Carlo procedure (see score in Figure ~\ref{fig:seesaw}) and that SEESAW seeks to minimize that score (since, for our models it is some combination of defects, development effort, and development time in months).

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

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

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

\section{Five Additional AI Model-Based Algorithms}

The case studies of \fig{cases} can be used to assess how well different AI algorithms can find changes to software projects. For example, a typical Simulated Annealing (SA) run explores 10,000 variants on some solution~\cite{kirkpatrick83}. A side-effect of that run is 10,000 sets of inputs, each scored with the $value$ function of \eq{edt}.

\begin{equation}\small\label{eq:edt}
value = 1- \left(\sqrt{Effort^2 + Defects^2 + Time^2} / \sqrt{3} \right) 
\end{equation}

Our tool classified the outputs into the  90\% {\em rest} and the 10\% {\em best} seen during the run of the SA. All the ranges from all the features were then ranked according to how much more frequently they appeared in {\em best} than {\em rest}. A {\em forward select} was then called using the first  $1{\ldots}x$ ranked items. \fig{run} shows the treatment $R_x$ at any $x$ value is the conjunction of ranges observed between 1 to $x$ (see the table at the bottom of that figure). The $y$ axis scores show median results in 100 runs of  COCOMO/COQUALMO, after imposing the treatment. The ``pruned'' range of that figure shows the results of a  {\em back select}  that worked backwards over the forward select ordering, deleting any item $x$ whose distribution of values was statistically insignificantly different to $x-1$. SA's final recommendation was the treatment $1 \le x \le 13$. The $improvement$ generated by that treatment 
can be seen by comparing the values at $x=0$ to $x=13$.
\bi
\item Defects reduced:  350 to 75; 
\item Time reduced:  16 to 10 months;
\item Effort reduced:  170 to 80 staff months.
\ei


\begin{figure}[!t]
\begin{center}
\includegraphics[width=4.0in]{figs/single-seesaw-tpts100-all-trio-2-1.pdf}
~\\
\begin{tabular}{|p{.3\linewidth}|p{.4\linewidth}|}
\multicolumn{2}{l}{Decisions made from round=1 to round=13: }\\\hline
x=0: $R_x = \emptyset$\newline
x=1 added \{pmat=3\}\newline
x=2: added  \{resl=4\} \newline
x=3: added   \{team=5\}\newline
x=4: added \{aexp=4\} \newline
x=5: added  \{docu=3\}\newline
x=6: added  \{plex=4\}
&
x=7: added \{rely=3\} \newline
x=8: added  \{stor = 3\}\newline 
x=9: added \{time = 3\}\newline
x=10: added  \{tool = 4\}\newline
x=11: added \{sced = 2\}\newline
x=12: added \{site = 4\}\newline
x=13: added  \{acap = 5\}
\\\hline
\end{tabular}
\end{center}
\caption{Example of SA's forward and back select.}
\label{fig:run}
\end{figure}

SA is just one way to generate a treatment. For our AI model-based methods, we explored five others. Given a random selected treatment, {\em MaxWalkSat} tries $n$ modifications to randomly selected features~\cite{selman96}. Sometimes   (controlled by the $\alpha$ parameter), the algorithm chooses the range that minimizes the value of the current solution. Other times (at probability $1-\alpha$), a random range is chosen for the feature. After $N$ retries, the best solution is returned. Our implementation used $n=50$, $\alpha=0.5$, and $N=10$.

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

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

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

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

\section{Comparisons of AI Model-based Methods}\label{sect:aicomp}
For each case study of \fig{data}, each algorithm was run 20 times (guided by the $value$ function of \eq{edt}). Separate statistics were collected for the defects/effort/time predictions seen at the policy point in the 20*4 trials. The {\em top-ranked} algorithm(s) of \fig{xper} had statistically  different and lower defects/effort/time predictions than any other algorithm(s). 

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

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

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



\section{Model vs. Case-Based Methods}\label{sect:modelins}
SEESAW requires models in the COCOMO format
so for our comparisons,
we restrict ourselves to data in that format.
{\W}2 used the historical cases from
the NASA93ii and COC81ii datasets.
These  data sets all have the features defined by Boehm~\cite{boehm81}; e.g.
analyst capability, required software reliability, and use of software tools.
Originally collected in the COCOMO-I format, 
JPL business experts have translated them from
their original COCOMO format to COCOMOII.

Both SEESAW and {\W}2 guided their search  using \eq{edt} and the
four $context$s of \tion{data}.
SEESAW used those $context$s to guide their ``what-if'' queries
around its COCOMO/COQUALMO models.
{\W}2 took  those $contexts$ then applied the seven step procedure described
above to  NASA93ii and COC81ii.
Recall that, in those steps, some $R_x$ was assessed on projects similar to the $context$
in a  $test$ set; i.e. all the cases in the $context$'s neighborhood.
Our comparison rig studied that same $test$ neighborhood using SEESAW and {\W}2.
We say that $rows_1$ and $rows_2$ are the rows selected from the neighborhood after applying
SEESAW's or {\W}2's recommendations (and by ``apply'', we mean reject any row that
contradicts the ranges in the recommendation).
From $rows_i$, we applied \eq{edt} to find $values_i$. 

\newcommand{\xxx}{\cellcolor[gray]{.8}} 
\input{figs/w2-vs-seesaw.tex}

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

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

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


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

In summary:
\bi
\item {\W}2's performance was better than SEESAW;
\item {\W}2 was more effective at reducing the medians;
\item Both case-based and model-based methods had similar issues with reducing the spread.
\item Possibly, the case-based approach of {\W} performs better on ``dirtier'',
nosier data than model-based methods.
\ei
%\begin{figure}[!t]
%\center
%\includegraphics[width=3in]{figs/changes.pdf}
%\caption{Range of changes in median and spread generated by applying
%the recommendations of either {\W} or SEESAW. The median observed
%changes were (34, 34)\% for (medians, spreads), respectively. The -94\% COC81ii OSP2 outlier has been omitted for clarity.
%}\label{fig:changes}
%\end{figure}
%We conducted statistical tests on each pair of {\W}2 vs SEESAW improvements in median/spread for each query.
%A Mann Whitney U test (95\% confidence) was performed on the two sets of reduction distributions from each comparison. The statistical tests are summarized in \fig{win-loss-tie}. Note that, in the majority case ($\frac{18}{24}$), {\W}2's case-based reasoning performs as well as $SEESAW's$ parametric modeling.
%
%\input{figs/win-loss-tie.tex}
%
%Also, where results differed, instance-based
%methods can perform much better than model-based.
%Observe the median reductions for NASA93ii OSP:
%{\W}2 offered median reductions of 72\%, 69\%, and 43\% compared to SEESAW's 22\%, 37\%, 13\% for defects, effort, and months respectively.
%