$\begin{array}{ll}{\min \limits_{w, b}} & {\frac{1}{2}\|w\|^{2}} \tag{2}\\ {\text { s.t. }} & {y_{i}\left(w^T \phi(x_i)+b\right)-1 \geqslant 0, \quad i=1,2, \cdots, N}\end{array}$

w, b min s.t. \frac{1}{2} ∥ w ∥^{2} y_{i} (w^{T} ϕ (x_{i}) + b) - 1 ⩾ 0, i = 1, 2, \dots, N (2)

其对偶问题为：

\begin{matrix} (3) & \begin{array}{ll} max_{α} & a m p; \sum_{i = 1}^{N} α_{i} - \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{i} α_{j} y_{i} y_{j} ϕ (x_{i})^{T} ϕ (x_{j}) \\ s.t. & a m p; \sum_{i = 1}^{N} α_{i} y_{i} = 0 \\ a m p; α_{i} ⩾ 0, i = 1, 2, \dots, N \end{array} \end{matrix}

$\begin{array}{ll}{\max \limits_{\alpha}} & { \sum_{i=1}^N\alpha_i-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j\phi(x_i)^T\phi(x_j)} \tag{3}\\ {\text { s.t. }} & {\sum_{i=1}^N\alpha_iy_i=0}\\ & {\alpha_i\geqslant 0, \quad i=1,2,\cdots,N}\end{array}$

α max s.t. \sum_{i = 1}^{N} α_{i} - \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{i} α_{j} y_{i} y_{j} ϕ (x_{i})^{T} ϕ (x_{j}) \sum_{i = 1}^{N} α_{i} y_{i} = 0 α_{i} ⩾ 0, i = 1, 2, \dots, N (3)

1.1 核技巧

求解 (2) 涉及到计算 $\phi(x_i)^T\phi(x_j)$ ，这是样本 $x_i$ 与 $x_j$ 映射到特征空间之后的内积。由于特征空间维数可能很高，设置可能是无穷维，因此直接计算 $\phi(x_i)^T\phi(x_j)$ 通常是困难的。为了避开这个障碍，可以设想这样一个函数：

$k(x_i,x_j)= \phi(x_i)^T\phi(x_j)\tag{4}$

核技巧： $x_i$ 与 $x_j$ 在特征空间的内积等于它们在原始样本空间中通过函数 $k(\cdot,\cdot)$ 计算的结果，于是 (3)可以重写为：

\begin{array}{ll} max_{α} & a m p; \sum_{i = 1}^{N} α_{i} - \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{i} α_{j} y_{i} y_{j} k (\cdot, \cdot) \\ s.t. & a m p; \sum_{i = 1}^{N} α_{i} y_{i} = 0 \\ a m p; α_{i} ⩾ 0, i = 1, 2, \dots, N \end{array}

$\begin{array}{ll}{\max \limits_{\alpha}} & { \sum_{i=1}^N\alpha_i-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j k(\cdot,\cdot)}\\ {\text { s.t. }} & {\sum_{i=1}^N\alpha_iy_i=0}\\ & {\alpha_i\geqslant 0, \quad i=1,2,\cdots,N} \end{array}$ \tag{5}

α max s.t. \sum_{i = 1}^{N} α_{i} - \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{i} α_{j} y_{i} y_{j} k (\cdot, \cdot) \sum_{i = 1}^{N} α_{i} y_{i} = 0 α_{i} ⩾ 0, i = 1, 2, \dots, N (5)

求解后即可得到：

\begin{array}{ll} f (x) & a m p; = w^{T} ϕ (x) + b \\ a m p; = \sum_{i = 1}^{N} α_{i} y_{i} ϕ (x_{i})^{T} ϕ (x) + b \\ a m p; = \sum_{i = 1}^{N} α_{i} y_{i} k (x, x_{i}) + b \end{array}

$\begin{array}{ll} {f(x)} &= {w^T\phi(x)+b} \\ &= {\sum_{i=1}^N{\alpha_iy_i\phi(x_i)^T\phi(x)+b}} \\ &= {\sum_{i=1}^N\alpha_iy_ik(x,x_i)+b}\\ \end{array}$ \tag{6}

f (x) = w^{T} ϕ (x) + b = \sum_{i = 1}^{N} α_{i} y_{i} ϕ (x_{i})^{T} ϕ (x) + b = \sum_{i = 1}^{N} α_{i} y_{i} k (x, x_{i}) + b (6)

这里的函数 $k(\cdot,\cdot)$ 就是“核函数”（kernel function）。上式显示出模型最优解可以通过训练样本的核函数展开，这一展开式又称为支持向量展式（support vector expansion）。

1.2 核函数

定理（核函数）：令 $X$ 为输入空间， $k(\cdot,\cdot)$ 是定义在 $X\times X$ 上的对称函数，则 $k$ 是核函数当且仅当对于任意数据 $D=\{x_1,x_2,\cdots x_m \}$ ，“核矩阵”（kernel matrix） $K$ 总是半正定的：^[2]

