期刊名称：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.
