C01. 绪论

这是一本机器学习本科生教材，只要具备大学本科三年级水平就可以满足自学需要。

提纲

• 重点

• 难点

• 要点

基本知识点

1.1 引言

机器学习：研究如何通过计算的手段，利用经验来改善系统自身的性能。

• 在计算机系统中，「经验」以「数据」形式存在，因此机器学习就是关于在计算机上从数据中产生「模型」的算法，即「学习算法」。
  • 「模型」泛指从数据中觉得的结果
    • 「模型」指全局性结果 ( 例如：一棵规则树 )
    • 「模式」指局部性结果 ( 例如：一条规则 )

1.2 基本术语

• 「数据集」(Data Set)：一组记录的集合

  • 「示例」或者「样本」：集合中的记录，用于描述事件或者对象，每条记录对于一个描述
  • 「属性」或者「特征」：反映事件或者对象在某个方面的表现或者性质的事项
    • 「属性值」：属性上的取值
  • 「属性空间」或者「样本空间」或者「输入空间」：属性张成的空间

• 「特征向量」：即示例，因为样本空间中的每个点对应一个坐标向量

  • 使用 $D={\text{x}_1,\cdots,\text{x}_m}$ 表示包含 $m$ 个示例的数据集
  • 每个示例由 $d$ 个属性描述
    • 每个示例 $\text{x}i= ( x{i1},\cdots,x_{id} )$ 是 $d$ 维样本空间 $\mathcal{X}$ 中的一个向量，即 $\text{x}_i\in\mathcal{X}$
    • $x_{ij}$ 是 $\text{x}_i$ 在第 $j$ 个属性上的取值
    • $d$ 是 $\text{x}_i$ 的「维度」

• 「学习」或者「训练」：从数据中学得模型的过程，通过执行某个学习算法来完成

  • 「训练数据」：训练过程中使用的数据
    • 「训练样本」：训练数据中的样本
    • 「训练集」：训练样本组成的集合
  • 学得模型对应了关于数据的某种潜在的规则，称为「假设」，这种潜在规律本身，称为「真相」或者「事实」
    • 学习过程就是为了找出或者逼近真相
  • 「模型」有时也称为「学习器」，是学习算法在给定数据和参数空间上的实例化

• 「标记」：关于示例结果的信息

  • 「样例」：拥有了标记信息的示例
  • 「标记空间」或者「输出空间」：所有标记的集合

• 如果预测是离散值，学习任务称为「分类」

  • 「二分类」任务：只涉及两个类别的学习任务
  • 「多分类」任务：需要涉及多个类别的学习任务
  • 「回归」任务：如果预测是连续值

• 学到模型后，使用其进行预测的过程称为「测试」

  • 被预测的样本称为「测试样本」

• 学习任务的分类

  • 监督学习：分类与回归
  • 无监督学习：聚类

• 学得模型适用于新样本的能力称为「泛化」

  • 具有强泛化能力的模型能够很好地适用于整个样本空间

• 假设样本空间中全体样本服从一个未知「分布」$\mathcal{D}$，那么获得的每个样本都是独立地从这个分布上采样获得的，即「独立同分布」( independent and identically distributed, i.i.d. )

  • 训练样本越多，得到的关于 $\mathcal{D}$ 的信息就越多，通过学习获得的模型的泛化能力就越强

1.3 假设空间

• 「归纳」是从特殊到一般的「泛化」，即从具体的事实归结出一般性规律
  • 「从样例中学习」是一个归纳过程，也称为「归纳学习」
    • 广义的归纳学习是从样例中学习
    • 狭义的归纳学习是从训练数据中学习，也称为「概念学习」或者「概念形成」
• 「演绎」是从一般到特殊的「特化」，即从基础原理推演出具体状况
  • 在数学公理系统中，基于一组公理和推理规则推导出与之相洽的定理，这是「演绎」
• 学习过程就是在所有假设组成的空间中进行搜索的过程，通过搜索找到与训练集「匹配」的假设
  • 学习过程面临假设空间过大和样本训练集有限这个矛盾，因此存在着一个与训练集一致的「假设集合」，称为「版本空间」

1.4 归纳偏好

机器学习算法在学习过程对某种类型假设的偏好，称为「归纳偏好」或者「偏好」

• 奥卡姆剃刀 ( Occam’s Razor ) 是一种常用的基本的原则，即「若有多个假设与观察一致，则选择最简单的那个」
• 「没有免费的午餐」定理 ( No Free Lunch Theorem, NFLT )，任意两种学习算法的期望性能完全相同
  • 假设样本空间 $\mathcal{X}$ 和 假设空间 $\mathcal{H}$ 都是离散的
  • $P ( h|X,\mathcal{L}_a )$ 代表算法 $\mathcal{L}_a$ 基于训练数据 $X$ 产生假设 $h$ 的概率
  • $f$ 代表希望学习的真实目标函数
  • $\mathbb{I} ( \cdot )$ 表示指示函数，$\mathbb{I} ( a ) =\begin{cases}1,a\neq 0\0,others\end{cases}$
  • $\mathcal{L}_a$ 的「训练集外误差」，即$\mathcal{L}_a$ 在训练集之外的所有样本上的误差为

