§5.2: the conjunction of all significant, non-harmful literals has error at most ε/2 (the analysis behind Theorem 5.2)
ProvedComputationalLearning.statistics_conjunction_errorboolean-conjunctionsstatistical-queriesunion-bound
§5.2 (p. 107). We say that is significant if and harmful if . We now argue that if is the conjunction of all the significant literals that are not harmful, then has error less than with respect to and : is at most the probability that some insignificant literal is in , at most by the union bound; is at most the probability that some harmful literal is in with , at most ; thus .
Formally: for every target conjunction over , every distribution on and , the conjunction of the significant non-harmful literals has error at most with respect to and . This is the exact-probability content of Theorem 5.2 (conjunctions are learnable from statistical queries with tolerance ).
Preamble
import Definitions.Def_ComputationalLearning_Noise open MeasureTheory ProbabilityTheory
Formal statement
namespace ComputationalLearning
/-- **Learning conjunctions from statistics** (§5.2, p. 107; the analysis behind Theorem 5.2). For
a target conjunction `c` over `x₁, …, xₙ`, a distribution `D` and `ε > 0`, if `h` is the
conjunction of all the significant literals (`p₀(z) ≥ ε/8n`) that are not harmful
(`p₀₁(z) < ε/8n`), then `error(h) ≤ ε/4 + ε/4 = ε/2`: a false positive requires an insignificant
literal of `c` to be `0`, a false negative a harmful literal of `h` to be `0` on a positive
example, and the union bound over the `2n` literals gives `ε/4` each. -/
theorem statistics_conjunction_error {n : ℕ} (T : Conjunction (Fin n)) (D : Measure (Cube (Fin n)))
[IsProbabilityMeasure D] {ε : ℝ} (hε : 0 < ε) :
errorOf D (evalConj T) (evalConj (statisticsConj D (evalConj T) ε)) ≤ ε / 2 := by sorry
end ComputationalLearning
Source
Kearns and Vazirani, An Introduction to Computational Learning Theory, MIT Press 1994, doi:10.7551/mitpress/3897.001.0001, §5.2 pp. 106-108, the algorithm for learning conjunctions from statistics and its error analysis
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.