Wo ist die Graphentheorie in grafischen Modellen?

29

Einführungen in grafische Modelle beschreiben sie als "... eine Verbindung zwischen Graphentheorie und Wahrscheinlichkeitstheorie".

Ich verstehe den Teil der Wahrscheinlichkeitstheorie, habe aber Probleme zu verstehen, wo genau die Graphentheorie hineinpasst. Welche Erkenntnisse aus der Graphentheorie haben dazu beigetragen, unser Verständnis der Wahrscheinlichkeitsverteilungen und der Entscheidungsfindung unter Ungewissheit zu vertiefen?

Ich suche konkrete Beispiele, die über den offensichtlichen Gebrauch der graphentheoretischen Terminologie in PGMs hinausgehen, wie die Klassifizierung einer PGM als "Baum" oder "zweiteilig" oder "ungerichtet" usw.

graphical-model graph-theory distributions Vimal
quelle

33

Es gibt sehr wenig echte mathematische Graphentheorie in probabilistischen graphischen Modellen, wobei ich mit echter mathematischer Graphentheorie Beweise über Cliquen, Vertexordnungen, Max-Flow-Min-Cut-Theoreme usw. meine. Sogar etwas so Grundlegendes wie Eulers Theorem und Handshaking Lemma werden nicht verwendet, obwohl ich vermute, dass man sie aufrufen könnte, um eine Eigenschaft von Computercode zu überprüfen, der zum Aktualisieren von Wahrscheinlichkeitsschätzungen verwendet wird. Darüber hinaus verwenden probabilistische Grafikmodelle selten mehr als eine Teilmenge der Grafikklassen, wie z. B. Mehrfachgrafiken. Theoreme über Flüsse in Graphen werden in probabilistischen grafischen Modellen nicht verwendet.

Wenn Schüler A ein Experte für Wahrscheinlichkeitsrechnung wäre, aber nichts über Graphentheorie wüsste, und Schüler B ein Experte für Graphentheorie wäre, aber nichts über Wahrscheinlichkeitsrechnung wüsste, dann würde A wahrscheinlich schneller probabilistische graphische Modelle lernen und verstehen als B.

David G. Stork
quelle

8

In einem strengen Sinn, Graph - Theorie scheint zu PGMs lose verbunden. Graph- Algorithmen sind jedoch nützlich. PGMs begannen mit der Inferenz der Nachrichtenübermittlung, einer Teilmenge der allgemeinen Klasse von Nachrichtenübermittlungsalgorithmen für Graphen (möglicherweise ist dies der Grund für das Wort „grafisch“ in ihnen). Graph-Cut-Algorithmen werden häufig für die Markov-Zufallsfeldinferenz in der Bildverarbeitung verwendet. Sie basieren auf Ergebnissen, die dem Ford-Fulkerson-Theorem ähneln (maximaler Durchfluss entspricht minimalem Schnitt). Die bekanntesten Algorithmen sind wahrscheinlich Boykov-Kolmogorov und IBFS.

Verweise. [Murphy, 2012 , §22.6.3] behandelt die Verwendung von Grafikschnitten für MAP-Inferenzen. Siehe auch [Kolmogorom und Zabih, 2004 ; Boykov et al., PAMI 2001] , die sich eher mit Optimierung als mit Modellierung befassen.

Roman Shapovalov
quelle

Interessanterweise werden in MRFs Graph-Cut-Algorithmen verwendet. Könnten Sie auf eine Referenz verweisen? Basierend auf der obigen Antwort von David Stork scheint es, dass diese Algorithmen auf der Tatsache beruhen, dass die Graphentheorie ein nützliches Modellierungswerkzeug war und keine fundamentale Verbindung zwischen der Graphentheorie und PGMs.

Vimal,

Ich habe die Referenzen hinzugefügt, wie Sie gefragt haben. Wie können wir nach Ihrer letzten Aussage die Ursachen trennen, dh feststellen, ob sie grundlegend sind oder nicht?

Roman Shapovalov

@overrider Könnten Sie vollständige Referenzen angeben, damit die Artikel leicht durchsucht werden können? Googeln kann Menschen zu den Referenzen führen, kann aber auch dazu führen, dass Zeit für irrelevante Ergebnisse verschwendet wird. So sind Titel, Verlage, Zeitschriftennamen, Links usw. eine gute Sache, um hinzuzufügen.

Tim

2

Algorithmen zum Schneiden von Graphen sind in der Bildverarbeitung nützlich, aber keine probabilistischen grafischen Modelle. Ein Problem beim Stereovision ist das Korrespondenzproblem: Finden, welche Punkte in Bild A den Punkten in Bild B entsprechen. Man kann ein Diagramm erstellen, bei dem die Scheitelpunkte den Merkmalspunkten in den beiden Bildern entsprechen und ein Diagramm alle möglichen Korrespondenzen darstellt. Dann kann das Problem des Findens der "richtigen" Entsprechungen als Graph-Cut-Problem gewertet werden. Es gibt keine solche Verwendung in generischen Grafikmodellen, obwohl ich annehmen könnte, dass man versuchen könnte, dieses Computer-Vision-Problem auf Grafikmodelle abzubilden.

David G. Stork

2

