



There are an overwhelming number  of features that could possibly be
extracted from a software development (see \fig{features}) and not all of them
can be useful.
In order to find new and more useful static code features,
we propose to lever human expertise in a
two-step process:
\bi
\item
Let humans {\em propose} new features;
\item
Let artificial intelligence {\em dispose} the less useful features.
\ei

To put that another way,  we plan to change the problem of learning defect prediction.
Instead of focusing on fully automatic
{\em artificially intelligent} data miners
(an approach
which, we argued above, seems to have run its course), we will now experiment with {\em intelligent
assistants} that help humans to recognize faulty modules.

Intelligent assistants are not indicated when humans must process large data sets
(such large scale data analysis is  best left to automatic data miners).
Therefore, while preparing this proposal,  we checked the practicality of intelligent
assistants using
{\em under-sampling}  experiments~\cite{drummond03}.
In under-sampling, members of the majority class are randomly discarded
till the resulting training set has equal percentages of all classes. \fig{unders}
shows a sample of those results.
%Under-sampled data sets
%were generated of size $N$ with equal number of defective and
%non-defective modules.
In a result consistent with the ceiling
effect discussed above, learning from 50 examples (with
25 defective and
25 non-defective modules) worked as well
as using much larger data sets.
\begin{wrapfigure}{r}{2in}
\noindent
\includegraphics[angle=90,width=2in]{underPC5.pdf}
\caption{Under-sampling.
}\label{fig:unders}
\end{wrapfigure}
Note that the \fig{unders} results
are not unusual:  the general pattern of \fig{unders} (where learning from
a few dozen examples worked as well as anything else) repeats in eleven more
NASA defect data sets.

The results of \fig{unders} suggests that intelligence assistants could be a practical
technology for human-in-the-loop
defect prediction.
Our proposed tool for the
proposal/disposal process
combines a library of {\em feature extractors}, an
{\em incremental rule learning-in-context} environment, and {\em feature subset selectors}
to prune useless features:
\be
\item
 The feature extractors would assert facts;
\item
The relevant rules would be triggered by  the facts;
\item
Some code modules would be classified as ``defective'';
\item
After numerous repetitions of items 1,2,3, the feature subset selectors would
assess the features and reject the useless ones.
\ee
The rest of this section offers further notes on the above four-part process.

{\em Feature extractors} (FX) are the sub-routines used in rule-based
programming~\cite{bar83,buch84a,bucsmi89,forgy82,nasa91}.
 The FX
library summarizes interesting features of the environment, then asserts those features into
the working memory of the rules.
For example, the text mining features used in \fig{ttwo} were
found via feature extractors. Also, all the features of \fig{features} would be generated by the FX
library.

In the 1980s and 1990s, we built FX libraries to support numerous commercial rule-based
projects~\cite{me89zb,mebfd92,me88,men87,me92k}. These libraries grew at an exponentially decreasing
rate. Initially, ever new rule required another function in the FX library. After a while,
the authors of the rules started reusing old feature extractors rather than requiring new ones.
Assuming that pattern holds for this project, then we would expect:
\bi
\item
Early in this project,
we would be mostly {\em extending} the FX library;
\item Later in the  project,  we would be mostly {\em using} the FX library in rules.
\ei

{\em Incremental rule learning-in-context} (IRLIC) is  a maintenance technique
for
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 early
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 represented
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 an 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}.

Numerous 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 the IRLIC
{\em ripple-down-rules}  (RDR) method proposed by
Compton~\cite{compton92,compton90,gaines92a,preston93,richards97,compton05} and
explored by Compton, Menzies, and others~\cite{me01a,me92k,me97b}.
RDR use an internal data structure especially
optimized for maintenance.
RDR include an {\em except} slot:
\[\mbox{rule ID1 {\em if} condition
{\em then} except rule ID2 {\em then} conclusion {\em because} EXAMPLE}\]
\begin{wrapfigure}{r}{4in}
\includegraphics[width=4in]{rdr.png}
\caption{An example ripple-down-rule set.
}\label{fig:rdr}
\end{wrapfigure}
where:
\bi
\item $(ID1,ID2)$ are unique identifiers for different rules;
\item
{\em EXAMPLE} is the example that prompted the creation
of this rule and is conjunction of features extracted by the FX library
discussed above;
\item
the $condition$ is some subset of the EXAMPLE. i.e.
$condition \subseteq EXAMPLE$ (the method for selecting that
subset is discussed below).
\ei
Rules and their exceptions form an RDR tree
like that shown in \fig{rdr}.

At run time, an interpreter explores the rules
and their exceptions as follows.
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.

RDR constrains rule authoring as follows.
Recall that these rules are only ever added in response to some
new EXAMPLE that fails on the existing rules. That is, each
rule is useful for at least one example. Hence, in standard RDR,
incorrect rules are never deleted; 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 experts work in an RDR  environment,
they
watch EXAMPLEs running over the RDR tree,
intervening only when 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 RDR tree.
This process is remarkably rapid. Compton et.al. report average rule edit times between 30 to 120 seconds
for rule bases up to 1000 rules in size~\cite{compton05}.


Note one special case: a {\em feature failure} is when
an expert cannot find the feature they want to add to
the new condition. Feature failures take a while to handle
since they require
the addition of new feature extractor for the FX library. Repeating the comment above,
our experience with this kind of environment 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.

