Approximating the Partition Function by Deleting and then Correcting for Model Edges
This work addresses a computational bottleneck in probabilistic graphical models, offering a flexible approximation framework that is incremental, as it builds upon existing methods like the Bethe free energy.
The paper tackles the problem of approximating the partition function by proposing a two-step method that deletes model edges and then corrects for them, allowing a trade-off between approximation quality and computational complexity, with empirical results demonstrating its practical utility.
We propose an approach for approximating the partition function which is based on two steps: (1) computing the partition function of a simplified model which is obtained by deleting model edges, and (2) rectifying the result by applying an edge-by-edge correction. The approach leads to an intuitive framework in which one can trade-off the quality of an approximation with the complexity of computing it. It also includes the Bethe free energy approximation as a degenerate case. We develop the approach theoretically in this paper and provide a number of empirical results that reveal its practical utility.