Kernel Method.

核方法是指通过核技巧把样本输入空间的非线性问题转换为特征空间的线性问题，通过引入核函数不显式地定义特征空间和映射函数，而是将优化问题的解表示成核函数的线性组合。

对于一个线性模型$f(x)=w^Tx$(忽略了偏置项$b$)，根据表示定理(representer theorem)，在满足一定条件时，参数$w$的最优解可以表示为$N$个样本数据的线性组合$w^* = \sum_{i=1}^{N} {\alpha_ix_i}$，故模型的最优解表示为：

\[f^*(x)=\sum_{i=1}^{N} {\alpha_ix_i^Tx}\]

引入映射$\phi:\mathcal{X}→\mathcal{F}$将样本空间$\mathcal{X}$变换到高维的特征空间$\mathcal{F}$，从而将在样本空间中线性不可分的样本在特征空间线性可分(如果原始样本空间为有限维，则一定存在一个高维线性空间使得样本可分)，为模型增加非线性表示能力。则对应的模型最优解为：

\[f^*(x)=\sum_{i=1}^{N} {\alpha_i\phi(x_i)^T\phi(x)}\]

注意到直接计算特征变换$\phi(x)$以及特征变换的内积$\phi(x)^T\phi(x’)$是相当困难的，事实上该特征变换可能会把样本投影到无穷维度的特征空间。由于模型最优解中仅出现了特征变换的内积$\phi(x)^T\phi(x’)$的形式，因此引入核函数 $\kappa(x,x’) = \phi(x)^T\phi(x’)$，将计算特征变换的内积$\phi(x)^T\phi(x’)$转化为计算核函数的值$\kappa(x,x’)$。

本文首先介绍表示定理，其次介绍如何定义核函数，之后介绍一些常用的核函数，最后介绍一些引入核方法的机器学习算法。

1. 表示定理 Representer Theorem

在本文中，我们重点关注线性模型的表示定理。事实上，表示定理适用于任何模型$h$，只要该模型的优化问题可以表示成如下结构风险(正则项)与经验风险之和：

\[\mathop{\min}_{h \in \mathcal{H}} \Omega(\|h\|_{\mathcal{H}}) + \frac{1}{N}\sum_{i=1}^{N} {l(y_i),h(x_i))}\]

其中$\mathcal{H}$为核函数$\kappa$对应的再生核希尔伯特空间，$||h||_{\mathcal{H}}$表示$\mathcal{H}$空间中关于$h$的范数。要求$\Omega$是单调递增函数，$l$是非负损失函数。则上述优化问题的最优解可以表示为核函数的线性组合：

\[h^*(x)=\sum_{i=1}^{N} {\alpha_i\kappa(x_i,x)}\]

一种特殊形式下的证明：线性模型+$L_2$正则化

如果线性模型$f(x)=w^Tx$使用了$L_2$正则化，即优化目标函数为:

\[\mathop{\min}_w \frac{λ}{N}w^Tw + \frac{1}{N}\sum_{i=1}^{N} {l(y_i,w^Tx_i)}\]

则参数$w$的最优解可以表示为所有样本的线性组合：

\[w^* = \sum_{i=1}^{N} {\alpha_ix_i}\]

证明如下：

注意到最优解$w^*$与样本$x$具有相同的空间维度。假设最优解由两部分组成：\(w^* = w_{\|}+w_{⊥}\),

其中\(w_{\|}\)平行于样本数据所张成的空间$\text{span}(x_1,…,x_N)$；$w_{⊥}$垂直于样本数据所张成的空间；

则目标函数的第二项：

\[l(y_i,{w^*}^Tx_i) = l(y_i,(w_{||}+w_{⊥})^Tx_i) = l(y_i,w_{||}^Tx_i)\]

且目标函数的第一项：

\[{w^*}^Tw^* = (w_{||}+w_{⊥})^T(w_{||}+w_{⊥}) = w_{||}^Tw_{||}+2w_{||}^Tw_{⊥}+w_{⊥}^Tw_{⊥} \\ = w_{||}^Tw_{||}+w_{⊥}^Tw_{⊥} ≥ w_{||}^Tw_{||}\]

