Low-Rank Constraints for Fast Inference in Structured Models
Authors: Justin T Chiu
Yuntian Deng
Alexander M Rush
Venue: NeurIPS 2021 Poster (2021)
Keywords: structured prediction
generative models
graphical models
inference

Abstract: Structured distributions, i.e. distributions over combinatorial spaces, are commonly used to learn latent probabilistic representations from observed data. However, scaling these models is bottlenecked by the high computational and memory complexity with respect to the size of the latent representations. Common models such as Hidden Markov Models (HMMs) and Probabilistic Context-Free Grammars (PCFGs) require time and space quadratic and cubic in the number of hidden states respectively. This work demonstrates a simple approach to reduce the computational and memory complexity of a large class of structured models. We show that by viewing the central inference step as a matrix-vector product and using a low-rank constraint, we can trade off model expressivity and speed via the rank.  Experiments with neural parameterized structured models for language modeling, polyphonic music modeling, unsupervised grammar induction, and video modeling show that our approach matches the accuracy of standard models at large state spaces while providing practical speedups.

Low-Rank Constraints for Fast Inference in Structured Models
Justin Chiu Cornell University jtc257@cornell.edd
Yuntian Deng"
Harvard University
dengyuntian@sean harvard. edu
Alexander M. Rush
Comelll University
arush@cornell.
Abstract
Structured distributions, i.c. distributions over combinatorial spaces, are commonly used to learn latent probabilistic representations from observed data. However, scaling these models bottlenecked by the high computational and memory complexity with respect to the size of the latent representations. Common models such as Hidden Markov Models (HMMs) and Probabilistic Context-Free Grammars (PCFGs) require time and space quadratic and cubic in the number of hidden states respectively. This work demonstrates simple approach to reduce the computational and memory complexity of a large class of structured models. We show that by viewing the central inference step as a matrix-vector product and using low-rank constraint, Experiments with neural parameterized structured models for language modeling, polyphonic music modeling, unsupervised grammar induction, and video modeling show that our approach matches the accuracy of standard models at large state spaces while providing practical speedups.
trade off model expressivity and speed via the rank.
Introduction
When modeling complex sequential spaces, such sentences, musical scores, video frames, key choice is the internal structural representations of the model. A common choice in recent years is to
Mikolov al. 2011 Brown et al. 2020 [Boulanger] Lewandowski et al.) 2012 Huang et al. 2018 Weissenborn et al. 2020 to store deterministic
neural representations [Bengio et al. 2003
history. These models yield strong predictive accuracy but their deterministie, continuous forms provide little insight into the intermediate decisions of the model]
Latent structured models provide alternative approach where complex modeling decisions broken down into a series of probabilistic steps. Structured models provide a principled framework for reasoning about the probabilistic dependencies between decisions and for computing posterior probabilities. The structure of the decision processes and the ability to answer queries through proba- bilistic inference afford interpretability and controllability that lacking in neural models (Koller
and Friedman 2009 Levine 2018).
Despite the benefits of structured models, the computational complexity of training scales asymptoti- cally much worse than for neural models, as inference, and therefore training, requires marginalizing
"Equal contribution
Code available here
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

