《机器学习》摘抄兼笔记

死去的排列组合、数理统计、线性代数回忆正在攻击我．

绪论

“奥卡姆剃刀” (Occam’s razor) 是一种常用的、自然科学研究中最基本的原则，即“若有多个假设与观察一致，则选最简单的那个”．……然而，奥卡姆剃刀并非唯一可行的原则．

对于一个学习算法 $\mathfrak{L}_a$，若它在某些问题上比学习算法 $\mathfrak{L}_b$ 好，则必然存在另一些问题，在那里 $\mathfrak{L}_b$ 比 $\mathfrak{L}_a$ 好．

“没有免费的午餐”定理，简称 NFL 定理。
如果不假设训练数据和测试数据之间有某种共同规律，那么学习是不可能的。
机器学习的关键不是找到“万能模型”，而是找到适合当前问题结构的模型、假设和归纳偏置。

模型评估与选择

我们希望得到泛化误差小的学习器．然而，我们……实际能做的是努力使经验误差 训练误差 最小化．

然而，当学习器把训练样本学得“太好”了的时候，很可能已经把训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质，这样就会导致泛化性能下降．这种现象在机器学习中称为“过拟合” (overfitting)．

……必须认识到，过拟合是无法彻底避免的，我们所能做的只是“缓解”，或者说减小其风险．

评估方法

为此，需使用一个“测试集” 验证集 来测试学习器对新样本的判别能力，然后以测试集上的“测试误差”作为泛化误差的近似．

测试集应该尽可能与训练集互斥，即测试样本尽量不在训练集中出现、未在训练过程中使用过．

• 留出法 (hold-out)：

  $$D = S \cup T, \quad S \cap T = \varnothing.$$

  常见做法是将大约 2/3 ~ 4/5 的样本用于训练，剩余样本用于测试．

• 交叉验证法 (cross validation)：

  $$D = D_1 \cup \dots \cup D_k, \quad D_i \cap D_j = \varnothing \; (i \neq j).$$

  每次用 $k-1$ 个子集的并集作为训练集，余下的子集作为测试集．
  $k$ 最常用的取值是 $10$，此时称为 10 折交叉验证．

  • 若令 $k=N$，则得到了一个特例：留一法 (Leave-One-Out, LOO)．
    留一法不受随机样本划分方式的影响，结果往往比较准确，然而计算开销可能是难以忍受的．

• 自助法 (bootstrapping)：独立（有放回地）随机选择 $N$ 个样本作为训练集 $D'$，则有约 1/e 的样本 $D - D’ $ 作为测试集．

  k 折交叉验证更适合评估模型、选择超参数；
  自助法更适合估计不确定性、训练集成模型．

性能度量

给定样例集 $D = \{ (\bm{x}_1, y_i), \dots, (\bm{x}_N, y_N) \}$，其中 $y_i$ 是示例 $\bm{x}_i$ 的真实标记．

回归任务最常用的性能度量是“均方误差” (mean squared error)

$$E(f; D) = \frac{1}{n} \sum_{i=1} ^ n \big(f(\bm{x}_i) - y_i\big) ^ 2, \tag{2.2}$$

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

$$E(f; \mathcal{D}) = \int_{\bm{x} \sim \mathcal{D}} \big(f(\bm{x}) - y\big) ^ 2 \, p(\bm{x}) \, \mathrm{d}\bm{x}. \tag{2.3}$$

查准率和查全率

查准率 $P$ 与查全率 $R$ 分别定义为

$$P = \frac{\mathrm{TP}}{\mathrm{TP} + \mathrm{FP}}, \tag{2.8}$$

$$R = \frac{\mathrm{TP}}{\mathrm{TP} + \mathrm{FN}}. \tag{2.9}$$

查准率和查全率是一对矛盾的度量．一般来说，查准率高时，查全率往往偏低；而查全率高时，查准率往往偏低．……通常只有在一些简单任务中，才可能使查全率和查准率都很高．

P-R 曲线反映的是，当你愿意找出更多正例样本时，查准率会怎样变化．

我认为书中给出的图 2.3 有科学性错误，主要问题出现在曲线两端。当 $R = 0$ 时，尚可以定义 $P = 1.0$，即 $(0, 1.0)$；但当 $R = 1.0$ 时，$P$ 是无论如何不应等于 $0$ 的（除非数据集中没有正例，但那样的话 $P$ 和 $R$ 永远都是 $0$）．

若一个学习器的 P-R 曲线被另一个学习器的曲线完全“包住”，则可断言后者的性能优于前者，例如图 2.3 中学习器 A 的性能优于学习器 C……

……BEP 平衡点 还是过于简化了些，更常用的是 $F_1$ 度量：

$$F_1 = \frac{2 P R}{P + R} = \frac{2 \mathrm{TP}}{2\mathrm{TP} + \mathrm{FP} + \mathrm{FN}} \tag{2.10}$$

$F_1$ 是 $P$ 和 $R$ 的调和平均数，因为调和平均数会“惩罚短板”．
$F_\beta$ 是 $P$ 和 $R$ 的加权调和平均数，$P : R = 1 : \beta ^ 2$．

ROC

ROC 曲线的纵轴是“真正例率”，横轴是“假正例率”，……两者分别定义为

$$\mathrm{TPR} = \frac{\mathrm{TP}}{\mathrm{TP} + \mathrm{FN}}, \tag{2.18}$$

$$\mathrm{FPR} = \frac{\mathrm{FP}}{\mathrm{TN} + \mathrm{FP}}. \tag{2.19}$$

换句话说，真正例率是实际正例被猜对了多少，而假正例率是实际反例被猜错了多少．
对比来看，ROC 更关心模型整体的区分能力，用于正例反例同等重要的时候；而 P-R 适合主要关注正例，或者正反例样本不平衡的时候．

代价

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

在非均等代价下，ROC 曲线不能直接反映出学习器的期望总体代价，而“代价曲线” (cost curve) 则可达到该目的．

比较检验

我们可使用“二项检验” (binomial test) 来对“$\epsilon \leq 0.3$”（即“泛化错误率是否不大于 0.3”）这样的假设进行检验．

在很多时候……通过多次重复留出法或是交叉验证法等进行多次训练/测试，这样会得到多个测试错误率，此时可使用“$t$ 检验”．

为什么这里的方差 $\sigma ^ 2$ 不是除以样本数 $k$ 而是 $k-1$？查找资料后发现，是因为用一组样本去估计总体方差时，要做无偏修正．用样本均值 $\bar{x}$ 得到的离差平方和，通常小于用总体均值 $\mu$ 得到的离差平方和，因此方差总是略小．至于为什么是减去 1，是因为 $\bar{x}$（书上写 $\mu$ 但其实应该是 $\bar{x}$）是由 $k$ 个样本得出的，所以只要前 $k-1$ 个偏差确定了，那么最后一个就被迫确定，也就是说自由度是 $k-1$．

• 交叉验证 $t$ 检验
• McNemar 检验
• Friedman 检验
• Nemenyi 后续检验

偏差与方差

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

偏差

$$\mathrm{bias}^2(\bm{x}) = (\bar{f}(\bm{x}) - y)^2 \tag{2.40}$$

度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学习算法本身的拟合能力；

方差

$$\mathrm{var}(\bm{x}) = \mathbb{E}_D\left[\big(f(\bm{x}; D) - \bar{f}(\bm{x})\big)^2 \right] \tag{2.38}$$

度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响；

噪声则表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界，即刻画了学习问题本身的难度．

书中这里用的符号有些混乱，更清晰的写法是

$$\begin{aligned} \mathrm{bias}^2(\bm{x}) &= \left( f(\bm{x}) - \mathbb{E}[\hat{f}(\bm{x})] \right) ^2 \\ \mathrm{var}(\bm{x}) &= \mathbb{E}_D \left[ \left( \hat{f}(\bm{x}; D) - \mathbb{E}[\hat{f}(\bm{x})] \right) ^2 \right] \end{aligned}$$

高偏差 $\longleftrightarrow$ 模型过于简单、欠拟合
高方差 $\longleftrightarrow$ 模型过于复杂、过拟合

线性模型

$$f(\bm{x}) = \bm{w}^\mathrm{T}\bm{x} + b \tag{3.2}$$

