# 文脈自由文法 ## 定義 文脈自由文法（Context-Free Grammar, CFG）とは、開始記号からはじめて生成規則（例: `[文] → [名詞句] [動詞句]`）に沿って非終端記号を終端記号（単語）に置換していく形式文法のクラスである。プログラミング言語の構文解析（パーサ）や自然言語処理の初歩的なモデルとして広く使われる。(Source: [[joisino-言語モデルの物理学-2025]]) [[Physics of Language Models]] Part 1（"Learning Hierarchical Language Structures"、arXiv:2305.13673）では、CFG の 2 つの重要な特性——**曖昧性**（同一トークン "saw" が動詞にも名詞にもなる）と**長距離依存**（節を挟んで離れた要素間の一致）——が LLM によって習得できるかを検証するためのコントロールされた実験基盤として用いられた。(Source: [[joisino-言語モデルの物理学-2025]]) ## LLM による CFG の学習 ### 成功した習得 - 高度に曖昧で長距離依存を持つ CFG から生成した長さ 512 のテキストを 960 万個で訓練すると、LLM は 99%+ の確率で正しい文法のテキストを生成する。 - **真の確率分布との KL ダイバージェンスが小さい**——単に「当たり障りのない」選択をするのでなく、文法の全パターンを逃げなしに習得している。 ### 内部表現 - 線形プロービングで、出力トークンの元となる非終端記号（[名詞句]・[動詞句] 等）を正確に推定できる——LLM は曖昧なトークンを出力しながら、頭の中ではその役割を把握している。 - アテンションパターンがマージ可能な区間の右端どうしに有意に強い注意を向ける——**動的計画法的な振る舞い**の証拠。CYK（Cocke-Younger-Kasami）アルゴリズムのような区間マージを内部で行っていると考えられる。 （Source: [[joisino-言語モデルの物理学-2025]]） ### ノイズ耐性 - 完璧なデータのみで訓練するとノイズに弱い。 - 訓練データの一部（例: 15%）にノイズを含めると、テスト時のノイズにも耐性が生まれる。 - ただし正しい文のみを出力させるには低温度（例: τ=0.1）が必要。 （Source: [[joisino-言語モデルの物理学-2025]]） ## 横断的知見 - **CFG 習得は "mechanistic interpretability" の実証的根拠を与える**: LLM が動的計画法的パターンを内部で実行しているという観察は、[[機構的解釈性]] の研究（注意ヘッドの機能分化等）と同方向の知見である。(Source: [[joisino-言語モデルの物理学-2025]]、[[joisino-LLMアテンションと外挿-2025]]) ## 未解決の問い - CFG ではなく文脈依存文法（CSG）や再帰下降型の文法も同様に学習できるか？ - LLM が内部で実行しているアルゴリズムが CYK であることを、より直接的に検証できるか？ - CFG 習得で確認された動的計画法的振る舞いは、[[Chain-of-Thought Prompting]] のような明示的な推論ステップとどのように対応するか？ ## 関連 - ソース: [[joisino-言語モデルの物理学-2025]] - 研究コンセプト: [[Physics of Language Models]] - 研究者: [[Zeyuan Allen-Zhu]] - 関連概念: [[機構的解釈性]] / [[アテンションヘッド]] / [[Chain-of-Thought Prompting]] ## 出典 - [[joisino-言語モデルの物理学-2025]]（Physics of Language Models Part 1）