机器学习

前言

本博客记录 Machine Learning 相关内容，初稿完成于大二下学期。由于初学时的一知半解，导致在后续的课程学习中屡屡碰壁，一问三不知，因此后续有时间就会对内容进行优化。笔记主要围绕 基础、模型、特征、拓展 四个方面展开。

注意：如果内容标上了小节号，表明其已经经过了绝对的考量，可以放心参考；反之，请谨慎参考并根据下列引用资料积极寻找原作进行校对。

部分参考引用资料如下：

[1] 周志华，机器学习与模式识别，清华大学出版社，2016.

[2] 机器学习公式详解，人民邮电出版社，https://github.com/datawhalechina/pumpkin-book，2023.

[3] 邱锡鹏，神经网络与深度学习，机械工业出版社，https://nndl.github.io/, 2020.

基础

基本概念

首先给出 ML 中的一些术语：

术语	含义
机器学习定义	利用 经验 改善系统自身性能，主要研究 智能数据分析 的理论和方法。
计算学习理论	最重要的理论模型是 PAC(Probably Approximately Correct, 概率近似正确) learning model，即以很高的概率得到很好的模型 $P(
P 问题	在多项式时间内计算出答案的解
NP 问题	在多项式时间内检验解的正确性
学习任务	监督学习、无监督学习、半监督学习、强化学习
泛化能力	应对未见样本的平均拟合能力
假设空间	所有可能的样本组合构成的集合空间
独立同分布假设	历史和未来的数据来自相同的分布
No Free Launch 理论	没有绝对好的算法，只有适合的算法。好的算法来自于对数据的好假设、好偏执。大胆假设，小心求证。

机器学习的 4 大流程：获取数据 $\to$ 确定模型 $\to$ 学习准则 $\to$ 优化算法。具体的：

• 获取 数据 后我们要对数据进行预处理，进行诸如：数据清洗、特征筛选等过程；
• 有了数据我们需要根据数据特点和任务场景确定好待学习的 模型，例如线性模型还是非线性模型等；
• 我们还需要根据学习任务确定 学习准则，也就是需要确定损失函数，当然这是针对监督学习而言。对于无监督学习，同样有类似的诸如模型度量等策略；
• 基于学习准则得到的损失函数都是我们需要优化的目标，诸如最小化最大化等等，针对这些损失函数我们可以采用优化理论中的各种 优化 算法来迭代求解。

模型评估

我们知道，ML 的最终任务就是学习一个合适的模型用来拟合和预测数据，那我们如何评价一个模型的好坏从而选择最优的模型呢？下面将先从数据集划分的策略开始，讨论模型的误差类型以及性能度量的指标，然后基于这些度量策略谈谈调参，最后从原理上讲讲模型误差的组成。

1 数据集划分

数据集的划分策略大约有以下三种：

留出法（hold-out）：将数据集分为三个部分，分别为训练集、验证集、测试集。测试集对于训练是完全未知的，我们划分出测试集是为了模拟未来未知的数据，因此当下的任务就是利用训练集和验证集训练出合理的模型来尽可能好的拟合测试集。那么如何使用划分出的训练集和验证集来训练、评估模型呢？就是根据模型的复杂度 or 模型训练的轮数，根据上图的曲线情况来选择模型。

交叉验证法（cross validation）：一般方法为 p 次 k 折交叉验证，即 p 次将训练数据随机划分为 k 个大小相似的互斥子集。将其中 $k-1$ 份作为训练数据，$1$ 份作为验证数据，每轮执行 $k$ 次获得平均误差。执行 p 次划分主要是为了减小划分方法带来的误差。

自助法（bootstrapping）：有放回采样获得训练集。每轮从数据集 $D$ 中（共 $m$ 个样本）有放回的采样 $m$ 次，这 $m$ 个抽出来的样本集合 $D'$ 大约占数据集的 $\frac{2}{3}$，于是就可以将抽出的样本集合 $D'$ 作为训练集，$D-D'$ 作为测试集即可。

▶

自助法的测试集占比 1/3 证明过程

2 模型误差

知道了数据集的划分策略后，针对不同的数据，模型会对应不同的误差。有以下四种：

• 训练误差。针对训练数据而言，训练轮数越多或模型的复杂度越高，训练误差越小；
• 验证误差。针对验证数据而言，就是模型在验证集上的误差；
• 测试误差。针对测试数据而言，分错的样本数 $a$ 占总样本数 $m$ 的比例 $E=\frac{a}{m}$；
• 泛化误差。针对测试数据而言，一般说来泛化误差就是 测试误差的期望。

一般来说，训练误差 $<$ 验证误差 $<$ 测试误差 $\approx$ 泛化误差。下图展示了训练误差与测试误差随模型复杂度的变化趋势：

可以看到，模型复杂度不够就会欠拟合，模型复杂度过高就会过拟合。如何解决欠拟合和过拟合呢？这里简单讲一下对应的策略：

欠拟合解决方法：

• 决策树：拓展分支；

• 神经网络：增加训练轮数。

过拟合解决方法：

• Early Stopping (当发现有过拟合现象就停止训练)

• Penalizing Large Weight (在经验风险上加一个 正则化 项，其实是一个范数)

• Bagging 思想 (对同一样本用多个模型投票产生结果)

• Boosting 思想 (多个弱分类器增强分类能力，降低偏差)

• Dropconnection (神经网络全连接层中减少过拟合的发生)

▶

正则化概念补充

在损失函数中添加正则化范数约束到底有什么好处？

1. 防止过拟合。为什么？其实可以形象化的将添加的正则化项理解为一个可以调节的「累赘」，为了让原始问题尽可能的最优，我让累赘愈发拖累目标函数的取值，这样原始问题就不得不更优以此来抵消累赘带来的拖累。
2. 可以进行特征选择。个人认为属于第一点的衍生意义，为什么这么说？同样用累赘来比喻正则化项。当原始问题的某些变量为了代偿拖累导致系数都接近于零了，那么这个变量也就没有存在的意义了，于是对应的特征也就被筛选掉了，也就是所谓的特征选择了。常常添加 L1 正则化项来进行所谓的特征选择。
3. 提升计算效率。同样可以理解为第三点的衍生意义，为什么这么说？因为都把变量筛掉了，那么对应的解空间是不是就相应的大幅度减少了，于是最优解的搜索也就更加快速了。

当然正则化项并非万能的万金油，在整个目标函数中正则化项有这举足轻重的意义，一旦正则化项的系数发生了微小的变动，对于整个模型的影响都是巨大的。因此有时添加正则化项并不一定可以带来泛化性能的提升。

正则化范数有以下形式：

1. 一般式（即 p 范数的 k 次方）：

   $$||\boldsymbol{x}||_p^k = \left ( \left ( \sum_{i = 1}^{N}|x_i|^{p} \right)^{\frac{1}{p}} \right)^k$$

2. L1 正则化（即 1 范数）：

   $$||\boldsymbol{x}||_1 = \sum_{i = 1}^N |x_i|$$

3. L2 正则化（即 1 范数的平方）：

   $$\begin{aligned}||\boldsymbol{x}||_2^2 &= \left ( \left ( \sum_{i = 1}^{N}|x_i|^{2} \right)^{\frac{1}{2}} \right)^2 \\&= \sum_{i = 1}^{N}|x_i|^{2} \\&= \sum_{i = 1}^{N}x_i^{2}\end{aligned}$$

默认的范数是 2 范数，即：

$$\begin{aligned}||\boldsymbol{x}|| &= \sqrt[2]{\textstyle \sum_{i = 1}^{N}|x_i|^{2} }\end{aligned}$$

3 性能度量

3.1 回归任务

对于回归任务，主要使用「均方误差」作为损失函数来度量回归模型的泛化性能，下面分别介绍：

• 均方误差 (Mean Square Error，简称 MSE)。即模型预测值 $f(\boldsymbol{x}_i)$ 与标签值 $y_i$ 的平均平方误差，也就是所谓的方差。取值范围为 $[0,+\infty]$，越小越好。如下式：

  $$\text{MSE} =\frac{1}{N} \sum_{i = 1}^N (f(\boldsymbol{x}_i) - y_i)^2$$

• $R^2$ 分数。衡量模型预测准确性的统计量，取值范围为 $[-\infty,1]$，越大越好。如下式：

  $$R^2 = 1 - \frac{\sum_{i = 1}^N(f(\boldsymbol{x}_i)-y_i)^2}{\sum_{i = 1}^N(\bar{y} - y_i)^2},\quad \bar{y} = \frac{1}{N}\sum_{i = 1}^N y_i$$

3.2 分类任务

对于二分类任务，主要使用混淆矩阵中的「查准率」和「查全率」来度量二分类模型的性能，但由于这两个指标是相互矛盾的，因此又提出「$F_{\beta}$ 度量」来对这两个指标进行一个侧重。而为了更进一步的度量二分类模型的泛化性能，引入了「P-R 曲线」和「ROC 曲线」两个概念。最后补充介绍多分类模型的性能度量策略。

1）二分类问题

我们可以统计二分类模型的预测结果如下所示：

基于上述分类结果的混淆矩阵 (confusion matrix)，我们有以下度量指标的定义：

• 准确率 (Accuracy)：错误率就是 1 减去准确率

  $$\text{Accuracy}=\frac{TP+TN}{TP+FN+FP+TN}$$

• 查准率/精度 (Precision)：适用于商品搜索推荐，需要尽可能推荐出适当的商品即可，至于商品数量无所谓

  $$P = \frac{TP}{TP+FP}$$

• 查全率/召回率 (Recall)：适用于逃犯、病例检测，需要尽可能将正例检测出来，至于查准率无所谓

  $$R = \frac{TP}{TP+FN}$$

当数据的 类别不平衡 时，有如下两个度量指标：

• 敏感性 (Sensitivity)：

  $$\text{Sensitivity} = \frac{TP}{TP + FN}$$

• 特异性 (Specificity)：

  $$\text{Specificity} = \frac{TN}{FP + TN}$$

由于实际场景中需要 兼顾查准率和查全率，为此我们引入 $F_{\beta}$ 分数 ($F_{\beta}$-score) 进行度量。当 $\beta=1$ 时就是标准的 F1-score，当 $\beta>1$ 时对查全率有偏好，当 $\beta<1$ 时对查准率有偏好。如下式：

$$F_{\beta} = \frac{(1+\beta^2)\times P \times R}{(\beta^2\times P) + R}$$

上述指标都是针对一个混淆矩阵展开，如果需要 度量二分类模型的泛化能力 这是远远不够的。为此我们引入 P-R 曲线和 ROC 曲线。两者的产生方式相同，都是：根据二分类模型对测试数据类别的预测概率划分一个阈值，并将预测概率超过阈值的认为是正例，低于阈值的认为是反例，将阈值依次选择为每个样本（假设为 N 个测试样本）的概率值进行二分类即可得到 N 个混淆矩阵，进而得到曲线中的 N 个数据点。两者的区别就在于横纵坐标的数学表达式不同。

对于 P-R 曲线，横坐标为查全率（Recall），纵坐标为查准率（Precision）。

• 趋势解读：随着截断点阈值值不断下降，很显然查全率 $R$ 会不断上升，查准率 $P$ 会不断下降

• 不同曲线对应了不同阈值下学习器的预测能力。曲线与横纵坐标围成的面积衡量了样本预测排序的质量。因此上图中 A 曲线的预测质量比 C 曲线的预测质量高。但是我们往往会遇到比较 A 与 B 的预测质量的情况，由于曲线与坐标轴围成的面积难以计算，因此我们引入了 平衡点 的概念。平衡点就是查准率与查询率相等的曲线，即 $P=R$ 的曲线。平衡点越往右上，学习器的预测性能越好。因此 A 模型的性能优于 B 模型的性能。

对于 ROC 曲线 (Receiver Operating Characteristic，即受试者工作特征，简称 ROC)，横坐标为假正例率 $\displaystyle FPR = \frac{FP}{FP+TN}$，纵坐标为真正例率 $\displaystyle TPR = \frac{TP}{TP+FN}$。

• 趋势解读：随着截断点的值不断下降，真正例率与假正例率均会不断上升，因为分子都是从 0 开始逐渐增加的

• 不同曲线同样对应了不同阈值下学习器的预测能力。曲线下方的面积 (Area Under ROC Curve，简称 AUC) 同样衡量了样本预测排序的质量。面积越大则对应模型的泛化性能更好。取值范围为 $[0.5,1]$。其中 $0.5$ 表示模型进行随机预测的性能。

2）多分类问题

我们可以将多分类问题拆分为多个二分类问题（ps：假设为 n 个），从而可以获得多个上述的混淆矩阵。而「宏」就是先求每一个混淆矩阵的指标，再取平均；「微」就是先将混淆矩阵的值取平均，再计算指标。如下：

• 宏：先求指标再取平均

  • 宏查准率：$\displaystyle macroP = \frac{1}{n} \sum_{i=1}^n P_i$
  • 宏查全率：$\displaystyle macroR = \frac{1}{n} \sum_{i=1}^n R_i$
  • 宏 $F1$：$\displaystyle macroF_1 = \frac{2 \times macroP \times macroR}{macroP+macroR}$

• 微：先取平均再求指标

  • 微查准率：$\displaystyle microP = \frac{\overline{TP}}{\overline{TP}+\overline{FP}}$
  • 微查全率：$\displaystyle microR = \frac{\overline{TP}}{\overline{TP}+\overline{FN}}$
  • 微 $F1$：$\displaystyle microF_1 = \frac{2 \times microP \times microR}{microP+microR}$

4 调参

学习了数据集的划分方法、模型的误差类型和分类与回归模型的性能度量方法，现在我们可以基于数据和模型进行调参了。所谓的调参，其实就是基于超参数进行的。我们知道一个模型有「可训练」的参数和「不可训练」的超参数，调参调的就是这里的超参数。在将数据集划分为训练集、验证集和测试集的情况下，一般使用训练集学习可训练的参数，使用验证集来度量不同超参数组合下的模型性能，得到最佳的超参数组合后才能最终使用测试集进行测试。

5 偏差与方差

现在我们得到了学习算法的泛化误差，我们还想知道为什么会有这样的泛化误差，即我们应该如何理论的解释这样的泛化性能呢？我们引入 偏差-方差分解 的理论来解释泛化误差。但这个方法一定是完美解释的吗？也有一定的缺点，因此我们还会引入 偏差-方差窘境 的理论来解释偏差和方差对于泛化误差的贡献。

在此之前我们需要知道偏差、方差和噪声的基本定义：

• 偏差：学习算法的期望输出与真实结果的偏离程度，刻画算法本身的拟合能力。
• 方差：使用同规模的不同训练集进行训练时带来的性能变化，刻画数据扰动带来的影响。
• 噪声：当前任务上任何算法所能达到的期望泛化误差的 下界（即不可能有算法取得更小的误差），刻画问题本身的难度。

5.1 偏差-方差分解

我们尝试对泛化误差的组成进行分解。先进行以下的符号定义：$x$ 为测试样本，$y_D$ 为 $x$ 在数据集中的标签，$y$ 为 $x$ 的真实标签，$f(x;D)$ 为模型在训练集 $D$ 上学习后的预测输出。以回归任务为例，有以下的变量定义：（$\mathbb{E}$ 表示 期望 结果）

• 模型的期望输出：$\overline{f}(x) = \mathbb{E}_D[f(x;D)]$
• 使用相同规模的训练集训练出来的模型产生的方差：$var(x) = \mathbb{E}_D[(\overline{f}(x) - f(x;D))^2]$
• 模型的期望输出与真实标记的偏差：$bias^2(x) = (\overline{f}(x) - y)^2$
• 噪声：$\epsilon ^2 = \mathbb{E}_D[(y_D - y)^2]$

最终可以得到偏差-方差分解的结论，即模型的泛化误差 $E(f; D)$ 由以下三个部分组成：

$$E(f; D) = bias^2(x) + var(x) + \epsilon^2$$

▶

推导

解释说明。模型的泛化性能是由学习算法的能力（偏差）、数据的充分性（方差）以及学习任务本身的难度（噪声）共同决定的。因此给定一个学习任务，我们可以从偏差、方差和噪声三个角度优化模型：使偏差尽可能小（选择合适的学习算法充分拟合数据）、使方差尽可能小（提升模型的抗干扰能力来减小数据扰动产生的影响）、使噪声尽可能小（选择合适的数据增强方法来减小因为数据本身带来的误差）。

5.2 偏差-方差窘境

其实偏差和方差是有冲突的，这被称为偏差-方差窘境（bias-variance-dilemma）。如上图所示：对于给定的学习任务，一开始拟合能力较差，学习器对于不同的训练数据不够敏感，此时泛化误差主要来自偏差。随着训练的不断进行，模型的拟合能力逐渐增强，这会加剧模型对数据的敏感度，从而使得方差主导了泛化误差。在模型过度训练后，数据的轻微扰动都可能导致预测输出发生显著的变化，此时方差就几乎完全主导了泛化错误率。

数据平衡

在分类任务的数据集中，往往会出现类别不平衡的问题，即使在类别的样本数量相近时，在使用一对其余等算法进行多分类时，也会出现类比不平衡的问题，因此解决类比不平衡问题十分关键。

阈值移动

常规而言，对于二分类任务。我们假设 $y$ 为样本属于正例的概率，则 $p=\frac{y}{1-y}$ 就是正确划分类别的概率。在假定类别数量相近时，我们用下式表示预测为正例的情况：

$$\frac{y}{1-y}> 1$$

但是显然，上述假设不总是成立，我们令 $m^+$ 为样本正例数量，$m^-$ 为样本反例数量。我们用下式表示预测为正例的情况：

$$\frac{y}{1-y} > \frac{m^+}{m^-}$$

根本初衷 是为了让 $\frac{m^+}{m^-}$ 表示数据类别的真实比例。但是由于训练数据往往不能遵循独立分布同分布原则，也就导致我们观测的 $\frac{m^+}{m^-}$ 其实不能准确代表数据的真实比例。那还有别的解决类别不平衡问题的策略吗？答案是有的！

欠采样

即去除过多的样本使得正反例的数量近似，再进行学习。

• 优点：训练的时间开销小
• 缺点：可能会丢失重要信息

典型的算法是：EasyEnsemble

过采样

即对训练集中类别数量较少的样本进行重复采样，再进行学习。

• 缺点：简单的重复采样会导致模型过拟合数据，缺少泛化能力。

典型的算法是：SMOTE

模型

线性模型

本章介绍机器学习模型中的线性模型。基本形式如下：

$$\begin{aligned} &f(\boldsymbol {x}) = \boldsymbol {w}^T \boldsymbol {x} \\ &\boldsymbol {w} \in R^{D+1}, \boldsymbol {x} \in R^{D+1} \end{aligned}$$

其中 $\boldsymbol {w} = [w_1,w_2,\cdots,w_D,b]^T, \boldsymbol {x} = [x_1,x_2,\cdots,x_D,1]^T$ 均为增广向量。样本的特征个数为 $D$，样本的总个数为 $N$，模型为 $f(\cdot)$。基于此模型，我们就可以通过机器学习来进行分类与回归任务。值得注意的是，尽管线性模型无法解决线性不可分的问题，但其强就强在形式简单、易于建模以及高可解释性，同时也是很多非线性模型的基础。

下面我将根据学习任务，从回归与分类两个角度展开。

线性回归

借着讲解线性回归算法，系统的介绍 4 种参数的 学习策略：经验风险最小化、结构风险最小化、最大似然估计、最大后验估计。

注：输入的样本增广特征矩阵 $\boldsymbol{X}_{(D+1)\times N}$ 为：

$$\boldsymbol{X}=\begin{bmatrix} x_{11} & x_{12} & \cdots & x_{1N} \\ x_{21} & x_{22} & \cdots & x_{2N} \\ \vdots & \vdots & \ddots & \vdots \\ x_{D1} & x_{D2} & \cdots & x_{DN} \\ 1 & 1 & \cdots & 1 \end{bmatrix}$$

经验风险最小化

希望模型在训练集上的平均误差尽可能小，就叫经验风险最小化原则。基于该规则，我们定义学习准则为平方损失函数 $E_{\hat w}$：

$$E_{\hat w} = (y - X \hat w) ^T (y - X \hat w)$$

若 $X^T X$ 可逆，则参数 $\hat w ^* = (X^TX)^{-1}X^Ty$，令样本 $\hat x_i = (x_i,1)$，则线性回归模型为：

$$f(x_i) = \hat x_i ^T \hat w^*$$

结构风险最小化

为了防止在上述经验风险最小化的情况下模型发生过拟合，引入正则化项来降低模型的复杂度，这就是所谓的结构风险最小化。

若上式中 $X^T X$ 不可逆，我们引入 $L_2$ 正则化项 $\alpha || \hat w ||^2$，此时就是所谓的「岭回归」算法：

现在的损失函数就定义为：

$$E_{\hat w} = (y - X \hat w) ^T (y - X \hat w) + \alpha || \hat w ||^2$$

同样将损失函数对参数向量 $\hat w$ 求偏导，得：

$$\begin{aligned} \frac{\partial E_{\hat w}}{\partial \hat w} &= \cdots \\ &= 2X^TX\hat w - 2 X^T y + 2 \alpha \hat w \\ &= 2 X ^T(X \hat w - y) + 2 \alpha \hat w \end{aligned}$$

我们令其为零，得参数向量 $\hat w$ 为：

$$\hat w = (X^T X + \alpha I)^{-1} X^T y$$

最大似然估计

最大后验概率

▶

其他线性回归案例

• 支持向量机回归

• 决策树回归

• 随机森林回归

• LASSO 回归：增加 $L_1$ 正则化项

  

• ElasticNet 回归：增加 $L_1$ 和 $L_2$ 正则化项

  

• XGBoost 回归

logistic二分类

线性模型如何进行二分类任务呢？我们介绍 对数几率回归。对数几率回归准确来说应该叫逻辑回归，但其解决的并且不是回归问题，而是二分类问题。当然，除了逻辑回归，还有 线性判别分析 可以用来进行二分类任务，这里不再展开。

模型

对于二分类任务。我们可以将线性模型的输出结果 $\boldsymbol{w}^T\boldsymbol{x}$ 通过阈值函数 $g(\cdot)$ 进行映射，然后根据映射结果便可以进行二分类。那么什么样的非线性函数可以胜任阈值函数一职呢？

最简单的一种阈值函数就是 单位阶跃函数。映射关系如下：

$$g(x) = \begin{cases} 0, &x < 0 \\ 0.5,& x = 0 \\ 1, & x > 0 \end{cases}$$

但由于单位阶跃函数并不单调可微，这导致我们后续无法对参数进行「基于梯度」的迭代优化。常用的一种数学性质良好、具备单调可微性质的阈值函数是对数几率函数，也叫 逻辑函数 (logistic function)。映射关系如下：

$$g(x) = \frac{1}{1+e^{-x}}$$

于是基于 logistic 函数的二分类模型就定义为：

$$g(\boldsymbol{w}^T\boldsymbol{x}) = \frac{1}{1+e^{-\boldsymbol{w}^T\boldsymbol{x}}}$$

模型有一个可学习参数「权重向量 $\boldsymbol {w}$」和一个不可学习的超参数「分类映射阈值」。其中权重向量 $\boldsymbol{w}$ 已经包含了偏执项 $b$，因此参数个数为 $D+1$；分类映射阈值表示：对于模型输出的一个介于 $0$ 到 $1$ 之间的概率值，需要人为的定义一个超参数 $lim$，当概率超过 $lim$ 时就将样本判定为正例，反之则判定为负例。

注：「对数几率回归」名称的由来。

由于逻辑函数可以将实数域压缩到 $(0,1)$ 之间，因此当我们对线性函数套一层逻辑函数后，就可以将映射的结果视为「样本属于正例的后验概率」，记作 $P(y=1 \ |\ \boldsymbol {x})$。因此有：

$$\begin{aligned}P(y=1 \ |\ \boldsymbol {x}) = \frac{1}{1 + e^{-\boldsymbol{w}^T\boldsymbol{x}}}\end{aligned}$$

那么样本属于负例的后验概率 $P(y=0 \ |\ \boldsymbol {x})$ 就为：

$$\begin{aligned}P(y=0 \ |\ \boldsymbol {x}) &= 1 - P(y=1 \ |\ \boldsymbol {x}) \\&= \frac{e^{-\boldsymbol{w}^T\boldsymbol{x}}}{1 + e^{-\boldsymbol{w}^T\boldsymbol{x}}}\end{aligned}$$

经过简单变形可以得到：

$$\begin{aligned}\boldsymbol{w}^T\boldsymbol{x} = \ln{\frac{P(y=1 \ |\ \boldsymbol {x})}{P(y=0 \ |\ \boldsymbol {x})}}\end{aligned}$$

其中，正例后验概率 $P(y=1 \ |\ \boldsymbol {x})$ 与负例后验概率 $P(y=0 \ |\ \boldsymbol {x})$ 的比值 $\frac{P(y=1 \ |\ \boldsymbol {x})}{P(y=0 \ |\ \boldsymbol {x})}$ 被称作几率，取对数 $\ln{\frac{P(y=1 \ |\ \boldsymbol {x})}{P(y=0 \ |\ \boldsymbol {x})}}$ 就是对数几率。因此逻辑回归可以看作预测值为“标签的对数几率”的线性回归模型。也就有了「对数几率回归」这个别名。

学习准则

我们采用最大似然估计。

若我们将 $y$ 视作类后验概率 $p(y=1 \ | \ x)$，则有

$$\ln \frac{p(y = 1 \ | \ x)}{p(y = 0 \ | \ x)} = w^Tx+b$$

同时，显然有

$$\begin{aligned} p(y = 1 \ | \ x) = \frac{1}{1 + e^{-(w^Tx+b)}} = \frac{e^{w^Tx+b}}{1 + e^{w^Tx+b}} \\ p(y = 0 \ | \ x) = \frac{e^{-(w^Tx+b)}}{1 + e^{-(w^Tx+b)}} = \frac{1}{1 + e^{w^Tx+b}} \end{aligned}$$

于是我们可以确定学习准则了。我们取学习准则为 对数似然函数，于是参数的学习就是需要求解下式：

$$\arg \max_{w, b} l(w, b) = \sum_{i = 1}^m \ln p(y_i\ | \ x_i; w, b)$$

而所谓的对数似然函数，就是 最大化类后验概率 使得样本属于真实标记的概率尽可能大。

我们将变量进行一定的变形：

$$\begin{aligned} \begin{cases} \beta = (w; b) \\ \hat x = (x; 1) \\ \end{cases} &\to w^Tx + b = \beta^T\hat x \\ \begin{cases} p_1(\hat x; \beta) = p(y = 1 \ | \ \hat x; \beta) \\ p_0(\hat x; \beta) = p(y = 0 \ | \ \hat x; \beta) \\ \end{cases} &\to p(y_i\ | \ x_i; w, b) = y_i p_1(\hat x; \beta) + (1 - y_i) p_0(\hat x; \beta) \end{aligned}$$

于是上述对数似然函数就可以进行以下转化：

$$\begin{aligned} l(w, b) &= l(\beta) \\ &= \sum_{i = 1}^m \ln \left [y_i p_1(\hat x; \beta) + (1 - y_i) p_0(\hat x; \beta) \right ] \\ &= \sum_{i = 1}^m \ln \left [y_i p(y = 1 \ | \ \hat x; \beta) + (1 - y_i) p(y = 0 \ | \ \hat x; \beta) \right ] \\ &= \sum_{i = 1}^m \ln \left [ y_i \frac{e^{\beta^T\hat x}}{1 + e^{\beta^T\hat x}} + (1-y_i) \frac{1}{1 + e^{\beta^T\hat x}} \right ] \\ &= \sum_{i = 1}^m \ln \left [ \frac{y_i \beta^T\hat x +1 -y_i}{1 + e^{\beta^T\hat x}} \right ] \\ &= \begin{cases} \sum_{i = 1}^m \ln \left ( \frac{1}{1 + e^{\beta^T\hat x}} \right ), & y_i = 0 \\ \sum_{i = 1}^m \ln \left ( \frac{e^{\beta^T\hat x}}{1 + e^{\beta^T\hat x}} \right ), & y_i = 1\\ \end{cases}\\ &= \sum_{i = 1}^m \ln \left ( \frac{\left(e^{\beta^T\hat x}\right)^{y_i}}{1 + e^{\beta^T\hat x}} \right ) \\ &= \sum_{i = 1}^m \left( y_i e^{\beta^T\hat x} - \ln({1 + e^{\beta^T\hat x}})\right ) \end{aligned}$$

进而从 极大似然估计 转化为：求解「极小化负的上述目标函数时」参数 $\beta$ 的值：

$$\arg \min_{\beta} l(\beta) = \sum_{i = 1}^m \left(- y_i e^{\beta^T\hat x} + \ln({1 + e^{\beta^T\hat x}})\right )$$

优化方法

由于上式是关于 $\beta$ 的高阶可导连续凸函数，因此我们有很多数值优化算法可以求得最优解时的参数值，比如梯度下降法、牛顿法、拟牛顿法等。我们以牛顿法（Newton Method）为例：

最优解 $\beta ^*$ 为：

$$\beta ^* = \arg \min_{\beta} l(\beta)$$

第 $t+1$ 轮迭代解的更新公式：

$$\beta ^{t+1} = \beta^t - \left( \frac{\partial^2{l(\beta)}}{\partial{\beta} \partial{\beta^T}} \right)^{-1} \frac{\partial{l(\beta)}}{\partial{\beta}}$$

其中 $l(\beta)$ 关于 $\beta$ 的一阶导、二阶导的推导过程如下：

感知器二分类

神经元模型

我们介绍 M-P 神经元模型。该神经元模型必须具备以下三个特征：

1. 输入：来自其他连接的神经元传递过来的输入信号
2. 处理：输入信号通过带权重的连接进行传递，神经元接受到所有输入值的总和，再与神经元的阈值进行比较
3. 输出：通过激活函数的处理以得到输出

激活函数可以参考 3.3 中的逻辑函数（logistic function），此处将其声明为 sigmoid 函数，同样不采用不。连续光滑的分段函数。

感知机与多层网络

本目从 无隐藏层的感知机 出发，介绍神经网络在简单的线性可分问题上的应用；接着介绍 含有一层隐藏层的多层感知机，及其对于简单的非线性可分问题上的应用；最后引入多层前馈神经网络模型的概念。

感知机

感知机（Perceptron）由两层神经元组成。第一层是输入层，第二层是输出层。其中只有输出层的神经元为功能神经元，也即 M-P 神经元。先不谈如何训练得到上面的 $w_1,w_2,\theta$，我们先看看上面的感知机训练出来以后可以有什么功能？

通过单层的感知机，我们可以实现简单的线性可分的分类任务，比如逻辑运算中的 与、或、非 运算，下面演示一下如何使用单层感知机实现上述三种逻辑运算：

▶

使用单层感知机实现线性可分任务：与、或、非三种逻辑运算

与运算、或运算是二维线性可分任务，一定可以找到一条直线将其划分为两个类别：

非运算是一维线性可分任务，同样也可以找到一条直线将其划分为两个类别：

多层感知机

所谓的多层感知机其实就是增加了一个隐藏层，则神经网络模型就变为三层，含有一个输入层，一个隐藏层，和一个输出层，更准确的说应该是“单隐层网络”。其中隐藏层和输出层中的所有神经元均为功能神经元。

为了学习出网络中的连接权 $w_i$ 以及所有功能神经元中的阈值 $\theta_j$，我们需要通过每一次迭代的结果进行参数的修正，对于连接权 $w_i$ 而言，我们假设当前感知机的输出为 $\hat y$，则连接权 $w_i$ 应做以下调整。其中 $\eta$ 为学习率。

$$\begin{aligned} w_i \leftarrow w_i + \Delta w_i \\ \Delta w_i = \eta (y - \hat y) x_i \end{aligned}$$

▶

使用多层感知机实现异或逻辑运算

多层前馈神经网络

所谓多层前馈神经网络，定义就是各层神经元之间不会跨层连接，也不存在同层连接，其中：

• 输入层仅仅接受外界输入，没有函数处理功能
• 隐藏层和输出层进行函数处理

误差逆传播算法

多层网络的学习能力比感知机的学习能力强很多。想要训练一个多层网络模型，仅仅通过感知机的参数学习规则是不够的，我们需要一个全新的、更强大的学习规则。这其中最优秀的就是误差逆传播算法（errorBackPropagation，简称 BP），往往用它来训练多层前馈神经网络。下面我们来了解一下 BP 算法的内容、参数推导与算法流程。

模型参数

我们对着神经网络图，从输入到输出进行介绍与理解：

• 隐层：对于隐层的第 $h$ 个神经元
  • 输入：$\alpha_h = \sum_{i=1}^dx_i v_{ih}$
  • 输出：$b_h = f(\alpha_h - \gamma_h)$
• 输出层：对于输出层的第 $j$ 个神经元
  • 输入：$\beta_j=\sum_{h=1}^q b_h w_{hj}$
  • 输出：$\hat y_j = f(\beta j - \theta_j)$

现在给定一个训练集学习一个分类器。其中每一个样本都含有 $d$ 个特征，$l$ 个输出。现在使用 标准 BP 神经网络模型，每输入一个样本都迭代一次。对于单隐层神经网络而言，一共有 4 种参数，即：

• 输入层到隐层的 $d \times q$ 个权值 $v_{ih}(i=1,2,\cdots,d,\ h=1,2,\cdots,q)$
• 隐层的 $q$ 个 M-P 神经元的阈值 $\gamma_h(h=1,2,\cdots,q)$
• 隐层到输出层的 $q\times l$ 个权值 $w_{hj}(h=1,2,\cdots,q,\ j=1,2,\cdots,l)$
• 输出层的 $l$ 个 M-P 神经元的阈值 $\theta_j(j=1,2,\cdots,l)$

参数推导

确定损失函数。

• 对于上述 4 种参数，我们均采用梯度下降策略。以损失函数的负梯度方向对参数进行调整。每次输入一个训练样本，都会进行一次参数迭代更新，这叫 标准 BP 算法。

• 根本目标是使损失函数尽可能小，我们定义损失函数 $E$ 为当前样本的均方误差，并为了求导计算方便添加一个常量 $\frac{1}{2}$，对于第 $k$ 个训练样本，有如下损失函数：

$$E_k = \frac{1}{2} \sum _{j = 1}^l (\hat y_j^k - y_j^k)^2$$

确定迭代修正量。

• 假定当前学习率为 $\eta$，对于上述 4 种参数的迭代公式为：

  $$\begin{aligned} w_{hj} &\leftarrow w_{hj}+\Delta w_{hj} \\ \theta_{j} &\leftarrow \theta_{j}+\Delta \theta_{j} \\ v_{ih} &\leftarrow v_{ih}+\Delta v_{ih} \\ \gamma_{h} &\leftarrow \gamma_{h}+\Delta \gamma_{h} \\ \end{aligned}$$

• 其中，修正量分别为：

  $$\begin{aligned} \Delta w_{hj} &= \eta g_j b_h \\ \Delta \theta_{j} &= -\eta g_j \\ \Delta v_{ih} &= \eta e_h x_i \\ \Delta \gamma_{h} &= -\eta e_h \\ \end{aligned}$$

▶

修正量推导 - 链式法则

公式表示：

隐层到输出层的权重、输出神经元的阈值：

输入层到隐层的权重、隐层神经元的阈值：

算法流程

对于当前样本的输出损失 $E_k$ 和学习率 $\eta$，我们进行以下迭代过程：

还有一种 BP 神经网络方法就是 累计 BP 神经网络 算法，基本思路就是对于全局训练样本计算累计误差，从而更新参数。在实际应用过程中，一般先采用累计 BP 算法，再采用标准 BP 算法。还有一种思路就是使用随机 BP 算法，即每次随机选择一个训练样本进行参数更新。

支持向量机二分类

依然是分类学习任务。我们希望找到一个超平面将训练集中样本划分开来，那么如何寻找这个超平面呢？下面开始介绍。

本章知识点逻辑链：

间隔与支持向量

对于只有两个特征，输出只有两种状态的训练集而言，很显然我们得到如下图所示的超平面，并且显然应该选择最中间的泛化能力最强的那一个超平面：

我们定义超平面为：

$$w^Tx+b = 0$$

定义支持向量机为满足下式的样例：

$$\begin{aligned} w^T+b&= 1 \\ w^T+b&=-1 \end{aligned}$$

很显然，为了求得这“最中间”的超平面，就是让异类支持向量机之间的距离尽可能的大，根据两条平行线距离的计算公式，可知间隔为：

$$\gamma = \frac{2}{|| w ||}$$

于是最优化目标函数就是：

$$\max_{w, b} \frac{2}{||w||}$$

可以等价转化为：

$$\begin{aligned} &\min_{w, b} \frac{1}{2} ||w||^2 \\ &s.t. \quad y_i(w^Tx_i+b) \ge 1 \quad(i = 1,2,\cdots, m) \end{aligned}$$

这就是 SVM（support vector machine）的基本型

对偶问题

将上述 SVM 基本型转化为对偶问题，从而可以更高效的求解该最优化问题。

▶

对偶转化推导

于是模型 $f(x)$ 就是：

$$\begin{aligned}f(x) &= w^Tx+b \\&= \sum_{i = 1}^m\alpha_iy_ix_i^Tx+b\end{aligned}$$

其中参数 b 的求解可通过支持向量得到：

$$y_if(x_i) = 1 \to y_i\left(\sum_{i = 1}^m\alpha_iy_ix_i^Tx+b \right)= 1$$

由于原问题含有不等式约束，因此还需要满足 KKT 条件：

$$\begin{cases}\alpha_i \ge 0&,\text{对偶可行性} \\y_if(x_i) \ge 1&,\text{原始可行性} \\\alpha_i(y_if(x_i)-1) = 0&,\text{互补松弛性}\end{cases}$$

对于上述互补松弛性：

• 若 $\alpha_i > 0$，则 $y_if(x_i)=1$，表示支持向量，需要保留
• 若 $y_if(x_i)>1$，则 $\alpha_i = 0$，表示非支持向量，不用保留

现在得到的对偶问题其实是一个二次规划问题，我们可以采用 SMO（Sequential Minimal Optimization） 算法求解。具体略。

核函数

对原始样本进行升维，即 $x_i \to \phi(x_i)$，新的问题出现了，计算内积 $\phi(x_i)^T \phi(x_i)$ 变得很困难，我们尝试解决这个内积的计算，即使用一个函数（核函数）来近似代替上述内积的计算结果，常用的核函数如下：

表格中的高斯核也就是所谓的径向基函数核 $\text{(Radial Basis Function Kernel, 简称 RBF 核)}$，其中的参数 $\gamma=\frac{1}{2\sigma^2}$，因此 RBF 核的表达式也可以写成：

$$\kappa(x_i, x_j) = \exp(-\gamma \|x_i - x_j\|^2)$$

• 当 $\gamma$ 较大时，$\exp(-\gamma \|x_i - x_j\|^2)$ 的衰减速度会很快。这意味着只有非常接近的样本点才会有较高的相似度。此时，模型会更关注局部特征。并且会导致模型具有较高的复杂度，因为模型会更容易拟合训练数据中的细节和噪声，从而可能导致过拟合。
• 当 $\gamma$ 较小时，$\exp(-\gamma \|x_i - x_j\|^2)$ 的衰减速度会变慢。较远的样本点之间也可能会有较高的相似度。此时，模型会更关注全局特征。但此时模型的复杂度较低，容易忽略训练数据中的细节，从而可能导致欠拟合

软间隔与正则化

对于超平面的选择，其实并不是那么容易，并且即使训练出了一个超平面，我们也不知道是不是过拟合产生的，因此我们需要稍微减轻约束条件的强度，因此引入软间隔的概念。

我们定义软间隔为：某些样本可以不严格满足约束条件 $y_i(w^Tx+b) \ge 1$ 从而需要尽可能减少不满足的样本个数，因此引入新的优化项：替代损失函数

$$l_{\text{option}}$$

常见的平滑连续的替代损失函数为：

我们引入松弛变量 $\xi_i$ 得到原始问题的最终形式：

$$\min_{w, b,\xi_i} \quad \frac{1}{2}||w||^2+C\sum_{i = 1}^m \xi_i$$

支持向量回归

支持向量回归（Support Vector Regression，简称 SVR）与传统的回归任务不同，传统的回归任务需要计算每一个样本的误差，而支持向量回归允许有一定的误差，即，仅仅计算落在隔离带外面的样本损失。

原始问题：

对偶问题：

KKT 条件：

预测模型：

核方法

通过上述：支持向量基本型、支持向量软间隔化、支持向量回归，三个模型的学习，可以发现最终的预测模型都是关于核函数与拉格朗日乘子的线性组合，那么这是巧合吗？并不是巧合，这其中其实有一个表示定理：

$$h^*(x) = \sum_{i = 1}^m\alpha_i \kappa(x, x_i)$$

softmax多分类

我们一般采用多分类+集成的策略来解决多分类的学习任务。具体的学习任务大概是：将多分类任务拆分为多个二分类任务，每一个二分类任务训练一个学习器；在测试数据时，将所有的分类器进行集成以获得最终的分类结果。这里有两个关键点：如何拆分多分类任务？如何集成二分类学习器？集成策略见第 8 章，本目主要介绍 多分类学习任务的拆分。主要有三种拆分策略：一对多、一对其余、多对多。对于 N 个类别而言：

一对一

▶

图例

• 名称：One vs. One，简称 OvO
• 训练：需要对 N 个类别进行 $\frac{N(N-1)}{2}$ 次训练，得到 $\frac{N(N-1)}{2}$ 个二分类学习器
• 测试：对于一个样本进行分类预测时，需要用 $\frac{N(N-1)}{2}$ 个学习器分别进行分类，最终分得的结果种类最多的类别就是样本的预测类别
• 特点：类别较少时，时间和内存开销往往更大；类别较多时，时间开销往往较小

一对其余

▶

图例

• 名称：One vs. Rest，简称 OvR
• 训练：需要对 N 个类别进行 $N$ 次训练，得到 $N$ 个二分类学习器。每次将目标类别作为正例，其余所有类别均为反例
• 测试：对于一个样本进行分类预测时，需要用 $N$ 个学习器分别进行分类，每一个学习器显然只会输出二值，假定为正负。正表示当前样例属于该学习器的正类，反之属于反类。若 $N$ 个学习器输出了多个正类标签，则还需通过执行度选择最终的类别。

多对多

▶

图例

• 名称：Many vs. Many，简称 MvM
• 训练（编码）：对于 N 个类别数据，我们自定义 M 次划分。每次选择若干个类别作为正类，其余类作为反类。每一个样本在 M 个二分类学习器中都有一个分类结果，也就可以看做一个 M 维的向量。m 个样本也就构成了 m 个在 M 维空间的点阵。
• 测试（解码）：对于测试样本，对于 M 个学习器同样也会有 M 个类别标记构成的向量，我们计算当前样本与训练集构造的 m 个样本的海明距离、欧氏距离，距离当前测试样本最近的点属于的类别，我们就认为是当前测试样本的类别。

softmax 函数

将当前测试样本属于各个类别的概率之和约束为 $1$。若共有 $n$ 个输出，则将第 $i$ 个输出 $x_i$ 转化为 $[0,1]$ 取值范围的公式为：

$$P_i =\frac{e^{x_i}}{\sum_{j = 1}^n e^{x_j}}$$

决策树模型

下面介绍一个经典的机器学习模型：决策树模型。可以利用该模型进行有监督的学习任务，比如分类或者回归，下面将会花较多篇幅讲解决策树模型在分类任务上的应用。当然，决策树模型绝不至于此，基于这种划分决策的思想诞生出了很多别的模型，例如：异常检测任务中的孤立森林模型、集成学习任务中的基学习器模型等等，留给读者进一步探索。

1 基本概念

决策树的结构如上图所示。决策树算法遵循自顶向下、分而治之的思想。叶子结点表示分类结果、边表示属性划分、分支结点表示属性选择。

决策树的算法伪代码如上图所示。下面依次解释：

1. 生成分支结点：选择最优的属性作为当前结点决策依据；
2. 生成所有的边：根据当前分支结点的属性在 测试数据 中所有可能的属性取值生成所有的分支；
3. 生成孩子结点：将当前结点的样本根据每一条边对应的属性取值依次划分到对应的孩子结点中；
4. 不断递归：不断重复上述 1-3 步直到递归终点，有以下三种递归终点：
   • 当前结点的训练样本类别均属于某个类别。则将当前结点设定为叶子结点，并标记当前叶子结点对应的类别为 当前结点同属的类别；
   • 当前结点的训练样本数为 $0$。则将当前结点为设定为叶子结点，并标记当前叶子结点对应的类别为 父结点中最多类别数量对应的类别；
   • 当前结点的训练样本的所有属性值都相同。则将当前结点设定为叶子结点，并标记当前叶子结点对应的类别为 当前训练样本中最多类别数量对应的类别。

2 划分策略

一般而言，决策树中每一个结点的分支数量可以是两个，即二路划分，也可以是多个，即多路划分。显然就需要对连续的数值属性进行离散化。但无论是类别属性（二元属性、标称属性、序数属性）还是离散化后的数值属性，划分时都要遵守分组的合法性，如下图所示：

3 属性选择

在递归建树时，如何选择出当前局面下的最优属性来划分样本呢？我们「希望当前结点的所包含的样本尽可能属于同一类」这一根本目的出发，讨论三种最优属性选择策略。

3.1 信息增益

Iterative dichotomiser 3 (ID3) 算法首次在机器学习中引入了信息的概念。具体的：

• 信息量 (Amount of information)。对于一个随机事件 $X$，其发生的概率为 $P$，则该事件是否发生对应的信息量为 $-\log_2 P$。可以看出，一个随机事件发生的可能性越大，对应的信息量就越少；
• 信息熵 (Information Entropy)。信息熵就是所有随机事件 $X_i, i \in N$ 信息量的期望。假设第 $i$ 个随机事件 $X_i$ 发生的概率为 $P_i$，则这些事件的信息熵为 $-\sum_{i=1}^N P_i \log_2P_i$。

而 ID3 算法选择最优属性的核心思路就是选择划分后使得信息增益 (Information gain) 最大的属性。

我们记训练集为 $D$，可供选择的属性列表为 $a,b,\cdots,\gamma$，随机事件定义为当前训练集中每一个类别的占比。假设当前样本集合中含有 $t$ 个类别，第 $k$ 个类别所占样本集合比例为 $P_k$，则当前训练集的信息熵 $\text{Ent}(D)$ 为：

$$\text{Ent}(D) = -\sum _{k = 1}^t P_k \log_2(P_k)$$

属性 $a$ 共有 $V$ 个属性取值，即 $a=\{a^1,a^2,\cdots.a^V\}$，于是便可以将当前结点对应的训练数据集 $D$ 划分为 $V$ 个子结点的训练数据 $D=\{D^1,D^2,\cdots.D^V\}$，由于每一个子结点划到的训练数据量不同，引入权重，则以 a 作为划分属性时得到的信息增益为：

$$\text{Ent\_Gain}(D, a)=\text{Ent}(D) - \sum_{i = 1}^V \frac{|D^i|}{|D|} \text{Ent}(D^i)$$

3.2 信息增益率

由于 ID3 算法使用信息增益选择最优属性进行划分时，会在属性的取值较多时有偏好，C4.5 算法对其进行了改进。同时 C4.5 算法考虑了连续的数值属性离散化、缺失值处理和剪枝技术，这都会在接下来的小节中具体展开。

不过所谓的属性选择策略的优化，其实就是在 ID3 的基础上增加了一个规范化，信息增益率的定义式如下：

$$\text{Ent\_Gain}\_\text{ratio}(D, a) = \frac{\text{Ent\_Gain}(D, a)}{\text{IV}(D, a)}$$

其中 $\text{IV}(D, a)$ 为：

$$\text{IV}(D, a) = -\sum_{i = 1}^V \frac{|D^i|}{|D|} \log_2 \frac{|D^i|}{|D|}$$

可以看出 $\text{IV}(D, a)$ 其实就是数据集 $D$ 在属性 $a$ 所以可能取值上的信息熵。一般而言，属性的属性取值越多，信息增益越大，对应的 $\text{IV}$ 值也越大，这样就可以规范化信息增益，避免在选择最优划分属性时模型偏好于更多属性取值的属性了。

3.3 基尼指数增益

分类与回归树 (Classification And Regression Tree, CART) 算法在决策树模型中引入了基尼指数 (Gini index) 来进行最优划分属性的选择。基尼指数是用来衡量一个国家或地区的收益差距的指标，基尼指数越小则表明收入差距越小。

假设当前结点对应的样本集合为 D，其中含有 $t$ 个类别并且第 $k$ 个类别所占样本集合比例为 $P_k$，则当前结点的基尼指数为：

$$\text{Gini(D)} = 1 - \sum_{k = 1}^{t}P_k^2$$

于是选择属性 $a$ 作为划分属性的的基尼指数增益 $\text{Gini\_Gain}(D,a)$ 为：

$$\text{Gini\_Gain}(D,a) = \text{Gini(D)} - \sum_{i = 1}^V \frac{|D^i|}{|D|} \text{Gini}(D^i)$$

4 剪枝处理

为了防止模型过拟合并且降低计算复杂度，我们需要使用验证集对决策树进行剪枝。一共有两种剪枝方法：

1. 预剪枝。基于贪心的思想，决策每次划分是否需要进行。我们知道最佳属性的选择是基于信息增益等关于结点纯度的算法策略，而是否进行子结点的生成需要我们进行性能评估，即从测试精度的角度来考虑。因此决策划分是否进行取决于子结点生成前后在验证集上的测试精度，如果可以得到提升则进行生成，反之则不生成子结点，也就是预剪枝的逻辑；
2. 后剪枝。同样是预剪枝的精度决策标准。我们在一个决策树完整生成以后，从深度最大的分支结点开始讨论是否可以作为叶子结点，也就是是否删除该分支的子结点。决策的依据是删除子结点前后在测试集上的精度是否有提升，如果有则删除子结点，反之不变。

两种剪枝策略的区别在于。预剪枝是基于贪心，也就是说没有考虑到全局的情况，可能出现当前结点划分后测试精度下降，但是后续结点继续划分会得到性能提升，从而导致预剪枝的决策树泛化性能下降；而后剪枝就可以规避贪心导致的局部最优，但是计算的时间开销更大。

连续与缺失值

连续值处理

这里讲解二分法 (bi-partition)。主要就是在计算信息增益时增加了一步，将属性的取值情况划分为了两类。那么如何划分呢？关键在于划分点的取值。假设当前属性 a 的取值是连续值，去重排序后得到 n 个数值，我们取这 n 个数值的 n-1 个间隔的中值作为划分点集合，枚举其中的每一个划分点计算最大信息增益，对应的划分点就是当前连续取值的属性的二分划分点。时间复杂度极高！也不知道 C4.5 算法怎么想的

缺失值处理

当然我们可以直接删除含有缺失信息的样本，但是这对数据信息过于浪费，尤其是当数据量不大时，如何解决这个问题呢？我们需要解决两个问题：

1. 在选择最优划分属性时，如何计算含有缺失值的属性对应的信息增益呢？
2. 在得到最优划分属性时，如何将属性值缺失的样本划分到合理的叶子结点呢？

对于第一个问题：只计算属性值没有缺失的样本，然后放缩到原始的数据集合大小即可

对于第二个问题：对于已知属性值的样本，我们可以计算出每一个属性值的样本数量，从而计算出一个集合比例，这样对于未知属性值的样本，只需要按照前面计算出来的集合，按照概率划分到对应的子结点即可

多变量决策树

很好，本目就是来解决上述连续值处理的过高时间复杂度的问题的。现在对于一个结点，不是选择最优划分属性，而是对建一个合适的线性分类器，如图：

决策树模型小结

贝叶斯模型

极大似然估计

根本任务：寻找合适的参数 $\hat \theta$ 使得「当前的样本情况发生的概率」最大。又由于假设每一个样本相互独立，因此可以用连乘的形式表示上述概率，当然由于概率较小导致连乘容易出现浮点数精度损失，因此尝尝采用取对数的方式来避免「下溢」问题。也就是所谓的「对数似然估计」方法。

我们定义对数似然 $\text{(log-likelihood)}$ 估计函数如下：

$$\begin{aligned} LL(\theta_c) &= \log P(D_c\ |\ \theta_c) \\ &= \sum_{x \in D_c} \log P(x\ |\ \theta_c) \end{aligned}$$

此时参数 $\hat \theta$ 的极大似然估计就是：

$$\hat \theta_c = \arg \max_{\theta_c} LL(\theta_c)$$

朴素贝叶斯分类器

我们定义当前类别为 $c$，则 $P(c)$ 称为类先验概率，$P(x\ |\ c)$ 称为类条件概率。最终的贝叶斯判定准则为：

$$P(c\ |\ x) = \frac{P(c)P(x\ |\ c)}{P(x)}$$

现在假设 各属性之间相互独立，则对于拥有 d 个属性的训练集，在利用贝叶斯定理时，可以通过连乘的形式计算类条件概率 $P(x \ | \ c)$，于是上式变为：

$$P(c\ |\ x) = \frac{P(c)}{P(x)} \prod_{i = 1}^d P(x_i\ |\ c)$$

注意点：

• 对于离散数据。上述类条件概率的计算方法很好计算，直接统计即可
• 对于连续数据。我们就没法直接统计数据数量了，替换方法是使用高斯函数。我们根据已有数据计算得到一个对于当前属性的高斯函数，后续计算测试样例对应属性的条件概率，代入求得的高斯函数即可。
• 对于类条件概率为 0 的情况。我们采用拉普拉斯修正。即让所有属性的样本个数 $+1$，于是总样本数就需要 $+d$ 来确保总概率仍然为 $1$。这是额外引入的 bias

半朴素贝叶斯分类器

朴素贝叶斯的问题是假设过于强，现实不可能所有的属性都相互独立。半朴素贝叶斯弱化了朴素贝叶斯的假设。现在假设每一个属性最多只依赖一个其他属性。即独依赖估计 $(\text{One-Dependent Estimator, 简称 ODE})$，于是就有了下面的贝叶斯判定准测：

$$P(c\ |\ x) \propto P(c) \prod _{i = 1}^d P(x_i\ |\ c, pa_i)$$

如何寻找依赖关系？我们从属性依赖图出发

如上图所示：

• 朴素贝叶斯算法中：假设所有属性相互独立，因此各属性之间没有连边
• SPODE 确定属性父属性算法中：假设所有属性都只依赖于一个属性（超父），我们只需要找到超父即可
• TAN 确定属性父属性算法中：我们需要计算每一个属性之间的互信息，最后得到一个以互信息为边权的完全图。最终选择最大的一些边构成一个最大带权生成树
• AODE 确定属性父属性算法中：采用集成的思想，以每一个属性作为超父属性，最后选择最优即可

贝叶斯网

构造一个关于属性之间的 DAG 图，从而进行后续类条件概率的计算。三种典型依赖关系：

同父结构	V 型结构	顺序结构
在已知 $x_1$ 的情况下 $x_3,x_4$ 独立	若 $x_4$ 未知则 $x_1,x_2$ 独立，反之不独立	在已知 $x$ 的情况下 $y,z$ 独立

概率计算公式参考：超详细讲解贝叶斯网络(Bayesian network)

EM 算法

现在我们需要解决含有隐变量 $Z$ 的情况。如何在已知数据集含有隐变量的情况下计算出模型的所有参数？我们引入 EM 算法。EM 迭代型算法共两步

• E-step：首先利用观测数据 $X$ 和参数 $\Theta_t$ 得到关于隐变量的期望 $Z^t$
• M-step：接着对 $X$ 和 $Z^t$ 使用极大似然函数来估计新的最优参数 $\Theta_{t+1}$

有两个问题：哪来的参数？什么时候迭代终止？

• 对于第一个问题：我们随机化初始得到参数 $\Theta_0$
• 对于第二个问题：相邻两次迭代结果中 参数 差值的范数小于阈值 $(|| \theta^{(i+1)} - \theta^{(i)}) || < \epsilon_1)$ 或 隐变量条件分布期望 差值的范数小于阈值 $(|| Q(\theta^{(i+1)} , \theta^{(i)})) - Q(\theta^{(i)} , \theta^{(i)}) || < \epsilon_2)$

