Inference for order reduction in Markov random fields

This paper presents an algorithm for order reduction of factors in High-Order Markov Random Fields (HOMRFs). Standard techniques for transforming arbitrary high-order factors into pairwise ones have been known for a long time. In this work, we take a fresh look at this problem with the following motivation: It is important to keep in mind that order reduction is followed by an inference procedure on the order-reduced MRF. Since there are many possible ways of performing order reduction, a technique that generates “easier” pairwise inference problems is a better reduction. With this motivation in mind, we introduce a new algorithm called Order Reduction Inference (ORI) that searches over a space of order reduction methods to minimize the difficulty of the resultant pairwise inference problem. We set up this search problem as an energy minimization problem. We show that application of ORI for order reduction outperforms known order reduction techniques both in simulated problems and in real-world vision applications.