Markov-Zufallsfeld: Erforschung der Leistungsfähigkeit von Markov-Zufallsfeldern in der Computer Vision

Von Fouad Sabry

Was ist ein Markov-Zufallsfeld

Im Bereich der Physik und Wahrscheinlichkeit ist ein Markov-Zufallsfeld (MRF), ein Markov-Netzwerk oder ein ungerichtetes grafisches Modell eine Reihe von Zufallsvariablen mit einer Markov-Eigenschaft, die durch einen ungerichteten Graphen beschrieben wird. Mit anderen Worten: Ein Zufallsfeld wird als Markov-Zufallsfeld bezeichnet, wenn es die Markov-Eigenschaften erfüllt. Das Konzept basiert auf dem Sherrington-Kirkpatrick-Modell.

Wie Sie davon profitieren

(I) Einblicke und Validierungen zu den folgenden Themen:

Kapitel 1: Markov-Zufallsfeld

Kapitel 2: Multivariate Zufallsvariable

Kapitel 3: Verstecktes Markov-Modell

Kapitel 4: Bayesianisches Netzwerk

Kapitel 5: Grafisches Modell

Kapitel 6: Zufallsfeld

Kapitel 7: Glaubensausbreitung

Kapitel 8: Faktordiagramm

Kapitel 9: Bedingtes Zufallsfeld

Kapitel 10: Hammersley-Clifford-Theorem

(II) Beantwortung der öffentlichen Top-Fragen zum Markov-Zufallsfeld.

(III) Beispiele aus der Praxis für die Verwendung des Markov-Zufallsfelds in vielen Bereichen.

Für wen dieses Buch gedacht ist

Berufstätige, Studenten und Doktoranden, Enthusiasten, Hobbyisten und diejenigen, die über Grundkenntnisse oder Informationen für jede Art von Markov-Zufallsfeld hinausgehen möchten.

 

 

• Sprache: Deutsch
• Herausgeber: Eine Milliarde Sachkundig [German]
• Erscheinungsdatum: 12. Mai 2024

Buchvorschau

Kapitel 1: Markov-Zufallsfeld

Ein Markov-Zufallsfeld (MRF), ein Markov-Netzwerk oder ein ungerichtetes grafisches Modell ist eine Sammlung von Zufallsvariablen mit einer Markov-Eigenschaft, die durch einen ungerichteten Graphen in den Bereichen Physik und Wahrscheinlichkeit dargestellt werden kann. Anders ausgedrückt: Ein zufälliges Feld hat nur dann Markov-Eigenschaften, wenn es bestimmte Eigenschaften erfüllt. Die Idee wurde im Sherrington-Kirkpatrick-Rahmen entwickelt.

In Bezug auf die Abhängigkeitsdarstellung ist ein Markov-Netzwerk oder Markov-Zufallsfeld (MRF) mit einem Bayes'schen Netzwerk vergleichbar, wobei der Hauptunterschied darin besteht, dass Bayes'sche Netzwerke gerichtet und azyklisch sind, während Markov-Netzwerke ungerichtet und potenziell zyklisch sind. Aus diesem Grund kann ein Markov-Netzwerk Abhängigkeiten darstellen, die ein Bayes'sches Netzwerk nicht darstellen kann (z. B. zyklische Beziehungen), während das Gegenteil nicht der Fall ist (z. B. induzierte Abhängigkeiten). Ein Markov-Zufallsfeld kann entweder einen endlichen oder einen unendlichen zugrunde liegenden Graphen haben.

Das Hammersley-Clifford-Theorem besagt, dass für eine geeignete (lokal spezifizierte) Energiefunktion ein Gibbs-Maß nur dann zur Darstellung eines Zufallsfeldes verwendet werden kann, wenn die gemeinsame Wahrscheinlichkeitsdichte der Zufallsvariablen streng positiv ist. Das Ising-Modell dient als paradigmatisches Beispiel für ein Markov-Zufallsfeld, und in diesem Zusammenhang wurde das Markov-Zufallsfeld erstmals vorgestellt.

Bei einem ungerichteten Graphen G=(V,E) bildet eine Menge von Zufallsvariablen, {\displaystyle X=(X_{v})_{v\in V}} die indiziert sind V , ein Markov-Zufallsfeld in Bezug darauf, G ob sie die lokalen Markov-Eigenschaften erfüllen:

Alle Paare nicht-kollinearer Variablen sind in Bezug auf alle anderen Variablen bedingt unabhängig, gemäß der paarweisen Markov-Eigenschaft:

{\displaystyle X_{u}\perp \!\!\!\perp X_{v}\mid X_{V\setminus \{u,v\}}}

Die lokale Markov-Eigenschaft besagt, dass eine gegebene Variable aufgrund ihrer unmittelbaren Umgebung bedingt unabhängig von jeder anderen Variablen ist:

{\displaystyle X_{v}\perp \!\!\!\perp X_{V\setminus \operatorname {N} [v]}\mid X_{\operatorname {N} (v)}}

wobei {\textstyle \operatorname {N} (v)} die Menge der Nachbarn von v ist und {\displaystyle \operatorname {N} [v]=v\cup \operatorname {N} (v)} die geschlossene Nachbarschaft von v ist.

Die globale Markov-Eigenschaft besagt, dass bei einer trennenden Teilmenge von Variablen zwei beliebige Teilmengen von Variablen bedingt unabhängig sind:

X_A \perp\!\!\!\perp X_B \mid X_S

wobei jeder Pfad von einem Knoten in A zu einem Knoten in B durch S .

