# MultiClass Classification - Training OvO and OvA

I like to know how OvO (One vs One) and OvA (One vs All) models are trained in multiclass classification problem. To keep it simple, we have 4 classes, each of which has 1000 datapoints. What are the details for training in both scenarios?

1. OvO: We need to build 6 classifiers (n=c(4,2)=6). For example, we need to run cross validation (CV) for the dataset of 2000 datapoints from class 1 and class 2 to find an optimal model? Then after training all of 6 classifiers, voting will be used to decide the final class?

2. OvA: In this case, we need to build 4 classifiers (n=4). For example, for class 1, we need to run CV for the entire dataset (6000 datapoints) which is highly imbalanced (1000 vs 5000) or we need to employ imbalanced techniques here (e.g.: subsampling, oversampling (SMOTE), other performance metrics like adjusted geometric mean or AUC ROC)?

Please point me to the right references.

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, $$$$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$$$$ 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{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}$$$$ 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.

Regarding point 1): everything OK but voting is only one of many possibilities. The name of the process of deciding what class to assign to a new data is called decoding (coding is the process of construction of the OVO/OVA/ECOC matrices - coding for OVO and OVA is trivial so no need to worry about it).

For example instead of using the decision (class 1 or class 2) of each binary classifier, you may use the degree of confidence (or probability) of the data being in class 1, and add all degrees; the class with higher sum of degrees is the chosen one.

https://jmlr.csail.mit.edu/papers/volume11/escalera10a/escalera10a.pdf Error-Correcting Output Codes Library JMLR vol 11 by Escalera, Pujol and Radeva has a nice discussion on decoding algorithms.

https://github.com/MLDMXM2017 (I dont know the name of the user) has some implementations of the decoding functions in Python (for example in https://github.com/MLDMXM2017/TCGA-ECOC/tree/master/Decoding)

(I think that for OVO all (or some of the) decoding algorithms that are not based on voting (but based on degree of confidence) are generally equivalent from a practical point of view - I am not sure of this - I think I tested some different decoders and did not get different accuracies on the test sets but this was long time ago and I dont remember the details anymore)

Regarding 2) I dont know of any published result on using imbalanced techniques (oversampling, undersampling, class weights, over-and-undersampling) on the binary classifiers. It is a good idea, I think.

Your other suggestion of using metrics that are less sensitive to imbalance (AUC, MCC, F1, Gmeans) does not look so good. The metric used for the binary classifiers is irrelevant - you never look at that metric unless you are doing hyperparameter search for the binary classifier. In that case, I dont know.