Published on February 18, 2008
SRL Approaches: Frame-based Probabilistic models: SRL Approaches: Frame-based Probabilistic models February 11, 2005 Today’s Outline: Today’s Outline Finish w/ Graphical Models Introduction Families of SRL Approaches Frame-based Probabilistic approaches Probabilistic Relational Models (PRMs) Probabilistic Entity Relation (PERs) SRL History: SRL History In general, SRL combines logic and probabilities Historically, there are two general threads of research The first takes graphical models or hierarchical Bayesian models and adds in some form of relational/logical representation examples: Probabilistic Relational Models (PRMs), Probabilistic Entity Relation Models (PERs), Object Oriented Bayesian Networks (OOBNs) comes largely from the Uncertainty in AI (UAI} community The second takes a logical representation (first-order logic, horn clauses, etc) and adds in some form of probabilities examples: Bayesian Logic Programs (BLPs), Stochastic Logic Programs (SLPs) comes largely from the Inductive Logic Programming (ILP) community Families of SRL Approaches: Families of SRL Approaches Frame-based Probabilistic Models Probabilistic Relational Models (PRMs), Probabilistic Entity Relation Models (PERs), Object Oriented Bayesian Networks (OOBNs) First Order Probabilistic Logic (FOPL) BLOGs Relational Markov Logic (RML) Stochastic Functional Programs PRISM Stochastic Logic Programs (SLPs) IBAL SRL Dimensions: SRL Dimensions Syntax – ‘logic-based’ vs. ‘schema-based’ Logical Semantics – relational vs. first-order domain closure/closed world vs. open world Probabilistic Semantics – ‘possible worlds’ vs. ‘domain frequencies’ directed vs. undirected models … others? Today: PRMs: Today: PRMs Developed by Daphne Koller’s group at Stanford representation: Avi Pfeffer builds on work in KBMC (knowledge-based model construction) by Haddawy, Poole, Wellman and others… Object Oriented Bayesian Networks Relational Probability Models learning: myself, Nir Friedman, Avi Attribute Uncertainty Structural Uncertainty Class Uncertainty Identity Uncertainty undirected models: Ben Taskar Motivation: Discovering Patterns in Structured Data: Motivation: Discovering Patterns in Structured Data Learning Statistical Models: Learning Statistical Models Traditional approaches work well with flat representations fixed length attribute-value vectors assume independent (IID) sample Problems: introduces statistical skew loses relational structure incapable of detecting link-based patterns must fix attributes in advance Roadmap: Roadmap Background: Bayesian Networks (BNs) [Pearl, 1988] Probabilistic Relational Models (PRMs) Learning PRMs w/ Attribute Uncertainty PRMs w/ Structural Uncertainty PRMs w/ Class Hierarchies Bayesian Networks: Bayesian Networks nodes = random variables edges = direct probabilistic influence Network structure encodes independence assumptions: XRay conditionally independent of Pneumonia given Infiltrates Bayesian Networks: Bayesian Networks Associated with each node Xi there is a conditional probability distribution P(Xi|Pai:) — distribution over Xi for each assignment to parents If variables are discrete, P is usually multinomial P can be linear Gaussian, mixture of Gaussians, … 0.8 0.2 p t p 0.6 0.4 0.01 0.99 0.2 0.8 t p t t p T P P(I |P, T ) BN Semantics: BN Semantics Compact & natural representation: nodes have k parents 2k n vs. 2n params conditional independencies in BN structure + local probability models full joint distribution over domain = Queries: Queries Full joint distribution specifies answer to any query: P(variable | evidence about others) XRay Lung Infiltrates Sputum Smear Tuberculosis Pneumonia XRay Sputum Smear BN Learning: BN Learning BN models can be learned from empirical data parameter estimation via numerical optimization structure learning via combinatorial search. BN hypothesis space biased towards distributions with independence structure. Roadmap: Roadmap Background: Bayesian Networks (BNs) Probabilistic Relational Models (PRMs) Learning PRMs w/ Attribute Uncertainty PRMs w/ Structural Uncertainty PRMs w/ Class Hierarchies Probabilistic Relational Models : Probabilistic Relational Models Combine advantages of relational logic & Bayesian networks: natural domain modeling: objects, properties, relations; generalization over a variety of situations; compact, natural probability models. Integrate uncertainty with relational model: properties of domain entities can depend on properties of related entities; uncertainty over relational structure of domain. Relational Schema: Relational Schema Strain Unique Infectivity Infected with Interacted with Describes the types of objects and relations in the database Contact Close-Contact Skin-Test Age Patient Homeless HIV-Result Ethnicity Disease-Site Contact-Type Probabilistic Relational Model: Probabilistic Relational Model Close-Contact Transmitted Contact-Type Disease Site Strain Unique Patient Homeless HIV-Result POB Contact Age Relational Skeleton : Relational Skeleton 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 A Portion of the BN: A Portion of the BN P1.Disease Site P1.Homeless P1.POB C1.Close-Contact C1.Transmitted C1.Contact-Type C1.Age C2.Close-Contact C2.Transmitted C2.Contact-Type C2.Age PRM: Aggregate Dependencies: PRM: Aggregate Dependencies sum, min, max, avg, mode, count Disease Site Patient Homeless POB Age Close-Contact Contact-Type Contact PRM with AU Semantics: PRM with AU Semantics PRM relational skeleton + = Strain s1 Patient p1 Patient p2 Contact c3 Contact c2 Contact c1 Strain s2 Patient p3 Next Time 2/18: Next Time 2/18 Structural Uncertainty Learning Probabilistic Models of Link Structure, L. Getoor, N. Friedman, D. Koller, B. Taskar. Journal of Machine Learning Research, 2002. http://www.cs.umd.edu/class/spring2005/cmsc828g/Readings/jmlr02.pdf Class Uncertainty PRMs with Class Hierarchies, chapter 5 of Learning Statistical Models of Relational Data, Lise Getoor, PhD Thesis, Stanford University, 2001. http://www.cs.umd.edu/class/spring2005/cmsc828g/Readings/thesis-ch5.pdf PERS Probabilistic Models for Relational Data, David Heckerman, Christopher Meek and Daphne Koller ftp://ftp.research.microsoft.com/pub/tr/TR-2004-30.pdf Background on Learning Graphical Models available in CS Library Today’s Outline 2/18: Today’s Outline 2/18 Frame-based Probabilistic approaches Probabilistic Relational Models (PRMs) Learning PRMs PRMs w/ Structural Uncertainty PRMs w/ Class Hierarchies Probabilistic Entity Relation (PERs) Learning PRMs w/ AU: Learning PRMs w/ AU Database Patient Strain Contact Relational Schema Patient Contact Strain Parameter estimation Structure selection Parameter Estimation in PRMs: Parameter Estimation in PRMs Assume known dependency structure S Goal: estimate PRM parameters q entries in local probability models, q is good if it is likely to generate the observed data, instance I . MLE Principle: Choose q* so as to maximize l As in Bayesian network learning, crucial property: decomposition separate terms for different X.A ML Parameter Estimation: ML Parameter Estimation Contact CloseContact Transmitted Patient HIV DiseaseSite Structure Selection: Structure Selection Idea: define scoring function do local search over legal structures Key Components: legal models scoring models searching model space Structure Selection: Structure Selection Idea: define scoring function do local search over legal structures Key Components: legal models scoring models searching model space Legal Models: Legal Models author-of PRM defines a coherent probability model over a skeleton if the dependencies between object attributes is acyclic How do we guarantee that a PRM is acyclic for every skeleton? Researcher Prof. Gump Reputation high Paper P1 Accepted yes Paper P2 Accepted yes sum Attribute Stratification: Attribute Stratification PRM dependency structure S dependency graph Paper.Accecpted Researcher.Reputation if Researcher.Reputation depends directly on Paper.Accepted Algorithm more flexible; allows certain cycles along guaranteed acyclic relations Structure Selection: Structure Selection Idea: define scoring function do local search over legal structures Key Components: legal models scoring models searching model space Scoring Models: Scoring Models Bayesian approach: Standard approach to scoring models; used in Bayesian network learning Structure Selection: Structure Selection Idea: define scoring function do local search over legal structures Key Components: legal models scoring models searching model space Searching Model Space: Searching Model Space Contact Strain Patient Phase 0: consider only dependencies within a class Phased Structure Search: Contact Strain Patient score Add P.HC.T Contact Strain Patient Contact Patient Strain Phase 1: consider dependencies from “neighboring” classes, via schema relations Phased Structure Search Phased Structure Search: Phased Structure Search score Add C.PS.I Phase 2: consider dependencies from “further” classes, via relation chains Contact Strain Patient Contact Strain Patient Contact Strain Patient Experimental Evaluation: Experimental Evaluation Synthetic Data: Synthetic Data Simple ‘genetic’ domain Construct training set of various sizes Compare the log-likelihood of test set of size 100,000 ‘gold’ standard model Learn parameters (model structure given) Learn model (learn both structure and parameters) Slide40: Blood Type M-chromosome P-chromosome Person Result Contaminated Blood Test Blood Type M-chromosome P-chromosome Person Blood Type M-chromosome P-chromosome Person (Father) (Mother) Error on Test Set: Error on Test Set Error Variance: Error Variance Errors in Learned Structure: Errors in Learned Structure TB Cases in SF: TB Cases in SF Patient (2300) Ethnicity Homeless Age @ diagnosis HIV result Disease-site X-ray Contact (20000) Contact-type Age Care Infected Strain (1000) Unique Drug-Resistance TB PRM: hivres # contacts result transmitted infectivity smrpos care closecont ageatdx closecont hh_oohh ethnic # infected % infected hh_oohh contype homeless gender contype disease site contage xray pob Contact Strain Subcase Patient TB PRM SEC PRM: total assets # roles rtn earn assets age rtn assets fired # employees top_role top_role total_assets retired retired salary salary Company Role Prev-Role Person SEC PRM 20,000 120,000 40,000 Your turn…: Your turn… Describe your focus problem What would a PRM for (an aspect of) your focus problem look like? Roadmap: Roadmap Motivation and Background PRMs w/ Attribute Uncertainty PRMs w/ Structural Uncertainty PRMs w/ Class Hierarchies An Example: An Example Topic Theory AI Agent Scientific Paper Attributes of object Attributes of linked objects Attributes of heterogeneous linked objects Collective Classification Structural Uncertainty: Structural Uncertainty Motivation: relational structure provides useful information for density estimation and prediction Construct probabilistic models of relational structure that capture structural uncertainty Two new mechanisms: Reference uncertainty Existence uncertainty PRMs w/ AU: another example: PRMs w/ AU: another example Vote Movie Person PRM consists of: Relational Schema PRM w/ Attribute Uncertainty: Fixed relational skeleton : set of objects in each class relations between them Movie m1 Vote v1 Movie: m1 Person: p1 Person p2 Person p1 Movie m2 Uncertainty over assignment of values to attributes PRM w/ Attribute Uncertainty Vote v2 Movie: m1 Person: p2 Vote v3 Movie: m2 Person: p2 PRM w/ AU Semantics: PRM w/ AU Semantics PRM relational skeleton + = Patient p2 Vote Movie Person Movie Vote Vote Person Person Movie Vote Issue: Issue PRM w/ AU applicable only in domains where we have full knowledge of the relational structure Next we introduce PRMs which allow uncertainty over relational structure… PRMs w/ Structural Uncertainty : PRMs w/ Structural Uncertainty 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 Citation Relational Schema: Citation Relational Schema Wrote Paper Topic Word1 WordN … Word2 Paper Topic Word1 WordN … Word2 Cites Count Citing Paper Cited Paper Author Institution Research Area Attribute Uncertainty: Attribute Uncertainty Paper Word1 Topic WordN Wrote Author ... Research Area Institution Reference Uncertainty: Reference Uncertainty Bibliography Scientific Paper ` 1. ----- 2. ----- 3. ----- Document Collection PRM w/ Reference Uncertainty: PRM w/ Reference Uncertainty Cites Citing Cited Dependency model for foreign keys Paper Topic Words Paper Topic Words 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 Citing Cited 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 PRMs w/ RU Semantics: PRMs w/ RU Semantics Cites Cited Citing Paper Topic Words Paper Topic Words PRM RU Learning PRMs w/ RU: Learning PRMs w/ RU Idea: just like in PRMs w/ AU define scoring function do greedy local structure search Issues: expanded search space construct partitions new operators Learning : Learning Idea: define scoring function do phased local search over legal structures Key Components: legal models scoring models searching model space PRMs w/ RU model new dependencies new operators unchanged Structure Search: New Operators: Structure Search: New Operators Cites Citing Cited Cited Author Institution PRMs w/ RU Summary: PRMs w/ RU Summary Define semantics for uncertainty over foreign-key values Search now includes operators Refine and Abstract for constructing foreign-key dependency model Provides one simple mechanism for link uncertainty Existence Uncertainty: Existence Uncertainty Document Collection Document Collection PRM w/ Exists Uncertainty: PRM w/ Exists Uncertainty Cites Dependency model for existence of relationship Paper Topic Words Paper Topic Words Exists Exists Uncertainty Example: Exists Uncertainty Example Cites Paper Topic Words Paper Topic Words Exists Citer.Topic Cited.Topic False True PRMs w/ EU Semantics: PRMs w/ EU Semantics PRM EU Cites Exists Paper Topic Words Paper Topic Words Learning PRMs w/ EU: Learning PRMs w/ EU Idea: just like in PRMs w/ AU 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 Structure Selection: Structure Selection Idea: define scoring function do phased local search over legal structures Key Components: legal models scoring models searching model space PRMs w/ EU model new dependencies unchanged unchanged Slide72: Experiment I: EachMovie+ age personal_income household_income Person Movie Actor MOVIE ROLE VOTE PERSON ACTOR * © 1999 -2000 Internet Movie Database Limited † http://www.research.digital.com/SRC/EachMovie Size: 1600 Size: 35,000 Size: 50,000 Size: 25,000 Size: 300,000 * † Slide73: EachMovie+ PRM-RU 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 Slide74: EachMovie+ PRM-EU 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 Experiment II: Prediction: Experiment II: Prediction Paper P506 Topic ?? w1 wN . . . Domains: 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 WebKB, Craven, et. al Prediction Accuracy : Prediction Accuracy Prediction Accuracy : Prediction Accuracy Experiment III: Collective Classification: Experiment III: Collective Classification Paper#2 Topic Paper#3 Topic WordN Paper#1 Word1 Topic ... ... ... Author#1 Area Inst #1-#2 Author#2 Area Inst Exists #2-#3 Exists #2-#1 Exists #3-#1 Exists #1-#3 Exists WordN Word1 WordN Word1 Exists Topic Topic Area Area #3-#2 Inference in Unrolled BN: Inference in Unrolled BN Prediction requires inference in “unrolled” network Infeasible for large networks Use approximate inference for E-step Loopy belief propagation (Pearl, 88; McEliece, 98) Scales linearly with size of network Guaranteed to converge only for polytrees Empirically, often converges in general nets (Murphy,99) Local message passing Belief messages transferred between related instances Induces a natural “influence” propagation behavior Instances give information about related instances Web Domain: ... From-Page Category Word1 WordN Exists From To Link Hub To-Page Word Anchor Has ... Category Word1 WordN Hub Web Domain WebKB Results*: WebKB Results* * from “Probabilistic Models of Text and Link Structure for Hypertext Classification”, Getoor, Segal, Taskar and Koller in IJCAI 01 Workshop Text Learning: Beyond Classification Roadmap: Roadmap Motivation and Background PRMs w/ Attribute Uncertainty PRMs w/ Structural Uncertainty PRMs w/ Class Hierarchies From Instances to Classes in Probabilistic Relational Models: From Instances to Classes in Probabilistic Relational Models Compare two approaches Probabilistic Relational Models (PRMs) Bayesian Network (BNs) PRMs with Class Hierarchies (PRM-CH) bridge gap between BNs and PRMs Learning PRM-CHs hierarchy supplied discovering hierarchy PRM for Collaborative Filtering: PRM for Collaborative Filtering Vote Program Voter Ranking + Dependency Model Relational Schema Person Age Gender Education PRM Instantiation: PRM Instantiation TV-Program Nova Genre doc Budget low Timeslot primetime Network PBS Person Jane Doe Age elderly Gender female Education bs Income medium Vote #5630 Ranking ? TV-Program Seinfeld Genre sitcom Budget high Timeslot rerun Network ABC TV-Program Frasier Genre sitcom Budget medium Timeslot primetime Network ABC Person John Deer Age middle-aged Gender male Education hs Income low Vote #5631 Ranking ? Vote #5632 Ranking ? Vote #5632 Ranking ? Vote #5633 Ranking ? Income Income 1 . 0 6 . 0 3 . 0 5 . 0 4 . 0 1 . 0 4 . 0 5 . 0 1 . 0 1 . 0 4 . 0 5 . 0 bs hs sitcom bs doc hs doc h m l E G sitcom BN for Collaborative filtering: BN for Collaborative filtering Law & Order Frasier NBC Monday Night Movies Mad about you Beverly Hills 90210 Seinfeld Friends Melrose Place Models Inc. Breese, et al. UAI-98 Limitations of PRMs: Limitations of PRMs In PRM, all instances of the same class must use the same dependency mode, it cannot distinguish: documentaries and sitcoms “60 Minutes” and Seinfeld PRM cannot have dependencies that are “cyclic” ranking for Frasier depends on ranking for Friends Limitations of BNs: Limitations of BNs In BN, each instance has its own dependency model, cannot generalize over instances If John tends to like sitcoms, he will probably like next season’s offerings whether a person enjoys sitcom reruns depends on whether they watch primetime sitcoms BN can only model relationships between at most one class of instances at a time In previous model, cannot model relationships between people if my roommate watches Seinfeld I am more likely to join in Desired Model : Desired Model Allows both class and instance dependencies PRMs w/ Class Hierarchies : PRMs w/ Class Hierarchies Allows us to: Refine a “heterogenous” class into more coherent subclasses Refine probabilistic model along class hierarchy Can specialize/inherit CPDs Construct new dependencies that were originally “acyclic” Provides bridge from class-based model to instance-based model PRM-CH: PRM-CH Person Age Gender Education Income Vote Program Voter Ranking Relational Schema Class Hierarchy SoapOpera Learning PRM-CHs: Learning PRM-CHs Relational Schema Database: TVProgram Person Vote Person Vote Instance I Class hierarchy provided Structure Selection: Structure Selection Idea: define scoring function do phased local search over legal structures Key Components: scoring models searching model space PRM w/ CHs new operators unchanged Guaranteeing Acyclicity with Subclasses: Guaranteeing Acyclicity with Subclasses Learning PRM-CH : Scenario 1: Class hierarchy is provided New Operators Specialize/Inherit Learning PRM-CH BudgetDocumentary Learning Class Hierarchy : Learning Class Hierarchy Issue: partially observable data set Construct decision tree for class defined over attributes observed in training set class2 New operator Split on class attribute Related class attribute Slide98: MOVIE Drama Comedy Romance Action Horror Thriller Theater Status Video Status Art/Foreign Classic VOTE Rating EachMovie+ PRM 1400 Movies 5000 People 240,000 Votes http://www.research.digital.com/SRC/EachMovie Slide99: PRM-CH Comparison : Comparison 5 Test Sets: 1000 votes, ~100 movies, ~115 people PRM Mean LL: -12,079, std 475.68 PRM-CH Mean LL: -10558, std 433.10 Using standard t-test, PRM-CH model outperforms PRM model with over 99% confidence PRM-CH Summary: PRM-CH Summary PRMs with class hierarchies are a natural extension of PRMs: Specialization/Inheritance of CPDs Allows new dependency structures Provide bridge from class-based to instance-based models Learning techniques proposed Need efficient heuristics Empirical validation on real-world domains Roadmap: Roadmap Motivation and Background PRMs w/ Attribute Uncertainty PRMs w/ Structural Uncertainty PRMs w/ Class Hierarchies Next Time 2/25: Next Time 2/25 Focus Problems Please add your focus problem to the class wiki Give a PRM for the problem Give a PER for the problem Give at least one of the logical-based methods (BLP, LPRM, LBN) For each representation, discuss some modeling issue, or some novelty you used – e.g. structural uncertainty, constraints, etc. Readings for next three weeks 2/28 – Logic-based approaches 3/4 – Advanced Logic-based approaches 3/11 – Undirected Models Please sign up to lead the discussion for one of the papers 2/28 – 3/11 For each paper, please post your comments for each paper on the wiki by midnight Wed before the class in which they are assigned to be discussed. This gives the discussion leader some time to synthesize the comments.