%XXX designed detectors
%XXX external validity turkey
%% XXX return to worst case below
%%% used mann-whitney cause this is not paired test. 
%XX recall our experimental rig: 

%% bare_jrnl.tex
%% V1.1
%% 2002/08/13
%% by Michael Shell
%% mshell@ece.gatech.edu
%%
%% NOTE: This text file uses MS Windows line feed conventions. When (human)
%% reading this file on other platforms, you may have to use a text
%% editor that can handle lines terminated by the MS Windows line feed
%% characters (0x0D 0x0A).
%%
%% This is a skeleton file demonstrating the use of IEEEtran.cls
%% (requires IEEEtran.cls version 1.6 or later) with an IEEE journal paper.
%%
%% Support sites:
%% http://www.ieee.org
%% and/or
%% http://www.ctan.org/tex-archive/macros/latex/contrib/supported/IEEEtran/
%%
%% This code is offered as-is - no warranty - user assumes all risk.
%% Free to use, distribute and modify.

% *** Authors should verify (and, if needed, correct) their LaTeX system  ***
% *** with the testflow diagnostic prior to trusting their LaTeX platform ***
% *** with production work. IEEE's font choices can trigger bugs that do  ***
% *** not appear when using other class files.                            ***
% Testflow can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/supported/IEEEtran/testflow


% Note that the a4paper option is mainly intended so that authors in
% countries using A4 can easily print to A4 and see how their papers will
% look in print. Authors are encouraged to use U.S. letter paper when
% submitting to IEEE. Use the testflow package mentioned above to verify
% correct handling of both paper sizes by the author's LaTeX system.
%
% Also note that the "draftcls", not "draft", option should be used if
% it is desired that the figures are to be displayed in draft mode.

% *************************************************************************
% You can now use this template both for submitting to peer review and,
% if your paper is accepted, for sending in final publication materials.
% To change from peer review format (single column, double-spaced) to
% final publication format (double column, single-spaced), just move the
% comment-line sign (%) from one \documentclass line to the other.
% The first is for peer review format(single column), the second is for final publication(double column).

%\documentclass[12pt,journal,draftcls,letterpaper,onecolumn]{IEEEtran}
%\renewcommand{\baselinestretch}{1.4}
%$documentclass[9.5pt,journal,cite, compsoc,twocolumn]{IEEEtran}
\documentclass[9.5pt,journal,cite,final,finalsubmission,twocolumn]{IEEEtran}
%\documentclass[journal,compsoc,twocolumn]{IEEEtran}
% *************************************************************************

\usepackage{pifont}
\usepackage{eso-pic}
\usepackage{color}
\usepackage{type1cm}
%\makeatletter
%  \AddToShipoutPicture{%
%    \setlength{\@tempdimb}{.5\paperwidth}%
%    \setlength{\@tempdimc}{.5\paperheight}%
%    \setlength{\unitlength}{1pt}%
%      \makebox(600,900){\rotatebox{45}{\textcolor[gray]{0.85}{\fontsize{9cm}{9cm}\selectfont{Draft}}}}}
%\makeatother
%
% If the IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it:
% \documentclass[journal,draftcls,onecolumn]{../sty/IEEEtran}


% some very useful LaTeX packages include:
\usepackage[all]{xy}
\usepackage{cite}      % Written by Donald Arseneau
                        % V1.6 and later of IEEEtran pre-defines the format
                        % of the cite.sty package \cite{} output to follow
                        % that of IEEE. Loading the cite package will
                        % result in citation numbers being automatically
                        % sorted and properly "ranged". i.e.,
                        % [1], [9], [2], [7], [5], [6]
                        % (without using cite.sty)
                        % will become:
                        % [1], [2], [5]--[7], [9] (using cite.sty)
                        % cite.sty's \cite will automatically add leading
                        % space, if needed. Use cite.sty's no adjust option
                        % (cite.sty V3.8 and later) if you want to turn this
                        % off. cite.sty is already installed on most LaTeX
                        % systems. The latest version can be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/contrib/supported/cite/

\usepackage{graphicx}  % Written by David Carlisle and Sebastian Rahtz
                        % Required if you want graphics, photos, etc.
                        % graphicx.sty is already installed on most LaTeX
                        % systems. The latest version and documentation can
                        % be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/required/graphics/
                        % Another good source of documentation is "Using
                        % Imported Graphics in LaTeX2e" by Keith Reckdahl
                        % which can be found as esplatex.ps and epslatex.pdf
                        % at: http://www.ctan.org/tex-archive/info/

%\usepackage{psfrag}    % Written by Craig Barratt, Michael C. Grant,
                        % and David Carlisle
                        % This package allows you to substitute LaTeX
                        % commands for text in imported EPS graphic files.
                        % In this way, LaTeX symbols can be placed into
                        % graphics that have been generated by other
                        % applications. You must use latex->dvips->ps2pdf
                        % workflow (not direct pdf output from pdflatex) if
                        % you wish to use this capability because it works
                        % via some PostScript tricks. Alternatively, the
                        % graphics could be processed as separate files via
                        % psfrag and dvips, then converted to PDF for
                        % inclusion in the main file which uses pdflatex.
                        % Docs are in "The PSfrag System" by Michael C. Grant
                        % and David Carlisle. There is also some information
                        % about using psfrag in "Using Imported Graphics in
                        % LaTeX2e" by Keith Reckdahl which documents the
                        % graphicx package (see above). The psfrag package
                        % and documentation can be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/contrib/supported/psfrag/

%\usepackage{subfigure} % Written by Steven Douglas Cochran
                        % This package makes it easy to put subfigures
                        % in your figures. i.e. "figure 1a and 1b"
                        % Docs are in "Using Imported Graphics in LaTeX2e"
                        % by Keith Reckdahl which also documents the graphicx
                        % package (see above). subfigure.sty is already
                        % installed on most LaTeX systems. The latest version
                        % and documentation can be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/contrib/supported/subfigure/

\usepackage{url}       % Written by Donald Arseneau
                        % Provides better support for handling and breaking
                        % URLs. url.sty is already installed on most LaTeX
                        % systems. The latest version can be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/contrib/other/misc/
                        % Read the url.sty source comments for usage information.

\usepackage{stfloats}  % Written by Sigitas Tolusis
                        % Gives LaTeX2e the ability to do double column
                        % floats at the bottom of the page as well as the top.
                        % (e.g., "\begin{figure*}[!b]" is not normally
                        % possible in LaTeX2e). This is an invasive package
                        % which rewrites many portions of the LaTeX2e output
                        % routines. It may not work with other packages that
                        % modify the LaTeX2e output routine and/or with other
                        % versions of LaTeX. The latest version and
                        % documentation can be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/contrib/supported/sttools/
                        % Documentation is contained in the stfloats.sty
                        % comments as well as in the presfull.pdf file.
                        % Do not use the stfloats baselinefloat ability as
                        % IEEE does not allow \baselineskip to stretch.
                        % Authors submitting work to the IEEE should note
                        % that IEEE rarely uses double column equations and
                        % that authors should try to avoid such use.
                        % Do not be tempted to use the cuted.sty or
                        % midfloat.sty package (by the same author) as IEEE
                        % does not format its papers in such ways.

\usepackage{amsmath}   % From the American Mathematical Society
                        % A popular package that provides many helpful commands
                        % for dealing with mathematics. Note that the AMSmath
                        % package sets \interdisplaylinepenalty to 10000 thus
                        % preventing page breaks from occurring within multiline
                        % equations. Use:
%\interdisplaylinepenalty=2500
                        % after loading amsmath to restore such page breaks
                        % as IEEEtran.cls normally does. amsmath.sty is already
                        % installed on most LaTeX systems. The latest version
                        % and documentation can be obtained at:
                        % http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/



% Other popular packages for formatting tables and equations include:

% Frank Mittelbach's and David Carlisle's array.sty which improves the
% LaTeX2e array and tabular environments to provide better appearances and
% additional user controls. Array.sty is already installed on most systems.
% The latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/tools/

% Mark Wooding's extremely powerful MDW tools, especially mdwmath.sty and
% mdwtab.sty which are used to format equations and tables, respectively.
% The MDWtools set is already installed on most LaTeX systems. The lastest
% version and documentation is available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/supported/mdwtools/

% V1.6 of IEEEtran contains the IEEEeqnarray family of commands that can
% be used to generate multiline equations as well as matrices, tables, etc.


% Also of notable interest:

% Scott Pakin's eqparbox package for creating (automatically sized) equal
% width boxes. Available:
% http://www.ctan.org/tex-archive/macros/latex/contrib/supported/eqparbox/




% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


\newenvironment{smallitem}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{itemize}
  \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{itemize}}

\newenvironment{smallenum}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{enumerate}
  \setlength{\leftmargin}{.2in}  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{enumerate}}


