Tighter Linear Program Relaxations for High Order Graphical Models
This work addresses inference accuracy issues in graphical models for researchers and practitioners in machine learning, representing an incremental improvement over standard methods.
The paper tackles the problem of loose linear program relaxations in high-order graphical models, which lead to poor inference results, by introducing additional consistency constraints and developing efficient message passing algorithms, showing empirically improved inference accuracy on challenging problems.
Graphical models with High Order Potentials (HOPs) have received considerable interest in recent years. While there are a variety of approaches to inference in these models, nearly all of them amount to solving a linear program (LP) relaxation with unary consistency constraints between the HOP and the individual variables. In many cases, the resulting relaxations are loose, and in these cases the results of inference can be poor. It is thus desirable to look for more accurate ways of performing inference in these models. In this work, we study the LP relaxations that result from enforcing additional consistency constraints between the HOP and the rest of the model. We address theoretical questions about the strength of the resulting relaxations compared to the relaxations that arise in standard approaches, and we develop practical and efficient message passing algorithms for optimizing the LPs. Empirically, we show that the LPs with additional consistency constraints lead to more accurate inference on some challenging problems that include a combination of low order and high order terms.