机器学习笔记(学习中 进度堪忧)

第1章 绪论

1.1 引言

通过对经验的利用，就能对新情况做出有效的决策。计算机在这方面可以帮忙。

机器学习致力于研究如何通过计算的手段，利用经验来改善系统自身的性能。机器学习所研究的主要内容，是关于在计算机上从数据中产生“模型”(model)的算法，即"学习算法"(learning algorithm).

1.2 基本术语

一组记录的集合称为一个“数据集”(data set),其中每条记录是关于一个事件或对象的描述，称为一个“示例”(instance)或"样本"(sample)

反映事件或对象在某方面的表现或性质的事项称为"属性"(attribute)或"特征"(feature).属性上的取值称为"属性值"(attribute value).属性张成的空间称为"属性空间"(attribute space)、“样本空间”(sample space)或"输入空间".我们也把一个示例称为一个"特征向量"(feature vector).

每个示例由d个属性描述,d称为样本的"维数"(dimensionality).

从数据中学得模型的过程称为"学习"(learning)或"训练"(training)

训练中使用的数据称为"训练数据"(training data),其中每个样本称为一个"训练样本"(training sample),训练样本组成的集合称为"训练集"(training set)

学得模型对应了关于数据的某种潜在的规律，因此亦称"假设"(hypothesis);这种潜在规律自身，则称为"真相"或"真实"(ground-truth).有时将模型称为"学习器"(learner),可以看作学习算法在给定数据和参数空间上的实例化.

标记(label);拥有了标记信息的示例,则称为"样例"(example).所有标记的集合称为"标记空间"(label space)或"输出空间".

(xi,yi)表示第i个样例,xi是d维向量.

若欲预测的是离散值，此类学习任务称为"分类"(classification);若欲预测的是连续值,此类学习任务称为"回归"(regression).

对于只涉及两个类别的“二分类”(binary classification)任务，通常称其中一个类为"正类"(positive class),另一个类为"反类"(negative class)；涉及多个类别时,则称为“多分类”(multi-class classification)任务。

学得模型后，使用其进行预测的过程称为“测试”(testing),被预测的样本称为"测试样本"(testing sample) .

聚类(clustering),即将训练中的示例分成若干组，每组称为一个"簇"(cluster);这些自动形成的簇可能对应一些潜在的概念划分.这样的学习过程有助于我们了解数据内在的规律，能为更深入地分析数据建立基础.

根据训练数据是否拥有标记信息，学习任务可大致划分为两大类:“监督学习”(supervised learning)和"无监督学习"(unsupervised learning),分类和回归是前者的代表,而聚类则是后者的代表.

机器学习的目标是使学得的模型能更好地适用于"新样本"，而不是仅仅在训练样本上工作得好.学得模型适用于新样本的能力,称为"泛化"(generalization)能力.

通常假设样本空间中全体样本服从一个未知"分布"(distribution)D,我们获得的每个样本都是独立地从这个分布上采样获得的,即"独立同分布"(independent and identically distributed,简称i.i.d)

1.3 假设空间

归纳(induction)和演绎(deduction)科学推理的两大基本手段

归纳学习(inductive learning).狭义的归纳学习要求从训练数据中学得概念(concept),亦称为"概念学习"或"概念形成".概念学习技术目前研究、应用都比较少，因为要学得泛化性能好且语义明确的概念实在太困难了,现实常用的技术大多是产生"黑箱"模型。

概念学习中最基本的是布尔概念学习.

“记住"训练样本，就是所谓的"机械学习”.

我们可以把学习过程看作一个在所有假设(hypothesis)组成的空间中进行搜索的过程,搜索目标是找到与训练集"匹配"(fit)的假设.现实问题中我们常面临很大的假设空间,但学习过程是基于有限样本训练集进行的,因此，可能有多个假设与训练集一致,即存在着一个与训练集一致的"假设集合",我们称之为"版本空间"(version space)

1.4 归纳偏好