\newcommand{\sect}[1]{\S\ref{sec:#1}}
\newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
\newcommand{\bi}{\begin{smallitem}}
\newcommand{\ei}{\end{smallitem}}
\newcommand{\be}{\begin{smallenum}}
\newcommand{\ee}{\end{smallenum}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\tion}[1]{\S\ref{sec:#1}}
\newcommand{\aive}{{\"aive}\ }

\newcommand{\boxplot}[5]{
	\begin{picture}(100,7)
		%\put(#1,4){\circle*{2}}
		\put(#3,4){\circle*{4}}
                %\put(#5,4){\circle*{1}}
		\put(50,0){\line(0,1){7}}
                \linethickness{0.25mm}
                \put(#2,4){\line(1,0){#4}}		
	\end{picture}
} 

\begin{document}
%
% paper title
\title{Overcoming Ceiling Effects in Defect Prediction}
%
%
% author names and IEEE memberships
% note positions of commas and non breaking spaces ( ~ ) LaTeX will not break
% a structure at a ~ so this keeps an authors name from being broken across
% two lines.
% use \thanks{} to gain access to the first footnote area
% a separate \thanks must be used for each paragraph as LaTeX2e's \thanks
% was not built to handle multiple paragraphs
\author{Tim Menzies,~\IEEEmembership{Member,~IEEE,}
       Zach Milton, \\Burak Turhan, Yue Jiang, Gregory Gay, Bojan Cukic, Ay\c{s}e Bener% <-this % stops a space
\thanks{Manuscript received April 1, 2008; revised XXX.}% <-this % stops a space
\thanks{Dr. Menzies, Dr. Cukic, Mr. Milton,  Mr. Gay, and Ms Jiang are with the Lane Department
of Computer Science and Electrical Engineering, West Virginia University, USA:
\protect\url{tim@menzies.us}, 
\protect\url{bojan.cukic@mail.csee.wvu.edu};
\protect\url{zmilton,yjiang1@mix.wvu.edu};
\protect\url{greg@4colorrebellion.com}}%
\thanks{Dr. Bener and Mr. Turhan are with the
Dept. of Computer Engineering, Bo{\u g}azi{\c c}i  University, Turkey:
\protect\url{bener,turhanb@boun.edu.tr}}%
\thanks{For enquiries on this work,
email \protect\url{tim@menzies.us}.
For an earlier draft,  see \protect\url{http://menzies.us/pdf/08ceffects.pdf}.}
\thanks{The research described in this paper was supported by Bo{\u g}azi{\c c}i  University 
research fund under grant number BAP-06HA104 and at West Virginia 
University under grants with NASAs Software Assurance Research Program. 
Reference herein to any specific commercial product, process, or service 
by trademark, manufacturer, or otherwise, does not constitute or imply its 
endorsement by the United States Government.}}

% note the % following the last \IEEEmembership and also the first \thanks -
% these prevent an unwanted space from occurring between the last author name
% and the end of the author line. i.e., if you had this:
%
% \author{....lastname \thanks{...} \thanks{...} }
%                     ^------------^------------^----Do not want these spaces!
%
% a space would be appended to the last name and could cause every name on that
% line to be shifted left slightly. This is one of those "LaTeX things". For
% instance, "A\textbf{} \textbf{}B" will typeset as "A B" not "AB". If you want
% "AB" then you have to do: "A\textbf{}\textbf{}B"
% \thanks is no different in this regard, so shield the last } of each \thanks
% that ends a line with a % and do not let a space in before the next \thanks.
% Spaces after \IEEEmembership other than the last one are OK (and needed) as
% you are supposed to have spaces between the names. For what it is worth,
% this is a minor point as most people would not even notice if the said evil
% space somehow managed to creep in.
%
% The paper headers
\markboth{Journal of VVV,~Vol.~WWW, No.~XXX,~Month~200Y}{Menzies \MakeLowercase{\textit{et al.}}:
Overcoming Ceiling Effects in Defect Prediction}
% The only time the second header will appear is for the odd numbered pages
% after the title page when using the two side option.


% If you want to put a publisher's ID mark on the page
% (can leave text blank if you just want to see how the
% text height on the first page will be reduced by IEEE)
%\pubid{0000--0000/00\$00.00~\copyright~2002 IEEE}

% use only for invited papers
%\specialpapernotice{(Invited Paper)}

% make the title area

\IEEEaftertitletext{\vspace{-1\baselineskip}\noindent\begin{abstract}
While data miners 
can 
learn defect predictors from static code features, the performance
improvement in such detectors is curiously static.
One explanation for this {\em ceiling effect} is that
static code features have {\em limited information content}. 
If so, then
it should be useful to give
our learners more knowledge about the problems they are processing.
Data miners build predictors using a performance
criteria $P$ (e.g. accuracy), then assess them
using another criteria $Q$ (e.g. probability of detection).
Typically, $P \not= Q$, so
learners are {\em blind to their purpose}. Therefore, it   is hardly surprising  
that they cannot find ways to better their performance.
WHICH is a new data miner with $P \approx Q$; i.e.  a similar evaluation
criteria is applied during training and testing. After  matching
$P$ to  the goals of a particular business application, we found that
commonly used data miners perform {\em no
better than} simple manual methods; and that
WHICH outperforms
other methods, coming close to a theoretical upper bound
in performance  (50 and 75 percentile of 70.9\% and 80\%, respectively).
That is, with knowledge of the business
application, it is possible to build new data miners that overcome
ceiling effects.
%XXX close and can do better
\end{abstract}
\noindent\begin{keywords}
product metrics, defect prediction, data mining, decision-tree learning, rule-learning,
C4.5, RIPPER.
\end{keywords}
}
\maketitle
\section{Introduction}
% The very first letter is a 2 line initial drop letter followed
% by the rest of the first word in caps.
%
% form to use if the first word consists of a single letter:
% \PARstart{A}{demo} file is ....
%
% form to use if you need the single drop letter followed by
% normal text (unknown if ever used by IEEE):
% \PARstart{A}{}demo file is ....
%
% Some journals put the first two words in caps:
% \PARstart{T}{his demo} file is ....
%
% Here we have the typical use of a "T" for an initial drop letter
% and "HIS" in caps to complete the first word.
\PARstart{F}{or} several years, the authors have
 relied upon straightforward application of standard data mining algorithms
 to learn  defect predictors
from static code features;
see
\cite{%
fea02a,%
jiang07,%
me00p,%
me02g,%
me02k,%
me03q,%
me04c,%
me05d,%
me07b,%
me07e%
}
Recent results, discussed in the paper, now suggest that 
{\em there has been 
\underline{too much} emphasis on machine learning, and 
\underline{too little} attention
on the use of specific software engineering knowledge.}

Automatically generated
detect predictors are demonstrably 
useful and, as described in \S2, can operate better than current
industrial best practices~\cite{me06d,me07b}. However, we have observed
that  these AI methods 
have hit a {\em performance ceiling};
i.e., some inherent upper bound on the amount
of information standard data miners can extract from,  say, static code features.
For example, after a careful study of 19 data miners for learning defect predictors,
Lessmann et.al.~\cite{lessmann09} conclude \begin{quote}
{\em the
importance of the {\em classification model} (our emphasis) is less than generally assumed
and that practitioners are free to choose from a broad set of candidate models when building defect predictors.}\end{quote}

Note that, if all learners yield similar results, then 
the value of further research into automatic defect predictors is questionable.
However, if  the performance goal is changed from
{\em classification}
to some {\em application-aware} criteria then, 
contrary to Lessmann's advice, the selection of learner becomes critical.
For example, this paper examines a specific business context
we call $application_1$:
 inspect the {\em fewest} lines of code; find
the {\em most} number of defective modules.
In the context of $application_1$, we show that several standard learners
are demonstrably inferior to simple manual methods. The same cannot be
said of our new learner, called WHICH~\cite{milton08}, that
performs {\em better} than {\em both} standard learners and manual methods.
In fact, WHICH's performance also comes
close to a theoretical upper bound on the performance of
any learner tackling $application_1$.

%
%That assessment shows that
%in the particular context of $applciation_1$,
%numerous
%prior publications  (including many papers written by the authors
%\cite{%
%fea02a,%
%jiang07,%
%me00p,%
%me02g,%
%me02k,%
%me03q,%
%me04c,%
%me05d,%
%me07b,%
%me07e%
%}) have endorsed inappropriate 
%data mining technology. 

This paper is structured as follows.
After a literature
review on defect predictors, we document the {\em ceiling effect}
mentioned above and hypothesize  that it is due to {\em
limited information
content} in static code attributes. 
Two {\em data reduction} experiments
(that shrink the size of training sets)
will confirm this hypothesis and show that the performance of our 
defect predictors {\em stabilizes after just a handful of training examples}\footnote{
Note that
the data reduction experiments of \S4 have been reported previously~\cite{me08d}. However, the
rest of this paper, including the definition and exploration of the
WHICH  learner, is all new work.}.
If limited information is the problem, the solution is clear: give our
learners more information. The details of $application_1$
will be used to design an application-aware
performance criteria for WHICH.
An experiment is performed where WHICH and three standard data miners are applied to
$application_1$. WHICH will be shown to perform better than manual methods
and standard data miners.
We hypothesize that
WHICH's superior performance
comes from detailed knowledge of the necessary business context. 
Unlike other learners, WHICH applies that knowledge at all levels of its reasoning.

Our conclusion will be that knowledge of the business application can overcome
ceiling effects.
We hope that this  result prompts a new cycle of defect prediction research
focused on discovering the {\em best} learner(s) for {\em particular} business context(s).
\section{About Defect Prediction}
% \subsection{Why Learn Defect Predictors?}
% Building high quality software and providing adequate assessment is
% expensive. Developers typically skew their quality assurance (QA)
% work towards artifacts where they believe it will be most useful.

% This skewing process can introduce an inappropriate bias to quality
% assurance (QA). If  the QA activities concentrate on  project
% artifacts, say {\em A,B,C,D}, then that leaves {\em blind spots} in
% {\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}. For example, Lutz and
% Mikulski~\cite{lutz03} found a blind spot in NASA deep-space
% missions: most of the mission critical {\em in-flight} anomalies
% resulted from errors in {\em ground software} that fails to
% correctly collect data from the flight systems.
% 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. For example, 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)\footnote{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)}$. For example, $N(0.90,10^{-3})=2301$.}.
% %\item {\bf Automatic formal methods:}
% %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.
% Exponential cost increase quickly exhausts finite QA resources.
% Hence, blind spots can't be avoided and must be managed. Standard
% practice is to apply the best available assessment methods on the
% sections of the program that the best available domain knowledge
% declares is the most critical.  We endorse this approach.  Clearly,
% the most critical sections require the best known assessment
% methods, in hope of minimizing the risk of safety or mission
% critical failure occurring post deployment. However, this focus on
% certain sections can blind us to defects in other areas which,
% through interactions, may cause similarly critical failures.
% Therefore, the standard practice should be augmented with a {\em
% lightweight sampling policy} that (a)~explores the rest of the
% software and (b)~raises an alert on parts of the software that
% appear problematic.  This sampling approach is incomplete by
% definition. Nevertheless, it is the only option when 
% resource limits block
% complete assessment.

\PARstart{D}ata miners learn defect predictors from static code features,
either from projects previously developed in the same environment or
from a continually expanding base of the current project's artifacts. To do so,
tables of examples are formed where one column has a boolean value
for ``defects detected'' and the other columns describe software
features such as lines of code, number of unique
symbols~\cite{halstead77},  or max. number of possible
execution pathways~\cite{mccabe76}.  
Each row in the table holds data
from one ``module'',  the  smallest unit of functionality. Depending on
the language, these may be called ``functions'', ``methods'', or
``procedures''. 
Static code features are
described in
Figures \ref{fig:attr},\ref{fig:halstead},\&\ref{fig:mccabe}

The data mining task is to find
combinations of  features that predict for the value in the defects
column.  
The value of static code features as defect predictors has
been widely debated.
While some researchers vehemently oppose them~\cite{fenton00b,shepperd94},
many others endorse their use~\cite{%
polyspace,%
chapman02,%
hall00,%
halstead77,%
journals/ese/KhoshgoftaarS03,%
conf/icse/NagappanB05a,%
conf/ictai/TangK04,%
khoshgoftaar01,%
khoshgoftaar99,%
mccabe76,%
me02e,%
me03a,%
me03k,%
me03q,%
me04g,%
me07b,%
me07e,%
nagappan05,%
nikora03,%
porter90,%
srinivasan95,%
tiang95%
}. Standard verification and validation (V\&V) textbooks
\cite{rakitin01} advise using static code complexity attributes to
decide which modules are worthy of manual inspections. For several
years, the authors have worked on-site at the NASA Independent software
Verification and Validation facility where large government software
contractors won't review software modules {\em unless} tools like
the McCabe static source code analyzer predict that they exhibit
high code complexity measures.

\begin{figure}[!t]
\renewcommand{\baselinestretch}{1}
\begin{center}
{\footnotesize
\begin{tabular}{l@{~}|l@{~}|l@{~}|c@{~}p{3.9cm}|}\cline{2-5}
%\begin{tabular}{|l|l|lcl|}\hline
%\multicolumn{3}{|c}{grouping}&\multicolumn{2}{|c|}{measure}\\\hline
		&\multicolumn{2}{l}{m = Mccabe }       &$v(g)$  &cyclomatic\_complexity  \\
        &        \multicolumn{2}{l}{~}                                 & $iv(G)$&design\_complexity\\
        &         \multicolumn{2}{l}{~}                                & $ev(G)$&essential\_complexity\\\cline{2-5}
        &locs&{loc}                         &   &loc\_total (one line = one count\\\cline{3-5}
	&	&loc(other)                      &   &loc\_blank           \\
        &       &                                &   &loc\_code\_and\_comment\\
        &       &                                &   &loc\_comments         \\
        &        &                                &   &loc\_executable\\
        &       &                                &    &number\_of\_lines (opening to closing brackets)\\\cline{2-5}
	&{Halstead} & h& $N_1$ &num\_operators\\
        &       &                                 &$N_2$ &num\_operands \\
        &       &                                 &$\mu_1$ &num\_unique\_operators\\
        &       &                                 &$\mu_2$ &num\_unique\_operands\\\cline{3-5}
        &       &  { H}&$N$  &length: $N= N_1 + N_2$\\
        &       &                                 & $V$  &volume: $V=N * log_{2}\mu$\\
        &       &                                 & $L$  &level: $L=V^*/V$ where\newline $V^*=(2+\mu{_2}^{*})log_{2}(2+\mu{_2}^{*})$\\
        &       &                                 & $D$  &difficulty: $D=1/L$\\
        &       &                                 &$I$   &content: $I=\hat{L}*V$ where\newline $\hat{L}=\frac{2}{\mu_{1}} * \frac{\mu_{2}}{N_{2}}$ \\
        &       &                                 & $E$  &effort: $E=V/\hat{L}$\\
        &       &                                 & $B$  &error\_est\\
        &       &                                 & $T$  &prog\_time: $T=E/18$ seconds\\\cline{2-5}
\end{tabular}}
\end{center}
\caption{Features used in this study. The Halstead features are explained in \fig{halstead}
and the Mccabe features are explained in \fig{mccabe}.}\label{fig:attr}
\end{figure}
\begin{figure}
\renewcommand{\baselinestretch}{1}
\footnotesize
\begin{tabular}{|p{.95\linewidth}|}\hline
The Halstead features were derived by Maurice Halstead in 1977. He
argued that modules
that are hard to read are more likely to be fault
prone~\cite{halstead77}. Halstead estimates reading complexity by
counting the number of operators and operands in a module: see the
$h$ features of \fig{attr}.  These three raw $h$  Halstead
features were 
then used to compute the $H$: the eight derived Halstead features
using the equations shown in
\fig{attr}.  In between the raw and derived Halstead features are
certain intermediaries:
 \bi
\item
$\mu= \mu_1 + \mu_2$;
\item
minimum operator count: $\mu_1^*=2$;
\item
$\mu_2^*$  is the minimum operand count (number of module parameters).
\ei\\\hline
\end{tabular}
\caption{Notes on the Halstead features}\label{fig:halstead}
\end{figure}
 \begin{figure}
\renewcommand{\baselinestretch}{1}
\footnotesize
\begin{tabular}{|p{.95\linewidth}|}\hline
An alternative to the Halstead features of \fig{halstead}
are the complexity features proposed by Thomas McCabe in 1976.
Unlike Halstead,
McCabe
 argued that the complexity of
pathways {\em between} module symbols are more insightful than just a count of the symbols~\cite{mccabe76}. 

The first three lines of \fig{attr}
shows McCabe three
main features for this pathway complexity. These are defined as follows.
\bi
\item
A
module is said to have a {\em flow graph}; i.e. a directed graph where each node corresponds to a
program statement, and each arc indicates the flow of control from
one statement to another.
\item
The {\em cyclomatic complexity} of a module is   $v(G) = e - n +
2$ where $G$ is a program's flow graph, $e$ is the number of arcs in
the flow graph, and $n$ is the number of nodes in the
flow graph~\cite{fenton96}.
\item
The {\em essential complexity}, ($ev(G)$) of a module is  the extent to which a
flow graph can be ``reduced'' by decomposing all the subflowgraphs
of $G$ that are {\em D-structured primes}
(also sometimes referred to as ``proper one-entry
one-exit subflowgraphs''~\cite{fenton96}). $ev(G) = v(G) - m$ where $m$ is the number of subflowgraphs of
$G$ that are D-structured primes~\cite{fenton96}.
\item
Finally, the
{\em design complexity}   ($iv(G)$) of a module is the cyclomatic complexity of a
module's reduced flow graph.
\ei\\\hline
\end{tabular}
\caption{Notes on the McCabe features}\label{fig:mccabe}
\end{figure}
Nevertheless, static code attributes can never be a full
characterization of a program module. Fenton offers
an insightful example where {\em the same} functionality is achieved
using {\em different} programming language constructs resulting in
{\em different} static measurements for that module~\cite{fenton97}.
Fenton used this example to argue the uselessness of static code
attributes for fault prediction.

If Fenton is right, then
%\bi\item
%Learning from just lines of code should do as well as anything else;
%\item
the performance of  predictors learned by  data mining static code
features should be poor. However, this is not true, at least for the
code we have
studied~\cite{me07e,me07b,me04g,me04c,me03q,me03k,me02l,me02g,me02e,jiang07}.
Using NASA data, our fault prediction models find defect
predictors~\cite{me07b} with a probability of detection ($pd$) and
probability of false alarm ($pf$) of $mean(pd,pf)=(71\%,25\%)$.

These values can be compared to
baselines in data mining and industrial practice.
Raffo (personnel communication) found that industrial reviews discover \mbox{$pd=TR(35, 50,
65)\%$}\footnote{ $TR(a,b,c)$ is a triangular distribution with
min/mode/max of $a,b,c$.} of a systems errors' (for full Fagan
inspections~\cite{fagan76}) to \mbox{$pd=TR(13, 21, 30)\%$} for
less-structured inspections.
Similar values were reported at an IEEE Metrics 2002
panel. That
panel declined to endorse claims by Fagan~\cite{fagan86} and
Schull~\cite{shull00a} regarding the efficacy of their inspection or
directed inspection methods. Rather, it concluded that manual
software reviews can find ${\approx}60\%$ of defects~\cite{shu02}.


As to comparing our defect predictors with standard results from the data mining community,
in prior work, we have checked the efficacy of data mining on 
standard machine learning data sets such as the UCI data repository~\cite{Blake+Merz:1998}. 
For each UCI data set, ten
experiments were conducted, using a state-of-the-art
decision tree learner~\cite{quinlan92}
from 90\% of
the data, selected at random.
The experiments tested the learned decision tree
on remaining 10\% of the data. 
On average, state of the art data miners perform at
 ($pd$,$pf$)=(81\%,20\%). 
This is close to the results we have obtained via data mining on static code attributes
 ($pd$,$pf$)=(71\%,25\%). 
Note that 
if static code attributes capture so little
about source code (as argued by Fenton), then we would expect lower probabilities
of detection and much higher false alarm rates. 
% \footnote{
% But note that we can only relatively compare the defect {\em detection}
% properties of automatic vs manual methods.
% The  relative merits of automatic vs manual methods for defect {\em repair}
% Unlike automatic defect
% prediction via data mining, the above manual inspection methods
% don't just report ``true,false'' on a module, Rather, the manual
% methods also provide specific debugging information.  Hence, a
% complete comparison of automatic vs manual defect prediction would
% have to include both an analysis of the time to {\em detect} potential
% defects {\em and} the time required to {\em fix} them.
% Manual methods might score higher
% to automatic methods
% since they can offer more clues back to the developer about
% what is wrong with the method.  However, such an analysis is beyond
% the scope of this paper.
% Here, we focus only on the relative merits of different methods for 
% {\em detecting} errors.
% }.

Overall, there are two reasons to recommend static code predictors.
Firstly, 
our $(pd,pf)$ results are 
better than currently
used industrial methods such as:
\bi
\item the $pd{\approx}60\%$ reported
at the 2002 IEEE Metrics panel or 
\item the $median(pd)=21..50$ reported
by Raffo.
\ei
Secondly, static code defect predictors can be built quickly,
even for very large
systems~\cite{nagappan05}. Other methods such as manual
code reviews may be more labor-intensive. Depending on the review method,
$8$ to $20$ lines of code (LOC) per minute can be inspected. This
effort repeats for all members of the review team (typically,
four or six~\cite{me02f}).
Our defect detectors, on the other hand, can be generated using automatic methods.

%XXX tse 2008 static doe defect predictors

%All the above results were collected by  a variety of different
%methods. Hence, it is somewhat complicated  to directly compare our data
%mining models with these industrial baselines. The least we can say
%is that automatically generated defect predictors do not appear to
%perform {\em worse} than industrial averages and might even perform
%somewhat better. Also, while the manual methods require {\em manual}
%effort, our defect predictors can be {\em automatically} and rapidly
%developed, then applied to large libraries of code in a
%cost-effective manner.
%
\section{Ceiling Effects}
\PARstart{A} ``ceiling effect'' may be observed when different treatments all yield similar upper-bounds
on their performance. 
As documented in this section,
there is much evidence for a ceiling effect in defect prediction. Specifically,
even after years
of exploring different learners and data pre-processing methods, the performance of our
learners has not improved. 

In January 2007, we published in TSE~\cite{me07b} a  study
 that
defined a
repeatable experiment in learning defect  predictors. The aim of
that work was a benchmark result that other
researchers could repeat/ improve/ refute. That experiment used
public domain data sets\footnote{From \url{http://promisedata.org}}
and
open source data mining
tools (the WEKA toolkit~\cite{witten05});
Data order was
randomly sorted 
(to stop
order effects).
Data mining was performed using
10-way cross-validation (to test on data {\em not} used in training).
Learner assessment was 
via multiple criteria such as probability of detection ($pd$),
probability of false alarm ($pf$), and $balance$ that 
combines $\{pd,pf\}$ ($balance$ is defined in \fig{measures}).
The experiment also included
statistical hypothesis tests over the assessment criteria;
novel visualization methods for the results;
feature subset selection to find important subsets of 
features;
and
learning via multiple types of machine learning algorithms: rule
learners, decision tree learners, n\aive Bayes classifiers.

Surprisingly, n\aive Bayes classifiers (with a simple
pre-processor for the numerics)
out-performed the other studied methods. For details on n\aive Bayes classifiers,
see Appendix I.

\begin{figure}[!t]
\begin{center}
\renewcommand{\baselinestretch}{1}
\footnotesize
\begin{tabular}{|p{.95\linewidth}|}\hline
If $\{A,B,C,D\}$ are the
true negatives,
false negatives, 
false positives, and 
true positives
(respectively) found by a defect predictor, then:
\begin{eqnarray}\label{eq:pd}
pd=&recall=&D/(B+D)\\
pf=&&C/(A+C)\\\label{eq:bal}
bal=&balance=&1 - \frac{\sqrt{\left(0 - pf\right)^2 + \left(1 - pd\right)^2}}{\sqrt{2}}
\end{eqnarray}
All these values range zero to one.
Better and {\em larger} balances fall  {\em closer} to the desired  zone 
of no false alarms and 100\% detection.

Other measures such as $accuracy$  and $precision$
were not used since, as shown in \fig{data}, the percent of defective examples
in our tables was usually very small (median value around 8\%).
Accuracy and precision
are poor indicators
of performance for data were the target class is so rare
(for more on this issue, see~\cite{me07b,me07e}). \\\hline
\end{tabular}
\end{center}
\caption{Performance measures.}\label{fig:measures}
\end{figure}
\begin{figure}
\begin{center}
\includegraphics[width=2.9in]{logandnom.pdf}
\end{center}
\caption{Box plot for area under PD-vs-PF curves seen with 9 learners
when, 100 times, a random 90\% selection of the data is  used for training and
the remaining data is used for testing.
The rectangles show the inter-quartile range (the
25\% to 75\% quartile range). The 
line shows the minimum to maximum range, unless that range extends
beyond 1.5 times the inter-quartile range (in which case dots are used
to mark these extreme outliers).
 From~\cite{jiang08a}.}\label{fig:logandnom}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics[width=2.9in]{all.pdf}
\end{center}
\caption{Range of ``ranks'' seen in 19 learners building
defect predictors
when, 
10 times, a random 66\% selection of the data is  used for training and
the remaining data is used for testing.
In ranked data, values from one method
are replaced
by their rank in space of all sorted values (so {\em smaller} ranks means 
{\em better}
performance). In this case, the performance
value was  {\em area under the false positive vs true-positive curve}
(and larger values are better).
Vertical lines divide the results into regions where the results are 
statically similar. For example,
all the methods whose top ranks are 4 to 12
are statistically {\em
insignificantly different}.  From~\cite{lessmann09}. }\label{fig:all}
\end{figure}



Since that study, we have tried to find  better data mining
algorithms for defect prediction. To date, we have failed. Our
recent experiments~\cite{jiang08a} have found little or no 
improvement from the application of 
numerous data mining methods. \fig{logandnom} shows some of those results
using (in order, left to right)
$aode$ average one-dependence estimators~\cite{yang06}; 
$bag$ bagging~\cite{brieman96}; 
$bst$ boosting~\cite{FreSch97}; 
$IBk$ instance-based learning~\cite{cover67}; 
$j48$ j48~\cite{quinlan92}; 
$jrip$ RIPPER~\cite{cohen95r}; 
$lgi$  logistic regression~\cite{breiman84}; 
$nb$ n\aive Bayes (second from the right);
and 
$rf$ random forests~\cite{briemann01}.
A statistical analysis shows that 
only  boosting
on
discretized data offers a statistically better result than 
n\aive Bayes.
However, we cannot recommend boosting: 
\bi
\item
Boosting is orders of
magnitudes slower than  n\aive Bayes;
\item
The median
improvement over n\aive Bayes is negligible. 
\ei
Other researchers have also failed to improve our results.
For example,  \fig{all} shows results from a study by Lessmann et al.
on
statistical differences  between 19
learners used for defect prediction~\cite{lessmann09}. 
At first glance, our preferred n\aive Bayes method  (shown as ``NB'' on the sixth line of \fig{all})
seems to perform poorly: it is ranked in the lower third of all 19 methods.
However, as with all statistical analysis,
it is important to examine not only central tendencies but also the  variance in the performance measure.
The vertical dotted lines in \fig{all} show Lessmann et al.'s statistical analysis that divided the results into regions where
all the results are significantly different: 
the performance of the top 16 methods are
statistically {\em insignificantly different} from each other (including our preferred
``NB'' method). Lessmann et.al. comment:
\begin{quote}
{\em ``Only four competitors are significantly
inferior to the overall winner (k-NN, K-start, BBF net, VP).
The empirical data
does not provide sufficient evidence to judge whether RndFor (Random Forest),
performs
significantly better than QDA  (Quadratic Discriminant Analysis)  
 or any classifier with better average
rank. }\end{quote}
In other words, Lessmann et al. are reporting a ceiling effect where a large number
of learners exhibit performance results that are indistinguishable.
%We now we ask for a halt to that line of research.
%Better defect predictors will arise, we will argue,
%not from better algorithms.
%We
%Exponential cost increase quickly exhausts finite QA resources.
%Hence, blind spots can't be avoided and must be managed. Standard
%practice is to apply the best available assessment methods on the
%sections of the program that the best available domain knowledge
%declares is the most critical. However, this focus on
%certain sections can blind us to defects in other areas which,
%through interactions, may cause similarly critical failures.
%Therefore, the standard practice should be augmented with a {\em
%lightweight sampling policy} that (a)~explores the rest of the
%software and (b)~raises an alert on parts of the software that
%appear problematic.  This sampling approach is incomplete by
%definition. Nevertheless, it is the only option when 
%resource limits block complete assessment.
%
%
%One such lightweight sampling policy is the
%use of {\em fault predictors}. To learn such prediction models,
%either from projects previously developed in the same environment or
%from a continually expanding base of current project's artifacts,
%tables of examples are formed where one column has a boolean value
%for ``faults detected'' and the other columns describe software
%features such as (i)~lines of code, (ii)~number of unique
%symbols~\cite{halstead77}, or (iii)~max. number of possible
%execution pathways~\cite{mccabe76}. Each row in the table holds data
%from one ``module''; i.e. the  unit of functionality. Depending on
%the language, modules may be called ``functions'', ``methods'',
%``procedures'' or ``files''. The data mining task is to find
%combinations of  features that predict for the value in the defects
%column.  Once such combinations are found, managers can use them to
%determine where to best focus their QA effort. Better yet, if they
%have already focused their QA effort on the most critical portions
%of the system, the detectors can ``nudge'' them towards areas that
%are also in need of quality improvement.
%
%
%For many years we relied upon straightforward application of data mining algorithms
% to learn quality predictors
%from the artifacts  generated by a software project; see  
%\cite{%
%chen05,%
%come96,%
%dekhtyar04,%
%fea02a,%
%hameph95,%
%hame93,%
%hame94,%
%jiang07,%
%lum06,%
%me00e,%
%me00p,%
%me00u,%
%me02c,%
%me02f,%
%me02g,%
%me02k,%
%me02l,%
%me02n,%
%me03c,%
%me03h,%
%me03i,%
%me03j,%
%me03k,%
%me03n,%
%me03q,%
%me03r,%
%me04a,%
%me04c,%
%me04g,%
%me04h,%
%me05a,%
%me05c,%
%me05d,%
%me06a,%
%me06d,%
%me06e,%
%me06f,%
%me07b,%
%me07e,%
%me07f,%
%Ramakrishnan1995,%
%RamMe1996%
%}.
%
%
%Standard verification and validation (V\&V) textbooks
%\cite{rakitin01} advise using static code complexity attributes to
%decide which modules are worthy of manual inspections. For several
%years, the PIs have worked on-site at the NASA Independent software
%Verification and Validation facility where large government software
%contractors won't review software modules {\em unless} tools like
%the McCabe static source code analyzer predicts that they exhibit
%high code complexity measures.
%
%Nevertheless, static code attributes are hardly a complete
%characterization of the internals of a program module. Fenton offers
%an insightful example where {\em the same} functionality is achieved
%using {\em different} programming language constructs resulting in
%{\em different} static measurements for that module~\cite{fenton97}.
%Fenton uses this example to argue the uselessness of static code
%attributes for fault prediction.
%
%An {\em alternative interpretation} of Fenton's example is that
%static attributes can never be a certain indicator of the presence
%of a  fault.  Nevertheless, they are useful as probabilistic
%statements that the frequency of faults tends to increase in code
%modules that trigger the predictor.
%
%Shepperd~\&~Ince and Fenton~\&~Pfleeger might reject the {\em
%alternative interpretation}. They present empirical evidence  that
%the McCabe static attributes offer nothing more than uninformative
%attributes that are mostly the derivatives of the lines of code.
%Fenton~\&~Pfleeger note that the main McCabe's attribute (cyclomatic
%complexity, or $v(g)$) is highly correlated with lines of
%code~\cite{fenton97}. Also, Shepperd~\&~Ince remark that ``for a
%large class of software it (cyclomatic complexity) is no more than a
%proxy for, and in many cases outperformed by, lines of
%code''~\cite{shepperd94}.
%
%If Shepperd \& Ince and Fenton \& Pfleeger are right, then
%%\bi\item
%%Learning from just lines of code should do as well as anything else;
%%\item
%the performance of  predictors learned by  data mining static code
%features should be poor. However, this is not true, at least for the
%NASA code we have
%studied~\cite{me07e,me07b,me04g,me04c,me03q,me03k,me02l,me02g,me02e,jiang07}.
%Using NASA data, our fault prediction models find defect
%predictors~\cite{me07b} with a probability of detection ($pd$) and
%probability of false alarm ($pf$) of $mean(pd,pf)=(71\%,25\%)$.
%These values can be best understood via a comparison against known
%industrial baselines \cite{fagan86, shu02}.
%
%The research work referenced above has produced useful results.
%However, there is much room for improvement; e.g. probabilities of
%detection reported in recent repeatable studies, should not only be
%achievable on a regular basis but improved.
%
%It has proved difficult to achieve those improvements. In our
%January 2007 TSE study~\cite{me07b} we set out to define a
%repeatable experiment in learning defect  predictors. The intent of
%that work was to offer a benchmark in defect prediction that other
%researchers could repeat/ improve/ refute. That experiment included:
%\bi
%\item
%Public domain data sets (from the the PROMISE
%repository\footnote{\url{http://promisedata.org/repository}});
%\item
%Open source data mining
%tools (the WEKA toolkit~\cite{witten05});
%\item
%Repeated  randomization of the sad order of training data (to avoid
%order effects);
%\item
%10-way cross-validation (to assess the results via data {\em not} used in training);
%\item
%Learning via multiple types of machine learning algorithms (rule
%learners, decision tree learners, Bayes classifiers);
%\item
%Assessment via multiple criteria such as probability of detection ($pd$),
%probability of false alarm ($pf$), and $balance$ that combines $\{pd,pf\}$ ;
%\item
%Statistical hypothesis tests over the assessment criteria;
%\item
%Novel visualization methods for the results;
%\item
%Feature subset selection to find the most important subset of the static code
%features;
%\ei
%
%Since that study, we have tried to find  better data mining
%algorithms for defect prediction. To date, we have failed. Our
%recent (as yet, unpublished) experiments have found no additional
%statistically significant improvement from the application of the
%following data mining methods: logistic regression; average
%one-dependence estimators~\cite{webb05}; under- or
%over-sampling~\cite{drummond03} random forests~\cite{breiman01},
%RIPPER~\cite{cohen95r}, j48~\cite{quinlan92}, OneR~\cite{holte93}
%and bagging~\cite{brieman96}. Only boosting~\cite{FreSch97} on
%discretized data offers a statistically better result than a Bayes
%classifier. However, we cannot recommend boosting: the median
%improvement is quite negligible and  boosting is orders of
%magnitudes slower than a simple Bayes classifier.
%
%Other researchers have also failed to improve our results. For the
%past four years, we participated in the PROMISE workshop on
%repeatable software engineering experiments. The rule of that
%workshop requires that if  a paper offers an empirical conclusion,
%then it must also offer the data used to reach the conclusions. That
%data is stored on-line in the PROMISE repository, which we
%administer and maintain for the PROMISE community. Our work on that
%web site, plus our interaction with the PROMISE community, gives us
%a unique insight into the empirical analysis as well as access to,
%as yet, unpublished results. Consequently, we are aware of studies
%by other researchers (currently under review) that tried 25 other
%data mining methods in fault prediction experiments. Those studies
%investigated the statistical difference of the results from 25
%learners on the same datasets using the Wilcoxon signed ranked
%test~\cite{wilcoxon45}. The Bayesian method discussed above ties in
%first place along with 15 other methods.
%

\section{The ``Limited Information Content''  Hypothesis}
\PARstart{H}ow to explain
all these failed attempts to improve fault
prediction?
One possibility is that these static code features have
a {\em limited information content}. If so, then simple learning methods
will uncover all that can be found. Further, more sophisticated
data mining methods will yield no more information.

The rest of this section offers evidence for 
the limited information hypothesis. 
%As we shall see, the amount of data required to 
%achieve the above state of the art results is surprisingly small (as few as 50 carefully
%selected examples may suffice). This observation will lead to three conclusions:
%\bi
%\item Static code features suffer from limited information content;
%\item The ceiling effect documented above cannot be overcome by more sophisticated 
%data mining methods (since there is nothing extra to find in this data);
%\item Nor can the ceiling effect be overcome by more examples of the {\em
%same} kind of data; 
%\item The only way through the ceiling effect is to give our data miners
%{\em different}  kinds of information. 
%\ei
%
%XXX plateau not an quirk of naive Bayes. central limit theorem of 30, other data set plateau much later much less than other methods

\subsection{Random Reduction Experiments }
In our {\em RandomReduction} study, 
 defect predictors were learned from
\mbox{$N=100, N=200, N=300, etc..$} instances  (selected at random) then 
$Test$ed on another 100
instances.
For all
experiments, the $Train$ and $Test$ instances were selected at random using
a 10-way cross-validation study\footnote{In  10-way cross-validation,
10 experiments are performed where
training is conducted on $|Train|=90\%*N$ instances, then tested
on data not used during training
(so \mbox{$Train \cap Test = \{\} $}). } for each value of $N$.

This {\em RandomReduction} study  was conducted on the
NASA sets of \fig{data} using  a n\aive Bayes classifier 
(since it performed so well in the above experiments).
Space does not permit
showing all the results but a representative sample
is shown in 
\fig{tone}~\cite{me08d}. In that
figure, the X-axis is the size of training set and the  Y-axis is
the $balance$ measure defined in \fig{measures}.
%All results come from a hold-out set of 100 instances.

Note that the performance does not change much regardless of whether
the model is inferred from 100 instances or from up to several
thousand instances. In fact, learning from too many training
examples may even be detrimental (witness the widening variance as
the training set increases). A Mann Whitney U test~\cite{mann47}
(95\% confidence)\footnote{In the rest of this paper, all statistical tests will be via the Mann-Whitney
non-paired non-parametric test. 
{\em Non-parametric} tests are used since Demsar advises
that parametric assumptions have conflated much prior data mining research~\cite{demsar06}.
{\em Non-paired} tests are used since, as in \fig{tone}, all the experiments from
here onwards apply the same treatment to different populations.
{\em Mann-Whitey} is used instead of, say, the Wilcoxon test~\cite{wilcoxon45} since 
(a)~Wilcoxon is a paired test and (b)~
a single Mann-Whitney test can compare one learner $L_1$ against rival
learners $L_2, L_3,...$ (since Mann-Whitney does not require that all samples
being compared have the same cardinality).
Hence, Mann-Whitney supports very succinct summaries of the results without the
post-processing required for Wilcoxon (see Demsar~\cite{demsar06} or Lessmann et al.~\cite{lessmann09}
 for details on the Wilcoxon
post-processing~\cite{lessmann09}).
}
 confirms the visual pattern apparent in
\fig{tone}: static code features used as the basis for predicting
module's fault content revealed all that they can reveal after as
little as 100 instances. 


\subsection{Structured Reduction Experiments}\label{sec:micro}

The \fig{tone} {\em RandomReduction}
experiment randomly discarded training data.
Perhaps a more 
{\em StructuredReduction} method
would not damage the information content of the data?
If so then, contrary to \fig{tone}, increasing the sample size
will improve performance and break through the ceiling effect reported above.
\begin{figure}
\renewcommand{\baselinestretch}{1}
\scriptsize
\begin{center}
\begin{tabular}{l|l|lrrr@{.}l}
&     &          & (\# modules)         &          &  &\\
source
&project & language & examples & features  & \multicolumn{2}{c}{\%defective}\\\hline
NASA&pc1  & C++ & 1,109    & 21          & 6&94\\
NASA&kc1  & C++ & 845      & 21          & 15&45\\
NASA&kc2  & C++ & 522      & 21          & 20&49\\
NASA&cm1  & C++ & 498      & 21          & 9&83\\
NASA&kc3  & JAVA & 458      & 39          & 9&38\\
NASA&mw1  & C++ & 403      & 37          & 7&69\\
SOFTLAB& ar4 & C++ &107 &  30            & 18 & 69\\
SOFTLAB& ar3& C++ & 63 &    30          & 12 & 70\\
NASA&mc2  & C++ & 61      & 39          & 32&29\\
SOFTLAB & ar5 & C++& 36 &  30           & 22 & 22\\
\cline{4-4}
     \multicolumn{3}{c}{~}     &  4,102 

\end{tabular}
\end{center}
\caption{Tables of data, sorted in order of number of examples.
The rows labeled ``NASA'' come from NASA aerospace projects while the rows
labeled ``SOFTLAB'' come  from a Turkish software company writing
applications for domestic appliances.
For details on the features used in each data set, see  \fig{attr}.
}\label{fig:data}
\end{figure} 

\begin{figure}[!t]
\begin{center}
\includegraphics[angle=90,width=2.2in]{incrementalKC1.pdf}
\includegraphics[angle=90,width=2.2in]{incrementalPC1.pdf}
\end{center}
\caption{{\em RandomReduction} results.
experimenting with training set size vs $balance$ (and $balance$ is
defined in \fig{measures}).
}\label{fig:tone}
\end{figure}


Three examples of  {\em StructuredReduction} are
micro-, over-, and under-sampling~\cite{drummond03,yun04}.  All of these methods  build
datasets with an equal number of defective and non-defective classes:
\bi
\item
In the case of {\em under-sampling}, random instances from the majority classification
are removed. This
results in a much smaller dataset, but the minority class is no
longer buried inside a larger set of other classes.
\item
In {\em over-sampling}, randomly selected instances from the minority
class are copied. Where as under-sampling
produces smaller data sets, over-sampling grows the size of the data.
\item
{\em Micro-sampling}  combines under-sampling
with {\em data reduction}.
Given $N$ defective modules
in a data set, \mbox{$M \in \{25,50,75,\ldots\} \le N$} 
defective modules are selected
at random. Another $M$ non-defective modules are then selected, at random. 
Note that under-sampling is a micro-sampling where $M=N$. Micro-sampling explores
training sets of {\em increasing} size $2M..2N$, while
standard under-sampling just explores one data set of
size $2N$.
\ei 

Under-sampling,  over-sampling, micro-sampling, and ``no-sampling''
 were applied to the NASA data sets from \fig{data} using
 10-way cross-validation. For the ``no-sampling'' experiments, the raw data was used for
training  and testing without any adjustment  to the class frequencies.

In these studies,
two data miners were used: the n\aive Bayes classifier we recommended above and 
the j48
decision tree learner~\cite{witten05,quinlan92}.  
j48 was used to test our rig against known over- and under- 
sampling results described in the literature~\cite{drummond03,kamei07}.
Other learners were not used since, as discussed above,
 all of our experiments
with other learners have not be productive. For more details on j48, see Appendix II.

\fig{bands} shows the under- and over- $balance$ results ($balance$
was defined in \fig{measures}).
The pattern of results is very clear:
\bi
\item
Over-sampling did not improve classifier performance.
This result is
consistent with Drummond \& Holte's sub-sampling experiments~\cite{drummond03}
and the sub-sampling
classification tree experiments of Kamei et.al.~\cite{kamei07}.
\item
The method with the highest medium performance was, yet again,
the simple n\aive Bayes we recommended previously~\cite{me07b}.
\item
Just like the \fig{tone} results,
throwing away data (i.e. under-sampling) 
does not degrade the performance of the learner. 
In fact, in the case of j48, throwing away data
 improved the median $balance$
performance from around 40\% to over 70\%.
\ei


\begin{figure}
\renewcommand{\baselinestretch}{1}
\begin{center}
{\scriptsize\begin{tabular}{cllrc} 
\multicolumn{3}{c}{~}& \multicolumn{1}{c}{2nd quartile, median }\\
rank&treatment&median& \multicolumn{1}{c}{and 3rd quartile}\\\hline
1&NB/ none & 74.6& \boxplot{21.9}{67.7}{74.6}{14}{100}\\ 
1&NB/ under& 74.1& \boxplot{19.9}{67.1}{74.1}{15}{100}\\
1&j48/ under& 73.6& \boxplot{21.6}{64.8}{73.6}{18}{100}\\ 
2&NB/ over  &62.5&\boxplot{17.5}{42}{62.5}{30}{100}\\
3&j48/ over &  45.6&\boxplot{0}{29.3}{45.6}{27}{100}\\
4&j48/ none & 42.3&\boxplot{0}{29.3}{42.3}{25}{100}\\\hline
&& & \multicolumn{1}{c}{50\%} 
\end{tabular}}
\end{center}
\caption{{\em StructuredReduction} results.
Over- \& under- \& no sampling results. 
Sorted descending by median $balance$ results ($balance$ is defined in \fig{measures}).
The right-hand side show median values (as a circle) within a 25\% to 75\% 
percentile range. The {\em rank}, shown left-hand-side, come from the 
statistical analysis of
\fig{stats}.
Three methods share top rank: NB/none, NB/under, j48/under.
}\label{fig:bands}
\end{figure}

\begin{figure}[!t]
\renewcommand{\baselinestretch}{1}
\scriptsize
\begin{center} 
\begin{tabular}{r|rrrr}
rank & treatment &  win & loss & ties\\\hline
1& nb / none & 3 & 0& 2\\
1& nb / under& 3 & 0 & 2\\
1& j48/ under &  3  & 0 & 2\\
2&nb / over & 2 & 3 & 0\\
3&j48/ over & 1 &4&0 \\
4&j48/ none &  0 & 5 & 0
\end{tabular}
\end{center}
\caption{{\em StructuredReduction} results: statistical tests on the \fig{bands} results.
Column two lists six treatments.
Each row
shows how the results for one treatment compare
to the other five.
This table is sorted in ascending
order on the number of losses
(so {\em better} methods appear at the {\em top} of the table.
The first column
shows
a comparison of one treatment against the other eight.
Two treatments have the same rank if their median ranks are
statistically insignificantly different  
(Mann-Whitney, 95\% confidence).
}
\label{fig:stats} \end{figure}
This last point motivated the micro-sampling experiment.
Recall that
micro-sampling is an under-sampling method that discards most of the
majority class while keeping only $M$ examples of the minority
class.   \fig{under} shows the results of an
under-sampling study where $M\in\{25,50,75,...\}$ defective modules
were selected at random, along with an equal $M$ number of defect-free
modules.  Note the same visual pattern as before: increasing data does
not necessarily improve $balance$.


\begin{figure}[!t]
\renewcommand{\baselinestretch}{1}
\begin{center}\noindent
\includegraphics[angle=90,width=2.1in]{underCM1.pdf}
\includegraphics[angle=90,width=2.1in]{underKC1.pdf}
\includegraphics[angle=90,width=2.1in]{underKC2.pdf}
\includegraphics[angle=90,width=2.1in]{underKC3.pdf}
\includegraphics[angle=90,width=2.1in]{underMC2.pdf}
\includegraphics[angle=90,width=2.1in]{underPC1.pdf}
\end{center}
\caption{{\em StructuredSampling} results: micro-sampling.}\label{fig:under}
\end{figure}

Mann-Whitney tests were applied to test the visual pattern of \fig{under}. 
Detectors learned from small $M$ instances do as well
as detectors learned from any other number of instances.
\bi
\item
For five data sets,
\{CM1,KC2, KC3,MC2,PC1\},
micro-sampling at $M=25$ did just as well as anything larger sample size.
\item
For one data set, KC1, best results were seen at $M=575$.
However, in hundreds of repeats for that data set,
in all by one case,
$M=25$ did as well as any larger value.
\ei
%\subsection{Discussion on Reduction Experiments}
%
%We have offered these results as evidence for the {\em limited information hypothesis}.
%An alternative explanation is that this results are just a result of our choice of learners.
%For example, using 
%the central limit theorem, an argument might be made that the performance of a  N\aive Bayes classifier
%will
%plateau after 30 samples. 
%
%Empirically, it can be shown that this argument is incomplete. Firstly, the {\em StructuredReduction}
%experiments reported that discarding static code features
%improved not just N\aive Bayes, but also decision tree learners (recall \fig{bands}).
%
%Secondly, 
%N\aive Bayes performance plateaus occur much later 
%in other data sets that do not use static code features.
%In one {\em RandomReduction} experiment with 10 data sets from the UCI Irvine data mining 
%repository, Orrego~\cite{orrego04} reports that accuracy performance of a N\aive Bayes classifier
%plateaus after 
%(20,
%30,
%50,
%50,
%120,
%180,
%200,
%360,
%400,
%410) examples. Note that the median value in that set is 150 and many of the values are at or over 200.
%

\newpage
\section{Adding Business Knowledge}
\PARstart{T}he above results offer much support
for the limited information content 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 learners   {\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 $Q$ since it is applied after
another criteria $P$ is used by the leaner to build a model.

In theory, data mining could use the evaluation criteria
$Q$ to guide their search for better predictors.
In practice, this is often not the case.
For example:
\bi
\item[$P$]:
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[$Q$]: 
During {\em testing}, the learned decision-tree might be tested on any of the criteria shown in \fig{measures}.
\ei

\begin{figure}
\begin{center}
\includegraphics[width=2.5in]{pfpfeffacc.pdf}
\end{center}
\caption{Properties of 30 defect predictors learned
from \fig{data}'s NASA data, sorted by $effort$. 
For example, the detector shown at 
X=1 has $(accuracy,effort,pd,pf)$ of $(80,20,10,5)$\% (respectively).
From~\cite{me03a,me03q}.}\label{fig:adfe}
\end{figure}

Predictors that satisfy some intra-learning assessment criteria
$P$ may not satisfy some post-learning assessment criteria
$Q$. For example, \fig{adfe} shows properties of some
defect predictors we have learned from the NASA data of \fig{data} (while only 30 predictors
are shown in that figure, we have other results where thousands of other predictors follow exactly
the same pattern~\cite{me03a,me03q}).  Observe how $accuracy$ remains stable over a wide range of changes to $pd$ and $effort$;
e.g. the predictors labeled $A$ and $B$ have similar accuracies while
 $pd$ changes by a factor of five.
If $P$ maximizes for accuracy, while $Q$ prefers detectors with high $pd$ values,
then it is conceivable that the learner will return a detector that satisfies $P$, but not $Q$
(e.g. 
all the detectors on the  left-hand-side of \fig{adfe}).


Hence, we say that it is important that the learner's internal evaluation criteria $P$ reflects  business concern $Q$
since the  latter can change markedly from application to application.
For example,
the accuracy measure defined in \fig{measures} is a widely used performance statistic for classifiers. However,
it may not be the most informative statistic for certain applications.
In the business task we will call  ``$application_1$'', a quality assurance (QA) team has insufficient budget to
inspect all the code. Therefore, they need some {\em sorting} policy that increases
the defect frequency in modules that are ranked high in the sort. In this application,
$Q$ rewards {\em minimizing} the inspection effort while {\em maximizing} the
number of defective modules they discover. 
As shown in \fig{adfe}, it is not necessarily true that a highly accurate learner also maximizes $effort$ and
$pd$.

For this reason, 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 $P$ criteria. If the underlying criteria used to guide the search
is orthogonal to the success criteria of, say, $application_1$ then cost-sensitive learning
and  ensemble combinations will not be able to generate a learner
that  supports that business application.


By this line of reasoning, we have an explanation for the ceiling effect described above: 
when $P \not= Q$, our learners are {\em 
blind to their purpose} and it is
hardly surprising that they cannot find ways to improve their performance.
What is required is a new kind of learner- one where  a similar
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.  

\section{WHICH}

\PARstart{T}{he} 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
WHICH's $P$ criteria is very close to $application_1$'s
 $Q$ (denoted $P\approx Q$)
and
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 $P$ .
WHICH's design allows for the easy modification to $P$. The exact $P$ used in this study
is discussed below in {\S}IV.C.
\item
Initially, WHICH's ``combinations'' are just each range of each feature. Subsequently,
they can create conjunctions of two or more features.
\item Two combinations are picked at random, favoring those combinations 
that are ranked highly by $P$.
\item The two combinations are themselves combined, scored, then sorted into the stacked
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 discards 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 $P\approx Q$.

For more details on WHICH, see Appendix IV.



\subsection{About $application_1$}
Our study will focus on $application_1$, 
the details of which are shown  in  \fig{task1}. In $application_1$,
a QA team working on a limited budget wants to
{\em sort} the {\em modules} that the  {\em data miner}  {\em predicts}
are defective in order to find
(a)~ those that require urgent inspection, and (b)~others
than could be inspected later (or never).  

\begin{figure}
\renewcommand{\baselinestretch}{1}
\begin{displaymath}
    \xymatrix{ 
old\; data \ar[r] & data\;miner \ar[d] & \\
new\; data \ar[r] & predictor \ar[r]                    & predicitons \ar[lld]\\
sorted \ar[r] & QA\; team \ar[r]   &  defect\; reports\\
    }
\end{displaymath}
\caption{$application_1$: the QA team inspects  the  new data modules that the data miner predicts are faulty.
The modules predicted to be faulty are sorted by their
 {\em relative defect frequency} (RDF)
where one module is ranked higher than another if it is more likely to contain defects.
The QA team inspects those modules in that sort order.
 }\label{fig:task1}
\end{figure}

We make no presumption that $application_1$ is the only possible way to use data miners.
There are many other business applications of defect predictors that do not conform to $application_1$.
However, $application_1$ was chosen for two reasons.
Firstly, it is a common usage of automatic defect predictors. For example, if a V\&V company is
hired to audit the code from some new off-shore client, they may have a large code base to inspect
in the shortest possible time.

Secondly,  $application_1$ addresses current concerns in the defect prediction literature.
Arisholm \& Briand~\cite{arisholm06} argue {\em against} certain standard measures of 
predictor performance such as accuracy (defined in
\fig{measures}), saying that a highly accurate predictor can be undesirable in other ways.
For example, accuracy says nothing about the appropriate sort order for reading modules.  
In $application_1$ we want a
QA team to {\em read less} while {\em finding more} defects.
For such a budget-conscious team, 
if X\% of the modules are predicted to be faulty and if those modules contain less than X\% of the detects,
then the costs of generating the defect predictor is not worth the effort. 

Koru et al.~\cite{koru07} have much to say about  the relative defect
frequency (RDF) of different biasing strategies for selecting which modules should be inspected next.
Based on a literature review and empirical studies,
they make a strong case
the relationship between module {\em size} and
{\em number of defects} is not linear, but {\em logarithmic};
i.e. smaller modules are proportionally more
troublesome. Accordingly, they argue that LOC can be be used to create a biasing
strategy with higher RDF. For example: if one has the resources to
inspect 10,000 LOC, then their {\em logarithm defect hypothesis} would say that it
is better to pick 100 classes of size
100-LOC as opposed to picking 10 classes of 1,000 LOC.

We can use $application_1$ to  test the logarithmic defect hypothesis by exploring two
$sort$ orders:
\bi
\item In Koru's preferred    {\em manualUp}  policy, the  {\em smaller} modules (those with less LOC)
 will be inspected first. 
\item In the opposite  {\em manualDown} policy,  the {\em larger} modules will be inspected  first.
\ei

\begin{figure}[!t]
\begin{center}
\includegraphics[width=2.5in]{plots/effort.pdf}
\end{center}
\caption{Effort-vs-PD.}\label{fig:effort}
\end{figure}

\subsection{Effort-vs-PD Curves}

The relative merits of biasing strategies like {\em manualUp} and {\em manualDown} 
can be compared using 
the $effort$-vs-$pd$ diagram of \fig{effort}.
The curves in that figure are generated as follows:
\bi
\item Some oracle {\em selects} a set of modules to inspect. In the case of automatic data mining, this would be the modules predicted
to be defective. In the case of {\em manualUp} and {\em manualDown}, it would be all modules.
\item The {\em selected} are sorted. For example,
except for {\em manualDown}, we sort all modules
ascending  on LOC.
\item The {\em selected} set is explored in the sorted order \mbox{$1 \le i \le |selected|$}.
Each $x$ value in \fig{effort} shows $\sum_i LOC_i$ found in the first $i$ modules.
\item
For each $x$ value, the $y$
value is the percentage of the defective modules seen in the first $i$ modules.
\ei
Typically, defect detectors do not trigger on all modules, and have some false alarm rate. 
For example, the {\em good} curve of \fig{effort} triggers on B=43\% of the code while only
detecting 85\% of the defective modules.  Similarly, the {\em bad} curve stops after finding 30\% of the defective
modules in 24\% of the code.
To compute the area under the $effort$-vs-$pd$ curve, 
we must fill in the gap between 
the termination point  and $X=100$.  In the sequel, we will assume
the QA team {\em only} inspects the modules referred to by the
data miner.
Visually, for the $good$ curve, this  assumption
 would correspond to
a flat line running to the right from point $C=85$.  


The $effort$-vs-$pd$ curve of 
\fig{effort} lets us define reasonable lower bounds on the performance of  an automatic data miner being used for  $application_1$.
For Arisholm \& Briand to approve of a data miner, its curve must fall {\em above} the diagonal line marked as {\em minimum}.
This is the region where $pd > effort$; i.e where
 the QA team can  {\em read less}
and  {\em finds more}.
Also,
 if Koru et al. are right then the {\em manualUp} and {\em manualDown} curves should appear as drawn in
 \fig{effort}; i.e. {\em manualUp} should find defective modules faster than {\em manualDown}.
 A {\em bad}  automatic method performs worse  than manual methods; i.e.
its $effort$-vs-$pd$ curve falls {\em below} the performance curves of the 
manual methods.
In $application_1$, there would be no business justification for a learner
that generates (e.g.) the $bad$ curve of \fig{effort} since it falls below one of the manual
curves.

\fig{effort} also lets us define a theoretical upper bound
on the performance of any learner tackling $application_1$.  Imagine an  omniscient oracle that restricts the
inspections to just the $A\%$ defective modules (in \fig{effort}, $A=30\%$). 
If  {\em manualUp} was then applied to just those defective modules,
then that would result in the {\em best} curve.  
Realistically, defect predictors can approach the {\em best} curve, but never reach it.  Hence, the most we can hope for 
is something like the {\em good} curve that  falls {\em below} the {\em best} curve and 
 {\em above} the {\em manualUp} and {\em manualDown} curves.

Two more details will complete our discussion of  \fig{effort}. 
Firstly, in the sequel, the following observation will become a significant point.
Even though \fig{effort} shows $effort$-vs-$pd$, it can also indirectly show $pf$.
Consider the plateau in the $good$ curve of \fig{effort},
marked with ``D'', at around $effort=10,pd=45$. Such plateaus mark false
alarms where the detectors are selecting modules that have no defects.
That is, one way to maximize the area under an $effort$-vs-$pd$ curve is to assign a heavy penalty
against false alarms that lead to plateaus.


Secondly, when comparing  supposedly {\em good} defect predictors,
it is useful to express their performance in terms of
the area under the $effort$-vs-$pd$
curve, expressed as
a ratio of
the area under the {\em best} curve. To be complete, that evaluation should contain the ``$\Delta$'' factor that models the effectiveness
of QA teams that inspect modules according to the defect predictors' recommendation
(and at $\Delta=1$, the inspection teams are perfect at recognizing defective modules). 
Note that 
 that factor applies to
the activity that occurs {\em after} the data miners runs and the modules are sorted in ascending order by LOC. 
Hence, it
is the {\em same across all data miners}.
By expressing the value of a defect predictor as a ratio of the area under the {\em best} curve, 
$\Delta$ cancels out.
In this way, 
for $application_1$,
we can assess the relative merits of different defect predictors {\em independently} of $\Delta$.

%XXX return to this point
We use $Q'$ to denote this performance measure; i.e. area under the $effort$-vs-$pd$ curve, measured
as a percentage of the area under the $best$ curve.
\subsection{Designing $P$ for $application_1$}
Recall that $P$ is the criteria used internally by the learner to grow a model. When the learner
terminates and outputs a model,  $Q$ is
used to assess the outputted model.

Our preferred $Q'$ was described in the last section. 
This section describes the $P'$ used by WHICH to incrementally grow candidate rule sets.
In summary, our experiments will using a $P'$ criteria that 
approximates the intent of $Q'$,
even if it does not implement it directly.

The $Q'$ criteria maximizes $pd$ while minimizing $effort$. To emulate
that criteria during rule generation, we experimented with:
\begin{equation}\label{eq:pprime}\scriptsize
 P' = 1 - \frac{\sqrt{pd^2*\alpha + (1-pf)^2*\beta + (1-effort)^2*\gamma}}{\sqrt{\alpha+\beta+\gamma}}
\end{equation}
where $(pd,pf,effort)$ were normalized to fall between zero and one.
The  $\alpha,\beta,\gamma$ terms of this expression represent
the relative utility of $pd,pf,effort$ respectively.
Clearly,
\[0 \le \left(P', \alpha,\beta,\gamma,pd,pf,effort\right) \le 1\] and larger values of $P'$ are better.
The $pf$ term was absent from the first version of $P'$ but was added after some initial experiments
that returned rules with high false alarm rates.
Note that {\em increasing} the $effort$ or $pf$ leads to a {\em decrease} in $P'$.

Initially, we gave $pd$ and $effort$ equal weights; i.e. \mbox{$\alpha=\gamma=1$}.
This yielded disappointing results: the performance of the learned detectors
varied wildly across our cross-val experiments.
%XXX needs to say what those results were. wild invariance
\fig{sizes} explains why: there exists a small number
of modules with very large LOCs. 
For example, there are 126 modules
in the $kc4$ data set, most of them are under 100 lines of code but a few of them
are over 1000 lines of code long.
The presence of small numbers of very large modules means that $\gamma=1$ is not recommended.
If the very large modules fall into a particular subset of some cross-val, then 
the performance associated with WHICH's rule can vary
unpredictably from one run to another.


\begin{figure}
\begin{center}
\includegraphics[width=2.5in]{lines.pdf}
\end{center}
\caption{Lines of code in a sample of our data sets.}\label{fig:sizes}
\end{figure}

To repair this problem, we had to deemphasize  $effort$ and
use $pf$ as a surrogate  measure.
False alarms create plateaus in
$effort$-vs-$pd$ curves (recall the above discussion on the point ``D'' in \fig{effort}).
Hence, in the following experiments, we used a variant of $P'$ that disables
$effort$ but places a very large penalty on $pf$; i.e.
$\alpha=1,\; \beta=1000,\; \gamma=0$.

% 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_1$} 
% 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: 



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

\begin{figure}[!t]
\renewcommand{\baselinestretch}{1}
\begin{center}
{\scriptsize\begin{tabular}{l@{~}l@{~}l@{~}r@{~}c} 
\multicolumn{4}{c}{~}& \multicolumn{1}{c}{2nd quartile, median }\\
data &rank & treatment & median $Q'$ & \multicolumn{1}{c}{and 3rd quartile} \\\hline
all& 1 &      which2&  70.9&\boxplot{   0.0}{  52.5}{  70.9}{27}{ 100.2}\\
& 1 &     micro20&  67.0&\boxplot{   0.0}{  50.0}{  67.0}{25.9}{ 100.0}\\
&2 &    manualUp&  61.1&\boxplot{   0.0}{  52.0}{  61.1}{16.4}{  99.3}\\
&3 &       n\aive Bayes&  56.8&\boxplot{   0.0}{  47.5}{  56.8}{15.6}{ 100.2}\\
&4 &  manualDown&  49.5&\boxplot{   0.0}{  43.8}{  49.5}{14.9}{ 100.5}\\
&5 &      which4&  49.2&\boxplot{   0.0}{  30.1}{  49.2}{29.6}{ 100.0}\\
&6 &      which8&  31.2&\boxplot{   0.0}{   1.7}{  31.2}{40.9}{ 100.0}\\
&6 &         j48&  27.6&\boxplot{   0.0}{  16.9}{  27.6}{26.3}{ 100.1}\\
&7 &        jRip&  21.9&\boxplot{   0.0}{  10.6}{  21.9}{26.3}{ 100.2}\\\hline
&& & & \multicolumn{1}{c}{50\%} 
\end{tabular}}
\end{center}
\caption{Results from all data sets of \fig{data}, combined from 10 repeats of a 3-way cross-val,
sorted by {\em median} $Q'$. 
The $rank$ values in column 1 were generated in the same manner as \fig{bands}.
}\label{fig:allr}
\end{figure}
\begin{figure}[!t]
\renewcommand{\baselinestretch}{0.5}
\begin{center}
{\scriptsize\begin{tabular}{l@{~}l@{~}l@{~}r@{~}c} 
\multicolumn{4}{c}{~}& \multicolumn{1}{c}{2nd quartile, median }\\
data &rank & treatment & median $Q'$ & \multicolumn{1}{c}{and 3rd quartile} \\\hline
ar4 &1 &      which2&  58.6&\boxplot{  33.6}{  49.6}{  58.6}{16.4}{  78.6}\\
& 1 &  manualDown&  56.5&\boxplot{  42.5}{  45.2}{  56.5}{18.5}{  84.2}\\
& 1 &       n\aive Bayes&  56.2&\boxplot{  33.6}{  47.7}{  56.2}{18.2}{  76.6}\\
& 1 &    manualUp&  56.2&\boxplot{  32.0}{  45.7}{  56.2}{16.9}{  70.4}\\
& 1 &      which4&  49.3&\boxplot{  11.6}{  36.7}{  49.3}{24.3}{  71.9}\\
& 1 &        jRip&  47.3&\boxplot{   0.0}{  34.0}{  47.3}{21.8}{  87.7}\\
&2 &     micro20&  49.2&\boxplot{   0.1}{  38.5}{  49.2}{17.9}{  78.6}\\
&3 &      which8&  42.6&\boxplot{   0.0}{  31.3}{  42.6}{15.3}{  66.1}\\
&3 &         j48&  38.8&\boxplot{   9.2}{  21.2}{  38.8}{31.2}{  67.2}\\\hline
cm1&1 &      which2&  68.1&\boxplot{   0.0}{  57.4}{  68.1}{14.1}{  81.5}\\
& 1 &     micro20&  64.7&\boxplot{   0.0}{  48.9}{  64.7}{21}{  89.1}\\
& 1 &    manualUp&  59.8&\boxplot{  48.3}{  57.4}{  59.8}{7.9}{  71.5}\\
&2 &       n\aive Bayes&  52.1&\boxplot{  36.2}{  46.0}{  52.1}{13.1}{  69.2}\\
&3 &  manualDown&  47.6&\boxplot{  33.6}{  40.3}{  47.6}{9}{  60.2}\\
&4 &      which8&  11.4&\boxplot{   0.0}{   0.0}{  11.4}{26.2}{  35.6}\\
& 4 &        jRip&   5.8&\boxplot{   0.0}{   0.0}{   5.8}{11.5}{  24.1}\\
& 4 &         j48&   0.1&\boxplot{   0.0}{   0.0}{   0.1}{12.9}{  33.3}\\
& 4 &      which4&   0.0&\boxplot{   0.0}{   0.0}{   0.0}{41.2}{  69.0}\\\hline
kc1&1 &      which2&  76.0&\boxplot{  71.4}{  73.8}{  76.0}{4.2}{  81.8}\\
&1  &     micro20&  75.1&\boxplot{   1.9}{  70.3}{  75.1}{5.9}{  80.1}\\
&2 &    manualUp&  67.6&\boxplot{  64.5}{  65.8}{  67.6}{3.1}{  70.0}\\
&3 &       n\aive Bayes&  61.9&\boxplot{  54.9}{  60.2}{  61.9}{2.8}{  67.7}\\
&4 &      which4&  52.9&\boxplot{   0.0}{  49.8}{  52.9}{5.4}{  60.5}\\
&5 &  manualDown&  43.3&\boxplot{  39.7}{  42.2}{  43.3}{3}{  47.7}\\
&6 &         j48&  27.8&\boxplot{  11.6}{  20.5}{  27.8}{11.2}{  40.1}\\
&7 &        jRip&  21.3&\boxplot{  10.2}{  17.3}{  21.3}{7.9}{  32.4}\\
&8 &      which8&   0.0&\boxplot{   0.0}{   0.0}{   0.0}{2}{  33.9}\\\hline
kc2&1 &      which2&  81.6&\boxplot{  65.6}{  76.0}{  81.6}{8.6}{  88.5}\\
&2 &     micro20&  74.8&\boxplot{  61.1}{  71.6}{  74.8}{7.8}{  88.4}\\
&3 &    manualUp&  69.3&\boxplot{  57.9}{  65.4}{  69.3}{5.6}{  76.6}\\
&4 &      which4&  59.4&\boxplot{  43.1}{  52.5}{  59.4}{14.3}{  79.6}\\
&4 &       n\aive Bayes&  58.7&\boxplot{  47.0}{  54.8}{  58.7}{6.2}{  69.4}\\
&5  &  manualDown&  46.1&\boxplot{  37.9}{  43.1}{  46.1}{9.2}{  62.4}\\
&5  &        jRip&  42.2&\boxplot{  22.2}{  36.0}{  42.2}{13.5}{  65.2}\\
&6 &      which8&  41.2&\boxplot{  26.3}{  36.5}{  41.2}{11.1}{  56.5}\\
&6 &         j48&  41.2&\boxplot{  26.0}{  36.1}{  41.2}{9.8}{  59.8}\\\hline
kc3&1 &      which2&  87.3&\boxplot{  73.3}{  82.4}{  87.3}{8.1}{  95.4}\\
&2 &     micro20&  76.3&\boxplot{  56.0}{  69.8}{  76.3}{11.6}{  94.6}\\
&3 &       n\aive Bayes&  64.2&\boxplot{  45.5}{  59.2}{  64.2}{10.4}{  75.4}\\
&3  &    manualUp&  64.2&\boxplot{  50.7}{  57.5}{  64.2}{10.6}{  77.4}\\
&4 &      which4&  47.8&\boxplot{   0.0}{  40.5}{  47.8}{18.1}{  67.2}\\
&4  &  manualDown&  47.6&\boxplot{  31.3}{  39.5}{  47.6}{16.1}{  66.8}\\
&4  &      which8&  46.7&\boxplot{   0.0}{  36.2}{  46.7}{16.5}{  62.1}\\
&5 &         j48&  23.1&\boxplot{   0.0}{  13.6}{  23.1}{15.3}{  42.6}\\
&5 &        jRip&  17.7&\boxplot{   0.0}{  13.1}{  17.7}{10.8}{  54.2}\\\hline
mw1&1 &      which2&  62.4&\boxplot{  35.8}{  57.4}{  62.4}{13.4}{  83.3}\\
&1  &  manualDown&  60.2&\boxplot{  42.8}{  52.1}{  60.2}{11.6}{  71.8}\\
&1  &     micro20&  55.7&\boxplot{   0.0}{  44.1}{  55.7}{19.9}{  78.5}\\
&2 &    manualUp&  47.8&\boxplot{  37.1}{  44.0}{  47.8}{7.9}{  62.5}\\
&3 &      which4&  42.7&\boxplot{   0.0}{  25.8}{  42.7}{24}{  60.6}\\
&3 &       n\aive Bayes&  41.7&\boxplot{  19.5}{  33.1}{  41.7}{14.6}{  62.1}\\
&4 &      which8&  39.3&\boxplot{   0.1}{  35.6}{  39.3}{12}{  60.4}\\
&5 &         j48&  20.0&\boxplot{   0.0}{  10.0}{  20.0}{14.3}{  42.9}\\
&5  &        jRip&  15.8&\boxplot{   0.0}{   7.9}{  15.8}{23.3}{  49.4}\\\hline
pc1&1 &      which2&  65.0&\boxplot{   0.0}{   0.0}{  65.0}{71.1}{  81.8}\\
&1  &     micro20&  64.4&\boxplot{   0.0}{  51.0}{  64.4}{17.9}{  78.6}\\
&1  &    manualUp&  60.6&\boxplot{  52.1}{  58.4}{  60.6}{5}{  71.6}\\
&2 &       n\aive Bayes&  51.5&\boxplot{  36.4}{  46.1}{  51.5}{7.3}{  60.9}\\
&3  &  manualDown&  44.6&\boxplot{  32.3}{  41.9}{  44.6}{4.3}{  55.3}\\
&4 &      which8&  22.6&\boxplot{   0.0}{   9.1}{  22.6}{21.6}{  47.7}\\
&4  &         j48&  19.2&\boxplot{   3.1}{  12.5}{  19.2}{12.1}{  41.5}\\
&4  &        jRip&  15.1&\boxplot{   0.0}{  11.0}{  15.1}{12.2}{  30.8}\\
&4  &      which4&   0.0&\boxplot{   0.0}{   0.0}{   0.0}{50.3}{  59.0}\\\hline
&& & & \multicolumn{1}{c}{50\%} 
\end{tabular}}
\end{center}
\caption{Seven examples of pattern \#1: WHICH2 ranked \#1 {\em and} has highest median.
This figure is reported in the same format as \fig{bands}.
}\label{fig:bands1}
\end{figure}

%XXXX why 10*3
% XXX from  the perspective of different proponents

\begin{figure}[!t]
\renewcommand{\baselinestretch}{1}
\begin{center}
{\scriptsize\begin{tabular}{l@{~}l@{~}l@{~}r@{~}c} 
\multicolumn{4}{c}{~}& \multicolumn{1}{c}{2nd quartile, median }\\
data &rank & treatment & median $Q'$ & \multicolumn{1}{c}{and 3rd quartile} \\\hline
ar3 &1 &  manualDown&  54.7&\boxplot{   0.0}{  40.0}{  54.7}{39.3}{ 100.5}\\
&1  &    manualUp&  52.6&\boxplot{   0.0}{  26.0}{  52.6}{34.3}{  99.3}\\
& 1 &         j48&  47.8&\boxplot{   0.0}{   0.1}{  47.8}{59.1}{ 100.0}\\
&1 &      which8&  42.7&\boxplot{   0.0}{   0.1}{  42.7}{61.6}{ 100.0}\\
&1 &      which2&  40.4&\boxplot{   0.0}{  20.6}{  40.4}{31.1}{ 100.2}\\
&2 &      which4&  41.8&\boxplot{   0.0}{  24.4}{  41.8}{28}{  89.2}\\
& 2 &     micro20&  38.0&\boxplot{   0.0}{   0.4}{  38.0}{54.1}{  77.2}\\
&3 &       n\aive Bayes&  34.4&\boxplot{   0.0}{   0.4}{  34.4}{42.3}{  60.8}\\
&4 &        jRip&   0.2&\boxplot{   0.0}{   0.0}{   0.2}{35.5}{  64.1}\\\hline
ar5&1 &     micro20&  77.6&\boxplot{  31.6}{  49.9}{  77.6}{37.2}{ 100.0}\\
& 1 &      which4&  71.4&\boxplot{   0.2}{  51.1}{  71.4}{32.1}{ 100.0}\\
& 1 &  manualDown&  69.6&\boxplot{  41.3}{  51.0}{  69.6}{30.5}{ 100.5}\\
& 1 &      which2&  67.6&\boxplot{   0.0}{  44.2}{  67.6}{36.2}{ 100.0}\\
& 1 &         j48&  56.1&\boxplot{   0.1}{  35.8}{  56.1}{34.7}{ 100.1}\\
& 1 &        jRip&  55.0&\boxplot{   0.0}{   0.2}{  55.0}{73.5}{ 100.2}\\
& 1 &       n\aive Bayes&  54.1&\boxplot{  24.3}{  42.7}{  54.1}{34.8}{ 100.2}\\
&2 &    manualUp&  56.5&\boxplot{   2.0}{  24.1}{  56.5}{39.5}{  80.9}\\
&3 &      which8&   0.0&\boxplot{   0.0}{   0.0}{   0.0}{31.1}{ 100.0}\\
\hline
&& & & \multicolumn{1}{c}{50\%} 
\end{tabular}}
\end{center}
\caption{Two examples of pattern \#2: While WHICH2 did not achieve the highest medians,
it was still ranked \#1 compared to eight other methods.
This figure is reported in the same format as \fig{bands}.
}\label{fig:bands2}
\end{figure}

\begin{figure}[!t]
\renewcommand{\baselinestretch}{1}
\begin{center}
{\scriptsize\begin{tabular}{l@{~}l@{~}l@{~}r@{~}c} 
\multicolumn{4}{c}{~}& \multicolumn{1}{c}{2nd quartile, median }\\
data &rank & treatment & median $Q'$ & \multicolumn{1}{c}{and 3rd quartile} \\\hline
mc2&1 &    manualUp&  74.3&\boxplot{  63.3}{  70.9}{  74.3}{7.4}{  80.4}\\
&2 &     micro20&  57.1&\boxplot{   0.0}{   6.3}{  57.1}{61.5}{  81.7}\\
&2  &       n\aive Bayes&  55.9&\boxplot{  21.4}{  46.6}{  55.9}{12.5}{  79.1}\\
&3 &         j48&  43.7&\boxplot{  21.9}{  29.3}{  43.7}{26.1}{  69.7}\\
&3  &  manualDown&  42.8&\boxplot{  29.7}{  38.1}{  42.8}{9.1}{  57.4}\\
&4 &        jRip&  28.5&\boxplot{  12.7}{  17.0}{  28.5}{18.2}{  56.4}\\
&5 &      which8&  21.9&\boxplot{   0.0}{  11.2}{  21.9}{16.2}{  42.4}\\
&6 &      which4&   5.6&\boxplot{   0.0}{   0.0}{   5.6}{25.3}{  47.9}\\
&6  &      which2&   0.0&\boxplot{   0.0}{   0.0}{   0.0}{40.8}{  99.7}\\
\hline
&& & & \multicolumn{1}{c}{50\%} 
\end{tabular}}
\end{center}
\caption{The only example of pattern \#3:  WHICH2 loses (badly) but  MICRO20 still ranks high.
This figure is reported in the same format as \fig{bands}.}\label{fig:bands3}
\end{figure}



%\begin{figure}
%\begin{center}
%{\scriptsize
%\begin{tabular}{l|lrrrr}
%rank & treatment & wins & ties & losses  \\\hline
%1 &      which2&    1&   7&    0\\
%1 &     micro20&    1&   7&    0\\
%2 &    manualUp&    0&   6&    2\\
%3 &       Bayes&    0&   5&    3\\
%4 &  manualDown&    0&   4&    4\\
%5 &      which4&    0&   3&    5\\
%6 &         j48&    1&   1&    6\\
%6 &      which8&    2&   0&    6\\
%7 &        jRip&    1&   0&    7\\
%\end{tabular}}
%\end{center}
%\caption{Mann-Whitney (99\%) analysis of the \fig{allr} results.  Each row shows
%a comparison of one treatment again the other eight.
%The rankings, shown on the left-hand-side,
%group together any treatments with the same ties+losses.
%}\label{fig:allrmann}
%\end{figure}

\section{Experiments}
\PARstart{F}{igure} \ref{fig:allr} shows results from experimental runs with different learners
on \fig{data}. Each run
randomized the order of the data ten times, then performed a N=3-way cross-val study
(N=3 was used since some of our data sets were quite small). For each part of the cross-val study,
pd-vs-effort curves were generated using:
\bi
\item {\em Manual methods}: manualUp and manualDown;
\item {\em Using standard data miners}: the j48 decision tree learner, the jRip rule learner, and our previously
recommended  n\aive Bayes method. For more details on these learners, see Appendicies I,II, and III.
Note that these standard miners included methods that we have advocated in prior publications \cite{%
jiang07,%
me00p,%
me02g,%
me02k,%
me03q,%
me04c,%
me05d,%
me07b,%
me07e%
}. 
\item Two versions of {\em WHICH}: 
WHICH2 discretized continuous ranges with a log filter, then divided the numerics into two equal width bins;
micro20 is WHICH2, plus the micro-sampling strategy discussed in \sect{micro}. For more details on WHICH,
see Appendix IV.
\ei
To be accurate, numerous versions of WHICH were explored, each  with different discretization policies. We only
report
WHICH2 and micro20 since they were  always on the upper envelope of the results. 

\subsection{Overall Results}
\fig{allr} shows the results for {\em all} the  data sets of \fig{data}, combined.
In terms of the title of this paper, 
the most important result is that
WHICH performs
{\em relatively}  better that
all of the other methods studied in this paper.
That is, unlike our prior results,  all the learners in this study do {\em not} 
hover around the same  performance ceiling.

Also, measured in {\em absolute} terms, WHICH performs very well.
In our discussion of \fig{effort}, the $best$ curve was presented as the upper bound 
in performance for any learner tackling $application_1$.
WHICH's performance rises close to this upper bound, rising to to 70.9 and 80\% (median  and 75\% percentile range) 
of the $best$ possible performance. 

Several other results from \fig{allr} are noteworthy.
\bi
\item
In a result consistent with our prior publications~\cite{me07b},  our n\aive Bayes
classifier
out-performs other standard data miners (j48 and jRip).
\item
In a result consistent with Koru et.al.'s logarithmic defect hypothesis,
manualUp defeats manualDown. 
\item
Also, in a result consistent with the limited information content hypothesis, micro20 has the same rank as WHICH2
(i.e. their performance is statistically indistinguishable). Recall that, under micro20-sampling, learning is
performed using just 40 examples, evenly mixed, of defective and non-defective modules.
\item
In \fig{allr}, standard data miners are defeated by a manual method (manualUp). 
The size of the defeat is very large: median values of 61.1\% to 27.6\% from manualUp to j48.
One very sobering result
in \fig{allr} is that two widely used methods (j48 and jRip) are defeated by manualDown; i.e. by a
a manual inspection method that Koru et al. would argue is the {\em worst} possible inspection policy.
These results calls into question the numerous prior defect prediction results,
including several papers written by the authors
\cite{%
jiang07,%
me00p,%
me02g,%
me02k,%
me03q,%
me04c,%
me05d,%
me07b,%
me07e%
}. 
\ei
%data mining technology. performs very well, defeating 

\subsection{Internal Validity}

\fig{allr} showed combined results from all of the data sets
in \fig{data}. From it, we concluded that
WHICH is preferred to other methods for $applciation_x$.

Figures \ref{fig:bands1},
\ref{fig:bands2}, and
\ref{fig:bands3} 
check the internal validity of this conclusion
by looking at each data set in isolation. 
The results divide into three patterns:
\bi
\item In the eight data sets of pattern \#1 (shown in \fig{bands1}),
WHICH2 has {\em both} the highest median $Q'$ performance 
{\em and} is found to be in the top rank by the Mann-Whitney statistical analysis.
\item
In the two data sets of pattern \#2 (shown in \fig{bands2}),
WHICH2 does not score the highest median performance, but still
is found in the top-rank.
\item
In the one data set that shows pattern \#3 (shown in \fig{bands3}),
WHICH2 is soundly defeated by manual methods (manualUp).
However, in this case, the WHICH variant micro20 falls into the second rank
\ei
In summary, when looking at each data set in isolation, WHICH2 performs very well
in $\frac{10}{11}$ of the data sets. Hence, we say that the general conclusion
of the last section
almost always holds for specific data sets.



% Reminder: the "draftcls", not "draft", class option should be used if
% it is desired that the figures are to be displayed while in draft mode.

% An example of a floating figure using the graphicx package.
% Note that \label must occur AFTER (or within) \caption.
% For figures, \caption should occur after the \includegraphics.
%
%\begin{figure}
%\centering
%\includegraphics[width=2.5in]{myfigure.eps}
%\caption{Simulation Results}
%\label{fig_sim}
%\end{figure}


% An example of a double column floating figure using two subfigures.
% (The subfigure.sty package must be loaded for this to work.)
% The subfigure \label commands are set within each subfigure command, the
% \label for the overall fgure must come after \caption.
% \hfil must be used as a separator to get equal spacing
%
%\begin{figure*}
%\centerline{\subfigure[Case I]{\includegraphics[width=2.5in]{subfigcase1.eps}
%\label{fig_first_case}}
%\hfil
%\subfigure[Case II]{\includegraphics[width=2.5in]{subfigcase2.eps}
%\label{fig_second_case}}}
%\caption{Simulation results}
%\label{fig_sim}
%\end{figure*}



% An example of a floating table. Note that, for IEEE style tables, the
% \caption command should come BEFORE the table. Table text will default to
% \footnotesize as IEEE normally uses this smaller font for tables.
% The \label must come after \caption as always.
%
%\begin{table}
%% increase table row spacing, adjust to taste
%\renewcommand{\arraystretch}{1.3}
%\caption{An Example of a Table}
%\label{table_example}
%\centering
%% The array package and the MDW tools package offers better commands
%% for making tables than plain LaTeX2e's tabular which is used here.
%\begin{tabular}{|c||c|}
%\hline
%One & Two\\
%\hline
%Three & Four\\
%\hline
%\end{tabular}
%\end{table}

\subsection{External Validity}

We argue that the data sets used in this paper are far broader (and hence, more
externally valid)
than seen in prior defect
prediction papers. All the data sets explored by Lessmann et al.~\cite{lessmann09} and
our prior work~\cite{me07b} come from NASA aerospace applications. Here, 
we use that data, plus three extra data sets from SOFTLAB, a Turkish company writing software controllers
for dishwashers (ar3), washing machines (ar4) and refrigerators (ar5).
The development practices from these two organizations are very different:
\bi
\item The SOFTLAB software was built in a profit- and 
revenue-driven commercial organization, whereas NASA is a cost-driven government entity
\item The SOFTLAB software was developed by very small teams (2-3 people) working in the same
physical location while the NASA
software was built by much larger team spread around the United States.
\item The SOFTLAB development was carried out in an ad-hoc,
informal way rather than the formal, process oriented approach used
at  NASA.
\ei
Our general conclusion,  that
WHICH is preferred to other methods for $applciation_x$, holds for $\frac{7}{8}$ 
of the NASA data sets and $\frac{3}{3}$ of the SOFTLAB sets.
The fact that the same result
holds  for such radically different organizations
is a strong argument for the external validity of our results.

%only hold for $application_1$.
%The whole point of this paper is to 
%to suggest to the research community that defect predictors should
%be assessed in the context of one application.  
%The external validity of that assessment
%to other business applications must therefore always be carefully monitored.
%Indeed,w e have
%preliminary results that WHICH's primacy with respect to
%$applciation_1$ does not hold for other applications. When we change
%the evaluation criteria $C_i$ from $balance$ to $accuracy$, and we
%ignore all effort considerations (so LOC is not included in $C_i$),
%then WHICH performs much worse than standard learners.    \fig{acc} 
%shows those accuracy results for four learners over
%one run over the data sets of \fig{data}\footnote{ZACH??}.
%Note how  WHICH's accuracy values are much worse than the other learners.
%
%\begin{figure}
%\begin{center}
%\includegraphics[width=2.5in]{plots/accuracy.pdf}
%\end{center}
%\caption{Accuracy results for four learners on the \fig{data} data.}\label{fig:acc}
%\end{figure}
%WHICH's poor performance with respect to accuracy is not surprising. 
%Standard learners have been developed and debugged for
%decades with the goal of improving accuracy. To date, we have not
%explored specific optimizations of WHICH to improve accuracy.
%For example, the variant of WHICH used in \fig{acc} discretized continuous values
%into just two ranges. We speculate that  smarter discretization policies 
%could significantly improve
%WHICH's performance.
\newpage
\section{Conclusion}
\PARstart{S}{ince} 2002~\cite{me02e}, we have been using standard data miners such as j48, jRip and n\aive Bayes
to learn defect predictors.
The general pattern of those results was documented above:
\bi
\item
From \fig{all}, we see 
Lessmann et al.~\cite{lessmann09} documenting an  effect that we have also observed~\cite{jiang08a}:
our learners suffer from a ceiling effect where supposedly more sophisticated learners do no
better than simple ones.
\item
From \fig{adfe}, we see that our prior work
generated
defect detectors from the \fig{data} data with a  $pd$ performance less than the $effort$.
Arisholm \& Briand~\cite{arisholm06} might dismiss these results, arguing that 
since we are finding X\% of the faulty modules after reading more than X\% of the code, then
the cost of generating the defect predictor is not worth the effort. 
\ei

These results are troubling, on two counts.
Firstly, our prior results do not add value to a budget-conscious test engineering team using the 
defect predictors to prioritize their inspection process (a task we have called $application_1$).
Secondly, neither our own research~\cite{jiang08a} nor the research of others~\cite{lessmann09}
has resulted in methods that improve 
our prior results 
(at least, for the purposes of extracting defect predictors from \fig{data} data).

The above negative results prompted the basic rethinking of the defect prediction problem presented in this
paper.
Based on:
\bi
\item the {\em RandomReduction} results of \fig{tone};
\item the {\em StructuredReduction} results of 
\fig{bands};
\item  and the micro20 results shown in 
Figures \ref{fig:bands1} \&
\ref{fig:bands2} \&
\ref{fig:bands3}
\ei
We assert that the performance of our learners will not improve merely by
passing more of the {\em same} kinds of data to our learners. The {\em RandomReduction}
and {\em StructuredReduction} experiments offer support for a {\em limited information content}
hypothesis
in static code features. 
i.e.
(i)~simple learning methods
will uncover all that can be found and  (ii)~more sophisticated
data mining methods will yield no more information.

Accordingly, we explored the value of
giving the learners {\em different} kinds of knowledge. Standard learners 
use some intra-learning assessment criteria $P$ to generate predictors. The learned model
is 
 assessed by a post-learning assessment criteria
$Q$. In all our prior work, $P\not=Q$. Therefore, it seemed important to try 
a new kind of learner, called WHICH, where $P\approx Q$.

The version of WHICH used in this study
was deliberately designed to be unsophisticated.
For example, it has no over-fitting operator that prunes
away superfluous parts of a model.
WHICH's search for predictors is completely random, biased
only by
some $P$ function. 
That is,  the performance of this study's WHICH learner was
{\em solely} determined by $P$. As such, it is an ideal tool
for assessing the value of learners where $P\approx Q$.


Our experiments used  $P$ criteria that 
approximates the intent of $application_1$'s $Q$ criteria,
even though it does not implement it directly.
Initially, we tried
$P=Q$ but, under cross-val, the presence of a small number of very large modules (see \fig{sizes})
resulted in wild variations in the measured performance. 
In the discussion around \fig{task1}, it was observed that
false alarms  lead to plateaus in an $effort$-vs-$pd$ curves. That is, one way to increase the area under a $effort$-vs-$pd$ curve is to 
assign a heavy penalty
against false alarms. 
In the above results, we used the  utility function shown in \eq{pprime} where
$pd$:$pf$ was weighted 1:1000.

The performance measure used in this study was area under an $effort$-vs-$pd$ curve,
expressed as a ratio of the area under the same curve for a
theoretical upper bound on any leaner tackling $application_1$ (i.e. the $best$ curve of \fig{task1}).
WHICH's results were compared to manual methods and standard learners using {\em median} performance
measures plus statistical tests
(Mann-Whitney, 95\%) to {\em rank} the performance of all learners/ manual methods. The results
are highly supportive of our hypothesis that learners that use $P\approx Q$ can out-perform other learners
where $P\not= Q$:
\bi
\item
In 7/11  data sets, WHICH scored  the highest median \&  rank. 
\item
In 2/11 data sets,
WHICH scored the highest ranking. 
\item
In the remaining data set, the standard WHICH algorithm (WHICH2) performed very badly but the micro-sampling
version of WHICH (micro20) scored the highest rank.
\ei
Hence, we recommend the use of WHICH2 or the micro20 variant for learning defect predictors for
$application_1$.

This recommendation
may not hold beyond the context of $application_1$. This
is not necessarily a flaw with this study. Rather, it our view that
it is a mistake to assess a learner {\em except} in the context of a
specific business context. The case for this view has been made above but we add
one further point here. The business acceptance of our data mining technology will
be greater if we can offer the learners {\em alongside} results relating to some
business-relevant application.

Finally, we find that the conclusion of Lessmann et al. (quoted in the introduction)
is correct in certain contexts.
They advise that
practitioners are free to choose from a broad set of candidate models when building defect predictors.
This is certainly true when defect detectors are assessed via accuracy since, in that case, they
all exhibit a ceiling effect.
However, when
they are assessed by other criteria (e.g. maximizing $effort$-vs-$pd$) then some learners such
as WHICH can break through that ceiling.
Overall, WHICH's performance was very good 
and rose to within
70.9 and 80\% (median  and 75\% percentile range) 
of the $best$ possible performance. 
Measured on the same scale, other learners such as j48, jRip, and n\aive Bayes, perform much worse.

% if have a single appendix:
%\appendix[Proof of the Zonklar Equations]
% or
%\appendix  % for no appendix heading
% do not use \section anymore after \appendix, only \section*
% is possibly needed

% use appendices with more than one appendix
% then use \section to start each appendix
% you must declare a \section before using any
% \subsection or using \label (\appendices by itself
% starts a section numbered zero.)
%
% Use this command to get the appendices' numbers in "A", "B" instead of the
% default capitalized Roman numerals ("I", "II", etc.).
% However, the capital letter form may result in awkward subsection numbers
% (such as "A-A"). Capitalized Roman numerals are the default.
%\useRomanappendicesfalse
%

% use section* for acknowledgment
% optional entry into table of contents (if used)
%\addcontentsline{toc}{section}{Acknowledgment}

% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
% adjust value as needed - may need to be readjusted if
% the document is modified later
%\IEEEtriggeratref{8}
% The "triggered" command can be changed if desired:
%\IEEEtriggercmd{\enlargethispage{-5in}}

% references section
% NOTE: BibTeX documentation can be easily obtained at:
% http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/

% can use a bibliography generated by BibTeX as a .bbl file
% standard IEEE bibliography style from:
% http://www.ctan.org/tex-archive/macros/latex/contrib/supported/IEEEtran/
%\bibliographystyle{IEEEtran.bst}
% argument is your BibTeX string definitions and bibliography database(s)
%\bibliography{IEEEabrv,../bib/paper}
%
% <OR> manually copy in the resultant .bbl file
% set second argument of \begin to the number of references
% (used to reserve space for the reference number labels box)

\bibliographystyle{IEEEtran}
\bibliography{refs}
\appendices
\section{N\aive Bayes Classifiers}
N\aive Bayes classifiers
offer a relationship between  fragments of evidence $E_i$,
a prior probability for
a class $P(H)$, and a posteriori  probability
$P(H|E)$: 
\begin{equation}\label{eq:bayes}
P(H|E)= \prod_iP(E_i|H) \frac{P(H)}{P(E)}
\end{equation}
%For example, in our data sets, there are two hypotheses: modules are either
%defective or note; i.e. \mbox{$H\in {defective,nonDefective}$}.
%Also, if a particular module has $numberofSymbols=27$ and
%$LOC=40$ and was previously classified
%as ``defective'' then
%\[
%\begin{array}{lcl}
%E_1&:& numberOfSymbols=27\\
%E_2& :& LOC=40
%\end{array}
%\]
%When building defect predictors,
%the
%posterior probability of each class (``defective'' or ``defect-free'')
%is calculated, given the features
%extracted from a 
%module.
%So, if a data set has 100 modules and 25 of them are faulty, then:
%\[P(defective)=0.25\]
%When testing new data, a module is assigned to the class
%with the higher probability, calculated from \eq{bayes}.
%

For
numeric features, 
a features mean $\mu$ and standard deviation $\sigma$ are used in
a
Gaussian  probability
function~\cite{witten05}:
\[f(x) =
1/(\sqrt{2\pi}\sigma)e^{-\frac{(x-\mu)^2}{2\sigma^2}}\] 

Simple  n\aive Bayes classifiers are called ``naive'' since they assume
independence of each feature. 
Potentially, this is a significant problem for data sets where
the static code measures are highly correlated (e.g. the number of
symbols in a module increases linearly with the module's lines of code). 
However, Domingos and Pazzini have shown theoretically
that the independence assumption is a problem in a vanishingly small percent
of cases~\cite{domingos97optimality}. 
This result
explains (a)~the repeated
empirical result that, on average, seemingly n\aive Bayes classifiers perform as well
as other seemingly more sophisticated schemes (e.g. see Table~1 in~\cite{domingos97optimality});
and
(b) our prior experiments where n\aive Bayes did not perform
worse than other learners that continually re-sample the data for dependent
instances (e.g. decision-tree learners that recurse
on each ``split'' of the data~\cite{quinlan92}).

%
% If you had an eps/pdf photo file (graphicx package needed)
% the extra braces prevent the LaTeX parser from getting confused
% when it sees the complicated \includegraphics command within an
% optional argument. You can create your own macro to make things
% simpler here.
%\begin{biography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{mshell.eps}}]{Michael Shell}
% or if you just want to reserve a space for a photo:

\section{The j48 Decision Tree Learner}

j48~\cite{witten05} is a JAVA port of Quinlan's decision tree learner
C4.5, release 8~\cite{quinlan92}.
j48 is  a {\em   iterative dichotomization algorithm} that seek the best attribute 
value {\em splitter} that most simplifies the data that falls into the different splits. Each 
such splitter becomes a root of a tree. Sub-trees are generated by calling iterative 
dichotomization recursively on each of the splits. 
j48 is defined for discrete 
class classification and uses an information-theoretic measure to describe the diversity 
of classes within a data set. 
A leaf generated by j48 stores the most frequency class seen during training. During test,
an example falls into one of the branches in the decision tree and is assigned the class from
he leaf of that branch.
J48 tends to produce big ``bushy'' trees so the algorithm includes a {\em pruning} step.
Sub-trees are eliminated if their removal does not greatly change the error rate of the tree.

\section{The RIPPER Rule Learner}
RIPPER~\cite{cohen95r}  is a {\em rule-covering} algorithm;
i.e. one rule is learned at each pass for the {\em majority class}.
All the examples that satisfy the rule condition
are marked as {\em covered} and are removed from
the data set. The algorithm then recurses on the remaining data. 

RIPPER takes a rather unique stance to rule generation and has operators
for 
{\em pruning}, {\em description length} and {\em rule-set
optimization}
For a full description of these techniques, see\cite{dietterich97}.
In summary,
after building a {\em rule}, RIPPER performs a back-select to see what parts of a {\em condition}
can be pruned, without degrading the performance of the rule.
Similarly,
after building a {\em set of rules}, RIPPER tries pruning away some of the rules.
The learned rules are built while minimizing  their {\em description length};
the size of the learned rules,
as well as a measure of the rule errors. 
Finally, after building rules, RIPPER
tries
replacing 
straw-man alternatives (i.e. rules grown very quickly by some
n\aive method).

%XXX get rid of Naive

\section{The WHICH Rule Learner}
% There are many learners that generate a numeric summary of the training examples; e.g
% the N\aive Bayes classifier described above;
% neural networks' support vector machines; principal components analysis; single value
% decomposition; or instance-based learners.
% Such learners use the numeric summary in  parametric evaluation (e.g \eq{bayes}) 
% to make conclusions
% about test examples. For example,  a Bayes classifier uses \eq{bayes} while an instance-based learner
% may use a Euclidean distance estimator to infer a conclusion from  the $k$ nearest training examples.

% An alternative approach is to generate a high level symbolic description~\cite{witten05}
% such as  a decision tree or set of rules. Such trees/rules can be  read and evaluated, even by
% business users without mathematical training. 


WHICH inputs a set of training examples
and a evaluation criteria $P\approx Q$ and outputs a single rule that is best for maximizing $P$.
 
Following the recommendations of~\cite{me07b}, all numeric data is transformed using
$x=log( max(0.00001,x))$\footnote{Many static code attributes have an exponential 
distribution with a small number of very large outliers.
This ``log transform'' flattens the distribution and makes the 
learning simpler. For more details, see~\cite{me07b}.}
then divided into $N$ ranges using equal-width discretization. Given a value $X$ from a column of data with minimum
and maximum values $min,max$ (respectively), then\begin{equation}\label{eq:dist}
RANGE(X)=floor\left(\frac{X - min}{(max-min)/N)}\right)+1
\end{equation}
This discretization policy
divides the values from a continuous variable  into $N$ ranges.
In this study, we
explored several variants of WHICH using different number of ranges including WHICH2, WHICH4, 
and WHICH8 that use N=2,4,8 ranges (respectively).

Internally, WHICH maintains a stack of conditions, sorted by the evaluation criteria $P$. For example, if $P_{pd}$ is the probability of detection
(see \eq{pd} in \fig{measures}), then the condition $LOC==0$ has the score $P_{pd}=0$ (since all modules have at least one line of code).
Hence, according to $P_{pd}$, this condition will be sorted to the bottom of the stack.

WHICH initializes the stack by scoring all the discretized  ranges from \eq{dist} 
generated from the discretization. As shown in \fig{stack}, all the raw scores are accumulated and normalized using 
\[normalized(i) = \frac{\sum^i_1 score(i)}{sum~of~all~scores}\]
\begin{figure}
\scriptsize
\begin{center}
\begin{tabular}{r|rr|l}
i&raw score& cumulative   & normalized\\\hline
1&100 & 100 &100 / 220 = 0.45\\
2&100 & 200 & 200 / 220 = 0.91\\
3&10  & 210 & 210 / 220 = 0.95\\
4&3 & 213 & 213 / 220 = 0.97\\
5&3 & 216 & 216 / 220 = 0.99\\
6&2 & 218 & 218 / 220 = 0.99\\
7&2 & 220 & 220 / 220 = 1.00
\end{tabular}
\end{center}
\caption{Example of scores on the WHICH stack.}\label{fig:stack}
\end{figure}
After initialization, WHICH enters a loop:
\be
\item $Old$ = score of the top of the stack
\item $Loop$ number of times, repeat:
\bi
\item[2a]: Pick two items from the stack, favoring those with higher score.
\item[2b]: Combine them and score the combination using $E$
\item[2c]: Sort the new combination into the stack
\ei
\item $New$ = score of top of stack
\item If $New > Old$  goto 1
\item Else return top of stack
\ee
Note that, initially, all the stack items are single conditionals. As the loop continues,
singletons may be combined into doubles which might  then combine into triples, etc.

We set the $Loop$ variable using our engineering judgment. \fig{picks} shows typical results from WHICH (running over sample
UCI data sets~\cite{Blake+Merz:1998}).  The score of the top-of-stack condition usually stabilizes in a remarkably short time
(after less than a dozen ``picks''; i.e. applications of step 2, described above). Occasionally, modest
 improvement is seen after 100 picks (see
plot marked with an ``A'').
Hence, to be cautious, we set $Loop$ to 200.

\begin{figure}
\begin{center}
\includegraphics[width=2.5in]{picks.pdf}
\end{center}
\caption{Top-of-stack scores of the WHICH stack seen after multiple ``picks'' (selection and scoring
of two conditions picked at random, then combined) for seven data sets from the UCI data mining repository~\cite{Blake+Merz:1998}.
Usually, top-of-stack stabilizes after just a  dozen pick. However, occasionally,
modest improvements are seen after a few hundred ``picks''
(see the plot marked   with  an ``A''). }\label{fig:picks}
\end{figure}
When selecting items for combination,
WHICH (a)~generates a random number $0 \le r \le 1$;  (b)~runs down the stack from top to bottom;
(c)~returns the first condition for which the normalized cumulative score is less than or equal to $r$.
On average, this approach returns conditions nearer top-of-stack (i.e. those with higher score).

Note that, when combining conditions, ranges from {\em different} features are joined using a {\em  conjunction} and ranges from the 
{\em same}
feature are joined with a {\em disjunction}. For example,  adding  $a=1$ to  \mbox{``$a=2 \wedge b=3$''} results in
\mbox{``$(a=1 \vee a=2) \wedge b=3$''}.

Also, when adding new combinations to the stack, 
if  a counter holds the total score of all conditions added to the stack, then the stack needs only hold the sorted raw score column.
All of the other columns can be computed-on-the-fly during by the condition selection algorithm described in the last point.
This avoids tedious updates of cumulative scores over the whole stack.


WHICH is fully described  elsewhere~\cite{milton08}.  For the reader conversant with AI literature, we remark:
\bi
\item
WHICH is a stochastic variant of beam search where the maximum height of the stack is the size of the beam. 
A standard beam search sweeps out over a tree of possibilities and performs cautious additions to each leaf (at most, only
graft one more test to the current branch).
WHICH's original design was a non-cautious beam search that copied entire sub-trees
from other branches in the  search, then grafted them onto the current branch. On reflection, we realized that the 
the above stack structure achieves the same goal, while being much simpler to implement.
\item The early stabilization of the top-of-stack is consistent with the {\em back door variable} effect discussed in the constraint
satisfaction literature~\cite{williams03}; i.e. many domains have  a small number of variables that control everything else.
If a domain has such ``back doors'' then (a)~all solutions must use them;  (b)~all changes to the output variables will be associated with
different ranges for the back doors; (c)~a stochastic search like WHICH will suffice to find them. Elsewhere, we  offer extensive
discussions on the implications of back doors on decision making in software engineering~\cite{me02c,me03l}.
\ei


WHICH would be a fruitful workbench for further experimentation. Our current results leaves many unexplored possibilities:
\bi
\item
It is possible to restrict the size of the stack to some maximum depth (and new combinations that score less than bottom-of-stack are
discarded). For the study shown here, we used an unrestricted stack size.
\item
Currently, WHICH sorts new items  into the stack using a linear time search from the top-of-stack. This is simple to implement via
a linked list structure but a faster alternative would be a  binary-search over skip lists~\cite{pugh90}.
\item Other rule learners employ a greedy back-select to prune
  conditions. To implement such a search, check to see if removing any part
  of the combined condition improves the score. If not, terminate the
  back select. Else, remove that part and recurse on the shorter
  condition.  Such a back-select is coded in the current version of
  WHICH, but the above results were obtained with back-select
  disabled.  
\item
Currently our default value for $Loop$ is 200. This may be an overly cautious setting.
 $Loop$ might be safely initialized to, say, 20 and only increased if no dramatic improvement is seen in the first loop.
Our initial experiments suggest that,
for most domains, this would yield a ten-fold speed increase.
\ei
We encourage further experimentation with WHICH. The current release is released under the GPL3.0 license and can be downloaded from
\url{http://unbox.org/wisp/tags/which}.

\end{document}

\begin{biography}[{\includegraphics[width=0.8in,height=0.8in]{tim/tim_menzies}}]{Tim Menzies}
is a  associate professor
at the Lane Department of Computer Science and Electrical Engineering at West Virginia University
(USA), and has been working with
NASA since 1998. He has a CS degree and a PhD
from the University of New South Wales and is the author of over 170 publications and a member of the IEEE.
\end{biography}
\begin{biography}[{\includegraphics[width=0.8in,clip,keepaspectratio]{zach/zach}}]{Zachery 
Milton} 
is a graduating Master's student in the
Lane Department of Computer Science and Electrical
Engineering at West Virginia University.  His
interests include machine learning and graphics
programming.
\end{biography}
\begin{biography}[{\includegraphics[width=0.8in,clip,keepaspectratio]{burak/burak}}]{Burak Turhan}
 is a research assistant and pursuing a PhD degree in the department of Computer Engineering at Bo{\u g}azi{\c c}i University. He received his BS and MS degrees from the same department. His research interests include all aspects of software quality and are focused on software defect prediction models. He is a student member of IEEE,  and ACM SIGSOFT. 
\end{biography}
\begin{biography}[{\includegraphics[width=0.8in,clip,keepaspectratio]{yue/yue}}]{Yue Jiang}
is a PhD student in the Lane Department of Computer Science
and Electrical Engineering at West Virginia University. Her received her
 MS degree from the same department. Her research interests include
data mining,  software defect prediction,  and bioinformatics.
\end{biography}
\begin{biography}[{\includegraphics[width=0.8in,clip,keepaspectratio]{greg/greg}}]{Gregory Gay} 
is a graduating senior in the Lane Department of
Computer Science and Electrical Engineering,
West Virginia University (USA) and plans to continue there as a MS student this fall. He is the chair of the university's student chapter of the ACM and a student member of IEEE. His interests include (but are not limited to) machine learning, the open-source movement, and Ludology (game studies).
\end{biography}
\begin{biography}[{\includegraphics[width=0.8in,clip,keepaspectratio]{bojan/bojan}}]{Bojan 
Cukic} is the 
  Robert C. Byrd Associate Professor of Computer Science and
  Electrical Engineering, West Virginia University . He  received a
  Dipl. Ing. (BS) degree in Computer Science from the University of
  Ljubljana, Slovenia, and both M.S. and Ph.D. degrees in Computer
  Science from the University of Houston in 1993 and 1997,
  respectively. 
\end{biography}
\begin{biography}[{\includegraphics[width=0.8in,clip,keepaspectratio]{ayse/ayse}}]{Ay\c{s}e  Bener}
is an assistant professor and a full time faculty member in the Department of Computer Engineering at Bo{\u g}azi{\c c}i University. Her research interests are software defect prediction, process improvement and software economics. Bener has a PhD in information systems from the London School of Economics. She is a member of the IEEE, AAAI and the ACM.
\end{biography} 
% You can push biographies down or up by placing
% a \vfill before or after them. The appropriate
% use of \vfill depends on what kind of text is
% on the last page and wither or not the columns
% are being equalized.

%\vfill

% Can be used to pull up biographies so that the bottom of the last one
% is flush with the other column.
%\enlargethispage{-5in}

% that's all folks
