Hatena::ブログ(Diary)

備忘録とか あと あれとか それとか

2013-04-07

主成分分析(PCA; Principal Component Analysis)を丁寧に解く

この間書いた記事で,codecogsのOnline Latex Equation Editorを使えば,はてなダイアリーでもキレイな数式を書けることが分かったので,昔書いたPCAの導出を載せておこうと思う.

PCAは固有値分解で主成分を抽出する写像を求めることができるんだけど,多くの教科書などでは,「PCAの最適化問題固有値問題になるよー」と書いて終わりなので,「どうして固有値問題で解くことができるのか」というところを丁寧に導出したい.

考えた結果,すごい回りくどい方法しか思いつかなかったので,他のシンプルな解説もあるのかもしれない.

特に直感的な説明などなくて式を丁寧に見ていっているだけです.たぶん間違ってたり抜けているところがあるので,見つけた人は優しくご指摘下さい.(言い訳がすごい)

主成分分析(PCA)の目的と定式化

次の観測されたN個の観測データから成るデータ集合が与えられたとする.

  • : 観測値
  • : 各の次元
  • : 内の一次独立であるベクトル数(別に意味は分からくてもいい).が成り立つはず.

この観測値の次元がすごく大きい場合,すごく扱いづらい.

なので,観測値の情報を出来るだけ維持しながら,次元を小さくしたい.

この次元削減を次のような式で実現する.

ここで,

  • : 次元ベクトルを次元に小さくする行列.
  • はもちろんより小さくする.の場合は次元削減の点で言えば全然意味ないんだけど,そういうのを求めたい変態も少なからずいる.また内の一次独立であるベクトルよりも小さくしたほうがいい)
  • : 行列によってを次元削減した結果.
  • 単位行列の列ベクトルは互いに直交する.理由はよく分からないけど,PCAはこういう写像を求めたいんだから仕方ない)

は,「観測値の情報を出来るだけ維持しながら,次元を小さくする」写像である.

この「情報を出来るだけ維持する」ことを評価するために,ここでは,平均二乗誤差(MSE: Mean Squared Error)を小さくすることを考える.

この誤差は,と観測値の空間を見たときの誤差のことである.

わかりづらいので,2次元の観測値を1次元に次元削減する問題

を例にとって説明してみる.

下のクソみたいな図は,による次元削減を元の空間(観測値がある空間)で表したものである.

f:id:hgshrs:20130407173641j:image:w360

何が言いたいかというと,

  • 元の空間上でみると,次元削減後の観測値がある空間というのは,基底で張られた空間(図では直線で表される1次元空間)である.
  • は,そのを基底としたときの座標である.つまり,というのは,元の空間でみると,ベクトルの長さのこと.
  • したがって誤差ベクトルというのは次のように定義できる.

  • 全観測値の誤差ベクトルの長さ(の二乗)を平均を取ると,

このような感じで,PCAの問題は最適化問題として定式化される.

最適化問題を解く

上のを最大にするを求めることを考える.

は次のように変形できる.

ここで,は,相関係数行列で

と定義される.

固有ベクトル固有値によって対角化する.

をこの固有値固有ベクトルで表すと

は,の正規直交基底なので,の列ベクトルをこれらの線形結合で表すことにする.

したがって,

と書けるので,は,

関数として書くことができる.

ここで,の行列で,その要素は,である.

さらに,制約条件は,

と書くことができる.

以上より,PCAの最適化問題を求める問題から変形され,を求める問題として以下のように定式化される.

ここで,評価関数の和の形で書けるため,それぞれで最大化値を求めれば良い.

また,重複する制約条件を省略すると,は,その他のパラメータに依存していないことが分かる.

したがって,

となる.

制約条件をとして,これを評価関数に代入すると,

となる.

よりよりという結果から,明らかにである.

したがって,評価関数の最大値はであり,そのときのパラメータの値は,

となる.

が求まったので,次に,最適化問題

を考える.

まず,明らかに,である.

さらに,制約条件をとして,これを評価関数に代入すると,

となるので,先ほどと同様に,これの最大値はである.

これを実現するパラメータは,

同様に,全てのパラメータを求めると,

となる.

最後に,より,

となる.

したがって,は,の大きい個の固有値に対応する固有ベクトルとして求めることができる.

トラックバック - http://d.hatena.ne.jp/hgshrs/20130407/1365335916
リンク元