On rappelle que $\{{\bf x}_i\}_{i=1}^N$ est l'ensemble des données (objets) d'entraînement et $\{y\}_{i=1}^{N}$ l'ensemble
des labels ($y_i\in\{-1,+1\}$) correspondants.
Le but de l'entraînement du Perceptron est de prédire la classe pour une donnée ${\bf x}_i$ telle que cette prédiction
corresponde à la classe réelle pour cette donnée: $y_{\text{pred}}({\bf x}_i)=y_i$.
Dans le cas où chaque donnée possède 2 caracteristiques (${\bf x}_i=[{\bf x}_i[1],{\bf x}_i[2]]$), la frontière de
classification est une droite qui sépare les 2 classes.
Droites du plan:
Dans le plan $({\bf x}[1],{\bf x}[2])$, l'équation d'une droite à la forme:
$${\bf x}[2] = a\cdot {\bf x}[1] + b$$
On réécrit cette équation sous la forme (homogène):
\begin{equation}
({\cal D}):~~~~~~~~~ w_2\cdot {\bf x}[2] + w_1\cdot {\bf x}[1] + w_0\cdot {\bf x}[0] = 0
\end{equation}
pour ${\bf w}=[w_0,w_1,w_2]$ et ${\bf x}=[{\bf x}[0],{\bf x}[1],{\bf x}[2]]$.
Remarque: si ${\bf x}[0]=1$, $w_0=-b$, $w_1=-a$, $w_2=1$, les équations sont équivalentes.
Sous cette forme, on peut écrire la règle
\begin{equation}
\begin{cases}
w_2\cdot {\bf x}[2] + w_1\cdot {\bf x}[1] + w_0\cdot {\bf x}[0] = 0&\text{si le point }({\bf x}[1],{\bf x}[2])\text{ appartient à }({\cal D})\\
w_2\cdot {\bf x}[2] + w_1\cdot {\bf x}[1] + w_0\cdot {\bf x}[0] < 0&\text{si le point }({\bf x}[1],{\bf x}[2])\text{ est à droite de }({\cal D})\\
w_2\cdot {\bf x}[2] + w_1\cdot {\bf x}[1] + w_0\cdot {\bf x}[0]> 0&\text{si le point }({\bf x}[1],{\bf x}[2])\text{ est à gauche de }({\cal
D})\\
\end{cases}
\label{eq:classification}
\end{equation}
Classification dans le plan:
Le test de classification sera donc de la forme:
$$\text{si}~~~~w_2\cdot {\bf x}[2] + w_1\cdot {\bf x}[1]+w_0\cdot {\bf x}[0] \leq 0~~~~\text{alors}~~~~y_{\text{pred}}(x) =-1~~~~\text{sinon}~~~~y_\text{pred}(x) = +1$$
qui peut s'écrire:
$$y_\text{pred}(x) = \text{sign}(w_2\cdot {\bf x}[2] + w_1\cdot {\bf x}[1]+w_0\cdot {\bf x}[0])=\text{sign}({\bf w}\cdot{\bf x})$$
où ${\bf w}\cdot{\bf x}$ est le produit scalaire entre les vecteurs ${\bf w}$ et ${\bf x}$.
Entraînement
L'entraînement du Perceptron cherche à ajuster les valeurs des poids $w_0, w_1, w_2$ pour que la droite $({\cal
D})$ sépare (classifie) correctement les données d'entraînement (${\bf x}_i$).
Intuition:
Etant données des valeurs pour $w_0, w_1, w_2$ et une donnée ${\bf x}_i$, si la donnée ${\bf x}_i$ est mal
classifiée par la droite $({\cal D})$ avec les poids $w_0, w_1, w_2$, on
ajoute ou soustrait la donnée ${\bf {\bf x}_i}$ à ces poids pour "attirer" la droite vers cette donnée.
Si le label $y_i$ est positif et la prediction $y_\text{pred}({\bf x}_i)$ est négative alors on doit soustraire la donnée aux poids pour corriger.
Dans le cas inverse, on l'ajoute aux poids.
Si la donnée est classifiée corectement, on ne change rien.
On utilise un
pas d'apprentissage (une valeur $\eta>0$) pour moduler cette attraction.
Formellement:
- Etant données des valeurs pour $w_0, w_1, w_2$
- Soit une donnée ${\bf x}_i = [{\bf x}_i[1],{\bf x}_i[2]]$ (on fixe ${\bf x}_i[0]=1$) et son label $y_i\in\{+1,-1\}$
- Etant donné un pas d'apprentissage $\eta>0$
- $y_{\text{pred}}({\bf x}_i) \leftarrow \text{sign}(w_2 {\bf x}[2] + w_1 {\bf x}[1] + w_0 {\bf x}[0])$
- Si $y_{\text{pred}}({\bf x}_i) =+1$ et $y_i=-1$ alors
$
\begin{cases}
w_0 \leftarrow w_0 - \eta\cdot {\bf x}_i[0]\\
w_1 \leftarrow w_1 - \eta\cdot {\bf x}_i[1]\\
w_2 \leftarrow w_2 - \eta\cdot {\bf x}_i[2]\\
\end{cases}
$
- Si $y_{\text{pred}}({\bf x}_i) =-1$ et $y_i=+1$ alors
$
\begin{cases}
w_0 \leftarrow w_0 + \eta\cdot {\bf x}_i[0]\\
w_1 \leftarrow w_1 + \eta\cdot {\bf x}_i[1]\\
w_2 \leftarrow w_2 + \eta\cdot {\bf x}_i[2]\\
\end{cases}
$
que l'on peut réécrire sous forme vectorielle:
- Etant données des valeurs pour $w_0, w_1, w_2$ et ${\bf w}=[w_0,w_1,w_2]$
- Soit une donnée ${\bf x}_i = [{\bf x}_i[1],{\bf x}_i[2]]$ (on fixe ${\bf x}_i[0]=1$) et son label $y_i\in\{+1,-1\}$
- Etant donné un pas d'apprentissage $\eta>0$
- $y_{\text{pred}}( {\bf x}_i) \leftarrow \text{sign}({\bf w}\cdot {\bf x}_i)$
- Si $y_{\text{pred}}( {\bf x}_i) =+1$ et $y_i=-1$ alors ${\bf w} \leftarrow {\bf w} -\eta\cdot {\bf x}_i$
- Si $y_{\text{pred}}( {\bf x}_i) =-1$ et $y_i=+1$ alors ${\bf w} \leftarrow {\bf w} +\eta\cdot {\bf x}_i$
Si on répète cette opération pour toutes les données de l'ensemble d'entraînement, la droite de classification
$({\cal D})$ s'ajuste afin de ne plus faire d'erreur: $y_{\text{pred}}({\bf x}_i)=y_i$ pour toutes les données.
Remarque: si les labels sont +1 et -1 on peut écrire le test d'apprentissage (lignes 5. et 6.) sous la forme générique ${\bf w} \leftarrow {\bf w} +{1 \over 2}\eta (y_i-y_{\text{pred}})\cdot{\bf x}_i$.
Références
