Tensors over Semirings for Latent-Variable Weighted Logic Programs (2020)

Abstract: Semiring parsing is an elegant framework for describing parsers by using semiring weighted logic programs. In this paper we present a generalization of this concept: latent-variable semiring parsing. With our framework, any semiring weighted logic program can be latentified by transforming weights from scalar values of a semiring to rank-n arrays, or tensors, of semiring values, allowing the modelling of latent-variable models within the semiring parsing framework. Semiring is too strong a notion when dealing with tensors, and we have to resort to a weaker structure: a partial semiring. We prove that this generalization preserves all the desired properties of the original semiring framework while strictly increasing its expressiveness.

## introduction weighted logic programming (wlp) is a declarative approach to specifying and reasoning about dynamic programming algorithms and chart parsers. wlp is a generalization of bottom-up logic programming where proofs are assigned weights by combining the weights of the axioms used in the proof, and the weight of a theorem is in turn calculated by combining the weights of all its possible proof paths. the combinatorial nature of this procedure makes weighted logic programs highly suitable for specifying dynamic programming algorithms. in particular, @xcite presents an elegant abstraction for specifying and computing parser values based on wlp where the values could be drawn from any complete semiring. this generalizes the case of boolean decision problems, probabilistic grammars with viterbi search and other quantities of interest such as the best derivation or 1 our definition of a partial semiring is slightly different than those in the abstract algebra literature e.g. @xcite . the set of all possible derivations. it is then possible to derive a general formulation of inside and outside calculations in a way that is agnostic to the particular semiring chosen. latent variable models have been an important component in the nlp toolbox. the central assumption in latent variable models is that the correlations between observed variables in the training data could be explained by unobserved, hidden variables. latent variables have been used with grammars such as probabilistic context-free grammars (pcfgs), where each node in the parse tree is represented using a vector of latent state probabilities that further extend the expressiveness of the grammar @xcite . the approach of adding latent variables to formal grammars have proven to be a fruitful one: in the context of pcfg parsing, @xcite show that latent variable pcfgs (l-pcfgs) perform on par with models hand-annotated with linguistically motivated features. @xcite report that on the penn treebank dataset, l-pcfgs trained with either em or a spectral algorithm provide a 20% increase in f1 over pcfgs without latent states. @xcite shows that the benefits of latent variables are not limited to pcfgs by successfully enriching both linear context-free rewriting systems and hybrid grammars with latent variables, and demonstrates their applicability on discontinuous constituent parsing. given the usefulness of latent variables, it would be desirable to have a generic inference mechanism for any latent variable grammar. wlps can represent inference algorithms for probabilistic grammars effectively. however, this does not trivially extend to latent-variable models because latent variables are often represented as vectors, matrices and higher-order tensors, and these taken together no longer form a semiring. this is because in the semiring framework, values for deduction items and for rules must all come from the same set, and the semiring operations must be defined over all pairs of values from this set. this does not allow for letting different grammar nonterminals be represented by vectors of different sizes. more importantly, it does not allow for a rule's value to be a tensor whose dimensionality depends on the rule's arity, as is generally the case in latent variable frameworks. in this paper we start with a broad interpretation of latent variables as tensors over an arbitrary semiring. while a set of tensors over semirings is no longer a semiring, we prove that if the set of tensors have certain matching dimensions for the set of grammar rules they are assigned to, then they fulfill all the desirable properties relevant for the semiring parsing framework. this paves the way to use wlps with latent variables, naturally improving the expressivity of the statistical model represented by the underlying wlp. introducing a semiring framework like ours makes it easier to seamlessly incorporate latent variables into any execution model for dynamic programming algorithms (or software such as dyna, @xcite , and other prolog-like/wlp-like solvers). we focus on cfg parsing, however the same latent variable techniques can be applied to any weighted deduction system, including systems for parsing tag, ccg and lcfrs, and systems for machine translation @xcite . the methods we present for inside and outside computation can be used to learn latent refinements of a specified grammar for any of these tasks with em @xcite , or used as a backbone to create spectral learning algorithms @xcite @xcite . ## main results takeaway we present a strict generalization of semiring weighted logic programming, with a particular focus on parser descriptions in wlp for context-free grammars. throughout, we utilize the correspondence between axioms and grammar rules, deductive proofs and grammar derivations, and derived theorems and strings. we assume that axioms/grammar rules come equipped with weights in the form of tensors over semiring values. the main issue with going from semirings to tensors over semiring values is that these weights need to be well defined in that any valid derivation should correspond to a sequence of well defined semiring operations. for cfgs, we give a straightforward condition that ensures this is the case. this essentially boils down to making sure that each non-terminal corresponds to a fixed vector space dimension. for example, if a corresponds to a space of d 1 dimensions, b to d 2 and c to d 3 , then a rule @xmath0. as long as the weights are well defined, the standard definitions for the value of a grammar derivation and a string according to a semiring weighted grammar extend to the case of tensors of semirings. weighted logic programming provides the means to declaratively specify an efficient algorithm to obtain these values of interest. in line with @xcite and @xcite we present precise conditions for when a partial-semiring wlp describes a correct parser. the value of the wlp formulation of parsing algorithms is that it provides a unified fashion in which dynamic programming algorithms can be extracted from the program description. this relies on the ability of a wlp to decompose the value of a proof to a combination of the values of the sub-proofs. specifically, given a derivation tree, a wlp description automatically provides algorithms for calculating the inside and outside values. we provide analogous algorithms for calculating the inside and outside values for partial-semiring wlps. our outside formulation addresses the noncommutative nature of tensors themselves, and could be extended to cases where the underlying semiring is non-commutative using the techniques presented by @xcite . ## related work the semiring characterization of possible values to assign to wlps gave rise to the formulation of a number of novel semirings. one novel semiring of interest for purposes of learning parameters is the generalized entropy semiring @xcite which can be used to calculate the kl-divergence between the distribution of derivations induced by two weighted logic programs. other two semirings of interest are expectation and variance semirings introduced by @xcite and @xcite . these utilize the algebraic structure to efficiently track quantities needed by the expectationmaximization algorithm for parameter estimation. their framework allows working with parameters in the form of vectors in r n for a fixed n, coupled with a scalar in @xmath1. the semiring value of a path is roughly calculated by the multiplication of the scalars and (appropriately weighted) addition of the vectors. this is in contrast with our framework where weights could be tensors of arbitrary rank rather than only vectors, and the values of paths are calculated via tensor multiplication. finally, @xcite extended the semiring framework to a more general algebraic structure with the purpose of incorporating nonlocal features. their extension comes at the cost that the new algebraic structure does not obey all the semiring axioms. our framework differs from theirs in that under reasonable conditions, tensors of semirings do behave fully like regular semirings. ## background and notation our formalism could be used to enrich any wlp that implements a dynamic programming algorithm, but for simplicity, we follow @xcite and focus our presentation on parsers with a context-free backbone. foot_0 ## latent-variable parsing as tensor weighted logic programs for semiring parsing to work for latent-variable models it should allow weights to be vectors, matrices and tensors. in this section we present a framework that generalizes that of @xcite , and is able to capture tensors over semirings as weights. note that this includes scalars as a special case. ## inside and outside calculations in the following, we will omit the sentence σ from inner σ (x) and refer to this as inner(x). let inner( a 1 ,..,a k x ) the set of derivation trees where the root note is x, and the direct children of x are a 1 , . . . , a k . for efficient computation of this value, we will assume that there is a partial order b on the items so that if the item y depends on x, then b(x) ≤ b(y). theorem 6.1. the proof uses the distributive property and follows that of @xcite . it can be found in appendix a. for the notion of a value of a derivation to extend to outside trees, we will have to do some modifications. this is because an outside tree will have one subtree b : a 1 , . . . , a n , such that v (a 1 ) ⊗ [v (a 2 ), . . . , v (a n )] will potentially not be defined since one of the subtrees a k will be missing. note that the missing a k will be headed by an item. we will say the a tree @xmath2. outer value z(t k ) is defined recursively as follows: if t k is headed by the goal item then z(t k ) = i d s . else, it has a direct parent tree t such that @xmath3: t 1 , . . . , t k , . . . , t n . in this case, z(t to understand the function of π it is useful to consider the dimensions of the term before and after it is applied. let the term v (t 0 ) ⊗ k [i t k ×d s , v (t k+1 ), . . . , v (t n )] have dimensions: here e 1 , . . . , e k-1 are the dimensions that will be contracted with v (t 1 ), . . . , v (t k-1 ) with the second multiplication operation, and d n , . . . , d m are the dimensions that were either introduced by the contraction with v (t k+1 ), . . . , v (t n ) or were trailing dimensions from v (t 1 ). the result of the contraction with i t k ×d s are the dimensions in the middle: d 1 , . . . , d i , d s , e k , d 1 , . . . , d i , d s . unlike the original definition of i there is one dimension e k missing from the beginning of the sequence since it got used up during the contraction operation. what the permutation does is to move one section of the dimensions introduced by i to the very end. the dimensions become: note that this has no effect on the next contraction with v (t 1 ), . . . , v (t k-1 ) since the first k-1 ranks are left in place. however, changing the order of the ranks allow the last contraction with z(t ) to be well defined. lemma 6.2. let v and z be defined on a commutative semiring s and let @xmath4. if combining o and t in the obvious way results in the complete derivation d, proof. (sketch) we proceed by induction on the parse tree. base case is where @xmath5, @xmath6. then v (t ) = v (d) and z(o) = i s . v (d) ⊗ * i @xmath7. otherwise t has a parent tree t @xmath8: t 1 , . . . , t n where @xmath9. furthermore, t @xmath10, o @xmath11 the proof progresses by calculating the value for [v (d)] i based on the above term and shows that this is equal to the value of [v (t ) ⊗ * z(o)] i . full proof can be found in appendix a. in the general case, @xcite defines the reverse value of x as the sum of all its outer trees. ## conclusion we have presented a general extension of the semiring parsing framework where the weights for the grammar rules are tensors of semiring values, with the motivation of extending semiring parsing framework to latent variable models. we hope that this work will enable streamlined development of embased or spectral learning algorithms for latent refinements of a number of grammar formalisms. which completes the proof. the last simplification step is obtained by replacing êk and e k with e k , dk and d k with d k and s and s with ŝ since these need to be equal for any term to contribute to the final sum. the commutativity of s then allows v (t k ) e k ,d k to be moved to its place in the sequence. otherwise the outer trees outer(x) could be written as the union of outer trees outer k, a 1 ...an b for each rule a 1 ...an b where a @xmath12. hence: z(x) = j,a 1 ,..,a k ,b s.t. a 1 ...a k b and @xmath13, a 1 ...an b ) z(d) for the inner part of this equation we have: and since v (a i ) and z(d b ) are defined as the summation of their inner and outer trees respectively