甲斐性なしのブログ

と、タイトルからいきなり疑問形なわけですが・・・
先日の記事で書いたGrassman Discriminant Analysisの論文内に
このPrincipal Anglesについて記述されていたので疑問に思ったわけです。
線形代数をきちんと学んだ人にとっては常識なのかもしれませんが、
お行儀があまりよろしくない学生だった僕には初耳の単語です。

さて、このPrincipal Anglesの定義は以下の通りです
（記号・表記の定義は前回の記事をご覧ください）。
2つの部分空間の間に下式を満たす $0 \leq \theta_1 \leq \theta_2 \leq \cdots \leq \theta_m \leq \pi/2$ が定義され、
これをPrincipal Anglesという。

$\displaystyle \cos{\theta_k}=\max_{{\bf u}_k} \: \max_{{\bf v}_k} \: {\bf u}_k^T {\bf v}_k$

${\rm subject} \: {\rm to}$
${\bf u}_k\in span({\bf Y}_1)$ , ${\bf v}_k\in span({\bf Y}_2)$ ,
${\bf u}_k^T{\bf u}_k=1$ , ${\bf v}_k^T{\bf v}_k=1$
${\bf u}_k^T{\bf u}_i=0$ , ${\bf v}_k^T{\bf v}_i=0 \; (k \neq i)$

つまり、 $\theta_1$ に関しては、なす角が最小（ $\cos{\theta}$ が最大）になるように、
両部分空間からそれぞれベクトル（ただしノルムが1）を持ってきて、
そのなす角を $\theta_1$ としましょう。
同様に $\theta_2$ も両部分空間からベクトルを選び、そのなす角を $\theta_2$ とするが、
ベクトルは $\theta_1$ の時に選んだそれと直交するように選びましょう。
ということです。 $\theta_3$ 以降も同様です。

では、このPrincipal Anglesを得る方法ですが、
実は、 ${\bf Y}_1^T{\bf Y}_2$ の特異値が $\cos\theta_1,\cos\theta_2,\cdots,\cos\theta_m$ と書かれています。
・・・なぜ？？？

ということで、本当にそうなのか確かめてみたいと思います。
とはいえ、全部のPrincipal Anglesが特異値だと示すのはちょっと面倒なので、
ここでは、Principal Anglesの１つは ${\bf Y}_1^T{\bf Y}_2$ の特異値ですよと示す方針で行きたいと思います。

まず、 $span({\bf Y}_1)$ 及び $span({\bf Y}_2)$ の任意の要素は、
任意のベクトル ${\bf a},{\bf b} \in {\bf {\cal R}}^m$ を用いて、
それぞれ以下のように表すことができます。

${\bf Y}_1 {\bf a} \in span({\bf Y}_1)$
${\bf Y}_2 {\bf b} \in span({\bf Y}_2)$

これらをPrincipal Anglesの定義式に代入すると、

$\displaystyle \cos{\theta}=\max_{{\bf a}} \: \max_{{\bf b}} \: {\bf a}^T {\bf Y}_1^T {\bf Y}_2 {\bf b}$ 　　（１）

${\rm subject} \:{\rm to}$
${\bf a}^T {\bf a}=1$ , ${\bf b}^T {\bf b}=1$

となります（今、１つのPrincipal Angleしか考えないので、直交の制約は省略）。
この最適化問題をラグランジュの未定乗数法を解くために、
ラグランジュ乗数 $\lambda_1, \lambda_2$ を導入し、次の式を考えます。

$L= {\bf a}^T {\bf Y}_1^T {\bf Y}_2 {\bf b} - \lambda_1({\bf a}^T {\bf a}-1) - \lambda_2({\bf b}^T {\bf b}-1)$

これを ${\bf a}$ 及び ${\bf b}$ で微分し、それぞれ0と置きます。
$\frac{\partial L}{\partial {\bf a}} = {\bf Y}_1^T {\bf Y}_2 {\bf b} - 2 \lambda_1 {\bf a}=0$
$\frac{\partial L}{\partial {\bf b}} = {\bf Y}_2^T {\bf Y}_1 {\bf a} - 2 \lambda_2 {\bf b}=0$

２つの式から、次の２式が導出されます。
${\bf Y}_1^T {\bf Y}_2 {\bf Y}_2^T {\bf Y}_1 {\bf a} = \lambda' {\bf a}$
${\bf Y}_2^T {\bf Y}_1 {\bf Y}_1^T {\bf Y}_2 {\bf b} = \lambda' {\bf b}$
ただし、 $\lambda' = 4\lambda_1\lambda_2$ 。

おお！これを見ると、 ${\bf a}$ と ${\bf b}$ の停留点はそれぞれ、
${\bf Y}_1^T {\bf Y}_2$ の（同じ特異値に対応する）左特異ベクトルと右特異ベクトルじゃないか！
ゴールが見えてきました。
ここで、 ${\bf a}$ と ${\bf b}$ の最適解（停留点の１つ）を $\hat{{\bf a}}$ と $\hat{{\bf b}}$ 、
${\bf Y}_1^T {\bf Y}_2$ の特異値分解を ${\bf Y}_1^T {\bf Y}_2={\bf U}{\bf \Sigma}{\bf V}^T$ とします。
これを（１）の式に代入すると、

$\cos{\theta}=\hat{{\bf a}}^T {\bf U}{\bf \Sigma}{\bf V}^T \hat{{\bf b}}=({\bf U}^T\hat{{\bf a}})^T {\bf \Sigma}{\bf V}^T \hat{{\bf b}}$
となります。
$\hat{{\bf a}}$ と $\hat{{\bf b}}$ はそれぞれ左右の特異ベクトルであることを思い出すと、
${\bf U}^T \hat{{\bf a}}={\bf V}^T \hat{\bf{b}}$ は１つの要素のみ1、他の要素は全て0のベクトルだとわかります。
従って、 $\cos{\theta}$ は ${\bf Y}_1^T{\bf Y}_2$ の特異値であるといえます。
ちょっと怪しい気がしますが・・・これで大丈夫なはず。

このPrincipal Anglesは、Grassmann Discriminant Analysis含め様々な
サンプルが部分空間である機械学習手法で要となっています。
例えば、Face recognition using temporal image sequence[Yamaguchi98]の論文では、
$\sin{\theta_1}$ を距離として用い、最近傍法を行うことで、
部分空間集合の学習・識別を実現しているらしい（元論文は読んでいません）。

最後にPrincipal Anglesとグラスマン多様体の関係についてちょっとだけ述べておくと、
グラスマン多様体上の２点間の測地線距離 $d_G({\bf Y}_i , {\bf Y}_j)$ は

$\displaystyle d_G^2({\bf Y}_i , {\bf Y}_j) = \sum_{k=1}^{m} \theta_k^2$

になるそうです。
多様体については、もっとちゃんと勉強せねば・・・と修士１年のころから思いつつ、
いつの間にか、社会人２年目なわけですよ

ときどき、学生のころ勉強していたこと（機械学習など）が懐かしくなって、
それに関連しそうな論文を探したり読んだりするんですが、
今日はその論文の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つのカーネル関数がどこから出てきたのかとか、グラスマン多様体がどうたらとか
肝心なことをスルーしちゃってます。
その辺りのことは、また別の記事で書くかもしれません（面倒になって放置する可能性の方が高いです）。
なお、ここまで書いてきましたが、実はまだ自分で実装して試していません。
これまた、いずれ実装してその結果をブログに書ければなぁと思います。

甲斐性なしのブログ

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

Principal Anglesの日本語訳って何？

Grassmann Discriminant Analysisの論文を読む