Multiclass Strategies: OvR/OvO/Softmax

three main strategies extend binary classifiers to $K$ classes. OvR (one-vs-rest): train $K$ 'class-vs-others' classifiers and predict by the highest score, $O(K \cdot d)$ parameters; OvO (one-vs-one): train $\binom{K}{2} = \frac{K(K-1)}{2}$ pairwise classifiers and vote, simpler per model but $O(K^2)$ total cost; Softmax (direct multiclass): a single model outputs $K$-dim probabilities $p_i = \frac{e^{z_i/\tau}}{\sum_{j=1}^{K} e^{z_j/\tau}}$, with temperature $\tau$ controlling smoothness — $\tau \to 0$ collapses to argmax, $\tau \to \infty$ approaches uniform; with cross-entropy the gradient is still $p - y$ (Softmax is the multiclass logistic regression).

interview comparisons of the three (model count / parameters / expressiveness), the role of $\tau$ in knowledge distillation and probability calibration, and why OvR scores are not probabilities.

OvR trains each class against 'the rest', suffers severe class imbalance, and the $K$ scores are not comparable (need calibration, e.g. Platt scaling); OvO's model count explodes as $\binom{K}{2}$ ($K=100$ → 4950 models) with possible voting ties; Softmax trains one model end-to-end and natively outputs valid probabilities, but assumes mutually exclusive classes (use multiple binary classifiers otherwise). Temperature additionally shapes the distribution: distillation uses $\tau > 1$ to soften labels and transfer dark knowledge (inference at $\tau = 1$); $\tau$ also affects confidence and calibration.

OvR vs OvO: number of models ($K$ vs $\frac{K(K-1)}{2}$), training/inference cost, tie-breaking; how many models for $K=100$?

Role of Softmax temperature $\tau$: derive the limits as $\tau \to 0$ and $\tau \to \infty$; why use $\tau > 1$ in distillation?

Whiteboard the Softmax + cross-entropy gradient $\frac{\partial L}{\partial z_i} = p_i - y_i$ and show it generalizes binary LR.

Why aren't OvR scores probabilities? How to calibrate (Platt scaling / Isotonic) and how does calibration differ from AUC?

The mutual-exclusion assumption: what tasks fit Softmax, why do multi-label tasks use per-class Sigmoid? When to pick OvR vs OvO vs Softmax?