La méthode de Monte Carlo par la Chaîne de Markov (MCMC) dans un sous-espace actif

La méthode de Monte Carlo par la Chaîne de Markov (MCMC) dans un sous-espace actif

Sous-espaces actifs et Approximations Sommaire 

Introduction aux sous-espaces actifs

 Les sous-espaces actifs sont des ensembles émergents d’outils de réduction des dimensions.Le travail dans les sous-espaces actifs ressemble à la réduction de dimension de Cui et al [3] bien que le contexte soit plus large que les problèmes statistiques inverses. On considère la description suivante sur les sous-espaces actifs.Soit f = f(x) une fonction de R m à R,le vecteur d’entrée x ∈ R m a m composantes indépendantes.Soit ρ : R −→ R+ une fonction de densité de probabilité donnée. Supposons que ρ = ρ(x) et x soit tel que : ˆ xρdx = 0, ˆ xxT ρdx = I (1.1) où I est la matrice identité de dimension m × m. Supposons également que f est différentiable avec vecteur gradient ∇f(x) ∈ R m dont les composantes sont respectivement de carrées intégrables avec ρ.Soit C une matrice définie semi-positive ,symétrique de dimension m × m et sa valeur propre se décompose comme suit : C = ˆ ∇f∇f T ρdx = WΛWT (1.2) où W est la matrice orthogonale des vecteurs propres et Λ la matrice diagonale des valeurs propres d’ordre décroissant.La i-ème valeur propre λi satisfait : λi = ˆ (w T i ∇f) 2 ρdx (1.3) En mots (1.3) signifie que la i-ème valeur propre mesure la moyenne au carré de la dérivée directionnelle de f le long du vecteur propre correspondant wi .Ainsi si λi = 0 alors f est La Méthode de Monte Carlo par la Chaîne de Markov (MCMC) dans un sous-espace actif c FST/UCAD 2017 Approximation dans le sous-espace actif 10 constante le long de la direction wi dans R m. Pour définir le sous-espace actif,supposons λn > λn+1 pour un certain n < m et la partition des valeurs propres et vecteurs propres se décompose respectivement comme suit : Λ =  Λ1 Λ2  , W = [W1 W2] (1.4) où Λ1 contient les n premières valeurs propres et les colonnes de W1 sont les n premiers vecteurs propres.Le sous-espace actif est la portée des colonnes de W1.Cependant il n’est pas nécessairement un sous-ensemble du domaine de f même lorsque le domaine de f luimême est R n .Au lieu de cela,les colonnes de W1 sont un ensemble de direction perturbant le long de x.Ces directions changent f(x) en moyenne plus que perturbant x le long des directions correspondantes aux colonnes de W2.Tout x ∈ R m peut s’écrire sous la forme : x = W1WT 1 x + W2WT 2 x = W1y + W2z (1.5) où y = WT 1 x est la variable active et z = WT 2 x est la variable inactive. La fonction densité ρ engendre une densité conjointe entre les variables actives et inactives : ρ(x) = ρ(W1y + W2z) = ρ(y, z) (1.6) Ce qui conduit à des densités marginales et conditionnelles sous la construction standard.Si ρ est une densité gaussienne standard sur x,le cas que nous considérons dans ce travail est alors dû aux colonnes orthogonales de W1 et W2.Les densités marginales et conditionnelles sur y et z sont également des densités gaussiennes standards. 1.1 Approximation dans le sous-espace actif Lemme 1.1.1. Les gradients de f avec respectivement de coordonnées y et z avec y = WT 1 x et z = WT 2 x satisfont : E h (∇f(y))T (∇f(y))i = λ1 + · · · + λn E h (∇f(z))T (∇f(z))i = λn+1 + · · · + λm Si les valeurs propres λ1, · · · , λn sont beaucoup plus grandes que les valeurs propres λn+1, · · · , λm alors on peut approximer f par une fonction de n combinaisons linéaires de x avec n < m.Pour construire cette approximation, on définit g : R n −→ R par la moyenne conditionnelle de f donnée par : g(y) = ˆ f(W1y + W2z)ρ(z/y)dz (1.7) où ρ(z/y) est la densité conditionnelle de z sachant y.Dans cette construction,nous avons la borne suivante sur l’erreur quadratique de l’approximation f(x) ∼ g(WT 1 x). Théorème 1.1.1. ˆ  f(x) − g(WT 1 x) 2 ρdx ≤ C(λn+1 + · · · + λm) (1.8) La Méthode de Monte Carlo par la Chaîne de Markov (MCMC) dans un sous-espace actif c FST/UCAD 2017 Approximation dans le sous-espace actif 11 où C est la constante de Poincaré associée à la densité ρ. Preuve : Posons F(x) = g(WT 1 x) on a :´ (f(x) − g(WT 1 x))2ρdx = E h (f − F) 2 (x)/yi or E h (f − F)(x)/yi = 0 de l’hypothèse f(x) ∼ F(x) Ainsi, E h (f − F) 2 i = E h E[(f − F) 2 /y] i (1.9) ≤ CE h E[(∇f(x))T (∇f(x))/y] i (1.10) = CE h (∇f(x))T (∇f(x))i (1.11) = C(λn+1 + · · · + λm) cqfd. (1.12) La ligne (1.10) est une inégalité de Poincaré et la ligne (1.12) vient du lemme 1.1.1 . Le conditionnel (1.7) n’est pas utile pour le calcul puisque l’évaluation de g(y) implique de calculer une intégrale de dimension n − m.Pour aller vers un calcul,nous introduisons l’approximation de Monte Carlo gˆ ∼ g définie par : gˆ(y) = 1 M X M i=1 f(W1y + W2zi) (1.13) où les zi sont indépendantes de la densité conditionnelle ρ(z/y). L’approximation f(x) ∼ gˆ(WT 1 x) admet l’estimation d’erreur quadratique moyenne suivante : Théorème 1.1.2. ˆ  f(x) − gˆ(WT 1 x) 2 ρdx ≤ C(1 + 1 M )(λn+1 + · · · + λm). (1.14) où C est la constante du théorème 1.1.1 . Preuve : Tout d’abord, on pose Fˆ(x) = ˆg(WT 1 x) et définissons la variance conditionnelle de f de donnée y par σ 2 y = E h (f − F) 2/yi et le théorème 1.1.1 donne E h σ 2 y i ≤ C(λn+1 + · · · + λm) L’erreur quadratique moyenne de l’approximation de Monte Carlo satisfait E h (f − Fˆ) 2 /yi = σ 2 y M Alors E h (f − Fˆ) 2 i = E h E h (f − Fˆ) 2/yii = 1 M E h σ 2 y i ≤ C M (λn+1 + · · · + λm) Finalement en utilisant le théorème 1.1.1,on a : La Méthode de Monte Carlo par la Chaîne de Markov (MCMC) dans un sous-espace actif c FST/UCAD 2017 Approximation dans le sous-espace actif estimé 12 E h (f − Fˆ) 2 i ≤ E h (f − F) 2 i + E h (F − Fˆ) 2 i ≤ C  1 + 1 M  (λn+1 + · · · + λm) cqfd. (1.15) Si f est tel que les valeurs propres λn+1 = · · · = λm = 0 alors l’estimation de la valeur de Monte Carlo est exacte pour tout nombre M > 0 d’échantillons.Une autre façon de voir cela est que λn+1 = · · · = λm = 0 implique que f est constante le long des directions correspondantes à W2 colonnes et la moyenne d’une constante est la constante. 

