木接合文法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

木接合文法: Tree-Adjoining GrammarTAG)とは、アラビンド・ジョシ英語版 による、形式文法の一種である。文脈自由文法にいくぶん似ているが、の書換をベースとすることが特徴で、木のノード群を書き換える規則群から成る(および木構造参照)。

概要[編集]

TAGにおける規則は、foot node と呼ばれる特殊な葉ノードを持つ木であり、foot node には単語が付属している。TAGにおける木は2種類に分類される。initial(初期)木('' とも)と auxiliary(補助)木('')である。初期木は基本的な結合価的関係を表し、補助木は再帰を許容する[1]。補助木には根ノードがあり、foot node は初期木と同じシンボルがラベルとして付けられている。導出は、初期木に対して行われ、「置換(substitution)」か「付加(adjunction)」を行っていく。置換とは、先端ノードを、根ノードが同じシンボルのラベルになっている別の木と置換する操作である。付加とは、補助木を別の木の途中に挿入する操作である[2]。補助木の根ノードと foot node のラベルは、挿入箇所のノードのラベルと一致していなければならない。

複雑性と応用[編集]

言語とオートマトンの理論[編集]

木接合文法は、文脈自由文法よりも強力だが文脈依存文法よりも弱い。

具体例として、任意の文字列を二回繰り返すような言語を記述することができる。より一般には、 のような言語を、一部の例外を除きほとんど記述することができる。このような処理はembedded pushdown automatonで表現できる。一方で、文字列を3回繰り返す言語や、4つ以上の同じ長さの文字の列からなる言語は木接合文法では生成できない。

よって「弱文脈依存文法」的である。

また、チョムスキー階層には当てはまらず、むしろ興味深い形でそれと交差している[3]

自然言語[編集]

前節で述べたような性質から、計算言語学自然言語処理でよく使われる。また、構文解析が一般に効率的に行えるなら、自然言語のモデルとして十分に意味があるという主張もある[4]

歴史[編集]

TAGの研究は、ゼリグ・ハリスの文字列文法である adjunction grammars (AG) [5]を Joshi らが研究したことから端を発している。AG は、自然言語学的な観点からは、内心構造(endocentric construction)を自然かつ効率的に扱えるが、外心構造(exocentric construction)はうまく扱えない。句構造文法はその逆である。1969年、Joshi は2種類の規則群を混合することで、少数の非常に単純な書き換え規則で、付加規則のための文字列の語彙を生成する、この相補性を同時に扱えるTAGを生み出した。

脚注[編集]

  1. ^ Jurafsky, Daniel; James H. Martin (2000年). Speech and Language Processing. Upper Saddle River, NJ: Prentice Hall. pp. 354. 
  2. ^ Joshi, Aravind; Owen Rambow (2003年). “A Formalism for Dependency Grammar Based on Tree Adjoining Grammar”. Proceedings of the Conference on Meaning-Text Theory. http://www1.cs.columbia.edu/~rambow/papers/joshi-rambow-2003.pdf 
  3. ^ Joshi, Aravind (1969年). Properties of Formal Grammars with Mixed Types of Rules and Their Linguistic Relevance. Proceedings Third International Symposium on Computational Linguistics, Stockholm, Sweden. 
  4. ^ Joshi, Aravind (1985年). “How much context-sensitivity is necessary for characterizing structural descriptions”. In D. Dowty, L. Karttunen, and A. Zwicky, (eds.). Natural Language Processing: Theoretical, Computational, and Psychological Perspectives. New York, NY: Cambridge University Press. pp. 206–250. 
  5. ^ Joshi, Aravind; S. R. Kosaraju, H. Yamada (1969年). String Adjunct Grammars. Proceedings Tenth Annual Symposium on Automata Theory, Waterloo, Canada. 

外部リンク[編集]