Slide 1Take-Away MessageOutlineSlide 4MotivationReal-World Data (Dramatically Simplified)Slide 7Slide 8A (very) Brief HistorySeveral SRL formalisms => Endless Possibilities(Propositional) Logic Program – 1-slide IntroLogic Programming (LP)Model Theoretic ViewProbabilities on Possible worldsProof TheoreticProbabilities on ProofsSlide 17Slide 18First-Order/Relational Logic + Probability = PLMModel-Theoretic ApproachesProbabilistic Relational Models – Getoor et al.Relational SchemaProbabilistic Relational ModelsSlide 24Bayesian Logic Programs (BLPs)Bayesian Logic Programs (BLPs) – Kersting & De RaedtProof theoretic Probabilistic Logic MethodsProbabilistic Proofs -PRISMProbabilistic Proofs -PRISMPRISMProbabilistic Proofs – Stochastic Logic Programs (SLPs)Slide 32Slide 33Slide 34Undirected Probabilistic Logic ModelsMarkov Logic Networks (Richardson & Domingos)Example: Friends & SmokersPlethora of ApproachesMultiple Parents ProblemMultiple Parents for “population”Solution 1: Aggregators – PRM, RDN, PRL etcSolution 2: Combining Rules – BLP, RBN,LBN etcSlide 43LearningParameter EstimationParameter Estimation – Model TheoreticParameter Estimation – Proof TheoreticSlide 48Slide 49Slide 50Sriraam NatarajanIntroduction to Probabilistic Logical ModelsIntroduction to Probabilistic Logical ModelsSlides based on tutorials by Kristian Kersting, James Cussens, Lise Getoor & Pedro DomingosTake-Away Message Learn from rich, highly structured dataProgress to date•Burgeoning research area•“Close enough” to goal•Easy-to-use open-source software available•Lots of Challenges/Problems in the futureIntroductionProbabilistic Logic ModelsDirected vs Undirected ModelsLearningConclusionOutlineIntroductionProbabilistic Logic ModelsDirected vs Undirected ModelsLearningConclusionMotivationMost learners assume i.i.d. data(independent and identically distributed)–One type of object–Objects have no relation to each otherTo predict if the image is “eclipse”Real-World Data (Dramatically Simplified)PatientID Gender Birthdate P1 M 3/22/63 PatientID Date Physician Symptoms Diagnosis P1 1/1/01 Smith palpitations hypoglycemic P1 2/1/03 Jones fever, aches influenzaPatientID Date Lab Test Result P1 1/1/01 blood glucose 42 P1 1/9/01 blood glucose 45PatientID SNP1 SNP2 … SNP500K P1 AA AB BB P2 AB BB AAPatientID Date Prescribed Date Filled Physician Medication Dose Duration P1 5/17/98 5/18/98 Jones prilosec 10mg 3 monthsNon- i.i.dMulti-RelationalSolution: First-Order Logic / Relational DatabasesShared ParametersThe World is inherently UncertainGraphical Models (here e.g. a Bayesian network) - Model uncertainty explicitly by representing the joint distributionFever AcheInfluenzaRandom VariablesDirect InfluencesPropositional Model!Logic + Probability = Probabilistic Logic aka Statistical Relational Learning ModelsLogicProbabilitiesAdd ProbabilitiesAdd RelationsStatistical Relational Learning (SRL)Uncertainty in SRL Models is captured by probabilities, weights or potential functionsA (very) Brief HistoryProbabilistic Logic term coined by Nilsson in 1986Considered the “probabilistic entailment” i.e., the probabilities of all sentences between 0 and 1Earlier work by (Halpern, Bacchus and others) focused on the representation and not learningNiem and Haddawy (1995) – one of the earlier approachesLate 90’s: OOBN, PRM, PRISM, SLP etc‘00- ‘05 : Plethora of approaches (representation)Learning methods (since ‘01)Recent thrust – Inference (Lifted Inference techniques)Several SRL formalisms => Endless PossibilitiesWeb data (web)Biological data (bio) Social Network Analysis (soc)Bibliographic data (cite)Epidimiological data (epi)Communication data (comm)Customer networks (cust)Collaborative filtering problems (cf)Trust networks (trust)Reinforcement LearningNatural Language ProcessingSAT…(Propositional) Logic Program – 1-slide IntroClauses: IF burglary and earthquake are true THEN alarm is trueburglary.earthquake.alarm :- burglary, earthquake.marycalls :- alarm.johncalls :- alarm.Herbrand Base (HB) = all atoms in the program burglary, earthquake, alarm, marycalls, johncallsProgramatombodyheadLogic Programming (LP)2 views:1) Model-Theoretic2) Proof-TheoreticModel Theoretic ViewLogic Program restricts the set of possible worldsFive propositions – Herbrand baseSpecifies the set of possible worlds An interpretation is a model of a clause C  If the body of C holds then the head holds, too.burglary.earthquake.alarm :- burglary, earthquake.marycalls :- alarm.johncalls :- alarm.burglaryearthquakealarmmarycalls johncalls truefalsetruefalsetruefalsetruefalsetruefalseProbabilities on Possible worldsSpecifies a joint distribution P(X1,…,Xn) over a fixed, finite set {X1,…,Xn}Each random variable takes a value from respective domainDefines a probability distribution over all possible interpretationsburglaryearthquakealarmmarycalls johncalls truefalsetruefalsetruefalsetruefalsetruefalseProof Theoreticburglary.earthquake.alarm :- burglary, earthquake.marycalls :- alarm.johncalls :- alarm.:- alarm.:- burglary, earthquake.:- earthquake.{}A logic program can be used to prove some goals that are entailed by programGoal :- johncallsProbabilities on ProofsStochastic grammarsEach time a rule is applied in a proof, the probability of the rule is multiplied with the overall probabilityUseful in NLP – most likely parse tree or the total probability that a particular sentence is derivedUse SLD trees for resolution1.0 : S  NP, VP 1/3 : NP  i 1/3 : NP  Det, N 1/3 : NP  NP, PP....Full Clausal LogicFull Clausal LogicRelational Clausal LogicRelational Clausal Logic Propositional Clausal LogicIntroductionProbabilistic Logic ModelsDirected vs Undirected ModelsLearningConclusionFirst-Order/Relational Logic + Probability = PLMModel-Theoretic vs. Proof-TheoreticDirected vs. UndirectedAggregators vs. Combining RulesModel-Theoretic ApproachesProbabilistic Relational Models – Getoor et al.Combine advantages of relational logic & Bayesian networks: –natural domain modeling: objects, properties,