Calcul du sous-espace actif avec Monte Carlo

 La méthode de Monte Carlo permet d’estimer des intégrales multidimensionnelles qui ne peuvent pas en général être calculées numériquement. La dimension m est supposée suffisamment grande pour que la méthode de Monte Carlo soit le choix le plus pratique.Pour estimer la matrice C dans (1.2),notre travail va analyser l’approximation de Monte Carlo [4].Soit xj avec j = 1, · · · , N tirés indépendamment de la densité ρ.Pour chaque xj ,on calcule le gradient ∇fj = ∇f(xj ).Alors approximativement : C ∼ Cˆ = 1 N X M j=1 ∇fj∇f T j = Wˆ ΛˆWˆ T (1.16) où Wˆ représente les vecteurs propres estimés et Λˆ les valeurs propres estimées et partitionnés comme dans (1.4).Soit ε l’erreur dans le sous-espace actif estimé,on a : ε = kW1WT 1 − Wˆ 1Wˆ T 1 k = kWˆ T 1 W2k (1.17) où k.k est la norme matricielle . Dans [4],il est montré que lorsque le nombre N de (1.16) est suffisamment grande,l’erreur relative dans les valeurs propres estimées Λˆ tombe en dessous d’une tolérance spécifiée par l’utilisateur avec une probabilité élevée. En pratique,s’il existe un écart entre λˆ n et λˆ n+1 alors la méthode de Monte Carlo donne une bonne estimation du sous-espace de dimension n.

 Approximation dans le sous-espace actif estimé Lemme

 Etant donné la partition de W et une partition comparable Wˆ = h Wˆ 1, Wˆ 2 i alors kWT 2 Wˆ 2k ≤ 1 et kWT 2 Wˆ 2k ≤ ε dans la matrice de norme sur L 2 . Les approximations de (1.7) et (1.13) utilisent les vecteurs propres estimés Wˆ 1.Les variables actives et inactives estimées sont respectivement yˆ = Wˆ T 1 x et zˆ = Wˆ T 2 x.Et les densités conjointes,marginales et conditionnelles sont semblables à (1.6). La moyenne conditionnelle des vecteurs propres estimés est : gε(ˆy) = ˆ f(Wˆ 1yˆ + Wˆ 2zˆ)ρ(ˆz/yˆ)dz (1.18) La Méthode de Monte Carlo par la Chaîne de Markov (MCMC) dans un sous-espace actif c FST/UCAD 2017 Approximation dans le sous-espace actif estimé 13 L’erreur quadratique moyenne dans l’approximation f(x) ∼ gε(Wˆ T 1 x) est donnée dans le théorème suivant : Théorème 1.3.1. ˆ  f(x) − gε(Wˆ T 1 x) 2 ρdx ≤ C  ε(λ1 + · · · + λn) 1 2 + (λn+1 + · · · + λm) 1 2 2 (1.19) où C vient du théorème 1.1.1 et ε est l’erreur du sous-espace de (1.17). Preuve : Suivant le même raisonnement de la preuve précédente,on utilise l’inégalité de Poincaré, E h (f − Fε) 2 i ≤ CE h (∇f(ˆz))T (∇f(ˆz))i En utilisant la règle de la chaîne, ∇f(ˆz) = WT 2 Wˆ 2∇f(z) + WT 1 Wˆ 2∇f(y) (1.20) Alors E h (∇f(ˆz))T (∇f(ˆz))i ≤ E h (∇f(z))T (∇f(z))i + 2εE h (∇f(z))T (∇f(z))i + ε 2E h (∇f(y))T (∇f(y))i ≤  E[(∇f(z))T (∇f(z))] 1 2 + εE[(∇f(y))T (∇f(y))] 1 2 2 ≤  ε(λ1 + · · · + λn) 1 2 + (λn+1 + · · · + λm) 1 2 2 cqfd. (1.21) La ligne qui suit (1.20) découle du lemme 1.3.1,la ligne qui précède (1.21) vient de l’inégalité de Cauchy-Schwartz et la ligne (1.21) vient du lemme 1.1.1 . Lorsque l’erreur dans le sous-espace estimé n’est pas nulle,l’estimation d’erreur inclut la contribution des plus grandes valeurs propres.L’estimation de Monte Carlo gˆε de moyenne conditionnelle gε est donnée par : gˆε(ˆy) = 1 M X M i=1 f(Wˆ 1yˆ + Wˆ 2zˆi) (1.22) où les zi sont indépendantes de la densité conditionnelle ρ(ˆz/yˆ). Le théorème suivant limite l’erreur quadratique moyenne dans l’approximation de Monte Carlo.