最大マージン kNN と SVM の関係: kNN も最近はがんばっています

先日書いた機械学習における距離学習の続き。

kNN (k-nearest neighbour: k 近傍法)は Wikipedia のエントリにも書いてある通り、教師あり学習の一つで、あるインスタンスのラベルを周辺 k 個のラベルから推定する手法。memory-based learning と呼ばれることもある。単純に多数決を取る場合もあれば(同点を解決する必要があるが)、近いインスタンスの重みを大きくする場合もあるのだが、いずれにせよかなり実装は単純なので、他の機械学習との比較(ベースライン)として使われることも多い。

簡単なアルゴリズムではあるが、1-NN の場合このアルゴリズムの誤り率はベイズ誤り率(達成可能な最小誤り率)の2倍以下となることが示されたり、理論的にもそれなりにクリアになってきているのではないかと思う。また、多クラス分類がちょっと一手間な SVM (pairwise にしたり one-vs-rest にしたりするか、[Crammer and Singer 1999] などの手法を用いたり)と違って、近いところ取ってくればいいので、多クラスでも全く問題ない、という利点がある。

ただ結局 kNN はインスタンス同士の距離をどう選ぶかというのが一番の問題で、特に素性が低次の場合はいいのだが、自然言語処理など典型的には高次元スパース(素性の数が多いが、ほとんどの素性の値はゼロ)であるような分野では、「次元の呪い」のためにいい性能が出ないことが多い。(これを回避するために、まず素性を PCA なり SVD なりで次元圧縮しておいて、その中で kNN するとスパースネスが回避されていい性能になることが知られている)　また、近いインスタンスを探さないといけないので、学習の時間は関係ないが、高速な距離計算ができないと分類時に時間がかかってしまうという問題点がある(ピボットを用いた pruning や Locality Sensitive Hashing を使うとかいろいろ手はあるのだが)。

距離にはユークリッド距離が用いられることが多いのだが、ここはいろんな距離関数がありえて、マハラノビス距離が用いられたり、他の尺度が用いられたりすることもある。そこで、教師あり学習で(kNN のための)マハラノビス距離を学習する手法が最近出てきた。特に kNN の設定では、線形変換するだけでもかなり性能が上がることが確認されているので、いろいろな手法が提案されている。

そのうち Large Margin Nearest Neighbour (LMNN) (Weinberger et al. NIPS-2005; http://www.weinbergerweb.net/Downloads/LMNN.htmlコードもダウンロードできる) と呼ばれる手法は、最大マージン(large margne だから最大じゃないと思うが他にいい言葉もないので……)化に基づいて kNN の距離を学習する手法であり、Semidefinite programming という制約付き最適化問題に落とし込むことで効率的にこの問題を解くことに成功している。

同じラベルを持つ近傍のインスタンスは近くに、逆に近くにあって違うラベルを持つインスタンスは遠くになるように距離を更新するのがミソである。(近傍の定義と k をいくつにするのかは cross validation したりして決める)　特に、グラフに基づく距離学習などではグローバルにラベルの制約を満たすように学習するのだが、この手法ではローカルにラベルの制約を満たせばよく、kNN では近くのインスタンスが正しくラベルつけられれば(グローバルはどうでも)いいので、ちょうど SVM で分離平面近くの(サポートベクトルとなるような)インスタンスにだけ重みがつくのとよく似ている。実際、他にもいろいろ SVM と似ているところがあり、論理的には kNN 版の SVM であると論文にも書かれている。(性能も SVM と同程度。SVM よりよいことも)

しかしやはり問題点は Semidefinite programming の部分で、これの計算が(最適解が効率的に求まるとはいえ)かなりヘビーなようで、さまざまな効率化の工夫をしているようだが、せいぜい数万事例(素性の次元は PCA で圧縮して数百次元程度にする)しか使えない、というのが問題点かな……。SVM も最近は(線形分類に限定したりすると)速いという話もあるので、実用上はあまり使えない気がする。

ちなみに高速な SVM としては Core Vector Machine (ツール名は LibCVM) (もしくはその発展系の Ball Vector Machine。O 野原くんの日記にも2007年に言及がある。)があり、これは色んなカーネルをサポートしていて、なおかつ学習が訓練データのサイズに依存しない(!)という利点がある。実際評価を見てみると学習時間はほとんど横ばいで、ほぼ一瞬で訓練終わるようで、しかも SVM と同じくらいの精度なので、こんなのよくできるなぁ、と思ったりもする。

半教師あり学習では Laplacian SVM (LapSVM) というのが現在の state-of-the-art のようだが、これはラベルありインスタンスとラベルなしインスタンス合わせて数千事例くらいしか扱えないようで(「半教師あり」と謳っている手法でも、よくよく論文を読むと全然スケールしない手法がほとんどで、ものすごくラベルあり事例が少ない状況で効果があるか、ラベルなし事例が少ししか現実的には足せないことが多いので、使おうと考えている人はスケーラビリティに注意したほうがいい)、これの半教師あり版の Sparcified Laplacian CVM というのを試してみたい(論文は NIPS-2006)のだが、まだコードに入っていないらしい。あと、多クラス版も論文には書いてあるのだが、実装はまだリリースされていないとのこと。(Windows 版しか正式にサポートされていないようなので FreeBSD でコンパイルできるように修正して使ってみたが、確かに学習は大規模データでも異様に早くてびっくり。ファイルを読み書きしている時間のほうがながいんじゃなかろうか……)

ともあれ、LMNN について詳しく知りたい人は彼の発表論文リスト(←各論文それぞれに論文の中から取った画像が貼られていて、こういう紹介の仕方もあるのか！　とびっくりしたので、一度クリックされることをお薦めする)から辿れる

• Weinberger and Saul. Distance Metric Learning for Large Margin Nearest Neighbor Classification (JMLR 09)

を読むとよい。これは彼の NIPS-2005 と ICML-2008 の論文をまとめた論文なので、短いほうが読みやすい人は個々の論文を読んでもらえるといい。

さて、一番書きたかったのは、これを書いている Weinberger は結局 Upenn を卒業したあと、今は Yahoo! Research で働いているらしい……。そして Semi-supervised Learning 本

Semi-Supervised Learning (Adaptive Computation and Machine Learning series)

を書いた Olivier Chapelle も現在は Yahoo! Research で働いているそうだ。うーむ。まあ、そんだけ。

機械学習ネタはいろいろ書きたいことはある(=自分が書くことで記憶に定着させるメソッド)のだが、なかなか論文との兼ね合いで書くのが難しい。論文に書けない(書かない)と分かったら日記に書いたりしているのだが……。