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. 
 A: 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.
A: 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}$)
