
\section{Adding Business Knowledge}
\PARstart{T}he above results offer much support
for the limited information hypothesis.
In those  results,
our learners' performance did not improve after:
\
\bi
\item
{\em RandomReduction}: 100 randomly selected examples;
\item
{\em StructuredReduction}:
25 examples each of  defective/non-defective modules.
\ei

If limited information content is the problem, then the solution is clear: 
give the
data miner more information.  However, as shown above, 
it is {\em not} useful to use more examples of the {\em same}
kinds of data.
Rather, we need to give our learneres   {\em different} kinds
of information.


One different kind of knowledge, not found in the training data of \fig{data},
is the criteria  by which a learner will be assessed.
We will call this {\em evaluation} criteria $C_2$ since it is applied after
another criteria $C_1$ is used by the leaner to build a model.

The evalaution criteria $C_2$ can change, depending on the business application.
For example:
\bi
\item In $application_x$, a quality assurance (QA) team has insufficient budget to
inspect all the code. Therefore, they need some {\em sorting} policy that increasing
the defect frequency in modules that are ranked high in the sort. In this application,
$C_2$ rewards {\em minimizing} the inspection effort while {\em maximizing} the
number of defective modules they discover.
\item In $application_y$,
the manager of a new contract between a V\&V consultancy and a client may feel the need
to impress the client. In which case, she may direct her engineers
to skim all the code looking for some single high severity error. The priorities
of $application_y$ are different to
$application_x$ in that the former will condone a review of all the code (at least,
at very high speed) while the latter only wants to see {\em some} of the code.
\item In $application_z$, a company is maintaining a  large and stable code base. 
In this situation,
the number of new modules written/change per day may be very low so
there may be no backlog of modules to inspect so there may be no need for data miners to prioritize
the inspection effort.
\ei
In theory, data mining could use the evaluation criteria
$C_2$ to guide their search for better predictors.
In practice, this is often not the case.
For example:
\bi
\item[$C_1$]:
During {\em training}, a decision-tree learner may stop branching if the diversity of the instances in a 
leaf of a branch\footnote{For numeric classes, this diversity measure might  be the standard deviation of the class feature.
For discrete classes, the diversity measure might be the entropy measure used in J48~\cite{witten05}.}
falls below some heuristic threshold.
\item[$C_2$]: 
During {\em testing}, the learned decision-tree might be tested on any of the criteria shown in \fig{measures}.
\ei
By this line of reasoning, we have an explanation for the ceiling effect described above: {\em our learners
are blind to their purpose}. If some business application demands $C_2$ and our learners train on $C_1$ 
($C_1\not=C_2$), then it is hardly surprising that they cannot find ways to improve their performance.

Some learning schemes support
biasing the learning according to the overall goal of the system; for example:
\bi
\item The  {\em cost-sensitive learners} discussed by Elkan~\cite{elkan01};
\item The   {\em ROC ensembles}discussed by Fawcett~\cite{fawcett01}  where
the conclusion is computed from some summation of the conclusions of the ensemble of 
ROC curves\footnote{ROC= receiver-operator characteristic curves such as graphs of
PD-vs-PF or PD-vs-precision}, 
proportionally weighted, to
yield a new learner.
\ei 
At best,  such biasing is only an indirect
control of the $C_1$ criteria. If the underlying criteria used to guide the search
is orthogonal to the success criteria of, say, $application_x$ then cost-sensitive learning
and  ensemble combinations will not be able to generate a learner
that  supports that business application.

What is required is a new kind of learner- one where the same
user-specified criteria is applied during training {\em and} testing.
The rest of this paper tests the speculation that such a learner can
overcome  performance ceilings.  

\subsection{WHICH}

The WHICH~\cite{milton08} rule learner loops over the space of
possible feature ranges, evaluating various combinations of features.
In terms of this discussion, the most important feature of WHICH is that
its evaluation criteria
$C$ is  not applied in a post-processing step. Rather, it is wired into the
inner loop of WHICH's learning:
\be
\item
WHICH maintains a stack of of combinations of features,
sorted by an evaluation criteria $C$.
Initially, WHICH's ``combinations'' are just each range of each feature. Subsequently,
they can conjunctions of two or more features.
\item Two combinations are picked at random, favoring those combinations 
that are ranked highly by $C$.
\item The two combinations are themselves combined, scored, then sorted into the stack.
population of prior combinations.
\item Go to step 1.
\ee
After numerous loops, WHICH returns the highest ranked combination
of features. During testing, if a new module satisfies this combination then it is predicted as being
``defective''.

