文法帰納法

確率的文脈自由文法の誘導にはいくつかの方法がある。^{[ 6 ] [ 7 ]}

Duda、Hart 、 Stork (2001)の第 8.7 節で提案されている方法は、文法規則（生成規則）を順次推測し、それらを肯定例と否定例に対してテストするというものです。規則セットは、各肯定例を生成できるように拡張されますが、与えられた規則セットが否定例も生成する場合は、その規則セットは破棄されなければなりません。この特定のアプローチは「仮説検定」と特徴づけられ、Mitchel のバージョン空間アルゴリズムといくらか類似しています。Duda 、Hart 、 Stork (2001)の本文には、このプロセスをうまく説明する簡単な例が示されていますが、このようなガイドなしの試行錯誤アプローチが、より深刻な問題に適用できるかどうかは疑問です。

進化アルゴリズムを用いた文法帰納法とは、何らかの進化プロセスを通して対象言語の文法表現を進化させるプロセスである。形式文法は、進化演算子を適用できる生成規則のツリー構造として容易に表現できる。このようなアルゴリズムは、ジョン・コザが先駆的に開発した遺伝的プログラミングのパラダイムに由来する。単純な形式言語に関する初期の研究では、遺伝的アルゴリズムのバイナリ文字列表現が用いられていたが、 EBNF言語で記述された文法の本質的に階層的な構造により、ツリー構造の方がより柔軟なアプローチとなった。

KozaはLispプログラムを木構造として表現した。彼は、標準的な木構造演算子の中に遺伝的演算子の類似点を見出すことができた。例えば、部分木の交換は、遺伝的交叉の対応するプロセス、すなわち遺伝コードの部分文字列を次世代の個体に移植するプロセスに相当する。適応度は、 Lispコードの関数の出力をスコアリングすることで測定される。木構造のLisp表現と、文法を木構造として表現することの間に同様の類似点があったため、遺伝的プログラミング技術を文法誘導に適用することが可能になった。

文法誘導の場合、サブツリーの移植は、ある言語の句を解析できるようにする生成規則の交換に対応します。文法の適合度演算子は、対象言語の文群を解析する際の文法の性能を測る何らかの尺度に基づいています。文法の木構造表現では、生成規則の終端記号は木の葉ノードに対応します。その親ノードは、規則セット内の非終端記号（例えば、名詞句や動詞句）に対応します。最終的に、ルートノードは文の非終端記号に対応する可能性があります。

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

これらの文脈自由文法生成アルゴリズムは、読み取った記号ごとに判断を下します。

• レンペル・ジブ・ウェルチアルゴリズムは、決定論的な方法で文脈自由文法を生成するため、生成された文法の開始規則のみを保存すればよい。
• セクィターとその派生形。

これらの文脈自由文法生成アルゴリズムは、まず与えられた記号列全体を読み込み、それから判断を開始します。

• バイトペア符号化とその最適化。

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

Angluin はパターンを「Σ からの定数記号と互いに素な集合からの変数記号の文字列」と定義しています。このようなパターンの言語は、その空でないすべての基本インスタンスの集合、つまり、その変数記号を定数記号の空でない文字列で一貫して置き換えることによって得られるすべての文字列の集合です。 ^{[注 1 ]} パターンは、入力文字列の有限集合に対して記述的であるとは、その言語が入力集合を包含するすべてのパターン言語の中で最小である場合（集合包含に関して）を指します。

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

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

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

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

新しい代数用語に加えて、その統計的手法は、以下の目的において斬新であった。

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

パターン理論は数学的な範囲が広く、代数学や統計学だけでなく、局所的な位相幾何学的性質や全体的なエントロピー的性質にも及ぶ。