西瓜书学习笔记(2)

主要内容：误差与过拟合、评估方法、训练集与测试集的划分方法、调参、性能度量

经验误差与过拟合

我们把学习器的实际预测输出与样本的真实输出之间的差异称为 误差(error) :

• 在训练集上的误差称为 训练误差(training error) 或 经验误差(empirical error)
• 在新样本上的误差称为 泛化误差(generalization error)
• 在测试集上的误差称为 测试误差(test error)

显然，我们希望得到的是在新样本上表现得很好的学习器，即泛化误差小的学习器。因此，我们应该让学习器尽可能地从训练集中学出普适性的”一般特征”，这样在遇到新样本时才能做出正确的判别。然而，当学习器把训练集学得”太好”的时候，即把一些训练样本的自身特点当做了普遍特征；同时也有学习能力不足的情况，即训练集的基本特征都没有学习出来。我们定义：

• 学习能力过强，以至于把训练样本所包含的不太一般的特性都学到了，称为： 过拟合(overfitting)
• 学习能太差，训练样本的一般性质尚未学好，称为： 欠拟合(underfitting)

在过拟合问题中，训练误差十分小，但测试误差教大；在欠拟合问题中，训练误差和测试误差都比较大。

目前，欠拟合问题比较容易克服，例如增加迭代次数等，但过拟合问题还没有十分好的解决方案，过拟合是机器学习面临的关键障碍。

过拟合是无法彻底避免的，我们所能做的只是”缓解”，或者说减小其风险。关于这一点，可大致这样理解:机器学习面临的问题通常是NP难甚至更难，而有效的学习算法必然是在多项式时间内运行完成，若可彻底避免过拟合，则通过经验误差最小化就能获最优解，这就意味着我们构造性地证明了”P=NP” ;因此，只要相信”P$\not=$NP”，过拟合就不可避免。

评估方法

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

测试样本也是从样本真实分布中独立同分布采样而得，测试集应该尽可能与训练集互斥，即测试样本尽量不在训练集中出现、未在训练过程中使用过。

假设老师出了10道习题供同学们练习，考试时老师又用同样的这10道题作为试题，可能有的童鞋只会做这10 道题却能得高分，很明显：这个考试成绩并不能有效地反映出真实水平。回到我们的问题上来，我们希望得到泛化性能好的模型，好比希望同学们课程学得好并获得了对所学知识”举一反三”的能力；训练样本相当于给同学们练习的习题，测试过程则相当于考试。显然，若测试样本被用作训练了，则得到的将是过于”乐观”的估计结果。

留出法

将数据集D划分为两个互斥的集合，一个作为训练集S，一个作为测试集T，满足D=S$\cup$T且S$\cap$T=$\emptyset$，常见的划分为：大约$\frac{2}{3}$~$\frac{4}{5}$的样本用作训练，剩下的用作测试。

需要注意的是：训练/测试集的划分要尽可能保持数据分布的一致性，以避免由于分布的差异引入额外的偏差，常见的做法是采取分层抽样。同时，由于划分的随机性，单次的留出法结果往往不够稳定，一般要采用若干次随机划分，重复实验取平均值的做法。

例如进行100次随机划分，每次产生一个训练/测试集用于实验评估，100次后就得到100个结果，而留出法返回的则是这100个结果的平均。

交叉验证法(K倍交叉验证)

将数据集D划分为k个大小相同的互斥子集，满足D=$D_{1}\cup D_{2}\cup \dots \cup D_{k}$，$D_{i} \cap D_{j} = \emptyset (i\not ={j})$，同样地尽可能保持数据分布的一致性，即采用分层抽样的方法获得这些子集。

交叉验证法的思想是： 每次用k-1个子集的并集作为训练集，余下的那个子集作为测试集，这样就有K种训练集/测试集划分的情况，从而可进行k次训练和测试，最终返回k次测试结果的均值。 k最常用的取值是10。

与留出法类似，将数据集D划分为k个子集的过程具有随机性，因此K折交叉验证通常也要重复p次，称为p次k折交叉验证，常见的是10次10折交叉验证，即进行了100次训练/测试。

特殊地当划分的k个子集的每个子集中只有一个样本时，称为”留一法”，显然，留一法的评估结果比较准确，但对计算机的消耗也是巨大的。

自助法

我们希望评估的是用整个D训练出的模型。但在留出法和交叉验证法中，由于保留了一部分样本用于测试，因此实际评估的模型所使用的训练集比D小，这必然会引入一些因训练样本规模不同而导致的估计偏差。留一法受训练样本规模变化的影响较小，但计算复杂度又太高了。”自助法”正是解决了这样的问题。

自助法的基本思想是： 给定包含m个样本的数据集D，每次随机从D 中挑选一个样本，将其拷贝放入D’，然后再将该样本放回初始数据集D 中，使得该样本在下次采样时仍有可能被采到。重复执行m 次，就可以得到了包含m个样本的数据集D’。 可以得知在m次采样中，样本始终不被采到的概率取极限为：

$$
\lim_{m\rightarrow \infty}
(1-\frac{1}{m})^{m} \rightarrow
\frac{1}{e} \approx
0.368
$$

这样，通过自助采样，初始样本集D中大约有36.8%的样本没有出现在D’中，于是可以将D’作为训练集，D-D’作为测试集。自助法在数据集较小，难以有效划分训练集/测试集时很有用，但由于自助法产生的数据集（随机抽样）改变了初始数据集的分布，因此引入了估计偏差。在初始数据集足够时，留出法和交叉验证法更加常用。

调参

大多数学习算法都有些参数(parameter) 需要设定，参数配置不同，学得模型的性能往往有显著差别，这就是通常所说的”参数调节”或简称”调参” (parameter tuning)。

学习算法的很多参数是在实数范围内取值，因此，对每种参数取值都训练出模型来是不可行的。常用的做法是：对每个参数选定一个范围和步长，这样使得学习的过程变得可行。

例如，假定算法有3个参数，每个参数仅考虑5个候选值，这样对每一组训练/测试集就有$5^3$= 125个模型需考察，由此可见：拿下一个参数（即经验值）对于算法人员来说是有多么的happy。

最后需要注意的是：当选定好模型和调参完成后，我们需要使用初始的数据集D重新训练模型，即让最初划分出来用于评估的测试集也被模型学习，增强模型的学习效果。

用考试的例子来比喻：就像高中时大家每次考试完，要将考卷的题目消化掉（大多数题目都还是之前没有见过的吧？），这样即使考差了也能开心的玩耍了~。

性能度量

性能度量（performance measure）是衡量模型泛化能力的评价标准，在对比不同模型的能力时，使用不同的性能度量往往会导致不同的评判结果。

在预测任务中，给定样例集D={$(x_{1},y_{1}),(x_{2},y_{2}),\dots,(x_{m},y_{m})$}，其中$y_{i}$是示例$x_{i}$的真实标记。要评估学习器f的性能，就要把学习器预测结果f(x)与真实标记y进行比较。

回归任务中，即预测连续值的问题，最常用的性能度量是 “均方误差”（mean squared error） ,很多的经典算法都是采用了MSE作为评价函数：

$$
E(f;D) =
\frac{1}{m}
\sum ^{m}_{i=1}
( f ( x _{i} ) - y _{i} )^{2}
$$

更一般的，对于数据分布D和概率密度函数p(·)，均方误差可描述为：

$$
\begin{align}
E(f;D) =
\int_{x\sim D}
(f(x)-y)^{2}
p(x)dx
\end{align}
$$

错误率与精度

在分类任务中，即预测离散值的问题，最常用的是错误率和精度，错误率是分类错误的样本数占样本总数的比例，精度则是分类正确的样本数占样本总数的比例，易知：错误率+精度=1。

错误率定义为:

$$
\begin{align}
E(f;D)=
\frac{1}{m}
\sum^{m}_{i=1} Ⅱ( f (x _{i}) \not = {y _i} )
\end{align}
$$

精度定义为：

$$
\begin{align}
acc(f;D)=
\frac{1}
{m}
\sum^{m}_{i=1}
Ⅱ( f ( x _{i}) = {y _i} )
=1-E(f;D)
\end{align}
$$

更一般的，对于数据分布D和概率密度函数p(·)，错误率与精度可分布描述为：

$$
\begin{align}
E(f;D)=
\int_{x\sim D}
Ⅱ( f ( x )\not = { y } )
p(x)dx
acc(f;D)=
\int_{x\sim D}
Ⅱ( f ( x ) = {y} )
p(x)dx
=1-E(f;D)
\end{align}
$$

查准率、查全率与F1

错误率和精度虽然常用，但不能满足所有的需求，例如：在推荐系统中，我们只关心推送给用户的内容用户是否感兴趣（即查准率），或者说所有用户感兴趣的内容我们推送出来了多少（即查全率）。因此，使用查准/查全率更适合描述这类问题。

对于二分类问题，分类结果混淆矩阵（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曲线是成负相关的，从（0，1）到（1，0），从胆小谨慎，到胆大包天。

P-R曲线如何评估

