Résumé
Domaine des réseaux de
neurones
Domaines d’application de l ’IA
Vision
Robotique
Langages
Parole naturels
Tâches
formelles
Sens
Réseaux
commun
neuroniques
Systèmes
experts
Cours #10GPA-779
- 2 Application des réseaux de neurones et des systèmes experts
Domaines d’application de l ’IA
Vision
Robotique
Langages
Parole naturels
Tâches
formelles
Sens
Réseaux
commun
neuroniques
Systèmes
experts
Cours #10GPA-779
- 3 Application des réseaux de neurones et des systèmes experts
Domaines d’application de l ’IA
Vision
Robotique
Langages
Parole naturels
Tâches
formelles
Sens
Réseaux
commun
neuroniques
Systèmes
experts
Cours #10GPA-779
- 4 Application des réseaux de neurones et des systèmes experts
Domaines d’application de l ’IA
Vision
Robotique
Langages
Parole naturels
Tâches
formelles
Sens
Réseaux
commun
neuroniques
Systèmes
experts
Cours #10GPA-779
- 5 Application des réseaux de neurones et des systèmes experts
Domaines d’application de l ’IA
Vision
Robotique
Langages
Parole naturels
Tâches
formelles
Sens
Réseaux
commun
neuroniques
Systèmes
experts
Cours #10GPA-779
- 6 Application des réseaux de neurones et des systèmes experts
Domaines d’application de l ’IA
Vision
Robotique
Langages
Parole naturels
Tâches
formelles
Sens
Réseaux
commun
neuroniques
Systèmes
experts
Cours #10GPA-779
- 7 Application des réseaux de neurones et des systèmes experts
Domaines d’application de l ’IA
Vision
Robotique
Langages
Parole naturels
Tâches
formelles
Sens
Réseaux
commun
neuroniques
Systèmes
experts
Cours #10GPA-779
- 8 Application des réseaux de neurones et des systèmes experts
Domaines d’application de l ’IA
Vision
Robotique
Langages
Parole naturels
Tâches
formelles
Sens
Réseaux
commun
neuroniques
Systèmes
experts
Cours #10GPA-779
- 9 Application des réseaux de neurones et des systèmes experts
Domaines d’application de l ’IA
Vision
Robotique
Langages
Parole naturels
Tâches
formelles
Sens
Réseaux
commun
neuroniques
Systèmes
experts
Cours #10GPA-779
- 10 Application des réseaux de neurones et des systèmes experts
Chapitre 1
Réseaux de neurones artificiels
Modèle d’un neurone artificiel N
net = ∑w x −θ
m i=1 mn n m
x1 Wm N
1
y = f (F ( ∑ w x , a )) = f (a )
x2 Wm m n=0 mn n m m
Entrée xk
x3 Wm 3
€ am (k)
Wm ym
x4
4
netm
Wm 5 € = =
x5 Wm
m f(a) Sortie
n
F(net,a)
xn
Wm N
f :
xN
Binaire ou Linéaire Sigmoïde
Signe à seuil
Cours #10GPA-779
- 12 Application des réseaux de neurones et des systèmes experts
netj : Somme pondérée de toutes les
entrées à ce site du neurone
netj : lorsqu’il y a 1 site
skj : lorsqu’il y a plus d’un site par
neurone
I v v
∑
net j= w ji xi=Wj• X
i=0
v v ⎛
net j=W j⋅X cosθ ⎞
⎝ ⎠ W
j
Cours #10GPA-779
- 13 Application des réseaux de neurones et des systèmes experts
N
neti= ∑ winxn±θi
n=1
Δwin=η⋅xn⋅r(win,yi,di)
x1 Wi 1
x2 Wi 2 ΔWi=η r(Wi,yi,di)X
x3 Wi
Entrée X
3
ai (k)
yi Sortie yi
Wi
x4
4
neti
Wi 5 = =
x5 Wi n
j f(a)
F(net,a)
xn Wi N
wi n
Générateur du
xN xn
r
di
Signal
d’apprentissage
Cours #10GPA-779
- 14 Application des réseaux de neurones et des systèmes experts
Taxonomie générale
Réseaux Réseaux
# couches
monocouches multicouches
Anticipation Récurrent Anticipation Résonant dynamique
non non non non
supervisé supervisé supervisé supervisé supervisé supervisé supervisé supervisé apprentis.
Perceptron Compétition Perceptron Multiréso-
Adaline Oja Sanger Hopfield BSB (rétroprop) lution ARTMAP ART 1-2 modèle
Mémoire Cellulaire Boltzmann Eidos Madaline BCS BAM SARDSRN
associative SOFM RBF
LVQ1-2 LVQ Cognitron
Convolution
Cours #10GPA-779
- 15 Application des réseaux de neurones et des systèmes experts
Taxonomie pour la
reconnaissance de formes
Problématique
Extraction Système
X des Y de D
primitives décision
Espace Espace Espace
d'entrée des primitives des décisions
Cours #10GPA-779
- 16 Application des réseaux de neurones et des systèmes experts
Les réseaux de neurones extracteurs de primitives
Réseau de neurones
d’extraction de
primitives Système
de
décision
Espace Espace des Espace
d’objet primitives des
s décision
Cours #10GPA-779
- 17 Application des réseaux de neurones et des systèmes experts
a) Vecteurs propres
Composantes
principales
y
y1
.
z
..
.
...
............
.
z.
.. .. . Système
v . .. .. . ... . ..
j
V2 de
i
x1 .. u décision
j V1
x
i
Espace Espace des Espace
d’objet primitives des
s
Cours #10 - 18
GPA-779 Application des réseaux de neurones et des systèmes experts
décision
b) Prototypes
Vecteurs
prototypes
P3 . . . .. P1
Extraction . .. ... d3 . . d1
des
primitives
. ..
d2
.z
P1, P2, P3 . ...
..
P2
Espace Espace des Espace
d’obje primitives des
ts- 19
Cours #10
GPA-779 Application des réseaux de neurones et des systèmes experts décision
c) Primitives visuelles
Primitives visuelles
Système
de
décision
Espace Espace des Espace
d’objet primitives des
s
Cours #10 - 20
GPA-779 Application des réseaux de neurones et des systèmes experts décision
c) Primitives visuelles (suite)
Éléments linéaires
Système
de
décision
Espace Espace des Espace
d’objet primitives des
s
Cours #10 - 21
GPA-779 Application des réseaux de neurones et des systèmes experts décision
Les réseaux de neurones classifieurs
Réseau de
neurones
classifieur
Extraction
des
primitives
Espace Espace des Espace
d’obje primitives des
ts décision
Cours #10GPA-779
- 22 Application des réseaux de neurones et des systèmes experts
Les réseaux de neurones extracteurs/classifieurs
Réseau d’extraction de primitives /
classifieurs
Extractio Système
n des de
primitive décision
s
Espace Espace des Espace
d’obje primitives des
Cours #10ts (d’observations
- 23 Application des réseaux
GPA-779 de neurones et des systèmes experts
décision
Taxonomie pour la reconnaissance de formes
Extraction de primitives Système de décision
Type (a) : vecteurs propres
réseau d’Oja; réseau de Sanger Réseaux de classification
composantes principales neurone de McCulloch & Pitts
composantes indépendantes perceptron de Rosenblatt
Adaline; Madaline
Type (b) : vecteurs prototypes réseau à base radiale (RBF)
réseaux LVQ; LVQ1 et LVQ2
réseau SOFM de Kohonen
Type (c) : primitives visuelles Mémoires associatives
réseau cellulaire; BCS statiques : matrices
pyramide multirésolution itératives : Hopfield, BAM
réseau impulsionnel de Eckhorn séquentielles : SARDSRN, SARDNET
réseaux convolutifs : ACP : Brain State in a Box, EIDOS
Néocognitron; convolution
Réseaux mixtes d’extraction de primitives et de classification
réseaux multicouches : rétropropagation du gradient d’erreur ; G.A.L.
réseaux résonants : ART1, ART2, ARTMAP
Cours #10GPA-779
- 24 Application des réseaux de neurones et des systèmes experts
Chapitre 2
Domaines d’application
Principaux domaines
d ’application
1. Classification
2. Regroupement
3. Approximation
4. Prédiction
5. Optimisation de
parcours
6. Mémoire
associative
7. Commande
Cours #10GPA-779
- 26 Application des réseaux de neurones et des systèmes experts
Introduction aux
Réseaux de Neurones
Application en Reconnaissance de Formes
B. Solaiman
Dépt. Image & Traitement de l'Information
Ecole Nationale Supérieure des Télécommunications de
Bretagne
Neurone formel
4 Réseaux Madaline
Le neurone formel de McCulloch&Pitts
.AND.
?
.OR.
.XOR.
…....
Fonctions logiques
Version circuit à seuil
x1
1
y yq
N xn
wn
y = X × WT = ∑w n xn Circuit à seuil
n =1
xN
wN
⎧ 1 si y > θ
yq = ⎨
Combinateur linéaire adaptatif
⎩- 1 sinon.
Modèle du neurone formel de
McCulloch&Pitts 1943
Cours #10GPA-779
- 29 Application des réseaux de neurones et des systèmes experts
Exemple
x1 x1
w1=+1 w1=+1
x2 x2
w2=+1 ET w2=+1 OU
x1 x2 Sortie ET Sortie OU
-1 -1 -1 -1
-1 1 -1 1
1 -1 -1 1
1 1 1 1
Cours #10GPA-779
- 30 Application des réseaux de neurones et des systèmes experts
4 Neurone formel - Réseaux Madaline
Le neurone formel et la reconnaissance de formes
1 Sortie binaire Discrimination de 2 classes
C1 -1, et
C2 +1
2 Surface de décision
N
yq < y q = ∑ω xn n <
n =1
N
Hyperplan dans N
: ∑ω x - = 0
n n
n =1
4 Neurone formel - Réseaux Madaline
Surface de décision 2 Surface de décision 3
x2 x3
x2
D +
D+
x1 x1
D - D-
La fonction réalisée par un neurone formel :
La séparation linéaire
4 Neurone formel - Réseaux Madaline
Apprentissage des poids synaptiques
1 deux classes C1 et C2
Apprentissage ? linéairement séparables
2 Surface de séparation :
N
∑ω n x n - = 0
3 Apprentissage n =1
Base d’exemples
(Xk, d(k)) Estimer wn et
d(k) = 1
L’algorithme d’apprentissage de Rosenblatt , 1958
x1(k)
w1
y(k)
yq(k)
xn(k)
wn
xN(k) Algorithme d(k)
wN Nouveaux
de
Rosenblatt
[w1, w2,…, wN]
eq(k)
W(t+1) = W(t) + eq(k) Xk
Cours #10GPA-779
- 34 Application des réseaux de neurones et des systèmes experts
Interprétation géométrique
de l’algorithme de Rosenblatt
x3
Xk W(t+1) = eq(k) Xk
W(t+1)
W(t)
x1
x2
La modification de poids est proportionnelle à l’erreur et au vecteur d’entrée et est
de même direction que ce dernier
Cours #10GPA-779
- 35 Application des réseaux de neurones et des systèmes experts
Le déroulement de l’algorithme d'apprentissage
initialisation aléatoire des poids synaptiques;
tant que CONDITION D’ARRÊT non vérifiée faire
Pour k=1 jusqu'à k=K
faire
présenter la forme Xk à l'entrée;
calculer yq(k);
calculer eq(k);
Pour n = 0 jusqu'à n = N faire
ajustement des poids :
wn(t+1) = wn(t) +
eq (k) xn(k)
Cours #10GPA-779 Fin
- 36 Application des réseaux de neurones et; des systèmes experts
4 Neurone formel - Réseaux Madaline
Rosenblatt a démontré, 1960, la convergence de cet
algorithme pour la séparation de deux classes à condition
qu'elles soient linéairement séparables.
Si eq(k) = 0 yq(k)= d(k)
w(k+1) = w(k) (i.e. pas de modification
des poids synaptiques)
Exemple : = 0, d(k)= 1
y (k) = 0.0001 eq(k) = 0
y (k) = 0.9999
L’algorithme de Widrow-Hoff, 1960
x1(k)
w1
yq(k)
xn(k)
y(k)
wn
xN(k) Algorithme
d(k)
de
wN Widrow-
Nouveaux
[w1, w2,…, wN] Hoff e(k)
Minimiser l'erreur analogique quadratique moyenne : [d(k) - y(k)]2
W(t+1) = W(t) + e(k) Xk
Cours #10GPA-779
- 38 Application des réseaux de neurones et des systèmes experts
4 Neurone formel - Réseaux Madaline
C1 C1 C1
C2 C2 C2
Widrow-Hoff
A p p r e n t i s s a g e
Rosenblatt
C1 C1 C1
C2 C2 C2
6 Applications - OCR
Le neurone formel en reconnaissance de chiffres
Séparation entre deux classes
Classe 1 : -1
Classe 2 : +1
Imagette Poids
d’entrée synaptiques
X
4 Neurone formel - Réseaux Madaline
réseaux Madaline
x2
x1 AN Décision
D
C1 : {-1,+1}
x2 OR Décision
x1
C2 : {-1,+1}
Solution « artificielle »
et si N > 3 ?
Naissance de l’architecture multicouches
Réseaux de Neurones Multicouches
Algorithme de rétropropagation de gradient
B. Solaiman
Dépt. Image & Traitement de l'Information
Ecole Nationale Supérieure des Télécommunications de
Bretagne
1 Réseaux multicouches
x1
x2
X xn
S
xN
Couche Couche Couche Couche de
d’entrée cachée 1 cachée 2 sortie
Comment associer une sortie à chaque classe ?
Classe « m » : X Cm sm=1, et sm’=0 si mm’
Quelle est la nature des sorties ?
Neurone de McCulloch&Pitts
sorties binaires +1 et -1
Comment réaliser l’apprentissage
des poids synaptiques ?
Algorithme du gradient fonctions «dérivables»
« Légère » modification du modèle proposé par McCulloch
& Pitts
1
f( t ) =
1 + e- 2 a t Fonction seuil
1,2
1
0,8 a = 0.5
f(t) 0,6 a =1.0
0,4 a = 1.5
0,2
0 la fonction sigmoïde
t
Nouveau paramètre à régler :
la pente de la fonction sigmoïde
2
L’algorithme de la rétropropagation
du gradient
Hypothèse Base d’apprentissage étiquetée
B = {( X , D ), k=1, 2, …, K}
k k
Xk=[x1(k), .., xi(k), .., xN(k) ]tr
k = 1, 2, .., K indice qui désigne une forme d’entrée
K nombre de formes d’entrée dans la base
N dimension des vecteurs d’entrée
Dk=[d1(k), .., dm(k), .., dM(k) ]tr {0, 1}M
vecteur de sortie désirée correspondant à Xk
Exemple : Trois classes C1, C2 et C3
Xk=[x1(k), .., xi(k), .., xN(k) ]tr : Classe C1
Dk=[1, 0, 0]tr
x1(k)
x2(k)
d1(k) = 1
xi(k) d2(k) = 0
d3(k) = 0
xN(k)
concrètement :
x1(k)
x2(k) s1(k) d1(k)
xi(k) s2(k) d2(k)
s3(k) d3(k)
xN(k)
Fonction du coût : Erreur quadratique instantanée
1 M
2
E =
k 2 ∑ m(d (k) −s m (k))
m =1
Algorithme de descente du gradient classique :
Fonction du coût à minimiser : Coût(p)
Coût(p)
P(n+1) = P(n) -
∂Coût ( p)
∂p P(n)
p
P(n)
P (n+1)
Fonction du coût à minimiser : Coût(p1, p2 ,…., pL)
∂Coût ( p ,..., p ,..., p )
Pl(n+1) = Pl(n) - 1 l L
∂p P (n)
l l
Cas d’une couche cachée
x1(k) s1(k)
x2(k)
Xk vj,n wm,j sm(k) Sk
xn(k)
yj(k)
xN(k)
sM(k)
Vecteur
d’entrée Couche cachée Vecteur de sortie
comportant J neurones obtenu
Cours #10GPA-779
- 50 Application des réseaux de neurones et des systèmes experts
Fonction du coût : Erreur quadratique instantanée
1 M
2
E =
k 2 ∑ m(d (k) −s m (k))
m =1
pour les poids synaptiques wm,j
Δw = η y (k) δ (k)
m, j j m
Wm,j
Erreur liée à sm
L
€ δ (k) = (d (k) − s (k)) f ′( ∑ w y (k))
m m m m, j j
j =1
Cours #10GPA-779
- 51 Application des réseaux de neurones et des systèmes experts
pour les poids synaptiques vj,i
Δv = η x n (k) δ j (k)
j,n
€
vj,n
M
?
δ δ j (k) = f ' ( net j ( k )) ∑ δ (k) w
m m, j
1 m =1
δ' δ
j m
€
δ
M
Cours #10GPA-779
- 52 Application des réseaux de neurones et des systèmes experts
Le déroulement de l'algorithme de la
rétropropagation du gradient
La propagation directe
1. La forme Xk est présentée à l'entrée du réseau
2. Calcul des y (k), j= 1, 2, .., J, et
j sm(k), m= 1, 2, .., M
3. Calcul des (k), m= 1, 2, .., M
m
La rétropropagation
1. Rétropropagation et calcul de , j=1,2, … ,J j
2. Actualisation des poids w m,j
3. Actualisation des poids v j,n
Cours #10GPA-779
- 53 Application des réseaux de neurones et des systèmes experts
Résumé: fonctionnement du rétro-prop.
a) propagation directe
Cours #10GPA-779
- 54 Application des réseaux de neurones et des systèmes experts
Résumé: fonctionnement du rétro-prop.
b) propagation inverse du gradient
Cours #10GPA-779
- 55 Application des réseaux de neurones et des systèmes experts
Point de vue extraction de primitives
Extraction des Discrimination
primitives linéaire
. . ** ..
. * 0
.. 0 0
. 0 0
0 0 0 00 0
* *0 * ***
*
4
Applications
Reconnaissance Optique des Caractères (O.C.R)
Seuillage d’images
Base d’apprentissage incrémentale
Data Mining, Extraction des connaissances
Compression d’images (Réseau Diabolo)
Chapitre 5
Mémoires associatives
Reconstruction d ’images
Cours #10GPA-779
- 59 Application des réseaux de neurones et des systèmes experts
5.1 Architecture
x1 y1
x2 y2
W
xN yM
Cours #10GPA-779
- 60 Application des réseaux de neurones et des systèmes experts
Phases d’opération
1- Entraînement
Prototype à mémoriser: V k 1 ≤k ≤P
p
Mémorisation: W = ∑W
(k)
k:1
Entrée:
Tk
2- Recherche
Y = XW T
Y T = WX T
Cours #10GPA-779
- 61 Application des réseaux de neurones et des systèmes experts
Catégories
1- Mémoire auto- Tk → Vk V =T 1 ≤k ≤P
associative k k
2- Mémoire héréro- Tk → Vk V ≠T 1 ≤k ≤P
associative k k
Cours #10GPA-779
- 62 Application des réseaux de neurones et des systèmes experts
5.2 Entraînement
Règle de Hebb
Algorithme
0- Initialisation
Wmn = 0
1- Pour chaque paire T : V
2- xn = tn
3- ym = vm
4- Wmn = Wmn(précédent) + xnym
Cours #10GPA-779
- 63 Application des réseaux de neurones et des systèmes experts
Algorithme alternatif: produit externe de vecteurs
⎡t1v1 L t1vm L t1vM ⎤
⎢ M M M⎥
⎢ ⎥
Wk = Tk oVk = TkT × Vk = ⎢t n v1 L t n v1 L t n vM ⎥
⎢ M M M⎥
⎢ ⎥
⎢t N v1 L
⎣ t N v1 L ⎥
t N vM ⎦
P
W = ∑TkT × Vk
k =1
W0 = W −PI
Cours #10GPA-779
- 64 Application des réseaux de neurones et des systèmes experts
Phase de recherche
X = Tk =l = Tl
Y = XW T
p
= ∑TlTkT Vk
k:1
= TlTl T Vl + ∑TlTkT Vk
k ≠l
1- Entrées non-corrélés (vecteurs orthogonaux)
recouvrement total et parfait
2- Entrées corrélés
recouvrement croisé (bruit d’intercorrélation)
Cours #10GPA-779
- 65 Application des réseaux de neurones et des systèmes experts
Règle Delta
Règle itérative utilisée pour des vecteurs à mémoriser qui
sont linéairement indépendants mais non-orthogonaux. La
règle atténue les effets de corrélation croisée et produit une
solution de moindres carrés lorsque les vecteurs ne sont pas
linéairement indépendants
xi = ti
⎛ ⎞
y j = f ⎜∑ xi w ji = net j ⎟
⎝ i ⎠
Δwij = η f ′(net j ) (v j −y j ) xi
Cours #10GPA-779
- 66 Application des réseaux de neurones et des systèmes experts
5.3 Mémoires anticipatives
Algorithme
1- Entraînement
a) Hebbien
b) Delta
2- Forme (partielle ou bruitée) présentée à l’entrée
netj = ∑ xi w ji
i
netj > 0
1
yj = 0 netj = 0
−1 netj < 0
Cours #10GPA-779
- 67 Application des réseaux de neurones et des systèmes experts
5.4 Mémoires itératives
5.4.1 Réseau de Hopfield
y1 y3
-2
1 1
wij = w ji
1 wii = 0
+4 +1
x1
-1
⎧1
⎪
∑w ij y j ≥0
1 yi = ⎨ j
x2 y2 ⎪−1 ∑w ij yj < 0
⎩ j
Cours #10GPA-779
- 68 Application des réseaux de neurones et des systèmes experts
Chapitre 6
Réseaux récurrents
Énergie d ’un réseau de Hopfield
Le système tend vers son
E=−1 ∑∑TijViV j−∑SiVi état d’énergie minimal :
2 i j i
• Décroissance assurée de
la fonction d’énergie
• Neurones activés à 1
• Activations calculées
une à une
• Attention aux minima
locaux (A) !
Cours #10GPA-779
- 70 Application des réseaux de neurones et des systèmes experts
Exemple de calcul de l’énergie
V1 V2
- E=−[V1V3T13+V1V2T12+V2V3T23]−[S1V1+S3V3]
1 1 2 1
−E=−4+(−2)+(−1)+1+(−1)
S1
+ +
4 1 −E=−7
-1
1
V3
S3
Cours #10GPA-779
- 71 Application des réseaux de neurones et des systèmes experts
6.2 Dynamique du réseau:
relaxation
Objectif : Partir d’un niveau d’énergie
donné, atteindre le minimum local le plus
proche pour récupérer l’information stockée
Conditions initiales : Forme P Si
Poids : Fixes (donnés par un apprentissage antérieur)
Neurones : a) Activations calculées une à
une
b) Selon une séquence aléatoire
c) Valeurs 1 pour assurer la
minimisation de la fonction d’energie.
Résultat : Minimisation de la fonction
Cours #10GPA-779
- 72 Application des réseaux de neurones et des systèmes experts
Relation entre changement d’état et
minimisation de l’ énergie
On a E=−12 ∑∑TijViV j−∑SiVi
i j i
Soit Vk l’activation d’un neurone k
quelconque :
Si le neurone ne change ΔE=0
pas d’état :
Si le neurone change Net(k)
d’état : ΔE=E (t+1)−E (t)
⎛
ΔE=−ΔVk⎜∑TikVi+Sk⎞
⎝ i≠k ⎠
Cours #10GPA-779
- 73 Application des réseaux de neurones et des systèmes experts
Relation entre changement d’état et
minimisation de l’énergie (2)
un changement d’état alors on est assuré de diminuer E :
⎛
ΔE=−ΔVk⎜∑TikVi+Sk⎞
⎝ i≠k ⎠
Vk (t)=Vk (t+1) Vk (t)≠Vk (t+1)
ΔE=0 ΔE<0
ΔVk estpositif ssi ∑TikVi+Skest positif
i≠k
ΔVk estnegatif ssi ∑TikVi+Sk estnegatif
i≠k
Cours #10GPA-779
- 74 Application des réseaux de neurones et des systèmes experts
Algorithme de relaxation
DÉPART
Tirage aléatoire d’une séquence de visite des neurones
Sélection du prochain neurone de la séquence
Vk =1si∑TikVi+Sk≥0
i
Vk =−1si∑TikVi+Sk<0
i
Non Vj tous
visités ?
Oui
Non
P stable ?
Oui
FIN
Cours #10GPA-779
- 75 Application des réseaux de neurones et des systèmes experts
6.3 Apprentissage
« tailler » la courbe d’énergie
La règle la plus simple: Hebb
L’apprentissage est réalisé AVANT
d’utiliser le réseau comme mémoire
associative pour retrouver la forme
emmagasinée à partir d’information
partielle ou bruitée
Cours #10GPA-779
- 76 Application des réseaux de neurones et des systèmes experts
6.4 Optimisation
Une fonction de coût remplace la
fonction d’énergie
L’optimisation consiste à minimiser la
fonction de coût
La fonction de sortie utilisée est la
fonction sigmoïde (au lieu de la
fonction signe ou échelon)
tanh(net
2 ) ou 1−net
1+e
Cours #10GPA-779
- 77 Application des réseaux de neurones et des systèmes experts
Exemple: Voyageur de commerce
Un vendeur doit établir un itinéraire de visite
de 5 villes. Il doit partir de Boston et revenir à
Boston à la fin de son itinéraire.
Chaque ville est visitée une et une seule fois
L’itinéraire doit être le plus court possible afin de
minimiser les frais d’essence
La principale difficulté rencontrée avec ce type
de problème est l’explosion combinatoire des
solutions à évaluer.
Cours #10GPA-779
- 78 Application des réseaux de neurones et des systèmes experts
Réseau de Hopfield
Lignes villes
Colonnes séquence de
visite
Poids contraintes du
problème à résoudre
– 1 ville visitée 1 seule fois
– 1 étape 1 seule ville
– Distance entre les villes
Activation du réseau
minimisation du coût
Cours #10GPA-779
- 79 Application des réseaux de neurones et des systèmes experts
Fonction de coût C
C1 C2 C3 C4
C≡E= A ∑∑ ∑ VxiVxj+ ∑∑∑VxiVyi+
B C ⎛⎜∑∑Vxi−n⎞ + D∑∑∑dxyVxi(Vy,i+1+Vy,i−1)
2 x i j≠i 2 i x y≠x 2⎝ x i ⎠ 2 x y≠x i
eurone correspondant à la ville x à l’étape i
istance entre les villes x et y
C, D : facteurs de pondération pour les contraintes
Cours #10GPA-779
- 80 Application des réseaux de neurones et des systèmes experts
Calcul des poids
W xi,yj = −Aδ xy (1− δ ij ) − Bδ ij (1− δ xy ) − C − Ddxy (δ i, j +1 + δ i, j−1 )
avec l' opérateur de Kronecker :
δ ij = 1 si i = j
δ ij = 0 sinon
Cours #10GPA-779
- 81 Application des réseaux de neurones et des systèmes experts