候補除去アルゴリズム - 開発者ドキュメント

1. 序章

このチュートリアルでは、データから概念を学習するための監視対象手法である候補除去アルゴリズム（CEA）について説明します。 CEAの完全な例を段階的に作成し、さまざまな側面からアルゴリズムについて説明します。

2. コンセプトラーニング

概念は、明確に定義されたオブジェクトのコレクションです。たとえば、「鳥」という概念には、鳥であるすべての動物が含まれ、鳥ではない動物は含まれません。

各概念には、すべての概念のメンバーを完全に説明する定義があり、他の概念に属するオブジェクトには適用されません。したがって、概念は、考えられるすべてのオブジェクトのセットに対して定義されたブール関数であり、特定のオブジェクトが概念のメンバーである場合にのみ返されると言えます。それ以外の場合は、を返します。

概念学習では、ポジティブまたはネガティブのいずれかとしてラベル付けされたオブジェクトのデータセットがあります。ポジティブなものはターゲットコンセプトのメンバーであり、ネガティブなものはそうではありません。私たちの目標は、データを使用して適切な概念関数を定式化することであり、候補除去アルゴリズム（CEA）はそれを正確に行うための手法です。

3. 例

友人のアルドがお気に入りのウォータースポーツを楽しんでいる（または楽しんでいない）日の天気データがあるとします：

のすべての例に対応するブール関数が必要です。タプルの空間上で定義された各ブール関数は、「アルドがお気に入りのウォータースポーツを楽しむ日」というターゲットコンセプトの候補仮説です。これは検索する無限のスペースであるため、適切な仮説表現を選択して制限します。

たとえば、用語の接続詞である仮説のみを検討する場合があります。ここで、およびは次のとおりです。

単一の値を取ることができます
または2つの特別な記号の1つ：
- 、これは、の許容値が許容できることを意味します
- 、これは価値がないことを意味します

たとえば、仮説は次のように表すことができます。

ブール関数に対応します。

仮説空間を、選択した表現が表現できるすべての候補仮説のセットと呼びます。

4. 候補除去アルゴリズム

データ内のポジティブオブジェクトを完全にキャプチャする複数の仮説が存在する可能性があります。しかし、私たちはネガティブなものとも一致するものに興味を持っています。ポジティブオブジェクトとネガティブオブジェクトに一致するすべての関数（つまり、それらが正しく分類される）は、ターゲットコンセプトのバージョンスペースを構成します。候補除去アルゴリズム（CEA）は、半順序に依存します。バージョンスペースを見つけるための仮説の。

4.1. 半順序

CEAが使用する順序付けは、「より一般的または同等に一般的」という関係によって引き起こされます。これを。と表記します。すべての例のラベルが正であるとラベル付けされている場合、仮説は仮説よりも一般的であるか、または同等に一般的であると言います。

(1)

この関係には、視覚的な解釈があります。

