ホーム » 「固有値」タグがついた投稿

タグアーカイブ: 固有値

Lassoの最適化アルゴリズムの考察

こんにちは。

前回の最後に、
– Coordinate descent(座標降下法)
– ISTA (メジャライザー最小化)
– FISTA (高速化)
の3つの最適化方法を紹介しました。今回は上の2つを解説します。そして次回実装へうつりましょう。

まずは簡単なLassoからです。

Coordinate descent

いきなり解説に入る前に何ですが、座標降下法ってメチャクチャシンプルなんですよ。
けど全く有名じゃないんですよね。(多分、理由は記事の最後)まあ、アルゴリズムみましょう


目的関数f(x) = g(x) + \sum_{i=1}^{n} h_i(x)の最適化を考えます。
ここでgはconvexかつdifferentiabl、h_i(x)はconvexとします。
(例えばconvexかつundifferentiablなf(x)を考えた場合、反例があります。詳しくはREADMORE)
k=1, 2, \cdots回目の更新を右肩の添え字で表すと、各変数に対して

    \[x_1^{(k)} = \texttt{argmin } f(x_1, x_2^{(k-1)}, x_3^{(k-1)}, \cdots, x_n^{(k-1)})\]

    \[x_2^{(k)} = \texttt{argmin } f(x_1^{(k-1)}, x_2, x_3^{(k-1)}, \cdots, x_n^{(k-1)})\]

    \[x_3^{(k)} = \texttt{argmin } f(x_1^{(k-1)}, x_2^{(k-1)}, x_3, \cdots, x_n^{(k-1)})\]

のように更新するアルゴリズムです。


Pointは1つ、変数を1つずつ更新するんです。その他の変数は定数とみるんです。なので

この図の感じですね。しかし次の問題を考えてみましょうx \in \mathbb{R}^2に対して

    \[\texttt{Minimize } x_1^2 + x_2^2 + 5|x_1 + x_2|\]

です。例えば初期値をx=(1,-1)で座標降下法をアプライしてみると
x_1, x_2のどちらから更新してもx=(1,-1)で停滞することがわかります。しかし
これは明らかに最適解はx=(0,0)ですよね。こういったことからスパースな問題にはあまり良くないようです。

次にメジャライザーの方を行きましょう。

Iterative Shrinkage Thresholding

ちなみにこのアルゴリズムは初めて聞きました。EMアルゴリズムでも似たことが行われますね。
こちらもアルゴリズムは単純で

テイラー展開を行い、目的関数を置き換えることで最適化問題を解きやすい形にしよう

というものです。


一次元の場合、fx=a周りでのテイラー展開

    \[f(x) \approx f(a) + f^{(1)}(a)(x-a) + \frac{1}{2!} f^{(2)}(a)(x-a)^2 + \frac{1}{3!} f^{(3)}(a)(x-a)^3 + \cdots\]

多次元の場合、

    \[f(\vc{x})= f(x_1,x_2, \ldots, x_n)\]

    \[f(\bf{x}) \approx f(\bf{a}) + Df(\bf{a}) (\bf{x}-\bf{a}) + \frac{1}{2} (\bf{x}-\bf{a})^T Hf(\bf{a}) (\bf{x}-\bf{a})\]


下の図がイメージになります。上界というのは「より大きいやつ」という意味です。

この図からアルゴリズムがどうやって動いて何で最適化できるのかは直感的にわかったかと思います。
しかし、このメジャライザーが本当に存在するのか?など疑問に思う人がいるでしょう。
では考察しましょう。

まず初期値をx^{(t)}とします。そして目的関数を\mathcal{L}(x),メジャライザーを\mathcal{T}(x)とします。
そして、メジャライザーは次のような性質を満たしてほしいです。
\mathcal{L}(x^{(t)}) = \mathcal{T}(x^{(t)})
\forall x\neq x^{(t)} に対して \mathcal{L}(x) \leq \mathcal{T}(x)
すると性質から明らかにTの最小化がLの最小化に繋がることがわかります。
では実際にそんな都合のいい\mathcal{T}(x)を探しましょう。の前にちょっと寄り道します。

どんな形のメジャライザーが都合いい?

メジャライザーT(x)を探すといえどこのままでは全くわかりません。
T(x) = x^2にすればいいのか?いや、それもわかりません。なので

都合のいいメジャライザーの形を予想します。

いきなりですが次の最適解xを考えましょう。次元は1です。(\lambda \geq 0)

    \[\texttt{argmin } \frac{1}{2} (y-x)^2 + \lambda |x|\]

前回の記事でやったようにこれは場合分けで簡単にできますね
\forall x \geq 0に対して

    \[\frac{1}{2} (x^2 - 2xy + y^2 + 2\lambda x) = \frac{1}{2} (x - (y-\lambda))^2 + \texttt{const}\]

同様にして\forall x < 0に対して

    \[\frac{1}{2} (x - (y+\lambda))^2 + \texttt{const}\]

では最後にyの範囲で場合分けすると前回のSoft thresholding functionが出てきましたね。

    \[x = S ( y, \lambda )\]

詳しく復習すると
y < - \lambdaの時

    \[x= y + \lambda\]

- \lambda \leq y \leq \lambdaの時

    \[x = 0\]

y > \lambdaの時

    \[x = y - \lambda\]

これが大切です。

 つまり平方完成して解が求まりました。

ではLassoの目的を再掲しましょう。

    \[\texttt{argmin } ||y - Xb||_2^2 + \lambda|b|_1^1\]

今の例と似てますよね。

 しかしここままでは平方完成できない

ここで

 平方完成できるやつを考えよう!!!

これがほしいメジャライザーを予測するということです。

では元に戻って都合のいい\mathcal{T}(x)を探しましょう。平方完成できるやるがいいんでしたね。
テイラーの2次近似の形を想像しながら

    \[\mathcal{T}(\mathbf{x}) = \mathcal{L}(\mathbf{x}^{(t)}) + \frac{d\mathcal{L}(\mathbf{x}^{(t)})}{d\mathbf{x}}(\mathbf{x} - \mathbf{x}^{(t)}) + \frac{\rho}{2}\bigl\vert\mathbf{x}-\mathbf{x}^{(t)}\bigr\vert^2\]

という形で考えましょう、(\frac{\rho}{2}は計算の都合上のもの)そうすれば

    \[= \frac{\rho}{2} \Bigl\vert \bigl( \mathbf{x}^{(t)} - \frac{1}{\rho} \frac{d\mathcal{L}(\mathbf{x}^{(t)})}{d\mathbf{x}}\bigr) - \mathbf{x} \Bigr\vert^2 + \texttt{const}\]

とできますね。よって

    \[\text{argmin } \Bigl(\mathcal{T}(\mathbf{x}) + \lambda |\mathbf{x}|\Bigr)\]

    \[x^{(t+1)} = S \Bigl( \frac{1}{\rho} \frac{d\mathcal{L}(\mathbf{x}^{(t)})}{d\mathbf{x}}, \lambda \Bigr)\]

となります。

 実はまだ終わっていない

そうなんです。先ほどメジャライザーを考えたときに\rhoを使いましたね。
この\rhoを決める必要があります。メジャライザーの性質(2)から

    \[\mathcal{T}(\mathbf{x}) - \mathcal{L}(\bf{x}) = \frac{1}{2} (\bf{x} - \bf{x}^{(t)})^\top (\rho I - X^TX) (\bf{x} - \bf{x}^{(t)})\]

が「0以上」を任意の\bf{x}について言える必要があるので

 (\rho I - X^TX)が半正定値

の必要があります。つまり、X^TXの最大の固有値が\rhoとして取りうる最小の値になります。

そこで固有値の大きさを見積れる定理があるのでそれを使いましょう。
Gershgorin circle theorem
Gershgorin’s Theorem for Estimating Eigenvalues
この定理からmaxをとることで

    \[\texttt{eigenvalue } \le \max_j \sum_i\bigl\vert{\mathrm{X^\top X}}_{ij}\bigr\vert\]

と固有値の大きさが見積もれます。

長かったですがとりあえずLassoはおしまいです。

でわ。

READMORE

ねぇPython、PCAって何?(実装編+)

こんにちは。では前回の内容を踏まえて空間を変えないPCAを行いましょう。今回使うのは

顔のデータ

各次元4096で400サンプル。これを空間を保ち64次元に落とす。つまり4096次元の空間で64本の固有ベクトルがはる空間へ射影する。

これでPCAは一件落着。

 

ニューラルネットワークに深入りしていく予定。

でわ。

ねぇPython、PCAって何?(理論編+2)

こんにちは。前回、射影行列を学びました。n次元ベクトルaを考えよう。行列Vの列ベクトルが作る空間の中でもっともaに近いものはVcという形で表された。ただし、cは縦ベクトルとすると

(1)   \begin{align*} Vc =  V(V^TV)^{-1}V^Ta \end{align*}

となりこれがもっともaに近いヤツで

    \[V(V^TV)^{-1}V^T \]

Vの列ベクトルがはる空間への射影行列

だった。今回はそのVはどんなやつ?か考える。つまりどんなベクトルが作る空間へ射影すればいいんだ?ということ

データ\in \mathbb{R}^m(m次元)

平面を貼るベクトルをU=[v_1, \cdots, v_n]

ただしv_i \in \mathbb{R}^m , i=1,\cdots,n

とする。目標はUを見つけ出すこと。計算の前にいくつか確認しておこう。

  1. 実対称行列の固有ベクトルは直行
  2. 実対称行列は対角化可能
  3. グラムシュミットで正規直交基底が作れる
  4. tr(AB) = tr(BA)
  5. x^T A x = tr(x^T A x)

まず、3番より射影行列P_wは次のようになる

    \[P_w = U(U^TU)^{-1}U^T = UU^T\]

ではどうやってUを決定するかだが、前回同様、分散を最大化させる作戦でいこう。射影後の分散が最大化されるようにUを決定したいので

(2)   \begin{align*} \sum_{i=1}^{N} \|P_w x^{(i)} \|^2 &=& \sum_{i=1}^{N} \|UU^Tx^{(i)} \|^2     \\ &=& \sum_{i=1}^{N} (UU^Tx^{(i)})^T(UU^Tx^{(i)})     \\ &=& \sum_{i=1}^{N} x^{{(i)}^T}UU^TUU^Tx^{(i)}     \\ &=& \sum_{i=1}^{N} x^{{(i)}^T}UU^Tx^{(i)}         \\ &=& \sum_{i=1}^{N} tr(x^{{(i)}^T}UU^Tx^{(i)})       \\ &=& \sum_{i=1}^{N} tr(U^Tx^{(i)}x^{{(i)}^T}U)     \\ &=& tr(U^TXX^TU)      \\ &=& tr(U^T P^TDPU)      \\ &=& tr((PU)^T D (PU)) \end{align*}

ここで、対称行列XX^TP^TDPと変形しました。これを行列の対角化といいます。ここで、Pは固有ベクトルを基底とした空間から標準基底の空間への変換行列なんですが、重要なことは基底(軸)の取り方によって座標が変わるということでしたね。これを踏まえて

    \[tr((PU)^T D (PU))\]

を最大化させるUの形を考えよう!例えば

    \[  tr \left(  \begin{pmatrix} a  & b & c  \\ d  & e & f  \\  \end{pmatrix}   \begin{pmatrix} 12 & 0 & 0 \\ 0 & 7 & 0 \\ 0 & 0 & 1 \\   \end{pmatrix} \begin{pmatrix} a & d  \\ b & e  \\ c & f    \end{pmatrix}  \right)\]

において[a,b,c], [d,e,f]を正規直交とするときどんなものがトレースを最大化させるか?

e_1, e_2

