机器学习基础笔记

  |     |   本文总阅读量:

版权声明:本文原创,转载请留意文尾,如有侵权请留言,谢谢

引言

  机器学习也学习了一段时间了,本文总结一些机器学习经常用的知识,做一些笔记。

机器学习基本三要素

  机器学习有基本三要素:模型,学习准则和优化算法。

模型

  机器学习的目标就是找到一个模型来近似真实映射函数 \(g(\boldsymbol{x})\) 或真实条件概率分布 \(p_{r}(y | \boldsymbol{x})\)。由于我们不知道它的具体形式,只能根据经验假设一个函数集合,即假设空间(Hypothesis Space) \(\mathcal{F}\),它通常为一个参数化的函数族,其中 \(\theta\) 是它的参数,\(d\) 是参数的数量:

\[ \mathcal{F}=\left\{f(\boldsymbol{x} ; \theta) | \theta \in \mathbb{R}^{d}\right\} \]

  我们需要通过观测其在训练集 \(\mathcal{D}\) 上的特性,从中选择一个理想的假设(Hypothesis) \(f^* \in \mathcal{F}\)

学习准则

  首先我们需要假设训练集 \(\mathcal{D}\) 是独立同分布(Identically and Independently Distributed, IID)的,即每个样本 \((\boldsymbol{x}, y) \in \mathcal{X} \times \mathcal{Y}\) 是从 \(\mathcal{X}\)\(\mathcal{Y}\) 的联合空间中按照某个未知分布 \(p_{r}(\boldsymbol{x}, y)\) 独立随机产生的,这里要求 \(p_{r}(\boldsymbol{x}, y)\) 必须是固定的,不会随时间变化,否则它本身可变的话,就无法通过这些数据进行学习。
  模型 \(f(\boldsymbol{x}\) 的好坏可以通过期望风险(Expected Risk)来衡量:

\[ \mathcal{R}(\theta)=\mathbb{E}_{(\boldsymbol{x}, y) \sim p_{r}(\boldsymbol{x}, y)}[\mathcal{L}(y, f(\boldsymbol{x} ; \theta))] \]

  其中 \(p_{r}(\boldsymbol{x}, y)\) 是真实的数据分布,\(\mathcal{L}(y, f(\boldsymbol{x} ; \theta))\) 为损失函数。

损失函数

  下面有几种常见的损失函数:

0-1 损失函数(0-1 Loss Function)

\[ \begin{aligned} \mathcal{L}(y, f(\boldsymbol{x} ; \theta)) &=\left\{\begin{array}{cc}{0} & {\text { if } y=f(\boldsymbol{x} ; \theta)} \\ {1} & {\text { if } y \neq f(\boldsymbol{x} ; \theta)}\end{array}\right.\\ &=I(y \neq f(\boldsymbol{x} ; \theta)) \end{aligned} \]

  它的缺点是不连续,导数为 0,难以优化。

平方损失函数(Quadratic Loss Function)

\[ \mathcal{L}(y, f(\boldsymbol{x} ; \theta))=\frac{1}{2}(y-f(\boldsymbol{x} ; \theta))^{2} \]

  它常用于回归任务中,一般不适用于分类问题。

交叉熵损失函数(Cross-Entropy Loss Function)

\[ \mathcal{L}(\boldsymbol{y}, f(\boldsymbol{x} ; \theta))=-\sum_{c=1}^{C} y_{c} \log f_{c}(\boldsymbol{x} ; \theta) \]

  它用来衡量两个费率分布它们之间的差异。

Hinge 损失函数(Hinge Loss Function)

\[ \begin{aligned} \mathcal{L}(y, f(\boldsymbol{x} ; \theta)) &=\max (0,1-y f(\boldsymbol{x} ; \theta)) \\ & \triangleq[1-y f(\boldsymbol{x} ; \theta)]_{+} \end{aligned} \]   其中 \([x]_{+}=\max (0, x)\)

风险最小化准则(Empirical Risk Minimization, ERM)

  一个好的模型应当有一个比较小的期望错误,但是因为我们不知道真实的数据分布和映射函数。实际上我们无法计算其期望风险,我们只能根据一个给定的数据集,计算经验风险(Empirical Risk),也就是在训练集上的平均损失:

\[ \mathcal{R}_{\mathcal{D}}^{e m p}(\theta)=\frac{1}{N} \sum_{n=1}^{N} \mathcal{L}\left(y^{(n)}, f\left(x^{(n)} ; \theta\right)\right) \]

  因此,一个切实可行的学习准则就是找到一组参数 \(\theta^*\) 使得经验风险最小,即:

\[ \theta^{*}=\underset{\theta}{\arg \min } \mathcal{R}_{\mathcal{D}}^{e m p}(\theta) \]

  训练数据少,噪声和模型能力强往往都会造成过拟合,为了解决过拟合,一般是在经验风险最小化的基础上再引入参数的正则化(Regularization)来限制模型能力,使其不要过度地最小化经验风险,这种准则就是结构经验风险最小化(Structure Risk Minimization, SRM):

\[ \begin{aligned} \theta^{*} &=\underset{\theta}{\arg \min } \mathcal{R}_{\mathcal{D}}^{s t r u c t}(\theta) \\ &=\underset{\theta}{\arg \min } \mathcal{R}_{\mathcal{D}}^{e m p}(\theta)+\frac{1}{2} \lambda\|\theta\|^{2} \\ &=\underset{\theta}{\arg \min } \frac{1}{N} \sum_{n=1}^{N} \mathcal{L}\left(y^{(n)}, f\left(x^{(n)} ; \theta\right)\right)+\frac{1}{2} \lambda\|\theta\|^{2} \end{aligned} \]

  这里 \(\|\theta\|^{2}\) 用的是 \(\ell_{2}\) 范数,也可以用 \(\ell_{1}\) 范数,它可以使得参数具有一定得稀疏性。从贝叶斯学习的角度来讲,正则化是假设了参数的先验分布,不完全依赖于训练数据。

优化算法

  在确定了训练集 \(\mathcal{D}\),假设空间 \(\mathcal{F}\) 和学习准则后,如何找到最优模型 \(f(\boldsymbol{x} ; \theta^*)\) 就成了一个最优化(Optimization)问题,有一些常见的数值优化方法。

梯度下降法(Gradient Descent)

  如果能利用凸优化中一些高效成熟的优化方法,例如共轭梯度和拟牛顿法,很多机器学习方法都倾向于选择合适的模型和损失函数来构造一个凸函数作为优化目标。但是许多模型例如神经网络的优化目标是非凸的,只能退而求其次找到局部最优解,其中最常用的就是梯度下降法:

\[ \begin{aligned} \theta_{t+1} &=\theta_{t}-\alpha \frac{\partial \mathcal{R}_{\mathcal{D}}(\theta)}{\partial \theta} \\ &=\theta_{t}-\alpha \cdot \frac{1}{N} \sum_{n=1}^{N} \frac{\partial \mathcal{L}\left(y^{(n)}, f\left(\boldsymbol{x}^{(n)} ; \theta\right)\right)}{\partial \theta} \end{aligned} \]

提前停止(Early Stop)

  为了防止过拟合,我们还可以使用早停机制,即在验证集上的错误率不再下降,就停止迭代。

随机梯度下降法(Stochastic Gradient Descent, SGD)

  之前的梯度下降法里,目标函数是整个训练集的风险函数,这种方式也称作批量梯度下降法(Batch Gradient Descent, BGD),这样的空间复杂度和时间复杂度都比较大,每次迭代计算开销也比较大。
  我们可以每次采样一个样本来计算损失函数并且更新参数,这就是 SGD:

\[ \theta \leftarrow \theta-\alpha \frac{\partial \mathcal{L}\left(\theta ; x^{(n)}, y^{(n)}\right)}{\partial \theta} \]

  实验表明,只要经过足够次数的迭代,SGD 就可以收敛到局部最优截。而且相比于 BGD,SGD 引入了随机噪声,当目标函数非凸时,反而可以使其逃离局部最优点。

小批量梯度下降法(Mini-Batch Gradient Descent)

  SGD 的缺点是每次只取一个样本,难以充分利用计算机的并行计算能力,因此可以每次采样一批小样本来计算损失函数更新参数,即:

\[ \theta_{t+1} \leftarrow \theta_{t}-\alpha \cdot \frac{1}{K} \sum_{(\boldsymbol{x}, y) \in \mathcal{I}_{t}} \frac{\partial \mathcal{L}(y, f(\boldsymbol{x} ; \theta))}{\partial \theta} \]

参数学习

  下面以一个简单的线性回归模型 \(f(\boldsymbol{x} ; \hat{\boldsymbol{w}})=\hat{\boldsymbol{w}}^{\mathrm{T}} \hat{\boldsymbol{x}}\) (其中 \({\boldsymbol{w}}^{\mathrm{T}}\) 为增广权重向量,\(\hat{\boldsymbol{x}}\) 为增广特征向量)为例,阐述四种不同的参数估计方法。

经验风险最小化

  因为模型输出都是连续的是数值,所以我们可以使用平方损失函数来衡量真实标签和预测标签之间的差异,经验风险定义为:

\[ \begin{aligned} \mathcal{R}(\boldsymbol{w}) &=\sum_{n=1}^{N} \mathcal{L}\left(y^{(n)}, f\left(\boldsymbol{x}^{(n)} ; \boldsymbol{w}\right)\right) \\ &=\frac{1}{2} \sum_{n=1}^{N}\left(y^{(n)}-\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}^{(n)}\right)^{2} \\ &=\frac{1}{2}\left\|\boldsymbol{y}-X^{\mathrm{T}} \boldsymbol{w}\right\|^{2} \end{aligned} \]

  \(\mathcal{R}(\boldsymbol{w})\) 是个关于 \(\boldsymbol{w}\) 的凸函数,可求偏导:

\[ \begin{aligned} \frac{\partial \mathcal{R}(\boldsymbol{w})}{\partial \boldsymbol{w}} &=\frac{1}{2} \frac{\partial\left\|\boldsymbol{y}-X^{\mathrm{T}} \boldsymbol{w}\right\|^{2}}{\partial \boldsymbol{w}} \\ &=-X\left(\boldsymbol{y}-X^{\mathrm{T}} \boldsymbol{w}\right) \end{aligned} \]

  令偏导数为 0,可得最优参数:

\[ \begin{aligned} \boldsymbol{w}^{*} &=\left(X X^{\mathrm{T}}\right)^{-1} X \boldsymbol{y} \\ &=\left(\sum_{n=1}^{N} \boldsymbol{x}^{(n)}\left(\boldsymbol{x}^{(n)}\right)^{\mathrm{T}}\right)^{-1}\left(\sum_{n=1}^{N} \boldsymbol{x}^{(n)} y^{(n)}\right) \end{aligned} \]

  这种求解线性回归参数的方法,也叫最小二乘法(Least Square Method, LSM)。注意,在最小二乘法中,\(X X^{\mathrm{T}} \in \mathbb{R}^{(d+1) \times(d+1)}\) 必须存在逆矩阵,即 \(X X^{\mathrm{T}}\) 是满秩的(\(rank(X X^{\mathrm{T}})=d+1\)),也就是 \(X\) 中的行向量之间是线性不相关的,即每一个特征都和其它特征不相关。\(X X^{\mathrm{T}}\) 当然也存在不可逆的情况,最常见的情况是样本数量 \(N\) 小于 特征数量 \(d + 1\),此时 \(X X^{\mathrm{T}}\) 的秩为 \(N\),这是会存在很多 \(\boldsymbol{w}^{*}\),可以使得 \(\mathcal{R}(\boldsymbol{w}^{*})=0\)。当 \(X X^{\mathrm{T}}\) 不可逆时,我们可以先通过 PCA 等方法先降维消除不同特征间的相关性,然后再使用最小二乘法来求解。
  或者也可以直接通过梯度下降法来求解,这种利用梯度下降法来估计参数的方法也称为最小均分(Least Mean Squares, LMS)算法:

\[ \boldsymbol{w} \leftarrow \boldsymbol{w}+\alpha X\left(\boldsymbol{y}-X^{\mathrm{T}} \boldsymbol{w}\right) \]

结构风险最小化

  最小二乘法要求特征之间相互独立,即保证 \(XX^{\mathrm{T}}\) 可逆,然后特征之间如果有较大的多重共线性(Multicollinearity),也会使 \(XX^{\mathrm{T}}\) 的逆在数值上无法精确计算,数据集 \(X\) 上的一些小的扰动就会导致 \((XX^{\mathrm{T}})^{-1}\) 发生大的改变,这样使得最小二乘法的计算变得很不稳定。

岭回归(Ridge Regression)

  因此,我们可以采用岭回归,给 \(XX^{\mathrm{T}}\) 的对角线元素都加上一个常数 \(\lambda\) 使得 \((XX^{\mathrm{T}} + \lambda I)\) 满秩,即它的行列式不为 0,最优参数为:

\[ \boldsymbol{w}^{*}=\left(X X^{\mathrm{T}}+\lambda I\right)^{-1} X \boldsymbol{y} \]

  岭回归的解也可以看作是结构风险最小化准则下的最小二乘法估计,目标函数为:

\[ \mathcal{R}(\boldsymbol{w})=\frac{1}{2}\left\|\boldsymbol{y}-X^{\mathrm{T}} \boldsymbol{w}\right\|^{2}+\frac{1}{2} \lambda\|\boldsymbol{w}\|^{2} \]

Lasso Regression

  利用 \(\ell_1\) 范数进行正则化,这就是 Lasso 回归:

\[ \mathcal{R}(\boldsymbol{w})=\frac{1}{2}\left\|\boldsymbol{y}-X^{\mathrm{T}} \boldsymbol{w}\right\|^{2}+\frac{1}{2} \lambda\|\boldsymbol{w}\|^{2}_1 \]

  它倾向于完全消除最不重要的特征的权重(即将它们设置为零),这导致稀疏模型,除了最重要的权重之外,所有权重都为零。这是一种自动执行特征选择的方法,如果您怀疑只有少数特征真正重要,这是很好的。当你不确定时,你应该更喜欢岭回归。

ElasticNet

  弹性网络介于 Ridge Regression 和 Lasso Regression 回归之间,它的正则项是两者正则项的简单混合,它提供了一个额外的超参数来调整两个正则项之间的关系:

\[ \mathcal{R}(\boldsymbol{w})=\frac{1}{2}\left\|\boldsymbol{y}-X^{\mathrm{T}} \boldsymbol{w}\right\|^{2}+\frac{1}{2} \lambda_1\|\boldsymbol{w}\|^{2} + \frac{1}{2} \lambda_2\|\boldsymbol{w}\|^{2}_1 \]

  ElasticNet 通常优于 Lasso,因为 Lasso 在某些情况下可能表现不稳定(当几个特征强烈相关或者有特征数多于训练实例时)。

最大似然估计(Maximum Likelihood Estimation, MLE)

  最小二乘法解决的是 \(\boldsymbol{x}\)\(y\) 存在未知的函数关系 \(y = h(\boldsymbol{x})\),然而还存在另外一种机器学习任务,它的条件概率 \(p(y|\boldsymbol{x})\) 服从某个未知分布,我们也可以从这个角度来进行参数估计。
  假设标签 \(y\) 是一个随机变量,它服从以均值为 \(f(\boldsymbol{x} ; \boldsymbol{w})=\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}\),方差为 \(\sigma^2\) 的高斯分布:

