内側-外側アルゴリズム

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

内部確率${\displaystyle \beta _{j}(p,q)}$単語を生成する全確率${\displaystyle w_{p}\cdots w_{q}}$ルート非終端が与えられた場合${\displaystyle N^{j}}$そして文法${\displaystyle G}$: ^{[ 1 ]}

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

外部確率${\displaystyle \alpha _{j}(p,q)}$開始記号から始まる確率の合計です${\displaystyle N^{1}}$非終端を生成する${\displaystyle N_{pq}^{j}}$そして外にあるすべての言葉${\displaystyle w_{p}\cdots w_{q}}$文法が与えられた場合${\displaystyle G}$: ^{[ 1 ]}

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

基本ケース:

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

一般的なケース：

ルールがあると仮定します${\displaystyle N_{j}\rightarrow N_{r}N_{s}}$文法では、生成する確率${\displaystyle w_{p}\cdots w_{q}}$根が${\displaystyle N_{j}}$は：

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

内部確率${\displaystyle \beta _{j}(p,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)}$

基本ケース:

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

ここで開始記号は${\displaystyle N_{1}}$。

一般的なケース：

ルールがあると仮定します${\displaystyle N_{r}\rightarrow N_{j}N_{s}}$生成する文法において${\displaystyle N_{j}}$すると、そのルールの外側確率への左側の寄与は${\displaystyle \alpha _{j}(p,q)}$は：

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

さて、あるルールがあるとしましょう。${\displaystyle N_{r}\rightarrow N_{s}N_{j}}$文法において。そして、 その規則の外部確率への正しい寄与${\displaystyle \alpha _{j}(p,q)}$は：

${\displaystyle \sum _{k=1}^{k=p-1}P(N_{r}\rightarrow N_{s}N_{j})\alpha _{r}(k,q)\beta _{s}(k,p-1)}$

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

${\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)}$

• J. Baker (1979):音声認識のための学習可能な文法。JJ Wolf および DH Klatt 編、第 97 回アメリカ音響学会で発表された音声通信論文集、547–550 ページ、マサチューセッツ州ケンブリッジ、1979 年 6 月。MIT。
• Karim Lari、Steve J. Young (1990):インサイド・アウトサイドアルゴリズムを用いた確率的文脈自由文法の推定. Computer Speech and Language、4:35–56.
• Karim Lari、Steve J. Young (1991): Inside–Outside アルゴリズムを用いた確率的文脈自由文法の応用. Computer Speech and Language、5:237–257.
• Fernando Pereira、Yves Schabes (1992):部分的に括弧で囲まれたコーパスからの内側-外側再推定。計算言語学会第30回年次大会論文集、計算言語学会、128-135。

• 内側・外側アルゴリズム - フェイ・シア
• インサイド・アウトサイド・アルゴリズム - マイケル・コリンズ