Variableneliminierung - Variable elimination

Variable Elimination (VE) ist ein einfacher und allgemeiner exakter Inferenzalgorithmus in probabilistischen grafischen Modellen wie Bayes-Netzwerken und Markov-Zufallsfeldern . Es kann zur Inferenz des maximalen a posteriori (MAP) Zustands oder zur Schätzung von bedingten oder marginalen Verteilungen über eine Untermenge von Variablen verwendet werden. Der Algorithmus hat eine exponentielle Zeitkomplexität, könnte aber in der Praxis für Graphen mit niedriger Baumbreite effizient sein , wenn die richtige Eliminationsreihenfolge verwendet wird.

Faktoren

Ein Faktor , der auch als Potenzial bezeichnet wird, ermöglicht eine wesentliche Reduzierung der algorithmischen Komplexität und ist eine Beziehung zwischen jeder Instanziierung von Variablen zu einer nicht negativen Zahl, die allgemein als bezeichnet wird . Ein Faktor hat nicht unbedingt eine festgelegte Interpretation. Man kann Operationen an Faktoren unterschiedlicher Darstellungen durchführen, wie etwa einer Wahrscheinlichkeitsverteilung oder einer bedingten Verteilung. Gemeinsame Verteilungen werden oft zu groß, um sie handhaben zu können, da die Komplexität dieser Operation exponentiell ist. Somit wird die Eliminierung von Variablen beim Berechnen von faktorisierten Entitäten machbarer. ${\displaystyle f}$${\displaystyle V}$${\displaystyle v}$${\displaystyle f}$${\displaystyle f(x)}$

Grundoperationen

Variable Summation

Algorithmus 1, Sum-out (SO) oder Marginalisierung genannt, eliminiert eine einzelne Variable aus einem Satz von Faktoren und gibt den resultierenden Satz von Faktoren zurück. Der Algorithmus Collect-relevant gibt diese Faktoren einfach zurück, wenn Variable einbezogen wird . ${\displaystyle v}$${\displaystyle \phi}$${\displaystyle \phi}$${\displaystyle v}$

Algorithmus 1 sum-out( , ) ${\displaystyle v}$${\displaystyle \phi}$

${\displaystyle \Phi}$ = Faktoren sammeln, die für relevant sind ${\displaystyle v}$

${\displaystyle \Psi}$ = das Produkt aller Faktoren in ${\displaystyle \Phi}$

${\displaystyle \tau =\sum_{v}\Psi}$

Rückkehr ${\displaystyle (\phi -\Phi)\cup \{\tau\}}$

Beispiel

Hier haben wir eine gemeinsame Wahrscheinlichkeitsverteilung . Eine Variable kann zwischen einer Menge von Instanziierungen summiert werden, wobei die Menge mindestens mit den verbleibenden Variablen übereinstimmen muss. Der Wert von ist irrelevant, wenn es sich um die auszusummierende Variable handelt. ${\displaystyle v}$${\displaystyle Vv}$${\displaystyle v}$

${\displaystyle V_{1}}$	${\displaystyle V_{2}}$	${\displaystyle V_{3}}$	${\displaystyle V_{4}}$	${\displaystyle V_{5}}$	${\displaystyle Pr(.)}$
wahr	wahr	wahr	falsch	falsch	0,80
falsch	wahr	wahr	falsch	falsch	0.20

Nach dem Eliminieren von wird seine Referenz ausgeschlossen und es bleibt nur eine Verteilung über die verbleibenden Variablen und die Summe jeder Instanziierung. ${\displaystyle V_{1}}$

${\displaystyle V_{2}}$	${\displaystyle V_{3}}$	${\displaystyle V_{4}}$	${\displaystyle V_{5}}$	${\displaystyle Pr(.)}$
wahr	wahr	falsch	falsch	1.0