当有多个模型(假设)时，应该采纳哪一个.这时,学习算法本身的"偏好"就会起到关键的作用.

机器学习算法在学习过程中对某种类型假设的偏好,称为"归纳偏好"(inductive bias),或简称为"偏好".

任何一个有效的机器学习算法必有其归纳偏好.

归纳偏好可看作学习算法自身在一个很庞大的假设空间中对假设进行选择的启发式或"价值观".“奥卡姆剃刀”(Occam’s razor)是一种常用的、自然科学研究中最基本的原则，即“若有多个假设与观察一致，则选最简单的那个”

算法的归纳偏好是否与问题本身匹配，大多数时候直接决定了算法能否取得好的性能.

对于一个学习算法A,若它在某些问题上比学习算法B好,则必然存在另一些问题,在那里B比A好.这个结论对任何算法均成立.证明待看

NFL定理(No Free Lunch Theorem)[Wolpert,1996;Wolpert and Macready,1995]

NFL的最重要寓意，是让我们清楚地认识到,脱离具体问题,空泛地谈论"什么学习算法更好"毫无意义。学习算法自身的归纳偏好与问题是否相配,往往会起到决定性的作用.

1.5 发展历程

二十世纪五十年代到七十年代初,人工智能研究处于"推理期",那时认为人们只要能赋予机器逻辑推理能力，机器就能具有智能.人们逐渐认识到,仅具有逻辑推理能力是远远实现不了人工智能的.后来认为，要使机器具有智能，就必须设法使机器拥有知识.从二十世纪七十年代中期开始,人工智能研究进入了"知识期"。大量专家系统问世。但逐渐的专家系统面临"知识工程瓶颈"，简单地说，就是由人来把知识总结出来再教给计算机是相当困难的.

二十世纪五十年代初已有机器学习的相关研究,五十年代中后期，基于神经网络的"连接主义"(connectionism)学习开始出现。在六七十年代，基于逻辑表示的“符号主义”(symbolism)学习技术蓬勃发展,以决策理论为基础的学习技术以及强化学习技术等也得到发展。

总的来看，二十世纪八十年代是机器学习成为一个独立学科领域、各种机器学习技术百花初绽的时期。

在二十世纪八十年代，“从样例中学习”的一大主流是符号主义学习，其代表包括决策树(decision tree)和基于逻辑的学习.典型的决策树学习以信息论为基础，以信息熵的最小化为目标，直接模拟了人类对概念进行判定的树形流程.决策树学习技术由于简单易用,到今天仍是最常用的机器学习技术之一.

BP一直是被应用得最广泛的机器学习算法之一.连接主义学习的最大局限是其"试错性"

二十世纪九十年代中期,“统计学习”(statistical learning)闪亮登场并迅速占据主流舞台,代表性技术是支持向量机(Support Vector Machine,简称SVM)以及更一般的“核方法”(kernel methods).在支持向量机被普遍接受后,核技巧被人们用到了机器学习的几乎每一个角落，核方法(kernel trick)也逐渐成为机器学习的基本内容之一.

二十一世纪初,连接主义又卷土重来,掀起了以"深度学习"为名的热潮.所谓深度学习，狭义地说就是"很多层"的神经网络.

1.6 应用现状

第二章 模型评估与选择

2.1 经验误差与过拟合

“错误率”(error rate)：分类错误的样本数占样本总数的比例.

“精度”(accuracy)：精度 = 1-错误率

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

“训练误差”(training error)或"经验误差"(empirical error):学习器在训练集上的误差

“泛化误差”(generalization error)：学习器在新样本上的误差

我们希望得到泛化误差小的学习器.然而，我们事先并不知道新样本是什么样的,实际能做的是努力使经验误差最小化.

“过拟合”(overfitting):当学习器把训练样本学得"太好"了的时候,很可能已经把训练样本本身的一些特点当做了所有潜在样本都会具有的一般性质,这样就会导致泛化性能下降.

