机器学习读书笔记

Reference

机器学习, 周志华

基本概念及发展历程

引言

机器学习所研究的主要内容, 是关于在计算机上从数据产生模型(model)的算法, 即学习算法(learning algorithm). 我们将经验数据提供给它, 他能基于数据产生模型, 当我们面对新情况时, 模型会给我们相应的判断.

基本术语

示例(instance)或样本(sample): 关于一个事件或对象的描述.

数据集(data set): 示例的集合.

属性(attribute)或特征(feature): 反应事件或对象在某方面的表现或性质的事项.

属性空间(attribute)或样本空间(sample space): 属性张成的空间.

特征向量(feature vector): 一个示例对应的点.

学习(learning)或训练(training): 从数据中学习模型的过程.

训练数据: 训练过程中使用的数据.

训练集: 训练样本组成的集合.

标记(label): 预测关于示例结果的信息.

标记空间(label space): 标记的集合.

样例(example): 有标记的示例.

分类(classification): 预测的值是离散值.

回归(regression): 预测的值是连续值.

测试(testing): 学习模型后用其进行预测.

测试样本.

聚类(clustering): 模型将训练集中的示例分成多组.

簇(cluster): 训练集示例的一个子集, 可能对应某些潜在概念.

监督学习(supervised learning): 训练数据有标记信息. 分类和回归是其代表.

无监督学习(unsupervised learning): 训练数据无标记信息. 聚类是其代表.

泛化(generalizatioin): 学得模型适应新样本的能力, 强泛化能力的模型能很好地适用于整个样本空间.

样本分布: 我们假设全体样本服从一个未知的分布, 我们获得的每一个样本都是独立同分布的. 一般而言, 样本越多, 我们通过学习获得的模型泛化能力越强.

假设空间

归纳(induction): 一般到特殊的泛化过程.

演绎(deduction): 特殊到一般的特化过程.

归纳学习(inductive learning): 从样例中学习的过程是一个归纳过程.

归纳学习

  • 狭义: 从训练数据中学得概念(concept), 亦称为概念学习, 概念形成. 目前这方面研究较少, 因为要学得泛化性能好, 语义明确的概念很困难, 现实常用的是黑箱模型.
  • 广义: 大体相当于从样例中学习

概念学习

布尔概念学习: 对可表示为是或不是的目标概念的学习

比如我想学习一个瓜怎么样算是好瓜(色泽==? && 根蒂==?&&敲声==?)

这个学习过程是一个在所有假设(hypothesis)组成的空间中进行搜索的过程, 搜索目标是找到与训练集匹配(fit)的假设.

现实问题中的假设空间很大, 但训练集很小, 会导致有多个匹配的假设, 这些假设的集合成为版本空间(versioin space)

归纳偏好

如上述的版本空间的问题, 这时候我们需要算法本身具有偏好. 任何有效的机器学习算法必有归纳偏好, 不然会被假设空间中看似在训练集上等效的假设迷惑. 可视化即为用一条合适的曲线分类两组点, 显然曲线有很多条.

归纳偏好可视为算法本身具有启发式或价值观. 一般的引导原则是奥卡姆剃刀(Occam’s razor), 即在多个与观察一致的假设中选取最简单的那个. 当然奥卡姆剃刀本身也不平凡. 实际中选取的偏好要尽量与实际问题匹配.

若数据包含噪声, 我们可以设置归纳偏好为:

通常认为两个数据的属性越相近,则更倾向于将他们分为同一类。若相同属性出现了两种不同的分类,则认为它属于与他最临近几个数据的属性。也可以考虑同时去掉所有具有相同属性而不同分类的数据,留下的数据就是没误差的数据,但是可能会丢失部分信息。

没有免费的午餐定理(No Free Lunch Theorem)

$H$: 假设空间

$L_\alpha$: 学习算法

$l$: 任意一个误差度量

$P(h|X,L_\alpha)$: 算法$L_\alpha$基于训练数据$\chi$产生假设$h$的概率

$f$: 希望学得的真实目标函数, 这个函数属于一个函数空间, 定理的一个重要前提是假设目标函数$f$是均匀分布.

