Le perceptron

Au chapitre 3, tu as compris pourquoi une fonction d’activation doit être non-linéaire Non-linéarité Propriété d'une fonction qui n'est pas affine. Une fonction d'activation non-linéaire est obligatoire dans un réseau profond, sans quoi la composition de plusieurs couches se réduit à une seule couche affine équivalente, et la profondeur perd tout intérêt. et dérivable pour qu’un réseau profond ait un intérêt mathématique. Or le premier neurone artificiel capable d’apprendre, le perceptron de Frank Rosenblatt (1958), utilise la fonction de seuil Fonction seuil Fonction d'activation binaire H(z) qui vaut 1 si z >= 0 et 0 sinon. Aussi appelée fonction de Heaviside. C'est l'activation originale de McCulloch-Pitts (1943) et du perceptron de Rosenblatt (1958), abandonnée plus tard parce qu'elle n'est pas dérivable. , qui n’est presque partout dérivable que de dérivée nulle. Comment Rosenblatt a-t-il pu lui faire apprendre quoi que ce soit ?

Ce chapitre répond à cette question en construisant le perceptron d’un point de vue géométrique, sans dérivée. On démontre que la procédure converge sur un dataset séparable, puis on découvre la limite qui a mis fin au premier âge des réseaux de neurones.

La géométrie d’un hyperplan

L’analogie de la règle sur la table

Pose une règle plate sur une table. Cette règle divise la surface de la table en deux zones : la partie devant la règle et la partie derrière la règle. Le bord de la règle, c’est la frontière. La direction perpendiculaire au bord, c’est ce qu’on va appeler le vecteur normal Vecteur normal Vecteur $w$ qui définit la direction perpendiculaire à un hyperplan d'équation $w \cdot x + b = 0$. Sa direction indique de quel côté de l'hyperplan se trouve un point ; sa norme fixe l'échelle de la distance signée. Source : Bishop, PRML, ch. 4 , et la distance entre la règle et le bord de la table, c’est le décalage.

Un hyperplan Hyperplan Sous-ensemble de Rⁿ défini par une équation linéaire w · x + b = 0. En dimension 2 c'est une droite, en dimension 3 un plan. C'est exactement la frontière de décision tracée par un neurone unique. en deux dimensions, c’est ça : une droite qui sépare le plan en deux demi-espaces Demi-espace Une des deux régions dans lesquelles un hyperplan partitionne Rⁿ. Algébriquement, l'ensemble des points x tels que w · x + b > 0 (resp. < 0). Un neurone à seuil sépare l'espace en exactement deux demi-espaces : actif et inactif. . En trois dimensions, c’est un plan. En $n$ dimensions, c’est une surface plate de dimension $n-1$.

Définition formelle

Soit $w \in \mathbb{R}^n$ un vecteur non nul et $b \in \mathbb{R}$ un scalaire. L’hyperplan affine d’équation $w \cdot x + b = 0$ est l’ensemble :

$$\mathcal{H} = \{\, x \in \mathbb{R}^n \;:\; w \cdot x + b = 0 \,\}.$$

Distance signée d’un point à l’hyperplan

Pour un point $x \in \mathbb{R}^n$ quelconque, on définit sa distance signée Distance signée Distance perpendiculaire d'un point à un hyperplan, affectée d'un signe selon le côté où se trouve le point. Pour l'hyperplan $w \cdot x + b = 0$, elle vaut $d(x) = (w \cdot x + b) / \|w\|$ : positive d'un côté, négative de l'autre, nulle sur l'hyperplan lui-même. Source : Hastie, Tibshirani, Friedman, ESL, ch. 4 à $\mathcal{H}$ par :

$$d(x, \mathcal{H}) \;=\; \frac{w \cdot x + b}{\|w\|}.$$

Cette quantité est positive d’un côté de $\mathcal{H}$, négative de l’autre, nulle sur $\mathcal{H}$ lui-même. En valeur absolue, c’est la distance perpendiculaire usuelle.

Joue avec l’hyperplan

Hyperplan : w · x + b = 0

Géométrie de l'hyperplan

w₁1.00

w₂0.50

b-0.50

Clique dans la grille pour placer un point sondé.

Aucun point sondé pour le moment.

Trois choses à remarquer en jouant :

• Quand $b = 0$, l’hyperplan passe exactement par l’origine.
• Multiplier $w$ par deux ne déplace pas la droite : seule la direction de $w$ compte pour la position de l’hyperplan, pas sa norme.
• La distance signée change de signe quand tu cliques de l’autre côté de la droite : c’est ce signe qu’on va exploiter pour classifier.

