(机器学习) – 读书笔记(基础)

  1. 基于数据构建统计模型从而对数据进行预测和分析。统计学习可由监督学习、非监督学习、半监督学习和强化学习等组成。
  2. 分类任务输出的是离散的值;回归任务输出的连续的值

监督学习

监督学习主要由模型、策略和算法组成。他的任务是学习一个模型,能够对任意一个给定的输入,对其给定一个合理的预测的输出。(是不是像一个函数?)

假设空间

监督学习的目的在于学习一个从输入到输出的映射,这个映射由模型来表示,学习的目的就是找到一个最好的模型。模型属于由输入空间到输出空间的映射集合,这个集合就是假设空间。监督学习可以学习概率模型和非概率模型,分别由条件概率$P(Y|X)$和决策函数$Y=f(X)$表示。

问题的形式化

给定一个训练集

$$T=\left\{(\mathbf{x}_1,y_1),\cdots,(\mathbf{x}_i,y_i)\right\}$$

$(\mathbf{x}_i,y_i),\quad i=1,2,\cdots,N$是一个样本点, $\mathbf{x}_i\in\mathcal{X}\subset\textbf{R}^n$是输入的观测值。$y_i\in\mathcal{Y}$是输出的观测值. 在监督学习中训练数据和测试数据是依据联合概率分布$P(X,Y)$独立同分布产生的. 学习过程中,模型使用预测的模型$\hat{P}(Y|X)$或者决策函数$Y=\hat{f}(X)$, 这个条件概率分布描述了输入与输出随机变量之间的映射关系. 衡量模型和真实的数据的标准之一就是预测的输出与实际的标签$y_i$d的误差较小

统计学习方法三要素

模型

模型的假设空间用$\mathcal{F}$表示, 假设空间可以定义为决策函数的集合:

$$\mathcal{F}=\{f|Y=f(X)\}$$

X 和 Y 都是定义在输入空间和输出空间的变量. $\mathcal{F}$是一个由参数向量决定的函数族:

$$\mathcal{F}=\{Y=f_\theta(X),\theta\in\textbf{R}^n\}$$

或者假设空间也能定义为条件概率的集合

$$\mathcal{F}=\{P|P(Y|X)\}$$

则相应的函数族变为:

$$\mathcal{F}=\{P|P_\theta(Y|X),\theta\in\textbf{R}^n\}$$

向量$\theta$取决于n为欧式空间$\textbf{R}^n$, 称为参数空间.

策略

指导如何学习一个最优模型, 所以需要引入损失函数.

损失函数

记为$L(Y,f(X))$作为度量学习的模型的在样本上的输出与实际的输出的方法, 常见的有:

  1. 0-1 损失函数:

$$L(Y,f(X))=\left\{ \begin{array}{ll} 1, & Y\neq f(X)\\ 0, & Y= f(X) \end{array} \right.$$

  1. 平方损失函数:

$$L(Y,f(X))=(Y-f(X))^2$$

  1. 绝对损失函数:

$$L(Y,f(X))=|Y-f(X)|$$

  1. 对数似然损失函数:

$$L(Y,P(Y|X))=-\log P(Y|X)$$
我们希望误差越小. 由于模型的输入和输出$(X,Y)$是随机变量, 遵循联合分布$P(X,Y)$, 所以期望损失(expected loss):$$R_\text{exp}(f)=E_P[L(Y,f(X))]=\int_{\mathcal{X}\times\mathcal{Y}}L(y,f(\mathbf{x}))P(x,y)d\mathbf{x}dy$$

但是我们目前不知道分布$P(X,Y)$所以无法直接计算$R_\text{exp}(f)$, 但是如果知道了分布,就可以计算条件概率分布$P(Y|X)$退而求其次,计算前$N$个样本的经验风险(empirical risk):

$$R_\text{emp}(f)=\frac{1}{N}\sum_{i=1}^N L(y_i,f(\mathbf{x}_i))$$

经验风险是基于有限的N个样本的估计, 根据大数定律, $R_\text{emp}(f)$会趋于$R_\text{exp}(f)$. 但是样本有限, 所以估计的结果并不好.

经验风险最小化和结构风险最小化

  • 经验风险最小化(empirical risk minimization, ERM)我们需要减小损失:

$$\begin{equation}\min_{f\in\mathcal{F}}\frac{1}{N}\sum_{i=1}^NL(y_i,f(x_i))\label{erm_min}\end{equation}$$

$\mathcal{F}$是假设空间. 在样本容量很小, 经验风险最小化的学习效果未必好, 会产生过拟合的现象.

  • 结构风险最小化(structural risk minimization)为了解决过拟合的现象, 则在 ERM 后加上一个正则项

$$R_\text{srm}(f)=\frac{1}{N}\sum_{i=1}^NL(y_i,f(x_i))+\lambda J(f)$$

$J(f)$为模型的复杂度, 是定义在空间$\mathcal{F}$的泛函, 与模型$f$的复杂度成正比. $\lambda\geq0$ 用来权衡经验风险和模型复杂度. 结构风险小的模型需要经验风险和模型复杂度同时小, 这种模型能够很好地对训练时据以及位置的测试数据有很好的预测. 所以要优化的问题就是

$$\begin{equation}\min_{f\in\mathcal{F}}\frac{1}{N}\sum_{i=1}^NL(y_i,f(x_i))+\lambda J(f)\label{srm_min}\end{equation}$$

$\eqref{erm_min}$和$\eqref{srm_min}$都是要解决的最优化问题.

算法

算法是学习模型的具体计算方法. 统计学习问题可以归结为最优化问题, 统计学习的算法称为求解最优问题的算法. 如果这个问题不能求出显式的解析解, 就需要利用数值计算的方法求解. 同时, 需要找到全局最优解, 避免占到局部最优解.

模型评估与模型选择

训练误差和测试误差

当损失函数给定时, 模型的训练误差和测试误差称为评估的标准:

$N$个样本的平均损失:

$$R_\text{emp}(\hat{f})=\frac{1}{N}\sum_{i=1}^NL(y_i,\hat{f}(\mathbf{x}_i))$$

测试误差时, 模型$Y=\hat{f}(X)$容量为$N\prime$的测试集的平均损失:

$$e_\text{test}=\frac{1}{N\prime}\sum_{i=1}^{N\prime}L(y_i,\hat{f}(\mathbf{x}_i))$$

测试误差能够反应学习方法对未知数据集的预测能力, 这个能力也成为泛化能力(generalization ability)

过拟合和模型选择

模型的复杂度与训练的误差和测试误差的关系.

在深度学习中, 使用更为复杂的模型就有可能带来过拟合.

为了防止过拟合, 可采用如下的办法选择复杂度适当的模型:

正则化和交叉验证

正则化

参考公式$\eqref{srm_min}$, 正则化项$\lambda J(f)$可以取不同的形式:

参数向量$\textbf{w}$

  • 回归问题, 损失函数是平方损失, 正则化项是参数向量的$L_2$范数:

$$L(w)=\frac{1}{N}\sum_{i=1}^N(f(\mathbf{x}_i;w)-y_i)^2+\frac{\lambda}{2}||\textbf{w}||^2$$
正则项符合奥卡姆剃刀原理(Occam's razor): 在所有可选择的模型中, 能够很好地解释已知数据并且十分简单的模型应该是应选的模型. 从贝叶斯估计的角度来看, 正则化对应于模型的先验概率, 可以假设复杂的模型有较大的先验概率, 简单的模型有较小的先验概率. 这个原则也可以帮我们在众多的匹配的模型中选择最简单的模型, 这个也就是归纳偏好. 如果没有对于一个偏好, 算法会选出时好时坏的模型.

例如, 曲线A相对于曲线B能够更简单地描述样本点, 那么我们的算法就有可能偏好于选择曲线A所描述的模型. 归纳偏好对应了学习算法本身所做出的"什么样的模型更好"的假设. 在具体的问题中, 这个假设是否成立, 大多数时决定了算法能否取得好的性能. 由于没有免费午餐定理(No Free Lunch, NFL), 脱离实际的问题, 空泛地谈论"那种学习算法更好"没有意义, 因为若考虑的所有的潜在的问题, 则算有的学习算法都一样的好, 有的看似银色子弹的算法甚至可能不如胡乱猜测的算法.

交叉验证

将数据分为训练集(training set)、验证集(validation set)和测试集(test set)

  • 简单交叉验证

随机地将数据分为互斥地训练集和测试集. 训练集在不同的参数个数下训练模型, 从而得到不同的模型; 在测试集上评价各个模型的测试误差, 选择误差最小者.

  • k折交叉验证(k-ford cross validation)

随机将数据集集$D$拆分为$k$个大小相似的互斥子集$D=D_1\cup D_2\cup\cdots\cup D_k, D_i\cap D_j=\emptyset(i\neq j)$, 这样每次可以进行$k$次训练/测试. 然后返回的结果取均值. 例如$k=10$的情况:

  • 留一交叉验证

如果$k=N$, 那么每个组只有一个数据, 也就是每一个训练集仅仅相对于源数据集$D$少了一个样本. 这个方法中被实际评估的模型与期望的用$D$训练的模型很相似. 留一交叉验证的结果往往很准确, 但是计算的开销与$N$正相关. 同时 NFL 定理也能用于验证的方法

自助法(bootstrapping)

为了权衡因为拆分训练集和测试集造成的规模不同所导致的估计偏差以及留一交叉验证的计算复杂度太大的问题, 自助法每次都从数据集$D$, 采样产生数据集$D\prime$: 每次随机地从$D$中选取一个样本拷贝地放入$D\prime$, 然后放回$D$. 重复$m$次就得到了容量为$m$的$D\prime$. 可以估计每个样本在$N$次被不采样的概率为$(1-\frac{1}{m})^m$, 取极限得到:

$$\lim_{m\to\infty}(1-\frac{1}{m})^m\to\frac{1}{e}\approx0.368$$

初始数据集$D$约有36.8%的样本没有出现在$D\prime$. 可以将$D\prime$作为训练集, $D\setminus{D}\prime$作为测试集. 自助法改变了数据集的分布, 这会引入估计偏差.

性能度量

假设学到的模型$\hat{f}$, 用这个模型对未知数据的预测的误差即为泛化误差(generalization error)

$$R_\text{exp}(\hat{f})=E_P[L(Y,\hat{f}(X))]=\int_{\mathcal{X}\times\mathcal{Y}}L(y,\hat{f}(\mathbf{x}))P(x,y)d\mathbf{x}dy$$

如果一种方法学习的模型比另外一种方法学习的模型具有更小的泛化误差, 那么这种方法更加有效.

错误率与精度

对于样本集$D$, 分类的错误率定义为:

$$E(\hat{f};D)=\frac{1}{m}\sum_{i=1}^m\mathbb{I}(\hat{f}(\mathbf{x}_i)\neq y_i)$$

精度定义为:

$$\begin{aligned}
& \text{acc}(\hat{f};D)=\frac{1}{m}\sum_{i=1}^m\mathbb{I}(\hat{f}(\mathbf{x}_i)=y_i)\\
& = 1-E(\hat{f};D)
\end{aligned}$$

更一般的, 对于数据分布$\mathcal{D}$和概率密度函数$p(\cdot)$, 错误率和精度可描述为:

$$E(\hat{f};D)=\int_{x\sim\mathcal{D}}\mathbb{I}(\hat{f}(\mathbf{x})\neq y)p(\mathbf{x})d\mathbf{x}$$

准确率:

$$\begin{aligned}
&\text{acc}=\int_{x\sim\mathcal{D}}\mathbb{I}(\hat{f}(\mathbf{x})=y)p(\mathbf{x})d\mathbf{x}\\
& = 1-E(\hat{f};D)
\end{aligned}$$

查准率、查全率与F1

查准率(precision)与查全率(亦称召回率, recall)能够很好的解答在 Web搜索中诸如"检索的信息中有多少比例是用户感兴趣的"等问题.

对于二分类问题, 可将样本根据真实标记划分为真正例(true positive)、假正例(false positive)、真反例(true negative)和假反例(false negative), 令$TP\text{、}FP\text{、}TN\text{、}FN$分别表示对应类别的数量, 其混淆矩阵:

真实情况 预测结果-正例 预测结果-反例
正例 TP FN
反例 FP TN

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

这两个标准是一个矛盾的度量. 例如希望将好瓜尽可能多地选出来, 可以通过增加选瓜的数量, 假设把所有的瓜都选上, 所有的好瓜必然被选上了, 但是查准率就较低;如果只选择有把我的好瓜, 就会漏掉不少好瓜, 这样查全率就较低.

对学习器的预测结果对样例排序, 排在前的最可能是正例的样本, 排在最后被认为是最不可能的正例样本. 按照顺序逐个把样本作为正例进行预测, 则每次可计算$R\text{和}P$:

可以看到学习器A 完全包住了学习器C, 所以学习器A 的性能优于学习器C. 但是学习器A和学习器B孰优孰劣可以通过F1度量进行判断.

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

如果希望对查全率和查准率的重视程度有所不同. 引入更一般的F1度量形式$F_\beta$

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

其中$\beta=\frac{\text{查全率}}{\text{查准率}}=\frac{R}{P}$. 其比值反映了用户对于查全率/查准率的偏好.

对于多分类(可以视为多次二分类, 每一次都会选取一个不同的正例). 记下每次二分类的查准率和查全率:$(P_1,R_1),\cdots,(P_n,R_n)$再计算平均值, 得到"宏查准率"(macro-P)、"宏查全率"(macro-R)以及"宏F1"(marco-F1). $n$个二分类器:

$$\text{macro-P}=\frac{1}{n}\sum_{i=1}^n{P_i}$$
$$\text{macro-R}=\frac{1}{n}\sum_{i=1}^n{R_i}$$
$$\text{macro-F1}=\frac{2\times{\text{macro-P}}\times{\text{macro-R}}}{{\text{macro-P}}+{\text{macro-R}}}$$

同时可以将各个混淆矩阵的对应元素进行平均, 得到$TP\text{、}FP\text{、}TN\text{、}FN$的平均值$\overline{TP}\text{、}\overline{FP}\text{、}\overline{TN}\text{、}\overline{FN}$, 在基于平均值计算"微查准率"(micro-P)、"微查全率"(micro-R)以及"微F1"(micro-F1):

$$\text{micro-P}=\frac{\overline{TP}}{\overline{TP}+\overline{FP}}$$
$$\text{micro-R}=\frac{\overline{TP}}{\overline{TP}+\overline{FN}}$$
$$\text{micro-F1}=\frac{2\times{\text{micro-P}}\times{\text{micro-R}}}{{\text{micro-P}}+{\text{micro-R}}}$$

ROC与AUC

有的时候, 神经网络输出的是一个概率, 判断是否是正例还是反例需要通过一个阈值(threshold)进行比较, $p\leq\text{threshold}$为反例, 其余为正例. 如果将最可能的正例排在前面, 最普可能的正例排在后面. 分类的过程就相当于在这个排序中以某一个截断点(cut point)将样本分为两个部分, 前一部分分为正例, 后一部分为反例. 若更重视查准率, 则可以选择排序中靠前未知进行阶段;若更重视查全率, 则可以选择靠后的位置进行阶段. 排序本身的质量好坏, 体现了综合考虑学习器在不同任务下的"期望泛化性能"的好坏. ROC(Receiver Operating Characteristic)曲线就能从这个角度出发研究学习器的泛化性能. 曲线的纵轴是真正例率(True Positive Rate, TPR), 横轴是假正例率(False Positive Rate, FPR):

$$\text{TPR}=\frac{TP}{TP+FN}$$
$$\text{FPR}=\frac{FP}{TN+FP}$$

在a图中, 对角线对应了随机猜测模型, 点(0,1)则对应于将所有正例排在所有反例之前的理想模型. 但是如果样本有限, 可以绘制如图b的基于有限样本的ROC曲线: 给定$m^+$个正例和$m^-$个反例, 根据学习器的结果对样例排序, 然后把分类的阈值设为最大, 即把所有的样例均预测为分离, 此时真正例率和假正例率均为0, 在坐标$(0,0)$标出. 然后, 将分类阈值依次设置每个样例的预测值, 即一次将每个样例划分为正例. 设前一个坐标为$(x,y)$, 若当前为真正例, 则对应的新坐标为$(x, y+\frac{1}{m^+})$;若当前为假正例, 则坐标为$(x+\frac{1}{m^-}, y)$, 连接即可.

如果学习器A的ROC曲线包含了学习器B, 那么学习器A的性能优于后者. 如果曲线交叉, 那么可以计算 ROC 包含的面积, 即AUC(Area Under ROC Curve).

根据定义, AUC的面积:

$$\text{AUC}=\frac{1}{2}\sum_{i=1}^{m-1}(x_{i+1}-x_i)\cdot{(y_i+y_{i+1})}$$

形式化看, AUC考虑样本预测的排序质量, 因此他与排序的误差有关系. 给定$m^+$个正例和$m^-$个反例, 令$D^+$和$D^-$分别表示正、反例集合, 排序损失定义为:

$$\begin{equation}
\mathcal{l}_{\text{rank}}=\frac{1}{m^+m^-}\sum_{x^+\in{D^+}}\sum_{x^-\in{D^-}}(\mathbb{I}(f(x^+)<f(x^-))+\frac{1}{2}\mathbb{i}(f(x^+)=f(x^-)))\label{loss_auc_above} \end{equation}$$
$\mathcal{l}_{\text{rank}}$是对应ROC曲线之上的面积: 若一个正例在ROC曲线之上, 对应坐标为$(x,y)$, 则$x$是排序之前的反例所占的比例, 即假正例率, 因此有:

AUC=1-l_rank

例如阈值为0.8, 可以计算真正例率为

$$\text{TPR}=\frac{1}{0+2}=0.5$$
$$\text{FPR}=\frac{0}{2+0}=0$$

$m^+=2\text{,}m^-=2$, 按照公式$\eqref{loss_auc_above}$, $\mathcal{l}_\text{rank}=\frac{1}{4}(1+0+0.5\times{0}+0+0.5\times{0})=\frac{1}{4}$

则 AUC:

$$\text{AUC}=1-\frac{1}{4}=\frac{3}{4}=0.75$$

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

待续

比较检验

为了检验模型的泛化性, 通过实验评估(性能度量)是一种基于训练集的比较, 而非基于与训练集不同的测试集. 本届的讨论主要以错误率为性能度量, 记为$\epsilon$.

假设检验

泛化错误率$\epsilon$的学习器在一个样本的犯错概率为$\epsilon$; 测试错误率$\hat{\epsilon}$表示着$m$个测试样本中有$\hat\epsilon\times{m}$个被错误分类. 恰将$\hat{\epsilon}\times{m}$个样本误分类的概率:

$$P(\hat\epsilon;\epsilon) = \begin{pmatrix} m \\ \hat\epsilon\times m \end{pmatrix} \epsilon^{\hat\epsilon\times m}(1-\epsilon)^{m-\hat\epsilon\times m}
$$

由$\frac{\partial{P(\hat\epsilon;\epsilon)}}{\partial\epsilon}=0$可知, $P(\hat\epsilon;\epsilon)$在$\epsilon=\hat{\epsilon}$最大, $|\epsilon-\hat{\epsilon}|$增大时, $P(\hat\epsilon;\epsilon)$减小.

假设$H_0:\epsilon\leq\epsilon_0$, 则在$1-\alpha$的概率内所能观测到的最大错误率. $1-\alpha$反映了置信度(confidence). 计算方法:

$$\begin{aligned}
&\overline{\epsilon}=\max\epsilon \\
&\text{s.t.}\quad\sum_{i=\epsilon_0\times{m+1}}^m
\begin{pmatrix}
m\\
i\\
\end{pmatrix}
\epsilon^i(1-\epsilon)^{m-i}<\alpha
\end{aligned}
$$

在$\alpha$的显著度下,假设 $H_0:\epsilon\leq\epsilon_0$不能被拒绝,能以$1-\alpha$的置信度认为, 学习器的泛化错误率不大于$\epsilon_0$;否则假设被拒绝, 即在$\alpha$的显著度下可认为该学习器的泛化错误率大于$\epsilon_0$.

在很多的情况下, 我们并非做一次留出估计法, 而通过多次留出法交叉验证法等进行多次训练/测试, 这样就会得到多个测试错误率, 此时可用t检验(t-test). 假设k个错误率: $\hat{\epsilon_1},\cdots,\hat{\epsilon_k}$, 则平均错误率$\mu$和方差$\sigma^2$:

$$\mu=\frac{1}{k}\sum_{i=1}^k\hat{\epsilon_i}$$
$$\sigma^2=\frac{1}{k-1}\sum_{i=1}^k(\hat{\epsilon_i}-\mu)^2$$

考虑k个测试错误率可看作泛化错误率$\epsilon_0$的独立采样, 则变量:

$$\tau_t=\frac{\sqrt{k}(\mu-\epsilon_0)}{\sigma}$$

服从自由度为$k-1$的$t$分布($k=10$):

设假设$H_1:\mu=\epsilon_0$和显著度$\alpha$, 当测试的错误率为$\epsilon_0$时, 在$1-\alpha$的概率内能观测到最大错误率, 即临界值. 在双边(two-tailed)假设中, 如上图两边阴影部分各有$\frac{\sigma}{2}$的面积; 假定阴影部分范围为$[-\infty,t_{-\alpha/2}]$和$[t_{\alpha/2},\infty]$. 若平均错误率$\mu$与$\epsilon_0$之差$|\mu-\epsilon_0|$位于临界范围$[t_{-\alpha/2},t_{\alpha/2}]$内, 则假设$H_1$接受, 泛化错误率为$\epsilon_0$, 置信度为$1-\alpha$, 否则被拒绝.

交叉验证t检验

待续

NcNemar 检验

待续

Friedman 检验和 Nemenyi 后续检验

待续

方差与偏差

解释学习算法泛化性的重要工具. 算法在不同的训练集上学得的结果很可能不同, 即便训练集来自同一个分布. 即测试样本为$\textbf{x}$, $y_D$是$\textbf{x}$在数据集上的标记, $y$是$\textbf{x}$的真实标记. 预测输出为$f(\textbf{x};D)$为在模型$f$的关于$\textbf{x}$的输出. 以回归任务为例:

  • 预测输出

$$\overline{f}(\mathbf{x})=\mathbb{E}_D[f(\mathbf{x};D)]$$

  • 使用样本数相同的不同训练加产生的方差: 度量了同样大小的训练集的变动所导致的学习性能的变化,也就是数据扰动所造成的影响:

$$\text{var}(x) = \mathbb{E}_D [(f(x;D)- \bar f (x) )^2]$$

  • 噪声(数据集标记和真实标记的方差): 当前任务上任何学习算法所能达到的期望泛化误差的下界,即刻画了学习问题本身的难度:

$$\varepsilon^2 = \mathbb{E}_D [(y_D - y)^2]$$

对回归任务,泛化误差可通过“偏差-方差分解”拆解为:

$$E(f;D) = bias^2(\mathbf{x}) + var(\mathbf{x}) + \varepsilon^2$$

一般说来, 方差和偏差有冲突, 即偏差-方差窘境(bias-variance dilemma).

  • 若训练不充分, 学习器的拟合能力不强, 训练数据的燃动不足以使学习器产生显著变化, 偏差主导了泛化错误率
  • 若过于充足, 学习器拟合能力很强, 训练数据的轻微扰动会导致学习器显著地变化. 若训练数据自身的非全局的特性被学习器学习到, 则发生过拟合.

摘自

  1. 《机器学习》周志华 著,2016.1,清华大学出版社
  2. 《统计学习方法》李航 著,2012.3,清华大学出版社
  3. (CSDN) kingsam_ - AUC的计算方法
  4. (wangwlj's Blog)西瓜书《机器学习》学习笔记(2):比较检验与偏差方差

添加评论