支持向量机

间隔与支持向量

在样本空间中，划分超平面可通过如下线性方程来描述：

\[ \bm{w}^T \bm{x} + b = 0 \]

其中 \(\bm{w}\) 为法向量，决定了超平面的方向；\(b\) 为位移项，决定了超平面与原点之间的距离。

样本空间中任意点 \(\bm{x}\) 到超平面 \((\bm{w}, b)\) 的距离可写为

\[ r = \frac{|\bm{w}^T \bm{x} + b|}{||\bm{w}||} \]

假设超平面 \((\bm{w}, b)\) 能将训练样本正确分类，即对于样本 \(\bm{x}_i\) 若 \(y_i = +1\)，则有 \(\bm{w}^T \bm{x}_i + b > 0\)；若 \(y_i = -1\)，则有 \(\bm{w}^T \bm{x}_i + b < 0\)。令

\[ \begin{cases} \bm{w}^T \bm{x}_i + b \ge +1 & y_i = +1 \\ \bm{w}^T \bm{x}_i + b \le -1 & y_i = -1 \end{cases} \]

通过缩放变换，可以使得距离超平面最近的几个训练样本点满足上式中的等式，此时它们被称为支持向量（support vector）。两个异类支持向量到超平面的距离之和为

\[ \gamma = \frac{2}{||\bm{w}||} \]

它被称为间隔（margin）。

欲找到具有最大间隔（maximum margin）的划分超平面，也就是要找到能满足上式约束的参数 \(\bm{w}\) 和 \(b\)，使得 \(\gamma\) 最大，即

\[ \max_{\bm{w}, b} \gamma = \frac{2}{||\bm{w}||} \\~\\ \text{s.t.} \quad y_i(\bm{w}^T \bm{x}_i + b) \ge 1, \quad i = 1, 2, \ldots, m \]

显然，为了最大化间隔，仅需最大化 \(||\bm{w}||^{-1}\)，这等价于最小化 \(||\bm{w}||^2\)。于是，上式可重写为

\[ \min_{\bm{w}, b} \frac{1}{2} ||\bm{w}||^2 \\~\\ \text{s.t.} \quad y_i(\bm{w}^T \bm{x}_i + b) \ge 1, \quad i = 1, 2, \ldots, m \]

这就是支持向量机（Support Vector Machine, 简称 SVM）的基本型。

对偶问题

转换为对偶问题

我们希望求解上述优化问题来得到大间隔划分超平面所对应的模型。注意到上述问题本身是一个凸二次规划（convex quadratic programming）问题，能直接用现成的优化计算包求解，但我们可以有更高效的办法。

对上述问题使用拉格朗日乘子法可得到其对偶问题（dual problem）。具体来说，对上述问题的每条约束添加拉格朗日乘子 \(\alpha_i \ge 0\)，则该问题的拉格朗日函数可写为

\[ L(\bm{w}, b, \bm{\alpha}) = \frac{1}{2} ||\bm{w}||^2 + \sum_{i=1}^m \alpha_i(1 - y_i(\bm{w}^T \bm{x}_i + b)) \]

现在我们令

\[ \theta(\bm{w}) = \max_{\bm{\alpha}} L(\bm{w}, b, \bm{\alpha}) \]

易得

\[ \theta(\bm{w}) = \begin{cases} \frac{1}{2} ||\bm{w}||^2 & \text{if } \bm{w} \text{ satisfies the constraints} \\ +\infty & \text{otherwise} \end{cases} \]

于是，原问题就被转换为了一个无约束优化问题

\[ \min_{\bm{w}, b} \theta(\bm{w}) = \min_{\bm{w}, b} \max_{\bm{\alpha}} L(\bm{w}, b, \bm{\alpha}) \]

再使用拉格朗日函数的对称性，将最小和最大的位置交换一下

\[ \max_{\bm{\alpha}} \min_{\bm{w}, b} L(\bm{w}, b, \bm{\alpha}) \]

令 \(L(\bm{w}, b, \bm{\alpha})\) 对 \(\bm{w}\) 和 \(b\) 的偏导为零可得

\[ \bm{w} = \sum_{i=1}^m \alpha_i y_i \bm{x}_i \]

\[ 0 = \sum_{i=1}^m \alpha_i y_i \]

将 \(\bm{w}\) 的公式代入 \(L(\bm{w}, b, \bm{\alpha})\)，即可将其中的 \(\bm{w}\) 和 \(b\) 消去，得到原问题的对偶问题

\[ \max_{\bm{\alpha}} \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j \bm{x}_i^T \bm{x}_j \]

\[ \text{s.t.} \quad \sum_{i=1}^m \alpha_i y_i = 0, \quad \alpha_i \ge 0, \quad i = 1, 2, \ldots, m \]

注意到原优化问题中有不等式约束，因此上述过程需满足 KKT（Karush-Kuhn-Tucker）条件，即要求

\[ \begin{cases} \alpha_i \ge 0 \\ y_i f(\bm{x}_i) - 1 \ge 0 \\ \alpha_i(y_i f(\bm{x}_i) - 1) = 0 \end{cases} \]

于是，对任意训练样本 \((\bm{x}_i, y_i)\)，总有 \(\alpha_i = 0\) 或 \(y_i f(\bm{x}_i) = 1\)。若 \(\alpha_i = 0\)，则该样本将不会在对偶问题的求和中出现，也就不会对 \(f(\bm{x})\) 有任何影响；若 \(\alpha_i > 0\)，则必有 \(y_i f(\bm{x}_i) = 1\)，所对应的样本点位于最大间隔边界上，是一个支持向量。这显示出支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关。

SMO 算法求解

不难发现，上述对偶问题一个凸二次规划问题，可使用通用的二次规划算法来求解。但是，该问题的规模正比于训练样本数，这会在实际任务中造成很大的开销。为了避开这个障碍，人们通过利用问题本身的特性，提出了很多高效算法，SMO（Sequential Minimal Optimization）是其中一个著名的代表。

SMO 的基本思路是先固定除两个变量 \(\alpha_i\) 和 \(\alpha_j\) 以外的所有参数，然后求 \(\alpha_i\) 和 \(\alpha_j\) 上的极值。由于存在约束 \(\sum_{i=1}^m \alpha_i y_i = 0\)，若固定除 \(\alpha_i\) 和 \(\alpha_j\) 以外的其他变量，则必可由其他变量导出。于是，SMO 每次选择两个变量 \(\alpha_i\) 和 \(\alpha_j\)，并固定其他参数。这样，在参数初始化后，SMO 不断执行如下两个步骤直至收敛：

• 选取一对需更新的变量 \(\alpha_i\) 和 \(\alpha_j\)；
• 固定 \(\alpha_i\) 和 \(\alpha_j\) 以外的参数，求解对偶问题获得更新后的 \(\alpha_i\) 和 \(\alpha_j\)。

注意到只需选取的 \(\alpha_i\) 和 \(\alpha_j\) 中有一个不满足 KKT 条件，目标函数就会在迭代后减小。直观来看，KKT 条件违背的程度越大，则变量更新后可能导致的目标函数值减幅越大。于是，SMO 先选取违背 KKT 条件程度最大的变量。第二个变量应选择一个使目标函数值减小最快的变量，但由于比较各变量所对应的目标函数值减幅的复杂度过高，因此 SMO 采用了一种启发式使选取的两变量所对应样本之间的间隔最大。一种直观的解释是，这样的两个变量有很大的差别，与对两个相似的变量进行更新相比，对它们进行更新会带给目标函数值更大的变化。

SMO 算法之所以高效，恰由于在固定其他参数后，仅优化两个参数的过程能做到非常高效。具体来说，仅考虑 \(\alpha_i\) 和 \(\alpha_j\) 时，对偶问题中的约束可重写为

\[ a_iy_i + a_jy_j = c, \quad 0 \le \alpha_i, \alpha_j \le C \]

消去对偶问题中的变量 \(\alpha_j\)，则得到一个关于 \(\alpha_i\) 的单变量二次规划问题，仅有的约束是 \(0 \le \alpha_i \le C\)。不难发现，这样的二次规划问题具有闭式解，于是不必调用数值优化算法即可高效地计算出更新后的 \(\alpha_i\) 和 \(\alpha_j\)。

如何确定偏移项 \(b\) 呢？注意到对任意支持向量 \((\bm{x}_i, y_i)\) 都有 \(y_i f(\bm{x}_i) = 1\)，即

\[ y_s \left( \sum_{i=1}^m \alpha_i y_i \bm{x}_i^T \bm{x}_s + b \right) = 1 \]

理论上，可选取任意支持向量并通过求解上式获得 \(b\)。但在实际任务中常采用一种更鲁棒的做法：使用所有支持向量求解的平均值

\[ b = \frac{1}{|S|} \sum_{s \in S} \left( y_s - \sum_{i=1}^m \alpha_i y_i \bm{x}_i^T \bm{x}_s \right) \]

