机器学习

机器学习三个基本要素

模型

​ 输入空间 𝒳 和输出空间 𝒴 构成了一个样本空间 . 对于样本空间中的样本样本的特征空间 $(𝒙, 𝑦) ∈ 𝒳 × 𝒴 $， 假定 𝒙 和 𝑦 之间的关系可以通过一个未知的真实映射函数 $𝑦 =𝑔(𝒙) $或真实条件概率分布$ 𝑝_𝑟 (𝑦|𝒙) $来描述 . 机器学习的目标是找到一个模型来近似真实映射函数$ 𝑔(𝒙) $或真实条件概率分布$ 𝑝_𝑟 (𝑦|𝒙)$.

​ 根据经验来假设一个函数集合 ℱ ， 称为假设空间（ Hypothesis Space ），然后通过观测其在训练集 𝒟 上的特性， 从中选择一个理想的假设（ Hypothesis ）𝑓 ^∗^ ∈ ℱ.
​ 假设空间 ℱ 通常为一个参数化的函数族

其中 𝑓(𝒙; 𝜃) 是参数为 𝜃 的函数，也称为模型（ Model ），𝐷 为参数的数量 .常见的假设空间可以分为线性和非线性两种， 对应的模型 𝑓 也分别称为线性模型和非线性模型 .

线性模型

​ 线性模型的假设空间为一个参数化的线性函数族，即：

其中参数 𝜃 包含了权重向量 𝒘 和偏置 𝑏.

非线性模型

​ 广义的非线性模型可以写为多个非线性基函数 𝜙(𝒙) 的线性组合：

其中$ 𝜙(𝒙) = [𝜙_1 (𝒙), 𝜙_2 (𝒙), ⋯ , 𝜙_𝐾 (𝒙)]^T $为 𝐾 个非线性基函数组成的向量， 参数 𝜃包含了权重向量 𝒘 和偏置 𝑏.
如果 𝜙(𝒙) 本身为可学习的基函数，比如:
$$
𝜙_𝑘 (𝒙) = ℎ(𝒘^T_𝑘 𝜙 ′ (𝒙) + 𝑏_𝑘 ), ∀1 ≤ 𝑘 ≤ 𝐾, (2.8)
$$

其中 ℎ(⋅) 为非线性函数， 𝜙 ′ (𝒙) 为另一组基函数， $𝒘_𝑘 和 𝑏_𝑘 $为可学习的参数，则$𝑓(𝒙;𝜃)$ 就等价于神经网络模型 .

学习准则

​ 令训练集$ 𝒟 = {(𝒙^{(𝑛)} , 𝑦^{(𝑛)} )}^𝑁_𝑛=1 $是由 𝑁 个独立同分布（ Identically and Inde-pendently Distributed ， IID ）的样本组成， 即每个样本 (𝒙, 𝑦) ∈ 𝒳 × 𝒴 是从 𝒳 和 𝒴的联合空间中按照某个未知分布$𝑝_𝑟 (𝒙, 𝑦)$ 独立地随机产生的 . 这里要求样本分布$𝑝_𝑟 (𝒙, 𝑦)$ 必须是固定的（虽然可以是未知的）， 不会随时间而变化 . 如果$𝑝_𝑟 (𝒙, 𝑦)$ 本身可变的话，就无法通过这些数据进行学习 .

​ 一个好的模型$ 𝑓(𝒙, 𝜃^∗ ) $应该在所有 (𝒙, 𝑦) 的可能取值上都与真实映射函数𝑦 = 𝑔(𝒙) 一致， 即：

​ 或与真实条件概率分布 $𝑝_𝑟 (𝒙, 𝑦)$ 一致，即：

其中 𝜖 是一个很小的正数，$𝑓_𝑦 (𝒙, 𝜃 ) $为模型预测的条件概率分布中 𝑦 对应的概率 .

​ 模型 𝑓(𝒙; 𝜃) 的好坏可以通过期望风险（ Expected Risk ） ℛ(𝜃) 来衡量， 其定义为：

​ 其中 $𝑝_𝑟 (𝒙, 𝑦)$ 为真实的数据分布，$ ℒ(𝑦, 𝑓(𝒙; 𝜃)) $为损失函数， 用来量化两个变量之间的差异 .

