Pedro Domingos

Statistical Relational Learning: 

Statistical Relational Learning Pedro Domingos Dept. of Computer Science & Eng. University of Washington

Overview: 

Overview Motivation Background Representation Inference Learning Software Applications Discussion

The Real World Is ComplexAnd Uncertain: 

The Real World Is Complex And Uncertain Information overload Incomplete information Contradictory information Many sources and modalities Rapid change How can computer systems handle these?

Probability Handles Uncertainty: 

Probability Handles Uncertainty Sensor noise Human error Inconsistencies Unpredictability

First-Order Logic Handles Complexity: 

First-Order Logic Handles Complexity Many types of entities Relations between them Non-independent samples Arbitrary knowledge

Statistical Relational Learning Combines the Two: 

Statistical Relational Learning Combines the Two Unified representation Solid formal foundations Inference algorithms Most probable explanations Probabilities of causes and events Learning algorithms Structure Parameters

Overview: 

Overview Motivation Background Representation Inference Learning Software Applications Discussion

Markov Networks: 

Markov Networks Undirected graphical models Cancer Cough Asthma Smoking Potential functions defined over cliques

Markov Networks: 

Markov Networks Undirected graphical models Log-linear model: Weight of Feature i Feature i Cancer Cough Asthma Smoking

First-Order Logic: 

First-Order Logic Constants, variables, functions, predicates E.g.: Anna, X, mother_of(X), friends(X, Y) Grounding: Replace all variables by constants E.g.: friends (Anna, Bob) World (model, interpretation): Assignment of truth values to all ground predicates

Example: Friends & Smokers: 

Example: Friends & Smokers

Example: Friends & Smokers: 

Example: Friends & Smokers

Overview: 

Overview Motivation Background Representation Inference Learning Software Applications Discussion

Representations: 

Representations

Markov Logic: 

Markov Logic Most developed approach to date Many other approaches can be viewed as special cases Used in rest of this talk

Markov Logic: Intuition: 

Markov Logic: Intuition A logical KB is a set of hard constraints on the set of possible worlds Let’s make them soft constraints: When a world violates a formula, It becomes less probable, not impossible Give each formula a weight (Higher weight  Stronger constraint)

Markov Logic: Definition: 

Markov Logic: Definition A Markov Logic Network (MLN) is a set of pairs (F, w) where F is a formula in first-order logic w is a real number Together with a set of constants, it defines a Markov network with One node for each grounding of each predicate in the MLN One feature for each grounding of each formula F in the MLN, with the corresponding weight w

Example: Friends & Smokers: 

Example: Friends & Smokers

Example: Friends & Smokers: 

Example: Friends & Smokers Two constants: Anna (A) and Bob (B)

Example: Friends & Smokers: 

Example: Friends & Smokers Cancer(A) Smokes(A) Smokes(B) Cancer(B) Two constants: Anna (A) and Bob (B)

Example: Friends & Smokers: 

Example: Friends & Smokers Cancer(A) Smokes(A) Friends(A,A) Friends(B,A) Smokes(B) Friends(A,B) Cancer(B) Friends(B,B) Two constants: Anna (A) and Bob (B)

Example: Friends & Smokers: 

Example: Friends & Smokers Cancer(A) Smokes(A) Friends(A,A) Friends(B,A) Smokes(B) Friends(A,B) Cancer(B) Friends(B,B) Two constants: Anna (A) and Bob (B)

Example: Friends & Smokers: 

Example: Friends & Smokers Cancer(A) Smokes(A) Friends(A,A) Friends(B,A) Smokes(B) Friends(A,B) Cancer(B) Friends(B,B) Two constants: Anna (A) and Bob (B)

Markov Logic Networks: 

Markov Logic Networks MLN is template for ground Markov nets Probability of a world x: Typed variables and constants greatly reduce size of ground Markov net Functions, existential quantifiers, etc. Infinite and continuous domains Weight of formula i No. of true groundings of formula i in x

Relation to Statistical Models: 