\[ \begin{aligned} p(y | \boldsymbol{x} ; \boldsymbol{w}, \sigma) &=\mathcal{N}\left(y ; \boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}, \sigma^{2}\right) \\ &=\frac{1}{\sqrt{2 \pi} \sigma} \exp \left(-\frac{\left(y-\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}\right)^{2}}{2 \sigma^{2}}\right) \end{aligned} \]

  参数 \(\boldsymbol{w}\) 在训练集 \(\mathcal{D}\) 上的似然函数(Likelihood)为:

\[ \begin{aligned} p(\boldsymbol{y} | X ; \boldsymbol{w}, \sigma) &=\prod_{n=1}^{N} p\left(y^{(n)} | \boldsymbol{x}^{(n)} ; \boldsymbol{w}, \sigma\right) \\ &=\prod_{n=1}^{N} \mathcal{N}\left(y^{(n)} ; \boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}^{(n)}, \sigma^{2}\right) \end{aligned} \]

  为了方便计算,取对数得到对数似然函数(Log Likelihood):

\[ \log p(\boldsymbol{y} | X ; \boldsymbol{w}, \sigma)=\sum_{n=1}^{N} \log \mathcal{N}\left(y^{(n)} ; \boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}^{(n)}, \sigma^{2}\right) \]

  MLE 就是找到一组参数 \(\boldsymbol{w}\) 使得似然函数 \(p(\boldsymbol{y} | X ; \boldsymbol{w}, \sigma)\) 最大,等价于对数似然然函数最大,令 \(\frac{\partial \log p(\boldsymbol{y} | X ; \boldsymbol{w}, \sigma)}{\partial \boldsymbol{w}}=0\) 得:

\[ \boldsymbol{w}^{M L}=\left(X X^{\mathrm{T}}\right)^{-1} X \boldsymbol{y} \]

  可以看出 MLE 的解实际上和最小二乘法的解相同。

最大后验估计(Maximum A Posteriori Estimation, MAP)

  假设参数 \(\boldsymbol{w}\) 是一个随机变量,并服从一个先验分布 \(p(\boldsymbol{w};\nu)\),简单起见,一般令 \(p(\boldsymbol{w};\nu)\) 为各向同性的高斯分布:

\[ p(\boldsymbol{w} ; \nu)=\mathcal{N}\left(\boldsymbol{w} ; \mathbf{0}, \nu^{2} I\right) \]

  其中 \(\nu^2\) 为每一维上的方差,根据贝叶斯公式,\(\boldsymbol{w}\) 的后验分布(Posterior Distribution)为:

\[ \begin{aligned} p(\boldsymbol{w} | X, \boldsymbol{y} ; \mathcal{V}, \sigma) &=\frac{p(\boldsymbol{w}, \boldsymbol{y} | X ; \nu, \sigma)}{\sum_{\boldsymbol{w}} p(\boldsymbol{w}, \boldsymbol{y} | X ; \nu, \sigma)} \\ & \propto p(\boldsymbol{y} | X, \boldsymbol{w} ; \sigma) p(\boldsymbol{w} ; \nu) \end{aligned} \]

  其中 \(p(\boldsymbol{y} | X, \boldsymbol{w} ; \sigma)\)\(\boldsymbol{w}\) 的似然函数。
  这种估计参数 \(\boldsymbol{w}\) 的后验概率分布的方法也称为贝叶斯估计(Bayesian Estimation),是一种统计推断问题,采用贝叶斯估计的线性回归也称为贝叶斯线性回归(Bayesian Linear Regression)。
  贝叶斯估计得到的是一个参数的区间估计,即参数在一个区间上的分布,如果我们需要得到一个最优的参数,即点估计,我们可以使用最大后验估计:

