Eliminacja zmienna - Variable elimination

Eliminacja zmiennych (VE) jest prostym i ogólnym algorytmem dokładnego wnioskowania w probabilistycznych modelach graficznych , takich jak sieci bayesowskie i pola losowe Markowa . Może być używany do wnioskowania o stanie maksimum a posteriori (MAP) lub estymacji rozkładów warunkowych lub krańcowych na podzbiorze zmiennych. Algorytm ma wykładniczą złożoność czasową, ale może być skuteczny w praktyce dla grafów o małej szerokości drzewa , jeśli zastosuje się odpowiednią kolejność eliminacji.

Czynniki

Umożliwiający kluczową redukcję złożoności algorytmicznej, czynnik , znany również jako potencjał zmiennych, jest relacją między każdym wystąpieniem zmiennych do liczby nieujemnej, powszechnie oznaczanej jako . Czynnik niekoniecznie ma ustaloną interpretację. Można wykonywać operacje na czynnikach o różnych reprezentacjach, takich jak rozkład prawdopodobieństwa lub rozkład warunkowy. Wspólne dystrybucje często stają się zbyt duże, aby je obsłużyć, ponieważ złożoność tej operacji jest wykładnicza. W ten sposób eliminacja zmiennych staje się bardziej realna przy obliczaniu jednostek podzielonych na czynniki. ${\displaystyle f}$${\ Displaystyle V}$${\displaystyle v}$${\displaystyle f}$${\displaystyle f(x)}$

Podstawowe operacje

Zmienna sumowanie

Algorytm 1, zwany sum-out (SO) lub marginalizacją, eliminuje pojedynczą zmienną ze zbioru czynników i zwraca wynikowy zbiór czynników. Algorytm zbieraj istotne po prostu zwraca te czynniki, w których bierze udział zmienna . ${\displaystyle v}$${\displaystyle \phi}$${\displaystyle \phi}$${\displaystyle v}$

Algorytm 1 suma ( , ) ${\displaystyle v}$${\displaystyle \phi}$

${\ Displaystyle \ Phi}$ = zbierz czynniki istotne dla ${\displaystyle v}$

${\ Displaystyle \ psi}$ = iloczyn wszystkich czynników w ${\ Displaystyle \ Phi}$

${\ Displaystyle \ tau = \ suma _ {v} \ psi}$

powrót ${\ Displaystyle (\ phi - \ Phi ) \ filiżanka \ {\ tau \}}$

Przykład

Tutaj mamy wspólny rozkład prawdopodobieństwa . Zmienna może być sumowana pomiędzy zbiorem instancji, w których zbiór jako minimum musi zgadzać się z pozostałymi zmiennymi. Wartość of jest nieistotna, gdy jest to zmienna do zsumowania. ${\displaystyle v}$${\ Displaystyle Vv}$${\displaystyle v}$

${\displaystyle V_{1}}$	${\displaystyle V_{2}}$	${\displaystyle V_{3}}$	${\displaystyle V_{4}}$	${\ Displaystyle V_ {5}}$	${\ Displaystyle Pr(.)}$
prawda	prawda	prawda	fałszywe	fałszywe	0,80
fałszywe	prawda	prawda	fałszywe	fałszywe	0,20

Po wyeliminowaniu jego odwołanie jest wykluczone i zostaje nam rozkład tylko na pozostałe zmienne oraz suma każdej instancji. ${\displaystyle V_{1}}$

${\displaystyle V_{2}}$	${\displaystyle V_{3}}$	${\displaystyle V_{4}}$	${\ Displaystyle V_ {5}}$	${\ Displaystyle Pr(.)}$
prawda	prawda	fałszywe	fałszywe	1,0

Wynikowy rozkład, który następuje po operacji sumowania, pomaga tylko odpowiedzieć na zapytania, które nie zawierają . Warto również zauważyć, że operacja sumowania jest przemienna. ${\displaystyle V_{1}}$

Mnożenie czynników

Obliczenie iloczynu między wieloma czynnikami daje w wyniku czynnik zgodny z pojedynczą instancją w każdym czynniku.

Algorytm 2 mnożniki ( , ) ${\displaystyle v}$${\displaystyle \phi}$

${\ Displaystyle Z}$ = Suma wszystkich zmiennych między iloczynem czynników ${\ Displaystyle f_ {1}(X_ {1}), ..., f_ {m} (X_ {m})}$

${\displaystyle f}$= współczynnik gdzie dla wszystkich ${\displaystyle f}$${\displaystyle f}$${\displaystyle f}$

Dla każdej instancji${\displaystyle z}$

Od 1 do${\ Displaystyle m}$

${\displaystyle x_{1}=}$instancja zmiennych zgodnych z${\displaystyle X_{1}}$${\displaystyle z}$

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

powrót ${\displaystyle f}$

Mnożenie współczynników jest nie tylko przemienne, ale także łączne.

Wnioskowanie

Najpopularniejszym typem zapytania jest forma gdzie i są rozłącznymi podzbiorami i obserwuje się, że przyjmuje wartość . Podstawowy algorytm obliczania p(X|E = e) nazywa się eliminacją zmiennych (VE), po raz pierwszy przedstawiony w. ${\ Displaystyle p (X | E = e)}$${\ Displaystyle X}$${\ Displaystyle E}$${\ Displaystyle U}$${\ Displaystyle E}$${\displaystyle e}$

Zaczerpnięty z tego algorytmu oblicza z dyskretnej sieci bayesowskiej B. VE wywołuje SO, aby wyeliminować zmienne jedna po drugiej. Dokładniej, w Algorytmie 2, czy zbiór C warunkowych tabel prawdopodobieństwa (odtąd „CPT”) dla B, jest listą zmiennych zapytania, jest listą obserwowanych zmiennych, jest odpowiednią listą obserwowanych wartości i jest eliminacją. porządkowanie dla zmiennych , gdzie oznacza . ${\ Displaystyle p (X | E = e)}$${\displaystyle \phi}$${\ Displaystyle X}$${\ Displaystyle E}$${\displaystyle e}$${\displaystyle \sigma}$${\ Displaystyle U-XE}$${\ Displaystyle XE}$${\ Displaystyle X \ filiżanka E}$

Algorytm eliminacji zmiennych VE( ) ${\displaystyle \phi,X,E,e,\sigma}$

Pomnóż współczynniki przez odpowiednie CPT, gdy σ nie jest puste

Usuń pierwszą zmienną z${\displaystyle v}$${\displaystyle \sigma}$

${\displaystyle \phi}$ = suma${\displaystyle (v,\phi)}$

${\ Displaystyle p (X, E = e)}$ = iloczyn wszystkich czynników ${\ Displaystyle \ psi \ w \ phi}$

powrót ${\ Displaystyle p (X, E = e) / \ suma _ {X} p (X, E = e)}$

Zamawianie

Znalezienie optymalnej kolejności eliminacji zmiennych jest problemem NP-trudnym. W związku z tym istnieją heurystyki, które można zastosować, aby lepiej zoptymalizować wydajność według kolejności:

1. Minimalny stopień : Wyeliminuj zmienną, która powoduje skonstruowanie najmniejszego możliwego współczynnika.
2. Minimalne wypełnienie: Konstruując nieskierowany wykres przedstawiający relacje zmiennych wyrażone przez wszystkie CPT, wyeliminuj zmienną, która spowoduje, że po eliminacji zostanie dodana najmniejsza krawędź.

Bibliografia