%~~~~~~~~~~~~~~~~~~\begin{wrapfigure}{r}{3in}
%\begin{tabular}{|p{.95\linewidth}|}\hline
%\small
%After Fenton \& Pfleeger~\cite{fenton97}, we divide features into {\em personnel},
%{\em process}, and {\em product} features.
%
%{\em Personnel features} describe {\em who} built the product. These features might include the skills and training level of the development team.
%
%{\em Process features} describe {\em how} a product was built and includes items such as
%records of the the time taken to complete different tasks; descriptions of
%development process (waterfall, agile,\ldots); etc.
%
%{\em Product features} describe {\em what} was built. These features are extracted from any artifact used in the development process
%such as the
%static code features or requirements features used above in \fig{tone} and \fig{ttwo}.
%However, there is much more to product measures that just static code features. Other product features include
%early life cycle brainstorming artifacts
%(e.g. CRC cards~\cite{beck89}, QOC diagrams~\cite{fischer96}, etc); design diagrams (e.g. UML diagrams, GUI diagrams, etc);
%call graph features (e.g. what modules call what other modules); test cases;
%and traceability matrices linking test cases to source code to requirements (just to name a few). For model-based development, the list of product
%features is even longer
%and includes formal logic assertions or  descriptions of the internal state space of the program~\cite{pelanek04}.
%\\\hline
%\end{tabular}
%\caption{Kinds of features.}\label{fig:features}
%\end{wrapfigure}
%\noindent
%Our {\em goal}
%is
%automatic  quality predictors.
%The best predictors we have found so far have a
%$(pd,pf) \approx (70\%,25\%)$, over the NASA data sets described in ~\cite{me07d}.
%We seek better defect predictors with
%{\em lower} false alarm rates and {\em higher} probabilities of detection.
%In order to achieve this goal, we have a three-part plan:
%{\em short term} (year one); {\em longer term} (years two and three); and
%{\em extensions} (if time permits).
%
%\noindent {\bf 2.1. SHORT TERM (year1):}
%The case was made in the last section that
% our data mining algorithms have
%hit a ceiling effect; i.e. further research into the algorithms
%will suffer from
%diminishing returns.
%On the other hand,
%combining static code features with other kinds of features (such as features extracted from requirements)
%greatly improved the performance of our defect predictors.
%That is,
%our best current hope for finding better
%quality predictors
%is to explore the features used in the data mining
%(and not the data mining algorithms themselves).
%Therefore, in year one, we seek to better characterize the
%set of features usefully  predict for
%the quality of software artifacts.
%Some features are {\em expensive to collect}. For example,
%in the case of government contracts,
%sub-contractors may not wish to supply details regarding the skills
%of the programmers they assign to particular projects.
%Also
%{\em some features are useless}. Our Jan'07 TSE paper
%checked if subsets of the available features perform as well as some superset.
%In numerous data sets, it was found that removing
%McCabe measures such as cyclomatic complexity~\cite{mccabe76} did not increase $pf$
%or decrease $pd$.
%That is,  we found no business case for purchasing special toolkits for calculating those feature.

Building software quality predictors via data mining is really an
{\em inductive generalization} over (past) project's experience.
According to Mitchell's classic model of data
mining~\cite{mitchell97}, any inductive generalization explores
the {\em version space} of possible theories. These theories range
from ``believe nothing'' to ``believe everything''. In between is
the space of possible domain features joined together via
conjunctions, disjunctions, and negations. A learner searches  this
version space looking for ``peaks'' where, say, $pd$ is larger than
in the surrounding area. The ceiling effect, described in the
previous section, is consistent with the learners getting stuck on
a plateau that is {\em flat}; i.e. with no local peaks where the
learner can climb higher.

To build better quality predictors, we need to {\em introduce
additional topology}  into the search space. Our thesis is that
standard machine learning algorithms are blind to numerous business
concerns (described below) and once those concerns are included, new
peaks will appear in the search space that will allow us to break
through the ceiling effect. If this thesis is correct, then the key
to better software quality prediction is through the inclusion of
project specific business context knowledge, which we plan to
acquire as follows: 
\newpage
\be
\item Automated data miners {\em propose} quality predictors using some user-approved
business criteria;
\item
Humans can {\em change} and {\em maintain} the quality predictors
proposed by the data  miners. A log is kept of the  human
maintenance activities.
\item
A learner mines the log for {\em new} business criteria.
\item
The {\em new} business criteria updates the {\em old} business criteria.
\item Go to 1.
\ee
Note that this process
{\em succeeds} if it can quickly find quality predictors in new domains; {\em OR}
if it finds predictors better than the current
performance baselines; i.e. ($mean(pd,pf)=(71,25)$).

Also, this process is  {\em superfluous} if the human maintenance does not yield better
fault predictors and
{\em fails} if the human maintenance of the quality predictors is
time-consuming or too expensive. 

To test is our process succeeds or is superluous, we propose to:
\be
\item
Use {\em ROC curves}  or {\em generalized
utility hypercubes} to model the business  criteria.
\item Utilize {\em treatment learners}, which can
augment an AI-search algorithm with business  criteria;
\item Use a {\em ripple-down-rules} environment allow for the fast maintenance of
the rules learned by the treatment learners.
The environment keeps a history of why old rules
were patched.
\item
 Use a {\em preference learner} to query the ripple-down rules log to
update the business  criteria. \ee

{\bf 2.6 ORGANISATION \& SCHEDULE:}
Our tasks are as follows.



{\bf Task0- setting up:}
Before anything else can be done,
an initial setting up $task0$ is required.
In this task, 
\begin{wrapfigure}{r}{2.7in}\includegraphics[width=2.7in]{locplatonic.pdf}
\caption{Regions of a typical ROC
curve.}\label{fig:typical}\end{wrapfigure} 
we must create a population of users, expert in some suite of software.
These users would be needed to run the 
ripple-down rules environment (described below)
and our propose extensions 
To create those users,
graduate students would learn some code base.
Students would download code from some public repository (e.g. one of the
162,852 projects at \url{sourceforge.net}), compile it, then looked for bugs.
To facilitate this process, we would go back in time and access some very early
version of a project (e.g. v0.1) with a rich bug history (such bug histories are
available in the bug tracking systems of sourceforge).


{\bf Task1- Build the business  criteria user interface:} Our\newline
criteria 
will be expressed, among other methods, as weights\newline
 on the
axis of a {\em generalized utility hypercube}
representing\newline business level project characteristics.
These weights will be specified
via a specialized GUI interface.

Generalized utility hypercubes are our generalizations of
two-dimensional receiver-operator curves (ROC).  Such ROC were
originally used in the 1920s to discuss design trade-offs regarding
signal-to-noise ratio in radio receivers. A typical ROC curve is
shown in \fig{typical}. The y-axis shows probability of detection
($pd$), i.e., the probability of correctly detecting a module that
contains a fault, and the x-axis shows the probability of false
alarms ($pf$), i.e., the probability that a fault-free module will
be marked by the model as fault-prone.  By definition, an ROC curve
must pass through the points $pf=pd=0$ and $pf=pd=1$.  Three
interesting trajectories connect these points. A straight line
from(0,0) to (1,1) is of little interest since it offers {\em no
information}. Another trajectory is the {\em negative curve} that
has a relatively consistent tendency to incorrectly mark modules.
Elsewhere~\cite{me02e}, we found that negating 
tests can transpose a negative curve into a {\em preferred
curve}.

The point ($pf=0$,
$pd=1$) is the ``sweet spot'' on a ROC curve, i.e., it represents
the model with  perfect performance.  This is where we correctly
recognize all faulty modules and never make mistakes. The {\em
preferred curve} bends towards this ideal point. In the ideal case,
a predictor has a high probability of detecting a genuine fault
($pd$) and a very low probability of false alarms ($pf$). Building
such a perfect model is very difficult.  Typically, in software
engineering studies the only way to achieve high probabilities of
detection is to allow the model to mark modules as faulty more
often. This, in turn, incurs more false alarms.

