12  Perceptron

Le perceptron est un modèle de classification linéaire qui s’écrit f(\boldsymbol{x}) = \begin{cases} +1,\ \text{si } \boldsymbol{\theta}^T \boldsymbol{x} \geq \theta_0\\ -1,\ \text{sinon} \end{cases} où les paramètres \boldsymbol{\theta}\in\mathbb{R}^d et \theta_0 sont respectivement les poids et le seuil de déclenchement du modèle et correspondent aux paramètres \boldsymbol{w} et -b d’un classifieur linéaire tel que décrit ici.

12.1 Apprentissage des poids (à seuil fixe)

L’algorithme d’apprentissage du Perceptron pour un seuil \theta_0=0 constant se définit ainsi :

  1. Initialisation (aléatoire) des poids \boldsymbol{\theta}
  2. Répéter jusqu’à convergence :
    • Pour i de 1 à m \boldsymbol{\theta }\leftarrow \begin{cases} \boldsymbol{\theta},\ &\text{si }f(\boldsymbol{x}_i) = y_i\\ \boldsymbol{\theta }+ y_i \boldsymbol{x}_i,\ &\text{sinon } \end{cases} (chaque itération sur la base d’apprentissage est appelée une epoch)

Cet algorithme peut s’interpréter ainsi :

  • tous les exemples de la base d’apprentissage sont classés tour à tour ;
  • pour chaque erreur, une correction positive est appliquée aux poids si f ne prend pas assez en compte l’exemple \boldsymbol{x}_i étiqueté positivement, et inversement dans le cas d’un exemlpe négatif.

Si y_i=1, alors la correction n’est appliquée que si f(\boldsymbol{x}_i)=-1 et donc \boldsymbol{\theta}^T\boldsymbol{x}_i < 0 et la correction devrait permettre d’augmenter la valeur de \boldsymbol{\theta}^T\boldsymbol{x}_i pour la faire éventuellement passer au-dessus de zéro.

Après correction, cette quantité vaut (\boldsymbol{\theta }+ y_i\boldsymbol{x}_i)^T \boldsymbol{x}_i = \underbrace{\boldsymbol{\theta}^T \boldsymbol{x}_i}_{ancienne\ valeur} + y_i \boldsymbol{x}_i^T \boldsymbol{x}_i où \boldsymbol{x}_i^T \boldsymbol{x}_i = \|\boldsymbol{x}_i\|^2 \geq 0. Donc la valeur de \boldsymbol{\theta}^T \boldsymbol{x}_i sera augmentée si y_i=+1 et diminuée si y_i=-1, ce qui rapprochera le classifieur d’une bonne classification sur cet exemple.

12.2 Convergence de l’algorithme

  • Si la base d’apprentissage n’est pas linéairement séparable, l’algorithme du perceptron ne peut pas converger, car il y aura toujours des erreurs et donc des corrections appliquées aux poids. C’est pour cela qu’en pratique on applique toujours cet algorithme avec un nombre maximum d’epochs.
  • Si la base d’apprentissage est linéairement séparable, l’algorithme du perceptron converge en un nombre fini d’itérations, qui dépend de la marge avec laquelle un classifieur linéaire peut classer les données, et donc de la plus petite distance entre deux points de catégories différentes.

Dans le cas linéairement séparable, il existe une solution \boldsymbol{\theta}^* de norme unité (\|\boldsymbol{\theta}^*\| = 1), qui classe correctement tous les exemples avec une marge d’au moins \gamma, c’est-à-dire que y_i \boldsymbol{x}_i^T \boldsymbol{\theta}^* \geq \gamma ,\quad i=1,\dots, m. Soit \boldsymbol{\theta}_t le vecteur des poids après t corrections. La convergence vers \boldsymbol{\theta}^* à partir d’une initialiation à \boldsymbol{\theta}_0 = \boldsymbol{0} sur des données bornées (\|\boldsymbol{x}_i\| \leq R) se démontre en combinant deux idées :

  1. le produit scalaire \boldsymbol{\theta}_t^T\boldsymbol{\theta}^* augmente à chaque itération ;
  2. la norme de \boldsymbol{\theta}_t n’augmente pas trop à chaque itération ;

