1 绪论

1.1 引言

机器学习：利用经验改善系统自身的性能。

任何经验在计算机内都以数据形式存在。

计算问题分类：

• P问题：可以在多项式时间（合理时间）内求解
• NP问题：在多项式时间内求不出答案，但可以验证一个解

在计算学习理论当中，有一个很重要的理论模型PAC模型。

如果对于任意小的：

• 误差上限 $\epsilon >0$（表示学得多接近真理）
• 置信下限 $1-\delta$（表示学得多可靠）

存在一个多项式时间算法，能从有限样本中学到一个假设 $h$，满足：
$$P(error(h)\le \epsilon )\ge 1-\delta$$
也就是说：以至少 $1-\delta$ 的概率，学到的模型错误率不超过 $\epsilon$。

机器学习面对的很多问题，既不是P问题也不是NP问题，这些问题通常是可验证的优化问题，只能从数据中学到近似最优解（高概率正确）。

1.2 基本术语

1.2.1 数据基本概念

• 标签(label)/目标(target)：模型要预测的结果
• 特征(feature)/属性(attribute)：从数据中抽取出来的，对结果预测有用的信息
• 示例(instance)：一个具体的输入对象，即一行特征数据，不包含标签。
• 样例(example)：带有标签的一行数据
• 样本(sample)：一行或几行，或整个数据集都可以叫样本

1.2.2 数据集与空间映射

• 参数(parameter)：模型通过训练自动学习得到的数值，用于描述模型本身
• 超参数(hyperparameter)：训练开始前人为设定的参数，控制模型的学习过程或结构，不会在训练中自动学习
• 数据集：
  • 训练集(training set)：用来训练模型的数据
  • 验证集(validation set)：用于调参或选择模型
  • 测试集(testing set)：用来测试模型的数据
• 机器学习的目标就是学习一个映射函数$f:\mathcal{X}\to \mathcal{Y}$，逼近真实映射函数$f^{\ast }:\mathcal{X}\to \mathcal{Y}$
  • 属性空间/特征空间/输入空间：输入特征的所有可能取值集合$\mathcal{X}$
  • 标签空间/目标空间/输出空间：输出结果的所有可能取值集合$\mathcal{Y}$
• 特征向量(feature vector)：所有特征表示为向量形式，示例在属性空间中的一个点

1.2.3 模型相关

机器学习就是：学习器(learner)基于已标注数据(ground truth)，在假设空间中寻找最优假设(hypothesis)，使其在未知样本上尽可能逼近真实规律(true function)。

• 真相函数(true function)：世界的真实规律，不可知
• 真值(ground truth)：我们已知的、标注好的真实标签
• 学习器(learner)：训练算法，从数据中学习规律，寻找最优假设
• 假设(hypothesis)：学习器学出来的近似函数，用来逼近真值
• 模型(Model)：一个机器学习算法与训练后的参数集合，用于进行预测或分类

1.2.4 任务类型

• 分类(classification)：根据输入特征，预测离散的类别标签
  • 二分类：判断样本属于两种类别中的哪一种，如猫/狗
    • 正类：我们关注的目标类，通常用标签1表示，如患病
    • 反类：与正类相对的非目标类，通常用标签0表示，如健康
    • 正/反类是人为定义的，没有绝对好坏，根据视角不同，可以调换
  • 多分类：判断样本属于多个类别中的哪一种，如猫/狗/鸟
• 回归(regression)：根据输入特征，预测一个连续数值，如预测房价

1.2.5 监督范式

• 监督学习(Supervised Learning)：用带标签的数据来训练模型，学习输入与输出的映射，常用于分类和回归任务
• 无监督学习(Unsupervised Learning)：数据没有标签，模型要自己发现规律或结构，常用于聚类和降维任务
• 半监督学习(Semi-supervised Learning)：只有少量样本带标签，通过少量监督信息引导整体学习
• 强化学习(Reinforcement Learning)：模型通过与环境交互、不断试错，根据奖励信号优化策略，以获得最大奖励

1.2.6 理论基础与泛化

• 独立同分布(i.i.d.)：大多数机器学习理论的基本假设
  1. 独立 (independent)：每个样本的生成不依赖其他样本
  2. 同分布 (identically distributed)：所有样本都来自同一个概率分布
• 未见样本(unseen instance)：模型在训练时没有见过的样本
• 未知分布：训练集和测试集都是从这个分布抽样的，机器学习的目标就是学习到一个模型，使它对这个未知分布的整体表现尽可能好
• 泛化(generalization)：模型在未见样本上的表现能力

1.2.7 学习理论

• 归纳偏好：学习器在多种可能假设中倾向选择某一类假设的偏好，是学习的前提
• 无免费午餐定理(No Free Lunch, NFL)：对所有可能的数据分布而言，没有任何算法在所有任务上都优于其他算法，如果一个算法在某些任务上表现好，那它必然在其他任务上表现差

NFL定理的前提是所有问题出现的机会相同，或所有问题同样重要。脱离具体问题，空谈什么算法好没有意义。

2 模型评估与选择

奥卡姆剃刀原则主张在有多个同样有效的解释时，应选择最简单的那个解释。核心理念是“如无必要，勿增实体”。但判断什么样的模型算简单这个问题并不简单。

2.1 误差和过拟合

经验误差并不是越低越好，如果太低可能会导致过拟合，使泛化误差升高。

• 经验误差：在训练集上的误差
• 泛化误差：在未来样本上的误差

过拟合(overfitting)：模型在训练集上学得太好，甚至记住了噪声或偶然特征，导致在训练集表现好、测试集表现差。
欠拟合(underfitting)：模型对训练数据学习不足，连训练集都拟合不好，模型太简单、能力不够，无法捕捉数据中的真实规律。

如何获得测试结果？评估方法
如何评估性能优劣？性能度量
如何判断实质差别？比较检验

