Lien de la note Hackmd

$$T_{t+1}\leftarrow T_{t+1}\times \alpha$$

Evaluation : projet

L'algorithme

On fait une marche aléatoire

T_∅ <- ?
loop i_cond <- ?
    tirage

On tire un

$x_{candidat}$, on preserve tous les

$x\ne x_{candidat}$

$$x=(x_1^{(t)},\dots ,x_{candidat},x_{candidat+1}^{(t)},x_N^{(t)})$$
Au lieu de changer touT le vecteur, on ne change qu'une valeure (le

$x_{candidat}$), l'algorithme convergera plus vite

$$\begin{array}{ccccccc}& x_{candidat}=(& \text{idem},& \boxed{{\displaystyle i_{random}}},& \text{idem},& \boxed{{\displaystyle i_{random}}},& \text{idem})\\ & & \updownarrow & \searrow & \updownarrow & \swarrow & \updownarrow \\ & & & \nearrow & & \nwarrow & \\ & x^{(t)}=(& & \boxed{{\displaystyle }}& & \boxed{{\displaystyle }}& )\end{array}$$

Comment choisir alpha ?
On le prend très proche de 1

Algorithme de descente - principe :

• parcourir toutes les variables
• Et pour chacunes des variables on parcourt toutes les valeurs possibles et on minimise l'energie (U) : Ca converge forcement mais ca converge vers un minimum local (et c'est pas ce qu'on cherche)