许多功能更为强大的非线性模型可在线性模型的基础上通过引入层级结构或高维映射而得．

由于 $\bm{w}$ 直观表达了各属性在预测中的重要性，因此线性模型有很好的可解释性 (comprehensibility)．

线性回归

基于均方误差最小化来进行模型求解的方法称为“最小二乘法” (least square method)．在线性回归中，最小二乘法就是试图找到一条直线，使所有样本到直线上的欧氏距离之和最小．

先考虑一种最简单的情形：输入属性的数目只有一个……

$$\begin{aligned} (w^*, b^*) &= \argmin_{(w, b)} \sum_{i=1}^n (y_i - f(x_i))^2 \\ &= \argmin_{(w, b)} \sum_{i=1}^n (y_i - wx_i - b)^2. \end{aligned} \tag{3.4}$$

求解过程称为线性回归模型的最小二乘“参数估计”．我们可分别对 $w$ 和 $b$ 求导，令导数为零可得到 $w$ 和 $b$ 最优解的闭式解．

……类似于式 $(3.4)$，有

$$\hat{\bm{w}}^* = \argmin_{\hat{\bm{w}}}(\bm{y} - \mathbf{X}\hat{\bm{w}})^\mathrm{T} (\bm{y} - \mathbf{X}\hat{\bm{w}}), \tag{3.9}$$

其中 $\hat{\bm{w}} = (\bm{w};b)$，$\bm{y} = (y_1; \dots; y_n)$，

$$\mathbf{X} = \left( \begin{matrix} x_{11} & \dots & x_{1d} & 1 \\ \vdots & \ddots & \vdots & \vdots \\ x_{n1} & \dots & x_{nd} & 1 \end{matrix} \right) = \left( \begin{matrix} \bm{x}_1^\mathrm{T} & 1 \\ \vdots & \vdots \\ \bm{x}_n^\mathrm{T} & 1 \end{matrix} \right).$$

$\mathbf{X}^\mathrm{T}\mathbf{X}$ 是否可逆，决定了最小二乘问题有没有唯一的解析解．求解过程见此处．

现实任务中 $\mathbf{X}^\mathrm{T}\mathbf{X}$ 往往不是满秩矩阵．……此时可解出多个 $\hat{\bm{w}}$，它们都能使均方误差最小化．选择哪一个解作为输出，将由学习算法的归纳偏好决定，常见的做法是引入正则化项．

对数几率回归

$$y = \frac{1}{1 + e ^ {-z}} \,, \tag{3.17}$$

$$\ln{\frac{y}{1-y}} = z.$$

对数几率函数是一种“Sigmoid 函数”．

若将 $y$ 视为样本 $\bm{x}$ 作为正例的可能性，则 $1-y$ 是其反例可能性，两者的比值称为“几率”，反映了 $\bm{x}$ 作为正例的相对可能性．对几率取对数则得到“对数几率” (logit)．

线性判别分析

LDA Linear Discriminant Analysis 的思想非常朴素：给定训练样例集，设法将样例投影到一条直线上，使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离．

若将数据投影到直线 $\bm{w}$ 上，……欲使同类样例的投影点尽可能接近，可以让同类样例投影点的协方差尽可能小；而欲使异类样例的投影点尽可能远离，可以让类中心之间的距离尽可能大．同时考虑二者，则可得到欲最大化的目标

$$\begin{aligned} J &= \frac {\|\bm{w}^\mathrm{T}\bm{\mu}_0 - \bm{w}^\mathrm{T}\bm{\mu}_1\|_2^2} {\bm{w}^\mathrm{T}\bm{\Sigma}_0\bm{w} + \bm{w}^\mathrm{T}\bm{\Sigma}_1\bm{w}} \\ &= \frac {\bm{w}^\mathrm{T} (\bm{\mu}_0 - \bm{\mu}_1)(\bm{\mu}_0 - \bm{\mu}_1)^\mathrm{T} \bm{w}} {\bm{w}^\mathrm{T}(\bm{\Sigma}_0+\bm{\Sigma}_1)\bm{w}}. \end{aligned} \tag{3.32}$$

注意到分子和分母都是关于 $\bm{w}$ 的二次项，因此解与 $\bm{w}$ 的长度无关，只与其方向有关．