📄 Tensors over Semirings for Latent-Variable Weighted Logic Programs

Summary

The paper combines semiring parsing (Goodman, 1999) with latent-variable models. Weighted logic programs (WLPs) make it possible to describe parsers and dynamic programming algorithms declaratively. However, all of their weights must belong to a single set on which the operations are defined for every pair of values. Latent states are usually represented by vectors, matrices and higher-order tensors, and such objects taken together do not form a semiring. The authors propose to "latentify" any semiring WLP by replacing scalar weights with tensors over an arbitrary semiring. The algebraic foundation is accordingly relaxed to a partial semiring. For CFGs, they formulate a simple correctness condition: each nonterminal is assigned a fixed dimensionality. The authors prove that this generalization preserves the key properties of the original framework while strictly increasing its expressive power. They also derive the inside and outside computations, and the outside formulation accounts for the non-commutativity of tensor multiplication. The paper contains no experiments; its contribution is purely theoretical. It provides a common foundation for EM and spectral learning of latent refinements of grammars across different formalisms.

Key points

• For a rule A → B C, where the nonterminals A, B and C are assigned dimensionalities d1, d2 and d3, the weight is a tensor of size d2 × d3 × d1. Hence the order of the weight depends on the arity of the rule.
• The authors define the notion of a partial semiring somewhat differently from the algebraic literature (in particular, Steenstrup, 1985). If the weights are not dimensionally compatible, the value of the derivation is denoted by the special symbol ⊥.
• For a commutative semiring, they prove that the value of a full derivation equals the contraction of the inside value of a subtree with the outside value of the rest of the tree. For the goal item, the outside value is the identity tensor, and a permutation π aligns the order of the dimensions.
• The exposition focuses on CFGs, but the approach carries over to any weighted deductive system (TAG, CCG, LCFRS, machine translation) and is compatible with solvers such as Dyna.
• As motivation, the authors cite the result of Cohen et al. (2013): on the Penn Treebank, L-PCFGs achieve an F1 roughly 20% higher than PCFGs without latent states.