Cube Summing, Approximate Inference with Non-Local Features, and Dynamic Programming without Semirings
Cube Summing, Approximate Inference with Non-Local Features, and Dynamic Programming without Semirings
复制标题
DOI：
10.3115/1609067.1609102
复制
发表时间：
2009-03
期刊：
影响因子：
--
通讯作者：
Kevin Gimpel;Noah A. Smith
中科院分区：
文献类型：
--
作者：
Kevin Gimpel;Noah A. Smith
我们介绍了立方求和，这种技术允许对结构求和的动态规划算法（如正向和内部算法）进行扩展，使其具有违反经典结构独立性假设的非局部特征。它的灵感来自立方体剪枝（Chiang, 2007; Huang and Chiang, 2007），它使用评分的k-best列表动态计算非局部特征，但也保留了用于计算近似边际的额外残余量。当局限于局部特征时，立方体求和简化为一种新的半环（k-best+残差），它推广了Goodman（1999）的许多半环。当包含非局部特征时，立方体求和不会简化为任何半环，而是与求解动态规划方程的通用技术兼容。
We introduce cube summing, a technique that permits dynamic programming algorithms for summing over structures (like the forward and inside algorithms) to be extended with non-local features that violate the classical structural independence assumptions. It is inspired by cube pruning (Chiang, 2007; Huang and Chiang, 2007) in its computation of non-local features dynamically using scored k-best lists, but also maintains additional residual quantities used in calculating approximate marginals. When restricted to local features, cube summing reduces to a novel semiring (k-best+residual) that generalizes many of the semirings of Goodman (1999). When non-local features are included, cube summing does not reduce to any semiring, but is compatible with generic techniques for solving dynamic programming equations.