核函数

在前面的讨论中，我们假设训练样本是线性可分的，即存在一个划分超平面能将训练样本正确分类。然而在现实任务中，原始样本空间内也许并不存在一个能正确划分两类样本的超平面。例如“异或”问题就不是线性可分的。

对这样的问题，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。幸运的是，如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分。

令 \(\phi(\bm{x})\) 表示将 \(\bm{x}\) 映射后的特征向量，于是，在特征空间中划分超平面所对应的模型可表示为

\[ f(\bm{x}) = \bm{w}^T \phi(\bm{x}) + b \]

其中 \(\bm{w}\) 和 \(b\) 是模型参数。类似地有

\[ \min_{\bm{w}, b} \frac{1}{2} ||\bm{w}||^2 \]

\[ \text{s.t.} \quad y_i(\bm{w}^T \phi(\bm{x}_i) + b) \ge 1, \quad i = 1, 2, \ldots, m \]

其对偶问题是

\[ \max_{\bm{\alpha}} \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j \phi(\bm{x}_i)^T \phi(\bm{x}_j) \]

\[ \text{s.t.} \quad \sum_{i=1}^m \alpha_i y_i = 0, \quad \alpha_i \ge 0, \quad i = 1, 2, \ldots, m \]

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

\[ \kappa(\bm{x}_i, \bm{x}_j) = \langle \phi(\bm{x}_i), \phi(\bm{x}_j) \rangle = \phi(\bm{x}_i)^T \phi(\bm{x}_j) \]

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

关于核函数，我们有下面的定理：

Mercer定理 令 \(\mathcal{X}\) 为输入空间，\(\kappa(\cdot, \cdot)\) 是定义在 \(\mathcal{X} \times \mathcal{X}\) 上的对称函数，则 \(\kappa\) 是核函数当且仅当对于任意数据 \(\{\bm{x}_1, \bm{x}_2, \ldots, \bm{x}_m\}\)，核矩阵（kernel matrix）\(K\) 总是半正定的：

\[ K = \begin{bmatrix} \kappa(\bm{x}_1, \bm{x}_1) & \kappa(\bm{x}_1, \bm{x}_2) & \cdots & \kappa(\bm{x}_1, \bm{x}_m) \\ \kappa(\bm{x}_2, \bm{x}_1) & \kappa(\bm{x}_2, \bm{x}_2) & \cdots & \kappa(\bm{x}_2, \bm{x}_m) \\ \vdots & \vdots & \ddots & \vdots \\ \kappa(\bm{x}_m, \bm{x}_1) & \kappa(\bm{x}_m, \bm{x}_2) & \cdots & \kappa(\bm{x}_m, \bm{x}_m) \end{bmatrix} \]

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

通过前面的讨论可知，我们希望样本在特征空间内线性可分，因此特征空间的好坏对支持向量机的性能至关重要。需注意的是，在不知道特征映射的形式时，我们并不知道什么样的核函数是合适的，而核函数也仅是隐式地定义了特征空间。

下表列出了一些常用的核函数：

核函数	公式	参数
线性核	\(\kappa(\bm{x}_i, \bm{x}_j) = \bm{x}_i^T \bm{x}_j\)
多项式核	\(\kappa(\bm{x}_i, \bm{x}_j) = (\bm{x}_i^T \bm{x}_j)^d\)	\(d \ge 1\)
高斯核（RBF核，径向基函数核）	\(\kappa(\bm{x}_i, \bm{x}_j) = \exp\left( -\frac{\|\bm{x}_i - \bm{x}_j\|^2}{2\sigma^2} \right)\)	\(\sigma > 0\) 为高斯核的带宽（width）
拉普拉斯核	\(\kappa(\bm{x}_i, \bm{x}_j) = \exp\left( -\frac{\|\bm{x}_i - \bm{x}_j\|}{\sigma} \right)\)	\(\sigma > 0\)
Sigmoid 核	\(\kappa(\bm{x}_i, \bm{x}_j) = \tanh(\beta \bm{x}_i^T \bm{x}_j + \theta)\)	\(\beta \gt 0, \theta \lt 0\)

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

