绪论

1. 基本术语

假设有一组关于西瓜的数据，记录成如下一个表格：

瓜瓜	色泽	根蒂	敲声
瓜1	青绿	蜷缩	浊响
瓜2	乌黑	稍蜷	沉闷
瓜3	浅白	硬挺	清脆
...	...	...	...

数据集：这组记录的继承称为一个\textcolor{red}{数据集}（data set），这个表格就是一个数据集。

样本：其中每一行即对每一个西瓜的描述，称为一个示例或样本（sample），这里面的“瓜1、瓜2、瓜3”就是3个样本。

属性：反映时间或对象在某方面的表现或性质的事项，称为属性（attribute）或特征（feature），这里面的“色泽、根蒂、敲声”就是特征。而属性对应的值，称为属性值（attribute value），这里面的“浅白、硬挺、沉闷”等就是属性值。

样本空间：由属性张成的空间称为样本空间（sample space）、属性空间（attribute space）或输入空间。例如，可以将西瓜的三个属性“色泽、根蒂、敲声”张成一个描述西瓜特征的三维空间，这个空间就是样本空间。因此，这个空间中每个点都对应一个西瓜。因此我们也可以把一个样本称为一个特征向量（feature vector）。

维数：通常用D = {x_1,x_2,...,x_m}来表示包含m个样本的数据集，其中每个样本由d个属性描述，即x_i=x_{i1};x_{2};...;x_{id}是d维样本空间\chi 中的一个向量。这里面的x_{ij}表示第i个样本的第个j属性对应的值，例如x_{23}表示第2个西瓜的第3个属性值，即“沉闷”。d称为样本x_i的维数（dimensionality）。

训练集：用于训练模型的样本集合称为训练集（training set）。

假设：事先假定的数据集潜在的某种规律，称为假设（hypothesis）。

标记：每个样本对应的结果称为标记（label）。例如，根据瓜1的属性，我们判断它是一个“好瓜”或“坏瓜”，这个“好瓜、坏瓜”就是这个样本的标记。如果一个样本带有属性和标记，那么这个样本叫做样例（example），但通常也称为样本。一般用(x_i,y_i)表示第i个样例，其中y_i∈У$是所有标记的集合，称为标记空间或输出空间。

若预测的标记是离散的，称为一个分类（classification）任务；若标记是连续的，称为一个回归（regression）任务。预测结果只涉及两个类别的，称为二分类（binary classification），其中一个称正类（positive class），另一个称反类（negative class）。对于多个类别的，称多分类（multi-class classification。）

测试集：用于测试模型的样本称为测试样本（training set）。

监督学习：带有标记的训练样本学习的过程称为监督学习（supervised learning）。分类和回归通常是监督学习。

无监督学习：没有带标记的训练样本学习的过程称为无监督学习（unsupervised learning）。聚类是无监督学习。

泛化能力：学得的模型适用于新样本的能力，称为泛化（generalization）能力。通常希望学习的模型有较强的泛化能力，以在新的数据集上表现良好。通常假设样本空间服从某个未知的分布，且我们获得的每个样本都是独立同分布（independent and identically distributed）的，这样的话，训练样本越多，习得的模型泛化能力越强。

2. 归纳偏好

通过学习得到的模型对应了假设空间中的一个假设，一个具体的学习算法会得到一个具体的模型，不同的模型对同一个训练集会产生不同的结果，即学习算法本身具有自己的“偏好”。若算法喜欢尽可能特殊的模型，那它对样本的适用情况尽可能少；若算法喜欢尽可能一般的模型，那它对样本的适用情况尽可能多。这种对某种类型假设的偏好，称为归纳偏好（inductive bias）或偏好。

在实际应用中，某个算法必须有自己的偏好，否则这个算法预测的结果完全是随机的，失去了预测的意义。

对于下面这个图示，黑点是训练样本集合，曲线A和曲线B均全部经过了黑点，代表有两种偏好的算法。

Pic1.png

曲线A和曲线B对应的两种算法，哪儿一个才是“正确的偏好”呢？一个常用的原则是奥卡姆剃刀（Occam's razor）：若有多个假设与观察一致，则选最简单的那个。由此原则，曲线A更易描述，显然更好。

