  Tensor networks are a powerful modeling framework developed for computational
many-body physics, which have only recently been applied within machine
learning. In this work we utilize a uniform matrix product state (u-MPS) model
for probabilistic modeling of sequence data. We first show that u-MPS enable
sequence-level parallelism, with length-n sequences able to be evaluated in
depth O(log n). We then introduce a novel generative algorithm giving trained
u-MPS the ability to efficiently sample from a wide variety of conditional
distributions, each one defined by a regular expression. Special cases of this
algorithm correspond to autoregressive and fill-in-the-blank sampling, but more
complex regular expressions permit the generation of richly structured data in
a manner that has no direct analogue in neural generative models. Experiments
on sequence modeling with synthetic and real text data show u-MPS outperforming
a variety of baselines and effectively generalizing their predictions in the
presence of limited data.