显然参数的一个可选解$w_{||}$比假设最优解$w^*$具有更小的目标函数，因此$w_{||}$是一个满足条件的更优解。故最优参数$w^*$平行于样本数据所张成的空间$\text{span}(x_1,…,x_N)$，即可被样本数据线性表示。

2. 核函数的定义

定义一

对于函数$\kappa:\mathcal{X} \times \mathcal{X}→\Bbb{R}$，如果存在映射$\phi:\mathcal{X} \times \Bbb{R}, \phi \in \mathcal{H}$，使得：

\[\kappa(x,x')= < \phi(x),\phi(x') >\]

则称$\kappa(x,x’)$为正定核函数。

其中$\mathcal{H}$是希尔伯特空间(Hilbert Space)，即完备的、可能是无限维的、被赋予内积的线性空间。

定义二

对于函数$\kappa:\mathcal{X} \times \mathcal{X}→\Bbb{R}$，如果满足下面两条性质：

  1. $\kappa(x,x’)$是对称函数，即$\kappa(x,x’)=\kappa(x’,x)$
  2. 对任意样本集\(x=\{x_1,x_2,...,x_N\}^T\)，其Gram矩阵(也称为核矩阵) $K=[\kappa(x_i,x_j)]_{N×N}$是半正定矩阵。

则称$\kappa(x,x’)$为正定核函数。

即一个对称函数所对应的核矩阵半正定，该函数就能作为核函数，所以称为正定核函数(positive definite kernel function)。

两种定义的等价性

上述两种正定核函数的定义是等价的。下面证明其必要性，即已知$\kappa(x,x’)= < \phi(x),\phi(x’) >$，求证$\kappa(x,x’)$是对称函数，且其Gram矩阵$是半正定矩阵。

\[\kappa(x,x')= < \phi(x),\phi(x') > = < \phi(x'),\phi(x) > = \kappa(x',x)\] \[\alpha^T K \alpha= [\alpha_1,\alpha_2,...,\alpha_N] [\kappa(x_i,x_j)]_{N×N} [\alpha_1,\alpha_2,...,\alpha_N]^T \\ = \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i\alpha_j\kappa(x_i,x_j) = \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i\alpha_j< \phi(x_i),\phi(x_j) > \\ = \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i\alpha_j\phi(x_i)^T\phi(x_j) = \sum_{i=1}^{N}\alpha_i\phi(x_i)^T \sum_{j=1}^{N} \alpha_j\phi(x_j) \\ = (\sum_{i=1}^{N}\alpha_i\phi(x_i))^T(\sum_{j=1}^{N} \alpha_j\phi(x_j)) = <\sum_{i=1}^{N}\alpha_i\phi(x_i),\sum_{j=1}^{N} \alpha_j\phi(x_j)> \\ = || \sum_{i=1}^{N}\alpha_i\phi(x_i) ||^2 > 0\]

3. 一些常用的核函数

对于一个核函数，总能找到一个对应的映射$\phi$，即任何核函数都隐式地定义了一个称为再生核希尔伯特空间(reproducing kernel Hilbert space)的特征空间。 通常希望样本在特征空间内是线性可分的。选择核函数相当于选择了特征空间，因此选择合适的核函数是核方法中的重要问题。下面介绍几个常用的核函数：

(1) 线性核（linear kernel）

线性核函数定义为：

