# Determining sample size for ML algorithm validation

I'm looking to do a third-party assessment of the false-positive rate of a video classification algorithm. Since I have a lot of video I'm trying to do a power analysis to figure out exactly how much video I need to look through so that it is representative of all the video data at a given confidence interval.

The algorithm flags video sequences that have at least one cat in it, and I'm looking to evaluate the frequency of false positives on a new unlabeled test set. So I have tagged all the video that my algorithm has identified a cat in and now want to sample the tagged video sections and look through them manually to validate my model since looking through all of it would take too long! Note, I'm not looking to refine the model at this point, just assess it.

My null hypothesis is that the FP rate of the sample of video I watch is equal to the FP rate of all the video.

I think I can use this formula to determine the number of video sequences to view:

Here is my question: am I thinking through this formulation correctly? Since my model has a CV false positive rate of ~0.96, I figure I can use that as a reference. Can I use that for the null hypothesis proportion, p0? Or will that be p, the true proportion?

I've been using this online calculator: http://powerandsamplesize.com/Calculators/Other/1-Sample-Binomial

I ask because when setting the parameters I have, I'm getting very small sample sizes, like less than 10 sequences to view. That can't be right.

• does 0.96 mean 96 out of 100 (96%), or 96 out of 10000 (0.96%)? – probabilityislogic Jan 21 '20 at 4:22
• yes, 96% sorry for the confusion – Zafar Jan 22 '20 at 0:07
• this sounds like a really bad model for classifying cat videos - for every 4 correct identifications it gives you 96 wrong ones! – probabilityislogic Jan 22 '20 at 1:39

Sample size calculation is a statistical consideration to determine the precision and power of a particular analysis where data comprise a random sample.

Validation (of an algorithm) involves testing performance under a variety of non-random scenarios, and describing any deficiencies or updating the algorithm as needed. The number of scenarios is determined by the scope of the algorithm.

If you randomly sample a bunch of videos and want to run your algorithm to estimate the proportion of cats in each video, that is a statistical analysis. The proportion $$p$$ is a useless quantity, because the videos comprise a convenience sample and you lack a gold standard. The test is even more useless because you don't actually have a hypothesis.

A gold standard means a viewer carefully watches the video and declares whether or not it has a cat in it.

If you want to describe the interrater agreement, use a test of Cohen's Kappa. This will give a powerful test for how often the algorithm agrees with the viewer, independent of the actual baseline frequency of cats.

• here the null hypothesis is: the rate of video sequences containing cats in the population is equal to the rate of video sequences containing cats in the sample. The "gold standard" that you speak of is exactly what I'm trying to do here, I want to carefully watch a sample of the videos (hopefully not all of them) and extrapolate my results at a 95% type I error to the population. Any ideas? – Zafar Jun 5 '19 at 19:00
• @Zafar that is calibration only. Calibration alone does not a good classifier make. – AdamO Jun 5 '19 at 19:15
• I definitely appreciate the expert advice here. For the example I posted, which is a simplification of my actual problem, let's take the classifier as final. I'm simply trying to assess the false positive rate using new video data. Think of it as a third-part verification of the FP rate. Is the method that I laid out above misguided? – Zafar Jun 5 '19 at 20:20
• My goal is to be able to say, "looking at a sample of the video, the FP rate is x given a confidence/precision of y". – Zafar Jun 6 '19 at 2:34

Your analysis appears very similar structurally to counting votes after an election. Often, the result is "called" well before all the votes are counted. You appear to want to do something similar here, such as declare the population proportion is larger than the some number $$p_{pop}>p_0$$ for some "quality threshold" $$p_0$$.

If we assume that you are taking a simple random sample of the newly classified "contains a cat" videos (e.g. randomly sort the videos before you select the ones to be in your sample), then you are in the classic "urn with blue and red balls" scenario, and you want to estimate the proportion of red balls in the urn. The FP rate (call this $$r$$) found in the sample of $$n$$ videos (from population size $$N$$ videos) will have a hypergeometric distribution "divided by $$n$$" with a mean and standard deviation

$$E(r)=p_{pop}$$ $$SD(r)=\sqrt{\left(1-\frac{n}{N}\right)\frac{p_{pop}(1-p_{pop})}{n}}$$

The calculator applies a normal approximation for $$r$$ to give the formula for $$n$$. It also assumes $$\frac{n}{N}\approx 0$$

Your sample size required is small because your proportion is very close to 1; and it is also far away from the null. Technically the "true value" is the alternative hypothesis for the purpose of the calculator. I get $$n=2$$ for this, which is likely wrong due to normal approximation. But when this happens the exact calculations are easy to do, as I show below.

E.g. seeing 2 FP in sample of 2 (100% FP rate) still has a 25% chance of occurring under null, and you would need more like 4 or 5 sample size as then a 100% FP rate occurs with (roughly) probability 6% and 3%. ie probability of 100% FP in sample is $$0.5^n$$ under the null (this uses binomial approximation rather than normal approximation, much more accurate for small sample sizes)

If you include power, you get $$0.96^n$$ chance of 100% fp under alternative, which is 85% chance when $$n=4$$ and 82% chance when $$n=5$$.

So you don't need a large sample to decide between the two options $$p_0=0.5$$ and $$p_a=0.96$$. Decision is also easy - if you find a cat, stop and accept $$h_0$$.

This does depend a lot on the value for your alternative. If you set $$p_a=0.75$$ then you need a sample of about $$n=24$$.

The basic idea is that the gap $$|p_0-p_a|$$ is a key determinant of how big the standard error of the estimator needs to be. In your scenario, the gap is large, so the sample size is small.

But....there is an underlying assumption here....you are assuming the true FP rate can only be 1 of two values, either $$0.5$$ or $$0.96$$. It is more likely that both values wrong than 1 of them is correct. Probably better to think in terms of estimation and the desired accuracy instead.

clearly $$SD(r)=0$$ if $$n=N$$ as we would expect. For the case $$n=5$$ and "large" $$N$$, we have $$SD(r)=0.087$$. So the usual 95% CI from the normal approximation would be $$r\pm 0.175$$. If $$r=0.8$$ (ie 4 out of 5 fp) then the CI is $$(0.625,0.975)$$ just including the alternative value of $$0.96$$.

I would use this formula to derive $$n$$ after you set a given standard deviation. I think it's easier to set this number to something you like and solve for $$n$$. This gives the formula

$$n=\left(\frac{SD(r)^2}{p_{pop}(1-p_{pop})}+\frac{1}{N}\right)^{-1}$$

e.g. suppose I want the standard error to be within say 5 percentage points of the true value. So you set $$SE(r)=0.05$$ (or your preferred number), and I have $$p_{pop}=0.96$$ from the previous data. If we assume $$N$$ is "big" so that $$\frac{n}{N}\approx 0$$, we get $$n=15.36$$.

(note: if the $$n$$ you get from assuming $$\frac{1}{N}\approx 0$$ is not small compared to $$N$$, then you should include the term $$\frac{1}{N}$$)