集成学习

基本概念

集成学习由多个不同的 组件学习器 组合而成。学习器不能太坏并且学习器之间需要有差异。如何产生并结合“好而不同”的个体学习器是集成学习研究的核心。集成学习示意图如下：

根据个体学习器的生成方式，目前集成学习可分为两类，代表作如下：

1. 个体学习器直接存在强依赖关系，必须串行生成的序列化方法：Boosting；
2. 个体学习器间不存在强依赖关系，可以同时生成的并行化方法：Bagging 和 随机森林 (Random Forest)。

Boosting 算法

Boosting 算法族的逻辑：

1. 个体学习器之间存在强依赖关系；
2. 串行生成每一个个体学习器；
3. 每生成一个新的个体学习器都要调整样本分布。

以 AdaBoost 算法为例，问题式逐步深入算法实现：

1. 如何计算最终集成的结果？利用加性模型 (additive model)，假定第 $i$ 个学习器的输出为 $h(x)$，第 $i$ 个学习器的权重为 $\alpha_i$，则集成输出 $H(x)$ 为：

   $$H(x) = \text{sign} \left(\sum_{i = 1}^T \alpha_i h_i(x)\right)$$

2. 如何确定每一个学习器的权重 $\alpha_i$ ？我们定义 $\displaystyle \alpha_i=\frac{1}{2}\ln (\frac{1-\epsilon_i}{\epsilon_i})$