二式是因为$f$可能有$|\chi|$的种

NFL意义

对于某一样本空间和某一标记空间的所有问题(每一个问题对应一个目标函数, 并假设每一个问题的等同重要的, 即目标函数空间是均匀分布), 选取任意一个算法, 对于最终某一目标函数在这个域上用任意一个算法学得的模型, 这个模型对非训练样本的预测能力的期望与算法无关.

即脱离问题选取算法毫无意义, 需要针对特定问题选取算法.

发展历程

机器学习是人工智能研究发展到一定阶段的必然产物.

  • 二十世纪五十年代到七十年代: 推理期, 人们认为只要赋予机器逻辑推理能力, 就能拥有智能, 代表工作有逻辑理论家(Logic Theorist, By A. Newell and H. Simon), 证明了数学原理的定理. 然而人们意识到仅具有逻辑推理能力是远远实现不了人工智能的, 要让机器具有知识. (?)
  • 二十世纪七十年代中期, 专家系统, 但有知识工程瓶颈, 因为人把知识总结出来教给计算机是相当困难的.
  • 二十世纪八十年代, 从样例中学习的一大主流是符号主义学习, 包括决策树和基于逻辑的学习. 决策树学习以信息论为基础, 以信息熵最小化为目标, 之际模拟了人类对概念进行判断的树形流程. 基于逻辑的学习使用谓词逻辑进行知识表达, 通过修改和扩充逻辑表达式来完成对数据的归纳.
  • 二十世纪九十年代中期以前, 连接主义
  • 二十世纪九十年代中期, 统计学习, 代表方法为支持向量机和核方法.
  • 二十一世纪, 由于数据多, 计算能力强, 连接主义复兴, 深度学习大热.

阅读材料

  • 机器学习: 一种人工智能途径
  • 人工智能手册

模型评估与选择

经验误差与过拟合

错误率(error rate): 分类错误的样本占样本总数(训练期间为训练集, 测试期间为测试集)的比例称为错误率.

精度(accuracy): 1-错误率

误差(error): 学习器的实际预测输出与样本的真实输出之间的差异.

  • 训练误差(training error)或经验误差(empirical): 在训练集上的误差
  • 泛化误差(generalization): 在新样本上的误差

我们希望模型对新样本也能有较好的精度.

过拟合(overfitting): 当学习器把训练样本学的太好, 把训练样本自身的一些特点当作所有潜在样本都会具有的一般性质时, 会导致泛化能力下降.

欠拟合(underfitting): 对训练样本的一般性质尚未学习好.

常见的导致过拟合的原因是学习能力过于强大, 常见的欠拟合原因是学习能力低下. 欠拟合较容易克服, 而过拟合是机器学习的关键障碍, 各类算法都必然带有一些针对过拟合的措施, 过拟合是无法避免的, 只能减缓.

模型选择(model selection): 选择算法, 选择算法的参数配置.

现实中我们需要选择不同的模型, 需要方法评估不同模型的泛化误差.

评估方法

通常, 可以通过实验测试来对学习器的泛化误差进行评估, 进而做出选择, 为此需要一个测试集进行测试, 用测试误差作为泛化误差的近似. 通常假设测试集也是从样本真是分布中独立同分布采样得到的, 需要注意的是, 测试集应该尽可能与训练集互斥.

留出法

留出法(hold-out): 直接将数据集D划分为两个互斥的集合. 训练集S和测试集T的划分要尽可能保持数据分布的一致性, 避免因数据划分过程引入额外的偏差.

划分通常是随机的.

缺点:

  • 若使训练集S包含绝大多数样本, 则训练出的模型可能更接近于用D训练出的模型, 但由于T比较小, 评估结果可能不够稳定准确.
  • 若令测试集T多包含一些样本, 则训练集S与D的差别更大, 学习到的映射可能不是理想的映射.

交叉验证法

