Convergence analysis of herded-Gibbs-type sampling algorithms: effects of weight sharing
Convergence analysis of herded-Gibbs-type sampling algorithms: effects of weight sharing
复制标题
群体吉布斯型采样算法的收敛性分析：权重共享的影响
DOI：
10.1007/s11222-019-09852-6
复制
发表时间：
2019
影响因子：
2.2
通讯作者：
Suzuki Hideyuki
中科院分区：
文献类型：
--
作者：
Yamashita Hiroshi;Suzuki Hideyuki
群体吉布斯（HG）和离散群体吉布斯（DHG）是吉布斯采样与羊群相结合的方法，是针对具有离散随机变量的马尔可夫随机场的确定性采样算法。在本文中，我们引入“权重共享”的概念来系统地看待这些 HG 型算法，并从理论上和数值上研究了它们的收敛性。我们表明，通过共享和减少权重变量的数量，HG 型算法以渐近收敛为代价实现了快速初始收敛。这意味着HG型算法实际上比传统的马尔可夫链蒙特卡罗算法更有效，尽管其估计不一定渐近收敛于目标。此外，我们将 HG 类型算法的数值积分误差分解为多个分量，并评估每个分量与羊群效应和权重共享的关系。通过使用这个公式，我们还提出了 HG 型算法的新变体，以减少渐近偏差。
Herded Gibbs (HG) and discretized herded Gibbs (DHG), which are Gibbs samplings combined with herding, are deterministic sampling algorithms for Markov random fields with discrete random variables. In this paper, we introduce the notion of “weight sharing” to systematically view these HG-type algorithms, and also investigate their convergence theoretically and numerically. We show that, by sharing and reducing the number of weight variables, the HG-type algorithm achieves fast initial convergence at the expense of asymptotic convergence. This means that the HG-type algorithm can be practically more efficient than conventional Markov chain Monte Carlo algorithms, although its estimate does not necessarily converge to the target asymptotically. Moreover, we decompose the numerical integration error of HG-type algorithms into several components and evaluate each of them in relation to herding and weight sharing. By using this formulation, we also propose novel variants of the HG-type algorithm that reduce the asymptotic bias.