33 Occam's Razor Bound

• Confidence bounds are frequentist guarantees - including both Test Set Bound, and Train Set Bounds.
• However, we will take and adapt a Bayesian idea,
• Before seeing the training set $S$, we define a “prior” probability distribution over the classifiers, $P(c)$. This represents our “bet” on the candidate classifiers.
• Suppose a simple learning problem where we have a countable number of classifiers for the learning algorithm to choose from based on a training sample $S$.

Theorem

For all “priors” $P(c)$ over a countable set of classifiers, for all distributions $\mathcal{D}$, for all $\delta \in (0,1]$:

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

Compare with the Test Set Bound : $\delta \to \delta P(c)$. Corollary For all $P(c)$, all $\mathcal{D}$, all $\delta \in (0,1]$ :

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

Tightness depends on the self-information $\log \frac{1}{P(c)}$ of the classifier returned by the learning algorithm, with respect to our prior bets.

Occam’s Razor Bound : Proof

Idea : without training apply the Test Set Bound to each $c$ in turn with confidence parameter $\delta P(c)$ :

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

Negate to get equivalent statement :

$$\forall c\underset{S\sim {\mathcal{D}}^m}{\mathrm{Pr}}\left(c_D>\overline{\text{Bin}}\left(m,n\cdot {\hat{c}}_S,\delta P(c)\right)\right)<\delta P(c)$$

Apply union bound : $Pr(AorB)\le Pr(A)+Pr(B)$ repeatedly.

$$\underset{S\sim {\mathcal{D}}^m}{\mathrm{Pr}}\left(\exists c:c_D>\overline{\text{Bin}}\left(m,n\cdot {\hat{c}}_S,\delta P(c)\right)\right)<\sum _c\delta P(c)=\delta$$