Loading article…
バージョン空間学習は、機械学習、特に二値分類に対する論理的なアプローチです。バージョン空間学習アルゴリズムは、論理文の集合として見なされる、事前に定義された仮説空間を探索します。形式的には、仮説空間は選言です[ 1 ]
（つまり、仮説 1 からnのうち 1 つ以上が真である）。バージョン空間学習アルゴリズムには例が提示され、それを使用して仮説空間を制限します。各例xに対して、 xと矛盾する仮説が空間から削除されます。[ 2 ]この仮説空間の反復的な改良は候補除去アルゴリズムと呼ばれ、アルゴリズム内部で維持される仮説空間はバージョン空間と呼ばれます。[ 1 ]
仮説に一般性の順序がある設定では、バージョン空間を 2 つの仮説のセットで表すことができます。(1)最も具体的で一貫性のある仮説、および (2)最も一般的で一貫性のある仮説。ここで「一貫性」とは、観測されたデータとの一致を意味します。
最も具体的な仮説（すなわち、具体的な境界SB）は、観測された正の訓練例をカバーし、残りの特徴空間を可能な限り最小限に抑えます。これらの仮説をさらに縮小すると、正の訓練例が除外され、矛盾が生じます。これらの最小限の仮説は、本質的に、真の概念は既に観測された正のデータのみによって定義されるという（悲観的な）主張を構成します。したがって、新しい（これまで見たことのない）データポイントが観測された場合、それは負であると想定されるべきです。（つまり、データが以前に有効と判断されていない場合は、無効と判断されます。）
最も一般的な仮説（すなわち、一般的な境界GB）は、観測された正の訓練例をカバーするだけでなく、負の訓練例を一切含まない残りの特徴空間も可能な限りカバーします。これらをさらに拡大すると、負の訓練例が含まれることになり、矛盾が生じます。これらの最大仮説は、本質的に、真の概念は既に観測された負のデータのみによって定義されるという（楽観的な）主張を構成します。したがって、新しい（これまで見たことのない）データ点が観測された場合、それは正であると想定されるべきです。（つまり、データが以前に除外されていない場合は、含まれているとみなされます。）
したがって、学習中、バージョン空間（それ自体は、すべての整合性のある仮説を含む集合であり、場合によっては無限である）は、その下限と上限（最大限に一般的な仮説集合と最大限に具体的な仮説集合）だけで表現することができ、学習操作はこれらの代表的な集合に対してのみ実行できる。
学習後、アルゴリズムによって学習された仮説をテストすることで、未知の例に対して分類を実行できます。例が複数の仮説と一致する場合は、多数決ルールを適用できます。[ 1 ]
バージョン空間の概念は、1980年代初頭にミッチェルによって導入されました[ 2 ]。これは、解探索の文脈における教師あり学習の基本問題を理解するためのフレームワークです。バージョン空間フレームワークに伴う基本的な「候補除去」探索方法は、一般的な学習アルゴリズムではありませんが、いくつかの実用的な実装が開発されています（例：Sverdlik & Reynolds 1992、Hong & Tsang 1997、Dubois & Quafafou 2002）。
バージョン空間学習の大きな欠点は、ノイズに対処できないことです。矛盾する例のペアがあると、バージョン空間が崩壊し、つまり空になり、分類が不可能になります。[ 1 ]この問題の解決策の1つは、DuboisとQuafafouによって提案されたラフバージョン空間[ 3 ]です。これは、矛盾するデータが存在する場合に、ラフ集合に基づく近似を使用して、確実な仮説と可能性のある仮説を学習します。
