第一章 概述

机器学习定义和典型应用

机器学习是近20多年兴起的一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。机器学习算法是一类从数据中自动分析获得规律，并利用规律对未知数据进行预测的算法。因为学习算法中涉及了大量的统计学理论，机器学习与统计推断学联系尤为密切，也被称为统计学习理论。

机器学习和人工智能的关系

人工智能是科学，为机器赋予视觉/听觉/触觉/推理等智能。

机器学习是人工智能的计算方法。

深度学习方法和其它人工智能方法的共性和差异

人工智能可大致分为三种学习方法或系统：

基于规则的方法（无可学习的模块，输入的数据直接获取特征然后输出）。
经典的机器学习方法或系统（数据输入后通过手工设计获得的特征，经过特征映射获得输出）。
表示学习方法或系统：

非深度学习方法（特征是通过学习获得，通过特征映射输出）。
深度学习方法（学习得到简单特征，通过附加的层去学习得到更多抽象的特征，再通过特征映射输出结果）。

机器学习和数据挖掘的关系

机器学习是数据挖掘的重要工具。

数据挖掘可以认为是机器学习和数据库技术的交叉学科，数据挖掘利用机器学习技术来分析海量数据，利用数据库技术来管理海量数据。

机器学习和统计学习的关系

计算机视觉是机器学习最重要的应用。

机器学习是统计学习减去模型和假设的检验。

机器学习的发展历程

略。

大数据机器学习的主要特点

与日俱增的数据量。
实验数据量的增加。
与日俱增的神经网络模型规模。
与日俱增的精度、复杂度和对现实世界的冲击。
GPU（Graphic Processing Unit）图形处理单元。
TPU （Tensor Processing Unit）张量处理单元。

测试

以下关于机器学习的基本概念中说法错误的是：

[ ] 机器学习是近20多年兴起的一门多领域交叉学科，涉及概率论、统计学、逼近论、凸 分析、算法复杂度理论等多门学科。
[ ] 人工智能大致分为三种学习方法，即基于规则的方法、经典的机器学习方法、基于表示的学习方法。
[x] 机器学习包括专家系统
[ ] D 数据挖掘可以认为是机器学习和数据库技术的交叉学科，数据挖掘主要利用机器学习来分析数据，利用数据库技术来管理数据。

【解析】专家系统，即按照经验制定的规则来做出决策的系统，并不具备学习能力。而机器学习并无“死板的规定”，而是通过训练数据自主学习对应的模型，从而对于输入做出相应的决策，具备可学习能力。

以下属于大数据机器学习的特征的是：

[ ] 与日俱增的数据量
[ ] 不断增加的网络模型及模型复杂度
[ ] 媲美甚至超越人类认知的准确度
[x] 以上都是

第二章 机器学习基本概念

机器学习的基本术语

数据集 data set：一组记录的集合
示例 instance/样本 sample：关于一个时间或对象的描述
属性 attribute/特征 feature：反映事件或对象在某方面的表现或性质的事项
属性值 attribute value：属性上的取值
属性空间 attribute space/样本空间 sample space：属性张成的空间，即(n)个特征描述出的(n)维空间
特征向量 feature vector：每个示例在空间中的坐标向量
(D={vec{x_1}, vec{x_2}, dots, vec{x_m}})：包含(m)个样本的数据集
(vec{x_i} = (x_{i1}; x_{i2}; dots; x_{id}))：(d)维样本空间(chi)中的一个向量，(x_i in chi)
(x_{ij})：(vec{x_i})在第(j)个属性上的取值，后期可能会用(vec{chi})展示
训练 training/学习 learning：从数据中学得模型的过程
训练数据 training data：训练过程中使用的数据
训练样本 training sample：训练中的每个样本
假设 hypothesis：学习模型对应了关于数据某种潜在的规律
真相/真实 ground-truth：潜在规律自身
学习器 learner：模型
预测 prediction：获得训练样本的“结果”信息
标记 label：样本结果的信息
样例 example：拥有标记信息的样本
输入空间：一个样本所有特征的集合
标记空间 label space/输出空间：所有标记的集合

