文章基本信息

标题：Cube Summing, Approximate Inference with Non-Local Features, and Dynamic Programming without Semirings
本地全文：下载
作者：Kevin Gimpel ; Noah A. Smith
期刊名称：Conference on European Chapter of the Association for Computational Linguistics (EACL)
出版年度：2009
卷号：2009
出版社：ACL Anthology
摘要：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.