Relation to Statistical Models Special cases: Markov networks Markov random fields Bayesian networks Log-linear models Exponential models Max. entropy models Gibbs distributions Boltzmann machines Logistic regression Hidden Markov models Conditional random fields Obtained by making all predicates zero-arity Markov logic allows objects to be interdependent (non-i.i.d.)

Relation to First-Order Logic: 

Relation to First-Order Logic Infinite weights  First-order logic Satisfiable KB, positive weights  Satisfying assignments = Modes of distribution Markov logic allows contradictions between formulas

Overview: 

Overview Motivation Background Representation Inference Learning Software Applications Discussion

Inferring the Most Probable Explanation: 

Inferring the Most Probable Explanation Problem: Find most likely state of world given evidence Query Evidence

Inferring the Most Probable Explanation: 

Inferring the Most Probable Explanation Problem: Find most likely state of world given evidence

Inferring the Most Probable Explanation: 

Inferring the Most Probable Explanation Problem: Find most likely state of world given evidence

Inferring the Most Probable Explanation: 

Inferring the Most Probable Explanation Problem: Find most likely state of world given evidence This is just the weighted MaxSAT problem Use weighted SAT solver (e.g., MaxWalkSAT [Kautz et al., 1997] ) Potentially faster than logical inference (!)

The WalkSAT Algorithm: 

The WalkSAT Algorithm for i ← 1 to max-tries do solution = random truth assignment for j ← 1 to max-flips do if all clauses satisfied then return solution c ← random unsatisfied clause with probability p flip a random variable in c else flip variable in c that maximizes number of satisfied clauses return failure

The MaxWalkSAT Algorithm: 

The MaxWalkSAT Algorithm for i ← 1 to max-tries do solution = random truth assignment for j ← 1 to max-flips do if ∑ weights(sat. clauses) > threshold then return solution c ← random unsatisfied clause with probability p flip a random variable in c else flip variable in c that maximizes ∑ weights(sat. clauses) return failure, best solution found

But … Memory Explosion: 

But … Memory Explosion Problem: If there are n constants and the highest clause arity is c, the ground network requires O(n ) memory Solution: Exploit sparseness; ground clauses lazily → LazySAT algorithm [Singla & Domingos, 2006] c

Computing Probabilities: 

Computing Probabilities P(Formula|MLN,C) = ? MCMC: Sample worlds, check formula holds P(Formula1|Formula2,MLN,C) = ? If Formula2 = Conjunction of ground atoms First construct min subset of network necessary to answer query (generalization of KBMC) Then apply MCMC (or other) Can also do lifted inference [Braz et al, 2005]

MCMC: Gibbs Sampling: 

MCMC: Gibbs Sampling state ← random truth assignment for i ← 1 to num-samples do for each variable x sample x according to P(x|neighbors(x)) state ← state with new value of x P(F) ← fraction of states in which F is true

But … Insufficient for Logic: 

But … Insufficient for Logic Problem: Deterministic dependencies break MCMC Near-deterministic ones make it very slow Solution: Combine MCMC and WalkSAT → MC-SAT algorithm [Poon & Domingos, 2006]

Overview: 

Overview Motivation Background Representation Inference Learning Software Applications Discussion

Learning: 

Learning Data is a relational database Closed world assumption (if not: EM) Learning parameters (weights) Generatively Discriminatively Learning structure (formulas)

Generative Weight Learning: 

Generative Weight Learning Maximize likelihood Use gradient ascent or L-BFGS No local maxima Requires inference at each step (slow!) No. of true groundings of clause i in data Expected no. true groundings according to model

Pseudo-Likelihood: 

Pseudo-Likelihood Likelihood of each variable given its neighbors in the data Does not require inference at each step Consistent estimator Widely used in vision, spatial statistics, etc. But PL parameters may not work well for long inference chains

Discriminative Weight Learning: 

Discriminative Weight Learning Maximize conditional likelihood of query (y) given evidence (x) Expected counts ≈ Counts in most prob. state of y given x, found by MaxWalkSAT No. of true groundings of clause i in data Expected no. true groundings according to model

Structure Learning: 

