Not Logged In

Learning Markov Networks with Bounded Inference Complexity

Full Text: inferning2013.pdf PDF

In this paper, we study the problem of learning the structure of Markov Networks that permit efficient inference. We formulate 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 inference complexity is measured with respect to any chosen algorithm (either exact or approximate), or a distribution over any marginal or conditional query. We relate our work to previous approaches for learning bounded treewidth models and arithmetic circuits. The main contribution of our work is to isolate the inference penalty from the incremental structure building process. Our algorithm can be used to learn networks which bound the inference time of both exact and approximate algorithms. Further, we show that bounding inference time for approximate inference results in networks that exhibit less approximation error.

Citation

U. Das Gupta, S. Sriram, S. Sharma, R. Greiner. "Learning Markov Networks with Bounded Inference Complexity". Interactions between Inference and Learning, June 2013.

Keywords: Markov Networks, Inference Complexity, Structure Learning
Category: In Workshop
Web Links: OpenReview

BibTeX

@misc{DasGupta+al:Inferning13,
  author = {Ujjwal Das Gupta and Srinivasan Sriram and Sanjeev Sharma and Russ
    Greiner},
  title = {Learning Markov Networks with Bounded Inference Complexity},
  booktitle = {Interactions between Inference and Learning},
  year = 2013,
}

Last Updated: February 12, 2020
Submitted by Sabina P

University of Alberta Logo AICML Logo