Die resultierende Verteilung, die der Sum-out-Operation folgt, hilft nur bei der Beantwortung von Anfragen, die nicht erwähnen . Bemerkenswert ist auch, dass die Aufsummierungsoperation kommutativ ist. ${\displaystyle V_{1}}$

Faktormultiplikation

Die Berechnung eines Produkts zwischen mehreren Faktoren führt zu einem Faktor, der mit einer einzelnen Instanziierung in jedem Faktor kompatibel ist.

Algorithmus 2 Multifaktoren( , ) ${\displaystyle v}$${\displaystyle \phi}$

${\displaystyle Z}$ = Vereinigung aller Variablen zwischen Produkt von Faktoren ${\displaystyle f_{1}(X_{1}),...,f_{m}(X_{m})}$

${\displaystyle f}$= ein Faktor über wo für alle ${\displaystyle f}$${\displaystyle f}$${\displaystyle f}$

Für jede Instanziierung${\displaystyle z}$

Für 1 bis${\displaystyle m}$

${\displaystyle x_{1}=}$Instanziierung von Variablen konsistent mit${\displaystyle X_{1}}$${\displaystyle z}$

${\displaystyle f(z)=f(z)f_{i}(x_{i})}$

Rückkehr ${\displaystyle f}$

Die Faktormultiplikation ist nicht nur kommutativ, sondern auch assoziativ.

Inferenz

Der gebräuchlichste Abfragetyp liegt in der Form vor, wobei und getrennte Teilmengen von sind , und es wird beobachtet, dass er Wert nimmt . Ein grundlegender Algorithmus zur Berechnung von p(X|E = e) wird als Variableneliminierung (VE) bezeichnet und zuerst vorgestellt. ${\displaystyle p(X|E=e)}$${\displaystyle X}$${\displaystyle E}$${\displaystyle U}$${\displaystyle E}$${\displaystyle e}$

Dieser Algorithmus berechnet aus einem diskreten Bayesschen Netzwerk B. VE ruft SO auf, um Variablen nacheinander zu eliminieren. Genauer gesagt ist in Algorithmus 2 die Menge C von bedingten Wahrscheinlichkeitstabellen (im Folgenden "CPTs") für B, ist eine Liste von Abfragevariablen , ist eine Liste von beobachteten Variablen, ist die entsprechende Liste von beobachteten Werten und ist eine Elimination Reihenfolge für Variablen , wobei bezeichnet . ${\displaystyle p(X|E=e)}$${\displaystyle \phi}$${\displaystyle X}$${\displaystyle E}$${\displaystyle e}$${\displaystyle \sigma}$${\displaystyle U-XE}$${\displaystyle XE}$${\displaystyle X\cup E}$

Variableneliminationsalgorithmus VE( ) ${\displaystyle \phi,X,E,e,\sigma}$

Multiplizieren Sie Faktoren mit geeigneten CPTs, während σ nicht leer ist

Entfernen Sie die erste Variable aus${\displaystyle v}$${\displaystyle \sigma}$

${\displaystyle \phi}$ = Summe aus${\displaystyle (v,\phi)}$

${\displaystyle p(X,E=e)}$ = das Produkt aller Faktoren ${\displaystyle \Psi\in\phi}$

Rückkehr ${\displaystyle p(X,E=e)/\sum _{X}p(X,E=e)}$

Bestellung

Die optimale Reihenfolge zum Eliminieren von Variablen zu finden, ist ein NP-schweres Problem. Als solche gibt es Heuristiken, denen man folgen kann, um die Leistung nach Reihenfolge besser zu optimieren:

1. Mindestgrad : Eliminieren Sie die Variable, die zur Konstruktion des kleinstmöglichen Faktors führt.
2. Minimale Füllung: Durch Konstruieren eines ungerichteten Graphen, der die durch alle CPTs ausgedrückten Variablenbeziehungen zeigt, eliminieren Sie die Variable, die dazu führen würde, dass nach der Eliminierung die wenigsten Kanten hinzugefügt werden.

Verweise