内側-外側アルゴリズム
Parameter estimation method for probabilistic context-free grammars

コンピュータサイエンスにおける構文解析アルゴリズムにおいて、インサイド・アウトサイド・アルゴリズムは、確率文脈自由文法における生成確率を再推定する方法である。これは、隠れマルコフモデルのパラメータ推定のための順方向・逆方向アルゴリズムを確率文脈自由文法に一般化したものとして、1979年にジェームズ・K・ベイカーによって導入された。これは、例えば期待値最大化アルゴリズム（教師なし学習アルゴリズム） の一部として、期待値を計算するために使用される。

内部確率と外部確率

内部確率は、語根非終端記号と文法が与えられた場合に単語を生成する全確率である：[1] β j ( p , q ) {\displaystyle \beta _{j}(p,q)} w p ⋯ w q {\displaystyle w_{p}\cdots w_{q}} N j {\displaystyle N^{j}} G {\displaystyle G}

β j ( p , q ) = P ( w p q | N p q j , G ) {\displaystyle \beta _{j}(p,q)=P(w_{pq}|N_{pq}^{j},G)}

外側確率は、文法が与えられたときに、開始記号から始まり、非終端記号と外側のすべての単語を生成する合計確率です。[1] α j ( p , q ) {\displaystyle \alpha _{j}(p,q)} N 1 {\displaystyle N^{1}} N p q j {\displaystyle N_{pq}^{j}} w p ⋯ w q {\displaystyle w_{p}\cdots w_{q}} G {\displaystyle G}

α j ( p , q ) = P ( w 1 ( p − 1 ) , N p q j , w ( q + 1 ) m | G ) {\displaystyle \alpha _{j}(p,q)=P(w_{1(p-1)},N_{pq}^{j},w_{(q+1)m}|G)}

内部確率の計算

基本ケース:

β j ( p , p ) = P ( w p | N j , G ) {\displaystyle \beta _{j}(p,p)=P(w_{p}|N^{j},G)}

一般的なケース:

文法に規則があるとすると、をルートとするサブツリーから始まる生成の確率は次のようになります。 N j → N r N s {\displaystyle N_{j}\rightarrow N_{r}N_{s}} w p ⋯ w q {\displaystyle w_{p}\cdots w_{q}} N j {\displaystyle N_{j}}

∑ k = p k = q − 1 P ( N j → N r N s ) β r ( p , k ) β s ( k + 1 , q ) {\displaystyle \sum _{k=p}^{k=q-1}P(N_{j}\rightarrow N_{r}N_{s})\beta _{r}(p,k)\beta _{s}(k+1,q)}

内部確率は、そのようなすべての可能なルールの合計です。 β j ( p , q ) {\displaystyle \beta _{j}(p,q)}

β j ( p , q ) = ∑ N r , N s ∑ k = p k = q − 1 P ( N j → N r N s ) β r ( p , k ) β s ( k + 1 , q ) {\displaystyle \beta _{j}(p,q)=\sum _{N_{r},N_{s}}\sum _{k=p}^{k=q-1}P(N_{j}\rightarrow N_{r}N_{s})\beta _{r}(p,k)\beta _{s}(k+1,q)}

外部確率の計算

基本ケース:

α j ( 1 , n ) = { 1 if  j = 1 0 otherwise {\displaystyle \alpha _{j}(1,n)={\begin{cases}1&{\mbox{if }}j=1\\0&{\mbox{otherwise}}\end{cases}}}

ここで、開始シンボルは です。 N 1 {\displaystyle N_{1}}

一般的なケース:

文法の中に を生成する規則があると仮定する。その規則の外側確率への左寄与は次のようになる。 N r → N j N s {\displaystyle N_{r}\rightarrow N_{j}N_{s}} N j {\displaystyle N_{j}} α j ( p , q ) {\displaystyle \alpha _{j}(p,q)}

∑ k = q + 1 k = n P ( N r → N j N s ) α r ( p , k ) β s ( q + 1 , k ) {\displaystyle \sum _{k=q+1}^{k=n}P(N_{r}\rightarrow N_{j}N_{s})\alpha _{r}(p,k)\beta _{s}(q+1,k)}

さて、文法に規則があると仮定します。 その規則の外側の確率への寄与は次のようになります。 N r → N s N j {\displaystyle N_{r}\rightarrow N_{s}N_{j}} α j ( p , q ) {\displaystyle \alpha _{j}(p,q)}

∑ k = 1 k = p − 1 P ( N r → N s N j ) α r ( k , q ) β s ( k , p − 1 ) {\displaystyle \sum _{k=1}^{k=p-1}P(N_{r}\rightarrow N_{s}N_{j})\alpha _{r}(k,q)\beta _{s}(k,p-1)}

外側の確率は、そのようなすべてのルールにおける左と右の寄与の合計です。 α j ( p , q ) {\displaystyle \alpha _{j}(p,q)}

α j ( p , q ) = ∑ N r , N s ∑ k = q + 1 k = n P ( N r → N j N s ) α r ( p , k ) β s ( q + 1 , k ) + ∑ N r , N s ∑ k = 1 k = p − 1 P ( N r → N s N j ) α r ( k , q ) β s ( k , p − 1 ) {\displaystyle \alpha _{j}(p,q)=\sum _{N_{r},N_{s}}\sum _{k=q+1}^{k=n}P(N_{r}\rightarrow N_{j}N_{s})\alpha _{r}(p,k)\beta _{s}(q+1,k)+\sum _{N_{r},N_{s}}\sum _{k=1}^{k=p-1}P(N_{r}\rightarrow N_{s}N_{j})\alpha _{r}(k,q)\beta _{s}(k,p-1)}

参考文献

  1. ^ ab マニング、クリストファー D.;ヒンリヒ・シュッツェ (1999)。統計的自然言語処理の基礎。米国マサチューセッツ州ケンブリッジ：MIT Press。 388–402ページ。ISBN 0-262-13360-1。
  • J. Baker (1979): 音声認識のための学習可能な文法. JJ WolfとDH Klatt編著,アメリカ音響学会第97回大会音声コミュニケーション論文集, 547–550ページ, マサチューセッツ州ケンブリッジ, 1979年6月. MIT.
  • Karim Lari, Steve J. Young (1990): Inside-Outsideアルゴリズムを用いた確率文脈自由文法の推定. Computer Speech and Language , 4:35–56.
  • Karim Lari, Steve J. Young (1991): Inside-Outsideアルゴリズムを用いた確率文脈自由文法の応用. Computer Speech and Language , 5:237–257.
  • フェルナンド・ペレイラ、イヴ・シャベス (1992): 部分的に括弧で囲まれたコーパスからの内外再推定.計算言語学協会第30回年次会議議事録, 計算言語学協会, 128–135.
  • インサイド・アウトサイド・アルゴリズム - フェイ・シア
  • 内外アルゴリズム - マイケル・コリンズ
Retrieved from "https://en.wikipedia.org/w/index.php?title=Inside–outside_algorithm&oldid=1143544206"