WEKO3
アイテム
HHMM変換を用いた左非循環PCFGの高速推論
https://ipsj.ixsq.nii.ac.jp/records/141570
https://ipsj.ixsq.nii.ac.jp/records/1415702221926c-ce77-4c45-a172-20c8943b693d
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 2015 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | Trans(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 2015-03-30 | |||||||
タイトル | ||||||||
タイトル | HHMM変換を用いた左非循環PCFGの高速推論 | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | Efficient Inference of Left Acyclic PCFG Using HHMM Transformation | |||||||
言語 | ||||||||
言語 | jpn | |||||||
キーワード | ||||||||
主題Scheme | Other | |||||||
主題 | [研究論文] 確率文脈自由文法,階層型隠れマルコフモデル,左非循環文法 | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
資源タイプ | journal article | |||||||
著者所属 | ||||||||
筑波大学図書館情報メディア系 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Faculty of Library, Information and Media Science, University of Tsukuba | ||||||||
著者名 |
若林, 啓
× 若林, 啓
|
|||||||
著者名(英) |
Kei, Wakabayashi
× Kei, Wakabayashi
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 確率的文脈自由文法(PCFG)は,系列データの統語構造を推定する機械学習モデルであり,自然言語処理をはじめとしてプラン認識やアクセスログ解析など広範な分野で利用されている.しかし,PCFGの代表的な推論アルゴリズムであるInside-outside algorithmは,計算量が系列長に対して3乗のオーダであり,長い系列を含むデータセットの解析は現実的でないという問題がある.本研究では,PCFGを定義する文法が左非循環文法(Left Acyclic Grammar; LAG)と呼ぶ制約を満たすことを条件として,PCFGを階層型隠れマルコフモデル(Hierarchical Hidden Markov Model; HHMM)に等価変換することにより,線形時間で等価なPCFGの推論を行う手法を提案する.実験により,提案手法によってInside-outside algorithmと等価な事後確率分布の推論が可能であることを確認し,特に長い系列を含むデータセットにおいて大幅な高速化が可能になることを示す. | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 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. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AA11464847 | |||||||
書誌情報 |
情報処理学会論文誌データベース(TOD) 巻 8, 号 1, p. 45-54, 発行日 2015-03-30 |
|||||||
ISSN | ||||||||
収録物識別子タイプ | ISSN | |||||||
収録物識別子 | 1882-7799 | |||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |