# Estimating bounds on false positives rate

I would like to estimate bounds on the false positive rates of a binary classifier. In my sample data I have 50% positive data points, and 50% negative data points. However, in the real data, which I don't have access to, I can estimate that there are going to be $N$ positive samples and $N^2$ negative samples, where $N$ is large, in the order of millions. Since I am looking for a needle of size $N$ in a haystack $N^2$, it is very important that my false positive rate remains as close to zero as possible.

I have 40 thousand positive samples and 40 thousand negative samples. Up until recall 0.8, I have a false positive rate of 0. I would like to use this to estimate the real false positive rate. I can model the false positive rate as a probability of labeling a Negative sample as Positive. Let's call this $P_{np}$ (for negative -> positive). I don't know its true value, but I do know that after labeling 0.8*40000 I have 0 false positives. The number of false positives, depends on the value of $P_{np}$ and should be binomially distributed. Assuming this is true, I can estimate a confidence interval around my empirical estimation of $P_{np}$. Does this make sense? Can you point me to relevant work in the literature?

-
Your false positive rate is going to depend on many factors. We need to know more about your model / binary classifier at a minimum. In the interim, (w/o meaning to sound snarky) the way to insure that you don't have any false positives is to classify all cases as negative. –  gung Aug 14 '12 at 1:21
You are right. I gave some indication about my classifier's accuracy, it has 0 false positives up until 80% recall. It's a Naive Bayes binary classifier, but I don't think that's relevant for the estimation. But I might be wrong. My main concern is that, even though the classifier seems to perform great, I am looking for a needle in a haystack and therefore will fall in the base-rate fallacy if I am not careful. My false positive rate seems to be very close to 0, but I cannot really measure it with my small sample, therefore I need to estimate bounds. –  Dan Aug 17 '12 at 17:25

Call your false positive rate p, the actual negative rate in your sample r, and n the number of trials without coming across a false positive. Clearly for your confidence interval, given you've observed no false positives so far, the lowest bound (and indeed the maximum likelihood estimate) is zero. For the higher bound, you can think "what is the value of p for which there is $\alpha$ probability of getting 0 failures out of my n trials? Higher values of p are not in your $1-\alpha%$ confidence interval.

The probability of a false positive for any one draw in your sample experiment is $p\times{r}$.

So solve $\alpha=(1-pr)^n$

and you get $p=\frac{1-e^{\frac{log(\alpha)}{n}}}{r}$

With your n=32000 and r=.5 (if I understand your question correctly) this suggests the upper bound of a 95% confidence interval for false positives is 0.0001872245.

-
I have found an article with a comparison of various techniques to estimate bounds on false positive and false negative rates. Here is is archive.nyu.edu/bitstream/2451/27802/2/CPP-07-04.pdf. –  Dan Aug 15 '12 at 20:02
does it say anything about my proposed method? (which only works when you have a sequence with no false negatives) –  Peter Ellis Aug 15 '12 at 22:51
Yes. Your method was the one I had in mind as well when I asked the question. In my estimation, I used Wilson's intervals to estimate the bounds are the false positive rate. This is part of a class of methods that consider false positive and false negative rates as two independent values that can be estimated with methods such as yours. There is another class of methods though that tries to estimate FPR and FNR bounds together. It's an interesting read. –  Dan Aug 17 '12 at 17:10
{1+ n/F$_ ($$_1$$_-$$_α$$_;$$_2$$_,$$_2$$_n$$_)}^-$$^1$.