3
$\begingroup$

Given that I have an algorithm that classifies data points as 'true' or 'false'. and I want to estimate its FPR, FNR. It is not a supervised model where I start with a large training set of labeled data, so I thought of getting a sample data set and labeling it manually. Labeling is very laborious, so I want the sample set to be as small as possible, what is the formula to calculate the sample size (and obviously, what parameters will it require)?

In particular, I don't have a good estimate about the real ratio of 'true' vs. 'false' in the real world.

Are there better measures than FPR / FNR in such a case?

$\endgroup$
2
  • 1
    $\begingroup$ Unclear to me - If you dont have labeled data points how do you expect to estimate FPR and FNR?. $\endgroup$
    – yoav_aaa
    Jan 2, 2018 at 14:09
  • 1
    $\begingroup$ I don't have a large set of labeled data points, but I can sample and label manually. I'll clarify $\endgroup$
    – IttayD
    Jan 2, 2018 at 14:15

2 Answers 2

2
$\begingroup$

There are some pretty simple formula you can use, based on the following assumptions.

1) you are taking a random sample of the population to get your sample

2) you want to estimate the FPR and the FNR for the population you are sampling from

3) you are happy to assume your "manual labelling" as the truth. ie you want the algorithm to replicate what manual labelling would do.

4) your algorithm is already trained, and you do not need to estimate or tune any parameters with the sample

Under the above assumptions, you can conceptualise your problem as the typical "draw $n$ balls from an urn with $N$ balls". There are four types of balls - TP, TN, FP, FN. You find out which type by sampling, giving you $n_{TP},n_{TN},n_{FP},n_{FN}$. You want to estimate the population equivalents, $N_{TP},N_{TN},N_{FP},N_{FN}$ , or functions of these.

There are lots of easy to find resources for sample size calculators for the above problem. I will go through some calculations for estimating $FPR=\frac{N_{FP}}{N_{FP}+N_{TN}}$.

An intuitive estimate for FPR is the corresponding sample equivalent, or

$$\hat{FPR}=\frac{n_{FP}}{n_{FP}+n_{TN}}$$

This is generally what most estimates will be close to, provided the sample size of "positives" are large. The variance associated with this estimate will generally be of the form:

$$var\left(\hat{FPR}\right)\approx \frac{FPR(1-FPR)}{nQ}$$

Where $Q=\frac{N_{FP}+N_{TN}}{N}$ is the proportion of the population classified as negative by manual labelling. If we want a certain level of accuracy, such as $var\left(\hat{FPR}\right)<\alpha$ we can turn this into an inequality for $n$

$$n\geq \frac{FPR(1-FPR)}{\alpha Q}$$

This reveals some intuitive relationships. Of course if you want more accuracy, $\alpha$ goes down, and $n$ goes up as expected. The accuracy depends on the population FPR. If it is close to 1 or close to 0 then your estimated value is more accurate - you will find out pretty quickly if the positives are always right or always wrong. It is maximised when FPR=0.5, so you can use this value as a conservative choice for setting the sample size when you have no idea what a reasonable value might be. The quantity $nQ$ is the expected number of negatives in the sample from manual labelling. If $Q\approx 0$ then you will need a large sample to find any negatives.

A similar formula can be obtained for the FNR, and by taking the maximum of the two bounds we have

$$n\geq \max\left[\frac{FPR(1-FPR)}{\alpha_{FPR} Q},\frac{FNR(1-FNR)}{\alpha_{FNR} (1-Q)}\right]$$

Where $\alpha_{FNR}$ is the accuracy you want for estimated FNR and $\alpha_{FPR}$ is the accuracy you want for estimated FPR. Note the term $1-Q$ is the proportion of "positives" manually labelled in the population.

Unfortunately, you will need to do some guessing, particularly for the value $Q$ as there is no upper bound to use. One option would be to use the first few samples to get a rough estimate for $Q$ (maybe 10? not sure what sort of scale you're working on) and then use that to decide how many more samples to take after that.

You may also find it difficult to specify the variance constraints - just how accurate an estimate do you want? not always something people think about. What the above formula does give you is a quantification of trade offs. You may find it easier to specify the standard error or confidence interval length first, then work backwards to get the variance constraint.

Hopefully this helps!

$\endgroup$
1
$\begingroup$

As I understand it, your question is consisted of two smaller questions:

  1. What is the needed sample size to evaluate my classification model(algorithm)?
  2. How do I select my evaluation(labeled) data in a manner that reduce selection bias(so my evaluation reflects real world performance)?

The first question is strongly related to the "samples per features" question.
Where the logic behind answering it is a function of your algorithm complexity. The more complex (more features/variables it uses) the more samples you need. There are many discussions around this topic with no clear cut rule of thumb arising.
A quick search led to these related questions on this topic:
How large a training set is needed?
Number of features vs. number of observations

Answering the second question. First, assure the whole of your data represents the real world (if not, then you need to get more data, or find ways extrapolating the results).
Under the assumption that it is representative, select a subset from the data (with size determined in previous step) that have the same characteristics as the full data set.
You can measure this similarity using goodness-of-fit measure - The Kolomogorov-Smirnov test is widely used.
And this article(section 2.3) is a good reading about this "training" subset selection process.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.