Theorem 1.2: conjunctions of boolean literals are PAC learnable by the elimination algorithm with m ≥ (2n/ε)(ln 2n + ln(1/δ)) examples
ProvedComputationalLearning.conjunctions_pac_learnableTheorem 1.2. The representation class of conjunctions of boolean literals is efficiently PAC learnable.
Formally (sample-complexity sense, with the book's algorithm and bound, p. 17): for every target conjunction over , every distribution on , , and
the elimination hypothesis (all literals not contradicted by a positive example of the sample) is consistent with every sample labeled by ; the probability, under the law of independent labeled examples from , that the elimination hypothesis has error greater than is at most ; and the class of conjunctions is PAC learnable using conjunctions. The proof of p. 17: the hypothesis contains the literals of so never errs on negatives; its error is at most with ; a bad literal () survives with probability at most , and the union bound over literals gives .
import Definitions.Def_ComputationalLearning_PAC open MeasureTheory
namespace ComputationalLearning
/-- **Theorem 1.2** (p. 16). The representation class of conjunctions of boolean literals is
(efficiently) PAC learnable, by the elimination algorithm: for every target conjunction `T` over
`x₁, …, xₙ`, every distribution `D` on `{0,1}ⁿ` and `ε, δ > 0`, the elimination hypothesis is
consistent with every sample labeled by `T`, and with `m ≥ (2n/ε)(ln(2n) + ln(1/δ))` examples it
has error greater than `ε` with probability at most `δ` (the bound of p. 17); hence conjunctions
are PAC learnable using conjunctions in the sample-complexity sense. -/
theorem conjunctions_pac_learnable {n : ℕ} (T : Conjunction (Fin n)) (D : Measure (Cube (Fin n)))
[IsProbabilityMeasure D] {ε δ : ℝ} (hε : 0 < ε) (hδ : 0 < δ) (hδ1 : δ < 1) (m : ℕ)
(hm : 2 * n / ε * (Real.log (2 * n) + Real.log (1 / δ)) ≤ m) :
(∀ S : Fin m → Cube (Fin n) × Bool, IsLabeledBy (evalConj T) S →
IsConsistent (evalConj (eliminate S)) S) ∧
sampleLaw D (evalConj T) m {S | ε < errorOf D (evalConj T) (evalConj (eliminate S))} ≤
ENNReal.ofReal δ ∧
PACLearnable (conjunctionClass (Fin n)) (conjunctionClass (Fin n)) := by sorry
end ComputationalLearning
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.