文法帰納（Grammar induction）は、観測された文字列や文の集合から形式文法（文脈自由文法や確率文脈自由文法など）を自動的に推論するタスクである。その目標は、言語の背後にある統語的規則性を捉え、システムが新しい有効な文を生成したり、未見の文を解析したりできるようにすることである。この問題は、Machine learning、Artificial intelligence、および計算言語学の交差点に位置し、コンピュータ科学の初期から研究されてきた。明示的なラベルを伴う教師あり学習とは異なり、文法帰納はしばしば注釈のないテキストを扱うため、教師なし学習または弱教師あり学習の一種となる。
この分野は、理論計算機科学と認知科学の両方に深いルーツを持つ。古典的なゴールドの定理（1967年）は、特定の文法クラスが正例のみから極限において学習できないことを示し、追加の制約や確率的枠組みの使用を動機付けた。その後の研究、例えばインサイド・アウトサイドアルゴリズム（確率文脈自由文法に対するフォワード・バックワードアルゴリズムの一般化）の開発は、パラメータ推定の実用的な方法を提供した。現代のアプローチは、特にTransformer (architecture)ベースのモデルなど、Neural networkアーキテクチャを活用して、大規模コーパスから文法のような構造を誘導することが多い。
歴史的基礎
文法帰納の形式的な研究は、1950年代から1960年代にかけて、ノーム・チョムスキーらによる形式言語理論の研究から始まった。チョムスキーの階層は、正規文法から帰納的可算文法まで、文法をその生成力によって分類した。1967年、E・マーク・ゴールドは、文脈自由文法が正例のみから学習できないことを証明し、この結果がその後の研究を形作った。これにより、正例と負例の両方からの学習や、データに対して最も可能性の高い文法を見つけることを目的とする確率文法の使用が探求されるようになった。
1980年代から1990年代にかけて、CYKパーサーやインサイド・アウトサイドアルゴリズムなどのアルゴリズムの導入により、計算手法が進歩した。これらにより、確率文脈自由文法における効率的な解析とパラメータ推定が可能になった。ダナ・アングルインなどの研究者は、学習者が文字列の所属についてオラクルに問い合わせることができる能動学習フレームワークを開発し、ゴールドの限界の一部を回避した。この分野はまた、認知科学、特に人間の幼児が限られた入力から言語を獲得する方法という問題からも影響を受けており、このテーマはBrendan LakeやJoshua Tenenbaumなどの研究者によって人間らしい学習の文脈で探求されている。
確率的およびベイズ的アプローチ
文法帰納における大きな転換は、確率的およびベイズ的方法の採用とともに訪れた。単一の文法を探索する代わりに、これらのアプローチは可能な文法の分布を維持し、より多くのデータが観測されるにつれてそれを更新する。1979年にジェームズ・ベイカーによって導入されたインサイド・アウトサイドアルゴリズムは、確率文脈自由文法のパラメータを推定するための期待値最大化（EM）手順を提供する重要な例である。このアルゴリズムは、隠れマルコフモデルで使用されるフォワード・バックワードアルゴリズムに類似している。
マーク・ジョンソンらによって開発されたベイズ的アプローチは、文法構造上の事前分布を組み込み、よりコンパクトで一般化可能な文法の誘導を可能にする。これらの方法は、しばしばマルコフ連鎖モンテカルロ（MCMC）サンプリングを使用して文法の空間を探索する。注目すべき例として、自然言語のベイズ文法帰納に関する研究があり、これは小規模なコーパスに適用され、人間の文法に類似した統語カテゴリを回復することが示されている。これらの技術はまた、言語獲得に関する仮説を検証するための認知モデリングにも使用されている。
ニューラルおよび深層学習法
Deep learningの台頭に伴い、文法帰納はNeural networkアーキテクチャを用いて再検討されている。初期のニューラルアプローチでは、リカレントニューラルネットワーク（RNN）や長短期記憶（LSTM）ネットワークを使用して系列データをモデル化したが、これらは明示的に文法を誘導するものではなかった。最近では、Large language modelで使用されるようなTransformer (architecture)ベースのモデルが、暗黙的に統語構造を捉えることが示されている。例えば、プロービング研究は、これらのモデルが明示的な文法監督なしで訓練されているにもかかわらず、その内部表現に階層的および文法的情報をエンコードしていることを実証している。
明示的なニューラル文法帰納モデルも開発されている。2019年にYikang Shenらによって導入されたON-LSTM（Ordered Neurons LSTM）は、潜在的なツリー構造を誘導するための特別なゲーティングメカニズムを使用する。Andrew Drozdovらによって提案されたDIORA（Dynamically-Inferred Ontology for Recursive Annotation）モデルは、インサイド・アウトサイドアルゴリズムの微分可能なバージョンを使用して構成素ツリーを誘導する。これらのモデルは生のテキストで訓練され、人間が注釈を付けたツリーバンクとかなりよく一致する解析ツリーを生成でき、教師なし解析ベンチマークで最先端の結果を達成している。
応用と課題
文法帰納には、いくつかの分野で実用的な応用がある。Natural language processingでは、誘導された文法は教師なし解析に使用でき、注釈付きツリーバンクが利用できない低リソース言語にとって価値がある。Machine learningでは、文法帰納は構造的帰納バイアスを提供することでモデルのサンプル効率を向上させることができる。認知科学では、言語獲得を理解するための計算フレームワークを提供する。さらに、文法帰納は、バイオインフォマティクス（例：RNA二次構造予測）やプログラム合成など、他の領域にも適用されており、そこでは基礎となる構造が文法的である。
進歩にもかかわらず、文法帰納は依然として困難な問題である。可能な文法の探索空間は広大であり、目的関数はしばしば非凸であるため、局所最適に陥る。評価も難しく、与えられた言語に対して単一の正しい文法は存在せず、異なる文法が同様に有効であり得る。この分野は進化を続けており、最近の研究では、文法帰納とLarge language modelの統合を探求して、その解釈可能性と構成的一般化を向上させている。MIT CSAILやStanford AI Labなどの機関の研究者は、これらの方向性を積極的に調査しており、言語に対する記号的アプローチとコネクショニスト的アプローチの間のギャップを埋めることを目指している。