Perceptron

Le perceptron est un algorithme d'apprentissage supervisé de classifieurs binaires (c'est-à-dire séparant deux classes). Il a été inventé en 1957 par Frank Rosenblatt^[1] au laboratoire d'aéronautique de l'université Cornell. Il s'agit d'un neurone formel muni d'une règle d'apprentissage qui permet de déterminer automatiquement les poids synaptiques de manière à séparer un problème d'apprentissage supervisé. Si le problème est linéairement séparable, un théorème assure que la règle du perceptron permet de trouver une séparation entre les deux classes.

Type

Algorithme, réseau de neurones à action directe

Inventeur

Frank Rosenblatt

Décrit par

The perceptron: a probabilistic model for information storage and organization in the brain (d), Encyclopédie soviétique arménienne, Perceptrons (en)

Faits en bref Type, Inventeur ...

Perceptron

Schéma d'un perceptron à n entrées. Les entrées i₁ à i_n sont multipliées avec les poids W₁ à W_n, puis sommées, avant qu'une fonction d'activation soit appliquée.

Type	Algorithme, réseau de neurones à action directe
Inventeur	Frank Rosenblatt
Décrit par	The perceptron: a probabilistic model for information storage and organization in the brain (d), Encyclopédie soviétique arménienne, Perceptrons (en)

Fermer

Définition

Le perceptron est le réseau de neurones à action directe le plus simple. Dans sa version initiale, le perceptron est mono-couche et n'a qu'une seule sortie (booléenne) à laquelle toutes les entrées (booléennes) sont connectées. Plus généralement, les entrées peuvent être des nombres réels et c'est alors un classifieur linéaire de données vectorielles réelles.

Un perceptron à n entrées $x=(x_{1},\dots ,x_{n})$ et à une seule sortie y est un modèle paramétrique défini par n poids $(w_{1},\dots ,w_{n})$ et un biais (ou seuil) $\theta$ par^[2]^,^[3]:

