Concavity of reweighted Kikuchi approximation
This work addresses theoretical guarantees for approximate inference in probabilistic graphical models, which is incremental as it builds on existing Kikuchi and Bethe approximations.
The paper tackles the problem of ensuring concavity in a reweighted Kikuchi approximation for estimating log partition functions, establishing conditions for concavity and showing that a reweighted sum product algorithm yields global optima upon convergence, with simulations demonstrating advantages.
We analyze a reweighted version of the Kikuchi approximation for estimating the log partition function of a product distribution defined over a region graph. We establish sufficient conditions for the concavity of our reweighted objective function in terms of weight assignments in the Kikuchi expansion, and show that a reweighted version of the sum product algorithm applied to the Kikuchi region graph will produce global optima of the Kikuchi approximation whenever the algorithm converges. When the region graph has two layers, corresponding to a Bethe approximation, we show that our sufficient conditions for concavity are also necessary. Finally, we provide an explicit characterization of the polytope of concavity in terms of the cycle structure of the region graph. We conclude with simulations that demonstrate the advantages of the reweighted Kikuchi approach.