Structure Learning Generalizes feature induction in Markov nets Any inductive logic programming approach can be used, but . . . Goal is to induce any clauses, not just Horn Evaluation function should be likelihood Requires learning weights for each candidate Turns out not to be bottleneck Bottleneck is counting clause groundings Solution: Subsampling

Structure Learning: 

Structure Learning Initial state: Unit clauses or hand-coded KB Operators: Add/remove literal, flip sign Evaluation function: Pseudo-likelihood + Structure prior Search: Beam search, shortest-first search

Overview: 

Overview Motivation Background Representation Inference Learning Software Applications Discussion

Alchemy: 

Alchemy Open-source software including: Full first-order logic syntax Generative & discriminative weight learning Structure learning Weighted satisfiability and MCMC Programming language features www.cs.washington.edu/ai/alchemy

Overview: 

Overview Motivation Background Representation Inference Learning Software Applications Discussion

Applications: 

Applications Information extraction Entity resolution Link prediction Collective classification Web mining Natural language processing Computational biology Social network analysis Robot mapping Activity recognition Probabilistic Cyc CALO Etc.

Information Extraction: 

Information Extraction Parag Singla and Pedro Domingos, “Memory-Efficient Inference in Relational Domains” (AAAI-06). Singla, P., & Domingos, P. (2006). Memory-efficent inference in relatonal domains. In Proceedings of the Twenty-First National Conference on Artificial Intelligence (pp. 500-505). Boston, MA: AAAI Press. H. Poon & P. Domingos, Sound and Efficient Inference with Probabilistic and Deterministic Dependencies”, in Proc. AAAI-06, Boston, MA, 2006. P. Hoifung (2006). Efficent inference. In Proceedings of the Twenty-First National Conference on Artificial Intelligence.

Segmentation: 

Segmentation Parag Singla and Pedro Domingos, “Memory-Efficient Inference in Relational Domains” (AAAI-06). Singla, P., & Domingos, P. (2006). Memory-efficent inference in relatonal domains. In Proceedings of the Twenty-First National Conference on Artificial Intelligence (pp. 500-505). Boston, MA: AAAI Press. H. Poon & P. Domingos, Sound and Efficient Inference with Probabilistic and Deterministic Dependencies”, in Proc. AAAI-06, Boston, MA, 2006. P. Hoifung (2006). Efficent inference. In Proceedings of the Twenty-First National Conference on Artificial Intelligence. Author Title Venue

Entity Resolution: 

Entity Resolution Parag Singla and Pedro Domingos, “Memory-Efficient Inference in Relational Domains” (AAAI-06). Singla, P., & Domingos, P. (2006). Memory-efficent inference in relatonal domains. In Proceedings of the Twenty-First National Conference on Artificial Intelligence (pp. 500-505). Boston, MA: AAAI Press. H. Poon & P. Domingos, Sound and Efficient Inference with Probabilistic and Deterministic Dependencies”, in Proc. AAAI-06, Boston, MA, 2006. P. Hoifung (2006). Efficent inference. In Proceedings of the Twenty-First National Conference on Artificial Intelligence.

Entity Resolution: 

Entity Resolution Parag Singla and Pedro Domingos, “Memory-Efficient Inference in Relational Domains” (AAAI-06). Singla, P., & Domingos, P. (2006). Memory-efficent inference in relatonal domains. In Proceedings of the Twenty-First National Conference on Artificial Intelligence (pp. 500-505). Boston, MA: AAAI Press. H. Poon & P. Domingos, Sound and Efficient Inference with Probabilistic and Deterministic Dependencies”, in Proc. AAAI-06, Boston, MA, 2006. P. Hoifung (2006). Efficent inference. In Proceedings of the Twenty-First National Conference on Artificial Intelligence.

State of the Art: 

State of the Art Segmentation HMM (or CRF) to assign each token to a field Entity resolution Logistic regression to predict same field/citation Transitive closure Alchemy implementation: Seven formulas

Types and Predicates: 

Types and Predicates token = {Parag, Singla, and, Pedro, ...} field = {Author, Title, Venue} citation = {C1, C2, ...} position = {0, 1, 2, ...} Token(token, position, citation) InField(position, field, citation) SameField(field, citation, citation) SameCit(citation, citation)

