Provable benefits of annealing for estimating normalizing constants: Importance Sampling, Noise-Contrastive Estimation, and beyond
Provable benefits of annealing for estimating normalizing constants: Importance Sampling, Noise-Contrastive Estimation, and beyond
复制标题
DOI：
10.48550/arxiv.2310.03902
复制
发表时间：
2023-10
期刊：
影响因子：
--
通讯作者：
O. Chehab;Aapo Hyvarinen;Andrej Risteski
中科院分区：
文献类型：
--
作者：
O. Chehab;Aapo Hyvarinen;Andrej Risteski
最近的研究已经开发了几种基于退火思想的蒙特卡罗方法来估计归一化常数（配分函数）。这意味着从一条分布路径中连续采样，该分布路径介于易处理的“建议“分布和未规范化的“目标“分布之间。在这个家庭中的突出估计包括退火重要性抽样和退火噪声对比估计（NCE）。这些方法取决于许多设计选择：使用哪种估计量，使用哪种分布路径以及是否使用路径;到目前为止，还没有关于哪些选择是有效的确定理论。在这里，我们通过它产生的渐近估计误差来评估每个设计选择。首先，我们表明，使用NCE是更有效的重要性抽样估计，但在无限小的路径步骤的限制，差异消失。其次，我们发现，使用几何路径带来的估计误差从一个指数到一个多项式函数的参数之间的距离的目标和建议的分布。第三，我们发现算术路径虽然很少被使用，但它比普遍使用的几何路径具有更好的最优性，事实上，在特定的限制下，最优路径是算术路径。基于此理论，我们最后提出了一个两步估计近似的最佳路径，在一个有效的方式。
Recent research has developed several Monte Carlo methods for estimating the normalization constant (partition function) based on the idea of annealing. This means sampling successively from a path of distributions that interpolate between a tractable"proposal"distribution and the unnormalized"target"distribution. Prominent estimators in this family include annealed importance sampling and annealed noise-contrastive estimation (NCE). Such methods hinge on a number of design choices: which estimator to use, which path of distributions to use and whether to use a path at all; so far, there is no definitive theory on which choices are efficient. Here, we evaluate each design choice by the asymptotic estimation error it produces. First, we show that using NCE is more efficient than the importance sampling estimator, but in the limit of infinitesimal path steps, the difference vanishes. Second, we find that using the geometric path brings down the estimation error from an exponential to a polynomial function of the parameter distance between the target and proposal distributions. Third, we find that the arithmetic path, while rarely used, can offer optimality properties over the universally-used geometric path. In fact, in a particular limit, the optimal path is arithmetic. Based on this theory, we finally propose a two-step estimator to approximate the optimal path in an efficient way.