$$\begin{gathered} x^{(t+1)}=(\text{arg}\underset{{\omega }_1\in {\mathrm{\Omega }}_1}{min}U({\omega }_1,x_2^{(t)}),x_2^{(t)})\text{var \#}1 \\ {x}^{(t+2)}=(x_1^{(t+1)},\text{arg}\underset{{\omega }_2\in {\mathrm{\Omega }}_2}{min}U({\omega }_2,x_2^{(t+1)}))\text{var \#}2 \end{gathered}$$

Ici, la solution (le x que l'on retient) est le x tel que

$U_{courant}=min$

Tour statistique : si j'itere 1million de fois,c'est sur que j'ai parcouru toutes mes variables

∞ loop
    Umin
    pour toutes les variables
        ... descente
    Ucourant
    si Ucourant = Umin
        conv. or
    sinon
        Umin = Ucourant

Notre algo n'est PAS une descente, c'est un optimiseur ! (On cherche minimum global, pas local)

$$P_{T_{\varnothing }}=\underset{T\to \mathrm{\infty }}{lim}{P}_T$$

Loi aléatoire avec une marche uniforme : c'est le CHAOS

Comment on choisi

$T_0$ ?
On prend une grande et une petite valeur de temperature et on fait une dichotomie. On mesure le nombre de fois ou on a monte et descendu en energie, ces mesure doivent etre equivalentes.

Si on a une temperature trop faible ?
Alors ce n'est pas une loi uniforme.

$----->T$ Plus T élevée (on va vers la droite) plus on se rapproche d'une loi uniforme

$$\begin{array}{ccc}{T}_{min}& T_{cherche}& T_{max}\\ & \equiv & \\ & \text{uniforme}& \end{array}$$

Si

$T_{min}$ et

$T_{max}$ loi uniforme alors on est trop a droite. Inversement, on sera trop à gauche. On veut donc :

$T_{max}$ grand et

$T_{min}$ petit mais pas trop.

Comment on fait la dichotomie ?
Il ne faut pas uniforme ou pas uniforme, il faut du suffisemment uniforme.

Recap
On cherche

$T_0$ tq

$P(T_0)$ suit une loi suffisemment uniforme
Il faut donc prendre un

$T_{min}$ et

$T_{max}$ avec une loi pas uniforme pour le min et uniforme pour le max.
On fait donc une dichotomie qui nous ramenera a 2 lois suffisemment uniforme pour trouver le

$T_0$

Peu de montées par rapport aux descentes énergétiques

$=$ on converge

Si je n'arrive pu à monter alors je suis proche de ma solution

Comment on optimise des tirages aleatoires ?
Ou

$$i_{\text{candidat swap }1}{i}_{\text{candidat swap }2}$$

On les precalcule

Le precalcul a un biais

:::

On va utiliser un tableau circulaire.

loop
    icandidat <- aleatoire

C'est pas possible, on aura des valeurs enormes

On a un tableau de valeurs

$x_{candidat}$ de longueur

$L$:

$\dots$	$a_i$	$\dots$

$L$ est tres grand et nombre premier

On va faire un damier,

$x^{(t)}=$

$1$	$11$	$2$	$12$	$3$
$13$	$4$	$14$	$5$	$15$
$6$	$16$	$7$		$8$
	$9$		$10$

Par exemple,

$4$ depend des valeurs qui l'entoure:

	$11\updownarrow$
$13\leftrightarrow$	$4$	$\leftrightarrow 14$
	$16\updownarrow$

$$P_T(X=x)=\frac{1}{Z_T}{e}^{-\frac{U(x)}{T}}$$

Propriete Markovienne
La probabilite d'avoir

$X^i=(x_1,\dots ,x_{i-1},x_{i+1},\dots ,x_n)=X\setminus X_i$

$$P(X_i=x_i|X^i=x^i)=P(X_i=x_i|X_{{\nu }_i}=x_{{\nu }_i})$$

$$X_{{\nu }_i}=(X_{{\nu }_1^i},\dots ,X_{{\nu }_w^i})$$

${\nu }_i$: voisinnage de

$i$

Le voisinnage d'un graphe complet d'un noeud c'est tous les noeuds sauf lui-meme

$$\to \stackrel{P(X_t|X_{t-2})}{\overbrace{X_{t-2}\to \underset{P(X_t=x_t|X_{t-1}=x_{t-1})}{\underbrace{X_{t-1}\to X_t}}}}$$

La propriété Markovienne est équivalente à celle des chaines de Markov

$$\mathcal{N}(e)\text{ verifie}\{\begin{array}{l}e\notin \mathcal{N}(e)\\ e\in \mathcal{N}(e^{\prime })\Rightarrow e^{\prime }\in \mathcal{N}(e)\end{array}$$

Clique
C'est un ensemble de sommets qui sont voisins soit:

$$E=\{\dots e_i\dots \}\{\begin{array}{l}E\ne \mathrm{\varnothing }\\ \text{et}\\ \mathrm{\forall }e,e^{\prime }\in E,e\mathcal{N}{e}^{\prime }\\ \text{ou}\\ \overline{E}=1\end{array}$$

$e\mathcal{N}{e}^{\prime }$:

$e$ et

$e^{\prime }$ sont voisins

E est un ensemble de sommet 2 à 2 voisins

un singleton est une clique, on dit que c'est une clique d'ordre 1

Une clique d'ordre n c'est un ensemble de n sommet 2 a 2 voisins

4 ord 1
4 ord 2
1 ord 3
----
9

Un graphe complet que l'on reduit aux voisins permet de reduire la dependance des variables.

$$P(X=x)={\mathrm{\Pi }}_{\text{c clique}}\varphi (x_c)$$

• $\varphi (x_c)$: fonction potentiel pour la clique
  $c$

Toujours vrai si

$\mathrm{\nexists }x,P(X=x)=\varnothing$

$$\begin{array}{rl}P(X=x)& =\frac{1}{Z}{e}^{-U(x)}\\ & =\frac{1}{Z}{e}^{-\sum _c{E}_c(x_c)}\end{array}$$

• Avec
  $U_c={\varphi }_c$ fonction potentielle pour la clique
  $c$

Modele graphique qui est un champs de Gibbs ?

On doit definir les fonctions

$U_c$ et

${\varphi }_c$, avec:

$$U(x)=\sum _c{U}_c(x_c)$$

$\overline{c}$: ordre de la clique

Exemple

Sur une image en niveau de gris

$$P(X=x|Y=y)=e^{-\sum _c{U}_c(x_c,y)}$$

$X_i$ depend de

$X_{i+1}$,

$X_{i-1}$,

$X_{i+nc}$,

$X_{i-nc}$

Probabilité équiprobable -> U vaut 0

on a une vraissemblance quand on melange X et Y

$$L(X=x_i|Y=y_i)\text{ proportionnelle à }{e}^{-U_L(x_i,y_i)}$$
Avec

$U_L(...)$ une clique d'ordre 2

$$\begin{gathered} U(X_i=\underset{\text{ordre }1}{\underbrace{x_i}})=\frac{1}{2} \\ {U}_1(\underset{\text{dans }x}{\underbrace{\text{noir}}})=\frac{1}{2} \\ {U}_1(\text{blanc})=\frac{1}{2}\mathrm{\forall }\text{ probabilite} \end{gathered}$$

$$U_2(\underset{\text{ordre }2}{\underbrace{x_i,x_j}}=1_{x_i\ne x_j})$$
Avec

$i$ et

$j$:

• voisins
• independants

Definissons

$U_L$

$$U_L(x_i,y_i)=\{\begin{array}{ll}255-y_i& \text{si }{x}_i=\text{blanc et }j\text{ voisins et inde}\\ y_i& \text{sinon}\end{array}$$

Tadaaa commande magique

$$\begin{array}{rl}U(x,y)& =\sum _c{U}_c(x_c,y)\\ & =\sum _i{U}_1(x_i)+\stackrel{\sum _i\sum _{j\in \mathcal{N}(i)}{U}_2(x_i,x_j)}{\overbrace{\sum _{i,j_{voisins}}{U}_2(x_i,x_j)}}+\sum _i{U}_2(x_i,y_i)\\ & =\sum _i(\stackrel{L(X|Y)}{\overbrace{U_2(x_i,y_i)}}+\stackrel{P_{(\text{a priori})}}{\overbrace{\underset{\text{ordre }1}{\underbrace{U_1(x_i)}}+\underset{\text{ordre }2}{\underbrace{\sum _{j\in \mathbb{N}(i)}{U}_2(x_i,x_i)}}}})\\ \Rightarrow U(x,y)& =\sum _i{U}_i(x_i,x_{{\nu }_i},y_i)\end{array}$$

Les énergies sont liées au proba
P appriori = P sachant …
Produit de P = Somme U (Car exp)