文法誘導

文法帰納法（または文法推論）^[1]は、機械学習において、一連の観測から形式文法（通常は書き換え規則や生成規則の集合、あるいは有限状態機械や何らかのオートマトンとして）を学習し、観測対象の特性を考慮したモデルを構築するプロセスです。より一般的には、文法推論は、インスタンス空間が文字列、木、グラフなどの離散的な組み合わせオブジェクトで構成される機械学習の分野です。

文法クラス

文法推論は、1980 年代からこの問題に対する効率的なアルゴリズムが存在していたため、さまざまなタイプの有限状態マシンを学習する問題に重点が置かれることが多くなりました (これらのアプローチの詳細については、「正規言語の帰納法」の記事を参照してください)。

今世紀の初め以来、これらのアプローチは、多重文脈自由文法や並列多重文脈自由文法などの文脈自由文法やより豊かな形式主義の推論の問題にまで拡張されてきました。文法推論が研究されている他の文法のクラスには、組合せ範疇文法、^[2] 確率文脈自由文法、^[3]文脈文法、パターン言語などがあります。

学習モデル

最も単純な学習形態は、学習アルゴリズムが単に対象言語から抽出した例のセットを受け取るというものである。その目的は、その例から言語を学習することである（まれに、反例、つまりその言語に属さない例から学習することもある）。しかし、他の学習モデルも研究されてきた。よく研究されている代替モデルの一つは、Angluin が導入した正確なクエリ学習モデルや最小限適切な教師モデルのように、学習者がメンバーシップクエリを尋ねることができるケースである。^[4]

方法論

文法推論にはさまざまな方法があります。代表的なものとしては、Fu (1977) と Fu (1982) があります。Duda、Hart、Stork (2001) もこの問題について短いセクションを割き、多数の参考文献を引用しています。彼らが提示する基本的な試行錯誤の方法について、以下で説明します。特に正規言語のサブクラスを推論するアプローチについては、 「正規言語の帰納法」を参照してください。より最近の教科書は de la Higuera (2010) ^[1]で、正規言語と有限状態オートマトンに関する文法推論の理論を扱っています。D'Ulizia、Ferri、Grifoni ^{[5] は、}自然言語の文法推論方法を調査した調査を提供しています。

確率文法の誘導

確率的文脈自由文法を誘導する方法はいくつかある。^[6]^[7]^{[さらなる説明が必要]}

試行錯誤による文法推論

Duda、Hart、Stork (2001) のセクション 8.7 で提案されている方法は、文法規則 (生成規則) を連続的に推測し、それを肯定的および否定的な観察に対してテストすることを提案しています。規則セットは、各肯定的な例を生成できるように拡張されますが、特定の規則セットが否定的な例も生成する場合は、それを破棄する必要があります。この特定のアプローチは、「仮説テスト」として特徴付けられ、Mitchel のバージョンスペースアルゴリズムと類似しています。Duda、Hart、Stork (2001) のテキストには、プロセスをわかりやすく示す簡単な例が示されていますが、より重要な問題に対してこのようなガイドなしの試行錯誤アプローチが実行可能かどうかは疑問です。

遺伝的アルゴリズムによる文法推論

進化的アルゴリズムを使用した文法帰納法は、何らかの進化的プロセスを通じて対象言語の文法の表現を進化させるプロセスです。形式文法は、進化的演算子を適用できる生成規則のツリー構造として簡単に表現できます。この種のアルゴリズムは、ジョン・コザが開拓した遺伝的プログラミングパラダイムに由来しています。^[^要出典^{]単純な形式言語に関するその他の初期の研究では、遺伝的アルゴリズムのバイナリ文字列表現が使用されていましたが、}EBNF言語で表現された文法の本質的に階層的な構造により、ツリーはより柔軟なアプローチになりました。

