pres1.pdfOutlineOur GoalExample: A simple domainExample: A simple domainExample: A simple domainOur GoalDefining the SchemaContinuing the example...InstantiationsSlot chainsProbabilities, finallyPartial InstantiationsLocality of InfluenceConditional independenceAn exampleCompiling into a BNPRMAggregatesAggregatesExample: AggregatesExtensionsAcknowledgementsResourcesIntro to Probabilistic RelationalModelsJames Lenfestey, with Tom Temple and Ethan HoweIntro to Probabilistic Relational Models – p.1/24OutlineMotivate problemDefine PRMsExtensions and future workIntro to Probabilistic Relational Models – p.2/24Our GoalObservation: the world consists of many distinctentities with similar behaviorsExploit this redundancy to make our models simplerThis was the idea of FOL: use quantification toeliminate redundant sentences over ground literalsIntro to Probabilistic Relational Models – p.3/24Example: A simple domaina set of students, S = {s1,s2,s3}a set of professors, P = {p1, p2, p3}Well-Funded,Famous: P → {true, false}Student-Of: S × P → {true, false}Successful: S → {true, false}Intro to Probabilistic Relational Models – p.4/24Example: A simple domainWe can express a certain self-evident fact in onesentence of FOL:∀s ∈ S ∀p ∈ PFamous(p) andStudent-Of(s, p)⇒Successful(s)Intro to Probabilistic Relational Models – p.5/24Example: A simple domainThe same sentence converted to propositional logic:(¬(p1_famous and student_of_s1_p1) or s1_successful) and(¬(p1_famous and student_of_s2_p1) or s2_successful) and(¬(p1_famous and student_of_s3_p1) or s3_successful) and(¬(p2_famous and student_of_s1_p1) or s1_successful) and(¬(p2_famous and student_of_s2_p1) or s2_successful) and(¬(p2_famous and student_of_s3_p1) or s3_successful) and(¬(p3_famous and student_of_s1_p1) or s1_successful) and(¬(p3_famous and student_of_s2_p1) or s2_successful) and(¬(p3_famous and student_of_s3_p1) or s3_successful)Intro to Probabilistic Relational Models – p.6/24Our GoalUnfortunately, the real world is not so clear-cutNeed a probabilistic version of FOLProposal: PRMsPropositionalLogicFirst-orderLogicBayesNetsPRMsIntro to Probabilistic Relational Models – p.7/24Defining the SchemaThe world consists of base entities, partitioned intoclasses X1,X2,...,XnElements of these classes share connections via acollection of relations R1,R2,...,RmEach entity type is characterized by a set ofattributes, A(Xi). Each attribute Aj∈ A (Xi)assumes values from a fixed domain, V(Aj)Defines the schema of a relational modelIntro to Probabilistic Relational Models – p.8/24Continuing the example...We can modify the domain previously given to this newframework:2 classes: S ,P1 relation:Student-Of⊂ S × PA (S ) = {Success}A (P ) = {Well-Funded,Famous}Intro to Probabilistic Relational Models – p.9/24InstantiationsAn instantiation I of the relational schema definesa set of base entities OI(Xi) for each class XiOI0(P ) = {p1, p2, p3}, OI0(S ) = {s1,s2,s3}Intro to Probabilistic Relational Models – p.10/24InstantiationsAn instantiation I of the relational schema definesa set of base entities OI(Xi) for each class XiOI0(P ) = {p1, p2, p3}, OI0(S ) = {s1,s2,s3}Ri(X1,...,Xk) ⊂ OI(X1) × ...× OI(Xk) for each RiStudent-Of= {( s1, p1),(s2, p3),(s3, p3)}Intro to Probabilistic Relational Models – p.10/24InstantiationsAn instantiation I of the relational schema definesa set of base entities OI(Xi) for each class XiOI0(P ) = {p1, p2, p3}, OI0(S ) = {s1,s2,s3}Ri(X1,...,Xk) ⊂ OI(X1) × ...× OI(Xk) for each RiStudent-Of= {( s1, p1),(s2, p3),(s3, p3)}values for the attributes of each base entity for eachclassp1.Famous= false,p3.Well-Funded= true,s2.Success= true,...Intro to Probabilistic Relational Models – p.10/24Slot chainsWe can project any relation R(X1,...,Xk) onto its ith andjth components to obtain a binary relation ρ(Xi,Xj)Notation: for x ∈ OI(Xi), letx.ρ = {y ∈ OI(Xj)|(x,y) ∈ ρ(Xi,Xj)}We call ρ a slot of Xi. Composition of slots (via transitiveclosure) gives a slot chainE.g. x1.Student-Of.Famousis the fame of x1’s adviserIntro to Probabilistic Relational Models – p.11/24Probabilities, finallyThe idea of a PRM is to express a joint probabilitydistribution over all possible instantiations of aparticular relational schemaSince there are infinitely many possibleinstantiations to a given schema, specifying the fulljoint distribution would be very painfulInstead, compute marginal probabilities overremaining variables given a partial instantiationIntro to Probabilistic Relational Models – p.12/24Partial InstantiationsA partial instantiation I0specifiesthe sets OI0(Xi)OI0(P ) = {p1, p2, p3}, OI0(S ) = {s1,s2,s3}Intro to Probabilistic Relational Models – p.13/24Partial InstantiationsA partial instantiation I0specifiesthe sets OI0(Xi)OI0(P ) = {p1, p2, p3}, OI0(S ) = {s1,s2,s3}the relations RjStudent-Of= {( s1, p1),(s2, p3),(s3, p3)}Intro to Probabilistic Relational Models – p.13/24Partial InstantiationsA partial instantiation I0specifiesthe sets OI0(Xi)OI0(P ) = {p1, p2, p3}, OI0(S ) = {s1,s2,s3}the relations RjStudent-Of= {( s1, p1),(s2, p3),(s3, p3)}values of some attributes for some of the baseentitiesp3.Famous= true, s1.Success= falseIntro to Probabilistic Relational Models – p.13/24Locality of InfluenceBNs and PRMs are alike in that they both assumethat real-world data exhibits locality of influence, theidea that most variables are influenced by only a fewothersBoth models exploit this property throughconditional independencePRMs go beyond BNs by assuming that there arefew distinct patterns of influence in totalIntro to Probabilistic Relational Models – p.14/24Conditional independenceFor a class X, values of the attribute X.A areinfluenced by attributes in the set Pa(X.A) (itsparents)Pa(X.A) contains attributes of the form X.B (B anattribute) or X.τ.B (τ a slot chain)As in a BN, the value of X.A is conditionallyindependent of the values of all other attributes,given its parentsIntro to Probabilistic Relational Models – p.15/24An exampleStudentProfessorWell-FundedFamousStudent-OfSuccessfulCaptures the FOL sentence from before in a probabilisticframework.Intro to Probabilistic Relational Models – p.16/24Compiling into a BNA PRM can be compiled into a BN, just as a statement inFOL can be compiled to a statement in
View Full Document