Die Global Markov-Eigenschaft übertrifft die Local Markov-Eigenschaft, die wiederum die paarweise Markov-Eigenschaft übertrifft. (die verknüpften Variablen nur Wahrscheinlichkeiten ungleich Null geben).

Die folgende Formulierung macht die Verbindung zwischen den drei Markov-Merkmalen kristallklar:

Paarweise: Für alle {\displaystyle i,j\in V} , die nicht gleich oder benachbart sind, {\displaystyle X_{i}\perp \!\!\!\perp X_{j}|X_{V\setminus \{i,j\}}} .

Lokal: Für alle {\displaystyle i\in V} und {\displaystyle J\subset V} nicht enthaltenden oder angrenzenden i , {\displaystyle X_{i}\perp \!\!\!\perp X_{J}|X_{V\setminus (\{i\}\cup J)}} .

Global: Für alle {\displaystyle I,J\subset V} , die sich nicht kreuzen oder angrenzen, {\displaystyle X_{I}\perp \!\!\!\perp X_{J}|X_{V\setminus (I\cup J)}} .

Markov-Zufallsfelder, die entsprechend den Cliquen des Netzwerks faktorisiert werden können, werden häufig verwendet, da die Markov-Eigenschaft einer beliebigen Wahrscheinlichkeitsverteilung schwierig zu ermitteln sein kann.

Bei einer gegebenen Menge von Zufallsvariablen {\displaystyle X=(X_{v})_{v\in V}} sei P(X=x) die Wahrscheinlichkeit einer bestimmten Feldkonfiguration x in X .

Das heißt, P(X=x) ist die Wahrscheinlichkeit, dass die Zufallsvariablen X den bestimmten Wert annehmen x .

Da X eine Menge ist, sollte die Wahrscheinlichkeit von x so verstanden werden, dass sie in Bezug auf eine gemeinsame Verteilung der {\displaystyle X_{v}} .

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

P(X=x) = \prod_{C \in \operatorname{cl}(G)} \phi_C (x_C)

und X bildet dann ein Markov-Zufallsfeld in Bezug auf G .

Hier {\displaystyle \operatorname {cl} (G)} ist die Menge der Cliquen von G .

Betrachtet man nur maximale Cliquen, bleibt das Konzept unverändert.

Die Funktionen {\displaystyle \phi _{C}} 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 {\displaystyle \phi _{C}} angewendet.

In Anbetracht dessen hat die Mechanik des Zufalls {\displaystyle \log(\phi _{C})} eine direkte Interpretation als die potentielle Energie einer Konfiguration {\displaystyle x_{C}} .

Es ist möglich, ein einfaches Beispiel für eine MRF zu entwerfen, die nicht auf einem 4-Knoten-Zyklus mit bestimmten unendlichen Energien faktorisiert, d.h.

probabilistische Nullsummenkonfigurationen, der Fall, der es den unendlichen Energien erlaubt, auf den vollständigen Graphen auf zu wirken V .

Wenn eine der folgenden Bedingungen zutrifft, werden MRFs faktorisiert:

Nach dem Hammersley-Theorem muss die Dichte von Clifford positiv sein.

Ein Sehnengraph (durch Äquivalenz zu einem Bayes'schen Netzwerk)

Ein Faktordiagramm des Netzwerks kann erstellt werden, wenn seine Scheitelpunkte faktorisiert wurden.

Jedes positive Markov-Zufallsfeld kann als Exponentialfamilie in kanonischer Form mit Merkmalsfunktionen geschrieben werden f_{k} , so dass die Vollgelenkverteilung als

P(X=x) = \frac{1}{Z} \exp \left( \sum_{k} w_k^{\top} f_k (x_{ \{ k \}}) \right)

wobei die Notation

w_k^{\top} f_k (x_{ \{ k \}}) = \sum_{i=1}^{N_k} w_{k,i} \cdot f_{k,i}(x_{\{k\}})

Partitionsfunktion, und Z ist nur ein Punktprodukt über Feldkonfigurationen hinweg:

Z = \sum_{x \in \mathcal{X}} \exp \left(\sum_{k} w_k^{\top} f_k(x_{ \{ k \} })\right).

Hier {\mathcal {X}} bezeichnet die Menge aller möglichen Zuweisungen von Werten zu allen Zufallsvariablen des Netzwerks.

In der Regel sind die Feature-Funktionen f_{k,i} so definiert, dass sie Indikatoren für die Konfiguration der Clique sind, d.h.

f_{k,i}(x_{\{k\}}) = 1 if x_{\{k\}} entspricht der i-ten möglichen Konfiguration der k-ten Clique und 0 sonst.

Das obige Cliquenfaktorisierungsmodell ist äquivalent zu diesem, wenn N_k=|\operatorname{dom}(C_k)| die Kardinalität der Clique ist und das Gewicht eines Merkmals f_{k,i} dem Logarithmus des entsprechenden Cliquenfaktors entspricht, d.h.

w_{k,i} = \log \phi(c_{k,i}) , wobei c_{k,i} die i-te mögliche Konfiguration der k-ten Clique ist, d.h.

Der i-te Wert im Bereich der Clique C_{k} .

Das Gibbs-Maß ist ein anderer Name für die Wahrscheinlichkeit P.

Nur wenn alle Cliquenfaktoren ungleich Null sind, kann ein Markov-Feld als logistisches Modell ausgedrückt werden, d.h.

Wenn keinem der Elemente von {\mathcal {X}} eine Wahrscheinlichkeit von 0 zugewiesen ist.

Dies ermöglicht den Einsatz von Methoden aus der Matrixalgebra, z.

Matrixspuren sind proportional zu Logarithmus von Determinanten, durch die Inzidenzmatrix des Graphen, um eine Matrixdarstellung des