Learning Probabilistic Relational ModelsOverviewMotivationRelated WorkWhat are PRMs?Mapping PRMs from Relational ModelsPRM SemanticsUniversity Domain Example - Relational SchemaPRM Semantics ContinuedSlide 10University Domain Example – An Instance of the SchemaUniversity Domain Example – Another Instance of the SchemaSlide 13Slide 14Slide 15University Domain Example – Relational SkeletonUniversity Domain Example – The Completion Instance IUniversity Domain Example – Another Relational SkeletonSlide 19More PRM SemanticsDefinition of PRMsDefinition of PRMs Cont’dPRM Dependency Structure for the University DomainDependency Structure in PRMsAggregation in PRMsPRM Dependency StructureParameters of PRMsCPDs in PRMsParameters of PRMs ContinuedSlide 30Class Dependency Graph for the University DomainEnsuring Acyclic DependenciesPRM for the Genetics DomainDependency Graph for Genetics DomainLearning PRMs: Parameter EstimationSlide 36Learning PRMs: Structure LearningLearning PRMs: Structure Learning ContinuedSlide 39Slide 40Slide 41Slide 42Slide 43Experimental ResultsExperimental Results ContinuedSlide 46Slide 47Slide 48Slide 49DiscussionSlide 51Slide 52Learning Probabilistic Relational ModelsLise Getoor1, Nir Friedman2, Daphne Koller1, and Avi Pfeffer31Stanford University, 2Hebrew University, 3Harvard UniversityOverview•Motivation•Definitions and semantics of probabilistic relational models (PRMs)•Learning PRMs from data–Parameter estimation–Structure learning•Experimental resultsMotivation•Most real-world data are stored in relational DBMS•Few learning algorithms are capable of handling data in its relational form; thus we have to resort to “flattening” the data in order to do analysis•As a result, we lose relational information which might be crucial to understanding the dataRelated Work•Most inductive logic programming (ILP) approaches are deterministic classification approaches, i.e. they do not attempt to model a probability distribution but rather learn a set of rules for classifying when a particular predicate holds•Recent developments in ILP related to PRMs:–Stochastic logic programs (SLPs) [Muggleton, 1996 and Cussens, 1999] –Bayesian logic programs (BLPs) [Kersting et al., 2000]What are PRMs?•The starting point of this work is the structured representation of probabilistic models of Bayesian networks (BNs). BNs for a given domain involves a pre-specified set of attributes whose relationship to each other is fixed in advance•PRMs conceptually extend BNs to allow the specification of a probability model for classes of objects rather than a fixed set of simple attributes•PRMs also allow properties of an entity to depend probabilistically on properties of other related entitiesMapping PRMs from Relational Models•The representation of PRMs is a direct mapping from that of relational databases•A relational model consists of a set of classes X1,…,Xn and a set of relations R1,…,Rm, where each relation Ri is typed•Each class or entity type (corresponding to a single relational table) is associated with a set of attributes A(Xi) and a set of reference slots R (X)PRM Semantics•Reference slots correspond to attributes that are foreign keys (key attributes of another table)•X.ρ, is used to denote reference slot ρ of X. Each reference slot ρ is typed according to the relation that it referencesCourseInstructorRatingDifficultyNameRegistrationCourseStudentGradeSatisfactionRegIDStudentIntelligenceRankingNameUniversity Domain Example - Relational SchemaProfessorPopularityTeaching-AbilityNamePrimarykeys are indicated by a blue rectangle Underlinedattributes arereferenceslots of the classDashed linesindicate the types of objects referencedMMM1M1Indicatesmany-to-manyrelationshipIndicatesone-to-manyrelationshipPRM Semantics Continued•Each attribute Aj  A(Xi) takes on values in some fixed domain of possible values denoted V(Aj). We assume that value spaces are finite•Attribute A of class X is denoted X.A•For example, the Student class has an Intelligence attribute and the value space or domain for Student.Intelligence might be {high, low}PRM Semantics Continued•An instance I of a schema specifies a set of objects x, partitioned into classes; such that there is a value for each attribute x.A and a value for each reference slot x.ρ•A(x) is used as a shorthand for A(X), where x is of class X. For each object x in the instance and each of its attributes A, we use Ix.A to denote the value of x.A in IUniversity Domain Example – An Instance of the SchemaOneprofessoris the instructor for both coursesJane Doe is registered for only one course, Phil101, while the other student is registered for both coursesRegistrationRegID #5639Grade ASatisfaction 3RegistrationRegID #5639Grade ASatisfaction 3CourseName Phil101Difficulty lowRating highStudentName Jane DoeIntelligence highRanking averageProfessorName Prof. GumpPopularity highTeaching-Ability mediumStudentName Jane DoeIntelligence highRanking averageRegistrationRegID #5639Grade ASatisfaction 3CourseName Phil101Difficulty lowRating highUniversity Domain Example – Another Instance of the SchemaThere are twoprofessorsinstructing a courseThere are three students in the Phil201 courseRegistrationRegID #5639Grade ASatisfaction 3RegistrationRegID #5639Grade ASatisfaction 3StudentName Jane DoeIntelligence highRanking averageProfessorName Prof. GumpPopularity highTeaching-Ability mediumStudentName Jane DoeIntelligence highRanking averageRegistrationRegID #5723Grade ASatisfaction 3CourseName Phil201Difficulty lowRating highProfessorName Prof. VincentPopularity highTeaching-Ability highStudentName John DoeIntelligence highRanking averagePRM Semantics Continued•Some attributes, such as name or social security number, are fully determined. Such attributes are labeled as fixed. Assume that they are known in any instantiation of the schema•The other attributes are called probabilisticCourseInstructorRatingDifficultyNameRegistrationCourseStudentGradeSatisfactionRegIDStudentIntelligenceRankingNameUniversity Domain Example - Relational SchemaProfessorPopularityTeaching-AbilityNameFixedattributesare shown in regular fontFixed attributes are shown in regular fontProbabilisticattributesare shown in