%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}
%\documentclass[9.5pt,journal,cite, compsoc,twocolumn]{IEEEtran}
\documentclass[9.5pt,journal,final,finalsubmission,twocolumn]{IEEEtran}
%\documentclass[journal,compsoc,twocolumn]{IEEEtran}
% *************************************************************************


% 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 noadjust 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{\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, \\Ay\c{s}e Bener, Bojan Cukic, Gregory Gay, Yue Jiang, Burak Turhan% <-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{momoku@gmail.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 twoside 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}
Static code attributes have {\em limited information content}. Hence,
static code predictors have encountered a 
{\em ceiling effect} where
supposedly more sophisticated learners do no 
better than simpler methods.
If lack of information is the problem, then 
the solution is clear: give
our learners more knowledge.
Typically, learners build predictors using a performance
criteria $C_1$ (e.g. accuracy), then assess them
using another criteria $C_2$ (e.g. probability of detection)
That is, during training, our
learners are {\em blind to their purpose}.  Given this, it is hardly surprising  
that they cannot find ways to improve their performance.
WHICH is a new learner with $C_1 = C_2$; i.e.  the same evaluation
criteria is applied during training and testing. After  matching
$C$ to  the goals of a particular business application, we report
three effects. Firstly, commonly used learners perform {\em no
better than} simple manual methods. Secondly, WHICH clearly outperforms
other methods, coming remarkably close to a theoretical upper bound
in performance  (XXX median value over 82\%).
That is, with knowledge of the business
application, it is possible to build new learners that overcome
ceiling effects.
\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 data mining algorithms
 to learn  defect predictors
from static code features;
see
\cite{%
fea02a,%
jiang07,%
me00p,%
me02g,%
me02k,%
me03q,%
me04c,%
me05d,%
me07b,%
me07e%
}.
Based on all that work we assert:
{\em there has been 
\underline{too much} emphasis on machine learning, and 
\underline{too little} attention
on the use of specific software engineering knowledge.}

While the current generation of detectors are demonstrably 
useful and, in certain contexts, better than current
industrial best practice~\cite{me06d,me07b}, we believe that these AI methods 
have hit a {\em performance ceiling};
i.e., some inherent upper bound on the amount
of information offered by, say, static code features when identifying modules which contain faults.
After much experimentation, we have come to doubt
that better defect predictors can be found just by trying better machine 
learning methods.

We speculate that we can overcome this ceiling effect by giving our
learners more access to business knowledge that characterizes
software projects. The WHICH learner is a test of that speculation.
This paper
assesses WHICH in the context of  
a standard business application we will all $application_1$:
i.e. inspect the {\em fewest} lines of code; find
the {\em most} number of defective modules.

This paper is structured as follows:
\bi
\item 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. 
\item
Two data reduction experiments
will confirm this hypothesis and show the performance of our 
defect predictors stabilize after seeing just a handful of examples.
\item
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.
WHICH's output will then be compared to three standard data miners as well
as simple manual methods.
\item
The experiments will show that
for $application_1$,
manual methods out-perform standard data miners. 
That is,  for $application_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. 
\item
Also, 
WHICH will significantly out-perform {\em both} manual methods {\em and}
standard data miners while coming close to a theoretical upper performance bound.  
\ei
Our conclusion will be that knowledge of the business
application can be used by data miners to overcome
ceiling effects.
Note that
the data reduction experiments have been reported previously~\cite{me08d}. However, the
rest of this paper including the experiments with WHICH is new work.

\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 mining learn defect predictors from static code features,
either from projects previously developed in the same environment or
from a continually expanding base of 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}.  Static code features are
described in
Figure \ref{fig:attr},\ref{fig:halstead},\&\ref{fig:mccabe}

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''. 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 predicts that they exhibit
high code complexity measures.

One reason for the popularity of static code defect predictors is
that they 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}).

\begin{figure}[!t]
\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}
\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}
\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 uses 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 should be compared to
baselines in data mining and industrial practice.
Raffo (personnel communication) found that industrial reviews find \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  a 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 repostiroy~\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.
Experiment 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\%) 
Note that this is close to the results we have obtained via data mining on static code attributes
 ($pd$,$pf$)=(71\%,25\%), 
