Learning Theory
No free lunch says a learner with no inductive bias cannot generalise. Computational learning theory turns that into arithmetic: restrict the hypothesis space \(H\), and the number of examples needed to generalise grows with the logarithm of \(|H|\), or with its VC dimension when \(H\) is infinite. A second strand counts mistakes instead of examples, for learners that predict online.
the setting
Training minimises the empirical risk: pick \(h \in H\) with the smallest training error. With \(H\) unrestricted this overfits, since a look-up table has zero training error. Learning theory asks when a restricted \(H\) makes empirical-risk minimisation safe.
Instances \(x\) are drawn independently from a fixed, unknown distribution \(\mathcal{D}\) over the instance space \(X\), and labelled by a target concept \(c : X \to \{0,1\}\) from a class \(C\). Labels are noise-free. Until the agnostic section we also assume realisability: \(c \in H\).
The true error of \(h\) is \(\operatorname{error}_{\mathcal{D}}(h) = \Pr_{x \sim \mathcal{D}}[h(x) \ne c(x)]\); the training error is the fraction of the sample \(S\) that \(h\) misclassifies. \(h\) is consistent with \(S\) if its training error is zero. The version space is \[ VS_{H,S} = \{ h \in H : h \text{ is consistent with } S \}. \] \(VS_{H,S}\) is \(\varepsilon\)-exhausted if every \(h\) in it has \(\operatorname{error}_{\mathcal{D}}(h) < \varepsilon\).
A consistent learner outputs some member of the version space. If the version space is \(\varepsilon\)-exhausted, it does not matter which member: all of them are good.
\(C\) is PAC-learnable by \(L\) using \(H\) if, for every \(c \in C\), every distribution \(\mathcal{D}\), every \(\varepsilon \in (0, \tfrac12)\) and every \(\delta \in (0, \tfrac12)\), \(L\) outputs with probability at least \(1 - \delta\) a hypothesis with \(\operatorname{error}_{\mathcal{D}}(h) \le \varepsilon\), in time polynomial in \(1/\varepsilon\), \(1/\delta\), the instance size \(n\) and \(\operatorname{size}( c)\).
“Probably” is \(\delta\), “approximately” is \(\varepsilon\). The sample complexity is the number of examples \(m\) that suffices. Polynomial time forces polynomial sample complexity, since every example has to be read.
finite hypothesis spaces
Let \(H\) be finite and let \(S\) be \(m\) independent examples of \(c\). For any \(\varepsilon \in [0,1]\), \[ \Pr\big[VS_{H,S} \text{ is not } \varepsilon\text{-exhausted}\big] \le |H| e^{-\varepsilon m}. \] So the version space is \(\varepsilon\)-exhausted with probability at least \(1-\delta\) once \[ m \ge \frac{1}{\varepsilon}\Big( \ln|H| + \ln\frac{1}{\delta} \Big). \]
Call \(h\) bad if \(\operatorname{error}_{\mathcal{D}}(h) \ge \varepsilon\). A bad \(h\) agrees with \(c\) on one random example with probability at most \(1 - \varepsilon\), so it survives all \(m\) independent examples with probability at most \((1-\varepsilon)^m\). The version space fails to be \(\varepsilon\)-exhausted exactly when some bad \(h\) survives. By the union bound over at most \(|H|\) bad hypotheses, and \(1 - \varepsilon \le e^{-\varepsilon}\), \[ \Pr[\text{some bad } h \text{ survives}] \le |H|(1-\varepsilon)^m \le |H| e^{-\varepsilon m}. \] Setting \(|H| e^{-\varepsilon m} \le \delta\) and taking logarithms gives the bound on \(m\).
The bound holds for any consistent learner, any target in \(H\) and any \(\mathcal{D}\). It is the precise sense in which Occam’s razor is justified: a smaller \(H\) needs fewer examples, because fewer hypotheses can fit the data by luck. It does not say simple targets are more likely, which is what no free lunch denies. Note \(m\) grows like \(1/\varepsilon\) but only like \(\ln(1/\delta)\): confidence is cheap, accuracy is not.
Instances have \(n = 12\) Boolean features. A hypothesis is a conjunction in which each feature appears positively, negated, or not at all, so \(|H| = 3^{12} = 531441\). For error at most \(\varepsilon = 0.05\) with probability \(0.99\) (\(\delta = 0.01\)): \[ m \ge \frac{1}{0.05}\big(12 \ln 3 + \ln 100\big) = 20\,(13.183 + 4.605) = 355.77, \] so \(m = 356\) examples suffice. Halving \(\varepsilon\) to \(0.025\) doubles this to 712; tightening \(\delta\) tenfold to \(0.001\) only raises it to 402.
An unbiased learner uses \(H = \) every Boolean function on \(X\). With \(n\) Boolean features, \(|X| = 2^n\) and \(|H| = 2^{2^n}\), so \[ m \ge \frac{1}{\varepsilon}\Big( 2^n \ln 2 + \ln\frac{1}{\delta} \Big), \] exponential in \(n\). For the numbers above (\(n = 12\), \(\varepsilon = 0.05\), \(\delta = 0.01\)) this is 56875 examples, against an instance space of only \(2^{12} = 4096\) points: the bound can only be met by seeing essentially every instance, which is memorisation, not generalisation.
Infinite spaces are not automatically hopeless. Thresholds on the real line, \(h_\theta(x) = 1\) iff \(x \ge \theta\), form an infinite \(H\) that is still PAC-learnable; the next section explains why.
Drop realisability, so no \(h \in H\) need be consistent, and let the learner return the \(h\) with the smallest training error. Hoeffding’s inequality gives, for each fixed \(h\), \[ \Pr\big[\operatorname{error}_{\mathcal{D}}(h) > \widehat{\operatorname{error}}_S(h) + \varepsilon\big] \le e^{-2m\varepsilon^2}, \] and a union bound over \(H\) shows that, with probability at least \(1 - \delta\), every \(h\) has true error at most its training error plus \(\varepsilon\) once \[ m \ge \frac{1}{2\varepsilon^2}\Big( \ln|H| + \ln\frac{1}{\delta} \Big). \]
The price of noise or misspecification is \(1/\varepsilon^2\) in place of \(1/\varepsilon\). For the conjunctions example the agnostic bound is 3558 examples, ten times the realisable 356, the factor being \(1/(2\varepsilon) = 10\).
infinite hypothesis spaces
For infinite \(H\), \(\ln|H|\) is useless. What matters is not how many hypotheses there are but how many labellings of a finite sample they can produce.
A set \(S \subseteq X\) is shattered by \(H\) if every one of the \(2^{|S|}\) labellings of \(S\) is produced by some \(h \in H\). The Vapnik–Chervonenkis dimension \(\operatorname{VC}(H)\) is the size of the largest finite set shattered by \(H\), or \(\infty\) if arbitrarily large sets are shattered.
To show \(\operatorname{VC}(H) = d\) takes two arguments of different shape: some set of \(d\) points is shattered, and no set of \(d+1\) points is. For finite \(H\), shattering \(d\) points needs \(2^d\) distinct hypotheses, so \(\operatorname{VC}(H) \le \log_2|H|\).
| hypothesis space | VC dimension |
|---|---|
| thresholds \(x \ge \theta\) on \(\mathbb{R}\) | 1 |
| intervals \([a,b]\) on \(\mathbb{R}\) | 2 |
| axis-parallel rectangles in \(\mathbb{R}^2\) | 4 |
| linear separators in \(\mathbb{R}^d\) | \(d+1\) |
| conjunctions of literals over \(d\) Boolean variables | \(d\) |
| convex polygons in \(\mathbb{R}^2\) | \(\infty\) |
| \(I(\sin(\alpha x) > 0)\), one parameter | \(\infty\) |
Intervals. Two points \(x_1 < x_2\) are shattered: each of the four labellings is cut out by a short interval or an empty one. No three points \(x_1 < x_2 < x_3\) are: the labelling \((+, -, +)\) needs an interval containing \(x_1\) and \(x_3\) but not \(x_2\), and intervals are convex. So the VC dimension is 2.
Rectangles. The four points \((0, \pm 1)\), \((\pm 1, 0)\) are shattered (the bounding box of any subset misses the others). For any five points, label positive the leftmost, rightmost, top and bottom points (at most four) and the remaining point negative; every rectangle containing the four contains the fifth. So the VC dimension is 4.
The last row of the table is the warning: VC dimension is not parameter count. \(\sin(\alpha x)\) has one parameter, yet a suitable \(\alpha\) realises every labelling of the points \(x_i = 10^{-i}\), for any number of them. For linear separators in \(\mathbb{R}^d\) the two happen to agree, \(d+1\) of each; margin-based bounds escape the dependence on \(d\) altogether, which is why the margin controls capacity in the SVM.
Let \(X = \{0,1\}^m\) and \(H\) be all decision trees on the \(m\) Boolean attributes. A tree that tests all \(m\) attributes on every path has one leaf per instance, and the leaf labels can be set freely, so every labelling of all \(2^m\) instances is realised. No larger set exists, so the largest shattered set is \(X\) itself and \(\operatorname{VC}(H) = 2^m\). For \(m = 3\) that is 8 points with \(2^8 = 256\) labellings, all realised. It meets the finite-space ceiling: unrestricted trees represent all \(2^{2^m}\) Boolean functions, and \(\log_2 2^{2^m} = 2^m\). Unpruned trees are an unbiased learner, which is why depth limits and pruning matter.
If \(\operatorname{VC}(H) = d < \infty\), a consistent learner \(\varepsilon\)-exhausts the version space with probability at least \(1 - \delta\) from \[ m = O\!\left( \frac{1}{\varepsilon}\Big( d \log\frac{1}{\varepsilon} + \log\frac{1}{\delta} \Big) \right) \] examples. The VC dimension plays the role \(\ln|H|\) played in Haussler’s bound.
For binary classification with 0–1 loss, and in the sample-complexity sense (ignoring computation), the following are equivalent: \(H\) is agnostic PAC-learnable; \(H\) is PAC-learnable; \(H\) has finite VC dimension. In particular a class of infinite VC dimension is not PAC-learnable by any algorithm.
mistake bounds
The online model drops the distribution. Examples arrive one at a time in any order, possibly chosen by an adversary; the learner predicts each label, then sees the truth. A mistake bound caps the total number of wrong predictions over any sequence.
- Start with \(V = H\), assumed finite and to contain the target.
- For each arriving \(x\), predict the majority vote of the hypotheses in \(V\).
- Receive \(c(x)\) and delete from \(V\) every hypothesis that predicted wrongly.
The halving algorithm makes at most \(\lfloor \log_2 |H| \rfloor\) mistakes on any sequence.
A mistake means the majority of \(V\) was wrong, and all of them are deleted, so each mistake at least halves \(|V|\). The target is never deleted, so \(|V| \ge 1\) throughout. After \(M\) mistakes \(1 \le |H|/2^M\), so \(M \le \log_2|H|\), and \(M\) is an integer.
Take conjunctions over 5 Boolean features, \(|H| = 3^5 = 243\). Since \(2^7 = 128 \le 243 < 256 = 2^8\), halving makes at most \(\lfloor \log_2 243 \rfloor = 7\) mistakes, however long the stream. The bound is a worst case over adversarial orderings. Correct predictions can shrink \(V\) too, but only mistakes are guaranteed to halve it.
Halving is not practical, since it stores \(H\), but it sets the benchmark. Three results place the practical online learners against it; the statements are enough.
- Perceptron. Novikoff’s theorem is a mistake bound: on data with margin \(\gamma\) and radius \(R\) the perceptron makes at most \((R/\gamma)^2\) mistakes. \(H\) is infinite here; the margin replaces \(\log_2|H|\) as the complexity measure.
- Winnow (Littlestone, 1988) learns a linear threshold function with multiplicative updates: on a mistake, the weights of the active features are multiplied by \(\alpha > 1\) (a missed positive) or divided by \(\alpha\) (a false positive). If the target depends on only \(r\) of the \(n\) features, Winnow makes \(O(r \log n)\) mistakes, logarithmic in the number of irrelevant features, where the additive perceptron update can need a number linear in \(n\).
- Weighted Majority (Littlestone and Warmuth, 1994) predicts by a weighted vote of \(N\) experts and multiplies the weight of every expert that errs by \(\beta \in [0,1)\). If the best expert makes \(k\) mistakes, the algorithm makes at most \[ \frac{k \log_2(1/\beta) + \log_2 N}{\log_2\big(2/(1+\beta)\big)} \] mistakes, about \(2.41\,(k + \log_2 N)\) for \(\beta = \tfrac12\). With a perfect expert in the pool and \(\beta = 0\) it is the halving algorithm. Its multiplicative reweighting is the ancestor of Hedge and of AdaBoost’s weights on the ensembles page.
see also
- No free lunch: the qualitative case for inductive bias; the unbiased-learner bound above is its quantitative twin.
- The bias-variance decomposition: the same trade-off between a rich \(H\) and the data it needs, for squared error.
- Support vector machines: margin as capacity control; the VC risk bound is stated on Multivariate Analysis.
- Perceptrons: the full proof of Novikoff’s mistake bound.
- Decision trees: the unbiased hypothesis space that pruning restricts.
- Curse of dimensionality: the other reason sample sizes explode with \(n\).
Backlinks (8)
1. Multivariate Analysis /wiki/mathematics/statistics/multivariate/
2. No Free Lunch Theorem /wiki/ml/theory/no-free-lunch/
averaged over all possible problems, every learning algorithm is exactly as good as random guessing — and every optimiser is exactly as good as blind enumeration. 𐃏 this sounds like nihilism but is actually the sharpest possible argument for inductive bias: an algorithm can only beat chance on some problems by losing to chance on others, so the whole game of machine learning is choosing whose lunch to eat.
3. Perceptrons (Augmented with Gradient Descent) /wiki/ml/dl/perceptron/
the perceptron is the hydrogen atom of neural networks: one neuron, one weight vector, one threshold — and yet it already exhibits the two behaviours that define the whole field. 𐃏 it learns from mistakes with a provable convergence guarantee, and it fails on problems its geometry cannot express. this page covers both, then swaps the hard threshold for a sigmoid so that gradient descent can take over — a companion to the sign-loss perceptron page, which treats the classical algorithm on its own.
4. Support Vector Machines (SVMs) /wiki/ml/supervised/classification/svm/
a linearly separable dataset admits infinitely many separating hyperplanes, and the perceptron will happily hand you whichever one it trips over first. 𐃏 the support vector machine asks a better question: of all the hyperplanes that separate the data, which one is farthest from everybody? the answer — the maximum-margin hyperplane — is determined by a handful of boundary points (the support vectors), drops out of a beautiful convex dual, and generalises via the kernel trick from lines to nearly anything.
5. Decision Trees /wiki/ml/supervised/classification/decision-trees/
Entropy and Information Gain
The entropy of a dataset \(S\) with classes \(C\) is:
\[H(S) = -\sum_{c \in C} p_c \log_2(p_c)\]
where \(p_c\) is the proportion of examples belonging to class \(c\). Entropy is maximised when classes are equally distributed and zero when all examples belong to a single class.
The information gain of splitting dataset \(S\) on attribute \(A\) is:
\[\text{IG}(S, A) = H(S) - \sum_{v \in \text{Values}(A)} \frac{|S_v|}{|S|} H(S_v)\]
6. Perceptron /wiki/ml/supervised/classification/perceptron/
Origins
The perceptron learning algorithm is the most simple algorithm we have for Binary Classification.
It was introduced by Frank Rosenblatt in his seminal paper: “The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain” in 1958. The history however dates back further to the theoretical foundations of Warren McCulloch and Walter Pitts in 1943 and their paper “A Logical Calculus of the Ideas Immanent in Nervous Activity”. The interested reader may visit these links for annotations and the original pdfs.
7. chapter 3: improving the way neural networks learn /wiki/ml/dl/feedforward/ch3/
3.1 the cross entropy function
- we often learn fastest when we’re badly wrong about something
- the cross-entropy cost function is always negative (which is something you desire for a cost function)
\begin{equation} \label{eq:neuron_ce} C = -\frac{1}{n}\sum_x [y \ln a + (1-y)\ln(1-a)] \end{equation}
- note here that at a = 1, you’ll get
nan. we handle this in the code below. - this cost tends towards zero as the neuron gets better at computing the desired output y
- it also punishes bad guesses more harshly.
- the cross-entropy is nearly always the better choice, provided the output neurons are sigmoid neurons
- if the output neurons however are linear neurons, then the quadratic cost will not cause learning slowdown. you may use it.
- to find the learning rate \(\eta\) for log-reg, you can divide that of the lin-reg by 6.
- ch1 = 95.42 accuracy
- 100 hidden neurons \(\implies\) 96.82 percent.
- eliminated one in fourteen errors; pretty good!
- neuron saturation is an important problem in neural nets.
- cross-entropy is a measure of surprise
- ch5 Cover & Thomas
- a softmax output layer with log-likelihood cost is quite similar to a sigmoid output layer with cross-entropy cost.
- softmax plus log-likelihood is worth using whenever you want to interpret the output activations as probabilities.
3.2 overfitting and regularisation
8. Machine Learning /wiki/ml/
Type 1 error
subtrees
- probabilistic graphical models — bayesian and markov networks, inference, hmms, learning
Comments