分類問題
今回は Classifier (分類器)についての歴史です。 前回は、Model, Optimization, そして、Featureの話でした。 この三つを知らないと話がわからないので注意。
ふたたび、x を見て、y を予測したいとします。 例えば、x はパスポートの写真。 y は性別とします。 まず、x を数字の行列で表すとします。 高校のときに習ったベクトルです。 デジタルイメージの写真で、360*360の大きさなら、パスポートの写真は、360*360次元の空間の一点である、という感じに x のデータを数字に落とすことができます。
この x が生きる世界が Feature Space. 次元ひとつが Featureに対応します。 まあ、こんな感じで、ベクトル空間の一点としてサンプルを表すことができます。
さて、男と女を分類するにはどうするか。 歴史上のブレイクスルーが、いくつかありました。
まず、Perceptronが発明されます (Rosenblatt 1957)
これは、ニューラルネットワークの先駆けです。 分類されていない x が見付かったら、Featureひとつごとに、重みを掛け算して、合計の数字が、ある一定より大きければ、女、小さければ、男、みたいなモデルです。 この重みが学習すべき対象のパラメータ Θ です。 Featureごとの重みさえわかれば予測ができるし、重さを学習してやればそれで終わり。 簡単で非常に良いシステムです。 しかも、On-line Learningです。 ここから先に出てくるのは Batchなので、いまだに、On-line の学習方法としては良く使われています。
パスポートの例だと次元が高いので、単純に二次元のデータだと仮定して説明します。 例えば x が成人日本人の身長と体重、y が性別だとします。 すると、二次元ベクトル空間の一点が一人の人を表します。
perceptron が、具体的に何をやっているかというと、この、二次元ベクトル空間に、一本の直線（斜めでも縦でも横でも良い）を引いて、その線の上あるいは下にくるのは、女である、とか、男である、とか言っているわけです。 簡単です。 この線を適切に選ぶことが大事だというわけです。
日本人の男女の平均身長は5センチぐらい違うので、多分、これでもまあまあ分類できると思われます。 ランダムに選んでも50%で正解しますが、例えば、165センチ以上は男だ、と予測してやれば、正解率は50%よりは確実に高いと思われます。 男性の方が筋肉質で、身長に対して体重が重い、などという関係があれば、更に正解率が高くなります。
ところが、この方法は区分が直線であるため、どうしても分類できないケースも出てきます。 例えば、男は体重が多くて背が低い、あるいは、体重が少なくて背が高いかどちらかしかないが、女は体重と身長が比例している、みたいなことが起きているとします。 男が左上と右下に極端にわかれて、間に女性がいます。 このままのFeature Spaceでは、一本の線を使って、男性と女性をわけるのは不可能です。 曲線とか、二本の線を使わないとできません。
これが証明されたのが、(Minsky and Papert 1969) でした。
ショック。 なんだ、Perceptronって使えないじゃん！ というわけで、しばらくこの線の研究が減ります。 その後、いきなりfeatureに重みを付けて足し算して、ある数より上か下かをみるんではなく、もう一段階踏んでみれば大丈夫だ、とわかってきます。 featureと重みを掛け算したものを幾つか足して、それにもう一度重みをつけて掛け算して足す、など、二段階、三段階踏めば、直線以外で分類できるぞ！と、分かったのです。
が、それだとOptimizationが上手くできない。 どうしたらいんだ？
Backpropagationが発見されます。(Rumelhart, Hinton, and Williams 1986）
そしてニューラルネットワークが一躍有名になり、流行ります。 二段階、三段階踏んでも、後ろから順番に重みを直すことで、学習できるようになったのです。 これで、直線以外で分類できるようになりました。
ところが。。。 この、Backpropagationは、Optimizationの方法としてはあまりエレガントでない。 パラメータ Θ を探すとき、局部的な解答を見つけてしまって、最適解を見つけられないし、訓練に時間がかかると分かってきます。
うーむ。
そうして、時代は Perceptronに逆戻り。 Support Vector Machine系の話が出始めます。 学習にあたって、最適な、男性と女性サンプルが一番遠くに分かれるような、一本の線をビシッと見つける方がいいのではないか？ という考え方です。 この、あたらしい考え方でOptimizationするのが良い、という理論が構築されます。
Soft Margin Support Vector Machineが発見されます。 (Boser, Guyon and Vapnik 1992)
だが、そのままでは曲線を使って分類できない。 なんとか、曲線を使ってビシッと分類できないものか？？？ 曲線を扱えるModelで、うまくOptimizationはできないのか？？
ここにきて、もうひとつの方法が注目されます。
Kernel Trickです (Aizerman, Braverman and Rozonoer 1964)
もともとのFeature Space から、もっと高い次元の新しい Feature Space へ、Kernel Trickを使って移動しよう。 その高い次元の方で、綺麗にサンプルを分けられる直線を探して、元の Feature Spaceに戻してやれば、そこでは、なんと曲線になるではないか！！！
ここ10年ぐらい、Classifierでは、この系統がずっと流行っています。 ニューラルネットワークは、ICMLや、NIPSのような機械学習の国際会議では、ほとんど見られなくなってしまいました。