{\em Feature subset selection:} Recall our two step process:
humans {\em propose} new features
and AI {\em disposes} the less useful features. While
RDR is a useful way to capture
the {\em proposed} features, it has its limitations.
RDR patches rules in their context of their immediate parents
and it possible that the same patch will be applied in multiple sub-trees.
Also, RDR never checks if new features added lower in the RDR tree can assist
older rules higher in the tree.

Consequently, it is useful ever few weeks to  optimize and simplify
an RDR tree via  a global
analysis of the entire tree. We will use AI methods to
 simplify and optimize the RDR tree, thus implementing the {\em dispose} part of
our two-step process.
All the EXAMPLEs stored in the tree will be passed through
all the known feature extractors.
The resulting data will be passed with {\em feature subset selectors} (FSS)
to find the subset of the features that matter.

A repeated empirical observation is that many candidate features can be
ignored without degrading the performance of the learned theory.
How can ignoring information be useful?
Kohavi \& John~\cite{kohavi97} review studies with Naive Bayes
classifiers. The accuracy of such classifiers decreases very slowly
as irrelevant features are added to an instance set. However, the
accuracy of the same classifiers can degrade sharply as the number of
correlated features increase. Note that this observation is similar
to the original motivations for using  PCA: i.e.  learning is simpler
when highly correlated features don't conflate the learning process.

Another explanation for the success of FSS is offered by Witten \&
Frank~\cite{witten99}. They note that effective generalization
requires numerous examples. Decision tree learners recursively split
instances by ranking features according to how much they decrease
the diversity of the classes in the split sets. As learning
progresses, fewer and fewer instances are available to learn the next
sub-tree. If the instances contain too many features of similar rank,
then many splits are quickly generated. Hence, instances become
sparser in the sub-trees, and effective generalization becomes
harder.

Yet another explanation for the success of FSS comes from Gunnalan,
Menzies, {\em et.al.}~\cite{me03d} who argue that solvable problems
have an average case property called {\em small backbones}. Small
backbone problems contain a small number of variables that control
all other variables in the system. Learning the essential features of
small backbone problems means finding the variables that are either
in the small backbone or   highly correlated to the backbone
variables.


\begin{figure}
\begin{center}
{\small \begin{tabular}{r@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c}\\
&\multicolumn{11}{c}{number of attributes}\\\cline{2-12}
before:& 10&13&15&180&22&8&25&36&6&6&6\\
 after:& 2&2&2&11&2&1&3&12&1&1&2\\
reduction:& 80\%& 84\%& 87\%&94\%&90\%& 87\%&
88\%&67\%&
83\%&83\%&67\%\\\hline
$\Delta$accuracy: & 0\%&6\%&5\%&4\%&2\%&1\%&0.5\%&0\%&-25\%  &6\%
&7\%
\end{tabular}}
\end{center}
\caption{Feature subset selection using a WRAPPER of a decision
tree leaner. The $\Delta$Accuracy
figure is the difference in the accuracies of the theories
found by decision tree learner using
 the $before$ and $after$ attributes.
From \protect\cite{kohavi97}.}\label{fig:reduce}
\end{figure}PCA is a common FSS method used by statisticians.
WRAPPER is a common FSS method used by data miners.
In this method, a {\em target learner} is augmented
with a pre-processor that used a
heuristic search to grow subsets of the available features.
At each step in the growth, the target learner is called
to find the accuracy of the model learned from the current subset.
Subset growth is stopped when the addition of new features did
not improve the accuracy.
\fig{reduce} shows some WRAPPER results from  experiments
by Kohavi and John~\cite{Kol97}.
In their experiments, 83\% (on average)
of the measures in a domain could be ignored with only a minimal
loss of accuracy.
The advantage of the this approach is that,
if some target learner is already implemented, then the WRAPPER
is simple to implement. The disadvantage of the wrapper method is
that each step in the heuristic search requires another call to
the target learner; i.e. it may be very slow.

When the data set is too large for WRAPPER, an alternate
methods is  information gain attribute ranking (INFOGAIN). This is a simple and
fast method for feature ranking~\cite{Dum98}. This method measures
the split criteria of the class before and after observing a
feature. The differences in the split criteria gives a measure of
the information gained because of that attribute~\cite{quinlan92}.
A final comparison of this measure is used in feature selection.

Another FSS method is the RELIEF instance based learning
scheme~\cite{Kir92,Kon94}. RELIEF works by randomly sampling one
instance within the data. It then locates the nearest neighbors
for that instance from not only the same class but the opposite
class as well. The values of the nearest neighbor features are
then compared to that of the sampled instance and the feature
scores are maintained and updated based on this. This process is
specified for some user-specified M number of instances.

Yet another FSS method is CFS, or correlation-based feature selection.
 CFS uses subsets of
features~\cite{Hall98}. This technique relies on a heuristic merit
calculation that assigns high scores to subsets with features that
are highly correlated with the class and poorly correlated with
each other. Merit can find the redundant features since they will
be highly correlated with the other features. It can also identify
ignorable features since they will be poor predictors of any
class. To do this CFS informs a heuristic search for key features
via a correlation matrix.

Finally, another FSS is CBS (consistency-based subset evaluation). CBS is really a
set of methods that use class consistency as an evaluation metric.
For example, one CBS method
finds the
subset of features whose values divide the data into subsets with
high class consistency~\cite{Alm91}.