@ DavidG.Stork Es gibt andere Probleme mit der Bildverarbeitung, bei denen Grafikschnitte auf ähnliche Weise angewendet werden: Bildsegmentierung, Erstellen von Collagen usw. Der Ansatz ist also allgemein genug. Diese Probleme können natürlich in ungerichteten grafischen Modellen ausgedrückt werden (obwohl dies in Papieren nicht immer der Fall ist). Dies ermöglicht die Verwendung verschiedener MRF-Inferenzalgorithmen sowie die Modellanpassung. Auf der anderen Seite können Grafikschnitte eine ziemlich große Teilmenge von MRFs optimieren und somit über das Sehvermögen hinaus angewendet werden, z. B. für die Analyse sozialer Netzwerke (obwohl ich mich jetzt nicht an bestimmte Artikel erinnern kann).

Roman Shapovalov

4

In einigen Arbeiten wurde der Zusammenhang zwischen der einfachen Decodierung von Paritätsprüfcodes mit niedriger Dichte (die hervorragende Ergebnisse erzielen, wenn Sie sie als probablistischen Graphen betrachten und Loopy Belief Propagation anwenden) und dem Umfang des durch die Paritätsprüfmatrix gebildeten Graphen untersucht . Diese Verbindung zum Umfang reicht bis in die Zeit zurück, als LDPCs erfunden wurden [1], aber es gab weitere Arbeiten in den letzten zehn Jahren [2] [3], nachdem Mackay et al. [4] sie separat wiederentdeckten und ihre Eigenschaften feststellten .

Ich sehe oft Perlens Kommentar zur Konvergenzzeit der Glaubensausbreitung in Abhängigkeit vom Durchmesser des zitierten Graphen. Ich kenne jedoch keine Arbeit, die sich mit den Durchmessern von Diagrammen in Nicht-Baum-Diagrammen befasst und welche Auswirkungen dies hat.

RG Gallager. Paritätsprüfcodes mit niedriger Dichte. MIT Press, 1963
IE Bocharova, F. Hug, R. Johannesson, BD Kudryashov und RV Satyukov. Neue Paritätsprüfcodes mit niedriger Dichte und großem Umfang basierend auf Hypergraphen. In Information Theory Proceedings (ISIT), IEEE International Symposium 2010, S. 819–823, 2010.
SC Tatikonda. Konvergenz des Summenproduktalgorithmus. In Information Theory Workshop, 2003. Verfahren. 2003 IEEE, Seiten 222 - 225, 2003
David JC MacKay und RM Neal. In der Nähe von Shannon ist die Leistung von Paritätsprüfcodes mit niedriger Dichte begrenzt. Electronics Letters, 33 (6): 457–458, 1997.

Klopfen
quelle

3

Eine erfolgreiche Anwendung von Graph-Algorithmen auf probabilistische graphische Modelle ist der Chow-Liu-Algorithmus . Es löst das Problem, die optimale (Baum-) Graphstruktur zu finden, und basiert auf dem Maximum-Spanning-Tree- (MST-) Algorithmus.

Eine gemeinsame Wahrscheinlichkeit über ein grafisches Baummodell kann wie geschrieben werden: Wir können eine normalisierte log-Wahrscheinlichkeit wie folgt aufschreiben: wobei die wechselseitige Information zwischen und wenn die empirische maximale Wahrscheinlichkeit (ML) gegeben ist Verteilung, die zählt, wie oft sich ein Knoten im Zustand . Da der erste Term unabhängig von der Topologie

p (x | T) = \prod_{t \in V} p (x_{t}) \prod_{(s, t) \in E} \frac{p (x_{s}, x_{t})}{p (x_{s}) p (x_{t})}

$\begin{equation} p(x|T) = \prod_{t\in V} p(x_t) \prod_{(s,t) \in E} \frac{p(x_s, x_t)}{p(x_s)p(x_t)} \end{equation}$

\frac{1}{N} \log P (D | θ, T) = \sum_{t \in V} \sum_{k} p_{M L} (x_{t} = k) \log p_{M L} (x_{t} = k) + \sum_{(s, t) \in E} I (x_{s}; x_{t} | θ_{s t})

$\begin{equation} \frac{1}{N}\log P(D|\theta, T) = \sum_{t\in V}\sum_k p_{ML}(x_t=k) \log p_{ML}(x_t=k) + \sum_{(s,t)\in E} I(x_s; x_t|\theta_{st}) \end{equation}$

I (x_{s}; x_{t} | θ_{s t})

$I(x_s;x_t|\theta_{st})$

x_{s}

$x_s$

x_{t}

$x_t$

x

$x$

k

$k$

T

$T$ können wir es ignorieren und uns auf die Maximierung des zweiten Terms konzentrieren.

Die logarithmische Wahrscheinlichkeit wird maximiert, indem der maximale Gewichtsüberspannungsbaum berechnet wird, wobei die Kantengewichte die paarweisen gegenseitigen Informationsterme . Der maximale Gewichtsspannungsbaum kann unter Verwendung des Prim-Algorithmus und des Kruskal-Algorithmus ermittelt werden . $I(x_s;x_t|\theta_{st})$

Vadim Smolyakov
quelle

Hallo Vadim. Vielen Dank für Ihre Antwort. Als graphentheoretische Formulierung ist dies sinnvoll. Man könnte es aber auch als Optimierungsproblem ansehen. Der Sinn der Frage bestand darin, einen grundlegenderen Zusammenhang zu untersuchen. Beispielsweise kann man das Sortierproblem als topologische Sortierung in einem Graphen formulieren, wobei die Knoten Zahlen sind und Pfeile <= Beziehung bezeichnen. Damit ist aber kein grundlegender Zusammenhang zwischen Sortier- und Grafikalgorithmen hergestellt, oder?

Vimal

Wo ist die Graphentheorie in grafischen Modellen?

Antworten: