\documentclass{article}
\usepackage{url,times,graphicx}
\begin{document}
\small
\section*{Implications of High
Precision Detectors}

\begin{tabular}{ll}
Tim Menzies& \url{tim@menzies.us}\\
Alex Dehytar &\url{dekhtyar@cs.uky.edu}\\
Justin DiStefano & \url{justin@lostportal.net}\\  
Jeremy Greenwald &\url{jegreen@cs.pdx.edu}
\end{tabular}

~\\
Zhang\&Zhang (hereafter, the Zhangs) argue that such 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''.
In their view, ``a good prediction model should achieve high Recall
and high Precision'' (which we will denote as ``high precision\&recall'').

We disagree and this short note explains why. Nevertheless, we 
find their analysis is insightful and
necessary addition to our paper.
Zhangs' equation is simple enough to derive but, to the best
of our knowledge, it has not appeared previously (at least, not in the software
engineering literature).
As shown below, Zhangs' equation can explain several
prior empirical results found in the literature.
The insightful feature of Zhangs' equation is that it can use information about the problem at hand
to precisely characterized the pre-conditions
for high precision and high recall detectors. As far as we know, prior to Zhangs' equation, no
such characterization was possible. 

Achieving both high precision\& recall can be problematic.
Optimizing for one often compromises the other.
Fortunately, there are may situations (e.g. web searching, text
mining, defect detection) where low precision and high recall
detectors are useful.
For example,
\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, Dehytar, \& 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, to take an example from
outside SE, a user of commercial
web search engine like Goggle can quickly flick through (say) three
pages of results before finding a page of interest.  Goggle 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.  
\end{itemize} 

 \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).
    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}
Also, we have empirical reasons to to deemphasize precision.
At least for the NASA data we have studied previously,
it has proven to be a problematic way to assess
detectors. 
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.
Performance
measured for
$prec$ (precision), $acc$ (accuracy), $pd$ (recall),
$pf$ (false alarms)
were then collected and compared to baseline.
\end{itemize}
The mean and standard deviations of those performance
deltas are shown in Figure~\ref{fig:lmeansvs} (in that
figure, a zero value denotes
that the detector worked the same
on training and  test data).
Mostly, 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$. 

Figure~\ref{fig:lmeansvs} 
is the real reason that we do
did not
assess performance in terms of precision.
But this figure  was not offered in the DMP paper.
Hence,
the Zhangs' are right to complain about 
our selection of assessment criteria.

Turning now to the details of their equation,
let \{A,B,C,D\} denote the
true negatives, false negative, false positive, and true positive
(respectively) found by a binary detector. 
Certain standard measures can be computed from
$A,B,C,D$ such as  $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}$.
Another measure, important in
the sequel, is the ratio of negative to positive instances; i.e.
$neg/pos=\frac{A+C}{B+D}$.  All these values range zero to one.
Zhangs' equation is derived as follows:

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

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.
Zhangs' equation enables a more nuanced  selection process.
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 a precision of $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.


A detail not explored by the Zhangs
is that many industrial problems have ``small targets'', i.e.
large $neg/pos$ ratios. E.g.:
\begin{itemize}
\item
In the data processed by DMP, the smallest of these ratios was 1.04, and the others were
7.33,
9,
10.11,
13.29,
15.67, and
249.
\item
Hayes, Dekhtyar, \& Sundaram use text mining to find pairs of connected requirements
 in a corpus of 220 requirements and 235 design elements~\cite{hayes06}.
Each sentence of each document can refer to itself, or any of the other documents; i.e. $220*235=51,700$ possible links.
Using other knowledge, that team asserted that on 361 of those links were valid;
i.e.
$neg/pos=51,700/361= 143.2$.
\item
Finally, for an extreme example, Goggle 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$. 
\end{itemize}


As $neg/pos$ increases, 
high recall\&precision
is only possible when $pf$ becomes vanishingly small.
The left-hand-side of Figure~\ref{pprnp}
graphs Equation~\ref{one} for the  sample of the DMP $neg/pos$ ratios.
\begin{figure}[!t]
\begin{tabular}{|c|c|}\hline
\includegraphics[width=3in]{y_0.pdf}&\includegraphics[width=3in]{y_05.pdf}\\\hline
\end{tabular}
\caption{The relationship between
$pd, prec, recall$ and $neg/pos$. Right-hand-side plot just shows the
region in the left-hand plot where $prec>0.5$.
}\label{pprnp}
\end{figure}
The right-hand-side of Figure~\ref{pprnp} 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$
corresponds to very small false alarm ($pf$) rates.
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}

\noindent
Zhangs' equation
explains certain prior results
seen in the literature:
\begin{itemize}
\item
The equation explains {\em both}
 the instability of precision {\em and} the stability of $pf$ and $pd$ (recall) 
seen 
in 
Figure~\ref{fig:lmeansvs}.
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).
The other measures in
Figure~\ref{pprnp}, on the other hand, change far more smoothly and slowly.
\item
Detectors learned in the domain of
software engineering
rarely yield
high precision detectors (see Figure~\ref{precs}).
Using Zhangs' equations, the reasons for this are very clear:
(1)~those detectors all try to maximize recall; (2)~Figure~\ref{pprnp} shows that such 
detectors can only achieve high precision in the rare case of very low $pf$.
\end{itemize}
\begin{figure}
\small
\begin{center}
\begin{tabular}{|p{4.5in}|}\hline
\begin{itemize}
\item
The DMP paper achieved recalls over 70\% and
minimum false alarm rates of 15\%.
Using 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, Dehytar, and Sundaram 
exhibited $pf>0.6$ (hence, very low precisions)~\cite{hayes06}.
\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.
\end{itemize}\\\hline
\end{tabular}
\end{center}
\caption{Some low precisions seen in the SE literature.}\label{precs}
\end{figure}

Just because high precision\&recall detectors have not been seen before in SE
does not mean that this goal is impossible.
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.

One way forward might be to change the $neg/pos$ ratio 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
raining set contains $neg/pos=1$, the test set still has the original distributions.
In any case, this area is ripe for further exploration. 

Another avenue for exploration is to explore augmented automatic learning with some user modeling.
Hayes, Dehytar, \& Sundaram~\cite{hayes06} iteratively refine their learned detectors, transforming
low precision detectors into high precision detectors. In one case study, the reached precisions and
recalls over 0.85 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.




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

