lprm tutorial

Views:
 
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

Learning Statistical Models From Relational Data: 

Learning Statistical Models From Relational Data Lise Getoor University of Maryland, College Park Joint work with: Nir Friedman, Hebrew U. Daphne Koller, Stanford Avi Pfeffer, Harvard Ben Taskar, Stanford

Outline: 

Outline Motivation and Background PRMs w/ Attribute Uncertainty PRMs w/ Link Uncertainty PRMs w/ Class Hierarchies Statistical Relational Models

Discovering Patterns in Structured Data: 

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

Outline: 

Outline Background: Bayesian Networks (BNs) [Pearl, 1988] Probabilistic Relational Models (PRMs) Learning PRMs w/ Attribute Uncertainty PRMs w/ Link Uncertainty PRMs w/ Class Hierarchies Statistical Relational Models

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 andamp; 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.

Outline: 

Outline Background: Bayesian Networks (BNs) Probabilistic Relational Models (PRMs) [Pfeffer, 2000] Learning PRMs w/ Attribute Uncertainty PRMs w/ Link Uncertainty PRMs w/ Class Hierarchies Statistical Relational Models

Probabilistic Relational Models : 

Probabilistic Relational Models Combine advantages of relational logic andamp; 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

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.HC.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.PS.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)

Slide34: 

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

Outline: 

Outline Motivation and Background PRMs w/ Attribute Uncertainty PRMs w/ Link Uncertainty PRMs w/ Class Hierarchies Statistical Relational Models

Introduction: 

Introduction Topic Theory AI Agent Scientific Paper Attributes of object Attributes of linked objects Attributes of heterogeneous linked objects Collective Classification

Our Approach: 

Our Approach Motivation: relational structure provides useful information for density estimation and prediction Construct probabilistic models of relational structure that capture link uncertainty Here we propose 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/ Link Uncertainty : 

PRMs w/ Link 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 Cited Citing 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 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

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 Cited Citing Citing 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

Slide65: 

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 * †

Slide66: 

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

Slide67: 

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

Outline: 

Outline Motivation and Background PRMs w/ Attribute Uncertainty PRMs w/ Structural Uncertainty PRMs w/ Class Hierarchies Statistical Relational Models

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 andamp; 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 Koller andamp; Pfeffer 1998 Pfeffer 2000

Learning PRM-CHs: 

Learning PRM-CHs Relational Schema Database: TVProgram Person Vote Person Vote Instance I Class hierarchy provided

Bayesian Model Selection for PRMs: 

Bayesian Model Selection for PRMs Idea: define scoring function do phased local search over legal structures Key Components: scoring models searching model space 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

Slide91: 

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

Slide92: 

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

Outline: 

Outline Motivation and Background PRMs w/ Attribute Uncertainty PRMs w/ Structural Uncertainty PRMs w/ Class Hierarchies Statistical Relational Models Summary

Statistical Relational Models: 

Statistical Relational Models Capture the frequency information, rather than probabilistic information about individuals Application to selectivity estimation, SIGMOD01 Here, development of theory

A Comparison of Two Aproaches: 

A Comparison of Two Aproaches Possible Worlds Domain Frequency Generalization Compression Syntax - (almost) same Learning - (almost) same Semantics - (very) different Inference - (very) different

Application: Query Result Size Estimation: 

Crucial for Multirelational data mining cost-based query optimization query profilers Key: joint frequency distribution FD (A1,…,An) Application: Query Result Size Estimation FD (X,Y) = FD (x2 , y3) Problem: exponential in # of attributes vn  representing distribution exactly is infeasible

Traditional Approaches to Selectivity Estimation: 

Traditional Approaches to Selectivity Estimation Approximate joint distribution by making several key independence assumptions: Attribute Value Independence: joint distribution is product of single attribute distributions Join Uniformity Assumption: tuple in one relation is equally likely to join with any tuple in the other relation

SRMs: 

SRMs Use graphical models to compactly represent joint distribution over single table for select selectivity over multiple tables for join selectivity Provides a unified framework for estimating the selectivity of select-join queries over multiple tables

System Architecture: 

System Architecture Model Constructor Database offline Methods for incremental maintenance of BN Friedman and Goldszmidt, 1997

BN Construction*: 

BN Construction* Heuristic search over graph and tree structure at nodes Learn more complex networks when required, simpler networks when possible; subject to storage size restrictions Key computational step: computation of sufficient statistics - frequency of different instantiations of a node and its parents in DB Database Construct BN B s.t. PD(A1,…,An)  FD (A1,…,An)/ |R| * Cooper and Herkovits, 1992; Heckerman, 1995

BNs for Selectivity Estimation: 

BNs for Selectivity Estimation Query: select * from R where R.A1 = a1 and … and R.Ak = ak Size(Q) = |R|  PD(a1,…,ak) Use Bayesian inference algorithm* to compute PD(a1,…,ak) Algorithm complexity depends on BN connectivity; efficient in practice * Pearl, 1988; Lauritzen and Spiegelhalter, 1988

Foreign-key Join Selectivity: 

Foreign-key Join Selectivity Person Purchase Uniform Join Assumption Assuming referential integrity

Correlated Attributes: 

Correlated Attributes Person Purchase Income = high Income = low Type = luxury Type = necessity

Skewed Join: 

Skewed Join Person Purchase Income = high Income = low Type = luxury Type = necessity

Join Indicator : 

