Machine Learning Meetings and Events
Group Meetings: Group meetings are held Mondays from 11am to Noon (talk starts 11:10am) in D.L. Pratt 290C unless otherwise noted. Meetings are coordinated by Hugo Larochelle.
Tea Talks: Tea talks are held every Wednesday at 4:00pm in D.L. Pratt 290C. Talks should be simple, accessible, and not exceed 15 minutes. Speakers bring snacks, make tea, and provide a copy of the presented paper.
Group Meeting Oct 20, 2008: Solving Satisfiability (SAT) Problems Using Loopy Belief Propagation, and Deriving a Convergent Variant Based on EM
- Speaker: Eric Hsu
- Abstract:
You can represent a boolean satisfiability (SAT) problem as a factor graph, and use loopy belief propagation (BP) to compute the marginal probability that each variable should be positive or negative. SAT has special properties that makes this information very useful for randomly generated problems of interest, motivating approaches like Survey Propagation (SP), which is BP on a slightly richer problem representation. I would also like to discuss a variant of BP that was motivated by this SAT problem, but which can be used on any problem that BP is used on. The approach is called EMBP because it is based on the EM framework. Distinguishing features of EMBP are that it replaces an outer product in BP with an outer sum, and that it always converges.
Most recent paper on applying BP/SP/EMBP to SAT:
http://www.cs.toronto.edu/~eihsu/papers/hsu-tr577.pdfDeriving general version of EMBP:
http://www.cs.toronto.edu/~eihsu/papers/hsu-tr579.pdf