確率文脈自由文法

提供: miniwiki
移動先:案内、検索

確率文脈自由文法（英: Stochastic context-free grammar, SCFG, Probabilistic context-free grammar, PCFG）は、各生成規則に確率が対応している文脈自由文法である。導出（構文解析）の確率は、その導出で使われた生成規則群の確率の積で表される。従って、導出結果は他の文法よりも確率文法により近い。SCFGの文脈自由文法への拡張は、隠れマルコフモデルの正規文法への拡張と似ている。SCFGは主に自然言語処理とバイオインフォマティクスにおけるRNA分子の研究で利用されている。SCFGは加重文脈自由文法の特殊な形態と言うことができる。

技法

CYK法の派生手法で、与えられたSCFGのビタビ構文解析を見つけることができる。ビタビ構文解析は、SCFGによる適用規則列の最も尤もらしい導出（構文解析）である。

Inside-Outside アルゴリズムがあり、与えられた文字列を何らかのSCFGで解析したときの全解釈について確率を求めるのに使われる。これはSCFGで適用規則列を生成するときの確率と等価であり、直観的には、その規則列が文法に照らしてどれだけ妥当かを示す尺度となる。

Inside-Outside アルゴリズムは、無作為な文字列生成において、ある文字列が現れる確率を計算するのにも使われる。これは、SCFGがモデルとすべき訓練例に基づき、最尤確率を学習させるために期待値最大化法の一部として使われる。このアルゴリズムは隠れマルコフモデルで使われるアルゴリズムに似ている。

応用

自然言語処理

文脈自由文法は本来、自然言語（人間が話す言語）のモデルとして考案された。これを研究者らが拡張したのが SCFG である。

以下に示すのは、2つの規則からなる SCFG 文法である。各規則の前にある数値は確率であり、それぞれがどのような頻度で出現するかを表している。

0.7 VP --> V NP
0.3 VP --> V NP NP

この文法によれば、VP から生成される NP の個数の期待値は 0.7 x 1 + 0.3 x 2 = 1.3 となる。

例えば、音声認識システムでSCFGを使い、確率推定能力を高め、性能を向上させるといった応用が考えられる。

最近では、SCFG は接近度階層を説明するにあたって、重要な役割を果たしている。接近度階層とは、文章構造によって理解しやすさが異なる原因を説明する概念である。

尤もらしい構造に関する確率的記述ができるなら、その構造について情報理論的尺度（エントロピー）が計算できることになる。情報理論に基づく文法（構文）認識装置があるとしたら、SCFG に類する技法を使うであろうことは想像に難くない[1]。

RNA

文脈自由文法は、RNAの二次構造のモデリングにも適用される[2][3]。一本鎖RNA分子におけるヌクレオチドの二次構造は、相補的であり、対を形成する。この基本対がRNA分子の機能において生物学的に重要である。基本対の多くは文脈自由文法で表現できる（例外として pseudoknot がある）。

例えば、次のような文法があるとする。ここで、a,c,g,u はヌクレオチドを表し、S は開始記号（唯一の非終端記号）である。

S → aSu | cSg | gSc | uSa

この単純な文脈自由文法が、2つの完全に相補的な領域から成るRNA分子を表している。ここでは、正規の相補的な対しか許されない（すなわち、A-U と C-G）。

もっと複雑な文脈自由文法に確率を付与すると、特定のRNAパターンをある程度モデル化することができる。Rfamデータベースでは、ノンコーディングRNAのパターンのモデル化にSCFGを使っており、他にありそうなゲノムシーケンスがないか探すのに使っている。比較ゲノム解析でもRNA遺伝子を探すのにSCFGが使われてきた。この場合、RNA遺伝子と思われる部分の相同体が遺伝的に近い2つの個体にあるとき、SCFGを使ってそれらの二次構造が保持されるかを確認する。もしそうなら、そのシーケンスはRNA遺伝子と考えられそのRNA分子の二次構造の推定にもSCFGなどの手法が使われる（Stemloc など）。

生成文法との比較

ゴールドの定理（1967年）[4]によれば、自然言語の文法を決定的な規則だけで説明すると、正しい例だけでは学習できないとされた。これは1980年に発表された「刺激の貧困」という主張の一部ともなり[5]、ノーム・チョムスキーは1950年代ごろからそのような主張を行っていた。この考え方は心理学的生得主義につながり、自然言語の文法は生まれたときから植えつけられているという考え方につながっていく。この考え方は、主として統率・束縛理論 (GB) やミニマリスト・プログラム (MP) の理論に制限される。

文法とは、言語の構文の説明である。理論的モデルは、精神言語や生成文法に集中している。それとは対照的に、言語の用法を説明する文法を構築すべく構文を研究する立場もある[6]。

形式文法全般に関わる問題として、1つの文章構造に複数の生成規則が対応可能である点が挙げられる。多くの構文を説明しようとすると、衝突が発生しやすくなるため、文法学者は規則の優先順位付けに多大な労力を費やすようになり、最終的にそれが無駄であったことが判明する。別の問題として、言語として意味を成さない文章まで生成できてしまうという問題がある。確率文法は、これらの問題への対処として生成規則の使用頻度でそれらを順位付けし、結果として最もそれらしい解釈ができるが、定義上、その解釈も追加データによって無効化される。構文の使用パターンは時と共に変化するので、確率的生成規則も再学習が必要であり、それによって文法が更新される。

伝統的な形式文法の全非終端記号に実例データから推定した確率値を付与することで確率文法を構築することもできる。一般に、一から精密に構築した文法よりも、データから確率を調整した確率文法の方がすぐれている（もっとも、規則に基づいた文法でもSCFGの正確さに近いものが出現している）。

最近では、確率文法はある程度の認識的尤もらしさを得たように見える。異なる文法構造にアクセスするのが難しいことはよく知られている（例えば、関係節の接近度階層）。ミニマリスト文法の確率バージョンは、わかりやすさと生成の困難さについて言語心理学的データとよく相関するような情報理論的エントロピーを計算するのに使われている[7]。

脚注

  1. ↑ John Hale (2006年). “Uncertainty About the Rest of the Sentence”. Cognitive Science 30: 643-672. doi:doi:10.1207/s15516709cog0000_64. 
  2. ↑ Durbin, Eddy, Krogh, Mitchison, Biological sequence analysis, Cambridge University Press, 1998. このバイオインフォマティクスの本では、RNAモデリングへのSCFGの適用方法だけでなく、1998年までのそれに関する歴史も解説している。
  3. ↑ Sean R. Eddy and Richard Durbin (1994), "RNA sequence analysis using covariance models", Nucleic Acids Research, 22 (11): 2079-88. [1]
  4. ↑ Gold, E. (1967). Language identification in the limit. Information and Control 10, 447-474.
  5. ↑ Chomsky, N. (1980). Rules and representations Oxford: Basil Blackwell.
  6. ↑ George Lakoff and Mark Johnson (1999年). Philosophy in the Flesh: The embodied mind and its challenge to Western thought. Part IV.. New York: Basic Books.. 
  7. ↑ John Hale (2006年). “Uncertainty About the Rest of the Sentence”. Cognitive Science 30: 643-672. doi:doi:10.1207/s15516709cog0000_64. 

参考文献

  • Elena Rivas and Sean R. Eddy (2001), "Noncoding RNA gene detection using comparative sequence analysis", BMC Bioinformatics, 2 (1): 8. [2]

外部リンク



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=確率文脈自由文法&oldid=112071」から取得