In the following experiment, we wanted to isolate the value of unifying the train/test evaluation criteria
against all other treatments.
Accordingly,  we ``crippled'' WHICH and disabled various internal options.
For example,
WHICH can optimize each combination via
a back select that discard superfluous parts of the combination.
Hence, the following results were obtained
by a data miner that knows nothing special about over-fitting avoidance  or any other AI
search technique. 
The {\em only} intelligence used by WHICH to find better defect predictors
is $C$.

For more details on WHICH, see Appendix IV.

\input{application}

% Decision-tree and rule-based learners
% build their trees/rules  after a search
% through the space of possible boolean combinations
% that test for ranges of the features in a training set. For non-numeric data, those
% boolean combinations include primitives such as equivalence or set membership
% $\{==, \in\}$ as well as combinations of multiple primitives $\{and,or,not\}$.

% Except for trivially small data sets, the space of combinations is too large to be
% explored exhaustively. For example, if the 21 numeric features of
% \fig{attr} are divided in two (for ``low'' and ``high''), then the space of possible combinations
% is hauntingly large (over four trillion: $(2^{21*2}= 4,398,046,511,104)$.

% Hence, all practical tree/rule employ some
% {\em heuristic evaluation criteria} $E$ to prune the space of options that they explore. Numerous heuristics
% have been found to be useful, ranging from simple entropy-based measures to complex
% multiple-pass growth-and-prune methods such as those used in RIPPER~\cite{cohen95r}. 
% For an extensive survey of
% heuristics used in rule-based learning, see~\cite{furnkranz05}.


% For more details on WHICH, see appendix D.

% but can read all

%  Given $M$ modules, V\&V
%   teams often {\em skew} their inspection according to some domain specific
%   prioritization. Budget considerations may mean some $missed \le M$ number
% of modules are not inspected at the current time.
% These $missed$ modules can add an  inappropriate bias to quality
% assurance (QA). If  the QA activities concentrate on  modules, say {\em A,B,C,D}, then that leaves {\em blind spots} in
% the $missed$ modules {\em E,F,G,H,I,...}. Blind spots can compromise high assurance
% software. Leveson remarks that in modern complex systems, unsafe
% operations often result from an unstudied interaction between
% components~\cite{leven95}. 
% To avoid blind spots, one option is to rigorously assess all aspects
% of all  software modules or other artifacts. But this is
% impractical. Software projects budgets are finite and QA
% effectiveness increases with QA effort. A {\em linear} increase in
% the confidence $C$ that we have found all faults can take {\em
% exponentially} more effort\footnote{
% The
% infamous state space explosion problem imposes
% strict limits on how much a system can be explored
% via automatic formal methods~\cite{me00q}.
% Lowry et.al.~\cite{lowrey98} and Menzies and
%   Cukic~\cite{me99q,me00y} offer numerous other examples where
%   assessment effectiveness is exponential on effort.
% It can also be hard to improve the assurance gained from even
% simple testing.
% A randomly
% selected input to a program will find a fault with probability $x$.
% Voas observes~\cite{voas95} that after $N$ random black-box tests,
% the chance of the inputs not revealing any fault is $(1-x)^N$.
% Hence, the chance $C$ of seeing the fault is $1-(1-x)^N$ which can
% be rearranged to
%  $N(C,x)=\frac{log(1 -
% C)}{log(1-x)}$. 
% Hence, to detect one-in-a-thousand
% module faults, moving $C$ from 90\% to 94\% to 98\% takes 2301,
% 2812, and 3910 black box tests (respectively). 
%  }
%  Exponential
%   cost increase quickly exhausts finite QA resources.  Hence, blind
%   spots can't be avoided and must be managed. 
% One way to manage inspections is the  {\em business $application_x$} 
% shown in \fig{task1}.
% A data miner can learn a predictor using old data. When applied to new data,
% a set of modules are predicted to be faulty.  A QA team can reflect over the predictions
% to sort the $missed$ modules into
% (a)~ those that require urgent inspection, and (b)~others
% than could be inspected later (or never).  
% We say that the inspection team is $\alpha$\% effective at inspecting modules and recognizing the ones that are 
% recall defective.

% %%% Local Variables: 
% %%% mode: latex
% %%% TeX-master: t
% %%% End: 
