Exercise 10.3: the error of hₜ with respect to the updated distribution D⁽ᵗ⁺¹⁾ is exactly 1/2
ProvedUnderstandingML.adaboost_reweighted_erroradaboostboosting
Exercise 10.3. The AdaBoost weighting mechanism forces the weak learner to focus on the problematic examples: the error of with respect to the distribution is exactly , that is, for every , .
Formally: for a nonempty sample and , the weighted error of under adaDist S h (t+1) equals .
Preamble
import Definitions.Def_UnderstandingML_Boosting open MeasureTheory
Formal statement
namespace UnderstandingML
/-- **Exercise 10.3** (p. 143). The error of `hₜ` with respect to the updated distribution
`D⁽ᵗ⁺¹⁾` is exactly `1/2`: `∑ᵢ Dᵢ⁽ᵗ⁺¹⁾ 𝟙[yᵢ ≠ hₜ(xᵢ)] = 1/2`. Stated for a nonempty sample and
`εₜ ∈ (0, 1)`, where the weight `wₜ` is defined. -/
theorem adaboost_reweighted_error {X : Type*} {m : ℕ} (hm : 0 < m) (S : Fin m → X × Bool)
(h : ℕ → X → Bool) (t : ℕ) (hε : 0 < adaError S h t ∧ adaError S h t < 1) :
weightedError (adaDist S h (t + 1)) S (h t) = 1 / 2 := by sorry
end UnderstandingML
Source
Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press 2014, doi:10.1017/CBO9781107298019, §10.7 Exercise 10.3 pp. 142-143
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.