=Paper=
{{Paper
|id=Vol-547/paper-33
|storemode=property
|title=L'intégration des méthodes Monte Carlo par chaînes de Markov dans l'apprentissage des réseaux de neurones
|pdfUrl=https://ceur-ws.org/Vol-547/189.pdf
|volume=Vol-547
|dblpUrl=https://dblp.org/rec/conf/ciia/OtmaniB09
}}
==L'intégration des méthodes Monte Carlo par chaînes de Markov dans l'apprentissage des réseaux de neurones==
https://ceur-ws.org/Vol-547/189.pdf
L’intégration des méthodes Monte Carlo par chaînes de Markov dans
l’apprentissage des réseaux de neurones
Linda OTMANI 1 et Abdelkader BENYETTOU 2
1 Université de sciences et de technologie d’ORAN-Mohamed Bodiaf-
Faculté des sciences-Département d’informatique-Laboratoire SIMPA
otmani_linda@yahoo.fr
2 Université de sciences et de technologie d’ORAN-Mohamed Bodiaf-
Faculté des sciences-Département d’informatique-Laboratoire SIMPA
aek.benyettou@univ-usto.dz
Résumé : Les méthodes Monte Carlo par chaînes de Markov (MCMC) , s’inscrivent dans le cadre
du formalisme Bayésien .On peut dire que l’application de ces méthodes à l’apprentissage des
réseaux de neurones peut apporter plusieurs avantages, tout d’abord, l’introduction de connaissances
a priori est susceptible d’améliorer l’estimation des paramètres. De plus, le formalisme Bayésien
permet une analyse complète des incertitudes et des probabilités des données. Dans cet article, nous
présenterons brièvement le principe de ces méthodes, qui présentent l’avantage d’être utilisables, et
nous allons montrer leurs applications pour l’apprentissage des réseaux de neurones.
Mot clés
Méthodes Bayésiennes, Réseaux de neurones, Méthodes Monte Carlo par chaînes de Markov
(MCMC),
1 Introduction
Les méthodes bayésiennes ont été appliquées ces dernières années aux réseaux de neurones par différents
auteurs, notamment dans les travaux de MacKay 1992 a [1], MacKay 1992 b[2],Neal 1992[3] , Neal 1994[4],
repris dans Neal 1996 [5], et Buntine et Weigened 1991, Bishop 1995, et plus récemment Freitas 1998, Vehtari
1999 et Freitas 2000.
Weigened (1991), Mackay (1992) et Neal (1994) ont montré que les méthodes bayésiennes pour l’apprentissage
des réseaux de neurones peuvent apporter plusieurs avantages, car il n’est pas nécessaire de limiter la taille du
réseau pour éviter le sur ajustement, et que le nombre de neurones cachés peut tendre vers l’infini, le seul
facteur qui doit limiter la taille du réseau est la capacité des ordinateurs utilisés et le temps disponible pour
effectuer les calculs nécessaires, mais comme les paramètres utilisés sont issus d’une distribution de probabilité,
il est nécessaire pour connaître un paramètre de calculer des intégrales faisant intervenir les distributions des
autres paramètres.
Il est, en général, impossible de calculer ces intégrales analytiquement, et plusieurs approches ont été proposées
pour effectuer ces calculs. Mais soit ces méthodes sont très lourdes à implémenter, soit elles reposent sur des
approximations qui peuvent fausser les résultats, et cela à cause des paramètres utilisés (paramètres du réseau de
neurone) qui sont issus d’une distribution de probabilité, pour inférer ces paramètres on est confronté soit à un
problème d’intégration ou d’optimisation comme celui de notre cas.
Pour résoudre ce problème nous avons opté pour l’algorithme appelé «reversible Jump MCMC Simulated
Annealing» proposé par [6] [10] et qui s’inscrit toujours dans le cadre des méthodes MCMC , et nous allons par
la suite vérifier son application pour l’approximation des fonctions.
-1-
2 L’inférence Bayésienne
Dans un formalisme Bayésien, toute inférence repose sur la densité à posteriori des paramètres qui nous
intéressent conditionnellement aux observations. [7]
Supposant que y = (y1, …, yN) soit le vecteur des observations et θ = (θ 1, …, θ d) ∈ Θ soit le vecteur de
paramètres à estimer.
La densité à posteriori p(θ \y) conjointe de tous les paramètres du modèles est définie à partir du théorème de
Bayes :
p( y / θ ) p(θ ) (1)
p(θ / y) =
p( y)
p(y\θ) est la densité de probabilité conditionnelle des observations connaissant les paramètres du modèle :
fonction de vraisemblance. [8] [9]
p(θ) est la densité à priori des paramètres θ choisie en fonction des connaissances disponibles sur θ avant la
prise en compte des observations.
p(y) est une constante, indépendante de θ , aussi appelée évidence Bayésienne .
1.1 Estimation paramétrique Bayésienne
1.1.1. Estimateur (MMSE)
L’estimateur MMSE est défini par la moyenne de la densité à posteriori considérée.
Etant donné un vecteur de paramètres θ et un vecteur d’observation y on a :
^
θ MMSE = ∫ θ p (θ / y ) . d θ (2)
Θ
1.1.2. Estimateur MAP
L’estimateur MAP est déterminé par le mode de la densité à posteriori considérée :
(3)
P (θ \ y)
Figure1 : Estimateurs paramétriques Bayésien
Pour résoudre un tel problème, nous proposons une méthode de simulation de densités de probabilité telle que la
méthode Monte Carlo par Chaîne de Markov, basée sur la génération de variables aléatoires distribuées suivant
une loi π à simuler.
2 Le modèle adopté
Pour réaliser notre travaille, nous allons adopter le schéma d’approximation proposé par Holmes et Mallicke
(1998) [10], qui consiste à mixer les k RBFs et la régression linéaire. Ce modèle est donné par :
Μ0: yt = b + β -1 xt + nt k=0 ; (4)
∑ a φ (║x - µ ║) b + β x +n k≥1
k
-1
Μk: yt = j =j1 t j t t (5)
1 ≤ k ≤ k max
D’où ║.║ : distance (euclidienne ou de mahalanobis).
µj ∈ Rd : j ème centre RBF pour un modèle avec k RBFs,
aj ∈ Rc : j ème coefficient (poids) RBF,
-2-
b ∈ Rc et β ∈ Rd × Rc : paramètres de la régression linéaire,
nt ∈ Rc : séquence de bruit.
φ :Une fonction RBF, (fonction gaussienne).
Le schéma suivant représente notre modèle adopté
y = D (µ 1: k ,1: d , x 1: N , 1: d ) α 1: 1+ d + k ,1: c + n t
Ö Le traitement du bruit est normalement (6) distribué comme suit :
nt ~ N
2
0 σ 1 0 .... 0
0 0 σ 2
.... 0
2
. .
. , .
. . .
0
0 0 .... σ c2
Un bruit additif, blanc, gaussien, de moyenne nulle et variance = σ 2 .
Ö Les inconnus sont :
9 Le nombre de RBFs : k,
9 Les paramètres des k RBFs : α, µ et σ 2.
3 Position du problème
Etant donné l’ensemble de données d’entrée /sortie {x, y} tel que :
O = {x1, x2, … , xN ; y1, y2 , … , yN }:
Notre objectif est d’estimer k et θ ∈ Θ k. D’où
Θ0 (Rd+1) c × (R+) c , et
Θk (Rd+1+k) c × (R+) c × Ω k pour k∈ {1, …, kmax} .
C à d α∈ (Rd+1+k) c ; σ ∈ (R+) c et µ ∈ Ω k
On note que :
ª Le nombre maximal de RBFs est défini par :
k max = compact
ª Ω k est un ensemble (N – (d+1)) . :
de données
2 (7)
Ω k = { µ ; µ1: k ,i ∈ [ min x1: N ,i − ι Ξ i , max x1: N ,i + ι Ξ i ]
pour i = 1,…, d } (8)
ι : un paramètre utilisateur. La prémisse ici est de placer les fonctions où les données sont condensées. Les
centres sont échantillonnés d’un espace dont l’hyper volume est [Freitas 98]
ψk = (∏ (1 + 2ι ) Ξ )
d
i =1 i
k
avec
Ξi = max (x1: N , i ) − min (x1: N , i )
4 Les MCMC pour l’apprentissage bayésien
L’inférence de k et Θ k est basée sur la distribution jointe à posteriori p(k, Θ k\ x, y), obtenue par le théorème de
Bayes. Notre but est d’estimer cette distribution pour obtenir « théoriquement » tous les éléments du posterior.
L’idée principale des MCMC, est de construire une chaîne de Markov dont la distribution stationnaire est la
distribution à posteriori désirée p (k,k (Θ
i)
(
,k\θx,(i )y).
i∈Ν
)
Comme nous l’avons déjà dit, une méthode MCMC simple n’est pas capable de « sauter » entre les sous espaces
de Θk (de dimensions différentes). Cependant, récemment Green a introduit une nouvelle classe flexible,
d’échantillonneurs MCMC, appelée « reversible jump MCM C» [10]. Capable de sauter entre les espaces des
paramètres de dimensions différentes. [11].
-2-
Figure2 : Le modèle linéaire d’approximation d’un RBF à
trois fonctions RBF, deux entrées et deux sorties.1
Une stratégie de recuit simulé peut être adoptée à cet l’algorithme, pour tirer des échantillons aléatoires à partir
de la chaîne de Markov. Ces échantillons sont utilisés pour approximer l’inférence désirée. [10] [12] [13].
c −1 2
(
p (k , µ 1 , ..... , µ k / x, y ) ∝ ∏ y1T:N , i P *i , k y1:N , i )
p( k )
i =1
4.1. Estimation des poids
Étant donné k, µ1, …, µk, l'estimation des moindres carrés de α est donnée par :
α 1:m , i = [D T (µ 1:k , x ) D (µ 1:k , x )]− 1 D T (µ 1:k , x ) y 1: N , i
^
(9)
4.2. Estimation des paramètres du bruit
En utilisant l’estimation conventionnelle de la distribution gaussienne, l’estimation de σ 2 est donnée par :
T
^2 1 ^ ^ ^ ^ 1 T
σi = y1:N, i − D µ1:k , xα1:m, i y1:N, i − D µ1:k , xα1:m, i = y1:N, i Pk* y1:N, i
N N (10)
*
P
D’où i , k est une matrice orthogonale de projection des moindres carrés :
−1
^ ^ ^ ^
Pk* = I N − D µ 1:k , x D T µ 1:k , x D µ 1:k , x D T µ 1:k , x (11)
4.3. La distribution jointe à posteriori
¾ On peut imposer la distribution à priori sur k :
P (k ) ∝ exp [− P] (12)
D’ou P est un terme de pénalité qui dépend de l’ordre du modèle. En se basant sur le critère du minimum
description length (MDL),
P MDL = ξ/2 log (N).
ξ = nombre de paramètres du modèle = k(c+1) + c(1+d) en cas d’un réseau RBF.
k (c + 1) + c (1 + d )
P (k ) = exp − log N (13)
2
¾ La fonction de vraisemblance est comme suit :
c − N
(
p ∝ ∏ y1T:N , i P *i , k y1:N , i 2
) (14)
i = 1
¾ Sachant que les échantillons du bruit sont gaussiens, la distribution jointe à posteriori p (k, µ1, …, µk \x,y) est
donnée par : Freitas 98
c −1 2
(
p (k , µ 1 , ..... , µ k / x, y ) ∝ ∏ y1T:N , i P *i , k y1:N , i )
p ( k ) (15)
i =1
-3-
¾ Par conséquent l'évaluation du maximum à posteriori (MAP) de ces paramètres est obtenue par la
maximisation du côté droit de (Equ.15).
c −1 2 k(c+1) +c(1+d)
(
p (k, µ1 k )MAP∝ argmax ∏ y1T:N,i P *i, k y1:N,i exp −
) 2
logN
k, µ1, k ∈Ω i=1
(16)
Nous allons utiliser l’algorithme Reversible jump Markov Chain Monte Carlo Simulated Annealing (R-J-
MCMC SA), pour estimer jointement l’ordre du modèle k (k <= k max ) et les centre RBF µ1, … , µk , à
chaque itération. [14] [15]
5. L’algorithme R-j-MCMC simulated annealing
1. Initialisation de: (k(0), θ (0)) ∈ Θ ;
2. Itération i
Ô Echantillonner u ~и [0, 1] et initialiser la température ;
Ô Si Alors « birth » ;
( u≤b )
Sinon si ( u ≤ b + d ) Alors « death » ;
k (i )
k(i) k (i)
Sinon si( u ≤ b + d + s ) Alors «split » ;
k (i ) k (i ) k (i )
Sinon si ( u ≤ b + d + s + m ) Alors «merge » ;
k (i) k (i) k(i) k(i)
Sinon mettre à jour les centres RBF ; Fin si
Ô Réaliser une étape MH avec le rapport d’acceptation recuit.
1. i ← i + 1 et aller à 2 ;
2. Calculer les coefficients α 1 : m ;
5.1. Les sauts de l’algorithme
Supposons que l’état courant de la chaîne de Markov est (k,θ k). A chaque itération, cet algorithme effectue
l’un des sauts suivants : [10] [16]
5.1.1. Saut de naissance « Birth jump»
- Proposer aléatoirement un nouveau centre RBF à partir de l’intervalle (Equ.8) ;
- Evaluer A birth, et échantillonner u ~и [0, 1] ;
- Si u ≤ A birth alors l’état de la chaîne de Markov devient (k+1, µ 1 : k+1) sinon elle reste (k, µ 1 : k).
r birth = y T *
N 2
ψ exp ( − C )
1: N , i p i , k y 1: N , i
c
∏
T *
i = 1 y 1: N , i p i , k + 1 y 1: N , i
(k + 1)
d’où p k* est donné dans (11).
C = [(c+1) log (N)/2 ] selon le critère MDL.
A birth = min (1, r birth).
5.1.2. Saut de mort « death jump »
- Supprimer aléatoirement un des k centres RBF dans (Equ.5);
- Evaluer A death, et échantillonner u ~и [0, 1] ;
- Si u ≤ A death alors l’état de la chaîne de Markov devient (k-1, µ 1 : k-1) sinon elle reste (k, µ 1 : k).
y T *
N 2
1: N , i p i , k y 1: N , i
c
r death = k exp ( C )
∏
T
i =1 y 1: N , i p i , k −1 y 1: N , i
*
ψ
A death = min (1, r death).
-4-
5.1.3. Saut de scission « split jump »
- Choisir aléatoirement un des centres RBF µ ;
- Le remplacer par ses voisins les plus proches µ1, µ2 tel que µ1 = µ – us ζ
et µ2 = µ + us ζ ;
- Le nouveau centre doit être lié à l’espace Ωk dans (Equ.8) ;
ζ est une constante (paramètre de simulation) et u ~и [0, 1] ;
- Evaluer A split, et échantillonner u ~и [0, 1] ;
- Si u ≤ A split alors l’état de la chaîne de Markov devient (k+1, µ 1 : k+1) sinon elle reste (k, µ 1 : k).
N 2
k ζ exp(− C )
r split = c y1:N , i pi, k y1:N , i
T *
∏ T *
i =1 y1: N , i pi , k +1 y1: N , i (k + 1)
A split = min (1, r split).
5.1.4. Saut de fusion « merge jump »
- Choisir aléatoirement un des k terme RBF µ1 ;
- Trouver son voisin proche µ2 ; (en utilisant la distance euclidienne) ;
- Si ║ µ1- µ2║< 2 ζ, alors remplacer les deux fonctions RBF par une seul RBF dont la location est µ = (µ1-
µ2)/2 ;
- Evaluer A merge, et échantillonner u ~и [0, 1] ;
- Si u ≤ A merge alors l’état de la chaîne de Markov devient (k-1, µ 1 : k-1) sinon elle reste (k, µ 1 : k).
y T *
N 2
k exp (C )
1: N , i p i , k y 1: N , i
c
r merge = ∏
i =1 y 1: N , i p i , k −1 y 1: N , i
T *
ζ (k − 1)
A merge = min (1, r merge).
5.1.5. Mise à jour « update move »
L’échantillonnage des centres RBF est difficile, puisque leur distribution est non linéaire. Là on échantillonne
un à la fois en utilisant un ensembles d’étapes MH.
Pour j = 1, 2, ….., k
x Tirer un échantillon u ~ и [0, 1] ;
x Si u < 0.5
Echantillonner aléatoirement un centre RBF à partir de l’intervalle initialement fixé dans (Equ.8).
Calculer µ •j
N 2
c y 1T: N , i p i*, k y 1 : N , i
r update =
∏ T
i = 1 y 1: N , i
p i*, k y 1 : N , i
•
D’où pi, k est le même que pi*, k avec µ1 : k, 1 : d, remplacé par :{µ1, 1 : d, µ2, 1 : d, …., µ j –1 , , µ j+1, 1 : d, ….,
µ j, 1 : d }. µ •j, 1:d
Si v ~ u [0,1] ≤ min {1, r update} alors l’état devient
(k, µ1, µ2, …., µ j - 1, , µj+1, …., µk) sinon il reste inchangé.
x Si u ≥ 0.5
Echantillonner aléatoirement un centre RBF µà partir
•
de la distribution : •
* \ µj, 1: d ~ N (µj, 1 : d, I ).
i, j
µj
µ j ,1:d
d 2
σ RW
N 2
r update = y T
p ∗ y
c
1 : N , i i, k 1 : N , i
∏
i=1 y T p • y
1 : N , i i, k 1 : N , i
Si v ~ u [0,1] ≤ min {1, r update} alors l’état devient (k, µ1,1 :d, µ2,1 :d, …., µ j–1,1 :d , , µj+1,1 :d, …., µk,1 :d) ,
sinon il reste inchangé. µ•j, 1:d
5.2. L’optimisation
-5-
D’une perspective MCMC, on peut résoudre un problème d’optimisation, comme celui posé dans notre cas, en
adoptant la stratégie du récuit simulé. Cette dernière implique la simulation de chaîne de Markov non homogène
dont la distribution à l’itération i, n’est pas π (z) mais :
π i (z) ∝ π 1/ T i (z) avec T : la température
Lorsque i → ∞ T = 0, la densité π∞ (z) se concentre sur l’ensemble des maximaux globaux π (z) .
Si l’on considère le noyau de transition de l’algorithme (R-J-MCMC) T(z, z*) comme loi de proposition, le
rapport d’acceptation recuit est donné par :
( )
π (1 / Ti − 1 ) z *
ARJSA = min 1,
π (1 / Ti − 1 ) ( z )
6 Explication des étapes de l’algorithme
1- Initialisation :
Les valeurs initiales de µ1, …, µk sont aléatoirement choisies selon (Equ.10).
2- La boucle :
♦ Les sauts « birth » et « death » permettent au réseau respectivement de s’augmenter de k à k+1, et de se
baisser de k à k-1.
♦ Les sauts « split » et « merge » permettent aussi de changer la dimension de k à k+1 et de k à k-1.
♦ Le saut « merge » sert à éviter de placer plusieurs fonctions RBF dans le même voisinage. D‘autre part
le saut « split » est utilisé dans les régions de données où il y a des composantes étroites.
Remarques :
♦ Le noyau résultant de la simulation de la chaîne de Markov est donc un mélange de plusieurs noyaux
de transition liés aux mouvements décrits ci-dessus.
♦ A chaque itération, un des sauts (b, d, m, s, u) est choisis aléatoirement. Les probabilités pour choisir
ces sauts sont respectivement bk, dk, mk, sk et uk, tel que bk + dk + mk + sk + uk = 1 avec (0≤ k ≤ kmax). Le
saut n’est effectué que si l’algorithme l’accepte.
9 Pour k = 0, les sauts mort, scission et fusion sont impossibles, donc :
d0 = 0 ; m0 = 0 ; s0 = 0.
9 Pour k = 1, le saut fusion est interdit. Donc m1 = 0.
9 Pour k = kmax, les saut naissance et scission, ne sont pas autorisés et pour cela ; bkmax = 0 ; s kmax
= 0.
♦Notre algorithme, donne la MAP jointe estimation de µ1 : k, et k avec
bk = dk = mk = sk = uk = 0.2 .
7 Application : Approximation des fonctions
Les fonctions a simuler sont des fonctions non linéaire à deux variables, où les entrées (x,y) sont tirées d’une
distribution gaussienne avec une moyenne nulle, une variance =1 et un bruit v.
Un aperçue de la vraie fonction, et celle réalisée par l’algorithme
-6-
8 Conclusion
Dans cet article, on a présenté une technique pour l’apprentissage des réseaux de neurones, s’appuyant sur le
principe des méthodes Monte Carlo par chaînes de Markov .L’intégration de ces méthodes à l‘apprentissage des
réseaux de neurones, nous a mené à des résultats satisfaisants par rapport à d’autres algorithmes classiques
d’apprentissage.
L’application de ces méthodes à l’approximation des fonctions nous a indiqué clairement que cette technique
d’apprentissage représente une alternative intéressante et prometteuse dans les méthodes existantes.
Dans cet article, nous avons donné une estimation du bruit, et du nombre de paramètres pour un modèle de
réseau RBF d’une façon générale.
Nous avons adopté une inférence bayesienne, avec l’algorithme MCMC à sauts réversible pour effectuer les
intégrales nécessaires, par conséquence une minimisation du temps d’apprentissage et de l’erreur pour le réseau
de neurones.
9 Références
[1] D. J. C. MacKay. “Bayesian interpolation”. Neural Computation, 4(3), 415-447, 1992.
[2] D. J. C. MacKay. “A Practical Bayesian Framework for Backpropagation Networks”. Neural Computation,
4(3), 448-472, 1992.
[3] R. M. Neal. “Bayesian Training of Backpropagation Networks by the Hybrid Monte Carlo Method”.
Technical Report CRG-TR-92-1, Department of Computer Science, University of Toronto, 1992.
[4] R. M. Neal. “Bayesian Learning for Neural Network”. Ph.D. thesis, University of Toronto, 1994.
[5] R. M. Neal. “Bayesian methods for Neural Networks”. New York : Springer- Verlag, 1996.
[6] W. Buntine, A.S “Weigend.Bayesian back-propagation“. Complex Systems, 5, 603-643, 1991.
[7] C. M. Bishop. “Neural Networks for Pattern Recognition”. Clarendon Press, Oxford, 1995.
[8] JFG de Freitas, M Niranjan, A H Gee, and A Doucet. “Sequential Monte Carlo methods for optimisation of
neural network models”. Technical Report CUED/F-INFENG/TR 328, Cambridge University Engineering
Department, July 1998.
[9] Aki Vehtari et Jouko Lampinen. « Bayesian neural networks with correlating residuals”. In Proc.
IJCNN’99, Washington, DC, USA, July 1999.
[10] JFG de Freitas. “Robust full bayesian methods for neural network”, Cambridge university , 2000.
[11] D. J. C. MacKay. “The Evidence Framework Applied to Classification Networks”. Neural Computation,
4(5), 698-714, 1992.
[12] Philippe Leray et Olivier François, « Etude comparative d’algorithme d’apprentissage et de structure dans
les réseaux bayésiens », Laboratoire Perception, Systèmes, Information - FRE CNRS 2645.
[13] N. J. Gordon, D. J. Salmond, and A. F. M. Smith. “Novel approach to nonlinear/non-gaussian bayesian
state estimation”. IEEE Proceedings-F, 140(2):107–113, April 1993.
[14] S. F. Gull. “Bayesian inductive inference and maximum entrop”. G. J. Erickson,C.R. Smith eds.
Maximum-Entropy and Bayesian Methods in Science and Engineering, Vol.1: Foundations, 53-74, Dordrecht:
Kluwer, 1988.
[15]. J S Liu and R Chen. “Sequential Monte Carlo methods for dynamic systems”. Journal of the American
Statisti- cal Association, 93:1032–1044, 1998.
[16] P. Muller. (1991). “Monte Carlo integration in general dynamic models”. Contemporary Mathematics,
115, 145–163.
-7-