\[ \boldsymbol{w}^{M A P}=\underset{\boldsymbol{w}}{\arg \max } p(\boldsymbol{y} | X, \boldsymbol{w} ; \sigma) p(\boldsymbol{w} ; \nu) \]   令似然函数 \(p(\boldsymbol{y} | X, \boldsymbol{w} ; \sigma)\) 为之前我们定义的高斯密度函数,那么后验分布 \(p(\boldsymbol{w} | X, \boldsymbol{y} ; \nu, \sigma)\) 的对数为:

\[ \begin{aligned} \log p(\boldsymbol{w} | X, \boldsymbol{y} ; \nu, \sigma) & \propto \log p(\boldsymbol{y} | X, \boldsymbol{w} ; \sigma)+\log p(\boldsymbol{w} ; \nu) \\ & \propto-\frac{1}{2 \sigma^{2}} \sum_{n=1}^{N}\left(y^{(n)}-\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}^{(n)}\right)^{2}-\frac{1}{2 \nu^{2}} \boldsymbol{w}^{\mathrm{T}} \boldsymbol{w} \\ &=-\frac{1}{2 \sigma^{2}}\left\|\boldsymbol{y}-X^{\mathrm{T}} \boldsymbol{w}\right\|^{2}-\frac{1}{2 \nu^{2}} \boldsymbol{w}^{\mathrm{T}} \boldsymbol{w} \end{aligned} \]

  可以看出,最大后验概率等价于平方损失的结构方法最小化,正则系数为 \(\lambda = \frac{\sigma^2}{\nu^2}\)
  最大似然估计和贝叶斯估计可以看作是频率学派和贝叶斯学派对需要估计的参数 \(\boldsymbol{w}\) 的不同解释。当 \(\nu \to \infty\) 时,先验分布 \(p(\boldsymbol{w};\nu)\) 退化为均匀分布,称为无信息先验(Non-Information Prior),此时最大后验估计退化为最大似然估计。

