確率文法とは

通常の文法ではパターンに一致するかしないかという1か0でしか評価できないが、確率文法は確率により一致度を評価するモデル。 配列パターンの例外を許すために配列を確率的にモデル化する。 確率文法モデルの生成は、文字列空間とその空間上の確率分布を定義しているのと同義である。

例

以下のように例外に対して低い確率を与えることで「だいたい正しい」パターンを認識できるようになっている。

S -> aW (0.45) S -> bW (0.45) 例外　S -> cW (0.1) (S, W: 非終端記号、a,b,c: 終端記号)

確率文法と生物学の関わり

DNA配列などの実際の解析上パターンに完全一致する配列というのはあまり見られない。確率でパターンの類似度を議論する必要がある。

隠れマルコフモデルと確率正規文法は同義である

どちらもW -> aWの変換で定義されるミーリー機械である。

• 隠れマルコフモデルと確率正規文法の違い

(歴史的に)異なった表現方法を持つこと。

確率文脈自由文法

隠れマルコフモデル(HMM)と同様の問題・アルゴリズム

確率モデルで最適な配列をアラインメントする方法

• HMM Viterbiアルゴリズム

• 確率文脈自由文法 CYKアルゴリズム

配列の確率を計算する方法

• HMM 前向き・後ろ向きアルゴリズム

• 確率文脈自由文法 inside outside アルゴリズム　（内側アルゴリズム、外側アルゴリズム）

学習データを利用した確率文法のパラメーター最適化

• HMM Baum-Welch

• 確率文脈自由文法 EMアルゴリズム

確率文脈自由文法の標準形

文脈自由文法はの書き換え規則は任意であるが、制限されたモデルを用いて全ての書き換え規則を表現することも可能である。

標準形に直すことでそれぞれに対応したアルゴリズムを適用できるようになる。

• 例

任意の確率文脈自由文法はチョムスキー標準形 (W -> W1W2 or W -> a)に展開できる

S -> aSa(チョムスキー標準形には当てはまらない)はチョムスキー標準形を用いると

S -> W1W2
W1 -> a W2 -> SW1

と表せる。