Newton-type Methods for Inference in Higher-Order Markov Random Fields
This work addresses a critical bottleneck in probabilistic graphical models for researchers and practitioners, though it is incremental as it builds on existing linear programming relaxations.
The paper tackles the problem of efficiently solving the Lagrangian dual for MAP inference in higher-order Markov Random Fields by proposing a Newton-type method, achieving superior convergence and handling ill-conditioning better than first-order methods.
Linear programming relaxations are central to {\sc map} inference in discrete Markov Random Fields. The ability to properly solve the Lagrangian dual is a critical component of such methods. In this paper, we study the benefit of using Newton-type methods to solve the Lagrangian dual of a smooth version of the problem. We investigate their ability to achieve superior convergence behavior and to better handle the ill-conditioned nature of the formulation, as compared to first order methods. We show that it is indeed possible to efficiently apply a trust region Newton method for a broad range of {\sc map} inference problems. In this paper we propose a provably convergent and efficient framework that includes (i) excellent compromise between computational complexity and precision concerning the Hessian matrix construction, (ii) a damping strategy that aids efficient optimization, (iii) a truncation strategy coupled with a generic pre-conditioner for Conjugate Gradients, (iv) efficient sum-product computation for sparse clique potentials. Results for higher-order Markov Random Fields demonstrate the potential of this approach.