which is noteworthy in two ways.
Firstly, 
it is unexpected. If static code attributes capture so little
about source code (as argued by Fenton), then we would expect lower probabilities
of detection much higher false alarm rates. 
Secondly, 
these $(pd,pf)$ results are 
better than currently
used industrial methods such as the $pd{\approx}60\%$ reported
at the 2002 IEEE Metrics panel or the $median(pd)=21..50$ reported
by Raffo.
% \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.
% }.


%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. Even after years
of exploring many learners and data pre-processing methods, the performance of our
learners are not improving. 

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: \bi
\item Public domain data sets\footnote{From \url{http://promisedata.org}};
\item
Open source data mining
tools (the WEKA toolkit~\cite{witten05});
\item
Randomly sorting 
training data rows (stops
order effects);
\item
10-way cross-validation (to test on data {\em not} used in training);

\item
Assessment 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});
\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;
\item
Learning via multiple types of machine learning algorithms: rule
learners, decision tree learners, Bayes classifiers.
Surprisingly, very simple Bayes classifiers (with a simple
pre-processor for the numerics)
out-performed the other studied methods. For details on Bayes classifiers,
see Appendix A.
\ei


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 no additional
statistically significant improvement from the application of the
following data mining methods: logistic regression; average
one-dependence estimators; under- or
over-sampling~\cite{drummond03}; instance-based learning; random forests,
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 example,   one very extensive recent study  (currently under review at TSE\footnote{On request, we can supply a reference
to this paper. It is a paper under active review in the TSE editorial system, co-ordinating
editor: Dr. Bev Littlewood. })
investigated the statistical difference of the results from two
dozen
learners on the same datasets that we have previously explored.
The simple Bayesian method we recommended in~\cite{me07b}
 tied in
first place along with 15 other methods.


%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 can we 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 supposedly more sophisticated
data mining methods will yield no more information than simpler methods.

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 broken by more sophisticated 
data mining methods;
\item The only way through the ceiling effect is to give our data miners
different {\em kinds} of information. 
\ei

\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$ 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}. Space does not permit
showing all the results but a representative sample
are 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) 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.


\begin{figure}[!t]
\begin{center}
\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}
\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{Fifteen 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}

\subsection{Structured Reduction Experiments}

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.

Three examples of  {\em StructuredReduction} are
micro-, over-, and under-sampling~\cite{drummond03,yun04}.  All these methods  build
datasets with 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,.\} \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 once data set of
size $2N$.
\ei 


\begin{figure}[!t]
\scriptsize
\begin{center}
\begin{tabular}{r@{~}|c@{~}c@{~}c@{~}c@{~}c@{~}|l}
\multicolumn{1}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{2-6}
&min& & median & &max\\\cline{2-6}
treatment&0& 25\%& 50\% & 75\%&100\%\\\hline
NB/ none & 21.9& 67.7& 74.6& 81.9&100.0&\boxplot{21.9}{67.7}{74.6}{14}{100}\\                                        
NB/ under&19.9& 67.1& 74.1& 81.6&100.0&\boxplot{19.9}{67.1}{74.1}{15}{100}  \\
J48/ under& 21.6& 64.8& 73.6& 82.6&100.0&\boxplot{21.6}{64.8}{73.6}{18}{100}\\ 
NB/ over  &17.5& 42.0& 62.5& 72.2&100.0&\boxplot{17.5}{42}{62.5}{30}{100} \\
J48/ over & 0.0& 29.3& 45.6& 56.2&100.0&\boxplot{0}{29.3}{45.6}{27}{100}\\
J48/ none & 0.0& 29.3& 42.3& 54.5&100.0&\boxplot{0}{29.3}{42.3}{25}{100}\\\cline{2-6}
\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 left-hand-side values are shown right-hand-side as simple quartile charts where
a circle shows the median value; 
the line shows the middle quartiles ($\pm 25\%$ from the median);
and a  vertical line marks
the 50\% value.
Visually, there is clear loser (J48/none) and
a three-way  tie for the winning method (NB/none, NB/under, J48/under).
These visual impression are confirmed by the statistical
tests  of \fig{stats}.}\label{fig:bands}
\end{figure}

