  Second-order Recurrent Neural Networks (2RNNs) extend RNNs by leveraging
second-order interactions for sequence modelling. These models are provably
more expressive than their first-order counterparts and have connections to
well-studied models from formal language theory. However, their large parameter
tensor makes computations intractable. To circumvent this issue, one approach
known as MIRNN consists in limiting the type of interactions used by the model.
Another is to leverage tensor decomposition to diminish the parameter count. In
this work, we study the model resulting from parameterizing 2RNNs using the CP
decomposition, which we call CPRNN. Intuitively, the rank of the decomposition
should reduce expressivity. We analyze how rank and hidden size affect model
capacity and show the relationships between RNNs, 2RNNs, MIRNNs, and CPRNNs
based on these parameters. We support these results empirically with
experiments on the Penn Treebank dataset which demonstrate that, with a fixed
parameter budget, CPRNNs outperforms RNNs, 2RNNs, and MIRNNs with the right
choice of rank and hidden size.
