前言

本节是支持向量机，想起我室友当初毕设就和这个有关

第六章

本章开始支持向量机的学习，记得我室友毕设就和这个有关哈哈

6.1 支持向量机

在分类任务中，对于线性可分问题，基础目标是找到一个能将样本完美分离的超平面。但仅满足分类正确性是不够的，因为机器学习的核心目标是构建泛化能力强的模型。关键在于：一个好的超平面应该最大化与最近样本点的距离。这种性质使得模型对噪声或微小扰动不敏感，从而提升泛化性能。

支持向量机的核心思想是：在所有可行超平面中，存在唯一最优解——该超平面不仅保证分类正确性，还通过最大化最近样本点的距离来优化泛化能力。我们定义支持向量为距离超平面最近的样本点，它们直接决定了最优超平面的位置。

• SVM仅依赖支持向量（而非全部样本数据），这与第三章的线性回归方法（依赖全体数据）不同

超平面的数学表示为：
$${\mathbf{w}}^T\mathbf{x}+b=0$$
其中：

• $\mathbf{w}=(w_1,w_2,\dots ,w_d)$ 是法向量（$d$ 为属性维度）；
• $b$ 是位移项。

空间中任意点 $\mathbf{a}$ 到超平面的距离公式为：
$$r=\frac{|{\mathbf{w}}^T\mathbf{a}+b|}{\Vert \mathbf{w}\Vert }$$

点到平面距离的推导
取空间点 $Q$ 和平面内点 $P$，距离为向量 $\overrightarrow{QP}$ 在法向量 $\mathbf{w}$ 方向的投影长度：$\frac{|\mathbf{w}\cdot \overrightarrow{QP}|}{\Vert \mathbf{w}\Vert }$

因此，只需计算所有支持向量到超平面的距离并取最小值即可确定最优间隔。超平面的一个特性是可任意放缩（即对任意$c\ne 0$，$c({\mathbf{w}}^T\mathbf{x}+b)=0$仍表示同一超平面）。为便于计算，需对$\mathbf{w},b$进行规范化：要求所有支持向量满足
$$|{\mathbf{w}}^T{\mathbf{x}}_{sv}+b|=1$$
在此规范下：

1. 几何间隔为 $r=\frac{1}{\Vert \mathbf{w}\Vert }$
2. 正负类支持向量到超平面的距离均为 $\frac{1}{\Vert \mathbf{w}\Vert }$
3. 最终间隔定义为两距离之和：$\frac{2}{\Vert \mathbf{w}\Vert }$

因此，SVM组基本的问题就是找到一组参数$(\mathbf{w},b)$使得$\frac{2}{\Vert \mathbf{w}\Vert }$最大且满足约束：
$$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1$$

• 其中yi∈{1,−1}y_{i}\in\{1,-1\}yi​∈{1,−1}为样本标签，约束乘积大于$1$表明标签和分类预测同号即要求分类正确
• 乘积大于等于1表明所有样本都必须在间隔之外或在间隔边界上（支持向量）

现在我们来求解这个最值问题，这是一个凸二次规划问题，对于这一类问题可以使用拉格朗日对偶性来解决。

构建拉格朗日函数

1. 原式要求$\frac{2}{\Vert \mathbf{w}\Vert }$最大，即求$\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$最小
2. 为所有样本约束引入乘子${\alpha }_i\ge 0$，写为${\alpha }_i(1-y_i({\mathbf{w}}^T{\mathbf{x}}_i+b))$
3. 所以拉格朗日函数为$L=\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+{\sum }_{i=1}^m{\alpha }_i(1-y_i({\mathbf{w}}^T{\mathbf{x}}_i+b))$

原问题的等价问题：上述约束问题可以等价于$mi{n}_{\mathbf{w},b}ma{x}_{\alpha }L$

