1. 开场白
在上一篇博客中，简要讨论了函数基础。我们从将函数视为无限向量开始，然后定义了函数的内积。类似于Rn\mathcal{R}^n空间，我们也可以为函数空间找到正交函数基。
这篇博客将进一步讨论核函数和再生核希尔伯特空间（RKHS）。核方法已被广泛应用于各种数据分析技术中。核方法的动机在于将Rn空间中的一个向量映射为特征空间中的另一个向量。例如，想象一下，如下图所示，有一些红点和一些蓝点，在Rn空间中它们不容易分开。然而，如果我们将它们映射到高维特征空间，我们可能能够轻松地将它们分开。本文不会提供严格的理论定义，而是对基本思想进行直观描述。
2. 特征分解
对于一个实对称矩阵 A\mathbf{A}，存在实数 λ\lambda 和向量 x\mathbf{x}，使得
Ax=λx\mathbf{A} \mathbf{x} = \lambda \mathbf{x}
则 λ 是 A 的特征值，x 是相应的特征向量。如果 A 有两个不同的特征值 λ1 和 λ2，λ1≠λ2，对应的特征向量分别为 x1 和 x2，
λ1x1Tx2=x1TATx2=x1TAx2=λ2x1Tx2\lambda_1 \mathbf{x}_1^T \mathbf{x}_2 = \mathbf{x}_1^T \mathbf{A}^T \mathbf{x}_2 = \mathbf{x}_1^T \mathbf{A} \mathbf{x}_2 = \lambda_2 \mathbf{x}_1^T \mathbf{x}_2
由于 $\lambda_1 \neq \lambda_2$，我们有 $\mathbf{x}_1^T \mathbf{x}_2 = 0$，即 $\mathbf{x}_1$ 和 $\mathbf{x}_2$ 是正交的。
对于 A∈Rn×n\mathbf{A} \in \mathcal{R}^{n \times n} ，我们可以找到 nn 个特征值以及 nn 个正交特征向量。因此，A\mathbf{A} 可以被分解为
A=QDQT\mathbf{A} = \mathbf{Q} \mathbf{D} \mathbf{Q}^T
其中 Q\mathbf{Q} 是正交矩阵（即，QQT=I\mathbf{Q} \mathbf{Q}^T = \mathbf{I} ），D=diag(λ1,λ2,⋯ ,λn)\mathbf{D} = \text{diag} (\lambda_1, \lambda_2, \cdots, \lambda_n) 。如果我们按列写出 Q\mathbf{Q}
Q=(q1,q2,⋯ ,qn)\mathbf{Q}=\left( \mathbf{q}_1, \mathbf{q}_2, \cdots, \mathbf{q}_n \right)
然后
\begin{array}{rl} \mathbf{A}=\mathbf{Q} \mathbf{D} \mathbf{Q}^T &= \left( \mathbf{q}_1, \mathbf{q}_2, \cdots, \mathbf{q}_n \right) \begin{pmatrix} \lambda_1\ &&& \ & \lambda_2\ && \ && \ddots\ & \ &&&\lambda_n \end{pmatrix} \begin{pmatrix} \mathbf{q}_1^T \ \mathbf{q}_2^T \ \vdots \ \mathbf{q}_n^T \end{pmatrix} \ &= \left( \lambda_1 \mathbf{q}_1, \lambda_2 \mathbf{q}_2, \cdots, \lambda_n \mathbf{q}_n \right) \begin{pmatrix} \mathbf{q}_1^T \ \mathbf{q}_2^T \ \vdots \ \mathbf{q}_n^T \end{pmatrix} \ &=\sum_{i=1}^n \lambda_i \mathbf{q}_i \mathbf{q}_i^T \end{array}
这里 {qi}i=1n{ {\mathbf{q}_i } }
_{i=1}^n 是 Rn\mathcal{R}^n 的一组正交基。
3. 核函数
一个函数 f(x) 可以被视为一个无限向量，对于具有两个独立变量的函数 K(x,y)，我们可以将其视为一个无限矩阵。其中，如果 K(x,y) ≠ K(y,x)
∫∫f(x)K(x,y)f(y)dxdy≥0\int \int f(\mathbf{x}) K(\mathbf{x},\mathbf{y}) f(\mathbf{y}) d\mathbf{x} d\mathbf{y} \geq 0
对于任何函数 ff，K(x,y)K(\mathbf{x},\mathbf{y}) 是对称且正定的，此时 K(x,y)K(\mathbf{x},\mathbf{y}) 是一个核函数。
类似于矩阵的特征值和特征向量，存在特征值 λ 和特征函数 ψ(x)，使得
∫K(x,y)ψ(x)dx=λψ(y)\int K(\mathbf{x},\mathbf{y}) \psi(\mathbf{x}) d\mathbf{x} = \lambda \psi(\mathbf{y})
对于不同的特征值 λ1\lambda_1 和 λ2\lambda_2，以及相应的特征函数 ψ1(x)\psi_1(\mathbf{x}) 和 ψ2(x)\psi_2(\mathbf{x})，很容易证明
∫λ1ψ1(x)ψ2(x)dx=∫∫K(y,x)ψ1(y)dyψ2(x)dx=∫∫K(x,y)ψ2(x)dxψ1(y)dy=∫λ2ψ2(y)ψ1(y)dy=∫λ2ψ2(x)ψ1(x)dx\begin{array}{rl} \int \lambda_1 \psi_1(\mathbf{x}) \psi_2(\mathbf{x}) d\mathbf{x} & = \int \int K(\mathbf{y},\mathbf{x}) \psi_1(\mathbf{y}) d\mathbf{y} \psi_2(\mathbf{x}) d\mathbf{x} \ & = \int \int K(\mathbf{x},\mathbf{y}) \psi_2(\mathbf{x}) d\mathbf{x} \psi_1(\mathbf{y}) d\mathbf{y} \ & = \int \lambda_2 \psi_2(\mathbf{y}) \psi_1(\mathbf{y}) d\mathbf{y} \ & = \int \lambda_2 \psi_2(\mathbf{x}) \psi_1(\mathbf{x}) d\mathbf{x} \end{array}
因此，
<ψ1,ψ2"> =∫ψ1(x)ψ2(x)dx =0 < \psi_1, \psi_2 > = \int \psi_1(\mathbf{x}) \psi_2(\mathbf{x}) d\mathbf{x} = 0
再次，特征函数是正交的。这里 ψ\psi 表示函数（无限向量）本身。
对于核函数，可能会找到无限的特征值 {λi}i=1∞{ {λ_i} }{i=1}^{∞} 以及无限的特征函数 {ψi}i=1∞{ {ψ_i} }{i=1}^{∞}。类似于矩阵情况，
K(\mathbf{x},\mathbf{y}) = \sum _{i=0}^{\infty} \lambda_i \psi_i (\mathbf{x}) \psi_i (\mathbf{y})
这是默瑟定理。在这里 <ψi,ψj> = 0 对于 i≠j。因此，{ψi}i=1∞ 构成了一个函数空间的正交基集合。
以下是一些常用的内核：
- 多项式核 K(x,y) = (γxTy+C)^d
- 高斯径向基核 K(x,y) = exp(-γ∥x-y∥2)
- 双曲正切核 K(x,y) = tanh(γxTy+C)
4. 再生核希尔伯特空间
将{λiψi}i=1∞{ {\sqrt{\lambda_i} \psi_i} }_{i=1}^{\infty} 视为一组正交基，并构建希尔伯特空间H\mathcal{H}。空间中的任何函数或向量都可以表示为基的线性组合。假设
f = \sum_{i=1}^{\infty} f_i \sqrt{\lambda_i} \psi_i
我们可以将ff表示为H中的无限向量\mathcal{H}：
f ext{=(f1,f2,...)HTf = (f_1, f_2, ...) ext{H}^T}
对于另一个函数 g extbackslash=(g1,g2,...)HTg = (g_1, g_2, ...)_\mathcal{H}^T ，我们有
<f,g>H=∑i=1∞figi< f,g >_\mathcal{H} = \sum_{i=1}^{\infty} f_i g_i
对于核函数 KK，这里我使用 K(x,y)K(\mathbf{x},\mathbf{y}) 表示在点 x,y\mathbf{x},\mathbf{y} 处对 KK 的评估，这是一个标量，使用 K(⋅,⋅)K(\cdot,\cdot) 表示函数（无限矩阵）本身，并使用 K(x,⋅)K(\mathbf{x},\cdot) 表示矩阵的第 x\mathbf{x} 行，即，我们将核函数的一个参数固定为 x\mathbf{x}，然后可以将其视为具有一个参数或无限向量的函数。然后
K(x,⋅) =∑i=0∞λiψi(x)ψiK(\mathbf{x},\cdot) = \sum_{i=0}^{\infty} \lambda_i \psi_i (\mathbf{x}) \psi_i
在空间 H\mathcal{H} 中，我们可以表示
K(x,⋅)=(λ1ψ1(x),λ2ψ2(x),⋯ )HTK(\mathbf{x},\cdot) = (\sqrt{\lambda_1} \psi_1 (\mathbf{x}), \sqrt{\lambda_2} \psi_2 (\mathbf{x}), \cdots )_\mathcal{H^T}
因此
<K(x,⋅),K(y,⋅)>H=∑i=0∞λiψi(x)ψi(y)=K(x,y)< K(\mathbf{x},\cdot), K(\mathbf{y},\cdot) >\mathcal{H} = \sum{i=0}^{\infty} \lambda_i \psi_i (\mathbf{x}) \psi_i(\mathbf{y}) = K(\mathbf{x},\mathbf{y})
这是 reproducing 属性，因此 H\mathcal{H} 被称为再生核 Hilbert 空间（RKHS）.
现在是时候回到本文开头的问题了：如何将一个点映射到特征空间中？如果我们定义一个映射
Φ(x)=K(x,⋅)=(λ1ψ1(x),λ2ψ2(x),⋯ )T\bold{\Phi} (\mathbf{x}) = K(\mathbf{x},\cdot) = (\sqrt{\lambda_1} \psi_1 (\mathbf{x}), \sqrt{\lambda_2} \psi_2 (\mathbf{x}), \cdots )^T
然后我们可以将点 x\mathbf{x} 映射到 H\mathcal{H}。这里 Φ\bold{\Phi} 不是一个函数，因为它指向特征空间 H\mathcal{H} 中的一个向量或函数。然后
<Φ(x),Φ(y)>H=<K(x,⋅),K(y,⋅)>H=K(x,y)< \bold{\Phi} (\mathbf{x}), \bold{\Phi} (\mathbf{y}) >\mathcal{H = < K(\mathbf{x},\cdot), K(\mathbf{y},\cdot) >\mathcal{H = K(\mathbf{x},\mathbf{y})
因此，我们实际上不需要知道映射是什么，特征空间在哪里，或者特征空间的基础是什么。对于对称正定函数 KK，必须至少存在一个映射 Φ\bold{\Phi} 和一个特征空间 H\mathcal{H}，使得
<Φ(x),Φ(y)> = K(x,y)< \bold{\Phi} (\mathbf{x}), \bold{\Phi} (\mathbf{y}) > = K(\mathbf{x},\mathbf{y})
所谓的核技巧。
5. 一个简单的例子
考虑核函数
K(x,y) = (x1, x2, x1x2)(y1y2y1y2) = x1y1+x2y2+x1x2y1y2K(\mathbf{x},\mathbf{y}) = \left( x_1, x_2, x_1 x_2 \right) \begin{pmatrix} y_1 \ y_2 \ y_1 y_2 \end{pmatrix} = x_1 y_1 + x_2 y_2 + x_1 x_2 y_1 y_2
其中 x=(x1,x2)T,y=(y1,y2)T。Let λ1=λ2=λ3=1，ψ1(x)=x1，ψ2(x)=x2，ψ3(x)=x1x2。我们可以定义映射为
(x1x2)⟶Φ(x1x2x1x2)\begin{pmatrix} x1 \ x2 \end{pmatrix} \overset{\bold{\Phi}}{\longrightarrow} \begin{pmatrix} x1 \ x2 \ x1 x2 \end{pmatrix}
然后
<Φ(x),Φ(y)>=（x1,x2,x1x2）（y1y2y1y2）=K(x,y)< \bold{\Phi} (\mathbf{x}), \bold{\Phi}(\mathbf{y}) > = \left( x_1, x_2, x_1 x_2 \right) \begin{pmatrix} y_1 \ y_2 \ y_1 y_2 \end{pmatrix} = K(\mathbf{x},\mathbf{y})
6. 支持向量机
支持向量机（SVM）是RKHS最广为人知的应用之一。假设我们有数据对 (xi,yi)i=1n{ (\mathbf{x}i, y_i) }{i=1}^n，其中 y_iy_i 要么是1，要么是-1，表示点 x_i\mathbf{x}_i 的类别。SVM假设一个超平面来最佳地分离这两个类别。
min_{\boldsymbol{\beta}, \beta_0} \frac{1}{2} \Vert \boldsymbol{\beta} \Vert^2 + C \sum_{i=1}^n \xi_i
subject to ξi≥0,yi(xiTβ+β0)≥1−ξi,∀i\text{subject to } \xi_i \geq 0, y_i (\mathbf{x}_i^T \boldsymbol{\beta} + \beta_0 ) \geq 1 - \xi_i, \forall i
有时两个类在Rn空间中无法轻松分离，因此我们可以将xi\mathbf{x}_i映射到一个高维特征空间，其中这两个类可能更容易分开。原始问题可以重新表述为
min_{\boldsymbol{\beta}, \beta_0} \frac{1}{2} \Vert \boldsymbol{\beta} \Vert^2 + C \sum_{i=1}^n \xi_i
subject to ξi≥0,yi(Φ(xi)Tβ+β0)≥1−ξi,∀i\text{subject to } \xi_i \geq 0, y_i (\bold{\Phi}(\mathbf{x}_i)^T \boldsymbol{\beta} + \beta_0 ) \geq 1 - \xi_i, \forall i
拉格朗日函数是
Lp=12∥β∥2+C∑i=1nξi−∑i=1nαi[yi(Φ(xi)Tβ+β0)−(1−ξi)]−∑i=1nμiξi
自从
∂Lp∂β=0\frac{\partial L_p}{\partial \boldsymbol{\beta}} = \mathbf{0}
我们得到
β=∑i=1nαiyiΦ(xi)\boldsymbol{\beta} = \sum_{i=1}^n \alpha_i y_i \bold{\Phi}(\mathbf{x}_i)
也就是说，β\boldsymbol{\beta}可以被写成xi\mathbf{x}_is的线性组合！我们可以替换β\boldsymbol{\beta}并得到新的优化问题。目标函数变为：
12∥∑i=1nαiyiΦ(xi)∥2+C∑i=1nξi=12<∑i=1nαiyiΦ(xi),∑j=1nαjyjΦ(xj)>+C∑i=1nξi=12∑i=1n∑j=1nαiαjyiyj<Φ(xi),Φ(xj)>+C∑i=1nξi=12∑i=1n∑j=1nαiαjyiyjK(xi,xj)+C∑i=1nξi \begin{array}{rl} &\frac{1}{2} \Vert \sum_{i=1}^n \alpha_i y_i \bold{\Phi} (\mathbf{x}_i) \Vert^2 + C \sum_{i=1}^n \xi_i \ =& \frac{1}{2} < \sum_{i=1}^n \alpha_i y_i \bold{\Phi} (\mathbf{x}_i), \sum_{j=1}^n \alpha_j y_j \bold{\Phi} (\mathbf{x}_j) > + C \sum_{i=1}^n \xi_i \ =& \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j < \bold{\Phi} (\mathbf{x}_i), \bold{\Phi} (\mathbf{x}_j) > + C \sum_{i=1}^n \xi_i \ = & \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j K(\mathbf{x}_i, \mathbf{x}_j) + C \sum_{i=1}^n \xi_i \end{array}
约束条件更改为:
yi[Φ(xi)T(∑j=1nαjyjΦ(xj))+β0]=yi[(∑j=1nαjyj<Φ(xi),Φ(xj)>)+β0]=yi[(∑j=1nαjyjK(xi,xj)+β0]≥1−ξi,∀i \begin{array}{rl} & y_i \left[\bold{\Phi}(\mathbf{x}_i)^T \left( \sum_{j=1}^n \alpha_j y_j \bold{\Phi}(\mathbf{x}_j) \right) + \beta_0 \right] \ =& y_i \left[ \left( \sum_{j=1}^n \alpha_j y_j < \bold{\Phi}(\mathbf{x}_i), \bold{\Phi}(\mathbf{x}_j) > \right) + \beta_0 \right] \ =& y_i \left[ \left( \sum_{j=1}^n \alpha_j y_j K(\mathbf{x}_i, \mathbf{x}_j) \right) + \beta_0 \right] \geq 1 - \xi_i, \forall i \end{array}
我们需要做的是确定一个核函数并求解α,β0,ξi\boldsymbol{\alpha}, \beta_0, \xi_i。我们不需要实际构造特征空间。对于具有未知类别的新数据x\mathbf{x}，我们可以通过
y^=sign[Φ(x)Tβ+β0]=sign[Φ(x)T(∑i=1nαiyiΦ(xi))+β0]=sign(∑i=1nαiyi<Φ(x),Φ(xi)>+β0)=sign(∑i=1nαiyiK(x,xi)+β0)\begin{array}{ccl} \hat{y} &=& \text{sign} \left[ \bold{\Phi} (\mathbf{x})^T \boldsymbol{\beta} + \beta_0 \right] \ &=& \text{sign} \left[ \bold{\Phi} (\mathbf{x})^T \left( \sum_{i=1}^n \alpha_i y_i \bold{\Phi}(\mathbf{x}i) \right) + \beta_0 \right] \ &=& \text{sign} \left( \sum{i=1}^n \alpha_i y_i < \bold{\Phi} (\mathbf{x}), \bold{\Phi}(\mathbf{x}i) > + \beta_0 \right) \ &=& \text{sign} \left( \sum{i=1}^n \alpha_i y_i K(\mathbf{x},\mathbf{x}_i) + \beta_0 \right) \end{array}
核方法极大地增强了支持向量机的判别能力。
7. 总结和参考资料
核方法在数据分析中被广泛应用。在这里，介绍了RKHS的基本属性。通过核技巧，我们可以轻松地将数据映射到特征空间并进行分析。这里有一个视频，演示了为什么我们可以在高维特征空间中轻松进行核SVM分类。
第5节中的示例来自
- Gretton A. (2015): 介绍RKHS和一些简单的核算法，来自伦敦大学学院的机器学习高级主题讲座。
其他参考资料包括
- Paulsen, V. I. (2009). 再生核希尔伯特空间理论导论. 讲义. * Daumé III, H. (2004). 从零到不超过十二页的再生核希尔伯特空间. * Friedman, J., Hastie, T., and Tibshirani, R. (2001). 统计学习的要素. Springer, Berlin: Springer 统计学系列.