【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.机器学习的定义
首先，我们先来看一下机器学习的定义。机器学习的定义有很多，这里列出了比较常见的一个定义。
机器学习的定义：假设用P来评估计算机程序在某任务类T上的性能，若一个程序通过利用经验E在T中任务上获得了性能改善，则我们就说关于T和P，该程序对E进行了学习。
2.机器学习的基本术语
我们结合一个西瓜数据集来帮助理解这些术语：
| 编号 | 色泽 | 根蒂 | 敲声 | 好瓜 |
|---|---|---|---|---|
| 1 | 青绿 | 蜷缩 | 浊响 | 是 |
| 2 | 乌黑 | 蜷缩 | 浊响 | 是 |
| 3 | 青绿 | 硬挺 | 清脆 | 否 |
| 4 | 乌黑 | 稍蜷 | 沉闷 | 否 |
- 数据集(data set):记录的集合。例如上表就是一个数据集。
- 示例(instance)或样本(sample)：每条记录（即关于对象的描述）。
- 属性(attribute)或特征(feature)：上表中有三个属性（特征），即色泽、根蒂和敲声。
- 属性值(attribute value)：每个属性的取值即为属性值。诸如青绿、乌黑等等。
- 属性空间(attribute space)或样本空间(sample space)或输入空间：属性张成的空间。大家可以这样理解：如果每个样本（示例）有3个属性（特征），x轴表示属性1，y轴表示属性2，z轴表示属性3，坐标轴上的值代表属性值，则每个样本（示例）都会对应三维空间的一个点，每个点其实可以理解为一个向量，因此，也把一个样本（示例）称为一个“特征向量”。样本空间的计算：例如有20个属性，每个属性有10个可能取值，则样本空间的规模为$10^{20}$。
- 维数：一般地，令$D=\lbrace x_1,x_2,…,x_m \rbrace$表示包含m个示例的数据集，每个示例有d个属性。则每个示例$x_i=(x_{i1};x_{i2};…;x_{id})$是d维样本空间中的一个向量，d称为样本$x_i$的维数。
- 样例(example)：拥有了标记(label)信息的示例，称为样例。用$(x_i,y_i)$表示第i个样例，其中$y_i\in Y$。Y是所有标记的集合，亦称“标记空间”(label space)或“输出空间”。上表中1-4行，每行都是一个样例。如果没有label，则每一行都是一个样本（示例）。
- 分类模型：预测值为离散值（如二分类、多分类等）。
- 回归模型：预测值为连续值。
- 有监督学习（亦称有导师学习）：👉详细介绍。
- 无监督学习（亦称无导师学习）：👉详细介绍。
- 泛化能力（generalization）:学得模型适用于新样本的能力，称为泛化能力。
- 独立同分布：假设样本空间中全部样本服从一个未知“分布”D，我们获得的每个样本都是独立地从这个分布上采样获得的，即“独立同分布”。
- 归纳（induction）与演绎(deduction):是科学推理的两大基本手段。归纳：从特殊到一般的泛化过程。演绎：从一般到特殊的特化过程。
3.假设空间
机器学习中的学习指的就是从样本中学习的过程，可以看作一个在所有假设组成的空间中进行搜索的过程，搜索目标是找到与训练集“匹配”的假设。
例如，我们有一个西瓜数据集，西瓜分为好瓜，坏瓜两种，每个样本有3个属性：色泽、根蒂、敲声。3个属性分别有3,2,2种可能的取值。
我们的目的是根据这些特征，判断一个瓜是否是好瓜（这是一个典型的二分类问题，在这里，我们假设正例=“好瓜”）。
我们先来看一下怎么构建假设空间。以“色泽”属性为例，该属性有3个属性值，简化记为$\lbrace a,b,c \rbrace$,则集合$\lbrace a,b,c \rbrace$的非空子集即为根蒂属性在假设空间的取值情况，为$\lbrace a \rbrace$,$\lbrace b \rbrace$,$\lbrace c \rbrace$,$\lbrace a,b \rbrace$,$\lbrace a,c \rbrace$,$\lbrace b,c \rbrace$,$\lbrace a,b,c \rbrace$，共7种，若不考虑$\lbrace a,b \rbrace$,$\lbrace a,c \rbrace$,$\lbrace b,c \rbrace$的情况，还剩4种取值，即$\lbrace a \rbrace$,$\lbrace b \rbrace$,$\lbrace c \rbrace$,$\lbrace a,b,c \rbrace$。其中，$\lbrace a,b,c \rbrace$指的是无论色泽取哪个值，结局都是好瓜，可以用通配符*表示。此外，还有一种特殊情况，就是“好瓜”这个概念根本就不存在，不管各个属性如何取值，结果一直都不是好瓜。因此，假设空间的规模为：$(3+1)(2+1)(2+1)+1=37$。
然后我们对假设空间进行搜索，搜索过程中不断删除与正例不一致的假设，和（或）与反例一致的假设。最终将会获得与训练集一致（即对所有训练样本能够进行正确判断）的假设。
与训练集一致的“假设集合”，称之为“版本空间”。
4.归纳偏好
但是“版本空间”中可能存在等效假设，所以需要归纳偏好来解决这个问题。
针对等效假设举个例子，如果在版本空间中存在这样两个假设：
- 假设1:若满足色泽=*，根蒂=蜷缩，敲声=*，则判定为好瓜，否则为坏瓜。
- 假设2:若满足色泽=*，根蒂=蜷缩，敲声=清脆，则判定为好瓜，否则为坏瓜。
若测试集有一条记录为色泽=青绿，根蒂=蜷缩，敲声=沉闷，同时符合假设1和假设2的条件，但是按照假设1，则判定为好瓜，按照假设2，则判定为坏瓜，此时便存在等效假设现象，需要“归纳偏好”来解决这个问题。
任何一个有效的机器学习算法必有其归纳偏好，否则它将被假设空间中看似在训练集上“等效”的假设所迷惑，每次结果可能都不一样。
归纳偏好举例：“奥卡姆剃刀”原则，即“若有多个假设与观察一致，则选最简单的那个”。但是“奥卡姆剃刀”原则的缺点也很明显，有时候无法判断哪个假设更简单。
“没有免费的午餐”定理（No Free Lunch Theorem,NFL）：
重要前提：所有“问题”出现的机会相同，或所有问题同等重要。
- 算法A：聪明的算法
- 算法B：随机胡猜的笨拙算法
可以得到这样一个结论：算法A和算法B的期望性能一样，产生的总误差与算法无关。所以，算法无优劣之分（包括随机胡猜），但是针对特定的某一具体问题，才会有优劣之分。同一算法在不同问题中表现也不尽相同。