2.2 评估方法

模型训练流程：

1. 初始划分：将原始数据划分为训练集 + 验证集 + 测试集。
2. 模型训练阶段：在训练集上训练模型，在验证集上调参、选择最优模型结构，训练过程中验证集不参与梯度更新，只是用来评估。
3. 模型选择阶段：使用验证集表现最好的参数，重新用训练集 + 验证集合并训练一次，得到最终模型。
4. 模型评估阶段：用测试集测试模型性能，测试集只用于一次性、最终评估，不能再回头调参。
5. 模型部署阶段：最终确认算法后，可以用全量数据（训练+验证+测试）重新训练一个生产模型，使模型能利用所有可用数据进行学习。

2.2.1 留出法(Hold-out)

核心思想：将数据随机分成多个部分，一部分用于训练模型，另一部分用于验证和测试模型。它既可用于模型评估，也可用于模型选择。

优点：简单、计算量小，适合大数据集。
缺点：对数据划分方式敏感，数据量少时，训练集和测试集都可能不足。

注意：

• 保证数据分布一致性，例如使用分层采样
• 多次重复划分，例如100次随机划分
• 测试集要适中，太大影响模型训练效果，太小影响模型测试效果

常见比例：

• 训练集 : 测试集 = 7 : 3 或 8 : 2
• 三划分时：训练 6，验证 2，测试 2

模型评估：

模型选择：

2.2.2 交叉验证法(Cross Validation, CV)

核心思想：将数据划分为 K 个折（fold），每次用 K−1 折训练、剩下 1 折测试，循环 K次，每个子集都做一次测试集，取平均度量作为性能估计。

常见形式：

• K折交叉验证(K-Fold CV)：最常见，K一般取10，还有5、20等
• 留一法(Leave-One-Out, LOO)：K = 样本数，每次只留 1 个样本作验证

优点：每个样本都参与训练与验证，充分利用数据，评估结果稳定可靠
缺点：计算成本高

2.2.3 自助法(Bootstrap)

当数据集非常小，以至于划分训练/测试集都感觉很奢侈时，自助法就派上用场了。

核心思想：从原始数据集中进行有放回采样，形成与原数据等大小的训练集。从未被采样过的样本称为袋外(out-of-bag, OOB)测试集，每次自主采样约有 36.8% 成为 OOB。

优点：在数据集较小、难以有效划分训练/测试集时非常有用
缺点：有放回采样，改变了原始数据集的分布

2.3 性能度量

2.3.1 回归任务(Regression)

• 均方误差 (Mean Squared Error, MSE)：每个样本的预测值与真实值之差的平方的平均值。
  $$MSE=\frac{1}{n}\sum _{i=1}^n(y_i-{\hat{y}}_i{)}^2$$

MSE 对误差进行平方，因此对异常值非常敏感。MSE的值越小，说明模型的预测越精准，性能越好。

• 均方根误差(Root Mean Squared Error, RMSE)：均方根误差是均方误差的平方根。
  $$RMSE=\sqrt{MSE}=\sqrt{\frac{1}{n}\sum _{i=1}^n(y_i-{\hat{y}}_i{)}^2}$$

RMSE 同样对大误差敏感，因为它是在 MSE 的基础上计算得到的，优势在于与目标的量纲一致。如果一味地降低 RMSE，可能会导致模型对异常值也拟合度很高，容易过拟合。

• 平均绝对误差(Mean Absolute Error, MAE)：预测值与真实值差的绝对值的平均值。
  $$MAE=\frac{1}{n}\sum _{i=1}^n|y_i-{\hat{y}}_i|$$

MAE 对所有误差都给予相同的权重，因此对异常值不敏感，并且和目标量纲一致。

如果希望模型对异常值更加敏感，可以选择 MSE 或 RMSE。RMSE 比 MSE 更易于解释。
如果希望模型对异常值不敏感，可以选择 MAE。
在实际应用中，通常会同时考虑这三个指标，以便更全面地评估模型的性能。

2.3.2 分类任务(Classification)

混淆矩阵(Confusion Matrix)：正类为 Positive §，负类为 Negative (N)。
总样本数 $n=TP+TN+FP+FN$。

真实类别	预测为正例	预测为反例
正例 §	真正例(True Positive, TP)	假反例(False Negative, FN)
反例 (N)	假正例(False Positive, FP)	真反例(True Negative, TN)

• 精度(Accuracy)：预测正确的比例。
  $$Accuracy=\frac{TP+TN}{n}$$

• 错误率(Error)：预测错误的比例。
  $$Error=\frac{FP+FN}{n}=1-Accuracy$$

• 查准率(Precision)：预测为正例的样本中，真正为正的比例，衡量模型预测的准不准。
  $$Precision=\frac{TP}{TP+FP}$$

核心特点：宁缺毋滥。
查准率高，意味着模型在说一个样本是正例时，有很高的可信度。误报代价高时更关心，比如垃圾邮件检测。

• 查全率/召回率(Recall)：真正的正例中，被模型判正的比例，衡量模型找得全不全。
  $$Recall=\frac{TP}{TP+FN}$$

核心特点：宁多报不漏报。
查全率高，意味着模型能够把绝大多数的正例都找出来，很少漏掉。漏报代价高时更关心，比如病毒检测。

• F1度量(F1-score)：查准率和查全率是相互制约的，需要一个综合性的指标来平衡它们，F1度量就是它们的调和平均数，同时兼顾了查准率和查全率。
  $$\frac{1}{F_1}=\frac{1}{2}\cdot (\frac{1}{Precision}+\frac{1}{Recall})$$
  得=>
  $$F_1=2\cdot \frac{Precision\cdot Recall}{Precision+Recall}$$