偏差-方差分解

  对于一个机器学习算法,我们可以通过实验估计其泛化性能,但我们却不知道它为什么具有这样的性能,偏差-方差分解(Bias-Variance Decomposition)可以用来解释学习算法的泛化性能,偏差-方差分解试图对学习算法的期望泛化错误进行拆解。
  算法在不同训练集上学得的结果可能不同,即便这些训练集来自同一个分布,我们定义一些符号,记测试样本为\(x\)\(y_D\)\(x\)在数据集上的标记,\(y\)\(x\)的真实标记(有可能数据集上的标记出现错误,即\(y_D \neq y\)),\(f(x;D)\)为训练集\(D\)上学得模型\(f\)\(x\)上的预测输出,学习算法的期望预测为: \[ \overline{f}(x) = E_D[f(x;D)] \]   使用样本数相同的不同训练集产生的方差为: \[ var(x) = E_D[(f(x;D) - \overline{f}(x))^2] \]   方差度量了同样大小的训练集的变动所导致的学习性能的变化,即刻画了数据扰动所造成的影响。
  噪声为: \[ \epsilon = E_D[(y_D-y)^2] \]   噪声度量了在当前任务上任何学习算法所能达到的期望泛化误差的下界,即刻画了学习问题本身的难度。
  偏差(bias)为期望输出与真实标记的差别: \[ bias^2(x) = (\overline{f}(x)-y)^2 \]   偏差度量了学习算法的期望预测与真实结果的偏离程度,即刻画了学习算法本身的拟合能力。
  我们来对期望泛化误差进行分解,假定噪声期望为0(\(E_D[y_D-y]=0\)): \[ \begin{aligned} E(f ; D) &=E_{D}[(f(x;D)-y_{D})^{2}] \\ &= E_{D}[(f(x;D)-\overline{f}(x)+\overline{f}(x)-y_{D})^{2}] \\ &= E_{D}[(f(x;D)-\overline{f}(x))^{2}]+E_{D}[(\overline{f}(x)-y_{D})^{2}] + E_{D}[2(f(x;D)-\overline{f}(x))(\overline{f}(x)-y_{D})](因为\overline{f}(x) = E_D[f(x;D)]) \\ &= E_{D}[(f(x;D)-\overline{f}(x))^{2}]+E_{D}[(\overline{f}(x)-y_{D})^{2}] \\ &= E_{D}[(f(x;D)-\overline{f}(x))^{2}]+E_{D}[(\overline{f}(x)-y+y-y_{D})^{2}] \\ &= E_{D}[(f(x;D)-\overline{f}(x))^{2}]+E_{D}[(\overline{f}(x)-y)^{2}]+E_{D}[(y-y_{D})^{2}] + 2E_{D}[(\overline{f}(x)-y)(y-y_{D})](噪声期望为0,故该项为0) \\ &= E_{D}[(f(x;D)-\overline{f}(x))^{2}]+(\overline{f}(x)-y)^{2}+E_{D}[(y_{D}-y)^{2}] \\ &= var(x) + bias^2(x) + \epsilon^2 \end{aligned} \]   由此看来,泛化误差可以分解为偏差,方差与噪声之和。这说明了泛化性能是由学习算法的能力,数据的充分性以及学习任务本身的难度所共同决定的。
  给定学习任务,为了取得好的泛化性能,则需使偏差较小,即能够充分拟合数据,并且使方差较小,即使得数据扰动产生的影响小。但是一般来说,偏差与方差是有冲突的,也叫偏差-方差窘境(Bias-Variance Dilemma)。如下图所示,给定学习任务,假定我们能控制学习算法的训练程度:

  • 在训练不足时,学习器的拟合能力不够强,训练数据的扰动不足以使学习器产生显著变化,此时偏差主导了泛化错误率。
  • 随着训练程度的加深,学习器的拟合能力逐渐增强,训练数据发生的扰动渐渐能被学习器学到,方差逐渐主导了泛化错误率。
  • 在训练程度充足后,学习器的拟合能力己非常强,训练数据发生的轻微扰动都会导致学习器发生显著变化,若训练数据自身的、非全局的特性被学习器学到了,则将发生过拟合。

  此外,我们从这个角度理解下集成模型,它其实就是通过多个高方差模型的平均来降低方差。

评价指标

  机器学习中有许多评价指标,我们记录一些常见的评价指标。

均方误差(Mean Squared Error, MSE)

  对于回归任务,通常会用到均方误差: \[ E(f ; D)=\frac{1}{m} \sum_{i=1}^{m}\left(f\left(\boldsymbol{x}_{i}\right)-y_{i}\right)^{2} \]   利用PDF,更一般的形式为: \[ E(f ; \mathcal{D})=\int_{\boldsymbol{x} \sim \mathcal{D}}(f(\boldsymbol{x})-y)^{2} p(\boldsymbol{x}) \mathrm{d} \boldsymbol{x} \]

