Movatterモバイル変換

[0]ホーム
URL:

Aller au contenu
Wikipédial'encyclopédie libre
Rechercher

Perceptron

Un article de Wikipédia, l'encyclopédie libre.
Perceptron
Type
Inventeur
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)Voir et modifier les données sur Wikidata

modifier -modifier le code -modifier WikidataDocumentation du modèle

Leperceptron est un algorithme d'apprentissage supervisé de classifieurs binaires (c'est-à-dire séparant deux classes). Il a été inventé en 1957 parFrank Rosenblatt[1] aulaboratoire d'aéronautique de l'université Cornell. Il s'agit d'unneurone formel muni d'une règle d'apprentissage qui permet de déterminer automatiquement lespoids 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.

Définition

[modifier |modifier le code]
Schéma d'un perceptron à n entrées.
Les entréesi1 àin sont multipliées avec les poids W1 à Wn, puis sommées, avant qu'une fonction d'activation soit appliquée.

Le perceptron peut être vu comme le type deréseau de neurones le plus simple. C'est unclassifieur linéaire. Ce type de réseau neuronal ne contient aucun cycle (il s'agit d'unréseau de neurones à propagation avant). Dans sa version simplifiée, 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 desnombres réels.

Un perceptron àn entréesx=(x1,…,xn){\displaystyle x=(x_{1},\dots ,x_{n})} et à une seule sortieo est défini par la donnée den poids (aussi appeléscoefficients synaptiques[réf. nécessaire])(w1,…,wn){\displaystyle (w_{1},\dots ,w_{n})} et un biais (ou seuil)θ{\displaystyle \theta } par[2]:

