时间戳

首页 > 技术文章 > 机器学习：支持向量机

机器学习：支持向量机

funmore233 2020-12-07 22:39 原文

目录

支持向量机

支持向量机 (support vector machines, SVM) 是一种二类分类模型, 它的基本模型是定义在特征空间上的间隔最大的线性分类器, 间隔最大使它有别于感知机, 支持向量机还包括核技巧, 这使它成为实质上的非线性分类器. 它的目标是寻找一个超平面对样本进行分割, 分割的原则是间隔最大化, 最终转化为一个凸二次规划 (convex quadratic programming) 问题来求解. 由简至繁的模型包括:

  • 当训练样本线性可分时, 通过硬间隔最大化 (hard margin maximization) 学习一个线性可分支持向量机 (linear support vector machine in linearly separable case).
  • 当训练样本近似线性可分时, 通过软间隔最大化 (soft margin maximization) 学习一个线性支持向量机 (linear support vector machine).
  • 当训练样本线性不可分时, 通过核技巧 (kernel trick) 和软间隔最大化, 学习一个非线性支持向量机 (non-linear support vector machine).

线性可分支持向量机

给定线性可分训练数据集, 通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为

\[\hat{\mathbf{\omega}}^T\mathbf{x} + \hat{b} = 0 \]

以及相应的分类决策函数

\[f(\mathbf{x}) = \text{sign}(\hat{\mathbf{\omega}}^T\mathbf{x} + \hat{b}) \]

称为线性可分支持向量机.

函数间隔和几何间隔

