A Novel Approach for Markov Random Field With Intractable Normalizing Constant on Large Lattices

The pseudo likelihood method of Besag (1974) has remained a popular method for estimating Markov random field on a very large lattice, despite various documented deficiencies. This is partly because it remains the only computationally tractable method for large lattices. We introduce a novel method to estimate Markov random fields defined on a regular lattice. The method takes advantage of conditional independence structures and recursively decomposes a large lattice into smaller sublattices. An approximation is made at each decomposition. Doing so completely avoids the need to compute the troublesome normalizing constant. The computational complexity is <i>O</i>(<i>N</i>), where <i>N</i> is the number of pixels in the lattice, making it computationally attractive for very large lattices. We show through simulations, that the proposed method performs well, even when compared with methods using exact likelihoods. Supplementary material for this article is available online.Besag（1974）提出的伪似然法（pseudo likelihood method），尽管已有诸多文献记录了其固有缺陷，但时至今日仍是超大规模格点上马尔可夫随机场（Markov random field）参数估计的主流方法。究其根源，该方法仍是当前针对大型格点唯一具备计算可行性的方案。本文提出一种全新的、适用于规则格点的马尔可夫随机场估计算法：该方法利用条件独立结构，将大型格点递归分解为若干小型子格点，每一步分解过程均引入近似处理，从而彻底规避了计算复杂棘手的归一化常数。该算法的计算复杂度为O(N)，其中N为格点内的像素总数，这使得其在超大规模格点场景下具备极佳的计算吸引力。本文通过仿真实验证明，即便与基于精确似然的方法相比，所提算法仍能取得优异的性能表现。本文补充材料可在线获取。