3. 如何调整样本分布？我们对样本进行赋权。学习第一个学习器时，所有的样本权重相等，后续学习时的样本权重变化规则取决于上一个学习器的分类情况。上一个分类正确的样本权重减小，上一个分类错误的样本权重增加，即：

   $$D_{i+1}(x) = \frac{D_i(x)}{Z_i} \times \begin{cases} e^{-\alpha_i}&, h_i(x)= f(x) \\ e^{\alpha_i}&, h_i(x)\ne f(x) \end{cases}$$

代表算法：AdaBoost、GBDT、XGBoost。

Bagging 算法

在指定学习器个数 $T$ 的情况下，并行训练 $T$ 个相互之间没有依赖的基学习器。最著名的并行式集成学习策略是 Bagging。问题式逐步深入 Bagging 算法实现：

1. 如何计算最终集成的结果？直接进行大数投票即可，注意每一个学习器都是等权重的
2. 如何选择每一个训练器的训练样本？顾名思义，就是进行 $T$ 次自助采样法
3. 如何选择基学习器？往往采用决策树 or 神经网络

Random Forest 算法

随机森林 (Random Forest, RF) 是 Bagging 的一个扩展。问题式逐步深入随机森林算法实现：

1. 如何计算最终集成的结果？直接进行大数投票即可，注意每一个学习器都是等权重的
2. 为什么叫森林？每一个基学习器都是「单层」决策树
3. 随机在哪？首先每一个学习器对应的训练样本都是随机的，其次每一个基学习器的属性都是随机的 $k(k \in [1,V])$ 个（由于基学习器是决策树，并且属性是不完整的，故这些决策树都被称为弱决策树）