• 若 \(\kappa_1\) 和 \(\kappa_2\) 为核函数，则对于任意正数 \(\gamma_1\)、\(\gamma_2\)，其线性组合 \(\gamma_1 \kappa_1 + \gamma_2 \kappa_2\) 也是核函数。
• 若 \(\kappa_1\) 和 \(\kappa_2\) 为核函数，则核函数的直积 \(\kappa_1 \otimes \kappa_2 (\bm{x}, \bm{z}) = \kappa_1(\bm{x}, \bm{z}) \kappa_2(\bm{x}, \bm{z})\) 也是核函数。
• 若 \(\kappa_1\) 是核函数，则对于任意函数 \(g(\bm{x})\)，其复合函数 \(\kappa(\bm{x}, \bm{z}) = g(\bm{x}) \kappa_1(\bm{x}, \bm{z}) g(\bm{z})\) 也是核函数。

软间隔与正则化

软间隔支持向量机

在前面的讨论中，我们一直假定训练样本在样本空间或特征空间中是线性可分的，即存在一个超平面能将不同类的样本完全划分开。然而，在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分；退一步说，即便恰好找到了某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合所造成的。

缓解该问题的一个办法是允许支持向量机在一些样本上出错。为此，要引入软间隔（soft margin）的概念。具体来说，前面介绍的支持向量机形式是要求所有样本均满足约束，即所有样本都必须划分正确，这称为硬间隔（hard margin），而软间隔则是允许一些样本不满足约束。当然，在最大化间隔的同时，不满足约束的样本应尽可能少。于是，优化目标可写为

\[ \min_{\bm{w}, b} \frac{1}{2} ||\bm{w}||^2 + C \sum_{i=1}^m \ell_{0/1} (y_i (\bm{w}^T \bm{x}_i + b) - 1) \]

其中 \(C > 0\) 是一个常数，\(\ell_{0/1}(z)\) 是0/1损失函数，当 \(z < 0\) 时为 1，否则为 0。

然而，\(\ell_{0/1}\) 非凸、非连续，数学性质不太好，使得式不易直接求解。于是，人们通常用其他一些函数来代替 \(\ell_{0/1}\)，称为替代损失（surrogate loss）。替代损失函数一般具有较好的数学性质，如它们通常是凸的连续函数且是 \(\ell_{0/1}\) 的上界。常用的替代损失函数有：

• hinge 损失：\(\ell_{\text{hinge}}(z) = \max(0, 1 - z)\)；
• 指数损失（exponential loss）：\(\ell_{\text{exp}}(z) = \exp(-z)\)；
• 对率损失（logistic loss）：\(\ell_{\text{log}}(z) = \log(1 + \exp(-z))\)。

若采用 hinge 损失，则上式变为

\[ \min_{\bm{w}, b} \frac{1}{2} ||\bm{w}||^2 + C \sum_{i=1}^m \max(0, 1 - y_i (\bm{w}^T \bm{x}_i + b)) \]

引入松弛变量（slack variables）\(\xi_i \ge 0\)，可将优化目标重写为

\[ \min_{\bm{w}, b, \bm{\xi}} \frac{1}{2} ||\bm{w}||^2 + C \sum_{i=1}^m \xi_i \]

\[ \text{s.t.} \quad y_i(\bm{w}^T \bm{x}_i + b) \ge 1 - \xi_i, \quad \xi_i \ge 0, \quad i = 1, 2, \ldots, m \]

这就是常用的软间隔支持向量机。

这仍是一个二次规划问题，可以通过拉格朗日乘子法得到拉格朗日方程：

\[ L(\bm{w}, b, \bm{\xi}, \bm{\alpha}, \bm{\mu}) = \frac{1}{2} ||\bm{w}||^2 + C \sum_{i=1}^m \xi_i + \sum_{i=1}^m \alpha_i (1 - \xi_i - y_i (\bm{w}^T \bm{x}_i + b)) - \sum_{i=1}^m \mu_i \xi_i \]

令 \(L(\bm{w}, b, \bm{\xi}, \bm{\alpha}, \bm{\mu})\) 对 \(\bm{w}\),\(b\),\(\xi_i\) 的偏导为零可得：

\[ \begin{cases} \bm{w} = \sum_{i=1}^m \alpha_i y_i \bm{x}_i \\ 0 = \sum_{i=1}^m \alpha_i y_i \\ C = \alpha_i + \mu_i \end{cases} \]

代入后可得到对偶问题：

\[ \max_{\bm{\alpha}} \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j \bm{x}_i^T \bm{x}_j \]

\[ \text{s.t.} \quad 0 \le \alpha_i \le C, \quad \sum_{i=1}^m \alpha_i y_i = 0 \]