损失函数

损失函数是一个非负实数函数， 用来量化模型预测和真实标签之间的差异 .下面介绍几种常用的损失函数 .

• 0-1 损失函数 最直观的损失函数是模型在训练集上的错误率，即 0-1 损失函数（ 0-1 Loss Function ）：

其中 𝐼(⋅) 是指示函数 .

虽然 0-1 损失函数能够客观地评价模型的好坏， 但其缺点是数学性质不是很好： 不连续且导数为 0 ，
难以优化 . 因此经常用连续可微的损失函数替代 .

• 平方损失函数 平方损失函数（ Quadratic Loss Function ）经常用在预测标签 𝑦为实数值的任务中，
  定义为：

​ 平方损失函数一般不适用于分类问题 .

• 交叉熵损失函数 交叉熵损失函数（ Cross-Entropy Loss Function ）一般用于分类问题 . 假设样本的标签 𝑦 ∈ {1, ⋯ 𝐶} 为离散的类别， 模型 $𝑓(𝒙; 𝜃) ∈ [0, 1]^𝐶 $的输出为类别标签的条件概率分布，即：

并满足:

​ 我们可以用一个 𝐶 维的 one-hot 向量 𝒚 来表示样本标签 . 假设样本的标签为𝑘 ， 那么标签向量 𝒚 只有第 𝑘 维的值为 1 ， 其余元素的值都为 0. 标签向量 𝒚 可以看作是样本标签的真实概率分布， 即第 𝑐 维（记为 $𝑦_𝑐 ， 1 ≤ 𝑐 ≤ 𝐶 $）是类别为 𝑐 的真实概率 . 假设样本的类别为 𝑘 ， 那么它属于第 𝑘 类的概率为 1 ，其他类的概率为 0.

对于两个概率分布， 一般可以用交叉熵来衡量它们的差异 . 标签的真实分布𝒚 和模型预测分布 𝑓(𝒙; 𝜃) 之间的交叉熵为

比如对于三分类问题，一个样本的标签向量为$ 𝒚 = [0, 0, 1]^T$ ，模型预测的标签分布为$ 𝑓(𝒙; 𝜃) = [0.3, 0.3, 0.4]^T $，则它们的交叉熵为 $−(0 × log(0.3) + 0 ×log(0.3) + 1 × log(0.4)) = − log(0.4).$

因为 𝒚 为 one-hot 向量， 公式 (2.18) 也可以写为:

其中 $𝑓_𝑦 (𝒙; 𝜃) $可以看作真实类别 𝑦 的似然函数 . 因此， 交叉熵损失函数也就是负对数似然函数（ Negative Log-Likelihood ） .

• Hinge 损失函数 对于二分类问题， 假设 𝑦 的取值为$ {−1, +1} ， 𝑓(𝒙; 𝜃) ∈ ℝ. Hinge$损失函数（ Hinge Loss Function ）为

风险最小化准则

​ 一个好的模型 𝑓(𝒙; 𝜃) 应当有一个比较小的期望错误， 但由于不知道真实的数据分布和映射函数， 实际上无法计算其期望风险 ℛ(𝜃). 给定一个训练集 $𝒟 ={(𝒙 (𝑛) , 𝑦 (𝑛) )}^𝑁_{𝑛=1} $， 我们可以计算的是经验风险（ Empirical Risk ）（经验风险也称为经验错误）， 即在训练集上的平均损失：

因此，一个切实可行的学习准则是找到一组参数 $𝜃^∗$ 使得经验风险最小，即

这就是经验风险最小化（ Empirical Risk Minimization,ERM ）准则 .

过拟合

​ 根据大数定理可知， 当训练集大小 |𝒟| 趋向于无穷大时， 经验风险就趋向于期望风险 . 然而通常情况下， 我们无法获取无限的训练样本， 并且训练样本往往是真实数据的一个很小的子集或者包含一定的噪声数据， 不能很好地反映全部数据的真实分布 . 经验风险最小化原则很容易导致模型在训练集上错误率很低，但是在未知数据上错误率很高 . 这就是所谓的过拟合（ Overfitting ） .

