主成分分析

主成分分析とは

主成分分析(Principal Component Analysis、PCA)は、n次元の空間にあるデータ点をより少ないl次元の符号(コード)に圧縮する手法です。グッドフェロー(Ian Goodfellow)、ベンジオ(Yoshua Bengio)、クールビル(Aaron Courville)の教科書「Deep Learning」(2016年)は、PCAを「基礎的な線形代数の知識だけから導出できる、単純な機械学習アルゴリズムの1つ」として紹介しています。

損失のある圧縮という見方

同書はPCAを損失のある圧縮の問題として説明します。損失のある圧縮とは、精度を多少落とす代わりに、少ないメモリでデータを保存することです。

m個の点 x(1), ..., x(m) がn次元の空間 R^n にあるとします。各点 x(i) に対して、l次元の符号ベクトル c(i) を1つずつ求めます。l が n より小さければ、元の点の代わりに符号を保存するほうが、少ないメモリで済みます。

このために、次の2つの関数を用意します。

• 符号化関数 f(x) = c: 入力点から符号を作ります
• 復号化関数 g(c): 符号から元の点を復元します

圧縮なので、復元した点は元の点と完全には一致しません。この失われる部分が損失です。

復号化関数の形と2つの制約

PCAは、復号化関数をどう選ぶかによって定義されます。復号を単純にするため、符号に行列を掛けて元の空間 R^n に戻す形にします。

g(c) = Dc

ここで D は n行l列の行列で、復号の仕方を決めます。PCAは D に次の2つの制約を課します。

1. D の列どうしが互いに直交すること。これにより符号化の問題が簡単になります
2. D の各列の長さ(ノルム)が1であること。これにより解が1つに定まります

なお、l が n と等しい場合を除き、D は技術的には「直交行列」とは呼べない点に注意が必要です。

最適な符号の選び方

入力点 x に対する最適な符号 c* は、元の点 x と、符号から復元した点 g(c*) の距離が最も小さくなるように選びます。この距離はL2ノルムで測ります。

c* = argmin_c ||x - g(c)||_2

argmin_c は、右側の式の値を最も小さくする c を表す記号です。L2ノルムは0以上の値をとるので、L2ノルムそのものを最小にする c と、L2ノルムの2乗を最小にする c は同じになります。そこで、同じ問題を次の2乗の形に書き換えて扱います。

c* = argmin_c ||x - g(c)||_2^2

まとめると、PCAは「行列 D で復号するという単純な形を決め、D に直交と長さ1の制約を課したうえで、元の点と復元した点のずれが最も小さくなる符号を選ぶ」手法として組み立てられています。

復号化行列Dの求め方と特異値分解との関係

ここまでは1つの入力点xに対する最適な符号c*の求め方でした。次に、すべての点に共通して使う復号化行列D自体をどう選ぶかを考えます。

m個の点をすべて使い、元の点と復元した点のずれ(Frobeniusノルムで測った誤差)が全体として最も小さくなるようにDを選びます。Dの列は直交し長さ1という制約のもとで、この最適化問題をトレース(Tr、行列の対角成分の和)の性質を使って変形していくと、次のことが分かります。

最適なDは、m個の点を並べた行列XについてX^TX(Xの転置とXの積)の固有ベクトルのうち、固有値が大きいものからl個を選んだものです。l=1の場合で言えば、最適な1本の軸は、X^TXの最大の固有値に対応する固有ベクトルです。

特異値分解の記事で見たとおり、ある行列の右特異ベクトルは、その行列の転置とその行列自身の積の固有ベクトルと一致します。したがって、ここで求めたDの列(X^TXの固有ベクトル)は、Xの右特異ベクトルでもあります。主成分分析は、特異値分解を使って計算できる手法の1つです。