On statistical inference when fixed points of belief propagation are unstable
On statistical inference when fixed points of belief propagation are unstable
复制标题
DOI：
10.1109/focs52979.2021.00047
复制
发表时间：
2021-01
期刊：
影响因子：
--
通讯作者：
Siqi Liu;Sidhanth Mohanty;P. Raghavendra
中科院分区：
文献类型：
--
作者：
Siqi Liu;Sidhanth Mohanty;P. Raghavendra
许多统计推断问题对应于从稀疏观测值中恢复一组隐藏变量的值。例如，在种植的约束满意度问题（例如种植的3个SAT）中，该子句是稀疏的观察结果，可以从中恢复隐藏的分配。在随机块模型中的社区检测问题中，社区标签是隐藏的变量，这些变量将从图的边缘恢复。受统计物理学的想法的启发，人们广泛猜想了稳定的信念式固定点的存在，以表征这些问题的计算障碍。对于随机块模型中的社区检测，许多这些预测已被严格确认。在这项工作中，我们考虑了统计推断问题的一般模型，其中包括随机块模型中的社区检测，又包括所有种植的约束满意度问题。我们执行从统计物理学的空腔方法计算，以计算应在算法上进行检测和恢复的参数状态。准确地是可预测的可拖动状态，我们给出：（i）检测问题的一般多项式时间算法：区分没有种植信号的输入与没有一个没有一个的信号的输入； （ii）用于恢复问题的一般多项式时间算法：输出与隐藏分配相关的向量明显好于随机猜测。类似于用于社区检测的光谱算法[1]，[2]，检测和恢复算法基于作为信念传播更新规则的衍生物产生的矩阵的光谱。为了在我们的通用模型中设计一种光谱算法，我们获得了具有相关和基质值条目的某些随机矩阵家族的光谱规范的界限。然后，我们演示了如何使用矩阵的各种幂的特征向量来部分恢复隐藏的变量。
Many statistical inference problems correspond to recovering the values of a set of hidden variables from sparse observations on them. For instance, in a planted constraint satisfaction problem such as planted 3-SAT, the clauses are sparse observations from which the hidden assignment is to be recovered. In the problem of community detection in a stochastic block model, the community labels are hidden variables that are to be recovered from the edges of the graph. Inspired by ideas from statistical physics, the presence of a stable fixed point for belief propogation has been widely conjectured to characterize the computational tractability of these problems. For community detection in stochastic block models, many of these predictions have been rigorously confirmed. In this work, we consider a general model of statistical inference problems that includes both community detection in stochastic block models, and all planted constraint satisfaction problems as special cases. We carry out the cavity method calculations from statistical physics to compute the regime of parameters where detection and recovery should be algorithmically tractable. At precisely the predicted tractable regime, we give: (i) a general polynomial-time algorithm for the problem of detection: distinguishing an input with a planted signal from one without; (ii) a general polynomial-time algorithm for the problem of recovery: outputting a vector that correlates with the hidden assignment significantly better than a random guess would. Analogous to the spectral algorithm for community detection [1], [2], the detection and recovery algorithms are based on the spectra of a matrix that arises as the derivatives of the belief propagation update rule. To devise a spectral algorithm in our general model, we obtain bounds on the spectral norms of certain families of random matrices with correlated and matrix valued entries. We then demonstrate how eigenvectors of various powers of the matrix can be used to partially recover the hidden variables.