Koza はLispプログラムをツリーとして表現しました。彼は、標準的なツリー演算子セットの中に遺伝的演算子の類似点を見つけることができました。たとえば、サブツリーの交換は、遺伝的交差の対応するプロセスに相当し、遺伝的コードの部分文字列が次世代の個体に移植されます。適応度は、 Lisp コードの関数からの出力をスコアリングすることによって測定されます。ツリー構造の Lisp 表現とツリーとしての文法表現の間の類似点により、文法誘導に遺伝的プログラミング技術を適用できるようになりました。

文法誘導の場合、サブツリーの移植は、ある言語のフレーズを解析できるようにする生成規則の交換に相当します。文法の適合度演算子は、ターゲット言語のいくつかの文のグループの解析でどの程度うまく機能したかを示す何らかの尺度に基づいています。文法のツリー表現では、生成規則の終端記号はツリーのリーフノードに相当します。その親ノードは、ルールセット内の非終端記号 (名詞句や動詞句など) に相当します。最終的に、ルートノードは文の非終端記号に相当する可能性があります。

貪欲アルゴリズムによる文法推論

すべての貪欲アルゴリズムと同様に、貪欲文法推論アルゴリズムは、その段階で最善と思われる決定を反復的に行います。通常、下される決定は、新しいルールの作成、既存のルールの削除、適用するルールの選択、または既存のルールのマージなどに関するものです。「段階」と「最善」を定義する方法は複数あるため、貪欲文法推論アルゴリズムも複数存在します。

これらの文脈自由文法生成アルゴリズムは、すべての読み取りシンボルの後に決定を下します。

Lempel-Ziv-Welch アルゴリズムは、生成された文法の開始規則のみを保存する必要があるような決定論的な方法で文脈自由文法を作成します。
Sequiturとその修正。

これらの文脈自由文法生成アルゴリズムは、まず与えられた記号シーケンス全体を読み取り、次に決定を下します。

バイトペアのエンコーディングとその最適化。

分配学習

より最近のアプローチは、分布学習に基づいています。これらのアプローチを使用するアルゴリズムは、文脈自由文法と軽度文脈依存言語の学習に適用されており、これらの文法の大規模なサブクラスに対して正確かつ効率的であることが証明されています。^[8]

学習のパターン言語

アングルインはパターンを「Σ からの定数記号と分離した集合からの変数記号の文字列」と定義しています。このようなパターンの言語は、そのすべての空でない基底インスタンスの集合、つまり、その変数記号を定数記号の空でない文字列に一貫して置き換えた結果生じるすべての文字列です。 ^{[注 1]} パターンは、その言語が入力セットを包含するすべてのパターン言語の中で最小 (セット包含に関して) である場合、有限の入力文字列セットに対して 記述的であると呼ばれます。

アングルインは、与えられた入力文字列セットに対して、1つの変数xのすべての記述パターンを計算する多項式アルゴリズムを提示している。^{[注2]この目的のために、彼女は関連する可能性のあるすべてのパターンを表すオートマトンを構築し、}xが唯一の変数であることに依存する単語の長さに関する洗練された議論を使用することで、状態数を大幅に削減することができる。^[9]

Erlebachらは、Angluinのパターン学習アルゴリズムのより効率的なバージョンと並列化されたバージョンを提示している。^[10]

有村らは、パターンの限定された結合から得られる言語クラスが多項式時間で学習できることを示している。^[11]

パターン理論

ウルフ・グレナンダー^[12]によって定式化されたパターン理論は、世界に関する知識をパターンとして記述する数学的形式主義である。パターン理論は、パターンを認識し分類するためのアルゴリズムや機械を規定することから始めるのではなく、パターンの概念を正確な言語で表現し、言い換えるための語彙を規定するという点で、人工知能に対する他のアプローチと異なる。

新しい代数語彙に加えて、その統計的アプローチは次の目的で斬新でした。

