%\documentclass[onecolumn,12pt,draftcls,journal,compsoc]{IEEEtran}
\documentclass[9pt,journal,compsoc]{IEEEtran}

\usepackage{times}
\usepackage{alltt}
\usepackage{graphicx}
\usepackage{url}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
% IEEE Computer Society needs nocompress option
% requires cite.sty v4.0 or later (November 2003)
\usepackage[nocompress]{cite}
% normal IEEE
 % \usepackage{cite}

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

\begin{document}

\title{Problems with Precision}

\author{Tim~Menzies,~\IEEEmembership{Member,~IEEE,}
        Alex~Dekhtyar,
		Justin~Distefano,
        and~Jeremy~Greenwald
\thanks{ 
~\newline
\protect\url{tim@menzies.us} (LCSEE, WVU) \newline
\protect\url{dekhtyar@cs.uky.edu} (CS, UK) \newline 
\protect\url{jdistefano@ismwv.com} (Integrated Software Metrics)\newline
\protect\url{jgreen@cs.pdx.edu} (CS, PDX)\newline 
See \protect\url{http://menzies.us/pdf/07precision.pdf} for an earlier draft of this paper.
Manuscript received Feburary 21, 2007; revised March  11, 2007.}}

\markboth{Journal of ???,~Vol.~6, No.~1, January~2007}%
{Menzies \MakeLowercase{\textit{et al.}}: Open Issues With High Precision
Detectors }

\maketitle


%------------------------------------------------------------------------- 

\section{Introduction}


Zhang\&Zhang~\cite{zhang07} (hereafter, the Zhangs) argue that the low precision
detectors seen in Menzies, Greenwald, and Frank's paper {\em Data
Mining Static Code Attributes to Learn Defect Predictors}~\cite{me07b}
(hereafter, DMP) are ``not satisfactory for practical purposes''.
They demand that  ``a good prediction model should achieve both high Recall
and high Precision'' (which we will denote as ``high precision\&recall'').
All other detectors, they argue, ``may lead to impractical prediction models''. 