Linéairement séparable, avec marge

L’analogie de la bande tampon

Imagine deux pays voisins avec une bande tampon entre eux. La frontière, c’est la droite au milieu. La largeur de la bande tampon, c’est la marge : plus elle est large, plus la frontière est robuste aux petites perturbations des points. Si la bande tampon se réduit à zéro, des habitants des deux pays se croisent et la frontière devient ambiguë.

Encodage des cibles : pourquoi $y \in \{-1, +1\}$

Jusqu’ici on a souvent codé les classes binaires par $0$ et $1$. Pour le perceptron, on choisit plutôt $-1$ et $+1$. Ce choix simplifie tout : un exemple $(x, y)$ est bien classé par $(w, b)$ si et seulement si $y$ et $w \cdot x + b$ ont le même signe, ce qui s’écrit en une seule inégalité :

$$y \, (w \cdot x + b) \;>\; 0.$$

Définitions formelles

Soit $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^m$ un jeu de données avec $x_i \in \mathbb{R}^n$ et $y_i \in \{-1, +1\}$. On dit que $\mathcal{D}$ est linéairement séparable Linéairement séparable Un jeu de données étiquetées est dit linéairement séparable s'il existe un hyperplan qui sépare correctement les points de label 1 des points de label 0. XOR est l'exemple historique d'un problème non linéairement séparable. s’il existe $(w, b) \in \mathbb{R}^n \times \mathbb{R}$ tels que pour tout $i$ :

$$y_i \, (w \cdot x_i + b) \;>\; 0.$$

Pour un tel couple $(w, b)$, on définit deux marges. La marge fonctionnelle Marge fonctionnelle Pour un exemple $(x, y)$ avec $y \in \{-1, +1\}$, la marge fonctionnelle est la quantité $\hat\gamma = y (w \cdot x + b)$. Elle est strictement positive si et seulement si l'exemple est bien classé. Elle dépend de l'échelle des poids et n'est pas une distance géométrique. Source : Bishop, PRML, ch. 7 du point $i$ est $\hat\gamma_i = y_i (w \cdot x_i + b)$. La marge géométrique Marge géométrique Distance perpendiculaire minimale entre un hyperplan séparateur et les points du jeu de données. Définie par $\gamma = \min_i y_i (w \cdot x_i + b) / \|w\|$ avec $y_i \in \{-1, +1\}$. Joue un rôle central dans le théorème de Novikoff et dans la formulation des machines à vecteurs de support. Source : Novikoff, 1962 du point $i$ est $\gamma_i = \hat\gamma_i / \|w\|$. La marge du dataset, c’est le minimum sur tous les points :

$$\gamma \;=\; \min_{i=1,\dots,m} \, \frac{y_i \, (w \cdot x_i + b)}{\|w\|}.$$

La marge fonctionnelle dépend de l’échelle des poids ($\hat\gamma$ double si on double $w$). La marge géométrique, elle, est invariante : elle mesure une vraie distance dans le plan.

Le perceptron, et la tension avec le chapitre 3

Définition

Soit $(w, b) \in \mathbb{R}^n \times \mathbb{R}$. Le perceptron associé est le classifieur

$$\hat y(x) \;=\; \operatorname{sgn}(w \cdot x + b),$$

où $\operatorname{sgn}$ est la fonction signe.

1958 et 1960 : deux dates distinctes

Frank Rosenblatt publie l’article fondateur dans la revue Psychological Review (Rosenblatt, 1958). Il y propose le modèle théorique et la règle d’apprentissage que tu vas voir tout de suite. Deux ans plus tard, il construit au Cornell Aeronautical Laboratory le Mark I Perceptron Mark I Perceptron Machine physique construite par Frank Rosenblatt entre 1958 et 1960 au Cornell Aeronautical Laboratory. Capable de reconnaître des formes simples grâce à 400 photorécepteurs connectés à des poids ajustables via potentiomètres motorisés. Première implémentation matérielle d'un algorithme d'apprentissage automatique, distincte du modèle théorique publié en 1958. Source : Rosenblatt, 1958, 1960 : une machine physique avec 400 photorécepteurs et des poids ajustables via des potentiomètres motorisés. Le New York Times titre alors que la marine américaine vient de construire « une machine qui apprend par elle-même ».

Le point important : 1958, c’est le modèle ; 1960, c’est l’implémentation matérielle. Beaucoup de récits confondent les deux, mais l’article théorique précède la machine de deux ans.

La tension avec ce que le chapitre 3 nous a appris

