A Expressivity of Low-Rank Models

We focus on the simplest case of HMMs for an analysis of expressivity. Next, we show that there does not exist a 2-state HMM that can have this marginal distribution. We start by setting up a system of equations. We provide the low-rank hypergraph marginalization algorithms for HMMs and PCFGs in Alg. 4, with loops over labels Words outside of the vocabulary are mapped to the UNK token. The dataset lengths are given in Table 3.