ext ref uncertainty

PRMs: Reference and Existence Uncertainty: 

PRMs: Reference and Existence Uncertainty Okan Basegmez PLL Seminar, WS03/04 Supervisor: Prof. Dr. Luc de Raedt, Kristian Kersting (Slides borrowed from Lise Getoor)

Outline: 

Outline Motivation PRMs with Reference Uncertainty Learning Settings PRMs with Existence Uncertainty Learning Settings Experiments Conclusion

Basic PRM Settings: 

Basic PRM Settings Fixed relational skeleton  set of objects in each class relations between them Uncertainty over assignment of values to attributes PRM defines distribution over instantiations of attributes

Extension Approach (1): 

Extension Approach (1) Motivation: relational structure provides useful information for density estimation and prediction Construct probabilistic models of relational structure that capture link uncertainty Two new mechanisms proposed: Reference uncertainty Existence uncertainty

Extension Approach (2): 

Extension Approach (2) Advantages: Applicable in cases where we do not have full knowledge of relational structure Incorporating uncertainty over relational structure into probabilistic model can improve predictive accuracy Two approaches: Reference uncertainty Existence uncertainty Different probabilistic models; varying amount of background knowledge required for each

Reference Uncertainty: 

Reference Uncertainty Bibliography Scientific Paper ` 1. ----- 2. ----- 3. ----- Document Collection

PRM with Reference Uncertainty: 

PRM with Reference Uncertainty Cites Cited Citing Paper Topic Words Paper Topic Words Dependency model for foreign keys Naïve Approach: multinomial over primary key noncompact limits ability to generalize

Reference Uncertainty Example: 

Reference Uncertainty Example Paper P5 Topic AI Paper P4 Topic AI Paper P3 Topic AI Paper M2 Topic AI Paper P1 Topic Theory Cites Cited Citing Paper P5 Topic AI Paper P3 Topic AI Paper P4 Topic Theory Paper P2 Topic Theory Paper P1 Topic Theory Paper.Topic = AI Paper.Topic = Theory P1 P2

Reference UncertaintyProbabilistic Model : 

Reference Uncertainty Probabilistic Model A probabilistic relational model with reference uncertainty has in addition for each reference slot in R(X) with range Y a new partition function with a set of partition attributes A new selector attribute Sp A set of parents and a CPD for Sp Then

Semantics: 

Semantics Cites Cited Citing Paper Topic Words Paper Topic Words PRM RU

Learning PRMs with Reference Uncertainty (1): 

Learning PRMs with Reference Uncertainty (1) Idea: just like in basic PRMs define scoring function do greedy local structure search Issues: expanded search space construct partitions new operators

Learning PRMs with Reference Uncertainty (2): 

Idea: define scoring function do local search over legal structures Key Components: legal models scoring models searching model space Learning PRMs with Reference Uncertainty (2) unchanged model new dependencies new operators

PRMs with Reference Uncertainty Summary: 

PRMs with Reference Uncertainty Summary Define semantics for uncertainty over foreign-key values Search now includes operators Refine and Abstract for constructing foreign-key dependency model

Existence Uncertainty: 

Existence Uncertainty Document Collection Document Collection

PRMs withExistence Uncertainty: 

PRMs with Existence Uncertainty Cites Paper Topic Words Paper Topic Words Exists Dependency model for existence of relationship

Existence Uncertainty Example: 

Existence Uncertainty Example Cites Paper Topic Words Paper Topic Words Exists Citer.Topic Cited.Topic False True

Existence UncertaintyProbabilistic Model: 

Existence Uncertainty Probabilistic Model Two changes to the definition of distributions 1) 2) Given an entity skeleton, a PRM with exists uncertainty specifies a distribution over a set of instantiations

Semantics: 

Semantics PRM EU Cites Exists Paper Topic Words Paper Topic Words

Learning PRMs with Existence Uncertainty (1): 

Learning PRMs with Existence Uncertainty (1) Idea: just like in PRMs with Attribute un. define scoring function do greedy local structure search Issues: efficiency Computation of sufficient statistics for exists attribute Do not explicitly consider relations that do not exist

Learning PRMs with Existence Uncertainty (2): 

Learning PRMs with Existence Uncertainty (2) Idea: define scoring function do phased local search over legal structures Key Components: legal models scoring models searching model space unchanged unchanged model new dependencies

Experiments : EachMovie: 

Experiments : EachMovie age personal_income household_income Person Movie Actor MOVIE ROLE VOTE PERSON ACTOR Size: 1600 Size: 35,000 Size: 50,000 Size: 25,000 Size: 300,000 †

Experiments : EachMovie Ref.Un.: 

Experiments : EachMovie Ref.Un. thriller horror gender theater_status gender video_status age animation art_foreign classic personal_income comedy drama rank household_income family Movie Person Movie Actor MOVIE ROLE VOTE PERSON ACTOR education

Experiments : EachMovie Ex.Un.: 

Experiments : EachMovie Ex.Un. comedy drama rank gender family personal_income horror romance exists household_income thriller exists gender theater_status action education animation art_foreign classic MOVIE ROLE VOTE PERSON ACTOR

Experiments: Prediction: 

Experiments: Prediction Paper P506 Topic ?? w1 wN . . .

Experiments: Domains: 

Experiments: Domains Cites Exists Paper Topic w1 wN . . . Paper Topic w1 wN . . . cited paper citing paper Cora Dataset, McCallum, et. al Link Exists Web Page Category w1 wN . . . Category w1 wN . . . From Page To Page Web Page

Experiments: Prediction Accuracy: 

Experiments: Prediction Accuracy

Conclusions: 

Conclusions PRMs can represent distribution over attributes from multiple tables PRMs can capture link uncertainty PRMs allow inferences about individuals while taking into account relational structure

References: 

References 'Learning Probabilistic Models of Link Structure', L. Getoor, N. Friedman, D. Koller, and B. Taskar. 'Learning Probabilistic Models of Relational Structure', L. Getoor, N. Friedman, D. Koller, and B. Taskar. 'Learning Statistical Models from Relational Data', L. Getoor.