问题如标题所述

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

当网格变大时，是否无法找到这样的连接树？

回答：

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

连接树是从MRF的诱导图创建的，这取决于消元顺序（你首先消除哪些变量来计算边缘分布）。消元成本在诱导图中最大团的大小上是指数级的。详见这篇论文。

因此，尽管我们可以在连接树上使用精确推断，但复杂度将是所使用消元顺序的诱导图中最大团大小的指数级。

最佳的消元顺序将产生一个最大团大小等于树宽的诱导图，对于n x n的网格，树宽为n。但没有有效的算法来找到它。