We have argued for some time~\cite{me03a} that the {\em best} fault
detector depends on local business criteria; e.g. mission-critical
systems need different quality prediction requirements than, say, a
casual gaming application. For the latter, time-to-market is all
important and such systems can compromise, to some degree, software
quality in order to save on the QA budget. On the other hand,
failure acceptability in a mission-critical applications such as the
shutdown system of the nuclear power plant is minimal.  In terms of
the implied choice of suitable defect prediction models that could
be used in such different application environments, business
criteria demand defect detectors from different regions of
\fig{typical}. Hence, for ROC curves the business criteria is a
domain-dependent determination of the appropriate failure cost (or
failure criticality) driven balance between $pd$ and $pf$.

ROC curves are an example of a much broader class of business  criteria.
Given some rule with a {\em condition}, that condition can be scored via
multiple criteria. Apart from $pd$ and $pf$, there can also be:
\bi
\item
 The $cost$
of collecting the data required to test the condition; e.g. some
features require the purchase of expensive static analyzers or may
be very time-consuming to collect.
\item
The $effort$ associated with checking the results; e.g. all other
criteria being equal, if fault  prediction models that require you
to inspect 25\% of the modules might be  preferred to predictors
that require you to inspect 50\%.
\item
The {\em limited QA budget} may imply that only a small number of
modules, say 10 or 20, can be exposed to rigorous fault analysis. In
this case models than consistently correctly identify the top 10 or
20 fault prone modules will be preferred.
\item
The {\em relative cost or criticality of failures} that may occur if a
fault is not removed through QA activities gives a different weight
to the consequences of higher/lower probability of detection. Models
which provide an appropriate balance based on the failure cost
implications have been mostly ignored.
\item
The ability to create models from 
{\em small samples} may also be an
important requirement for environments in which the metrics /
features have not been collected in the past, or the development
process has been changed significantly.  Lower $pd$ and $pf$ may be
acceptable initially, if the model is able to adapt over time, i.e.,
continuing to learn from the project's progress.
 \ei

This is by no means an exhaustive list of business criteria. For
example, some software metrics might be more acceptable as
prediction features if they are drawn from a software development
process that local project managers hold in high regard (e.g. the
experience with some process maturity metric). That is, rule
conditions can be assessed via  business criteria $C$. Based on our
initial assessment, the set of criteria needs to include at least
those listed above:
{\em (pd,pf,cost,effort,QA budget limitations,failure cost,
learning rates )}. 
Our
hypothesis is that once we let users offer domain dependent business
criteria, this list will grow to $|C|{\gg}7$.

To handle an arbitrary number of business criteria, we propose to
score all conditions using a {\em generalized utility hypercube}
with $N$ dimensions. To allow for the comparison of criteria from
different scales, all criteria scores will be normalized to zero to
one scale using $\frac{score - min(score)}{max(score) - min(score)}$
(where $min$ and $max$ are the observed minimum and maximum range
for a particular criteria). One corner of this hypercube is the {\em
apex} where are the criteria have their preferred values; e.g. for a
two-dimensional hypercube representing an ROC curve, that corner is
$(pd,pf)=(1,0)$. All the examples can  be scored by their weighted
normalized Euclidean distance $D$ to the apex, or a more
sophisticated fusion criterion.  For example, if a condition scored
by $N$ criteria yields values $C_1,C_2,..C_N$; then
\begin{equation}\label{eq:d}
0 \le \left(D= \frac{\sum_i^N \alpha_i(C_i -
Goal_i)^2}{\sum_i^N\alpha_i}\right) \le 1\end{equation} where
$Goal_i$ is the ideal apex point for criteria $i$ and $0 \le
\alpha_i \le 1$ is the domain dependent weight offered by the user
(or inferred from the context) to criteria $C_N$. Note that
the overall goal is to minimize $D$; i.e. the distance to the ideal apex point. Also,
the utility weights $\alpha$ represent the business knowledge of the
domain; e.g. setting $\alpha_i=0$ effectively removes the $i$-th
criteria.

