machine-learning - 为什么网格图中 MRF 的精确推断是不可能的

Question

问题如标题中所写

上图中有一个 3x3 的网格图。我们可以将其转换为连接树。然后可以使用消息传递（积和算法）进行推理（估计似然性/后验等）。所以我想知道为什么网格图中的精确推断如此困难？

当网格变大时，是否不可能找到这样的连接树？

Answer 1

简短的回答：对于 nxn 网格，复杂性至少是指数 n。

从 MRF 的诱导图创建连接树，这取决于消除顺序（您首先消除哪些变量以计算边际）。消除成本与诱导图中最大集团的大小成指数关系。有关详细信息，请参阅本文。

因此，即使我们可以在联结树上使用精确推断，复杂度在所使用的消除顺序的诱导图中的最大团的大小上也是指数级的。

最佳可能的消除顺序将产生等于树宽度的最大团大小，对于 nxn 网格，它是 n。但是没有找到它的有效算法。