Dynamic Programming in Rank Space: Scaling Structured Inference with Low-Rank HMM s and PCFG s (2022)

Abstract: Hidden Markov Models (HMMs) and Probabilistic Context-Free Grammars (PCFGs) are widely used structured models, both of which can be represented as factor graph grammars (FGGs), a powerful formalism capable of describing a wide range of models. Recent research found it beneficial to use large state spaces for HMMs and PCFGs. However, inference with large state spaces is computationally demanding, especially for PCFGs. To tackle this challenge, we leverage tensor rank decomposition (aka. CPD) to decrease inference computational complexities for a subset of FGGs subsuming HMMs and PCFGs. We apply CPD on the factors of an FGG and then construct a new FGG defined in the rank space. Inference with the new FGG produces the same result but has a lower time complexity when the rank size is smaller than the state size. We conduct experiments on HMM language modeling and unsupervised PCFG parsing, showing better performance than previous work. Our code is publicly available at https://github.com/VPeterV/RankSpace-Models .

## introduction hidden markov models (hmms) and probabilistic context-free grammars (pcfgs) are widely used structured models in natural language processing. they can both be represented as factor graph grammars (fggs) @xcite , which are a powerful tool to describe a wide range of models, allowing exact and tractable inference in most situations of interest. over-parameterization has been shown beneficial in facilitating optimization of deep networks @xcite @xcite . @xcite found that overparameterization is also helpful in learning latent variable models by increasing the number of hidden states. @xcite argued that it is important to study over-parameterization in structured settings because structured latent variable models are more suitable to model real-word phenomena which exhibit complex dependencies. hmms and pcfgs are typical structured latent variable models, and recently researchers have found it beneficial to use large state spaces for hmms and pcfgs @xcite @xcite . however, structured inference with large state spaces is computationally demanding, especially for pcfgs, pushing researchers to develop methods to decrease the computational complexities. @xcite propose a neural vl-hmm with 2 15 states for language modeling, narrowing down the performance gap between hmms and lstms. they follow @xcite to impose a strong sparsity constraint (i.e., each hidden state can only generate a small subset of terminal symbols) to decrease the time complexity of the forward algorithm, thus requiring pre-clustering of terminal symbols. @xcite use a large state space for neural pcfg induction and achieve superior unsupervised constituency parsing performance. they follow @xcite to use tensor rank decomposition (aka. canonical-polyadic decomposition (cpd) @xcite ) to decrease the computational complexity of the inside algorithm, but only scale the state size from tens to hundreds because the resulting complexity is still high. @xcite use tensor matricization and low-rank matrix decomposition to accelerate structured inference on chain and tree structure models. however, their method has an even higher complexity than @xcite on pcfgs. recently, @xcite propose a family of randomized dynamic programming algorithms to scale structured models to tens of thousands of states, which is orthogonal to the aforementioned low-rank-based approaches as the former performs approximate inference whereas the latter perform exact inference. in this work, we propose a new low-rank-based approach to scale structured inference, which can be described by fgg notations intuitively. we first provide an intuitive and unifying perspective toward the work of @xcite and @xcite , showing that their low-rank decompositionbased models can be viewed as decomposing large factors in an fgg-e.g., the binary rule probability tensor in pcfgs-into several smaller factors connected by new "rank" nodes. then we target at a subset of fggs-which we refer to as b-fggssubsuming all models considered by @xcite , whereby the inference algorithms can be formulated via b-graphs @xcite . we propose a novel framework to support a family of inference algorithms in the rank space for b-fggs. within the framework, we apply cpd on the factors of a b-fgg and then construct a new b-fgg defined in the rank space by marginalizing all the state nodes. inference with the new b-fgg has the same result and a lower time complexity if the rank size is smaller than the state size. we conduct experiments in unsupervised pcfg parsing and hmm language modeling. for pcfg induction, we manage to use 20 times more hidden states than @xcite , obtaining much better unsupervised parsing performance. for hmm language modeling, we achieve lower perplexity and lower inference complexity than @xcite . ## low-rank structured inference in this section, we recover the accelerated inside algorithms of td-pcfg @xcite and lpcfg @xcite in an intuitive and unifying manner using the fgg notations. the accelerated forward algorithm of lhmm @xcite can be derived similarly. denote @xmath0, and α i,@xmath1, j). @xcite derived the recursive form: eq. 9 can be derived automatically by combining eq. 7 (or fig. 3 (a) ) and eq. 5-6. cohen et al. recently, @xcite use low-rank matrix decomposition to accelerate pcfg inference. they first perform tensor matricization to flatten t to @xmath2, and then let @xmath3, @xmath4. by un-flattening v to @xmath5, their accelerated inside algorithm has the following recursive form: eq. 11 can be derived by combining fig. 3 (b ) and eq. 5-6. the resulting inside time complexity is o(n 3 m 2 r + n 2 mr), which is higher than that of td-pcfg. when learning a pcfg and a hmm, there is no need to first learn t and then perform decomposition on t. instead, one can learn the decomposed matrices (e.g., u, v) to learn t implicitly. during inference, one can follow eq. 10 or 12 without the need to reconstruct t. ## conclusion and future work in this work, we leveraged tensor rank decomposition (cpd) for low-rank scaling of structured inference. we showed that cpd amounts to decomposing a large factor into several smaller factors connected by a new rank node, and gave a unifying perspective towards previous low-rank structured models @xcite . we also presented a novel framework to design a family of rank-space inference algorithms for b-fggs, a subset of fggs which subsume most structured models of interest to the nlp community. we have shown the application of our method in scaling pcfg and hmm inference, and experiments on unsupervised parsing and language modeling validate the effectiveness of using large state spaces facilitated by our method. we believe our framework can be applied to many other models which have high inference time complexity and are subsumed by b-fggs, including lexicalized pcfgs, quasi-synchronous contextfree grammars (qcfgs), etc. a direct application of our method is to decrease the inference complexity of the neural qcfg @xcite .