$\mathbf{K}=\left[$

\begin{array}{ccccc} κ (x_{1}, x_{1}) & a m p; \dots & a m p; κ (x_{1}, x_{j}) & a m p; \dots & a m p; κ (x_{1}, x_{m}) \\ ⋮ & a m p; ⋱ & a m p; ⋮ & a m p; ⋱ & a m p; ⋮ \\ κ (x_{i}, x_{1}) & a m p; \dots & a m p; κ (x_{i}, x_{j}) & a m p; \dots & a m p; κ (x_{i}, x_{m}) \\ ⋮ & a m p; ⋱ & a m p; ⋮ & a m p; ⋱ & a m p; ⋮ \\ κ (x_{m}, x_{1}) & a m p; \dots & a m p; κ (x_{m}, x_{j}) & a m p; \dots & a m p; κ (x_{m}, x_{m}) \end{array}

$\begin{array}{ccccc}{\kappa\left(\boldsymbol{x}_{1}, \boldsymbol{x}_{1}\right)} & {\cdots} & {\kappa\left(\boldsymbol{x}_{1}, \boldsymbol{x}_{j}\right)} & {\cdots} & {\kappa\left(\boldsymbol{x}_{1}, \boldsymbol{x}_{m}\right)} \\ {\vdots} & {\ddots} & {\vdots} & {\ddots} & {\vdots} \\ {\kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{1}\right)} & {\cdots} & {\kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)} & {\cdots} & {\kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{m}\right)} \\ {\vdots} & {\ddots} & {\vdots} & {\ddots} & {\vdots} \\ {\kappa\left(\boldsymbol{x}_{m}, \boldsymbol{x}_{1}\right)} & {\cdots} & {\kappa\left(\boldsymbol{x}_{m}, \boldsymbol{x}_{j}\right)} & {\cdots} & {\kappa\left(\boldsymbol{x}_{m}, \boldsymbol{x}_{m}\right)}\end{array}$ \right] \tag{7}

K = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ κ (x_{1}, x_{1}) ⋮ κ (x_{i}, x_{1}) ⋮ κ (x_{m}, x_{1}) \dots ⋱ \dots ⋱ \dots κ (x_{1}, x_{j}) ⋮ κ (x_{i}, x_{j}) ⋮ κ (x_{m}, x_{j}) \dots ⋱ \dots ⋱ \dots κ (x_{1}, x_{m}) ⋮ κ (x_{i}, x_{m}) ⋮ κ (x_{m}, x_{m}) ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ (7)

这个定理表明，只要一个对称函数所对应的核矩阵半正定，它就能作为核函数使用。事实上，对于一个半正定核矩阵，总能找到一个与之对应的映射 $\phi$ 。换言之，任何一个核函数都隐式地定义了一个称为“再生核希尔伯特空间”（RKHS, Reproducing Kernel Hilbert Space）的特征空间。

1.2.1 核函数选择

通过前面讨论我们知道，我们希望样本在特征空间内线性可分，因此特征空间的好坏对支持向量机的性能直观重要。需要注意的是，在不知道特征映射的形式时，我们并不知道什么样的核函数时合适的，而核函数也仅是隐式地定义了这个特征空间。于是，“核函数选择”称为支持向量机的最大变数。若核函数选择不合适，则意味着将样本映射到了一个不合适的特征空间，很可能导致性能不佳。

表1 常用核函数

对文本数据通常采用线性核；情况不明时可先尝试高斯核（RBF 核）

此外，还可以通过函数组合得到，例如：

若 $k_1$ 和 $k_1$ 为核函数，则对于任意正数 $\gamma_1, \gamma_2$ ，其线性组合：

$\gamma_1 k_1 + \gamma_2 k_2 \tag{8}$

也是核函数；
1

若 $k_1$ 和 $k_1$ 为核函数，则核函数的直积：

$k_1 \otimes k_2(x,z)=k_1(x,z)k_2(x,z) \tag{9}$

也是核函数；
1

若 $k_1$ 为核函数，则对于任意函数 $g (x)$ ：

$k(x,z)=g(x)k_1(x,z)g(z) \tag{10}$

也是核函数。
1

1.2.2 RBF 函数

首先来看一个例子，假设我们要将一组直线上的数据进行分类，但由于它们是非线性的，因此需要利用核函数将数据变换为线性可分的数据。

图3 非线性数据

我们通过一条曲线将直线上的数据投射到一个平面上，可以看见，所有的正实例都被投射到了曲线的顶端，而所有的负实例都被投射到了曲线的低端，因此这时我们就可以利用线性可分支持向量机找出分类超平面。

图4 高斯核函数变换后的线性可分数据

那么这条曲线是怎么构造出来的呢，这里就要介绍一个函数：径向基函数（RBF Radial Basis Function）。

所谓径向基函数，就是某种沿径向对称的标量函数。通常定义为空间中任一点 $x$ 到某中心 $x_c$ 之间欧式距离的单调函数，可以记为 $k(x,x_c)$ ，其作用往往是局部的，即当 $x$ 原理 $x_c$ 时函数取值很小。

最常用的径向基函数是高斯径向基函数：

$k(x,x_c) = exp(-\frac{\|x-x_c\|^2}{2\sigma^2}) \tag{11}$

当我们使用高斯径向基函数作为核函数时，就称之为高斯核函数。

它的图像与高斯分布 $y=\frac{1}{\sigma \sqrt{2\pi}}e^{-\frac{(x-\mu)^2}{2\sigma^2}}$ 相似，在高斯分布中，其分布被参数 $\sigma$ 和 $\mu$ 唯一确定，当 $\sigma$ 越大时，图像越矮胖；当 $\sigma$ 越小时，图像越高瘦。