若一个学习器C的P-R曲线被另一个学习器A的P-R曲线完全包住（如上图所示），则称：A的性能优于C。若A和B的曲线发生了交叉，则谁的曲线下的面积大，谁的性能更优。

但一般来说，曲线下的面积是很难进行估算的，所以衍生出了”平衡点”（Break-Event Point，简称BEP），即当P=R时的取值，平衡点的取值越高，性能更优。

F1度量

P-R指标有时会出现矛盾的情况，这样就需要综合考虑他们，最常见的方法就是F-Measure，又称F-Score。F-Measure是P和R的加权调和平均，既：

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

特别的，当$\beta=1$时，也就是常见的F1度量，是P和R的调和平均。当F1较高时，模型的性能越好。

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

F1是基于查准率与查全率的调和平均定义的：$\frac{1}{F1}=\frac{1}{2}(\frac{1}{p}+\frac{1}{R})$
$F_{\beta}$则是加权调和平均：$\frac{1}{F_{\beta} }=\frac{1}{1+\beta^{2} }(\frac{1}{p}+\frac{\beta^2}{R})$
其中$\beta$>0度量了查全率对查准率的相对重要性；$\beta$>1时查全率有更大影响；$\beta$<1时查准率有更大影响。

n个混淆矩阵的综合考察

有时候我们会有多个二分类混淆矩阵，例如：多次训练或者在多个数据集上训练，那么估算全局性能的方法有两种，分为宏观和微观。

• 宏观：先算出每个混淆矩阵的P值和R值，然后取得平均P值macro_P和平均R值macro_R，在算出Fβ或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×mraco_P×mraco_R}
{mraco_P+mraco_R}
$$

• 微观：计算出混淆矩阵的平均TP、FP、TN、FN，接着进行计算P、R，进而求出Fβ或F1。

$$
micro_P =
\frac{\over{TP}}
{ {\over{TP} } + {\over{FP} } }
$$

$$
micro_R =
\frac{\over{TP} }
{ {\over{TP} } + {\over{FN} } }
$$

$$
micro_F1 =
\frac{2×micro_P×micro_R}
{micro_P+micro_R}
$$

ROC与AUC

学习器对测试样本的评估结果一般为一个实值或概率，设定一个阈值，大于阈值为正例，小于阈值为负例，因此这个实值的好坏直接决定了学习器的泛化性能，若将这些实值排序，则排序的好坏决定了学习器的性能高低。ROC曲线正是从这个角度出发来研究学习器的泛化性能。

ROC

受试者工作特征曲线 （receiver operating characteristic curve，简称ROC曲线），又称为感受性曲线（sensitivity curve）。

ROC曲线与P-R曲线十分类似，都是按照排序的顺序逐一按照正例预测，不同的是ROC曲线以 “真正例率”（True Positive Rate，简称TPR）为横轴，纵轴为 “假正例率”（False Positive Rate，简称FPR），ROC曲线偏重研究基于测试样本评估值的排序好坏。

$$
TPR = \frac{TP}{TP + FN} = 1 - FNR
$$

$$
FPR = \frac{FP}{TN + FP} = 1 - TNR
$$

$$
TNR = \frac{TN}{TN + FP} = 1 - FPR
$$

FPR的值等于1-特异性。特异性（Specificity）是指在所有实际为负例的样本中，模型正确地预测为负例的样本比例，其衡量的是模型对负例样本的判断能力。

简单分析图像，可以得知（0,0）表示将所有的样本预测为负例，（1,1）则表示将所有的样本预测为正例，（0,1）对应正例全部出现在负例之前的理想模型，（1,0）则表示负例全部出现在正例之前的最差模型，对角线对应于”随即猜测”模型。

ROC曲线是正相关的，纵轴为真正例率，横轴为假正例率，从（0，0）到（1，1），从小兵到将军，到达人生巅峰。

现实中的任务通常都是有限个测试样本，因此难以绘制出光滑的ROC曲线，只能绘制出近似ROC曲线。绘制方法：首先根据测试样本的评估值对测试样本排序，接着按照以下规则进行绘制。

第一步是按照属于’正样本’的概率将所有样本排序，如下图所示:

第二步，让我们依次来看每个样本。对于样本1，如果我们将他的score值做阈值，也就是说，只有score大于等于0.9时，我们才把样本归类到真阳性（true positive），这么一来， 在ROC曲线图中，样本1对应的混淆矩阵（confusion matrix）为:

其中，只有样本1我们看作是正确分类了（也就是我们预测是正样本，实际也是正样本）；其余还有9个实际是正样本，而我们预测是负样本的（2，4，5，6，9，11，13，17，19）；剩下的实际是负样本，我们都预测出是负样本了（也就是false positive = 0， true negative = 10）。

