Folien - Übersicht

Reasoning and Decision-Making
under Uncertainty
13. Session:
Markov Logic (Networks) & Summary
Prof. Dr.-Ing. Stefan Kopp
Center of Excellence „Cognitive Interaction Technology“
AG Sociable Agents
Sociable gents
Markov Logic!
[Richardson & Domingos, 2006]
Originated from Natural Language Processing
Natural language is characterized by
‣ Complex relational structure
‣ High uncertainty (ambiguity, imperfect knowledge)
First-order logic handles relational structure, probability handles
uncertainty
‣ Let’s combine the two
‣ more powerful than PRMs
2
Sociable gents
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
Sociable gents
Markov Logic
Syntax:
‣ First-order logic + Weights
Semantics:
‣ Templates for Markov/Bayesian networks
Inference:
‣ Weighted satisfiability + MCMC
[ Learning: ]
‣ Inductive Logic Programming (IPL)
4
Sociable gents
Markov Networks
Undirected graphical models
B
A
with a different form of
factorization


C
D
Potential functions defined over all cliques C
Markov Network = product of potentials on variables

Z: Partition function
Sociable gents
Markov Logic Networks

Alternative factorization for a set of weighted binary features
(simplified version of Boltzmann machine):
Weight of Feature i Feature i
Sociable gents
Markov Logic Networks
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)
Sociable gents
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
Sociable gents
Markov Logic Networks
MLN is template for ground Markov nets
Probability of a world
x:
Weight of formula i
No. of true groundings of formula i in x
Sociable gents
Example: Friends & Smokers
Suppose we have two constants: Anna (A) and Bob (B)
Smokes(A)
Cancer(A)
Smokes(B)
Cancer(B)
Sociable gents
Example: Friends & Smokers
Suppose we have two constants: Anna (A) and Bob (B)
Friends(A,B)
Friends(A,A)
Smokes(A)
Cancer(A)
Smokes(B)
Friends(B,A)
Friends(B,B)
Cancer(B)
Sociable gents
Example: Friends & Smokers
Suppose we have two constants: Anna (A) and Bob (B)
Friends(A,B)
Friends(A,A)
Smokes(A)
Cancer(A)
Smokes(B)
Friends(B,A)
Friends(B,B)
Cancer(B)
Sociable gents
Example: Friends & Smokers
Suppose we have two constants: Anna (A) and Bob (B)
Friends(A,B)
Friends(A,A)
Smokes(A)
Cancer(A)
Smokes(B)
Friends(B,A)
Friends(B,B)
Cancer(B)
Sociable gents
More on MLNs
Markov Logic Network
‣ is template for ground Markov nets
‣ Typed variables and constants greatly reduce size of ground
Markov net
‣ Functions, existential quantifiers, etc.
‣ MLN without variables = Markov network
(subsumes graphical models)
Relation to First-order logic:
‣ Infinite weights ➔ First-order logic
‣ Satisfiable KB, positive weights ➔ Satisfying assignments = Modes of
distribution
‣ MLNs allow contradictions between formulas
Sociable gents
Inference: MPE/MAP
Goal: Find most likely truth values of non-evidence ground atoms given
evidence
Idea: Apply weighted satisfiability solver (max‘es sum of weights of
satisfied clauses)
MaxWalkSat algorithm [Kautz et al., 1997]
‣ Start with random truth assignment
‣ With prob p, flip atom that max‘es weight sum;
else flip random atom in unsatisfied clause
‣ Repeat n times
‣ Restart m times
Sociable gents
Conditional Inference
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
-
-
Initialize Markov net to contain all query preconditions
For each node in network
‣ Add node’s Markov blanket to network
‣ Remove any evidence nodes
Repeat until done
‣ Then apply MCMC, Gibbs sampling, or other
Sociable gents
Relation to Other Approaches
Representation
Logical language
Probabilistic
language
Markov logic
First-order logic
Markov nets
RMNs (relational
markov network)
Conjunctive queries Markov nets
PRMs (prob. relational
model)
Frame systems
Bayes nets
KBMC (know.-based
model construction)
Horn clauses
Bayes nets
SLPs (stochastic logic
programs)
Horn clauses
Bayes nets
Sociable gents
Available tools
‣ ProbCog (TU München)
-
http://ias.cs.tum.edu/research/probcog
‣ Tuffy (U Wisconsin-Madison)
-
http://research.cs.wisc.edu/hazy/tuffy/
‣ Alchemy (U Washington)
-
http://alchemy.cs.washington.edu/
See also: http://en.wikipedia.org/wiki/Markov_logic_network
18
Sociable gents
Example: tuffy
19
Sociable gents
Example: tuffy
MAP inference: produce a most likely world
‣ suppose you want to find the most likely set of people with
cancer
Marginal inference
‣ estimate the probability that each person has cancer
20
Sociable gents
Example: ProbCog (M. Beetz)
21
Sociable gents
Work with us!
Research in the CITEC Sociable
Agents Group applies advanced A.I.
methods and cognitive models to
increase interaction abilities of
technical systems
Many sources of uncertainty:
‣ complex communication system (language, nonverbal behavior)
‣ vague and underspecified meanings, implicit communication, etc.
‣ user-based inferences: intentions, beliefs, skills, mood, etc.
‣ predictability problems, learning problems
‣ architectural complexity of complete systems
22
Sociable gents
http://www.techfak.uni-bielefeld.de/ags/soa/theses/open-topics.html
23
Sociable gents
Summary of this lecture
Ein idealer rationaler Agent ...
1.
2.
3.
4.
Überlegt nicht bevor er handelt
Maximiert seine Kosten
Verwendet eine externe Repräsentation
Handelt um seine Ziele möglichst schnell zu erreichen
24
Sociable gents
Summary of this lecture
Klassisches logisches Schließen ist
1.
2.
3.
4.
Nicht-monoton, modular und global
Abduktiv, lokal und inferenziell
Modular, lokal und monoton
Super
25
Sociable gents
Summary of this lecture
In klassischen logik-basierten KI-Systemen entsteht Unsicherheit durch
1.
2.
3.
4.
Unvollständiges Wissen und exaktes Schließen
Zweiwertige Semantik und Nicht-Monotonie
das Frame-Problem
Default-Annahmen und Zurücknahme von Schlüssen
26
Sociable gents
Summary of this lecture
Welches Entscheidungsproblem ist das schwerste weil unsicherste?
1.
2.
3.
4.
Single-state problem
Sensorless, conformant problem
Exploration problem
Contingency problem
27
Sociable gents
Summary of this lecture
Der Bayesianische Ansatz, Unsicherheit zu modellieren, interpretiert
Wahrscheinlichkeit als ...
1.
2.
3.
4.
die Häufigkeit, eine Aussage in der Welt erfüllt zu finden
Sicherheit einer möglichen Welt
Subjektiver Grad des Glaubens/Sicherheit bzgl. einer Aussage
Vagheit bzgl. der Erfülltheit einer Aussage
28
Sociable gents
Summary of this lecture
Als „Conditioning“ bezeichnet man
1. das Tuppieren der Haare
2. das Einschränken möglicher Welten
3. das Anpassen einer Wahrscheinlichkeitsverteilung anhand von
Evidenz
4. eine bedingte Wahrscheinlichkeit nach Anwenden der Bayes-Regel
29
Sociable gents
Summary of this lecture
Marginalisierung entsteht aus der Anwendung von
1.
2.
3.
4.
5.
Bayes-Regel
Gesetz der totalen Wahrscheinlichkeit
Kettenregel
Produktregel
Keines von allem
30
Sociable gents
Summary of this lecture
Ein Bayes-Netz repräsentiert formal
1.
2.
3.
4.
kausale Einflüsse zwischen Variablen
im Grunde nur Wahrscheinlichkeitsverteilungen
(Un-)Abhängigkeiten zwischen Zufallsvariablen
einen naiven Klassifikator
31
Sociable gents
Summary of this lecture
Die sogenannte „Markov Blanket“ eines Knotens enthält
1.
2.
3.
4.
Alle Nachbarn
Alle Eltern, Kinder und Kindeskinder
Alle Eltern, Kinder und Kindeseltern
Alle Kinder, Geschwister und deren Kinder
32
Sociable gents
Summary of this lecture
Gegeben alle Elternknoten, ist ein Knoten bedingt unabhängig von
1.
2.
3.
4.
Allen Nachbarn
Allen Nicht-Nachfahren
Allen Nachfahren
Allen Nicht-Nachbarn
33
Sociable gents
Summary of this lecture
In diesem Bayes-Netz gilt: P(c,a,r,b,e) = ...
1.
2.
3.
4.
P(c|a,r,b,e)P(r|a,b,e)P(r|b,e)P(e)P(b)
P(c|a,b)P(a|b,e)P(r|e)P(a)P(e)
P(e)P(r|e)P(c|a)P(a|b,e)P(b)
P(r,a,b,e|c)P(c)P(e)P(a)P(b)
34
Sociable gents
Summary of this lecture
Welche Aussage ist falsch, wenn C, A und R
gegeben sind?
1.
2.
3.
4.
Der Pfad E-A-C ist geblockt.
Der Pfad R-E-A-B ist geblockt.
Der Pfad B-A-C ist geblockt.
Der Pfad A-E-R ist offen.
35
Sociable gents
Summary of this lecture
Das MEU-Prinzip betrifft...
1.
2.
3.
4.
Die Mehrheit der EU-Bürger
Die Auswahl von Aktionen nach gegebenen Utility-Werten
Die Präferenzen bei der Planung von Handlungsfolgen
Kriterien zur Aktionsauswahl nach erwartetem Nutzen
36
Sociable gents
Summary of this lecture
Die Definition eines Markov-Entscheidungsproblems beinhaltet nicht
1. Ein Übergangsmodell
2. Eine Belohnungsfunktion
3. Einen Zielzustand
4. Einen Startzustand
5. Ein Beobachtungsmodell
37
Sociable gents
Summary of this lecture
Maximum Likelihood Estimation ist ein Verfahren, um...
1. Die Struktur von Bayes-Netzen zu lernen
2. Den Wert einer Evidenz abzuschätzen
3. Die Parameter einer bedingten WS-Verteilung zu lernen
4. Fehlende Datenpunkte beim Parameterlernen zu rekonstruieren
38
Sociable gents