07 Markov Logik Netze (MLN) Flashcards
Markov Netz - Verbundwahrscheinlichkeit
Durch s.g. Probabilisitische Graphische Modelle (PGM) lassen sich die Verbundwahrscheinlichkeitsverteilung über die Mengen von Zufallsvariablen beschreiben
Knoten repräsentieren Zufallsvariablen
Graph kodiert Abhängigkeiten zwischen Zufallsvariablen
Gereichtete azyklische Graphen –> Bayesche Netze (Kausalität)
Ungerichtete Graphen –> Markov Netze (Korrelation)
Grundidee der Markov Logik
Logische Wissensbasis –> strikte Entscheidungen (hard constraints) bzgl. Raum der potentiellen Welten
Aufweichen (soft constraints):
Wenn eine Welt eine Regel (Formel) verletzt wird diese Welt weniger wahrscheinlich aber nicht unmöglich
Grundidee: Jede Formel wird gewichtet
(je höher das Gewicht umso stärker ist der Einfluss dieser Formel)
Gesamtwahrscheinlichkeit (“Möglichkeit”) einer Welt:
P(Welt) = exp(Summe_Formeln(Gewicht der Formel die erfüllt ist))
Definition Markov Logik Netze
Syntax:
Ein Markov Logik Netz (MLN) ist eine Menge von Tupeln (F_i, w_i) wobei:
* F_i: ist eine Formel in Prädiktenlogik erster Ordnung
* w_i ist eine reelle Zahl (Gewicht)
Semantik:
Mit einer Menge von Konstanten wird daraus ein Markov Netz definiert, mit:
* Je einem Knoten für jede mögliche Belegung jedes Prädikates des MLN (Zufallsvariable im MN ~ Variable ~ Belegung eines Prädikats)
* Je einem Feature für jee Belegung (grounding) jeder Formel F_i des MLN mit dem entsprechenden Gewicht w_i
MLN
MLN ist eine Schablone (Template) für den Aufbau eines Markov Netzes
Typisierte PL - Variablen und Konstanten reduzieren sehr stark die Größe des aufgebauten Markov Netzes (reduzierte Belegung)
Möglichkeit der Nutzung von:
- Funktionen, Quantoren, …
- Endliche und kontinuierliche Domäne
Vergleich zu Prädikatenlogik erster Ordnung
Wenn unendliche Gewichte
–> MLN = reine Prädikatelogik erster Ordnung (beweisbar)
Wenn erfüllbare Wissensbasis, dh Welten s.d. alle Formeln wahr sind
- -> erfüllende Interpretationen (Welten) sind die Modalwerte der Verteilung
- -> dh dass auch im Falle von verrauschten Daten die Welten, die durch die Prädikatenlogik ausgedrückt werden enthalten sind
Vorteil: Markov Logik erlaubt Widersprüche unter den Formeln
–> wichtig für reale verrauschte Daten oder unvollständiges Modell
MAP/MPE Inferenz
Problem:
Finden des wahrscheinlichsten Zustands der Welt (Variablen y ~ Wahrheitswert der Belegung des entsprechenden Atoms), gegeben Evidenzen x (wahrscheinlichste Erklärung für y)
Bekannter Ansatz: Maximum a-posteriori (MAP) Ansatz bzw. most probable estimate (MPE)
argmax_y P(y|x)
in MLN eingesetzt:
argmax_y Summe(w_i*n_i(x,y))
Dies ist bekannt ls “weighted MaxSAT” Problem
- SAT = satisfied belief / satisfiability - solver –> alle Formeln erfüllen
- MaxSAT –> so viele Formeln wie möglich erfüllen
- Weighted MaxSAT –> max. gewichtete Anzahl von Formeln erfüllen
Vorteile:
+ standard Verfahren : SAT solver
+ Potentiell schneller als rein logische Inferenz !
WalkSAT Algorithmus
Ziel:
Finden einer Interpretation (Wahrheitswert - Zuordnung, truth assignments) der Variablen (PL-Atome) um alle Klauseln gleichzeitig zu erfüllen
Klauseln: Disjunktion von Literalen (Verallgemeinerung: jede Formel in disjunktive Form konvertierbar)
Problem Speicherkomplexität
Wenn es n Konstanten gibt und Klausel mit (max.) Anzahl c unterschiedlichen Varialben
Dann benötigt das belegte Netz O(n^c) Speicher –> kann schnell, sehr stark explodieren
Praktikable Lösung:
- Nutzung der dünnen Belegung (sparseness)
- -> Klauseln werden nur dünn belegt
Anfragen und Wahrscheinlichkeiten
- Häufige Fragestellungen:
(geg. MLN, Konstante C)
P(Formel | MLN, C) = ?
entspricht der Summer der Wahrschienlichkeiten der Welten in denen die Formel erfült ist
Aber: gro0e exponentielle Anzahl von Welten
Lösung:
- MCMC (Markov Chain Monte Carlo) Ansatz:
- stochastisches Abtasten der Welten (Wiederholtes sampeln von Interpretationen für eine / jeder Variable in abh. von MAP)
- Test ob Formel erfüllt ist
- -> Anteil (Faktor) entspricht der gesuchten Wahrscheinlichkeit P
- Anfrage (geg MLN, C)
P(Formel1 | Formel2, MLN, C) = ?
Idee: In MCMC Berücksichtigen der Welten die bedingende Formel erfüllen
Lernen in MLN
Gegeben
- Daten (beobachtete Welten), z.B. in einer relationalen Form (Datenbank)
- Geschlossene Welt - Annahme, d.h. jedes Atom, das nicht in den Daten /Datenbank ist, ist falsch (sonst erweiterte Verfahren wie EM)
Lernen
* Parameter (Gewichte):
Formeln sind gegeben, Gewichte sind unbekannt
Ansätze: Generativ Lernen, Diskriminatives Lernen
* Struktur:
Formeln und Gewichte sind unbekannt (oder nur teilweise vorhanden)
Generatives Lernen von Gewichten
Finden der Gewichte, die am wahrscheinlichsten die Daten generiert haben
Lösung: Maximul likelihood Ansatz : log(P) maximieren
Maximierungsalgorithmus zB Gradientenverfahren
Gradient ist Konvex, dh keine lokalen Maxima, Initialisierung beliebig .
Aber: benögitg Inferenz um die ERwartung zu bestimmen - in jedem Schritt des Gradientenverfahrens. Langsam!
Diskriminatives Lernen von Gewichten
Maximieren der bedingten Wahrscheinlichkeit der Anfrage (y) gegeben Evidenzen (x) - wenn vorab Evidenzen bekannt sind (üblich)
Vorteil durch Evidenzen: Viele Inferenzschritte fallen weg
Struktur Lernen - Idee
Typischer (heuristischer) Algorithmus:
- Initialisierung: Atomare Klauseln oder vorgegebene Wissensbasis
- Iterieren:
* Ändern durch Operatoren: Add/Löschen v Literalen, Negieren …
* Lernen der Gewichte des MLN
* Evaluationsfunktion für MLN durch:
- - Güte des Modells für Daten –> Verbundswahrscheinlichkeit
- - Strukturbewertung (prior): Bestrafung wenn Struktur zu sehr von einer def. Vorgabe abweicht (zur Reduzierung von Overfitting) - Suchen nach neuen Kandidaten (Änderung)
* Verschiedene Methoden …