Published on August 27, 2007
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.