机器学习课程自学笔记

参考内容：《机器学习》周志华

成绩构成：

考勤、作业、研讨：10%
项目：40%
期末：50%

一. 绪论

根据训练数据是否拥有标记数据，学习任务大致可分为两类：监督学习、无监督学习。
- 分类和回归是前者的代表，聚类是后者的代表
- 聚类意思是在训练过程中，机器会自动的对事物的潜在概念进行划分，并把物体分成若干组
模型适用于新样本的能力，称为泛化能力
通常假设样本空间中全体样本服从一个位置分布$\mathcal{D}$，我们获得的每个样本都是独立地从这个分布上采样得到的，即“独立同分布”。
假设空间
- 简单理解，就是所有输入的状态
- 书中举了个例子，有A、B、C三种属性，分别有3、2、2种取值方式。学习目标是某个状态$(a, b, c)$是否是牛逼的？求所有状态数。
  - 对于属性A，其实有4种状态，$a_1, a_2, a_3, *$，$*$表示这个属性取什么无所谓。对于B、C属性同理
  - 那么状态数就有：$4 * 3 * 3 = 36$种
  - 其实还漏了一种，还有一种状态是世界上没有"牛逼"这个概念，也就是$\phi$状态。
  - 所以这个例子的总状态数是37种。
  - 我来列举其中的几种：
    - A是$a_1$，B是$b_2$，C是$c_3$时，是牛逼的
    - A是$*$，B是$b_1$，C是$*$时，是牛逼的
    - $\cdots$
    - 世界上没有"牛逼"这个东西
版本空间
- 简单理解，就是把假设空间中不符合样本的所有假设剔除掉的空间
- 以书中例子为例
  - 根据表1.1，我们知“好瓜”的概念是成立的，所以先删除 $\phi$ 的假设
  - 根据样本（（色泽=青绿）^{（根蒂=蜷缩）}（敲声=浊响））——>好瓜，删除所有状态对不上的假设
  - 根据样本（（色泽=乌黑）^{（根蒂=蜷缩）}（敲声=浊响））——>好瓜，删除所有状态对不上的假设
  这里把（（色泽=乌黑）^{（根蒂=蜷缩）}（敲声=浊响））删除，这个和样本2符合，不要觉得心虚，因为利用样本2进行删除的时候也会删掉（（色泽=青绿）^{（根蒂=蜷缩）}（敲声=浊响））这样刚好留下了（（色泽=*）^{（根蒂=蜷缩）}（敲声=浊响）
  - 根据样本（（色泽=青绿）^{（根蒂=硬挺）}（敲声=清脆））——>不是好瓜，删除所有状态对上的假设
  - 根据样本（（色泽=乌黑）^{（根蒂=稍蜷）}（敲声=沉闷））——>不是好瓜，删除所有状态对上的假设
  - 所以最后剩下了三个假设，这三个假设我们称之为版本空间：(色泽 = , 根蒂 = 蜷缩, 敲声 = )、(色泽 = , 根蒂 = , 敲声 = 清脆)、(色泽 = *, 根蒂 = 蜷缩, 敲声 = 清脆)
归纳偏好
- 现实问题中，我们常面临很大的假设空间，但学习过程是根据有限的样本训练集进行的，那么对于不同版本的训练集，就会有不同的版本空间。版本空间内每一个假设都可以判断上面数据集中的每一条数据，是好瓜还是不是好瓜，但是用不同的假设判断一条新数据可能会得出不一样的结果，这就属于“归纳偏好”。

二. 模型评估与选择

精度 = 1 - 错误率
学习器在训练集上的误差叫“训练误差”或“经验误差”
学习器在新样本上的误差叫“泛化误差”。显然，我们想要泛化误差小的学习器。
过拟合是指训练误差很小，但是泛化误差不理想。欠拟合是指俩误差都不理想。

模型评估方法

