§2.2: by Occam's Razor the elimination algorithm needs only m ≥ (1/ε)(ln(3ⁿ + 1) + ln(1/δ)) examples
ProvedComputationalLearning.conjunctions_occam_bound§2.2 (p. 38). The elimination algorithm always outputs a conjunction consistent with its sample, so it is an Occam algorithm; the number of conjunctions over is bounded by (each variable occurs positively or negatively or is absent), so applying Theorem 2.2, examples are sufficient to guarantee that the hypothesis has error less than with confidence at least , an improvement by a logarithmic factor over Chapter 1.
Formally: for every target conjunction , every distribution on , , and , the probability that the elimination hypothesis has error greater than is at most . The count includes the empty concept, which the elimination algorithm outputs (as a contradictory conjunction) on a sample without positive examples.
import Definitions.Def_ComputationalLearning_Occam open MeasureTheory
namespace ComputationalLearning
/-- **§2.2, the improved sample size for conjunctions** (pp. 37–38). The elimination algorithm is
an Occam algorithm for conjunctions, and the hypothesis class it uses has at most `3ⁿ + 1`
concepts (each variable positive, negated or absent, plus the empty concept of a contradictory
conjunction); by Theorem 2.2, `m ≥ (1/ε)(ln(3ⁿ + 1) + ln(1/δ))`, i.e.
`O((1/ε) log(1/δ) + n/ε)`, examples suffice for error at most `ε` with confidence `1 − δ`, a
logarithmic improvement over the bound of Chapter 1. -/
theorem conjunctions_occam_bound {n : ℕ} (T : Conjunction (Fin n)) (D : Measure (Cube (Fin n)))
[IsProbabilityMeasure D] {ε δ : ℝ} (hε : 0 < ε) (hε1 : ε ≤ 1) (hδ : 0 < δ) (m : ℕ)
(hm : 1 / ε * (Real.log (3 ^ n + 1) + Real.log (1 / δ)) ≤ m) :
sampleLaw D (evalConj T) m {S | ε < errorOf D (evalConj T) (evalConj (eliminate S))} ≤
ENNReal.ofReal δ := by sorry
end ComputationalLearning
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.