“欠拟合”(underfitting):指对训练样本的一般性质尚未学好。

欠拟合比较容易克服,例如在决策树学习中扩展分支、在神经网络学习中增加训练轮数等

过拟合是机器学习面临的关键障碍,过拟合是无法彻底避免的,我们所能做的只是"缓解".只要相信P $\not=$ NP,过拟合就不可避免.

机器学习中的"模型选择"(model selection)问题,如何进行模型评估与选择呢？

疑惑：这里的评估是对学习算法在这特定问题上表现的评估吧？

2.2 评估方法

通常，我们可通过实验测试来对学习器的泛化误差进行评估并进而做出选择.为此，需使用一个“测试集”(testing set)来测试学习器对新样本的判别能力,然后以测试集上的“测试误差"(testing error)作为泛化误差的近似.测试集应该尽可能与训练集互斥.

有限的数据集,如何产生训练集S和测试集T.下面是几种常见的做法

2.2.1 留出法(hold-out)

直接将数据集D划分为两个互斥的集合。

训练/测试集的划分要尽可能保持数据分布的一致性,避免因数据划分过程中中引入额外的偏差而对最终结果产生影响.“分层采样”(stratified sampling).

单次使用留出法得到的估计结果往往不够稳定可靠,在使用留出法时,一般要采用若干次随机划分、重复进行试验评估后取平均值作为留出法的评估结果.

保真性(fidelity),划分比例过大或过小导致的问题没有完美的解决方案,常见做法是将大约2/3~4/5的样本用于训练，剩余样本用于测试.

2.2.2 交叉验证法(cross validation)

将数据集D划分为k个子集,保证每个子集数据分布的一致性(可以通过分层采样).每次用k-1个子集训练，剩下的一个做测试集。这样可以得到k组.最后返回k个测试结果的均值.

这种方法的稳定性和保真性在很大程度上取决于k的取值，通常把这种方法称为"k折交叉验证"(k-fold cross validation).通常k取10

把数据集D划分为k个子集存在多种方式,所以为了减小划分不同引入的误差,通常要随机使用不同的划分重复p次,最终的评估结果是这p次k折交叉验证结果的均值.

假定数据集D中包含m个样本,若令k=m，则得到了交叉验证法的一个特例:留一法(Leave-One-Out,简称LOO)。显然，留一法不受随机样本划分方式的影响.留一法的评估结果往往被认为比较准确.留一法也有缺陷:在数据集比较大时，训练m个模型的计算开销可能是难以忍受的.而且这还是在未考虑算法调参的情况下.留一法的估计结果也未必永远比其他评估方法准确.

“没有免费午餐"定理对实验评估方法同样适用。

2.2.3 自助法(bootstrapping)=可重复采样

有没有什么办法可以减少训练样本规模不同造成的影响,同时还能比较高效地进行实验估计呢？

”自助法“是一个比较好的解决方案,它直接以自助采样法(bootstrap sampling)为基础.就是相当于摸小球放回知道摸的次数与小球数相等。

样本在m次采样中始终不被采到的概率是 $(1-\frac{1}{m})^m$，取极限为 $\frac{1}{e} \approx 0.368$ ,将未被抽中的作为测试集。这样的测试结果，亦称"包外估计”(out-of-bag estimate).

自助法在数据集较小、难以有效划分训练/测试集时很有用；此时，自助法能从初始数据集中产生多个不同训练集,这对集成学习等学习方法有很大的好处。然而，自助法产生的数据集改变了初始数据集的分布，会引入估计偏差.因此在初始数据量足够时，留出法和交叉验证法更常用一些.

2.2.4 调参(parameter tuning)与最终模型

参数可能在实数范围内取值，有着极大的调参工作量,以至于在不少应用任务中,参数调的好不好往往对最终模型性能有关键性影响。

模型选择完成后，学习算法和参数配置已选定,此时应该用数据集D重新训练模型.这才是我们最终提交给用户的模型.

