Hatena::ブログ(Diary)

Mi manca qualche giovedi`? このページをアンテナに追加 RSSフィード Twitter

2010-06-02 職人が一つ一つ手作りしたカーネルです。

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


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


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

  • 高い記述能力(自由度)
  • 半正定値という弱い条件だけで、強い定理が成立することがわかっている
    • 再生核とかリプレゼンター定理とか
  • いろんなレシピ&組み合わせにより、カーネル関数を形式的に構成できる

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

¥bf{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 は特徴空間の次元(≠主成分空間の次元)。ここまでの章と違うんだから、記号変えてくれればいいのに。

f:id:n_shuyo:20100603012903p:image


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

 ¥bf{C}=¥frac{1}{N}¥nosmash¥sum_{n=1}^N ¥phi(¥bf{x}_n)¥phi(¥bf{x}_n)^T

  • C の固有方程式は

 ¥bf{C}¥bf{v}_i=¥lambda_i¥bf{v}_i (i=1, ..., M)

  • C を入れて

 ¥frac{1}{N}¥nosmash¥sum_{n=1}^N ¥phi(¥bf{x}_n)¥{¥phi(¥bf{x}_n)^T¥bf{v}_i¥}=¥lambda_i¥bf{v}_i


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

 ¥bf{v}_i = ¥nosmash¥sum_{n=1}^N a_{in}¥phi(¥bf{x}_n)

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

 ¥frac{1}{N}¥nosmash¥sum_{n=1}^N ¥phi(¥bf{x}_n)¥phi(¥bf{x}_n)^T¥nosmash¥sum_{m=1}^N a_{im}¥phi(¥bf{x}_m)=¥lambda_i¥nosmash¥sum_{n=1}^N a_{in}¥phi(¥bf{x}_n)

  •  k(¥bf{x}_n,¥bf{x}_m)=¥phi(¥bf{x}_n)^T¥phi(¥bf{x}_m) に置き換えると

 ¥frac{1}{N}¥nosmash¥sum_{n=1}^N k(¥bf{x}_l,¥bf{x}_n) ¥nosmash¥sum_{m=1}^N a_{im}k(¥bf{x}_n,¥bf{x}_m)=¥lambda_i¥nosmash¥sum_{n=1}^N a_{in}k(¥bf{x}_l,¥bf{x}_n)


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

 ¥bf{K}^2 ¥bf{a}_i = ¥lambda_i N ¥bf{K} ¥bf{a}_i

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

 ¥bf{K} ¥bf{a}_i = ¥lambda_i N ¥bf{a}_i

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

1=¥bf{v}_i^T ¥bf{v}_i=¥nosmash¥sum_{n=1}^N ¥nosmash¥sum_{m=1}^N a_{in}a_{im}¥bf{¥phi}(¥bf{x}_n)^T ¥bf{¥phi}(¥bf{x}_n)=¥bf{a}_i^T ¥bf{K}¥bf{a}_i=¥lambda_i N ¥bf{a}_i^T ¥bf{a}_i


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

y_i(¥bf{x})=¥bf{¥phi}(¥bf{x})^T ¥bf{v}_i=¥nosmash¥sum_{n=1}^N a_{in}¥bf{¥phi}(¥bf{x})^T ¥bf{¥phi}(¥bf{x}_n)=¥nosmash¥sum_{n=1}^N a_{in}k(¥bf{x},¥bf{x}_n)


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

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

(1) ¥bf{K} ¥bf{a}_i = ¥lambda_i N ¥bf{a}_i ¥Rightarrow ¥bf{K}^2 ¥bf{a}_i = ¥lambda_i N ¥bf{K} ¥bf{a}_i

(2) {}^¥forall ¥lambda, {}^¥forall¥bf{a}, {}^¥forall¥bf{a}_0 ¥; ¥rm{with} ¥; ¥bf{K} ¥bf{a} = ¥lambda N ¥bf{a}, ¥; ¥bf{K} ¥bf{a}_0 = ¥bf{0}

  ¥Rightarrow¥; ¥bf{K}^2 (¥bf{a} + ¥bf{a}_0) = ¥lambda N ¥bf{K}(¥bf{a} + ¥bf{a}_0)

(3) (2) の  ¥bf{a}, ¥bf{a}_0 に対し ¥bf{a}’ = ¥bf{a} + ¥bf{a}_0 とおくと

  ¥nosmash¥sum_{n=1}^N a_{n}k(¥bf{x},¥bf{x}_n) = ¥nosmash¥sum_{n=1}^N {a’}_{n}k(¥bf{x},¥bf{x}_n) ¥;(¥rm{for} ¥; {}^¥forall ¥bf{x})


【証明】 (1), (2) は明らか。

(3) ¥bf{v}_0 = ¥nosmash¥sum_{n=1}^N a_{0n} ¥bf{¥phi}(¥bf{x}_n) とおくと、

¥bf{v}_0^T ¥bf{v}_0 = ¥nosmash¥sum_{n=1}^N ¥nosmash¥sum_{m=1}^N a_{0n} a_{0m} ¥bf{¥phi}(¥bf{x}_n)^T ¥bf{¥phi}(¥bf{x}_m) = ¥bf{a}_0^T¥bf{K}¥bf{a}_0 = 0 から ¥bf{v}_0 = ¥bf{0}.

よって ¥nosmash¥sum_{n=1}^N {a’}_{n}k(¥bf{x},¥bf{x}_n) - ¥nosmash¥sum_{n=1}^N a_{n}k(¥bf{x},¥bf{x}_n) = ¥nosmash¥sum_{n=1}^N a_{0n} ¥bf{¥phi}(¥bf{x})^T ¥bf{¥phi}(¥bf{x}_n) = ¥bf{¥phi}(¥bf{x})^T ¥bf{v}_0 = 0.

(つまり  ¥bf{K}=¥bf{¥Phi}¥bf{¥Phi}^T,¥; ¥bf{K}¥bf{a} = ¥bf{0} ¥;¥Rightarrow¥; ¥bf{¥Phi}^T¥bf{a} = ¥bf{0} ってこと)


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

  • D : データ空間の次元
  • N : データ点の個数
  • M : 特徴空間の次元
  • 主成分の数の上限=特徴空間上でのサンプル共分散 C のランク
    •  ¥bf{C}=¥frac{1}{N}¥nosmash¥sum_{n=1}^N ¥bf{¥phi}(¥bf{x}_n)¥bf{¥phi}(¥bf{x}_n)^T
    • C のランクは、その作り方から、高々 N
    • つまり主成分の数の上限 ≦ min{M, N}

特徴ベクトルの中心化

仮定 ¥sum_n ¥bf{¥phi}(¥bf{x}_n) = ¥bf{0} がない場合。

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

 ¥begin{eqnarray}&&¥tilde{K}_{nm}=¥tilde{¥bf{¥phi}}(¥bf{x}_n)^T¥tilde{¥bf{¥phi}}(¥bf{x}_m)¥¥&=& k(¥bf{x}_n,¥bf{x}_m) -¥frac{1}{N}¥sum_{l=1}^N k(¥bf{x}_l,¥bf{x}_m)-¥frac{1}{N}¥sum_{l=1}^N k(¥bf{x}_n,¥bf{x}_l)+¥frac{1}{N^2}¥sum_{j=1}^N¥sum_{l=1}^N k(¥bf{x}_j,¥bf{x}_l)¥end{eqnarray}

 ¥tilde{¥bf{K}} = ¥bf{K}-¥bf{1}_N ¥bf{K} - ¥bf{K}¥bf{1}_N + ¥bf{1}_N ¥bf{K}¥bf{1}_N

where ¥bf{1}_N は全ての要素が 1/N という値を取る N×N 行列

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


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

カーネル多変量解析」でのカーネル PCA は、PRML とちょっと違う。

(以下、記号は PRML に合わせた)

  • f(x)=w^T¥phi(x) とおき、¥rm{Var}¥[f(x)¥] の最大化を考える。ただしw~Tw=1
  • ¥frac{¥partial L}{¥partial w}=0 より ¥bf{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}¥bf{a}^T K^2 ¥bf{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¥bf{1} where ¥bf{1} は 1 を N 個並べたベクトル
    • ¥rm{Var}¥[f(x)¥]=¥mathbb{E}¥[f(x)^2¥]-¥mathbb{E}¥[f(x)¥]^2=¥frac{1}{N}¥bf{a}^T K^2 ¥bf{a}-¥frac{1}{N^2}a^TK¥bf{1}¥bf{1}^TKa
    • より (K-¥bf{1}_NK)a=¥lambda a を得る(★PRMLと異なる。この差は?←未検証……)

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

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

【証明】

x_n を行ベクトルとする N×D 行列 X を考えると、K=XX^T であり、

 ¥begin{eqnarray}&&¥tilde{¥bf{K}} = ¥bf{X}¥bf{X}^T-¥bf{1}_N ¥bf{X}¥bf{X}^T - ¥bf{X}¥bf{X}^T¥bf{1}_N + ¥bf{1}_N ¥bf{X}¥bf{X}^T¥bf{1}_N¥¥&=& (¥bf{X}-¥bf{1}_N ¥bf{X})¥bf{X}^T - (¥bf{X} - ¥bf{1}_N ¥bf{X})¥bf{X}^T¥bf{1}_N¥¥&=& (¥bf{X}-¥bf{1}_N ¥bf{X})(¥bf{X} - ¥bf{1}_N¥bf{X})^T¥end{eqnarray}

ここで ¥bf{X}-¥bf{1}_N ¥bf{X}¥bf{x}_n-¥bar{¥bf{x}} を行ベクトルとする行列。where ¥bar{¥bf{x}}=¥frac{1}{N}¥sum_n ¥bf{x}_n.

したがって  ¥tilde{¥bf{K}} = ¥sum_{n=1}^N (¥bf{x}_n-¥bar{¥bf{x}})(¥bf{x}_n-¥bar{¥bf{x}})^T=NS.

where S は通常の PCA で用いるサンプル共分散行列。

このとき固有方程式  ¥tilde{¥bf{K}} ¥bf{a}_i = ¥lambda_i N ¥bf{a}_i

NS¥bf{a}_i = ¥lambda_i N ¥bf{a}_iS¥bf{a}_i = ¥lambda_i ¥bf{a}_i となり、PCA の固有方程式と一致する。


カーネルPCAの例

f:id:n_shuyo:20100605002223p:image


カーネルPCAの欠点&注意