しかないのは明らか。よってUの列ベクトルには固有ベクトルが並べばいいことがわかります。実際、例えばU=p_1が最大固有値 \lambda_1に対応する固有ベクトルとする時Pp_1e_1となる(Pが座標変換するから)

(3)   \begin{align*} tr((PU)^T D (PU)) = tr((Pp_1)^T D (Pp_1)) = tr(e_1^T D e_1) = \lambda_1 \end{align*}

となるからです。従って射影行列P_w=UU^TUは列ベクトルとして固有ベクトルを並べればいいことがわかりました。

次回はこれを実装で確かめましょう。

 

でわ

 

基底と座標と対角化

こんにちは。PCAの(理論編+2)では基底と座標について少し複雑なトークがでてきます。この記事はそのためのものですが、そのためにとどまらず

基底と座標

そして

対角化

はとても重要なものなので是非マスターしましょう。

ここでは基底と座標の関係を確認しよう。とはいってもいきなりやっても面白くないので簡単な例を用いてその重要性を確認しよう。例えばベクトルp = [10, -4]は僕たちが無意識に使っている標準基底というもので

(1)   \begin{align*} p = 10 \begin{pmatrix} 1\\0 \end{pmatrix} -4 \begin{pmatrix} 0\\1 \end{pmatrix} \end{align*}

つまり座標は[10,-4]とかけます。ところが次のような基底a,bを考えると

(2)   \begin{align*} p = 2 \begin{pmatrix} 1\\2 \end{pmatrix} +8 \begin{pmatrix} 1\\-1 \end{pmatrix} \end{align*}

となり、これはつまりベクトルpa,bを基底としてみるとその座標は[2,8]となり標準基底で見たときの座標と異なっている、という事実が重要です。これを一般化しましょう。

wというベクトルを考える

u_k, v_k  (k=1\cdots,d)はそれぞれ異なる基底とする

uvの関係式がわかれば異なる基底間での座標変換ができますよね。進めていきましょう。

これを全v_kで行うと

となり、両辺に右からpをかけると

となりcの形がわかりました。さらにm_kv_kuで書いた時の座標であることに注意すると

となり基底vでの座標から基底uでの座標への変換行列Mとわかりました。となるとM^{-1}c = pでその逆の変換ができることもわかります。

これを先ほどの例に適応し確認してみましょう。標準基底

(3)   \begin{align*} e_1 = \begin{pmatrix} 1\\0 \end{pmatrix} ,  e_2 = \begin{pmatrix} 0\\1 \end{pmatrix} \end{align*}

から次の基底

(4)   \begin{align*} v_1 = \begin{pmatrix} 1\\2 \end{pmatrix} ,  v_2 = \begin{pmatrix} 1\\-1 \end{pmatrix} \end{align*}

への座標変換行列Mは各e_1,e_2v_1,v_2で書いた時の座標を並べればいいので

(5)   \begin{align*} M = -\frac{1}{3} \begin{pmatrix} -1&-1 \\ -2&1 \end{pmatrix} \end{align*}

です、これをもちいて計算すると

(6)   \begin{align*} -\frac{1}{3} \begin{pmatrix} -1&-1 \\ -2&1 \end{pmatrix}  \begin{pmatrix} 10\\-4 \end{pmatrix}  = \begin{pmatrix} 2\\8 \end{pmatrix} \end{align*}

とたしかに先ほどと同じ結果になりました!今回はMを基底を元に書き換えましたが考える2組の基底のうち片方が標準基底の場合は簡単に求まります。なぜならv_1,v_2e_1,e_2で書くと座標はv_1,v_2そのものになり逆行列を計算するなりすればいいからです。

では次に対角化についてです。まずは次の問題を考えてみましょう。僕たちにとってポピュラーなの標準基底Wを使う空間において

    \[ A = \begin{pmatrix} 1&-2\\2&1  \end{pmatrix}\]

という行列による線形変換を考えます。つまりy = Ax

この❓にはどんな行列が来ますか?青矢印のルートと赤矢印のルートは等しくなる必要があります、なので