最も一般的な仮説は、すべての例を肯定的なものとしてラベル付けするものです。同様に、最も具体的なのは、常にを返すものです。付随する関係:(厳密により一般的）、（厳密に一般的ではなく、厳密により具体的）、および同様に定義されます。簡潔にするために、これ以降、「より一般的」と呼びます。

4.2. バージョンスペースを見つける

CEAは、その一般的な境界と特定の境界を識別することによってバージョンスペースを見つけます。また、。には、の最も一般的な仮説が含まれていますが、最も具体的な仮説は。にあります。到達するまでの仮説を特殊化するか、到達するまでの仮説を一般化することで、すべての仮説を取得できます。

一般的および特定の境界がとであるバージョンスペースとして示しましょう。 CEAの開始時に、に最も一般的な仮説のみが含まれています。同様に、に最も具体的な仮説のみが含まれています。 CEAは、ラベル付けされたオブジェクトを1つずつ処理します。必要に応じて、これまでに処理されたすべてのオブジェクトを正しく分類するように、特殊化および一般化します。：

5. 実際のCEAの例

CEAが友人のAldoと一緒に例をどのように処理するかを示しましょう。

5.1. 初期化

最初に、CEAはとに初期化します。と、で囲まれた空間は、仮説空間全体です。

5.2. 最初のポジティブオブジェクトの処理

の唯一の仮説はオブジェクトと一致しているため、CEAは最初の反復で一般的な境界を変更しないため、同じままです。

ただし、の唯一の仮説はオブジェクトと一致していないため、削除します。オブジェクトをカバーする最小の一般化は、まさに仮説です。の仮説ほど一般的ではありません。したがって、更新された特定の境界は次のとおりです。

5.3. 2番目のポジティブオブジェクトの処理

仮説は前向きな例と一致しているため、一般的な境界を変更する必要はありません。だから、それはそれを保持します。

ただし、からの仮説は非常に具体的であるため、境界から削除します。 2番目の正のオブジェクトをカバーするその最小の一般化はです。これは、で持っているよりも一般的ではないので、：

5.4. 最初のネガティブオブジェクトの処理

データの3番目の例（）は負であるため、CEAのメインループでelse-branchを実行します。はオブジェクトと矛盾しないため、変更しないので、を使用します。調べてみると、それは一般的すぎることがわかり、境界から削除します。次に、例と一致する、削除された仮説の6つの最小限の特殊化があることがわかります。

否定的なオブジェクトを正しく分類するように仮説を特殊化するために、仮説内のそれぞれをオブジェクト内の値以外の値に置き換えます。したがって、の代わりに、などの代わりにを使用します。

ただし、、、およびのみが、での仮説よりも一般的です。特定の境界内の少なくとも1つの仮説よりも一般的ではない仮説は、すべての肯定的な例を肯定的なものとして分類しません。そのため、次の仮説よりも最小限の専門分野のみを保持します。

5.5. 3番目のポジティブオブジェクトの処理

仮説はオブジェクトと矛盾しているため、削除します。すべての特殊化によってオブジェクトがポジティブとして分類されないため、特殊化することはできません。同様に、以前に処理したネガティブオブジェクトと一致しないため、一般化することはできません。したがって、唯一のオプションは仮説を削除することです。

オブジェクトはそれが過度に具体的であることを示しているので、CEAは仮説をに一般化し、新しい境界を取得します。

最後に、CEAはバージョンスペースを返します。

6. CEAの収束

すべてのトレーニングオブジェクトを正しく分類する仮説が含まれていて、データにエラーがない場合、CEAが検出するバージョンスペースにはその仮説が含まれます。出力バージョンスペースに1つの仮説のみが含まれている場合、CEAはに収束すると言います。ただし、データにエラーが含まれている場合、またはデータセット全体と一致する仮説が含まれていない場合、CEAは空のバージョンスペースを出力します。

7. CEAの高速化

CEAがトレーニングオブジェクトを処理する順序は、結果のバージョンスペースには影響しませんが、収束速度には影響します。 CEAは、各反復で現在のバージョンスペースのサイズを半分にしたときに最大速度を達成します。これにより、検索スペースが最も削減されます。

良いアプローチは、CEAが次に処理するラベル付きオブジェクトをユーザーに照会できるようにすることです。 CEAはバージョンスペースを検査できるため、処理によってスペースのサイズが半分になるオブジェクトを要求できます。

8. 部分的に学んだ概念

バージョンスペースに複数の仮説が含まれている場合、CEAはターゲットの概念を部分的に学習したと言えます。その場合、新しいオブジェクトを分類する方法を決定する必要があります。

1つの戦略は、すべての仮説がそのラベルに同意する場合にのみ、新しいオブジェクトを分類することです。コンセンサスがない場合、分類しません。 これを行う効率的な方法は、スペースの境界とを考慮することです。のすべての仮説が肯定的であると分類された場合、他のすべての仮説も肯定的であることがわかります。それは、それらがすべて、少なくとも。のそれらと同じくらい一般的だからです。逆に、仮説が否定的であることに同意するかどうかをテストする場合があります。 したがって、全会一致を求める場合、境界を越えて見る必要はありません。

一方、不一致を許容できる場合は、多数決を出力できます。すべての仮説を同じように取り入れると、多数決はの最も可能性の高い分類を表します。さらに、正として分類される仮説のパーセンテージは、正である確率と見なすことができます。否定的な分類についても同じことが言えます。

9. 無制限の仮説スペース

データセットと一致する仮説が含まれていない場合、CEAは空のバージョンスペースを返します。これが発生しないように、任意の概念をのメンバーにする表現を選択できます。オブジェクトが由来するスペースである場合、はのすべての可能なサブセットを表す必要があります。つまり、のべき集合に対応する必要があります。

これを行う1つの方法は、論理和、接続詞、またはより単純な仮説の否定で構成される複雑な仮説を許可することです。そのためには、まず、最も単純な原子仮説を設計します。たとえば、セクション3で示した仮説の定義は、実際の例での原子仮説を説明していると言えます。次に、組み合わせを許可するためにさらに2つのルールを追加します。

原子仮説は仮説です。
およびが仮説である場合、、、およびも仮説です。

9.1. データの過剰適合

しかし、問題は、非常に表現力豊かなスペースが原因でCEAがデータを過剰適合させることです。返されるバージョンスペースの特定の境界は、すべてのポジティブトレーニングオブジェクトを記憶しますが（）、その一般的な境界は、観察されたすべてのネガティブインスタンスを記憶します（）：

9.2. 無制限のスペースでの分類

結果として、そのようなバージョンスペースは、トレーニングオブジェクトについて尋ねられた場合にのみ全会一致の投票を提供します。他のオブジェクトの場合、仮説の半分はそれを正として分類し、残りの半分はそれを負として分類します。のべき集合に対応するため、正として分類されるものには、負としてラベル付けされているを除くすべてのオブジェクトに一致するが存在する必要があることがわかります。しかし、トレーニングされていないオブジェクトについてのみ同意しないので、もにあります。したがって、制限のない仮説スペースは役に立たず、何らかの制限が必要です。

10. 誘導バイアスから演繹的推論へ

この制限は、特定のタイプの仮説に向けて検索にバイアスをかけるため、誘導バイアスと呼ばれます。 バイアスは演繹的推論を可能にする一連の仮定として説明できます。これは、バージョンスペースが正しいラベルを出力することを証明できることを意味します。基本的に、ラベルを定理とトレーニングデータ、分類するオブジェクト、バイアスを定理証明者への入力と見なします。

バージョンスペースで仮説の全会一致の投票が必要な場合、CEAの誘導バイアスは単純に次のようになります。

仮説空間には、ターゲットの概念が含まれています。

これは、ラベルの正式な証明を取得するために採用しなければならない最も弱い仮定です。ただし、バイアスが本当に成り立つ場合にのみ、証明が意味的に正しいことに注意する必要があります。