We believe that that $\alpha$ will change from domain to domain.
Capturing the $\alpha$ weights can be a non-trivial task since users
will have to offer subjective weight factors to a multitude of
criteria. The {\em business  criteria GUI} will be a tool that will
let us quickly capture locally preferred settings to $\alpha$. Some
experimentation will be required to find the right capture method
but, initially, we will try the multi-dimensional utility
elicitation techniques of Shaw and Gaines~\cite{shaw92}. Given $N$
criteria, the user will be offered pairs of randomly generated
examples of sets of criteria settings. The user's task is to declare
that one set is better than the other. After, say, $R=30$ such
presentations, a correlation matrix will be developed showing the
relations of each pair of weights $\alpha_i,\alpha_{j\not=i}$. Using
the first $X=3$ components found by a principle components analysis
of this matrix, clusters will be formed around sets that the user
liked and disliked. The user is then presented with $R=30$ more
examples but this time, inside our modeling engine, the GUI will use
the clusters to guess which set the user will declare to be
``better''. This process stops when the GUI can correctly guess the
users decision in $Z\%$ of offered examples, at which point we know
that the GUI has captured the user's $\alpha$ weight factors. The
research activities of this first task will include developing the
above described elicitation process and tools as well as an
evaluation of the appropriateness of this method.  Determining the
best settings of the ``magic" numbers $<R,X,Z>$ and checking the
stability of these weights across multiple users working in the same
domain represent the further research challenges.

{\bf Task2: Implement a Criteria-based Search:} Having defined
customizable business  criteria, we now must apply it at the very
core of any data mining technique for developing software quality
prediction models. One method for implementing this is to use a {\em
treatment learning}
algorithm~\cite{clark05,me02c,me03c,me04a,me02f,me03j,me03r,me06b}.
Treatment learners hunt for a {\em minimal difference set} between
desired and undesired concepts.  In the context of software quality,
that would be fault-free and faulty modules). Internally, the
treatment learner maintains a list of conditions, sorted by the $D$
score of \eq{d}. Initially, this list  just contains the ranges of
the known features, discretized into bins\footnote{Discretization
divides a potentially infinite numeric range into a small number of
bins. Many discretization methods exist - this research will
experiment with Fayyad\&Irani's entropy-based
measure~\cite{FayIra93Multi} or one of Webb's weighted bin
schemes~\cite{yang02}.}. In this initial state, a treatment learner
treats all the items as simple rules of the form {\mbox {\em if
feature=$bin_x$ then defective}}. These rules are then
combined via a stochastic beam search: \be
\item
 Randomly select any two items,
favoring those with higher $D$ scores (from \eq{d}).
\item
Combine these two items into a larger
more specific condition;
\item
Score the new combined item by its {\em lift} i.e. how much
the \eq{d}  score of the rule is greater than alternative rules.
\item
Insert the new combined item back into the sorted list.
If the combined item scores poorly, it sorts to the end of the list and
is unlikely to be picked again.
\item Goto 1
\ee Initially, all the items will test just for one value; e.g.
$feature=bin_x$. Subsequently, items may be of size 
\mbox{$\ge 1$} so
items will be of size $\ge 2$.

We prefer treatment learning to other data miners for three reasons.
Firstly, the above stochastic search scales to very large data sets.
In an era when software systems may contain tens or hundreds of
thousands of modules, this is essential.  Secondly, treatment
learners make no assumptions about the scoring function. Hence, the
scoring function can change if and when any new business criteria is
discovered. Thirdly, in many experiments, we have found that the
minimal difference set that {\em distinguishes} the two concepts is
often much smaller than a {\em description} of the two concepts.
Treatment learning finds that minimal difference set via the {\em
lift} calculation. This means that treatment learners generate very
small rule sets. Such brevity is vitally important for any
human-in-the-loop process (such as in this proposal). Cognitive
scientists and researchers studying human decision making note that
humans often use simple models rather than intricate
ones~\cite{giger96}. Standard machine learners
(e.g.~\cite{bay99,cai98,quinlan92}), on the other hand, can generate
overly elaborate models that complicate, rather than clarify, a
situation.


