貝葉斯網絡中的變量消除

Question

我們最近研究了變量消除，老師強調它是貝葉斯網絡使得消除變差效率更高。 我對此有點困惑，爲什麼會出現這種情況？ 希望你們能給我一些想法，非常感謝。

羅伯特

Answer 1

我想這是因爲它可以消除一個變量是其有且只有一個變量，它是依賴於它。在貝葉斯網絡中，這些將很容易找到，因爲它們是單個孩子的節點。

Answer 2

貝葉斯網絡可以利用變量消除的順序的，因爲內置於條件獨立性假設。

具體地，想象具有聯合分佈P（A，B，C，d）和想知道的邊際P（a）。如果你對條件獨立性一無所知，你可以通過對b，c和d進行求和來計算。如果這些具有k-ary域，則需要執行O（k^3）操作。

另一方面，假設你有一個貝氏網，其中A是根，B是A的孩子，C是B的孩子，D是C的孩子。然後，你可以重寫關節作爲P（a | b）P（b | c）P（c | d）P（d）並且儘可能地將你的三個總和分配到等式的右邊。當你真的想計算P（a）時，你可以預先計算sum_d P（d）的值並存儲這個函數。同樣，您可以預先計算P（c | d）* sum_d P（d）的值並存儲它。

通過這種方式，您最終可以完成O（k^w * + 1）的工作，其中W *是貝葉斯網絡中任何節點的最大子數。在這種情況下，我們做O（k^2）的工作，這也是我們必須保留在內存中的最大條件概率表的大小。請注意，這比我們原來的O（k^3）結果要好，如果我們有更多的變量，情況會更好。

簡而言之，BN的條件獨立性允許您更有效地排除變量。對此的另一個解釋可以在http://www.cs.uiuc.edu/class/sp08/cs440/notes/varElimLec.pdf找到。