この行列Xは

と求まります。

だからなに?

ですよね。とりあえずここからわかることは

標準基底Wの空間での線形変換行列が

    \[\begin{pmatrix} 1&-2\\2&1  \end{pmatrix}\]

は基底Vの空間では

    \[\begin{pmatrix} 1&2\\-2&1  \end{pmatrix}\]

この例では特に面白いことはありません、、、、VAの固有ベクトルでない。一方で

    \[B =  \begin{pmatrix} 0.5&1.5 \\  1.5&0.5  \end{pmatrix}\]

こんな例を考えると

おっとーーーーー?

基底Vの変換行列が対角行列になった!

この時の基底Vは行列Bの固有ベクトルになってる!実際、

となりたしかに

    \[Bx = \lambda x\]

となっている!

で、なにがいいの?

まずは

計算量が少ない。これはでかい、

メリットそれだけ?

可視化で確認しよう!

つまり

データが見やすくなる

 

本日は基底変換、座標変換、対角化について学びました。これで引き続きPCAに取り組みましょう。

 

でわ

ねぇPython、PCAって何?(理論編+1)

こんにちは。理論編で主成分分析についてはみなさん理解できたと思います。が。本日は少し応用です。

とりあえず復習から始めましょう。

PCAは固有ベクトルへの射影

そうです。たとえば400次元から2次元へのPCAは固有値を大きい方から2つ選び、対応する固有ベクトルに射影です。つまり

軸を新しく定義している

つまり

空間が変わっている

 

まさにこの図、3次元のデータ(左)にPCAをかけて2次元データ(右)にしている。軸が異なるどころかその数も変わっていることより空間が変わったことは明らか。

しかし、今回は

次元を保ったまま空間を押しつぶす

をします。

重要なのは次の考え方のみ!

適当に作った例だと

    \[ [1,2,3] \rightarrow [4,-2]  \]

が前回のPCAに対し

    \[ [1,2,3] \rightarrow [4,-2, 0]\in H\]