集成输出

基学习器有了，如何确定集成模型的最终输出呢？我们假设 $T$ 个基学习器对于当前样本 $x$ 的输出依次为 $h_i(x),i=1,2,\cdots,T$。模型的最终输出为 $H(x)$。

平均法

对于数值型输出 $h_i(x) \in R$，常见的结合策略采是 平均法。分为两种：

1. 简单平均法：$H(x) = \displaystyle \frac{1}{T} \sum_{i =1}^T h_i(x)$
2. 加权平均法：$H(x) = \displaystyle\sum_{i=1}^T w_i h_i(x),\quad w_i \ge 0, \sum_{i=1}^Tw_i = 1$

显然简单平均法是加权平均法的特殊。一般而言，当个体学习器性能差距较大时采用加权平均法，相近时采用简单平均法。

投票法

对于分类型输出 $h_i(x) = [h_i^1(x), h_i^2(x), \cdots, h_i^N(x)]$，即每一个基学习器都会输出一个 $N$ 维的标记向量，其中只有一个打上了标记。常见的结合策略是 投票法。分为三种：

1. 绝对多数投票法：选择超过半数的，如果没有则 拒绝投票
2. 相对多数投票法：选择票数最多的，如果有多个相同票数的则随机取一个
3. 加权投票法：每一个基学习器有一个权重，从而进行投票

