Blog
WEB+DB PRESS Vol.64に「作って学ぶ日本語入力」という特集記事を書かせていただきました。徳永です。全国の書店で発売中ですので、ぜひみなさんお買い求めください。（宣伝）
さて今回は、線形識別器でカーネルを使うのと同じ効果を得るための手法を紹介したいと思います。
カーネルとは
SVMはカーネルトリックによって非線形識別を可能としたことによって、研究コミュニティで大流行しました。
カーネルトリックは線形空間では線形分離できないデータを高次元空間に写像してそっちで線形分離しちゃおう、でも高次元に実際に写像してしまうと計算量が増えちゃうから、問題を等価な形に変形して高次元に写像した場合と同じ結果を高速に計算しようね、というテクニックです。具体的には、高次元データが出てくる部分は全部内積で書ける形に変形し、この内積の部分をカーネルと呼ばれる特殊な関数で置き換えます。
結局、自然言語処理の分野では、大規模データへ対応するためにはカーネルトリックはちょっと非現実的だよねということで、カーネルトリックなしの線形識別器がよく使われていますが、カーネルの持つ非線形分離の性質は魅力的です。そこで今回は、なんとか高次元空間へとうまいこと効率よく写像してやることでカーネルのように非線形識別を可能とするテクニックをいくつか紹介したいと思います。
二値素性に対するPower Set Kernelの高速化
二値素性、つまり特徴が0-1で表現される場合、ある種のカーネルに対しては、素性の組み合わせを用いることで同等の効果を実現できることが分かっています。例えば、多項式カーネルはその典型例ですし、より広く、Powerset Kernelと呼ばれる種類のカーネルに対して素性を明示的に取り出すことができることも既に実証されています[1]。この中には、メジャーなカーネルの一つであるRBFカーネルも含まれます。
カーネル関数のフーリエ変換
[1]では二値素性の場合はかなり広い範囲のカーネルが取り扱えるということがわかりましたが、特徴が0-1ではなく実数値で入力されるような場合にはどうもこの方法は使えないようです。
特徴が実数値である場合に、近似的でもいいからカーネルが使えれば嬉しいですね。Rahimiらは、そのための手法としてフーリエ変換を使う手法を提案しています[2]。以下ではその手法を簡単に説明します。
ある種のカーネル関数では、\(k(x,y)\)というという形ではなく、\(k(x – y)\)という形でカーネル関数を書くことができます。我々が欲しいのは、\(z(x) z(y) \simeq k(x – y)\)となる写像\(z(x)\)です。また、\(z(x)\)の値域が無限次元になったりしたら実際に計算できませんから、\(z(x)\)はの結果は十分に低次元である方が望ましいです。
ここでフーリエ変換が出てきます。\(k(x – y)\)の\(x – y\)は長いので\(\Delta\)と書くことにしましょう。\(k\)のフーリエ変換を\(p\)と書くことにすると、フーリエ変換後の関数\(p(\omega)\)は以下のような式になります。
\(p(\omega) = \frac{1}{2\pi} \int \exp(-j \omega \Delta) k(\Delta) d\Delta\)
Bochnerの定理より、\(k(\Delta)\)が適切にスケールを調整されていれば、\(p(\omega)\)は確率分布となります。Rahimiらの手法では、この確率分布からのサンプリングを行って特徴ベクトルを作ります。
暑いので太字にするのをサボってきましたが、実は\(x, y, \omega\)は\(d\)次元の実数ベクトルなので、\(\omega\)からサンプリングされたベクトルもやはり\(d\)次元のベクトルになります。それらのベクトルを\(w_i\)と表記することにすると、以下のような\(2D\)次元のベクトルが写像後のベクトルになります。
\(z(x) = \sqrt{\frac{1}{D}} [\cos(w_1\cdot x), \ldots, \cos(w_D\cdot x), \sin(w_1\cdot x), \ldots, \sin(w_D\cdot x)]\)
\(p(\omega)\)からのサンプリングはどうすんのよ…とちょっと途方に暮れそうになりますが、典型的ないくつかのカーネルについては論文中に\(p(\omega)\)の形を書いてくれているので、後は頑張ればサンプリングのコードは書けそうです。
Dは数百程度の次元でよく、データセットの性質にもよりますが、まじめに双対形式でカーネルを計算する場合と比べて10倍から100倍程度の高速化が行えたという報告になっていました。
[3]はこのテクニックを用いて、実際にRBFカーネル（Gaussianカーネル）の近似を行っています。 PASCAL VOC 2007のデータを使って画像からの物体認識の実験を行っています。こちらの実験結果によると、サンプリングの回数は1000〜2000程度は必要そうです。これはすなわち特徴ベクトルが1000〜2000次元になるという事に相当します。密ベクトルで1000〜2000というとちょっとデータがでかい気もいますが、これで精度が上がるのだと考えると、1000〜2000は非常にリーズナブル、良心的特徴数でございます、と言っても良いのかもしれません。
おまけ：Hash Kernel
カーネルで精度を上げるんだ、というよりは、メモリ消費量の削減や高速化の方に重きを置いた試みとしてHash Kernelというものがあります[4]。これはその名の通りで、特徴ベクトルにハッシュ関数をかけて狭い空間に写像してしまいます。写像後の空間を狭くすれば衝突の可能性が増えてしまうわけですが、ハッシュ後のデータサイズは28bit程度でも結構うまくいくそうです。
まとめ
ランダムにサンプリングすることでカーネルを近似して線形識別器に事えるようにするテクニックを紹介しました。計算量はちょっと増えてしまいますが、これで精度が2〜3%程度でも上がってくれるのであれば、なかなか嬉しい手法ですよね。何かで活用することができそうな手法であると感じました。
参考文献リスト
[1] 工藤 拓, 松本 裕治. 素性の組み合わせを実現する Power Set Kernel とその高速化. 電子情報通信学会「人工知能と知識処理」, 情報処理学会「知能と複雑系」, 人工知能学会「人工知能基礎論」 「知識ベースシステム」合同研究会. 2003
[2] A. Rahimi and B. Recht. Random features for large-scale kernel machines. In Proc. NIPS, 2007.
[3] Sreekanth Vempati, Andrea Vedaldi, Andrew Zisserman, C. V. Jawahar. Generalized RBF feature maps for efficient detection. 21st British Machine Vision Conference (BMVC), 2010 (Oral Presentation), Aberystwyth, UK
[4] Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alex Smola, Alex Strehl and Vishy Vishwanathan, Hash Kernels, Twelfth International Conference on Artificial Intelligence and Statistics, Florida, Apirl 14-19, 2009.
Tag
