Understanding Machine Learning

Motivation

Chapter 17 introduced multiclass prediction; Chapter 29 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), asks the two questions the fundamental theorem answered for binary classes: which classes of multiclass predictors are PAC learnable with respect to the 0–1 loss, and with what sample complexity. Natarajan's dimension generalizes the VC dimension by shattering with two disagreeing label functions, and the multiclass fundamental theorem (Theorem 29.3) bounds the uniform-convergence, agnostic and realizable sample complexities in terms of it, up to logarithmic factors in the number of labels $k$; the only new ingredient in its proof is Natarajan's lemma, the multiclass substitute for Sauer's lemma. The chapter then computes or bounds the Natarajan dimension of the classes that matter, One-versus-All and general reductions to binary classifiers, and linear multiclass predictors (Theorem 29.7). Its last section is a warning: unlike the binary case, not all ERMs are equal, and with infinitely many labels a class can be learnable by one ERM and not by another, so learnability and uniform convergence come apart (Claim 29.9).

Setting

$H$ is a class of functions from $X$ to a finite label set $Y$ with $|Y| = k$. $C \subseteq X$ is shattered by $H$ if there are $f_0, f_1 : C \to Y$ with $f_0(x) \ne f_1(x)$ everywhere on $C$ such that every $B \subseteq C$ is realized by some $h \in H$ agreeing with $f_0$ on $B$ and with $f_1$ on $C \setminus B$ (Definition 29.1); $\operatorname{Ndim}(H)$ is the largest size of a shattered set (Definition 29.2). One-versus-All builds $T(\bar h)(x) = \operatorname{argmax}_i h_i(x)$ from $k$ binary classifiers, the smaller label on ties; a general reduction applies a rule $r : \{0,1\}^l \to [k]$ to $l$ binary classifiers; the linear class $H_\Psi$ predicts $\operatorname{argmax}_i\langle w, \Psi(x, i)\rangle$ for a class-sensitive feature map $\Psi : X \times [k] \to \mathbb{R}^d$ (29.1). The class of §29.4 has labels $P_f(X) \cup \{\ast\}$, the finite and cofinite subsets of $X$ plus a special label, and hypotheses $h_A(x) = A$ if $x \in A$ and $\ast$ otherwise; $A_{good}$ returns $h_\emptyset$ on an all-$\ast$ sample and $A_{bad}$ returns $h_{\{x_1, \dots, x_m\}^c}$.

Formalization targets

Goal: Theorem 29.3

There are absolute constants $C_1, C_2 > 0$ such that every class $H \subseteq Y^X$ with $\operatorname{Ndim}(H) = d$ satisfies

$$C_1\frac{d + \log(1/\delta)}{\epsilon^2} \le m^{UC}_H(\epsilon,\delta),\ m_H(\epsilon,\delta) \le C_2\frac{d\log k + \log(1/\delta)}{\epsilon^2}, \qquad C_1\frac{d + \log(1/\delta)}{\epsilon} \le m^{\mathrm{real}}_H(\epsilon,\delta) \le C_2\frac{d\log(kd/\epsilon) + \log(1/\delta)}{\epsilon},$$

the upper bounds by every ERM learner and the lower bounds for small $\epsilon, \delta$ and $d \ge 2$, in the format of Mission IV's Theorem 6.8.

Milestones

Lemma 29.4 (Natarajan: $|H| \le |X|^{\operatorname{Ndim}(H)}k^{2\operatorname{Ndim}(H)}$); Lemma 29.5 (the Natarajan dimension of One-versus-All is $O(kd\log(kd))$); Theorem 29.7 ($\operatorname{Ndim}(H_\Psi) \le d$); Claim 29.9(1) ($A_{good}$ needs $\frac1\epsilon\log\frac1\delta$ examples); Claim 29.9(2) ($A_{bad}$ fails with constant probability on $(|X|-1)/(6\epsilon)$ examples). Further items: the equality $\operatorname{Ndim} = \operatorname{VCdim}$ for two classes, and Lemma 29.6 for general reductions.

Significance