et donc \boldsymbol{\theta}_t est de plus en plus aligné avec \boldsymbol{\theta}^*, ce qui revient à dire qu’ils produisent la même classification.

Montrons le point 1. : \boldsymbol{\theta}_{t+1}^T\boldsymbol{\theta}^* = (\boldsymbol{\theta}_t + y_i\boldsymbol{x}_i)^T \boldsymbol{\theta}^* = \boldsymbol{\theta}_t^T\boldsymbol{\theta}^* + y_i \boldsymbol{x}_i^T \boldsymbol{\theta}^* \geq \gamma + \boldsymbol{\theta}_t^T\boldsymbol{\theta}^*. Après t itérations, nous avons donc (avec \boldsymbol{\theta}_0=\boldsymbol{0}) \boldsymbol{\theta}_t^T\boldsymbol{\theta}^* \geq t\gamma + \boldsymbol{\theta}_0^T\boldsymbol{\theta}^* = t\gamma.

Pour le point 2., nous avons (en utilisant |y_i| = 1): \|\boldsymbol{\theta}_{t+1}\|^2 = \|\boldsymbol{\theta}_t + y_i\boldsymbol{x}_i\|^2 \leq \|\boldsymbol{\theta}_{t}\|^2 + \|y_i\boldsymbol{x}_i\|^2 = \|\boldsymbol{\theta}_{t}\|^2 + R^2 Après t itérations, nous avons donc \|\boldsymbol{\theta}_{t}\|^2 \leq t R^2

Combinant ces deux résultats et l’inégalité de Cauchy-Schwarz, nous obtenons t\gamma \leq \boldsymbol{\theta}_t^T\boldsymbol{\theta}^*\leq \|\theta_t\| \|\boldsymbol{\theta}^*\| \leq \sqrt{t} R et donc t \leq \frac{R^2}{\gamma^2}

12.3 Apprentissage des poids et du seuil

Pour permettre l’apprentissage du seuil, il suffit d’appliquer l’algorithme précédent à des données étendues avec une composante supplémentaire égale à -1 : \boldsymbol{\theta}^T \boldsymbol{x} \geq \theta_0\ \Leftrightarrow\ \boldsymbol{\theta}^T \boldsymbol{x} - \theta_0 \geq 0\ \Leftrightarrow \begin{bmatrix} \boldsymbol{\theta}^T & \theta_0\end{bmatrix}\begin{bmatrix} \boldsymbol{x} \\ -1\end{bmatrix} \geq 0\ \Leftrightarrow\ \tilde{\boldsymbol{\theta}}^T \tilde{ \boldsymbol{x}} \geq 0 Ainsi, en appliquant l’algorithme de base à \tilde{\boldsymbol{\theta}}, nous obtenons \ \boldsymbol{\theta }\leftarrow \begin{cases} \boldsymbol{\theta},\ &\text{si }f( \boldsymbol{x}_i) = y_i\\ \boldsymbol{\theta }+ y_i \boldsymbol{x}_i,\ &\text{sinon } \end{cases} \quad\text{et } \quad \theta_0 \leftarrow \begin{cases}\theta_0,\ &\text{si }f(\boldsymbol{x}_i) = y_i\\ \theta_0 - y_i,\ &\text{sinon } \end{cases}

En pratique, un taux d’apprentissage \mu\in(0,1] est inséré dans les mises à jour pour accélérer la convergence \ \boldsymbol{\theta }\leftarrow \begin{cases} \boldsymbol{\theta},\ &\text{si }f( \boldsymbol{x}_i) = y_i\\ \boldsymbol{\theta }+ \mu y_i \boldsymbol{x}_i,\ &\text{sinon } \end{cases} \quad\text{et } \quad \theta_0 \leftarrow \begin{cases}\theta_0,\ &\text{si }f(\boldsymbol{x}_i) = y_i\\ \theta_0 - \mu y_i,\ &\text{sinon } \end{cases} Le taux d’apprentissage joue le même rôle que le paramètre \mu de la descente de gradient.