{\W}2 is a simple, data-agnostic case-based reasoning tool for software quality optimization. Given a dataset of historical cases and a range of controllable attributes within that space, {\W}2 recommends changes that offer the best utility within that space.

In the case of software projects, {\W}2 recommends changes that best improve estimated software quality given a description of a potential new project.

\begin{figure}[!h]
\begin{center}
         \includegraphics[scale=0.75]{figs/cbrcycle1.png}
         \caption{Four steps of case-based reasoning, from \protect\url{http://www.peerscience.com/intro_cbr.htm}.}
         \label{fig:cbr}
 \end{center}
\end{figure}

\section{Case-Based Reasoning}

An opposite approach to model-based methods is case-based reasoning (CBR), also referred to as instance-based reasoning. In CBR, there are no universally-applicable models. Rather, every conclusion is dependent on the particulars of the task at hand. CBR is based on a theory of {\em reconstructive memory}. According to this theory, humans do not remember things as they actually happened. Rather, ``remembering'' is an inference
process, characterized by Bartlett as:
\begin{quote}
{\em ... a blend of information contained in specific traces encoded at the time it occurred, plus 
{\em (retrieval time)} inferences based on knowledge, expectations, beliefs, and attitudes derived from other sources~\cite{bartlett32}.}
\end{quote}
Bartlett's work was ignored when first published (1932) but today it is highly influential; e.g.
experts in psychology \& law caution reconstructive memory means that {\em leading questions} can significantly alter a report given by a human witness~\cite{loftus03}.

In AI research, Janet Kolodner~\cite{kolodner83} used reconstructive memory to characterize expert explanations.  To support her claim, she offered a set of transcripts of experts explaining some effect.
Her reading of those transcripts was that the experts do not use {\em verbatim recalling}  when discussing the past. Rather, they {\em reconstruct} an account of their expertise, on the fly, in response to a particular query.

Inference using case-based reasoning is usually characterized~\cite{aamod94} in four steps:
\be
\item \textit{Retrieve}: Find the most similar cases to the target problem. 
\item \textit{Reuse}: Adapt our actions conducted for the past cases to solve the new problem.
\item \textit{Revise}: Revise the proposed solution for the new problem and verify it against the case base.
\item \textit{Retain}: Retain the parts of current experience in the case base for future problem solving.
\ee


Having verified the results from a chosen adapted action on the new case, the new case is added to the available case base. The last step allows CBR to effectively learn from new experiences. In this manner, a CBR system  is able to automatically maintain itself.

In terms of cognitive theory, CBR challenges notions of reasoning as model-building.
The mantra of CBR is ``don't think, remember''. That is, when faced with some new situation:
\bi
\item
Do not reason it out using some underlying model (e.g. Newton's equations or Boehm's parametric models).  
\item
Rather, respond to a new situation via an on-demand survey of past experiences \cite{schank83}. 
\ei

(Note that we call CBR {\em model-lite}, but not {\em model-free}. For more on this distinction, see \tion{modellite}.)

The above discussion motivates a comparison between parametric model-based methods and CBR. To make that
comparison,  we need to explore the same task with two different approaches. Accordingly, this section describes the general principle of contrast set learning behind quality optimization, then describes two specific implementations using SEESAW's parametric models or {\W}2's case-based reasoning.

%One thing that may not be apparent from the following discussion is the relative complexity of the two systems.
%Based on recent experience with teaching graduate AI, we assert that building and assessing SEESAW is a term project while {\W}2 can be implemented in two weekly homework assignments (week1 implements some basic data loading and nearest neighbor measures; week2 extends that code
%to complete {\W}2).

\section{Contrast Set Learning (CSL)}\label{sect:csl-description}

One process for self-improvement is to emulate those around you that are doing well. For example, imagine a failing student seeking recommendations to improve their grades. Standard parental advice may be to simply study more. However, while such general platitudes may indeed bring improvement, they ignore any local lessons about their life that may bring more success with less effort.

Instead, students being social creatures, they seek out advice from those around them. Given that close friends and colleagues are most likely under the same pressures, it makes sense to seek advice from those in similar circumstances. Then, a rationally-minded student may divide their friends and colleages into two groups: those doing well (to serve as role models), and those not doing so well (to serve as cautionary tales). Finally, the student adopts as many traits they perceive as unique to the role models.

Such a processes allows for multiple, targeted avenues of improvement compared to generic idioms such as ``study more.'' So, the student finds that by avoiding Tuesday parties, asking questions after class, and sitting towards the front of the room, success is achievable. In other words, local lessons offer a more tailored approach to improvement.

Contrast set learning (CLS) applies this process by asking the question "What are my role models doing that I'm not?" Formally, this takes place in three steps:

\bi
\item {\em Relevancy Filtering} - Find examples similar to the problem at hand.
\item {\em Utility Separation} - Divide the relevant examples into two populations based on some utility measure: those I want to imitate (the {\em best}) and those I don't want to imitate (the {\em rest}).
\item {\em Contrast Set Generation} - Perform a greedy search on attributes that occur more often in {\em best} than in {\em rest}. Rank these attributes by some {\em score} that favors contrast, biasing towards attributes that occur often in {\em best} but rarely or never in {\em rest}.
\ei

A simple strategy to score more favorably towards attributes that occur most often in the best case is to square the number of times they occurs. Taking this heuristic one step further, given an attribute $x$, we can penalize $x$'s occurrence in the "rest" by dividing the sum of the frequency counts in best and rest~\cite{me09f}, the ensuring rare attributes are weighted appropriately:

\begin{equation}\label{eq:br}
like = \frac{freq(x\vert best)^2}{freq(x\vert best) + freq(x\vert rest)}
\end{equation}

From this measure we need only sort each attribute by it's $like$ score to prioritize our recommendations. Thus, we establish a means for finding attributes that most drive us towards our desired goal. An alternative to Equation~\ref{eq:br} is to log the odds ratio between an attribute appearing in {\em best} rather than {\em rest}~\cite{mozina04}.

%The cognitive basis of case-based reasoning offers an alternative to model-based approaches for software quality estimation. One can relate the use of a model as an attempt to extrapolate a single, general, {\em verbatim recollection} of knowledge in order to infer about any related problems. For example, consider the case of Brooks' law. Brooks' law states that adding more programmers to an already delayed project will only delay it further. Thus, a general, model-based approach for software quality would state:
%\begin{quote}
%{\em Do not add programmers to an already delayed project if schedule deadlines are important.}
%\end{quote}

%These general guidelines are similar to the scale factors and effort multipliers of the USC COCOMO model ~\ref{fig:coc1}. In the case of COCOMO, for example, very low analyst capability ({\em pcap}) always signals a shift towards greater project effort and lower software quality. By combining these guidelines into a general model as Boehm has done, we can use tools like SEESAW to optimize software quality given a constrained query on the software project considered.

%Because of the many issues regarding SEESAW's model-based approach already outlined, we have devised a modification of CBR that attempts to instead {\em reconstruct} smaller, local accounts of what drives better software quality. Using CBR as a guide, we seek a way to {\em retrieve} relevant information about a software project, {\em reuse} that information to extract possible improvements, {\em revise}  our proposed quality estimate, then {\em retain} this knowledge for future estimates.

%We refer to this simple process as Contrast Set Learning. CSL seeks to optimize the choice of potential actions based solely on what how similar, historical instances implementing those actions have performed. In terms of software quality: given a manager's possible decisions and accounts of past decisions, which decisions are most likely to improve software quality?

%CSL extracts these decisions using {\em contrast sets}. From the pool of historical cases, those most similar to the project at hand are selected. From this local neighborhood, cases are sorted based on some utility measure such as software effort. Two sets are formed, one labelled ``best'' that contains the most desireable cases, and one labelled ``rest'' that contains the remaining cases. The contrast set consists of the attributes that occur more often in ``best'' than ``rest''. That is, attributes that occur frequently in only one population tell us more than attributes that appear in both. Such attributes provide more \emph{contrast} between the populations. That is, high contrast attributes better encapsulate the properties that separate the two populations, whereas attributes with low contrast tell us very little about the space as a whole.

%\subsubsection{A Worked Example of CSL}

%For example, consider a company faced with a software project that is sprialling out of control. Currently they are missing deadlines, lack funding, and lack programmers. Management decides to solve this problem by hiring additional programmers. Not surprisingly, in accordance with Brooks' law, the additional training time causes the project to be delivered even later, and now grossly over budget.

%Using contrast set learning, management would instead look at past projects from the same or similar departments. Say the best projects (those requiring the least effort) were either given additional funds or allowed to extend their deadlines $best=(more-money|extend-deadlines)$. Now consider that the remaining projects (those requiring the most effort) were either given additional programmers or allowed to extend their deadlines $rest=(more-programmers|extend-deadlines)$.

%Looking at these decisions we can infer little effect from extending deadlines, as this change occurred equally in both the $best$ and $rest$ sets. Thus, it provides little contrast. However, both adding funding and adding programmers present {\em high-contrast}. Only the best projects involved adding money, and only the worst projects involved adding programmers.

\section{The {\W}2 Algorithm}\label{sect:w-desc}

CSL describes a general strategy for reasoning about two distinct populations. Because CSL requires no underlying model to implement, we originally created {\W} to add CSL decision power to case-based reasoning software cost estimates. Upon further experimentation, we improved upon {\W} by removing the kth nearest neighbor calculation in favor of simply using our {\em overlap} measure to perform relevancy filtering. The original description of {\W} can be found in ~\cite{me10c}. We offer a statement on performance between {\W} and {\W}2's in the ~\tion{runtimes} and ~\fig{bestoverlap-vs-knn}.

{\W}2 answers the question: ``What can I change about this project to make it more like best cases?'' In other words, ``How can I best imitate what I aspire to be?'' To answer this, {\W}2 requires two sets of information:
\bi
\item A set of historical cases $C_i$ with quantified attributes (say, management experience, lines of code) and some measure of utility (say, effort in man-months, total defects, months for development). All attributes have been discretized into a small number of ranges (e.g. manager experience $\in \{1,2,3,4,5\}$ denoting
very low, low, nominal, high, very high respectively)
\item A query $q$ describing the current project seeking improvement, with defined ranges for potential changes, as well as any constraints that cannot be changed. For example, if we are interested in a schedule over-run for a complex, high reliability project that has only minimal access to tools, then those constraints can be expressed in the syntax of \fig{nasaproj}. 
\ei
\begin{figure}[!t]
\begin{verbatim}
@project brookslaw
@attribute apex 2
@attribute plex 1 2
@attribute ltex 1 2 3
@attribute ?pmat 2 3
@attribute ?rely 3 4 5
@attribute ?data 2 3
@attribute ?cplx 4 5
@attribute ?time 4 5
@attribute ?stor 3 4 5
@attribute ?pvol 2 3 4
@attribute ?acap 3 4 5
@attribute ?pcap 3 4 5
@attribute ?tool 3 4
@attribute ?sced 2 3
\end{verbatim}
\caption{The Brooks' Law Query for the NASA93 dataset in COCOMO II format.}\label{fig:brooks}
\end{figure}

{\W}2 is easily demonstrated visually. ~\fig{brooks} demonstrates a query representing a project query $q$ involving Brooks' Law ~\cite{brooks75} using 93 NASA project cases in COCOMO format. In the 1970's, Brooks noted that software production is a very human-centric activity and managers need to be aware of the human factors that increase/decrease productivity. For example, a common practice at that time at IBM was to solve deadline problems by allocating more resources. In the case of programming, this meant adding more programmers to the team. Brooks argued that this was an inappropriate response since, according to Brooks' law ``adding manpower [sic] to a late software project makes it late''. The reason for this slowdown is two-fold:
\bi
\item The more people involved the greater the communication overhead. While this is certainly an issue if all parts of the software system are accessible to all other parts, with an intelligent module design, this first issue can be mitigated.
\item The second issue is more fundamental. Software construction
is a complex activity. Newcomers to a project suffer
from inexperience in the tools, the platform, the problem domain,
etc.
\ei
The query in ~\fig{brooks} models this second issue. Attributes with a ? represent controllable attributes, with {\em apex, plex}, and {\em ltex} representing the uncontrollably lower ratings of analyst experience, programmer language experience, and language and tool experience, respectively.

%\subsubsection{The {\W}2 Algorithm}

First, cases are randomly separated into 67\% Training and 33\% Testing sets. Then, {\W}2 implements the same three steps used for CSL. Finally, {\W}2 estimates the impact of its recommendations:

\subsection{Relevancy Filtering}

\input{figs/train-filter.tex}

From Training, 20 cases are selected with the highest total {\em overlap} with the project query (~\fig{train-filter}). For example, if a case had a schedule rating of {\em high}, and $q$ defines the controllable scedule range as potentially {\em high} or {\em very high}, then that attribute is said to {\em overlap} with the query. This is the {\em retrieve} step in Standard CBR nomencalature.

\subsection{Utility Separation}

\input{figs/train-contrast.tex}

The 20 cases are then sorted by some utility measurement, with the top 5 cases placed into the {\em best} set and the remaining 15 into the {\em rest} set (~\fig{train-bestrest}). For datasets with multiple goals, such as the NASA93 and COC81 datasets that contain project effort, defects, and months, a utility function normalizes each value into a single utility ``score''. Other datasets simply minimize software effort in man-months. This is the first half of the CBR {\em reuse} (or adapt) step.

\subsection{Contrast Set Generation}

\input{figs/train-bestrest.tex}

Changes to $q$ are ranked according to equation \ref{eq:br}. This sorted order $S$ defines a set of candidate $q'$ queries that use the first {\em i-th} entries in $S$ (~\fig{train-contrast}):
\[
q_i' = q \cup S_1 \cup S_2 ... \cup S_i
\]

In the Brooks' Law example, {\W}2 learns that {\em pmat=3} scores the highest for reducing development effort. This is the last half CBR {\em reuse} (or adapt) step.

At this point, {\W}2 has created a ranked list of recommendations that best drive $q$ towards more desirable utility measures (~\fig{train-bestrest}). However, we do not yet have an estimate as to the impact of applying these recommendations. The next phase of {\W}2 estimates the improvement in software quality after applying $q_i'$.

\subsection{Estimating Impact}

\input{figs/test-constrain.tex}

According to \fig{cbr}, after {\em retrieving} and {\em reusing} comes
{\em revising} (this is the ``verify'' step).
When revising $q'$, {\W}2 prunes away irrelevant ranges using the algorithm of \fig{w}.

On termination, {\W}2 recommends changing a project according to the set $q'-q$.
For example, in \fig{nasaproj}, if $q' -q$ is $rely=3$ then this treatment recommends
that the best way to reduce the effort for this project is to 
reject $rely=4\;or\;5$.

Formally, the goal of {\W}2 is find the smallest $i$ value such that
$q_i'$ selects cases with the more of the {\em better} estimates.
The reader might protest that the generation of some succinct human-readable construct like $q_i'$ means
that {\W}2 is not a ``real'' case-based reasoner. In that view, the distinguishing feature of CBR
is that its reasoning is case-based and it never generates any generalizations.

\begin{figure}
\center
\begin{tabular}{|p{.95\linewidth}|}\hline
	\be
	\item Set $i=0$ and $q_i'=q$ 
	\item Let $Found_i$ be  the test cases consistent with  $q_i'$ (i.e. that
do not contradict any of the attribute ranges in $q_i'$).
	\item Let $Effort_i$ be  the median efforts seen in $Found_i$.
	\item If $Found$ is too small then terminate (due to over-fitting). 
After Shepperd~\cite{shepperd97}, we
terminated for $|Found|<3$. 
	\item If $i>1$ and $Effort_i < Effort_{i-1}$, then terminate (due to no improvement).
	\item Print $q_i'$ and $Effort_i$.
    \item Set $i=i+1$ and $q_i'= q_{i-1} \cup S_i$ 
	\item Go to step 2.
	\ee\\\hline
\end{tabular}
\caption{Revising $q$ to learn $q'$.}\label{fig:w}
\end{figure}

In reply, we observe that 
{\W}2 is not the only system that extends standard CBR with some generalization tools.
Watson~\cite{watson98} reviews numerous CBR systems that, for example, run decision tree
learners over their case library in order to automatically generate an index to the cases. 
Also, once
a system can read a case library,
compute distance calculations, and generate a sorted list of the nearest neighbors, implementing
\fig{w} and \eq{br}
is only a few dozen lines of code. That is, {\W}2 is such a  small extension
to standard CBR that it would be somewhat pedantic to declare that it is not ``real'' CBR.


%Software estimates are reported as the median class value of some local neighborhood. This neighborhood is typically defined as the Euclidean distance from a defined project in n-dimensional space with n project features~\cite{shepperd97}. {\W} works similarly , but defines a project as a range of values:
%\bi
%\item From a range of project values, cases are retrieved that match a specific amount of \emph{overlap} with the defined project ranges. A case's overlap is defined as the percentage of attributes that fall within the specified ranges of the defined project.
%\item From these selected similar cases, the cases are sorted by a measure of utility to determine the {\em better}
%examples.
%\item From these sorted ranges, a \emph{contrast set} is learned. The top 5 "best" cases (those with the best utility measure) are placed into a set labeled "best". The next 15 ranked cases are placed into a set labeled "rest", for a combined total of 20 cases.
%\item From the contrast set, {\W} selects the features that best select for the region with the best utility measurements.
%\ei
%In the above, {\em better}  is determined by some
%domain-specific predicate.
% In the case of effort, defect, and month estimations, this utility is the normalized euclidean distance from the lowest possible cost for all three factors.

%\subsubsection{Contrast Sets}

%Once a contrast set learner is available, it is a simple matter to add {\W} to CBR.  {\W} finds contrast sets using a  greedy search, where candidate contrast sets are ranked by the frequency of which they appear in the "best" set squared divided by how often the candidate appears in both the "best" and "rest" sets. A simple strategy to score more favorably towards attributes that occur most often in the best case is to square the number of times. Taking this heuristic one step further, given an attribute $x$, we can penalize $x$'s occurrence in the "rest" by dividing the sum of the frequency counts in best and rest~\cite{me09f}, the ensuring rare attributes are weighted appropriately:

%\begin{equation}\label{eq:br}
%like = \frac{freq(x\vert best)^2}{freq(x\vert best) + freq(x\vert rest)}
%\end{equation}

%From this measure we need only sort each attribute by it's $like$ score to prioritize our recommendations

\begin{figure}[!t]
\begin{verbatim}
@project example
@attribute ?rely 3 4 5 
@attribute tool  2 
@attribute cplx 4 5 6 
@attribute ?time 4 5 6
\end{verbatim}
\caption{{\W}2's syntax for describing
the input query $q$. Here,  all the values run 1 to 6.
$4\le cplx \le 6$ denotes projects with above average complexity.
Question marks denote what can be controlled- in this
case, $rely,time$ (required reliability and development time)}
\label{fig:nasaproj}
\end{figure}

On termination, {\W}2 recommends changing a project according to the set $q'-q$.
For example, in \fig{nasaproj}, if $q' -q$ is $rely=3$ then this treatment recommends
that the best way to reduce the effort for this project is to 
reject $rely=4\;or\;5$.

\section{Measuring Performance}

To compare the effectiveness of different treatments,
we offer the following performance measures:
\bi
\item All our measures are taken from the test set.
\item The $as is$ values are from the neighborhood
of the $context$; e.g. the $effort$ column.
\item
The $to be$ values are from the cases selected
by a treatment; e.g. the $effort$ column.
\item
The $median$ of a distribution is the 50-th percentile of the sorted values in that distribution.
\item
The $spread$ of a distribution is the (75-25)th percentile of the sorted values. 
\item
The $improvement$ from $a=as is$ to \mbox{$t=to be$}  is 
$100*(a - t)/a$.
$Larger$ improvements are better.
\ei
For example, consider $pmat=3$:
\bi
\item Without the $pmat=3$ restriction, the median and spread
in the test set are  235 and 633 months, respectively.
\item With $pmat=3$,
the median and spread of  projects similar to $context_1$ are 81 and 353 months (see \fig{testing-constrained}).
\item The observed improvement in the median  is hence 66\%.
\item The observed improvement in the spread is hence 44\%.
\ei
