Dynamic Programming in Rank Space: Scaling Structured Inference with Low-Rank HMMs and PCFGs
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
\url{https://github.com/VPeterV/RankSpace-Models}.