nips nips2012 nips2012-314 nips2012-314-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Tivadar Papai, Henry Kautz, Daniel Stefankovic
Abstract: Markov logic is a widely used tool in statistical relational learning, which uses a weighted first-order logic knowledge base to specify a Markov random field (MRF) or a conditional random field (CRF). In many applications, a Markov logic network (MLN) is trained in one domain, but used in a different one. This paper focuses on dynamic Markov logic networks, where the size of the discretized time-domain typically varies between training and testing. It has been previously pointed out that the marginal probabilities of truth assignments to ground atoms can change if one extends or reduces the domains of predicates in an MLN. We show that in addition to this problem, the standard way of unrolling a Markov logic theory into a MRF may result in time-inhomogeneity of the underlying Markov chain. Furthermore, even if these representational problems are not significant for a given domain, we show that the more practical problem of generating samples in a sequential conditional random field for the next slice relying on the samples from the previous slice has high computational cost in the general case, due to the need to estimate a normalization factor for each sample. We propose a new discriminative model, slice normalized dynamic Markov logic networks (SN-DMLN), that suffers from none of these issues. It supports efficient online inference, and can directly model influences between variables within a time slice that do not have a causal direction, in contrast with fully directed models (e.g., DBNs). Experimental results show an improvement in accuracy over previous approaches to online inference in dynamic Markov logic networks. 1
[1] Pedro Domingos and Daniel Lowd. Markov Logic: An Interface Layer for Artificial Intelligence. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2009.
[2] Thomas Geier and Susanne Biundo. Approximate online inference for dynamic markov logic networks. In Tools with Artificial Intelligence (ICTAI), 2011 23rd IEEE International Conference on, pages 764–768, 2011.
[3] Shalini Ghosh, Natarajan Shankar, and Sam Owre. Machine reading using markov logic networks for collective probabilistic inference. In In Proceedings of ECML-CoLISD., 2011.
[4] Vibhav Gogate and Rina Dechter. Samplesearch: Importance sampling in presence of determinism. Artif. Intell., 175(2):694–729, 2011.
[5] Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 1990.
[6] Dominik Jain, Andreas Barthels, and Michael Beetz. Adaptive Markov Logic Networks: Learning Statistical Relational Models with Dynamic Parameters. In 19th European Conference on Artificial Intelligence (ECAI), pages 937–942, 2010. 8
[7] K. Kersting, B. Ahmadi, and S. Natarajan. Counting belief propagation. In J. Bilmes A. Ng, editor, Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence (UAI–09), Montreal, Canada, June 18–21 2009.
[8] D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009.
[9] John Lafferty. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. pages 282–289. Morgan Kaufmann, 2001.
[10] Steffen Lauritzen and Thomas S. Richardson. Chain graph models and their causal interpretations. B, 64:321–361, 2001.
[11] B. Limketkai, D. Fox, and Lin Liao. CRF-Filters: Discriminative Particle Filters for Sequential State Estimation. In Robotics and Automation, 2007 IEEE International Conference on, pages 3142–3147, 2007.
[12] Andrew McCallum, Dayne Freitag, and Fernando C. N. Pereira. Maximum entropy markov models for information extraction and segmentation. In Proceedings of the Seventeenth International Conference on Machine Learning, ICML ’00, pages 591–598, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc.
[13] Kevin Patrick Murphy. Dynamic bayesian networks: representation, inference and learning. PhD thesis, 2002. AAI3082340.
[14] Aniruddh Nath and Pedro Domingos. Efficient belief propagation for utility maximization and repeated inference, 2010.
[15] Hoifung Poon and Pedro Domingos. Sound and efficient inference with probabilistic and deterministic dependencies. In Proceedings of the 21st national conference on Artificial intelligence - Volume 1, AAAI’06, pages 458–463. AAAI Press, 2006.
[16] G. Potamianos and J. Goutsias. Stochastic approximation algorithms for partition function estimation of Gibbs random fields. IEEE Transactions on Information Theory, 43(6):1948– 1965, 1997.
[17] Adam Sadilek and Henry Kautz. Recognizing multi-agent activities from GPS data. In TwentyFourth AAAI Conference on Artificial Intelligence, 2010.
[18] R. Salakhutdinov. Learning and evaluating Boltzmann machines. Technical Report UTML TR 2008-002, Department of Computer Science, University of Toronto, June 2008.
[19] Charles Sutton, Andrew McCallum, and Khashayar Rohanimanesh. Dynamic conditional random fields: Factorized probabilistic models for labeling and segmenting sequence data. J. Mach. Learn. Res., 8:693–723, May 2007. 9