PRML 読書会 #15 「12.3 カーネル主成分解析」資料

「パターン認識と機械学習」(PRML)読書会 #15 で担当する 12.3「カーネル主成分解析」の資料です。

カーネルちょび復習(PRML６章)

カーネル関数: 対称な半正定値関数 k(x, x')
- 特徴ベクトル φ(x) から作る: $k(\boldsymbol{x},\boldsymbol{x}')=\boldsymbol{\phi}(\boldsymbol{x})^T\boldsymbol{\phi}(\boldsymbol{x}')$
- カーネル関数から φ(x) を得ることも(双対性)
φ(x) で高次元の特徴空間への写像し、そこで線形な処理を行う
- 元の空間で非線形なモデルを考えているのと等価
カーネルトリック
- 特徴空間上で計算する代わりに、カーネル関数を使ってデータ点から直接計算
- おおむね [データ点の個数] < [特徴空間の次元(無限大とか)] なので

カーネル法だと何が嬉しい？

高い記述能力(自由度)
- 非線形ノンパラメトリック(モデルを有限個のパラメータで規定しない)
半正定値という弱い条件だけで、強い定理が成立することがわかっている
- 再生核とかリプレゼンター定理とか
いろんなレシピ＆組み合わせにより、カーネル関数を形式的に構成できる
- データや問題に合わせたチューニングをブラックボックスで行える

詳しくは「カーネル多変量解析―非線形データ解析の新しい展開 (シリーズ確率と情報の科学)」参照

カーネル主成分解析(kernel PCA)

PCA(Principal Component Analysis)の非線形への一般化
カーネル関数 k(x,x') だけで、主成分部分空間への非線形射影を記述する

$\boldsymbol{x}_n \in \mathbb{R}^D$ : 観測変数 (n = 1, ..., N)
$\phi : \mathbb{R}^D \rightarrow \mathbb{R}^M$ : M次元の特徴空間(feature space)への非線形変換

特徴空間において {φ(x_n)} に対して通常の PCA を行う代わりに、カーネル関数＋データ点だけで(特徴空間上で計算せずに解く)のが Kernel PCA のゴール。
- ★ M は特徴空間の次元(≠主成分空間の次元)。ここまでの章と違うんだから、記号変えてくれればいいのに。

まず $\sum_n \phi(\boldsymbol{x}_n) = \boldsymbol{0}$ と仮定する(一般の場合は後で)。
特徴空間におけるサンプル共分散行列 C

$\boldsymbol{C}=\frac{1}{N} \sum_{n=1}^N \phi(\boldsymbol{x}_n)\phi(\boldsymbol{x}_n)^T$

C の固有方程式は

$\boldsymbol{C}\boldsymbol{v}_i=\lambda_i\boldsymbol{v}_i$ (i=1, ..., M)

C を入れて

$\frac{1}{N} \sum_{n=1}^N \phi(\boldsymbol{x}_n)\{\phi(\boldsymbol{x}_n)^T\boldsymbol{v}_i\}=\lambda_i\boldsymbol{v}_i$

λ_i>0 を仮定すると、v_i は φ(x_n) の線形結合で書ける
- (★ λ_i=0 だと、そもそも主成分たりえないから？)

$\boldsymbol{v}_i = \sum_{n=1}^N a_{in}\phi(\boldsymbol{x}_n)$

v_i を固有方程式に代入し、左から φ(x_l)^T をかける

$\frac{1}{N} \sum_{n=1}^N \phi(\boldsymbol{x}_n)\phi(\boldsymbol{x}_n)^T \sum_{m=1}^N a_{im}\phi(\boldsymbol{x}_m)=\lambda_i \sum_{n=1}^N a_{in}\phi(\boldsymbol{x}_n)$

$k(\boldsymbol{x}_n,\boldsymbol{x}_m)=\phi(\boldsymbol{x}_n)^T\phi(\boldsymbol{x}_m)$ に置き換えると

$\frac{1}{N} \sum_{n=1}^N k(\boldsymbol{x}_l,\boldsymbol{x}_n) \sum_{m=1}^N a_{im}k(\boldsymbol{x}_n,\boldsymbol{x}_m)=\lambda_i \sum_{n=1}^N a_{in}k(\boldsymbol{x}_l,\boldsymbol{x}_n)$

K : (n, m) 成分を k(x_n, x_m) とするグラム行列
$\boldsymbol{a}_i = (a_{i,1}, ... , a_{i,N})^T$ とすると、

$\boldsymbol{K}^2 \boldsymbol{a}_i = \lambda_i N \boldsymbol{K} \boldsymbol{a}_i$

λ_i, a_i は次の固有方程式の解として得られる
- ゼロ固有値の分の差はあるが、主成分による射影には影響しない → (Ex.12.26)

$\boldsymbol{K} \boldsymbol{a}_i = \lambda_i N \boldsymbol{a}_i$

a_i は定数倍の自由度を持つが、特徴空間での規格化(正規化)を行う

$1=\boldsymbol{v}_i^T \boldsymbol{v}_i= \sum_{n=1}^N \sum_{m=1}^N a_{in}a_{im}\boldsymbol{\phi}(\boldsymbol{x}_n)^T \boldsymbol{\phi}(\boldsymbol{x}_n)=\boldsymbol{a}_i^T \boldsymbol{K}\boldsymbol{a}_i=\lambda_i N \boldsymbol{a}_i^T \boldsymbol{a}_i$

主成分への射影は、特徴空間から部分主成分空間への射影によって得られる。
第 i 成分を計算すると、下記の通りカーネル関数により表せる。

$y_i(\boldsymbol{x})=\boldsymbol{\phi}(\boldsymbol{x})^T \boldsymbol{v}_i= \sum_{n=1}^N a_{in}\boldsymbol{\phi}(\boldsymbol{x})^T \boldsymbol{\phi}(\boldsymbol{x}_n)= \sum_{n=1}^N a_{in}k(\boldsymbol{x},\boldsymbol{x}_n)$

Ex.12.26 (主成分への射影はゼロ固有値の影響を受けない)

グラム行列 K に対して、以下が成り立つことを示せ。

(1) $\boldsymbol{K} \boldsymbol{a}_i = \lambda_i N \boldsymbol{a}_i \Rightarrow \boldsymbol{K}^2 \boldsymbol{a}_i = \lambda_i N \boldsymbol{K} \boldsymbol{a}_i$
(2) ${}^\forall \lambda, {}^\forall\boldsymbol{a}, {}^\forall\boldsymbol{a}_0 \; \rm{with} \; \boldsymbol{K} \boldsymbol{a} = \lambda N \boldsymbol{a}, \; \boldsymbol{K} \boldsymbol{a}_0 = \boldsymbol{0}$
　　 $\Rightarrow\; \boldsymbol{K}^2 (\boldsymbol{a} + \boldsymbol{a}_0) = \lambda N \boldsymbol{K}(\boldsymbol{a} + \boldsymbol{a}_0)$
(3) (2) の $\boldsymbol{a}, \boldsymbol{a}_0$ に対し $\boldsymbol{a}' = \boldsymbol{a} + \boldsymbol{a}_0$ とおくと
　　 $\sum_{n=1}^N a_{n}k(\boldsymbol{x},\boldsymbol{x}_n) = \sum_{n=1}^N {a'}_{n}k(\boldsymbol{x},\boldsymbol{x}_n) \;(\rm{for} \; {}^\forall \boldsymbol{x})$

【証明】 (1), (2) は明らか。
(3) $\boldsymbol{v}_0 = \sum_{n=1}^N a_{0n} \boldsymbol{\phi}(\boldsymbol{x}_n)$ とおくと、
$\boldsymbol{v}_0^T \boldsymbol{v}_0 = \sum_{n=1}^N \sum_{m=1}^N a_{0n} a_{0m} \boldsymbol{\phi}(\boldsymbol{x}_n)^T \boldsymbol{\phi}(\boldsymbol{x}_m) = \boldsymbol{a}_0^T\boldsymbol{K}\boldsymbol{a}_0 = 0$ から $\boldsymbol{v}_0 = \boldsymbol{0}$ .
よって $\sum_{n=1}^N {a'}_{n}k(\boldsymbol{x},\boldsymbol{x}_n) - \sum_{n=1}^N a_{n}k(\boldsymbol{x},\boldsymbol{x}_n) = \sum_{n=1}^N a_{0n} \boldsymbol{\phi}(\boldsymbol{x})^T \boldsymbol{\phi}(\boldsymbol{x}_n) = \boldsymbol{\phi}(\boldsymbol{x})^T \boldsymbol{v}_0 = 0$ .
(つまり $\boldsymbol{K}=\boldsymbol{\Phi}\boldsymbol{\Phi}^T,\; \boldsymbol{K}\boldsymbol{a} = \boldsymbol{0} \;\Rightarrow\; \boldsymbol{\Phi}^T\boldsymbol{a} = \boldsymbol{0}$ ってこと)

特徴空間の次元と主成分の数

D : データ空間の次元
N : データ点の個数
M : 特徴空間の次元
- M<D, M<N とは限らない
- M は無限大の可能性もあり(e.g.ガウスカーネル)

主成分の数の上限＝特徴空間上でのサンプル共分散 C のランク
- $\boldsymbol{C}=\frac{1}{N} \sum_{n=1}^N \boldsymbol{\phi}(\boldsymbol{x}_n)\boldsymbol{\phi}(\boldsymbol{x}_n)^T$
- C のランクは、その作り方から、高々 N
- つまり主成分の数の上限 ≦ min{M, N}

特徴ベクトルの中心化

仮定 $\sum_n \boldsymbol{\phi}(\boldsymbol{x}_n) = \boldsymbol{0}$ がない場合。

中心化された特徴ベクトル $\tilde{\boldsymbol{\phi}}(\boldsymbol{x}_n) = \boldsymbol{\phi}(\boldsymbol{x}_n) - \frac{1}{N}\sum_{l=1}^N \boldsymbol{\phi}(\boldsymbol{x}_l)$ についてグラム行列を求めると

$\begin{eqnarray}&&\tilde{K}_{nm}=\tilde{\boldsymbol{\phi}}(\boldsymbol{x}_n)^T\tilde{\boldsymbol{\phi}}(\boldsymbol{x}_m)\\&=& k(\boldsymbol{x}_n,\boldsymbol{x}_m) -\frac{1}{N}\sum_{l=1}^N k(\boldsymbol{x}_l,\boldsymbol{x}_m)-\frac{1}{N}\sum_{l=1}^N k(\boldsymbol{x}_n,\boldsymbol{x}_l)+\frac{1}{N^2}\sum_{j=1}^N\sum_{l=1}^N k(\boldsymbol{x}_j,\boldsymbol{x}_l)\end{eqnarray}$
$\tilde{\boldsymbol{K}} = \boldsymbol{K}-\boldsymbol{1}_N \boldsymbol{K} - \boldsymbol{K}\boldsymbol{1}_N + \boldsymbol{1}_N \boldsymbol{K}\boldsymbol{1}_N$
where $\boldsymbol{1}_N$ は全ての要素が 1/N という値を取る N×N 行列

この $\tilde{\boldsymbol{K}}$ に対し、固有方程式 $\tilde{\boldsymbol{K}} \boldsymbol{a}_i = \lambda_i N \boldsymbol{a}_i$ を解けばよい。

(「カーネル多変量解析」の場合)

「カーネル多変量解析」でのカーネル PCA は、PRML とちょっと違う。
(以下、記号は PRML に合わせた)

とおき、の最大化を考える。ただし
- ラグランジュ未定乗数法を使う $L=-\rm{Var}[f(x)]+\lambda(w^Tw-1)$
よりを得る
- これにより $f(x)=\sum_n a_n k(x,x_n)$ と書き直せる(★PRMLと導出手順は違うが、結果は一緒)
次に Var[f(x)] を計算する。

φ(x_n) が中心化されている場合
- $\rm{Var}[f(x)]=\frac{1}{N}\sum_l\left(\sum_n a_n k(x_l,x_n)\right)^2=\frac{1}{N}\boldsymbol{a}^T K^2 \boldsymbol{a}$
- L に代入し $\frac{\partial L}{\partial a}=0$ より $Ka=\lambda a$ を得る(★右辺の N を省略)

φ(x_n) が中心化されていない場合
- $\mathbb{E}[f(x)]=\frac{1}{N}\sum_n f(x_n)=\frac{1}{N}a^TK\boldsymbol{1}$ where $\boldsymbol{1}$ は 1 を N 個並べたベクトル
- $\rm{Var}[f(x)]=\mathbb{E}[f(x)^2]-\mathbb{E}[f(x)]^2=\frac{1}{N}\boldsymbol{a}^T K^2 \boldsymbol{a}-\frac{1}{N^2}a^TK\boldsymbol{1}\boldsymbol{1}^TKa$
- より $(K-\boldsymbol{1}_NK)a=\lambda a$ を得る(★PRMLと異なる。この差は？←未検証……)

Ex.12.27 (普通のPCAはカーネルPCAの特殊例)

線形カーネル $k(\boldsymbol{x},\boldsymbol{x}')=\boldsymbol{x}^T \boldsymbol{x}'$ を選択すれば、通常の PCA を再現できることを示せ。

【証明】
x_n を行ベクトルとする N×D 行列 X を考えると、K=XX^T であり、
$\begin{eqnarray}&&\tilde{\boldsymbol{K}} = \boldsymbol{X}\boldsymbol{X}^T-\boldsymbol{1}_N \boldsymbol{X}\boldsymbol{X}^T - \boldsymbol{X}\boldsymbol{X}^T\boldsymbol{1}_N + \boldsymbol{1}_N \boldsymbol{X}\boldsymbol{X}^T\boldsymbol{1}_N\\&=& (\boldsymbol{X}-\boldsymbol{1}_N \boldsymbol{X})\boldsymbol{X}^T - (\boldsymbol{X} - \boldsymbol{1}_N \boldsymbol{X})\boldsymbol{X}^T\boldsymbol{1}_N\\&=& (\boldsymbol{X}-\boldsymbol{1}_N \boldsymbol{X})(\boldsymbol{X} - \boldsymbol{1}_N\boldsymbol{X})^T\end{eqnarray}$
ここで $\boldsymbol{X}-\boldsymbol{1}_N \boldsymbol{X}$ は $\boldsymbol{x}_n-\bar{\boldsymbol{x}}$ を行ベクトルとする行列。where $\bar{\boldsymbol{x}}=\frac{1}{N}\sum_n \boldsymbol{x}_n$ .
したがって $\tilde{\boldsymbol{K}} = \sum_{n=1}^N (\boldsymbol{x}_n-\bar{\boldsymbol{x}})(\boldsymbol{x}_n-\bar{\boldsymbol{x}})^T=NS$ .
where S は通常の PCA で用いるサンプル共分散行列。
このとき固有方程式 $\tilde{\boldsymbol{K}} \boldsymbol{a}_i = \lambda_i N \boldsymbol{a}_i$ は
$NS\boldsymbol{a}_i = \lambda_i N \boldsymbol{a}_i$ 、 $S\boldsymbol{a}_i = \lambda_i \boldsymbol{a}_i$ となり、PCA の固有方程式と一致する。