1. 对于内层，只关心$\alpha$的变化，我们已经要求$\alpha \ge 0$，
2. 如果存在一个样本违背了约束($(1-y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)>0$)，那么求和项会出现正数，$ma{x}_{\alpha }$会让$L$趋于无穷，最终外层的$min$永远无法满足，因此不能有样本违背约束。
3. 如果所有样本都满足约束 $y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1$，则 $1-y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\le 0$。为了最大化 $L$，$\sum {\alpha }_i(1-y_i(\dots ))$ 这一项必须取其最大可能值，即 0。这要求对于所有 $i$，必须满足 ${\alpha }_i(1-y_i({\mathbf{w}}^T{\mathbf{x}}_i+b))=0$。这就是KKT互补条件。
4. 回到整个式子$mi{n}_{\mathbf{w},b}ma{x}_{\alpha }L$就等价于$min\left(\frac{1}{2}\Vert \mathbf{w}{\Vert }^2\right)$，因此等价

考虑对偶问题，即交换$max$与$min$，其对偶问题为$ma{x}_{\alpha }mi{n}_{\mathbf{w},b}L$。可以证明强对偶性成立，两个问题最优解是一样的

求解内层最小化问题
对于内层，变量只有$\mathbf{w},b$，所以可以求偏导令其为$0$有。
$$\begin{array}{rl}\frac{\partial L}{\partial \mathbf{w}}& =0\Rightarrow \mathbf{w}=\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i\\ \frac{\partial L}{\partial b}& =0\Rightarrow \sum _{i=1}^m{a}_i{y}_i=0\end{array}$$
前者表明最优$\mathbf{w}$由$\alpha ,y$决定，是${\mathbf{x}}_i$的线性组合；后者给出了$\alpha ,y$的一个约束。现在我们代回$L$得到对偶目标函数
$$\begin{array}{rl}L& =\frac{1}{2}{\left(\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i\right)}^T\left(\sum _{j=1}^m{\alpha }_j{y}_j{\mathbf{x}}_j\right)+\sum _{i=1}^m{\alpha }_i-\sum _{i=1}^m{\alpha }_i{y}_i\left({\left(\sum _{j=1}^m{\alpha }_j{y}_j{\mathbf{x}}_j\right)}^T{\mathbf{x}}_i+b\right)\\ & =\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i^T{\mathbf{x}}_j)+\sum _{i=1}^m{\alpha }_i-\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_j^T{\mathbf{x}}_i)-b\sum _{i=1}^m{\alpha }_i{y}_i\\ & =\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({\mathbf{x}}_i^T{\mathbf{x}}_j)\end{array}$$
其中用到了${\mathbf{x}}_j^T{\mathbf{x}}_i={\mathbf{x}}_i^T{\mathbf{x}}_j$与${\sum }_{i=1}^m{a}_i{y}_i=0$.这样完整的对偶问题就被构建完成，我们需要求解${\alpha }_i$在满足约束条件${\sum }_{i=1}^m{\alpha }_i{y}_i=0$和${\alpha }_i\ge 0$的最大$L$。这也是一个二次规划问题，但现在$L$仅仅依赖于$\alpha$。它的求解方法很多，这里我们介绍最出名的序列最小最优化 (Sequential Minimal Optimization, SMO算法，其核心思想是选取两个变量${\alpha }_i,{\alpha }_j$固定其他所有变量（因为存在约束条件，只选取一个的话，该变量可由其他固定变量根据约束条件导出），这样就可以求解子问题。具体说来

• 选一对乘子，通常会优先选择那些最"违反" KKT 条件的乘子，收敛快
• 固定其他 $m-2$ 个乘子，将对偶目标函数 $L(\alpha )$ 视为仅关于 ${\alpha }_i$ 和 ${\alpha }_j$ 的函数，并求解这个子优化问题，得到更新后的最优值 $({\alpha }_i^{new},{\alpha }_j^{new})$。这个子问题因为只有两个变量，并且约束简单，可以解析求解。
• 更新原来的乘子和$b$
• 检查所有乘子是否在一定容忍度内满足 KKT 条件。如果满足，则算法收敛；否则，进行下一轮迭代。

因此，最优法向量
$$\mathbf{w}=\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i$$
其中，${\alpha }_i$是最优乘子。最后我们说一下$b$的求解，根据KKT互补，只有支持向量才会出现和$b$有关的等式（非支持向量${\alpha }_i=0$，含$b$项约束是一个不等式），所以我们只需要考虑$1$个支持向量，解约束项等式就可以得到$b$。但为了健壮性，我们一般考虑所有支持向量求解的期望：
$$b=\frac{1}{|S|}\sum _{s\in S}\left(y_s-\sum _{i=1}^m{a}_i{y}_i{\mathbf{x}}_i^T{\mathbf{x}}_s\right)$$
其中$S$是所有支持向量的集合。

最终$b$的表达式和书上不太一致，我感觉是教材写错了

6.2 核函数

我们已经知道，支持向量机的核心目标是找到一个超平面，用于处理线性可分数据的分类问题。然而，这与感知机面临的困境类似：对于线性不可分问题，超平面无法直接有效分类。在感知机中，解决方案是引入隐层和非线性激活函数，通过将超平面转换为曲面来实现分类。而SVM采用了另一种策略：通过核函数将原始样本映射到更高维的特征空间，在该空间中寻找一个线性超平面完成分类。

一个列子：假设实数区间$\mathbb{R}$中$[-1,1]$被定义为负类，其余实数$\mathbb{R}\setminus [-1,1]$为正类。此时无法通过一维空间的线性决策边界（即一个点）实现完美分类，因为该问题线性不可分。但若通过映射$\varphi :\mathbb{R}\to {\mathbb{R}}^2$将样本升维至二维空间，其中$\varphi (x)=(x,x^2)$，则样本在二维空间中形成抛物线$y=x^2$：负类值域落在$[0,1]$区间，正类值域分布于$(1,+\infty )$。此时可用线性超平面（如直线$y=1.01$）实现分类（注意，映射后的点都落在抛物线上，而不是整个平面）。

更形式化地说，我们可以定义一个映射$\varphi$将原始样本空间$\mathcal{X}$中的样本点$x\in \mathcal{X}$映射到一个高维空间$\mathcal{H}$中的点$\varphi (x)$，即$\varphi :\mathcal{X}\to \mathcal{H}$。然后我们就可以在$\mathcal{H}$中训练一个SVM，其线性决策边界为$0={\mathbf{w}}^T\varphi (\mathbf{x})+b$，并求解高维空间中的对偶问题：
$$\underset{\alpha }{\max }\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\varphi ({\mathbf{x}}_i{)}^T\varphi ({\mathbf{x}}_j)$$
但这样会引入一个问题：映射后的空间$\mathcal{H}$维度可能很高（甚至是无限维），导致直接计算$\varphi (\mathbf{x})$困难且存储成本高。

幸运的是可以发现：所有$\varphi (x)$的出现都以内积形式$\varphi ({\mathbf{x}}_i{)}^T\varphi ({\mathbf{x}}_j)$存在，包括决策函数：
$$f(\mathbf{z})=\sum _{i\in SV}{\alpha }_i{y}_i\varphi ({\mathbf{x}}_i{)}^T\varphi (\mathbf{z})+b$$
其中$\mathbf{z}$是预测数据。因此，我们可以引入核函数$\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)=\varphi ({\mathbf{x}}_i{)}^T\varphi ({\mathbf{x}}_j)$，避免显式计算$\varphi (\mathbf{x})$。

