Lemma 4.1: if h₁, h₂, h₃ have error ≤ β on D, D₂, D₃, then majority(h₁, h₂, h₃) has error ≤ g(β) = 3β² − 2β³ on D
ProvedComputationalLearning.modest_boostingboostingmajority-voteprobability
Lemma 4.1. Let . Let the distributions , and be as defined above, and let and satisfy , and . Then if , .
Formally: for a probability measure , measurable , , with and (a conditional on a null event being the zero measure), the three error bounds imply . The degenerate cases (a null conditioning event) are covered: verified exhaustively on random distributions over up to five points, all hypothesis triples, no violation.
Preamble
import Definitions.Def_ComputationalLearning_Boosting open MeasureTheory ProbabilityTheory
Formal statement
namespace ComputationalLearning
/-- **Lemma 4.1** (p. 82). Let `g(β) = 3β² − 2β³`. Let the distributions `D`, `D₂` and `D₃` be as
defined in §4.3.1 (`D₂` filters `D` through `h₁`, `D₃` conditions `D` on `h₁ ≠ h₂`), and let
`h₁, h₂, h₃` satisfy `error_D(h₁) ≤ β`, `error_{D₂}(h₂) ≤ β` and `error_{D₃}(h₃) ≤ β`. Then, for
`h = majority(h₁, h₂, h₃)`, `error_D(h) ≤ g(β)`. Stated for `0 ≤ β ≤ 1/2` and measurable
`c, h₁, h₂, h₃`; when a conditioning event is null the corresponding filtered measure is the zero
measure (or has mass `1/2`), and the bound still holds. -/
theorem modest_boosting {X : Type*} [MeasurableSpace X] (D : Measure X) [IsProbabilityMeasure D]
(c h₁ h₂ h₃ : X → Bool) (hc : Measurable c) (h₁m : Measurable h₁) (h₂m : Measurable h₂)
(h₃m : Measurable h₃) {β : ℝ} (hβ0 : 0 ≤ β) (hβ : β ≤ 1 / 2)
(e₁ : errorOf D c h₁ ≤ β) (e₂ : errorOf (filtered2 D c h₁) c h₂ ≤ β)
(e₃ : errorOf (filtered3 D h₁ h₂) c h₃ ≤ β) :
errorOf D c (majority3 h₁ h₂ h₃) ≤ boostFun β := by sorry
end ComputationalLearning
Source
Kearns and Vazirani, An Introduction to Computational Learning Theory, MIT Press 1994, doi:10.7551/mitpress/3897.001.0001, §4.3.1-4.3.2 pp. 79-85, Lemma 4.1 with its proof (Equations (4.1)-(4.7))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.