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

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

Principal Anglesの日本語訳って何?

と、タイトルからいきなり疑問形なわけですが・・・
先日の記事で書いた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の1つは{\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}  (1)

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

となります(今、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

2つの式から、次の2式が導出されます。
{\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}の最適解(停留点の1つ)を \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とします。
これを(1)の式に代入すると、

\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つの要素のみ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とグラスマン多様体の関係についてちょっとだけ述べておくと、
グラスマン多様体上の2点間の測地線距離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年のころから思いつつ、
いつの間にか、社会人2年目なわけですよ