Dynamic Programming in Rank Space: Scaling Structured Inference with Low-Rank HMMs and PCFGs

Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 4797 - 4809 July 10-15, 2022 ©2022 Association for Computational Linguistics Dynamic Programming in Rank Space: Scaling Structured Inference with Low-Rank HMMs and PCFGs Songlin Yang∗, Wei Liu*, Kewei Tu† School of Information Science and Technology, ShanghaiTech University Shanghai Engineering Research Center of Intelligent Vision and Imaging {yangsl,liuwei4,tukw}@shanghaitech.edu.cn Abstract Hidden Markov Models (HMMs) and Proba- bilistic 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 de- scribing a wide range of models. Recent re- search found it beneficial to use large state spaces for HMMs and PCFGs. However, in- ference with large state spaces is computation- ally demanding, especially for PCFGs. To tackle this challenge, we leverage tensor rank decomposition (aka. CPD) to decrease infer- ence computational complexities for a sub- set 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 unsuper- vised PCFG parsing, showing better perfor- mance than previous work. Our code is pub- licly available at https://github.com/ VPeterV/RankSpace-Models. 1 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 gram- mars (FGGs) (Chiang and Riley, 2020), which are a powerful tool to describe a wide range of mod- els, allowing exact and tractable inference in most situations of interest. Over-parameterization has been shown benefi- cial in facilitating optimization of deep networks (Arora et al., 2018; Xu et al., 2018; Du et al., 2019). Buhai et al. (2020) found that over- parameterization is also helpful in learning latent ∗Equal contributions: Songlin Yang formulated the idea and Wei Liu conducted the experiments. † Corresponding author. variable models by increasing the number of hidden states. Buhai et al. (2020) argued that it is impor- tant 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 mod- els, and recently researchers have found it benefi- cial to use large state spaces for HMMs and PCFGs (Dedieu et al., 2019; Chiu and Rush, 2020; Yang et al., 2021b; Chiu et al., 2021). However, struc- tured inference with large state spaces is computa- tionally demanding, especially for PCFGs, push- ing researchers to develop methods to decrease the computational complexities. Chiu and Rush (2020) propose a neural VL-HMM with 215 states for lan- guage modeling, narrowing down the performance gap between HMMs and LSTMs. They follow Dedieu et al. (2019) to impose a strong sparsity constraint (i.e., each hidden state can only …

Content truncated to 500 words