\subsection{Algorithmes génériques pour l'inférence bayésienne}
\label{subsec:Generatif-algos}
Les algorithmes que nous allons pr\'esenter interviennent fr\'equemment en statistique bayésienne pour simuler des lois a posteriori. En effet, si on se donne une loi a priori sur les param\`etres $\pi(\param)$ et si on connaît la loi des observations $p(x|\param)$, la loi a posteriori est donn\'ee par :
\[
p(\param|x)=\frac{\pi(\param)p(x|\param)}{\int \pi(\param)p(x|\param)d\param}.
\]
À part dans des cas simples (lois conjugu\'ees), il n'est pas toujours possible d'expliciter la loi a posteriori \`a cause du d\'enominateur $\int \pi(\param)p(x|\param)d\param$. Ceci empêche par exemple d'avoir explicitement un intervalle de crédibilité pour les param\`etres. Une mani\`ere de contourner ce probl\`eme est de simuler num\'eriquement la loi a posteriori, afin d'approcher sa densité par un histogramme. Ceci reste possible même si l'on ne connaît sa distribution qu'\`a une constante pr\`es. 

Nous commençons par quelques rappels simples sur la simulation de variables al\'eatoires, puis nous expliquons le principe des m\'ethodes MCMC ainsi que deux algorithmes classiques : l'algorithme de Metropolis Hastings et l'\'echantilloneur de Gibbs.
\subsubsection{Quelques algorithmes simples de simulation de variables al\'eatoires}
Rappelons tout d'abord le principe de simulation par inversion:
\begin{prop}
Soit $X$ une variable al\'eatoire de fonction de r\'epartition $F$. Pour tout $u\in [0,1]$, on d\'efinit alors $F^{-}(u)=\inf\{x,\,F(x)\geq u\}$. Si $U\sim \mathcal{U}[0,1]$, alors $F^{-}(U)$ a m\^eme loi que $X$.
\end{prop}
L'exercice 7.7 aborde la simulation de variables aléatoires par inversion.
D'autres algorithmes peuvent \^etre propos\'es pour simuler d'autres lois : gaussiennes, gamma \`a partir de la transformation d'une variable al\'eatoire suivant la loi uniforme. Nous pr\'esentons maintenant la m\'ethode d'acceptation-rejet, qui nous servira dans la suite pour comprendre l'algorithme de Metropolis Hastings.
On rapelle que si l'on se donne une densit\'e de probabilit\'e $f$ d'une variable al\'eatoire $X$, son support not\'e $supp(f)$ est l'ensemble $\mathbb{R}\setminus\{x,\,f=0\,p.p.\mbox{ au voisinage de }x\}$.On suppose que la densit\'e $f$ de la variable al\'eatoire que l'on cherche \`a simuler est domin\'ee par une autre densit\'e $g$ telle que :
\begin{itemize}
\item Il est ais\'e de simuler suivant $g$
\item $supp(f) \subset supp(g)$.
\item Il existe une constante $M$ telle que $f(x)\leq Mg(x)$ pour tout $x$.
\end{itemize} 
%\AFAIRE{S'assurer que la notion de support à été introduite avant}.\\
On peut proposer l'algorithme suivant (algorithme \ref{algo:Generatif:rejet}) 
pour simuler une variable al\'eatoire de densit\'e $f$:
\restylealgo{algoruled}
\begin{algorithm}[h!]
\caption{Algorithme d'acceptation-rejet}
\label{algo:Generatif:rejet}
	\begin{itemize}
		\item G\'en\'erer $Y$ suivant la loi $g$.
		\item  G\'en\'erer $U$ suivant une loi $\mathcal{U}[0,1]$
		\item  Accepter la valeur $Y$ et l'ajouter \`a l'\'echantillon si $U<f(Y)/(Mg(Y))$
	\end{itemize}
\end{algorithm}
% \AFAIRE{Harmoniser la présentation des algos.}

On a alors le r\'esultat suivant :
\begin{prop}
La variable al\'eatoire $Y$ d\'efinie par l'algorithme pr\'ec\'edent a pour densit\'e $f$.
\end{prop}
Remarquons que si $\sup_y f(y)/(Mg(y))$ est tr\`es petit, cet algorithme est tr\`es coûteux car $Y$ sera tr\`es souvent rejet\'ee. Par ailleurs, il faut savoir trouver la valeur de $M$, si possible la plus petite. Cette m\'ethode n'est donc, dans bien des cas, pas tr\`es efficace. Par ailleurs, si $f$ n'est connue qu'\`a une constante pr\`es (ce qui est souvent le cas en statistique bayésienne), il est difficile de déterminer $M$. Ceci motive l'introduction de m\'ethodes alternatives plus efficaces et valides dans un contexte plus g\'en\'eral : les m\'ethodes~MCMC. 
\subsubsection{Méthodes MCMC}
\label{subsubsec:MCMC}
L'id\'ee des m\'ethodes MCMC est de simuler une chaîne de Markov dont la loi limite est la loi cible, de densit\'e $f$. Nous pr\'esentons deux m\'ethodes permettant de construire une telle chaîne.\\
\noindent{\bf{Algorithme de M\'etropolis Hastings}}.\index{algorithme!Metropolis Hastings} Comme dans l'algorithme d'acceptation-rejet, on se donne une densit\'e cible $f$ et une loi auxiliaire $q$ suivant laquelle on va simuler \`a chaque pas de l'algorithme. Il s'agit cette fois-ci d'une loi conditionnelle $q(\cdot|x)$, d\'ependant de l'\'echantillon obtenu lors du pas pr\'ec\'edent de l'algorithme que nous détaillons ci-après.


\begin{algorithm}[H]
    \SetKwInOut{Entr}{Entrée}
    \SetKwInOut{Sort}{Sortie}
    \SetKwInOut{Init}{Initialisation}
\caption{Algorithme de M\'etropolis Hastings}
       \textbf{Initialisation :}
       \begin{itemize}\item G\'en\'erer $x_0$ al\'eatoirement.\end{itemize}
		\Pour{$n=1,\cdots$} {
			\begin{itemize}
				\item  G\'en\'erer $y_n$ suivant $q(\cdot|x_n)$
				\item  Choisir
				\[
				x_{n+1}=\left\{\begin{array}{l}y_n\mbox{ avec probabilit\'e }p(x_n,y_n)\\x_n \mbox{ avec probabilit\'e }1-p(x_n,y_n)\end{array}\right.
				\]
				avec $p(x,y)=\min\left(\frac{f(y)}{f(x)}\frac{q(x|y)}{q(y|x)},1\right)$.
			\end{itemize}
		}
\end{algorithm} 

Pour \'enoncer un r\'esultat de convergence, nous allons avoir besoin d'introduire la notion suivante : \\
% \AFAIRE{À étendre à des noyaux de transition}
\begin{dfn}
Une matrice $A=(a_{i,j})$ \`a coefficients positifs ou nuls est dite irr\'eductible si, pour tous $(i,j)$, il existe $p\in\mathbb{N}$ et $(i_1,\cdots,i_p)$ tels que $a_{ii_1},\cdots a_{i_p j}$ sont tous strictement positifs. En particulier, une matrice \`a coefficients tous strictement positifs est irr\'eductible.
\end{dfn}
\begin{prop}
Les $(x_n)$ forment une cha\^ine de Markov. Si $q$ est tel que la matrice $(q(y|x))_{x,y}$ est irr\'eductible, alors la chaîne de Markov $(x_n)$ converge et sa loi limite est $f$.
\end{prop}
Le point cl\'e est le choix de $q$ qui influe en particulier sur la vitesse de convergence.% Il n'y a pas de r\'esultats g\'en\'eraux sur cette vitesse de convergence. \\
% \AFAIRE{Propos à modérer certainement.}\\
En pratique, on peut se donner des crit\`eres empiriques de convergence (par exemple, regarder la moyenne empirique de l'\'echantillon et attendre qu'elle se stabilise).\\
\noindent{\bf{\index{echantillonneur de Gibbs@échantillonneur de Gibbs}Échantillonneur de Gibbs}}. 
Le contexte est un peu diff\'erent de celui que nous venons de d\'ecrire et est tr\`es adapt\'e au cadre bayésien. Supposons qu'on cherche à simuler la loi a posteriori d'un paramètre multidimensionnel $\Theta = (\theta_1,\cdots,\theta_n)$ sachant des observations. On suppose qu'on ne sait pas simuler la loi jointe $p(\Theta|X)$ mais qu'on est capable de simuler, pour tout $i$, les lois conditionelles $p(\theta_i|X,\Theta_{-i})$ o\`u on note  $\Theta_{-i}$ le vecteur $\Theta$ auquel on a enlev\'e sa $\eme{i}$ coordonn\'ee. L'algorithme de Gibbs consiste \`a réaliser les op\'erations suivantes :

\begin{algorithm}[H]
    \SetKwInOut{Entr}{Entrée}
    \SetKwInOut{Sort}{Sortie}
    \SetKwInOut{Init}{Initialisation}
\caption{Algorithme de Gibbs\index{algorithme!de Gibbs}}
       \textbf{Initialisation :}
       \begin{itemize}	
	\item $\Theta^{(0)}$\end{itemize}
		\Pour{$t=1,\cdots,T_{max}$} {
			\Pour{$i=1,\cdots,n$} {
				\begin{itemize}
				\item Simuler $\theta_1^{(t+1)}$ suivant $p(\cdot|X,\theta_2=\theta_2^{(t)},\cdots,\theta_n=\theta_n^{(t)})$
				\item Simuler $\theta_2^{(t+1)}$ suivant $p(\cdot|X,\theta_1=\theta_1^{(t+1)},\theta_3=\theta_3^{(t)},\cdots,\theta_n=\theta_n^{(t)})$
				\item .....
				\item Simuler $\theta_n^{(t+1)}$ suivant $p(\cdot|X,\theta_1=\theta_1^{(t+1)},\cdots,\theta_{n-1}=\theta_{n-1}^{(t+1)})$
				\end{itemize}}}
\end{algorithm} 

On a le r\'esultat suivant :
\begin{prop}
Supposons que les lois conditionelles sont toutes des lois \`a densit\'e toutes positives. Alors la suite des vecteurs g\'en\'er\'es est une chaîne de Markov dont la distribution invariante, limite ergodique de la chaine, est la loi du param\`etre $\Theta$.
% \AFAIRE{Mieux vérifier les conditions de convergence, etc.}\\
\end{prop}
La difficult\'e de cette m\'ethode consiste \`a \^etre capable de simuler les lois conditionnelles.

\subsubsection{Approches empiriques. Lien avec EM}
% \AFAIRE{Vérifier la présentation d'EM dans un autre chapitre.}\\
Rappelons qu'EM est un algorithme it\'eratif qui sert à estimer les param\`etres d'un mod\`ele probabiliste \`a partir de la maximisation de sa vraisemblance dans le cas o\`u il contient des variables latentes (i.e. non observ\'ees). Les deux \'etapes de cet algorithme sont les suivantes :
\begin{itemize}
\item Étape E : calcul de l'esp\'erance de la vraisemblance par rapport aux variables latentes en tenant compte des derni\`eres variables observ\'ees.
\item Étape M : on maximise cette esp\'erance par rapport aux param\`etres du mod\`ele.
\end{itemize}
L'\'etape E requiert l'estimation d'une esp\'erance, ce qui n'est pas toujours possible. Une alternative \`a cette m\'ethode est \index{algorithme!EM Monte Carlo}l'algorithme EM Monte Carlo, o\`u le calcul de l'esp\'erance est remplac\'e par la simulation de $n$~r\'ealisations iid des variables latentes et le calcul de la moyenne empirique associ\'ee.

