Loading article…
木結合文法( TAG ) は、Aravind Joshiによって定義された文法形式です。木結合文法は文脈自由文法に似ていますが、書き換えの基本単位は記号ではなく木です。文脈自由文法では記号を他の記号の文字列として書き換える規則がありますが、木結合文法では木のノードを他の木として書き換える規則があります (「木 (グラフ理論)」および「木 (データ構造) 」を参照)。
歴史
TAG は、ジョシとその学生による付加文法 (AG) ファミリー ( [1]ゼリッグ・ハリス の「文字列文法」)の研究に端を発しています。[2] AG は言語の外心的特性を自然かつ効果的に処理しますが、内心的構造をうまく特徴づけることができません。その逆は、書き換え文法、または句構造文法(PSG) に当てはまります。 1969 年、ジョシは 2 種類の規則を混合することでこの相補性を活用する文法ファミリーを導入しました。ごく単純な書き換え規則をいくつか使用すれば、付加規則の文字列の語彙を生成するのに十分です。このファミリーはチョムスキー-シュッツェンベルガー階層とは異なりますが、興味深く言語的に重要な方法で交差しています。[3]中心文字列と付加文字列は、依存性文法によって生成することもでき、書き換えシステムの制限を完全に回避できます。[4] [5]
説明
TAG のルールは、単語に固定されたフットノードと呼ばれる特別なリーフノードを持つツリーです。TAG には、初期ツリー (多くの場合 ' ' と表されます) と補助ツリー (' ') の 2 種類の基本ツリーがあります。初期ツリーは基本的な価数関係を表し、補助ツリーは再帰を可能にします。[6] 補助ツリーでは、ルート (トップ) ノードとフットノードに同じシンボルが付けられます。導出は初期ツリーから始まり、置換または付加によって結合します。置換では、境界ノードをトップノードが同じラベルを持つ別のツリーに置き換えます。補助ツリーのルート/フットラベルは、それが隣接するノードのラベルと一致する必要があります。したがって、付加は補助ツリーを別のツリーの中央に挿入する効果を持つことができます。[4]
TAG の他のバリアントでは、複数コンポーネントのツリー、複数のフットノードを持つツリー、およびその他の拡張機能が許可されます。
複雑さと応用
木結合文法は、文脈自由文法よりも強力（弱い生成能力の観点から）ですが、線形文脈自由書き換えシステム[7]、 [注1]、または文脈依存文法ほど強力ではありません。
TAG は、正方形の言語 (任意の文字列が繰り返される) と言語を記述できます。このタイプの処理は、埋め込みプッシュダウンオートマトンで表すことができます。キューブ (つまり、3 重の文字列) を持つ言語、または長さが同じ 4 つ以上の異なる文字列を持つ言語は、木結合文法では生成できません。
これらの理由から、木結合文法は軽度文脈依存であるとよく説明される。これらの文法クラスは、一般的なケースでは効率的に解析可能でありながら、自然言語をモデル化するのに十分強力であると推測される。[8]
同値性
Vijay-ShankerとWeir(1994) [9]は、線形索引文法、組合せ範疇文法、木結合文法、ヘッド文法は、すべて同じ文字列言語を定義するという点で、弱等価な形式主義であることを示しています。
語彙化された
語彙化木結合文法（LTAG）はTAGの変形であり、各基本木（母音または助動詞）が語彙項目に関連付けられています。英語の語彙化文法は、ペンシルバニア大学認知科学研究所のXTAG研究グループによって開発されました。[5]
参照
注記
- ^ 各木結合文法に対して、同じ言語を生成する線形インデックス文法が見つかる（下記参照）ため、後者に対しては、弱等価な（適切な）インデックス文法が見つかる（インデックス文法#計算能力参照）。
参考文献
- ^ Joshi, Aravind; SR Kosaraju; H. Yamada (1969)。「文字列付加文法」(文書)。第 10 回オートマトン理論シンポジウムの議事録、ウォータールー、カナダ。 ジョシ、アラヴィンド K.; コサラジュ、S. ラオ; ヤマダ、HM (1972)、「文字列付加文法: I. 局所的および分散的付加」、情報制御、21 (2): 93–116、doi : 10.1016/S0019-9958(72)90051-4 ジョシ、アラヴィンド K.; コサラジュ、S. ラオ; ヤマダ、HM (1972)、「文字列付加文法: II. 等式表現、ヌル記号、および言語的関連性」、情報制御、21 (3): 235–260、doi : 10.1016/S0019-9958(72)80005-6
- ^ Harris, Zellig S. (1962)。文構造の文字列分析。形式言語学論文集。第1巻。ハーグ：Mouton & Co.
- ^ Joshi, Aravind (1969)。「混合型の規則を持つ形式文法の特性と言語的関連性」(文書)。スウェーデン、ストックホルムで開催された第 3 回国際計算言語学シンポジウムの議事録。
- ^ ab Joshi, Aravind; Owen Rambow (2003). 「木結合文法に基づく依存文法の形式主義」(PDF)。意味テキスト理論に関する会議の議事録。
- ^ ab 「英語のための語彙化された木構造の隣接文法」。
- ^ Jurafsky, Daniel ; James H. Martin (2000).音声言語処理. Upper Saddle River, NJ: Prentice Hall. p. 354.
- ^ Kallmeyer, Laura (2010). Parsing Beyond Context-Free Grammars. Springer. ここ: p.215-216
- ^ Joshi, Aravind (1985)。「構造的記述を特徴付けるにはどの程度の文脈依存性が必要か」。D. Dowty、L. Karttunen、A. Zwicky (編)。自然言語処理: 理論的、計算的、心理学的観点。ニューヨーク、NY: Cambridge University Press。pp. 206–250。ISBN 9780521262033。
- ^ Vijay-Shanker, K. および Weir, David J. 1994.文脈自由文法の4つの拡張の同値性。数学システム理論27(6):511–546。
外部リンク
- 自然言語処理に TAG を使用する XTAG プロジェクト。
- TAGのチュートリアル
- SemConst ドキュメント TAG フレームワーク内で問題となる構文とセマンティック インターフェースに関する簡単な調査。
- TuLiPaプロジェクト テュービンゲン言語解析アーキテクチャ（TuLiPA）は、主にツリータプルを持つマルチコンポーネントツリー結合文法向けに設計された、マルチ形式主義の構文（および意味）解析環境です。
- Metagrammar Toolkit は、MetaGrammar を編集して TAG にコンパイルするためのツールをいくつか提供します。また、広範囲に及ぶフランス語の Metagrammar も含まれています。
- LLP2 使いやすいグラフィカル環境を提供する語彙化ツリー隣接文法パーサー (フランス語のページ)