当時は一般的だった人工的な刺激ではなく、現実世界のデータを使用してデータセットの隠れた変数を識別します。
ギブスのようなグラフの頂点を形成する隠れ変数の事前分布と観測変数のモデルを定式化します。
これらのグラフのランダム性と変動性を調べます。
パターンの変形をリストすることによって適用される確率モデルの基本クラスを作成します。
モデルを使用して信号を分析するだけでなく、モデルから合成（サンプル）します。

パターン理論は数学的に広範囲に渡ってカバーしており、代数や統計だけでなく、局所的な位相特性や大域的なエントロピー特性にも及びます。

アプリケーション

文法帰納法の原理は自然言語処理の他の側面にも応用されており、（他の多くの問題の中でも）意味解析、^[2]、自然言語理解、^[13]、用例に基づく翻訳、^[14]、言語習得、^[15]、文法に基づく圧縮、^[16]、異常検出^[17]に適用されています。

圧縮アルゴリズム

アメリカ独立宣言の2 番目の文の直線文法(開始記号 ß を使用) 。青い文字はそれぞれ非終端記号を表し、文のgzip圧縮から取得されました。

文法ベースコードまたは文法ベース圧縮は、圧縮する文字列の文脈自由文法（CFG）を構築するという考えに基づく圧縮アルゴリズムです。例としては、ユニバーサルロスレスデータ圧縮アルゴリズムがあります。^[18]データシーケンスを圧縮するために、文法ベースコードは文脈自由文法に変換されます。入力シーケンスの最小の文法を見つける問題（最小文法問題）はNP困難であることが知られており、^[19]理論的および実用的な観点から多くの文法変換アルゴリズムが提案されています。 $x=x_{1}\cdots x_{n}$ $x$ $G$

一般的に、生成された文法は算術符号化などの統計的エンコーダによってさらに圧縮されます。

G

参照

注記

^ 同じ変数が少なくとも 2 回出現するパターンの言語は、ポンピング補題により正規ではありません。
^ x は複数回出現する可能性があるが、他の変数y は出現しない可能性がある

参考文献

