07 Markov Logik Netze (MLN) Flashcards

1
Q

Markov Netz - Verbundwahrscheinlichkeit

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Grundidee der Markov Logik

A

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))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Definition Markov Logik Netze

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

MLN

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Vergleich zu Prädikatenlogik erster Ordnung

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

MAP/MPE Inferenz

A

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 !

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

WalkSAT Algorithmus

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Problem Speicherkomplexität

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Anfragen und Wahrscheinlichkeiten

A
  1. 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
  1. Anfrage (geg MLN, C)

P(Formel1 | Formel2, MLN, C) = ?

Idee: In MCMC Berücksichtigen der Welten die bedingende Formel erfüllen

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Lernen in MLN

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Generatives Lernen von Gewichten

A

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!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Diskriminatives Lernen von Gewichten

A

Maximieren der bedingten Wahrscheinlichkeit der Anfrage (y) gegeben Evidenzen (x) - wenn vorab Evidenzen bekannt sind (üblich)

Vorteil durch Evidenzen: Viele Inferenzschritte fallen weg

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Struktur Lernen - Idee

A

Typischer (heuristischer) Algorithmus:

  1. Initialisierung: Atomare Klauseln oder vorgegebene Wissensbasis
  2. 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)
  3. Suchen nach neuen Kandidaten (Änderung)
    * Verschiedene Methoden …
How well did you know this?
1
Not at all
2
3
4
5
Perfectly