極限における言語識別

極限における言語識別は、主にコンピュータによる形式言語の帰納的推論のための形式モデルである（機械学習と正規言語の帰納を参照）。これは、E. Mark Goldが同名の技術レポート^{[ 1 ]}とジャーナル記事^{[ 2 ]}で紹介した。

このモデルでは、教師は学習者に対して、ある形式言語の何らかの表現（文字列のシーケンスなど）を提供する。学習は無限のプロセスとみなされる。学習者が表現の要素を読むたびに、その言語の表現（例えば形式文法）が提供されるはずである。

ゴールドは、学習者が言語クラスを極限的に識別できるのは、そのクラス内の任意の言語の提示が与えられた際に、学習者が誤った表現を有限個しか生成せず、その後正しい表現に固執する場合であると定義している。ただし、学習者はその正しさを宣言できる必要はなく、教師は任意の表現に対して、後になってから反例を提示してもよい。

ゴールドはプレゼンテーションを2種類に分類した。

• テキスト（肯定的な情報）：言語を構成するすべての文字列の列挙。
• 完全なプレゼンテーション（肯定情報と否定情報）：考えられるすべての文字列を列挙し、それぞれの文字列に、その文字列が言語に属するかどうかを示すラベルを付ける。

このモデルは、学習可能性の概念を形式的に捉えようとする初期の試みである。ゴールドの論文^{[ 3 ]}では、対照としてより強力なモデルが紹介されている。

• 有限識別（学習者が有限ステップ後に正しさを宣言しなければならない）および
• 固定時間識別（事前に指定されたステップ数後に正しさに到達しなければならない）。

学習可能性に関するより弱い形式モデルとしては、 1984年にレスリー・ヴァリアントによって提唱された、おそらく近似的に正しい学習（PAC）モデルがある。

極限における識別の定義が言及する学習セッションの具体的な例（表に示されているもの）を見てみることは有益である。

1. テキスト提示からアルファベット{ a , b }上の正規言語L を学習する架空のセッション:各ステップで、教師はLに属する文字列を与え、学習者は正規表現としてエンコードされたLの推測に答えます。^{[注 1 ]}ステップ3では、学習者の推測はこれまでに見た文字列と一致しません。ステップ4では、教師は文字列を繰り返し与えます。ステップ6の後、学習者は正規表現 ( ab + ba ) ^*に固執します。これが教師が考えている言語Lの説明である場合、学習者はその言語を学習したと言われます。学習者の役割を担うコンピュータプログラムが存在し、各正規言語を正常に学習できる場合、その言語のクラスは極限で識別可能になります。ゴールドは、そうではないことを示しました。^{[ 4 ]}
2. 特定の学習アルゴリズムでは、L はこれまで見てきたすべての文字列の和集合であると常に推測します 。Lが有限言語であれば、学習者は最終的に正しく推測しますが、いつ正しく推測できるかはわかりません。ステップ3から6の間、推測は変わりませんでしたが、学習者は正しいと確信できませんでした。Goldは、有限言語のクラスは極限で識別可能であることを示しましたが、^{[ 5 ]}このクラスは有限時間でも固定時間でも識別可能ではありません。
3. 完全なプレゼンテーションから学ぶ方法：各ステップで、教師は文字列を提示し、それがLに属するか（緑色）、属さないか（赤色、取り消し線）を指示します。教師は最終的に、考えられるすべての文字列をこのように分類します。
4. 要求による完全なプレゼンテーションからの学習:学習者がクエリ文字列を与え、教師はそれがLに属するかどうか(はい) または属さないかどうか (いいえ) を答えます。次に学習者はLの推測を与え、続いて次のクエリ文字列を与えます。この例では、学習者は各ステップで、例 3 で教師から与えられたのと同じ文字列をクエリしています。一般に、Gold は、要求プレゼンテーション設定で識別可能な各言語クラスは、説明プレゼンテーション設定でも識別可能であることを示しました^{[ 6 ]。}これは、学習者が文字列をクエリする代わりに、最終的に教師から与えられるまで待つ必要があるためです。

より正式には、^{[ 7 ]}

• 言語​${\displaystyle L}$は空でない集合であり、その要素は文と呼ばれます。
• 言語ファミリーとは、言語の集合のことである。
• 言語学習環境${\displaystyle E}$言語の場合${\displaystyle L}$は、${\displaystyle L}$、各文は${\displaystyle L}$少なくとも一度は登場する。
• 言語学習者は関数である${\displaystyle f}$それは、文のリストをある言語に送信する。
  • これは、文章を見た後に、${\displaystyle a_{1},a_{2}...,a_{n}}$その順序で、言語学習者は、文を生成する言語は${\displaystyle f(a_{1},...,a_{n})}$。
  • 学習者は必ずしも正解する必要はないことに注意してください。学習者は、実際には含まれていない言語を推測することも十分に可能です。${\displaystyle a_{1},...,a_{n}}$。