y=\left\{{\begin{matrix}1&\mathrm {si} &\sum _{i=1}^{n}w_{i}x_{i}\geq \theta \\0&\mathrm {sinon} &\end{matrix}}\right.

La sortie y résulte alors de l'application de la fonction de Heaviside au potentiel post-synaptique $z=\sum _{i=1}^{n}w_{i}x_{i}-\theta$ , où la fonction de Heaviside est :

\forall z\in \mathbb {R} ,\ H(z)=\left\{{\begin{matrix}0&\mathrm {si} &z<0\\1&\mathrm {si} &z\geq 0.\end{matrix}}\right.

On a alors $y=H\left(\sum _{i=1}^{n}w_{i}x_{i}-\theta \right)$ . La fonction $H$ est non linéaire et appelée fonction d'activation. Une alternative couramment employée est $f=\tanh$ , la tangente hyperbolique.

Algorithme d'apprentissage

Notations

Dans la suite de cet article, on considère un échantillon fini de données labélisées ${\mathcal {S}}=\{(X_{1},y_{1}),~\dots ~,(X_{n},y_{n})\}$ , avec pour tout $k\in [\![1,\,n]\!]$ , $X_{k}=(x_{1}^{(k)},\dots ,x_{d}^{(k)},x_{d+1}^{(k)})\in \mathbb {R} ^{d+1}$ , où $x_{d+1}^{(k)}=1$ ^[a], et $y_{k}\in \{-1,\,1\}$ . On dit alors que les vecteurs $X_{k}$ sont les « exemples » et que les points $y_{k}$ sont leurs « classes ». Puisque le perceptron ne traite que les problèmes de classification binaire, les $y_{k}$ ne peuvent prendre que deux valeurs, par convention $-1$ et $1$ .

Enfin, on pose $R=\max _{k\in [\![1,n]\!]}\|X_{k}\|$ , et $\gamma =\max _{W\in \mathbb {R} ^{d+1}}\min \left\{{\dfrac {y\langle W,X\rangle }{\|W\|}}\,|\,(X,y)\in {\mathcal {S}}\right\}$ .

On suppose également que ${\mathcal {S}}$ est linéairement séparable, donc $\gamma$ est (strictement) positif. Le fait que $\gamma$ soit non-nul découle du lemme suivant :

Lemme de séparabilité linéaire stricte^[4] — S'il existe un hyperplan séparant deux classes de données, alors il existe un hyperplan les séparant et tel qu'aucun exemple ne se trouve dessus, i.e. :

$\exists (W,b)\in \mathbb {R} ^{d}\times \mathbb {R} ,\,\forall (X_{k},y_{k})\in S,\quad y_{k}(\langle W,X_{k}\rangle +b)>0.$

Démonstration^[5]

Soit ${\mathcal {S}}$ un échantillon de données labélisées linéairement séparables. Soit $(W,b)$ un hyperplan séparant les données de ${\mathcal {S}}$ . On a alors : ${\begin{cases}\langle W,X_{k}\rangle +b\geq 0\quad {\text{si }}y_{k}=1\\\langle W,X_{k}\rangle +b<0\quad {\text{si }}y_{k}=-1.\end{cases}}$ Posons $\varepsilon =-\max _{k}\left\{\langle W,X_{k}\rangle +b\,|\,y_{k}=-1\right\}$ . On a alors : ${\begin{cases}\langle W,X_{k}\rangle +b+{\frac {\varepsilon }{2}}\geq {\frac {\varepsilon }{2}}>0\quad {\text{si }}y_{k}=1\\\langle W,X_{k}\rangle +b+{\frac {\varepsilon }{2}}\leq -{\frac {\varepsilon }{2}}<0\quad {\text{si }}y_{k}=-1.\end{cases}}$ L'hyperplan $(W,b+{\frac {\varepsilon }{2}})$ démontre donc le lemme.

Énoncé

Il existe plusieurs algorithmes d'apprentissage pour un perceptron. L'un des premiers est l'algorithme du perceptron de Rosenblatt, inventé en 1957, qui a pour but de trouver les paramètres d'un hyperplan séparant correctement les deux classes de données^[6]^,^[7] :

Entrées : un échantillon  ${\mathcal {S}}=\{(X_{1},y_{1}),~\dots ~,(X_{n},y_{n})\}$  de données labellisées
Sortie : la matrice  $W$  de poids telle que  $\forall (X_{k},y_{k})\in S,\quad y_{k}(\langle W,X_{k}\rangle +b)>0$ 
1 Initialiser  $W=0_{\mathbb {R} ^{d+1}}$ 
2 Répéter
3    Pour  $i=1$  à  $n$ 
4        Si  $y_{i}\langle W,X_{i}\rangle \leq 0$  alors
5             $W\leftarrow W+y_{i}X_{i}$ 
6    Fin pour
7 jusqu'à ce qu'il n'y ait plus d'erreurs
8 Retourner  $W$

L'algorithme du perceptron de Rosenblatt est un cas particulier de l'algorithme du gradient stochastique utilisant comme fonction objectif $C(W)=\sum _{i\in {\mathcal {M}}}y_{i}\langle W,X_{i}\rangle$ , où ${\mathcal {M}}$ est l'ensemble des exemples mal classés ; et un taux d'apprentissage de $1$ ^[8].

Convergence

La convergence de l'algorithme est démontrée en 1962 par Novikoff.

Théorème de convergence de Novikoff^[9]^,^[10] — L'algorithme du Perceptron de Rosenblatt converge si et seulement si l'échantillon de données entré est linéairement séparable. La convergence se fait en au plus $(R/\gamma )^{2}$ itérations.

Démonstration^[11] — On note $(W_{k})$ la suite des valeurs prises par $W$ lors de l'exécution de l'algorithme. On a donc $W_{1}=0$ . On suppose que l'algorithme fait $k$ erreurs, et que la $k$ -ième erreur est faite sur l'exemple $X_{t}$ . On note $W^{*}$ les paramètres d'un hyperplan classant correctement tous les exemples, avec $\|W^{*}\|=1$ .

On a donc, en appliquant l'algorithme :

${\begin{aligned}\langle W_{k+1},W^{*}\rangle &=\langle W_{k}+y_{t}X_{t},W^{*}\rangle \\&=\langle W_{k},W^{*}\rangle +y_{t}\langle X_{t},W^{*}\rangle \\&\geq \langle W_{k},W^{*}\rangle +\gamma \\&\geq k\gamma \end{aligned}}$

La troisième ligne découle de la définition de $\gamma$ . La quatrième ligne s'obtient par récurrence, puisque $W_{1}=0$ . Or, d'après l'inégalité de Cauchy-Schwarz, $\|W_{k+1}\|~\|W^{*}\|\geq \langle W_{k+1},W^{*}\rangle$ , et $\|W^{*}\|=1$ donc, $\|W_{k+1}\|\geq k\gamma$ .

De plus :

${\begin{aligned}\|W_{k+1}\|^{2}&=\|W_{k}+y_{t}X_{t}\|^{2}\\&=\|W_{k}\|^{2}+y_{t}^{2}\|X_{t}\|^{2}+2y_{t}\langle X_{t},W_{k}\rangle \\&\leq \|W_{k}\|^{2}+R^{2},\end{aligned}}$

puisque $y_{t}^{2}\|X_{t}\|^{2}=\|X_{t}\|^{2}\leq R^{2}$ et $y_{t}\langle X_{t},W_{k}\rangle \leq 0$ , car l'algorithme se trompe sur le $t$ -ième exemple à la $k$ -ième itération. Finalement, on obtient par récurrence que : $\|W_{k+1}\|^{2}\leq kR^{2}$ .

Donc, $k^{2}\gamma ^{2}\leq \|W_{k+1}\|^{2}\leq kR^{2}$ . On en déduit enfin que $k\leq (R/\gamma )^{2}$ .

Lorsque les données entrées ne sont pas linéairement séparables, l'algorithme ne converge pas, et la suite $(W_{k})$ est périodique. Le cycle peut cependant être long et difficile à détecter.

Règle de Hebb

Article détaillé : règle de Hebb.

La règle de Hebb, établie par Donald Hebb^[12], est une règle d'apprentissage des réseaux de neurones artificiels dans le contexte de l'étude d'assemblées de neurones.

Cette règle suggère que lorsque deux neurones sont excités conjointement, ils créent ou renforcent un lien les unissant.

Dans le cas d'un neurone artificiel seul utilisant la fonction signe comme fonction d'activation cela signifie que :

W'_{i}=W_{i}+\alpha (Y.X_{i})

où $W'_{i}$ représente le poids $i$ corrigé et $\alpha$ représente le pas d'apprentissage.

Cette règle n'est malheureusement pas applicable dans certains cas bien que la solution existe.^[Quoi ?]

Règle d'apprentissage du perceptron (loi de Widrow-Hoff)

Le perceptron de Frank Rosenblatt est très proche de la règle de Hebb, la grande différence étant qu'il tient compte de l'erreur observée en sortie.

Cette fonction est recommandée lorsque la tangente hyperbolique (tanh) est utilisée comme fonction d'activation.

W'_{i}=W_{i}+\alpha (Y_{t}-Y)X_{i}

avec :

$W'_{i}$ = le poids $i$ corrigé ;
$Y_{t}$ = sortie attendue ;
$Y$ = sortie observée ;
$\alpha$ = le taux d'apprentissage ;
$X_{i}$ = l'entrée du poids $i$ pour la sortie attendue $Y_{t}$ ;
$W_{i}$ = le poids $i$ actuel.

Notes et références

Notes

[a]
Ainsi, le biais est inclus dans le vecteur $X_{k}$ .

Références

[1]
« Psychological Review Vol. 65, No. 6, 1958 "THE PERCEPTRON: A PROBABILISTIC MODEL FOR INFORMATION STORAGE AND ORGANIZATION IN THE BRAIN" - F. ROSENBLATT », sur citeseerx.ist.psu.edu (consulté le 1^er mai 2018)
[2]
Le Perceptron, dans Marc Tommasi , Apprentissage automatique : les réseaux de neurones, cours à l'université de Lille 3.
[3]
Arnaud Bodin, François Recher, « DEEPMATH, p.65 », sur exo7, 2023
[4]
(en) Barnabás Póczos, « Convex Optimization : Lecture 2, Linear Programming » [PDF], sur Carnegie Mellon University, 2013.
[5]
Stéphane Ayache, Cécile Capponi, François Denis, Rémi Eyraud, Hachem Kadr et Liva Ralaivola, « Classication, Apprentissage, Décision : Chapitre cinquième : Perceptron » [PDF].
[6]
(en) Frank Rosenblatt, « The Perceptron, A perceiving and recognizing automaton », Cornell Aeronautical Laboratory,‎ janvier 1957 (lire en ligne [PDF]).
[7]
(en) Jean-Christophe B. Loiseau, « Rosenblatt’s perceptron, the very first neural network », sur Medium, 10 janvier 2022 (consulté le 30 juin 2022).
[8]
Hastie, The Elements of Statistical Learning, p. 131.
[9]
(en) Albert Novikoff, On convergence proofs for Perceptrons, Washington, D.C., Office of Naval Research et Stanford Research Institute, janvier 1963 (lire en ligne [PDF]), p. 2.
[10]
(en) Charlie Murphy, Patrick Gray et Gordon Stewart, « Verified perceptron convergence theorem », Proceedings of the 1st ACM SIGPLAN International Workshop on Machine Learning and Programming Languages, Association for Computing Machinery, mAPL 2017,‎ 18 juin 2017, p. 43–50 (ISBN 978-1-4503-5071-6, DOI 10.1145/3088525.3088673, lire en ligne , consulté le 30 juin 2022).
[11]
(en) Michael Collins, « Convergence Proof for the Perceptron Algorithm » [PDF], sur Université Columbia.
[12]
Donald Olding HEBB, The Organization of Behavior, New York, Wiley & Sons, 1949.