Multiclass problems can be partitioned into a set of 1-versus-many classification problems. Statistical classifiers handle such differently - let me make a distinction
- Probabilistic classifiers
- Boundary-based (linear or non-linear) classifiers
Probabilistic classifiers have an inherent proximity property - they yield the estimated probability of class membership, $\hat{P}(\omega_j \mid {\bf x})$. This makes it straight-forward to build a multi-class classifier or a series of one-versus-others probabilistic classifiers. Clearly,
\begin{equation}
P(\omega_j \mid {\bf x}) \; + \; P(\omega_1 \mid {\bf x})+\ldots + P(\omega_{j-1} \mid {\bf x}) + P(\omega_{j+1} \mid {\bf x})+ \ldots + P(\omega_{c} \mid {\bf x}) = 1
\end{equation}
for a $c$ class problem. Hence, $P(\omega_j \mid {\bf x}) = 1-P(\lnot \omega_j \mid {\bf x})$.
Boundary-based classifiers include support vector machines, RELU neural networks and kNN classifiers. In their basic fabric, they draw boundaries between classes in the high-dimensional feature space. But distances as such do not map to class proximity, at least not outside a small local neighborhood. SVMs have their major drawback here, because they are unsuited for multiclass classification. Why? because the output values do not translate into class proximity for more distance feature vectors. kNN classifiers can be used in a probabilistic way - feed-forward neural networks with sigmoid activation functions do approach the class probabilities, $P(\omega_j \mid {\bf x})$.
The basic question posed is when to construct on-versus-one or one-versus-all classifiers. For simple probabilistic classifiers with discrete feature distributions, the variance of the log posterior probability ratio has the approximate variance:
\begin{equation}
\begin{split}
\sigma^2(\ln[P(\omega_j \mid {\bf X})/(1-P(\omega_j \mid {\bf X})]) \approx & \\
&\frac{1}{N\,P(\omega_{j})\, (1-P(\omega_{j}))} + \\
& \sum_{i} \frac{1-P(X_{i} \mid \omega_j)}{N\, P(\omega_{j})\,P(X_{i} \mid \omega_j)} + \left(1- \frac{1-P(X_{i} \mid \omega_j)}{N\, P(\omega_{j})\,P(X_{i} \mid \omega_j)} \right)
\end{split}
\end{equation}
for the sample size $N \to\infty$. Here, $X_{i}$ is the discrete outcome of input variable $i$.
Now, for a one-versus-others classifier, the one class $\omega_j$ will in most application areas have a smaller probability than $\lnot \omega_j$, which consists of all the other $c-1$ classes. As can be seen, the variance of the log class probability ratio increases rapidly the more skewed the class prior becomes: the variance terms associated with the individual feature distributions are hyperbolic formula's. The denominators of the most seldom class variance terms grow increasingly fast with a smaller probability: $P(\omega_j)$ or $P(\lnot \omega_j)$. Hence, the variance of the class probabilities are the largest in the one-versus-others classifiers - as compared to class $\omega_1$ versus $\omega_2$, $\omega_1$ versus $\omega_3$, $\omega_2$ versus $\omega_3$ (for a three class problem).
High outcome variances mean volatile classifiers, which are more sensitive to random fluctuations. Therefore, OvO classifiers are recommended above OvA classifiers- the variance of the outcomes of OvO are simply smaller, hence OvO classifiers are more noise robust.
