【読書メモ】カーネル多変量解析

カーネル多変量解析 1 の読書メモ.データの解釈しやすさを保ちつつ非線形データに対応するカーネル法の基礎を知ることを目的に読み進めた.後半の理論的な部分に関しては自らの浅学な部分が災いし理解に至らず.今後の自分に期待.

以下に同書籍の気になる点(メモ)を列挙する.

§ 3:固有値問題を用いたカーネル多変量解析

低次元構造抽出の際に分散を考える理由(P.42)

データ圧縮のため低次元構造を抽出する際は,以下の2つの基準から最適化を行う.なおいずれの基準においても結果は同じになる.

  1. 低次元に射影した時に,分散が最大となるようにする.
  2. 低次元構造で元のデータを近似した際にその二乗誤差が最小となるようにする.

上記規範について,1. で分散を考える理由は,正規分布が持つ情報量は分散で測ることができるからである.現に1次元の正規分布の平均を $\mu$ ,分散を $\sigma^{2}$ とした場合に Shannon のエントロピーは以下で表される.

$$ \frac{1}{2} + \frac{1}{2} \ln(2\pi\sigma^2) = \frac{1}{2} \ln\sigma^2 + \mathrm{const.} $$ カーネル主成分分析とは(P.44)

高次元の特徴ベクトルに変換後主成分分析を実施,低次元の線形部分空間を求めること.図 3.2 の概念図が分かりやすい(放物線をカーネルで線形化した場合が掲載されている). 基本はグラム行列からなる固有値問題を解くことに帰着される.

§ 4:凸計画問題を用いたカーネル多変量解析

サポートベクトルマシン(Support Vector Machine: SVM)による2クラス分類(P.87 〜 P.88)

2クラスに分類するときは出力 $y$ を $y =\mathrm{sgn}\left[f\left(\boldsymbol{x}\right)\right]$ とする場合が一般的であるが,その際損失関数(評価関数)として二乗誤差

$$ r_{\mathrm{square}} = \left(y - f\left(\boldsymbol{x}\right)\right)^2 = \left(1 - yf\left(\boldsymbol{x}\right)\right)^2 \quad \because y = \pm1 $$

を用いると,$yf\left(\boldsymbol{x}\right)$ が 1 より大きい場合違いが顕著となる(i.e. 外れ値に敏感である).損失関数としては,正しい出力 $y = \pm 1$ と出力した学習値 $\mathrm{sgn}\left[f\left(\boldsymbol{x}\right)\right]$ との誤差である誤識別関数

$$ r_{\mathrm{mismatch}} = \left(\frac{y - \mathrm{sgn}\left[f\left(\boldsymbol{x}\right)\right]}{2}\right)^2 = \frac{1 - y\,\mathrm{sgn}\left[f\left(\boldsymbol{x}\right)\right]}{2} = \frac{1 - \mathrm{sgn}\left[yf\left(\boldsymbol{x}\right)\right]}{2} \quad \because y = \pm1, \mathrm{sgn}\left[f\left(\boldsymbol{x}\right)\right] = \pm1 $$

を利用することが自然である.しかしながら誤識別関数 $r_{\mathrm{mismatch}}$ は非凸関数であり最適化が難しい.そこで凸関数の中で $r_{\mathrm{mismatch}}$ に近い関数であるヒンジ関数

$$ r_{\mathrm{hinge}} = \max \left\{0, 1 - yf\left(\boldsymbol{x}\right) \right\} $$

を損失関数として用いることを考える.カーネル法を利用した識別において,ヒンジ関数 $r_{\mathrm{hinge}}$ を損失関数として用いるのがサポートベクトルマシン(SVM)である

サポートベクトルとは(P.93)

凸二次計画問題(Quadratic Programing: QP)において,KKT 条件上の相補性条件を満たす際にスラック変数が 0 にならないサンプル(観測値ベクトル)のこと.

(付録 A.2)Lagrange 関数と双対問題

最適化問題

