Markov Logik
Transcrição
Markov Logik
Markov Logik Matthias Balwierz Seminar: Maschinelles Lernen WS 2009/2010 Prof. Fürnkranz Überblick z z z z z z z Markov Netze Prädikatenlogik erster Stufe Markov Logik Inferenz Lernen Anwendungen Software 18.11.2009 Markov Logik - Matthias Balwierz 2 Markov Netze z z Statistisches Model zur Beschreibung von ungerichteten Zusammenhängen eines Netzwerkes Anwendungen: z z z 18.11.2009 Segmentierung von klassifizierten Flächen Optisches Tracking und Matching Magnetismus in Festkörpern Markov Logik - Matthias Balwierz 3 Markov Netze II z Markov Netz besteht aus: z z z z z z Menge von Variablen X = ( x1 , x 2 ,..., x n ) ∈ ℵ Ein ungerichteter Graph Eine Menge potenzieller Funktionen φk Graph hat einen Knoten pro Variable Ein Modell hat eine potenzielle Funktion pro Clique Eine potenzielle Funktion ist reell und nicht negativ 18.11.2009 Markov Logik - Matthias Balwierz 4 Markov Netze III z Multivariate Verteilung: 1 P( X = x) = ∏ φk ( x{k } ) Z k z Mit der Zustandssumme Z = ∑ x∈ℵ ∏k φk ( x{k } ) z Mit Zustand 18.11.2009 x{k } der k-ten Clique Markov Logik - Matthias Balwierz 5 Markov Netze IV z Lässt sich als log-lineares Modell darstellen ⎛ ⎞ 1 P( X = x) = exp⎜⎜ ∑ w j f j ( x) ⎟⎟ Z ⎝ j ⎠ z z Mit durch w j gewichteten Features f j ( x) ∈ {0,1} Features können Funktionen sein die den Zustand einer Clique beschreiben 18.11.2009 Markov Logik - Matthias Balwierz 6 Prädikatenlogik erster Stufe z z Eine Wissensbasis besteht einer Menge von logischen Formeln Formeln bestehen aus z z z z 18.11.2009 Konstanten aus dem Definitionsbereich (z.B. Anna, Bob, Chris) Variablen Funktionen (Abbildung von Tupel von Objekten auf Objekte z.B. MutterVon) Prädikate (Relationen zwischen zwei Objekten oder Attribute z.B. Freunde oder Raucht) Markov Logik - Matthias Balwierz 7 Prädikatenlogik erster Stufe II z z z z z Variablen und Konstanten können typisiert sein Ein Term ist eine Konstante, Variable oder eine Funktion angewendet auf Unterterme Eine atomare Formel ist ein Prädikat angewendet auf Unterterme Eine Formel ist rekursiv konstruiert aus atomaren Formeln verknüpft mit logischen Symbolen ¬,∧,∨, ⇒, ⇔ und Quantoren ∃x, ∀x Atomare Formeln sind wahr, negierte sind unwahr 18.11.2009 Markov Logik - Matthias Balwierz 8 Prädikatenlogik erster Stufe III z Beispiel z z z Fr(x, y): x und y sind Freunde Sm(x): x ist Raucher Ca(x): x hat Krebs (Richardson et al 2004) z Problem: Nicht jeder Raucher hat Krebs 18.11.2009 Markov Logik - Matthias Balwierz 9 Markov Logik z z z z z Prädikatenlogik hat harte Randbedingungen Eine Welt welche eine Formel verletzt hat die Wahrscheinlichkeit 0 Markov Logik weicht diese Randbedingung auf Eine Welt die eine Formel verletzt ist weniger wahrscheinlich aber nicht unmöglich Die „Härte“ einer Formel wird durch Gewichte ausgedrückt 18.11.2009 Markov Logik - Matthias Balwierz 10 Markov Logik II z z z Definition: Ein MLN L ist eine Menge von Paaren ( Fi , wi ) z Fi ist eine Prädikatenlogische Formel z wi ist ein Gewicht Mit einer endlichen Menge von Konstanten C = {c1 , c2 ,..., c C } ergibt das ein Markov Netz ML,C 18.11.2009 Markov Logik - Matthias Balwierz 11 Markov Logik III Beispiel: Freunde haben gleiches Rauchverhalten ∀x∀yFriends( x, y ) ⇒ ( Smokes( x) ⇔ Smokes( y )) und Rauchen verursacht Krebs ∀xSmokes( x) ⇒ Cancer ( x) mit Konstanten Anna und Bob 18.11.2009 Markov Logik - Matthias Balwierz 12 (De Raedt et al 2008) Markov Logik IV z MLN ist eine Schablone zum Konstruieren von Markov Netzen mit der Wahrscheinlichkeitsverteilung: 1 ⎞ ⎛ F P( X = x) = exp⎜ ∑ wi ni ( x) ⎟ Z ⎠ ⎝ i z F ist die Anzahl der Formeln und ni ist die Anzahl der wahren Groundings von Fi 18.11.2009 Markov Logik - Matthias Balwierz 13 Markov Logik V z MLN mit der Formel ∀xSmokes( x) ⇒ Cancer ( x) und C = {A} ergeben sich vier mögliche Welten {¬R( A), ¬C ( A)},{R( A), ¬C ( A)},{¬R( A), C ( A)},{R( A), C ( A)} mit P({R( A), ¬C ( A)}) = 1 (3e + 1) und für die anderen Markov Logik generalisiert die Prädikatenlogik mit w → ∞ w z 18.11.2009 Markov Logik - Matthias Balwierz e w (3e w + 1) 14 Inferenz z Aufgabe: Finde den wahrscheinlichsten Zustand der Welt mit gegebenen Beweisen z z z z Maximierungsproblem welches mit typischen Solvern gelöst werden kann (P-vollständig) MaxWalkSAT LazySAT noch besser Aufgabe: Wahrscheinlichkeit für eine Formel z 18.11.2009 MC-SAT Markov Logik - Matthias Balwierz 15 Inferenz II (Domingos et al 2008) 18.11.2009 Markov Logik - Matthias Balwierz 16 Lernen z Generative Gewichte: z z z z 18.11.2009 Beispielwelt(en) Geschlossen: Klauseln die nicht enthalten sind, sind falsch Maximum-Likelihood-Methode ∂ log Pw ( X = x) = ni ( x) − ∑ Pw ( X = x' )ni ( x' ) ∂wi x' Erfordert Inferenz, kann durch Pseudo-Likelihood optimiert werden (Markov Blanket) Markov Logik - Matthias Balwierz 17 Lernen II z Diskriminative Gewichte z z z 18.11.2009 Partitionierung der Grund Atome in Beweise und „Queries“ Conditional Likelyhood Schneller lösbar als Maximum-Likelihood Markov Logik - Matthias Balwierz 18 Lernen III z Strukturen lernen: z z z Neue Klauseln finden Alle atomaren Klauseln hinzufügen Längere Klauseln bilden z z 18.11.2009 Um (negiertes) Prädikat erweitern mit min einer gemeinsamen Konstante Neue Kandidaten bewerten und beste(n) zu Klauseln hinzufügen Markov Logik - Matthias Balwierz 19 Lernen IV z Bewertung über Likelihood z z z Weitere Regeln für bestehende Klauseln z z z z 18.11.2009 WPLL mit L-BFGS Overfitting wird bestraft Vorzeichenwechsel Literale löschen Variablen matchen (maximale Anzahl an Variablen) Verfeinerte Klauseln löschen Markov Logik - Matthias Balwierz 20 Lernen V (Kok et al 2005) 18.11.2009 Markov Logik - Matthias Balwierz 21 Anwendungen z z z z z z Web Mining Natural Language Processing Computational Biology Robotik Spiele Soziale Netzwerke 18.11.2009 Markov Logik - Matthias Balwierz 22 Software z Alchemy z z Open Source KI Framework alchemy.cs.washington.edu 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”) (Domingos 2008) 18.11.2009 Markov Logik - Matthias Balwierz 23 Zusammenfassung z Markov Logik z z z z 18.11.2009 Vereinigt Wahrscheinlichkeitsnetze und Logik Widersprüche machen eine Welt weniger wahrscheinlich aber nicht unmöglich Wahrscheinlichste Zustände fehlender Information einer Welt können berechnet werden Wahrscheinlichkeiten und Strukturen können aus Beispielen gelernt werden Markov Logik - Matthias Balwierz 24 Literatur Luc De Raedt, Paolo Frasconi, Kristian Kersting, Stephen Muggleton (eds.) Probabilistic Inductive Logic Programming. Springer-Verlag, 2009. Pedro Domingos. Markov Logic: A Unifying Language for Information and Knowledge Management. CIKM. (2008) Lise Getoor and Ben Taskar, Introduction to Statistical Relational Learning, MIT Press. 2007. Stanley Kok , Pedro Domingos, Learning the structure of Markov logic networks, Proceedings of the 22nd international conference on Machine learning, p.441-448, August 07-11, 2005, Bonn, Germany M. Richardson, P. Domingos – Machine Learning, 2006 - Springer 18.11.2009 Markov Logik - Matthias Balwierz 25