评估方法存在的意义：实际中，我们不可能直接拿到泛化误差，因为泛化误差是指实际情况的误差。产品都没开发出来咋获得嘛。而训练误差又由于过拟合现象的存在而不适合作为标准。所以，这时候就需要设计一些精妙的评估方法
留出法
- 将数据集D切为训练集S和验证集T
- 需要注意，S和T的划分要尽可能保持数据分布的一致性。例如在分类任务中至少要保证样本的类别比例相似
- 为了结果可靠，可以进行多次留出法，用平均值作为最终结果
- 留出法的缺点：我们希望的是评估用D训练出的模型的性能，但留出法本质上是评估的S训练出来的模型的性能。这就会陷入一个窘境：若S包含绝大多数样本，虽然S与D的差距拉近，但是T太小导致评估结果可能不稳定；若S太少，S与D的差距就更远了。所以这个bug没有完全的解决方案，常见做法是将约1/5 ~ 1/3的样本用于测试，剩下的用于训练
交叉验证法
- 将D划分为k个大小相似的互斥子集：$D = D_1 \cup D_2 \cup \cdots \cup D_k$。然后枚举$D_i$，每次(全集 - $D_i$)作为训练集，$D_i$作为验证集。进行k次训练测试，最后返回k次结果的均值。
- 可以发现，交叉验证法的稳定性和保真性很大程度取决于k，通常取10，称为10折交叉验证
- 需要注意，$D_i$尽可能保持数据分布的一致性
- 为了结果可靠，可以进行多次交叉验证法，用均值作为最终结果。常见的有：10次10折交叉验证
- （当k = D样本数量时，是交叉验证法的一个特例，称为留一法）
自助法
- 无论是留出法还是交叉验证法，S != D，所以必然会存在一定偏差。留一法虽然可以使得S $\to$ D，但是训练集太大计算复杂度太高。有没有两全其美的方法呢——自助法。
- 做法：假设D样本数为m，则进行放回随机采样m次，得到D'。用D'作为训练集，D'作为验证集。
- 样本在m次采样始终不被采到的概率：
\[ \lim_{m\mapsto\infty}\left(1-\frac1m\right)^m\mapsto\frac1e\approx0.368 \]
- 即数据集D中约36.8%的样本不会出现在D'中。
- 优点：评估的模型和期望评估的模型都使用了m个样本，但仍有1/3的数据供我们验证。在数据集较小或难以划分训练/验证集时很有用。
- 缺点：自助法生产的数据集改变了初始数据集分布，会引入估计偏差。因此数据量充足时，留出法和交叉验证法更常用
在进行完模型评估（也就是训练和评估）后，需要再将数据集D全部丢进模型训练一次。这么做是因为模型评估时S != D。

性能度量

当得到一个模型后，如何评估它的泛化能力呢？显然需要去度量它的性能，衡量模型泛化能力的评价标准，就叫性能度量。不同的性能度量往往会导致不同的评判结果。
回归任务最常用的性能度量是“均方误差”：
- 离散：$E(f; D) = \frac1m\sum_{i=1}^m(f(x_i) - y_i)^2$
- 一般：$E(f; \mathcal{D}) = \int_{x \sim \mathcal{D}}(f(x) - y)^2p(x)dx$
ok，接下来介绍分类任务的性能度量

错误率和精度
- 错误率定义
  - 离散：$E(f; D) = \frac1m\sum_{i=1}^m\mathbb{I}(f(x_i) \ne y_i)$
  - 一般：$E(f; \mathcal{D}) = \int_{x \sim \mathcal{D}}\mathbb{I}(f(x)\ne y)p(x)dx$
- 精度定义
  - 离散：$acc(f; D) = \frac1m\sum_{i=1}^m\mathbb{I}(f(x_i)=y_i)=1-E(f; D)$
  - 一般：$acc(f; \mathcal{D}) = \int_{x \sim \mathcal{D}}\mathbb{I}(f(x)=y)p(x)dx=1-E(f; \mathcal{D})$
查准率、查全率、F1
- 举个例子，若我们关心“挑出的西瓜中有多少比例是好瓜”以及“所有好瓜中有多少比例被挑了出来”。前者我们用“查准率”(precision)描述，后者用"查全率"(recall)来描述。
- 对二分类来说，我们将预测结果抽象为混淆矩阵：
- （TP, true positive表示它确实是正例，表示我们预测对了。TN, true negative表示它确实是反例，表示我们预测对了。）
- 显然$TP + FN + FP + TN = $样例总数
- 查准率：$P = \frac{TP}{TP + FP}$
- 查全率：$R = \frac{TP}{TP + FN}$
- 可以发现，查准率和查全率都兼顾有些困难。因为如果想让查全率高，那么就要增加选瓜数量，但是选瓜数量增加后，选出的瓜中是好瓜的概率可能就下降，即查准率下降；若希望选出的好瓜比例高，那么只挑选最有把握的瓜，这样难免就会漏掉不少好瓜，即查全率较低。通常只有在一些简单任务中，才能使P和R都很高。
- 所以，有没有直观的比较方法呢——PR图。
- 我们根据学习器的预测结果对样例排序，＂最可能＂是正例的排在最前边或者说最左边，＂最不可能＂是正例的排在最后边或者说最右边．按此顺序逐个把样本作为正例进行预测，每次计算测试样本的查准率和查全率并把这两项作为PR曲线的纵轴和横轴。
- 显然若一条曲线包住了另一条曲线，那么说明它在任意时刻表现都好。如果俩曲线有相交，那么就比较下俩曲线所形成的面积，谁大谁牛逼。
- 当然面积可能不好算，所以我们直接用“平衡点”（BEP, 即P = R时的R坐标）来衡量，谁平衡点大谁牛逼。但是平衡点这方法还是太简陋了，所以我们使用F1度量（谁大谁牛逼）：
\[ \frac{1}{F_1} = \frac12\cdot (\frac1P + \frac1R) \]
- 为了更定制化，还可以使用$F_\beta$度量（$F_1$是调和平均，$F_\beta$是加权调和平均）：
\[ \frac{1}{F_\beta} = \frac{1}{1+\beta^2}\cdot (\frac1P + \frac{\beta^2}{R}) \]
- $\beta$度量了查全率对查准率的相对重要性，$\beta=1$为一样重要，$\beta > 1$表示我们更重视查全率。
- 如果有多个混淆矩阵呢？
- 第一种方法，直接对所有P、R、F1取均值作为最终结果。这样得到的结果叫做：宏查准率、宏查全率、宏F1
- 第二种方法，先对所有混淆矩阵对应四个位置取均值，再算出对应的P、R、F1。这样得到的结果叫做：微查准率、微查全率、微F1
ROC和AUC
- ROC曲线跟PR曲线绘制流程一样，只是横坐标换为了“假正例率”（FPR），纵坐标换为了“真正例率”（TPR）。
- $TPR = \frac{TP}{TP + FN}, \quad FPR = \frac{FP}{FP + FN}$
- TPR表示对于全部好瓜，你预测对了百分之TPR；FPR表示对于全部坏瓜，你预测错了百分之FPR。
- 显然TPR越高越好，FPR越低越好。
- ROC曲线画出来的感觉如下：
- AUC是ROC曲线的面积。显然如果一个曲线包住另一个，但它就更牛逼。如果俩线有相交，那么就看看谁的AUC更大，越大越牛逼。
代价敏感错误率和代价曲线
- 在现实中同样是判断错误，但是后果可能不同。比如门禁系统错误的把陌生人放进来的危害肯定比把可通行人拦在外边危害更大。所以同样是判断错误，我们需要赋予其不同的权值。最后的目标是使平均代价最小。
- 所以可以抽象出代价矩阵的概念：
- 代价敏感错误率：
\[ E(f; D; cost) = \frac1m(\sum_{x_i \in D^+}\mathbb{I}(f(x_i) \ne y_i) \times cost_{01} + \sum_{x_i \in D^-}\mathbb{I}(f(x_i) \ne y_i) \times cost_{10}) \]
- 当不同后果的权重不同时，上面说的ROC曲线就不能直接反映出学习器的期望总体代价了。所以这时候我们需要“代价曲线”。
- 略

比较检验

目前，我们已经可以使用某种模型评估方法，测出某个性能度量的结果。
但是泛化性能是对新样本进行预测的性能，新样本看成一个总体，那么这个总体我们永远无法完整获得，也就是真实泛化性能永远也不知道是多少。从这个总体中抽样得到一个样本集合，也就是我们通常说的“测试集”，很显然，每次抽样，获得的测试集都不相同，从而从测试集计算得到的性能值也就不同。从测试集得到的性能值可以看成是总体泛化性能的一个估计值，基于这个估计值可以对总体泛化性能进行假设检验和区间估计。
如果$\mathcal{D}$是服从二项分布的。那么测试集样本容量n你是知道的，错误次数k你也是知道的。那么你可以开始玩假设检验。比如假设$H_0: p_0 \le 0.5$。然后你就假设你这个假设是对的呗，然后算一算在此假设下，错误次数为k的概率。如果算出来的概率小于$\alpha$（显著性水平），说明在此假设下发生这件事的概率极低，那么说明你假设是错的。如果概率大于了$\alpha$，说明至少我不能信心满满的否决你的假设了，我只能说我有$1 - \alpha$置信度认为你的假设是正确的。
很多时候我们并非做一次留出法估计，而是多次。所以我们会得到k个测试错误率。则我们可以计算平均错误率及其方差。那么检验统计量$\tau_t = \frac{\sqrt{k}(\mu - \epsilon_0)}{\sigma}$服从t分布。（$\mu$是平均错误率，$\epsilon_0$是假设的错误率， $\sigma$是前面算的方差）
如果算出来的$\tau_t$落在$[t_{-\alpha/2}, t_{\alpha/2}]$内，则可下置信度为$1 - \alpha$的判断认为真实错误率为$\epsilon_0$；反之则可下真是错误率不为$\epsilon_0$的判断。
以上俩方法都是关于对单个学习器泛化性能的假设进行的检验，但在实际任务中，更多时候我们需要对不同学习器的性能进行比较，方法有：交叉验证t检验、McNemar检验、Friedman检验、Nemenyi后续检验

交叉验证t检验
- 略
McNemar检验
- 对二分类问题，使用留出法不仅可估计出学习器A、B的测试错误率，还可以获得俩学习器分类结果的差别，即：两者都分类正确、都错误、A对B错，A错B对的次数，即“列联表”：
- 若我们的假设是俩学习器性能相同，则应有$e_{01} = e_{10}$。则$|e_{01} - e_{10}| \sim N(1, e_{01} + e_{10})$。
- 则有：$\tau_{\chi^2}=\frac{(|e_{01} - e_{10}| - 1) ^ 2}{e_{01} + e_{10}}$
- 即$\tau_{\chi^2}$服从自由度为1的卡方分布。
- 当$\tau_{\chi^2}$小于临界值$\chi_\alpha^2$时，即认为俩学习器性能没有显著差别；反之则认为有显著差别，平均错误率小的那个更牛逼。
Friedman检验
- 略
Nemenyi后续检验
- 略

偏差与方差

为取得良好的泛化能力，则需使偏差较小，此时能够充分拟合数据。并且要使方差较小，因为越小的方差表示受数据扰动的影响小。
但是往往两全不能齐美，称为偏差-方差窘境。
具体内容略。