カーネル判別分析（Kernel Discriminant Analysis, KDA）は、線形判別分析（Linear Discriminant Analysis, LDA）を非線形に拡張した手法であり、再生核ヒルベルト空間（RKHS）においてクラス間分散を最大化しつつクラス内分散を最小化することで、非線形な識別構造を抽出する方法である。カーネルトリックにより、高次元特徴空間への写像を明示することなく計算が可能である。
ラベル付きデータ
\[\{(x_i, y_i)\}_{i=1}^n, \quad x_i \in \mathbb{R}^d,\; y_i \in \{1,\dots, C\}\]
を考える。各クラス $c$ に属するサンプル数を $n_c$ とする。
非線形写像
\[\phi : \mathbb{R}^d \to \mathcal{H}\]
により、特徴空間 $\mathcal{H}$ にデータを写像する。
全体平均およびクラス平均は
\[\mu = \frac{1}{n} \sum_{i=1}^n \phi(x_i), \quad\mu_c = \frac{1}{n_c} \sum_{i \in c} \phi(x_i)\]
で定義される。
クラス内分散作用素は
\[S_W = \sum_{c=1}^C \sum_{i \in c} (\phi(x_i) - \mu_c) \otimes (\phi(x_i) - \mu_c)\]
クラス間分散作用素は
\[S_B = \sum_{c=1}^C n_c (\mu_c - \mu) \otimes (\mu_c - \mu)\]
で定義される。
KDAは、次のレイリー商を最大化する問題として定式化される：
\[\max_{v \in \mathcal{H}} \frac{\langle v, S_B v \rangle}{\langle v, S_W v \rangle}\]
解はデータの張る部分空間に属するため
\[v = \sum_{i=1}^n \alpha_i \phi(x_i)\]
と表せる。
カーネル関数を
\[k(x_i, x_j) = \langle \phi(x_i), \phi(x_j) \rangle\]
とし、カーネル行列 $K \in \mathbb{R}^{n \times n}$ を
\[K_{ij} = k(x_i, x_j)\]
とする。
係数ベクトル $\alpha$ に関して、目的関数は
\[\max_{\alpha} \frac{\alpha^T K M K \alpha}{\alpha^T K N K \alpha}\]
と書ける。ここで、$M$ はクラス間分散を表す行列、$N$ はクラス内分散を表す行列である。
具体的には、$M$ は
\[M = \sum_{c=1}^C \frac{1}{n_c} \mathbf{e}_c \mathbf{e}_c^T - \frac{1}{n} \mathbf{1}\mathbf{1}^T\]
の形で与えられ、$N$ は
\[N = I - \sum_{c=1}^C \frac{1}{n_c} \mathbf{e}_c \mathbf{e}_c^T\]
で与えられる（$\mathbf{e}_c$ はクラス $c$ に属するサンプルに対応する指示ベクトル）。
最適化問題は次の一般化固有値問題に帰着する：
\[K M K \alpha = \lambda K N K \alpha\]
数値的安定性のため、通常は正則化を加えて
\[K M K \alpha = \lambda (K N K + \kappa I) \alpha\]
とする。
新しいデータ点 $x$ の判別軸への射影は
\[y = \langle v, \phi(x) \rangle= \sum_{i=1}^n \alpha_i k(x_i, x)\]
で与えられる。
線形カーネルを用いると、KDAは通常のLDAに一致する。したがってKDAはLDAの非線形拡張である。
KDAはRKHSにおける分散作用素
\[S_B, S_W\]
に基づく一般化固有値問題であり、本質的にはヒルベルト空間におけるレイリー商最大化問題である。これは有限次元LDAの完全な一般化である。
非ゼロ固有値の数は最大で $C-1$ であり、これはクラス間分散のランクに対応する。
カーネル判別分析は、RKHSにおいてクラス間分散とクラス内分散の比を最大化することで非線形な判別構造を抽出する手法である。カーネルトリックにより高次元空間でのLDAを効率的に実現し、分類問題における強力な非線形特徴抽出法として重要である。
Mathematics is the language with which God has written the universe.