Discriminative Probabilistic Models for Relational Data

By B. Taskar, Pieter Abbeel, Daphne Koller. Conference on Uncertainty in Artificial Intelligence, 2002

821 citations recorded by the source corpus.

In many supervised learning tasks, the entities to be labeled are related to each other in complex ways and their labels are not independent. For example, in hypertext classification, the labels of linked pages are highly correlated. A standard approach is to classify each entity independently, ignoring the correlations between them. Recently, Probabilistic Relational Models, a relational version of Bayesian networks, were used to define a joint probabilistic model for a collection of related entities. In this paper, we present an alternative framework that builds on (conditional) Markov networks and addresses two limitations of the previous approach. First, undirected models do not impose the acyclicity constraint that hinders representation of many important relational dependencies in directed models. Second, undirected models are well suited for discriminative training, where we optimize the conditional likelihood of the labels given the features, which generally improves classification accuracy. We show how to train these models effectively, and how to use approximate probabilistic inference over the learned model for collective classification of multiple related entities. We provide experimental results on a webpage classification task, showing that accuracy can be significantly improved by modeling relational dependencies.

Subfields: Artificial Intelligence, Information Systems

View Paper: https://www.semanticscholar.org/paper/9cc36397e1fef5c922d64e88211a7e08ecc64759

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

Citations in the corpus

Learning Causal Models of Relational Domains (2010, methodology): “These algorithms are typically based on the search-andscore paradigm, with the objective of learning a model of high likelihood and not of explicitly learning the generative structure of the data (Getoor et al. 2007; Richardson and Domingos 2006; Taskar, Abbeel, and Koller 2002).”
Discovering molecular pathways from protein interaction and gene expression data (2003, methodology): “This algorithm has been shown to perform effectively for models of this type (Segal et al. , 2001; Taskar et al. , 2002).”
A bias/variance decomposition for models using collective inference (2008, methodology): “Relational autocorrelation is a statistical dependency between the values of the same variable (e.g., the class label) on related entities and is a nearly ubiquitous characteristic of relational datasets (Jensen and Neville 2002; Taskar et al. 2002; Bernstein et al. 2003; Hill et al. 2006).”
An Introduction to Conditional Random Fields for Relational Learning (2007, methodology): “For example, when classifying Web documents, the page’s text provides much information about the class label, but hyperlinks deﬁne a relationship between pages that can improve classiﬁcation [Taskar et al., 2002].”
A Linear Programming Formulation for Global Inference in Natural Language Tasks (2004, result): “It could be contrasted with other approaches to sequential inference or to general Markov random field approaches [2, 8].”
Max-Margin Markov Networks (2003, background): “This approach has the advantage of exploiting the cor relations between the different labels, allowing them to obtain significant improvements in accuracy over approaches that classify instances independently [7, 10].”
Collective Classi!cation in Network Data (2008, methodology): “…and Gallagher 2004; Neville and Jensen 2007) and the work of Ben Taskar and colleagues (Taskar, Segal , and Koller 2001; Getoor et al. 2001; Taskar, Abbeel, and Koller 2002; Taskar, Guestrin, and Koller 2003), the general problem of inference for structured output spaces has received…”
Deep transfer via second-order Markov logic (2009, background): “Relational Markov networks (RMNs) (Taskar et al., 2002) are another representation language that makes use of relational cliques.”
Combining content and link for classification using matrix factorization (2007, background): “[19] propose relational Markov networks (RMNs) for entity classification, by describing a conditional distribution of entity classes given entity attributes and relationships.”
Learning associative Markov networks (2004, methodology): “We also trained the same AMN model using the RMN approach of Taskar et al. (2002).”
Why collective inference improves relational classification (2004, background): “Researchers have evaluated their performance on several domains, including classifying web pages [1,15], tracking communicable diseases [6], and identifying topics in scientific literature [12].”
Collective Classification in Network Data (2008, methodology): “[12] mode, count, SQL RMNs, Taskar, Abbeel, & Koller [55] mode, SQL MLNs, Richardson & Domingos [51] FOL Lu & Getoor [35] mode, count, exists Macskassy & Provost [36] prop Gupta, Diwan, & Sarawagi [21] mode, count McDowell, Gupta, & Aha [39] prop”
A Survey of Link Prediction in Social Networks (2011, background): “[54] show how the parameters of a RMN over a xed set of cliques can be learned from data.”
Relational learning via latent social dimensions (2009, background): “Relational learning with collective inference has been shown to outperform models that do not consider the connectivity information [4, 33, 24].”
Using ghost edges for classification in sparsely labeled networks (2008, background): “In recent years, there has been a great deal of work on models for learning and inference in relational data [7, 10, 11, 16, 18].”
Probabilistic models with unknown objects (2006, background): “, 1999] and relational Markov networks [Taskar et al., 2002].”