Au chapitre 3, on a démontré que la profondeur d’un réseau ne sert à rien si la fonction d’activation est linéaire, et qu’on a besoin d’une fonction dérivable pour calculer un gradient. Or $\operatorname{sgn}$ est presque partout dérivable de dérivée nulle. Comment Rosenblatt a-t-il fait apprendre une machine équipée d’une telle fonction ?

La réponse, étonnamment, est qu’il n’a pas eu besoin d’une dérivée. Sa procédure d’apprentissage est une correction géométrique locale : quand le perceptron se trompe sur un exemple, on déplace le vecteur de poids dans la direction qui corrigerait l’erreur, sans jamais calculer de gradient.

C’est une exception historique. À partir du chapitre 7, on rebasculera sur des fonctions d’activation dérivables et la descente de gradient Descente de gradient Algorithme d'optimisation qui ajuste itérativement les paramètres d'un modèle pour minimiser une fonction de coût. À chaque étape, il déplace les paramètres dans la direction opposée au gradient, d'une distance proportionnelle au taux d'apprentissage. Méthode dominante pour entraîner les réseaux de neurones. Source : Cauchy, 1847 prendra le relais. Mais pour le perceptron, l’apprentissage se fait à la main, par projection.

La règle d’apprentissage du perceptron

L’analogie du panneau de signalisation

Imagine un panneau de signalisation mal orienté. À chaque automobiliste qui se trompe à cause de lui, tu le tournes d’un cran dans la direction qui aurait évité l’erreur. Tu ne calcules pas de dérivée, tu ne maximises rien : tu réagis localement, à chaque incident. Au bout d’un certain nombre d’incidents, le panneau est correctement orienté.

C’est exactement ce que fait la règle de Rosenblatt sur les poids $w$ et le biais $b$.

Énoncé

Soit $\eta > 0$ le taux d’apprentissage Taux d'apprentissage Scalaire positif qui contrôle la taille du pas effectué par la descente de gradient à chaque itération. Trop petit, l'apprentissage est lent ; trop grand, il oscille ou diverge. Souvent noté η (eta) ou α (alpha). C'est le premier hyperparamètre à régler dans tout entraînement. . Pour un exemple $(x_i, y_i)$ mal classé, la règle d’apprentissage Règle d'apprentissage Procédure qui met à jour les paramètres (poids, biais) d'un modèle à partir d'exemples observés. Pour le perceptron, la règle est $w \leftarrow w + \eta \cdot y \cdot x$ et $b \leftarrow b + \eta \cdot y$ appliquée seulement quand un exemple est mal classé. Source : Rosenblatt, 1958 du perceptron applique :

$$w \;\leftarrow\; w + \eta \, y_i \, x_i, \qquad b \;\leftarrow\; b + \eta \, y_i.$$

Pour un exemple bien classé, on ne touche à rien. La procédure parcourt le dataset, applique l’update à chaque erreur, et recommence jusqu’à ce qu’aucun exemple ne soit mal classé.

Trois formes pour la même règle

Forme	Écriture
Par composante	$w_j \leftarrow w_j + \eta y_i x_{i,j}$ pour chaque $j$
Vectorielle	$w \leftarrow w + \eta y_i x_i$
Avec biais absorbé	$\tilde w \leftarrow \tilde w + \eta y_i \tilde x_i$ avec $\tilde x = (x, 1)$ et $\tilde w = (w, b)$

Les trois disent exactement la même chose. La forme par composante est la plus explicite pour calculer à la main. La forme vectorielle est la plus compacte. La forme avec biais absorbé est utile pour les démonstrations : elle réduit deux mises à jour ($w$ et $b$) à une seule.

Démonstration : l’update améliore strictement la marge fonctionnelle

Avant l’update, soit $\hat\gamma_i = y_i (w \cdot x_i + b)$ la marge fonctionnelle de l’exemple $(x_i, y_i)$. Comme cet exemple est mal classé, on a $\hat\gamma_i \leq 0$.

Après l’update, le nouveau $(w', b') = (w + \eta y_i x_i, \, b + \eta y_i)$. Calculons la nouvelle marge fonctionnelle.

Étape 1. On remplace $(w', b')$ par leur expression.

$$\hat\gamma_i' \;=\; y_i \, (w' \cdot x_i + b') \;=\; y_i \, \big[ (w + \eta y_i x_i) \cdot x_i + (b + \eta y_i) \big].$$

Étape 2. On développe.

$$\hat\gamma_i' \;=\; y_i \, (w \cdot x_i + b) + \eta \, y_i^2 \, (x_i \cdot x_i) + \eta \, y_i^2.$$