学习法

其实就是将所有基学习器的输出作为训练数据，重新训练一个模型对输出结果进行预测。其中，基学习器称为“初级学习器”，输出映射学习器称为“次级学习器”或”元学习器” $\text{(meta-learner)}$。对于当前样本 $(x,y)$，$n$ 个基学习器的输出为 $y_1 = h_1(x),y_2 = h_2(x),\cdots,y_n = h_n(x)$，则最终输出 $H(x)$ 为：

$$H(x) = G(y_1, y_2, \cdots, y_n)$$

其中 $G$ 就是次级学习器。关于次级学习器的学习算法，大约有以下几种：

1. Stacking
2. 多响应线性回归 $(Mutil-response linear regression, MLR)$
3. 贝叶斯模型平均 $(Bayes Model Averaging, BMA)$

经过验证，Stacking 的泛化能力往往比 BMA 更优。

小结

Random Forest 与 Bagging 相比，多增加了一个属性随机，进而提升了不同学习器之间的差异度，进而提升了模型性能，效果如下：

Random Forest 与 Bagging 均采用自助采样法。Bagging 优势在于不仅解决了训练样本不足的问题，同时 T 个学习器的训练样本之间是有交集的，这也就可以减小测试的方差。

区别：

• 序列化基学习器最终的集成结果往往采用加权投票；
• 并行化基学习器最终的集成结果往往采用平权投票。

