Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Boosting Sketch, Ranking, and Voting

(For other courses)

This page is a survey, not a session: it collects the three places where “combining many weak decisions” appears in the course — boosting a classifier, aggregating a ranking, and voting — and it shows that the three are the same kind of object, an average of experts with weights.

1. From weak to strong

A weak learner is a rule that does slightly better than chance on any distribution over the data: for some γ>0\gamma>0, its error is at most 12−γ\tfrac12-\gamma. A strong learner can reach any target error with enough data. The surprising fact of boosting (Kearns’ question, answered by Schapire in 1990) is that the two are equivalent: a weak learner repeated on reweighted data produces a strong one. Boosting is therefore not a new hypothesis class; it is a way of turning a small class into a large one, and its complexity is controlled by the number of rounds, not by the dimension.

2. AdaBoost in five lines

Labels yi∈{−1,+1}y_i\in\{-1,+1\}, weights D1(i)=1/nD_1(i)=1/n, and for t=1,…,Tt=1,\dots,T:

εt=∑iDt(i) 1{ht(xi)≠yi},αt=12log⁡1−εtεt,Dt+1(i)=Dt(i) e−αtyiht(xi)Zt,\varepsilon_t=\sum_i D_t(i)\,\mathbb{1}\{h_t(x_i)\neq y_i\}, \qquad \alpha_t=\tfrac12\log\frac{1-\varepsilon_t}{\varepsilon_t}, \qquad D_{t+1}(i)=\frac{D_t(i)\,e^{-\alpha_t y_i h_t(x_i)}}{Z_t},

and the final classifier is the weighted vote H(x)=sign⁡(∑tαtht(x))H(x)=\operatorname{sign}\big(\sum_t\alpha_t h_t(x)\big), with ZtZ_t the normalising constant. Three readings of the same update:

The classical guarantee is the training-error bound L^n(H)≤∏t2εt(1−εt)\hat L_n(H)\le \prod_t 2\sqrt{\varepsilon_t(1-\varepsilon_t)}, which is at most 2T∏tεt2^T\prod_t\sqrt{\varepsilon_t}; if every εt≤12−γ\varepsilon_t\le \tfrac12-\gamma the product decays geometrically and the training error reaches zero in O(log⁡n/γ2)O(\log n/\gamma^2) rounds. Note what the bound does not say: it is about training error, and boosting can overfit when the weak learners are too strong or the data are noisy.

3. Ranking as a linear-algebra problem

Given nn items and a set of pairwise comparisons (“ii beats jj”), the task is a global order.

4. Voting rules and their paradoxes

RuleAggregatesFails
pluralityfirst places onlya Condorcet winner can lose
Bordafull rankingirrelevant alternatives can change the outcome
pairwise majorityeach paircan be cyclic (Condorcet paradox)
PageRank on the comparison graphweighted votes, dampedsensitive to the damping factor

Condorcet paradox. Three voters, three candidates: A≻B≻CA\succ B\succ C, B≻C≻AB\succ C\succ A, C≻A≻BC\succ A\succ B. Pairwise, AA beats BB, BB beats CC, CC beats AA: the majority relation has a cycle, so no total order agrees with it. This is the same phenomenon as a non-transitive tournament, and it is why the PageRank fix (damping, which makes the walk ergodic) is not a technicality but a modelling assumption.

5. Why this page is a survey

Boosting, ranking and voting each deserve a course. Here they appear for three reasons: the exponential-loss view of section 2 closes the loop with gradient descent; section 3 is the one place where a matrix of pairwise data replaces a matrix of features, which is the “data as a graph” idea of the random-graphs chapter; and section 4 warns that “combine the numbers and sort” is a modelling decision with axioms attached. The exercises below are the intended use of the page.

Exercises

  1. Trace three rounds of AdaBoost by hand on four two-dimensional points, computing the weights, the error εt\varepsilon_t and αt\alpha_t at each round. Verify that the training error reaches zero.

  2. Show that the exponential loss ∑ie−yiF(xi)\sum_i e^{-y_iF(x_i)} upper-bounds the 0–1 loss, and explain why minimising the former is a sensible surrogate.

  3. Treat PageRank as a voting rule on a four-node graph: compute the stationary distribution with and without damping, and describe how one high-degree node changes the ranking.

  4. Verify that AdaBoost’s weight update keeps ∑iDt+1(i)=1\sum_i D_{t+1}(i)=1, and compute ZtZ_t in closed form for a two-class problem with εt\varepsilon_t known.

  5. Construct a profile of five voters and four candidates with a Condorcet cycle, then compute the Borda ranking and show that it disagrees with the pairwise majority on at least one pair.

  6. Write the Borda scores as a row sum of the pairwise matrix WW, and explain what happens to them when a candidate is removed from every ballot. Which axiom of Arrow’s list does that violate?

Sources