To estimate the partition function of a graphical model we need to integrate (sum) an arbitrary non-negative function f over its entire domain. For non-negative functions, integration can be reduced (in a probabilistic, approximate sense) to maximization over random subsets of the domain defined by uniformly random systems of linear equations modulo 2 (parity constraints). Unfortunately, using dense parity matrices makes maximization computationally intractable (even if maximization over the entire domain, i.e., MAP, used to be easy), while using sparse matrices leads to poor approximation.
We introduce two ideas to address this problem, motivated by the theory of error-correcting codes. The first idea exploits code linearity to reduce integration to unconstrained optimization over an exponentially smaller domain. The second idea, closer in spirit to the original approach, is to use systems of linear equations defining Low Density Parity Check (LDPC) codes. Even though the equations in such systems only contain few variables each, their sets of solutions (codewords) have excellent statistical properties. By combining these ideas we achieve dramatic speedup and levels of accuracy that were completely unattainable previously.
Based on joint work with Pei Jiang.