核方法

令H为核函数\kappa 对应的再生核希尔伯特空间，\|h\|_{H}

表示H空间中的h函数，对于任意单调递增函数\Omega:[0, \infty] x \mapsto R 和任意非负损失函数l: R^{m} x \mapsto[0 . \infty] ，优化问题

\underset{h \in H}{\arg \min }=\Omega\left(\|h\|_{H}\right)+l\left(h\left(x_{1}\right), h\left(x_{2}\right), \ldots, h\left(x_{m}\right)\right)

表示定理对损失函数没有限制，对正则化项\Omega 仅要求单调递增，甚至不要求\Omega 是凸函数，意味着对于一般的损失函数和正则化项，优化问题的最优解h^{*}(x) 都可表示为核函数\kappa\left(x, x_{1}\right) 的线性组合；这显示出核函数的巨大威力。人们发展出一系列基于核函数的学习方法，统称为“核方法”(kernel method)。最常见的，是通过“核化”(即引入核函数)来将线性学习器拓展为非线性学习器。下面我们以线性判别分析为例来演示如何通过核化来对其进行非线性拓展，从而得到“核线性判别分析”(Kernelized Linear Discriminant Analysis，简称KLDA)。

我们假设可通过某种映射\phi: \chi x \mapsto F 将样本映射到一个特征空间F，然后在F中执行线性判别分析，以求得h(x)=w^{T} \phi(x)

KLDA的学习目标是：

\max _{w} J(w)=\frac{w^{T} S_{b}^{\phi} w}{w^{T} S_{w}^{\phi} w}

其中S_{b}^{\phi} 和S_{w}^{\phi} 分别为训练样本在特征空间F中的类间散度矩阵的类内散度矩阵。令X_i 表示第i \in\{0,1\}类样本的集合，其样本数为m_i ；总样本数m=m_{0}+m_{1} 第i类样本在特征空间F中的均值为\mu_{i}^{\phi}=\frac{1}{m_{i}} \sum_{x \in X_{i}} \phi(x) 两个散度矩阵分别为S_{b}^{\phi}=\left(\mu_{1}^{\phi}-\mu_{0}^{\phi}\right)\left(\mu_{1}^{\phi}-\mu_{0}^{\phi}\right)^{T}

通常我们难以知道映射\phi 的具体形式，因此使用核函数\kappa\left(x, x_{i}\right)=\phi\left(x_{i}\right)^{T} \phi(x) 来隐式地表达这个映射和特征空间F。把J(w) 作为(6.57)中的损失函数l，再令\Omega \equiv 0 ，由表示定理，函数h(x)可写为h(x)=\sum_{i=1}^{m} \alpha_{i} \kappa\left(x, x_{i}\right)

于是由式(6.59)可得w=\sum_{i=1}^{m} \alpha_{i} \phi\left(x_{i}\right)

令K \in R^{m \times m} 为核函数K 所对应的核矩阵，(K)_{i j}=\kappa\left(x_{i}, x_{j}\right)，令(K)_{i j}=\kappa\left(x_{i}, x_{j}\right) 为第i类样本的指示向量，即1_{i} 为第j和分量为1当且仅当x_{j} \in X_{i} 否则1_i 的第j个分量为0.再令\hat{\mu}_{0}=\frac{1}{m_{0}} K 1_{0} ,M=\left(\hat{\mu}_{0}-\hat{\mu}_{1}\right)\left(\hat{\mu}_{0}-\hat{\mu}_{1}\right)^{T} ,N=K K^{T}-\sum_{i=0}^{1} m_{i} \hat{\mu}_{i} \hat{\mu}_{i}^{T}

于是，上式等价为\max _{\alpha} J(\alpha)=\frac{\alpha^{T} M \alpha}{\alpha^{T} N \alpha}

显然，使用线性判别分析来求解方法即可得到\alpha ，进而可以得到投影函数h(x)。