30 Preparation for Test Set Bounds

For the purposes of the test set bound, $c$ is a pre-trained classifier, and $S$ stands for an independent test set. Question : What is the distribution of $n\cdot {\hat{c}}_S$ ?

Ans : Binomial with mean $n\cdot c_{\mathcal{D}}$. This represents the probability of $k$ errors in $n$ flips of a coin with bias parameter $c_{\mathcal{D}}$.

$$\underset{S\sim {\mathcal{D}}^n}{\mathrm{Pr}}\left(n\cdot {\hat{c}}_S=k\mid c_{\mathcal{D}}\right)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)c_{\mathcal{D}}^k(1-c_{\mathcal{D}}{)}^{n-k}$$

Choose desired confidence level $\delta$, say 0.1

• Pivot of the cumulative :

$$\overline{\text{Bin}}(n,k,\delta )=\max \left\{p:\text{Bin}(n,k,p)\ge \delta \right\}$$

This is the largest true error such that the probability of observing $k$ or fewer “heads” (error) in $n$ trials (test points) is at least $\delta$.