Markov-Zufallsfeld - Markov random field

Ein Beispiel für ein Markov-Zufallsfeld.
Ein Beispiel für ein Markov-Zufallsfeld. Jede Kante steht für Abhängigkeit. In diesem Beispiel: A hängt von B und D ab. B hängt von A und D ab. D hängt von A, B und E ab. E hängt von D und C ab. C hängt von E ab.

Im Bereich der Physik und Wahrscheinlichkeit ist ein Markov-Zufallsfeld ( MRF ), ein Markov-Netzwerk oder ein ungerichtetes grafisches Modell ein Satz von Zufallsvariablen mit einer durch einen ungerichteten Graphen beschriebenen Markov-Eigenschaft . Mit anderen Worten, ein Zufallsfeld wird als Markov- Zufallsfeld bezeichnet, wenn es die Markov-Eigenschaften erfüllt.

Ein Markov-Netzwerk oder MRF ähnelt in seiner Darstellung von Abhängigkeiten einem Bayes-Netzwerk ; der Unterschied besteht darin, dass Bayessche Netzwerke gerichtet und azyklisch sind , während Markov-Netzwerke ungerichtet sind und zyklisch sein können. Somit kann ein Markov-Netzwerk bestimmte Abhängigkeiten darstellen, die ein Bayes-Netzwerk nicht darstellen kann (wie zyklische Abhängigkeiten); auf der anderen Seite kann es bestimmte Abhängigkeiten nicht darstellen, die ein Bayes-Netzwerk kann (wie etwa induzierte Abhängigkeiten). Der zugrundeliegende Graph eines Markov-Zufallsfeldes kann endlich oder unendlich sein.

Wenn die gemeinsame Wahrscheinlichkeitsdichte der Zufallsvariablen streng positiv ist, wird sie auch als Gibbs-Zufallsfeld bezeichnet , weil sie nach dem Satz von Hammersley-Clifford dann durch ein Gibbs-Maß für ein geeignetes (lokal definiertes) Energiefunktion. Das prototypische Markov-Zufallsfeld ist das Ising-Modell ; tatsächlich wurde das Markov-Zufallsfeld als allgemeine Einstellung für das Ising-Modell eingeführt. Im Bereich der künstlichen Intelligenz wird ein Markov-Zufallsfeld verwendet, um verschiedene Aufgaben auf niedriger bis mittlerer Ebene in der Bildverarbeitung und Computer Vision zu modellieren .

Definition

Bei einem ungerichteten Graphen bildet eine Menge von Zufallsvariablen, die durch indiziert   sind, ein Markov-Zufallsfeld in Bezug darauf,   ob sie die lokalen Markov-Eigenschaften erfüllen:

Paarweise Markov-Eigenschaft: Beliebige zwei nicht benachbarte Variablen sind bei allen anderen Variablen bedingt unabhängig :
Lokale Markov-Eigenschaft: Eine Variable ist aufgrund ihrer Nachbarn bedingt unabhängig von allen anderen Variablen:
wo ist die Menge der Nachbarn von , und ist die geschlossene Umgebung von .
Globale Markov-Eigenschaft: Beliebige zwei Teilmengen von Variablen sind bedingt unabhängig, wenn eine trennende Teilmenge gegeben ist:
wobei jeder Pfad von einem Knoten in zu einem Knoten in durchläuft .

Die Global-Markov-Eigenschaft ist stärker als die Local-Markov-Eigenschaft, die wiederum stärker ist als die Pairwise-Eigenschaft. Die obigen drei Markov-Eigenschaften sind jedoch für positive Verteilungen äquivalent (solche, die den zugeordneten Variablen nur Wahrscheinlichkeiten ungleich Null zuordnen).

Cliquenfaktorisierung

Da die Markov-Eigenschaft einer willkürlichen Wahrscheinlichkeitsverteilung schwierig zu bestimmen sein kann, sind eine häufig verwendete Klasse von Markov-Zufallsfeldern diejenigen, die gemäß den Cliquen des Graphen faktorisiert werden können .