Types and Predicates: 

Types and Predicates token = {Parag, Singla, and, Pedro, ...} field = {Author, Title, Venue, ...} citation = {C1, C2, ...} position = {0, 1, 2, ...} Token(token, position, citation) InField(position, field, citation) SameField(field, citation, citation) SameCit(citation, citation) Optional

Types and Predicates: 

Types and Predicates Evidence token = {Parag, Singla, and, Pedro, ...} field = {Author, Title, Venue} citation = {C1, C2, ...} position = {0, 1, 2, ...} Token(token, position, citation) InField(position, field, citation) SameField(field, citation, citation) SameCit(citation, citation)

Types and Predicates: 

token = {Parag, Singla, and, Pedro, ...} field = {Author, Title, Venue} citation = {C1, C2, ...} position = {0, 1, 2, ...} Token(token, position, citation) InField(position, field, citation) SameField(field, citation, citation) SameCit(citation, citation) Types and Predicates Query

Formulas: 

Token(+t,i,c) => InField(i,+f,c) InField(i,+f,c) <=> InField(i+1,+f,c) f != f’ => (!InField(i,+f,c) v !InField(i,+f’,c)) Token(+t,i,c) ^ InField(i,+f,c) ^ Token(+t,i’,c’) ^ InField(i’,+f,c’) => SameField(+f,c,c’) SameField(+f,c,c’) <=> SameCit(c,c’) SameField(f,c,c’) ^ SameField(f,c’,c”) => SameField(f,c,c”) SameCit(c,c’) ^ SameCit(c’,c”) => SameCit(c,c”) Formulas

Formulas: 

Formulas Token(+t,i,c) => InField(i,+f,c) InField(i,+f,c) <=> InField(i+1,+f,c) f != f’ => (!InField(i,+f,c) v !InField(i,+f’,c)) Token(+t,i,c) ^ InField(i,+f,c) ^ Token(+t,i’,c’) ^ InField(i’,+f,c’) => SameField(+f,c,c’) SameField(+f,c,c’) <=> SameCit(c,c’) SameField(f,c,c’) ^ SameField(f,c’,c”) => SameField(f,c,c”) SameCit(c,c’) ^ SameCit(c’,c”) => SameCit(c,c”)

Formulas: 

Formulas Token(+t,i,c) => InField(i,+f,c) InField(i,+f,c) <=> InField(i+1,+f,c) f != f’ => (!InField(i,+f,c) v !InField(i,+f’,c)) Token(+t,i,c) ^ InField(i,+f,c) ^ Token(+t,i’,c’) ^ InField(i’,+f,c’) => SameField(+f,c,c’) SameField(+f,c,c’) <=> SameCit(c,c’) SameField(f,c,c’) ^ SameField(f,c’,c”) => SameField(f,c,c”) SameCit(c,c’) ^ SameCit(c’,c”) => SameCit(c,c”)

Formulas: 

Formulas Token(+t,i,c) => InField(i,+f,c) InField(i,+f,c) <=> InField(i+1,+f,c) f != f’ => (!InField(i,+f,c) v !InField(i,+f’,c)) Token(+t,i,c) ^ InField(i,+f,c) ^ Token(+t,i’,c’) ^ InField(i’,+f,c’) => SameField(+f,c,c’) SameField(+f,c,c’) <=> SameCit(c,c’) SameField(f,c,c’) ^ SameField(f,c’,c”) => SameField(f,c,c”) SameCit(c,c’) ^ SameCit(c’,c”) => SameCit(c,c”)

Formulas: 

Token(+t,i,c) => InField(i,+f,c) InField(i,+f,c) <=> InField(i+1,+f,c) f != f’ => (!InField(i,+f,c) v !InField(i,+f’,c)) Token(+t,i,c) ^ InField(i,+f,c) ^ Token(+t,i’,c’) ^ InField(i’,+f,c’) => SameField(+f,c,c’) SameField(+f,c,c’) <=> SameCit(c,c’) SameField(f,c,c’) ^ SameField(f,c’,c”) => SameField(f,c,c”) SameCit(c,c’) ^ SameCit(c’,c”) => SameCit(c,c”) Formulas

