One-Against-All decomposition

Introduction

A lot of classification methods are defined only for binary problems. An extension of arbitrary binary method to multi-class one can be done by the descoposition methods. The decomposition methods splits the original multi-class problem to a serie of simpler binary problems which can be solve by the given binary method. The resulting binary classifiers are then prorely combined together to form resulting multi-class classifier. The One-Against-All (OAA) decomposition is a typical example.

Let ${\cal T}_{XY}=\{(x_1,y_1),\ldots,(x_l,y_l)\}$ be a training set of observable vectors $x_i\in{\cal X}\subseteq{\mathbb{R}}^n$ and corresponding hidden states $y_i\in{\cal Y}=\{1,\ldots,c\}$. The task is to train the multi-class classifier $q\colon{\cal X}\rightarrow{\cal Y}$ which is defined as

$$q(x) = \mathop{\rm argmax}\limits_{y\in{\cal Y}} f_y(x) \:,$$ (5)

where $f_y\in{\cal X}\rightarrow{\mathbb{R}}$, $y\in{\cal Y}$ are the discriminant functions. The task is to train the discriminant functions form the training data ${\cal T}_{XY}$. This can be done using the OAA decomposition and a selected binary classification methods. Let ${\cal T}_{XY}^{y}=\{(x_1,y_1'),\ldots,(x_l,y_l')\}$ be a modified training set its labels are defined as

$$y_i' = \left \{ \begin{array}{rcl} 1 & \mbox{for} & y... ...2 & \mbox{for} & y_i \neq y \:. \\ \end{array} \right .$$

The discriminant function $f_y$ of the multi-class classifier (5) can be trained in the same way as the discriminant function of binary classifier trained on the data ${\cal T}_{XY}^y$.

Figure 4: Structure of the multi-class classifier.

Task assignment

• Implement the One-Against-All decomposition method to extend the AdaBoost classifier for the multi-class problem.
• Use the implemented multi-class AdaBoost to train the classifier for Brodatz textures [brodatz_trn.mat].
• Validate the multi-class classifier on the testing data [brodatz_tst.mat].

Useful functions

msvm_exp1

Example on using the One-Against-All Decomposition.