Learning Markov Networks by Analytic Center Cutting Plane Method

During the last decade the super-modular Pair-wise Markov Networks (SM-PMN) have become a routinely used model for structured prediction. Their popularity can be attributed to efficient algorithms for the MAP inference. Comparably efficient algorithms for learning their parameters from data have not been available so far. We propose an instance of the Analytic Center Cutting Plane Method (ACCPM) for discriminative learning of the SM-PMN from annotated examples. We empirically evaluate the proposed ACCPM on a problem of learning the SM-PMN for image segmentation. Results obtained on two public datasets show that the proposed ACCPM significantly outperforms the current state-of-the-art algorithm in terms of computational time as well as the accuracy because it can learn models which were not tractable by existing methods.