p. 117: the probability that h disagrees with the noisy label is γ_h = η + (1 − 2η) error(h)
ProvedComputationalLearning.noisy_disagreementclassification-noisehypothesis-selection
p. 117. If we define (the probability disagrees with the label provided by the noisy oracle), then , and .
Formally: for a distribution , measurable and , and , the probability under the noisy example law that equals .
Preamble
import Definitions.Def_ComputationalLearning_Noise open MeasureTheory ProbabilityTheory
Formal statement
namespace ComputationalLearning
/-- **The disagreement probability under noise** (§5.4.3, p. 117). If `γ_h` is the probability that
`h` disagrees with the label provided by the noisy oracle, then
`γ_h = (1 − η) error(h) + η (1 − error(h)) = η + (1 − 2η) error(h)`; hence
`γ_{h_i} − γ_{h_j} = (1 − 2η)(error(h_i) − error(h_j))`, and the hypothesis with the smallest
estimated `γ` has the smallest error. -/
theorem noisy_disagreement {X : Type*} [MeasurableSpace X] (D : Measure X)
[IsProbabilityMeasure D] (c h : X → Bool) (hc : Measurable c) (hh : Measurable h) {η : ℝ}
(hη0 : 0 ≤ η) (hη1 : η ≤ 1) :
(noisyExampleLaw D c η {p | h p.1 ≠ p.2}).toReal = η + (1 - 2 * η) * errorOf D c h := 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.4.3 p. 117, the identity used to select the best hypothesis among the simulations
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.