Join Indicator S R Query: select * from R, S where R.F = S.K and R.A = a and S.B = b P(JF) = prob. randomly chosen tuple from R joins with a randomly chosen tuple from S size(Q) = | R | | S | P(JF, a, b)

Universal Foreign Key Closure: 

Universal Foreign Key Closure A DB schema is table-stratified if we can order the tables s.t. if R.F refers to S.K, S precedes R.F in the stratification ordering The universal foreign key closure is the query constructed by introducing a tuple variable for each leaf in the stratification, and, introducing, for each foreign key, a new tuple variable

Universal Foreign Key Closure: 

Universal Foreign Key Closure Schema: R, S, T R.F refers to S, S.F refers to T stratification: T andlt; S andlt; R r s t r r.F1 = s.K s.F2 = t.K

Statistical Relational Models: 

Statistical Relational Models Model distribution of attributes across multiple tables Allow attribute values to depend on attributes in the same table (like a BN) Allow attribute values to depend on attributes in other tables along a foreign key join Can model the join probability of two tuples using join indicator variable

Example SRM: 

Example SRM Person Income Age School Prestige Jschool Attended Bought-by

Path Dependency Graph: 

Path Dependency Graph Construct path dependency graph T C S JT U D JS 2 R A JS 1 B Q JR E JU

SRM Semantics: 

SRM Semantics Theorem: If D is a model of  then PU(V) = P(V) Definition: D is a model of  if over same table-stratified schema IU(V,nondescendants(V)|Pa(V),J*=T) PU(V|Pa(V),J*=T) = P(V|Pa(V),J*=T)

Answering Queries Using SRMs: 

Answering Queries Using SRMs Construct Query Evaluation BN for Query: select * from Person, Purchase where Person.id = Purchase.buyer-id and Person.Income = high and Purchase.Type = luxury Compute upward closure of query attributes by including all parents as well Person Income Age School Prestige Purchase Jperson Type Jperson Jschool

SRM Learning : 

SRM Learning Learn parameters andamp; qualitative dependency structure Extend known techniques for learning Bayesian networks from data and learning PRMs Database Patient Strain Contact

Structure selection: 

Structure selection Idea: like in BNs define scoring function Generalization: Bayesian Score, MDL Compression: modified LL do greedy local structure search Issues: immense set of structures searching over large space efficiency sufficient statistics harder to compute: associated with multiple entities requires intelligent use of DB technology

SRM for TB Database: 

closecont hiv age smear care us_born hhoohh J_patient infected disease_site J_strain gender contage treatment race contype homeless unique Strain Contact Patient SRM for TB Database

Query Evaluation BN for TB: 

hiv us_born J_strain gender race homeless unique Query Evaluation BN for TB Query: select * from patient, strain where patient.strain = strain.id and patient.homeless = true

Experimental Setup: 

Experimental Setup Compare Sampling BN w/ Uniform Join SRM with same storage restrictions Two realworld databases: TB database and financial database* Relative error on three different query sets; each query joins three relations, select on one attribute from each relation * http://lisp.vse.cz/pkdd99/chall.htm, 1999

Results on Select-Join Queries: 

Results on Select-Join Queries Account 4.5K tuples Transaction 106K tuples District 77 tuples 0 10 20 30 40 50 60 70 80 90 100 1 2 3 Query Set Average Relative Error (%) SAMPLE BN+UJ SRM Patient 2.3K tuples Contact 20K tuples Strain 1K tuples Construction Time: 124 sec Estimation Time: 0.004 sec Construction Time: 157 sec Estimation Time: 0.002 sec 0 200 400 600 800 1000 1200 1400 1 2 3 Query Set Average Relative Error (%) SAMPLE BN+UJ SRM

SRMs vs PRMs: 

SRMs vs PRMs Syntax - (almost) same Learning - (almost) same Semantics - (very) different Inference - (very) different

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 (they do not make inapproriate independence assuptions) SRMs provide a unified framework for selectivity estimation for both select and join operations SRMs provide extremely compact model that captures frequency information in multirelational data

Selected Publications: 

Selected Publications 'Learning Probabilistic Models of Link Structure', L. Getoor, N. Friedman, D. Koller and B. Taskar, JMLR 2002. 'Probabilistic Models of Text and Link Structure for Hypertext Classification', L. Getoor, E. Segal, B. Taskar and D. Koller, IJCAI WS ‘Text Learning: Beyond Classification’, 2001. 'Selectivity Estimation using Probabilistic Models', L. Getoor, B. Taskar and D. Koller, SIGMOD-01. 'Learning Probabilistic Relational Models', L. Getoor, N. Friedman, D. Koller, and A. Pfeffer, chapter in Relation Data Mining, eds. S. Dzeroski and N. Lavrac, 2001. see also N. Friedman, L. Getoor, D. Koller, and A. Pfeffer, IJCAI-99. 'Learning Probabilistic Models of Relational Structure', L. Getoor, N. Friedman, D. Koller, and B. Taskar, ICML-01. 'From Instances to Classes in Probabilistic Relational Models', L. Getoor, D. Koller and N. Friedman, ICML Workshop on Attribute-Value and Relational Learning: Crossing the Boundaries, 2000. Notes from AAAI Workshop on Learning Statistical Models from Relational Data, eds. L.Getoor and D. Jensen, 2000. Notes from IJCAI Workshop on Learning Statistical Models from Relational Data, eds. L.Getoor and D. Jensen, 2003. See http://www.cs.umd.edu/~getoor

authorStream Live Help