HHMM変換を用いた左非循環PCFGの高速推論

IPSJ

Bibliographic Information

Other Title
  • Efficient Inference of Left Acyclic PCFG Using HHMM Transformation

Search this article

Abstract

確率的文脈自由文法（PCFG）は，系列データの統語構造を推定する機械学習モデルであり，自然言語処理をはじめとしてプラン認識やアクセスログ解析など広範な分野で利用されている．しかし，PCFGの代表的な推論アルゴリズムであるInside-outside algorithmは，計算量が系列長に対して3乗のオーダであり，長い系列を含むデータセットの解析は現実的でないという問題がある．本研究では，PCFGを定義する文法が左非循環文法（Left Acyclic Grammar; LAG）と呼ぶ制約を満たすことを条件として，PCFGを階層型隠れマルコフモデル（Hierarchical Hidden Markov Model; HHMM）に等価変換することにより，線形時間で等価なPCFGの推論を行う手法を提案する．実験により，提案手法によってInside-outside algorithmと等価な事後確率分布の推論が可能であることを確認し，特に長い系列を含むデータセットにおいて大幅な高速化が可能になることを示す．

Probabilistic Context Free Grammar (PCFG) is a machine learning model for estimating latent syntactic structures of sequence data, which has a wide application area such as natural language processing, plan recognition and log analysis. However, the standard inference method for PCFGs, inside-outside algorithm, has cubic-time complexity for input sequence that makes it impractical to apply to long sequence data. In this study, we propose a linear-time inference method for PCFGs by using equivalent transformation into Hierarchical Hidden Markov Model (HHMM) under a condition of grammar named Left Acyclic Grammar (LAG). We give the experimental results that demonstrate our proposal method estimates exactly identical posterior distribution with inside-outside algorithm does, and show the execution time is dramatically improved especially for long sequence data.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top