定义 2.1 – 过拟合： 给定一个假设空间 ℱ ， 一个假设 𝑓 属于 ℱ ， 如果存在其他的假设 𝑓 ′ 也属于 ℱ, 使得在训练集上 𝑓 的损失比 𝑓 ′ 小， 但在整个样本空间上 𝑓 ′ 比 𝑓 的损失小，那么就说假设 𝑓 过度拟合训练数据 [Mitchell, 1997].

​ 过拟合问题往往是由于训练数据少和噪声以及模型能力强等原因造成的 .为了解决过拟合问题， 一般在经验风险最小化的基础上再引入参数的正则化（ Regularization ）来限制模型能力，使其不要过度地最小化经验风险 . 这种准则就是结构风险最小化（ Structure Risk Minimization ，SRM ）准则：

其中 ‖𝜃‖ 是 $ℓ^2$ 范数的正则化项， 用来减少参数空间， 避免过拟合； 𝜆 用来控制正则化的强度 .

​ 正则化项也可以使用其他函数， 比如$ ℓ_1 $范数 . $ ℓ_1 $范数的引入通常会使得参数有一定稀疏性， 因此在很多算法中也经常使用 . 从贝叶斯学习的角度来讲， 正则化是假设了参数的先验分布，不完全依赖训练数据 .

​ 和过拟合相反的一个概念是欠拟合（ Underfitting ）， 即模型不能很好地拟合训练数据， 在训练集的错误率比较高 . 欠拟合一般是由于模型能力不足造成的 .图 2.3 给出了欠拟合和过拟合的示例 .

​ 总之， 机器学习中的学习准则并不仅仅是拟合训练集上的数据， 同时也要使得泛化错误最低 . 给定一个训练集， 机器学习的目标是从假设空间中找到一个泛化错误较低的 “理想” 模型， 以便更好地对未知的样本进行预测， 特别是不在训练集中出现的样本 . 因此， 机器学习可以看作是一个从有限、 高维、 有噪声的数据上得到更一般性规律的泛化问题 .

优化算法

​ 在确定了训练集 𝒟 、假设空间 ℱ 以及学习准则后，如何找到最优的模型$𝑓(𝒙, 𝜃^∗ ) $就成了一个最优化（ Optimization ）问题 . 机器学习的训练过程其实就是最优化问题的求解过程 .

参数与超参数 在机器学习中，优化又可以分为参数优化和超参数优化 . 模型𝑓(𝒙; 𝜃) 中的 𝜃 称为模型的参数， 可以通过优化算法进行学习 . 除了可学习的参数𝜃 之外， 还有一类参数是用来定义模型结构或优化策略的， 这类参数叫做超参数（ Hyper-Parameter ） .

​ 常见的超参数包括： 聚类算法中的类别个数、 梯度下降法中的步长、 正则化项的系数、 神经网络的层数、 支持向量机中的核函数等 . 超参数的选取一般都是组合优化问题， 很难通过优化算法来自动学习 . 因此， 超参数优化是机器学习的一个经验性很强的技术， 通常是按照人的经验设定， 或者通过搜索的方法对一组超参

数组合进行不断试错调整 .

梯度下降法

​ 为了充分利用凸优化中一些高效、 成熟的优化方法， 比如共轭梯度、 拟牛顿法等， 很多机器学习方法都倾向于选择合适的模型和损失函数以构造一个凸函数作为优化目标 . 但也有很多模型（比如神经网络）的优化目标是非凸的， 只能退而求其次找到局部最优解 .

​ 在机器学习中， 最简单、 常用的优化算法就是梯度下降法， 即首先初始化参数$𝜃^0$ ， 然后按下面的迭代公式来计算训练集 𝒟 上风险函数的最小值：

其中 𝜃 𝑡 为第 𝑡 次迭代时的参数值， 𝛼 为搜索步长 . 在机器学习中， 𝛼 一般称为学习率（ Learning Rate ） .

提前停止

​ 针对梯度下降的优化算法， 除了加正则化项之外， 还可以通过提前停止来防止过拟合 .