^ ab de la Higuera, Colin (2010). Grammatical Inference: Learning Automata and Grammars (PDF) . Cambridge: Cambridge University Press. 2019-02-14 のオリジナル(PDF)からアーカイブ。2017-08-16に取得。
^ ab Kwiatkowski, Tom、他「意味解析のための CCG 文法誘導における語彙一般化」自然言語処理における経験的手法に関する会議議事録。計算言語学協会、2011 年。
^ クラーク、アレクサンダー。「分布クラスタリングを使用した確率的文脈自由文法の教師なし誘導」。2001 年計算自然言語学習ワークショップ議事録 - 第 7 巻。計算言語学協会、2001 年。
^ Dana Angluin (1987). 「クエリと反例からの正規集合の学習」(PDF) . Information and Control . 75 (2): 87–106. CiteSeerX 10.1.1.187.9414 . doi :10.1016/0890-5401(87)90052-6. S2CID 11873053. 2013-12-02にオリジナル(PDF)からアーカイブ。
^ D'Ulizia, A., Ferri, F., Grifoni, P. (2011)「自然言語学習のための文法推論手法の調査^{[リンク切れ‍ ]}」、人工知能レビュー、第36巻、第1号、pp.1–27。
^ Talton, Jerry、他「ベイジアン文法誘導によるデザインパターンの学習」第 25 回 ACM ユーザーインターフェイスソフトウェアおよびテクノロジシンポジウムの議事録。2012 年。
^ Kim, Yoon, Chris Dyer、Alexander M. Rush。「文法誘導のための複合確率文脈自由文法」arXivプレプリントarXiv:1906.10225 (2019)。
^ Clark and Eyraud (2007) Journal of Machine Learning Research ; Ryo Yoshinaka (2011) Theoretical Computer Science
^ Dana Angluin (1980). 「文字列セットに共通するパターンの検出」. Journal of Computer and System Sciences . 21 : 46–62. doi : 10.1016/0022-0000(80)90041-0 .
^ T. Erlebach; P. Rossmanith; H. Stadtherr; A. Steger ; T. Zeugmann (1997)。「平均的、並列的、およびクエリによる 1 変数パターン言語の効率的な学習」。M. Li、A. Maruoka (編)。第 8 回アルゴリズム学習理論国際ワークショップ — ALT'97 議事録。LNAI。第 1316 巻。Springer。pp. 260–276。
^ 有村弘樹、篠原健、大月節子 (1994)。「パターン言語の和集合に対する最小一般化の発見とポジティブデータからの帰納的推論への応用」(PDF)。Proc . STACS 11。LNCS。第775巻。Springer。pp. 649–660。^{[リンク切れ‍ ]}
^ Grenander、Ulf、Michael I. Miller。パターン理論：表現から推論へ。^{[リンク切れ‍ ]}第1巻。オックスフォード：オックスフォード大学出版局、2007年。
^ ミラー、スコット他「自然言語の隠れた理解モデル」。計算言語学協会第 32 回年次会議議事録。計算言語学協会、1994 年。
^ Brown, Ralf D. 「用例ベース翻訳のための転送ルール誘導」用例ベース機械翻訳に関する MT Summit VIII ワークショップの議事録。2001 年。
^ チャター、ニック、クリストファー・D・マニング。「言語処理と習得の確率モデル」認知科学の動向 10.7 (2006): 335-344。
^ Cherniavsky、Neva、Richard Ladner。「DNA 配列の文法ベースの圧縮」DIMACS ワーキンググループ、Burrows–Wheeler 変換 21 (2004)。
^ Senin, Pavel、他「文法ベースの圧縮による時系列異常検出」Edbt. 2015。
^ Kieffer, JC; Yang, E.-H. (2000)、「文法ベースのコード: ユニバーサルロスレスソースコードの新しいクラス」、IEEE Trans. Inf. Theory、46 (3): 737–754、doi :10.1109/18.841160
^ チャリカー、M.リーマン、E.リュー、D.パニグラヒー、R.プラバラカン、M.サハイ、A. Shelat, A. (2005)、「最小の文法問題」、IEEE Trans。情報理論、51 (7): 2554–2576、土井:10.1109/tit.2005.850116、S2CID 6900082

出典

Duda, Richard O.; Hart, Peter E.; Stork, David G. (2001)、パターン分類（第2版）、ニューヨーク：John Wiley & Sons
フー、キング・サン（1982）、統語的パターン認識と応用、ニュージャージー州エングルウッドクリフス：プレンティス・ホール
Fu, King Sun (1977)、統語的パターン認識、応用、ベルリン：Springer-Verlag
ホーニング、ジェームズ・ジェイ（1969）「文法推論の研究」（博士論文編）、スタンフォード：スタンフォード大学コンピュータサイエンス学部、ProQuest 302483145
Gold, E. Mark (1967)、「Language Identification in the Limit」第10巻、「Information and Control」、pp. 447–474、2016年8月28日にオリジナルからアーカイブ、 2016年9月4日に取得
ゴールド、E.マーク（1967）、限界における言語識別（PDF）、第10巻、情報と制御、pp.447-474

[9] 同じ変数が少なくとも 2 回出現するパターンの言語は、ポンピング補題により正規ではありません。

[10] x は複数回出現する可能性があるが、他の変数y は出現しない可能性がある

[Grammatical_Inference-1] Higuera, Colin (2010). Grammatical Inference: Learning Automata and Grammars (PDF) . Cambridge: Cambridge University Press. 2019-02-14 のオリジナル(PDF)からアーカイブ。2017-08-16に取得。

[Kwiatkowski-2] Kwiatkowski, Tom、他「意味解析のための CCG 文法誘導における語彙一般化」自然言語処理における経験的手法に関する会議議事録。計算言語学協会、2011 年。

