31 Test Set Bound (Theorem)

For all classifiers $c$, for all distributions $\mathcal{D}$, for all $\delta \in (0,1]$ :

$$\underset{S\sim {\mathcal{D}}^n}{\mathrm{Pr}}\left(c_D\le \overline{\text{Bin}}(n,n\cdot {\hat{c}}_S,\delta )\right)\ge 1-\delta$$

• This result provides a probabilistic guarantee on the true error rate based on observed data.
• It is derived under the assumption of i.i.d. samples from the distribution $\mathcal{D}$. The probability that ${\hat{c}}_S$ will not fall into a tail of size $\delta$ is exactly $1-\delta$. Hence, with this probability, $\text{Bin}(n,n\cdot {\hat{c}}_S,c_D)\ge \delta$, so by the definition of $\text{Bin}$, we have $c_D\le \text{Bin}(n,n\cdot {\hat{c}}_S,\delta )$.

How to use the test set bound ?

• For the tightest bound, we can use numerical methods to compute $\overline{\text{Bin}}(n,n\cdot {\hat{c}}_S,\delta )$.
• For reasons of simplicity we can use upper-bound on $\overline{\text{Bin}}(n,n\cdot {\hat{c}}_S,\delta )$ instead at the expense of giving up some tightness.

Simplified forms of the bound

There are upper bound approximation $\overline{\text{Bin}}(n,k,p)$ that are simpler to compute and simpler to interpret. One of these result in the following corollary. Corollary. For all classifiers $c$, for all distributions $\mathcal{D}$, for all $\delta \in (0,1]$

$$\underset{S\sim {\mathcal{D}}^n}{\mathrm{Pr}}\left(c_D\le {\hat{c}}_S+\sqrt{\frac{\ln \frac{1}{\delta }}{2n}}\right)\ge 1-\delta$$

This corollary is also obtainable from Hoeffding’s bound

What does the Test Set Bound Tell Us ?

• The test set bound gives a mechanism to certify the extent to which the classifier has learned to predict correctly.
• The guarantee is probabilistic - it only implies that the bound will not be wrong for a $1-\delta$ fraction of its applications / i.e., training sets.
• The bound tightens with larger sample sizes $n$.
• Relies on the assumption of independent and identically distributed samples.
• Useful for both theoretical insights and practical applications.
• Simple and its validity is well understood.