Theorem 2.1 (Occam's Razor): an (α, β)-Occam algorithm is a PAC learning algorithm, with explicit sample-size conditions
ProvedComputationalLearning.occam_razoroccam-learningpac-learningsample-complexity
Theorem 2.1 (Occam's Razor). Let be an efficient -Occam algorithm for using . Let be the target distribution, the target concept and . Then there is a constant such that if is given a random sample of examples with , then with probability at least the output of satisfies .
Formally: hypotheses are binary strings with a representation map to measurable concepts; maps samples of size to strings; on every sample labeled by its output represents a consistent hypothesis and has length at most ( bounding , , ). If , and , then the probability that has error greater than is at most . These explicit conditions instantiate the book's constant ; efficiency is not modelled.
Preamble
import Definitions.Def_ComputationalLearning_Occam open MeasureTheory
Formal statement
namespace ComputationalLearning
/-- **Theorem 2.1 (Occam's Razor)** (p. 34). Let `L` be an `(α, β)`-Occam algorithm for `C`
using `H`: on a sample of `m` examples labeled by `c ∈ Cₙ` it outputs a representation (a binary
string) of a hypothesis consistent with the sample of bit length at most `(n · size(c))^α m^β`,
`α ≥ 0`, `0 ≤ β < 1`. Then there is a constant `a > 0` such that if `L` is given a random sample of
`m ≥ a((1/ε) log(1/δ) + ((n · size(c))^α/ε)^{1/(1−β)})` examples, with probability at least
`1 − δ` its hypothesis has error at most `ε`. Stated with the explicit sufficient conditions
`m ≥ (2/ε) ln(1/δ)`, `m ≥ 4 ln 2/ε` and `m^{1−β} ≥ (4 ln 2/ε)(n s)^α`, where `s` bounds
`size(c)` (they make `2^{K+1}(1 − ε)^m ≤ δ` for `K = (n s)^α m^β`, the number of binary strings
of length at most `K` being less than `2^{K+1}`). -/
theorem occam_razor {X : Type*} [MeasurableSpace X] (c : X → Bool) (hc : Measurable c)
(D : Measure X) [IsProbabilityMeasure D] (R : List Bool → X → Bool)
(hR : ∀ r, Measurable (R r)) (n s : ℕ) {α β : ℝ} (hα : 0 ≤ α) (hβ0 : 0 ≤ β) (hβ : β < 1)
{ε δ : ℝ} (hε : 0 < ε) (hε1 : ε ≤ 1) (hδ : 0 < δ) (hδ1 : δ < 1) (m : ℕ)
(L : (Fin m → X × Bool) → List Bool)
(hcons : ∀ S, IsLabeledBy c S → IsConsistent (R (L S)) S)
(hsize : ∀ S, IsLabeledBy c S →
((L S).length : ℝ) ≤ ((n * s : ℕ) : ℝ) ^ α * (m : ℝ) ^ β)
(hm1 : 2 / ε * Real.log (1 / δ) ≤ m) (hm2 : 4 * Real.log 2 / ε ≤ m)
(hm3 : 4 * Real.log 2 / ε * ((n * s : ℕ) : ℝ) ^ α ≤ (m : ℝ) ^ (1 - β)) :
sampleLaw D c m {S | ε < errorOf D c (R (L S))} ≤ ENNReal.ofReal δ := by sorry
end ComputationalLearning
Source
Kearns and Vazirani, An Introduction to Computational Learning Theory, MIT Press 1994, doi:10.7551/mitpress/3897.001.0001, §2.1 pp. 33-37, Definition 6 and Theorem 2.1 with its proof from Theorem 2.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.