同理我们来看样本3，它的混淆矩阵为:

其中，样本1，2我们看作是正确分类了（也就是我们预测是正样本，实际也是正样本）;其余还有8个实际是正样本，而我们预测是负样本的（2，4，5，6，9，11，13，17，19）;而样本3是假阳性（我们预测是正样本，实际是负样本）;剩下的（7，8，10，12，14，15，16，18，20）实际是负样本，我们都预测出是负样本了（也就是false positive = 1，true negative = 9）。

从样本3的混淆矩阵中，我们可以算出X轴坐标（false positive rate）= 1/(1+9)= 0.1 和Y轴坐标（true positive rate）= 2/(2+8)= 0.2，这就是下图中的第三个点。

依次把20个样本的混淆矩阵列出来，再算出X轴坐标（false positive rate） 和Y轴坐标（true positive rate），就可以得到ROC曲线啦～

AUC

进行模型的性能比较时，若一个学习器A的ROC曲线被另一个学习器B的ROC曲线完全包住，则称B的性能优于A。

若A和B的曲线发生了交叉，则谁的曲线下的面积大，谁的性能更优。

ROC曲线下的面积定义为AUC（Area Uder ROC Curve），不同于P-R的是，这里的AUC是可估算的，即AOC曲线下每一个小矩形的面积之和。易知：AUC越大，证明排序的质量越好，AUC为1时，证明所有正例排在了负例的前面，AUC为0时，所有的负例排在了正例的前面。

假设ROC曲线是由坐标为{$(x_{1},y_{1}),(x_{2},y_{2}),\dots,(x_{m},y_{m})$}的点按顺序连接而成$(x_{1}=0,x_{m}=1)$，则AUG定义为：

$$
AUG =
\frac{1}{2}
\sum_{i=1}^{m-1}
(x_{i+1}-x_{i})·(y_{i}+y_{i+1})
$$

AUC考虑的是样本预测的排序质量，因此它与排序误差有紧密联系.给定$m^{+}$个正例和$m^{-}$个反例，令$D^{+}$和$D^{-}$分别表示正、反例集合，则排序”损失”(loss)定义为：

$$
\ell_{rank}=
\frac{1}{m^{+}+m^{-}}
\sum_{x^{+}\in D^{+}}
\sum_{x^{-}\in D^{-}} \big(
Ⅱ(f(x^{+})<f(x^{-})) +
\frac{1}{2}
Ⅱ(f(x^{+})=f(x^{-}))
\big)
$$

$\ell_{rank}$对应的是ROC曲线之上的面积，于是便有：

$$
AUC = 1 - \ell_{rank}
$$

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

代价敏感错误率通俗来讲就针对错误来赋予其代价。

例如：将无疾病–>有疾病只是增多了检查，但有疾病–>无疾病却是增加了生命危险.

以二分类为例，由此引入了 “代价矩阵”（cost matrix） 。

通常来说重要的是比值而非绝对值。

在非均等错误代价下，我们希望的是最小化”总体代价”，这样”代价敏感”的错误率:

$$
E(f;D;cost) =
\frac{1}{m}(
\sum_{x_{i}\in D^{+}}
Ⅱ(f(x_{i})\not ={y_{i}})×cost_{01} +
\sum_{x_{i}\in D^{-}}
Ⅱ(f(x_{i})\not ={y_{i}})×cost_{10}
)
$$

代价曲线

同样对于ROC曲线，在非均等错误代价下，演变成了”代价曲线”，代价曲线横轴是取值在[0,1]之间的正例概率代价，式中p表示正例的概率，纵轴是取值为[0,1]的归一化代价。

$$
P(+)cost =
\frac{p×cost_{01}}
{p×cost_{01}+(1-p)×cost_{10}}
$$

$$
cost_{norm} =
\frac{FNR×p×cost_{01}+FPR×(1-p)×cost_{10}}
{p×cost_{01}+(1-p)×cost_{10}}
$$

代价曲线的绘制很简单，如图所示：

$$
FNR = \frac{FN}{TP+FN} = 1- TPR
$$

设ROC曲线上一点的坐标为(TPR，FPR) ，则可相应计算出FNR=1-TPR，然后在代价平面上绘制一条从(0，FPR) 到(1，FNR) 的线段，线段下的面积即表示了该条件下的期望总体代价；如此将ROC 曲线土的每个点转化为代价平面上的一条线段，然后取所有线段的下界，围成的面积即为在所有条件下学习器的期望总体代价