Formulas: 

Token(+t,i,c) => InField(i,+f,c) InField(i,+f,c) <=> InField(i+1,+f,c) f != f’ => (!InField(i,+f,c) v !InField(i,+f’,c)) Token(+t,i,c) ^ InField(i,+f,c) ^ Token(+t,i’,c’) ^ InField(i’,+f,c’) => SameField(+f,c,c’) SameField(+f,c,c’) <=> SameCit(c,c’) SameField(f,c,c’) ^ SameField(f,c’,c”) => SameField(f,c,c”) SameCit(c,c’) ^ SameCit(c’,c”) => SameCit(c,c”) Formulas

Formulas: 

Formulas Token(+t,i,c) => InField(i,+f,c) InField(i,+f,c) <=> InField(i+1,+f,c) f != f’ => (!InField(i,+f,c) v !InField(i,+f’,c)) Token(+t,i,c) ^ InField(i,+f,c) ^ Token(+t,i’,c’) ^ InField(i’,+f,c’) => SameField(+f,c,c’) SameField(+f,c,c’) <=> SameCit(c,c’) SameField(f,c,c’) ^ SameField(f,c’,c”) => SameField(f,c,c”) SameCit(c,c’) ^ SameCit(c’,c”) => SameCit(c,c”)

Formulas: 

Formulas Token(+t,i,c) => InField(i,+f,c) InField(i,+f,c) ^ !Token(“.”,i,c) <=> InField(i+1,+f,c) f != f’ => (!InField(i,+f,c) v !InField(i,+f’,c)) Token(+t,i,c) ^ InField(i,+f,c) ^ Token(+t,i’,c’) ^ InField(i’,+f,c’) => SameField(+f,c,c’) SameField(+f,c,c’) <=> SameCit(c,c’) SameField(f,c,c’) ^ SameField(f,c’,c”) => SameField(f,c,c”) SameCit(c,c’) ^ SameCit(c’,c”) => SameCit(c,c”)

Robot Mapping: 

Robot Mapping Input: Laser range finder segments (xi, yi, xf, yf) Outputs: Segment labels (Wall, Door, Other) Assignment of wall segments to walls Position of walls (xi, yi, xf, yf)

Robot Mapping: 

Robot Mapping

MLNs for Hybrid Domains: 

MLNs for Hybrid Domains Allow numeric properties of objects as nodes E.g.: Length(x), Distance(x,y) Allow numeric terms as features E.g.: –(Length(x) – 5.0)2 (Gaussian distr. w/ mean = 5.0 and variance = 1/(2w)) Allow α = β as shorthand for –(α – β)2 E.g.: Length(x) = 5.0 Etc.

Robot Mapping: 

Robot Mapping SegmentType(s,+t) => Length(s) = Length(+t) SegmentType(s,+t) => Depth(s) = Depth(+t) Neighbors(s,s’) ^ Aligned(s,s’) => (SegType(s,+t) <=> SegType(s’,+t)) !PreviousAligned(s) ^ PartOf(s,l) => StartLine(s,l) StartLine(s,l) => Xi(s) = Xi(l) ^ Yi(s) = Yi(l) PartOf(s,l) => = Etc. Yf(s)-Yi(s) Yi(s)-Yi(l) Xf(s)-Xi(s) Xi(s)-Xi(l)

Overview: 

Overview Motivation Background Representation Inference Learning Software Applications Discussion

Next Steps: 

Next Steps Further improving scalability, robustness and ease of use Online learning and inference Discovering deep structure Generalizing across domains and tasks Relational decision theory Solving larger applications Adversarial settings Etc.

Summary: 

Summary The real world is complex and uncertain First-order logic handles complexity Probability handles uncertainty Statistical relational learning combines the two Markov logic: Most advanced approach to date Alchemy: Complete suite of state-of-the-art algorithms Many challenging applications now within reach We’re at an inflection point in what we can do