联系：

• 序列化减小偏差。即可以增加拟合性，降低欠拟合；
• 并行化减小方差。即可以减少数据扰动带来的误差。

懒惰学习

K 近邻算法

K 近邻（k-Nearest Neighbor, KNN）是一种监督学习方法。一句话概括就是「近朱者赤近墨者黑」，每一个测试样本的分类或回归结果取决于在某种距离度量下的最近的 k 个邻居的性质。不需要训练，可以根据检测样本实时预测，即懒惰学习。为了实现上述监督学习的效果，我们需要解决以下两个问题：

• 如何确定「距离度量」的准则？就那么几种，一个一个试即可；
• 如何定义「分类结果」的标签？分类任务是 k 个邻居中最多类别的标签，回归任务是 k 个邻居中最多类别标签的均值。

KNN 变种：最近邻子空间分类器 (Nearest Subspace Classifier, NS)。同样是懒惰学习的方式，对每一个测试样本计算到「训练样本形成的所有子空间」之间的距离，并将当前样本的类别判定为距离最近的子空间对应的类别。这里有两个问题：

1. 子空间是怎么来的？这是基于先验假设而来，也就是说所有的子空间都是人为提前定义好的；
2. 如何计算测试样本到子空间的最小距离？对于高维特征空间，最小距离的计算并不容易，为了计算最小距离，本质上就转变成了一个线性回归的拟合问题，即拟合出一组最佳参数使得当前样本到子空间的距离最小。

