Learning Markov Networks with Bounded Inference Complexity
Ujjwal Das Gupta, Sriram Srinivasan, Sanjeev Sharma, Russell Greiner · 2013
In this paper, we study the problem of learning the structure of Markov Networks that permit ecient inference. We formu-late structure learning as an optimization problem that maximizes the likelihood of the model such that the inference complexity on the resulting structure is bounded. The infer-ence complexity is measured with respect to any chosen algorithm (either exact or approx-imate), or a distribution over any marginal or conditional query. We relate our work to pre-vious approaches for learning bounded tree-width models and arithmetic circuits. The main contribution of our work is to isolate the inference penalty from the incremental struc-ture building process. Our algorithm can be used to learn networks which bound the in-ference time of both exact and approximate algorithms. Further, we show that bound-ing inference time for approximate inference results in networks that exhibit less approxi-mation error. 1.