6x86のブログ

いつか秋葉原でCyrixのCPUを買うんだなんて夢を見てた田舎の中学生も大人になりました

主成分分析の基礎

はじめに

この記事は、TUT Advent Calendar 2014の24日目です。

メリークリスマス!数年前に修了したモノです! せっかくなので、現役技科大生にとって、少しでもプラスになる記事にしたいと思います。 というわけで、いま大人気の機械学習手法のうち、ベーシックな手法である主成分分析(Principal Component Analysis, PCA)を紹介したいと思います。 主成分分析は、顔認識や可視化など様々な場面で利用されています。

次元削減手法としての主成分分析

パターン認識などで、データの特性を捉えようとすると、どうしても次元数(特徴数)が大きくなってしまいます。 例えば、絵画を見た目で分類したい場合、人物画であるか風景画であるか、描かれた年代はいつか、使われている技法や色など、 パターンを判別するための特徴が増えていきます。 次元数が大きくなると、計算負荷が大きくなったり、良かれと思って追加した特徴が悪影響を与えたりなど、 不都合なことが出てきます。

この問題を解決する手段の一つが次元削減です。 元の高次元空間の重要な情報を保存した低次元部分空間への変換を得る手法です。 いま、d次元の特徴ベクトル\mathbf{x}\in\mathbb{R}^{d}が与えられたとします。 このとき、(線形)次元削減手法により、射影行列W\in\mathbb{R}^{d\times p}が計算できたとすると、 低次元表現\mathbf{y}\in\mathbb{R}^{p}は、\mathbf{y}=W^{\top}\mathbf{x}で得られます。 この射影行列Wを求める方法の一つが、主成分分析です。

主成分分析における射影行列の導出

以降、\mathbf{x}は中心化されているとします。 つまり、各特徴ベクトルから、平均ベクトル\mathbf{m}=\frac{1}{n}\sum_{i=1}^{n}\mathbf{x}_{i}を減じているとします。

主成分分析には様々な導き方があるのですが、今回は直感的に分かりやすい再構成誤差最小化の観点から導きたいと思います。 つまり、元の特徴ベクトルと、低次元表現から復元したベクトルとの誤差が小さくなるような、射影行列を求めます。これを数式で表すと、次のようになります。

{ \displaystyle
\min\frac{1}{n}\sum_{i=1}^{n}\left|\left|\mathbf{x}_{i}-W\mathbf{y}_{i}\right|\right|^{2}
}

では、どんどん式を展開していきましょう。

{ \displaystyle
\frac{1}{n}\sum_{i=1}^{n}\left|\left|\mathbf{x}_{i}-WW^{\top}\mathbf{x}_{i}\right|\right|^{2}
}

{ \displaystyle
=\frac{1}{n}\sum_{i=1}^{n}(\mathbf{x}_{i}-WW^{\top}\mathbf{x}_{i})^{\top}(\mathbf{x}_{i}-WW^{\top}\mathbf{x}_{i})
}

{ \displaystyle
=\frac{1}{n}\sum_{i=1}^{n}(
  \mathbf{x}_{i}^{\top}\mathbf{x}_{i}-
  \mathbf{x}_{i}^{\top}WW^{\top}\mathbf{x}_{i}-
  \mathbf{x}_{i}^{\top}WW^{\top}\mathbf{x}_{i}+
  \mathbf{x}_{i}^{\top}WW^{\top}WW^{\top}\mathbf{x}_{i}
)
}

ここで、W^{\top}W=Iとすると(正規直交基底とすると)、

{ \displaystyle
\frac{1}{n}\sum_{i=1}^{n}\left(\mathbf{x}_{i}^{\top}\mathbf{x}_{i}-(W^{\top}\mathbf{x}_{i})^{\top}W^{\top}\mathbf{x}_{i}\right)
}

となります。さらに、C=\frac{1}{n}\sum\mathbf{x}\mathbf{x}^{\top}とおき、任意のベクトル\mathbf{a}に対して\mathbf{a}^{\top}\mathbf{a}=\text{Tr}(\mathbf{a}\mathbf{a}^{\top})が成り立つことを利用すると、以下のようになります。

{ \displaystyle
\text{Tr}(C)-\text{Tr}(W^{\top}CW)
}

第一項がWに依らないことを考慮すると、再構成誤差最小化は、 W^{\top}W=Iという制約のもとで、\text{Tr}(W^{\top}CW)を最大化する問題となります。 これは、ラグランジュの未定乗数法を用いて、

{ \displaystyle
\mathcal{L}=\text{Tr}(W^{\top}CW)-\text{Tr}((W^{\top}W-I)\Lambda)
}

を、W偏微分して0と置くことで、以下の固有値問題に帰着します。ここで、\Lambdaは未定乗数からなる対角行列です。

{ \displaystyle
CW=W\Lambda
}

つまり、主成分分析の射影行列Wは、(共分散)行列C固有値分解することで得られる、 上位p個の固有値\lambda_{1},\ldots,\lambda_{p}に対応する 固有ベクトル\mathbf{w}_{1},\ldots,\mathbf{w}_{p}を並べたものとなります。

主成分分析による可視化

主成分分析の応用例として、高次元データを可視化してみましょう。 使用するデータは、USPS Handwritten Digitsという大きさが16x16の手書き数字画像のデータです。 画像の各ピクセル値を並べると16x16=256次元の特徴ベクトルができます。 この特徴ベクトルを、主成分分析を用いて二次元に削減したものが、以下の画像です。

f:id:c6x86:20141224003912p:plain

256次元の空間は想像がつかないですが、このように主成分分析で可視化することで、パターンの配置が把握できるようになります。 ちなみに、同じ数字が近くに配置されるかは、次元削減手法だけでなく、特徴ベクトルによっても変わってきます。

おわりに

主成分分析は、1900年代初頭に提案された歴史ある(?)手法で、様々なバリエーションがあります。 目的に合わせて、色々と探してみると、楽しいのではないでしょうか!?