[3] クラーク、アレクサンダー。「分布クラスタリングを使用した確率的文脈自由文法の教師なし誘導」。2001 年計算自然言語学習ワークショップ議事録 - 第 7 巻。計算言語学協会、2001 年。

[4] Dana Angluin (1987). 「クエリと反例からの正規集合の学習」(PDF) . Information and Control . 75 (2): 87–106. CiteSeerX 10.1.1.187.9414 . doi :10.1016/0890-5401(87)90052-6. S2CID 11873053. 2013-12-02にオリジナル(PDF)からアーカイブ。

[5] D'Ulizia, A., Ferri, F., Grifoni, P. (2011)「自然言語学習のための文法推論手法の調査^{[リンク切れ‍ ]}」、人工知能レビュー、第36巻、第1号、pp.1–27。

[6] Talton, Jerry、他「ベイジアン文法誘導によるデザインパターンの学習」第 25 回 ACM ユーザーインターフェイスソフトウェアおよびテクノロジシンポジウムの議事録。2012 年。

[7] Kim, Yoon, Chris Dyer、Alexander M. Rush。「文法誘導のための複合確率文脈自由文法」arXivプレプリントarXiv:1906.10225 (2019)。

[8] Clark and Eyraud (2007) Journal of Machine Learning Research ; Ryo Yoshinaka (2011) Theoretical Computer Science

[11] Dana Angluin (1980). 「文字列セットに共通するパターンの検出」. Journal of Computer and System Sciences . 21 : 46–62. doi : 10.1016/0022-0000(80)90041-0 .

[12] T. Erlebach; P. Rossmanith; H. Stadtherr; A. Steger ; T. Zeugmann (1997)。「平均的、並列的、およびクエリによる 1 変数パターン言語の効率的な学習」。M. Li、A. Maruoka (編)。第 8 回アルゴリズム学習理論国際ワークショップ — ALT'97 議事録。LNAI。第 1316 巻。Springer。pp. 260–276。

[13] 有村弘樹、篠原健、大月節子 (1994)。「パターン言語の和集合に対する最小一般化の発見とポジティブデータからの帰納的推論への応用」(PDF)。Proc . STACS 11。LNCS。第775巻。Springer。pp. 649–660。^{[リンク切れ‍ ]}

[14] Grenander、Ulf、Michael I. Miller。パターン理論：表現から推論へ。^{[リンク切れ‍ ]}第1巻。オックスフォード：オックスフォード大学出版局、2007年。

[15] ミラー、スコット他「自然言語の隠れた理解モデル」。計算言語学協会第 32 回年次会議議事録。計算言語学協会、1994 年。

[16] Brown, Ralf D. 「用例ベース翻訳のための転送ルール誘導」用例ベース機械翻訳に関する MT Summit VIII ワークショップの議事録。2001 年。

[17] チャター、ニック、クリストファー・D・マニング。「言語処理と習得の確率モデル」認知科学の動向 10.7 (2006): 335-344。

[18] Cherniavsky、Neva、Richard Ladner。「DNA 配列の文法ベースの圧縮」DIMACS ワーキンググループ、Burrows–Wheeler 変換 21 (2004)。

[19] Senin, Pavel、他「文法ベースの圧縮による時系列異常検出」Edbt. 2015。

[20] Kieffer, JC; Yang, E.-H. (2000)、「文法ベースのコード: ユニバーサルロスレスソースコードの新しいクラス」、IEEE Trans. Inf. Theory、46 (3): 737–754、doi :10.1109/18.841160

[21] チャリカー、M.リーマン、E.リュー、D.パニグラヒー、R.プラバラカン、M.サハイ、A. Shelat, A. (2005)、「最小の文法問題」、IEEE Trans。情報理論、51 (7): 2554–2576、土井:10.1109/tit.2005.850116、S2CID 6900082