Theory of Active Learning SVM (1)
（ある程度SVMのことがわかってる方向け）
Active Learning SVM（能動学習SVM）の理論。
SVMの能動学習とは、現在の学習状況から、次に学習するべき事例を選ぶというもの。
- 能動学習の必要性
SVMはいわゆる教師付き学習(Supervised Learning)の一種で、データの特徴量からクラスを予測する判別器を生成するものです。そのため学習データとして特徴量とクラスをもった事例を与える必要があります。クラスは人間が与えなければいけないので、学習データが大規模だったりするとこれを人手で行うのが大変になります。そこでそのコストを削減するため、能動的に次にクラスを与える事例を決めて学習を進めていく手法が重要になってきます。
TongとKollerは、バージョン空間という概念を用いてSVMのための能動学習手法を理論立てました。
S. Tong & D. Koller, "Support Vector Machine Active Learning with Applications to Text Classification",
Journal of Machine Learning Research, Volume 2,pp 45-66, 2001
Tongらが考案した手法は、「候補となる事例のうち、判別面から最も近いものを取得する」というもので、SIMPLE法、DISTANCE法、MARGIN法などの呼び名で知られています（Tong自身はSimpleと呼んでいます）。この手法は実装も簡単で、現在最も一般的な手法として知られています。
直観的には、「判別面に最も近い事例」＝「クラスが最も不確定な事例」であるといえます。
なので、確かに判別面は素早く収束しそうな気がしますね。
それでは理論の話。
まず判別面Hを次のように定義し、
バージョン空間（判別面の集合）Vを考えます。
このへんは深く考えなくて大丈夫です。
そして、通常の特徴空間をハフ変換（y=ax+b → b=-xa+yとして、定数部を軸にとります）して得られるパラメータ空間を考えます。この空間では、点が線（一般には超平面）、線（超平面）が点になります。
するとこんな感じに
注意：てきとーに書いたので、多分完全にこの図の通りにはなりません。
バージョン空間は判別面の集合ですから、事例に囲まれた多角形がこれに該当しますね。ちなみにマージン最大化は、ここではこの多角形に内接する円（超球）の半径を最大化することに当たります。判別面はその円の中心点になります。この点はバージョン空間の重心の近似として扱うことができます。*1
- なぜバージョン空間なんてものを考える必要があるのか。
能動学習は、少ないデータでもたくさんのデータを学習させたように高精度の判別器を生成することが目的です。たくさんのデータを学習させると、すべてのデータをちょうどよく判別する判別器は少なくなります。
すなわち、バージョン空間は狭くなっていきます。
したがって、「少ないデータで高精度の判別器を生成する」という問題は、「バージョン空間をより狭くするようなデータ
を学習させる」という問題に置き換えることができます。
- バージョン空間を狭くするにはどうすればいいか
先ほどSVMの判別面はバージョン空間の重心の近似として扱えると述べましたが、次に学習させるデータがこの重心の上を通るとなるとバージョン空間はちょうど半分になります。この重心に近いデータ、すなわち判別面に近いデータを取得し、新たに学習させることでバージョン空間を狭くすることができそうですね。
以上が、TongらによるSVMのための能動学習手法の理論です。
しかし、実際的には穴のある理論でもあります。何度も述べた通り、バージョン空間は判別面の集合です。しかしこの判別面は、「すべての事例を正しく分類できるような面」として定義されています。つまり、完全分離可能でないような場合、そもそもバージョン空間は存在しません。
多くの実データの場合、完全分離可能な場合はむしろ少ないですね。