Gegeben eine Menge von Zufallsvariablen sei die Wahrscheinlichkeit einer bestimmten Feldkonfiguration in  . Das heißt, ist die Wahrscheinlichkeit, dass die Zufallsvariablen den bestimmten Wert annehmen . Da es sich um eine Menge handelt, sollte die Wahrscheinlichkeit von in Bezug auf eine gemeinsame Verteilung von verstanden werden .

Wenn diese Fugendichte über die Cliquen von faktorisiert werden kann :

bildet dann ein Markov-Zufallsfeld bezüglich . Hier ist die Menge der Cliquen von . Die Definition ist äquivalent, wenn nur maximale Cliquen verwendet werden. Die Funktionen werden manchmal als Faktorpotentiale oder Cliquenpotentiale bezeichnet . Beachten Sie jedoch, dass widersprüchliche Terminologie verwendet wird: Das Wort Potenzial wird oft auf den Logarithmus von angewendet . Dies liegt daran, in der statistischen Mechanik , eine direkte Interpretation als hat potentielle Energie einer Konfiguration .  

Einige MRFs faktorisieren nicht: Ein einfaches Beispiel kann auf einem Zyklus von 4 Knoten mit einigen unendlichen Energien konstruiert werden, dh Konfigurationen von Null-Wahrscheinlichkeiten, selbst wenn eine die unendlichen Energien passender auf den gesamten Graphen wirken lässt .

MRFs faktorisieren, wenn mindestens eine der folgenden Bedingungen erfüllt ist:

Wenn eine solche Faktorisierung existiert, ist es möglich, einen Faktorgraphen für das Netzwerk zu erstellen.

Exponentielle Familie

Jedes positive Markov-Zufallsfeld kann als Exponentialfamilie in kanonischer Form mit Merkmalsfunktionen geschrieben werden, so dass die Full-Joint-Verteilung geschrieben werden kann als

wo die notation

ist einfach ein Punktprodukt über Feldkonfigurationen und Z ist die Partitionsfunktion :

Hier bezeichnet die Menge aller möglichen Zuordnungen von Werten an alle Zufallsvariablen des Netzes. Üblicherweise sind die Merkmalsfunktionen so definiert, dass sie Indikatoren für die Konfiguration der Clique sind, dh wenn sie der i- ten möglichen Konfiguration der k- ten Clique entsprechen und ansonsten 0. Dieses Modell ist für die Clique Faktorisierung Modell äquivalent oben angegebenen, wenn die Mächtigkeit der Clique ist, und das Gewicht eines Merkmal entspricht den Logarithmus des entsprechenden Clique Faktors, das heißt , wo die i mögliche Konfiguration des -te k - th Clique, dh der i- te Wert im Bereich der Clique .

Die Wahrscheinlichkeit P wird oft als Gibbs-Maß bezeichnet. Dieser Ausdruck eines Markov-Feldes als logistisches Modell ist nur möglich, wenn alle Cliquenfaktoren ungleich Null sind, dh wenn keinem der Elemente von eine Wahrscheinlichkeit von 0 zugewiesen wird. Dies ermöglicht die Anwendung von Techniken aus der Matrixalgebra, z. B. dass die Spur einer Matrix ist der Logarithmus der Determinante , wobei sich die Matrixdarstellung eines Graphen aus der Inzidenzmatrix des Graphen ergibt .

Die Bedeutung der Partitionsfunktion Z liegt darin, dass viele Konzepte aus der statistischen Mechanik , wie zB die Entropie , direkt auf den Fall von Markov-Netzwerken verallgemeinert werden und dadurch ein intuitives Verständnis gewonnen werden kann. Darüber hinaus ermöglicht die Partitionsfunktion die Anwendung von Variationsmethoden zur Lösung des Problems: Man kann einer oder mehreren der Zufallsvariablen eine treibende Kraft zuordnen und die Reaktion des Netzwerks als Reaktion auf diese Störung untersuchen . So kann man zum Beispiel für jede Ecke v des Graphen einen treibenden Term J v zur Partitionsfunktion hinzufügen , um zu erhalten:

Formell mit Bezug auf differenzier J v ergibt der Erwartungswert der Zufallsvariablen X v mit dem Scheitelpunkt zugeordnet v :

Korrelationsfunktionen werden ebenfalls berechnet; die Zwei-Punkte-Korrelation ist:

Obwohl die Likelihood eines logistischen Markov-Netzwerks konvex ist, erfordert die Auswertung der Likelihood oder des Gradienten der Likelihood eines Modells leider eine Inferenz im Modell, die im Allgemeinen rechnerisch nicht durchführbar ist (siehe „Inferenz“ unten).

Beispiele

Gaussian

Eine multivariate Normalverteilung bildet ein Markov-Zufallsfeld in Bezug auf einen Graphen, wenn die fehlenden Kanten Nullen in der Präzisionsmatrix (der inversen Kovarianzmatrix ) entsprechen:

so dass

Inferenz

Wie in einem Bayesschen Netzwerk kann man die bedingte Verteilung einer Menge von Knoten mit gegebenen Werten auf eine andere Menge von Knoten im Markov-Zufallsfeld berechnen, indem man über alle möglichen Zuweisungen zu summiert ; dies wird als exakte Inferenz bezeichnet . Exakte Inferenz ist jedoch ein #P-vollständiges Problem und daher im allgemeinen Fall rechnerisch schwer zu handhaben. Approximationstechniken wie Markov-Chain-Monte-Carlo und Loopy- Belief-Propagation sind in der Praxis oft praktikabler. Einige bestimmte Unterklassen von MRFs, wie Bäume (siehe Chow-Liu-Baum ), haben Inferenzalgorithmen in Polynomialzeit; Das Auffinden solcher Unterklassen ist ein aktives Forschungsthema. Es gibt auch Subklassen von MRF , die effizient erlauben MAP oder am wahrscheinlichsten Zuordnung, Inferenz; Beispiele hierfür sind assoziative Netzwerke. Eine weitere interessante Unterklasse ist die der zerlegbaren Modelle (wenn der Graph chordal ist ): Mit einer geschlossenen Form für den MLE ist es möglich, eine konsistente Struktur für Hunderte von Variablen zu entdecken.

Bedingte Zufallsfelder

Eine bemerkenswerte Variante eines Markov-Zufallsfeldes ist ein bedingtes Zufallsfeld , bei dem jede Zufallsvariable auch von einer Menge globaler Beobachtungen abhängig sein kann . In diesem Modell ist jede Funktion eine Abbildung aller Zuweisungen sowohl an die Clique k als auch die Beobachtungen an die nichtnegativen reellen Zahlen. Diese Form des Markov-Netzwerks ist möglicherweise besser geeignet, um diskriminative Klassifikatoren zu erzeugen , die die Verteilung über die Beobachtungen nicht modellieren. CRFs wurden 2001 von John D. Lafferty , Andrew McCallum und Fernando CN Pereira vorgeschlagen .

Vielfältige Anwendungen

Markov-Zufallsfelder finden in einer Vielzahl von Bereichen Anwendung, die von Computergrafik über Computer Vision, maschinelles Lernen oder Computerbiologie reichen . MRFs werden in der Bildverarbeitung zur Erzeugung von Texturen verwendet, da sie zur Erzeugung flexibler und stochastischer Bildmodelle verwendet werden können. Bei der Bildmodellierung besteht die Aufgabe darin, eine geeignete Intensitätsverteilung eines bestimmten Bildes zu finden, wobei die Eignung von der Art der Aufgabe abhängt und MRFs flexibel genug sind, um für Bild- und Textursynthese, Bildkomprimierung und -wiederherstellung , Bildsegmentierung , 3D-Bild verwendet zu werden Inferenz aus 2D-Bildern, Bildregistrierung , Textursynthese , Superauflösung , Stereoabgleich und Informationsabruf . Sie können verwendet werden, um verschiedene Computer-Vision-Probleme zu lösen, die sich als Energieminimierungsprobleme oder Probleme stellen können, bei denen verschiedene Regionen unter Verwendung eines Satzes von Unterscheidungsmerkmalen innerhalb eines Markov-Zufallsfeldrahmens unterschieden werden müssen, um die Kategorie der Region vorherzusagen. Markov-Zufallsfelder waren eine Verallgemeinerung des Ising-Modells und werden seitdem häufig in kombinatorischen Optimierungen und Netzwerken verwendet.

Siehe auch

Verweise