Markov-Logik-Netz

Markov-Logik-Netze wenden probabilistische graphische Modelle auf die Prädikatenlogik erster Stufe an und ermöglichen so probabilistische Inferenz. Sie wurden 2006 von Matthew Richardson und Pedro Domingos vorgestellt. In einem Markov-Logik-Netz werden Schlussfolgerungen durch die Anwendung des MCMC-Verfahrens gemacht.

Motivation

Die Prädikatenlogik erster Stufe ist gut geeignet, wenn sichere Informationen vorliegen und Zusammenhänge garantiert auftreten. Allerdings ist dies in der realen Welt selten gegeben. So ist die Schlussfolgerung „Der Boden ist nass“ $\rightarrow$ „Es hat geregnet“ zwar häufig richtig, aber es könnte auch jemand den Boden mit dem Gartenschlauch nass gemacht haben.

Probabilistische graphische Modelle hingegen erlauben solch unsichere Inferenz. Kann man die Zufallsvariablen durch einen gerichteten azyklischen Graph (DAG) in Zusammenhang bringen, so erhält man ein Bayessches Netz. Drückt man den Zusammenhang der Zufallsvariablen durch einen ungerichteten Graph aus, so erhält man ein Markov-Logik-Netz. Bei den Bayesschen Netzen stehen die Kanten für Kausalität, bei Markov-Logik-Netzen jedoch nur für Korrelation.

Definition

Ein Markov-Logik-Netz wurde in sinngemäß wie folgt definiert:

Ein Markov-Logik-Netz $L$ ist eine Menge aus Tupeln $(F_{i},w_{i})$, wobei $F_{i}$ eine Formel der Prädikatenlogik erster Ordnung ist und $w_{i}\in \mathbb {R}$ ein Gewicht ist.

Zusammen mit einer endlichen Menge an Konstanten $C=\{c_{1},c_{2},\dots ,c_{n}\}$ mit $n\in \mathbb {N}$ kann mithilfe des Markov-Logik-Netzes ein Markov Random Field definiert werden. Dafür wird jede mögliche Belegung jedes Prädikats des Markov-Logik-Netzes zu einem Knoten im Markov Random Field.

Inferenz

Die Inferenz-Aufgabe in Markov-Logik-Netzen ist es, die wahrscheinlichste Welt (Variablenbelegung) zu finden. Diese Art der Schlussfolgerungen kann in Markov-Logik-Netzen auf folgende Art geschehen:

• Maximum a posteriori Methode
• MCMC-Verfahren
  • MC-SAT
• Lifted Belief Propagation

Beziehung zu anderen Statistischen Modellen

Folgende statistische Modelle sind Spezialfälle von Markov-Logik-Netzen:

• Bayessches Netz
• Boltzmann-Maschine
• Hidden Markov Model
• Log-lineares Modell
• Logistische Regression
• Markov Random Field
  • Conditional Random Field