但是实际上，并非总是适用此种原则，例如下图（黑点是训练样本，白点是测试样本）：

Pic2.png

显然第二种情况曲线B对应的算法对测试样本表现良好，明显优于曲线A。因此，若某个算法在某些方面优于另一个算法，那么它在其他方面肯定逊色于另一种算法。根据没有免费的午餐（NFL）理论，所有的问题出现机会相同，所有问题同等重要，因此任何学习算法的期望学习性能都相同。但在实际应用中，我们只关心要解决的问题，为达到这样的目的寻找最合适的方案，至于这个方案对其他问题好坏我们不关心。因此，脱离具体的问题，算法的优劣就无从谈起，最合适的才是最好的。

模型评估与选择

1. 经验误差与过拟合

错误率：分类错误的样本数占样本总数的比例，称为错误率（error rate）。若个m样本中，有个a样本分类错误，则错误率E=a/m。

精度：1-错误率。

误差：学习器在训练集上的误差与样本真是输出之间的差异称为误差（error）。学习器在训练集上的误差称为训练误差（training error）或经验误差（empirical error）。在新样本上的误差称为泛化误差（generalization error）。

过拟合：由于学习器学习能力过好，把训练样本中的一些特点（或噪点）当成所有潜在样本都具有的普遍规律也学习了进去，在成在训练集上表现很好但在测试集上表现较差，体现出泛化能力的降低，称为过拟合（overfitting）。

欠拟合：与过拟合相反，对样本的普遍规律学习不全，导致泛化能力较低，称为欠拟合（underfitting）。通常欠拟合较易处理而过拟合较为困难。

2. 评估方法

对于一个数据集D={(x_1,y_1),(x_2,y_2),...,(x_m,y_m)}，我们可以分出训练集S和测试集T。

2.1 留出法

留出法：直接将数据集D划分为互斥的两个集合，一个作为训练集S，另一个作为测试集T，两者互相不包含相同的样本。例如一个二分类任务：假设数据集D包含1000个样本，其中训练集S包含700个样本，测试集T包含300个样本。用S训练后，在T上有90个分类错误，那么错误率E=(90/300)=30%，相应的精度为70%。

需要注意的是，留出法的数据集分配需要采样分层抽样，以保证训练集和测试集和数据集类别比例相同。

留出法有个缺点：若训练集S包含绝大多数样本，那么训练处的模型更接近用数据集D训练出的模型，由于测试集T比较小，导致评估结果不够稳定准确。若测试集T数据较多，则用S训练的模型与D差别可能会很大，降低了评估结果的保真性。通常采用2/3至4/5的样本用于训练。

2.2 交叉验证

交叉验证：先将数据集D划分为k个大小相似的互斥子集，通过分层抽样保证每个子集与整体呈现相同的分布。每次用k-1个子集作为训练集，余下的那个用作测试集。这样就能得到k组训练集/测试集，进而进行k次训练，将每次训练结果取平均值，即是返回的结果。

交叉验证法的评估结果的稳定性和保真性在很大程度上取决于k的取值，通常把交叉验证法称为k折交叉验证。最常用的取值是10。

下面是一个10折交叉验证的示意图：

Pic3.png

为减小因样本划分不同而引入的误差，k折交叉验证通常要随机使用不同的划分重复进行多次，最终取平均值。常见的有10次10折交叉验证，共进行了100次的训练/测试。

2.3 自助法

上面两种方法都需要将数据集一分为二，用于训练的样本数少于数据集，会因此引入估计偏差，而自助法则不同。

自助法：随机从包含m个样本的数据集D中选取一个样本，将其拷贝至数据集D^{‘后，再放回数据集D内（有放回抽样）；重复这个过程m次，就得到了包含m个样本的数据集D}‘。这样有一部分样本会在中D^‘重复出现而一部分样本根本不会被抽中。再一次抽样中，任一样本被抽中的概率为1/m。根据极限：

$\lim_{x\rightarrow\infty}{(1-\frac{1}{m})^m=\frac{1}{e}≈36.8\%}$

因此，当较大时，会有三分之一的样本未被抽中。我们利用D^{‘作为训练集，而D\D}‘作为测试集。这种方法称为包外估计（out-of-bag estimate）。

