Try   HackMD

Lien de la note Hackmd

Tt+1Tt+1×α

Evaluation : projet

L'algorithme

On fait une marche aléatoire

T_∅ <- ?
loop i_cond <- ?
    tirage

On tire un

xcandidat, on preserve tous les
xxcandidat

x=(x1(t),,\colorbluexcandidat,xcandidat+1(t),xN(t))
Au lieu de changer touT le vecteur, on ne change qu'une valeure (le
xcandidat
), l'algorithme convergera plus vite

xcandidat=(idem,irandom,idem,irandom,idem)x(t)=()

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)

x(t+1)=(argminω1Ω1U(ω1,x2(t)),x2(t))var #1x(t+2)=(x1(t+1),argminω2Ω2U(ω2,x2(t+1)))var #2

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

Ucourant=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)

PT=limTPT

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Comment on choisi

T0 ?
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

TminTchercheTmaxuniforme

Si

Tmin et
Tmax
loi uniforme alors on est trop a droite. Inversement, on sera trop à gauche. On veut donc :
Tmax
grand et
Tmin
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

T0 tq
P(T0)
suit une loi suffisemment uniforme
Il faut donc prendre un
Tmin
et
Tmax
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
T0

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

icandidat swap 1icandidat 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

xcandidat de longueur
L
:

ai

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
13
4
14
16

PT(X=x)=1ZTeU(x)\colorblueT

Propriete Markovienne
La probabilite d'avoir

Xi=(x1,,xi1,xi+1,,xn)=XXi

P(Xi=xi|Xi=xi)=P(Xi=xi|Xνi=xνi)

Xνi=(Xν1i,,Xνwi)

νi: voisinnage de
i

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

Xt2Xt1XtP(Xt=xt|Xt1=xt1)\colorblueP(Xt|Xt2)

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

N(e) verifie{eN(e)eN(e)eN(e)

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

E={ei}{Eete,eE,eNeouE¯=1

eNe:
e
et
e
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)=Πc cliqueϕ(xc)

  • ϕ(xc)
    : fonction potentiel pour la clique
    c

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Toujours vrai si

x,P(X=x)=

P(X=x)=1ZeU(x)=1ZecEc(xc)

  • Avec
    Uc=ϕc
    fonction potentielle pour la clique
    c

Modele graphique qui est un champs de Gibbs ?

On doit definir les fonctions

Uc et
ϕc
, avec:

U(x)=cUc(xc)

c¯: ordre de la clique

Exemple

Sur une image en niveau de gris

P(X=x|Y=y)=ecUc(xc,y)

Xi depend de
Xi+1
,
Xi1
,
Xi+nc
,
Xinc

Probabilité équiprobable -> U vaut 0

on a une vraissemblance quand on melange X et Y

L(X=xi|Y=yi) proportionnelle à eUL(xi,yi)
Avec
UL(...)
une clique d'ordre 2

U(Xi=xiordre 1)=12U1(noirdans x)=12U1(blanc)=12 probabilite

U2(xi,xjordre 2=1xixj)
Avec
i
et
j
:

  • voisins
  • independants

Definissons

UL
UL(xi,yi)={255yisi xi=blanc et j voisins et indeyisinon

Tadaaa commande magique

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

U(x,y)=cUc(xc,y)=iU1(xi)+i,jvoisinsU2(xi,xj)ijN(i)U2(xi,xj)+iU2(xi,yi)=i(U2(xi,yi)\colorblueL(X|Y)+U1(xi)ordre 1+jN(i)U2(xi,xi)ordre 2P(a priori))U(x,y)=iUi(xi,xνi,yi)

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