Discriminative Probabilistic Models for Relational Data:

Discriminative Probabilistic Models for Relational Data Ben Taskar, Pieter Abbeel, Daphne Koller

Tradition statistic classification Methods:

Tradition statistic classification Methods Dealing with only ‘flat’ data – IID
In many supervised learning tasks, entities to be labeled are related to each other in complex way and their labels are not independent
This dependence is an important source of information to achieve better classification

Collective Classification:

Collective Classification Rather than classify each entity separately
Simultaneously decide on the class label of all the entities together
Explicitly take advantage of the correlation between the labels of related entitiies

Undirected vs. directed graphical models :

Undirected vs. directed graphical models Undirected graphical models do not impose the acyclicity constraint, but directed ones need acyclicity to define a coherent generative model
Undirected graphical models are well suited for discriminative training, achieving better classification accuracy over generative training

Our Hypertext Relational Domain:

Our Hypertext Relational Domain Label HasWord1 HasWordk ... Doc Label HasWord1 HasWordk ... Doc From To Link

Schema:

Schema A set of entity types
Attribute of each entity type
Content attribute E.X
Label attribute E.Y
Reference attribute E.R

Instantiation:

Instantiation Provide a set of entities I (E) for each entity type E
Specify the values of all the attribute of the entities, I.x, I.y, I.r
I.r is the instantiation graph, which is call relational skeleton in PRM

Cliques A set of nodes in the graph G such that
for each are connected by an
edge in G

Potentials:

Potentials The potential for the clique c defines the compatibility between values of variables in the clique
Log-linearly combination of a set of features

Probability in Markov Network:

Probability in Markov Network Given the values of all nodes in the Markov Network

Conditional Markov Network:

Conditional Markov Network Specify the probability of a set of target variables Y given a set of conditioning variables X

Relational Markov Network (RMN):

Relational Markov Network (RMN) Specifies the conditional probability over all the labels of all the entities in the instantiation given the relational structure and the content attributes
Extension of the Conditional Markov Networks with a compact definition on a relational data set

Relational clique template:

Relational clique template F --- a set of entity variables (From)
W--- the condition about the attributes of the entity variables (Where)
S --- subset of attributes (content and label attribute) of the entity variables (Select)

Relationship to SQL query:

Relationship to SQL query SELECT doc1.Category,doc2.Category
FROM doc1,doc2,Link link
WHERE link.From=doc1.key and link.To=doc2.key
Doc1 Doc2 Link Doc1

Potentials:

Potentials Potentials are defined at the level of relational clique template
The cliques of the same relational clique template have the same potential functions

Unrolling the RMN:

Unrolling the RMN Given an instantiation of a relational schema, unroll the RMN as follows
Find all the cliques in the unrolled the relational schema where the relational clique templates are applicable
The potential of a clique is the same as that of the relational clique template which this clique belongs to

Slide18:

Doc1 Doc3 Doc2 link1 link2

Probability in RMN:

Probability in RMN

Slide20:

Learning RMN:

Learning RMN Given a set of relational clique templates
Estimate feature weight w using conjugate gradient
Objective function--Product of likelihood of instantiation and parameter prior
Assume a shrinkage prior over feature weights

Learning RMN (Cont’d):

Learning RMN (Cont’d) The conjugate gradient of the objective function
where

Inference in RMN:

Inference in RMN Exact inference
Intractable due to the network is very large and densely connected
Approximate inference
Belief propagation

Experiments:

Experiments WebKB dataset
Four CS department websites
Five categories (faculty,student,project,course,other)
Bag of words on each page
Links between pages
Experimental setup
Trained on three universities
Tested on fourth

Flat Models:

Flat Models Based only on the text content on the WebPages
Incorporate meta-data

Relational model:

Relational model introduce relational clique template over the labels of two pages that are linked
Doc2 Link Doc1

Relational model (Cont’d):

Relational model (Cont’d) relational clique template over the label of section and the label of the pages it is on
Relational clique template over the label of the section containing the link and the label of the target page

Slide28:

Discriminative vs. Generative:

Discriminative vs. Generative Exit+Naïve Bayes: a complete generative model proposed by Getoor et al
Exit+logistic: using logistic regression for the conditional probability distribution of page label given words
Link: a fully discriminative training model

Slide30:

You do not have the permission to view this presentation. In order to view it, please
contact the author of the presentation.

Send to Blogs and Networks

Processing ....

Premium member

Use HTTPs

HTTPS (Hypertext Transfer Protocol Secure) is a protocol used by Web servers to transfer and display Web content securely. Most web browsers block content or generate a “mixed content” warning when users access web pages via HTTPS that contain embedded content loaded via HTTP. To prevent users from facing this, Use HTTPS option.