Stochastic Integration via Error-Correcting Codes
Stochastic Integration via Error-Correcting Codes
复制标题
通过纠错码进行随机积分
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Pei Jiang
中科院分区：
文献类型：
--
作者：
D. Achlioptas;Pei Jiang
我们考虑对离散集Ω上的非负函数f求和的任务，例如，计算图形模型的配分函数。Ermon等人已经证明，在概率近似意义上，求和可以简化为在由奇偶性（XOR）约束定义的Ω的随机子集上最大化f。不幸的是，具有许多变量的xor在计算上难以处理，而具有很少变量的xor在统计性能上很差。我们引入了两个想法来解决这个问题，这两个想法都是由纠错码理论激发的。首先是在显式生成的Ω的随机仿射子空间上最大化f，这相当于在指数较小的域上无限制地最大化f。第二个想法，在精神上更接近最初的方法，是使用线性方程组来定义低密度奇偶校验（LDPC）纠错码。尽管这种系统中的方程每个只包含O(1)个变量，但它们的解集（码字）具有出色的统计特性。通过结合这些想法，我们实现了比原始方法更快的速度和完全无法达到的精度水平。
We consider the task of summing a non-negative function f over a discrete set Ω, e.g., to compute the partition function of a graphical model. Ermon et al. have shown that in a probabilistic approximate sense summation can be reduced to maximizing f over random subsets of Ω defined by parity (XOR) constraints. Unfortunately, XORs with many variables are computationally intractable, while XORs with few variables have poor statistical performance. We introduce two ideas to address this problem, both motivated by the theory of error-correcting codes. The first is to maximize f over explicitly generated random affine subspaces of Ω, which is equivalent to unconstrained maximization of f over an exponentially smaller domain. The second idea, closer in spirit to the original approach, is to use systems of linear equations defining Low Density Parity Check (LDPC) error-correcting codes. Even though the equations in such systems only contain O(1) variables each, their sets of solutions (codewords) have excellent statistical properties. By combining these ideas we achieve dramatic speedup over the original approach and levels of accuracy that were completely unattainable.