Theorem 29.3 is the multiclass fundamental theorem of Natarajan (1989) and Ben-David, Cesa-Bianchi, Haussler and Long (1995): finite Natarajan dimension characterizes multiclass learnability, and the sample complexity is linear in it, with the dependence on $k$ confined to logarithms. Natarajan's lemma is the combinatorial core, and the dimension bounds of §29.3 are what make the theorem usable: a One-versus-All scheme over a class of VC dimension $d$ costs $\tilde O(kd)$, and a linear multiclass predictor costs at most its number of parameters, so the multivector construction of Chapter 17 is learnable with $\tilde O(nk/\epsilon^2)$ examples. Claim 29.9 is a genuine phenomenon of Daniely, Sabato, Ben-David and Shalev-Shwartz (2011): in multiclass classification the choice of ERM matters, and the equivalence "learnable iff uniform convergence" of the binary theory is false, which is why Conjecture 29.10 about good ERMs is open in the form the chapter states it.

Difficulty

The equality with the VC dimension for two labels is a direct comparison of the two shattering definitions. Natarajan's lemma is a Sauer-type induction on $|X|$, in which a shattered set must be produced from two hypotheses that differ at a point; the exercise-level proof of the book becomes a careful double induction formally. Theorem 29.3's upper bounds follow the binary proof of Chapter 28 with Natarajan's lemma in place of Sauer's, hence Massart's lemma and Theorem 26.5 for the agnostic case and the double-sample argument for the realizable case; the lower bounds reduce to the binary ones by embedding a binary class into a multiclass one on a shattered set. These are long formal developments, and the theorem is stated with unspecified constants for that reason. Lemmas 29.5 and 29.6 are counting: a shattered $C$ has $2^{|C|} \le |H_C| \le |(H_{bin})_C|^k$, Sauer's lemma bounds the right side by $\big(\sum_{i \le d}\binom{|C|}{i}\big)^{k}$, and the resulting inequality is solved. For Lemma 29.5's printed $3kd\log(kd)$ this fails only at $(k, d) = (2, 1), (3, 1)$. There a shattered set splits by the label pair $\{f_0(x), f_1(x)\}$ into parts shattered by $\{B \setminus A : A, B \in H_{bin}\}$ (pairs $\{0, b\}$) or by $H_{bin}$ (other pairs). The first class has at most $31$ traces on $5$ points. Theorem 29.7 maps a shattered set into $\mathbb{R}^d$ by $\rho(x) = \Psi(x, f_0(x)) - \Psi(x, f_1(x))$, up to sign, and shows the image is shattered by homogeneous halfspaces; the tie-breaking rule decides which sign and which halfspace convention to use. Claim 29.9(1) is the bound $(1-\epsilon)^m \le \delta$; Claim 29.9(2) needs only that at most $(d-1)/2$ of the $d-1$ light points appear in the sample, an event of probability at least $1/3$ by Markov's inequality when $m \le (d-1)/(6\epsilon)$, which exceeds the claimed $e^{-1}/6$.

Formalization scope

