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 , its error is at most . 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 , weights , and for :
and the final classifier is the weighted vote , with the normalising constant. Three readings of the same update:
Reweighting. A point that the current rule gets wrong gets its weight multiplied by ; a point it gets right is down-weighted. The next weak learner is forced to concentrate on the mistakes of the previous ones.
A vote. is the weight of the expert: zero for an error of , growing without bound as . A perfect rule would get infinite weight, which is why in practice is clipped away from 0.
Gradient descent. AdaBoost is forward stagewise minimisation of the exponential loss over , one coordinate at a time. That is the same “fit the negative gradient” idea as the gradient descent page, with a different loss.
The classical guarantee is the training-error bound , which is at most ; if every the product decays geometrically and the training error reaches zero in 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 items and a set of pairwise comparisons (“ beats ”), the task is a global order.
Borda count. Each voter ranks the items; item receives the sum of its ranks (or of ), and the items are sorted by that score. Equivalently, item gets one point for every item it beats in every voter’s list, so the Borda score of is .
Pairwise matrix. Collect the results in a matrix with = number of voters who prefer to . Then , and the row sums of are the Borda scores. Ranking is now a matrix problem: a score vector is the stationary object of , which is exactly the PageRank computation of the random-walks page when is normalised row by row.
The catch. No method is simultaneously faithful to all pairwise majorities (Arrow’s theorem for social choice, and the Condorcet paradox below), so “the” ranking always involves a choice of aggregation. Saying which axiom you are willing to lose is part of the modelling.
4. Voting rules and their paradoxes¶
| Rule | Aggregates | Fails |
|---|---|---|
| plurality | first places only | a Condorcet winner can lose |
| Borda | full ranking | irrelevant alternatives can change the outcome |
| pairwise majority | each pair | can be cyclic (Condorcet paradox) |
| PageRank on the comparison graph | weighted votes, damped | sensitive to the damping factor |
Condorcet paradox. Three voters, three candidates: , , . Pairwise, beats , beats , beats : 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¶
Trace three rounds of AdaBoost by hand on four two-dimensional points, computing the weights, the error and at each round. Verify that the training error reaches zero.
Show that the exponential loss upper-bounds the 0–1 loss, and explain why minimising the former is a sensible surrogate.
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.
Verify that AdaBoost’s weight update keeps , and compute in closed form for a two-class problem with known.
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.
Write the Borda scores as a row sum of the pairwise matrix , and explain what happens to them when a candidate is removed from every ballot. Which axiom of Arrow’s list does that violate?
Sources¶
Blum, Hopcroft, Kannan, Foundations of Data Science, selected sections.
Freund, Y. and Schapire, R., “A decision-theoretic generalization of on-line learning and an application to boosting”, JCSS 55(1), 1997.
Hastie, Tibshirani, Friedman, The Elements of Statistical Learning, 2nd ed., Ch. 10 (boosting as stagewise additive modelling).
Langville, A. and Meyer, C., Google’s PageRank and Beyond, Ch. 1–2 (ranking from pairwise data).