{\bf Task3- Build a Human-in-the-Loop Maintenance Environment:}
Treatment learning converts a set of examples to set of quality
detectors, sorted by $D$. It is vital to our process that humans
actively critique these detectors, looking for missing knowledge or
knowledge that needs elaboration. For example, a human reviewer of
the rules might propose collecting new kinds of data like the
text mining features of \fig{ttwo}.

Therefore, once we  {\em initialize}  the quality prediction models
using treatment learning, we will then: \bi
\item
{\em Maintain} them using some human-in-the-loop maintenance
principle.
\item
When necessary (``necessary'' will be defined below), the quality
prediction models will {\em reinitialize} using treatment learning,
plus any new business  criteria learned during the maintenance
phase. \ei

{\em Ripple-down rules} is  a maintenance technique for rule-based
programs initially developed by
Compton~\cite{compton92,compton05,compton90,gaines92a,preston93,richards97}
and explored by Compton, Menzies, and
others~\cite{me01a,me92k,me97b}. In this proposal, ripple-down rules
would initialize its rules using the output of treatment learning.

Note that ripple-down rules are not just a maintenance environment.
They also provide a {\em discovery} environment for recognizing
missing knowledge, as well as a method for {\em applying} that
missing knowledge, once it has been operationalized. We will use
this aspect of ripple-down rules to learn new business criteria.

Ripple-down rules are best understood by comparison with standard
rule-based programming. In standard rule-based programming, each
rule takes the form {\em rule ID {\em if} condition {\em then}
action} where $condition$ is some test on the {\em current case}. In
the 1970s and early 1980s rule-based systems were hailed as the cure
to the ills of software and knowledge
engineering~\cite{buch83,buch78,buch84}. Rules are useful, it was
claimed, since they represent high-level logic of the system
expressed in a simple form that can be rapidly modified. However, as
these systems grew in size, it became apparent that rules were
surprisingly harder to manage. One reason for this was that, in
standard rule-based programming, all rules exist in one large global
space where any rule can trigger any other rule. Such an open
architecture is very flexible. However, it is also difficult to
prevent unexpected side-effects after editing a rule. Consequently,
the same rule-based programs hailed in early 1980s~\cite{mcderm81}
became case studies about how hard it can be to maintain rule-based
systems~\cite{vandebrug86,mcderm93,soloway87}.

Many  researchers argued that rule authors must work in precisely
constrained environments, lest their edits lead to spaghetti
knowledge and a maintenance
nightmare~\cite{marcus89,marcus87,marques92,sch94,sch99}. One such
constrained environment is ripple-down rules that adds an {\em
except} slot to each rule:
\[\mbox{rule ID1 {\em if} condition
{\em then} except rule ID2 {\em then} conclusion {\em because} EXAMPLE}\]
\begin{wrapfigure}{r}{3.8in}
\begin{center}
\includegraphics[width=3.8in]{rdr.png}
\end{center}
\caption{An example ripple-down-rule set.
}\label{fig:rdr}
\end{wrapfigure}
Here,
$(ID1,ID2)$ are unique identifiers for different rules;
{\em EXAMPLE} is the case that prompted the
creation of the rule (internally, EXAMPLEs
conjunction of features); and
the $condition$ is some subset of the EXAMPLE, i.e., $condition
\subseteq EXAMPLE$ (the method for selecting that subset is
discussed below).
Rules and their exceptions form a ripple-down rule tree are shown in
\fig{rdr}.

At run time, a ripple-down rule interpreter explores the rules and
their exceptions. If the condition of rule ID1 is found
to be true, the interpreter checks the rule referenced in the {\em
except} slot. If ID2's rule condition is false, then the interpreter
returns the conclusion of ID1. Else, the interpreter recurses into
rule ID2.