聚类学习

本章我们学习一个经典的无监督学习方法：聚类。即通过某种规则将数据集划分为不同的簇。我们将会首先学习数据对象的距离计算规则，接着从结果论的角度学习如何评估一个聚类结果的好坏，最后按照类别介绍几个具体的聚类算法。

1 基本概念

距离计算。聚类的本质就是根据样本之间的距离将距离相近的数据对象认定为同一个类别，因此最关键的一步就是如何定义数据对象之间的距离（有些教材也会将距离度量成为邻近度度量）。无论是什么类型的属性，比如二元属性、标称属性、序数属性、数值属性等等，都可以归纳为以下两种距离计算的标准：

1. 有序属性：闵可夫斯基距离；

2. 无序属性：VDM 距离。

性能度量。一来是进行聚类算法的评估，二来也可以作为聚类算法的优化目标。分为两种，分别是外部指标和内部指标：

1. 外部指标。所谓外部指标就是已经有一个“参考模型”存在了，将当前模型与参考模型的比对结果作为指标。我们考虑两两样本的聚类结果，定义下面的变量：

   $$\begin{gathered} a=|SS|,SS=\{(\boldsymbol{x}_{i},\boldsymbol{x}_{j})\mid\lambda_{i}=\lambda_{j},\lambda_{i}^{*}=\lambda_{j}^{*},i<j)\},\\ b=|SD|,SD=\{(\boldsymbol{x}_{i},\boldsymbol{x}_{j})\mid\lambda_{i}=\lambda_{j},\lambda_{i}^{*}\neq\lambda_{j}^{*},i<j)\},\\ c=|DS|,DS=\{(\boldsymbol{x}_{i},\boldsymbol{x}_{j})\mid\lambda_{i}\neq\lambda_{j},\lambda_{i}^{*}=\lambda_{j}^{*},i<j)\},\\ d=|DD|,DD=\{(\boldsymbol{x}_i,\boldsymbol{x}_j)\mid\lambda_i\neq\lambda_j,\lambda_i^*\neq\lambda_j^*,i<j)\}, \end{gathered}$$

   显然 $a+b+c+d=m(m-1)/2$，常见的外部指标如下：

   • JC 指数：$\displaystyle JC = \frac{a}{a+b+c}$
   • FM 指数：$\displaystyle \sqrt{\frac{a}{a+b} \cdot \frac{a}{a+c}}$
   • RI 指数：$\displaystyle \frac{2(a+d)}{m(m-1)}$

   上述指数取值均在 $[0,1]$ 之间，且越大越好。

2. 内部指标。所谓内部指标就是仅仅考虑当前模型的聚类结果。同样考虑两两样本的聚类结果，定义下面的变量：

   $$\begin{aligned} \mathrm{avg}(C)&=\frac{2}{|C|(|C|-1)}\sum_{1\leqslant i<j\leqslant|C|}\operatorname{dist}(\boldsymbol{x}_{i},\boldsymbol{x}_{j}),\\ \mathrm{diam}(C)&=\max_{1\leqslant i<j\leqslant|C|}\mathrm{dist}(\boldsymbol{x}_{i},\boldsymbol{x}_{j}),\\ d_{\min}(C_i,C_j)&=\min_{\boldsymbol{x}_i\in C_i,\boldsymbol{x}_j\in C_j}\mathrm{dist}(\boldsymbol{x}_i,\boldsymbol{x}_j),\\ d_{\mathrm{cen}}(C_i,C_j)&=\mathrm{dist}(\boldsymbol{\mu}_i,\boldsymbol{\mu}_j), \end{aligned}$$

   常见的内部指标比如：轮廓系数。

2 基于划分的聚类算法

Kmeans 及其变种都只适用于 凸形状 的样本分布。

K-means

目标函数（损失函数）定义为：

$$\text{loss}=\sum_i^K\sum_{x\in c_i}\|x-c_i\|_2^2$$

Kmeans 算法流程大体上可以归纳为三步：

1. 随机选择 k 个数据对象作为 $k$ 个聚类中心（K 均值算法需要提前给出超参数，即簇的数量 $k$）；
2. 枚举所有样本并将其划分到欧氏距离（或其他距离度量方法）最近的一个聚类中心；
3. 更新 $k$ 个簇中心为簇中所有样本的均值。

重复上述迭代过程直到算法收敛。达到以下任意一种条件即表示算法收敛：

• 损失函数小于阈值；
• 达到最大迭代次数。

假设样本数量为 N，簇的数量为 K，最大迭代轮数为 iter，则 Kmeans 算法的时间复杂度为 $O(\text{iter} \times NK)$。

K-means++

此法相对于 K-means 做出了一个小的改进。在一开始选择 k 个聚类中心时，并不是随机初始化 k 个，而是首先随机出 1 个，然后循环 $k-1$ 次选择剩下的 k-1 个聚类中心。选择的规则是：每次选择最不可能成为新的聚类中心的数据对象，或者是到所有聚类中心的最小距离最大的数据对象。

Bisecting K-means

此法叫做二分 K-means 算法。具体的，在一开始将所有的数据对象划分为一个簇，然后每次选择一个误差最大的簇进行二分裂，不断分裂直到收敛。这种方法不能使得 Loss 最小，但是可以作为 K-means 算法的一个预热，比如可以通过这种方法得到一个相对合理的簇中心，然后再利用 K-means 算法进行聚类。

K-mediods

目标函数定义为：

$$\text{loss}=\sum_i^K\sum_{x\in o_i}\lvert x-o_i\rvert$$

即 K 中心点算法。例如 PAM 算法，其使用实际的数据对象作为簇中心而不是用均值众数等新点作为簇中心。具体的，对于每一个簇中心 $O_i$，随机选择一个非簇中心的数据对象 $O_{\text{random}}$，如果用 $O_{\text{random}}$ 替换 $O_i$ 之后损失减小，则替换，否则继续迭代直到算法收敛。

3 基于层次的聚类算法

主要介绍簇之间的邻近性度量方法以及凝聚方法 (Agglomerative, AGNES) 和分裂方法 (Divisive Analysis, DIANA)。两种算法可以形象的表述为下图：

簇之间的邻近性度量

单链（Single-linkage）：簇之间的邻近度定义为不同簇中两个最近的数据对象的距离；

全链（Complete-linkage）：簇之间的邻近度定义为不同簇中两个最远的数据对象的距离；

均链（Average-linkage）：簇之间的邻近度定义为不同簇中所有数据对象之间距离的均值；

质心距离（Distance between centroids）：簇之间的邻近度定义为不同簇的质心之间的距离。

AGNES

凝聚算法有点类似于并查集，初始时每一个样本点都是一个簇，不断合并最接近的两个簇直到达到需要的簇数量就停止合并。而这里簇之间的距离就按照上面介绍的簇之间的邻近性度量来实现。

不同邻近度方法下凝聚层次聚类对比：

	单链	全链	均链	质心距离
优点	可以处理非椭圆形的簇		簇间的距离不易受到噪声或异常值的影响	簇间的距离不易受到噪声或异常值的影响
缺点	聚类结果对噪声或异常值敏感	倾向于分裂较大的簇	倾向于形成球形的簇	倾向于形成球形的簇

DIANA

分裂算法有点类似于 Bisecting K-means，每次选一个簇根据某种规则将其分类为两个簇，直到达到需要的簇数量就停止分裂。

4 基于密度的聚类算法

DBSCAN

基于密度的带噪声空间聚类（Density-Based Spatial Clustering of Application with Noise, DBSCAN）

其实，就是一个朴素 dfs。算法定义为：

• 每次随机选择一个没有访问过的对象开始 dfs；
• 如果发现无法成为核心对象，即邻域 $\epsilon$ 内的数据对象数量小于 $\text{Minpts}$，则标记为 visited 并重新选点；
• 如果可以成为核心对象，则形成一个簇 C 并将当前邻域内没有归属的数据对象全都纳为 C 的数据对象，并以这些新纳入的数据对象为起点递归的拓展，直到无法拓展新的数据对象。

基于密度的 DBDSAN 聚类算法可以适应更加复杂的数据分布场景，但是缺点在于对超参数 ($\epsilon,\text{Minpts}$) 很敏感。并且由于超参数是二维联合的，因此如何调参 ($\epsilon,\text{Minpts}$) 是一个很困难的事。在此基础之上，提出 DBSCAN 算法的团队又提出了其改良版本：OPTICS 算法。

OPTICS

用于确定聚类结构的排序点聚类（Ordering Points To Identify the Clustering Structure, OPTICS）

基于密度的 OPTICS 算法延续了 DBSCAN 的策略，只需要提前设定邻域内最少数据对象数量 $\text{Minpts}$ 而不需要提前设置邻域大小 $\epsilon$。有两个关键的概念：

• 核心距离：数据对象成为核心对象的最小半径阈值；
• 可达距离：对于两个数据对象 p 和 q，其中 q 是核心对象，可达距离定义为 $\max{(q \text{ 的核心距离}, p \text{ 与 } q \text{ 的距离})}$。

最终可以得到一个按照某种规则排序的以及其可达距离。此时可以自行划分邻域的值进而按照预期进行聚类而不会像 DBSCAN 一样不受控制。OPTICS 的演示效果如下所示：

特征

特征工程在机器学习任务中起着举足轻重的作用，大多数机器学习的应用场景下，大部分的时间其实都花在了特征工程上。而之所以需要花费大量的精力去做特征工程，主要有两个方面，一来可以通过减低特征维度来减少计算开销，二来可以通过减少特征维度来去除冗余特征，提升模型泛化性能的同时也能降低计算开销。

下面将会从不改变特征值的 “特征选择” 以及会改变特征值的 “特征映射” 两种方法展开特征工程的学习。

特征选择

所谓的特征选择，就是在 $D$ 个特征中直接选择出 $D'\ (D'<D)$ 个特征来作为模型的输入。常见的方法就是网格搜索，即尺取法枚举。

特征映射

特征映射（降维）同样是减少数据的特征维度，只不过特征映射的降维策略更加复杂而已。但与上述特征选择策略不同的是，特征映射还会改变特征值。

降维算法

1）多维缩放 (MDS)

「多维缩放降维算法」的原则：对于任意的两个样本，降维后两个样本之间的距离保持不变。

