ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Two AdaBoost rounds with normalized weights

Example

Take four observations with labels $(+ 1, + 1, - 1, - 1)$ , first classifier predictions $(+ 1, + 1, + 1, - 1)$ , and second classifier predictions $(- 1, + 1, - 1, - 1)$ . The two weighted errors are $1 / 4$ and $1 / 6$ ; the normalized weights after the first and second rounds are $(1 / 6, 1 / 6, 1 / 2, 1 / 6)$ and $(1 / 2, 1 / 10, 3 / 10, 1 / 10)$ . The final margins are $(\frac{1}{2} \log (3 / 5), \frac{1}{2} \log (15), \frac{1}{2} \log (5 / 3), \frac{1}{2} \log (15))$ , so one of four examples has nonpositive margin. The normalizer product is $\sqrt{15} / 6$ , which bounds the empirical nonpositive-margin fraction.

Facts & Assumptions

Given: The four labels and two classifier prediction vectors stated in the Example.

[F1]

Finite-sample AdaBoost.M1 with half-log coefficients: For $0 < e_{m} < 1 / 2$ , the algorithm uses $a_{m} = \frac{1}{2} \log ((1 - e_{m}) / e_{m})$ , $Z_{m} = 2 \sqrt{e_{m} (1 - e_{m})}$ , the normalized update $w_{i}^{(m + 1)} = w_{i}^{(m)} e^{- a_{m} y_{i} h_{m} (x_{i})} / Z_{m}$ , and $F_{m} = F_{m - 1} + a_{m} h_{m}$ .

[F2]

AdaBoost's exponential training-loss and nonpositive-margin bound: For completed weak rounds, the fraction with nonpositive margin is at most $\prod_{m} Z_{m}$ .

Verification

1.1givenF1algebra

Initially each weight is $1 / 4$ . The first classifier misclassifies only observation $3$ , so $e_{1} = 1 / 4$ , $a_{1} = \frac{1}{2} \log 3$ , and $Z_{1} = \sqrt{3} / 2$ .

2.1F1step 1.1algebra

The first update gives weight $(1 / 4) e^{a_{1}} / Z_{1} = 1 / 2$ to observation $3$ and weight $(1 / 4) e^{- a_{1}} / Z_{1} = 1 / 6$ to each other observation, hence $w^{(2)} = (1 / 6, 1 / 6, 1 / 2, 1 / 6)$ .

3.1givenF1step 2.1algebra

Under $w^{(2)}$ , the second classifier misclassifies only observation $1$ , so $e_{2} = 1 / 6$ , $a_{2} = \frac{1}{2} \log 5$ , and $Z_{2} = \sqrt{5} / 3$ .

4.1F1step 3.1algebra

The second update gives weight $1 / 2$ to observation $1$ , $1 / 10$ to observations $2$ and $4$ , and $3 / 10$ to observation $3$ , so $w^{(3)} = (1 / 2, 1 / 10, 3 / 10, 1 / 10)$ .

5.1F1F2step 1.1step 3.1algebra∎

The margins $y_{i} F_{2} (x_{i})$ are respectively $a_{1} - a_{2} = \frac{1}{2} \log (3 / 5) < 0$ , $a_{1} + a_{2} = \frac{1}{2} \log 15 > 0$ , $a_{2} - a_{1} = \frac{1}{2} \log (5 / 3) > 0$ , and $a_{1} + a_{2} > 0$ . Thus the nonpositive-margin fraction is $1 / 4$ , while $Z_{1} Z_{2} = \sqrt{15} / 6$ and $1 / 4 \leq \sqrt{15} / 6$ . By [F2] this is within the theorem's empirical bound.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · one level

2 results within one dependency step of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.