Variable Elimination Algorithm

Algorytm dokładny na wnioskowanie bayesowskie (Bayesian inference) w Graphical Model. Może być użyty do wnioskowania nt. Maximum a posteriori, conditional probability, marginal probability.

Przykładowo, gdyby chcieć policzyć marginal distribution to w ogólności musimy zrobić tak: $p(y=1)={\sum }_{x_1}{\sum }_{x_2}\dots {\sum }_{x_n}p(y=1,x_1,x_2,\dots ,x_n)$co stanowi bardzo dużo obliczeń. Algorytm, wykorzystując strukturę grafu prawdopodobieństw, pozwala przyspieszyć obliczenia, poprzez poprzestawianie działań (ustawienie kolejności sum i mnożenia).

Na szybkość obliczeń wpływa kolejność w jakiej wykonywanej są kroki (jest to kluczowe) - znalezienie optymalnej kolejności jest NP-trudne, wykorzystywane są heurystyki, które działają dobrze.

Factors

Factor możemy sobie wyobrazić jako tablicę, które przypisuje wartość konkretnym wartościowaniom kilku zmiennych, np.

first variable	second variable	third variable	value
$a_1$	$b_1$	$c_1$	0.1
$a_2$	$b_2$	$c_2$	0.23

Zakładamy, że mamy model graficzny dany jako produkt factorów: $p(x_1,\dots ,x_n)={\prod }_{c\in C}{\varphi }_c(x_c)$

Źródło: CS 228 - Probabilistic Graphical Models.