Simulation algorithms

Probability law of a MRF

$$P(x)=\frac{1}{Z}\exp(-\sum_{c \in C} U_c (x))$$

Simulation

• The global law of a MRF is not directly computable, because of the partition function Z.
• It's possible to show that the conditionnal law has a simple form, with a simple local partition function.

=> We use one of the following sampling algorithms : Gibbs sampler, Metropolis dynamics.

Optimisation : Simulated annealing

• Gibbs distribution with a temperature

  
  

  $$P_T(X=x)=\frac{1}{Z(T)}\exp(-\frac{U(x)}{T})$$
  
  

     : P_T converges on the uniform law on .
    T = 0 : P_T is uniformly distributed on the gobal minima of U.

• Simulated annealing

  T⁽⁰⁾ high and for any x⁽⁰⁾.

  Step n : - simulation of x⁽ⁿ⁾ for Gibbs energy , from x^(n-1),
                 - decrease of temperature not slower than the theoretical bound, such that :
  

  $$T^{(n)}>\frac{c}{\log (1+n)}$$
  
  

  Iterations until a stopping criterion is fulfilled.