Learning theory — what can be learned from data

Parent: math

Computational & statistical learning theory: the mathematics of generalization — when do finitely many examples pin down a rule that works on unseen data?

The trap that makes it non-trivial. Infinitely many rules fit any finite sample equally well — you can always match the seen points and be wrong everywhere else. So learning is impossible unless you restrict your hypotheses in advance (an inductive bias). This field draws the exact boundary between what such a restricted class can and cannot learn.

The setup (every note below uses these symbols)

The objects

• inputs live in a space X (points, emails, images); each has a true label, say + or −.
• the target c is the unknown true rule c: X → {+,−} — what you're trying to learn.
• inputs arrive from an unknown distribution D; your sample is m labeled examples (x₁,y₁), …, (xₘ,yₘ) drawn independently from D.
• you fix a hypothesis class H in advance — the menu of candidate rules you're willing to consider (this is your bias): e.g. all straight-line boundaries, or all axis-aligned rectangles, or all depth-≤5 decision trees. A hypothesis h ∈ H is one such rule, a function h: X → {+,−} (input → predicted label). Learning = pick the best h from the menu H.
• the generalization error err(h) = the probability, over a fresh x drawn from D, that h(x) ≠ c(x) (how often h disagrees with the truth on unseen data).
• ε = the accuracy you demand (err ≤ ε); δ = the confidence (allowed chance of failing); m = the sample size.

The goal: from the sample alone, pick h ∈ H with small err(h) — and be able to guarantee it.

Hypothesis class

Fix an instance space $X$ and binary label set $Y = \{+,-\}$. A hypothesis is a function $h : X \to Y$. A hypothesis class is a subset of the function space

$$H \;\subseteq\; Y^X \;:=\; \{\, f \mid f : X \to Y \,\},$$

so h ∈ H is ordinary set membership. Equivalently, identifying each $h$ with the set $h^{-1}(+) = \{\, x \in X : h(x) = + \,\}$, a class is a family of subsets $H \subseteq 2^X$; the pair $(X, H)$ is the range space / set system of Vapnik–Chervonenkis theory.

Here "class" is loose terminology for that set / family — not a set-theory proper class. H may be infinite (all thresholds, all lines) yet is still an ordinary set; finite VC dimension keeps it effectively small (Sauer–Shelah: O(nᵈ) labelings on n points, not 2ⁿ).

Notes

• pac — Valiant's framework: learn approximately (error ≤ ε) probably (prob ≥ 1−δ), from a polynomial number of samples.
• vc-dimension — the capacity of a hypothesis class; the fundamental theorem PAC-learnable ⟺ finite VC dimension.
• no-free-lunch — no universal learner exists; learning requires a prior bias — and that bias cannot itself be learned.

The one boundary to remember

Learnable ⟺ finite capacity (VC). Too little flexibility can't fit the truth; too much flexibility can't generalize (it fits any labeling, including noise). Learning lives in the middle, and the amount of data you need scales with the capacity you allow.