Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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. 

main_review: I’ll detail the strengths, weaknesses, and questions below:

### Strengths


1. 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.


2. The proposed method is effective theoretically, reducing the complexity by a factor of hidden state size.


3. 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.





### Weaknesses

1. 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. 


2. 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. 

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

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.

In 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. 

The 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).

The 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. 

Questions for the authors:
1. 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?  
2. How good is the approximation of the kernelized $\Psi$ matrices? What properties hold by using the kernels for the system?
3. What hardware is used for the experiments?


Minor:
* Formatting of captions in tables is incorrect.

References

[1] Mahto et al. "Multi-timescale Representation Learning in LSTM Language Models", ICLR 2021.
limitations_and_societal_impact: Negative societal impact was included with the supplementary material instead of the main paper.
Error bars/standard deviations were not included in the paper. Is hard to assess the significance of some results.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.
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.

In 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.

It 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.

Minor comments:

In 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.

Also, the order in which the models are discussed in section 2 differs from section 3.2. (But this is not really important.)

Typos:
 - 44: "attention attention"
 - 114: "generate process"
 - 148: missing space between "." and "Algorithm"
 - 199: "to nonterminal to nonterminal"

Conclusion: I recommend rejection, mainly because of the omission of evidence for practical speedups, which to me looks like a major limitation.

----

UPDATE: 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.
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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

With 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.

This 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.  

It 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.
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.

The 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.

Figure 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.

Figure 2 is similar to Figure 1, but for another task.
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?

I 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.

I 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.

One 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.
review_title: null

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)