​ 在梯度下降训练的过程中， 由于过拟合的原因， 在训练样本上收敛的参数， 并不一定在测试集上最优 . 因此， 除了训练集和测试集之外， 有时也会使用一个验证集（ Validation Set ）（验 证 集 也 叫开 发 集）来进行模型选择， 测试模型在验证集上是否最优 . 在每次迭代时， 把新得到的模型 𝑓(𝒙; 𝜃) 在验证集上进行测试， 并计算错误率 . 如果在验证集上的错误率不再下降， 就停止迭代 . 这种策略叫提前停止（ Early Stop ） . 如果没有验证集， 可以在训练集上划分出一个小比例的子集作为验证集 . 图 2.4 给出了提前停止的示例 .

随机梯度下降法

​ 在公式 (2.27) 的梯度下降法中， 目标函数是整个训练集上的风险函数， 这种方式称为批量梯度下降法（ Batch Gradient Descent ，BGD ） . 批量梯度下降法在每次迭代时需要计算每个样本上损失函数的梯度并求和 . 当训练集中的样本数量𝑁 很大时， 空间复杂度比较高， 每次迭代的计算开销也很大 .

​ 在机器学习中，我们假设每个样本都是独立同分布地从真实数据分布中随机抽取出来的，真正的优化目标是期望风险最小 . 批量梯度下降法相当于是从真实数据分布中采集 𝑁 个样本， 并由它们计算出来的经验风险的梯度来近似期望风险的梯度 .为了减少每次迭代的计算复杂度， 我们也可以在每次迭代时只采集一个样本，计算这个样本损失函数的梯度并更新参数，即随机梯度下降法（ Stochastic Gradient Descent ，SGD ） . 当经过足够次数的迭代时， 随机梯度下降也可以收敛到局部最优解 [Nemirovski et al., 2009].

随机梯度下降法的训练过程如算法 2.1 所示 .

​ 批量梯度下降和随机梯度下降之间的区别在于每次迭代的优化目标是对所有样本的平均损失函数还是单个样本的损失函数 . 随机梯度下降因为实现简单，收敛速度也非常快， 因此使用非常广泛 . 随机梯度下降相当于在批量梯度下降的梯度上引入了随机噪声 . 当目标函数非凸时，反而可以使其逃离局部最优点 .

​ 不同机器学习算法的区别在于模型、 学习准则（损失函数）和优化算法的差异 . 相同的模型也可以有不同的学习算法 . 比如线性分类模型有感知器、 Logistic回归和支持向量机。它们之间的差异在于使用了不同的学习准则和优化算法 .

• 小批量梯度下降法 随机梯度下降法的一个缺点是无法充分利用计算机的并行计算能力 . 小批量梯度下降法（ Mini-Batch Gradient Descent ）是批量梯度下降和随机梯度下降的折中 . 每次迭代时， 我们随机选取一小部分训练样本来计算梯度并更新参数，这样既可以兼顾随机梯度下降法的优点，也可以提高训练效率 .

第 𝑡 次迭代时， 随机选取一个包含 𝐾 个样本的子集 $S_t$ ， 计算这个子集上每个（𝐾通常不会设置很大通常设置
为 2 的幂 $2^𝑛$ .）样本损失函数的梯度并进行平均，然后再进行参数更新：

在实际应用中， 小批量随机梯度下降法有收敛快、 计算开销小的优点， 因此逐渐成为大规模的机器学习中的主要优化算法 [Bottou, 2010].

机器学习的简单示例： 线性回归

在本节中， 我们通过一个简单的模型（线性回归）来具体了解机器学习的一般过程， 以及不同学习准则（经验风险最小化、 结构风险最小化、 最大似然估计、最大后验估计）之间的关系 .

​ 线性回归（ Linear Regression ）是机器学习和统计学中最基础和广泛应用的模型， 是一种对自变量和因变量之间关系进行建模的回归分析 . 自变量数量为 1时称为简单回归，自变量数量大于 1 时称为多元回归 .

​ 从机器学习的角度来看， 自变量就是样本的特性向量 $𝒙 ∈ ℝ^𝐷 $（每一维对应一个自变量）， 因变量是标签 𝑦 ， 这里 𝑦 ∈ ℝ 是连续值（实数或连续整数） . 假设空间是一组参数化的线性函数:

其中权重向量 𝒘 ∈ ℝ 𝐷 和偏置 𝑏 ∈ ℝ 都是可学习的参数， 函数 𝑓(𝒙; 𝒘, 𝑏) ∈ ℝ 也称为线性模型 .

为简单起见，我们将公式 (2.30) 写为

其中 𝒘 ̂ 和 𝒙 ̂ 分别称为增广权重向量和增广特征向量：

其中 ⊕ 定义为两个向量的拼接操作 .

不失一般性， 在本章后面的描述中我们采用简化的表示方法， 直接用 𝒘 和 𝒙来表示增广权重向量和增广特征向量 . 这样， 线性回归的模型简写为$ 𝑓(𝒙; 𝒘) =𝒘^T 𝒙.$

参数学习

​ 给定一组包含 𝑁 个训练样本的训练集$ 𝒟 = {(𝒙^{(𝑛)} , 𝑦^{(𝑛) })}^𝐷_𝑛=1 ，$ 我们希望能够学习一个最优的线性回归的模型参数 𝒘.我们介绍四种不同的参数估计方法： 经验风险最小化、 结构风险最小化、 最大似然估计、 最大后验估计 .

经验风险最小化

​ 由于线性回归的标签 𝑦 和模型输出都为连续的实数值， 因此平方损失函数非常合适来衡量真实标签和预测标签之间的差异 .

根据经验风险最小化准则，训练集 $D$上的经验风险定义为:

其中$ 𝒚 = [𝑦^{(1)} , ⋯ , 𝑦^{(𝑁)} ]^T ∈ ℝ^𝑁$ 是由所有样本的真实标签组成的列向量，而$𝑿 ∈ ℝ^{ (𝐷+1)×𝑁} $是由所有样本的输入特征$ 𝒙^{(1)} , ⋯ , 𝒙^{(𝑁)}$ 组成的矩阵

风险函数 ℛ(𝒘) 是关于 𝒘 的凸函数， 其对 𝒘 的偏导数为:

​ 这种求解线性回归参数的方法也叫最小二乘法（ Least Square Method ， LSM ）,图 2.5 给出了用最小二乘法来进行线性回归参数学习的示例 .

​ 在最小二乘法中，$ 𝑿𝑿^T ∈ ℝ^{(𝐷+1)×(𝐷+1)}$ 必须存在逆矩阵， 即 $𝑿𝑿^T $是满秩的$（ rank(𝑿𝑿^T ) = 𝐷 + 1 ）$ . 也就是说， 𝑿 中的行向量之间是线性不相关的， 即每一个特征都和其他特征不相关 . 一种常见的$ 𝑿𝑿^T$ 不可逆情况是样本数量 𝑁 小于特征数量 (𝐷 + 1) ，$𝑿𝑿^T $的秩为 𝑁. 这时会存在很多解 𝒘 ∗ ， 可以使得$ ℛ(𝒘^∗ ) = 0.$

​ 当$ 𝑿𝑿^T$ 不可逆时， 可以通过下面两种方法来估计参数：（ 1 ）先使用主成分分析等方法来预处理数据， 消除不同特征之间的相关性， 然后再使用最小二乘法来估计参数；（ 2 ）通过用梯度下降法来估计参数 . 先初始化 𝒘 = 0 ， 然后通过下面公式进行迭代：

其中 𝛼 是学习率 . 这种利用梯度下降法来求解的方法也称为最小均方（ Least Mean Squares ， LMS ）算法 .

结构风险最小化

​ 最小二乘法的基本要求是各个特征之间要互相独立， 保证$𝑿𝑿^T$ 可逆 . 但即使 $𝑿𝑿^T$可逆， 如果特征之间有较大的多重共线性（ Multicollinearity ）， 也会使得$𝑿𝑿^T $的逆在数值上无法准确计算 . 数据集 𝑿 上一些小的扰动就会导致 $(𝑿𝑿^T )^{−1}$发生大的改变，进而使得最小二乘法的计算变得很不稳定 . 为了解决这个问题，
[Hoerl et al., 1970] 提出了岭回归（ Ridge Regression ）， 给 $𝑿𝑿^T$ 的对角线元素都加上一个常数 𝜆 使得 $(𝑿𝑿^T + 𝜆𝐼) $满秩，即其行列式不为 0. 最优的参数 $𝒘^∗$ 为:

其中 𝜆 > 0 为预先设置的超参数， 𝐼 为单位矩阵 .

岭回归的解 $𝒘^∗ $可以看作是结构风险最小化准则下的最小二乘法估计， 其目标函数可以写为

其中 𝜆 > 0 为正则化系数 .

最大似然估计

​ 机器学习任务可以分为两类： 一类是样本的特征向量 𝒙 和标签 𝑦 之间存在未知的函数关系 𝑦 = ℎ(𝒙) ， 另一类是条件概率 𝑝(𝑦|𝒙) 服从某个未知分布 .第 2.3.1.1 中介绍的最小二乘法是属于第一类，直接建模 𝒙 和标签 𝑦 之间的函数关系 . 此外，线性回归还可以通过建模条件概率 𝑝(𝑦|𝒙) 的角度来进行参数估计 .

假设标签 𝑦 为一个随机变量， 其服从以均值为$𝑓(𝒙; 𝒘) = 𝒘^T 𝒙 ， 方差为 𝜎^2$ 的高斯分布：

参数 𝒘 在训练集 𝒟 上的似然函数（ Likelihood ）为

其中$ 𝒚 = [𝑦^{(1)} , ⋯ , 𝑦 ^{(𝑁)} ]^ T $为所有样本标签组成的向量，$ 𝑿 = [𝒙 ^{(1)} , ⋯ , 𝒙 ^{(𝑁) }] $为所有样本特征向量组成的矩阵.

为了方便计算，对似然函数取对数得到对数似然函数（ Log Likelihood ），

​ 最大似然估计（ Maximum Likelihood Estimation ， MLE ）是指找到一组参数 𝒘 使得似然函数 𝑝(𝒚|𝑿; 𝒘, 𝜎) 最大，等价于对数似然函数 log 𝑝(𝒚|𝑿; 𝒘, 𝜎) 最大 .

可以看出，最大似然估计的解和最小二乘法的解相同 .

最大后验估计

​ 最大似然估计的一个缺点是当训练数据比较少时会发生过拟合， 估计的参数可能不准确 . 为了避免过拟合，我们可以给参数加上一些先验知识 .

​ 假设参数 𝒘 为一个随机向量， 并服从一个先验分布 𝑝(𝒘; 𝜈). 为简单起见， 一般令 𝑝(𝒘; 𝜈) 为各向同性的高斯分布：

其中$𝜈^2$ 为每一维上的方差 .

根据贝叶斯公式，那么参数 𝒘 的后验分布（ Posterior Distribution ）为

其中 𝑝(𝒚|𝑿; 𝒘, 𝜎) 为 𝒘 的似然函数，定义见公式 (2.47) ，𝑝(𝒘; 𝜈) 为 𝒘 的先验 .

​ 这种估计参数 𝒘 的后验概率分布的方法称为贝叶斯估计（ Bayesian Estima-tion ）， 是一种统计推断问题 . 采用贝叶斯估计的线性回归也称为贝叶斯线性回归（ Bayesian Linear Regression ） .

​ 贝叶斯估计是一种参数的区间估计，即参数在一个区间上的分布 . 如果我们希望得到一个最优的参数值（即点估计），可以使用最大后验估计 .最大后验估计（ Maximum A Posteriori Estimation ， MAP ）是指最优参数为后验分布𝑝(𝒘|𝑿, 𝒚; 𝜈, 𝜎) 中概率密度最高的参数：

令似然函数 𝑝(𝒚|𝑿, 𝒘; 𝜎) 为公式 (2.48) 中定义的高斯密度函数， 则后验分布𝑝(𝒘|𝑿, 𝒚; 𝜈, 𝜎) 的对数为

可以看出，最大后验概率等价于平方损失的结构方法最小化，其中正则化系数$𝜆 = 𝜎^2 /𝜈^2 .$

​ 最大似然估计和贝叶斯估计可以看作是频率学派和贝叶斯学派对需要估计的参数 𝒘 的不同解释 . 当 𝜈 → ∞ 时， 先验分布 𝑝(𝒘; 𝜈) 退化为均匀分布， 称为无信息先验（ Non-Informative Prior ），最大后验估计退化为最大似然估计 .