over all possible latent structures. For standard general-purposs purpose models like Hidden Markov Models (HMM) and Probabilistic Context-Free Grammars (PCFG). the runtime of inference scales quadrati- cally and cubically in the number of states respectively, which limits the ability to reach massive scale. Promisingly, recent work has shown that in specific situations these models can be scaled, and that the increased scale results in commensurate improvements in accuracy without sacrificing the ability to perform exact inference (Dedieu et al. 2019 Chiu and Rush 2020 Yang et al., 2021].
In this work, we propose an approach for improving the runtime of a large class of structured latent models by introducing low-rank constraint. We target the family of models where inference can be formulated through a labeled directed hypergraph. which describes a broad class of dynamic- programming based inference [Klein and Manning, 20044, Huang and Chiang 2005| Zhou al.) 2006, Javidian et al. 2020, Chiang and Riley] [2020]. We show how under low-rank constraints these models allow for more efficient inference. Imposing a low-rank constraint allows for a key step of inference to be rewritten as a fast matrix-vector product. This approach is also inspired by recent advances in computationally efficient neural attention attention (Katharopoulos et al., 2020 Peng al. 2021 Choromanski et al.) 2020). a significantly different task and formulation, that rewrites matrix-vector products as fast low-rank products using approximate kernel techniques.
We evaluate this approach by learning low-rank structured models for the tasks of language modeling, polyphonic music modeling, unsupervised grammar induction. and video modeling. For these tasks we use variety of models including HMMs, PCFGs, and Hidden Semi-Markov Models (HSMMs). As the application of low-rank constraints is nontrivial in high-dimensional structured models due to reduced expressivity, we demonstrate effective techniques for overcoming several practical challenges of low-rank parameterivations. We find that our approach achieves very similar results to unconstrained models at large state sizes, while the decomposition allows us to greatly increase the speed of inference. Results on HMMs show that we can scale to more than 16,000 states; results on PCFGs achieve a significant perplexity reduction from much larger state spaces compared to past work [Kim et al. 2019]; and results on HSMMs show that our formulation enables scaling to much larger state spaces for continuous emissions [Fried et al. 2020
2 Background: Latent Structure and Hypergraphs
We consider the problem of modeling a sequence of observations p(x)) p(.1....,.22 These observations can range in complexity from the words in a sentence to a series of co-occurring musical notes, or to features of video frames, and may be discrete or continuous. We assume these observations are generated by an unobserved (latent) structured representation 2, and therefore model the joint p(æ, 2). The structure may be sequential or hierarchical, such as latent trees, and the set of structures Z is combinatorial, i.e. exponential in size with respect to the input sentence. In order to train these models on observations, we must optimize the evidence p(x) = E. p(x, 2) by marginalizing over z. Scaling this marginalization is the focus of this work.
Hypergraphs are graphical model formalism for structured distributions that admit tractable inference through dynamic programming [Klein and Manning 2004 Huang and Chiang| (2055 Zhou et al.) 2006 Javidian al. 2020 Chiang and Riley [2020] A labeled, directed, acyclic hypergraph consists of a set of nodes V. a set of hyperedges & and a designated root node S E V. Each node e E V has collection of labels L.. Each hyperedge e E has a head node u and tuple of tail nodes, (#1,... ")e[), where |e| is the number of tail nodes. For simplicity, we will assume at most 2 tail nodes v1, U2, and unless noted, a fixed label set L throughout, Each hyperedge e is associated with a score matrix Ve E _Cxc"" with score for all head and tail labels We use the notation [ [Vel=..(z1.z)) indicate the score for head label o, and tail labels 21 and 22. Finally, we assume we have a topological ordering over the edges.
2
3
A hypergraph is used to aggregate scores bottom- up through dynamic programming (belief prop- (left) shows the algorithm. It works by filling in a table vector agation) algorithm. Algorithm |
While the formalism is similar to undirected factor graphs. it allows us to represent more complex distribu- tions: notably dependency structures with unknown topologies, such as latent trees. "This formalism can represent inference in both locally and globally normalized models, although we focus on local normalization in this work.

---

Algorithm Hypergraph marginalization
[Scalar Form]
[Matrix Form] for u f- v hyperedge topologically do Ou _ V. return 0g
for u f- U1, U2 hyperedge topologically do for 2u E Lu do
[0u|2 _ E Velenn(e1)e2)
la [Quzl22
return Eylas]=
Algorithm 2 Hypergraph marginalization for HMMs and PCFGs
[HMM -Backward]
[PCFG CKY] for (i, k) + (i,j), (j, k) in span-size order do
for t + (t 11+11 1) in right-to-left order do
for 21+1 do
for 21, 22 ELs Ly.k do
[8(+1
(ac-1lzm
[B1,,,b((1122) = lasll,
0₁ _ V,3r-1
0ii $ B. return a aj, 1
return an
ag E R- for each node in order, and is initialized to I at the leaf nodes It returns the sum latent structures, p(r). Counting loops, the worst-case runtime complexity is O((E) x T, I-1) where L |C] is the size of the label set and |e"| the max hyperedge tail size. Algorithm (right) shows the same algorithm in matrix form by introducing joined tail vectors 3, E c for each group of nodes v. Letting 2, (21, 22), the joined tail vector contains entries [$]=
[0
To make this formalism more concrete, we show how hypergraphs can be used for inference several structured generative models: hidden Markov models, probabilistic context-free grammars, and hidden semi-Markov models. Inference in these examples are instances of the hypergraph algorithm.
Example: Hidden Markoy Models (HMM) HMMs are discrete latent sequence models defined by the following generative process: first, sequence of discrete latent states (21,..., 2r) with state size L are sampled as a Markov chain. Then each state independently emits an observation Iy, i.e.
T
p(x, 2) = II p(ze 211) p(re 2x),
p(E
(1)
where p(2: 1x-1) is the transition distribution, p(x;; 2x) the emission distribution, and p(z1 | zo) is the initial distribution with distinguished start symbol 20-
Given a sequence of observations x (#1...., xx) we can compute p(.)) = E, p(x, ( 2) using labeled directed hypergraph, with single-tailed edges, nodes corresponding to state positions, labels corresponding to states, and emissions probabilities incorporated into the scoring matrices V. There are 7 scoring matrices, V E RCC with entries [V=]= p(=++1, zt) corresponding to transitions Algorithm 2 (left) shows the approach. This requires time O(TL²) and is identical to the backward algorithm for HMMs 6
Example: Context-Free Grammars (CFG) CFGs are structured model defined by the 5-tuple SS..P,... R), where S is the distinguished start symbol, A is set of nonterminals, P is set of preterminals, X' is the token types in the vocabulary, and R. is set of grammar rules. Production rules for start, nonterminals, and preterminals take the following forms
S A, A - BC, B,C&NUR D DEP,IEX.
probabilistic context-free grammar (PCFG) additionally has a probability measure on the set of rules. To compute p(æ1,..... .T) with hypergraph, create one node for each contiguous subspan [i, k) in the sentence. Nodes with + have nonterminal label set N.. Nodes with
"The accumulation of scores is denoted by c Multiple hyperedges can have the same head node, whose scores must be added together.
'The left-most scoring matrix for the HMM has entries [ p(22, 21)p(21 20). 'In the case of HMMs, the table vectors au correspond to the backward algorithm's 8 values. We restrict our attention grammars in Chomsky normal form.

---

i+ 1 = k have a preterminal label set Ci1+1 = P. The main scoring matrix is v RCxc? with entries [ ==) = p 22 2 2 Algorithm (right) shows how for every hyperedge we join the scores from the two tail nodes in Os,j and ajj.k into joined tail vector Bi.j. RC As there are O(T9) hyperedges and the largest C is of size [A] the runtime of the algorithm is ((T) This approach is identical to the CKY algorithm.
Example: Hidden Semi-Markoy Models (HSMM) HSMMs are extensions of HMMs that allow for generating a variable-length sequence of observations per state. It defines the following generate process: first, we sample a sequence of discrete latent states 2 = (z). ,2x) with a first-order Markov model. We then use them generate the length of observations per state. For experiments
we generate independent continuous emissions 2₁ with a Gaussian distribution for p(æ; zx). Full details of the inference procedure given in Appendix
3 Rank-Constrainee Structured Models
For these structured distributions, hypergraphs provide general method for inference (and therefore training parameterized versions). However, the underlying algorithms scale poorly with the size of the label sets (quadratic for HMM and HSMM, cubic for CFG). This complexity makes it challenging scale these models and train versions with very large numbers of states.
In this section, we consider an approach for improving the scalability of these models by reducing the dependence of the computational complexity of inference the label set size. The main idea is to speed up the matrix-vector product step in inference by using a low-rank decomposition of the scoring matrix V. In the next section we show that this constraint can be easily incorporated into parameterized versions of these models.
3.1 Low-Rank Matrix- Vector Products
The main bottleneck for inference speed the matrix-vector product Or $ V Ve that must be computed for every edge in the hypergraph. As saw in A (1eft)) this step takes time L to compute, but it can be sped up by making structural assumptions on Ve. In particular, we focus on scoring matrices with low rank.
We note the following elementary property of matrix-vector products. If the scoring matrix can be decomposed the product of two smaller matrices V. U.V.", where Ue RCXN and Ve E NRxll then the matrix-vector products can be computed in time O(EE) x L x N) as follows:
V.B, 1 (U.V. (v))
This reordering of computation exchanges a factor of L for a factor of N. When & L, this method is both faster and more memory-efficient,
We enforce the low-rank constraint by directly parameterizing the factors U, and V. for scoring matrices Ve that we would like to constrain. We treat both U. and V. as embedding matrices, where each row corresponds to an embedding of each value of 2, and a joint embedding of (21, 22) respectively:
UVeean.n co.
[Vel(En.s2).n = C22 (0(g(Z), 22))
where f and g are embedding functions; Cz2, and C21.22 are constants (used to ensure proper normal- ization) or clamped potentials (such as conditional probabilities); and á RRD - R is a function that ensures nonnegativity, necessary for valid probability mass functions. Algorithm 3 shows the role of the low-rank metrix-vector product in marginalization
We have a separate matrix for terminal production on x which we clide for simplicity. "If the normalizing constants are given by 6x,, they can be computed from unnormalized 0c V. follows: Cz.
[Ve V. 1),, in time O(L | N + LN), and similarly for C21.22-

---

3.2 Application to Structured Models
As enforcing low-rank factorization of every scoring matrix limits the expressiv- ity of model, we explicitly target scoring matrices that are involved in computational bottlenecks 10 For these key scoring matri- ces, we directly parameterize the scoring matrix with low-rank factorization, which call low-rank parameterization. For other computations, we utilize a standard softmax parameterization and do not factor- ize the resulting scoring matrix. We refer to this mixed parameterization.
Algorithm 3 Low-rank marginalization
for 01, 02 hyperedge topologically do
for n E i,..... I....,N do
hn)n Σ co [6(0(2), 22) [3ol.. D> O(T
On _ U.y return ag
O(IN)
Hidden Markov Models Low-rank HMMs (LHMMs) use the following mixed parameterization, which specifically targets the state-state transition bottleneck by using low-rank parameterization for the transition distribution, but softmax parameterization for the emission distribution:
p( 21-1) x (u(.,..) ((vz.), p(z, 24) exp(u__,zz) Vz.).
(5)
where Us, 1 1(=-1) and Va, = g(z)) are (possibly neural) embedding functions. The param- eterizations of the embedding functiinn fig : C + IR,, as well as the non-negative mapping & _2_h + E are detailed in Appendix F When performing inference, we treat the emission probabilities p(rz 24) as constants, and absorb them into Cu-
This allows inference to be run in time O(TLN), where T is the length of a sequence, L the size of the label space, and N the feature dimension.
Hidden Semi-Markov Models For low-rank HSMM (LHSMM), we similarly target the transition distribution and keep the standard Gaussian emission distribution:
p(=k 2k-1) u = Vz p( zk) x KCams( X.),
where Uz-_, = ((f(=x11) and Vsa = ((g(z))) are state embeddings. while KGauss (-.-) is the Gaussian kernel used model continuous xç. The full parameterization of the embeddings given in Appendix F The total inference complexity is O(TLMN), where M is the maximum length of the observation sequence under any state.
Context-Free Grammars For PCFGs, the inference bottleneck is related to the transition from a nonterminal symbol to two nonterminal symbolss (A - B C), and specifically parameterize using a low-rank parameterization:
p S) o exp(u u xx,,), p(za,, 2z 22,k) x cx a.e Vas 25) o( (
#+1=jV
j+1mk
O.W.
p(z, 2x) x exp(u..v..) v2.).
where uz/u,, is the embedding of = when is used as va/vd, is the embedding of x/(21, #2) when they are used as tail. See Appendix [ for the full parameterization, drawn from Kim al. [2019]. Note that we limit the application of low-rank constraints to nonterminal to nonterminal productions. These productions dominate the runtime as they are applied at O(T*) hyperedges. This allows inference to be run in time ( where 7 is the length of a sequence, L the size of the label space, and N the feature dimension.
4 Experimental Setup
We evaluate the application of low-rank constraints with four experiments: sequential language modeling with HMMs, polyphonic music modeling with a large observation space, hierarchical language modelings with PCFGs, and video modeling with HSMMs.
For discussion of the expressivity of low-rank models compared to models with fewer labels, see Appendix
5

---

Data Our first set of experiments evaluate sequential models on PENN TREEBANK dataset (PTB) [Marcus et al. 1993] for the task of word-level language modeling. We use the preprocessing from Mikolov et al. 201 J. The second set of experiments is on polyphonic music modeling [Boulanger] Lewandowski et al. 2012]. We evaluate on four music datasets: Nottingham (Nott), Piano, MuseDDta (Muse), and JSB chorales (JSB). Each timestep consists of an 88- 88-dimensional binary vector indicating whether a particular note is played. Since multiple notes may be played at the same time, the effective vocabulary size is extremely large. The third set of experiments use PCFGs for language modeling, we also use PTB, but with the splits and preprocessing used in unsupervised constituency parsing [Shen] et al., 2018 2019. Kim et al., 2019]. The last set of experiments use HSMMs for video modeling, where we use CROSSTASK Zhukov et al., 2019 with 10% of the training data for validation. We follow the preprocessing steps in (Fied et al. [2020] and apply PCA to project features vectors of size 200. For the full details on datasets, please see Appendix [
Models and Hyperparameters For language modeling with HMMs, we experiment with range of state sizes, |2] = L E {210, 22,,,21 22,, 212 213 ,21,,214, and rank N E {I//2, L/4, L/8). For polyphonic music modeling with HMMs, we experiment with states sizes L E {27 25, 22,2, "2,,0,,11" .2" For language modeling with PCFGs, we use a set of nonterminals of size [ E (30, 60, 100) and preterminals of twice the number of nonterminals [P] 2| Our smallest setting ([V = 30, [P] = 60) is the one used in Kim et al. [2019] For video modeling with HSMMs, we use the same model setting as Fried et al. [2220], but we don't constrain states to the predefined states per task, and we experiment with state sizes E {20, 2 2$, 2,, 2,,22 22,1 and rank N E {{2 25 20,2" ]
We utilize the feature map d(x) exp(Wxr) for the LHMM and LHSMM, and <(x)) exp(W>r [|=ll//22 for the LPCFG. We initialize the parameters of feature maps using orthogonal feature projections [Choromansii al. [2200], and update it alongside the model parameters. For the full
hyperparameter and optimization details, see Appendix G
Baselines and Evaluation The language modeling experiments evaluated using perplexity. Baselines are neurally parameterized HMM with a standard softmax transition. We also com- pare VL-HMM, which makes strong structural sparsity assumption the emission distri- bution [Chiu and Rush| 2020]. We include for reference a state-of-the-art language model, the AWD-LSTM [Merity al. 2017]. For polyphonic music modeling, we compare our LHMM against RNN-NADE Douulangr-Lewandowske et al.) 2012) which models the full joint distribution of notes as well as temporal dependencies;
well autoregressive neural models such as the R-Transformer [Wang et al. 2019) (as reported by Song et al. (2019) ) and an LSTM (as reported by Ziegler and Rush [2019]: ): models with latent continuous dynamics such as the LV-RNN (Gu ct 20.13] and SRNN Fraccaro et al. 2016]; and finally comparable models with latent discrete dynamics, the TSBN Gan et al.] 2015) and the baseline HMM. We evaluate perplexities of our low-rank PCFG (LPCFG) against softmax PCFG (PCFG) [Kim et al. [2019]. For video modeling,
we evaluate the negative log likelihoods on the test set and compare low-rank HSMMs to softmax
HSMMs.
5 Results
Hidden Markov Models for Language Modeling Our main experimental result is that the low-rank models achieve similar accuracy, measured by perplexity, our baselines. Fig. I shows that perplexity improves as we increase the scale of the HMM, and that the performance of our LHMM also improves at the same rate. At small sizes, the low-rank constraints slightly hinder accuracy; however once the size is large enough, i.e. larger than 212 LHMMs with 8:1 state-to-rank ratios perform comparably.
Fig. 1 also contains speed comparisons between HMMS and LHMMS. A state-to-rank ratio of 8:1 matches the accuracy of softmax HMMs at larger state sizes and also gives an empirical speedup of more than 3x at L = 244 As expected, we only see a speedup when the state-to-rank ratio exceeds 2:1, as replaced the O(L²) operation with two OLLN) ones. This implies that the low-rank constraint is most effective with scale, where we observe large computational gains at no cost in accuracy.
See Appendix for an analysis of the ranks of HMMS/

---

2-1
180
Batch
170
Parameterization
softmax
2
160
low rank (2:1)
low (4:1)
150
2'4
low (8:1)
2"9
210
211
212
2
224
2
2
2
2
2
Number of states
Number of states
Figure 1: Validation perplexities on PTB versus model scale, as well as speed in seconds per batch.
Model
L N
Train
Val
Model
Val
Test
HMM
95.9
144.3
LHMM
97.5
141.4
AWD-LSTM
60.0
57.3
LHMM+band
8
101.1
143.8
VL-HMM
128.6
119.5
LHMM
110.6
146.3
HMM
144.3
136.8
LHMM+band
16
96.9
138.8
LHMM
141.4
131.8
LHMM
108.4
153.7
LHMM+band
32
110.7
145.0
Table 1: Model perplexities PTB. All HMM variants have L = 2 states. (Left):: Validation
and test perplexities. The LHMM has a state-to-rant ratio 8 1. (Right): Further experiments with extending the low-rank structure of LHMMs with banded transition structure.
HMMs are outperformed by neural models, and also by VL-HMMs [Chiu and Rush 2020] which offer similar modeling advantages to HMMs, shown in Tbl. (lett. This indicates that some aspects of performance are not strictly tied to scale. We posit this is due to the problem-speciff block-sparse emission constraint in VL-HMMs. While very effective for language modeling, the VL-HMM relies on a hard clustering of states for constraining emissions. This is difficult to apply to problems with richer emission models (as in music and video modeling).
Hidden Markoy Models for Music Modeling We next apply LHMMs on polyphonic music model- ing. This has max effective vocabulary size of 288, as multiple notes may occur simultaneously. Unlike for language modeling, we use factored Bernoulli emission model, modeling the presence of each note independently. Fig. 2 (right) shows that HMMs are competitive with many of the models on these datasets, including LSTMs. We find that LHMMs achieve performance slightly worse than but comparable to the unconstrained HMMs overall. Fig. 2 (left) shows that the distinction drops with more states. Both HMMs achieve low negative likelihoods (NLL) on the datasets with shorter sequences, Nottingham and JSB, but relatively poorer NLLS on the datasets with longer sequences (Muse and Piano).
Context- Free Grammars For syntactic language modeling on PTB, our low-rank PCFG (LPCFG) achieves similar performance to PCFGs, as shown in Table 2 (left), with an improvement in com- putational complexity. The complexity of inference in PCFGs models is cubic in the number of nonterminals, so even models with | = 30 nonterminals are relatively costly. Our approach achieves comparable results with N = 8 features. As we scale up the number of nonterminals to WW| = 100, LPCFG stays competitive with a lower computational complexity (since N < [W]. These experiments also demonstrate the importance of scale in syntactic language models with more than 50 point gain in perplexity over a strong starting model.
CFG Speed Once the model is large enough, i.e. [ > 60 nonterminals and |P] > 120 preterminals, the LPCFG faster than PCFG, as shown in Thl. (left). Note that the LPCFG is faster than the
CFG even when the number of features N >> (V] in contrast to the HMM case where a speedup can only be obtained when N < L/2. This is due to the scoring matrix being rectangular: Recall the
2
low-rank matrix product v UVV (), where, when specialized to PCFGs, the left-hand side takes
7

---

7.25
Parameterization
Model
Nott
Piano
Muse
JSB
softmax
7.00
low rank (2:1)
RNN-NADE
2.31
7.05
5.6
5.19
6.75
low rank (4:1)
R-Transformer
2.24
7.44
7.00
8.26
low rank (8:1)
LSTM
3.43
7.77
7.23
8.17
Valid
6.50
LV-RNN
2.72
7.61
6.89
3.99
SRNN
2.94
8.20
6.28
4.74
6.00
TSBN
3.67
7.89
6.81
7.48
5.75
HMM
2.43
8.51
7.34
5.74
2'
2
2
2
2
LHMM
2.60
8.89
7.60
5.80
Number of states
Figure 2: Polyphonic music negative log-likelihoods (NLL), measured in nats. (Left): HMM and LHMM validation performance for various state sizes and state:rank ratios. (Right): Test-set NLLs for polyphonic music. The HMM models have = 2 states and the LHMM has rank = 29, 4:1 state:rank ratio.
PP|
Model
N
PPL
Secs
Model
L
N
NLL
Secs
30
60
PCFG
252.60
0.23
HSMM 12
151
1.432e5
LPCFG
8
247.02
0.27
LPCFG
250.59
0.27
HSMM
26
1.428c5
0.78
HSMM
27
1.427e5
2.22
60
120
PCFG
234.01
0.33
HSMM
28
1.426c5
7.69
LPCFG
16
217.24
0.28
LPCFG
32
213.81
0.30
LHSMM
27
27
1.427e5
4.17
LHSMM
28
26
1.426e5
5.00
100
200
PCFG
191.08
1.02
LHSMM
29
25
1.424e5
5.56
LPCFG
32
203.47
0.64
LPCFG
64
194.25
0.81
LHSMM
20
24
1.423e5
10.0
Table 2: (Left): Test perplexities and speeds for PCFG models on PTB. The complexity of PCFG (TT1N)3) whereas the complexity of LPCFG is O N)) Speeds are given in seconds per batch. (Right): Negative log likelihoods (NLL) per video and speeds for HSMM models on CROSSTASK. We cannot train HSMMs beyond 2 states due to GPU memory constraints, but we can train LHSMMs with up to 20 states. Speeds are given in seconds per batch.
time O(1,3) and the right-hand side takes O + LN). For PCFGs, the term V B dominates the runtime. This contrasts with HMMs, where both V T and the subsequent multiplication by U take the same amount time, (LN).
Hidden Semi-Markov Models for Video Modeling Table (right) shows the results of video modeling using HSMMs. In addition using different hypergraph for inference, these experiments use continuous Gaussian emission model. By removing the state constraints from tasks, our HSMM baselines get better video-level NLLs than that from Fried al. (2020) at the cost of more memory consumption. Due to GPU memory constraints, we can only train HSMMs up to 2 states. However, the low-rank parameterization allows models to scale to 200 states, yielding an improvement in NLL. Absolute results could likely be improved with more states and by improved emission parameterization for all models.
Improving Rank Assumptions One potential limitation of all low-rank models is that they cannot learn high-rank structures with low N. We began see this issue a ratio of 16:1 states features for large HMMs. To explore the effects of this limitation, we perform an additional experiment that combines low-rank features with sparse component. Specifically we add an efficient high-
rank sparse banded transition matrix. The full details are in Appendix [ Tbl. [ (right) shows that combination with the band strueture allows for larger ratios than just the low-rank structure alone, while only adding another operation that costs O(LN).

---

6
Related Work
Similar to our work, other approaches target matrix or tensor operations in inference, and impose structural model constraints to improve computational complexity. Many of the works HMMs in particular take advantage of the transition structure. The Dense-mostly-conttee
(DMC) HMM assigns a subset learnable parameters per row of the transition matrix and sets the rest a constant, leading to sub-quadratic runtime (Siddiqi and Moore 2005). Other structures have also been explored, such aligning the states of an HMM underlying phenomena that allows inference to be sped up (Felzenszwwlb et al., 2004, Roweis 2000]. Additionally, other methods take advantage of emission structure HMMs in order scale, such as the Cloned HMM [Dedieu et al. [209]] and VL-HMM [Chiu and Rush 22220] Compared to these approaches, our method is more flexible and generie, since it can be applied in a non-application-speiff manner, and even extended with high-rank components (such as banded structure).
Low-rank structure has been explored in both HMMs (Siddiqi et al. 2009 generalization of PCFGs called weighted tree automata [Rabusseau et al. 2015). and conditional random fields TTai et al. 2018). The reduced-rank HMM (Siddiqi et al. 2009 has at most 50 states, and relies on spectral methods for training. The low-rank weighted tree automata [Rabusseau et al. 2013 also trains latent tree models via spectral methods. We extend the low-rank assumption neural parameterizations. which have been shown to be effective for generalization [Kim et al., 2019 Chiu and Rush] [020], and directly optimize the evidence via gradient descent. Finally, Thai al. [2018] do not take advantage of the low-rank parameterization of their CRF potentials for faster inference via low-rank matrix products, a missed opportunity. Instead, the low-rank parameterization used only as a regularizer, with the full potentials instantiated during inference.
Concurrent work in unsupervised parsing uses tensor decomposition scale PCFGs to large state spaces (Yang et al. 2021]. Our low-rank decomposition of the flattened head-tail scoring matrix is more general, resulting in worse scaling for the PCFG setting but with wider applicability, as shown by experiments with HMMs and HSMMs.
Conclusion
This work improves the scaling of structured models by establishing the effectiveness of low-rank constraints for hypergraph models. We show that viewing key step of inference in structured models as a vecror product, in combination with a low-rank constraint on relevant parameters, allows for immediate specdup. Low-rank inference allows complexity of marginalization at the cost of constrained model. Our approach applies to a wide class of models, including HMMs, HSMMs, and PCFGs. Through experiments language, video, and polyphonic music modeling, we demonstrate an effective approach for overcoming the practical difficulty of applying low-rank constraints in high dimensional, structured spaces by targeting and constraining model components that bottleneck computation. Future work includes exploration of other structural constraints for speeding up matrix-vector products (Dao al. 2020 performed in inference, as well as application to models where exact inference is intractable.
obtain reduction in the asymptotic
Acknowledgments and Disclosure of Funding
We thank Nikita Kitaev for the discussion that sparked this project. We thank Sam Wiseman, Jack Morris, and the anonymous reviewers for valuable feedback. Yuntian Deng is sponsored by NSF 1704834, Alexander Rush by NSF CAREER 1845664, and Justin Chiu by an Amazon research award.
References
Justin Bayer and Christian Osendorfer. Learning stochastic recurrent networks, 2015.

---

Yoshua Bengio, Réjean Ducharme, Pascal Vincent, and Christian Janvin. A neural probabilistic language model. J. Mach. Learn. Res., 3:1137-1155, March 2003. ISSN 1532-4435.
Nicolas Boulanger-Lewandowwe
Yoshua Bengio, and Pascal Vincent. Modeling temporal de- pendencies in high- dimensiinn sequences: Application to polyphonic music generation and transcription. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML' 12, page 1888, Madison, WI, USA, 2012. Omnipress. ISBN 9781450312851.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners, 2020.
David Chiang and Darcey Riley. Factor graph grammars. arXiv preprint arXiv:2010. 12048, 2020.
Justin Chiu and Alexander Rush. Scaling hidden Markov language models. In Proceedings of the
2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1341- 1349, Online, November 2020. Association for Computational Linguistics. doi: 10. 18.18853/v1// 1/2020. maalp-main.Ige URL http:ttts////ww.clllet org/ http///nhhooog///..oooooo
emnlp emnlp-main. 103
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, David Belanger, Lucy Colwell, and Adrian Weller. Rethinking attention with performers, 2020.
Tri Dao, Nimit Sohoni, Albert Gu, Matthew Eichhorn, Amit Blonder, Megan Leszczynski, Atri Rudra, and Christopher Ré. Kaleidoscope: An efficient, learnable representation for all structured linear maps. In International Conference on Learning Representations, 2020. URL https //openreview. wetpiiewwweetteeee www//eerrmmiideeeemeeeee Btte:/orruu-nddBBBBBBy
Antoine Dedieu, Nishad Gothoskar, Scott Swingle, Wolfgang Lehrach, Miguel Lázaro-Gredilla, and Dileep George. Learning higher-order sequential structure with cloned hmms, 2019.
Pedro Felzenszwalb, Daniel Huttenlocher, and Jon Kleinberg. Fast algorithms for large- state-space hmms with applications to web usage analysis. In S. Thrun, L. Saul, and B. Schölkopf, editors, Advances in Neural Information Processing Systems, vol- ume 16. MIT Press, 2004. URL htttss://pooeeddinn: neurips wttpp/ppe///////////pppp .df]
Marco Fraccaro, Søren Kaae Sønderby, Ulrich Paquet, and Ole Winther. Sequential neural models with stochastic layers, 2016
Daniel Fried, Jean- nan-Baptiste Alayrac, Phil Blunsom, Chris Dyer, Stephen Clark, and Aida Nematzadeh. Learning to segment actions from observation and narration. arXiv preprint arXh::2005.0368. 2020.
Zhe Gan, Chunyuan Li, Ricardo Henao, David Carlson, and Lawrence Carin. Deep temporal sigmoid belief networks for sequence modeling, 2015.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 249-256 JMLR Workshop and Conference Proceedings, 2010.
Shixiang Gu, Zoubin Ghahramani, and Richard E. Turner. Neural adaptive sequential monte carlo, 2015.
Cheng-Zhi Anna Huang, Ashish Vaswani, Jakob Uszkoreit, Noam Shazeer, Curtis Hawthorne, Andrew M. Dai, Matthew D. Hoffman, and Douglas Eek. An improved relative self-attention mechanism for transformer with application to music generation. CoRR, abs/1809.00 04281, 2018. URL http::/arxii org/ abs/ 1809. 04281
10

---

Liang Huang and David Chiang. Better k-best parsing. In Proceedings of the Ninth International Workshop on Parsing Technology, pages 53-64, 2005.
Mohammad Ali Javidian, Zhiyu Wang, Linyuan Lu, and Marco Valtorta. On hypergraph prob- abilistic graphical model. Annals of Mathematics and Artificial Intelligence, 88(9):1003-100 2020.
A. Katharopoulos, A. Vyas, N. Pappas, and F. Fleuret. Transformers are mns: Fast autoregressive transformers with linear attention. In Proceedings of the International Conference on Machine Learning (ICML), 2020.
Yoon Kim, Chris Dyer, and Alexander Rush. Compound probabilistic context-free grammars for gram- mar induction. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2369-2385, Florence, Italy, July 2019. Association for Computational Linguis- tics. doi: 10.18653/v 1/1111111//11 1228. URL www. aclweb. org hwtp///aholoogg/111111 1228
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017.
Dan Klein and Christopher D Manning. Parsing and hypergraphs. In New developments in parsing technology, pages 351-372. Springer, 2004.
Daphne Koller and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques Adaptive Computation and Machine Learning. The MIT Press, 2009. ISBN 0262013193.
Rahul G. Krishnan, Uri Shalit, and David Sontag. Structured inference networks for nonlinear state space models, 2016.
Sergey Levine. Reinforcement learning and control as probabilistic inference: Tutorial and review, 2018.
Xiaolei Liu, Zhongliu Zhuo, Xiaojiang Du Xiaosong Zhang, Qingxin Zhu, and Mohsen Guizani. Adversarial attacks against profile hmm website fingerprinting detection model. Cognitive Systems Research, 54, 12 2018. doi: 10. 200.:/ff..oosss..11....... 12.005.
Ilya Loshchilov and Frank Hutter. Fixing weight decay regularization in adam. CoRR, abs/ 2017. httptt/////axiii
05101
Mitchell Marcus, Mary Ann Mareinkiewicz, and Beatrice Santorini. Building a large annotated corpus of english: The penn treebank. Comput. Linguist., 19())313-330, June 1993. ISSN 0891-2017.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing LSTM language models. CoRR, fos//708.022 2017. URL http::///// www. abs/ 1708. 02182
Tomas Mikolov, Anoop Deoras, Stefan Kombrink, Lukás Burget, and Jan Cernocky. Em- pirical evaluation and combination of advanced language modeling techniques. pages 605 608, 2011. URL http://dblp.... http:/dlllpliiiiiieeemmmm uni-trier dw/ hto/a////nntt/mmeerreeee////e//p htm1HMikolovDDBC111
Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah Smith, and Lingpeng Kong. Random feature attention. In International Conference Learning Representations, 2021. URL
httpps://pperrevier htte/formmm/--QQQTTTTTEE.E
Guillaume Rabusseau, Borja Balle, and Shay B. Cohen. Weighted tree automata approximation by singular value truncation. CoRR, abs/1511.01442, 2015. URL httt:::/aaxxvvorr//baaa.. 01442
Sam Roweis. Constrained hidden markov models. In S. Solla, T. Leen, and K. Müller, editors, Advances in Neural Information Processing Systems, volume 12. MIT Press, 2000. URL
pdf
Yikang Shen, Zhouhan Lin, Chin wei Huang, and Aaron Courville. Neural language modeling by jointly learning syntax and lexicon. In International Conference on Learning Representations,
2018. http//ppss//ppeeeeeeeeeeeeetrrrr

---

Yikang Shen, Shawn Tan, Alessandro Sordoni, and Aaron Courville. Ordered neurons: Integrating tree structures into recurrent neural networks. In International Conference on Learning Representations. 2019. http::tttts:://peeeeveee
net/forum? Bdd
Sajid M. Siddiqi and Andrew W. Moore. Fast inference and learning in large-state-space hmms. In Proceedings of the 22nd International Conference on Machine Learning, ICML '05, page 800-807, New York, NY. USA, 2005, Association for Computing Machinery. ISBN 1595931805 doi: 10. 1. 102455.. URL (ttphtt::///// :/tpiio//dooooreee wwgg.pooy... wwwrrrii..coom cornell edu/10 1145/1102351 1102452
Sajid M. Siddiqi. Byron Boots, and Geoffrey Gordon. Reduced-rank hidden markov models. CoRR, abs/0910.0990 2009. URL
0902
Kyungwoo Song. JoonHo Jang, Seungjae Shin, and I1-Chul Moon. Bivariate beta LSTM. CoRR, abs/1905.105211 2019. UtL/
10521
Daniel Stoller, Mi Tian, Sebastian Ewert, and Simon Dixon. Seq-u-net: one-dimensional causal u-net for efficient sequence modelling. CoRR, abs/1911.00339 2019. (RLppp/://aaxx org/
abs/1911. 06393
Dung Thai, Sree Harsha Ramesh, Shikhar Murty, Luke Vilnis, and Andrew McCallum. Embedded- state latent conditional random fields for sequence labeling. In Proceedings of the 22nd Con- ference on Computational Natural Language Learning, pages 1-10, Brussels, Belgium, Oc- tober 2018. Association for Computational Linguistics. doi: 10.18653/1/K118-100 URL https://acclntholl
oww.oog///.... (ts//K88-100 1001
Zhiwei Wang, Yao Ma, Zitao Liu, and Jiliang Tang. R-transformer: Recurrent neural network enhanced transformer, 2019.
Dirk Weissenborn, Oscar Täckström, and Jakob Uszkoreit. Scaling autoregressive video models. In International Conference on Learning Representations, 2020. URL. http::://oopnrreeiieett net/
Forum??d=r.JgsskrFi
Songlin Yang, Yanpeng Zhao, and Kewei Tu. Pefgs can do better: Inducing probabilistic context-free grammars with many symbols, 2021.
Shun-Zheng Yu. Hidden semi-markov models. Artificial intelligence, 174(2):215-443 2010.
Hongpo Zhang, Ning Cheng, Yang Zhang, and Zhanbo Li. Label flipping attacks against naive bayes on spam filtering systems. Applied Intelligence, pages 1-12, 2021.
Xinyang Zhang, Ningfei Wang, Shouling Ji, Hua Shen, and Ting Wang. Interpretable deep learning under fire. CORR, abs/18 hts//8112 2.00091, 2018. URL http:://aaxiii......// http://xxiv..or///b////11/// 00891
Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. Learning with hypergraphs: Clustering, classification, and embedding. Advances in neural information processing systems, 19:1601-1608, 2006.
Dimitri Zhukov, Jean- BaannBaptiste Alayrac, Ramazan Gokberk Cinbis, David Fouhey, Ivan Laptev, and Josef Sivie. Cross-task weakly supervised learning from instructional videos. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3537-3545, 2019.
Zachary M. Ziegler and Alexander M. Rush. Latent normalizing flows for discrete sequences, 2019.
12


Reviews:
[{"review_id": "l9-6_Cq6Z_9", "reviewer": "Reviewer_Yt4e", "summary": "The paper proposes a way of speeding up inference in directed graphical models by noting that the most expensive operation in the inner loop can be represented as a matrix-vector product and that if the model is parametrized in a different way this matrix-vector product can be done in lower computational complexity than in the usual algorithms. The interesting experimental result is that many classic models (including HMMs and CFG parsing) in reasonable applications can be parametrized in this way without a significant loss in model quality but a significant gain in speed, which allows for much larger model capacity than previously considered in the literature, leading to higher model quality at a fixed computational budget.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall the paper is well written and clear, and the improvements are compelling.\n\nI wish the fully instantiated linear algorithms were presented in the same notation as algorithm 2 (the reference algorithms expressed in hypergraph terminology) as that would make it easier to understand particular details of the linear parametrization used in the paper.\n\nI also wish the linear algebra was expressed directly as well as being coated in kernel language. AFAICT this is a fundamental property of the fact that the matrix of probabilities might be expressible in a factorized form; this allows for the HMM case to reparametrize a multiplication of the form [labels, labels] [labels] with complexity O(labels^2) with a multiplication of the form [labels, features] [features, labels] [labels] which can be computed in O(features * labels) if the multiplication is associated to the right (i.e. [labels, features] ([features, labels] [labels])).\n\nOne thing which is not obvious to me from reading the paper is how does this ensure that the probability distribution of the PCFGs/HMMs remains normalized, while with a softmax parametrization it's trivial to ensure that every conditional probability is normalized. This would also be improved by more details on the particular algorithm used.\n\nClarifying the linear algebra structure would also help clarify generalizations to other semirings (like the max-product ring useful when doing maximum a posteriori inference and where the normalization of the conditional probabilities is immaterial).\n\nI believe the paper needs to be revised to more explicitly clarify the issues raised above.\n\nMinor nits:\n line 46, \"attention\" is repeated\n\n\n---\n\nNote: score revised after author response.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No issues here.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "fc94rYiiNx", "reviewer": "Reviewer_Ys2d", "summary": "A variety of structured probabilistic models (HMMs, PCFGS, etc) permit inference using dynamic programming. A primary driver of computational cost is the matrix multiplications required for passing the messages in the associated hyper-graph. This paper proposes using low-rank matrices for the costs in these hyper-edges, which allows for cost that scales with the rank of the matrix. Since this is rank is a free parameter, it can be used to tune a speed-accuracy tradeoff.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Expressivity of the model**\nCan you formally argue why using a model with high-dimensional hidden states, but a low-dimensional kernel, is not equivalent to a model with lower-dimensional hidden states? It's definitely not clear why the machinery of this paper is necessary, when the hidden state size is a hyperparameter that the user could decrease if computational complexity was an issue. If they're not formally equivalent, they still strike me as similar in terms of expressivity (which is supported by your experiments).\n\n\n**Training**\nThere are far too few details regarding how the models are trained. I'm assuming you used EM. This is very dependent on initialization in practice. How did you do it?\n\n\n**Computational Complexity**\nWith modern hardware, big-O analysis may not be helpful because certain operations can be done in parallel. For example, for O(L N^2) inference, the cost is sequential in L, but parallelizable in N. Also, for certain ranges of N, the cost of matrix multiplication on a GPU is more or less constant. \n\n\nThe right panel of fig 1 should be in log space. Does it give the slope we expect? \n\n**Results**\nI expected to see much more of an analysis of an accuracy-speed tradeoff. However, besides the HMM experiments, all other results only consider accuracy. In terms of accuracy, I could not find a convincing result demonstrating that using LHMM vs. HMM or LPFCG vs. PCFG gave a meaningful performance improvement. \n\n\nOverall, I am confused why much of the analysis sweeps over the number of hidden states. Shouldn't this just be a hyper-parameter that gets tuned for each model? For example, figure 1 would be much more clear if it was collapsed into a single scatter plot of PPL vs. speed. \n\n\n**Related Work**\nI found a few important related papers. Can you comment on the relationship between your proposed method and these works?\n\nThai et al., \"Embedded-State Latent Conditional Random Fields for Sequence Labeling\" \n\nMcAuley et al., \"Exploiting Data-Independence for Fast Belief-Propagation\"\n\nBelanger et al., \"MAP Inference in Chains using Column Generation\"\n\n\n**After authors' response**\nScore raised from weak reject to weak accept.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "eodOW3LShI", "reviewer": "Reviewer_51Nb", "summary": "Structured models e.g. HMM are shown to have good performance when the number of labels is very large. As one of the main computational bottlenecks of this is matrix-vector multiplications, the paper proposes to use low-rank decomposition to reduce the matrix-vector multiplication cost. The key challenge is which kernel to use for the low-rank decomposition so that the property of the transition matrix still holds. \n\nThe paper presents several experiments, cover several fields applications (language modelling, music modelling, video modelling) and structured architectures (HMM, CFG, HSMM). The proposed low-rank decomposition is shown to help reduce computational cost (2 to 2^6 times) while losing little or no accuracy. \n\nContributions: \n- the paper proposes low-rank decomposition for matrix-vector multiplication to reduce the computational cost of structured architecture when the number of labels is very large, \n- the proposed low-rank decomposition is applicable to any structured architectures whose a bottleneck is matrix-vector multiplication\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality** \n\nAs low-rank decomposition proposed in this paper is very much similar to e.g. Choromanski et al (2020), it is hard to say that the work is original. The main difference of the paper is that the authors apply similar decomposition technique to structured models, with thoughtful arguments (e.g. how to apply to HMM, CRF) and experiments.  \n\n**Quality** \n\nAs structured models (e.g. HMM, CFG) and low-rank decomposition similar in this paper are well studied, the paper is technically sound. The experiment results confirm that the proposed low-rank decomposition work as expected: the computational time is reduced about 8 times (depending on settings) whereas the accuracy lost is small.  \n\n**Clarity** \n\nThe paper is very well written, with lots of details, thorough experiments. I particular like the flow of the paper, showing the clear motivation: from how to use matrix language describing structured models to the use of kernels. \n\nThere are some points that I didn't catch: \n1. Line 145: what is the role of  \\alpha_v here?\n2. The authors drop the normalising constants c after the equation line 140. It is unclear how these factors are learnt. \n3. In the experiments, N has different ranges for different experiments (line 219 - 226). This leads to one more hyper param to tune. I'm wondering whether it's a problem, or whether the authors have a \"universal\" wisdom to choose N. \n4. In practise, is the computation time reduction worth? For instance, looking at table 1, AWD-LSTM significantly outperforms LHMM (57.3 vs 131.8 ppl). If we make AWD-LSTM to have similar running time like LHMM (e.g. reduce its #parameters), will be AWD-LSTM outperformed by LHMM?\n\nThe most crucial thing that I hardly get is the title of the paper \"linearized structured models\". Although I see where \"linearize\" comes from, this title is misleading as it might give a reader (e.g. me) an intuition that the paper proposes a method to turn nonlinear models to linear model.\n\n**Significance** \n\nThis paper proposes an interesting idea for reducing theoretical computational cost. This theoretical result is important, though it is hard to see whether the empirical result is. \n\n\nAll in all I like the paper, but its originality is questionable. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The submission includes \"potential negative impact\" in an appendix. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7h"}, "extra_text": {}}, {"review_id": "H2ES2LgLzU0", "reviewer": "Reviewer_HMa8", "summary": "The paper proposes an approach to reduce the cost of dynamic programming inference in structured discrete models such as HMMs and PCFGs. Viewing each message passing step as a multiplication by a matrix of conditional scores, the proposed approach replaces this matrix by a low-rank matrix, parameterized as the linearization of a finite-dimensional kernel evaluated on state embeddings. This speeds up inference by roughly a factor of `L / N`, where L is the number of states and N is the rank of the kernel. The method is evaluated for HMMs on tasks of modeling language and polyphonic music, for PCFG parsing on the Penn Treebank, and for a video modeling task with HSMMs.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is overall well written and straightforward to follow. I quite liked the unified exposition of dynamic programming algorithms as matrix-vector multiplication on hypergraphs. These algorithms are fundamental even in the modern 'neural' paradigm, and a convincing asymptotic speedup would be a significant contribution.\n\nUnfortunately, I don't think the abstract's claim that \"we can reduce the complexity of inference by a factor of the hidden state size\" is supported by the experiments. Given that claim, I would expect to see LHMM experiments using a factor of N more states than the largest practical HMMs, but the experiments explore only relatively small constant factors (2:1, 4:1, etc, maxing out around 32:1), and even then struggle to demonstrate practical gains. That said, I do applaud the both range of experiments and the inclusion of relevant baselines.\n\nMy fundamental issue with the story of this paper is that I don't have any intuition (and the paper doesn't seem to provide any) for why an LHMM with L states and rank N < L should be a different model class from just learning an HMM on N states, which is even cheaper (and the analogous statement for PCFGs). Given a rank-N transition matrix, you can always derive an equivalent HMM on a set of N 'abstract' states $w_t \\in Z_N$, with transition probabilities $$p(w_{t+1} | w_t) = \\sum_z p(w_{t+1} | Z_t=z) p(Z_t =z| w_t) = (V_{e_1})^T_{w_{t + 1}} (U_{e_2})_{w_t}$$\nand emission model\n$$p(x_t | w_t) = \\sum_z p(x_t | Z_t=z)p(Z_t = z | w_t)$$\nderived by marginalizing out the L-dimensional state vectors. The 2009 Siddiqi et al. work on low-rank HMMs explicitly acknowledges this (the abstract mentions that 'the dynamics evolve in a k-dimensional subspace') but focuses on the case with Gaussian emissions, where you do at least end up with more expressivity from implicitly emitting a mixture of L rather than N Gaussians (this would explain the improvement of LHSMM over HSMM for the video modeling task), but in the discrete case I'm not sure why you wouldn't just use the smaller model. Can the authors comment? I could imagine that overparameterizing the model might be helpful for optimization, or that the ability to also add banded structure makes the higher-rank model more interesting, but I'd want to see those stories developed and supported by evidence. Either way, I think this equivalence is worth mentioning.\n\nAs a somewhat more superficial quibble, I found the framing in terms of kernels a bit confusing. The 'point' of kernel methods is generally that you can use the dual representation (or approximations like random features) to work in high-dimensional spaces without paying the corresponding costs. But if I understand the proposed approach, it's not attempting to linearize any particular high-dimensional computation; rather, it's explicitly learning a low-dimensional feature map. It seems like the main idea of the paper is essentially 'parameterize the score matrix as the product of low-dimensional embedding vectors learned by gradient descent'. That's a reasonable idea, but cloaking it in the language of kernels seems unnecessarily obfuscatory when it could equally well be explained with undergrad linear algebra (which is not a flaw! simple approaches are better, if they work well).\n\nI imagine that a lot was learned in the course of writing this paper, but in its current form I unfortunately don't think it rises past the NeurIPS bar. If I'm significantly misunderstanding the approach, that would of course change my view. At the least, I'd like to see the claims of order-of-magnitude improvement either scaled back, or supported by stronger evidence. \n\n****************************\nUpdate: Thanks to the authors for their response: as they point out, low-rank HMMs are more expressive than reduced-state-size HMMs even in the discrete case once you consider the joint distribution of $x_t$'s across timesteps (vs in the continuous case, where implicitly using a mixture of $L > N$ Gaussians would get you more expressivity even at a single timestep). This addresses my deepest concern with the paper, and I've increased my score by a point. I think this could be a solid paper with the promised revisions, though unfortunately can't fully credit them sight unseen.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations of the method (e.g., the restrictions on parameterization) are clearly discussed and examined experimentally, which is admirable.\n\nThe work is on core algorithms and raises no specific societal impact concerns.", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper analyzes the speed up in reduced-rank forms of HMMs and PCFGs. The reviewers agree that the paper is well written, has useful contributions, and the experiments are good. I strongly suggest following up on the change of title, including the low-rank HMM discussion, and the semi-ring discussions from the rebuttal process in the paper.
Decision: Accept (Poster)