Learning Weighted Lower Linear Envelope Potentials in Binary Markov Random Fields

Markov random fields containing higher-order terms are becoming increasingly popular due to their ability to capture complicated relationships as soft constraints involving many output random variables. In computer vision an important class of constraints encode a preference for label consistency over large sets of pixels and can be modeled using higher-order terms known as lower linear envelope potentials. In this paper we develop an algorithm for learning the parameters of binary Markov random fields with weighted lower linear envelope potentials. We first show how to perform exact energy minimization on these models in time polynomial in the number of variables and number of linear envelope functions. Then, with tractable inference in hand, we show how the parameters of the lower linear envelope potentials can be estimated from labeled training data within a max-margin learning framework. We explore three variants of the lower linear envelope parameterization and demonstrate results on both synthetic and real-world problems.