Multiclass: One-vs-All, All-Pairs, Direct

How it works

1. One-vs-All: for each class i, relabel its points +1 and every other class −1, and train a binary linear classifier h_i (logistic regression by gradient descent).
2. All-Pairs: for each pair i < j, keep only the points of classes i and j, label i as +1 and j as −1, and train h_ij — k(k−1)/2 classifiers.
3. Combine: One-vs-All predicts the class with the largest score ⟨w_i,x⟩ + b_i, or (binary labels only) a class whose h_i says +1; All-Pairs gives each pairwise winner one vote and predicts the class with the most wins. Ties go to the smallest class and are reported.
4. Direct: one linear multiclass predictor h(x) = argmax_y ⟨w, ψ(x, y)⟩ with a score per class, trained by the multiclass Perceptron (w ← w + ψ(x, y) − ψ(x, ŷ) on each mistake).
5. Compare the combined prediction regions and training errors: with three bands side by side, the middle class cannot be separated from the rest, so One-vs-All by binary labels loses it, while All-Pairs and the direct predictor classify every point.

Default run (8 steps): One-vs-All with 3 classes: train 3 binary classifiers, one per class, each separating that class from all the remaining classes. The binary learner is logistic regression trained by 100 gradient-descent iterations (η = 0.5). … Combine: predict the class whose classifier gives the largest score ⟨w_i,x⟩ + b_i (ties go to the smallest class). Result on the training points: no training errors.