机器学习基础：基本概念、评估方法与性能度量

计算学习理论#

概率近似正确（Probably Approximately Correct，PAC）描述的是一种学习保证：训练样本由未知分布随机抽取时，学习算法以至少 $1-\delta$ 的概率得到泛化误差足够小的模型。

一种常见的不可知 PAC 表述是：

其中，$S$ 是从分布 $\mathcal D$ 独立抽取的训练集，$h_S$ 是算法根据 $S$ 学到的模型，$R_{\mathcal D}(h)$ 是模型在真实分布上的风险。

$\epsilon$ 表示允许的误差裕量，$\delta$ 表示学习保证失败的概率。公式中的概率来自训练集的随机抽取，而不是“取得某个模型”的概率。

PAC 讨论的是样本复杂度和泛化保证，不能由 $\epsilon=0$、$\delta=0$ 推导出 P 与 NP 的关系。通常只要求二者为足够小的正数。

术语名词#

1.示例 = 特征向量，样本

• 名词解释:即对某个事件或者对象的 全局 描述
• 构成元素:多组(特征:特征值)
• 样本 要根据上下文来判断含义

2.特征 = 属性

• 名词解释：即对某个事件或对象的一个 具体 特征的描述

3.样本空间 = 属性空间 = 输入空间

• 名词解释：即特征张成的空间，空间中每个点对应一个特征向量即样本

4.数据集、训练集、验证集与测试集

• 训练集用于拟合模型参数。
• 验证集用于选择模型和超参数。
• 测试集只用于最终评估，不能参与调参。

一个包含 $m$ 个样本的数据集可表示为：

若每个样本包含 $d$ 个特征，则 $\boldsymbol x_i\in\mathbb R^d$。实际划分比例应根据样本量与任务决定，并不存在固定的“二八分”规则。

5.样例，标记，标记空间

• 样例=样本+标记

标记：即想预测的结果的 实际信息，比如想预测瓜的好坏，实际样本中的信息为”好瓜”/“坏瓜”，

一般表示为：

标记空间 or 输出空间：所有标记的集合

6.假设空间，版本空间

1
假设：学得模型关于数据的潜在规律
2

3
真实or真相：潜在规律本身
4

5

6
假设空间：所有假设构成的集合
7

8
版本空间：与训练集一致的假设构成的集合，由一个或多个假设空间的子集构成

…

基本假设#

我们知道训练出的模型是为了对未知数据进行结果预测

但是为什么模型可以对未知数据进行预测呢？

这里我们引出了机器学习的基本假设。

归纳偏好#

归纳偏好对应了学习算法本身所做出的关于“什么样的模型更好”的假设

对假设空间 筛选 后所得到的 版本空间中 可能有多个假设 这些假设都能够匹配训练集中的训练样本

而如何对版本空间中的假设进行选择呢？🤔

这里引入一个原则or方法论：

奥卡姆剃刀：

若非必要勿增实体

选取多个假设中最简单的。

但是其实感觉没啥用，因为”简单“的定义难以量化。

一个“随机乱猜”的算法有可能优于精心选择的算法

“没有免费的午餐”（NFL）定理：

1
任意算法的“训练集外误差”相等，即不同算法的误差期望相同，无绝对意义上的更优算法。

所以 不能摆脱具体问题 谈论算法的优劣

实际上：还是看测试集再模型上的效果，以及结合特定领域的需求对模型进行选择

机器学习分类#

1
预测结果 ∈ R

机器学习的发展#

• 符号主义：源于数学逻辑，产生明确的概念表示

  符号主义认为人工智能源于数理逻辑后来又发展了 启发式算法>专家系统>知识工程理论与技术

  主要方向：决策树 和 基于逻辑的学习

  1
    决策树->模拟人类对概念的判定树形过程
  2
  
  3
    基于逻辑的学习-->典型代表：归纳逻辑程序设计(ILP)

