Champs de Markov: Metropolis-Hastings et recuit simule

Rappels

$P(X=x)$ => variable aleatoire

• $x$: ne pas lister toutes les valeurs possibles pour
  $X$

$$P(X=x\underset{\text{et}}{\underbrace{,}}Z=z)$$

On le notait

$\cap$ au lycee

$$P(A\cap B)=P(A).P(B)$$

• $X=(X_1,\dots ,X_n)$ est un vecteur aleatoire
• $x=(x_1,\dots ,x_n)$ est une realisation

Sudoku

Il existe une solution dediee mais on ne la connait pas

$\text{color}red{x}_1$	$\text{color}red{x}_2$
$\text{color}red{x}_4$	$2\text{color}green\to y_1$

$$P(\left|\begin{array}{cc}1|& 1\\ 1|& \end{array}\right|)=?\{\begin{array}{l}{x}_1=1\\ x_2=1\\ x_4=1\end{array}$$

Dans ce cas, on ne regard que 3 realisations et on va les evaluer

$$\begin{gathered} P(\left|\begin{array}{cc}1|& 1\\ 3|& \end{array}\right|)=?\{\begin{array}{l}{x}_1=1\\ x_2=1\\ x_4=3\end{array} \\ P(\left|\begin{array}{cc}1|& 3\\ 4|& \end{array}\right|)=?\{\begin{array}{l}{x}_1=1\\ x_2=3\\ x_4=4\end{array} \\ P(\left|\begin{array}{cc}3|& 1\\ 4|& \end{array}\right|)=?\{\begin{array}{l}{x}_1=3\\ x_2=1\\ x_4=4\end{array} \\ P(\left|\begin{array}{cc}1|& 1\\ 1|& \end{array}\right|)\text{color}green<P(\left|\begin{array}{cc}1|& 1\\ 3|& \end{array}\right|)\text{color}green<P(\left|\begin{array}{cc}1|& 3\\ 4|& \end{array}\right|)\text{color}green=P(\left|\begin{array}{cc}3|& 1\\ 4|& \end{array}\right|) \\ \text{color}red\boxed{{\displaystyle L(X=x|Y=y)=P(Y=y|X=x)}} \end{gathered}$$

On veut reecrire

$f(x,y)=\cos (x)\sin (\frac{1}{y})$ en

$g(y,x)$

$$g(a,b)=\cos (b)\sin (\frac{1}{a})$$

Retour au sudoku: on sait parler des probas et des vraisemblances

On lit les donnees a un espace de recherche

Pour avoir des vraisemblances:

$$\begin{array}{rlrlr}& L(\left|\begin{array}{cc}1|& 1\\ 1|& \text{color}red2\end{array}\right|)\text{color}red& L(\left|\begin{array}{cc}1|& 1\\ 3|& \text{color}red2\end{array}\right|)\text{color}red& L(\left|\begin{array}{cc}1|& 3\\ 4|& \text{color}red2\end{array}\right|)\text{color}red=& L(\left|\begin{array}{cc}3|& 1\\ 4|& \text{color}red2\end{array}\right|)\\ & \stackrel{\downarrow }{\overbrace{L(\left|\begin{array}{cc}2|& 1\\ 1|& \text{color}red2\end{array}\right|)}}& \uparrow & & \end{array}$$

Rappel : Bayes

$$\begin{array}{rl}{x}_{\text{sol}}={\text{arg max}}_x& \underbrace{P(X=x|Y=y)}\\ & =\text{color}blue\frac{L(X=\boxed{{\displaystyle x}}|Y=y)P(X=\boxed{{\displaystyle x}})}{P(Y=y)}\end{array}$$

La meteo de Gulli

Le retour de rand()

$$\{\begin{array}{ll}P(\text{beau})=0.5& \text{color}red\varnothing \\ P(\text{pourri})=0.3& \text{color}red1\\ P(\text{couvert})=0.2& \text{color}red2\end{array}\leftarrow P(T=t)t\in \text{{beau},\text{pourri},\text{couvert}}$$

$\varnothing \dots \varnothing$	$1|\text{color}red1\dots 1$	$2\dots 2$

C'est pareil pour le sudoku: tout depend de tout

On va voir comment calculer des probas ou les variables ne sont pas independantes

$$\begin{array}{rl}y& \to \\ u& \to \end{array}◯\to x_{\text{sol}}={\text{arg max}}_{x}P(X=x|Y=y)$$

$$\begin{gathered} \{\begin{array}{l}P(\text{beau})=0.4\\ P(\text{pluie})=0.1\\ P(\text{couvert})=0.2\\ P(\text{orage})=0.2\\ P(\text{neige})=0.2\end{array} \\ \text{color}red{x}_{sol}=beau \end{gathered}$$

On a un echantilloneur:

$$P\to ◯\to x$$

Il y a plus de chances que l'echantilloneur ne nous donne pas la bonne solution

Hypothese

$$\begin{gathered} U\to P? \\ \text{hypothese}:\mathrm{\nexists }x,P(x)=\varnothing \\ P(X=x)=\boxed{{\displaystyle \text{color}red\frac{1}{Z}{e}^{-U(x\text{color}green,y)}}}\Rightarrow U(x)=-\log (Z.\underset{\text{color}red\text{ouf}\ne \varnothing }{\underbrace{P(X=x)}}) \\ \sum _{x}P(X=x)=1\Rightarrow Z=\sum _x{e}^{-U(x)}>\varnothing \text{ une constante} \end{gathered}$$

Un algo: Metropolis-Hastings

Il a ete invente en meme temps par 2 chercheurs

$$\begin{gathered} x^{(0)}=\left|\begin{array}{cc}1& 1\\ 1& \text{⧸}2\end{array}\right|=\text{color}red\left(\begin{array}{c}1\\ 2\\ 1\end{array}\right) \\ {x}^{(1)}=\left|\begin{array}{cc}2& 1\\ 3& \text{⧸}2\end{array}\right|=\text{color}red\left(\begin{array}{c}2\\ 1\\ 3\end{array}\right) \\ ⋮ \\ {x}^{(t)}=\left|\begin{array}{cc}\bullet & \bullet \\ \bullet & \bullet \end{array}\right| \end{gathered}$$

Initialisation:

1. $x^0$ tire aleatoirement avec loi uniforme
2. $t\leftarrow \varnothing$
3. Repeter jusqu'a l'infini (un algo… a l'infini)

On fait juste un tres grand nombre d'iterations

*Repeter jusqu'a l'infini:

• $$x_{\text{rand}}$$ tire avec loi uniforme
• $$P_{\text{trans}}=\frac{P(X=x_{\text{candidat}})}{P(X=x^{(t)})}$$
• Si
  $$P_{\text{trans}}>1\text{color}red\iff P(X=x_{\text{candidat}})>P(X=x^{(t)})$$
• Alors
  $$x^{(t+1)}\leftarrow x_{\text{candidat}}\text{color}green\equiv \text{ MIEUX = ON GARDE}$$
• Sinon on fait
  $$\text{color}green\boxed{{\displaystyle x^{(t+1)}\leftarrow x_{\text{candidat}}}}\text{color}red\iff P(x_{\text{candidat}})<P(x^{(t)})$$ avec la proba
  $$P_{\text{trans}}\le 1$$
  • Sinon
    $x^{(t+1)}\leftarrow x^{(t)}$
• $t\leftarrow t+1$

Quel est cet algo ?

C'est un algorithme de descente

Cet algo est tel que la fonction

$P(x^{(t+1)})\ge P(x^{(t)})$, quand

$t$ augmente,

$P(x^{(t)})$ augmente aussi.

C'est un optimiseur hyper sous-efficace

Surtout compare a des algos de descente

Exemple

$0$	$1\dots \text{color}green\boxed{{\displaystyle 1}}1$	$0\dots 0$	RANDMAX

$$i_{\text{trans}}=0.8\times \text{RANDMAX}$$

• Si rand()
  $$<P_{\text{trans}}\times$$ RANDMAX
  • $x^{(t+1)}\leftarrow x_{\text{candidat}}$
• Sinon
  $x^{(t+1)}\leftarrow x^{(t)}$

$$\begin{array}{rl}P(X=x)& =\frac{1}{Z}{e}^{-U(x)}\\ P_{\text{trans}}& =\frac{\text{⧸}\frac{1}{Z}{e}^{-U(x_{\text{candidat}})}}{\text{⧸}\frac{1}{Z}{e}^{-U(x^{(t)})}}\\ & =e^{-(\underset{\text{color}red\mathrm{\Delta }U}{\underbrace{U(x_{\text{candidat}})-U(x^{(t)})}})}\end{array}$$

Recuit simule

Comme les forgerons qui chauffe la lame d'une epee, qui la mette dans l'eau le temps de manger, la rechauffe en revenant et la laisse refroidir lentement a l'air libre apres avoir ete formee

• Apres avoir ete dans l'eau, l'epee est cassante
• On atteint l'etat le plus stable possible en lassant refroidir lentement, l'epee est la plus solide possible

C'est un etat de basse energie qui pourrait etre trouve dans la nature

Algorithme

Initialisation

1. $T^{(\varnothing )}\leftarrow$ elevee
2. On repete:
   • $\mathrm{P̸}\to P_{T^{(t)}}$
   • $T^{(t+1)}\simeq T^{(t)-}$
   • $t\leftarrow t+1$

$$\begin{gathered} P_{\text{color}redT}(X=x)=\frac{1}{Z_{\text{color}redT}}{e}^{-U(x)} \\ P(X=x)\propto e^{-U(x)} \\ {P}_{\text{color}redT}(X=x)\propto e^{-\frac{U(x)}{T}} \\ {U}_T(x)=\frac{U(x)}{T} \end{gathered}$$

Exemples d'utilisation

• On prend une image en niveau de gris qu'on stylise
• On prend une image qu'on veut binariser, avec le moins de regions blanches/noires possibles mais les plus grandes possibles

Est-ce qu'on a la meilleure solution ?

On en a pas la moindre idee

Retour sur l'algo

Initialisation:

1. ${\mathrm{x̸}}^{(0)}$ tire aleatoirement (avec loi uniforme)
2. $t\leftarrow \varnothing$
   $\text{color}blue{T}^{(0)}\leftarrow \text{elevee}$
3. Repeter jusqu'a l'infini (un algo… a l'infini)

Repeter jusqu'a l'infini:

• $$x_{\text{rand}}$$ tire avec loi uniforme
• $$P_{\text{trans}}=\frac{P_{\text{color}blueT}(X=x_{\text{candidat}})}{P_{\text{color}blueT}(X=x^{(t)})}=e^{\frac{-(U(x_{\text{candidat}}-U(x^{(t)})))}{\text{color}blue{T}^{(t)}}}$$
• Si
  $$P_{\text{trans}}>1$$
• Alors
  $$x^{(t+1)}\leftarrow x_{\text{candidat}}\text{color}green\equiv \text{ MIEUX = ON GARDE}$$
• Sinon on fait
  $$\text{color}green\boxed{{\displaystyle x^{(t+1)}\leftarrow x_{\text{candidat}}}}$$ avec la proba
  $$P_{\text{trans}}\le 1$$
  • Sinon
    $x^{(t+1)}\leftarrow x^{(t)}$
• $\text{color}blue{T}^{(t+1)}\leftarrow \propto T^{(t)}\text{ ou }\propto =1^{-}$
• $t\leftarrow t+1$

Si on fait un tirage aleatoire, est-ce que c'est intelligent de mettre que des

$1$ dans une grille vide d'un sudoku ?

Non, c'est la meme proba de mettre des

$1$ que n'importe quel autre chiffre

$\text{color}blue1$	$\text{color}blue1$	$\text{color}blue1$	$\text{color}blue2$
$\text{color}blue2$	$\boxed{{\displaystyle 2}}$	$\boxed{{\displaystyle 3}}$	$\text{color}blue2$
$\text{color}blue3$	$\text{color}blue3$	$\text{color}blue3$	$\boxed{{\displaystyle 4}}$
$\boxed{{\displaystyle 1}}$	$\text{color}blue4$	$\text{color}blue4$	$\text{color}blue4$

C'est quoi l'interet de ce tirage "moins con"? (et pas du tout aleatoire)

On peut changer

$x^{(t)}$ aleatoirement (en echangeant des cases par exemples)

$\text{color}blue1$	$\text{color}blue1$	$\text{color}blue1$	$\text{color}red\boxed{{\displaystyle 3}}$
$\text{color}blue2$	$\boxed{{\displaystyle 2}}$	$\boxed{{\displaystyle 3}}$	$\text{color}blue2$
$\text{color}blue3$	$\text{color}red\boxed{{\displaystyle 2}}$	$\text{color}blue3$	$\boxed{{\displaystyle 4}}$
$\boxed{{\displaystyle 1}}$	$\text{color}blue4$	$\text{color}blue4$	$\text{color}blue4$

On met de l'intelligence dans cet algo qui a vraiment besoin d'etre aleatoire

$$\begin{gathered} P_{T\to +\mathrm{\infty }}(X=x)=\frac{1}{Z}{e}^{-\frac{U(x)}{T}} \\ \text{color}red{P}_{+\mathrm{\infty }}(x)=\frac{1}{Z}\text{uniforme} \\ \text{color}green{P}_1(x)=P(x) \\ {P}_0(x)=\varnothing \mathrm{\forall }x \end{gathered}$$

Ce n'est pas une loi de probabilite car la somme des probas

$=0$

On va determiner la loi de probas autrement, en regardant par exemple un ratio:

$$\begin{gathered} \frac{P_T(X=x_{\text{solution}})}{P_T(X=x)}=e_{\text{color}blue\to -\mathrm{\infty }}^{\boxed{{\displaystyle \frac{-(\stackrel{\text{color}red\text{positif}}{\overbrace{U(x)-U(x_{\text{solution}})}})}{T\text{color}green\to 0^{+}}}}}\to 0^{+} \\ \frac{P_0(x\ne x_{\text{solution}})}{P_0(x_{\text{solution}})}=\varnothing \\ \{\begin{array}{l}\mathrm{\forall }x\ne x_{\text{solution}},P_0(x)=\varnothing \\ P_0(x_{\text{solution}})=1\end{array} \end{gathered}$$

$$\begin{gathered} \downarrow \\ {P}_0(x)=\{\begin{array}{ll}1& \text{si }x=x_{\text{solution}}\\ \varnothing & \text{sinon}\end{array} \end{gathered}$$