将该式与上面对比可看出，两者的区别仅在于对 \(\alpha_i\) 的约束条件不同：前者是 \(0 \le \alpha_i \le C\)，后者是 \(\alpha_i \ge 0\)。于是，可采用前面的算法求解该对偶问题；在引入核函数后能得到与前面相同的支持向量展式。

根据 KKT 条件可推得最终模型仅与支持向量有关, 也即 hinge 损失函数依然保持了支持向量机解的稀疏性。

正则化

我们还可以将 0/1 损失函数换成别的替代损失函数以得到其他学习模型，这些模型的性质与所用的替代函数直接相关，但它们具有一个共性：优化目标中的第一项用来描述划分超平面的“间隔”大小，另一项用来表述训练集上的误差，可写为更一般的形式

\[ \min_{f} \Omega(f) + C \sum_{i=1}^m \ell(f(\bm{x}_i), y_i) \]

其中 \(\Omega(f)\) 称为结构风险（structural risk），用于描述模型 \(f\) 的某些性质；第二项 \(\sum_{i=1}^m \ell(f(\bm{x}_i), y_i)\) 称为经验风险（empirical risk），用于描述模型与训练数据的契合程度；\(C\) 用于对二者进行折中。

从经验风险最小化的角度来看，\(\Omega(f)\) 表述了我们希望获得具有何种性质的模型，这为引入领域知识和用户意图提供了途径；另一方面，该信息有助于削减假设空间，从而降低了最小化训练误差的过拟合风险。从这个角度来说，该式称为正则化（regularization）问题，\(\Omega(f)\) 称为正则化项，\(C\) 则称为正则化常数。

\(L_p\) 范数（norm）是常用的正则化项，其中 \(L_2\) 范数 \(||\bm{w}||_2\) 倾向于 \(\bm{w}\) 的分量取值尽量均衡，即非零分量个数尽量稠密，而 \(L_0\) 范数 \(||\bm{w}||_0\) 和 \(L_1\) 范数 \(||\bm{w}||_1\) 则倾向于 \(\bm{w}\) 的分量尽量稀疏，即非零分量个数尽量少。

支持向量回归

对样本 \((\bm{x}_i, y_i)\)，传统回归模型通常直接基于模型输出 \(f(\bm{x}_i)\) 与真实输出 \(y_i\) 之间的差别来计算损失，当且仅当 \(f(\bm{x}_i)\) 与 \(y_i\) 完全相同时，损失才为零。与此不同，支持向量回归（Support Vector Regression, 简称 SVR）假设我们能容忍 \(f(\bm{x}_i)\) 与 \(y_i\) 之间最多有 \(\epsilon\) 的偏差，即仅当 \(f(\bm{x}_i)\) 与 \(y_i\) 之间的差别绝对值大于 \(\epsilon\) 时才计算损失。这相当于以 \(y_i\) 为中心，构建了一个宽度为 \(2\epsilon\) 的间隔带，若训练样本落入此间隔带，则认为是被预测正确的。

于是，SVR 问题可形式化为

\[ \min_{\bm{w}, b} \frac{1}{2} ||\bm{w}||^2 + C \sum_{i=1}^m \ell_{\epsilon} (f(\bm{x}_i) - y_i) \]

其中 \(C\) 为正则化常数，\(\ell_{\epsilon}\) 是不敏感损失（insensitive loss）函数

\[ \ell_{\epsilon}(z) = \begin{cases} 0, & \text{if } |z| \le \epsilon \\ |z| - \epsilon, & \text{otherwise} \end{cases} \]

引入松弛变量 \(\xi_i\) 和 \(\hat{\xi}_i\)，可将上式重写为

\[ \min_{\bm{w}, b, \bm{\xi}, \bm{\hat{\xi}}} \frac{1}{2} ||\bm{w}||^2 + C \sum_{i=1}^m (\xi_i + \hat{\xi}_i) \]

\[ \begin{aligned} \text{s.t. } \ &f(\bm{x}_i) - y_i \le \epsilon + \xi_i, \\ &y_i - f(\bm{x}_i) \le \epsilon + \hat{\xi}_i, \\ &\xi_i, \hat{\xi}_i \ge 0, \quad i = 1, 2, \ldots, m \end{aligned} \]

通过拉格朗日乘子法可得 SVR 问题的对偶问题

\[ \max_{\bm{\alpha}, \hat{\bm{\alpha}}} \sum_{i=1}^m [y_i(\hat{\alpha}_i - \alpha_i) - \epsilon (\hat{\alpha}_i + \alpha_i)] - \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m (\alpha_i - \hat{\alpha}_i) (\alpha_j - \hat{\alpha}_j) \bm{x}_i^T \bm{x}_j \]