Étape 3. Comme $y_i \in \{-1, +1\}$, on a $y_i^2 = 1$. La nouvelle marge fonctionnelle est donc :

$$\hat\gamma_i' \;=\; \hat\gamma_i + \eta \, \big( \|x_i\|^2 + 1 \big).$$

Résultat. La quantité ajoutée $\eta (\|x_i\|^2 + 1)$ est strictement positive (car $\eta > 0$). L’update a donc augmenté strictement la marge fonctionnelle de l’exemple. Aucune dérivée n’a été calculée nulle part dans la démonstration. □

Construis le perceptron pas à pas

● cible +1● cible −1contour vert : bien classécontour rouge : mal classé

Construire le perceptron pas à pas

Jeu de données

ANDORNANDXOR

Taux η0.50

w₁ = 0.00

w₂ = 0.00

b = 0.00

Corrections : 0 · Époques : 0

Mal classés : 1/4

Prochaine erreur+1 époque+10 époquesInitialiser au hasardRemettre à zéro

Trois choses à observer en jouant :

• Sur OR ou AND, la frontière violette se stabilise rapidement. Le compteur d’erreurs tombe à zéro et le perceptron a convergé.
• Sur XOR, le compteur d’erreurs ne tombe jamais à zéro, même après cent époques. La règle continue d’osciller indéfiniment.
• Le taux $\eta$ ne change pas la convergence sur les datasets séparables : il modifie seulement l’amplitude de chaque pas et donc la vitesse visuelle de la frontière, pas le résultat final.

Le théorème de convergence (Novikoff, 1962)

L’analogie du curseur qui zigzague

Imagine un curseur qui rebondit entre les deux bords d’un canal étroit. À chaque rebond, il dépense un peu de son élan. Si le canal a une largeur strictement positive, le curseur finit par s’arrêter au milieu en un nombre fini de rebonds.

C’est ce que va prouver le théorème de Novikoff Théorème de Novikoff Si un jeu de données est linéairement séparable avec marge géométrique $\gamma > 0$ et rayon $R = \max_i \|x_i\|$, alors l'algorithme du perceptron initialisé à zéro converge en au plus $T \leq (R / \gamma)^2$ corrections, quelle que soit la valeur du taux d'apprentissage. Source : Novikoff, 1962 : tant que la marge $\gamma$ est strictement positive, le nombre de corrections du perceptron est borné par une quantité qui ne dépend que de la géométrie du dataset.

Énoncé

Soit $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^m$ un jeu de données linéairement séparable. On suppose qu’il existe un vecteur unitaire $w^* \in \mathbb{R}^n$ avec $\|w^*\| = 1$ et un scalaire $b^* \in \mathbb{R}$ tels que pour tout $i$ :

$$y_i \, (w^* \cdot x_i + b^*) \;\geq\; \gamma \;>\; 0.$$

Soit $R = \max_{i} \|x_i\|$ le rayon du dataset.

Une précision de rigueur : une fois le biais absorbé, les quantités du théorème se lisent toutes dans $\mathbb{R}^{n+1}$. Le rayon est alors $R = \max_i \|\tilde x_i\| = \max_i \sqrt{\|x_i\|^2 + 1}$, et $w^*$ désigne le séparateur optimal renormalisé à $\|w^*\| = 1$ dans ce même espace augmenté. La borne $R^2 / \gamma^2$ garde exactement sa forme.

Théorème. L’algorithme du perceptron (en forme à biais absorbé) initialisé à $w_0 = 0$ avec pas $\eta = 1$ effectue au plus

$$T \;\leq\; \frac{R^2}{\gamma^2}$$

corrections avant de classer correctement tous les exemples.

Démonstration en deux lemmes

On note $w_t$ le vecteur de poids après la $t$-ème correction.

Lemme 1 (minoration). Pour tout $t \geq 0$, $w_t \cdot w^* \geq t \gamma$.

Étape 1. À l’initialisation, $w_0 = 0$, donc $w_0 \cdot w^* = 0$.

Étape 2. À la $(t+1)$-ème correction, on a $w_{t+1} = w_t + y_i x_i$ pour un exemple $(x_i, y_i)$ mal classé.

Étape 3. Calculons $w_{t+1} \cdot w^*$ :

$$w_{t+1} \cdot w^* \;=\; (w_t + y_i x_i) \cdot w^* \;=\; w_t \cdot w^* + y_i \, (w^* \cdot x_i).$$

Étape 4. Par hypothèse de séparation avec marge $\gamma$ : $y_i (w^* \cdot x_i) \geq \gamma$. Donc :