\begin{figure}[!t]
\scriptsize
\begin{center} 
\begin{tabular}{r|r|rrr}
learner / sampler& win - loss & win & loss & ties\\\hline
nb / none &3& 3 & 0& 2\\
nb / under&3& 3 & 0 & 2\\
j48/ under & 3 & 3  & 0 & 2\\
nb / over &-1& 2 & 3 & 0\\
j48/ over & -3 &1 &4&0 \\
j48/ none & -5 & 0 & 5 & 0
\end{tabular}
\end{center}
\caption{{\em StructuredReduction} results: statistical tests on the \fig{bands} results.
Six treatments are shown in column one and each row shows how each treatment compared
to the other five.
the 
Mann-Whitney~\cite{mann47} test (95\%) was used to compared the median ranks of all the $balance$
values seen in \fig{bands}.
 Two treatments tied if their median ranks were
statistically insignificantly different (95\% confidence). Otherwise,
medians were compared numerically to assign ``win'' or ``loss'' for
each treatment against the other five. This table is sorted in descending
order on the total number of ``$wins$''-``$losses$'' for each treatment against
the other five. Hence, better methods appear at the top of the table.
}
\label{fig:stats} \end{figure}



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 Naive 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 our experiments
with other learners have not be productive. For more details on J48, see Appendix B.

\fig{bands} shows the under- and over- $balance$ results (and recall that $balance$
was defined in \fig{measures}).
The results are  divided into {\em quartiles}; i.e. all results, sorted, divided
into four equal sized groups. The figures on the right hand side of \fig{bands} give a 
simple visual summary of the results and
\fig{stats} shows a statistical summary. 
The pattern of results is very clear, both visually and statistically:
\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 Naive 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
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]
\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 this visual pattern. 
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, for that data sets, in all by one case,
$M=25$ did as well as any larger value.
\ei
\input{adding}


\input{results}
\subsubsection{Subsubsection Heading Here}
Subsubsection text here.

% 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}

\section{External Validity}


The aim of this paper was to suggest to the research community that learners 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.

Our results may not hold beyond the context of $application_1$. This
is not necessarily a fault with this paper. 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.

XXX and what held?

XXX AR?
\section{Conclusion}
Previously~\cite{me07b}, we have found that a very simple learning
scheme (Naive Bayes) performs better than other standard data miners
for learning defect detectors. Prior to this paper, despite years of
effort, and despite experiments with a very large number data miners,
we have been unable to find a better predictor that this very simple
scheme.


After numerous unsuccessful attempts to do better that Naive Bayes,
we began to wonder if the problem was inherent to the data. In
particular, we hypothesized that static code features have {\em
  limited information content}. If so, then no algorithm would improve
over our existing results since our existing methods had exhausted the
information in our static code features.

This paper has offered much evidence for the limited information content hypothesis. After various reduction 
studies we found that the performance of our learners 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 the problem is limited  information content, then the solution is to increase that content. 

XXX to be precise, we did not break the balance performance ceiling. we redefined the problem and explored another performance criteria

% 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
%
\appendices
\section{Proof of the First Zonklar Equation}
Appendix one text goes here.

% you can choose not to have a title for an appendix
% if you want by leaving the argument blank
\section{}
Appendix two text goes here.

% use section* for acknowledgment
\section*{Acknowledgment}
% optional entry into table of contents (if used)
%\addcontentsline{toc}{section}{Acknowledgment}
The authors would like to thank... This work was supported by the IEEE.

% 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}
\appendix
\subsection{Naive Bayes Classifiers}
Bayesian classifiers
offers 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 feature's mean $\mu$ and standard deviation $\sigma$ is used in
a
Gaussian  probability
function~\cite{witten05}:
\[f(x) =
1/(\sqrt{2\pi}\sigma)e^{-\frac{(x-\mu)^2}{2\sigma^2}}\] 

Simple  Bayes classifiers are often called ``naive'' since they assume
independence of each feature. While this assumption
 simplifies the implementation  