Labels are an arbitrary finite type, shattering and the Natarajan dimension are stated with witnesses $f_0, f_1$ defined on all of $X$, and the dimension is a supremum in $\mathbb{N} \cup \{\infty\}$. The multiclass 0–1 loss, the ERM property, agnostic PAC learnability and uniform convergence are Mission I's generic notions; the realizable multiclass PAC property is defined here in the shape of Definition 3.1 with $D(\{h \ne f\})$ as the error, since Mission I's binary version is $\{0,1\}$-specific. Theorem 29.3 is stated exactly as Mission IV states Theorem 6.8, with existential constants, upper bounds for every ERM learner of a nonempty measurable class with the countable-approximation property (the measurability device of Remark 3.1), and lower bounds for $\epsilon < \epsilon_0$, $\delta < \delta_0$, $d \ge 2$. Argmax predictors, both One-versus-All and $H_\Psi$, break ties towards the smallest label; the book states this rule for One-versus-All, and some fixed rule is necessary for Theorem 29.7, since with arbitrary tie-breaking every function is an argmax predictor of the zero mapping. Lemmas 29.5 and 29.6 are stated per shattered set. Lemma 29.5 keeps the printed $3kd\log(kd)$, which is true although the book's step $|(H_{bin})_C| \le |C|^d$ fails for small $|C|$. Lemma 29.6 uses $2ld\log_2(2ld)$, which the counting supports, because the printed $3ld\log(ld)$ is false at $l = d = 1$. Theorem 29.3's uniform-convergence upper bound is stated for $d \ge 1$. At $d = 0$ the confidence term $\log(1/\delta)$ vanishes as $\delta \to 1$, the bound reaches $m = 1$, and a single example is not representative. The class of §29.4 has labels Option of the subtype of finite-or-cofinite sets, with the discrete σ-algebra, and the two ERMs are predicates fixing the output on all-$\ast$ samples; Claim 29.9(1) is stated for countable $X$ with measurable singletons and Claim 29.9(2) for finite $X$ of size at least $2$, with the proof's own distribution, $h_\emptyset$ as target, and every $\epsilon \in (0, 1/2)$ in place of the book's unspecified constant $a$.

Not stated: Corollary 29.8 (its lower bound $(k-1)(n-1)$ is cited, not proved), Conjecture 29.10, the exercises.

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapter 29. doi:10.1017/CBO9781107298019
• B. K. Natarajan, On learning sets and functions, Machine Learning 4, 1989. doi:10.1007/BF00114804
• S. Ben-David, N. Cesa-Bianchi, D. Haussler, P. M. Long, Characterizations of learnability for classes of {0, …, n}-valued functions, Journal of Computer and System Sciences 50(1), 1995. doi:10.1006/jcss.1995.1008
• D. Haussler, P. M. Long, A generalization of Sauer's lemma, Journal of Combinatorial Theory A 71(2), 1995. doi:10.1016/0097-3165(95)90001-2
• A. Daniely, S. Sabato, S. Ben-David, S. Shalev-Shwartz, Multiclass learnability and the ERM principle, COLT 2011; Journal of Machine Learning Research 16, 2015.
• A. Daniely, S. Sabato, S. Shalev-Shwartz, Multiclass learning approaches: a theoretical comparison with implications, NIPS 2012.

Motivation