$$w_{t+1} \cdot w^* \;\geq\; w_t \cdot w^* + \gamma.$$

Étape 5. Par récurrence sur $t$, $w_t \cdot w^* \geq t \gamma$. □

Lemme 2 (majoration). Pour tout $t \geq 0$, $\|w_t\|^2 \leq t R^2$.

Étape 1. À l’initialisation, $\|w_0\|^2 = 0$.

Étape 2. À la $(t+1)$-ème correction :

$$\|w_{t+1}\|^2 \;=\; \|w_t + y_i x_i\|^2 \;=\; \|w_t\|^2 + 2 y_i \, (w_t \cdot x_i) + \|x_i\|^2.$$

Étape 3. Comme $(x_i, y_i)$ est mal classé par $w_t$, on a $y_i (w_t \cdot x_i) \leq 0$ (sinon, il serait bien classé). Donc le terme du milieu est négatif ou nul :

$$\|w_{t+1}\|^2 \;\leq\; \|w_t\|^2 + \|x_i\|^2 \;\leq\; \|w_t\|^2 + R^2.$$

Étape 4. Par récurrence, $\|w_t\|^2 \leq t R^2$, donc $\|w_t\| \leq \sqrt{t} \, R$. □

Combinaison via Cauchy-Schwarz.

Étape 1. L’inégalité de Cauchy-Schwarz donne, pour deux vecteurs $u, v$ :

$$u \cdot v \;\leq\; \|u\| \, \|v\|.$$

Étape 2. Appliquée à $w_T$ et $w^*$ avec $\|w^*\| = 1$ :

$$w_T \cdot w^* \;\leq\; \|w_T\|.$$

Étape 3. En combinant avec les deux lemmes après $T$ corrections :

$$T \gamma \;\leq\; w_T \cdot w^* \;\leq\; \|w_T\| \;\leq\; \sqrt{T} \, R.$$

Étape 4. On élève au carré et on simplifie par $T$ (qui est positif) :

$$T^2 \gamma^2 \;\leq\; T R^2 \;\;\Longrightarrow\;\; T \;\leq\; \frac{R^2}{\gamma^2}.$$

Résultat. Le nombre de corrections du perceptron est borné par $R^2 / \gamma^2$. Avec un pas $\eta \neq 1$, le facteur $\eta$ apparaîtrait identiquement dans les deux lemmes : le minorant deviendrait $T \, \eta \, \gamma$ et la majoration $T \, \eta^2 \, R^2$. Après Cauchy-Schwarz et simplification, on retrouverait exactement la même borne. Le nombre de corrections ne dépend donc pas du choix de $\eta$, et la procédure converge en un nombre fini d’étapes. □

Lecture intuitive

• Plus la marge $\gamma$ est étroite (deux classes très proches), plus la borne $R^2 / \gamma^2$ explose, et plus la convergence est lente.
• Plus le rayon $R$ est grand (points éloignés de l’origine), plus la borne croît quadratiquement.
• Mais quelle que soit la difficulté, la borne reste finie tant que $\gamma > 0$.

Explore la borne en direct

Glisse les points pour modifier R et γ.

Explorateur de la borne de Novikoff

R (rayon) : 1.44

γ (marge atteinte) : 0.707

T effectif : 1

Borne (R/γ)² : 4.2

Ratio : 24.0%

Erreurs par époque

Réinitialiser les points

Trois choses à observer en jouant :

• Rapproche les deux groupes de points : $\gamma$ rétrécit et la borne $(R / \gamma)^2$ explose, alors que le $T$ effectif augmente plus modérément.
• Éloigne un point isolé du centre : $R$ grossit, la borne aussi, mais le $T$ effectif n’augmente pas forcément autant.
• Le ratio $T / (R/\gamma)^2$ est généralement bien inférieur à $1$ : la borne est pessimiste, mais elle existe.

Et si le dataset n’est pas séparable ?

Le théorème de Novikoff fait une hypothèse cruciale : il existe un séparateur linéaire de marge $\gamma > 0$. Que se passe-t-il quand cette hypothèse tombe ?

Le perceptron oscille

La borne $T \leq R^2 / \gamma^2$ est démontrée sous l’hypothèse $\gamma > 0$. Quand le dataset n’est pas linéairement séparable, $\gamma$ n’est pas défini : il n’existe aucun couple $(w, b)$ qui classe tout correctement. Conséquence : la règle d’apprentissage de Rosenblatt continue à corriger en boucle, sans jamais converger. Le vecteur de poids $w$ oscille indéfiniment, et même les itérations qui passent par un « presque bon » $(w, b)$ sont perdues à l’itération suivante quand un autre exemple mal classé déclenche un update qui dégrade ce qu’on avait.

