WFSTに基づく確率文脈自由文法およびその拡張文法の高速EM学習法  [in Japanese] Efficient EM Learning of probabilistic CFGs and their extensions by using WFSTs  [in Japanese]

Access this Article

Search this Article

Author(s)

    • 亀谷 由隆 KAMEYA Yoshitaka
    • 東京工業大学大学院情報理工学研究科計算工学専攻 Department of Computer Science, Graduate School of Information Science and Engineering, Tokyo Institute of Technology
    • 森 高志 MORI Takashi
    • 東京工業大学大学院情報理工学研究科計算工学専攻 Department of Computer Science, Graduate School of Information Science and Engineering, Tokyo Institute of Technology
    • 佐藤 泰介 SATO Taisuke
    • 東京工業大学大学院情報理工学研究科計算工学専攻 Department of Computer Science, Graduate School of Information Science and Engineering, Tokyo Institute of Technology

Abstract

現在, 統計的言語モデルのークラスとして確率文脈自由文法 (PCFG) が広く知られている. また, 括弧なしコーパスからPCFGを訓練する方法としてInside-Outside (I-O) アルゴリズムが知られてきた. I-OアルゴリズムはPCFG用に効率化を施したEM (expectation-maximization) アルゴリズムだが, 依然その計算速度に問題があることが知られている. 本論文では, 文法構造があらかじめ与えられていることを前提に, 訓練過程を構文解析とEM学習に分離した高速EM学習法を提案する. その中間データ構造にパーザが生成するWFST (well-formed substring table) を用いる. 例えば, 一般化LRパーザを用いると事前コンパイル・ボトムアップ探索による効率性, およびChomsky標準形を要求しないという一般性を引き継ぐことができる. 一方EM学習では, WFSTのコンパクトさを利用して効率的なパラメタ推定が行なわれる. 推定結果はI-Oアルゴリズムで得られるものと一致する. 更に, 文脈依存性を取り入れたPCFGの拡張モデルに対する多項式オーダのEM学習法を示す. また, ATR対話コーパスを用いて実験を行ない, 訓練時間が大幅に短縮されていることを確認した.

Probabilistic context-free grammars (PCFGs) are a widely-known class of statistical language models. The Inside-Outside (I-O) algorithm is also well-known as an efficient EM algorithm tailored for PCFGs. Although the algorithm requires only inexpensive linguistic resources, there remains a problem in its efficiency. In this paper, we present a new framework for efficient EM learning of PCFGs in which the parser is separated from the EM algorithm, assuming the underlying CFG is given. A new EM procedure exploits the compactness of WFSTs (well-formed substring tables) generated by the parser. Our framework is quite general in the sense that the input grammar need not to be in Chomsky normal form (CNF) while the new EM algorithm is equivalent to the I-O algorithm in the CNF case. In addition, we propose a polynomial-time EM procedure for CFGs with context-sensitive probabilities, and report experimental results with ATR corpus and a hand-crafted Japanese grammar.

Journal

  • Journal of Natural Language Processing

    Journal of Natural Language Processing 8(1), 49-84, 2001-01-10

    The Association for Natural Language Processing

References:  26

Cited by:  3

  • Efficient Grammar Induction Algorithm with Parse Forests from Real Corpora  [in Japanese]

    KURIHARA Kenichi , KAMEYA Yoshitaka , SATO Taisuke

    Transactions of the Japanese Society for Artificial Intelligence 19, 360-367, 2004-11-01

    J-STAGE  References (15)

  • PRISM : A Logic Programming Language and System for Probabilistic Modeling  [in Japanese]

    KAMEYA Yoshitaka , SATO Taisuke , ZHOU Neng-Fa , IZUMI Yusuke , IWASAKI Tatsuya , Yoshitaka Kameya , Taisuke Sato , Neng-Fa Zhou , Yusuke Izumi , Tatsuya Iwasaki , 東京工業大学大学院情報理工学研究科計算工学専攻 , 東京工業大学大学院情報理工学研究科計算工学専攻 , 東京工業大学大学院情報理工学研究科計算工学専攻 , 東京工業大学大学院情報理工学研究科計算工学専攻 , Dept. of Computer Science Graduate School of Information Science and Engineering Tokyo Institute of Technology , Dept. of Computer Science Graduate School of Information Science and Engineering Tokyo Institute of Technology , CUNY Brooklyn College , Dept. of Computer Science Graduate School of Information Science and Engineering Tokyo Institute of Technology , Dept. of Computer Science Graduate School of Information Science and Engineering Tokyo Institute of Technology

    Computer Software 24(4), 2-22, 2007-10-26

    J-STAGE  References (59) Cited by (3)

  • A Description Method of Syntactic Rules on Filmscripts  [in Japanese]

    KUROSAWA YOSHIAKI , ICHIMURA TAKUMI , AIZAWA TERUAKI

    自然言語処理 = Journal of natural language processing 12(2), 25-62, 2005-03-31

    References (20)

Codes

  • NII Article ID (NAID)
    10008830219
  • NII NACSIS-CAT ID (NCID)
    AN10472659
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    13407619
  • NDL Article ID
    5634337
  • NDL Call No.
    Z21-B168
  • Data Source
    CJP  CJPref  NDL  J-STAGE 
Page Top