很多情况下，类别之间的分类边界并不是线性的，一种更好的选择是使用更复杂的非线性函数来描述分类。本文介绍了模式识别常用的非线性分类器，主要包括近邻法分类器（NN、KNN）、支持向量机（SVM）、决策树（DT），最后介绍分类器的集成。本章内容预计花费 4 个课时学习。
1. 引言
在介绍线性分类器时，我们介绍过大多数线性分类器在样本线性可分的情况下可以取得很好的效果。但很多情况下，类别之间的分类边界并不是线性的，如果依然使用线性分类器也能勉强使用，但一种更好的选择是使用更复杂的非线性函数来描述分类。
2. 近邻法分类器（NN / KNN）
2.1. 最近邻法
对于一个新样本，把它逐一与已知样本进行比较，找出距离新样本最近的已知样本，并以该样本的类别作为新样本的类别。其严格的数学描述如下：
假定有 $c$ 个类别的模式识别问题，每类包含样本个数为 $N_i,i=1,2,\cdots,c$。定义两个样本之间的距离度量 $\delta(\boldsymbol{x_i},\boldsymbol{x_j})$（比如可以采用欧式距离 $\delta(\boldsymbol{x_i},\boldsymbol{x_j})=\Vert \boldsymbol{x_i} - \boldsymbol{x_j} \Vert$），则对于任意未知新样本 $\boldsymbol{x}$，可以规定类 $w_i$ 的判别函数为：
\[g_i(\boldsymbol{x}) = \min_k \delta(\boldsymbol{x}, \boldsymbol{x_i}^{(k)}), \; k =1,2,\cdots,N_i\]其中 $\boldsymbol{x}_k$ 是类别 $w_i$ 中的第 $k$ 个样本。
对于每个类别都求出其判别函数，那么决策规则为
\[\boldsymbol{x}\in w_i\quad\text{if}\quad i=\arg\min_i g_i(\boldsymbol{x}),\; i=1,2,\cdots,c\]可以看出，最近邻法的思想很简单，新样本离谁最近，就把新样本判为最近的样本所属的类别。但在很多情况下，把决策建立在一个最近的样本上有一定风险，尤其是当数据分布复杂或数据中噪声严重时。如下图所示：
图中，黄色圆点为新样本（已知其为蓝色类别），但其最近邻为红色圆点样本。很明显，该红色样本是一个野值，其深入到了蓝色样本所属类别的区域。如果以最近邻的类别作为新样本的类别，那么显会导致分类错误。
为了更严格地分析最近邻法的错误率，我们需要进行一定的数学推导。当近邻法中训练样本的数量无限多（$N\rightarrow \infty$）时，某待分类的未知样本 $\boldsymbol{x}$ 的最近邻在极限意义上就是其自身，此时最近邻法分类正确的条件为：样本与它最近邻都属于同一类别。即分类正确率为
\[\sum_{i=1}^c P(w_i\vert \boldsymbol{x})P(w_i\vert \boldsymbol{x}) = \sum_{i=1}^c P(w_i\vert \boldsymbol{x})^2\]对应的错误率为
\[\lim_{N\rightarrow\infty} P_N(e\vert \boldsymbol{x}) = 1 - \sum_{i=1}^c P(w_i\vert \boldsymbol{x})^2\]则平均错误率为
\[\begin{aligned} P &= \lim_{N\rightarrow \infty}P(e) =\lim_{N\rightarrow \infty} \int P_N(e\vert \boldsymbol{x})p(\boldsymbol{x})\text{d}x\\ &= \int \lim_{N\rightarrow \infty} P_N(e\vert \boldsymbol{x})p(\boldsymbol{x})\text{d}x\\ &= \int \left(1 - \sum_{i=1}^c P(w_i\vert \boldsymbol{x})^2\right)p(\boldsymbol{x})\text{d}x \end{aligned}\]$P$ 又被称为最近邻法的渐进平均错误率，是 $P_N(e)$ 在 $N\rightarrow \infty$ 的极限。
为了更进一步了解最近邻法错误率的上界和下界，我们可以将其和理论上具备最优错误率的贝叶斯错误率进行比较。已知 $c$ 分类问题的贝叶斯错误率为
\[P^\star = \int[1- \max_i P(w_i \vert \boldsymbol{x})]p(\boldsymbol{x})\text{d}x,\; i=1,2,\cdots,c\]记 $m = \arg\max_i P(w_i\vert \boldsymbol{x})$，则
\[P^\star = \int[1- P(w_m\vert \boldsymbol{x})]p(\boldsymbol{x})\text{d}x\]因此，比较最近邻错误率和贝叶斯错误率的关键在于衡量以下两者的大小关系：
\[P(w_m\vert \boldsymbol{x}) \quad \text{和} \quad \sum_{i=1}^c P(w_i\vert \boldsymbol{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$，使得对于任意的 $\boldsymbol{x}_1\in D_0$ 和 $\boldsymbol{x}_2\in D_1$，都有：
\[\begin{aligned} \boldsymbol{w}^\top \boldsymbol{x}_1 + b &> 0,\; \boldsymbol{x}_1\in D_0\\ \boldsymbol{w}^\top \boldsymbol{x}_2 + b &< 0,\; \boldsymbol{x}_2\in D_1 \end{aligned}\]对于线性可分的样本，感知准则可以找到一个超平面将两类样本完全分开，但并不能保证该超平面是最优的。
SVM 可以看作感知准则的一种改进，SVM 的目标是找到一个超平面将两类样本分开，并且使得两类样本到超平面的距离最（标量）大，从而引入了某种最优性。
3.1.1. 硬间隔 SVM 优化问题
3.1.1.1. 优化问题描述
以二分类为例，假设样本集为 $S={(\boldsymbol{x}_1,y_1),(\boldsymbol{x}_2,y_2),\cdots,(\boldsymbol{x}_N,y_N)}$，其中 $\boldsymbol{x_i}$ 是样本，$y_i$ 是样本的类别标签（取值为 $\pm 1$）。假设样本集线性可分，存在一个超平面 $H$ 将两类样本完全分开。假设超平面 $H$ 的法向量为 $\boldsymbol{w}$，超平面到原点的距离为 $b$，则超平面可以表示为：
\[\boldsymbol{w}^\top \boldsymbol{x} + b = 0\]那么判别函数可写为
\[\begin{cases} \boldsymbol{w}^\top \boldsymbol{x_i} + b > 0, y = 1\\ \boldsymbol{w}^\top \boldsymbol{x_i} + b < 0, y= -1 \end{cases}\]合并为简单形式，则线性可分的条件为
\[y_i(\boldsymbol{w}^\top\boldsymbol{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 \boldsymbol{x_i}+b) > 0, \forall i=1,2,\cdots,N \end{aligned}\]上述优化问题中唯一不确定的地方就是间隔（margin）的定义。间隔被定义为样本中离决策面最近的那些样本到决策面的距离。设 $d_i$ 为样本 $\boldsymbol{x_i}$ 到超平面的距离（标量），则有：
\[d_i = \frac{\vert \boldsymbol{w}^\top \boldsymbol{x_i} + b\vert}{\Vert \boldsymbol{w} \Vert}\]那么间隔定义为
\[\text{margin}(\boldsymbol{w},b) = \min_{i} d_i\]则 SVM 的优化问题变为
\[\begin{aligned} \max_{\boldsymbol{w},b} \min_{i} &\quad\frac{\vert \boldsymbol{w}^\top \boldsymbol{x_i} + b\vert}{\Vert \boldsymbol{w} \Vert}\\ s.t. &\quad y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b) > 0, \forall i=1,2,\cdots,N \end{aligned}\]注意到，约束条件表明 $y_i$ 和 $\boldsymbol{w}\boldsymbol{x_i}+b$ 同号且二者相乘恒大于零，那么可安全地将优化目标函数的绝对值打开，得到
\[\begin{aligned} \max_{\boldsymbol{w},b} \min_{i} &\quad\frac{\textcolor{green}{y_i(\boldsymbol{w}^\top \boldsymbol{x_i} + b)}}{\Vert \boldsymbol{w} \Vert}\\ s.t. &\quad y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b) > 0, \forall i=1,2,\cdots,N \end{aligned}\]观察优化目标函数中，不同优化方向的作用对象，可移项如下
\[\begin{aligned} \max_{\boldsymbol{w},b}&\; \textcolor{green}{\frac{1}{\Vert \boldsymbol{w} \Vert}} \; \min_{i} \; y_i(\boldsymbol{w}^\top \boldsymbol{x_i} + b)\\ s.t. &\quad y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b) > 0, \forall i=1,2,\cdots,N\\ \end{aligned}\]既然约束条件要求 $y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b) > 0$，那么一定有
\[\exists \gamma > 0,\; \min_i y_i(\boldsymbol{w}^\top\boldsymbol{x_i}+b) =\gamma\]此处 $\gamma$ 被称为 函数间隔。引入函数间隔后，优化问题变为如下形式
\[\begin{aligned} \max_{\boldsymbol{w},b}&\; \frac{1}{\Vert \boldsymbol{w} \Vert} \; \min_{i} \; y_i(\boldsymbol{w}^\top \boldsymbol{x_i} + b)\\ s.t. &\quad y_i(\boldsymbol{w}^\top \boldsymbol{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 \boldsymbol{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 \boldsymbol{x_i}+b) \textcolor{red}{\geq \gamma}, \forall i=1,2,\cdots,N \end{aligned}\]注意到当 $\boldsymbol{w},b$ 发生变化（如分别扩大两倍）也会导致函数间隔发生变化（同样扩大两倍）。虽然这种操作不会改变最优解，但会产生一个等价的优化问题。为了避免这种情况，不妨令 $\gamma = 1$，优化问题变为
\[\begin{aligned} \max_{\boldsymbol{w},b}&\quad \frac{1}{\Vert \boldsymbol{w} \Vert}\\ s.t. &\quad y_i(\boldsymbol{w}^\top \boldsymbol{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}\]得到最终的 SVM 优化问题的描述
\[\begin{aligned} \textcolor{blue}{\min_{\boldsymbol{w},b}} &\quad \textcolor{blue}{\frac{1}{2} \boldsymbol{w}^\top \boldsymbol{w}}\\ \textcolor{blue}{s.t.} &\textcolor{blue}{\quad y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b) \geq 1, \forall i=1,2,\cdots,N} \end{aligned}\]上述优化问题是一个包含 $N$ 个不等式约束的二次凸优化问题。
对于线性可分的样本，所有样本一定能够满足上面的不等式约束，也即所有样本都可以位于间隔的两侧，不存在错分的情况，所以上述优化问题一定有解。我们称上述优化问题为 硬间隔 SVM 优化问题。对应的图示如下
3.1.1.2. 拉格朗日乘子
对于一个带约束的优化问题，采用拉格朗日乘子法转化为一个无约束优化问题，拉格朗日函数如下
\[\textcolor{blue}{L(\boldsymbol{w},b,\lambda) = \frac{1}{2}\boldsymbol{w}^\top\boldsymbol{w} + \sum_{i=1}^N\lambda_i(1-y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b)),\; \lambda_i \geq 0}\]优化问题变为
\[\begin{aligned} \textcolor{blue}{\min_{w,b}}\quad & \textcolor{blue}{\max_\lambda L(\boldsymbol{w},b,\lambda)}\\ \textcolor{blue}{s.t.} & \quad \textcolor{blue}{\lambda_i \geq 0, \forall i=1,2,\cdots,N}\\ \end{aligned}\]拉格朗日乘子法变换后的优化问题与原始优化问题的等价性可分析如下：
定义 $\delta = 1-y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b)$，SVM 优化问题的约束条件变为
\[\delta_i \leq 0\]整个 $(\boldsymbol{w},b)$ 空间可划分为两个部分，不满足约束（$\delta > 0$）和满足约束（$\delta \leq 0$）。
- 对于 $\delta > 0$，约束被违反，可以取 $\lambda \to \infty$ 使得优化目标
- 对于 $\delta \leq 0$，约束被满足，可以取$\lambda = 0$ 使得优化目标取到最大值
综上两种情况，拉格朗日乘子法的优化问题可以写为
\[\min_{w,b}\max_\lambda L(\boldsymbol{w},b,\lambda) = \min_{w,b} [+\infty,\;\frac{1}{2}\boldsymbol{w}^\top\boldsymbol{w}] = \min_{w,b} \frac{1}{2}\boldsymbol{w}^\top\boldsymbol{w}\]也即与原始优化问题等价，其中外层 $\min_{w,b}$ 会自动忽略不满足约束（$\delta > 0$）的解。
3.1.1.3. 对偶问题求解
上述优化问题的 对偶问题 为（交换 $\max$ 与 $\min$）
\[\begin{aligned} \textcolor{blue}{\max_\lambda \min_{w,b}} &\quad \textcolor{blue}{L(\boldsymbol{w},b,\lambda)}\\ \textcolor{blue}{s.t.} &\quad \textcolor{blue}{\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 \boldsymbol{x_i}, x \rangle$，这可以通过核函数高效完成，避免直接处理高维向量。
- 核函数的引入：
对偶问题的形式天然适合引入核函数，将数据映射到高维空间进行非线性分类，而无需显式计算高维空间中的坐标。这是 SVM 能够处理非线性问题的关键。
注意原问题和对偶问题存在如下关系
\[\min_{w,b}\max_\lambda L(\boldsymbol{w},b,\lambda) \geq \max_\lambda \min_{w,b} L(\boldsymbol{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(\boldsymbol{w}^\top \boldsymbol{x_i}+b))=0\quad \text{互补松弛性}\\ \lambda_i \geq 0\quad \text{对偶可行性}\\ 1-y_i(\boldsymbol{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(\boldsymbol{w},b,\lambda) &= \frac{1}{2}\boldsymbol{w}^\top\boldsymbol{w} + \sum_{i=1}^N\lambda_i(1-y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b))\\ &= \frac{1}{2}\boldsymbol{w}^\top\boldsymbol{w} + \sum_{i=1}^N \lambda_i - \sum_{i=1}^N \lambda_i y_i w^\top \boldsymbol{x_i} \end{aligned}\]简化后的目标函数对 $w$ 求偏导令其为零，得到最优参数 $\boldsymbol{w}^\star$ 的形式
\[\frac{\partial L}{\partial \boldsymbol{w}} = \boldsymbol{w} - \sum_{i=1}^N \lambda_i y_i \boldsymbol{x_i} = 0\Rightarrow \boldsymbol{w}^\star= \sum_{i=1}^N \lambda_i y_i \boldsymbol{x_i}\]将其代入目标函数进行进一步化简，有
\[\begin{aligned} L(\boldsymbol{w},b,\lambda) =& \frac{1}{2}(\sum_{i=1}^N\lambda_i y_i \boldsymbol{x_i})^\top (\sum_{i=j}^N\lambda_j y_j \boldsymbol{x_j})+ \sum_{i=1}^N \lambda_i\\ & - \sum_{i=1}^N \lambda_i y_i (\sum_{i=j}^N \lambda_j y_j \boldsymbol{x_j})^\top \boldsymbol{x_i}\\ =&\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \lambda_i \lambda_j y_i y_j \boldsymbol{x_i}^\top \boldsymbol{x_j} + \sum_{i=1}^N \lambda_i\\ & - \sum_{i=1}^N\sum_{j=1}^N \lambda_i \lambda_j y_i y_j \boldsymbol{x_j}^\top \boldsymbol{x_i}\\ =& -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \lambda_i \lambda_j y_i y_j \boldsymbol{x_i}^\top \boldsymbol{x_j} + \sum_{i=1}^N \lambda_i \end{aligned}\]至此我们根据 KKT 条件中的梯度可行性条件，得到了 $w^\star$ 的形式，并对目标函数进行了化简。
下面继续根据 KKT 条件中的互补松弛条件、对偶可行条件、原始可行条件，确定最优参数 $b^\star$ 的形式
\[\begin{aligned} \lambda_i(1-y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b))=0\\ \lambda_i \geq 0\\ 1-y_i(\boldsymbol{w}^\top \boldsymbol{x}_i + b)\leq 0\\ \end{aligned}\]对于第 $k$ 个样本 $(\boldsymbol{x}_k, y_k)$ 的原始可行性条件分类讨论如下：
-
第一种情况，样本使得 $y_i(\boldsymbol{w}^\top \boldsymbol{x} + b) = 1$
这个样本点就是距离分类面最近的那些样本点，被称为 支持向量（Support Vector）。此时对 $\lambda_i$ 没有额外约束。因此我们通过 选择任意一个支持向量 可以求出 $b^\star$
\[\begin{aligned} y_k(\boldsymbol{w}^\top \boldsymbol{x}_k + b) &= 1\\ \Rightarrow y_k^2(\boldsymbol{w}^\top \boldsymbol{x}_k + b) &= y_k \end{aligned}\]注意到类别标签取值为 $\pm 1$，因此 $y_k^2 = 1$，则可以得到最优参数 $b^\star$ 的形式
\[b^\star = y_k-w^\top \boldsymbol{x}_k= y_k-\sum_{i=1}^N \lambda_i y_i \boldsymbol{x}_i^\top \boldsymbol{x}_k\]考虑到样本带噪声的情况，我们也可以通过对所有支持向量求出 $b$ 后取均值得到 $b^\star$。
-
第二种情况，样本使得 $y_i(\boldsymbol{w}^\top x + b) > 1$
此时，该样本为距离分类面较远的样本，不是支持向量。根据互补松弛条件，必须要求$\lambda_i = 0$。
也就是说，只有当样本是支撑向量时对应的 $\lambda_i \neq 0$，否则 $\lambda_i = 0$。这极大简化 $\boldsymbol{w}^\star,b^\star$ 的计算，因为不用计算其中$\lambda_i = 0$ 项的向量内积。
至此，我们已经确定了内层优化 $\min_{w,b}$ 的最优解，并且得到了最优参数的表达式
\[\begin{aligned} \boldsymbol{w}^\star &= \sum_{i=1}^N \lambda_i y_i \boldsymbol{x_i}\\ b^\star &= y_k-\sum_{i=1}^N \lambda_i y_i \boldsymbol{x}_i^\top \boldsymbol{x}_k\quad \text{support vector}\; (\boldsymbol{x}_k,y_k) \end{aligned}\]注意到其中拉格朗日系数还是未知的，需要求解剩余的外层优化问题得到
\[\begin{aligned} \max_\lambda &\quad -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \lambda_i \lambda_j y_i y_j \boldsymbol{x_i}^\top \boldsymbol{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}\]这个问题是针对 $N$ 个拉格朗日乘子 $\lambda_i$ 进行优化，我们需要求一个 $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
至此解出了所有参数 $\boldsymbol{w}^\star, b^\star, \lambda_i$，得到 SVM 的判别函数 如下
\[f(x) = \text{sign}({\boldsymbol{w}^\star}^\top x + b^\star)\]并且知道 $\boldsymbol{w}^\star,b^\star$ 仅是 支持向量 的线性组合（因为 $\lambda_i$ 只有在样本为支持向量时才不为零）。所以 SVM 训练完成后，大部分的训练样本都不需要保留，最终的分类模型仅与支持向量有关。
3.1.2. 软间隔 SVM 优化问题
3.1.2.1. 优化问题描述
前面一直假定训练样本在样本空间或特征空间线性可分，即存在一个超平面将不同类的样本完全划分开。但现实中，很难确定使得训练样本在特征空间中线性可分。缓解该问题的办法是允许支持向量机出错，可以通过在目标函数中额外添加一项 $\text{loss}$ 来实现这一点，新的优化问题如下
\[\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 \boldsymbol{x_i}+b) \geq 1, \;\forall i=1,2,\cdots,N \end{aligned}\]$\text{loss}$ 选取可以有以下几种形式，第一种是引入 $0/1$ 损失函数作为惩罚项，每当有一个样本不满足约束则计数加 $1$，最后寻找参数 $(\boldsymbol{w},b)$ 使得包含计数的损失函数最小
\[\begin{aligned} \text{loss} &= C\sum_{i=1}^N l_{0/1}\{1-y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b)\}, \;\forall i=1,2,\cdots,N\\ l_{0/1} &= \begin{cases} 0,\;\text{if}\;1-y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b) \leq 0 \\ 1,\;\text{if}\;1-y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b) > 0 \;\text{违背约束} \end{cases} \end{aligned}\]但 $0/1$ 损失函数非凸、非连续，不容易优化，需要采用其他替代损失。
令 $z = y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b)$，几种可行的替代损失如下图所示
求解替代损失函数得到的解是否仍为原问题的解，在理论上称为替代损失的 “一致性” 问题。替代损失一般选取为原始损失损失函数的上界，这样替代损失函数得到优化时，原始损失函数也同样得到优化。此外，替代函数一般选为凸函数，便于优化。
上图中列出的几种常见替代损失都已被证明是一致的，可以替代 $0/1$ 损失函数。SVM 求解选取 hinge loss 作为替代损失，同时引入 $C$ 作为惩罚参数
\[\textcolor{blue}{\text{loss} = C\sum_{i=1}^N\max\{ 0, 1-y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b) \}}\]对 hinge loss 展开分析如下：
- $z=y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b)\geq 1, \quad\text{loss}=0$
- $z=y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b)< 1, \quad\text{loss}=1-y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b)$
可以看出，hinge loss 在约束满足时取值为 0，在约束不满足时取值即为约束的正值，两个区间的边界处（$z=1$）的函数值是连续的。引入这个惩罚项后，假设有样本不满足约束，我们通过优化带上述惩罚项的目标函数，即希望使得不满足约束的样本带来的影响（对约束的违背程度）尽可能小。
虽然 hinge loss 函数取值已经连续了，但由于存在 $\max$ 算符，在实际使用时仍然不太方便。这里把 hinge loss 单独定义为一个变量 $\xi_i$，并且要求 $\xi_i \geq 0$，即
\[\xi_i = \max\{0,1-y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b)\}\]可进行如下讨论
- 当 $\xi_i = 0$ 时， 样本满足 $y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b) \geq 1\textcolor{green}{=1-\xi_i}$；
- 当 $\xi_i > 0$ 时， 样本满足 $y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b) = 1 - \xi_i$；
因此惩罚项可以移除 $\max$ 写成统一的形式，约束不等式也可以写为统一的形式。则优化问题可以写成如下的 软间隔 SVM 优化问题
\[\begin{aligned} \textcolor{blue}{\min_{\boldsymbol{w},b,\xi_i}} &\quad \textcolor{blue}{\frac{1}{2} \boldsymbol{w}^\top \boldsymbol{w} + C\sum_{i=1}^N\textcolor{red}{\xi_i}}\\ \textcolor{blue}{s.t.} &\quad \textcolor{blue}{y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b) \geq \textcolor{red}{1-\xi_i},\; \xi_i \geq 0,\; \forall i=1,2,\cdots,N} \end{aligned}\]其中 $\xi_i$ 又称为松弛变量，引入松弛变量相当于我们放宽了对样本点的约束，原本要求其必须在硬间隔之外，现在只要都保证在软间隔之外即可。
最小化目标函数包含两层含义：第一项使硬间隔尽量大，第二项使误分类点的个数尽量小，$C$ 是调和二者的系数。并且只要错分一个样本点，我们都将付出 $C\xi_i$ 的代价。极端情况下，当 $C\to \infty$，表明此时我们无法容忍误分类样本点，只要有一丁点误分就会导致目标函数变得很大，相当于 $\xi_i\to 0$，软间隔 SVM 问题退化成为硬间隔 SVM 问题。
软间隔 SVM 优化问题的图示如下所示
3.1.2.2. 拉格朗日乘子
同样采用拉格朗日乘子法，上述软间隔 SVM 优化问题可以写成如下形式
\[\begin{aligned} &\min_{w,b,\xi_i} \max_{\lambda, \mu}L(\boldsymbol{w},b,\xi,\lambda, \mu) = \\ &\frac{1}{2}\boldsymbol{w}^\top\boldsymbol{w} + C\sum_{i=1}^N \xi_i \textcolor{red}{+ \sum_{i=1}^N \lambda_i(1-\xi_i-y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b)) - \sum_{i=1}^N \mu_i\xi_i}\\ &s.t. \quad \xi_i \geq 0, \lambda_i \geq 0,\mu_i \geq 0, \quad \forall i=1,2,\cdots,N \end{aligned}\]3.1.2.3. 对偶问题求解
同样将原问题转化为对偶问题
\[\begin{aligned} &\textcolor{green}{\max_{\lambda, \mu} \min_{w,b,\xi_i}} L(\boldsymbol{w},b,\xi,\lambda, \mu) = \\ &\frac{1}{2}\boldsymbol{w}^\top\boldsymbol{w} + C\sum_{i=1}^N \xi_i + \sum_{i=1}^N \lambda_i(1-\xi_i-y_i(\boldsymbol{w}^\top \boldsymbol{x_i}+b)) - \sum_{i=1}^N \mu_i\xi_i\\ &s.t. \quad \xi_i \geq 0, \lambda_i \geq 0,\mu_i \geq 0, \quad \forall i=1,2,\cdots,N \end{aligned}\]根据 KKT 条件中的梯度可行性条件，可以得到如下的等式：
\[\begin{cases} \nabla_w L(\boldsymbol{w},b,\xi,\lambda, \mu) = \boldsymbol{w} - \sum_{i=1}^N \lambda_i y_i \boldsymbol{x_i} = 0\\ \nabla_b L(\boldsymbol{w},b,\xi,\lambda, \mu) = - \sum_{i=1}^N \lambda_i y_i = 0, \quad \forall i=1,2,\cdots,N\\ \nabla_{\xi_i} L(\boldsymbol{w},b,\xi,\lambda, \mu) = C - \lambda_i - \mu_i = 0\\ \end{cases}\]可以得到
\[\begin{cases} \boldsymbol{w} = \sum_{i=1}^N \lambda_i y_i \boldsymbol{x_i}\\ \sum_{i=1}^N \lambda_i y_i=0, \quad \forall i=1,2,\cdots,N\\ C-\lambda_i-\mu_i=0 \end{cases}\]又根据 KKT 条件中的互补松弛性等条件，对于 $ \forall i=1,2,\cdots,N$
\[\begin{aligned} \lambda_i \geq 0,\mu_i \geq 0 &\quad \text{对偶可行性}\\ 1-\xi_i-y_i(\boldsymbol{w}^T\boldsymbol{x_i}+b) \leq 0,\;\xi_i\geq 0 &\quad \text{原始可行性}\\ \lambda_i(1-\xi_i-y_i(\boldsymbol{w}^T\boldsymbol{x_i}+b))=0 &\quad \text{互补松弛性}\\ \mu_i\xi_i=0 &\quad \text{互补松弛性} \end{aligned}\]对于第 $i$ 个样本分析如下
- $ \lambda_i = 0$：样本不是支持向量；
- 梯度可行条件条件：$\lambda_i+\mu_i=C$，因此 $ \mu \geq 0 \Rightarrow \lambda_i \leq C$
- $0<\lambda_i < C \Rightarrow \mu_i > 0 \Rightarrow \xi_i = 0$：样本是支持向量；
- $\lambda_i = C \Rightarrow \mu_i = 0$：$\xi_i$ 取值任意，样本不是支持向量；
- $0\leq \xi_i < 1$：样本落在最大间隔内部；
- $\xi_i = 1$：样本落在分类超平面上；
- $\xi_i > 1$：样本被错误分类；
代入原始目标函数可得化简的目标函数（隐去 $\mu_i$）为
\[\begin{aligned} \max_\lambda &\quad -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \lambda_i \lambda_j y_i y_j \boldsymbol{x_i}^\top \boldsymbol{x_j} + \sum_{i=1}^N \lambda_i\\ s.t. &\quad \sum_{i=1}^N \lambda_i y_i=0,\; \textcolor{green}{0\leq \lambda_i \leq C},\; i=1,2,\cdots,N\\ \end{aligned}\]上述标绿约束也是 软间隔 SVM 与 硬间隔 SVM 优化问题的唯一区别。利用 KKT 条件和 SMO 算法继续求解拉格朗日系数 $\lambda_i$，此处不在赘述。
最后我们也可以解得优化问题的最优解为
\[\begin{aligned} w^\star &= \sum_{i=1}^N \lambda_i y_i \boldsymbol{x_i}\\ b^\star &= y_k-\sum_{i=1}^N \lambda_i y_i \boldsymbol{x_i}^\top \boldsymbol{x}_k\quad \text{support vector}\; (\boldsymbol{x}_k,y_k) \end{aligned}\]得到 SVM 的判别函数 如下
\[f(x) = \text{sign}({\boldsymbol{w}^\star}^\top x + b^\star)\]其形式和 硬间隔 SVM 的最优解形式是一样的。
3.1.3. 统计机器学习的一般形式
我们用一个统一的目标函数同时刻画 硬间隔 SVM 和 软间隔 SVM 的目标函数，即：
\[\min_f \quad \underbrace{\Omega(f)}_{结构风险} + \underbrace{C\sum_{i=1}^N l(f(\boldsymbol{x}_i),y_i)}_{经验风险}\]其中
- 结构风险（Structural Risk）：描述模型本身的某些性质，通常称为正则化项，使用正则化项的方法称之为 “罚函数法”；
- 经验风险（Experience Risk）：描述模型在训练数据集上的拟合程度。
相比于其他基于数据的机器学习，SVM 这类基于统计的机器学习通过对不希望的结果（模型选择）施加惩罚，使得优化过程趋向于希望目标。
从贝叶斯估计的角度，则可认为结构风险这一正则化项是提供了模型的先验概率（对模型的喜好和态度），或者称为归纳偏好。
3.2. 非线性支持向量机
对于非线性可分问题，我们本着简化问题的思想，自然是希望将其转化为熟悉的线性可分问题进行处理。
Cover 定理指出：将复杂的模式分类问题非线性地投射到高维空间将比投射到低维空间更可能是线性可分的。极端情况下，在维度超过数据数量时，数据一定线性可分（试想如果我们把每个数据点都映射到不同的坐标轴上，那么可不就是线性可分的了么）。
因此，我们对非线性可分的数据，可以将数据映射至高维空间，然后再用我们熟悉的线性支持向量机分类，至此，剩下的问题就是怎么映射至高维。
通过坐标变换而不进行升维在一些特殊场景下也能实现分类，如
使用极坐标 $\phi(x):[x_1,x_2]^\top \to [r,\theta]^\top,\quad \mathbb{R}^2\to \mathbb{R}^2$
但这种映射方式适用面较窄，并不常用。
3.2.1. 特征升维分类实例
考虑如下四个样本，需要将其进行分类，可以发现没有任何一个线性分类面能够完成此任务
\[\begin{aligned} \text{class 1}:\;&(0,3),(3,0)\\ \text{class 2}:\;&(2,1),(1,2) \end{aligned}\]
我们尝试通过升维操作来解决分类问题。那么第三个维度可以选什么呢？我们尝试如下三种
\[(x,y,\textcolor{red}{x+y}),(x,y,\textcolor{green}{xy}),(x,y,\textcolor{blue}{x^2})\]分别求得三种情况下的第三维度计算结果
| $\textcolor{red}{(0,3)}$ | $\textcolor{green}{(1,2)}$ | $\textcolor{green}{(2,1)}$ | $\textcolor{red}{(3,0)}$ | |
|---|---|---|---|---|
| $x+y$ | 3 | 3 | 3 | 3 |
| $xy$ | 0 | 2 | 2 | 0 |
| $x^2$ | 0 | 1 | 4 | 9 |
很明显，使用第三个维度为 $xy$ 时能够区分两类不同的样本。结果如图所示
上述过程实际上是一个朴素的特征映射过程，其仍然存在以下两个问题：
- 特征映射需要凭借经验设计（如设计第三个维度为 $xy$）；
- 特征映射引入了额外的计算成本（后面展开介绍）。
3.2.2. 核技巧
观察线性 SVM 的优化目标函数
\[\max_\lambda \quad -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \lambda_i \lambda_j y_i y_j \boldsymbol{x_i}^\top \boldsymbol{x_j} + \sum_{i=1}^N \lambda_i\]可以看出其主要通过计算样本的内积来优化得到分类超平面。由于升维可以使得原本线性不可分的样本变得线性可分，其关键在于如何对样本进行升维后求内积。
观察线性 SVM 的判别函数可以得到同样的结论，因为其超平面方程的参数 $b^\star$ 表达式中同样包含样本内积
假设我们用一个映射函数 $\phi(\cdot)$ 将原始样本升维，那么优化函数变为
\[\max_\lambda \quad -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \lambda_i \lambda_j y_i y_j \phi(\boldsymbol{x_i})^\top \phi(\boldsymbol{x_j}) + \sum_{i=1}^N \lambda_i\]假设样本在映射函数 $\phi(\cdot)$ 的作用下从二维升至六维，如下
\[\boldsymbol{x} = [a, b]^\top\mathop{\longrightarrow}\limits^{\phi}\phi(\boldsymbol{x})=[1,\sqrt{2}a,\sqrt{2}b,a^2,b^2,\sqrt{2}ab]^\top\]那么先映射后再求内积可以得到
\[\phi(\boldsymbol{x}_1)\cdot \phi(\boldsymbol{x}_2) = 1+2a_1a_2+2b_1b_2+a_1^2a_2^2+b_1^2b_2^2+2a_1a_2b_1b_2\]可以看出，
- 设计六维特征已经十分繁杂，更高维度特征设计我们无从下手；
- 随着维度的增加，求内积操作变得十分复杂。
下面通过引入核函数的方式解决上述两个问题。
3.2.2.1. 多项式核函数
我们转换思想，尝试 先求内积再进行映射，定义如下关于内积的函数：
\[\begin{aligned} \mathcal{K}(\boldsymbol{x}_1,\boldsymbol{x}_2) &= (1+\boldsymbol{x}_1^\top\cdot\boldsymbol{x}_2)^2\\ &=(1+a_1a_2+b_1b_2)^2\\ &=1+2a_1a_2+2b_1b_2+a_1^2a_2^2+b_1^2b_2^2+2a_1a_2b_1b_2 \end{aligned}\]可以发现，其结果正好等于前述映射到六维后的样本内积结果。因此，在实际使用时只需要在样本低维空间先求内积，然后将内积的结果代入函数中，进行简单计算即可得到映射到高维空间后的内积结果。
上述操作使用的函数被称为「核函数」，通过引入核函数来简化内积计算的这种操作被称为「核技巧」，具体而言，这里采用的是 多项式核函数
\[\mathcal{K}_{poly}^{(c,d)}(\boldsymbol{x}_1,\boldsymbol{x}_2) = (c+\boldsymbol{x}_1^\top\cdot\boldsymbol{x}_2)^d\]当 $c=1,d=2$ 时，就可以将原本的样本升至前述六维。如果换一组参数，可以将原样本升至不同的维度。因此，多项式核函数确定了一组参数后，也就确定了转换后的样本特征维度。
多项式核函数中的常数 $c$ 十分重要，其决定了内积结果的表达始终包含了从低次项到高次项的数据组合，体现出维度的多样性。当 $c=0$ 时，点积展开式将只包含高次项。进一步，我们可以通过将多个不同次的多项式核函数相加组合，使结果同时具有高低次项，以此丰富维度的多样性
\[\begin{aligned} &\textcolor{red}{c=1,d=2:}\\ &\mathcal{K}(\boldsymbol{x}_1,\boldsymbol{x}_2) =\textcolor{green}{1+2a_1a_2+2b_1b_2}+a_1^2a_2^2+b_1^2b_2^2+2a_1a_2b_1b_2\\ &\textcolor{red}{c=0,d=2:}\\ &\mathcal{K}(\boldsymbol{x}_1,\boldsymbol{x}_2) =a_1^2a_2^2+b_1^2b_2^2+2a_1a_2b_1b_2\\ &\textcolor{red}{(c=0,d=2)+(c=0,d=2):}\\ &\mathcal{K}(\boldsymbol{x}_1,\boldsymbol{x}_2) =\textcolor{green}{2a_1a_2+2b_1b_2}+a_1^2a_2^2+b_1^2b_2^2+2a_1a_2b_1b_2\\ \end{aligned}\]多项式核函数通过构建特征的高次组合，适用于存在较明显非线性但复杂度适中的数据。多项式阶数的选择直接影响模型的复杂度和拟合能力，过高可能导致过拟合，过低可能无法捕捉数据的非线性特性。
虽然引入核函数可以在某种程度上简化高维特征的设计问题（通过调节参数 $c$ 和 $d$ 即可直接得到不同的高维特征），并且可以降低计算量。但是多项式核函数仍然存在以下局限性：
- 阶数 $d$ 的选择困难：
- $d$ 太小可能导致模型欠拟合，无法捕捉复杂模式；
- $d$ 太大容易过拟合，且计算复杂度高（特征空间维度爆炸增长）。
-
数值问题：当 $d$ 较大时，$\boldsymbol{x}_i^\top\boldsymbol{x}_j$ 的值可能非常大或非常小，导致数值不稳定。
-
对特征尺度敏感：多项式核的性能受特征尺度影响较大，通常需要标准化数据，而高斯核对尺度敏感度较低（因已包含距离度量）。
- 灵活性不足：多项式核只能捕捉固定阶数的多项式关系，而高斯核可以近似任意复杂函数。
下面介绍的 RBF （高斯）核函数能够解决上述绝大部分局限，使用更为广泛。
3.2.2.2. RBF 核函数
根据 Cover 定理，维度越高越有可能使得样本变得线性可分。极端情况下，如果希望样本特征升至无限维，那么原本的先映射再计算内积的方法就失效了，因为我们无法对映射后的无限维特征进行求内积操作。因此我们只能使用核技巧来计算。
注意到，即使使用多项式核函数也无法通过 $d=+\infty$ 实现无限升维。这里我们给出另一种核函数，被称为 RBF 核函数（Radial Basis Function）、径向基核函数 或 高斯核函数。其定义如下
\[\begin{aligned} RBF(\boldsymbol{x}_i, \boldsymbol{x}_j) & = \exp\left(-\frac{\Vert \boldsymbol{x}_i-\boldsymbol{x}_j\Vert^2}{2\sigma^2}\right) \\ \end{aligned}\]其反应了两个样本向量的相似度信息，其参数 $\sigma$ 是核函数的参数，用来调控对样本向量之间的相似度和距离之间的敏感程度。
简便起见，令 $\sigma = 1$，对 RBF 核函数展开如下
\[\begin{aligned} RBF(\boldsymbol{x}_i, \boldsymbol{x}_j) &= \exp\left(-\frac{\Vert \boldsymbol{x}_i-\boldsymbol{x}_j\Vert^2}{2}\right) \\ &=\exp\left(-\frac{1}{2}(\boldsymbol{x}_i-\boldsymbol{x}_j)^\top(\boldsymbol{x}_i-\boldsymbol{x}_j)\right) \\ &=\exp\left(-\frac{1}{2}[\boldsymbol{x}_i^\top\boldsymbol{x}_i+\boldsymbol{x}_j^\top\boldsymbol{x}_j - 2\boldsymbol{x}_i^\top\boldsymbol{x}_j]\right)\\ &= \exp\left(-\frac{1}{2}[\boldsymbol{x}_i^\top\boldsymbol{x}_i+\boldsymbol{x}_j^\top\boldsymbol{x}_j]\right)\exp\left(\boldsymbol{x}_i^\top\boldsymbol{x}_j\right)\\ &=C\cdot\exp\left(\boldsymbol{x}_i^\top\boldsymbol{x}_j\right) \end{aligned}\]可以看出，RBF 核函数是关于两向量内积的指数函数，对其进行泰勒展开可以得到
\[RBF(\boldsymbol{x}_i,\boldsymbol{x}_j) = C\cdot\sum_{n=0}^{\infty}\frac{1}{n!}\left(\boldsymbol{x}_i^\top\boldsymbol{x}_j\right)^n = C\cdot\sum_{n=0}^{\infty}\frac{1}{n!}\left(\mathcal{K}_{poly}^{(0,n)}\right)\]\[\exp(x) = \sum_{n=0}^{\infty}\frac{1}{n!}x^n\]
因此，RBF 核函数可以看作无数个不带常数的多项式核函数从低次到高次的加权和，可以表达高低次项的无限多样性。这样，我们就实现了在不实质踏入无限维度的情况下，得到无限维度下向量相似度的结果。
RBF 核函数是最常用的非线性核函数之一，尤其适用于高维、复杂非线性数据。其参数 $\gamma = \frac{1}{2\sigma^2}$ 决定了核函数的宽度，对模型的复杂度和分类效果有显著影响。RBF核因其局部性、平滑性和无限维映射等特性，常能在保持较低模型复杂度的同时获得良好的分类性能。
4. 决策树（DT）
决策树（Decision Tree）是一种用于分类和回归的监督学习方法。它通过构建树形结构来模拟决策过程，每个内部节点表示一个特征属性上的选择，每个分支代表一个选择结果，每个叶子节点代表一个类别或预测结果。决策树通过递归地划分数据集，将数据集分割成更小的子集，直到满足停止条件为止。
二叉树是最简单的决策树模型，每个非终止节点上采用线性分类器进行决策，每个非终止节点有两个分支，故称为二叉树。二叉树将多峰问题或多类问题转换为多级的线性问题。
4.1. ID3 算法
构建决策树的一般步骤如下：
- 特征选择：从众多的特征中选择（属性）一个特征作为当前节点分裂的标准；
- 决策树生成：根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树生长；
- 剪枝：缩小树结构规模、缓解过拟合。
随之而来的第一个问题是，如何从众多特征中选择一个特征作为当前节点分裂的标准呢？这里介绍 ID3（Interactive Dichotomizer-3）算法，其采用信息熵和信息增益来衡量不同特征的优先级。对于信息增益大的特征，优先选择该特征作为当前节点分裂的标准。
以下表为例，根据苹果颜色特征和形状特征来对苹果甜不甜进行分类，假设数据如下：
| 苹果编号 | 红不红H | 圆不圆Y | 甜不甜T |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 1 |
| 3 | 1 | 0 | 0 |
| 4 | 0 | 1 | 0 |
| 5 | 0 | 1 | 0 |
4.1.1. 信息熵
在信息论中，熵（entropy） 是随机变量不确定性的度量，熵越大，则随机变量的不确定性越大。信息熵是度量样本集合纯度最常用的一种指标。
设 $X$ 是一个取有限个值的离散随机变量，其概率分布为
\[P(X=x_i) = p_i,\;i=1,2,\ldots,n\]则随机变量 $X$ 的熵定义为
\[H(X) = -\sum_{i=1}^n p_i\log_2 p_i\]且约定 $0\log_2 0 = 0$。信息熵反映了信息的纯度，信息熵越大表明信息的纯度越低（越杂乱），包含的不同类别越多。纯度越高表明同一类别的样本占比越高。
当熵中的概率由数据估计得到时，所对应的熵称为经验熵(empirical entropy)。
对于苹果分类的例子，我们首先计算该数据的经验熵为：
\[\begin{aligned} H(T) &= -\sum_{i=0}^1 p_i\log_2 p_i\\ &=- P(T=1)\log_2 P(T=1)-P(T=0)\log_2 P(T=0)\\ &= -\frac{2}{5}\log_2 \frac{2}{5} -\frac{3}{5}\log_2 \frac{3}{5}\approx 0.971\; \text{bit} \end{aligned}\]4.1.2. 条件熵
随机变量 $X$ 给定的条件下，随机变量 $Y$ 的条件熵（conditional entropy）定义为：$X$ 给定的条件下 $Y$ 的条件概率分布的信息熵对 $X$ 的数学期望：
\[H(Y\vert X) = \sum_{i=1}^n p_i H(Y\vert X=x_i)\]类似地，当条件熵中的概率由数据估计（特别是极大似然估计）得到时，称为经验条件熵。
给定苹果 “红不红” 的条件，有
- 若为红苹果
- 若为不红苹果
则条件熵为：
\[\begin{aligned} H(T\vert H) &= P(H=1)H(T\vert H=1) + P(H=0)H(T\vert H=0)\\ &=\frac{3}{5}\cdot 0.918 + \frac{2}{5}\cdot 0 =0.551\; \text{bit} \end{aligned}\]类似给定苹果 “圆不圆” 的条件，有
- 圆苹果条件下的条件熵为：
- 不圆苹果条件下的条件熵为：
则条件熵为：
\[\begin{aligned} H(T\vert Y) &= P(Y=1)H(T\vert Y=1) + P(Y=0)H(T\vert Y=0)\\ &= \frac{4}{5}\cdot 1 + \frac{1}{5}\cdot 0 = 0.8\; \text{bit} \end{aligned}\]4.1.3. 信息增益
计算出原始样本的经验熵，以及给定不同特征的经验条件熵，那么衡量特征的优先级，就可以使用信息增益来判断。信息增益（Information Gain，IG）为在已知某个特征的情况下，对总体的信息（不确定性）减少程度。计算公式为
\[\text{IG}(Y,X) = H(Y) - H(Y|X)\]给定上述苹果数据集后，我们分别计算不同特征的信息增益，可以得到如下结果：
\[\begin{aligned} \text{IG}(T,H) &= H(T) - H(T|H) = 0.971 - 0.551 = 0.420 \; \text{bit}\\ \text{IG}(T,Y) &= H(T) - H(T|Y) = 0.971 - 0.800 = 0.171\; \text{bit}\\ \end{aligned}\]可以看出 “红不红”（H）这个特征的信息增益比较大，意味着按照该特征进行划分能够更好的降低信息的不确定性，提高信息的纯度，有利于分类。所以应该首先选 “红不红” 这个特征来进行划分，因此构建决策树如下：
flowchart TD;
A[红不红] --不红--> D[不甜];
A[红不红] --红--> B[圆不圆];
B[圆不圆] --不圆--> C[不甜];
B[圆不圆] --圆--> E[甜];
信息增益又被称为互信息（mutual information），等价于训练数据集中类别与特征的互信息。
4.2. C4.5 算法
4.2.1. 信息增益的局限
ID3 算法使用信息增益时存在两个局限性。
首先，当某个特征的取值非常多时，对该特征计算条件熵几乎为0，带来的信息增益几乎等于原始数据本身的信息熵，此时因为其信息增益最大，ID3 算法会使用该特征进行决策树划分，这种情况下会造成过拟合。
比如，对上述苹果数据集进行扩充，引入价格特征如下：
| 苹果编号 | 价格P | 红不红H | 圆不圆Y | 甜不甜T |
|---|---|---|---|---|
| 1 | 5.7 | 1 | 1 | 1 |
| 2 | 6.5 | 1 | 1 | 1 |
| 3 | 5.1 | 1 | 0 | 0 |
| 4 | 5.2 | 0 | 1 | 0 |
| 5 | 6.0 | 0 | 1 | 0 |
每一个价格唯一对应一个样本，因此每组仅含有1个样本，纯度为100%。对价格计算条件熵为
\[H(T \vert P=5.7) = H(T \vert P=6.5) = \cdots = 0\;\text{bit}\] \[H(T\vert P) = -\sum_{i=1}^5 P_i\log_2 H(T\vert P_i) = -\sum_{i=1}^5 \frac{1}{5}\cdot 0 = 0\;\text{bit}\]信息增益为
\[\text{IG}(T,P) = H(T) - H(T\vert P) = 0.971 - 0 = 0.971\;\text{bit}\]则价格特征的信息增益最大，应该按照该特征进行划分，很显然这是不对的。
其次，信息增益的数值是相对于训练数据集而言的，观察其计算公式可以发现其计算过程和样本的个数有关，并没有绝对意义。
因此我们需要对 ID3 算法进行改进。
4.2.2. 信息增益比（增益率）
采用信息增益比来代替信息增益进行特征选择，该方法称为 C4.5 算法。特征 $X$ 对训练数据集 $D$ 的信息增益比定义为：信息增益与特征 $X$ 对数据集划分的信息熵 之比，即
\[\text{Gain Ratio} = \frac{\text{IG}(D,X)}{H_X(D)} = \frac{\text{IG}(D,X)}{\text{SplitInfo}(X)}\]特征 $X$ 对数据集划分的信息熵 又称为 分裂信息（Split Information），其衡量该特征的分布均匀程度。其定义为
\[\text{SplitInfo}(X) = -\sum_{i=1}^n \frac{D_i}{D} \log_2 \frac{D_i}{D}\]其中 $n$ 为特征 $X$ 的不同取值个数，$D_i$ 表示特征 $X$ 的第 $i$ 个取值对应的数据集的个数，$D$ 表示训练数据集 $D$ 的个数。
对上述苹果数据集，三个特征的分裂信息为：
\[\begin{aligned} \text{SplitInfo}(H) &= - \sum_{i=0}^1 P(H=i) \log_2 P(H=i) \approx 0.971\; \text{bit} \\ \text{SplitInfo}(Y) &= - \sum_{i=0}^1 P(Y=i) \log_2 PY=i) \approx 0.722\; \text{bit}\\ \text{SplitInfo}(P) &= - \sum_{i=\textcolor{red}{1}}^{\textcolor{red}{5}} P(P=i) \log_2 P(P=i) \approx 2.321\; \text{bit} \end{aligned}\]则三个特征的信息增益比为：
\[\begin{aligned} \text{Gain Ratio}(T,H) &= \frac{0.420}{0.971} = 0.433 \;\text{bit}\\ \text{Gain Ratio}(T,Y) &= \frac{0.171}{0.722} = 0.237 \;\text{bit}\\ \text{Gain Ratio}(T,P) &= \frac{0.971}{2.321} = 0.418 \;\text{bit} \end{aligned}\]可以发现，“红不红” 特征的信息增益比最大。因此 4.5 算法可以有效客服高基数特征（取值多的特征）带来的影响。
4.3. CART 算法
ID3 和 C4.5算法，生成的决策树是多叉树（叉的个数与选取的特征的取值个数有关，每个特征只会参与一次节点建立），且只能处理分类不能处理回归。下面介绍的 CART 算法形成的决策树是二叉树，具备更好的数学性质，且既可用于分类也可用于回归。如果配合剪枝、集成等策略，基于CART 算法生成的决策树可构建出很多非常优秀的模型，比如随机森林、随机梯度上升树等。
4.3.1. 基尼指数
基尼指数是决策树（如CART算法）中用于衡量数据不纯度的指标，类似于信息熵（Entropy），但计算更高效（不用计算 $\log_2$）。
假设数据集 $D$ 中的目标变量 $Y$ 有 $c$ 个类别，则基尼指数定义为：
\[\text{Gini}(D) = 1 - \sum_{i=1}^{c} p_i^2 = 1- \sum_{i=1}^{c} (\frac{D_i}{D})^2\]对于所有样本的特征 $X$，假设其有 $k$ 个取值，将这些取值从小到大排列为 $x_1, x_2, \cdots, x_k$，分别取两个相邻特征值的均值作为分裂点，则一共有 $k-1$ 个分裂点，第 $i$ 个分裂点为 $t_i = ({x_i+x_{i+1}})/{2}$。
则特征 $X$ 条件（分裂）下的基尼指数定义为：
\[\begin{aligned} &D_{\text{left}} = \{D\vert X\leq t_i\},\quad D_{\text{right}} = \{D\vert X>t_i\}\\ &\text{Gini}_{\text{split}}(D) = \frac{D_{\text{left}}}{D} \text{Gini}(D_{\text{left}})+ \frac{D_{\text{right}}}{D} \text{Gini}(D_{\text{right}}) \end{aligned}\]基尼指数反应数据集 $D$ 的不确定性，特征 $X$ 条件下（分裂后）的基尼指数反应了特征 $X$ 条件下（分裂后）数据集 $D$ 的不确定性。
与信息增益类似，分裂前后的基尼指数的变化反映了特征的好坏。我们可以直接选择特征条件下基尼指数小的特征作为分裂特征，此时表示经由该特征分裂后，数据集的基尼指数下降的多。
4.3.2. CART 分类树
使用基尼系数作为决策树特征划分的指标的方法称为 「CART 算法」（Classification and Regression Trees）。下面结合算法伪代码，给出 CART 算法生成二叉树分类决策树的过程：
- 输入：训练数据集 $D$，阈值；
- 从根节点开始，递归地对每个节点进行以下操作，构建二叉树：
- Step0：判断当前节点是否满足停止计算的条件，若满足则退出当前递归循环。停止计算的条件为：达到最大深度阈值、节点中的样本个数小于阈值，或样本集的基尼指数小于阈值，或者没有更多特征。
- Step1：计算现有特征对该数据集D的基尼指数。即对每一个特征A，对其可能取的每个值 ，根据样本是否满足 $A=a$ 将 $D$ 划分为 $D_1$和 $D_2$ 两部分，计算 $A=a$ 条件下的基尼指数 $\text{Gini}_{A=a}(D)$；
- Step2：在所有可能的特征 $A$ 以及他们所有可能的划分点 $a$ 中，选择基尼指数最小的特征及其对应可能的划分点作为最优特征和最优划分点。根据最优特征和最优划分点，从现节点生成两个子节点 $A\geq a, \;A < a $，将训练数据集依特征分配到两个子节点中去；
- Step3：对两个子节点，返回 Step0 继续递归；
- 输出：CART 决策树 $T$。
在使用决策树时，抵达叶子节点后，叶子节点负责做出最终决策。它可以输出以下几种结果：
- 「类别标签」：在分类任务中，叶子节点输出数据点所属的类别，由该节点中样本的多数决定；
- 「类别概率」：在概率分类任务中，叶子节点输出数据点属于不同类别的概率；
- 「标量取值」：在回归任务中，叶子节点输出一个连续的数值结果，为叶子节点所含所有样本点的均值。
4.3.3. CART 回归树
对于回归问题，CART 采用均方误差（MSE）来衡量误差
\[MSE(D) = \frac{1}{D}\sum_{i=1}^{D}(y_i - \bar{y})^2\]其中 $\bar{y}$ 是数据集 $D$ 中所有样本的均值。
对数据进行分裂，得到两部分$D_{\text{left}},D_{\text{right}} $，则分裂后的均方误差为：
\[MSE_{\text{split}}(D) = \frac{D_{\text{left}}}{D} MSE(D_{\text{left}})+ \frac{D_{\text{right}}}{D} MSE(D_{\text{right}})\]目标是找到使得 $MSE_{\text{split}}$ 最小的分裂方式。
与 CART 分类树类似，回归树的生成过程主要包括：
- 计算所有可能分裂点的 MSE，选择最优分裂点。
- 递归分裂，直到满足停止条件（如叶子节点的样本数小于某个阈值）。
- 叶子节点的输出是该节点样本的均值。
4.3.4. 三种决策树构建算法区别
- CART 算法：
- 【树结构】：二叉树（严格二叉树，每个节点只有左右两个分支）；
- 【分裂规则】：
- 对分类问题：使用 基尼指数（Gini Index） 选择最优特征和分割点；
- 对回归问题：使用 均方误差（MSE）；
- 【分裂方式】：
- 对于连续特征：通过阈值二分（如”红程度 ≥ 0.5”）；
- 对于类别特征：通过”是/否”二分（如”颜色=红色?”）。
- C4.5 算法：
- 【树结构】：多叉树（一个节点可以有多个子节点，取决于特征取值数量）；
- 【分裂规则】：使用信息增益比（Gain Ratio）；
- 【分裂方式】：直接按特征的所有可能取值划分（如“颜色$\in${红,黄,绿}”生成3个子节点）；
- ID3 算法：
- 【树结构】：多叉树（类似C4.5，但无连续特征处理能力）；
- 【分裂规则】：使用信息增益（Information Gain）；
- 【局限性】：
- 只能处理离散特征，不能直接处理连续特征或缺失值；
- 对多值特征敏感（可能生成过深的树）。
为什么CART必须是二叉树？
- 计算效率：二分法简化了特征选择和分割点搜索（尤其对连续特征）。
- 泛化能力：避免多值特征导致过拟合（如“用户ID”若多叉划分会完全拟合数据）。
- 统一性：回归和分类问题均可使用相同的二分框架。
思考：CART 如何处理缺失值特征？
- 赋给所有训练样本中该属性的最常见值；
- 赋给它对应类别的训练样本中该属性的最常见值；
- 为缺失值的每个可能值赋予一个概率，而不是简单地将最常见的值赋给它。
4.4. 局限性与剪枝
对于构建（特别是 CART 算法）得到的决策树，一个很大的局限性是树存在较大的过拟合问题。因此我们需要采取剪枝来缓解过拟合问题。
剪枝是从已经生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶子节点，从而简化决策树模型的方法。
剪枝分为先剪枝和后剪枝：
- 先剪枝就是控制决策树的生长，在决策树构建过程中决定某节点是叶节点、还是继续分枝。这在前述算法伪代码中有所体现；
- 后剪枝是在决策树得到充分生长之后，再对其进行修剪。从叶节点开始，合并具有相同父节点的叶节点后不会导致纯度明显降低，则执行合并。
5. 分类器集成
分类器集成是机器学习中集成学习领域的一个子集，是针对模式识别中分类问题的应用。
集成学习原名为 Classifier combination / ensemble learning，它是根据训练数据构造一组基分类器（base classifier），通过聚合每个基分类器的输出来进行分类。
- 基分类器的性能取决于它选择的分类算法和训练集；
- 对于单个性能比较弱的基分类器，称之为弱分类器（错误率略优于0.5）；
- 对于单个性能比较强的基分类器，称之为强分类器（准确率很高，并且能在多项式时间内完成）。
多项式时间是计算机科学中用于衡量算法时间复杂度的核心概念，指算法的运行时间随输入规模 $n$ 的增长可按某个多项式函数（如 $O(n^k)$）增长。该概念是区分 “高效” 算法与 “低效” 算法的重要标准
常见的多项式复杂度算法包括：
- $O(n^2)$：如冒泡排序的最差情况；
- $O(n\log n)$：如快速排序的最差情况；
- $O(n)$：如遍历数组的最差情况；
多项式时间算法的效率显著高于超多项式时间（如指数时间 $O(2^n)$ 或阶乘时间 $O(n!)$）。当输入规模增大时，后者的运行时间会急剧上升，远超实际可行性。
根据多项式时间可以判定一些问题的求解难度：
- P类问题：可在多项式时间内解决的判定问题，例如排序、最短路径等；
- NP类问题：虽不确定是否存在多项式时间解法，但可在多项式时间内验证解的正确性，例如旅行商问题（TSP）的判定版本。NP完全性理论进一步探讨了这类问题的计算难度边界。
为什么需要集成学习?
- 弱分类器间存在一定的差异性 ，这会导致分类的边界不同，也就是说可能存在错误。那么将多个弱分类器合并后，就可以得到更加合理的边界，减少整体的错误率，实现更好的效果;
- 对于数据集过大或者过小，可以分别进行划分和有放回的操作产生不同的数据子集，然后使用数据子集训练不同的分类器，最终再合并成为一个大的分类器;
- 如果数据的划分边界过于复杂，使用线性模型很难描述情况，那么可以训练多个模型，然后再进行模型的融合;
- 对于多个异构的特征集的时候，很难进行融合，那么可以考虑每个数据集构建一个分模型，然后将多个模型融合。
关于多个弱分类器集成能提高分类效果降低错误率的分析如下：考虑一种简单的情况，对于一个二分类问题 $y\in{-1,+1}$，最简单直接的集成策略就是少数服从多数的投票，即对于 $T$（不妨设为奇数）个基分类器 $h_i(\boldsymbol{x}),\; i=1,\ldots,T$ 的投票结果为
\[H(\boldsymbol{x}) = \text{sign}\left[ \sum_{i=1}^T h_i(\boldsymbol{x}) \right]\]集成分类器若分类错误，相当于假设有 $k=[0,(T-1)/2]$ 个基分类器分类正确，此时分类正确的基分类器占少数，所以总分类器实际上是错分的。因此，计算集成分类器的错误率需要对 $k$ 进行遍历，然后计算不同 $k$ 取值下的概率和。假设基分类器的错误率相互独立，且错误率均为 $\varepsilon$，则集成分类器的错误率为
\[E = \sum _{k=0}^{(T-1)/2} C_T^k (1-\varepsilon)^k\varepsilon^{T-k}\]上式根据一个很复杂的变换可以转化为下面的格式
\[E \leq \exp (-\frac{1}{2} T(1-2\varepsilon)^2)\]即集成学习其分类错误的概率存在一个上限值，这个值在 $\varepsilon = 0.5$ 时达到最大值 1。当 $\varepsilon$ 保持不变的情况下，集成分类器的错误率随着分类器数目 $T$ 的增大呈现指数级的缩小。
上述分析有一个关键假设，基分类器的误差相互独立。现实任务中，基分类器是为了解决同一个问题（甚至基于同一个数据集）而训练出来的，显然不可能相互独立。事实上，基分类器的 “准确性” 和 “多样性” 本身就存在冲突，如何产生 “好而不同” 的基分类器是集成学习研究的核心。
根据集成学习的思想不同，分为 Bagging、Boosting、Stacking 等。
5.1. Bagging
Bagging 方法又叫做自举汇聚法（Bootstrap Aggregating），是一种并行的算法。其基本思想是︰在原始数据集上通过有放回的抽样的方式，重新选择出 $T$ 个新数据集来分别训练 $T$ 个分类器的集成技术。也就是说这些模型的训练数据中允许存在重复数据。
-
Bagging 的“自举”（Bootsrap）：从训练集里面采集固定个数的样本，但是每采集一个样本后，都将样本放回。也就是说，之前采集到的样本在放回后有可能继续被采集到。
-
Bagging 的汇聚（Aggregating）：对于分类问题，通常使用简单投票法，得到最多票数的类别或者类别之一为最终的模型输出。对于回归问题，通常使用简单平均法，对 $T$ 个弱学习器得到的回归结果进行算术平均得到最终的模型输出。
由于 Bagging 算法每次都进行采样来训练模型，因此泛化能力很强，对于降低模型的方差很有作用。当然对于训练集的拟合程度就会差一些，也就是模型的偏差会大一些。
Bagging 方法的弱学习器可以是前面介绍过的基本算法模型，比如 Linear、ID3、C4.5、CART、SVM、KNN 等。如果 Bagging 中每一个弱分类器都是一个决策树，那么称该方法为 「随机森林」。
5.1.1. 随机森林
在 Bagging 集成策略的基础上，通过构建决策树作为弱分类器，可以得到随机森林（Random Forest），具体步骤如下：
- 从样本集 $N$ 中用 Bootstrap 采样选出 $n$ 个样本；
- 从所有属性 $K$ 中随机选择 $k\ll K$ 个属性，选择出最佳分割属性作为节点创建决策树；
- 重复以上两步 $m$ 次，即建立 $m$ 棵决策树；
- 这 $m$ 个决策树形成随机森林，通过投票表决结果决定数据属于那一类。
随机森林中「随机」二字的内涵之一就是源于 Bagging 思想中对样本的随机抽样和放回操作。抽样数据在一定程度上体现了全体样本数据的特性，所以可以用样本数据训练模型来预测其他的全体数据。但是，抽样数据与全体样本数据之间仍然是存在差异性的，弱分类器（决策树）在拟合各自抽样得到的数据集时，有可能出现不拟合生产环境中数据的情况，这就是过拟合。
在决策树中，进行特征属性划分选择的时候，如果选择最优，表示这个划分在当前数据集上一定是最优的，但是不一定在全体数据中最优；在随机森林中，如果每个决策树都是选择最优的进行划分，就会导致所有弱分类器模型（决策树）很大概率上会使用相同的特征属性进行数据的划分，容易导致过拟合，所以在随机森林中一般使用随机的方式选择特征属性划分，这也是随机森林中「随机」二字的内涵之一。
影响随机森林的分类效果因素包括：
- 随机森林中任意两棵树的相关性，相关性越强错误率越大；
- 森林中每棵树的分类能力，越强则整棵树的错误率越小；
- 特征 $k$ 的个数，减少特征个数，树的相关性和分类能力都会下降；反之二者也会随之增大。
特征个数 $k$ 和树的个数 $m$ 是随机森林的两个参数，其中 $k$ 的选择是随机森林的一个重要参数，因为其对随机森林的性能影响很大。
5.2. Boosting
在正式介绍Boosting思想之前，先介绍一个例子：将每次测验的错的题目记录在错题本上，不停的翻阅，直到我们完全掌握。这个例子都说明 Boosting 的道理，也就是不断重复学习达到最终的要求。
Boosting 的思想源于计算学习理论中的概率计算正确理论 PAC（Probably Approximately Correct）。某个模型如果称为 PAC 可学习的（learnable ），则存在一种算法能够以很大的概率，学到一个很高的精确度，并且在多项式时间内完成。实际上，由于需要对任意高的概率和精确度都可学习，只有很少的模型是属于 PAC 可学习范畴的 “强” 可学习模型。“弱” 可学习模型只能保证以任意高的概率学到比随机猜测好一点。
Valiant 和 Kearns 首次提出了 PAC 学习模型中弱学习算法和强学习算法的等价性问题，即任意给定仅比随机猜测略好的弱学习算法，是否可以将其提升为强学习算法。
Schapire 于 1990 年构造性地证明了：“弱”可学习模型与“强”可学习模型这两个概念是等价的。说明，任何弱学习算法都可以被组合成一个强学习算法。这个证明就是最初实际可用的 Boosting 算法（即 AdaBoost）。
Boosting 方法是按照一定的顺序来训练不同的基模型，每个模型都针对前序模型的错误进行专门训练,从而增加不同基模型之间的差异性。 Boosting 方法是一种非常强大的集成方法，只要基模型的准确率比随机猜测高，就可以通过集成方法来显著地提高集成模型的准确率。
算法的步骤如下：
- 首先从初始训练集训练出一个弱分类器 1，根据弱分类器 1 的表现对训练样本分布进行调整，使得之前弱分类器1识别错误的训练样本在后面得到更多的重视
- 然后基于调整后的训练集来训练弱分类器 2，如此重复进行，直到弱分类器数达到事先指定的数目 $T$
- 最终将这 $T$ 个弱分类器通过集成策略进行整合，得到最终的强分类器。
Boosting 方法的示意图如下所示。
在上述算法步骤中，有两个问题需要进一步解决：
- 如何调整训练集权重用于训练弱分类器？
- 如何将训练好的各弱分类器联合起来形成强分类器？
下面介绍 AdaBoost 算法为上面两个问题提供了一种解决方案。
5.2.1. AdaBoost
AdaBoost（Adaptive Boosting）算法是 Boosting 方法的一种，采用了以下策略：
- 使用加权后选取的训练数据代替随机选取的训练样本，这样将训练的焦点集中在比较难分的训练数据样本上；
- 将弱分类器联合起来，使用「加权的投票机制」代替平均投票机制。让分类效果好的弱分类器具有较大的权重，而分类效果差的分类器具有较小的权重。
对于一个二分类任务而言，首先对样本集中所有 $n$ 样本点的权重初始化为相同的大小，对于第 $t=1$ 次迭代时有
\[w_t(i) = \frac{1}{n}, i = 1, 2, \cdots, n\]调用弱学习算法，产生一个基分类器 $h_t$，该分类器的「加权错误率」为 $\varepsilon_t$，可得
\[\varepsilon_t = \sum_{i=1}^n w_t(i) \cdot l_{0/1}\{y_i \neq h_t(x_i)\},\; y\in\{-1,+1\}-\]其中 $l_{0/1}$ 为 0/1 计数函数，当括号内条件满足时为 1，否则为 0。
定义 $\alpha_t$ 为基分类器 $h_t$ 的权重系数，其计算公式为
\[\alpha_t = \frac{1}{2} \ln \left( \frac{1 - \varepsilon_t}{\varepsilon_t} \right)\]当 $\varepsilon = 0.5$ 时（相当于基分类器随机猜测），对应权重系数为 0。但凡基分类器是一个弱分类器，其权重系数就会大于零。基分类器性能越好，错误率越小，权重系数越大。注意，此处的权重定义并非随意指定的，而是可以通过加性模型（Additive Model）的梯度下降优化或指数损失函数的最小化严格推导得出，详见后文。
但凡弱分类器的错误率 $\varepsilon < 0.5$，即可对样本集中的所有样本更新权值分布，即
\[w_{t+1}(i) = \begin{cases} w_t(i)\exp(-\alpha_t),\; h_i(\boldsymbol{x}) = y_i\\ w_t(i)\exp(\alpha_t),\; h_i(\boldsymbol{x}) \neq y_i \end{cases}\]也即对于误分的样本其权值会乘以一个 $\exp(\alpha_t) > 1$ 的系数；反之则会乘以一个 $\exp(-\alpha_t) < 1$ 的系数。可将其写为一行的简化形式，并进行归一化
\[\begin{aligned} w_{t+1}(i) &= w_t(i)\exp(-\alpha_t \cdot y_i h_t(\boldsymbol{x}_i))\\ w_{t+1}(i) &= \frac{w_{t+1}(i)}{\sum_{j=1}^n w_{t+1}(j)} \end{aligned}\]基于权重更新过后的样本集再次设计新的基分类器。如此重复经过全部 $T$ 轮迭代后，定义最终的强分类器为 $H$，其为迭代过程中所有基分类器 $h_t$ 按照一定的规则组合起来，一种加权投票的组合形式如下
\[H(\boldsymbol{x}) = \text{sign}\left(\sum_{t=1}^T \alpha_th_t(\boldsymbol{x})\right)\]所以，与前面介绍的 Bagging 算法不同，AdaBoost 是一种「串行」的算法，通过弱学习器开始加强，它每一步产生弱预测模型（如决策树），并加权累加到总模型中。
5.2.2. 加性模型与指数损失函数
AdaBoost可视为对加性模型
\[H(\boldsymbol{x}) = \sum_{t=1}^T \alpha_th_t(\boldsymbol{x})\]的优化，其目标是最小化指数损失函数
\[L(H) = \mathbb{E}_{(\boldsymbol{x},y)\sim D}[e^{-yH(\boldsymbol{x})}]\]当预测正确时，$yH(\boldsymbol{x})>0$，损失较小；反之损失较大。
在第 $t$ 轮迭代中，假设已经得到前 $t-1$ 轮的模型 $H_{t+1}(x)$，当前目标是找到一个弱分类器 $h_t(\boldsymbol{x})$ 和权重 $\alpha_t$ 使得以下损失函数最小化
\[L(\alpha_t, h_t) = \mathbb{E}_D\left[e^{-y(H_{t-1}(\boldsymbol{x}) + \alpha_t h_t(\boldsymbol{x}))}\right]\]令
\[w_t(i) = e^{-y_i H_{t-1}(\boldsymbol{x}_i)}\]为前 $t-1$ 轮累计的权重因子，则损失函数变为
\[L(\alpha_t, h_t) = \sum_{i=1}^n w_t(i)e^{-y_i\alpha_t h_t(\boldsymbol{x}_i)}\]损失函数可按分类结果拆分为两部分
\[L(\alpha_t) = \sum_{y_i=h_t(\boldsymbol{x}_i)}^n w_t(i)e^{-\alpha_t}+\sum_{y_i\neq h_t(\boldsymbol{x}_i)}^n w_t(i)e^{\alpha_t}\]定义第 $t$ 轮迭代得到的基分类器 $h_t$ 的加权错误率为
\[\varepsilon_t = \frac{\sum_{y_i\neq h_t(\boldsymbol{x}_i)} w_t(i)}{\sum_{i=1}^n w_t(i)}\]则损失函数可以表示为
\[L(\alpha_t) = (1-\varepsilon_t)e^{-\alpha_t} + \varepsilon_te^{\alpha_t}\]对损失函数关于 $\alpha_t$ 求导并令导数为零，有
\[(1-\varepsilon_t)e^{-\alpha_t} = \varepsilon_te^{\alpha_t} \; \Rightarrow \; \frac{1-\varepsilon_t}{\varepsilon_t} = e^{2\alpha_t} \; \Rightarrow \; \alpha_t = \frac{1}{2}\ln \left( \frac{1 - \varepsilon_t}{\varepsilon_t} \right)\]上述推导和前面基分类器系数定义是一致的。
5.3. 集成表决策略
将个体学习器结合为集成学习器的方法有很多种，下面简单进行介绍总结。
- 平均法
- 简单平均法：$H(x) = \frac{1}{N}\sum_{i=1}^N h_i(x)$
- 加权平均法:$H(x) = \sum_{i=1}^N \alpha_i h_i(x)$
- 投票法
- 绝对多数投票：如果某个标签的的票数超过半数，则预测为该标记；否则拒绝该标记
- 相对多数投票：预测为得票数最多的类别，如果有多个类别的票数相同且都最高，那么从这几个类别中随机选择一个
- 加权投票：与前述加权平均法类似，对每个基分类器施加权重，再输出得票最多的类别。
- 学习法
- 当训练数据过多时，使用简单的结合策略可能会导致很大的误差，这时可以采用一个更为强大的学习策略：学习法，即通过另一个学习器来进行结合。最为著名的学习法的代表就是「Stacking」方法，这里我们把个体学习器称为初级学习器，把用于结合的学习器称为次级学习器。
5.4. Stacking
前述 Boosting 和 Bagging 通常都是使用同一种基分类器，因此我们一般称之为同质集成方法。Stacking 通常都是基于多个不同的基分类器做的集成，因此我们称之为异质集成方法。
可参考：https://zhuanlan.zhihu.com/p/501426671
6. 参考文献
[1] 周志华. 机器学习. 北京：清华大学出版社, 2016.
[2] T. M. Cover and P. E. Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13:21–27, January 1967.