为什么无法精确推断网格图中的 MRF

Question

题目如题

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

是不是格子变大了就找不到这样的连接树了？

Answer 1

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

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

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

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