甲斐性のない男が機械学習とか最適化とかを綴るブログ

うどんくらいしか食べる気がしない

Grassmann Discriminant Analysisの論文を読む

ときどき、学生のころ勉強していたこと(機械学習など)が懐かしくなって、
それに関連しそうな論文を探したり読んだりするんですが、
今日はその論文の1つを紹介しようかなと思います。

J. Hamm and D. D. Lee.
Grassmann Discriminant Analysis: a Unifying View on Subspace-Based Learning (2008)

従来の教師あり学習だと特徴ベクトルとして表現されているデータを
学習・判別するというのが一般的だといえます。
しかし、この論文では、複数の特徴ベクトルをひとまとめにした集合を、
1つのデータとして学習・判別する方法について言及しています。
例えば、同じ被写体を異なる角度から写した複数の画像を入力とし、
その被写体が何であるか判別するといったタスクへの応用が考えられます。

「複数の特徴ベクトルをひとまとめにした集合」をこの論文では、部分空間として取り扱います。
つまり、N個の学習サンプルがそれぞれm次元部分空間として表現されているときの、
教師あり学習手法を提案しています。
取り扱う問題をもう少し詳しく記述すると、
まず、特徴ベクトルの次元をD、各サンプルの部分空間の次元はmとします(当然、D>mです)。
{\bf Y}\in{\bf {\cal R}}^{D\times m}を部分空間の正規直交基底を並べた直交行列とし、
{\bf Y}で張られる部分空間をspan({\bf Y})と表現します。
従って、N個の学習サンプルの集合は、\{span({\bf Y}_1),span({\bf Y}_2),\cdots,span({\bf Y}_N)\}になります。
なお、このような部分空間を元とする集合をグラスマン多様体{\bf {\cal g}}(m,D)と呼ぶそうです。
なので、グラスマン多様体上のN個の学習サンプルをどう学習するかという問題になります。

グラスマン多様体とかなにやら物騒な単語が出てきました。
と言っても、その辺りの理論は置いていおいて実装したいというなら、
やることは部分空間同士のカーネルを定めて、
カーネル拡張したフィッシャー判別分析法を適用するというものなのでさほど難しくないと思います。
てことで、早速実装方法に移ります。

まず、特徴ベクトルの集合\{{\bf x}_1,{\bf x}_2,\cdots,{\bf x}_p\}から部分空間の直交基底を計算して\bf{Y}を得ます。
その方法としては、\bf{X}=[{\bf x}_1,{\bf x}_2,\cdots,{\bf x}_p]という行列を特異値分解して、
その左特異ベクトルのうちm個を{\bf Y}とすればよいはずです。
この操作をN組の学習サンプル全てに施し、\{{\bf Y}_1,{\bf Y}_2,\cdots,{\bf Y}_N\}を得ます。

次に、グラム行列を計算します。
この論文で提案しているカーネル関数は以下の2種類です。

Projection kernel
k_p({\bf Y}_i,{\bf Y}_j) = ||{\bf Y}_i^T{\bf Y}_j||_{F}^2

Binet-Cauchy kernel
k_{bc}({\bf Y}_i,{\bf Y}_j) = (\det{\bf Y}_i^T {\bf Y}_j)^2

このどちらかのカーネル関数を用いてグラム行列を計算した後は、
カーネルフィッシャー判別分析を適用し次元削減すればOK。
カーネルフィッシャー判別分析については、この論文内にも記述されていますし、
Fisher Discriminant Analysis with Kernels[Mika99]が元論文のはずなので、
そちらも参考になると思います。
次元削減後は普通にユークリッド空間上のデータとして扱えます。
煮るなり焼くなりしちゃってください。

とりあえず、目的と手法の実装方法を書いていみましたが、
上記2つのカーネル関数がどこから出てきたのかとか、グラスマン多様体がどうたらとか
肝心なことをスルーしちゃってます。
その辺りのことは、また別の記事で書くかもしれません(面倒になって放置する可能性の方が高いです)。
なお、ここまで書いてきましたが、実はまだ自分で実装して試していません。
これまた、いずれ実装してその結果をブログに書ければなぁと思います。