基于此思想，可以得到以下降维流程：我们定义 $b_{ij}$ 为降维后任意两个样本之间的内积，$dist_{ij}$ 表示任意两个样本的原始距离，$Z \in R^{d'\times m},d' \le d$ 为降维后数据集的属性值矩阵。

内积计算：

$$b_{ij}=-\frac{1}{2}(dist_{ij}^{2}-dist_{i\cdot}^{2}-dist_{\cdot j}^{2}+dist_{\cdot\cdot}^{2})$$

新属性值计算：特征值分解法。其中 $B = V \Lambda V^T$

$$\mathbf{Z}=\mathbf{\Lambda}_*^{1/2}\mathbf{V}_*^\mathrm{T}\in\mathbb{R}^{d^*\times m}$$

2）主成分分析 (Principal Component Analysis, PCA)

「主成分分析降维算法」的两个原则：

• 样本到超平面的距离都尽可能近
• 样本在超平面的投影都尽可能分开

基于此思想可以得到 PCA 的算法流程：

▶

3 个样本 2 个特征降维到 1 个特征的算例

假设我们有一个简单的数据集 $D$，包括以下三个样本点：

$$x_1 = \begin{pmatrix} 2 \\ 3 \end{pmatrix}, \quad x_2 = \begin{pmatrix} 3 \\ 4 \end{pmatrix}, \quad x_3 = \begin{pmatrix} 4 \\ 5 \end{pmatrix}$$

我们希望将这些样本从二维空间降维到一维空间（即 $d' = 1$ ）。

步骤 1: 样本中心化

首先计算样本的均值向量：

$$\mu = \frac{1}{3} (x_1 + x_2 + x_3) = \frac{1}{3} \begin{pmatrix} 2 \\ 3 \end{pmatrix} + \frac{1}{3} \begin{pmatrix} 3 \\ 4 \end{pmatrix} + \frac{1}{3} \begin{pmatrix} 4 \\ 5 \end{pmatrix} = \begin{pmatrix} 3 \\ 4 \end{pmatrix}$$

然后对所有样本进行中心化：

$$\tilde{x}_1 = x_1 - \mu = \begin{pmatrix} 2 \\ 3 \end{pmatrix} - \begin{pmatrix} 3 \\ 4 \end{pmatrix} = \begin{pmatrix} -1 \\ -1 \end{pmatrix}$$

$$\tilde{x}_2 = x_2 - \mu = \begin{pmatrix} 3 \\ 4 \end{pmatrix} - \begin{pmatrix} 3 \\ 4 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$$

$$\tilde{x}_3 = x_3 - \mu = \begin{pmatrix} 4 \\ 5 \end{pmatrix} - \begin{pmatrix} 3 \\ 4 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$$

步骤 2: 计算协方差矩阵

样本的协方差矩阵为：

$$\begin{aligned}XX^T &= \frac{1}{m} \sum_{i = 1}^m \tilde{x}_i \tilde{x}_i^T \\&= \frac{1}{3} \left( \begin{pmatrix} -1 \\ -1 \end{pmatrix} \begin{pmatrix} -1 & -1 \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \end{pmatrix} \begin{pmatrix} 0 & 0 \end{pmatrix} + \begin{pmatrix} 1 \\ 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \end{pmatrix} \right)\\&= \frac{1}{3} \left( \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} + \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix} + \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} \right) \\&= \frac{1}{3} \begin{pmatrix} 2 & 2 \\ 2 & 2 \end{pmatrix} \\&= \begin{pmatrix} \frac{2}{3} & \frac{2}{3} \\ \frac{2}{3} & \frac{2}{3} \end{pmatrix}\end{aligned}$$

步骤 3: 对协方差矩阵进行特征值分解

协方差矩阵的特征值分解：

$$\begin{pmatrix} \frac{2}{3} & \frac{2}{3} \\ \frac{2}{3} & \frac{2}{3} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix} \begin{pmatrix} \frac{4}{3} & 0 \\ 0 & 0 \end{pmatrix} \begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix}$$

特征值为 $\lambda_1 = \frac{4}{3}$ 和 $\lambda_2 = 0$，对应的特征向量分别为：

$$w_1 = \begin{pmatrix} 1 \\ 1 \end{pmatrix}, \quad w_2 = \begin{pmatrix} -1 \\ 1 \end{pmatrix}$$

步骤 4: 取最大的 $d'$ 个特征值对应的特征向量

我们选择最大的特征值对应的特征向量 $w_1 = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$ 作为最终的投影矩阵。

3）核化线性降维

「核化线性降维算法」的原则：pass

4）流形学习降维

假定数据满足流形结构。

• 等度量映射。流形样本中，直接计算两个样本之间的欧式距离是无效的。我们引入「等度量映射」理念。根本算法逻辑是：利用最短路算法计算任意两个样本之间的「测地线距离」得到 $dist_{ij}$，接着套用上述 10.2 中的 MDS 算法即可进行降维得到最终的属性值矩阵 $Z \in R^{d'\times m},d' \le d$。
• 局部线性嵌入。

度量学习

降维的本质是寻找一种合适的距离度量方法，与其降维为什么不直接学习一种距离计算方法呢？我们引入「度量学习」的理念。

为了“有参可学”，我们需要定义距离计算表达式中的超参，我们定义如下「马氏距离」：

为什么用所谓的马氏距离呢？欧氏距离不行吗？我们有以下结论：

• 欧式距离具有旋转不变性和平移不变性，在低维和属性直接相互独立时是最佳实践。但是当属性之间有相关性并且尺度相差较大时，直接用欧式距离计算会丢失重要的特征之间的信息；
• 马氏距离具有尺度不变性，在高维和属性之间有关系且尺度不同时是最佳实践。缺点在于需要计算协方差矩阵导致计算量远大于欧氏距离的计算量。

下面介绍两种度量学习算法来学习上述 M 矩阵，也就是数据集的「协方差矩阵的逆」中的参数。准确的说是学习一个矩阵来近似代替协方差矩阵的逆矩阵。

1）近邻成分分析

近邻成分分析 (Neighborhood Component Analysis, NCA)，目标函数是：最小化所有数据点的对数似然函数的负值。

2）LMNN

大间隔最近邻 (Large Margin Nearest Neighbor, LMNN)，目标函数是：最小化同一个类别中最近邻点的距离，同时最大化不同类别中最近邻点的距离。

paper: Distance Metric Learning for Large Margin Nearest Neighbor Classification

explain: 【LMNN】浅析 “从距离测量到基于 Margin 的邻近分类问题”

拓展

半监督学习

半监督学习的根本目标：同时利用有标记和未标记样本的数据进行学习，提升模型泛化能力。主要分为三种：

1. 主动学习
2. 纯半监督学习
3. 直推学习

未标记样本

对未标记数据的分布进行假设，两种假设：

1. 簇状分布
2. 流形分布

生成式方法

分别介绍「生成式方法」和「判别式方法」及其区别和联系。

生成式方法：核心思想就是用联合分布 $p(x,y)$ 进行建模，即对特征分布 $p(x)$ 进行建模，十分关心数据是怎么来（生成）的。生成式方法需要对数据的分布进行合理的假设，这通常需要计算类先验概率 $p(y)$ 和特征条件概率 $p(x\ |\ y)$，之后再在所有假设之上进行利用贝叶斯定理计算后验概率 $p(y\ |\ x)$。典型的例子如：

• 朴素贝叶斯
• 高斯混合聚类
• 马尔科夫模型

判别式方法：核心思想就是用条件分布 $p(y\ |\ x)$ 进行建模，不对特征分布 $p(x)$ 进行建模，完全不管数据是怎么来（生成）的。即直接学一个模型 $p(y\ |\ x)$ 来对后续的输入进行预测。不需要对数据分布进行过多的假设。典型的例子如：

• 线性回归
• 逻辑回归
• 决策树
• 神经网络
• 支持向量机
• 条件随机场

自监督训练（补）

根本思想就是利用有标记数据进行模型训练，然后对未标记数据进行预测，选择置信度较高的一些样本加入训练集重新训练模型，不断迭代进行直到最终训练出来一个利用大量未标记数据训练出来的模型。

如何定义置信度高？我们利用信息熵的概念，即对于每一个测试样本都有一个预测向量，信息熵越大表明模型对其的预测结果越模糊，因此置信度高正比于信息熵小，将信息熵较小的测试样本打上「伪标记」加入训练集。

半监督 SVM

以经典 S3VM 中的经典算法 TSVM 为例。给出优化函数、算法图例、算法伪代码：

图半监督学习

同样解决分类问题，以「迭代式标记传播算法」为例。

二分类，可以直接求出闭式解。

算法逻辑。每一个样本对应图中的一个结点，两个结点会连上一个边，边权正比于两结点样本的相似性。最终根据图中已知的某些结点进行传播标记即可。与基于密度的聚类算法类似，区别在于此处不同的簇 cluster 可能会对应同一个类别 class。

如何进行连边？不会计算每一个样本的所有近邻，一般采用局部近邻选择连边的点，可以 k 近邻，也可以范围近邻。

优化函数。定义图矩阵的能量损失函数为图中每一个结点与所有结点的能量损失和，目标就是最小化能量损失和：

多分类，无法直接求出闭式解，只能进行迭代式计算。

新增变量。我们定义标记矩阵 F，其形状为 $(l+u) \times d$，学习该矩阵对应的值，最终每一个未标记样本 $x_i$ 就是 $\arg \max F_i$：

概率图模型

为了分析变量之间的关系，我们建立概率图模型。按照图中边的性质可将概率图模型分为两类：

• 有向图模型，也称贝叶斯网
• 无向图模型，也称马尔可夫网

隐马尔可夫模型

隐马尔可夫模型 $\text{(Hidden Markov Model, 简称 HMM)}$ 是结构最简单的动态贝叶斯网。是为了研究变量之间的关系而存在的，因此是生成式方法。

需要解决三个问题：

1. 如何评估建立的网络模型和实际观测数据的匹配程度？
2. 如果上面第一个问题中匹配程度不好，如何调整模型参数来提升模型和实际观测数据的匹配程度呢？
3. 如何根据实际的观测数据利用网络推断出有价值的隐藏状态？

马尔科夫随机场

马尔科夫随机场 $\text{(Markov Random Field, 简称 MRF)}$ 是典型的马尔科夫网。同样是为了研究变量之间的关系而存在的，因此也是生成式方法。

联合概率计算逻辑按照 势函数 和 团 展开。其中团可以理解为 完全子图；极大团就是结点最多的完全子图，即在当前的完全子图中继续添加子图之外的点就无法构成新的完全子图；势函数就是一个关于团的函数。