该理论属于再生核希尔伯特空间（RKHS），涉及Mercer定理等数学基础。

略去复杂的数学部分，我们只需要知道一个有效的核函数一定对应一个高维$\mathcal{H}$和对应的映射函数$\varphi$使得$\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)=\varphi ({\mathbf{x}}_i{)}^T\varphi ({\mathbf{x}}_j)$成立。
有效核函数的条件：

1. 对称性：$\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)=\kappa ({\mathbf{x}}_j,{\mathbf{x}}_i)$
2. 半正定核矩阵：对任意数据集{x1,...,xm}\{\mathbf{x}_1, ..., \mathbf{x}_m\}{x1​,...,xm​}，矩阵$G_{ij}=\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)$是半正定的。

选择核函数及其参数对 SVM 的性能至关重要，但这一选择通常没有理论上的最优解，而是需要依赖实验调优。

最后说明一下常见的核函数：

核函数类型	表达式	参数说明
线性核	$\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)={\mathbf{x}}_i^T{\mathbf{x}}_j$	无参数
多项式核	$\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)=({\mathbf{x}}_i^T{\mathbf{x}}_j{)}^d$	$d$：多项式阶数
高斯核（RBF）	$\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)=\exp (-\gamma |{\mathbf{x}}_i-{\mathbf{x}}_j{|}^2)$	$\gamma =\frac{1}{2{\sigma }^2}$（带宽参数，控制函数平滑度）
拉普拉斯核	$\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)=\exp (-\gamma |{\mathbf{x}}_i-{\mathbf{x}}_j|)$	$\gamma =\frac{1}{\sigma }>0$（与高斯核类似，但使用L1距离）
Sigmoid核	$\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)=\tanh (\beta {\mathbf{x}}_i^T{\mathbf{x}}_j+\theta )$	$\beta >0$（缩放因子），$\theta <0$（偏置项）

