En classification, l’étiquette y\in\mathcal{Y} détermine la catégorie de \boldsymbol{x}\in\mathcal{X} parmi un nombre de catégories C fini. Le modèle de prédiction est ainsi amené à classer les données \boldsymbol{x} en différentes catégories et est couramment appelé un classifieur.
L’erreur d’un classifieur sur un exemple est mesurée par la fonction de perte 0-1 : \ell(f,\boldsymbol{x},y) = \mathbf{1}(f(\boldsymbol{x})\neq y) = \begin{cases} 1 ,&\text{si } f(x)\neq y\\0,&\text{sinon}\end{cases} D’après les propriétés de la fonction indicatrice, le risque de classification est donc la probabilité de mal classé un exemple : R(f) = \mathbb{E}\mathbf{1}(f(\boldsymbol{X})\neq Y) = P(f(\boldsymbol{X})\neq Y)
On distingue souvent entre
Le classifieur de Bayes prédit la catégorie la plus probable pour tout \boldsymbol{x} :
f_{Bayes}(\boldsymbol{x}) = \arg\max_{y\in\mathcal{Y}} P(Y=y | \boldsymbol{X}=\boldsymbol{x})
Dans le cas binaire où \mathcal{Y}=\{-1,+1\}, il s’écrit aussi comme :
f_{Bayes}(\boldsymbol{x}) = \begin{cases} +1,\ \text{si } P(Y=1 | \boldsymbol{X}=\boldsymbol{x}) \geq P(Y=-1 | \boldsymbol{X}=\boldsymbol{x})\\
-1,\ \text{si } P(Y=1 | \boldsymbol{X}=\boldsymbol{x}) < P(Y=-1 | \boldsymbol{X}=\boldsymbol{x})
\end{cases}
Ce classifieur est le classifieur optimal, c’est-à-dire le meilleur possible parmi toutes les fonctions de \mathcal{X} dans \mathcal{Y} :
R(f_{Bayes}) = \min_{f:\mathcal{X}\to\mathcal{Y}} R(f)
et donc celui qui possède la plus petite probabilité de se tromper.
Pour tout f : \mathcal{X}\to\mathcal{Y}, nous montrons les étapes suivantes :
En classification binaire, avec \mathcal{Y}=\{-1,+1\}, un classifieur linéaire de \mathcal{X}\subset\mathbb{R}^d est un classifieur de la forme f(\boldsymbol{x}) = \text{signe}\left(\boldsymbol{w}^T\boldsymbol{x} + b\right) \tag{8.1} avec des paramètres \boldsymbol{w}\in\mathbb{R}^d et b\in\mathbb{R}.
La frontière de décision d’un classifieur est la frontière entre les régions de l’espace \mathcal{X} affectées à différentes catégories. Pour un classifieur linéaire, cette frontière est un hyperplan : H = \{\boldsymbol{x} : \boldsymbol{w}^T \boldsymbol{x} + b = 0 \} où \boldsymbol{w} est un vecteur orthogonal à l’hyperplan indiquant son orientation et b nous informe sur sa distance à l’origine qui vaut |b|/\|\boldsymbol{w}\|.
En dimension d=3, cet hyperplan est en fait un plan, en dimension d=2 il devient une simple droite et se réduit à un point x=-b/w en dimension d=1.
Nous générons 100 points \boldsymbol{x}_i en 2D répartis dans 2 catégories (bleus et rouges). Un classifieur linéaire correspond à une droite qui coupe le plan en deux parties, chacune affectée à une des catégories : f(\boldsymbol{x})= bleu pour tous les points \boldsymbol{x} au-dessus de la droite et rouge en-dessous.
X = np.random.rand(100,2)
y = np.random.rand(100) > 0.5
X[y,:] += np.array([2,2])
plt.plot(X[y,0], X[y,1], "ob")
plt.plot(X[~y,0], X[~y,1], "or")
w = np.array([1, 1])
b = -3
x1 = 0
x2 = 3
plt.plot([x1,x2], [-(x1*w[0] + b)/w[1], -(x2*w[0] + b)/w[1]], "-k")
t=plt.title("Droite de séparation en 2D")
Un classifieur linéaire de x\in\mathbb{R} est une fonction constante par morceaux qui commute entre f(x)=-1 et f(x)=1 lorsque wx+b=0, c’est-à-dire au point x=-b/w.
w = 1
b = -0.4
X = np.random.rand(12)
y = w*X + b >= 0
plt.plot(X[y],np.zeros(np.sum(y)), "ob")
plt.plot(X[~y], np.zeros(np.sum(~y)), "or")
plt.plot(-b/w,0, "ok", markersize=10)
x = np.arange(0,1,0.02)
plt.plot(x,w*x+b)
plt.plot(x, np.sign(w*x+b))
plt.grid()
plt.legend(["y_i = -1", "y_i = +1", "frontière", "wx+b", "f(x)"])
t=plt.title("Classification linéaire en 1D")
Un jeu de données \left((\boldsymbol{x}_i,y_i)\right)_{1\leq i\leq m} est dit linéairement séparable s’il existe un classifieur linéaire capable de classer correctement toutes ces données, autrement dit, s’il existe (\boldsymbol{w},b) tels que \text{signe}\left(\boldsymbol{w}^T\boldsymbol{x}_i + b\right) = y_i,\quad i=1,\dots, m ce qui peut être réécrit comme un système d’inégalités linéaires : y_i(\boldsymbol{w}^T\boldsymbol{x}_i + b) \geq 1,\quad i=1,\dots, m.
En classification binaire, y_i\in\{-1,+1\}, et donc y_i = \text{signe}(y_i). Ainsi, tester la séparabilité linéaire et trouver \boldsymbol{w} et b tels que \text{signe}\left(\boldsymbol{w}^T\boldsymbol{x}_i + b\right) = y_i revient à trouver \boldsymbol{w} et b tels que \boldsymbol{w}^T\boldsymbol{x}_i + b et y_i aient le même signe, ce qui est garanti si y_i(\boldsymbol{w}^T\boldsymbol{x}_i + b) > 0 ce qui est bien le cas si y_i(\boldsymbol{w}^T\boldsymbol{x}_i + b) \geq 1. Dans le cas où il n’existe pas de couple (\boldsymbol{w},b) tel que y_i(\boldsymbol{w}^T\boldsymbol{x}_i + b) \geq 1 alors il ne peut pas en exister pour satisfaire y_i(\boldsymbol{w}^T\boldsymbol{x}_i + b) > 0 (car si y_i(\boldsymbol{w}^T\boldsymbol{x}_i + b) \geq \epsilon > 0, alors (\boldsymbol{w}/\epsilon, b/\epsilon) serait solution de y_i(\boldsymbol{w}^T\boldsymbol{x}_i + b) \geq 1) et donc le jeu de données est non linéairement séparable.
En dimension d=1, un jeu de données est non linéairement séparable si n’existe aucun point sur l’axe des réels tel que tous les points de la base d’apprentissage de chaque côté soient de la même catégorie (couleur).
X = np.random.rand(12)
y = (X >= 0.4) & (X < 0.7)
plt.plot(X[y],np.zeros(np.sum(y)), "ob")
plt.plot(X[~y], np.zeros(np.sum(~y)), "or")
t=plt.title("Données non linéairement séparable en 1D")
En dimension d=2, un jeu de données est non séaparable si aucune droite ne peut correctement classer tous les exemples.
X = np.random.randn(100,2)
y = np.random.rand(100) > 0.5
X[y,:] += np.array([2,2])
plt.plot(X[y,0], X[y,1], "ob")
plt.plot(X[~y,0], X[~y,1], "or")
t=plt.title("Données non linéairement séparable en 2D")
Lorsque le nombre de catégories C est supérieur à 2, le problème de classification devient multi-classe et certaines méthodes ne sont plus directement applicables. Par exemple, un classifieur linéaire de la forme donnée en Équation 8.1 ne peut que diviser l’espace en deux catégories.
Pour pouvoir appliquer un algorithme de classification binaire à un problème multi-classe, il est nécessaire de décomposer le problème en un ensemble de sous-problèmes binaires. Il existe deux grandes approches décrites ci-dessous pour y parvenir.
La décomposition un-contre-tous crée C classifieurs binaires pour traiter un problème à C catégories, où chaque classifieur binaire f_k(\boldsymbol{x})=\text{signe}\left( g_k(\boldsymbol{x})\right) est chargé de séparer une classe de l’ensemble des autres.
La classification multi-classe est obtenue par f(\boldsymbol{x}) = \arg\max_{k\in\mathcal{Y}} g_k(\boldsymbol{x}) où la sortie réelle du kème classifieur, g_k(\boldsymbol{x}), peut être interprétée comme un score pour la catégorie k, et \boldsymbol{x} est affeté à la catégorie avec le plus grand score.
Cette technique permet de lever l’ambiguïté lorsque plusieurs classifieurs binaires prédisent que \boldsymbol{x} appartient à leur catégorie, ou lorsqu’ils le rejettent tous.
La décomposition un-contre-un crée C(C-1)/2 classifieurs binaires, c’est-à-dire un pour chaque paire de catégories. Ainsi, chaque classifieur binaire f_{j/k} est chargé de séparer un couple de catégories et produit une sortie binaire dans \{j,k\}.
La classification multi-classe est ensuite obtenue par un vote majoritaire : f(\boldsymbol{x}) = \arg\max_{y\in\mathcal{Y}} \sum_{1\leq j < k \leq C} \mathbf{1}( f_{j/k}(\boldsymbol{x}) = y )