(frequency
counts are required only for each feature),
 it is possible
that
correlated events are missed by this ``naive'' approach.
Potentially, this is a significant problem for our kinds of data sets where
the static code measures are highly correlated (e.g. the number of
symbols in a module increases linearly with module lines of code). 

In a previous work, we have investigated variants of Bayesian models considering this issue and observed that the independence assumption of naive Bayes is safe for the Nasa datasets~\cite{turhan07qsic}. Furthermore, 
Domingos and Pazzani show theoretically
that the independence assumption is a problem in a vanishingly small percent
of cases~\cite{domingos97optimality}. This explains the repeated
empirical result that, on average, seemingly naive Bayes classifiers perform as well
as other seemingly more sophisticated schemes (e.g. see Table~1 in~\cite{domingos97optimality}).

The Domingos and Pazzani result
also explains our prior experiments where naive 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}).


% biography section
%
% 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:

\subsection{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 simpliﬁes the data that fall into the diﬀerent 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 deﬁned for discrete 
class classiﬁcation 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 busy 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.

\subsection{The RIPPER Rule Learner}
RIPPER~\cite{cohen95r}  is a {\em rule-covering} covering algorithm that executes as follows.
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 removed from
the data set. The algorithm then recurses on the remaining data. 
The output is an ordered {\em decision list} of rules where $rule_j$ is only tested if
all conditions in $rule_{i<j}$ fail.
When applied to new data, RIPPER
returns the conclusion of the first rule with a satisfied
condition.

One way to visualize a covering algorithm is to
imagine the data as a table on a piece of paper. If there exists a clear pattern between the features
and the class,
define that pattern as a rule
and cross out all the rows covered by that rule.  
As covering
recursively explores the remaining data, it keeps splitting the data into:
\bi
\item
 what is easiest to explain, and
\item
 remaining ambiguities that require more  analysis.
\ei
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:
\bi
\item  {\em Pruning:}
After building a {\em rule}, RIPPER performs a back-select to see what parts of a {\em condition}
can be deleted, without degrading the performance of the rule.
Similarly,
after building a {\em set of rules}, RIPPER performs a back-select to see what {\em rules}
can be deleted, without degrading the performance of the rule set.
These back-selects remove features/rules that add little to the overall performance.
For example, back pruning could remove the residual rules.
\item {\em Description length:}
The learned rules are built while minimizing  their {\em description length}.
This is an information theoretic measure computed from the size of the learned rules,
as well as the rule errors. If a rule set is over-fitted, the error rate increases,
the description length grows, and RIPPER applies a rule set pruning operator.
\item
{\em Rule set optimization} 
tries
replacing rules
straw-man alternatives (i.e. rules grown very quickly by some
n\"aive method).
\ei


\subsection{The WHICH Rule Learner}
% There are many learners that generate a numeric summary of the training examples; e.g
% the Naive 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 $C$ and outputs a single rule that is best for maximizing $C$.
 
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 $C$. For example, if $C_{pd}$ is the probability of detection
(see \eq{pd} in \fig{measures}), then the condition $LOC==0$ has the score $C_{pd}=0$ (since all modules have at least one line of code).
Hence, according to $C_{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 top of 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 of ``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 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 the 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 achieve 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
satisfication 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 unexplored many 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 unused an unrestricted stack size.
\item
Currently, WHICH sorts new items  into the stack using a linear time search from 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 it 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 20. This may be an overly cautious setting.
 $Loop$ might be safely initialized to 20 and only increased if no dramatic improvement seen in the first loop.
For most domains, this would yield a ten-fold speed up of our current implementation.
\item
We showed above in \fig{acc} that WHICH2 performs poorly compared to other
accuracy-based learners. It would be interesting to explore WHICH variants that
offer better accuracy results.
\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}.


\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 just this guy, you know? Needs a beard and a Ph.D.\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} 
\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]{greg/greg}}]{Gregory Gay} 
is a graduating senior in the Lane Deparmtent 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{biographynophoto}{Yue Jiang}Biography text here.\end{biographynophoto}

\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}

% 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
\end{document}