此外，对于任意正实数 $c_1,c_2$ 和核函数 ${\kappa }_1,{\kappa }_2$，以及函数 $g(\mathbf{x})$，以下构造均为核函数：

1. 线性组合：$c_1{\kappa }_1+c_2{\kappa }_2$
2. 直积：${\kappa }_1\otimes {\kappa }_2(\mathbf{x},\mathbf{z})={\kappa }_1(\mathbf{x},\mathbf{z}){\kappa }_2(\mathbf{x},\mathbf{z})$
3. 函数缩放：$g(\mathbf{x}){\kappa }_1(\mathbf{x},\mathbf{z})g(\mathbf{z})$

6.3 软间隔与正则化

在引入核函数后，虽然SVM的理论框架趋于完善，但仍存在两个关键问题需要解决：

1. 复杂问题的线性可分性：无论是原始样本空间还是映射后的特征空间$\mathcal{H}$，要找到一个完美分离所有样本的超平面极其困难，这在实际应用中会带来高昂的计算和优化成本。
2. 异常点导致的过拟合：若样本中存在少量异常点（如错误标注或离群点），SVM为强制分类这些点可能导致间隔大幅缩小，从而损害模型的泛化能力。

这些问题的根源在于硬间隔的严格约束——即要求所有样本必须满足$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1$。通过允许部分样本违反该约束（称为软间隔，soft margin），可显著提升模型对噪声和复杂分布的适应性。