のように次元を保ったまま平面上の点に置き換える。上の図だとc_1,c_2 \in \mathbb{R}に対し

    \[ a' =  c_1v_1 + c_2 v_2  = c_1 \begin{pmatrix} v_{11} \\ v_{12} \\ v_{13}  \end{pmatrix} + c_2 \begin{pmatrix} v_{21} \\ v_{22} \\ v_{23}  \end{pmatrix} \]

とできる。ただし、a,a',v_1,v_2\in \mathbb{R}^3である。

 

まとめると、

あるベクトルたちの線型結合で全部書き直そう

ということ。上では3次元ベクトル2本(v_1,v_2)用いて平面を構成した。aを平面H上の点a'としようということ、これを全データ点で行う。計算してみよう。V = [v_1,v_2]とするとVcv_1,v_2が貼る平面状の点を表すことができるので

    \[\|a - Vc\|^2  \]

を最小化するようなcを見つければいい。このときVc=a'となる。ここで

    \[\frac{\partial}{\partial x} x^T A x = (A+A^T)x\]

    \[ \frac{\partial}{\partial x} a^Tx = a^T, \frac{\partial}{\partial x} x^Ta = a\]

これらの公式を用いて

(1)   \begin{align*} \frac{\partial}{\partial c} \|a - Vc\|^2 &= \frac{\partial}{\partial c} (a - Vc)^T(a - Vc) \\ &= \frac{\partial}{\partial c} \left(c^TV^TVc - c^TV^Ta - a^TVc +a^Ta  \right) \\ &= \frac{\partial}{\partial c} \left(c^TV^TVc - 2a^TVc +a^Ta  \right) \end{align*}

微分を0とする。

(2)   \begin{align*} \frac{\partial}{\partial c} \|a - Vc\|^2 &= \frac{\partial}{\partial c} \left(c^TV^TVc - 2a^TVc +a^Ta  \right) \\ &= (V^TV + (V^TV)^T)c - 2V^Ta = 2V^TVc - 2V^Ta = 0 \end{align*}

従って逆行列をかけることで

(3)   \begin{align*} c =  (V^TV)^{-1}V^Ta \end{align*}

つまり!

(4)   \begin{align*} Vc =  V(V^TV)^{-1}V^Ta \end{align*}

a'である。

    \[V(V^TV)^{-1}V^T \]

Vの列ベクトル空間がはる空間への射影行列

という。

では数学の時間です。

データ\in \mathbb{R}^m(m次元)

平面を貼るベクトルをV=[v_1, \cdots, v_n]

ただしv_i \in \mathbb{R}^m , i=1,\cdots,n

とする。目標はVを見つけ出すこと。見つかれば上で導出した射影行列を全データにかければ良い。なんだけど、ちょっと長くなるから次の記事で。

 

でわ。

 

READMORE

  1. http://python.astrotech.io/machine-learning/principal-component-analysis.html#id1
  2. http://www.asahi-net.or.jp/~jb2y-bk/NaturalSci/math/daenmen.htm

ねぇPython、PCAって何?(実装編)

こんにちは。英語が非常に難しい」そんな日々が続きます。

主成分分析とは?

共分散行列の固有ベクトルへの射影による次元削減でした。固有ベクトルと固有値をパパッとほしいですね。

これ便利です。Numpyにその計算機あるんです。これを使って実装へレッツゴー

PCAってすごい簡単ですよね。ただ次元とデータが多くなると共分散行列と固有ベクトルの計算がかなり大変そうですが、、、

では簡単にまとめ

  • 共分散行列が大事
  • 各軸は固有ベクトル

最後に

軸30個 の世界から 軸30個の世界を軸2個の世界と見た 世界へ移動

はどうなる?

これは空間を維持した押しつぶしによる射影である。

と意味わからないことが書いていますがこれについてはまた今度。簡単な例だと、りんごを押しつぶして平たくすると(平面化)これは3次元空間を保ったまま2次元に落ちたと考えられるということです。

 

でわ。

ねぇPython、PCAって何?(理論編)

こんにちは。いまだにたまに暑いと感じるkzです。今回はなにをやりましょうかねえ。

このデータは見ての通り2次元(平面)データです。これを1次元(直線)に置き換えたいです。

各点の配置は?

置き換える時に重要なのは距離感です。離れていた点通しが置き換えた先でご近所さんになると元のデータをうまく表現できてるとは言えませんよね。それが次の図です。

離れていたはずがご近所さんになってしまっています。一方で次の図はどうでしょう、

さっきよりはうまく元のデータを表せていますよね。ではこれを先ほどの青いデータで考えると

この赤矢印上に先ほどと同様にして点を置き換えれば\mathbb{R}^2 \Rightarrow \mathbb{R}^1つまり2次元のデータを1次元で説明できることになります。

では本日の本題に入りましょう。

上の赤矢印(軸)

どうやっていい軸を選びましょうか。じーっと見てみましょう。広がっている方向に矢印が伸びていますね。つまりいい軸とはデータを矢印だけで表現したものと捉えることができそうです。では具体的にいい軸(ベクトル)をどう求めるかを考えましょう。

とりえあず求めるベクトルをvとします。今長さは別に興味ないので| v |=1とします。

正射影ベクトルを考えます。下の緑(a_1)はaのbへの射影です。

  1. https://www.geogebra.org/m/mkV7F8Jf

上の図はaをデータ点bを求めたいベクトルとした時にa_2の最小化もしくわa_1の最大化がしたいことになります。この事実は次のgifより明らかです。

なので今回はデータをx_i、ベクトルをbとするとその正射影ベクトルは

    \[ \frac{x_i \cdot v}{|v|}  v\]

です。これを全データで最大化したいので次のようになります。\frac{1}{N-1}は都合上のものです!

    \[\frac{1}{N-1} \sum_{i=1}^{N}  (x_i^T v)^2 = \frac{1}{N-1}  \sum_{i=1}^{N}  (x_i^T v)^T(x_i^T v)\]

    \[=   v^T \left(\frac{1}{N-1}\sum_{i=1}^{N} ( x_i x_i^T)\right) v\]

となります。\frac{1}{N-1} \sum_{i=1}^{N} ( x_i x_i^T)これって何でしょう?一応ですがx_i,vは共に縦ベクトルです。

そうです共分散行列です。これを\Sigmaと書くことにします。すると

    \[v^T \Sigma v  \]

が今回の目的関数です。今まで通りならこれを最大化するだけだったんですが今回は制約があります。

    \[| v | = 1  \]

です。この状況を条件付き極値問題と言います。これを解くには技が必要です。

    \[\texttt{Maximize} ~~~ f(x,y)  \]

    \[\texttt{Subject to} ~~~ g(x,y)=0  \]

を考える、f,g\mathbb{C}^1級(微分可能かつ導関数が連続)とする。点Pが極値をとるならば

    \[\mathcal{L} (x,y, \lambda) = f(x,y) - \lambda g(x,y)  \]

    \[\nabla f (P) - \lambda \nabla g(P) = 0\]

を満たす。あくまで候補点です。要点だけいうと勾配が平行になる点です。

証明や詳しい解説はここにあります。

  1. https://en.wikipedia.org/wiki/Lagrange_multiplier
  2. http://www.yunabe.jp/docs/lagrange_multiplier.html
  3. https://ocw.mit.edu/courses/mathematics/18-02sc-multivariable-calculus-fall-2010/2.-partial-derivatives/part-c-lagrange-multipliers-and-constrained-differentials/session-40-proof-of-lagrange-multipliers/MIT18_02SC_notes_22.pdf

これをラグランジュの未定乗数法と言います。これを使って計算しましょう。

    \[  \mathcal{L} (v, \lambda)  =  v^T\Sigma v - \lambda (| v|)\]

    \[\frac{\partial \mathcal{L}}{\partial v}= (\Sigma+\Sigma^T)v - 2 \lambda v = 0  \]

    \[ \Sigma v = \lambda v\]

おっと、これわ。。。。

固有ベクトルと固有値そのもの

要点をいうとx\neq 0のベクトルが行列Aの固有値であり\lambdaがその固有ベクトルとは

    \[Ax = \lambda x\]

となることをいい、行列Aによる作用が伸縮になるベクトルを固有ベクトルといいその伸縮率を固有値といいます。

もう少し別の言い方をすると。行列をかけた時に向きが変わらないベクトルとその伸縮率です。

詳しくは下のリンクを見てください。

  1. https://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors
  2. https://qiita.com/kenmatsu4/items/2a8573e3c878fc2da306

したがって今回私たちが求めていたベクトル、いい軸は

データの共分散行列の固有ベクトル

とわかりました。つまりデータを固有ベクトルという軸へ射影することで得た新たなデータ点は

データの次元を落としつつ最大限に元のデータを表現している新しいデータ

ということになります。これがPCAのやってることです。

「PCAは射影である」

今回は2次元から1次元へのPCAでしたが一般にn次元へのPCAも同じです。固有ベクトルを軸としてとってきて射影により座標がデータのPCA後の座標です。2次元へのPCAなら2本の固有ベクトルにデータを射影して新たな座標を定義します。

最後に用語の説明をしておきます。

  • 第n主成分: 固有値が大きい方から数えてn番目のものに対応する固有ベクトルのことをいう。
  • 寄与率: (第n番目固有値/固有値の総和)
  • 累積寄与率: 寄与率の累積

寄与率?固有値?

はい、説明します。固有値は伸縮率といいました。つまり対応する固有ベクトル方向へのデータの散らばり具合です。よって固有値とはデータの広がり具合(分散)を説明します。なので「元データを説明している具合」を分散という観点から考えて寄与としています。

本日はここまで。でわ

参考;

  1. http://cs229.stanford.edu/notes/cs229-notes10.pdf