• 连接主义：基于神经网络

  算法复杂度高，假设空间大，且参数设置缺乏理论指导

  经典代表：BP反向传播算法

• 统计学习：支持向量机(SVM)，核方法

  与连接主义关系密切

• 深度学习：早期连接主义的衍生，基于神经网络，现阶段很流行

1.1 留出法(hold-out)：#

将数据集直接划分为训练集和测试集

留出法：对数据集的划分方法会影响模型结果；训练集和测试集的数据分布必须保持一致；测试集过大会使模型拟合效果变差，太小会使得测试估计偏小；有一些数据可能从未被训练过

总结：

1. 保证数据分布一致性（比如分层取样）
2. 多次重复划分 (例如: 100次随机划分)
3. 测试集不能太大或太小（例如：1/5~1/3，其实二八分偏多）
4. 可能遗漏数据（随机划分没取到该数据进行训练）

1.2 交叉验证法#

对于 留出法出现 可能遗漏数据（随机划分没取到该数据进行训练）的问题

我们引入新的划分方法 k-折交叉验证法 可以有效解决该问题

以该图为例：

首先将数据集D随机划分为10个子集， 进行十次操作， 每一次取其中1个子集为测试集，其余为训练集（实际也可以选取多个子集为测试集） 将结果做平均处理

而对于再划分子集的阶段，将测试集中只留有一个数据的方法叫做留一法 留一法每次只留一个样本用于验证，因此单次训练集与原始数据集非常接近。它的数据利用率高，但需要训练 $m$ 次，计算成本较高；不同训练集高度重叠，评估结果也可能具有较高方差。

优缺点：

在 $k$ 折交叉验证中，每个样本会恰好作为一次验证样本，并在其余 $k-1$ 折中参与训练。较大的 $k$ 能提高训练数据利用率，但会显著增加计算成本。

划分时仍要遵守数据的独立结构。例如，同一用户、同一时间序列或同一实体的相关样本不应随意分到训练折和验证折，否则可能产生数据泄漏。

1.3 自助法#

“自助法”(bootstrapping) 基于放回取样 亦称“可重复采样”

从含有 $m$ 个样本的原始数据集中进行 $m$ 次有放回抽样，可以得到一个大小仍为 $m$ 的训练集，但其中会包含重复样本。

某个原始样本在一次抽样中未被选中的概率为 $1-1/m$，在 $m$ 次抽样后仍未被选中的概率为：

因此，约有 $36.8\%$ 的原始样本不会进入本次自助训练集，可作为包外样本（out-of-bag samples）进行评估；进入训练集的不同原始样本约占 $63.2\%$。

优缺点：

优点： 自助法在数据集较小、难以有效划分训练/测试集时很有用， 自助法能从初始数据集中产生多个不同的训练集,这对集成学习等方法有很大的好处。

缺点： 自助法产生的数据集改变了初始数据集的分布，这会引入估计偏差。但是通过增加数据划分的次数，就可以缓解该影响。

1.4 调参与验证集#

在模型评估与选择的过程中，我们既要选择学习算法，还要对算法的参数进行设定

训练过程中的参数分为两种：

• 算法参数：亦称“超参数”，由人工设定
• 模型参数：由训练集训练而成

1.5 重新训练#

模型选择和调参完成后，可以合并训练集与验证集重新训练最终模型，再使用此前从未参与训练和调参的测试集进行一次独立评估。

测试集不是用来选择算法或参数的。如果把测试集也用于重新训练，就不能再用同一测试集报告无偏的泛化性能。部署前确实可以使用全部已有数据训练，但之后应准备新的独立数据进行评估。

2.1 错误率和精度#

错误率定义：

精度定义：

然而对于不同的任务需求，仅仅用错误率和精度是不够的，故引出查准率、查全率、F1的概念

2.2 查准率、查全率、F1#

1
现有一瓜田含10000个瓜，其中有100个好瓜，利用学习器挑瓜

2.3 ROC与AUC#