We have a different view and this short note explains why.   
While we disagree with the Zhangs' conclusions,
we find that their derived equation is
an important result.
The insightful feature of the {\em Zhangs' equation}
is that it can use information about the problem at hand
to characterize the pre-conditions
for high precision and high recall detectors. 
To the best
of our knowledge, no such characterization has been
previously reported (at least, not in the software
engineering literature).

\section{Precision Instability}
{\em Precision instability}
is the real reason that we do
not
assess performance in terms of precision.
But precision instability was not discussed  in the DMP paper.
Hence,
the Zhangs' are right to complain about 
our selection of assessment criteria.



 \begin{figure*}[!t]
    \begin{center}
    \includegraphics[width=5in]{lmeansv.pdf}
    \end{center}
    \caption{Mean $\mu$ and standard deviation $\sigma$
    of changes in defect detector statistics between
a baseline (tested on the training set) and another data set
(tested on different data).
A zero value denotes
that the detector worked the same
on training and  test data.
    Dots
    denote mean ($\mu$) values.
    Whiskers extend from $\mu + \sigma$ to $\mu-\sigma$.
The data sets used in this
study had some overlap with the DMP
data; i.e. $cm1, kc1, kc2, jm1, pc$.  From~\protect\cite{me03q}.
}
    \label{fig:lmeansvs}
    \end{figure*}

We first detected precision instability
in several NASA data sets.
If a researcher
wants to demonstrate that detector generator 
$A$ is better than method $B$, then they must measure the performance
of $A$ and $B$, under a variety of
treatments.
Figure~\ref{fig:lmeansvs} shows one such study~\cite{me03q} where
different learners (e.g. M5', J48, ROCKY, LSR)
were:
\begin{itemize} 
\item
{\em Trained} on one of five data sets;
\item
{\em Self-applied} on the same training set (to generate a baseline
performance measure);
\item
Then {\em tested}
on each of the other four data sets.
\end{itemize}
The results are shown in
Figure~\ref{fig:lmeansvs}.
On most performance measures,
the detectors were remarkably stable and  similar performances
were
observed in different data sets.
The exception was $prec$ (precision) 
which had very large standard deviations when applied to different data sets.
Hence, if detectors were to be assessed in terms of precision,
it would be very difficult to show that method $A$ was better
than $B$. 

Another problem with precision instability is maintainability.
It is                                                                       
important to stabilize a project's defect detectors so that they remain                                                                          
viable after release. For example, no project manager wants to discover
that
their 80\% precise detector is only 25\% precise when a project update is                                                                     
pushed out 3 months later. 

We show below that the Zhangs' equation can explain 
precision instability, as well as certain other
prior empirical results.


\section{The Mathematics of Precision}

Let $\{A,B,C,D\}$ denote the
true negatives, 
false negatives, 
false positives, and 
true positives
(respectively) found by a binary detector. 
Certain standard measures can be computed from
$A,B,C,D$: 
\[
\begin{array}{ll}
pd=recall=&\frac{D}{B+D}\\
pf=&\frac{C}{A+C}\\
prec=precision=&\frac{D}{D+C}\\
acc=accuracy=&\frac{A+D}{A+B+C+D}\\
selectivity=&\frac{C+D}{A+B+C+D}\\
neg/pos=&\frac{A+C}{B+D}
\end{array}
\]
The last measure ($neg/pos$) is most important to the subsequent discussion.
The Zhangs' equation is derived as follows:

\begin{equation}\label{one}
prec = \frac{D}{D+C} = \frac{1}{1+ \frac{C}{D}} = \frac{1}{1 + neg/pos \cdot pf/recall}
\end{equation}
which can be rearranged to
\begin{equation}\label{two}
pf = \frac{pos}{neg}\cdot\frac{ (1 -  prec) }{ prec}\cdot recall
\end{equation}

Note that, in Equation~\ref{two}, when $recall$ is fixed then
false alarm rate becomes controlled by precision and a 
fixed constant determined by the data set being examined; i.e.
when ($\alpha=neg/pos$) and \mbox{$recall=1$}
then:
\begin{equation}\label{three}
pf = \alpha\cdot \frac{1-prec}{prec}
\end{equation}
From Equation~\ref{three}, it is clear that for any targeted recall value,
{\em increasing} 
precision requires
{\em decreasing}
false alarm rates; e.g. for \mbox{$prec\in\{0.5,0.70,0.9,0.95\}$}, $pf$ becomes $\{1,0.43, 0.11, 0.005\}$,
respectively. The effect is particularly marked for data sets
with large $neg/pos$ ratios
(e.g. like the data processed by DMP).
\section{Large $Neg/Pos$ Ratios}

A detail not explored by the Zhangs is that many software engineering data sets have extremely
large
$neg/pos$ ratios.
%Elsewhere~\cite{me03a,me03q}\footnote{See also the PREDICTIVE toolkit~  \url{http://www.ismwv.com/}},
%we have conducted extensive studies
%on methods for  generating and selecting detectors appropriate to different business contexts.
%The Zhangs' equation enables a more nuanced  selection process.
For example:
\bi
\item In the DMP paper, the data sets studied
had $neg/pos$ ratios
of
1.04, 
7.33,
9,
10.11,
13.29,
15.67, and
249.
\item
  Hayes, Dekhtyar and Sundaram \cite{hayes06} use text mining to                                                                     
find pairs of connected requirements in a corpus of 220 requirements and                                                                     
235 design elements (the same CM-1 dataset used in 
\cite{me07b}).
The total number of possible links in the dataset is $220\cdot 235 =                                                                        
51,700$, while the the ground truth RTM contains 361 links, for the                                                                         
$neg/pos$ ratio of $51,700/361 = 143.2$.   
\item
For an extreme example, Google reports that
over $10^{9}$ web pages contain the phrase ``software''
but only one them is the home page of this journal. Hence, $neg/pos$ for
web searching is at least $10^9$. 
\ei
%For example, consider the  the mission critical situation requiring $recall=1$.
%Equation~\ref{two}
%shows that when $prec=0.25$ and
%$neg=500$ and $pos=100$, achieving the goal of $recall=1$ requires
%a detector with  $pf=0.6$.
%As precision increases, detectors become harder and harder to
%design. For example, continuing the security example,
%at $recall=1$ and $neg/pos=5$,
%increasing the precision 
%0.25 to
%0.5 to 0.75 requires detectors with
%false alarm rates of 0.6 to  0.2 to 0.067 (respectively).
%As discussed below, building high precision detectors
%can be expensive.
%Depending on the available research budget, companies
%might elect to use lower precision detectors that are cheaper to build.
%
%experiments - some minor changes in formulas may affect the exact numbers,
%but not the ballparks), our pf for CM-1 dataset, without filtering,
%feeback, or any other tricks, is probably around 60-65% (we retrieve
%around 33,000 links outright, out of 51700 possible). Only with filtering
%(either by absolute value, or by relative rank) can we get to pf of 0.1 or
%better with decent recall.
%MGF report probability of detection and false alarm rates of
%of \{pd=75\%, pf=25\%\}, respectively. MGF argue that these are high enough to be useful.
%However,  Zhang\&Zhang derive an expression that can compute precision from the data found
%in MGF. Those computed  precisions suggest that the MGF results are  quite useless:
%\[
%\{min,median,max\}=\{2\% 20\%, 70\%\}
%\]
%
%Here, we show that Zhang\&Zhang
%do not take their conclusions far enough. 
%A large number of current industrial problems can be characterized by ``small targets'' and
%``some false alarms''  (quoted terms are defined below).
%Using the expression derived by Zhang\&Zhang, we show that all such domains are prone to
%the problem of low precision.
%However, unlike Zhang\&Zhang, we will argue that low precisions are acceptable in some
%of those domains.
%Also, unlike Zhang\&Zhang, we also will offer a specific research direction 
%on how to improve the MGF results. Interestingly, that research direction
%{\em requires} accepting low precision detectors, at least initially.

Figure~\ref{pprnp}
graphs Equation~\ref{one} for the  DMP $neg/pos$ ratios.
\begin{figure}
\begin{center}
\includegraphics[width=3in]{y_0.pdf}
\end{center}
\caption{The relationship between
$pd, prec, recall$ and $neg/pos$. 
}\label{pprnp}
\end{figure}
\begin{figure}
\begin{center}
\includegraphics[width=3in]{y_05.pdf}
\end{center}
\caption{
Figure~\ref{pprnp},
cropped to the region
where $prec>0.5$.
}\label{pprnp1}
\end{figure}
Figure~\ref{pprnp1} does the same, 
but is restricted to zones of higher precision:
only the surface for
$0.5\le prec \le 1$ is shown. 
That shadow of the  surface on the bottom plane
shows that this zone of high precision, high recall, and large
$neg/pos$.
As $neg/pos$ increases, 
high recall\&precision
is only possible when $pf$ becomes vanishingly small.
For example, in the ranges 
\mbox{$0.65 \le prec,recall \le 0.8$}, 
Equation~\ref{two} reports that $pf$ falls into the following ranges:
\begin{itemize}
\item  $0.023 \le pf \le 0.062$  for $neg/pos = 7$;
\item  $0.0108 \le pf \le 0.0287$ for $neg/pos = 15$;
\item  $0.007 \le pf \le  0.0017$ for $neg/pos = 250$;
\end{itemize}
Detectors learned in the domain of
software engineering
rarely yield
high precision detectors (see Figure~\ref{precs}).
Using the Zhangs' equations, the reasons for this are very clear:
\bi
\item
Those detectors all try to maximize recall; 
\item
Figure~\ref{pprnp} shows that such 
detectors can only achieve high precision in the rare case of very low $pf$.
\ei

Not only do the Zhangs' equation explain the Figure~\ref{precs} results,
they also inform the 
 the instability of precision {\em and} the stability of $pf$ and $pd$ (recall) 
seen 
in 
Figure~\ref{fig:lmeansvs}:
\bi
\item
Note how, in Figure~\ref{pprnp},
that at very small $pf$ values,
tiny changes in $pf$ can lead to very large changes in $prec$ 
(sudden jumps from zero to one).
\item
The other measures in
Figure~\ref{pprnp}, on the other hand, change far more smoothly and slowly.
\ei
That is, the Zhangs' equation is the essential theoretical statement
needed to explain numerous prior results such as those shown in Figure~\ref{precs} 
(i.e. \cite{me03q,me07b,huan06,hayes06,antoniol02,antoniol05,marcus03}).
\begin{figure}[!b]
\small
\begin{center}
\begin{tabular}{|p{0.95\linewidth}|}\hline
\bi
\item
The DMP paper achieved recalls over 70\% and minimum false alarm
rates of 15\%.  Using the Zhangs' equation and data from DMP, it
can be shown that the DMP precisions were quite low:
$\{min,median,max\}=\{2\% 20\%, 70\%\}$ (the last number came from
a data set with $neg/pos\approx 1$).
\item
Huang et.al.~\cite{huan06} won ``best paper'' at the 2006 IEEE
Requirements Engineering conference with detectors exhibiting
$prec\approx 0.25$.
\item
Without extensive feedback from human experts, the classifiers used
by Hayes, Dekhtyar, and Sundaram exhibited $pf>0.6$ (hence, very
low precisions)~\cite{hayes06}.
\item
Other such as Antoniol et.al.~\cite{antoniol02,antoniol05} and
Marcus et.al.~\cite{marcus03} researchers into software tracability
report that high recall is achievable only with low precision
detectors.  Antoniol has also been exploring bug traces in Mozilla
components and has found the same high-precision, low-recall
trade-off.
\item
After much experiments with linear regression, model tree learners,
Bayes classifiers, decision tree learners, singleton rule learners,
and some home-brew learners~\cite{me03q}, the general trend is very
clear. For those learners, executing on the DMP datasets, $pf \le
pd - 0.5$; That is, for those learners and those data sets, obtaining
high recall figures of $pd>0.6$ implies $pf>0.1$ and, consequently,
low precision.
\ei  
\\\hline \end{tabular} \end{center} 
\caption{Some
low precisions seen in the SE literature.}\label{precs} 
\end{figure}

\section{When Low Precision is Useful}

Achieving both high precision\& recall can be problematic.
As shown by Zhangs' equation,
optimizing for one often compromises the other (especially for data sets with large $neg/pos$ ratios).
Fortunately, there are may industrial
situations 
where low precision and high recall
detectors are useful.
For example, one of us (DiStefano) has used
our low-precision detectors to review flight code
developed at
the NASA Glenn Research Center (Ohio, USA).
When the results of these detectors were presented to the lead flight
engineer, he confirmed that the identified sections (which did not
have any recorded defects) had been problematic to maintain, and
contained several bugs which had not yet been entered into the
defect system. 


For another example,
from
outside the field of SE, 
a user of commercial
web search engine like Google can quickly flick through (say) three
pages of results before finding a page of interest.  Google has so
many return customers since even with precisions of (say) $\frac{1}{30}$,
the effort involved in looking at a page is so low that users don't
mind examining 29 false alarms.  

More generally, there are several situations where low precision
detectors are useful:
\begin{itemize}
\item
{\em When the cost of missing the target is prohibitively expensive.}
In mission critical or security  applications, the goal of
100\% recall may be
demanded in all situations, regardless of the  precision.
\item {\em When only a small  fraction
the data
is returned.}
Hayes, Dekhytar, \& Sundaram call this fraction
$selectivity$ and offer an extensive discussion of the merits of
this measure~\cite{hayes06}.  \item {\em When there is little or no cost in checking
false alarms.}  For example,  a detector we have found useful in industrial settings is to
check modules  where \[\frac{lines\; of\; comments}{lines\; of\; code} > 0.25\]
This detector triggers on complex functions that 
programmers comment extensively, instead of splitting up into smaller, more maintainable,
functions.
This detector is imprecise- it often triggers on well-written
functions with detailed comments. 
However, based on commercial experience, we assert
that it is fast and simple for
a human agent to inspect  the identified modules and discern which                                                                    
ones were well-written and which were over-commented to disguise being                                                                      
badly coded.
We use this detector to find code that should be rewritten prior to release.
\end{itemize} 

\section{Research Directions}

Just because high precision\&recall detectors have not been seen
before in SE does not mean that this goal is impossible.  If large
$neg/pos$ ratios are the problem, then perhaps the solution is to
change those ratios in the training data.  In ``oversampling'', the
minority class ($pos$) is repeated multiple times. In ``under-sampling'',
some portion of the  majority class ($neg$) is discarded. In this
way, a training data set with $neg/pos=1$ might be generated.
Figure~\ref{pprnp} shows that the space of $neg/pos=1$ detectors
 contains many candidates with both high precision\&recall.
However, while a promising technique, there is contradictory evidence
for its value.  Yiu reports that the appropriate re-sampling technique
and appropriate classifier is dataset dependent~\cite{yun04}.  In
limited studies with one learner and a few data sets, Drummond \&
Holte~\cite{drummond03} found that oversampling had little value.
They offer some evidence for the value of under-sampling but concluded
that other methods can do better.  One issue is that while re-sampling
yields training set contains $neg/pos=1$, the test set still has
the original distributions.  In any case, this area is ripe for
further exploration.  

Another promising direction might be to try boosting.  The AdaBoost
algorithm~\cite{FreSch97} builds an ensemble of detectors 1,2,3,...
where detector $i$ is built from problems that were misclassified
by detectors $1,2,..,i-1$.  AdaBoost defines a voting procedure for
making conclusions after passing all new test instances to every
member of the ensemble.  It can be shown that increasing the size
of the ensemble decreases error~\cite{FreSch97}. That is, the goal
of both high precision\&recall might be achievable using boosting.
Curiously, to do so, we require using detectors that generates
enough false alarms to inform the boosting.

The theoretical advantage of boosting has yet to show significant
improvements in real-world defect data sets (see the modest
improvements of \cite{khos02z} or the poor comparative performance
of AdaBoost compared to other methods in~\cite[p64-77]{ma07}).
Therefore, to address the Zhangs' challenge of high precision\&recall,
we need to look for other techniques.

Yet another avenue to explore is {\em stacking}; i.e. levering the strengths and weaknesses
of  different learners in an assembly that does better than any single learner.
For example, Gaddam et.al. achieved high precision\&recall
in one data set by combining clustering with decision tree learning. However,
stacking is a poorly understood area and the behavior of the resulting
assembly is difficult to predict. 
Gaddam et.al.'s toolkit only reached high precision\&recall in one
dataset; in several others, it could not~\cite{gaddam07}.

Our final suggestion for how to achieve the Zhangs' goal  is to
augment automatic learning with some user modeling.  Starting with
unsupervised learners, it is possible to give learners information
about the top candidate conclusions. A feedback loop can then be
entered as a kind of as iterative supervised learning (results from
generation $i$ inform and improve the results at generation $i+1$).
This methodology leads to two different things you can measure:
(1)~the recall/precision of the {\em current} output, or (2)~the
recall/precision of the list of candidate conclusions  used for
learning {\em during multiple iterations}:  \bi \item In ~\cite{hayes06},
the former is measured and Hayes, Dekhytar, \& Sundaram iteratively
refine their learned detectors, transforming low precision detectors
into high precision detectors. In one case study, the reached
precisions and recalls increased over 0.85 (in the $current$ output)
after five rounds of users reviewing and commenting on the learned
detectors.  The challenge with this method is that is requires
extensive involvement by knowledgeable users- and such users can
be a scarce and expensive resource. Researchers exploring this
approach must balance the benefits of high precision\&recall detectors
against their high construction cost.  \item 
In subsequent
work~\cite{dekhtyar07}, Hayes and Dekhytar measured the recall/precision of the
candidates used {\em during multiple iterations}. They found that
they were still faced with the  same low precision-high recall
trade-off; e.g., to have seen 90\% of the correct candidates, we
had to go through a list whose precision is about 20\%.  \ei 
In summary, while the above techniques show promise,
it may take much further research to 
achieve 
high precision\&recall detectors in software engineering data sets
with large $neg/pos$ ratios.

\section{Conclusion}
The Zhangs argue that predictors
are useless {\em unless} they  have high precison\&recall.
We have a different view, for two reasons.
Firstly, for
SE data sets with large $neg/pos$ ratios, 
it is often required to lower precision to achieve higher recall.
Secondly, there are many domains where low precision detectors are useful.

Nevertheless, there is much value in Zhangs' equation.
It is  
a useful result
that 
explains numerous prior results such as~\cite{me03q,me07b,huan06,hayes06,antoniol02,antoniol05,marcus03}.
The Zhangs' equation also explains why
precision is much less stable than other measures. 
Hence, 
researchers are advised {\em } not to use precision
when assessing
their detectors. Other measures are more stable (i.e. recall ($pd$) and false alarm rates),
especially for data sets with large $neg/pos$ ratios.


%Two different categories of re-sampling methods commonly used to overcome the 
%problem of imbalanced data.  The first increases the frequency of the minority class in 
%the training set (Oversampling) and the other decreases the frequency of the majority 
%class in the training set (Undersampling) (Weiss and Provost 2001; Drummond and 
%Holte 2003).
%Drummond, C. and R. C. Holte (2003). C4.5, class imbalance, and cost sensitivity: why 
%under-sampling beats over-sampling. Workshop on Learning from Imbalanced 
%Datasets II. 

%In this paper, we used cost curves to explore the in- 
%teraction of over and under-sampling on the decision 
%tree learner C4.5. Surprisingly, over-sampling is in- 
%effective, at least when the default settings are used, 
%often producing little or no change in performance. 
%Under-sampling does produce a reasonable sensitivity 
%to changes in misclassification costs and class distri- 
%bution. But representing these changes internally by 
%down-weighting gives the best performance overall. 

%~\cite{yun04}

\bibliographystyle{plain}
\bibliography{refs}
\end{document}


\bibliographystyle{IEEEtran}
\bibliography{refs}

%------------------------------------------------------------------------- 

\end{document}