准确率(Accuracy)

  准确率定义为:

\[ \begin{aligned} \operatorname{acc}(f ; D) &=\frac{1}{m} \sum_{i=1}^{m} \mathbb{I}\left(f\left(\boldsymbol{x}_{i}\right)=y_{i}\right) \\ &=1-E(f ; D) \end{aligned} \]

  对于PDF,更一般的形式为:

\[ acc(f ; \mathcal{D}) = \int_{\boldsymbol{x} \sim \mathcal{D}} \mathbb{I}(f(\boldsymbol{x}) = y) p(\boldsymbol{x}) \mathrm{d} \boldsymbol{x} \]

错误率(Error Rate)

  错误率定义为:

\[ err(f ; D)=\frac{1}{m} \sum_{i=1}^{m} \mathbb{I}\left(f\left(\boldsymbol{x}_{i}\right) \neq y_{i}\right) \]

  对于PDF,更一般的形式为: \[ \operatorname{err}(f ; \mathcal{D}) =\int_{\boldsymbol{x} \sim \mathcal{D}} \mathbb{I}(f(\boldsymbol{x}) \neq y) p(\boldsymbol{x}) \mathrm{d} \boldsymbol{x} =1-acc(f ; \mathcal{D}) \]

查准率(Precision)与查全率(Recall)

  定义混淆矩阵(confusion matrix):

  查准率 \(P\)

\[ P=\frac{T P}{T P+F P} \]

  查全率 \(R\)

\[ R=\frac{T P}{T P+F N} \]

  这两者是相互矛盾的,通常用 PR 图来表示它们之间的关系:

  显然,如果一个学习器的曲线被另一个学习器的曲线完全包住,则说明后者的性能更好。如果不能包住,可以通过计算面积的方法。但是面积通常不太容易计算,所以可以采用平衡点(Break-Even Point, BEP)来比较,它是 \(P=R\) 的取值,越大性能越好。

\(F1\) 值(F1 Measure)

  BEP 有点过于简化,更通常的是使用 \(F1\) 度量:

\[ F 1=\frac{2 \times P \times R}{P+R}=\frac{2 \times TP}{样例总数 + TP -TN} \]

  如果想有所偏好的话,可以使用 \(F_{\beta}\)\(\beta \gt 1\) 时查全率更有影响,\(\beta \lt 1\) 时查准率更有影响:

\[ F_{\beta}=\frac{\left(1+\beta^{2}\right) \times P \times R}{\left(\beta^{2} \times P\right)+R} \]

  这两者实际都是调和平均(harmonic mean):

\[ \frac{1}{F 1}=\frac{1}{2} \cdot\left(\frac{1}{P}+\frac{1}{R}\right) \\ \frac{1}{F_{\beta}}=\frac{1}{1+\beta^{2}} \cdot\left(\frac{1}{P}+\frac{\beta^{2}}{R}\right) \]

  与算数平均 \(\frac{P+R}{2}\) 和几何平均 \(\sqrt{P + R}\) 相比,调和平均更重视较小值。

宏平均(Macro Average)

  如果执行多次分类任务,得到多个混淆矩阵,计算出了多个查准率与查全率 \((P_1,R_1),(P_2,R_2),\cdots,(P_n,R_n)\),计算它们的平均值,可以得到宏查全率,宏查准率,宏 \(F1\)

\[ \begin{array}{c}{\operatorname{macro-P}=\frac{1}{n} \sum_{i=1}^{n} P_{i}} \\ {\operatorname{macro-R}=\frac{1}{n} \sum_{i=1}^{n} R_{i}} \\ {\operatorname{macro-F} 1=\frac{2 \times \operatorname{macro-P} \times \operatorname{macro-R}}{\operatorname{macro-P}+\operatorname{macro-R}}}\end{array} \]

微平均(Micro Average)

  也可以先将混淆矩阵的对应元素求平均值,得到 \(TP, FP, TN, FN\) 的平均值 \(\overline{TP}, \overline{FP}, \overline{TN}, \overline{FN}\),再基于这些平均值计算出微查准率,微查全率和微\(F1\)\[ \operatorname{micro-P}=\frac{\overline{T P}}{\overline{T P}+\overline{F P}} \\ \operatorname{micro-R}=\frac{\overline{T P}}{\overline{T P}+\overline{F N}} \\ \operatorname{micro-F1}=\frac{2 \times \operatorname{micro-P} \times \operatorname{micro-R}}{\operatorname{micro-P}+\operatorname{micro-R}} \]

