Learning Markov Networks with Bounded Inference Complexity
- Ujjwal Das Gupta, University of Alberta
- Srinivasan Sriram, University of Alberta
- Sanjeev Sharma, University of Alberta
- Russ Greiner, Dept of Computing Science; PI of AICML
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