$$
\begin{aligned}
E_{ote} ( \mathcal{L}a|X,f )
&=\sum{h}\sum_{\text{x}\in\mathcal{X}-X} P ( \text{x} ) \mathbb{I} ( h ( \text{x} )) \
&=f ( \text{x} ) P ( h|X,\mathcal{L}_a )
\end{aligned}
$$

• 二分类问题，真实目标函数可以是任何函数 $\mathcal{X}\mapsto{0,1}$, 函数空间为 ${0,1}^{|\mathcal{X}|}$, 对所有可能的 $f$ 按均匀分布对误差求和

$$
\begin{aligned}
\sum_f E_{ote} ( \mathcal{L}a|X,f )
&=\sum_f\sum_h\sum{\text{x}\in\mathcal{X}-X} P ( \text{x} ) \mathbb{I} ( h ( \text{x} ) \neq f ( \text{x} )) P ( h|X,\mathcal{L}a ) \
&=\sum{\text{x}\in\mathcal{X}-X} P ( \text{x} ) \sum_h P ( h|X,\mathcal{L}a ) \sum_f \mathbb{I} ( h ( \text{x} ) \neq f ( \text{x} )) \
&=\sum{\text{x}\in\mathcal{X}-X} P ( \text{x} ) \sum_h P ( h|X,\mathcal{L}a ) \frac12 2^{|\mathcal{X}|}\
&=\frac12 2^{|\mathcal{X}|} \sum{\text{x}\in\mathcal{X}-X} P ( \text{x} ) \sum_h P ( h|X,\mathcal{L}a ) \
&=2^{|\mathcal{X}|-1}\sum{\text{x}\in\mathcal{X}-X} P ( \text{x} ) 1
\end{aligned}
$$

• 注 1: NFL 定理的重要前提，所有「问题」出现的机会相同 或者 所有问题同等重要
• 注 2: NFL 定理说明，脱离具体问题，空谈「算法的好坏」毫无意义。

1.5 发展历程

• 20 世纪 50~70 年代，人工智能研究处于「推理期」，即赋予机器逻辑推理能力，代表工作：逻辑理论家程序和通用问题求解程序
• 20 世纪 50 年代，基于神经网络的「连接主义」，代表工作：感知机
• 20 世纪 60~70 年代，基于逻辑表示的「符号语义」，代表工作：结构学习系统、基于逻辑的归纳学习系统、概念学习系统
• 20 世纪 90 年代，统计学习理论
• 归纳学习：从样例中学习，即从训练样例中归纳出学习结果，涵盖了监督学习和非监督学习等。
• 20 世纪 80 年代，从样例中学习的主流是符号语义学习，代表工作：决策树和基于逻辑的学习
  • 决策树以信息论为基础，以信息熵为最小化目标，模拟了人类对概念进行判定的树形流程
  • 基于逻辑的学习是归纳逻辑程序设计 ( Inductive Logic Programming, ILP )，是机器学习和逻辑程序设计的交叉，使用一阶逻辑 ( 即谓词逻辑 ) 来进行知识表示，通过修改和扩充逻辑表达式来完成对数据的归纳。ILP 不仅可以利用领域知识辅助学习，还可以通过学习对领域知识进行精化和增强；因为表示能力太强，导致学习过程面临的假设空间太大、复杂度极高，当问题规模过大后就难以进行有效学习
• 20 世纪 90 年代，从样例中学习的主流是连接主义学习，BP 算法使得应用非常广泛；局限是其「试错性」，即学习过程涉及大量参数，参数的设置缺乏理论指导。
• 20 世纪 90 年代，统计学习的代表性技术是支持向量机 ( Support Vector Machine, SVM ) 和核方法 ( Kernel Methods )。
• 21 世纪，深度学习，狭义地说就是「很多层」的神经网络。

1.6 应用现状

• 2012 年，美国启动「大数据研究与发展计划」，三大关键技术：机器学习、云计算、众包 ( crowdsourcing )
• 数据挖掘是从海量数据中发掘知识。数据库为数据挖掘提供数据管理技术，机器学习和统计学为数据挖掘提供数据分析技术。
• 机器学习可以促进理解「人类如何学习」

1.7 阅读材料

• 第一本机器学习教材。[^Mitchell,1997]
• 入门读物。[^Duda,2001]
• 进阶读物。[^Hastie,2009]
• 贝叶斯进阶读物。[^Bishop,2006]