Le Pocket Algorithm de Gallant

La solution classique est étonnamment simple : on garde en poche le meilleur $(w, b)$ jamais rencontré. À chaque mise à jour de la règle de Rosenblatt, on évalue le nouveau $(w, b)$ sur l’ensemble du dataset, on compte le nombre d’exemples bien classés, et si ce nombre dépasse celui du couple « en poche », on remplace. À la fin (après un budget fixé d’itérations, qu’on peut choisir grand), on retourne le contenu de la poche, pas la dernière valeur de $(w, b)$.

Cette procédure, le Pocket Algorithm, a été introduite par Gallant (1990). Sur dataset séparable elle se réduit au perceptron classique (la poche finit par contenir un séparateur parfait). Sur dataset non séparable, elle converge en probabilité vers le séparateur qui maximise le nombre d’exemples bien classés. On perd la garantie de Novikoff, mais on récupère une procédure utilisable en pratique.

L’impossibilité de XOR

L’analogie du damier impossible

Imagine quatre cases d’un damier : les diagonales sont alternées (deux blanches en bas-gauche et haut-droite, deux noires en haut-gauche et bas-droite). Aucune ligne droite ne peut séparer les deux blanches des deux noires. C’est exactement la situation de la fonction XOR.

Énoncé

La fonction $\text{XOR}: \{0, 1\}^2 \to \{0, 1\}$ définie par $\text{XOR}(0,0) = 0$, $\text{XOR}(0,1) = 1$, $\text{XOR}(1,0) = 1$, $\text{XOR}(1,1) = 0$ n’est pas réalisable par un seul perceptron.

Démonstration par contradiction

Pour cette démonstration, on revient à l’encodage usuel de XOR avec cibles dans $\{0, 1\}$ et la convention de la fonction de Heaviside : la sortie vaut $1$ si $w \cdot x + b \geq 0$ et $0$ sinon. Le résultat ne dépend pas du choix d’encodage : passer aux cibles $\{-1, +1\}$ et à la fonction $\operatorname{sgn}$ donne quatre inéquations équivalentes par changement de variable, et la même contradiction.

Supposons qu’il existe $(w_1, w_2, b) \in \mathbb{R}^3$ tels que le perceptron réalise XOR. Alors les quatre contraintes suivantes sont simultanément vraies :

Point $(x_1, x_2)$	XOR	Inéquation
$(0, 0)$	$0$	(1) : $b < 0$
$(1, 0)$	$1$	(2) : $w_1 + b \geq 0$
$(0, 1)$	$1$	(3) : $w_2 + b \geq 0$
$(1, 1)$	$0$	(4) : $w_1 + w_2 + b < 0$

Étape 1. Additionnons (2) et (3) :

$$(w_1 + b) + (w_2 + b) \;\geq\; 0 \;\;\Longrightarrow\;\; w_1 + w_2 + 2b \;\geq\; 0.$$

Étape 2. De (1), $b < 0$, donc $-b > 0$, donc $-2b > 0$. En réécrivant l’étape 1 :

$$w_1 + w_2 \;\geq\; -2b \;>\; 0.$$

La chaîne combine une inégalité large ($\geq -2b$) et une inégalité stricte ($-2b > 0$), donc le résultat est strict : $w_1 + w_2 > 0$.

Étape 3. En ajoutant $b$ de chaque côté :

$$w_1 + w_2 + b \;\geq\; -b \;>\; 0.$$

Étape 4. Mais (4) dit que $w_1 + w_2 + b < 0$.

Résultat. On a simultanément $w_1 + w_2 + b > 0$ et $w_1 + w_2 + b < 0$. Contradiction. Donc aucun triplet $(w_1, w_2, b)$ ne réalise XOR. □

Explore-le toi-même

Pourquoi XOR est impossible

w₁1.00

w₂1.00

b-0.50

Essayer une frontière de type OREssayer une frontière de type ANDRéinitialiser

Les quatre inéquations XOR

(1) (0,0) → 0 : b < 0✓

(2) (1,0) → 1 : w₁ + b ≥ 0✓

(3) (0,1) → 1 : w₂ + b ≥ 0✓

(4) (1,1) → 0 : w₁ + w₂ + b < 0✗

Inéquations satisfaites3 / 4

Pourquoi 4/4 est impossible

Trois choses à observer en jouant :