Ripple-down rules constrain rule authoring as follows. Recall that
these rules are only ever added in response to some new EXAMPLE.
That is, each rule is useful for at least one example. Hence
ripple-down rules never delete old rules; rather they are patched
with {\em except} rules. These {\em except} rules cover the special
case that confused the parent rule. If the parent rule with
$condition1$ has
 $EXAMPLE1$ and the new rule
is being created in response to $EXAMPLE2$, then the new rule's
$condition2$ must be formed from the features not used in the parent
rule and must hold for the new $EXAMPLE2$; i.e.
\begin{eqnarray}\label{eq:one}
condition2&=&EXAMPLE1 - condition1\\\label{eq:two}
condition2 &\subseteq& EXAMPLE2
\end{eqnarray}

When users work in an ripple-down rules  environment, they watch
EXAMPLEs running over the ripple-down rules tree, intervening only
when they believe that the  wrong conclusion is generated. At that
point, the environment generates a list of features to add to
$condition2$ (this list is generated automatically from \eq{one} and
\eq{two}). The expert picks some items from this list and the patch
rule is automatically to the ripple-down rules tree.

Note one special case: a {\em patch failure} occurs when the user
cannot find the feature he or she wants to add to the new condition.
In terms of adding new business knowledge into a software quality
prediction model, a feature failure is a very important event. Patch
failures let us recognize what is {\em missing} and what should be
{\em added} to the system. Patch failures occur  when users inject
their domain knowledge to say that there is some important, but
currently absent, part of the rules. For example, on patch failure,
the user may demand: \bi
\item That a new feature be added. For example, \fig{ttwo} could result if the user demands text
mining features from related requirement documents.
\item That an existing $\alpha_i$ weight be adjusted.
\item That a new criteria be added. For example, users might note that some condition works
in so few cases that their  $support$ criteria  only allows rules
that are true for (say) 10\% of the training set. \ei



Without patch failures, ripple-down rules are a very rapid rule
maintenance environment. Compton et.al. report average rule edit
times between 30 to 120 seconds for rule bases up to 1000 rules in
size~\cite{compton05}.

Patch failures are slower to handle since they require some
additional programming for the environment, plus the support code to
extract that feature from the project databases. Our experience with
this kind of environment~\cite{me01a,me92k,me97b} is that,
initially, much of the time is devoted to handling feature failure.
Later, feature failures become very rare and experts can rapidly
enter rules. The research goal of Task 3 will be to check if the
frequency of  patch failures asymptotes downwards. Otherwise, the
ripple-down rules environment would be too slow and cumbersome for
practical usage.

{\bf Task4-  Update the business criteria:} Ripple-down rules
incrementally patch old knowledge via local additions of {\em
except} clauses. Such patching is both {\em fast} and {\em useful}
since it ensures that the users will not suddenly see radically new
and unfamiliar knowledge about fault prediction in their project.

Despite this, there are occasions when it is 
useful to
perform a global reorganization of a ripple-down rules environment.
First, at some point, local repairs lead to overly complex
expression of knowledge. Second, and more important for our work,
our method for breaking through the performance barrier in software
quality modeling is based on adding more topology to search using
the treatment learning techniques.

From a technical viewpoint, updating a treatment learner's business
criteria and  reinitializing the rule base is a relatively simple
matter. We saw above that business criteria and new features are
added every time there is a patch failure in the ripple-down rules
environment. A global  reorganization requires:\bi
\item
Augmenting all  EXAMPLEs, all new features found in Task 4.
\item
Re-compiling our treatment learner  with \eq{d}  updated with  all the
changed and new $\alpha_i$ weights.
\item
Re-running the new treatment learner on the augmented examples.
\ei
While simple to implement, this re-initialization is  critical to this research:
\bi
\item If we have
correctly diagnosed the ceiling effect, then these
revised rules should perform significantly better than the results
seen in \fig{tone} and the baseline results seen in current
literature~\cite{me07b}.
\item
Otherwise, this line of research will have not been successful.
\ei