ROC

  很多学习器是为测试样本产生一个实值或概率预测,然后将这个预测值与一个分类阈值(threshold)进行比较,若大于阈值则分为正类,否则为反类。这个实值或概率预测结果的好坏,直接决定了学习器的泛化能力。实际上,根据这个实值或概率预测结果,我们可将测试样本进行排序,“最可能”是正例的排在最前面,“最不可能”是正例的排在最后面。这样,分类过程就相当于在这个排序中以某个截断点(cut point)将样本分为两部分,前一部分判作正例,后一部分则判作反例。在不同的应用任务中,我们可根据任务需求来釆用不同的截断点,例如若我们更重视“查准率”,则可选择排序中靠前的位置进行截断;若更重视“查全率”,则可选择靠后的位置进行截断。
  因此,排序本身的质量好坏,体现了综合考虑学习器在不同任务下的“期望泛化性能”的好坏,或者说,“一般情况下”泛化性能的好坏,ROC曲线则是从这个角度出发来研究学习器泛化性能的有力工具。
  ROC(Receiver Operating Characteristic)接收者操作特征曲线,是由二战中的电子工程师和雷达工程师发明用来侦测战场上敌军载具(飞机、船舰)的指标,属于信号检测理论。我们根据学习器的预测结果对样例进行排序,按此顺序逐个把样本作为正例进行预测,每次计算出两个重要量的值,分别以它们为横纵坐标作图,ROC曲线的横坐标是假正例率(False Positive Rate,FPR),纵坐标是真正例率(True Positive Rate, TPR),它们的计算方式如下:

\[ TPR = \frac{TP}{TP + FN} \\ FPR = \frac{FP}{TN + FP} \]

  容易理解一点,可以这么描述:

  • \(TPR\):真实的正例中,被预测正确的比例
  • \(FPR\):真实的反例中,被预测错误的比例

  我们举书中的一个示意图:

  左边圆滑的是处理过后的图,通常我们通过有限点绘制出的图如右边所示,那么它是怎么画出来的呢?
  绘图过程很简单:给定 \(m^+\) 个正例和 \(m^-\) 个反例,根据学习器预测结果对样例进行排序,然后把分类阈值设为最大,即把所有样例均预测为反例,此时真正例率和假正例率均为 0,在坐标 \((0, 0)\) 处标记一个点。然后,将分类阈值依次设为每个样例的预测值,即依次将每个样例划分为正例。设前一个标记点坐标为 \((x, y)\),当前若为真正例,则对应标记点的坐标为 \((x, y + \frac{1}{m^+})\)。当前若为假正例,则对应标记点的坐标为 \((x + \frac{1}{m^-}, y)\),然后用线段连接相邻点即得。

AUC

  进行学习器的比较时,与 PR 图相似,若一个学习器的 ROC 曲线被另一个学习器的曲线完全“包住”,则可断言后者的性能优于前者;若两个学习器的 ROC 曲线发生交叉,则难以一般性地断言两者孰优孰劣。此时如果一定要进行比较,则较为合理的判据是比较 RO C曲线下的面积,即 AUC (Area Under ROC Curve)。
  它可通过如下的积分公式估算出来:

\[ AUC = \frac{1}{2}\Sigma_{i=1}^{m-1}(x_{i+1}-x_i)(y_i+y_{i+1}) \]

  同时,我们也可以计算出排序的损失,然后用总的面积减去它算出 AUC:

\[ l_{rank}=\frac{1}{m^+m^-}\Sigma_{x^+ \in D^+}\Sigma_{x^- \in D^-}(I(f(x^+) \lt f(x^-)) + \frac{1}{2}I(f(x^+) = f(x^-))) \\ AUC = 1 - l_{rank} \]

  即考虑每一对正、反例,若正例的预测值小于反例,则记一个“罚分”,若相等,则记0.5个“罚分”。容易看出,对应的是R〇C曲线之上的面积:若一个正例在ROC曲线上对应标记点的坐标为 \((x, y)\) ,则 \(x\) 恰是排序在其之前的反例所占的比例,即假正例率。

意义

  那么与简单的 PR 图相比,AUC 的意义是什么呢,我们举一个极端的例子:一个二类分类问题一共 10 个样本,其中 9 个样本为正例,1 个样本为负例,在全部判正的情况下准确率将高达 90%,而这并不是我们希望的结果,尤其是在这个负例样本得分还是最高的情况下,模型的性能本应极差,从准确率上看却适得其反。而 AUC 能很好描述模型整体性能的高低。这种情况下,模型的 AUC 值将等于 0。

例子

  我们来举几个例子来理解下,现在假设有一个训练好的二分类器对 10 个正负样本(正例 5 个,负例5 个)预测,得分按高到低排序得到的最好预测结果为\([1, 1, 1, 1, 1, 0, 0, 0, 0, 0]\),即 5 个正例均排在 5 个负例前面,正例排在负例前面的概率为 100%。然后绘制其 ROC 曲线,由于是 10 个样本,除开原点我们需要描 10 个点,如下:

  我们可以看出AUC的面积为 1,上图的 AUC 等于 1,印证了正例排在负例前面的概率的确为 100%。
  我们再看个例子,预测结果为 \([1, 1, 1, 1, 0, 1, 0, 0, 0, 0]\)

  计算上图的 AUC 为 0.96,与计算正例排在负例前面的概率 \(0.8 × 1 + 0.2 × 0.8 = 0.96\) 相等,而左上角阴影部分的面积则是负例排在正例前面的概率 \(0.2 × 0.2 = 0.04\)
  再看个例子,预测结果序列为 \([1, 1, 1, 0, 1, 0, 1, 0, 0, 0]\)

  计算上图的 AUC 为 0.88,与计算正例排在负例前面的概率 \(0.6 × 1 + 0.2 × 0.8 + 0.2 × 0.6 = 0.88\) 相等,左上角阴影部分的面积是负例排在正例前面的概率 \(0.2 × 0.2 × 3 = 0.12\)
  最后看一个例子,也就是我们之前讲的情况,预测结果为 \([0, 1, 1, 1, 1, 1, 1, 1, 1, 1]\)