• Quel que soit le réglage des sliders, on n’atteint jamais 4 / 4 inéquations satisfaites. Le maximum est 3 / 4.
• Le preset « OR-like » satisfait (1), (2), (3) mais viole (4). Le preset « AND-like » satisfait (1), (4) mais viole (2) ou (3). Aucune frontière linéaire ne peut concilier les quatre.
• En cliquant « Pourquoi 4 / 4 est impossible », tu retrouves la démonstration par contradiction sous forme condensée.

Le contexte historique

Marvin Minsky et Seymour Papert Minsky & Papert Marvin Minsky et Seymour Papert, auteurs du livre *Perceptrons* (MIT Press, 1969) qui démontre formellement les limites d'un perceptron simple, notamment l'impossibilité de réaliser la fonction XOR. Leur analyse a contribué au déclin du financement public de la recherche en réseaux de neurones jusqu'au milieu des années 1980. Source : Minsky & Papert, *Perceptrons*, MIT Press, 1969 publient Perceptrons en 1969, livre dont le chapitre central démontre cette impossibilité et la généralise à toute une famille de fonctions « non-locales ». Leur analyse rigoureuse a contribué à un repli du financement public de la recherche en réseaux de neurones, période qu’on appelle aujourd’hui le premier hiver de l’IA Hiver de l'IA Période de désintérêt et de coupure de financement de la recherche en intelligence artificielle. Le premier hiver, années 1970 et début des années 1980, suit la critique du perceptron par Minsky et Papert (1969). Le second, fin des années 1980 et années 1990, suit les déceptions liées aux systèmes experts. Chaque hiver précède un regain : la rétropropagation pour le premier, l'apprentissage profond moderne pour le second. Source : Russell & Norvig, *AIMA*, ch. 1 . Il faudra attendre Hopfield en 1982 et la redécouverte de la rétropropagation par Rumelhart, Hinton et Williams en 1986 pour que la communauté reparte.

Exercices papier-crayon

Exercice 1 : une itération en trois dimensions

Soit $w = (0{,}2, -0{,}5, 0{,}1)$, $b = 0$, $\eta = 0{,}1$. On présente l’exemple $x = (1, 1, -1)$ avec cible $y = +1$.

(a) Calcule la prédiction $\operatorname{sgn}(w \cdot x + b)$. Est-elle correcte ?

(b) Applique la règle d’apprentissage et donne le couple $(w', b')$ après mise à jour.

(c) Vérifie que la nouvelle marge fonctionnelle $\hat\gamma_i' = y (w' \cdot x + b')$ est strictement supérieure à l’ancienne.

Exercice 2 : tester la séparabilité

Le jeu de données $\{((0, 0), +1), ((1, 1), +1), ((1, 0), -1), ((0, 1), -1)\}$ est-il linéairement séparable ? Justifie.

Exercice 3 : un perceptron explicite pour NAND

Trouve explicitement $(w_1, w_2, b)$ tels que le perceptron réalise la fonction NAND, c’est-à-dire $\text{NAND}(x_1, x_2) = 1$ sauf si $x_1 = x_2 = 1$. Vérifie ta solution sur les quatre points.

Exercice 4 : sans biais, Novikoff peut échouer

On force $b = 0$ pendant tout l’apprentissage (le perceptron ne met à jour que les poids $w$, pas le biais). Donne un dataset de deux points en dimension $1$, linéairement séparable, pour lequel l’algorithme du perceptron sans biais ne converge pas. Justifie.

En une phrase

Le perceptron prouve qu’une machine peut construire géométriquement la frontière qui sépare deux classes, sans calculer de dérivée, en un nombre fini d’étapes : à condition que cette frontière soit une droite, et XOR ne l’est pas.

Vers le chapitre 5 : empiler résout XOR

XOR n’est pas linéairement séparable, mais on peut l’écrire comme une composition de fonctions qui le sont :

$$\text{XOR}(x_1, x_2) \;=\; \big( x_1 \;\vee\; x_2 \big) \;\wedge\; \neg\big( x_1 \;\wedge\; x_2 \big).$$

OR est linéairement séparable, et $\neg(x_1 \wedge x_2) = \text{NAND}(x_1, x_2)$ l’est aussi (tu viens de le démontrer en exercice 3). En posant $u = x_1 \vee x_2$ et $v = \text{NAND}(x_1, x_2)$, on a $\text{XOR}(x_1, x_2) = u \wedge v = \text{AND}(u, v)$, et AND est lui-même séparable. Trois perceptrons, deux dans une première couche (OR et NAND) puis un dans une seconde (AND), suffisent donc à résoudre XOR :