一般来说, 一个点距离超平面的远近可以表示分类预测的确信程度. 在超平面 \(\mathbf{\omega}^T\mathbf{x} + b = 0\) 确定的情况下, \(|\mathbf{\omega}^T\mathbf{x} + b|\) 能够相对的表示点 \(\mathbf{x}\) 距离超平面的远近, 而 \(\mathbf{\omega}^T\mathbf{x} + b\) 的符号与 \(y\) 的符号是否一致可以表示分类是否正确, 因此可以用量 \(y(\mathbf{\omega}^T\mathbf{x} + b)\) 来表示分类的正确性及准确性. 对于给定的训练数据集 \(T = \{ (\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \cdots, (\mathbf{x}_N, y_N) \}\) 和超平面 \((\mathbf{\omega}, b)\), 可以定义超平面 \((\mathbf{\omega}, b)\) 关于样本点 \((\mathbf{x}_i, y_i)\) 的函数间隔 (functional margin)为

\[\hat{\gamma}_i = y_i(\mathbf{\omega}^T\mathbf{x}_i + b) \]

定义超平面 \((\mathbf{\omega}, b)\) 关于训练数据集 \(T\) 的函数间隔为超平面 \((\mathbf{\omega}, b)\) 关于 \(T\) 中所有样本点 \((\mathbf{x}_i, y_i)\) 的函数间隔之最小值

\[\hat{\gamma} = \min_{i = 1,\cdots, N} \hat{\gamma}_i \]

函数间隔可以表示分类预测的正确性及准确性, 但同一个分离超平面的参数可表示为 \(\{(k\mathbf{\omega}, kb)|k \neq0 \}\) 形式, 当成比例的改变 \(\mathbf{\omega}\) 和 \(b\) 时, 例如变为 \(2\mathbf{\omega}\) 和 \(2b\), 超平面并没有改变, 但函数间隔缺成为原来的 \(2\) 倍. 此时可以对分类超平面的法向量 \(\mathbf{\omega}\) 加以规范化约束 \(||\mathbf{\omega}||=1\) 使得间隔是确定的. 这时函数间隔成为几何间隔 (geometric margin).

样本空间中任意一点 \(\mathbf{x}\) 到到超平面 \(\mathbf{\omega}^T\mathbf{x} + b = 0\) 的几何间隔可以表示为

\[\gamma_i = \frac{1}{||\mathbf{\omega}||} |\mathbf{\omega}^T\mathbf{x}_i + b| \]

下图给出了二维情况下 \(\mathbf{\omega}^T\mathbf{x} > 0\) 且 \(b>0\) 的几何间隔计算示例, \(\frac{\mathbf{\omega}}{||\mathbf{\omega}||}\) 为单位法向量. 具体来说, 几何间隔就是点 \(\mathbf{x}\) 到超平面 \(\mathbf{\omega}^T\mathbf{x} + b = 0\) 的距离, 也就是点 \(\mathbf{x}\) 与超平面上任一点形成的向量在法向量上的投影的正值.

svm_geo_margin

对于给定的训练数据集 \(T = \{ (\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \cdots, (\mathbf{x}_N, y_N) \}\) 和超平面 \((\mathbf{\omega}, b)\), 可以定义超平面 \((\mathbf{\omega}, b)\) 关于样本点 \((\mathbf{x}_i, y_i)\) 的几何间隔为:

\[\gamma_i = y_i \left( \frac{\mathbf{\omega}}{||\mathbf{\omega}||} \cdot \mathbf{x}_i + \frac{b}{||\mathbf{\omega}||} \right) \]

定义超平面 \((\mathbf{\omega}, b)\) 关于训练数据集 \(T\) 的几何间隔为超平面 \((\mathbf{\omega}, b)\) 关于 \(T\) 中所有样本点 \((\mathbf{x}_i, y_i)\) 的几何间隔之最小值

\[\gamma = \min_{i = 1,\cdots, N} \gamma_i \]

从函数间隔与几何间隔的定义可以得到函数间隔与几何间隔之间的关系为

\[\gamma_i = \frac{\hat{\gamma_i}}{||\mathbf{\omega}||}, \ \gamma = \frac{\hat{\gamma}}{||\mathbf{\omega}||} \]

间隔最大化

支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面. 对于线性可分的训练数据集而言, 线性可分分离超平面有无穷多个 (等价于感知机), 但几何间隔最大的分离超平面是唯一的, 这里的间隔最大化又称为硬间隔最大化. 间隔最大化的直观解释是以充分大的确信度对训练数据集进行分类, 也就是不仅将正负实例点分开, 而且对最难分的实例点 (离超平面最近的实例点) 也有足够大的确信度将它们分开, 提高对未知实例点的分类预测能力. 几何间隔最大的分离超平面可以表示为下面的约束最优化问题:

\[\begin{equation} \begin{aligned} & \max_{\mathbf{\omega}, b}\ \ \gamma\\ & \text{subject to}\ \ y_i \left( \frac{\mathbf{\omega}}{||\mathbf{\omega}||} \cdot \mathbf{x}_i + \frac{b}{||\mathbf{\omega}||} \right) \geq \gamma, \ i = 1,2,\cdots,N \end{aligned} \end{equation} \]

考虑几何间隔与函数间隔之间的关系, 上式也可以改写为

\[\begin{equation} \begin{aligned} & \max_{\mathbf{\omega}, b}\ \ \frac{\hat{\gamma}}{||\mathbf{\omega}||}\\ & \text{subject to}\ y_i(\mathbf{\omega}^T\mathbf{x}_i + b) \geq \hat{\gamma}, \ i = 1,2,\cdots,N \end{aligned} \end{equation} \]

函数间隔的取值并不影响最优化问题的解, 因为当系数 \(\mathbf{\omega}\) 和 \(b\) 成比例的改变时, 函数间隔也会相应的改变, 而这一系列改变对上面的约束最优化问题没有影响. 这样可以取 \(\hat{\gamma} = 1\), 并且注意到最大化 \(\frac{1}{||\mathbf{\omega}||}\) 与最小化 \(\frac{1}{2}||\mathbf{\omega}||^2\) 等价, 于是得到下面的线性可分支持向量机学习的最优化问题:

\[\begin{equation} \begin{aligned} & \min_{\mathbf{\omega}, b}\ \ \frac{1}{2}||\mathbf{\omega}||^2\\ & \text{subject to}\ y_i(\mathbf{\omega}^T\mathbf{x}_i + b) - 1 \geq 0, \ i = 1,2,\cdots,N \end{aligned} \end{equation} \]

这是一个凸二次规划问题, 其解可以容易求出, 进而得到最大间隔分离超平面 \(\mathbf{\omega}^* \cdot\mathbf{x} + b^* = 0\) 以及分类决策函数 \(f(\mathbf{x} = \text{sign}(\mathbf{\omega}^* \cdot\mathbf{x} + b^*)\). 可以证明线性可分训练数据集的最大间隔分离超平面是存在且唯一的.

下面将线性可分支持向量机学习算法 (最大间隔法, maximum margin method) 总结如下:

输入: 线性可分训练数据集 \(T = \{ (\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \cdots, (\mathbf{x}_N, y_N) \}\), 其中 \(\mathbf{x}_i \in \mathcal{X} = \mathbb{R}^n\), \(y_i \in \mathcal{Y} = \{+1, -1\}\), \(i=1,2,\cdots,N\).

输出: 最大间隔分离超平面和分类决策函数.

  1. 构造并求解约束最优化问题:

    \[\begin{equation} \begin{aligned} & \min_{\mathbf{\omega}, b}\ \ \frac{1}{2}||\mathbf{\omega}||^2\\ & \text{subject to}\ y_i(\mathbf{\omega}^T\mathbf{x}_i + b) - 1 \geq 0, \ i = 1,2,\cdots,N \end{aligned} \end{equation} \]

    求得最优解 \(\mathbf{\omega}^*\), \(b^*\).

  2. 由此得到最大间隔分离超平面 \(\mathbf{\omega}^* \cdot\mathbf{x} + b^* = 0\) 以及分类决策函数 \(f(\mathbf{x} = \text{sign}(\mathbf{\omega}^* \cdot\mathbf{x} + b^*)\).

在线性可分情况下, 训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量 (support vector), 支持向量是使约束条件等号成立的点, 即

\[y_i(\mathbf{\omega}^T\mathbf{x}_i + b) - 1 = 0 \]

对 \(y_i=+1\) 的正例点, 支持向量在超平面 \(\mathbf{\omega}^T\mathbf{x} + b = 1\) 上, 对 \(y_i=-1\) 的负例点, 支持向量在超平面 \(\mathbf{\omega}^T\mathbf{x} + b = -1\) 上. 注意到两个超平面平行并且没有实例点落在它们之间, 在它们之间形成一条长带, 长带的宽度称为间隔 (margin), 间隔依赖于分离超平面的法向量 \(\mathbf{\omega}\), 等于 \(\frac{2}{||\mathbf{\omega}||}\), 而这两个超平面称为间隔边界.

svm_linear_separable_margin
支持向量与间隔

在决定分离超平面时只有支持向量起作用, 而其他实例点并不起作用, 正是由于支持向量在确定分离超平面中起着决定性的作用, 所以将这种分类模型称为支持向量机.

拉格朗日对偶性

在约束最优化问题中, 常利用拉格朗日对偶性 (Lagrange duality) 将原始问题转换为对偶问题, 通过求解对偶问题而得到原始问题的解. 假设 \(f(x)\), \(c_i(x)\), \(h_i(x)\) 是定义在 \(\mathbb{R}^n\) 上的连续可微函数, 考虑如下最优化问题

\[\begin{equation} \begin{aligned} \min_{x \in \mathbb{R}^n}\ \ & f(x)\\ \text{subject to}\ \ & c_i(x) \leq 0, \ i = 1,2,\cdots,k\\ & h_j(x) = 0, \ j = 1,2,\cdots,l\\ \end{aligned} \end{equation} \label{primal} \]

称此约束最优化问题为原始最优化问题或原始问题.

由此可以引入广义拉格朗日函数 (generalized Lagrange function)

\[L(x, \alpha, \beta) = f(x) + \sum^k_{i=1}\alpha_ic_i(x) + \sum^l_{j=1}\beta_j h_j(x) \]

其中 \(\alpha_i\), \(\beta_j\) 是拉格朗日乘子, \(\alpha_i \geq 0\). 对于如下函数 (下标 \(P\) 表示原始问题)

\[\theta_P(x) = \max_{\alpha,\beta;\alpha_i \geq 0} L(x, \alpha, \beta) \]

假设给定某个 \(x\), 如果 \(x\) 违反原始问题的约束条件, 即 \(c_i(x)>0\) 或者 \(h_j(x) \neq 0\), 那么有

\[\theta_P(x) = \max_{\alpha,\beta;\alpha_i \geq 0} \left[f(x) + \sum^k_{i=1}\alpha_ic_i(x) + \sum^l_{j=1}\beta_j h_j(x)\right] = +\infty \]

若 \(x\) 满足约束条件, 那么 \(\theta_P(x) = f(x)\). 所以下面的极小化问题

\[\min_x \theta_P(x) = \min_x \max_{\alpha,\beta;\alpha_i \geq 0} L(x, \alpha, \beta) \]

与原始约束优化问题等价 (约束条件下的极小化问题). 问题 \(\min_x \max_{\alpha,\beta;\alpha_i \geq 0} L(x, \alpha, \beta)\) 称为广义拉格朗日函数的极小极大问题. 定义原始问题的最优值为

\[p^* = \min_x \theta_P(x) \]

下面定义

\[\theta_D(\alpha, \beta) = \max_{\alpha,\beta;\alpha_i \geq 0} \min_x L(x, \alpha, \beta) \]

为广义拉格朗日函数的极大极小问题. 也可以表示为约束最优化问题:

\[\begin{equation} \begin{aligned} & \max_{\alpha,\beta}\theta_D(\alpha, \beta) = \max_{\alpha,\beta} \min_x \ \ L(x, \alpha, \beta)\\ & \text{subject to}\ \ \alpha_i \geq 0, \ i = 1,2,\cdots,k \end{aligned} \end{equation} \label{dual} \]

定义对偶问题的最优值为

\[d^* = \max_{\alpha,\beta}\theta_D(\alpha, \beta） \]

定理 1: 若原始问题和对偶问题都有最优值, 则

\[d^* = \max_{\alpha,\beta;\alpha_i \geq 0} \min_x L(x, \alpha, \beta) \leq \min_x \max_{\alpha,\beta;\alpha_i \geq 0} L(x, \alpha, \beta) = p^* \]

定理 2: 对原始问题 \(\eqref{primal}\) 和对偶问题 \(\eqref{dual}\), 假设函数 \(f(x)\) 和 \(c_i(x)\) 是凸函数, \(h_j(x)\) 是仿射函数, 并且不等式约束 \(c_i(x)\) 是严格可行的, 即存在 \(x\) 对所有 \(i\) 有 \(c_i(x)<0\), 则存在 \(x^*\), \(\alpha^*\), \(\beta^*\), 使得 \(x^*\) 是原始问题的解, \(\alpha^*\), \(\beta^*\) 是对偶问题的解, 并且

\[p^* = d^* = L(x^*,\alpha^*,\beta^*) \]

定理 3: 对原始问题 \(\eqref{primal}\) 和对偶问题 \(\eqref{dual}\), 假设函数 \(f(x)\) 和 \(c_i(x)\) 是凸函数, \(h_j(x)\) 是仿射函数, 并且不等式约束 \(c_i(x)\) 是严格可行的, 则 \(x^*\) 和 \(\alpha^*\), \(\beta^*\) 分别是原始问题和对偶问题的解的充分必要条件是 \(x^*\), \(\alpha^*\), \(\beta^*\) 满足下面的 Karush-Kuhn-Tucker (KKT) 条件:

\[\nabla_x L(x^*,\alpha^*,\beta^*) = 0 \]

\[\alpha^*_ic_i(x^*)=0, \ i=1,2,\cdots,k \]

\[c_i(x^*) \leq 0, \ i=1,2,\cdots,k \]

\[\alpha^* \geq 0, \ i=1,2,\cdots,k \]

\[h_j(x^*) = 0, \ j=1,2,\cdots,l \]

学习的对偶算法

为了求解线性可分支持向量机的最优化问题, 将它作为原始最优化问题, 应用拉格朗日对偶性, 通过求解对偶问题 (dual problem) 得到原始问题 (primal problem) 的最优解, 这就是线性可分支持向量机的对偶算法 (dual algorithm). 这样做的优点, 一是对偶问题往往更容易求解, 而是可以自然引入核函数推广到非线性问题.

对每一个不等式约束引入拉格朗日乘子 (Lagrange multiplier) \(\alpha_i \geq 0\), \(i=1,2,\cdots,N\), 定义拉格朗日函数为

\[L(\mathbf{\omega}, b, \alpha) = \frac{1}{2}||\mathbf{\omega}||^2 + \sum^N_{i=1}\alpha_i \left(1 - y_i(\mathbf{\omega}^T\mathbf{x}_i + b)\right) \]

此时原始约束最优化问题可以等价地转化为拉格朗日函数的极小极大问题:

\[\min_{\mathbf{\omega},b} \max_{\alpha} L(\mathbf{\omega}, b, \alpha) \]

根据拉格朗日对偶性, 原始问题的对偶问题是极大极小问题:

\[\max_{\alpha} \min_{\mathbf{\omega},b} L(\mathbf{\omega}, b, \alpha) \]

原始问题满足定理 2 的条件, 因此存在 \(\mathbf{\omega}^*\), \(b^*\), \(\alpha^*\) 使得 \(\mathbf{\omega}^*\), \(b^*\) 是原始问题的解, \(\alpha^*\) 是对偶问题的解. 求出对偶问题的解也就等价于求出原始问题的解, 为了得到对偶问题的解, 需要先求 \(L(\mathbf{\omega}, b, \alpha)\) 对 \(\mathbf{\omega}\), \(b\) 的极小, 再求对 \(\alpha\) 的极大. 最终得到对偶最优化问题:

\[\begin{equation} \begin{aligned} \min_{\alpha}\ & \frac{1}{2}\sum^N_{i=1}\sum^N_{j=1}\alpha_i\alpha_jy_iy_j(\mathbf{x}_i \cdot \mathbf{x}_j) - \sum^N_{i=1} \alpha_i\\ \text{subject to}\ & \sum^N_{i=1} \alpha_i y_i = 0\\ & \alpha_i \geq 0, \ i = 1,2,\cdots,N \end{aligned} \end{equation} \]

对线性可分训练数据集, 可以利用 KKT 条件由 \(\alpha^*\) 求出原始最优化问题的解 \(\mathbf{\omega}^*\), \(b^*\), 即设 \(\alpha^* = (\alpha^*_1, \alpha^*_2,\cdots,\alpha^*_N)^T\) 是对偶最优化问题的解, 则存在下标 \(j\), 使得 \(\alpha^*_j>0\), 并且有:

\[\mathbf{\omega}^* = \sum^N_{i=1} \alpha^*_i y_ix_i \]

\[b^* = y_i - \sum^N_{i=1} \alpha^*_i y_j (\mathbf{x}_i \cdot \mathbf{x}_j) \]

由上式可知, \(\mathbf{\omega}^*\) 和 \(b^*\) 只依赖于训练数据集中对应于 \(\alpha^*_i>0\) 的样本点 \((\mathbf{x}_i, y_i)\), 其他样本点对 \(\mathbf{\omega}^*\) 和 \(b^*\) 没有影响. 将训练数据集中对应于 \(\alpha^*_i>0\) 的实例点 \(\mathbf{x}_i \in \mathbb{R}^n\) 称为支持向量, 支持向量一定在间隔边界上, 由 KKT 条件也可以得到

\[y_i(\mathbf{\omega}^T\mathbf{x}_i + b) - 1 = 0 \]

下面将线性可分支持向量机对偶学习算法总结如下:

输入: 线性可分训练数据集 \(T = \{ (\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \cdots, (\mathbf{x}_N, y_N) \}\), 其中 \(\mathbf{x}_i \in \mathcal{X} = \mathbb{R}^n\), \(y_i \in \mathcal{Y} = \{+1, -1\}\), \(i=1,2,\cdots,N\).

输出: 最大间隔分离超平面和分类决策函数.

  1. 构造并求解约束最优化问题:

    \[\begin{equation} \begin{aligned} \min_{\alpha}\ & \frac{1}{2}\sum^N_{i=1}\sum^N_{j=1}\alpha_i\alpha_jy_iy_j(\mathbf{x}_i \cdot \mathbf{x}_j) - \sum^N_{i=1} \alpha_i\\ \text{subject to}\ & \sum^N_{i=1} \alpha_i y_i = 0\\ & \alpha_i \geq 0, \ i = 1,2,\cdots,N \end{aligned} \end{equation} \]

    求得最优解 \(\alpha^* = (\alpha^*_1, \alpha^*_2,\cdots,\alpha^*_N)^T\).

  2. 计算

    \[\mathbf{\omega}^* = \sum^N_{i=1} \alpha^*_i y_ix_i \]

    并选择 \(\alpha^*\) 的一个正分量 \(\alpha^*_j>0\), 计算

    \[b^* = y_i - \sum^N_{i=1} \alpha^*_i y_j (\mathbf{x}_i \cdot \mathbf{x}_j) \]

  3. 由此得到最大间隔分离超平面 \(\mathbf{\omega}^* \cdot\mathbf{x} + b^* = 0\) 以及分类决策函数 \(f(\mathbf{x} = \text{sign}(\mathbf{\omega}^* \cdot\mathbf{x} + b^*)\).

线性不可分支持向量机

原始问题与对偶问题

对于线性不可分训练数据集, 线性可分问题中的支持向量机学习方法是不适用的, 因为它不满足函数间隔大于等于 \(1\) 的约束条件, 此时可以对每个样本点 \((\mathbf{x}_i, y_i)\) 引入一个松弛变量 \(\xi_i \geq 0\), 使函数间隔加上松弛变量大于等于 \(1\). 线性不可分的线性支持向量机的学习问题变成如下凸二次规划问题 (原始问题):

\[\begin{equation} \begin{aligned} \min_{\mathbf{\omega}, b, \xi}\ & \frac{1}{2}||\mathbf{\omega}||^2 + C\sum^N_{i=1} \xi_i\\ \text{subject to}\ & y_i(\mathbf{\omega}^T\mathbf{x}_i + b) \geq 1 - \xi_i\\ & \xi_i \geq 0, \ i = 1,2,\cdots,N \end{aligned} \end{equation} \]

目标函数中对每一个 \(\xi_i\) 支付一个代价, 这里 \(C>0\) 称为惩罚参数, \(C\) 值大时对误分类的惩罚增大, \(C\) 值小时对误分类的惩罚减小. 最小化目标函数使间隔 \(\frac{1}{2}||\mathbf{\omega}||^2\) 尽量小, 同时使误分类点的个数尽量少, \(C\) 是调节两者的系数.

同样可以得到原始问题的对偶问题:

\[\begin{equation} \begin{aligned} \min_{\alpha}\ & \frac{1}{2}\sum^N_{i=1}\sum^N_{j=1}\alpha_i\alpha_jy_iy_j(\mathbf{x}_i \cdot \mathbf{x}_j) - \sum^N_{i=1} \alpha_i\\ \text{subject to}\ & \sum^N_{i=1} \alpha_i y_i = 0\\ & 0 \leq \alpha_i \leq C, \ i = 1,2,\cdots,N \end{aligned} \end{equation} \]

下面将线性支持向量机学习算法 (对偶形式) 总结如下:

输入: 线性可分训练数据集 \(T = \{ (\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \cdots, (\mathbf{x}_N, y_N) \}\), 其中 \(\mathbf{x}_i \in \mathcal{X} = \mathbb{R}^n\), \(y_i \in \mathcal{Y} = \{+1, -1\}\), \(i=1,2,\cdots,N\).

输出: 最大间隔分离超平面和分类决策函数.

  1. 选择惩罚参数 \(C>0\), 构造并求解约束最优化问题:

    \[\begin{equation} \begin{aligned} \min_{\alpha}\ & \frac{1}{2}\sum^N_{i=1}\sum^N_{j=1}\alpha_i\alpha_jy_iy_j(\mathbf{x}_i \cdot \mathbf{x}_j) - \sum^N_{i=1} \alpha_i\\ \text{subject to}\ & \sum^N_{i=1} \alpha_i y_i = 0\\ & 0 \leq \alpha_i \leq C, \ i = 1,2,\cdots,N \end{aligned} \end{equation} \]

    求得最优解 \(\alpha^* = (\alpha^*_1, \alpha^*_2,\cdots,\alpha^*_N)^T\).

  2. 计算

    \[\mathbf{\omega}^* = \sum^N_{i=1} \alpha^*_i y_ix_i \]

    并选择 \(\alpha^*\) 的一个分量 \(\alpha^*_j\) 适合条件 \(0< \alpha_j^* < C\), 计算

    \[b^* = y_i - \sum^N_{i=1} \alpha^*_i y_j (\mathbf{x}_i \cdot \mathbf{x}_j) \]

  3. 由此得到最大间隔分离超平面 \(\mathbf{\omega}^* \cdot\mathbf{x} + b^* = 0\) 以及分类决策函数 \(f(\mathbf{x} = \text{sign}(\mathbf{\omega}^* \cdot\mathbf{x} + b^*)\).

支持向量

在线性不可分的情况下, 将对偶问题的解 \(\alpha^* = (\alpha^*_1, \alpha^*_2,\cdots,\alpha^*_N)^T\) 中对应于 \(\alpha^*_i>0\) 的实例点 \(\mathbf{x}_i \in \mathbb{R}^n\) 称为支持向量 (软间隔的支持向量). 如下图给出了正例点 (用 o 表示) 和负例点 (用 x 表示) 的支持向量, 分离超平面为实线, 间隔边界为虚线. 软间隔的支持向量 \(\mathbf{x}_i\) 或者在间隔边界上, 或者在间隔边界与分离超平面之间, 或者在分离超平面误分一侧.

svm_soft_margin

合页损失函数

线性支持向量机学习还有另外一种解释, 就是最小化以下目标函数:

\[\sum^N_{i=1} \left[ 1 - y_i(\mathbf{\omega}^T\mathbf{x}_i + b) \right]_+ + \lambda ||\mathbf{\omega}||^2 \]

目标函数的第 1 项

\[L(y(\mathbf{\omega}^T\mathbf{x} + b)) = \left[ 1 - y(\mathbf{\omega}^T\mathbf{x} + b) \right]_+ \]

称为合页损失函数 (hinge loss function). 也就是说当样本点被正确分类且函数间隔 (确信度) \(y_i(\mathbf{\omega}^T\mathbf{x}_i + b)>1\) 时, 损失函数为 \(0\), 否则损失函数为 \(1 - y(\mathbf{\omega}^T\mathbf{x} + b)\). 目标函数的第 2 项是系数为 \(\lambda\) 的 \(\mathbf{\omega}\) 的 \(L_2\) 范数, 是正则化项.

可以证明线性支持向量机原始最优化问题:

\[\begin{equation} \begin{aligned} \min_{\mathbf{\omega}, b, \xi}\ & \frac{1}{2}||\mathbf{\omega}||^2 + C\sum^N_{i=1} \xi_i\\ \text{subject to}\ & y_i(\mathbf{\omega}^T\mathbf{x}_i + b) \geq 1 - \xi_i\\ & \xi_i \geq 0, \ i = 1,2,\cdots,N \end{aligned} \end{equation} \]

等价于最优化问题:

\[\min_{\mathbf{\omega}, b} \sum^N_{i=1} \left[ 1 - y_i(\mathbf{\omega}^T\mathbf{x}_i + b) \right]_+ + \lambda ||\mathbf{\omega}||^2 \]

这时可以看到 SVM 也可以写成结构风险最小化 (structural risk minimization) 的一般形式:

\[J(f) = \frac{1}{N}\sum^N_{i=1}L(y_i,f(x_i)) + \Omega(f) \]

这里 SVM 的损失函数为合页损失函数 \(L(y_i, f(x_i)) = [1 - y_i f(x_i)]_+\), 其中\(f(x) = \mathbf{\omega}^T\mathbf{x} + b\), 输出 \(y_i \in \{+1, -1\}\), 正则项为 \(\Omega = \lambda ||\mathbf{\omega}||^2\). 类似的二分类学习算法 Logistic 回归也可以表示为上面形式, 不同的是 Logistic 回归的损失函数为交叉熵损失函数 \(L(y_i,f(x_i)) = \log(1 + \exp(-y_if(x_i)))\).

svm_error_compare

上图给出了不同损失函数的示意图, 其中 0/1 损失函数可以认为是二类分类问题真正的损失函数, 而其余损失函数是 0/1 损失函数的上界. 由于 0/1 损失函数不是连续可导的, 直接优化由其构成的目标函数比较困难, 可以认为 SVM 或者 Logistic 回归是优化由 0/1 损失函数的上界构成的目标函数. 这样的上界函数又称为代理损失函数 (surrogate loss function).

支持向量回归

下面来考虑回归问题, 给定训练数据集 \(T = \{ (\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \cdots, (\mathbf{x}_N, y_N) \}\), 其中 \(y_i \in \mathbb{R}\), \(i=1,2,\cdots,N\). 希望学习到一个模型 \(f(\mathbf{x}) = \mathbf{\omega}^T\mathbf{x} + b\) 使得 \(f(\mathbf{x})\) 与 \(y\) 尽可能接近. 对样本 \((\mathbf{x}_i, y_i)\), 传统回归模型通常直接基于模型输出 \(f(\mathbf{x})\) 与真实输出 \(y\) 之间的差别来计算损失, 当且仅当 \(f(\mathbf{x})\) 与 \(y\) 完全相同时损失才为 \(0\). 支持向量回归 (support vector regression, SVR) 假设能容忍 \(f(\mathbf{x})\) 与 \(y\) 之间最多有 \(\varepsilon\) 的偏差, 即当 \(f(\mathbf{x})\) 与 \(y\) 之间的差别大于 \(\varepsilon\) 时才计算损失. 如下图, 这相当于以 \(f(\mathbf{x})\) 为中心, 构建了一个宽度为 \(2\varepsilon\) 的隔离带, 当样本落入此间隔带, 则损失记为 \(0\).

svm_regression_margin
支持向量回归示意图, 红色表示落入隔离带的样本不计算损失

于是 SVR 问题可以形式化为:

\[\min_{\mathbf{\omega}, b}\ \frac{1}{2}||\mathbf{\omega}||^2 + C\sum^N_{i=1} l_{\varepsilon}(f(\mathbf{x}_i) - y_i) \]

其中 \(C\) 为正则化常数, \(l_{\varepsilon}\) 为下图所示的 \(\varepsilon\)-不敏感损失 ( \(\varepsilon\)-insensitive loss) 函数

\[\begin{equation} l_{\varepsilon}(z) = \max (0, |z|-\varepsilon) = \left\{ \begin{matrix} 0, & \text{if } |z| \leq \varepsilon\\ |z|-\varepsilon, & \text{otherwise} \end{matrix}\right. \end{equation} \]

svm_regression_insensitive_loss

引入松弛变量 \(\xi_i^{\vee}\) (upper tube violations) 和 \(\xi_i^{\wedge}\) (lower tube violations), 即要使样本点尽可能地落在隔离带间 (\(\xi_i^{\vee}\) 和 \(\xi_i^{\wedge}\) 尽可能地小), 也就是 \(-\varepsilon - \xi_i^{\vee} \leq y_i - f(\mathbf{x}_i) \leq \varepsilon + \xi_i^{\wedge}\). 上式可重写为:

\[\begin{equation} \begin{aligned} \min_{\mathbf{\omega}, b, \xi_i^{\vee}, \xi_i^{\wedge}}\ & \frac{1}{2}||\mathbf{\omega}||^2 + C\sum^N_{i=1} (\xi_i^{\vee} + \xi_i^{\wedge})\\ \text{subject to}\ & f(\mathbf{x}_i) - y_i \leq \varepsilon + \xi_i^{\vee}\\ & y_i - f(\mathbf{x}_i) \leq \varepsilon + \xi_i^{\wedge}\\ & \xi_i^{\vee} \geq 0, \xi_i^{\wedge} \geq 0,\ i = 1,2,\cdots,N \end{aligned} \end{equation} \]

由拉格朗日乘子法也可以得到 SVR 的对偶形式:

\[\begin{equation} \begin{aligned} \min_{\alpha^{\vee},\alpha^{\wedge}}\ & \frac{1}{2}\sum^N_{i=1}\sum^N_{j=1} (\alpha^{\wedge}_i-\alpha^{\vee}_i)(\alpha^{\wedge}_j-\alpha^{\vee}_j)(\mathbf{x}_i \cdot \mathbf{x}_j) + \sum^N_{i=1} \left[(\varepsilon - y_i)\alpha^{\wedge}_i + (\varepsilon + y_i)\alpha^{\vee}_i\right]\\ \text{subject to}\ & \sum^N_{i=1} (\alpha^{\wedge}_i-\alpha^{\vee}_i) = 0\\ & 0 \leq \alpha^{\wedge}_i\leq C, \ 0 \leq \alpha^{\vee}_i\leq C,\ i = 1,2,\cdots,N \end{aligned} \end{equation} \]

上述过程需要满足 KKT 条件, 即

\[\begin{equation} \begin{aligned} & \alpha^{\vee}_i(f(\mathbf{x}_i) - y_i - \varepsilon - \xi_i^{\vee}) = 0 \\ & \alpha^{\wedge}_i(y_i - f(\mathbf{x}_i) - \varepsilon - \xi_i^{\wedge}) = 0 \\ & \alpha_i^{\vee} \alpha_i^{\wedge} = 0, \ \xi_i^{\vee}\xi_i^{\wedge} = 0 \\ & (C-\alpha_i^{\vee})\xi_i^{\vee} = 0, \ (C-\alpha_i^{\wedge})\xi_i^{\wedge} = 0 \end{aligned} \end{equation} \]

可以看出, 对于落在隔离带间的样本点有 \(|f(\mathbf{x}_i) - y_i| < \varepsilon\), 此时由松弛变量的定义得到 \(\xi_i^{\vee}\) 和 \(\xi_i^{\wedge}\) 都为 \(0\), 则从 KKT 条件第 1 和第 2 式 (complementary slackness) 可以得出 \(\alpha_i^{\vee}\) 和 \(\alpha_i^{\wedge}\) 都为 \(0\). 也就是说, 当样本 \((\mathbf{x}_i, y_i)\) 不落入隔离带间, 相应的 \(\alpha_i^{\vee}\) 和 \(\alpha_i^{\wedge}\) 才能取非零值, 从而由SVR 解的形式可以得出得到 SVR 解的稀疏性 (对应于下面 SVR 解的形式).

还可以得到 SVR 解的形式为:

\[f(\mathbf{x}) = \sum^N_{i=1} (\alpha^{\wedge}_i-\alpha^{\vee}_i) (\mathbf{x}_i \cdot \mathbf{x}_j) + b \]

由 KKT 条件, 对每个样本 \((\mathbf{x}_i, y_i)\), 在得到 \(\alpha_i\) 之后, 若 \(0<\alpha_i<C\), 则必有 \(\xi_i=0\), 进而可以得到:

\[b = y_i + \varepsilon - \sum^N_{i=1} (\alpha^{\wedge}_i-\alpha^{\vee}_i) (\mathbf{x}_i \cdot \mathbf{x}_j) \]

因此在求解 SVR 的对偶形式得到 \(\alpha_i\) 后, 从理论上来说, 可任意选取 \(0<\alpha_i<C\) 的样本通过上式求得 \(b\), 但在实践中通常采用一种更鲁邦的方式, 即选择多个 (或所有) 满足条件的样本求解 \(b\) 后取平均值.

核技巧与非线性支持向量机

核技巧

设 \(\mathcal{X}\) 是输入空间 (欧式空间 \(\mathbb{R}^n\) 的子集或者离散集合), \(\mathcal{H}\) 为特征空间 (Hilbert 空间), 如果存在一个从 \(\mathcal{X}\) 到 \(\mathcal{H}\) 的映射:

\[\phi(x): \mathcal{X} \rightarrow \mathcal{H} \]

使得对所有 \(x, z \in \mathcal{X}\), 函数 \(K(x,z)\) 满足条件

\[K(x,z) = \phi(x) \phi(z) \]

则称 \(K(x,z)\) 为核函数, \(\phi(x)\) 为映射函数.

非线性可分问题可以利用非线性支持向量机求解, 其主要特点是利用核技巧 (kernel trick), 核技巧不仅应用于支持向量机, 而且应用于其他统计学习问题. 核技巧应用到支持向量机, 其基本想法是在学习与预测中通过一个非线性变换将输入空间 \(\mathcal{X}\) 的数据映射到新的特征空间 \(\mathcal{H}\) (通常是高维甚至是无穷维的), 使得在输入空间 \(\mathbb{R}^n\) 中的超曲面模型对应于特征空间 \(\mathcal{H}\) 中的超平面模型 (支持向量机), 这样分类问题的学习任务通过在特征空间中求解线性支持向量机就可以完成. 这里的映射是通过映射函数 \(\phi(x)\) 给出的, 但是核技巧在学习与预测过程中只定义核函数 \(K(x,z)\), 而不显式给出具体的 \(\phi(x)\), 核函数在低维 (输入空间) 上进行计算, 而将实质上的分类效果表现在了高维上, 这样避免了直接在高维空间中的复杂计算. 这里的映射函数 \(\phi(x)\) 实际上就相当于从原始 Hilbert 空间 \(\mathcal{X}\in \mathbb{R}^n\) 到另一个 Hilbert 空间 (特征空间) \(\mathcal{H}\) 的映射, 通过将原始线性不可分的数据集转化到更高维的空间中, 使其线性可分.

非线性支持向量机

在线性支持向量机的对偶问题中, 无论是目标函数还是决策函数 (分离超平面) 都只涉及输入实例与实例之间的内积, 在对偶问题中的内积 \(\mathbf{x}_i \cdot \mathbf{x}_j\) 可以用核函数 \(K(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i ) \cdot \phi(\mathbf{x}_j)\) 代替. 以非线性支持向量机对偶学习算法为例, 利用核函数可将对偶问题转化为:

\[\begin{equation} \begin{aligned} \min_{\alpha}\ & \frac{1}{2}\sum^N_{i=1}\sum^N_{j=1}\alpha_i\alpha_jy_iy_j K(\mathbf{x}_i, \mathbf{x}_j) - \sum^N_{i=1} \alpha_i\\ \text{subject to}\ & \sum^N_{i=1} \alpha_i y_i = 0\\ & 0 \leq \alpha_i \leq C, \ i = 1,2,\cdots,N \end{aligned} \end{equation} \]

相应的决策函数为:

\[f(\mathbf{x}) = \text{sign}(\sum^N_{i=1} \alpha^*_i y_i K(\mathbf{x}, \mathbf{x}_i) + b^*) \]

常用核函数

  1. 线性核函数 (linear kernel function), 对应于前面的线性支持向量机.

    \[K(x,z) = x \cdot z \]

  2. 多项式核函数 (polynomial kernel function), 对应的支持向量机是一个 \(d\) 次多项式分类器.

    \[K(x,z) = (\alpha x \cdot z +c)^d \]

  3. 高斯核函数 (Gaussian kernel function), 对应的支持向量机是高斯径向基函数 (radial basis function) 分类器.

    \[K(x,z) = \exp(-\frac{||x-z||^2}{2\sigma^2}) \]

推荐阅读