监督学习

监督学习目的是学习一个由输入到输出的映射，称为模型。

概率模型：条件概率分布(P(Y|X))。
非概率模型：决策函数(Y=f(X))。

训练数据和测试数据被看作是以联合概率分布(P(x, y))独立同分布产生的。

假设空间

模型的集合就是假设空间（hypothesis space）。

学习过程： 搜索所有假设空间，与训练集匹配。

假设空间规模：所有可能取值组合。

假设形状，剥皮，味道分别有3，2，3种可能取值，加上取任意值*和空集，假设空间规模(4 imes 3 imes 4 + 1 = 49)。

学习方法三要素

方法 = 模型 + 策略 + 算法。

当假设空间(F)为决策函数的集合，(F)实质上就是参数向量决定的函数族，(F = {f | Y = f(x)})。

当假设空间(F)为条件概率的集合，(F)实质上就是参数向量决定的条件概率分布族，(F = {f | Y = f_{ heta}(x), heta in R^n})。

损失函数：模型一次预测的好坏，损失函数值越小，模型越好。

0-1损失函数 0-1 loss function：(L(Y, f(X)) =
left{
egin{aligned}
1, Y
eq f(X) \
0, Y = f(X)
end{aligned}
ight.)。
平方损失函数 quadratic loss function：(L(Y,f(X)) = (Y – f(X))^2)。
绝对损失函数 absolute loss function：(L(Y,f(X)) = |Y – f(X)|)。
对数损失函数 quadratic loss function/对数似然损失函数 loglikelihood loss function：(L(Y,P(Y|X)) = -logP(Y|X))。

风险函数：平均意义上模型预测的好坏。

风险函数 risk function/期望损失 expected loss（损失函数的期望）：(R_{exp}(f) = E_p[L(Y, f(X))] = int_{x imes y}L(Y, f(X))P(x, y)dxdy)。

我们想到，可以用经验风险估计期望风险：

经验风险最小化最优模型：(min_{f in F} frac{1}{N} sum_{i = 1}^N L(y_i, f(x_i)))。

当样本容量很小时，经验风险最小化学习的效果未必很好，会产生“过拟合overfitting”。

为防止过拟合提出的策略，结构风险最小化 structure risk minimization，等价于正则化（regularization），加入正则化项regularizer，或罚项 penalty term。

奥卡姆剃刀定理

如无必要，勿增实体。

没有免费的午餐定理

一个学习算法A，若它在某个问题上比另一个学习算法B好，则必然存在另一些问题B比A好。

NFL定理前提条件：

所有“问题”出现的机会相同或所有问题同等重要。
假设真实函数F为均匀分布。

NFL定理寓意：脱离具体问题，空谈“什么方法好”毫无意义。

训练误差和测试误差

训练误差，即训练数据集的平均损失：(Remp(hat{f}) = frac{1}{N} sum_{i = 1}^N L(y_i,hat{f}(x_i)))。

测试误差，即测试数据集的平均损失：(e_{test} = frac{1}{N’} sum_{i = 1}^{N’} L(y_i,hat{f}(x_i)))。

损失函数是0-1函数时：(e_{test} = frac{1}{N’} sum_{i = 1}^{N’} I(y_i
eq hat{f}(x_i)))。

测试数据集的准确率：(r_{test} = frac{1}{N’} sum_{i = 1}^{N’} I(y_i = hat{f}(x_i)))。

过拟合与模型选择

过拟合：学习时选择的模型过于复杂或包含的参数过多，导致这一模型对已知数据预测得很好，但是对未知数据预测得很差。

当模型较复杂时，我们可以采用增加训练样本集大小的方式减小泛化误差。也可以通过增加正则化项防止过拟合的产生。

泛化能力

对泛化能力的分析是通过研究泛化误差（generalization error）的概率上界进行的。

性质：随着样本容量增加，泛化误差趋于0。假设空间容量越大，泛化误差越大。

生成模型和判别模型

监督学习的目的就是学习一个模型。

生成方法（generative approach）对应生成模型（generative model），如：朴素贝叶斯法和隐马尔科夫模型法等。

判别方法（discriminative approach）对应判别模型（discriminative model），如：K近邻，感知机，决策树，logistic回归等。

两模型对比：

生成模型

可以还原联合概率，而判别模型不能。
学习收敛速度快，当样本容量增加时，学到的模型可以更快收敛。
当存在隐变量时，可以使用生成模型，判别模型不行。

判别模型

直接学习决策函数或条件概率，学习的准确率更高。
可以对数据进行抽象，定义特征和使用特征，可以简化学习问题。

测试

经验风险最小化最优模型，当样本容量很小时，经验风险最小化学习可能会产生哪种现象？

[ ] 欠拟合
[x] 过拟合

下图中蓝色表示采样点，绿色曲线为样本的真实分布，红色曲线是通过采样点拟合的多项式模型，则下列模型中欠拟合的是？

答案：AB

第三章 模型性能评估

留出法

留出法（hold-out）：将数据集D划分为两个互斥的集合，其中一个集合作为训练集S，另一个作为测试集T，S ∩ T = ∅。

注意：

训练/测试集的划分尽可能保持数据分布的一致性，避免引入额外偏差。
存在多种划分方式对初始数据集进行分割，采用若干次随机划分，重复实验。

存在问题：

S大，T小，测出的泛化误差不太可靠。
S小，T大，获得的模型可能就不太可靠。

交叉验证法

交叉验证法（k-fold cross validation）：将数据集D划分为k个大小相等的互斥子集，子集间无交集，k-1个子集并集为训练集，剩余1个为测试集。共测试k次，将k次的测试结果取平均。

自助法

给定包含m个样本的数据集，对其进行采样，产生数据集D’。具体过程为：每次随机从D中挑选一个样本将其拷贝放入D’，然后再放回原来的初始数据集D中，使得该样本在下次采样时仍有可能被采到，重复执行m次。

优点：

适用于数据集较小，难以进行数据集和测试集划分的情况。
从数据集产生不同的训练集，适用于集成学习方法。

缺点：产生的训练集改变了初始数据集的分布，会引入估计偏差。

性能度量

性能度量：对模型泛化能力评估的统一评价标准。不同任务性能度量不同，如回归任务是看均方误差，分类任务是看错误率和精度。

有时单纯依靠错误率和精度不能很好的进行性能度量，此时引入查准率（准确率 precision）、查全率（召回率 recall）和F1分数。

查准率：(P = frac{TP}{TP + FP})。
查全率：(R = frac{TP}{TP + FN})。

PR曲线

提高查准率，会降低召回率；提高召回率，会降低查准率。

为平衡两者之间的大小关系，引入F1 Score，(F_1 = 2 frac{PR}{P + R})，此方法会给查找率和召回率中较低的值一个更高的权重，因此此方法要想有个较大的权值，必须两者相差不大。

拓展：(F_eta)度量：(F_eta = frac{(1 + eta^2) imes P imes R}{(eta^2 imes P) + R})，可根据P、Q重要程度调节(eta)大小。

当有多个二分类混淆矩阵时，如：多次训练/测试、多个数据集上训练/测试、执行多分类任务。有两种考察方法：

宏查准率(macro-P)/宏查全率(macro-R)/宏F1：将所有的P、R、F1取平均。

(macro-P = frac{1}{n} sum_{i = 1}^n P_i)，(macro-R = frac{1}{n} sum_{i = 1}^n R_i)，(macro-F_1 = frac{2 imes macro-P imes macro-R}{macro-P + macro-R})。

微查准率(micro-P)/微查全率(micro-R)/微FI：先对每个TP、FP、PN分别取平均，再根据公式计算各自的性能值。

(micro-P = frac{overline{TP}}{overline{TP} + overline{FP}})，(micro-R = frac{overline{TP}}{overline{TP} + overline{FN}})，(micro-F_1 = frac{2 imes micro-P imes micro-R}{micro-P + micro-R})。

ROC和AUC曲线

ROC(Receiver Operating Characteristic)

纵轴：“真正例率” (True Positive Rate，简称TPR)
横轴：“假正例率” (False Positive Rate，简称FPR)

当一个曲线包住另一条曲线，则前者性能更优；当两个曲线发生交叉，则AUC(Area Under ROC Curve) 面积大者性能更优。

代价敏感错误率

应用背景：不同类型的错误所造成的后果不同。

为了权衡不同类型错误所造成的不同损失，可以为错误赋予非均等代价。

非均等代价下，ROC曲线不能直接反映出学习期的期望的总体代价，但代价曲线可以。

横轴：正例概率代价——P为样例为正例的概率，(P(+)cost = frac{p imes cost_{01}}{p imes cost_{01} + (1 – p) imes cost_{10}})。

纵轴：取值为 [0,1] 的归一化代价，(cost_{norm} = frac{FNR imes p imes cost_{01} + FNR times (1 – p) times cost_{10}}{p imes cost_{01} + (1 – p) imes cost_{10}})。

曲线绘制过程：ROC曲线上的每一点都对应了代价平面上的一条线段，设ROC曲线上的点的坐标为FPR，则可相应的计算出FNR，然后在代价平面上绘制一条FPR到1，FNR两点的线段，线段下的面积表示了该条件下的期望总体代价。这样就将ROC曲线上的每个点都转化为代价平面上的一条线段，取所有线段的下界围成的面积即为在所有条件下学习期的期望总体代价。

假设检验

不可直接用上述评估方法获得的性能度量“比大小”，原因：

希望比较泛化性能，实验评估的是测试集性能。
测试集性能和测试集的选择有关，测试样例不同，结果不同。
机器学习算法本身有一定的随机性，相同的参数，相同的数据集，结果也会不同。

统计假设检验（hypothesis test）：在测试集上观察到学习器A比B好，则A的泛化性能是否在统计意义上优于B，以及这个结论的把握有多大。

假设检验：

对单个学习器泛化性能的假设进行检验

“二项检验” (binomial test)
“t 检验”(t-test)

对不同学习器的性能进行比较

“成对 t 检验” (paired t-tests)

T检验

略。

偏差和方差

期望输出与真实标记的差别称为偏差。

泛化误差可分解为偏差、 方差与噪声之和。

测试

真正例率TPR的怎么计算？

[x] (TPR = frac{TP}{(TP+FN)})
[ ] (TPR=frac{FP}{(FN+FP)})
[ ] (TPR=frac{(TP+FN)}{TP})
[ ] (TPR=frac{(TN+FP)}{FP})

解析：

真正例率(TPR = frac{TP}{(TP+FN)})，表示预测为正例且真实情况为正例的，占所有真实情况中正例的比率。
假正例率(TPR=frac{FP}{(FN+FP)})，表示预测为正例但真实情况为反例的，占所有真实情况中反例的比率。
(TPR)越大，则表示挑出的越有可能（是正确的）；(FPR)越大，则表示越不可能（在挑选过程中，再挑新的出来，即再挑认为是正确的出来，越有可能挑的是错误的）。
(TPR)与(FPR)呈反相关，随着采样的继续，越不可能是正例的被采样出来，(TPR)降低，(FPR)升高。

在(ROC)分析中，分类器的性能曲线的理想状态是

[ ] 对角线（AUC等于0.5）
[ ] 越靠下越好（AUC趋近于0）
[x] 越靠上越好（AUC趋近于1）

任意一条ROC曲线都有一条代价曲线与之对应，反之亦然。

[x] 对
[ ] 错

解析：ROC曲线的点对应了一对（TPR，FPR），即一对（FNR，FPR），由此可得一条代价线段（0，FPR)–(1，FNR），由所有代价线段构成簇，围取期望总体代价和它的边界–代价曲线。所以说，ROC对应了一条代价曲线，反之亦然。