nips nips2010 nips2010-71 nips2010-71-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Ni Lao, Jun Zhu, Liu Xinwang, Yandong Liu, William W. Cohen
Abstract: Markov networks (MNs) can incorporate arbitrarily complex features in modeling relational data. However, this flexibility comes at a sharp price of training an exponentially complex model. To address this challenge, we propose a novel relational learning approach, which consists of a restricted class of relational MNs (RMNs) called relation tree-based RMN (treeRMN), and an efficient Hidden Variable Detection algorithm called Contrastive Variable Induction (CVI). On one hand, the restricted treeRMN only considers simple (e.g., unary and pairwise) features in relational data and thus achieves computational efficiency; and on the other hand, the CVI algorithm efficiently detects hidden variables which can capture long range dependencies. Therefore, the resultant approach is highly efficient yet does not sacrifice its expressive power. Empirical results on four real datasets show that the proposed relational learning method can achieve similar prediction quality as the state-of-the-art approaches, but is significantly more efficient in training; and the induced hidden variables are semantically meaningful and crucial to improve the training speed and prediction qualities of treeRMNs.
[1] Galen Andrew and Jianfeng Gao. Scalable training of ℓ1 -regularized log-linear models. In ICML, 2007.
[2] Razvan C. Bunescu and Raymond J. Mooney. Collective information extraction with relational Markov networks. In ACL, 2004.
[3] Miguel A. Carreira-Perpinan and Geoffrey E. Hinton. On contrastive divergence learning. In AISTATS, 2005.
[4] Gal Elidan and Nir Friedman. The information bottleneck em algorithm. In UAI, 2003.
[5] Gal Elidan, Noam Lotner, Nir Friedman, and Daphne Koller. Discovering hidden variables: A structure-based approach. In NIPS, 2000.
[6] Nir Friedman, Lise Getoor, Daphne Koller, and Avi Pfeffer. Learning probabilistic relational models. In IJCAI, 1999.
[7] Yi Huang, Volker Tresp, and Stefan Hagen Weber. Predictive modeling using features derived from paths in relational graphs. In Technical report, 2007.
[8] Ariel Jaimovich, Ofer Meshi, and Nir Friedman. Template-based inference in symmetric relational Markov random fields. In UAI, 2007.
[9] Charles Kemp, Joshua B. Tenenbaum, Thomas L. Griffiths, Takeshi Yamada, and Naonori Ueda. Learning systems of concepts with an infinite relational model. In AAAI, 2006.
[10] Stanley Kok and Pedro Domingos. Learning the structure of Markov logic networks. In ICML, 2005.
[11] Stanley Kok and Pedro Domingos. Statistical predicate invention. In ICML, 2007.
[12] Stanley Kok and Pedro Domingos. Learning Markov logic networks using structural motifs. In ICML, 2010.
[13] Su-In Lee, Varun Ganapathi, and Daphne Koller. Efficient structure learning of Markov networks using ℓ1 -regularization. In NIPS, 2006.
[14] Kurt T. Miller, Thomas L. Griffiths, and Michael I. Jordan. Nonparametric latent feature models for link prediction. In NIPS, 2009.
[15] Kevin P. Murphy, Yair Weiss, and Michael I. Jordan. Loopy belief propagation for approximate inference: An empirical study. In UAI, 1999.
[16] Iftach Nachman, Gal Elidan, and Nir Friedman. “Ideal parent” structure learning for continuous variable networks. In UAI, 2004.
[17] Simon Perkins, Kevin Lacker, and James Theiler. Grafting: Fast, incremental feature selection by gradient descent in function spaces. In JMLR, 2003.
[18] Hoifung Poon and Pedro Domingos. Joint inference in information extraction. In AAAI, 2007.
[19] Karen Sachs, Omar Perez, Dana Peer, Douglas A. Lauffenburger, and Garry P. Nolan. Causal protein-signaling networks derived from multiparameter single-cell data. In Science, 2005.
[20] Ilya Sutskever, Ruslan Salakhutdinov, and Josh Tenenbaum. Modelling relational data using Bayesian clustered tensor factorization. In NIPS, 2009.
[21] Benjamin Taskar, Pieter Abbeel, and Daphne Koller. Discriminative probabilistic models for relational data. In UAI, 2002.
[22] Benjamin Taskar, Eran Segal, and Daphne Koller. Probabilistic classification and clustering in relational data. In IJCAI, 2001.
[23] Max Welling and Geoffrey E. Hinton. A new learning algorithm for mean field Boltzmann machines. In ICANN, 2001.
[24] Zhao Xu, Volker Tresp, Kai Yu, and Hans-Peter Kriegel. Infinite hidden relational models. In UAI, 2006.
[25] Alan Yuille. The convergence of contrastive divergence. In NIPS, 2004.
[26] Jun Zhu, Ni Lao, and Eric P. Xing. Grafting-light: Fast, incremental feature selection and structure learning of Markov random fields. In KDD, 2010.
[27] Hui Zou and Trevor Hastie. Regularization and variable selection via the elastic net. In Journal Of The Royal Statistical Society Series B, 2005. 9