自助法在数据集较小、难以有效划分训练/测试集时很有用，此外它能从初始数据集中产生多个不同的训练集，对集成学习很有用。但它改变了初始数据集的分布，会引入估计偏差。

3. 性能度量

性能度量：衡量模型泛化能力的标准。

对于数据集集D={(x_1,y_1),(x_2,y_2),...,(x_m,y_m)}，评估学习器f的性能，就是把学习器预测结果f(x)与真实标记y进行比较。

回归任务中最常用的指标是均方误差（mean squared error）。

对于离散型数据：

$E(f;D)=\frac{1}{m}\sum_{i=1}^{m}{(f(x_i)-y_i)^2}$
对于连续型数据：

$E(f;D)=\int_{x~D}{(f(x)-y)^2}p(x)dx$

3.1 错误率与精准率

根据之前的定义，错误率和精度分别表示为：

对于离散型数据：

$E(f;D)=\frac{1}{m}\sum_{i=1}^{m}Ⅱ{(f(x_i)≠y_i)}$

$acc(f;D)=\frac{1}{m}\sum_{i=1}^{m}Ⅱ{(f(x_i)=y_i)}=1-E(f;D)$

对于连续型数据：

$E(f;D)=\int_{x~D}Ⅱ{(f(x)≠y)}p(x)dx$

$acc(f;D)=\int_{x \widetilde{} D}Ⅱ{(f(x)=y)}p(x)dx=1-E(f;D)$

3.2 查准率、查全率与F1

根据分类结果，建立混淆矩阵：

实际情况	预测结果	预测结果
	正例	反例
正例	TP（真正例）	FN（假反例）
反例	FP（假正例）	TN（真反例）

查准率P定义为：

$P=\frac{TP}{TP+FP}$

查全率Q定义为：

$Q=\frac{TP}{TP+FN}$

从定义可以看出：查准率P指的是在所有预测为正类的数量中，预测正确的比例。查全率Q指的是样本所有正类中被正确预测的数量的比例。通常来说，查准率与查全率是一对矛盾的度量，一个高的同时，另一个就会低。

从极端的情况来看：假设有100个样本，其中60个正例及40个反例。

将所有样本均分为正例，此时TP=60，FP=40，FN=0，即P=60%，Q=100%；
从100个样本中，挑出20个肯定是正例的样本，其余均分为反例，此时TP=20，FP=0，FN=40，即P=100%，Q=33.3%；

以查准率为纵轴，查全率为横轴作图，得到“查准率-查全率”曲线，称为“P-R曲线”，显示该曲线的图称为“P-R图”：

Pic4.png

一个P-R曲线完全包住另一个P-R曲线，则前者性能优于后者；当两条P-R曲线有交叉时，一般来说，曲线与坐标轴围成的面积更大的性能更好一点，但也要看具体的问题。

除此之外，还有其他的性能度量：

平衡点：是查全率=查准率时的取值。例如上图中，A曲线平衡点大于B曲线，可以认为A的性能更好一点。
F1度量：

$F1=\frac{2\times P \times R}{P+R}=\frac{2\times TP}{样例总数+TP-FN}$

在不同的任务中，对查准率和查全率有不同的重视程度，F_\beta表示查准率/查全率的不同偏好：

$F_\beta=\frac{(1+\beta^2)\times P \times R}{(\beta^2\times P)+R}, \beta>0$

当\beta=1时，F_\beta就是F1；当\beta>1时,查全率有更大的影响；当\beta<1时，查准率有更大的影响。

当有n个二分类混淆矩阵时，综合考察查准率和查全率：

在各混淆矩阵上计算出查准率和查全率，然后求平均值，得到宏查准率、宏查全率和宏F1：

$macro-P=\frac{1}{n}\sum_{i=1}^{n}{P_i}$

$macro-R=\frac{1}{n}\sum_{i=1}^{n}{R_i}$

$macro-F1=\frac{2\times macro-P \times macro-R}{macro-P+macro-R}$
先将各混淆矩阵对应的元素进行平均，再求微查准率、微查全率和微F1：

$micro-P=\frac{\overline{TP}}{\overline{TP}+\overline{FP}}$

$micro-R=\frac{\overline{TP}}{\overline{TP}+\overline{FN}}$

$micro-F1=\frac{2\times micro-P \times micro-R}{micro-P+micro-R}$