o={1si∑i=1nwixi≥θ0sinon{\displaystyle o=\left\{{\begin{matrix}1&\mathrm {si} &\sum _{i=1}^{n}w_{i}x_{i}\geq \theta \\0&\mathrm {sinon} &\end{matrix}}\right.}

La sortieo résulte alors de l'application de lafonction de Heaviside au potentiel post-synaptiquez=∑i=1nwixi−θ{\displaystyle z=\sum _{i=1}^{n}w_{i}x_{i}-\theta }, où la fonction de Heaviside est :

∀z∈R, H(z)={0siz<01siz≥0.{\displaystyle \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 alorso=H(∑i=1nwixi−θ){\displaystyle o=H\left(\sum _{i=1}^{n}w_{i}x_{i}-\theta \right)}. La fonctionH{\displaystyle H} est non linéaire et appeléefonction d'activation. Une alternative couramment employée estf=tanh{\displaystyle f=\tanh }, latangente hyperbolique.

Exemple

[modifier |modifier le code]
Un perceptron qui calcule le OU logique.

La figure de droite montre un perceptron avec 2 entréesx{\displaystyle x} ety{\displaystyle y}. Les poids sont marqués sur les arcs : 1 et 1. Le biais est de 1. Ce perceptron calcule le OU logique dex{\displaystyle x} ety{\displaystyle y}, comme le montre la table suivante :

xyx+yx+y≥{\displaystyle \geq } 1 ?valeur de la sortie
000non0
101oui1
011oui1
112oui1

Algorithme d'apprentissage

[modifier |modifier le code]

Notations

[modifier |modifier le code]

Dans la suite de cet article, on considère un échantillon fini de données labéliséesS={(X1,y1), … ,(Xn,yn)}{\displaystyle {\mathcal {S}}=\{(X_{1},y_{1}),~\dots ~,(X_{n},y_{n})\}}, avec pour toutk∈[[1,n]]{\displaystyle k\in [\![1,\,n]\!]},Xk=(x1(k),…,xd(k),xd+1(k))∈Rd+1{\displaystyle X_{k}=(x_{1}^{(k)},\dots ,x_{d}^{(k)},x_{d+1}^{(k)})\in \mathbb {R} ^{d+1}}, oùxd+1(k)=1{\displaystyle x_{d+1}^{(k)}=1}[a], etyk∈{−1,1}{\displaystyle y_{k}\in \{-1,\,1\}}. On dit alors que les vecteursXk{\displaystyle X_{k}} sont les « exemples » et que les pointsyk{\displaystyle y_{k}} sont leurs « classes ». Puisque le perceptron ne traite que les problèmes de classification binaire, lesyk{\displaystyle y_{k}} ne peuvent prendre que deux valeurs, par convention−1{\displaystyle -1} et1{\displaystyle 1}.

Enfin, on poseR=maxk∈[[1,n]]‖Xk‖{\displaystyle R=\max _{k\in [\![1,n]\!]}\|X_{k}\|}, etγ=maxW∈Rd+1min{y⟨W,X⟩‖W‖|(X,y)∈S}{\displaystyle \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 queS{\displaystyle {\mathcal {S}}} est linéairement séparable, doncγ{\displaystyle \gamma } est (strictement) positif. Le fait queγ{\displaystyle \gamma } soit non-nul découle du lemme suivant :

Lemme de séparabilité linéaire stricte[3] — 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. :

∃(W,b)∈Rd×R,∀(Xk,yk)∈S,yk(⟨W,Xk⟩+b)>0.{\displaystyle \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[4] — SoitS{\displaystyle {\mathcal {S}}} un échantillon de données labélisées linéairement séparables. Soit(W,b){\displaystyle (W,b)} un hyperplan séparant les données deS{\displaystyle {\mathcal {S}}}. On a alors :{⟨W,Xk⟩+b≥0si yk=1⟨W,Xk⟩+b<0si yk=−1.{\displaystyle {\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ε=−maxk{⟨W,Xk⟩+b|yk=−1}{\displaystyle \varepsilon =-\max _{k}\left\{\langle W,X_{k}\rangle +b\,|\,y_{k}=-1\right\}}. On a alors :{⟨W,Xk⟩+b+ε2≥ε2>0si yk=1⟨W,Xk⟩+b+ε2≤−ε2<0si yk=−1.{\displaystyle {\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+ε2){\displaystyle (W,b+{\frac {\varepsilon }{2}})} démontre donc le lemme.

Énoncé

[modifier |modifier le code]

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[5],[6] :

Entrées : un échantillonS={(X1,y1), … ,(Xn,yn)}{\displaystyle {\mathcal {S}}=\{(X_{1},y_{1}),~\dots ~,(X_{n},y_{n})\}}de données labéliséesSortie : la matriceW{\displaystyle W} de poids telle que∀(Xk,yk)∈S,yk(⟨W,Xk⟩+b)>0{\displaystyle \forall (X_{k},y_{k})\in S,\quad y_{k}(\langle W,X_{k}\rangle +b)>0}1 InitialiserW=0Rd+1{\displaystyle W=0_{\mathbb {R} ^{d+1}}}2Répéter3Pouri=1{\displaystyle i=1}àn{\displaystyle n}4Siyi⟨W,Xi⟩≤0{\displaystyle y_{i}\langle W,X_{i}\rangle \leq 0}alors5W←W+yiXi{\displaystyle W\leftarrow W+y_{i}X_{i}}6Fin pour7jusqu'à ce qu'il n'y ait plus d'erreurs8RetournerW{\displaystyle W}

L'algorithme du perceptron de Rosenblatt est un cas particulier de l'algorithme du gradient stochastique utilisant commefonction objectifC(W)=∑i∈Myi⟨W,Xi⟩{\displaystyle C(W)=\sum _{i\in {\mathcal {M}}}y_{i}\langle W,X_{i}\rangle }, oùM{\displaystyle {\mathcal {M}}} est l'ensemble des exemples mal classés ; et un taux d'apprentissage de1{\displaystyle 1}[7].

Convergence

[modifier |modifier le code]

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

Théorème de convergence de Novikoff[8],[9] — 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/γ)2{\displaystyle (R/\gamma )^{2}} itérations.

Démonstration[10] — On note(Wk){\displaystyle (W_{k})} la suite des valeurs prises parW{\displaystyle W} lors de l'exécution de l'algorithme. On a doncW1=0{\displaystyle W_{1}=0}. On suppose que l'algorithme faitk{\displaystyle k} erreurs, et que lak{\displaystyle k}-ième erreur est faite sur l'exempleXt{\displaystyle X_{t}}. On noteW∗{\displaystyle W^{*}} les paramètres d'un hyperplan classant correctement tous les exemples, avec‖W∗‖=1{\displaystyle \|W^{*}\|=1}.

On a donc, en appliquant l'algorithme :

⟨Wk+1,W∗⟩=⟨Wk+ytXt,W∗⟩=⟨Wk,W∗⟩+yt⟨Xt,W∗⟩≥⟨Wk,W∗⟩+γ≥kγ{\displaystyle {\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γ{\displaystyle \gamma }. La quatrième ligne s'obtient par récurrence, puisqueW1=0{\displaystyle W_{1}=0}. Or, d'après l'inégalité de Cauchy-Schwarz,‖Wk+1‖ ‖W∗‖≥⟨Wk+1,W∗⟩{\displaystyle \|W_{k+1}\|~\|W^{*}\|\geq \langle W_{k+1},W^{*}\rangle }, et‖W∗‖=1{\displaystyle \|W^{*}\|=1} donc,‖Wk+1‖≥kγ{\displaystyle \|W_{k+1}\|\geq k\gamma }.

De plus :

‖Wk+1‖2=‖Wk+ytXt‖2=‖Wk‖2+yt2‖Xt‖2+2yt⟨Xt,Wk⟩≤‖Wk‖2+R2,{\displaystyle {\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}}}

puisqueyt2‖Xt‖2=‖Xt‖2≤R2{\displaystyle y_{t}^{2}\|X_{t}\|^{2}=\|X_{t}\|^{2}\leq R^{2}} etyt⟨Xt,Wk⟩≤0{\displaystyle y_{t}\langle X_{t},W_{k}\rangle \leq 0}, car l'algorithme se trompe sur let{\displaystyle t}-ième exemple à lak{\displaystyle k}-ième itération. Finalement, on obtient par récurrence que :‖Wk+1‖2≤kR2{\displaystyle \|W_{k+1}\|^{2}\leq kR^{2}}.

Donc,k2γ2≤‖Wk+1‖2≤kR2{\displaystyle k^{2}\gamma ^{2}\leq \|W_{k+1}\|^{2}\leq kR^{2}}. On en déduit enfin quek≤(R/γ)2{\displaystyle 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(Wk){\displaystyle (W_{k})} est périodique. Le cycle peut cependant être long et difficile à détecter.

Règle de Hebb

[modifier |modifier le code]
Article détaillé :règle de Hebb.

La règle de Hebb, établie parDonald Hebb[11], est une règle d'apprentissage desréseaux de neurones artificiels dans le contexte de l'étude d'assemblées de neurones.

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

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

Wi′=Wi+α(Y.Xi){\displaystyle W'_{i}=W_{i}+\alpha (Y.X_{i})}

oùWi′{\displaystyle W'_{i}} représente le poidsi{\displaystyle i} corrigé etα{\displaystyle \alpha } représente le pas d'apprentissage.

Cette règle n'est malheureusement pas applicable dans certains cas bien que la solution existe.

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

[modifier |modifier le code]

Le perceptron deFrank Rosenblatt est très proche de larè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 latangente hyperbolique (tanh) est utilisée comme fonction d'activation.

Wi′=Wi+α(Yt−Y)Xi{\displaystyle W'_{i}=W_{i}+\alpha (Y_{t}-Y)X_{i}}

avec :

Notes et références

[modifier |modifier le code]

Notes

[modifier |modifier le code]
  1. ↑Ainsi, le biais est inclus dans le vecteurXk{\displaystyle X_{k}}.

Références

[modifier |modifier le code]
  1. ↑« Psychological Review Vol. 65, No. 6, 1958 "THE PERCEPTRON: A PROBABILISTIC MODEL FOR INFORMATION STORAGE AND ORGANIZATION IN THE BRAIN" - F. ROSENBLATT », surciteseerx.ist.psu.edu(consulté le)
  2. ↑Le Perceptron, dans Marc Tommasi ,Apprentissage automatique : les réseaux de neurones, cours à l'université de Lille 3.
  3. ↑(en) Barnabás Póczos, « Convex Optimization : Lecture 2, Linear Programming »Accès libre[PDF], surCarnegie Mellon University,.
  4. ↑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 »Accès libre[PDF].
  5. ↑(en) Frank Rosenblatt, « The Perceptron, A perceiving and recognizing automaton »,Cornell Aeronautical Laboratory,‎(lire en ligneAccès libre[PDF]).
  6. ↑(en) Jean-Christophe B.Loiseau, « Rosenblatt’s perceptron, the very first neural network », surMedium,(consulté le).
  7. ↑Hastie,The Elements of Statistical Learning,p. 131.
  8. ↑(en) Albert Novikoff,On convergence proofs for Perceptrons, Washington, D.C., Office of Naval Research et Stanford Research Institute,(lire en ligne[PDF]),p. 2.
  9. ↑(en) CharlieMurphy, PatrickGray et GordonStewart, « Verified perceptron convergence theorem »,Proceedings of the 1st ACM SIGPLAN International Workshop on Machine Learning and Programming Languages, Association for Computing Machinery, mAPL 2017,‎,p. 43–50(ISBN 978-1-4503-5071-6,DOI 10.1145/3088525.3088673,lire en ligneAccès payant, consulté le).
  10. ↑(en) Michael Collins, « Convergence Proof for the Perceptron Algorithm »Accès libre[PDF], surUniversité Columbia.
  11. ↑ Donald Olding HEBB, The Organization of Behavior, New York, Wiley & Sons, 1949.

Voir aussi

[modifier |modifier le code]

Bibliographie

[modifier |modifier le code]
  • F. Rosenblatt (1958),The perceptron: a probabilistic model for information storage and organization in the brain,
- repris dans J.A. Anderson & E. Rosenfeld (1988), Neurocomputing. Foundations of Research, MIT Press


v ·m
Concepts
Techniques
Applications
Enjeux et philosophie
Histoire et événements
Science-fiction
Règlementation
Organisations
Ouvrages
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Perceptron&oldid=223640459 ».
Catégories :
Catégories cachées :
[8]ページ先頭
©2009-2025 Movatter.jp