Theorem 4.9: if C is weakly PAC learnable using H then C is strongly PAC learnable using ternary majority trees over H
ProvedComputationalLearning.weak_strong_equivalenceTheorem 4.9. Let be any concept class and any hypothesis class. Then if is efficiently weakly PAC learnable using , is efficiently strongly PAC learnable using a hypothesis class of ternary majority trees with leaves from .
Formally (sample-complexity sense): if is weakly learnable using measurable hypotheses in (some constant advantage , confidence , sample size , by an algorithm jointly measurable in the sample and the instance, uniformly over measurable targets in and all distributions), then is PAC learnable using the class of ternary majority trees with leaves from : for all there are a sample size and a learning algorithm outputting majority trees over with error greater than with probability at most , for every measurable target in and every distribution. The algorithm is Strong-Learn of §4.3.3 (recursive modest boosting on filtered distributions sampled by rejection from the sample) with the confidence boosting of §4.2; its polynomial running time is not formalized.
Why the learner is measurable. Strong-Learn runs on distributions filtered through 's own earlier hypotheses, so its analysis conditions on the earlier samples and integrates. For an arbitrary function that integral need not exist. Outer-measure bounds on the separate runs do not combine: there are sets, under the continuum hypothesis, whose sections all have measure while the whole has full outer measure. The book's weak learner is an algorithm, and every algorithm is measurable.
import Definitions.Def_ComputationalLearning_Boosting open MeasureTheory ProbabilityTheory
namespace ComputationalLearning
/-- **Theorem 4.9** (p. 100). Let `C` be any concept class and `H` any hypothesis class. Then if
`C` is efficiently weakly PAC learnable using `H`, `C` is efficiently strongly PAC learnable using
a hypothesis class of ternary majority trees with leaves from `H`. Stated in the
sample-complexity sense: if for some constant advantage `γ > 0`, confidence `δ₀ > 0` and sample
size a jointly measurable algorithm outputs hypotheses in `H` with error at most `1/2 − γ` with probability at
least `δ₀`, for every measurable target in `C` and every distribution, then `C` is PAC learnable
using the class of ternary majority trees over `H` (the recursive accuracy boosting of §4.3
with the confidence boosting of §4.2; running time is not modelled). -/
theorem weak_strong_equivalence {X : Type*} [MeasurableSpace X] (C H : Set (X → Bool))
(hH : ∀ h ∈ H, Measurable h) (hweak : WeaklyLearnable C H) :
PACLearnable C (majorityTrees H) := by sorry
end ComputationalLearning
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.