Stat 206A: Gibbs Measures, Fall 2006

In this course we will study the mathematical theory of Gibbs measures with special emphasis on its recent applications in machine learning, satisfiability, coding and computational biology. The mathematical theory of Gibbs measures uses discrete mathematics, convexity, ergodic theory, probability and analysis. The course will intertwine the theory with various applications.  The plan is to focus on the following topics:

1. Soft introduction to ensambles of factor graphs (chapters 9-12 in Constraint Satisfaction Networks in Physics and Computation). 

2. Low Density Parity Check Codes (chapters 2-3 in Modern Coding Theory).

3. Gibbs measures on trees and their role in studying Gibbs measures on general graphs (papers 1-5)

4. Gibbs measures on trees and Phylogenetics (papers 6-8).

5. Additional topics and students projects. .

 

Prerequisites: Strong background in probability and analysis. Background in Markov Chain Mote Carlo is recommended. For students with no background in MCMC it is recommended to concurrently take Sinclair's course. 

One year of Stat 205 or Stat 204 is required. Students who have not taken Stat 205 or Stat 204 and students who feel they may not have sufficient mathematical background are encouraged to contact the instructor in order to verify that they have the appropriate background.

 

 

Lectures: Tuesday & Thursday, 5-6:30pm, Evans 330.

 

Instructor: Elchanan Mossel (mossel@stat dot berkeley dot edu)

 

Grade: The grade will be based on the following:

  1. Participation.
  2. Scribing two lectures. You can find a latex file here.
  3. Submitting homework problems (10 points in total)
  4. Presenting a paper / project at the end of the term.

Bibliography -- Books
  1. Georgii, Hans-Otto Gibbs measures and phase transitions. de Gruyter Studies in Mathematics, 9. Walter de Gruyter & Co., Berlin, 1988. xiv+525 pp.
  2. Liggett, Thomas M. Interacting particle systems. Reprint of the 1985 original. Classics in Mathematics. Springer-Verlag, Berlin, 2005. xvi+496 pp
  3. Liggett, Thomas M. Stochastic interacting systems: contact, voter and exclusion processes. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 324. Springer-Verlag, Berlin, 1999. xii+332
  4. Modern Coding Theory by T. Richardson and R. Urbanke to appear in Cambridge University Press. 
  5. Constraint Satisfaction Networks in Physics and Computation by M. Mezard and A. Montanari, to appear in Oxford University Press.

Bibliography -- Papers
  1. Broadcasting on trees and the Ising model. (W. Evans, C. Kenyon, Y. Peres and L. Schulman).  Ann. Appl. Probab. 10, (2000), 410--433. 

  2. Information flow on trees   Mossel, Elchanan, Peres, Yuval Ann. Appl. Probab. 13 no.3 817--844. (2003)

  3. The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels

    Christian Borgs, Jennifer Chayes, Elchanan Mossel, Sebastien Roch

    To Appear in Proceedings of FOCS 2006 (2006)
  4. Loopy belief propagation and Gibbs measures. S. Tatikonda and M. I. Jordan. In D. Koller and A. Darwiche (Eds)., Uncertainty in Artificial Intelligence (UAI), Proceedings of the Eighteenth Conference, 2002.  
  5. Counting independent sets up to the tree threshold in STOC 2006 by D. Weitz.

  6. On the impossibility of reconstructing ancestral data and phylogenies

    Elchanan Mossel Jour. Comput. Bio. 10 no.5 669--678. (2003)

  7. Phase transitions in Phylogeny Elchanan Mossel
    Trans. Amer. Math. Soc.     356 no.6 2379--2404 (electronic).

  8. Optimal Phylogenetic Reconstruction    Constantinos Daskalakis, Elchanan Mossel, Sebatien Roch In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing (STOC 2006), 159--168,. (2006)


SCRIBE NOTES:

Scribe notes  : Motivating Example, Aug 29                                 Markov Factorization, Markov Property, Clifford Hammesrseley, Aug 31
Scribe notes  : Ensembles of Factor GraphsSep  5                      Random 1-SAT and 2-SAT, Sep 7
Scribe notes  : REM (Andrea Montanari), Sep  12                       Thresholds for Random 2-SAT, 2-XOR-SAT Sep 14
Scribe notes  : Some more SAT bounds, Sep  19                          Unit Clause Propagation, Sep 21
Scribe notes  : Second momment for SAT, Sep  26                       Introduction to LDPC, Sep 28
Scribe notes  : Weight Enumerator, Regular Codes, Oct3          The Saddle Point Method and Weight Enumeration for general Codes, Oct 5
Scribe notes  : Rate and Distance Properties of LDPC, Oct 10   Capacity of LDPC Codes, Oct 12
Scribe notes  : Bit Flipping Algorithms and Expansion, Oct 17  Decay of Correlation Notions, Oct 19
Scribe notes  : Belief Propagation, Oct 24                                    The computation tree, Oct 26
Scribe notes  : Uniqueness of Ising on the tree, Oct  31

SUGGESTED FINAL PROJECTS (Projects suggested by students are more than welcome!)

1. Clifford Hammersley for models with hard-core constraints: Geometry of rank tests,   Three Counterexamples on Semigraphoids     
2. Random sub-graphs:  Percolation  on finite graphs and isoperimetric inequalities - taken (Nov 30, Dey)
3. Models of Random Regular Graphs -- taken (Stauffer / Ding - Nov 14) .
4. Find simple proof for the threshold for RANDOM-2-SAT.
5. Hardness of sampling solutions of 2-SAT formula: On counting independent sets in sparse graphs. -- taken (Fabrikant, Nov 9)
6. Exponential algorithms for solving SAT problems: Find 1.999^m algorithm for solving a general SAT formula (m = # of clauses).
7. Aging in the Random Energy model and other models:  Dynamics of Trap Models and The Arcsine Law.
8. The differential Equations method. (+ Stochastic corrections?)
9. 2nd moment method for vatiants of the satisfiability problem.
10. Efficient Erasure Correcting Codes. -- Taken (Aminzadeh, Nov 28)
11. Random Vectors of Bounded Weight and their linear independence.
12. Any advanced topic in coding from Modern Coding Theory
13. The Saddle Point Method in Analytic Combinatorics.
14. The laplacian and Belief Propagation: On the properties of Bethe Approximation and Loopy Belief Propagation on binary networks.
15.. Bound Propagation.  -- taken (Nov 28, Simma)
16. Aldous' Objective Method.
17. Robust Uniqueness and Reconstruction.
18. Uniqueness as a local condition and on infinite systems from "Gibbs Measures and Phase Transitions" by Georgii.
19. Uniqueness and Reconstruction for SAT problems on trees.
20. Do spin-glasses care about geometry?  Newman's view.
21. Planted SAT is easy.  (and relation to real life problems?)
22. Some easy Phase transitions in Phylogeny. (Average branch length bounds? - taken Mefford, Nov 16)
23. Implementation of Phylogenetic bounds.
24. Reconstructing Markov-Random-Fields from observations?
25. Asymptotic convex geomery of tree colorings measures.

Final Projects

1. Nov 2nd:  Roch: Reconstruction on Trees
2. Nov 7th:   Daskalakis: Phylogenetic Reconstruction.
3. Nov 9'th:  Fabrikant : Hardness of sampling 2-SAT solutions +  Dimakis: Random Games.
4. Nov 14th: Ding + Stauffer: Random Regular Graphs.
5. Nov 16th:  Mefford: Easy Phylogenetic bounds + Sly: Uniqueness on graphs and Trees.
6. Nov 28th:  Aminzadeh: Efficient Erasure Correcting  Codes +  Simma: Bound Propagation.
7. Nov 30  :  Dey: Percolation on finite graphs + Etesami: SAT refutations. 
8. Dec   5   :  Moorea  TBA + Bresler: Aldous objective method.
9. Dec   7:   :  Sen: Easy proof for the 2-SAT threshold + concluding remaks.



Department of Statistics

Elchanan Mossel's homepage