为什么在网格图中不可能精确推断MRF

Question

问题如标题所示。

​

​

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

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

Answer 1

简而言之:对于n×n网格，复杂度至少是指数n。

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

因此，即使我们可以在连接树上使用精确的推理，但在所使用的排除顺序的诱导图中，复杂性将是最大团的指数大小。

最佳可能的消除顺序将产生与树宽度相等的最大集团大小，对于n×n网格，该宽度为n。但目前还没有有效的算法来找到它。