Corollary 1, p. 346 — on a region where F is constant, the average of e^{−y_i c} is minimized at c = ½ log(n₊/n₋), matching the sample proportions
ProvedAddLogReg.ExpCrit.corollary_1Let be the labels of the observations in a region of feature space on which takes a constant value (for example a terminal node of a decision tree), and suppose both labels occur. Let and be the numbers of labels equal to and , and put
Then
- minimizes the average exponential criterion over the region: for every real ,
- the sample proportions are given by the symmetric logistic transform of :
This is the sample version of Lemma 1: replacing the expectation by averages over a region gives the same minimizer with sample proportions in place of conditional probabilities. It is what the data versions of the boosting algorithms compute in each terminal node.
Formalization Note The averages are written with the factor , as in the corollary's "averages". The requirement that both labels occur is the sample counterpart of : without it the logarithm is of or a division by , and no minimizer exists.
import Mathlib import Definitions.Def_AddLogReg_ExpCrit_Setting open MeasureTheory ProbabilityTheory
namespace AddLogReg.ExpCrit
/-- Corollary 1 (p. 346): with `E` replaced by the average over a region where `F` is a
constant `c` (labels `y_1, …, y_n`, both classes present), the average of `e^{−y_i c}` is
minimized at `c = ½ log(n₊/n₋)`, and the sample proportions of `y = 1` and `y = −1` are
`e^{c}/(e^{−c} + e^{c})` and `e^{−c}/(e^{−c} + e^{c})`. -/
theorem corollary_1 (n : ℕ) (y : Fin n → Bool) (hpos : ∃ i, y i = true)
(hneg : ∃ i, y i = false) :
let npos : ℕ := (Finset.univ.filter (fun i => y i = true)).card
let nneg : ℕ := (Finset.univ.filter (fun i => y i = false)).card
let c : ℝ := (1 / 2) * Real.log ((npos : ℝ) / nneg)
(∀ c' : ℝ, (1 / (n : ℝ)) * ∑ i, Real.exp (-(sgn (y i) * c)) ≤
(1 / (n : ℝ)) * ∑ i, Real.exp (-(sgn (y i) * c'))) ∧
(npos : ℝ) / n = Real.exp c / (Real.exp (-c) + Real.exp c) ∧
(nneg : ℝ) / n = Real.exp (-c) / (Real.exp (-c) + Real.exp c) := by sorry
end AddLogReg.ExpCrit
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.