一. 绪论
1.1 引言
- 在计算机系统中，经验通常以数据的形式存在，因此，机器学习所研究的主要内容是关于计算机从数据中产生的模型的算法，即“学习算法”。
1.2 基本术语
现在收集到西瓜的数据
\[表\quad1-1\quad西瓜数据集 \]| 编号 | 色泽 | 根茎 | 敲声 |
|---|---|---|---|
| 1 | 青绿 | 蜷缩 | 浊响 |
| 2 | 乌黑 | 稍蜷 | 沉闷 |
| 3 | 青绿 | 硬挺 | 清脆 |
- 示例/样本：每一条记录都是一个样本。
- 属性/特征：反应事件或对象在某方面的表现或性质的事项，如”色泽“、“根茎”、“敲声“。
- 属性值：属性的取值。如”乌黑”
- 属性空间/样本空间/输入控件：属性张成的空间。
- 特征向量：一个示例被称为一个特征向量。
- 训练集：训练过程中使用的数据。
- 训练样本：训练集中的每一个样本。
- 假设：学得模型对用了关于数据的某种潜在的规律，因此也称为“假设”。
- 真实/真相：数据中存在的潜在规律自身。
- 学习器：有时将模型称为学习器，因为学习过程就是为了找出或逼近真相。
- 样例：为每一条示例添加相关标记，例如是否是好瓜。
- 标记空间/输出空间：标记组成的空间。
- 预测类型：
- 回归问题
- 分类问题：
- 二分类
- 多分类
- 测试样本：对学得模型进行测试，被预测的样本是测试样本。
- 聚类：对训练集的西瓜分为若干组，每一组称为一个“簇”，这些自动形成的簇可能存在一些潜在的概念划分。需要注意的是，这些概念事先是不知道的，且学习过程中使用的训练样本通常不具有标记信息。
- 泛化能力：学得的模型适用于“新样本”的能力，具有强泛化能力的模型可以很好的适用于整个样本空间。
- 独立同分布：我们假设样本中的全体样本符合一个未知的分布D，我们取得的每个样本都是独立的从这个分布上采样获得的，这就是独立同分布。
1.3 假设空间
-
假设空间与版本空间：
EG：现有房价数据如下表，要求根据学校数量预测房价：
| 年份 | 学校数量 | 房价 |
|---|---|---|
| 2020 | 1所 | 1万/平方米 |
| 2021 | 2所 | 4万/平方米 |
- 假设空间：我们可以假设一个模型：学校数量和房价成正比，即\(y=kx+b\)。此时假设空间就是该函数，随后采用机器学习可以学的模型：\(y=3x-2\)
- 版本空间：事实上，我们可以假设多个模型。例如:\(y=kx+b\)、\(y=ax^2+bx+c\)……由所有能够拟合训练集的模型构成的集合称为版本空间。
-
科学推理两大手段：
- 归纳：从特殊到一般的泛化。
- 演绎：从一般到特殊的特化，
-
归纳的广义与狭义之分：
- 广义：从样例中学习。
- 狭义：从训练数据中获取概念。（又叫概念学习）但是要学的泛化性能好且语义明确的概念过于困难，现有的技术大多产生于“黑箱”模型。
-
一个简单的概念学习示例：布尔概念学习
-
表\(\quad1-3\quad\)西瓜数据集
编号 色泽 根茎 敲声 好瓜 1 青绿 蜷缩 浊响 是 2 乌黑 蜷缩 浊响 是 3 青绿 硬挺 清脆 否 4 乌黑 稍蜷 沉闷 否 -
色泽有青绿、乌黑、浅白3种取值，根蒂有蜷缩、稍蜷、硬挺3种取值，敲声有浊响、清脆、沉闷3种取值。
那么好瓜的布尔表达式：好瓜 <--> （色泽=？）&& （根茎=？）&& （敲声=？）
-
如何找到正确的布尔表达式？
-
如果直接用第一条数据去填写，我们发现，该模型将会在其余样本上失败。
-
我们可以将学习的过程看作一个在假设空间上搜索的过程，搜索目标是找到与训练集匹配的假设，不匹配的删去。那么，每种属性取值为（这里以色泽为例）：青绿、乌黑、浅白、任何情况都行。那么情况为\((3+1)*(3+1)*(3+1)=64\)种。此外还有一种极端情况：好瓜这个概念根本不存在，可以用空来表示该假设，因此假设空间规模为\(64+1=65\)，有六十五种假设。
-
假设空间图形：
-
如何在假设空间选择：
- 删除与正例（好瓜）不一致的假设
- 删除与反例（坏瓜）一致的假设。
-
版本空间：但是在现实生活中，我们发现在训练集筛选假设空间完毕后，可能得到多个假设与训练集一致，也就是存在一个符合训练集的训练集合，我们称之为假设空间。
-
上述表对应的版本空间为：
色泽＝＊，根蒂＝蜷缩，敲声＝＊
色泽＝＊，根蒂＝＊，敲声＝浊响
色泽＝＊，根蒂＝蜷缩，敲声＝浊响
-
1.4 归纳偏好
-
上述得到的西瓜问题的版本空间给我们带来一个问题：我们需要的只是一个假设用于输出结果，而不是多个假设，否则我们的模型在面临相同的新数据时，有可能产生不同的输出。
-
如何解决版本空间的问题：为算法在学习过程中设置某种类型的偏好，如喜欢尽可能特殊情况的算法模型，那它就会选择好瓜 <--> （色泽=*）&& （根茎=蜷缩）&& （敲声=清脆）
-
版本空间的几何表示：每一个训练样本是图中的一个点，而找到一个与训练集一致的模型，就是要找到一个穿过所有的点的曲线。
我们发现：有多条曲线与有限样本训练集一致，此时就需要偏好来选择使用哪一条曲线。
-
奥卡姆剃刀理论：
- 思想：一种引导算法确立偏好性的原则，即若有多个假设与观察的一致，则选择最简单的一个。
- EG：幂函数，指数越小越简单，就选择简单的一个。
- 缺点：什么是简单？对于西瓜的不同假设，好瓜 <-->（色泽=青绿）&& （根茎=蜷缩）&& （敲声=清脆）；好瓜 <-->（色泽=乌黑）&& （根茎=蜷缩）&& （敲声=清脆），哪一种更简单？这就需要借助其它机制来判断了。因此事实上这一方法并不简单，在实际中更加倾向于使用测试集验证来解决。
- 思想：一种引导算法确立偏好性的原则，即若有多个假设与观察的一致，则选择最简单的一个。
-
那么另一个问题来了：基于不同选择偏好的产生的模型，究竟哪个更好？这里以奥卡姆剃刀原理为偏好原则进行讨论：
让我们看（a）图，可以看到A模型对于未训练的数据泛化能力缺失比B要优秀。但是图（b）呢，难道b的情况不会出现吗？事实上，这是完全有可能的。这也说明：对于一个算法A，若它在某些问题上表现比学习算法B好，那么一定会有一些问题，在哪里B比A要好。这就导出了NFL理论：没有免费的午餐。
-
NFL定理的数学证明：
我们记样本空间为M，假设空间为H。（为了方便，将二者视为离散的）
\(P(h|X,L_a)\)是算法\(L_a\)在训练集X上产生假设h的概率。（可能产生多个假设）
\(f\)：我们所希望得到的真实目标函数。（显然唯一）
那么\(L_a\)的训练集外误差，也就是在M-X外的样本的误差为：
（遍历该算法在样本上可能取到的所有目标函数，遍历样本空间内、训练集外的所有样本，对每一个取到的样本，判断假设\(h(x)=f(x)\)的取值，这里要乘上取得样本x的概率和产生假设h的概率，随后对结果进行累加即可。）
接下来我们以二分类问题为例进行正式求解：
二分类问题中，真实的目标函数可以是任意的\(X\rightarrow{0,1}\)。例如现有训练集\(X={x_1,x_2}\)，那么可能有的目标函数如下：
\[ f_1(x_1)=0,f_1(x_2)=0\\ f_2(x_1)=1,f_2(x_2)=0\\ f_3(x_1)=0,f_3(x_2)=1\\ f_4(x_1)=1,f_4(x_2)=1 \]共有四个可能的目标函数，函数空间为\(\{0,1\}^{|X|}\)，可能的真实目标函数有\(2^{|X|}\)个
我们假设所有可能的f是均匀分布的（具体问题上并非如此，通常我们认为可以高度拟合样本数据的函数才是目标函数），那么我们对所有可能的f按照均匀分布对误差求和，得到：
\[ 公式\quad(1-2) \]
公式（1-2）第二步到第三步：因为无论h(x)对任意样本x取什么值，都会有一半的f(x)取值与其相同。
由公式（1-2）可以证得：总误差与学习算法无关。
-
NFL定理得前提条件：
- 分析：以上计算步骤中可以发现一个条件，那就是假设真实目标函数均匀分布，也就是：所有问题出现的机会相同、或同等重要，但在实际应用中并不是这样。
- 反例：这里以西瓜为例，以NFL的理论，好瓜 <-->（色泽=*）&& （根茎=蜷缩）&& （敲声=浊响）和 好瓜 <-->（色泽=*）&& （根茎=硬挺）&& （敲声=清脆）两个假设应该是一样好的。但是在实际生活中，（根茎=蜷缩）&& （敲声=浊响）得好瓜很常见，但（根茎=硬挺）&& （敲声=清脆）得好瓜不常见，也就是说，目标函数f并不均匀分布。
-
NFL的启示：
-
若考虑所有潜在的问题，则所有算法都一样好。但在实际生活中，我们需要针对具体的问题，选择在某些问题上表现良好的算法。
-
学习算法自身归纳偏好与问题是否相配，往往会起到决定性作用。
-
1.5 发展历程
1.5 1 人工智能历史
- 推理期：
- 时间：二十世纪五十年代到七十年代初。
- 核心思想：认为只要赋予机器逻辑推理能力，机器就能具有智能。
- 典型代表：
- 逻辑理论家程序
- 通用问题求解程序。
- 知识期：
- 时间：二十世纪七十年代中期开始。
- 核心思想：要使得机器具有智能，必须使机器具有知识。
- 典型代表：专家系统。
- 机器学习期：
- 时间：二十世纪九十年代到今天
- 核心思想：由人类总结知识并交给机器极其困难，不如让机器自己掌握知识。
1.5.2 机器学习发展史
- 符号主义：
- 时间：二十世纪八十年代。
- 核心思想：从样例中学习
- 代表：
- 决策树
- 基于逻辑的学习：著名代表是ILP。
- 基于神经网络的连接主义：
- 时间：二十世纪九十年代之前
- 当时的局限性：
- 只能处理线性分类，连“异或”这么简单的问题都解决不了。
- 试错性：学习过程实际大量参数，参数的设置却缺乏理论指导，主要靠手工调参。
- 特点：产生的是黑箱模型，因此从知识获取的角度看，连接主义学习技术有明显的弱点。
- 统计学习：
- 时间：二十世纪九十年代中期。
- 代表技术：
- 支持向量机。
- 核方法。
- 特点：统计学习与连接学习有密切的联系。
- 连接主义卷土重来：
- 时间：进入二十一世纪。
- 特点：
- 数据量大
- 计算能力强：GPU的发明