模式识别（非线性分类器）

本文介绍了模式识别的非线性分类器，主要包括近邻法分类器、支持向量机（SVM）、决策树，最后介绍分类器的集成。

---

• 1. 引言
• 2. 近邻法分类器
  • 2.1. 最近邻法
  • 2.2. K 近邻法
  • 2.3. KD 树
  • 2.4. 构造 KD 树
• 3. 支持向量机（SVM）
  • 3.1. 线性支持向量机
    • 3.1.1. 硬间隔 SVM 优化问题
    • 3.1.2. SVM 优化对偶问题
    • 3.1.3. 软间隔 SVM 优化问题
  • 3.2. 非线性支持向量机
    • 3.2.1. 核函数（kernel）
• 4. 参考文献

1. 引言

在介绍线性分类器时，我们介绍过大多数线性分类器在样本线性可分的情况下可以取得很好的效果。但很多情况下，类别之间的分类边界并不是线性的，如果依然使用线性分类器也能勉强使用，但一种更好的选择是使用更复杂的非线性函数来描述分类。

2. 近邻法分类器

2.1. 最近邻法

对于一个新样本，把它逐一与已知样本进行比较，找出距离新样本最近的已知样本，并以该样本的类别作为新样本的类别。其严格的数学描述如下：

假定有 $c$ 个类别的模式识别问题，每类包含样本个数为 $N_i,i=1,2,\cdots,c$。定义两个样本之间的距离度量 $\delta(x_i,x_j)$（比如可以采用欧式距离 $\delta(x_i,x_j)=\Vert x_i - x_j \Vert$），则对于任意未知新样本 $x$，可以规定类 $w_i$ 的判别函数为：

\[g_i(x) = \min_k \delta(x, x_i^{(k)}), \; k =1,2,\cdots,N_i\]

其中 $x_k$ 是类别 $w_i$ 中的第 $k$ 个样本。

对于每个类别都求出其判别函数，那么决策规则为

\[x\in w_i\quad\text{if}\quad i=\arg\min_i g_i(x),\; i=1,2,\cdots,c\]

可以看出，最近邻法的思想很简单，新样本离谁最近，就把新样本判为最近的样本所属的类别。但在很多情况下，把决策建立在一个最近的样本上有一定风险，尤其是当数据分布复杂或数据中噪声严重时。如下图所示：

图中，黄色圆点为新样本（已知其为蓝色类别），但其最近邻为红色圆点样本。很明显，该红色样本是一个野值，其深入到了蓝色样本所属类别的区域。如果以最近邻的类别作为新样本的类别，那么显会导致分类错误。

为了更严格地分析最近邻法的错误率，我们需要进行一定的数学推导。当近邻法中训练样本的数量无限多（$N\rightarrow \infty$）时，某待分类的未知样本 $x$ 的最近邻在极限意义上就是其自身，此时最近邻法分类正确的条件为：样本与它最近邻都属于同一类别。即分类正确率为

\[\sum_{i=1}^c P(w_i\vert x)P(w_i\vert x) = \sum_{i=1}^c P(w_i\vert x)^2\]

对应的错误率为

\[\lim_{N\rightarrow\infty} P_N(e\vert x) = 1 - \sum_{i=1}^c P(w_i\vert x)^2\]

则平均错误率为

\[\begin{aligned} P &= \lim_{N\rightarrow \infty}P(e) =\lim_{N\rightarrow \infty} \int P_N(e\vert x)p(x)dx\\ &= \int \lim_{N\rightarrow \infty} P_N(e\vert x)p(x)dx\\ &= \int \left(1 - \sum_{i=1}^c P(w_i\vert x)^2\right)p(x)dx \end{aligned}\]

$P$ 又被称为最近邻法的渐进平均错误率，是 $P_N(e)$ 在 $N\rightarrow \infty$ 的极限。

为了更进一步了解最近邻法错误率的上界和下界，我们可以将其和理论上具备最优错误率的贝叶斯错误率进行比较。已知 $c$ 分类问题的贝叶斯错误率为

\[P^\star = \int[1- \max_i P(w_i \vert x)]p(x)\text{d}x,\; i=1,2,\cdots,c\]

记 $m = \arg\max_i P(w_i\vert x)$，则

\[P^\star = \int[1- P(w_m\vert x)]p(x)\text{d}x\]

因此，比较最近邻错误率和贝叶斯错误率的关键在于衡量以下两者的大小关系：

\[P(w_m\vert x) \quad \text{和} \quad \sum_{i=1}^c P(w_i\vert x)^2\]

二者作差

\[\begin{aligned} P(w_m\vert x) - \sum_{i=1}^c P(w_i\vert x)^2 &= P(w_m\vert x) -P(w_m\vert x)^2 - \sum_{i\neq m} P(w_i\vert x)^2\\ &= P(w_m\vert x)(1-P(w_m\vert x)) - \sum_{i\neq m} P(w_i\vert x)^2\\ &= P(w_m\vert x)\sum_{i\neq m} P(w_i\vert x) - \sum_{i\neq m} P(w_i\vert x)^2\\ &= \sum_{i\neq m} P(w_i\vert x)[P(w_m\vert x) - P(w_i\vert x)]\\ &\geq 0 \end{aligned}\]

至此我们确定了最近邻法的错误率下界为贝叶斯错误率，即

\[P^\star \leq P\]

为了求得最近邻法的错误率上界，需要借助柯西-施瓦茨不等式。

柯西-施瓦茨不等式：对于任意两个实值随机变量 $a$ 和 $b$，有

\[\left( \sum_{i=1}^n a_ib_i \right)^2 \leq \sum_{i=1}^n a_i^2 \sum_{i=1}^n b_i^2\]

推论为

\[n\sum_{i=1}^n a_i^2 \geq \left( \sum_{i=1}^n a_i \right)^2\]

对于最近邻错误率有

\[\begin{aligned} \sum_{i\neq m} P(w_i\vert x)^2 &\geq \frac{1}{c-1}\left(\sum_{i\neq m} P(w_i\vert x)\right)^2\\ &= \frac{1}{c-1}\left(1 - P(w_m\vert x)\right)^2 \end{aligned}\]

左右两边同时补上 $P(w_m\vert x)^2$ 有

\[\begin{aligned} \sum_{\textcolor{red}{i=1}}^c P(w_i\vert x)^2 &\geq \frac{1}{c-1}\left(1 - P(w_m\vert x)\right)^2 + \textcolor{red}{P(w_m\vert x)^2}\\ \textcolor{green}{1 - }\sum_{i=1}^c P(w_i\vert x)^2 &\textcolor{green}{\leq 1 - }\frac{1}{c-1}\left(1 - P(w_m\vert x)\right)^2 + \textcolor{red}{[1-(1-P(w_m\vert x))]^2} \end{aligned}\tag{1}\]

将上式右侧展开有

\[\begin{aligned} &1-\frac{1}{c-1}\left(1 - P(w_m\vert x)\right)^2 - [1-(1-P(w_m\vert x))]^2\\ =& 1 - \frac{1}{c-1}\left(1 - P(w_m\vert x)\right)^2 -[1-2(1-P(w_m\vert x)) + (1-P(w_m\vert x))^2]\\ =& 1 - \frac{1}{c-1}\left(1 - P(w_m\vert x)\right)^2 - 1 + 2(1-P(w_m\vert x)) - (1-P(w_m\vert x))^2\\ =& (-\frac{1}{c-1}-1)\left(1 - P(w_m\vert x)\right)^2 + 2(1-P(w_m\vert x))\\ =& (1-P(w_m\vert x))[2-(1+\frac{1}{c-1})(1-P(w_m\vert x))]\\ =& (1-P(w_m\vert x))\left[2-\frac{c}{c-1}(1-P(w_m\vert x))\right]\\ \end{aligned}\tag{2}\]

将式（2）代回式（1），左右同时积分有

\[\begin{aligned} 1-\sum_{i=1}^c P(w_i\vert x)^2 &\leq (1-P(w_m\vert x))\left[2-\frac{c}{c-1}(1-P(w_m\vert x))\right]\\ \int \left(1-\sum_{i=1}^c P(w_i\vert x)^2\right)p(x)\text{d}x &\leq \int [1-P(w_m\vert x)]p(x)\text{d}x\left[2-\frac{c}{c-1}\int [1-P(w_m\vert x)]\text{d}x\right]\\ \end{aligned}\]

因此我们得到最近邻法的错误率上界为

\[P \leq P^\star \left[2-\frac{c}{c-1}P^\star\right]\]

经过数学推导可知，最近邻的渐进错误率最坏不会超过两倍的贝叶斯错误率，而最好则有可能接近或达到贝叶斯错误率。

最后分析等号成立的条件，即最近邻法的错误率等于贝叶斯错误率的条件。

• 对于下界，当且仅当 $P(w_m\vert x) = P(w_i\vert x)$ 时取到等号，此时 $P(w_m\vert x) = P(w_i\vert x) = 1/c$，即所有类别的后验概率相等，不管是最近邻分类器还是贝叶斯分类器都相当于瞎猜，二者因此错误率都一样。

• 对于上界，当且仅当 $P(w_m\vert x) = 1$ 时取到等号，此时 $P(w_m\vert x) = 1$，即后验概率最大的类别的后验概率为 1，表明样本全为某一类，此时贝叶斯分类器和最近邻分类器都能 100% 做出正确决策。

2.2. K 近邻法

为了解决最近邻法容易受到噪声和野值影响的问题，简单且符合直觉的想法是可以考虑使用 $k$ 近邻法，即找出距离新样本最近的 $k$ 个样本，然后以这 $k$ 个样本中出现次数最多的类别作为新样本的类别。

根据 $k$ 值选取的不同，可做出如下讨论：

• $k$ 值越小，模型复杂度越高，容易发生过拟合。极端情况 $k=1$ 退化为最近邻法，如果恰好遇到噪声，就会完全错误； 随着 $k$ 值增大，模型泛化能力也增大，但丢失的信息也增多。$k$ 值的增大就意味着整体的模型变得简单；
• $k=N$，则任意新输入样例的分类就等于训练样例中样本数最多的分类，此时无论输入样本是什么，都只是简单的预测它属于在训练样本中最多的类。

对于 $k$ 近邻法，其错误率的上界和下界与最近邻法类似，但是 $k$ 近邻法的错误率上界和下界都比最近邻法的要好。

$k$ 近邻法的特点概括如下：

• 优点：可以解决几乎所有分类问题，概念简单未经优化，分类器设计容易，且错误率并不高；
• 缺点：计算量大，内存开销大，特别依赖快速搜索算法。

2.3. KD 树

K-近邻算法是机器学习中最简单的算法之一，如果训练样本过大，则传统的遍历全样本寻找 K-近邻的方式将导致性能的急剧下降。为了优化效率，不同的训练数据存储结构被纳入到实现方式之中。

KD 树（K-Dimension Tree）是一种对 $k$ 维空间中的实例点进行存储以便对其进行快速检索的树形数据结构，主要用于高效地组织和搜索多维空间中的点。

2.4. 构造 KD 树

构造 KD 树相当于不断地用垂直于坐标轴的超平面将 $k$ 维空间切分，构成一系列的 $k$ 维超矩形区域。KD 树的每个节点对应于一个 $k$ 维超矩形区域。通常，依次选择坐标轴对空间划分，选择训练样本点在选定坐标轴上的中位数为切分点，这样得到的 KD 树是是平衡的。

以样本 $a = {(2,3)^\top,(5,4)^\top,(9,6)^\top,(4,7)^\top,(8,1)^\top,(7,2)^\top }$ 为例，构造 KD 树的过程如下：

• 计算方差，选择方差最大的维度开始，本例中为 $x$ 轴，之后按照维度顺序进行切分。有时为了简便起见，直接按照维度顺序切分而不计算方差；
• 选择 $x$ 轴，对 $a$ 中的样本按照 $x$ 轴坐标进行排序，得到 $a_x = {(2,3)^\top,(4,7)^\top,(5,4)^\top,(7,2)^\top,(8,1)^\top,(9,6)^\top }$，选择中位数 $m = (5,4)^\top$ 作为切分点，得到左右子树 $a_{x_l} = {(2,3)^\top,(4,7)^\top,(7,2)^\top }$ 和 $a_{x_r} = {(8,1)^\top,(9,6)^\top }$；
• 选择 $y$ 轴，对 $a_{x_l}$ 中的样本按照 $y$ 轴坐标进行排序，得到 $a_{x_l,y} = {(2,3)^\top,(7,2)^\top,(4,7)^\top }$，选择中位数 $m = (7,2)^\top$ 作为切分点，得到左右子树 $a_{x_l,y_l} = {(2,3)^\top }$ 和 $a_{x_l,y_r} = {(4,7)^\top }$；
• 如此循环直至所有样本都被划分到叶子节点。

得到的划分如下图所示。

形成的 KD 树如下图所示。

完成 KD 树的构建只是第一步，接下来需要对 KD 树进行搜索。

查询时，从根节点开始，沿着与查询点在当前维度上最接近的方向遍历树。到达叶子节点或分裂超平面时，会检查另一个子空间是否有更近的点，这依赖于当前点到查询点的距离和超平面的距离。这一过程重复，直到找到最近的点或达到预定的搜索深度。

进行最近邻搜索时，KD 树利用其结构减少搜索空间，具体步骤如下：

• 从根节点出发，根据构造 KD 树时的切分规则（切分维度顺序和左小右大），递归地向下访问 KD 树的节点，直到到达叶子节点；
• 跟踪最近点：记录遍历过程中遇到的最近点，并在每个节点处计算是否可能存在更近的点在另一侧的子树中；
• 回溯：递归地向上回退，检查每个节点的另一侧是否可能存在更近的点，直到整个树都被搜索完毕。

对于上述实例，如果查询点为 $(2,4.5)^\top$，则搜索过程如下：

• 找寻最近点：
  • 从根节点开始，根据 $x$ 轴坐标，查询点 $(2,4.5)^\top$ 在 $x$ 轴上小于 $(7,2)^\top$，因此向左子树搜索；
  • 在左子树中，根据 $y$ 轴坐标，查询点 $(2,4.5)^\top$ 在 $y$ 轴上大于 $(5,4)^\top$，因此向右子树搜索；
  • 在右子树中，查询点 $(2,4.5)^\top$ 的最近点为 $(4,7)^\top$，计算二者距离为 $3.2$；
• 回溯：
  • 回溯上层 $(5,4)^\top$，计算距离为 $3.04$，比 $(4,7)^\top$ 更近，更新最近点为 $(5,4)^\top$；
  • 以 $3.04$ 做圆；此圆与 $(5,4)^\top$ 所切分的上下两个平面相交，需要检查$(5,4)^\top$ 的另外侧；
  • $(5,4)^\top$ 的另一侧子节点为 $(2,3)^\top$ ，与之距离为 $1.5$，更新最近点为 $(2,3)^\top$；
  • 由于 $(2,3)^\top$ 为叶子节点，回溯至 $(7,2)^\top$，确认与 $(7,2)^\top$ 切分的右子平面无关；
  • 抵达根节点，回溯结束。最终确定最近点为 $(2,3)^\top$。

进一步，给出使用 KD 树进行 K 近邻搜索的伪代码：

• 输入查询节点 $x$；
• 创建 $k$ 个元素的空列表 $L$，用于存储 $x$ 的最近邻点和相应距离；
• （1） 根据 $x$ 的坐标和当前节点切分规则（左小右大）向下搜索；
• （2） 到达底部节点，将其标记为访问过，如果 $L$ 中有空位且叶子节点与 $x$ 的距离小于 $L$ 中的最大值，则用叶子节点替换其中距离最大值对应节点；
• （3） 如果当前节点不是根节点，执行 （4）；反之，输出 $L$ 算法结束；
• （4） 向上回溯一个节点，抵达 $p$。如果 $p$ 未被访问过，将其标记为访问过，并执行后续子步骤；如果访问过，则再次执行 （4）；
  • （a） 如果 $L$ 有空位，则将 $p$ 加入 $L$；反之，如果 $L$ 已满 但 $p$ 与 $x$ 的距离小于 $L$ 中的最大值，则用 $p$ 替换 $L$ 中的最大值；
  • （b） 计算 $x$ 与 $p$ 的切分线的距离，记为 $d$；如果 $d$ 小于 $L$ 中的最大值，或者 $L$ 中有空位，则访问 $p$ 的另一侧子节点，回到 （1） 执行；反之，如果 $d$ 大于 $L$ 中的最大值且$L$ 已满，则切分线另一边不会有更近的点，返回 （3）。

KD 树的缺点：

• 维度诅咒：随着维度的增加，KD树的效率急剧下降。这是因为高维空间中，数据点间的距离变得非常相似，难以通过简单的分割有效区分，这种现象被称为“维度诅咒”。
• 平衡问题：KD树的性能对分割轴的选择很敏感，如果数据分布不均匀或者选择的分割策略不当，容易导致树的不平衡，进而影响搜索效率。尽管有一些平衡策略，但完全避免不平衡较难。
• 维护成本：在动态数据集中，频繁的插入和删除操作可能导致KD树结构失衡，需要花费额外的时间来重新平衡树，这可能抵消掉一部分查询效率的优势。
• 不适合高度倾斜或复杂数据分布：当数据分布呈现高度偏斜或具有复杂模式时，简单地按照中位数分割可能不是最优选择，这会导致搜索效率降低。在这种情况下，更复杂的树结构，如球树（Ball Tree）或覆盖树（Cover Tree），可能提供更好的性能。

3. 支持向量机（SVM）

支持向量机（Support Vector Machines，SVM）被提出于1964年，20世纪90年代后得到快速发展，并衍生出一系列改进和扩展算法。在解决小样本情况下的机器学习问题和高维、非线性问题中表现出较为优异的效果。

SVM 是基于线性可分的最优分类面提出的，最优分类面的定义保证了在样本一定的情况下，两类样本间的距离最大。注意到，截至目前讨论的 SVM 似乎表现为一个线性分类器而不是非线性分类器，但后面会介绍到，SVM 的非线性分类能力是通过引入核函数来实现的。

3.1. 线性支持向量机

前面介绍线性分类器时，我们介绍了感知准则，并提到了线性可分性的概念。假设 $D_0$ 和 $D_1$ 是 $n$ 维欧式空间中的两个点集，$D_0$ 和 $D_1$ 线性可分的条件是存在一个超平面 $H$，使得 $D_0$ 和 $D_1$ 分别位于超平面的两侧。即存在一个向量 $\boldsymbol{w}$ 和一个标量 $b$，使得对于任意的 $x\in D_0$ 和 $y\in D_1$，都有：

\[\begin{aligned} \boldsymbol{w}^\top x + b &> 0,\; x\in D_0\\ \boldsymbol{w}^\top y + b &< 0,\; y\in D_1 \end{aligned}\]

对于线性可分的样本，感知准则可以找到一个超平面将两类样本完全分开，但并不能保证该超平面是最优的。

SVM 可以看作感知准则的一种改进，SVM 的目标是找到一个超平面将两类样本分开，并且使得两类样本到超平面的距离最（标量）大，从而引入了某种最优性。

3.1.1. 硬间隔 SVM 优化问题

以二分类为例，假设样本集为 $S={(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)}$，其中 $x_i$ 是样本，$y_i$ 是样本的类别标签。假设样本集线性可分，存在一个超平面 $H$ 将两类样本完全分开。假设超平面 $H$ 的法向量为 $\boldsymbol{w}$，超平面到原点的距离为 $b$，则超平面可以表示为：

\[\boldsymbol{w}^\top x + b = 0\]

那么判别函数可写为

\[\begin{cases} \boldsymbol{w}^\top x_i + b > 0, y = 1\\ \boldsymbol{w}^\top x_i + b < 0, y= -1 \end{cases}\]

合并为简单形式，则线性可分的条件为

\[y_i(\boldsymbol{w}x_i+b) \geq 0, \forall i=1,2,\cdots,N\]

根据前述 SVM 目标，我们希望求解如下优化问题：

\[\begin{aligned} \max_{\boldsymbol{w},b} &\quad \text{margin} (\boldsymbol{w},b)\\ s.t. &\quad y_i(\boldsymbol{w}^\top x_i+b) > 0, \forall i=1,2,\cdots,N \end{aligned}\]

上述优化问题中唯一不确定的地方就是间隔（margin）的定义。间隔被定义为样本中离决策面最近的那些样本到决策面的距离。设 $d_i$ 为样本 $x_i$ 到超平面的距离（标量），则有：

\[d_i = \frac{\vert \boldsymbol{w}^\top x_i + b\vert}{\Vert \boldsymbol{w} \Vert}\]

那么间隔定义为

\[\text{margin}(w,b) = \min_{i} d_i\]

则 SVM 的优化问题变为

\[\begin{aligned} \max_{\boldsymbol{w},b} \min_{i} &\quad\frac{\vert \boldsymbol{w}^\top x_i + b\vert}{\Vert \boldsymbol{w} \Vert}\\ s.t. &\quad y_i(\boldsymbol{w}^\top x_i+b) > 0, \forall i=1,2,\cdots,N \end{aligned}\]

注意到，约束条件表明 $y_i$ 和 $\boldsymbol{w}x_i+b$ 同号且二者相乘恒大于零，那么可安全地将优化目标函数的绝对值打开，得到

\[\begin{aligned} \max_{\boldsymbol{w},b} \min_{i} &\quad\frac{\textcolor{green}{y_i(\boldsymbol{w}^\top x_i + b)}}{\Vert \boldsymbol{w} \Vert}\\ s.t. &\quad y_i(\boldsymbol{w}^\top x_i+b) > 0, \forall i=1,2,\cdots,N \end{aligned}\]

观察优化目标函数中，不同优化方向的作用对象，可移项如下

\[\begin{aligned} \max_{\boldsymbol{w},b}&\; \textcolor{blue}{\frac{1}{\Vert \boldsymbol{w} \Vert}} \; \min_{i} \; y_i(\boldsymbol{w}^\top x_i + b)\\ s.t. &\quad y_i(\boldsymbol{w}^\top x_i+b) > 0, \forall i=1,2,\cdots,N\\ \end{aligned}\]

既然约束条件要求 $y_i(\boldsymbol{w}^\top x_i+b) > 0$，那么一定有

\[\exists \gamma > 0,\; \min_i y_i(\boldsymbol{w}x_i+b) =\gamma\]

此处 $\gamma$ 被称为 函数间隔。引入函数间隔后，优化问题变为如下形式

\[\begin{aligned} \max_{\boldsymbol{w},b}&\; \textcolor{blue}{\frac{1}{\Vert \boldsymbol{w} \Vert}} \; \min_{i} \; y_i(\boldsymbol{w}^\top x_i + b)\\ s.t. &\quad y_i(\boldsymbol{w}^\top x_i+b) \textcolor{red}{\geq \gamma}, \forall i=1,2,\cdots,N\\ \text{or}\quad s.t.\quad \textcolor{green}{\min_i}&\quad \textcolor{green}{y_i(\boldsymbol{w}^\top x_i+b) = \gamma}, \forall i=1,2,\cdots,N \end{aligned}\]

将条件代入目标函数，消去 $\min_i$ 项，有

\[\begin{aligned} \max_{\boldsymbol{w},b}&\quad \frac{\textcolor{red}{\gamma}}{\Vert \boldsymbol{w} \Vert}\\ s.t. &\quad y_i(\boldsymbol{w}^\top x_i+b) \textcolor{red}{\geq \gamma}, \forall i=1,2,\cdots,N \end{aligned}\]

注意到当 $\boldsymbol{w},b$ 发生变化（如分别扩大 2 倍）也会导致函数间隔发生变化（同样扩大两倍）。虽然这种操作不会改变最优解，但会产生一个等价的优化问题。为了避免这种情况，不妨令 $\gamma = 1$，优化问题变为

\[\begin{aligned} \max_{\boldsymbol{w},b}&\quad \frac{1}{\Vert \boldsymbol{w} \Vert}\\ s.t. &\quad y_i(\boldsymbol{w}^\top x_i+b) \geq 1, \forall i=1,2,\cdots,N \end{aligned}\]

这一事实给了我们另一个启示，我们应该对法向量 $\boldsymbol{w}$ 加一个约束，使得间隔固定不变，此时的间隔为 几何间隔。

最后，利用如下等价性

\[\max_{\boldsymbol{w},b} \frac{1}{\Vert \boldsymbol{w}\Vert} = \min_{\boldsymbol{w},b} \Vert \boldsymbol{w}\Vert^2 = \frac{1}{2}\min_{\boldsymbol{w},b} \boldsymbol{w}^\top \boldsymbol{w}\]

得到最终优化问题的描述

\[\begin{aligned} \min_{\boldsymbol{w},b} &\quad \frac{1}{2} \boldsymbol{w}^\top \boldsymbol{w}\\ s.t. &\quad y_i(\boldsymbol{w}^\top x_i+b) \geq 1, \forall i=1,2,\cdots,N \end{aligned}\]

上述优化问题是一个包含 $N$ 个不等式约束的二次凸优化问题。

对于线性可分的样本，所有样本一定能够满足上面的不等式约束，也即所有样本都可以位于间隔的两侧，不存在错分的情况，所以上述优化问题一定有解。我们称上述优化问题为 硬间隔 SVM 优化问题。对应的图示如下

3.1.2. SVM 优化对偶问题

对于一个带约束的优化问题，采用拉格朗日乘子法转化为一个无约束优化问题，拉格朗日函数如下

\[L(w,b,\lambda) = \frac{1}{2}w^\top w + \sum_{i=1}^N\lambda_i(1-y_i(w^\top x_i+b)),\; \lambda_i \geq 0\]

优化问题变为

\[\begin{aligned} \min_{w,b}\quad & \max_\lambda L(w,b,\lambda)\\ s.t. & \quad \lambda_i \geq 0, \forall i=1,2,\cdots,N\\ \end{aligned}\]

拉格朗日乘子法变换后的优化问题与原始优化问题的等价性可如下简单说明：

定义 $\delta = 1-y_i(w^\top x_i+b)$，SVM 优化问题的约束条件变为

\[\delta_i \leq 0\]

整个 $(w,b)$ 空间可划分为两个部分，不满足约束 （$\delta > 0$） 和 满足约束 （$\delta \leq 0$）。

• 对于 $\delta > 0$，约束被违反，可以取 $\lambda \to \infty$ 使得优化目标

\[\max_\lambda L(w,b,\lambda) = \frac{1}{2}w^\top w + \infty = +\infty\]

• 对于 $\delta \leq 0$，约束被满足，可以取$\lambda = 0$ 使得优化目标取到最大值

\[\max_\lambda L(w,b,\lambda) = \frac{1}{2}w^\top w + 0 = \frac{1}{2}w^\top w\]

综上，拉格朗日乘子法的优化问题

\[\min_{w,b}\max_\lambda L(w,b,\lambda) = \min_{w,b} [+\infty,\;\frac{1}{2}w^\top w] = \min_{w,b} \frac{1}{2}w^\top w\]

与原始优化问题等价，其中外层 $\min_{w,b}$ 会自动忽略不满足约束的解。

上述优化问题的对偶问题为（交换 $\max$ 与 $\min$）

\[\begin{aligned} \max_\lambda \min_{w,b} &\quad L(w,b,\lambda)\\ s.t. &\quad \lambda_i \geq 0, \forall i=1,2,\cdots,N \end{aligned}\]

关于为何 SVM 要引入原问题的对偶问题，是因为：

• 支持向量的稀疏性：

在对偶问题中，拉格朗日乘子 $\lambda_i$ 只有在支持向量上才会非零，而支持向量的数量通常远小于总样本数。这意味着在分类时，只需要计算支持向量与查询点的内积，大大减少了计算量。

• 高维空间的计算效率：

如果直接求解原问题，分类时需要计算 $w^\top x$，其中 $w$ 是一个高维向量（维度为 $d$）。而在对偶问题中，分类只需要计算支持向量与查询点的内积 $\sum \lambda_i y_i \langle x_i, x \rangle$，这可以通过核函数高效完成，避免直接处理高维向量。

• 核函数的引入：

对偶问题的形式天然适合引入核函数，将数据映射到高维空间进行非线性分类，而无需显式计算高维空间中的坐标。这是 SVM 能够处理非线性问题的关键。

注意原问题和对偶问题存在如下关系

\[\min_{w,b}\max_\lambda L(w,b,\lambda) \geq \max_\lambda \min_{w,b} L(w,b,\lambda)\]

在优化理论中，原始问题（Primal Problem）和对偶问题（Dual Problem）之间存在一定的关系，而 KKT（Karush-Kuhn-Tucker）条件 是连接两者的桥梁。对于支持向量机（SVM）的优化问题，原始问题和对偶问题之间满足 弱对偶性（Weak Duality），而在一定条件下（如凸优化+Slater条件），它们还满足 强对偶性（Strong Duality），即原始问题的最优值等于对偶问题的最优值。此时，KKT条件成为取等号的充要条件。

KKT 条件，$\forall i=1,2,\cdots,N$，有

\[\begin{aligned} \frac{\partial L}{\partial w} = 0,\frac{\partial L}{\partial b} = 0,\frac{\partial L}{\partial \lambda} = 0\quad \text{梯度可行性}\\ \lambda_i(1-y_i(w^\top x_i+b))=0\quad \text{互补松弛性}\\ \lambda_i \geq 0\quad \text{对偶可行性}\\ 1-y_i(w^\top x + b)\leq 0\quad \text{原始可行性}\\ \end{aligned}\]

求解此对偶问题，根据梯度可行性条件，目标函数首先对 $b$ 求偏导令其为零，有

\[\frac{\partial L}{\partial b} = 0\Rightarrow \sum_{i=1}^N\lambda_i y_i = 0\\\]

将其代入目标函数进行化简，有

\[\begin{aligned} L(w,b,\lambda) &= \frac{1}{2}w^\top w + \sum_{i=1}^N\lambda_i(1-y_i(w^\top x_i+b))\\ &= \frac{1}{2}w^\top w + \sum_{i=1}^N \lambda_i - \sum_{i=1}^N \lambda_i y_i w^\top x_i \end{aligned}\]

简化后的目标函数对 $w$ 求偏导令其为零，得到最优参数 $w^\star$ 的形式

\[\frac{\partial L}{\partial w} = w - \sum_{i=1}^N \lambda_i y_i x_i = 0\Rightarrow w= \sum_{i=1}^N \lambda_i y_i x_i\]

将其代入目标函数进行进一步化简，有

\[\begin{aligned} L(w,b,\lambda) =& \frac{1}{2}(\sum_{i=1}^N\lambda_i y_i x_i)^\top (\sum_{i=j}^N\lambda_j y_j x_j)+ \sum_{i=1}^N \lambda_i\\ & - \sum_{i=1}^N \lambda_i y_i (\sum_{i=j}^N \lambda_j y_j x_j)^\top x_i\\ =&\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \lambda_i \lambda_j y_i y_j x_i^\top x_j + \sum_{i=1}^N \lambda_i\\ & - \sum_{i=1}^N\sum_{j=1}^N \lambda_i \lambda_j y_i y_j x_j^\top x_i\\ =& -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \lambda_i \lambda_j y_i y_j x_i^\top x_j + \sum_{i=1}^N \lambda_i \end{aligned}\]

下面继续确定最优参数 $b^\star$ 的形式。根据 KKT 条件中的互补松弛条件、对偶可行条件、原始可行条件进行分析

\[\begin{aligned} \lambda_i(1-y_i(w^\top x_i+b))=0\\ \lambda_i \geq 0\\ 1-y_i(w^\top x + b)\leq 0\\ \end{aligned}\]

对第一条等式进一步讨论，

• 第一种情况，肯定存在某些样本点 $(x_k, y_k)$ 使得 $y_i(w^\top x + b) = 1$，这些样本点就是距离分类面最近的那些样本点，被称为 支持向量（Support Vector）。此时对 $\lambda_i$ 没有额外约束。对于任意一个支持向量，有

  \[\begin{aligned} y_k(w^\top x_k + b) &= 1\\ y_k^2(w^\top x_k + b) &= y_k \end{aligned}\]

  考虑到 $y_k^2 = 1$，则可以得到最优参数 $b^\star$ 的形式

  \[b^\star = y_k-w^\top x_k= y_k-\sum_{i=1}^N \lambda_i y_i x_i^\top x_k\]

• 第二种情况，其他样本距离分类面更远，因此 $y_i(w^\top x + b) > 1$，那么第一条等式的充要条件必须要求$\lambda_i = 0$。也就是说，只有当样本是支撑向量时对应的 $\lambda_i \neq 0$，否则 $\lambda = 0$。这将极大简化 $w^\star,b^\star$ 的计算。

至此，我们已经确定了内层优化 $\min_{w,b}$ 的最优解，剩余的优化问题如下

\[\begin{aligned} \max_\lambda &\quad -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \lambda_i \lambda_j y_i y_j x_i^\top x_j + \sum_{i=1}^N \lambda_i\\ s.t. &\quad \lambda_i \geq 0,\;\sum_{i=1}^N\lambda_i y_i = 0,\; \forall i=1,2,\cdots,N \end{aligned}\]

这个问题是针对拉格朗日乘子 $\lambda$ 进行优化，我们需要求一个 $N$ 元函数的受不等式约束的极值问题。当 $N$ 很大的时候，这个问题就很难求解。我们需要借助 序列最小化算法（Sequential Minimal Optimization，SMO），将问题简化为，每次只变动两个参数，记作 $\alpha_i,\alpha_j$，与此同时固定其余所有的参数，问题就能转变为一个一元二次函数求极值问题，最终可以求解得到所有的 $\lambda_i$，具体求解略。

之所以选择变动两个参数，是因为我们有限制条件

\[\sum_{i=1}^N\lambda_i y_i = 0\]

如果仅变动一个参数，那么这个参数实际上可以由其他参数唯一确定。

关于 SMO 算法的详细讨论，可以参考：https://zhuanlan.zhihu.com/p/367578887

最后将优化问题的解列写如下

\[\begin{aligned} w^\star &= \sum_{i=1}^N \lambda_i y_i x_i\\ b^\star &= y_k-\sum_{i=1}^N \lambda_i y_i x_i^\top x_k \end{aligned}\]

得到 SVM 的判别函数 如下

\[f(x) = \text{sign}({w^\star}^\top x + b^\star)\]

并且知道 $w^\star,b^\star$ 仅是 支持向量 的线性组合（因为 $\lambda_i$ 已只有在样本为支持向量时才不为零）。所以 SVM 训练完成后，大部分的训练样本都不需要保留，最终的分类模型仅与支持向量有关。

3.1.3. 软间隔 SVM 优化问题

前面一直假定训练样本在样本空间或特征空间线性可分，即存在一个超平面将不同类的样本完全划分开。但现实中，很难确定使得训练样本在特征空间中线性可分。缓解该问题的办法是允许支持向量机出错。其优化问题如下

\[\begin{aligned} \min_{\boldsymbol{w},b} &\quad \frac{1}{2} \boldsymbol{w}^\top \boldsymbol{w} + \text{loss}\\ s.t. &\quad y_i(\boldsymbol{w}^\top x_i+b) \geq 1, \;\forall i=1,2,\cdots,N \end{aligned}\]

$\text{loss}$ 选取可以有以下几种形式，第一种是引入 $0/1$ 计数函数作为惩罚项，每当有一个样本不满足约束则计数加 $1$，最后寻找参数 $(w,b)$ 使得包含计数的损失函数最小

\[\begin{aligned} \text{loss} &= \sum_{i=1}^N \text{I}\{1-y_i(\boldsymbol{w}^\top x_i+b),0\}, \;\forall i=1,2,\cdots,N\\ \text{where I} &= \begin{cases} 0,\;\text{if}\;1-y_i(\boldsymbol{w}^\top x_i+b) \leq 0 \\ 1,\;\text{if}\;1-y_i(\boldsymbol{w}^\top x_i+b) > 0 \;\text{违背约束} \end{cases} \end{aligned}\]

但 $0/1$ 计数函数对参数 $w$ 而言是不连续的，不便于优化计算，所以我们一般不采用上述方法。我们希望能找到一个连续函数来刻画出错的情况。一种可选的函数称为 hinge loss，同时引入 $C$ 作为惩罚参数

\[\text{loss} = C\sum_{i=1}^N\max\{ 0, 1-y_i(\boldsymbol{w}^\top x_i+b) \}\]

可以看出，hinge loss 在约束满足时取值为0，在约束不满足时取值即为约束的正值，两个区间的边界处的函数值是连续的。引入这个惩罚项后，假设有样本不满足约束，我们通过优化带上述惩罚项的目标函数，也希望尽可能使得不满足约束的样本带来的影响（对约束的违背程度）尽可能小。

虽然函数取值已经连续了，但由于存在 $\max$ 算符，在实际使用时仍然不太方便。这里把 hinge loss 单独定义为一个变量 $\xi_i$，并且要求 $\xi_i \geq 0$，即

\[\xi_i = \max\{0,1-y_i(\boldsymbol{w}^\top x_i+b)\}\]

可进行如下讨论

• 当 $\xi_i = 0$ 时， 样本满足 $y_i(\boldsymbol{w}^\top x_i+b) \geq 1$；
• 当 $\xi_i > 0$ 时， 样本满足 $y_i(\boldsymbol{w}^\top x_i+b) = 1 - \xi_i$；

因此惩罚项可以移除 $\max$ 写成统一的形式，约束不等式也可以写为统一的形式。则优化问题可以写成如下的 软间隔 SVM 优化问题

\[\begin{aligned} \min_{\boldsymbol{w},b} &\quad \frac{1}{2} \boldsymbol{w}^\top \boldsymbol{w} \textcolor{red}{+ C\sum_{i=1}^N\xi_i}\\ s.t. &\quad y_i(\boldsymbol{w}^\top x_i+b) \geq \textcolor{red}{1-\xi_i}\\ &\quad \xi_i \geq 0,\; \forall i=1,2,\cdots,N \end{aligned}\]

其中 $\xi_i$ 又称为松弛变量，引入松弛变量相当于我们放宽了对样本点的约束，原本要求其必须在硬间隔之外，现在只要都保证在软间隔之外即可，如图所示

后续求解与硬间隔 SVM 的优化问题一致，将其转为对偶问题然后利用 KKT 条件和 SMO 算法求解，此处不在赘述。

3.2. 非线性支持向量机

对于非线性可分问题，我们本着简化问题的思想，自然是希望将其转化为熟悉的线性可分问题进行处理。Cover 定理指出：将复杂的模式分类问题非线性地投射到高维空间将比投射到低维空间更可能是线性可分的。极端情况下，在维度超过数据数量时，数据一定线性可分（试想如果我们把每个数据点都映射到不同的坐标轴上，那么可不就是线性可分的了么）。

因此，我们对非线性可分的数据，可以将数据映射至高维空间，然后再用我们熟悉的线性支持向量机分类，至此，剩下的问题就是怎么映射呢？这就需要核函数登场了。

3.2.1. 核函数（kernel）

4. 参考文献

[1] 周志华. 机器学习. 北京：清华大学出版社, 2016.

[2] T. M. Cover and P. E. Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13:21–27, January 1967.

[3] blilbili. SVM白板推导(六)-支持向量机SVM（Support Vector Machine）.

[4] 知乎. 机器学习-白板推导系列(六)-支持向量机SVM（Support Vector Machine）笔记.