Machine Learning Reductions & Mother Algorithms, Part II: Multiclass to Binary Classification

Following our introductory Part I on ML reductions & mother algorithms, let's talk about a classic reduction: one-against-all (OAA) -- also known as one-vs-all (OVA) and one-vs-rest (OVR). Unfortunately, it's seen in some circles as too simple, with dissidents pointing to the problem with class imbalance. In fact, this issue can be mitigated with a neat trick (more on that later), leaving us with a general purpose solution to almost any multiclass problem you can think of. Classification algorithms aim to learn a optimal decision boundary to separate different inputs from each other. At prediction time, inputs are classified into different classes using this boundary.