Approximate survey propagation for statistical inference
Approximate survey propagation for statistical inference
复制标题
DOI：
10.1088/1742-5468/aafa7d
复制
发表时间：
2019-02-01
影响因子：
2.4
通讯作者：
Zdeborova, Lenka
中科院分区：
文献类型：
--
作者：
Antenucci, Fabrizio;Krzakala, Florent;Zdeborova, Lenka
近似消息传递算法在过去的十年中受到了广泛的关注。在本文中，我们介绍了一个变体的AMP算法，考虑到玻璃的性质所考虑的系统。我们把这种算法称为近似调查传播（ASP），并推导出它的一类低秩矩阵估计问题。我们推导出ASP算法的状态演化，并证明它再现了一步复制对称破缺（1RSB）不动点方程，众所周知的无序系统的物理。因此，我们的推导给出了一个具体的算法意义的1RSB方程是独立的利益。我们的ASP的性能的收敛性和均方误差作为一个功能的自由Parisi参数s。我们的结论是，当真实生成模型和推理模型之间存在模型失配时，AMP的性能在MSE和收敛性方面都迅速下降，而对于精心选择的Parisi参数值，ASP在更大的范围内收敛，并且可以达到更低的误差。在其他结果中，我们的分析使我们得出一个惊人的假设，即只要s（或其他参数）可以以恢复Nishimori条件M = Q > 0的方式设置，则相应的算法能够达到与模型及其参数已知并在推理过程中精确匹配时获得的贝叶斯最优误差一样低的均方误差。剩下的缺点是，我们还没有找到一个程序，将系统地找到一个值的s导致如此低的错误，这是一个具有挑战性的问题，让未来的工作。
Approximate message passing algorithm enjoyed considerable attention in the last decade. In this paper we introduce a variant of the AMP algorithm that takes into account glassy nature of the system under consideration. We coin this algorithm as the approximate survey propagation (ASP) and derive it for a class of low-rank matrix estimation problems. We derive the state evolution for the ASP algorithm and prove that it reproduces the one-step replica symmetry breaking (1RSB) fixed-point equations, well-known in physics of disordered systems. Our derivation thus gives a concrete algorithmic meaning to the 1RSB equations that is of independent interest. We characterize the performance of ASP in terms of convergence and mean-squared error as a function of the free Parisi parameter s. We conclude that when there is a model mismatch between the true generative model and the inference model, the performance of AMP rapidly degrades both in terms of MSE and of convergence, while for well-chosen values of the Parisi parameter s ASP converges in a larger regime and can reach lower errors. Among other results, our analysis leads us to a striking hypothesis that whenever s (or other parameters) can be set in such a way that the Nishimori condition M = Q > 0 is restored, then the corresponding algorithm is able to reach mean-squared error as low as the Bayes-optimal error obtained when the model and its parameters are known and exactly matched in the inference procedure. The remaining drawback is that we have not found a procedure that would systematically find a value of s leading to such low errors, this is a challenging problem let for future work.