• 言語学習者${\displaystyle f}$言語を学ぶ${\displaystyle L}$環境において${\displaystyle E=(a_{1},a_{2},...)}$学習者が常に推測する場合${\displaystyle L}$環境から十分な事例を見た後で。
• 言語学習者${\displaystyle f}$言語を学ぶ${\displaystyle L}$学習すれば${\displaystyle L}$どんな環境でも${\displaystyle E}$のために${\displaystyle L}$。
• ある言語族が学習可能であるとは、その言語族に含まれるすべての言語を学習できる言語学習者が存在する場合をいう。

注：

• ゴールドの定理の文脈では、文は区別可能であればよい。形式言語学で通常用いられるような有限文字列など、特定の形式である必要はない。
• 学習可能性は個々の言語の概念ではありません。${\displaystyle L}$常に推測するだけの単純な学習者でも習得できる${\displaystyle L}$。
• 学習可能性は、個々の学習者だけを対象とした概念ではありません。言語ファミリーが学習可能であるのは、そのファミリーを学習できる学習者が存在する場合に限ります。学習者がそのファミリー以外の言語をどれだけうまく学習できるかは関係ありません。

否定例が許容される場合、ゴールドの定理は容易に回避される。特に、言語族${\displaystyle \{L_{1},L_{2},...,L_{\infty }\}}$常に推測する学習者によって習得できる${\displaystyle L_{\infty }}$最初の否定的な例を受け取るまで${\displaystyle \neg a_{n}}$、 どこ${\displaystyle a_{n}\in L_{n+1}\setminus L_{n}}$その時、それは常に推測します${\displaystyle L_{n}}$。

ダナ・アングルインは、1980年の論文でテキスト（肯定情報）からの学習可能性の特徴付けを行った。^{[ 8 ]}学習器が有効 である必要がある場合、再帰言語のインデックス付きクラスは、クラス内の各言語のテルテールを均一に列挙する有効な手順が存在する場合に極限で学習可能である（条件1）。 ^{[ 9 ]}理想的な学習器（つまり、任意の関数）が許容される場合、インデックス付き言語クラスは、クラス内の各言語にテルテールがある場合に極限で学習可能であることは容易にわかる（条件2）。^{[ 10 ]}

この表は、どの学習モデルにおいてどの言語クラスが極限で識別可能かを示しています。右側では、各言語クラスはすべての下位クラスのスーパークラスです。各学習モデル（つまり、表現形式）は、その下位のすべてのクラスを極限で識別できます。特に、有限言語のクラスはテキスト表現によって極限で識別可能ですが（上記の例2を参照）、正規言語のクラスは識別できません。

ダナ・アングルインが1980年の別の論文で紹介したパターン言語^{[ 12 ]}も、通常のテキスト表示で識別できます。これらはシングルトンより上位で、原始的な再帰言語クラスより下位に位置しますが、その間のクラスとは比較できないため、表には記載されていません。 ^{[注7 ]}

^{アングルインの論文[ 9 ]}の条件1は、必ずしも容易に検証できるとは限りません。そのため、言語クラスの学習可能性に関するさまざまな十分条件が考案されています。正規言語の学習可能なサブクラスについては、「正規言語の帰納」も参照してください。

収束までに発生する仮説変更回数の上限。

• 有限の厚さは有限の弾性を意味するが、^{[ 15 ] [ 17 ]}その逆は真ではない。
• 有限の弾力性と保守的な学習可能性は、心の変化の限界が存在することを意味する。
• 有限弾性とM有限厚さは、心の変化限界の存在を意味する。しかし、M有限厚さだけでは心の変化限界の存在を意味するわけではなく、心の変化限界の存在もM有限厚さを意味するわけではない。
• 心の変化の限界が存在するということは、学習可能性が存在することを意味するが、その逆は真ではない。
• 計算不可能な学習者を許容する場合、有限の弾力性は思考変化の限界の存在を意味するが、その逆は成り立たない。
• ある言語クラスに累積順序が存在しない場合、そのクラス内に無限の交差特性を持つ言語（必ずしもそのクラスに含まれるとは限らない）が存在し、それはひいてはそのクラスの無限の弾力性を意味する。

• 可算クラスの再帰言語が、非計算可能な学習者に対して思考変化の限界を持つ場合、そのクラスは計算可能な学習者に対しても思考変化の限界を持つのか、それともそのクラスは計算可能な学習者にとって学習不可能なのか？