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 ELi 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 Hy, 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 are 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 V. E NRxll then the matrix-vector products can be computed in time O(EE) x L x N) as follows:
V.B, 108,=(UJ)) (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 (uu.,..) ((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 x,,,), 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) [Mareus 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. [0200], 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-specff 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 matrix-vector 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. manlp-main. 103. URL http:ttts////ww.llllet 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. wttpiiiwwweetteeee www//ferrmmiideeeemeeeee Btte:/orruunnddB-BBBBg
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::/arxia 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///nholoogg/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 httefformmm.---QQTTTTTEE.E
Guillaume Rabusseau, Borja Balle, and Shay B. Cohen. Weighted tree automata approximation by singular value truncation. CoRR, abs/1511.01442, 2015. URL httt:://arxxv.org/abbs.. 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.JgeskrFi
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://xxiiv..rg//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": "vfuV5W0-VOM", "reviewer": "Reviewer_scrw", "summary": "The paper studies the problem of marginalization for a class of latent variable models defined over a hypergraph, which includes HMMs and PCFGs. The paper proposes a method to reduce the time and memory complexity of marginalization by a factor of $L/N$, where $L$ is the size of the label set and $N$ is a feature dimension to be chosen. In particular, the larger $N$ is, the more expressive the distribution of the model is. The idea of the method is to use kernel linearization to parameterize the conditional probabilities of the model.", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "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 theoretical part is in general clear. A small thing that confused me was that section 3 never said how $K$ or $\\phi$ was chosen. It took me a while to realize that this is a “user choice”, and to see how you choose it in the experiments section. Maybe this could be clarified earlier.\n\nIn the empirical part, my main concern is that the paper does not report the speed of the algorithm for the experiments other than the first one. There is no explanation for this — the text just shifts from talking about speed to talking about $L/N$ and time complexity. This implicitly suggests that the speedups are not significant for these experiments. If this interpretation is wrong and there are actual speedups, I think it would be very important to include the evidence for them. Practical speedups seem to be a very important ingredient of this paper, and the paper claims such speedups (e.g., at lines 49-59, it claims that “the decomposition allows us to greatly increase the speed of inference”). If there are no practical speedups, it is not clear that the method is very useful (although the memory improvements could still be useful). The improvement in time complexity is, in my opinion, not very relevant for this paper, since it is already mainly a heuristic (because of the kernel linearization with small $N$), so I feel that it should be evaluated based on its practical merits.\n\nIt is also not clear why ratios smaller than 1/8 were not chosen. It seems that it would have been helpful to look into this in order to understand better the limitations of the proposed method.\n\nMinor comments:\n\nIn figure 1, why does a ratio of 2:1 consistently outperform softmax in perplexity, even with small number of states? Maybe a comment about this would be useful.\n\nAlso, the order in which the models are discussed in section 2 differs from section 3.2. (But this is not really important.)\n\nTypos:\n - 44: \"attention attention\"\n - 114: \"generate process\"\n - 148: missing space between \".\" and \"Algorithm\"\n - 199: \"to nonterminal to nonterminal\"\n\nConclusion: I recommend rejection, mainly because of the omission of evidence for practical speedups, which to me looks like a major limitation.\n\n----\n\nUPDATE: The authors added some more evidence for practical speedups, as I originally requested. However, as another reviewer notices, these speedups are fairly modest, and as such they do not convince me that the proposed technique leads to significant practical speedups. I maintain my original score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some of the technical limitations were discussed in the main review. Other than that, I think the paper is fine.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "t_MHCW0Z9m", "reviewer": "Reviewer_1AvQ", "summary": "This paper focuses on scaling unsupervised latent structure models such as HMM and PCFG, whose training/inference time complexity scales quadratically or cubically with the hidden state size. Specifically, the authors view the central inference step in the dynamic program as a matrix-vector product and apply a kernel linearization constraint, and as a result reduce the complexity of inference by a factor of the hidden state size. Experiments are conducted on language modeling, music modeling, and video modeling, covering HMM, PCFG, and HSMM models to evaluate the proposed technique. \n", "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": "I’ll detail the strengths, weaknesses, and questions below:\n\n### Strengths\n\n\n1. The problem studied in this paper is important. Reducing the quadratic or cubic complexity in latent structure models is critical for them to scale up to large datasets/models and potentially compete with typical neural models.\n\n\n2. The proposed method is effective theoretically, reducing the complexity by a factor of hidden state size.\n\n\n3. The experiments are extensive, evaluating three different models (HMM, PCFG, HSMM) on three different tasks. Experimental results indicate that the proposed technique is able to achieve speed-up while obtaining comparable PPL or NLL to the vanilla version.\n\n\n\n\n\n### Weaknesses\n\n1. I think that efficiency should be evaluated empirically as one of the main metrics in most settings in this paper (currently the only efficiency evaluation is Figure 1), given that improving efficiency/scaling is the main goal. While the speed-up is clear on the theoretical side, the practical benefits it brings (e.g. training and inference time) are related to the model size or data size. Therefore, it is important to demonstrate the total training/inference time in every setting/dataset and how it compares with the baselines, otherwise, it is difficult to judge whether the theoretical speed-up would really make a difference in practice. \n\n\n2. The proposed method limits the rank of the transition probability matrix to be a relatively small value, which clearly limits the capacity as acknowledged by the authors. It is good that the paper proposes possible solutions to mitigate this issue (Table 1), but the efficiency of the “LHMM + band” method should be reported empirically to understand its actual overhead. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "d0Puc8_qLVR", "reviewer": "Reviewer_Kr3H", "summary": "HMMs used to be the method of choice in speech (and other apps) before nets took over.  This paper proposes a way to think about HMMs (and more) in a way that might make them more competitive again.  This perspective offers the hope that we can come up with a unified framework that includes HMMs and nets and more.  It would be very nice to have such a unified framework.\n\nWith a trigram model, for example, the number of states grows quickly.  The number of trigrams could be V^3 , where V is the size of the vocabulary, though actually, it is also limited by N_train, the size of the training set.  In practice, V^3 >> N_train, but even so, the number of states can easily become problematic.\n\nThis paper proposes a linearization so inference time is me O(TLN), where T is the length of the input, L is the size of the label space and N is the feature dimension.  There are obvious consequences for time here.  \n\nIt is less clear though exactly how the parameterization is done.  Appendix C suggests that there are different parameterizations for each task, which is somewhat disappointing.  One might expect that these parameterizations introduce certain approximations.  Is it possible to estimate bounds on these approximations?  If each task is approximated differently, maybe the proposed unified framework is not all that unified.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "This paper is mainly a theoretical paper.  It is intended to provide an understanding of traditional methods such as HMMs and PCFGs in a way that is more comparable with modern methods.  This is an admirable goal.\n\nThe crux of the suggestion is referred to as parameterization, as illustrated in equations (5) and (6).   These equations are presented as facts, but I assume they are approximations.\n\nFigure 1 suggests that the proposed parameterization has some advantages over HMMs in terms of speed; 8:1 state-to-rank ratio has comparable in performance (PPL) to HMMs, and considerable advantages in terms of speed.\n\nFigure 2 is similar to Figure 1, but for another task.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I would really like to understand better what is meant by parameterization.  Factoring?  Approximation?  Can we say more about the properties that the parameterization should have?\n\nI really hate papers with code, but are there ways to compare the results in this paper with those results?  Superficially, these results seem to be far from SOTA.  Maybe that is beside the point, but if these results are not competitive, the paper should make that clear.\n\nI assume the point of this paper is to give some insight as to why modern methods are better than traditional methods, and to suggest a direction to move in that could help understand this gap.  As such, the point of the experiments is more to show that the proposed parameterization improves traditional methods than to claim that they are better than the best alternatives.\n\nOne more flame... I really really hate the practice that has become all too standard of reporting perplexity on Penn Treebank, but actually replacing most of the content in the Penn Treebank with <unk>, as described in the appendix.    The Penn Treebank becomes unreadable after these replacements.  If we replaced all words with <unk>, PPL would be very impressive (but useless in any practical setting).  What does it mean to report perplexity when <unk> is one of the more common words in the vocabulary?  As a reviewer, I can't fault a paper for following precedent, but this precedent is not likely to advance the field.\n\n", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "91F8Phiqeh_", "reviewer": "Reviewer_6Rb7", "summary": "This work proposes to reduce the runtime of the marginalization computation needed for inference in structured (graphical) models. Some examples of such models are: Hidden-Markov Models (HMM), Hidden Semi-Markov Models (HSMM), and Probabilistic Context Free Grammars (PCFG). In order to infer in this models, multiple matrix-vector multiplications are needed, cause of the bottleneck computation. The authors proposed to solve this problem by approximating the matrix-vector multiplication in the computation bottleneck by an approximated low rank factorization. This is achieved by considering kernelized approximations, yielding a reduced runtime complexity by a factor of the number of states. Such reduction allows for scaling approximate methods to larger models (more states). Lastly, the method is tested on a set of sequential data tasks showing similar accuracy to standard models but with increased runtime performance.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "This paper uses combinations of ideas to reduce the runtime complexity for the marginalization of a (structured) graphical model. Kernel methods and kernelized approximations are not new topics. Nevertheless, such application to structured models for runtime improvement is novel to the best of my knowledge.\n\nIn general, the submission covers all the technical details properly. However, several important details have been relegated to the supplementary material (like the definition of $K$ used for the models). Further the authors proposed a \"neural\" parameterization without much explanation or reference. These neural parameterizations required to train weights and are non-linear. Details on how to train them are missing. The claim the the property of linearization of $\\Psi$ (line 139) has no reference or proof. Further, it is unclear why $\\Psi$ is a square matrix (assuming 2 tail nodes, it looks rectangular). It could be interesting to try data with exponential decay to evaluate the HMM models as PTB and other types of data have a power law decay that cannot be captured with HMMs (see [1]). The quality of the approximation of $\\Psi$ with different kernels was not explored and as a function of the number of states. Such experiment could share insights about the quality of the final result. \n\nThe paper is well organized and most of it reads nicely. Hypergraphs and the subsequent definition of inference in each of the models, introduces a lot of notation that is hard to follow. One or more figures could help to reduce this burden on the reader. Note that each model has a different final solution given by the selected kernels. Important details are missing that can help understand the paper and reproduce it (see comments above and questions below).\n\nThe problem is an important bottleneck problem in graphical models and interesting to the NeurIPS community. The work has valuable practical aspects, and demonstrates the capability of scaling to a higher number of states. \n\nQuestions for the authors:\n1. Your work relies on kernelized approximations of $\\Psi$ matrices. Can you explain in more detail why directly approximating each matrix $\\Psi$ as a low rank decomposition is not a good option?  \n2. How good is the approximation of the kernelized $\\Psi$ matrices? What properties hold by using the kernels for the system?\n3. What hardware is used for the experiments?\n\n\nMinor:\n* Formatting of captions in tables is incorrect.\n\nReferences\n\n[1] Mahto et al. \"Multi-timescale Representation Learning in LSTM Language Models\", ICLR 2021.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Negative societal impact was included with the supplementary material instead of the main paper.\nError bars/standard deviations were not included in the paper. Is hard to assess the significance of some results.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {"ethical_concerns": "The Penn TreeBank (PTB) is not a publicly available dataset and includes a paid license. Authors should consider verifying that this is not an issue with the LDC, owners of the PTB dataset.\n\n\n\n==================\nUPDATE: after rebuttal\n\nAfter reading all the reviews and responses, I decided to modify my score under the expectation that authors will add important details and explanations on the parameterization, and will include timings in the experimental sections.\n\n"}}]

Author rebuttal:

Meta-review: This paper presents an an approach to speeding up marginalization in structured unsupervised models by using a low-rank approximation to corresponding matrix (HMM) and tensor multiplies (PCFG). Experiments are conducted on a variety of tasks. Reviewers are split -- two in favor and two opposed. Generally, reviewers appreciated the paper's clarity, viewed the underlying algorithmic idea positively, and saw the paper's goal of speeding up structured unsupervised models as important and well-motivated. The main concern shared by many reviewers relates to the empirical results and practicality of the proposed approach. While the proposed approach does reduce asymptotic bounds on computation, it also reduces model capacity. The question of whether the proposed approach offers a practical speedup (or reduction in memory consumption) at useful performance levels is an important one. The draft included very few experiments measuring runtime. Author response provided more complete runtime comparisons with baselines, but unfortunately showed very modest gains (and in some cases, none at all). Thus, taking these points in balance, I lean towards rejection. However, I do encourage authors to revise experiments and resubmit if more practical gains can be achieved.  
Decision: Accept (Poster)