C’est exactement ce que le chapitre 5 va formaliser : empiler des perceptrons en couches élargit drastiquement la classe de fonctions que le réseau peut représenter. Au chapitre 5, un seul neurone séparera l’espace en deux ; plusieurs neurones organisés en couches sépareront en régions arbitrairement complexes.

Quiz

Quiz

1. 1. Pourquoi la règle d'apprentissage du perceptron n'a-t-elle pas besoin de calculer une dérivée ?

   • Parce que la fonction signe est dérivable partout.
   • Parce que l'update est une correction géométrique locale : on déplace w dans la direction de l'exemple mal classé, sans optimiser une fonction de coût continue.
   • Parce que Rosenblatt n'avait pas encore inventé le calcul différentiel.
   Valider

2. 2. Sur un dataset non linéairement séparable, que se passe-t-il avec le perceptron ?

   • Il converge vers la meilleure frontière possible au sens des moindres carrés.
   • Il oscille indéfiniment, sans jamais classer tous les exemples correctement.
   • Il diverge : les poids partent à l'infini.
   Valider

3. 3. Dans l'update w ← w + η y x, pourquoi multiplie-t-on par x et pas par autre chose ?

   • Pour normaliser le pas.
   • Pour que seuls les poids dont l'entrée a contribué à l'erreur soient corrigés : une composante nulle de x laisse le poids correspondant inchangé.
   • Parce que c'est plus rapide à calculer.
   Valider

4. 4. Quelle est la signification géométrique de b dans l'équation w · x + b = 0 ?

   • C'est la pente de l'hyperplan.
   • C'est tel que b / ‖w‖ est la distance signée de l'origine à l'hyperplan ; en valeur absolue, |b| / ‖w‖ est la distance perpendiculaire.
   • C'est la norme du vecteur normal.
   Valider

5. 5. Pourquoi XOR n'est-il pas réalisable par un seul perceptron, et que va faire le chapitre 5 ?

   • Parce que XOR a quatre valeurs au lieu de deux ; le chapitre 5 va utiliser un perceptron à quatre entrées.
   • Parce que la fonction XOR n'est pas linéairement séparable (démontré par contradiction) ; le chapitre 5 va l'écrire comme composition (x₁ OR x₂) AND NOT(x₁ AND x₂) et empiler trois perceptrons en deux couches.
   • Parce que XOR est NP-difficile ; le chapitre 5 va utiliser une approximation polynomiale.
   Valider

Sources

• Rosenblatt, F. (1958). « The perceptron: A probabilistic model for information storage and organization in the brain ». Psychological Review 65(6), 386-408. DOI 10.1037/h0042519
• Novikoff, A. B. J. (1962). « On convergence proofs on perceptrons ». Symposium on the Mathematical Theory of Automata 12, 615-622.
• Minsky, M. & Papert, S. (1969). Perceptrons: An Introduction to Computational Geometry. MIT Press. ISBN 978-0-262-13043-1.
• Gallant, S. I. (1990). « Perceptron-Based Learning Algorithms ». IEEE Transactions on Neural Networks 1(2), 179-191. (Introduction du Pocket Algorithm.) DOI 10.1109/72.80230
• Bishop, C. M. (2006). Pattern Recognition and Machine Learning, ch. 4. Springer. ISBN 978-0-387-31073-2.
• Hastie, T., Tibshirani, R. & Friedman, J. (2009). The Elements of Statistical Learning, ch. 4. Springer. ISBN 978-0-387-84857-0.
• Goodfellow, I., Bengio, Y. & Courville, A. (2016). Deep Learning, ch. 1. MIT Press. ISBN 978-0-262-03561-3.

Pour aller plus loin

• Cortes, C. & Vapnik, V. (1995). « Support-Vector Networks ». Machine Learning 20(3), 273-297. Les SVM sont précisément le perceptron à marge maximale : là où la règle de Rosenblatt accepte n’importe quel séparateur valide, SVM optimise le séparateur dont la marge géométrique $\gamma$ (celle-là même qui apparaît dans Novikoff) est la plus grande possible. C’est l’héritage direct du perceptron, et la pierre angulaire de l’apprentissage supervisé pré-2012. DOI 10.1007/BF00994018
• Freund, Y. & Schapire, R. E. (1999). « Large Margin Classification Using the Perceptron Algorithm ». Machine Learning 37(3), 277-296. Introduit le voted perceptron qui agrège les hypothèses intermédiaires : sur dataset bruité, performance proche de SVM pour un coût comparable au perceptron. DOI 10.1023/A:1007662407062