上述过程中需要满足 KKT 条件，即要求

\[ \begin{cases} \alpha_i (f(\bm{x}_i) - y_i - \epsilon - \xi_i) = 0, \\ \hat{\alpha}_i (y_i - f(\bm{x}_i) - \epsilon - \hat{\xi}_i) = 0, \\ \alpha_i \hat{\alpha}_i = 0, \quad \xi_i \hat{\xi}_i = 0, \\ (C - \alpha_i) \xi_i = 0, \quad (C - \hat{\alpha}_i) \hat{\xi}_i = 0. \end{cases} \]

可以看到，当且仅当 \(f(\bm{x}) - y_i - \epsilon - \xi_i = 0\) 时 \(\alpha_i\) 才能取非零值，当且仅当 \(y_i - f(\bm{x}_i) - \epsilon - \hat{\xi}_i = 0\) 时 \(\hat{\alpha}_i\) 才能取非零值。换言之，仅当样本 \((\bm{x}_i, y_i)\) 不落入间隔带中，相应的 \(\alpha_i\) 和 \(\hat{\alpha}_i\) 才能取非零值。此外，\(f(\bm{x}) - y_i - \epsilon - \xi_i = 0\) 和 \(y_i - f(\bm{x}_i) - \epsilon - \hat{\xi}_i = 0\) 不能同时成立，因此 \(\alpha_i\) 和 \(\hat{\alpha}_i\) 中至少有一个为零。

通过拉格朗日函数求偏导可得 \(\bm{w} = \sum_{i=1}^m (\hat{\alpha}_i - \alpha_i) \bm{x}_i\)，因此 SVR 的解形式为

\[ f(\bm{x}) = \sum_{i=1}^m (\hat{\alpha}_i - \alpha_i) \bm{x}_i^T \bm{x} + b \]

能使 \((\hat{\alpha}_i - \alpha_i) \ne 0\) 的样本即为 SVR 的支持向量，它们必落在间隔带之外。显然，SVR 的支持向量仅是训练样本的一部分，即其解仍具有稀疏性。

若考虑特征映射形式 \(\phi(\bm{x})\)，则相应的，SVR 的解形式为

\[ f(\bm{x}) = \sum_{i=1}^m (\hat{\alpha}_i - \alpha_i) \phi(\bm{x}_i)^T \phi(\bm{x}) + b \]

核方法

回顾 SVM 和 SVR 中的模型表达式可发现，给定训练样本 \(\{(\bm{x}_1, y_1), \ldots, (\bm{x}_m, y_m)\}\)，若不考虑偏移项 \(b\)，则无论 SVM 还是 SVR，学得的模型总能表示成核函数 \(\kappa(\bm{x}, \bm{x}_i)\) 的线性组合。不仅如此，事实上我们有下面这个称为表示定理（representer theorem）的更一般的结论：

表示定理 令 \(\mathbb{H}\) 为核函数 \(\kappa\) 对应的再生核希尔伯特空间，\(||h||_{\mathbb{H}}\) 表示 \(\mathbb{H}\) 空间中关于 \(h\) 的范数，对于任意单调递增函数 \(\Omega: [0, \infty] \to \mathbb{R}\) 和任意非负损失函数 \(\ell: \mathbb{R}^m \to [0, \infty]\)，优化问题

\[ \min_{f} F(h) = \Omega(||h||_{\mathbb{H}}) + \ell(h(\bm{x}_1), \ldots, h(\bm{x}_m)) \]

的解总可写为

\[ h^*(\bm{x}) = \sum_{i=1}^m \alpha_i \kappa(\bm{x}, \bm{x}_i) \]

表示定理对损失函数没有限制，对正则化项 \(\Omega\) 仅要求单调递增，甚至不要求 \(\Omega\) 是凸函数，意味着对于一般的损失函数和正则化项，优化问题的最优解无论如何都可表示为核函数 \(\kappa(\bm{x}, \bm{x}_i)\) 的线性组合；这显示出核函数的巨大威力。

人们发展出一系列基于核函数的学习方法，统称为核方法（kernel methods）。最常见的，是通过核化（即引入核函数）来将线性学习器拓展为非线性学习器。

通过表示定理可以得到很多线性模型的”核化”版本，例如核SVM、核LDA、核PCA。KLDA（Kernelized Linear Discriminant Analysis）就是先将样本映射到高维特征空间, 然后在此特征空间中做线性判别分析。