\[\kappa(x,x') = x^Tx'\]

其优缺点如下：

(2) 二项式核（binomial kernel）

对于输入样本\(x = (x_1,x_2,...,x_d)^T\)，定义二阶多项式变换得到的特征向量：

\[z = φ(x) = (1,x_1,...,x_d,x_1^2,x_1x_2,...,x_d^2)^T\]

由核函数的定义：

\[\kappa(x,x') = φ(x)^Tφ(x') = 1 + \sum_{i=1}^{d} {x_i{x'}_i} + \sum_{i=1}^{d} {\sum_{j=1}^{d} {x_i{x'}_ix_j{x'}_j}} \\ = 1 + x^Tx' + (x^Tx')^2\]

对特征变换进行一些修改，可以得到对应的核函数：

上面的这些变化对应的特征空间是相同的，但内积是不同的，最终得到的模型也是不同的。

(3) 多项式核（polynomial kernel）

扩展二项式核得到多项式核：

\[\kappa(x,x') = (ζ+γx^Tx')^q, \quad ζ≥0,γ>0\]

其优缺点如下：

(4) 高斯核（Gaussian kernel）

高斯核又叫径向基函数(radial basis function, rbf)，是一种无限维度的特征变换，高斯核函数为：

\[\kappa(x,x') = \text{exp}(-γ||x-x'||^2)\]

其中超参数$γ>0$控制高斯函数的方差，$γ$取值越大，径向基函数的径向越小，模型越容易过拟合：

当超参数$γ$趋于无穷大时，高斯核趋近于：

\[\kappa(x,x') = \begin{cases} 0, & x≠x' \\ 1, & x=x' \end{cases}\]

高斯核的优缺点如下：

下面由核函数分析高斯核所对应的特征变换$φ(x)$，为简化过程假设$γ=1$，其中用到了指数函数的Taylor展开：

\[\kappa(x,x') = \text{exp}(-||x-x'||^2) = \text{exp}(-x^2)\text{exp}(-{x'}^2)\text{exp}(2xx') \\ = \text{exp}(-x^2)\text{exp}(-{x'}^2) \sum_{n=0}^{∞} {\frac{(2xx')^n}{n!}} \\ = \sum_{n=0}^{∞} {\text{exp}(-x^2)\text{exp}(-{x'}^2) \sqrt{\frac{2^n}{n!}} \sqrt{\frac{2^n}{n!}} x^n{x'}^n} \\ = \sum_{n=0}^{∞} (\text{exp}(-x^2) \sqrt{\frac{2^n}{n!}} x^n)(\text{exp}(-{x'}^2) \sqrt{\frac{2^n}{n!}} {x'}^n) \\ = φ(x)^Tφ(x')\]

可以得到特征变换$φ(x)$：

\[z = φ(x) = \text{exp}(-x^2)(1,\sqrt{\frac{2^1}{1!}} x^1,\sqrt{\frac{2^2}{2!}} x^2,...,\sqrt{\frac{2^n}{n!}} x^n,...)^T\]

(5) 拉普拉斯核（Laplacian kernel）

拉普拉斯核函数为：

\[\kappa(x,x') = \text{exp}(-\frac{||x-x'||}{\sigma}), \quad \sigma>0\]

(6) Sigmoid核

Sigmoid核函数为：

\[\kappa(x,x') = \text{tanh}(\beta x^T x' + \theta), \quad \beta>0,\theta<0\]

(7) 核函数的线性组合

\[\gamma_1\kappa_1+\gamma_2\kappa_2\] \[\kappa_1 \otimes \kappa_2(x,x') = \kappa_1(x,x')\kappa_2(x,x')\] \[\kappa(x,x') = g(x)\kappa_1(x,x')g(x')\]

4. 引入核方法的机器学习算法

一些常用的引入核方法的机器学习算法介绍如下：

核岭回归

\[L(w) = \sum_{i=1}^{N} {(w^Tx_i-y_i)^2} + λw^2 = (Xw-y)^T(Xw-y)+ λw^Tw\] \[w = (X^TX+λI)^{-1}Xy, \quad y=\sum_{i=1}^{N} {w^Tx_i}\] \[L(α) = \sum_{i=1}^{N} {(\sum_{n=1}^{N} {α_nK(x_n,x_n)}-y^{(i)})^2} + λ \sum_{i=1}^{N} {\sum_{j=1}^{N} {α_iα_jK(x_i,x_j)}} = (y-Kα)^T(y-Kα) + λα^TKα\] \[α = (K+λI)^{-1}y, \quad y = \sum_{i=1}^{N} {α_iφ(x_i)^Tφ(x)} = \sum_{i=1}^{N} {α_iK(x_i,x)}\]

支持向量回归

\[\mathop{\min}_{α} \frac{1}{2}\sum_{n=1}^{N} {\sum_{m=1}^{N} {(α_n^+-α_n^-)(α_m^+-α_m^-){φ(x^{(n)})}^Tφ(x^{(m)})}} + \sum_{n=1}^{N} {((ε-y^{(n)})α_n^++(ε+y^{(n)})α_n^-)} \\ \text{s.t. } \sum_{n=1}^{N} {(α_n^+-α_n^-)}=0 \\ C ≥ α_n^- ≥ 0,C ≥ α_n^+ ≥ 0\] \[y=w^Tx=\sum_{n=1}^{N} {(α_n^+-α_n^-)(x^{(n)})^Tx}\] \[\mathop{\min}_{α} \frac{1}{2}\sum_{n=1}^{N} \sum_{m=1}^{N} {(α_n^+-α_n^-)(α_m^+-α_m^-){K(x^{(n)},x^{(m)})}} + \sum_{n=1}^{N} {((ε-y^{(n)})α_n^++(ε+y^{(n)})α_n^-)} \\ \text{s.t. } \sum_{n=1}^{N} {(α_n^+-α_n^-)}=0 \\ C ≥ α_n^- ≥ 0,C ≥ α_n^+ ≥ 0\] \[y=w^Tx=\sum_{n=1}^{N} {(α_n^+-α_n^-)K(x^{(n)},x)}\]

核逻辑回归

\[L(w) = \sum_{i=1}^{N} {-y^{(i)}ln(σ(w^Tx^{(i)})) - (1-y^{(i)})ln(1-σ(w^Tx^{(i)}))} + \frac{λ}{N}w^Tw\] \[L(β) = \sum_{i=1}^{N} {-y^{(i)}ln(σ(\sum_{n=1}^{N} {β_nK(x^{(n)},x^{(i)})})) - (1-y^{(i)})ln(1-σ(\sum_{n=1}^{N} {β_nK(x^{(n)},x^{(i)})}))} \\ + \frac{λ}{N}\sum_{i=1}^{N} {\sum_{j=1}^{N} {β_iβ_jK(x^{(i)},x^{(j)})}}\]

核支持向量机

\[\mathop{\max}_{α} -\frac{1}{2}\sum_{i=1}^{N} {\sum_{j=1}^{N} {α_iα_jy_iy_j{x_i}^Tx_j}} + \sum_{i=1}^{N} {α_i} \\ \text{s.t. } α_i≥0,i=1,...,N \\ \quad \quad \sum_{i=1}^{N} {α_iy_i} = 0\] \[y = \text{sign}(w^Tx+b)\\ = \text{sign}(\sum_{i=1}^{N} {α_iy_i{x_i}^Tx} + y^{(s)} - \sum_{i=1}^{N} {α_iy_i{x_i}^Tx_s})\] \[\mathop{\max}_{α} -\frac{1}{2}\sum_{i=1}^{N} {\sum_{j=1}^{N} {α_iα_jy_iy_jK(x_i,x_j)}} + \sum_{i=1}^{N} {α_i} \\ \text{s.t. } α_i≥0,i=1,...,N \\ \quad \quad \sum_{i=1}^{N} {α_iy_i} = 0\] \[y = \text{sign}(w^Tφ(x)+b)\\ = \text{sign}(\sum_{i=1}^{N} {α_iy_iK(x_i,x)} + y_s - \sum_{i=1}^{N} {α_iy_iK(x_i,x_s)})\]

核线性判别分析

\[J = \frac{w^T(\mu_0-\mu_1)(\mu_0-\mu_1)^Tw}{w^T(\Sigma_0+\Sigma_1)w} = \frac{w^TS_bw}{w^TS_ww}\] \[w = S_w^{-1}(\mu_0-\mu_1)\] \[J = \frac{w^T(\mu_0^{\phi}-\mu_1^{\phi})(\mu_0^{\phi}-\mu_1^{\phi})^Tw}{w^T(\sum_{c=0,1}^{} \sum_{x \in X_c}^{}(\phi(x)-\mu_c^{\phi})(\phi(x)-\mu_c^{\phi})^T)w}= \frac{w^TS_b^{\phi}w}{w^TS_w^{\phi}w}\]

核主成分分析

\[xx^Tw_j = λ_jw_j\] \[y_j = w_j^Tx\] \[K\alpha^j = λ_j\alpha^j\] \[y_j = w_j^T\phi(x)=\sum_{i=1}^{N}\alpha_i^j\phi(x_i)^T\phi(x) = \sum_{i=1}^{N}\alpha_i^jK(x_i,x)\]