先将数据集D划分为k个大小近似的互斥子集, 每个子集都尽可能保持数据分布的一致性, 即从D中通过分层抽样得到, 每次选取一个子集为测试集, 可以获得k组训练测试集, 进行k次训练和测试, 返回k个测试结果的均值. 显然, 交叉验证法评估结果的稳定性和保真性在很大程度上取决于k的取值. 常用为10折.

1543850668243

为减小因样本划分不同引入的差别, 需要重复选取不同的k值p次, 并返回均值.

留一法: 设数据集包含m个样本, k=m. 留一法被认为比较准确, 但是开销巨大.

自助法

我们希望评估的是用D训练出来的模型, 但是在交叉验证法中我们需要保留测试样本, 因此实际评估的模型会比D小, 引入了一些因训练样本规模不同而导致的估计偏差. 留一法虽好, 但是代价高昂. 我们希望找到一种可以减少训练样本规模不造成影响, 同时高效估计的方法.

自助法(bootstrapping)直接以自助采样法为基础, 给定包含m个样本的数据集D, 对其进行采样产生数据集D’, 每次随机从D中挑选一个样本, 将其拷贝放入D’, 然后再将该样本放回初始数据集D, 使得该样本在下次采样时仍有可能被采到.

这个过程重复执行m次, 得到包含m个样本的数据集D’. D中有一部分样本会在D’中多次出现, 而另一部分样本不出现. 样本在m次采样后不被采到的概率是$lim(1-\frac{1}{m})^m=\frac{1}{e}\approx 0.368$

通过自助采样, 初始数据集D中约有36.8%的样本未出现在采样数据集D’中. 我们可以将D’作为训练集, D\D' 作为测试集, 这样实际评估的模型与期望评估的模型都使用m个训练样本. 这样的测试结果称为”包外估计”(out-of-bagestimate).

自助法在数据集较小, 难以有效划分训练/测试集时很有用.

自助法能产生多个不同训练集, 对集成学习等方法有很大好处.

但是自助法产生的数据改变了初始数据集的分布, 引入估计偏差. 因此, 初始数据量足够时, 留出法和交叉验证法更常用.

调参与最终模型

调参(parameter tuning): 对算法参数进行设定. 这和算法选择没有本质区别.

常用调参方法为在选择范围和步长, 取一组离散点.

最终提交给用户的模型需要用选定的参数和全部数据集重新训练.

测试数据: 学得模型在实际使用中遇到的数据.

验证集(validation set): 模型评估与选择中用于评估测试的数据集.

性能度量

上一节讲的是实验中的估计方法, 这一节讲衡量模型泛化能力的评价标准, 即性能度量(performance measure).

对于回归问题, 一般使用均方误差, 对更一般的情况, 对数据分布D和概率密度函数p, 均方误差可描述为:

对于分类问题, 下面详述.

错误率与精度

错误率与精度定义

查准率, 查全率与F1

精度关心的是预测精度, 但假如我们关心的是挑出来的瓜多少是好瓜, 好瓜中多少被挑出来, 我们就需要其他度量.

分类结果混淆矩阵

预测真预测假
真实真TP(真正例)FN(假反例)
真实假FP(假正例)TM(真反例)

查准率P: 挑出的瓜中好瓜比例

查全率R: 好瓜中多少被挑出来

查准率与查全率一般成负相关.

文章目录
  1. 1. Reference
  2. 2. 基本概念及发展历程
    1. 2.1. 引言
    2. 2.2. 基本术语
    3. 2.3. 假设空间
      1. 2.3.1. 概念学习
    4. 2.4. 归纳偏好
      1. 2.4.1. 没有免费的午餐定理(No Free Lunch Theorem)
    5. 2.5. 发展历程
    6. 2.6. 阅读材料
  3. 3. 模型评估与选择
    1. 3.1. 经验误差与过拟合
    2. 3.2. 评估方法
      1. 3.2.1. 留出法
      2. 3.2.2. 交叉验证法
      3. 3.2.3. 自助法
      4. 3.2.4. 调参与最终模型
    3. 3.3. 性能度量
      1. 3.3.1. 错误率与精度
      2. 3.3.2. 查准率, 查全率与F1
|