Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images

#pwlkyiv on a seminal paper by Stuart Geman and Donald Geman

http://ieeexplore.ieee.org/document/4767596/

Transcript

1. (Mis-)Interpretation by Vlad Ki
3. Statistical Physics
5. Outline
6. → Bayesian (an inference framework) → MRFs & Images (modeling image restoration images) → Gibbs Sampler (a computationally tractable representation for MRFs defined over graphs) → Relaxation (computing the best Gibbs)
8. (Statistics) Framework Wars Frequentist to Bayesian is like Angular to React
9. Bayes → originally published to make theological arguments → made cool by Laplace → inference and decision come as plugins → works recursively (Kalman, Particle filters & more, aka sequential estimation) → AI without a GPU: just refine your priors
10. → y - signal (measurement, evidence, input) → x - state (unknown, hypothesis, output) think: model parameters vs data
11. posterior = likelihood times prior, over evidence Bayes rule lets us swap those!
12. Estimation problems → MAP - maximum a posteriori → MLE - maximum likelihood (aka MAP when you have no prior)
13. logs are like probability buffs: slay exps, turn ugly into neat negation turns maximization into minimization
14. Aside energy log likelihood (stat physics and CV people like saying energy a lot)
15. Graphs
16. sites (nodes) neighborhood family (edges per site) neighborhood set, symmetric (undirected)
17. cliques are subsets of sites such that every pair in the set is a neighbor means "all cliques":
18. Graphs and Images
19. lattice:
20. Pixels: (grayscale) - 8-bit grayscale
21. Homogeneous neighborhoods
22. More than pixels "dual" lattice for edge elements, midway between each pixel pair
23. Or take both
25. MRF Markov Random Field
26. family of random variables per site
27. X is a MRF wrt if all probabilities are positive probability of a site given others is the same as a probability of a site given its neighbors (Markov Property)
28. Markov Property → probability at site depends only at values of a finite neighborhood → neighborhood of site
29. Bayesian Model
30. Noisy Image Prior → : pixel intensities ( ) → - some nonlinearity (like ) → - blur → - invertible noise
31. Original Image is a MRF over a graph that contains original intensities ( ) and image edges ( ). A set of all possible configurations of :
33. Posterior What was the original image given the data?
34. Maximum A Posteriori Let's enumerate states!
35. Hammersley-Clifford Theorem → any probability measure that satisfies a Markov property is a Gibbs distribution for an appropriate choice of (locally defined) energy function MRF Gibbs
36. Gibbs Distribution aka Boltzmann Distribution - temperature - energy function
37. → normalizing constant ("partition function")
38. What would U be? → - set of graph clique potentials
39. Gibbs Sampler → introduced in the subj paper → produces a Markov chain with as equilibrium distribution → MCMC algorithm family
40. P(new state of site) = Gibbs(visited now | others) P(everyone else before) → This MAP is a statistical process itself (hence MCMC) → Parallel!
41. Theorem A (Relaxation) No matter where we start ( ), our state will end up a Gibbs Distribution if we keep ( ) sampling infinitely .
42. Simulated Annealing (general intuition)
43. Experiments
44. Clique potentials? What configurations of local variables are preferred to others
45. What are clique potentials for restoring images? [end of section ]
50. Runnable Demo → http://www.inf.u-szeged.hu/~kato/software/ → "Supervised Image Segmentation Using Markov Random Fields" → "Supervised Color Image Segmentation in a Markovian Framework" → Usable on https://github.com/proger/mrf
52. Beyond
53. → Do more things with MRFs! (like segmentation) → MAP using Graph Cuts (Ford-Fulkerson for max- flow/min-cut) → CRF (learning potentials by conditioning on training data)
54. Next steps Probabilistic Graphical Models by Daphne Koller (MRF is a "undirected probabilistic graphical model") Pattern Recognition and Machine Learning by Christopher Bishop (More theory on everything)