Lien de la note Hackmd
Evaluation : projet
On fait une marche aléatoire
On tire un , on preserve tous les
Au lieu de changer touT le vecteur, on ne change qu'une valeure (le ), l'algorithme convergera plus vite
Comment choisir alpha ?
On le prend très proche de 1
Algorithme de descente - principe :
Ici, la solution (le x que l'on retient) est le x tel que
Tour statistique : si j'itere 1million de fois,c'est sur que j'ai parcouru toutes mes variables
Notre algo n'est PAS une descente, c'est un optimiseur ! (On cherche minimum global, pas local)
Loi aléatoire avec une marche uniforme : c'est le CHAOS
Comment on choisi ?
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.
Plus T élevée (on va vers la droite) plus on se rapproche d'une loi uniforme
Si et loi uniforme alors on est trop a droite. Inversement, on sera trop à gauche. On veut donc : grand et 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 tq suit une loi suffisemment uniforme
Il faut donc prendre un et 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
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
On les precalcule
Le precalcul a un biais
:::
On va utiliser un tableau circulaire.
C'est pas possible, on aura des valeurs enormes
On a un tableau de valeurs de longueur :
est tres grand et nombre premier
On va faire un damier,
Par exemple, depend des valeurs qui l'entoure:
Propriete Markovienne
La probabilite d'avoir
: voisinnage de
Le voisinnage d'un graphe complet d'un noeud c'est tous les noeuds sauf lui-meme
La propriété Markovienne est équivalente à celle des chaines de Markov
Clique
C'est un ensemble de sommets qui sont voisins soit:
: et 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
Un graphe complet que l'on reduit aux voisins permet de reduire la dependance des variables.
Toujours vrai si
Modele graphique qui est un champs de Gibbs ?
On doit definir les fonctions et , avec:
: ordre de la clique
Sur une image en niveau de gris
depend de , , ,
Probabilité équiprobable -> U vaut 0
on a une vraissemblance quand on melange X et Y
Avec une clique d'ordre 2
Avec et :
Definissons
Tadaaa commande magique
Les énergies sont liées au proba
P appriori = P sachant …
Produit de P = Somme U (Car exp)