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),
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[
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. 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(y /θ )
p(θ ) p(y)
(1)
p(y\θ) est la densité de probabilité conditionnelle des observations connaissant les paramètres du modèle :
fonction de vraisemblance. [8] [
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
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)
L’estimateur MAP est déterminé par le mode de la densité à posteriori considérée :
(3)
P (θ \ y) 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.
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 ;
k Μk: yt = ∑ ja=j1φ (║xt - µj║) b + β -1 xt +nt k≥1
1 ≤ k ≤ k D’où ║.║ : distanmcaex (euclidienne ou de mahalanobis). µj ∈ Rd : j ème centre RBF pour un modèle avec k RBFs, aj ∈ Rc : j ème coefficient (poids) RBF, (4) (5) 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 0
σ012 0. . ,
. 0 0 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.
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ù C à d On note que : ª Le nombre maximal de RBFs est défini par : Θ 0 (Rd+1) c × (R+) c , et Θ k (Rd+1+k) c × (R+) c × Ω k pour k∈ {1, …, kmax} .
α∈ (Rd+1+k) c ; σ ∈ (R+) c et µ ∈ Ω k ª
Ω k est un eknsmeamxb=le c(oNmp–ac(tdd+e1d)o)nn2é.es : Ω k = {µ ; µ1: k,i ∈ [ min x1:N,i − ι Ξ i, max x1: N,i + ι Ξ i ] pour i = 1,…, d }
ι : 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] avec Ξ i = ψ k = (∏id=1 (1 + 2ι ) Ξ i )k
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].
(7)
(8)
Étant donné k, µ1, …, µk, l'estimation des moindres carrés de α est donnée par :
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 : (9) (10) (11) (12) (13) (14) α 1:m ,i = [D T (µ 1:k , x )D (µ 1:k , x )]−1 D T (µ 1:k , x ) y 1:N , i ^ σ^ i2 = N1 y1:N, i − Dµ1:k^, xα1:^m, i T y1:N, i − Dµ1:k^, xα1:^m, i = N1 y1T:N, i Pk* y1:N, i
D’où Pi*,k est une matrice orthogonale de projection des moindres carrés :
^ ^ ^ −1 Pk* = I N − D µ1:k , x DT µ1:k , x D µ1:k , x
D T µ1:k^, x
¾ On peut imposer la distribution à priori sur k : ¾ 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 p (k, µ1 , ....., µ k / x, y) ∝ ∏ ( y1T:N ,i P *i, k y1:N ,i i=1 )−1 2 p( k ) (15) 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
2 ¾ La fonction de vraisemblance est comme suit : p ∝ ∏c ( y1T:N ,i P *i, k y1:N ,i ) − N 2 i = 1 ¾ 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). p (k, µ1k )MAP∝ ak,rµg1,mk∈Ωax ∏i=c1 ( y1T:N,i P*i, k y1:N,i )−12 exp − k(c+1) +2c(1+d) logN
(16)
Nous allons utiliser l’algorithme Reversible jump Markov Chain Monte Carlo Simulated Annealing
(R-JMCMC SA), pour estimer jointement l’ordre du modèle k (k <= k max ) et les centre RBF µ1, … , µk , à
chaque itération. [14] [
( u ≤ b k(i) ) Sinon si ( u ≤ b k(i) + d k(i) ) Alors « death » ; Sinon si( u ≤ b k(i)
+ d k(i) + s k(i) ) Alors «split » ; Sinon si ( u ≤ b k(i) + d k(i) + s k(i) + m k(i) ) Alors «merge » ; 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 ;
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] [
- 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 = c y1T:N , i p i*, k y1:N , i ∏i=1 y1T:N , i p i*, k +1 y1:N , i
N 2 d’où pk* est donné dans (11).
C = [(c+1) log (N)/2 ] selon le critère MDL.
A birth = min (1, r birth).
ψ exp ( − C ) (k + 1) 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). r death = c y1T:N , i p i*, k y1:N , i ∏i=1 y1T:N , i p i*, k −1 y1:N , i
N 2 A death = min (1, r death).
k exp (C ) ψ 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). 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). r merge = ∏i=c1 yy1T:1TN:N, ,i i ppi*,i*,kk−1 yy1:1N:N, ,i i N 2 kζ (ekxp− 1()C )
A merge = min (1, r merge).
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 initialemenµtfi•xé dans (Equ.8). Calculer j r update =
c y 1T: N , i p i*, k ∏ i = 1 y 1T: N , i p i*, k
N 2 y 1 : N , i
y 1 : N , i • D’où pi, k est le même que µ j, 1 : d }.
* pi, k 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 µ *j ,1:d\ µj, 1: d ~ N (µj, 1 : d,
I dσ). R2W r update =
c y T ∏ 1 : N , i i = 1 y T 1 : N , i p i∗, k p i•, k y 1 : N , i N 2 y 1 : N , i av•ec µ1 : k, 1 : d, remplacé par :{µ1, 1 : d, µ2, 1 : d, …., µ j –1 , µ j, 1:d , µ j+1, 1 : d, …., µà pi•,arjtir de la distribution µ: • j Si v ~ u [0,1] ≤ min {1, r update} alors l’é•tat devient (k, µ1,1 :d, µ2,1 :d, …., µ j–1,1 :d , sinon il reste inchangé. µ j, 1:d , µj+1,1 :d, …., µk,1 :d) ,
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 :
ARJSA = min 1, π (1/Ti − 1) (z * )
π (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
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.