PAC 可学习

  计算学习理论(Computation Learning Theory)是关于机器学习的理论基础,其中最基础的理论就是可能近似正确(Probably Approximately Correct, PAC)。
  泛化错误(Generalization Error)是指期望错误和经验错误之间的差异。即:

\[ \mathcal{G}_{\mathcal{D}}(f)=\mathcal{R}(f)-\mathcal{R}_{\mathcal{D}}^{e m p}(f) \]

  根据大数定律,当训练集大小趋于无穷时,泛化错误趋向于 0,即经验风险趋近于期望风险:

\[ \lim _{|\mathcal{D}| \rightarrow \infty} \mathcal{R}(f)-\mathcal{R}_{\mathcal{D}}^{e m p}(f)=0 \]

  由于我们不知道真实的数据分布 \(p(\boldsymbol{x},y)\),也不知道真是的目标函数 \(g(\boldsymbol{x})\),因此期望从有限的训练样本上学习到一个期望错误为 0 的函数 \(f(\boldsymbol{x})\) 是不切实际的,因此我们只要求学习算法可以以一定的概率学习到一个近似正确的假设即可,这就是 PAC 可学习,它有两个部分:

  • 近似正确(Approximately Correct):一个假设 \(f \in \mathcal{F}\) 是近似正确的,是指它的泛化错误小于一个界限 \(\epsilon(1 \lt \epsilon \lt \frac{1}{2})\)
  • 可能(Probably):一个学习算法 \(\mathcal{A}\) 有可能以 \(1 - \delta(1 \lt \delta \lt \frac{1}{2})\) 的概率学习到一个近似正确的假设。

  一个 PAC 可学习的算法是指该学习算法能够在多项式时间内从合理数量的训练数据中学习到一个近似正确的 \(f(\boldsymbol{x})\)

\[ P\left(\left(\mathcal{R}(f)-\mathcal{R}_{\mathcal{D}}^{e m p}(f)\right) \leq \epsilon\right) \geq 1-\delta \]

  其中 \(\epsilon,\delta\) 是和样本数量 \(N\) 以及假设空间 \(\mathcal{F}\) 有关的变量,如果固定 \(\epsilon,\delta\),可以反过来计算出需要的样本数量:

\[ N(\epsilon, \delta) \geq \frac{1}{2 \epsilon^{2}}\left(\log |\mathcal{F}|+\log \frac{2}{\delta}\right) \]

  因此从 PAC 可学习的角度,我们也可以看出,模型越复杂,及假设空间的大小 \(|\mathcal{F}|\) 越大,模型的泛化能力就越差,要达到相同的泛化能力,越复杂的模型就需要越多的样本。

Refer

相关内容


坚持原创技术分享,您的支持将鼓励我继续创作,π(3.14)元就够啦!



文章目录
  1. 1. 引言
  2. 2. 机器学习基本三要素
    1. 2.1. 模型
    2. 2.2. 学习准则
      1. 2.2.1. 损失函数
        1. 2.2.1.1. 0-1 损失函数(0-1 Loss Function)
        2. 2.2.1.2. 平方损失函数(Quadratic Loss Function)
        3. 2.2.1.3. 交叉熵损失函数(Cross-Entropy Loss Function)
        4. 2.2.1.4. Hinge 损失函数(Hinge Loss Function)
      2. 2.2.2. 风险最小化准则(Empirical Risk Minimization, ERM)
    3. 2.3. 优化算法
      1. 2.3.1. 梯度下降法(Gradient Descent)
        1. 2.3.1.1. 提前停止(Early Stop)
      2. 2.3.2. 随机梯度下降法(Stochastic Gradient Descent, SGD)
      3. 2.3.3. 小批量梯度下降法(Mini-Batch Gradient Descent)
  3. 3. 参数学习
    1. 3.1. 经验风险最小化
    2. 3.2. 结构风险最小化
      1. 3.2.1. 岭回归(Ridge Regression)
      2. 3.2.2. Lasso Regression
      3. 3.2.3. ElasticNet
    3. 3.3. 最大似然估计(Maximum Likelihood Estimation, MLE)
    4. 3.4. 最大后验估计(Maximum A Posteriori Estimation, MAP)
  4. 4. 偏差-方差分解
  5. 5. 评价指标
    1. 5.1. 均方误差(Mean Squared Error, MSE)
    2. 5.2. 准确率(Accuracy)
    3. 5.3. 错误率(Error Rate)
    4. 5.4. 查准率(Precision)与查全率(Recall)
    5. 5.5. \(F1\) 值(F1 Measure)
    6. 5.6. 宏平均(Macro Average)
    7. 5.7. 微平均(Micro Average)
    8. 5.8. ROC
    9. 5.9. AUC
      1. 5.9.1. 意义
      2. 5.9.2. 例子
  6. 6. PAC 可学习
  7. 7. Refer
  8. 8. 相关内容
您是第 位小伙伴 | 本站总访问量 | 已经写了 670.5k 字啦

载入天数...载入时分秒...