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

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

  • カーネル関数: 対称な半正定値関数 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 : 特徴空間の次元
  • 主成分の数の上限=特徴空間上でのサンプル共分散 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 に合わせた)

  • f(x)=w^T\phi(x) とおき、\rm{Var}[f(x)] の最大化を考える。ただしw~Tw=1
  • \frac{\partial L}{\partial w}=0 より \boldsymbol{w}=\sum_n a_n \phi(x_n) を得る
    • これにより 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}_iS\boldsymbol{a}_i = \lambda_i \boldsymbol{a}_i となり、PCA の固有方程式と一致する。

カーネルPCAの例


カーネルPCAの欠点&注意