論文の概要: Dynamic Programming in Rank Space: Scaling Structured Inference with
Low-Rank HMMs and PCFGs
- arxiv url: http://arxiv.org/abs/2205.00484v1
- Date: Sun, 1 May 2022 14:58:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-04 03:52:57.789832
- Title: Dynamic Programming in Rank Space: Scaling Structured Inference with
Low-Rank HMMs and PCFGs
- Title（参考訳）: ランク空間における動的プログラミング:低ランクHMMとPCFGによる構造化推論のスケーリング
- Authors: Songlin Yang, Wei Liu, Kewei Tu
- Abstract要約: 近年の研究では、HMMやPCFGに大規模な状態空間を使うことが有益であることが判明している。
大規模状態空間での推論は特にPCFGに対して計算的に要求されている。
テンソル階数分解を利用して推論計算の複雑さを減少させる。
- 参考スコア（独自算出の注目度）: 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}.
- Abstract（参考訳）: 隠れマルコフモデル (HMMs) と確率的文脈自由文法 (PCFGs) は広く使われているモデルであり、どちらも幅広いモデルを記述することができる強力な形式主義である因子グラフ文法 (FGGs) として表される。
近年の研究では、HMMやPCFGに大規模な状態空間を使うことが有益であることが示されている。
しかし、特にPCFGの場合、大きな状態空間での推論は計算的に要求される。
この課題に取り組むためにテンソル階分解(別名)を利用する。
CPD)は、HMMとPCFGを仮定するFGGのサブセットの推論計算複雑性を減少させる。
FGG の因子に CPD を適用し、次に階数空間で定義される新しい FGG を構築する。
新しいFGGによる推論は、同じ結果をもたらすが、ランクサイズが状態サイズよりも小さい場合、時間の複雑さが小さくなる。
我々は,HMM言語モデリングと教師なしPCFG解析の実験を行い,従来よりも優れた性能を示した。
我々のコードは \url{https://github.com/VPeterV/RankSpace-Models} で公開されている。
関連論文リスト
- Gaussian Ensemble Belief Propagation for Efficient Inference in High-Dimensional Systems [3.6773638205393198]
高次元モデルにおける効率的な推論は、機械学習における中心的な課題である。
本稿では Ensemble Kalman Filter (EnKF) と Gaussian Belief Propagation (GaBP) を紹介する。
GEnBPは、グラフィカルモデルのエッジに低ランクのローカルメッセージを渡すことで、先行サンプルのアンサンブルを後続サンプルに更新する。
論文 参考訳（メタデータ） (2024-02-13T03:31:36Z) - Simple Hardware-Efficient PCFGs with Independent Left and Right
Productions [77.12660133995362]
この研究は、独立した左右のプロダクションを持つ単純なPCFG形式であるemphSimplePCFGを導入している。
教師なしのアルゴリズムとして、我々の単純なPCFGは英語 PTB の平均 F1 65.1 を取得し、言語モデルとして、119.0 のパープレキシティを得る。
論文 参考訳（メタデータ） (2023-10-23T14:48:51Z) - Learning Hidden Markov Models Using Conditional Samples [72.20944611510198]
本稿では,隠れマルコフモデル(HMM)の学習における計算複雑性について述べる。
本稿では,HMMの条件分布からサンプルを問合せする対話型アクセスモデルを提案する。
具体的には、正確な条件付き確率に対するクエリアクセスが可能な設定において、HMMを学習するための効率的なアルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-28T16:53:41Z) - Variational Flow Graphical Model [22.610974083362606]
変分グラフフロー(VFG)モデルは,メッセージパッシング方式を用いて高次元データの表現を学習する。
VFGは低次元を用いてデータの表現を生成し、多くのフローベースモデルの欠点を克服する。
実験では、VFGは改良されたエビデンスローバウンド(ELBO)と複数のデータセットの確率値を達成する。
論文 参考訳（メタデータ） (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]
カーネルトリックを用いて,最適乗算重み更新(OMWU)アルゴリズムをゲームツリーサイズ毎のリニア時間でEFGの正規形等価値にシミュレート可能であることを示す。
特に、KoMWUは、最終点収束を同時に保証する最初のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-02-01T06:28:51Z) - Low-Rank Constraints for Fast Inference in Structured Models [110.38427965904266]
この研究は、大規模構造化モデルの計算とメモリの複雑さを低減するための単純なアプローチを示す。
言語モデリング,ポリフォニック・ミュージック・モデリング,教師なし文法帰納法,ビデオ・モデリングのためのニューラルパラメータ構造モデルを用いた実験により,我々の手法は大規模状態空間における標準モデルの精度と一致することを示した。
論文 参考訳（メタデータ） (2022-01-08T00:47:50Z) - Scaling Structured Inference with Randomization [64.18063627155128]
本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。
我々の手法は古典的DPベースの推論に広く適用できる。
また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
論文 参考訳（メタデータ） (2021-12-07T11:26:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。