• F-beta度量：不平衡场景可用加权的 $F_{\beta }$​ 强调召回或查准。
  $$F_{\beta }=(1+{\beta }^2)\cdot \frac{PR}{{\beta }^{2}P+R}$$

• 当 $\beta >1$ 时，更看重Recall（如 $F_2$ 度量）

• 当 $\beta <1$ 时，更看重Precision（如 $F_{0.5}$ 度量）

2.4 比较检验

McNemar检验
交叉验证 t 检验

3 线性模型

3.1 一元线性回归

一元线性回归方程：
$$y=w\mathbf{x}+b$$
定义损失函数：
$$L(w,b)=\sum _{i=1}^m(y_i-(wx+b){)}^2$$
对损失函数进行最小二乘估计，分别对 $w$ 和 $b$ 求偏导，令导数等于 0，得到闭式(closed-form)解：
$$w=\frac{{\sum }_{i=1}^m{y}_i(x_i-\bar{x})}{{\sum }_{i=1}^m{x}_i^2-\frac{1}{m}({\sum }_{i=1}^m{x}_i{)}^2}b=\frac{1}{m}\sum _{i=1}^m(y_i-w{x}_i)$$

线性回归中，对于离散属性的处理：

• 若有“序”，则连续化，如高、中、低，可以转为0，1，2
• 无“序”，则转为k维向量，如红、绿、蓝，转为三个特征，[1, 0, 0] [0, 1, 0] [0, 0, 1]

3.2 多元线性回归

多元线性回归方程：
$$y=w_1{x}_1+w_2{x}_2+w_3{x}_3+\cdots +w_n{x}_n+b$$
可以用向量简化为：$y={\mathbf{w}}^{\mathbf{T}}\mathbf{x}+b$

其中$\mathbf{w}=\left(\begin{array}{c}{w}_1\\ w_2\\ w_3\\ ...\end{array}\right)$，$\mathbf{x}=\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ ...\end{array}\right)$，将$\mathbf{w}$进行转置后和$\mathbf{x}$做矩阵乘法：${\mathbf{w}}^{\mathbf{T}}\mathbf{x}=\left(\begin{array}{c}{w}_1,w_2,w_3,...\end{array}\right)\times \left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ ...\end{array}\right)$

还可以将 $b$ 吸收进去$\mathbf{w}=\left(\begin{array}{c}1\\ w_1\\ w_2\\ w_3\\ ...\end{array}\right)$，$\mathbf{x}=\left(\begin{array}{c}b\\ x_1\\ x_2\\ x_3\\ ...\end{array}\right)$，简化书写为：$y={\mathbf{w}}^{\mathbf{T}}\mathbf{x}$

同样采用最小二乘求解，得到解析解为：
$$\mathbf{w}=({\mathbf{X}}^T\mathbf{X}{)}^{-1}{\mathbf{X}}^T\mathbf{y}$$
若 $X^{T}X$ 不满秩，可以解出多个 $w$，此时需要设定归纳偏好，或引入正则化(regularization)。

矩阵的转置与矩阵相乘等于 $L_2$ 范数 $||x|{|}_2$ 的平方：${\mathbf{x}}^T\mathbf{x}=||x|{|}_2^2$

3.3 广义线性回归

令预测值稍作变换便可得到 $y$ 的衍生物。
$$lny=w^{T}x+b$$
上述变换得到了对数线性回归(log-linear regression)，实际是用 $e^{w^{T}x+b}$ 逼近$y$。

推广得到广义线性模型的一般形式，将线性回归的输出作为输入传入 $g^{-1}$ 函数：
$$y=g^{-1}(w^{T}x+b)$$

其中 $g$ 称为联系函数(link function)，是单调可微的，令 $g(\cdot )=ln(\cdot )$ 则得到对数线性回归。

3.4 对数几率回归（逻辑回归）

对数几率回归（逻辑回归， Logistic Regression），也称对率回归，是解决分类问题的算法。

线性回归模型 $z=w^{T}x+b$ 产生实值输出，我们期望输出 y ∈ { 0 , 1 } y\in\{0, 1\} y∈{0,1} 来解决分类问题，根据上一节的描述，我们需要找到一个 $z$ 和 $y$ 的联系函数。