验证集(validation set)存疑

2.3 性能度量

需要有衡量模型泛化能力的评价标准,这就是性能度量(performance measure).面对不同的任务需求，选用不同的性能度量。

回归任务最常用的性能度量是"均方误差"(mean squared error) 公式待补

下面主要介绍分类任务中常用的性能度量.

2.3.1 错误率与精度

这是分类任务中最常用的两种性能度量，既适用于二分类任务，也适用于多分类任务 公式待补

2.3.2 查准率(precision)、查全率(recall)与F1

对于二分类问题,可将样例根据其真实类别与学习器预测类别的组合划分为真正例(true positive,TP)、假正例(false positive,FP)、真反例(true negative,TN)、假反例(false negative,FN)四种情形。 分类结果的"混淆矩阵"(confusion matrix)

真实情况	预测结果	预测结果
真实情况	正例	反例
正例	TP(真正例)	FN(假反例)
反例	FP(假正例)	TN(真反例)

查准率P与查全率R分别定义为: $$ P=\frac{TP}{TP+FP} $$

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

查准率和查全率是一对矛盾的度量.一般来说，查准率高时，查全率往往偏低;反之类似.

查准率-查全率曲线,简称”P-R曲线“，显示该曲线的图称为”P-R图“.

若一个学习器的P-R曲线被另一个学习器的曲线完全"包住"，则可断言后者的性能优于前者.

若两个学习器的P-R曲线发生了交叉,则一般难以一般性地断言两者孰优孰劣,只能在具体的查准率或查全率条件下进行比较.仍希望比个高低,这时一个比较合理的判据是比较P-R曲线下面积的大小。

人们设计了一些综合考察查准率、查全率的性能度量.

”平衡点“(Break-Even Point,简称BEP)就是这样一个度量,它是”查准率=查全率“时的取值

但BEP还是过于简化了些，更常用的是F1度量:

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

F1是基于查准率与查全率的调和平均(harmonic mean)定义的

F1的一般形式是$F_{\beta}$，能让我们表达出对查准率/查全率的不同偏好,$F_{\beta}$是加权调和平均.

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

其中$\beta >0$度量了查全率对查准率的相对重要性.$\beta = 1$时退化为标准的F1;$\beta >1$时查全率有更大影响；$\beta <1$时查准率有更大影响

我们希望在n个二分类混淆矩阵上综合考察查准率和查全率.

一种直接的做法是先在各混淆矩阵上分别计算出查准率和查全率，然后计算平均值,这样就得到"宏查准率"(macro-P)、“宏查全率”(macro-R),以及相应的"宏F1"(macro-F1):

还有一种:先将各混淆矩阵的对应的元素进行平均,再基于这些平均值计算出"微查准率"(micro-P)、“微查全率”(micro-R)和"微F1"(micro-F1)

2.3.3 ROC与AUC

分类阈值(threshold) 截断点(cut point)

排序本身的质量好坏,体现了综合考虑学习器在不同任务下的"期望泛化性能"的好坏，或者说，”一般情况下“泛化性能的好坏，ROC曲线则是从这个角度出发来研究学习器泛化性能的有力工具.

ROC全称是”受试者工作特征“(Receiver Operating Characteristic)曲线

ROC曲线的纵轴是”真正例率“(True Positive Rate,简称"TPR"),横轴是"假正例率"(False Positive Rate,简称FPR)

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

$$FPR = \frac{FP}{TN+FP}$$

两条ROC曲线的比较类似于P-R曲线类似. ROC曲线下的面积,即AUC(Area Under ROC Curve)

公式待补

排序"损失"(loss)的定义为: 公式待补

$l_{rank}$对应的是ROC曲线之上的面积,AUC = 1-$l_{rank}$

2.3.4 代价敏感错误率与代价曲线

为权衡不同类型错误所造成的不同损失，可为错误赋予"非均等代价"(unequal cost).