于是在考虑最大化间隔的情况下，引入常数$C>0$和$0/1$损失函数$L_{0/1}$，优化目标可以写为
$$\underset{w,b}{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m{L}_{0/1}(y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)-1)$$
其中
$$L_{0/1}(z)=\{\begin{array}{ll}0& \text{if }z>0\\ 1& \text{if }z\le 0\end{array}$$
这相当于分类出错的样本给一个惩罚。但是$L_{0/1}$函数性质不好，不适合求解，于是常用一些其他函数来替代它称为“替代损失”。设$z=y_{i}f({\mathbf{x}}_i)$常见的三种替代损失为：

损失函数名称	表达式	备注
Hinge损失	$\max (0,1-z)$	用于支持向量机（SVM）
指数损失	$\exp (-z)$	常用于AdaBoost算法
对率损失	$\log (1+\exp (-z))$	逻辑回归的平滑替代损失

因此我们采用Hinge损失函数，目标函数变为
$$\underset{w,b}{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m\max (0,1-y_i({\mathbf{w}}^T{\mathbf{x}}_i+b))$$
为了更方便的计算，引入松弛变量${\xi }_i\ge 0$，每一个样本点都有一个对应的${\xi }_i$，因此优化目标可以重写为
$$\underset{w,b,\xi }{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m{\xi }_i$$
可以发现其实就是用${\xi }_i$替换了Hinge损失的值，用来表示样本不满足原始约束的违背程度，注意存在约束$1-y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\le {\xi }_i$，这就是常用的软间隔支持向量机。注意到这依旧是一个二次规划问题，因此引入拉格朗日乘子：
$$L=\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m{\xi }_i+\sum _{i=1}^m{\alpha }_i(1-{\xi }_i-y_i(w^T\varphi (x_i)+b))-\sum _{i=1}^m{\mu }_i{\xi }_i$$
求得对偶问题：
$$\underset{\alpha }{\max }\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\kappa (x_i,x_j)$$
约束条件：
$$\begin{array}{rl}& \sum _{i=1}^m{\alpha }_i{y}_i=0\\ & 0\le {\alpha }_i\le C,i=1,...,m\end{array}$$
可以发现比起硬间隔唯一区别就是$\alpha$有了上限$C$。最后由KKT条件下有

• 若 ${\alpha }_i=0$： 则 $y_{i}f(x_i)\ge 1$ 则${\xi }_i=0$。点在间隔边界外，被正确分类。不是支持向量。
• 若 $0<{\alpha }_i<C$： 则 $y_{i}f(x_i)=1$ 则 ${\xi }_i=0$。点恰好在间隔边界上。这些是自由支持向量 ，它们决定了 $b$ 的值。
• 若 ${\alpha }_i=C$： 则 $y_{i}f(x_i)\le 1$ 则 ${\xi }_i\ge 0$。点在间隔边界内部或者被错误分类。这些是有界支持向量 。它们可能是：
  • $0\le y_{i}f(x_i)<1$ 则 ${\xi }_i=1-y_{i}f(x_i)>0$ (在间隔内)
  • $y_{i}f(x_i)<0$则${\xi }_i>1$（被错误分类）

最终的决策边界 $w=\sum {\alpha }_i{y}_i\varphi (x_i)$ 仍然只由 ${\alpha }_i>0$ 的点（即所有支持向量，包括自由的和有界的）决定。

最后软间隔中还有一个神奇的常数$C$没有提到，其实这个常数正是正则化思想的体现。所谓正则化，是一种在机器学习中广泛使用的技术，其主要目的是防止模型过拟合并提高模型的泛化能力。它通过向标准的学习目标（通常是最小化训练误差）中添加一个与模型复杂度相关的惩罚项来实现，这相当于引入了一种对模型复杂度的偏好或约束，引导模型学习到更简单、更具有普适性的规律。

形式上来说，正则化的目标函数通常表现为：
$$mi{n}_{f}C\sum _{i=1}^{N}L(y_i,f({\mathbf{x}}_i))+\Omega (f)$$
这个式子和软间隔目标函数确实类似，但我们先跳出SVM领域，只看这个式子，其中

• ${\sum }_{i=1}^{N}L(y_i,f({\mathbf{x}}_i))$ 称为经验风险，用于描述模型 $f$ 在训练集上的拟合程度（例如，误差或损失的总和），是我们想主要降低的目标
• $\Omega (f)$ 称为正则化项或惩罚项，它度量模型 $f$ 的复杂度，目的是为了让最后训练出来的模型不会过分偏离正则化项
• $C$就很明显是平衡正则化项和经验风向的权重，$C$越小，对模型复杂度的惩罚越重，模型趋向于更简单；反之模型越倾向于拟合训练数据。
  可以明显看出来，对于正则化来说经验风险才是重点，这与SVM的直观感受不符，但不可否认的是SVM也符合这个目标函数，因此也可以拿SVM作为例子。

回到正则化方法中，我们会选择合适的正则化项 $\Omega (f)$ 的形式（这通常基于领域知识或对模型特性的期望），可以限制模型的复杂度，从而降低模型在训练数据上过拟合的风险，进而提高其在未见数据上的泛化能力。上述优化问题称为正则化问题。常用的正则化项 $\Omega (f)$ 包括：

• $L_2$范数正则化：$\Omega (f)=||\mathbf{w}|{|}_2^2$。倾向于使得权重向量 $\mathbf{w}$ 的分量取值比较小且分散（均衡），防止个别权重过大。
• $L_1$范数正则化：$\Omega (f)=||\mathbf{w}|{|}_1$。倾向于产生稀疏的权重向量，即 $\mathbf{w}$ 中许多分量为0。这可以用于特征选择。
• $L_0$范数：$\Omega (f)=||\mathbf{w}|{|}_0$（非零分量的个数）。直接度量稀疏性，但优化困难，通常用 $L_1$ 范数作为其凸近似。

6.4 支持向量回归

接下来我们考虑回归问题，回忆线性回归模型$y={\mathbf{w}}^T\mathbf{x}+b$，我们需要找到一个超平面来最小化所有样本点的预测误差。与传统线性回归不同，支持向量回归（SVR）受SVM启发引入$ϵ$-不敏感带——当样本点落在以预测直线为中心、宽度为$2ϵ$的带状区域内时，不产生任何损失。这种机制通过容许部分偏离直线的样本点，将SVM的间隔思想成功迁移到回归问题中，其核心优势体现在对噪声的不敏感和稀疏解特性上。

现在我们就开始数学部分，我们的目标依旧是找到线性模型的参数$\mathbf{w},b$，只是这一次我们借鉴SVM引入间隔，那么损失函数可以写为：
$$\sum _{i=1}^m{l}_{ϵ}(f({\mathbf{x}}_i)-y_i)$$
其中
$$l_{ϵ}=\{\begin{array}{l}0,if|z|\le ϵ;\\ |z|-ϵ,otherwise\end{array}$$
称为$ϵ$-不敏感损失，考虑正则化，我们希望参数$\mathbf{w}$更平坦，所以引入正则化项$\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$且基于同样的理由——$l_{ϵ}$不是一个好函数，引入松弛变量${\xi }_i,{\hat{\xi }}_i\ge 0$于是有
$$\underset{\mathbf{w},b,{\xi }_i,{\hat{\xi }}_i}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C\sum _{i=1}^m({\xi }_i+{\hat{\xi }}_i)$$
其中

• ${\xi }_i$是衡量超出间隔上边界$f({\mathbf{x}}_i)+ϵ$的量
• ${\hat{\xi }}_i$是衡量超出间隔下边界$f({\mathbf{x}}_i)-ϵ$的量
  而约束条件写为
  $$\{\begin{array}{l}{\xi }_i+ϵ\ge f({\mathbf{x}}_i)-y_i\\ {\hat{\xi }}_i+ϵ\ge y_i-f({\mathbf{x}}_i)\\ {\xi }_i,{\hat{\xi }}_i\ge 0\end{array}$$
  接下来就是拉格朗日乘子法继续发力，得到对偶问题
  $$\underset{\alpha ,\hat{\alpha }}{\max }\sum _{i=1}^m{y}_i({\hat{\alpha }}_i-{\alpha }_i)-ϵ({\hat{\alpha }}_i+{\alpha }_i)-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m({\hat{\alpha }}_i-{\alpha }_i)({\hat{\alpha }}_j-{\alpha }_j){\mathbf{x}}_i^T{\mathbf{x}}_j$$
  满足约束
  $$\begin{array}{rl}& \sum _{i=1}^m({\hat{\alpha }}_i-{\alpha }_i)=0\\ & 0\le {\alpha }_i,{\hat{\alpha }}_i\le C\end{array}$$
  中间步骤对$\mathbf{w}$求导可以得到
  $$\mathbf{w}=\sum _{i=1}^m({\hat{\alpha }}_i-{\alpha }_i){\mathbf{x}}_i$$
  这表明最优的 $w$ 可以表示为输入样本 $x_i$ 的线性组合，系数由拉格朗日乘子决定。重要的KKT条件为
  $$\begin{array}{rl}& {\alpha }_i(w^T{x}_i+b-y_i-ϵ-{\xi }_i)=0\\ & {\hat{\alpha }}_i(y_i-w^T{x}_i-b-ϵ-{\hat{\xi }}_i)=0\\ & (C-{\alpha }_i){\xi }_i=0\\ & (C-{\hat{\alpha }}_i){\hat{\xi }}_i=0\end{array}$$
  由KKT条件，我们可以知道，只有落在间隔边界上和间隔外部的样本其对应的乘子$\alpha$才是非零值，对参数$\mathbf{w}$有贡献，而只有落在间隔边界上的样本（$\xi =0,\alpha \ne 0$）可以求得参数$b$，依旧是取多个这样的样本点求平均。
  综上，只有不落在间隔内部的样本才对模型有贡献，解依旧有稀疏性。最后目标函数依旧是只含有$\mathbf{x}$的内积，可以使用核函数处理。

6.5 核方法

我们之前已经使用过核函数帮助我们用线性方法处理非线性问题了，现在我们更进一步地学习核方法。核方法是一大类用于模式分析的算法。它们的核心思想是：

• 隐式映射到高维空间：通过一个核函数 $\kappa (x,x^{\prime })$，将原始输入空间 $\mathcal{X}$ 中的数据 $x$ 隐式地映射到一个希尔伯特空间 $\mathcal{H}$（通常称为特征空间），这个映射通常表示为 $\varphi :\mathcal{X}\to \mathcal{H}$。

• 核函数计算内积：核函数的关键作用在于，它直接计算了特征空间中两个映射后向量的内积：
  $$\kappa (x,x^{\prime })=⟨\varphi (x),\varphi (x^{\prime }){⟩}_{\mathcal{H}}$$
  这里的 $⟨\cdot ,\cdot {⟩}_{\mathcal{H}}$ 表示特征空间 $\mathcal{H}$ 中的内积。重要的是，我们不需要显式地知道映射 $\varphi$ 的具体形式，也不需要计算 $\varphi (x)$ 的坐标，只需能计算 $\kappa (x,x^{\prime })$ 的值即可。

• 在特征空间中应用线性方法：核方法的基本策略是在高维特征空间 $\mathcal{H}$ 中应用线性的模式分析方法（如分类、回归、降维等）。由于核函数允许我们计算特征空间中的内积，任何仅依赖于数据点之间内积的线性算法，都可以通过将内积替换为核函数，转化为一个在原始空间中表现为非线性的算法。

回顾 SVM 中使用核函数的部分，应该更容易理解这一思想。

事实上许多核方法的理论基础是理论定理，他指出对于一个形如
$$\underset{h\in \mathcal{H}}{\min }l(h(x_1),\dots ,h(x_m))+\Omega (||h|{|}_{\mathcal{H}}^2)$$
找出最优解$h(\mathbf{x})$的问题，其中$||h|{|}_{\mathcal{H}}^2$是函数 $h$ 在 RKHS $\mathcal{H}$ 中的范数 (norm) 平方，只要满足

• $\Omega (\cdot )$ 是一个定义在 $[0,\infty )$的单调递增函数
• 损失函数$l$非负
  那么最优解一定可以写为
  $$h^{\ast }(\mathbf{x})=\sum _{i=1}^m{\alpha }_i\kappa (\mathbf{x},{\mathbf{x}}_i)$$
  书上介绍了用LDA（第三章）基于核方法处理非线性问题，我这里就不赘述了。