The book has characterized learnability through uniform convergence and through stability; Chapter 30 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), gives a third sufficient condition, compression: if a learning algorithm's output can be reconstructed from a small subsequence of $k$ training examples, then the error on the remaining examples estimates the true error, and the algorithm generalizes with a bound of order $k\log(m/\delta)/m$ (Theorem 30.2, Littlestone and Warmuth). The bound is a union bound over the $m^k$ possible index sequences of a held-out estimate that follows from Bernstein's inequality (Lemma 30.1), and in the consistent case it gives $L_D \le 8k\log(m/\delta)/m$ (Corollary 30.3). Classes admitting such compression schemes include axis-aligned rectangles ($k = 2d$), homogeneous halfspaces ($k = d$, through the minimal-norm point of the convex hull and Carathéodory's theorem), separating polynomials by reduction, and any margin-separable data ($k \le 1/\gamma^2$, through the Perceptron). Whether every class of finite VC dimension has a compression scheme of size $O(d)$ is Warmuth's problem, open when the book was written.

Setting

A sample $S = (z_1, \dots, z_m)$ is drawn i.i.d. from $D$; a selection rule picks $(i_1, \dots, i_k) \in [m]^k$ (repetitions allowed), a reconstruction map $B : Z^k \to H$ produces $A(S) = B(z_{i_1}, \dots, z_{i_k})$, and $V$ is the set of positions not selected, with $L_V$ the average loss over them. The loss takes values in $[0,1]$. A class $H$ has a compression scheme of size $k$ (Definition 30.4) if for every $m \ge 1$ there are such $A$ and $B$ with $B(S_{A(S)})$ correct on every sample labeled by a member of $H$; the unrealizable version (Definition 30.5) asks $B(S_{A(S)})$ to be an empirical risk minimizer on every sample.

Formalization targets

Goal: Theorem 30.2

For a $[0,1]$-valued loss, $k \ge 1$, $m \ge 2k$, any reconstruction map $B$ and any selection rule, with probability at least $1 - \delta$ over $S \sim D^m$,

$$L_D(A(S)) \le L_V(A(S)) + \sqrt{L_V(A(S))\,\frac{4k\log(m/\delta)}{m}} + \frac{8k\log(m/\delta)}{m}.$$

Milestones

Lemma 30.1 (the held-out Bernstein bound); Corollary 30.3 (the consistent case); Lemma 30.6 (realizable schemes give unrealizable schemes); the compression scheme of size $2d$ for axis-aligned rectangles (§30.2.1); the separation property of the minimal-norm point of the convex hull (§30.2.2). Further items: the size-$d$ scheme for homogeneous halfspaces and the margin scheme of §30.2.4.

Significance

Compression bounds are the cleanest generalization argument in the book: no complexity measure of the class enters, only the number of examples needed to encode the output, and the resulting bound is data-dependent through $L_V$. They explain why support vector machines and the Perceptron generalize in terms of the number of support vectors or updates, and they underlie the sample-compression view of learning that connects to Chapters 9 and 15. Lemma 30.6 shows that compression is robust to label noise in the binary case. The halfspace scheme is a small piece of convex geometry of independent interest, and Warmuth's question about VC classes, settled in the affirmative for finite size by Moran and Yehudayoff after the book appeared, remains open in the form $O(d)$.

Difficulty

Lemma 30.1 is Bernstein's inequality for the $n$ held-out losses with variance at most $L_D(h_T)$, followed by solving the resulting quadratic in $\sqrt{L_D}$ to move the risk from the right-hand side to $L_V$; the constant $4$ comes out of that step (the exact value is about $3.19$). Theorem 30.2 is a union bound over the $m^k$ index sequences with $\delta' = m^k\delta$, using $|V| \ge m - k \ge m/2$ and $\log(m^k/\delta') \le k\log(m/\delta')$, which needs $k \ge 1$; formally the event for the learner is contained in the union of the events of Lemma 30.1 for each fixed index sequence, so no measurability of the selection rule is needed. Corollary 30.3 is immediate. Lemma 30.6 applies the realizable scheme to the subsample on which an ERM hypothesis is correct. The rectangle scheme is bookkeeping about extremal coordinates. The halfspace scheme needs three facts: the minimal-norm point of the hull separates (a one-line perturbation argument), it lies on a face and hence is a convex combination of $d$ sample points (Carathéodory's theorem, in Mathlib, applied to a face), and it is the minimal-norm point of the hull of those $d$ points (uniqueness of the projection onto a convex set); the existence of the minimizer uses compactness of the hull. The margin scheme is the Perceptron convergence theorem of Mission VI applied to the batch algorithm, whose output is the sum of the updated examples.

Formalization scope

Samples are Fin m-indexed under Mission I's iidLaw, and probability statements bound the outer measure of the failure event. Lemma 30.1 splits a sample of size $k + n$ into its first $k$ and last $n$ entries; Theorem 30.2 takes an arbitrary selection rule $\mathrm{sel} : Z^m \to [m]^k$ and reconstruction map $B$, the held-out set being the positions not in the range of the selection, and requires $k \ge 1$ and $m \ge 1$ in addition to the book's $m \ge 2k$: for $k = 0$ the bound reads $L_D \le L_V$, which fails, and the book's derivation uses $k \ge 1$ in $\log(m^k/\delta') \le k\log(m/\delta')$. Compression schemes are defined for every $m \ge 1$, since for $m = 0$ there is no index to select, with indices allowed to repeat as in $[m]^k$ and with $B$'s outputs in $H$; the unrealizable version uses Mission XXIII's multiclass 0–1 loss. The halfspace results are stated for strictly separable $\pm1$-labeled samples, $y_i\langle w^\star, x_i\rangle > 0$, the book's "w.l.o.g. all labels positive" normalization; this avoids the boundary negatives that a realizable sample may contain under the $\operatorname{sign}(0)$ convention of Mission VI, and it is the setting in which the minimal-norm argument works. The scheme is stated as the existence of $d$ indices whose signed examples have a minimal-norm hull point separating the whole sample, which is the content of $A$ and $B$ without fixing how ties among faces are broken. Rectangles are closed boxes. The margin scheme uses Theorem 9.1's normalization.

Not stated: §30.2.3 (polynomials, a reduction), the bibliographic remarks, and the intermediate Carathéodory step as a separate item.

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapter 30. doi:10.1017/CBO9781107298019
• N. Littlestone, M. K. Warmuth, Relating data compression and learnability, technical report, University of California, Santa Cruz, 1986.
• S. Floyd, M. K. Warmuth, Sample compression, learnability, and the Vapnik-Chervonenkis dimension, Machine Learning 21, 1995. doi:10.1007/BF00993593
• S. Ben-David, A. Litman, Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes, Discrete Applied Mathematics 86, 1998. doi:10.1016/S0166-218X(98)00000-6
• S. Moran, A. Yehudayoff, Sample compression schemes for VC classes, Journal of the ACM 63(3), 2016. doi:10.1145/2890490

Motivation

The MDL and Occam principles of Chapter 7 rank hypotheses by description length and pay for a hypothesis according to its rank. Chapter 31 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), generalizes this to the PAC-Bayesian approach of McAllester: prior knowledge is a prior distribution $P$ over the class, the learner outputs a posterior $Q$, read as the randomized predictor that draws $h \sim Q$, and the price of $Q$ is its Kullback–Leibler divergence from $P$. The PAC-Bayes theorem (Theorem 31.1) says that with probability $1 - \delta$, simultaneously for every posterior, the generalization loss exceeds the training loss by at most $\sqrt{(D(Q\|P) + \ln(m/\delta))/(2(m-1))}$. Its proof is a compact and elegant argument: Markov's inequality for an exponential moment, a change of measure from $Q$ to $P$ by Jensen's inequality, an exchange of expectations that is possible because the prior does not depend on the sample, and a moment bound for the deviation of a single hypothesis. The bound suggests the learning rule of Remark 31.1, minimize $L_S(Q)$ plus the divergence penalty, which is regularized risk minimization in disguise, and for a finite class with a uniform prior it recovers an Occam-type bound (Exercise 2).

Setting

$H$ is a measurable space of hypotheses, $\ell : H \times Z \to [0,1]$ a jointly measurable loss, $D$ a distribution over $Z$, and $P$ a prior probability measure on $H$. For a posterior $Q$, $\ell(Q, z) = \mathbb{E}_{h \sim Q}[\ell(h, z)]$, $L_D(Q) = \mathbb{E}_{h \sim Q}[L_D(h)]$ and $L_S(Q) = \mathbb{E}_{h \sim Q}[L_S(h)]$, and $D(Q\|P) = \mathbb{E}_{h \sim Q}[\ln(dQ/dP)]$ is the Kullback–Leibler divergence, a real number when $Q \ll P$ and the log-density is $Q$-integrable.

Formalization targets

Goal: Theorem 31.1

For $m \ge 2$ and $\delta \in (0,1)$, with probability at least $1 - \delta$ over $S \sim D^m$, every probability measure $Q \ll P$ with finite divergence satisfies

$$L_D(Q) \le L_S(Q) + \sqrt{\frac{D(Q\|P) + \ln(m/\delta)}{2(m-1)}}.$$

Milestones

The identity $\mathbb{E}_{z \sim D}[\ell(Q, z)] = L_D(Q)$ (§31.1); the moment bound $\mathbb{E}_S[e^{2(m-1)\Delta(h)^2}] \le m$ of the proof (p. 417); Exercise 2, the bound for a finite class with the uniform prior.

Significance

PAC-Bayes bounds are among the tightest generalization bounds known in practice, and the reason is visible in Theorem 31.1: the complexity term is not a property of the class but of the posterior actually chosen, measured against a prior, so a learner that stays close to its prior generalizes even in a huge class. The theorem is the ancestor of a large literature (Seeger, Langford, Catoni, Maurer) and of modern nonvacuous bounds for neural networks. Formally it is a pleasant target: the change-of-measure inequality $\mathbb{E}_{h \sim Q}[f(h)] - D(Q\|P) \le \ln\mathbb{E}_{h \sim P}[e^{f(h)}]$ is the Donsker–Varadhan inequality, of independent value, and the moment bound is a sharp sub-Gaussian fact. On the platform, the mission introduces Gibbs risks and the Kullback–Leibler divergence between measures on a class, ending the book's series with its last learning principle.

Difficulty

The Gibbs risk identity is Fubini for a bounded jointly measurable function. The moment bound is the delicate step: the book derives it from Hoeffding's tail bound through Exercise 1, whose one-sided hypothesis is not enough (a constant negative variable satisfies it with an unbounded moment), and even the two-sided tail integrates only to $2m - 1$; the claim $\le m$ is nevertheless true, for instance by writing $e^{a\Delta^2} = \mathbb{E}_g[e^{\sqrt{2a}\,g\Delta}]$ for a standard Gaussian $g$ and applying Hoeffding's lemma to the sample mean, which gives $\mathbb{E}_S[e^{2(m-1)\Delta^2}] \le (1 - (m-1)/m)^{-1/2} = \sqrt m$. Theorem 31.1 then follows the book: Markov's inequality on $e^{f(S)}$ with $f(S) = \sup_Q(2(m-1)\mathbb{E}_{h \sim Q}\Delta(h)^2 - D(Q\|P))$, the change of measure (31.2) by Jensen's inequality for $\ln$ applied to the density $dQ/dP$ (the Donsker–Varadhan inequality, which needs $Q \ll P$ and an integrable log-density), the exchange of expectations (31.4) by Fubini, the moment bound, and finally Jensen for $x^2$ in (31.6); formally the supremum over all posteriors is handled by proving the bound for each $Q$ on the event $\{S : \mathbb{E}_{h \sim P}[e^{2(m-1)\Delta(h)^2}] \le m/\delta\}$, whose complement has probability at most $\delta$ by Markov, which sidesteps any measurability question about $f$. Exercise 2 is the theorem with $Q = \delta_h$, for which $D(Q\|P) = \ln|H|$.

Formalization scope

The class is an arbitrary measurable space, priors and posteriors are probability measures on it, and $Q(h)/P(h)$ is Mathlib's Radon–Nikodym derivative; the divergence is a Bochner integral, so the theorem quantifies over posteriors $Q \ll P$ whose log-density is $Q$-integrable, exactly the posteriors with a finite divergence, for which the bound has content, and no junk value can make a case false. Posteriors may depend on the sample: the statement bounds the outer measure of the set of samples for which some admissible $Q$ violates the bound. The loss is jointly measurable so that $h \mapsto L_D(h)$ and $(S, h) \mapsto L_S(h)$ are measurable and the Gibbs risks are genuine integrals; $m \ge 2$ is forced by the denominator $2(m-1)$. The moment bound is stated as the claim the proof needs rather than as Exercise 1, whose printed hypothesis is insufficient; the item text records this. Exercise 2 is stated as a simultaneous bound over the finite class, the form in which the theorem delivers it.

Not stated: Remark 31.1 (a learning rule, not a theorem), Exercise 1 as printed, and the second part of Exercise 2.

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapter 31. doi:10.1017/CBO9781107298019
• D. A. McAllester, Some PAC-Bayesian theorems, Machine Learning 37, 1999. doi:10.1023/A:1007618624809
• D. A. McAllester, PAC-Bayesian stochastic model selection, Machine Learning 51, 2003. doi:10.1023/A:1021840411064
• A. Maurer, A note on the PAC Bayesian theorem, arXiv:cs/0411099, 2004.
• M. Seeger, PAC-Bayesian generalisation error bounds for Gaussian process classification, Journal of Machine Learning Research 3, 2002.
• J. Langford, J. Shawe-Taylor, PAC-Bayes and margins, NIPS 2002.