Dynamic Programming in Rank Space: Scaling Structured Inference with Low-Rank HMMs and PCFGs

• URL: http://arxiv.org/abs/2205.00484v1
• Date: Sun, 1 May 2022 14:58:25 GMT
• Title: Dynamic Programming in Rank Space: Scaling Structured Inference with Low-Rank HMMs and PCFGs
• Authors: Songlin Yang, Wei Liu, Kewei Tu
• Abstract summary: Recent research found it beneficial to use large state spaces for HMMs and PCFGs. Inference with large state spaces is computationally demanding, especially for PCFGs. We leverage tensor rank decomposition to decrease inference computational complexities.
• Score: 35.31888995651471
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Hidden Markov Models (HMMs) and Probabilistic Context-Free Grammars (PCFGs) are widely used structured models, both of which can be represented as factor graph grammars (FGGs), a powerful formalism capable of describing a wide range of models. Recent research found it beneficial to use large state spaces for HMMs and PCFGs. However, inference with large state spaces is computationally demanding, especially for PCFGs. To tackle this challenge, we leverage tensor rank decomposition (aka.\ CPD) to decrease inference computational complexities for a subset of FGGs subsuming HMMs and PCFGs. We apply CPD on the factors of an FGG and then construct a new FGG defined in the rank space. Inference with the new FGG produces the same result but has a lower time complexity when the rank size is smaller than the state size. We conduct experiments on HMM language modeling and unsupervised PCFG parsing, showing better performance than previous work. Our code is publicly available at \url{https://github.com/VPeterV/RankSpace-Models}.

Related papers

• Gaussian Ensemble Belief Propagation for Efficient Inference in High-Dimensional Systems [3.6773638205393198]
  Efficient inference in high-dimensional models is a central challenge in machine learning. We introduce the Ensemble Kalman Filter (EnKF) and Gaussian Belief Propagation (GaBP) GEnBP updates ensembles of prior samples into posterior samples by passing low-rank local messages over the edges of a graphical model.
  arXiv  Detail & Related papers  (2024-02-13T03:31:36Z)
• Simple Hardware-Efficient PCFGs with Independent Left and Right Productions [77.12660133995362]
  This work introduces emphSimplePCFG, a simple PCFG formalism with independent left and right productions. As an unsupervised algorithm, our simple PCFG obtains an average F1 of 65.1 on the English PTB, and as a language model, it obtains a perplexity of 119.0, outperforming similarly-sized low-rank PCFGs.
  arXiv  Detail & Related papers  (2023-10-23T14:48:51Z)
• Learning Hidden Markov Models Using Conditional Samples [72.20944611510198]
  This paper is concerned with the computational complexity of learning the Hidden Markov Model (HMM) In this paper, we consider an interactive access model, in which the algorithm can query for samples from the conditional distributions of the HMMs. Specifically, we obtain efficient algorithms for learning HMMs in settings where we have query access to the exact conditional probabilities.
  arXiv  Detail & Related papers  (2023-02-28T16:53:41Z)
• Variational Flow Graphical Model [22.610974083362606]
  Variational Graphical Flow (VFG) Model learns the representation of high dimensional data via a message-passing scheme. VFGs produce a representation of the data using a lower dimension, thus overcoming the drawbacks of many flow-based models. In experiments, VFGs achieves improved evidence lower bound (ELBO) and likelihood values on multiple datasets.
  arXiv  Detail & Related papers  (2022-07-06T14:51:03Z)
• Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games [76.21916750766277]
  We show that the Optimistic Multiplicative Weights Update (OMWU) algorithm can be simulated on the normal-form equivalent of an EFG in linear time per iteration in the game tree size using a kernel trick. Specifically, KOMWU gives the first algorithm that guarantees at the same time last-iterate convergence.
  arXiv  Detail & Related papers  (2022-02-01T06:28:51Z)
• Low-Rank Constraints for Fast Inference in Structured Models [110.38427965904266]
  This work demonstrates a simple approach to reduce the computational and memory complexity of a large class of structured models. 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.
  arXiv  Detail & Related papers  (2022-01-08T00:47:50Z)
• Scaling Structured Inference with Randomization [64.18063627155128]
  We propose a family of dynamic programming (RDP) randomized for scaling structured models to tens of thousands of latent states. Our method is widely applicable to classical DP-based inference. It is also compatible with automatic differentiation so can be integrated with neural networks seamlessly.
  arXiv  Detail & Related papers  (2021-12-07T11:26:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.