理想的单位阶跃函数(unit-step function)为：
$$y=\{\begin{array}{l}0,z<0\\ 0.5,z=0\\ 1,z>0\end{array}$$
但是该函数分段，用不可导的点，性质不好，于是寻找替代函数：
$$y=\frac{1}{1+e^{-z}}$$
该函数称为 sigmoid 函数，或 logistics 函数，具有单调可微、任意阶可微可导的性质。

将线性回归的输出作为输入会得到 {0, 1} 的输出。
$$y=\frac{1}{1+e^{-(w^{T}x+b)}}$$
即：
$$ln\frac{y}{1-y}=w^{T}x+b$$
根据上一节的广义线性模型，相当于用右侧的线性模型去逼近左侧的 $y$ 衍生物。

其中 $\frac{y}{1-y}$ 中的 $y$ 表示正例的可能性，$1-y$ 为负例的可能性，整体在统计学上称为几率(odds)，反映了 $x$ 作为正例的相对可能性，加上 $ln$ 称为对数几率(log odds, 亦称为 logit)，在计算机学科当中通常使用 logistics regression，建议称为对数几率回归，简称对率回归。

注意：由于历史原因，逻辑回归本身是一个错误的翻译，Logistic并没有逻辑的意思，而是源自 Logit，不是 Logic，Logit本身来自 Log odds，也就是对数几率。

对率回归有几大优点：

• 不同于很多模型，无需假设数据分布，这意味着用很强的普适性
• 可以得到类别的近似概率预测
• 可用现有数值优化算法求取最优解

3.5 多分类学习

拆解法：将一个多分类任务转化为多个二分类任务，然后对多个二分类任务的结果进行举手表决。

• 一对一(One-vs-One, OvO)：
  • 训练 $N(N-1)/2$ 个分类器，存储开销和测试时间大
  • 训练只用两个类的样本，训练时间短
• 一对其他(One-vs-Rest, OvR)：
  • 训练 $N$ 个分类器，存储开销和测试时间小
  • 训练用到全部样例，训练时间长

实践中，逻辑回归、SVM、神经网络等模型均可通过OvR或OvO扩展至多分类任务。两者预测性能取决于具体的数据分布，大多数情况差不多。

4 决策树

决策树是直接导致机器学习能够成为一个学科的模型，思想非常简单。

4.1 决策树基本流程

决策树基于树结构进行决策。

• 每个“内部节点”对应某个特征上的“测试”（test）
• 某个分支对应该测试的某种可能结果，即该特征的某个取值
• 每个“叶子结点”对应一个“预测结果”

学习过程：通过对训练样本的分析来确定“划分特征”，即内部结点所对应的特征。
预测过程：将测试示例从根结点开始，沿着划分特征所构成的“判定测试序列”下行，直到叶子结点。

策略：分而治之（divide-and-conquer）
自根至叶的递归过程，在每个中间节点寻找一个划分（split or test）属性。

既然是递归，停止条件非常重要：

1. 当前节点的样本都属于同一类别，无需划分。
2. 当前节点样本有不同类别，但是特征集为空，没有能够划分的特征了，或者其余特征值都相同。
3. 当前节点包含的样本集合为空（有这个特征但是训练集中没有这种样本）

4.2 信息增益划分

信息熵（entropy）是度量样本集合“纯度”的一个指标，当前样本集合 $D$ 中共有 $k$ 种类别，第 $i$ 类样本样本的比例（也就是出现概率）为 $p_k$，则 $D$ 的信息熵定义为：
$$Ent(D)=-\sum _{i=1}^k{p}_{i}lo{g}_2{p}_i$$
不难发现，信息熵越小，$D$ 的纯度越大。可以得出，$Ent(D)$的最小值为 0，最大值为 $lo{g}_{2}k$。

直接以信息熵为基础，计算当前划分对信息熵所造成的变化，也就是信息增益（information gain），衡量的是当前划分对信息的不确定性减少的贡献程度。公式为 划分前的信息熵 - 划分后的信息熵。
$$\mathrm{Gain}(D,A)=\mathrm{Ent}(D)-\sum _{v=1}^V\frac{|D_v|}{|D|}\mathrm{Ent}(D_v)$$
可以看出， 划分后的信息熵表达的是在给定特征 $A$ 的条件下，数据集 $D$ 的不确定性，称为条件熵：
$$Ent(D|A)=\sum _{v=1}^V\frac{|D_v|}{|D|}\mathrm{Ent}(D_v)$$

• 特征 $A$ 的取值：$a_1,a_2,...a_v$，共有 V 个
• $D_v$：$D$ 在特征 $A$ 上取值为 $a_v$ 的样本子集
• $\frac{|D_v|}{D}$：取值为 $a_v$ 的样本比例，第 $v$ 个分支的权重，样本越多越重要
• $Ent(D_v)$：子集 $D_v$ 的信息熵

其实就是按照特征 $A$ 的取值将样本划分为 $V$ 个子集，分别计算每个子集的信息熵 $Ent(D_v)$，但是由于特征 $A$ 的取值并不是均匀的，所以需要按比例划分权重 $\frac{|D_v|}{D}$，每个子集的信息熵与权重相乘 $\frac{|D_v|}{D}Ent(D_v)$，最后再相加，至此得到了给定特征 $A$ 的信息熵，用划分前信息熵 - 划分后信息熵，由此得到了一个差值，即信息增益。

划分后的信息熵越小，说明特征 $A$ 的选择性越强，每一个子集 $D_v$ 内部纯度越高。

ID3 树就是使用信息增益作为划分准则。

4.3 信息增益率划分

信息增益作为划分准则时，越大越好，即划分后的信息熵越小越好，也就是划分后的子集 $D_v$ 内部越纯越好。如此便会导致一个问题，信息增益倾向于筛选性强，极端来看每个特征值只对应一个结果，那么结果就够纯，所以信息增益会倾向于选择取值较多的特征。

比如按照每个人的手机号特征进行划分，由于结果绝对纯正，它的信息增益会很高，但是由此会造成这个树的泛化能力变得极差。

由于信息增益的这个缺陷，引入了信息增益率（information gain ratio）：
$$\mathrm{Gai}{\mathrm{n}}_{\mathrm{r}}\mathrm{atio}(D,A)=\frac{\mathrm{Gain}(D,A)}{\mathrm{IV}(A)}$$
其中 $IV(A)$ 为：
$$IV(A)=-\sum _{v=1}^V\frac{|D_v|}{|D|}{\log }_2\frac{|D_v|}{|D|}$$
$IV(A)$ 表述的基本思想是特征 $A$ 的取值信息熵，取值数目越多，则 $IV(A)$ 取值越大。

信息增益率希望选择的是：

1. 信息增益尽可能大
2. 特征取值尽可能少

这种思想叫做规范化（normalizetion），在 $R^2$ 系数中也有体现。

由此便解决了信息增益偏向选择取值较多的特征，但我们并不清楚怎样平衡信息增益和特征取值两者的重要性，所以在 C4.5 决策树中并不是单纯的使用信息增益率作为划分依据，而是采用了启发式方法。

算法会检查高信息增益率的特征是否也具有足够高的信息增益。 如果一个特征的信息增益率很高，但其信息增益很低，那么它可能只是因为分裂信息非常小，而不是因为它真的能很好地划分数据。

C4.5 试图在以下两者之间找到平衡：

• 避免选择具有大量值的属性 (信息增益率的作用)
• 避免选择分裂信息太小的属性 (启发式修正的作用)

4.4 基尼指数划分

样本 $D$ 有 $k$ 种类别，样本属于第 $k$ 种类别的概率为 $p_k$，那么两次抽到的是同一类别的概率为 ${p_k}^2$，一共 $k$ 种类别求和得到抽到任一同样类别的概率，用 1 减去这个概率，反映的是从样本 D 中任取两个样本，其类别标签不一致的概率。
$$Gini(D)=1-\sum _{k=1}^n{p_k}^2$$
该值称为基尼指数（Gini index），值越小，纯度越高。

属性 A 的基尼指数为：
$$Gini\_index(D,A)=\sum _{v=1}^V\frac{|D_v|}{|D|}Gini(D_v)$$
和特征熵类似，根据特征 A 的取值，将数据集分为 V 个子集， 分别计算每个子集的基尼指数，按照权重（占比）进行求和。

CART 树就是基于使用基尼指数作为划分依据，既可以做分类任务，又可以做回归任务，在候选特征集当中，选取基尼指数最小的特征。

4.5 决策树剪枝

不止是信息增益和基尼指数，只要有一个概念能够描述划分子集中的数据纯度，便可以产生一个决策树算法。然而研究表明：划分选择的各种准则虽然对决策树的尺寸有较大影响，但对泛化性能的影响很有限。例如信息增益与基尼指数产生的结果，仅在约 2% 的情况下不同。

剪枝方法和程度对于决策树泛化性能的影响更为显著。

在整个机器学习中，最大的敌人是过拟合。决策树的目的是把子集划分的越来越纯，当树的深度很深的时候，就学到了不该学的数据，将数据划分过于精细，决策树的泛化性能下降。剪枝（pruning） 主动去掉一些分支，之前能分干净的现在做不到了，训练数据的划分能力变弱，但整体的泛化能力变强，剪枝是决策树对付过拟合的主要手段。

基本策略：剪枝过程中通过划分测试集，评估剪枝前后树的优劣来决定是否剪枝。

• 预剪枝 （pre-pruning）：提前终止某些分支的生长（贪心的思想导致不顾及全局最优）
  • 划分前验证集精度与划分后相等，根据奥卡姆剃刀原则，预剪枝决策为不划分
  • 测试时间开销降低，训练时间开销降低
  • 过拟合风险降低，欠拟合风险增加
• 后剪枝 （post-pruning）：生成一棵完整的树之后，再回头剪枝
  • 划分前验证集精度与划分后相等，根据奥卡姆剃刀原则，后剪枝决策为不剪枝
  • 测试时间开销降低，训练时间开销增加
  • 过拟合风险降低，欠拟合风险基本不变
• 后剪枝泛化性能通常优于预剪枝

通常单个决策树一定要剪枝，而在集成学习中的弱学习器一般不剪枝。

5 支持向量机

5.1 支持向量机基本型

找到一个超平面方程 $w^{T}x+b=1$ ，将空间划分为两类。直觉上看，分类的点离这个超平面越远越好，离这个超平面最近的这些点叫做支持向量 (support vector)，两个异类支持向量到超平面的距离之和称之为间隔 (margin)。

5.2 求解方法

目标是寻找参数 $w$ 和 $b$，使得 $\gamma$ 最大，也就是最大化间隔。
$$\begin{array}{rl}& \arg \underset{\mathbf{w},b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2\\ & \text{ s.t. }{y}_i\left({\mathbf{w}}^{\top }{\mathbf{x}}_i+b\right)\ge 1,i=1,2,\dots ,m.\end{array}$$

如果明白凸优化理论，不难发现这是一个凸二次规划问题，能用优化计算包求解，但可以有更高效的办法——拉格朗日乘子法。

最终解为：
$$f(\mathbf{x})={\mathbf{w}}^{\top }\mathbf{x}+b=\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i^{\top }\mathbf{x}+b$$
在推导对偶问题时，引入的拉格朗日乘子存在约束条件，需要满足 KTT 条件：
$$\{\begin{array}{ll}{\alpha }_i\ge 0;& \\ 1-y_{i}f({\mathbf{x}}_i)\le 0;& \\ {\alpha }_i\left(1-y_{i}f({\mathbf{x}}_i)\right)=0.& \end{array}$$
解的稀疏性：训练完成后，最终模型仅与支持向量有关，支持向量机（Support Vector Machine, SVM） 因此而得名。

还有著名的 SMO 算法，是一个迭代更新的算法，先选取 KKT 条件违背程度最大的变量，当变量固定后，原始问题具有闭式解。

5.3 特征空间映射

若不存在一个能正确划分两类样本的超平面，怎么办？
将样本从原始空间映射到一个更高维的特征空间，使样本在这个特征空间内线性可分。

如果原始空间是有限维（特征数有限），那么一定存在一个高维特征空间使样本线性可分。

原始问题：
$$\begin{array}{rl}& \underset{\mathbf{w},b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2\\ & \text{ s.t. }{y}_i\left({\mathbf{w}}^{\top }\mathbf{\varphi }\left({\mathbf{x}}_i\right)+b\right)⩾1,i=1,2,\dots ,m.\end{array}$$
对偶问题：
$$\begin{array}{rl}& \underset{\mathbf{\alpha }}{\max }\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j\mathbf{\varphi }{\left({\mathbf{x}}_i\right)}^{\top }\mathbf{\varphi }\left({\mathbf{x}}_j\right)\\ & \text{ s.t. }\sum _{i=1}^m{\alpha }_i{y}_i=0,{\alpha }_i⩾0,i=1,2,\dots ,m\end{array}$$
预测：
$$f(\mathbf{x})={\mathbf{w}}^{\top }\mathbf{\varphi }(\mathbf{x})+b=\sum _{i=1}^m{\alpha }_i{y}_i\mathbf{\varphi }{\left({\mathbf{x}}_i\right)}^{\top }\mathbf{\varphi }(\mathbf{x})+b$$

5.4 核函数

由于两个高维向量求内积是困难的，所以设计核函数 (Kernel Function) ，它能绕过显式考虑特征映射、缓解计算高维内积的困难，并且直接在原始的特征空间计算。
$$\kappa (x_i,x_j)=\varphi (x_i{)}^{\mathrm{T}}\varphi (x_j)$$

Mercer 定理：若一个对称函数所对应的核矩阵半正定，则它就能作为核函数来使用。

任何一个核函数，都隐式地定义了一个 RKHS （Reproducing Kernel Hilbert Space，再生核希尔伯特空间）。

核函数选择是决定支持向量机性能的关键！

在机器学习中，没有最优解，只有近似最优解。在支持向量机算法中，前面的每一步都经过了严格的数学推导，是确定的，只有核函数这一步是无法确定的。

6 神经网络

神经网络是由具有适应性的简单单元组成的广泛并行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应。神经网络模型的两个最重要的要素是神经元模型和网络结构。

神经网络是一个很大的学科领域，这里仅讨论神经网络与机器学习的交集，即“神经网络学习”，亦称“连接主义（connectionism）”学习。

6.1 神经网络模型

神经网络中的简单单元是神经元模型，目前应用最广泛的还是 1943 年 McCulloch and Pitts 提出的 M-P神经元模型。神经网络学得的知识蕴含在连接权重 $w$ 与阈值 $\theta$ 中。

激活函数 (activation function)，也称响应函数、挤压函数，理想的激活函数是阶跃函数，0 表示抑制神经元，而 1 表示激活神经元，但阶跃函数具有不连续、不光滑等不好的性质，常用的是 Sigmoid 函数，在对率回归中也有用到。（其实 Sigmoid 并不是指某一个函数，S 型的函数都可以）

---

目前神经网络最常用的网络结构多层前馈网络。

• 多层网络：包含隐层的网络
• 前馈网络：神经元之间不存在同层连接也不存在跨层连接

隐层和输出层神经元亦称“功能单元”（Functional Unit）。

6.2 万有逼近性

多层前馈网络有强大的表示能力，也就是万有逼近性。

仅需一个包含足够多神经元的隐层，多层前馈神经网络就能以任意精度逼近任意复杂度的连续函数。

如何设置隐层神经元数是未决问题（Open Problem）。 实际常用“试错法”。

万有逼近性并不是神经网络独有的特性，具有万有逼近性是能够作为机器学习模型的一个前提，许多数学模型如傅立叶变换、泰勒展开式也具备这种性质。决策树在划分过程中有信息熵支撑最后一定能够划分很干净，支持向量机也有理论保障能够找到间隔满足要求的划分超平面。
为什么这里强调神经网络具有万有逼近性？因为神经网络整个训练过程一塌糊涂，是一个黑盒，没有严格的理论支撑，所以原来大家都怀疑它有没有万有逼近性，事实证明它有这个能力。

6.3 缓解过拟合

早停（early stopping）：

• 若训练误差连续 a 轮的变化小于 b，则停止训练
• 使用验证集：若训练误差降低、验证误差升高，则停止训练

正则化 （regularization）：

• 在误差目标函数中增加一项描述网络复杂度
• 模型偏好比较小的连接权和阈值，使网络输出更“光滑”
• $$E=\lambda \frac{1}{m}\sum _{k=1}^m{E}_k+(1-\lambda )\sum _i{w}_i^2$$

深度学习并非“突然出现”的"颠覆性技术”，而是经过了长期发展、很多研究者做出贡献，“冷板凳”坐“热”的结果。

7 贝叶斯分类器

7.1 贝叶斯决策论

贝叶斯决策论（Bayesian Decision Theory）是是概率框架下实施决策的基本理论。
给定 N 个类别，令 ${\lambda }_{ij}$ 代表将第 $j$ 类样本误分类为第 $i$ 类所产生的损失，则基于后验概率将样本 $x$ 分到第 $i$ 类的条件风险为：
$$R(c_i\mid \mathbf{x})=\sum _{j=1}^N{\lambda }_{ij}P(c_j\mid \mathbf{x})$$
贝叶斯判定准则（Bayes decision rule）：在条件风险中选择最小的。
$$h^{\ast }(\mathbf{x})=\underset{c\in \mathcal{Y}}{\mathrm{argmin}}R(c\mid \mathbf{x})$$

• $h^{\ast }$ 称为贝叶斯最优分类器（Bayes optimal classifier），其总体风险称为贝叶斯风险（Bayes risk）
• $1-R(h^{\ast })$ 反映了学习性能的理论上限

7.2 生成式和判别式模型

$P(c\mid x)$ 在现实中通常难以直接获得，从这个角度来看，机器学习所要实现的是基于有限的训练样本尽可能准确地估计出后验概率。

两种基本策略：

• 判别式（Discriminative） 模型
  • 思路：直接对 $P(c\mid x)$ 建模
  • 代表：
    • 决策树
    • BP 神经网络
    • SVM
• 生成式（Generative）模型
  • 思路：先对联合概率分布 $P(x\mid c)$ 建模，再由此获得 $P(c\mid x)$
    $$P(c\mid x)=\frac{P(x,c)}{P(x)}$$
  • 代表：贝叶斯分类器

7.3 贝叶斯定理

对于根据贝叶斯定理可以将上式 $P(c\mid x)$ 转为：
$$P(c\mid x)=\frac{P(c)P(x\mid c)}{P(x)}$$

• $P(c)$：先验概率（Prior），样本空间中各类样本所占的比例，可通过各类样本出现的频率估计（大数定律）
• $P(x)$：证据（Evidence）因子，与类别无关
• $P(x\mid c)$： 样本相对于类标记的类条件概率 (Class-Conditional Probability)，亦称似然 (Likelihood)

主要困难在于估计似然。

7.4 极大似然估计

先假设某种概率分布形式（独立同分布），再基于训练样例对参数进行估计。

假定 $P(x\mid c)$ 具有确定的概率分布形式，且被参数 ${\theta }_c$ 唯一确定，则任务就是利用训练集 D 来估计参数 ${\theta }_c$。

${\theta }_c$ 对于训练集 D 中第 c 类样本组成的集合 $D_c$ 的似然（Likelihood）为：
$$P(D_c\mid {\theta }_c)=\prod _{c\in D}P(x\mid {\theta }_c)$$
概率都是小于 1 的浮点数，连乘易造成下溢，因此通常使用对数似然（Log-Likelihood）：
$$LL({\theta }_c)=\log P(D_c\mid {\theta }_c)=\sum _{x\in D_c}\log P(x\mid {\theta }_c)$$
于是 ${\theta }_c$ 的极大似然估计为 ${\hat{\theta }}_c=\arg {\max }_{{\theta }_c}LL({\theta }_c)$

7.5 朴素贝叶斯分类器

朴素贝叶斯分类器（Naive Bayes Classifier）对于：
$$P(c\mid x)=\frac{P(c)P(x\mid c)}{P(x)}$$
主要障碍是求解所有属性上的联合概率 $P(x\mid c)$ ，难以从有限训练样本估计获得，并且存在组合爆炸；样本稀疏的问题。

基本思路是假定所有特征是独立的。

• 估计 $P(c)$：$$P(c)=\frac{|D_c|}{|D|}$$
• 估计 $P(c\mid x)$：
  • 离散属性：令 $D_{c{x}_i}$ 表示 $D_C$ 中在第 i 个属性上取值为 $x_i$ 的样本组成的集合$$P(x_i\mid c)=\frac{|D_{c,x_i}|}{|D_c|}$$
  • 连续属性：考虑概率密度函数，假定 $p(x_i\mid c)\sim \mathcal{N}({\mu }_{c,i},{\sigma }_{c,i}^2)$ $$p(x_i\mid c)=\frac{1}{\sqrt{2\pi }{\sigma }_{c,i}}\exp \left(-\frac{(x_i-{\mu }_{c,i}{)}^2}{2{\sigma }_{c,i}^2}\right)$$

7.6 拉普拉斯修正

在单纯的贝叶斯定理中，若某个属性值在训练集中没有与某个类同时出现过，则直接计算会出现
问题，因概率连乘将“抹去”其他属性提供的信息。例如，若训练集中未出现过“敲声=清脆”的好瓜，则模型在遇到“敲声=清脆”的测试样本时，不论其他特征多么符合好瓜的“定义”，也会断定为好瓜的概率为 0。

拉普拉斯修正(Laplacian Correction) 解决了这一问题，思路非常简单，初始时为所有可能的特征值添加 1 个初始值。
$$\hat{P}(c)=\frac{|D_c|+1}{|D|+N},\hat{P}(x_i\mid c)=\frac{|D_{c,x_i}|+1}{|D_c|+N_i}$$

不过这里假设了特征值与类别的均匀分布，这是额外了引入的 bias，因此要根据实际问题量身定制 bias。比如好人比坏人多，给初始值的时候给好人多一些。

8 集成学习

集成学习（Ensemble Learning）将多个个体学习器组合起来，显著提高整体的预测能力。只包含同种类型的个体学习器的集成称为同质集成，包含不同类型个体学习器的称为异质集成。

术语梳理：

• 基学习器：是集成学习的基本组成部分，可以是弱学习器或强学习器。
• 个体学习器：广泛指单个模型，强调其与其他学习器的独立性。所有基学习器都是个体学习器。
• 弱学习器：专指那些表现略好于随机猜测的模型，通常在集成学习中（尤其是 Boosting）用于组合成强学习器。
• 强学习器：性能很强、准确率高的学习器，可以是单个模型或由多个基学习器组合而成的模型（如随机森林）。

集成学习分为两大类：

• 序列化方法
  • AdaBoost ［Freund & Schapire, JCSS97］
  • Gradient Boost［Friedman, AnnStat01］
  • LPBoost［Demiriz, Bennett, Shawe-Taylor, MLJ06］
• 并行化方法
  • Bagging［Breiman, MLJ96］
  • Random Forest［Breiman, MLJ01］
  • Random Subspace［Ho, TPAMI98］

Gradient Boost 早在 2001 年便已提出，是一种框架性算法，后来华人学生陈天奇在 2014 年发布 XGBoost，是 Gradient Boos 的一种高效实现。它在算法的基础上引入了许多工程化的改进，使得模型训练更快、更稳健，并且在很多竞赛中表现出色。

8.1 Boosting

由 AdaBoosting 发展而来的这一系列算法称为 Boosting，整体流程为：

1. 初始化权重：给每个训练样本分配一个初始权重，通常是相同的
2. 迭代弱学习器：经过多轮迭代，每轮生成一个弱学习器
   1. 训练弱学习器：使用带有权重的训练数据训练一个新的弱学习器，重点关注权重较高样本
   2. 更新样本权重：每轮的学习器根据评估结果赋予权重（如决策树可以直接处理权重）或采样（按比例抽取，如神经网络中无法处理权重），使错误样本在后续学习中得到更多关注
3. 组合多个弱学习器：将多个弱学习器的预测结果按照加权组合，得到最终结果

由于都是前者学习器未能解决的问题，越往后的学习器需要攻克的问题越困难，一般来说准确率越低。

8.2 Bagging

Bagging 的数据都来自原始数据集，怎样保证多样性？可以使用 Bootstrap 采样，在不同的数据集上训练，得到的结果使用投票解决分类问题，使用平均解决回归问题。

8.3 好而不同

Bagging 通过举手表决做出最终判断，如果个体学习器的表决都一样，那么整体的预测并不会有提升，如果个体学习器的错误率很高，整体可能更差。所以 Bagging 的核心思想是个体学习器需要好而不同。

有一个式子描述“好而不同”，误差-分歧分解 （error-ambiguity decomposition）：

然而多样性（diversity）是不易做到的，当多个个体学习器的准确率都达到很高，比如 99% 时，它们之间是高度相似的，此时就可以考虑舍弃一些准确率，从而来提升多样性。

同质集成只需要使用同一种算法，实现方便，但是最大的麻烦是如何保持多样性。
异质集成有天然的优点，具有多样性，但是不同算法的输出之间无法直接比较，需要做配准（alignment）。这件事非常困难，所以重点讨论的还是同质集成。

9 聚类

9.1 概述

监督学习：分类、回归
无监督学习：聚类、密度估计

聚类是无监督学习中研究最多、应用最广的。

目标：将数据样本划分为若干个通常不相交的簇（cluster）。

既可以作为一个单独过程用于找寻数据内在的分布结构，也可以作为分类等其他学习任务的前驱过程。
比如：在没有先验知识的前提下对客户进行分组，提供个性化策略。

9.2 聚类性能指标

聚类性能度量，也称为有效性指标（validity index）。

• 外部指标（external index）：将聚类结果与参考模型（referencemodel）进行比较。但参考模型并不意味着标准，可以有很多种聚法。如 Jaccard 系数，FM 指数，Rand 指数。
• 内部指标（internal index）：直接考察聚类结果而不参考模型。如 DB 指数、Dunn指数。基本想法是簇内尽可能紧密，簇间尽可能远离：
  • 簇内相似度高
  • 簇间相似度低

9.3 距离度量

上一节中提到簇内尽可能紧密，既然谈到紧密，就一定涉及某种距离度量。

距离度量（distance metric）需满足的性质：
$$\begin{array}{rl}& \text{非负性:dist}({\mathbf{x}}_i,{\mathbf{x}}_j)⩾0;\\ & \text{同一性:dist}({\mathbf{x}}_i,{\mathbf{x}}_j)=0\text{ 当且仅当 }{\mathbf{x}}_i={\mathbf{x}}_j;\\ & \text{对称性:dist}({\mathbf{x}}_i,{\mathbf{x}}_j)=\mathrm{dist}({\mathbf{x}}_j,{\mathbf{x}}_i);\\ & \text{直递性:dist}({\mathbf{x}}_i,{\mathbf{x}}_j)⩽\mathrm{dist}({\mathbf{x}}_i,{\mathbf{x}}_k)+\mathrm{dist}({\mathbf{x}}_k,{\mathbf{x}}_j).\end{array}$$
尽管大部分距离满足上述四个条件，然而某些情况第四条直递性不满足，需要使用非距离度量（Non-metric distance）。在图像识别等领域还有相似度（Similaring），也有非距离度量的理念。

常用距离形式-闵可夫斯基距离：
$${\mathrm{dist}}_{\mathrm{mk}}({\mathbf{x}}_i,{\mathbf{x}}_j)={\left(\sum _{u=1}^n|x_{iu}-x_{ju}{|}^p\right)}^{\frac{1}{p}}$$

对于无序（non-ordinal）属性，可使用 VDM(Value Difference Metric)，令$m_{u,a}$表示属性$u$上取值为$a$的样本数，$m_{u,a,i}$表示在第$i$个样本簇中在属性$u$上取值为$a$的样本数，$k$为样本簇数，则属性$u$上两个离散值$a$与$b$之间的 VDM 距离为：
$$\begin{array}{r}VD{M}_p(a,b)=\sum _{i=1}^k{\left|\frac{m_{u,a,i}}{m_{u,a}}-\frac{m_{u,b,i}}{m_{u,b}}\right|}^p\end{array}$$

对于混合属性，可以使用 MinkovDM：
$${\mathrm{MinkovDM}}_p(x_i,x_j)={\left(\sum _{u=1}^{n_c}|x_{iu}-x_{ju}{|}^p+\sum _{u=n_c+1}^n{\mathrm{VDM}}_p(x_{iu},x_{ju})\right)}^{\frac{1}{p}}$$

9.4 聚类方法概述

聚类的好坏没有绝对标准，可以将人们按男女聚类，也可以按照是否近视聚类。

聚类的故事：
老师拿来苹果和梨，让小朋友分成两份。
小明把大苹果大梨放一起，小个头的放一起，老师点头，恩，体量感。
小芳把红苹果挑出来，剩下的放一起，老师点头，颜色感。
小武的结果？不明白。小武掏出眼镜：最新款，能看到水果里有几个籽，左边这堆单数，右边双数。
老师很高兴：新的聚类算法诞生了。

聚类也许是机器学习中“新算法”出现最多、最快的领域总能找到一个新的“标准”，使以往算法对它无能为力。

• 原型聚类
  • 亦称“基于原型的聚类” （prototype-based clustering）
  • 假设：聚类结构能通过一组原型刻画
  • 过程：先对原型初始化，然后对原型进行迭代更新求解
  • 代表：k均值聚类，学习向量量化（LVQ），高斯混合聚类
• 密度聚类
  • 亦称“基于密度的聚类”（density-based clustering）
  • 假设：聚类结构能通过样本分布的紧密程度确定
  • 过程：从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇
  • 代表：DBSCAN, OPTICS, DENCLUE
• 层次聚类 （hierarchical clustering）
  • 假设：能够产生不同粒度的聚类结果
  • 过程：在不同层次对数据集进行划分，从而形成树形的聚类结构
  • 代表：AGNES（自底向上），DIANA（自顶向下）