$$ \min_{\boldsymbol{x}}f(\boldsymbol{x}) \quad \mathrm{s.t.} \,\, g_i(\boldsymbol{x}) \leq 0 \,\,(i = 1, \cdots, m) $$

における Lagrange 関数

$$ L(\boldsymbol{x}, \boldsymbol{\lambda}) = f(\boldsymbol{x}) + \sum_{i=1}^{m} \lambda_i g_i(\boldsymbol{x}) $$

において,

  • 主問題(primal problem):$L_{\mathrm{primal}} (\boldsymbol{x}):= \sup_{\boldsymbol{\lambda}\geq\boldsymbol{0}} L(\boldsymbol{x}, \boldsymbol{\lambda})$ を最小化する問題のこと.
    • $L_{\mathrm{primal}} (\boldsymbol{x})$ は $\boldsymbol{x}$ を固定して $\boldsymbol{\lambda}\geq\boldsymbol{0}$ に関する Lagrange 関数の最大化を行った関数であると考えられる.
  • 双対問題(dual problem):$L_{\mathrm{dual}} (\boldsymbol{\lambda}):= \inf_{\boldsymbol{x}} L(\boldsymbol{x}, \boldsymbol{\lambda})$ を最大化する問題のこと.
    • $L_{\mathrm{dual}} (\boldsymbol{\lambda})$ は $\boldsymbol{\lambda}$ を固定して $\boldsymbol{x}$ に関する Lagrange 関数の最小化を行った関数であると考えられる.
    • 主問題の凸性とは無関係に凹関数の最大化問題となっている.

以下は双対問題と主問題との関係の重要事項.

主問題の最適解 $\boldsymbol{x}^{\mathrm{opt}}$ は,双対問題の解 $\boldsymbol{\lambda}^{\mathrm{opt}}$ を KKT 条件に代入した条件を満たすものとして求められる.

§7:汎化と正則化の理論

不良設定問題とは(P.166)

$$ Af = F $$
  • $A$:作用素
  • $f$:真の構造(関数)
  • $F$ :(観測)結果

上記の関係式が成立するとき,

  • 不良設定問題:$F$ の近似解 $\hat{F}$ が真の $F$ に近づいても,$Af = \hat{F}$ の解 $\hat{f}$ が $Af = F$ の解に近づかない状況のこと.
  • vs. 良設定問題:$F$ の近似解 $\hat{F}$ が真の $F$ に近づいたとき,$Af = \hat{F}$ の解 $\hat{f}$ が $Af = F$ の解に近づく状況のこと.

経験損失(経験誤差)と期待損失(汎化誤差)(P.177)

$r(\boldsymbol{x} ; f)$ を損失関数(データ$\boldsymbol{x}$ を関数 $f$ で処理した時の値),$p(\boldsymbol{x})$ を$\boldsymbol{x}$ の確率分布であるとしたとき,本書の枠組みにおける多変量解析では,以下に示す期待損失(汎化誤差) $R(f)$ を最小化する $f$ を求めることが目標である.

$$ R(f) = \int r(\boldsymbol{x}; f) p(\boldsymbol{x}) \mathrm{d} \boldsymbol{x} $$

ただし,実際問題では $p(\boldsymbol{x})$ は未知である.そのため,期待損失の代わりに $p(\boldsymbol{x})$ から生成されたサンプル $\boldsymbol{x^{(i)}}(i = 1,\cdots, n)$ に対する損失 $\hat{R}_n (f)$(経験損失,経験誤差という)を最小化する $f$ を求める.

$$ \hat{R}_n (f) = \frac{1}{n} \sum_{i=1}^n r(\boldsymbol{x}^{(i)}; f) $$

期待損失 $R(f)$ の代わりに経験損失 $\hat{R}_n (f)$ を最小化するのは,以下が成立する(i.e. 不偏性がある)と仮定しているからである.

$$ \lim_{n \to \infty} \hat{R}_n (f) = R(f) $$
以上

  1. 赤穂 昭太郎, “カーネル多変量解析, ” 岩波書店,2008.