机器学习的三个基本要素

💡

机器学习是从有限的观测数据中学习出具有一般性的规律，并且可以将总结出来的规律推广应用到未观测的样本上

机器学习方法可以粗略的分为三个基本要素：模型、学习准则、优化算法

一、模型

对于一个机器学习任务，首先要确定其输入空间 $\mathcal{X}$ 和输出空间 $\mathcal{Y}$

不同的机器学习任务主要区别在于输出空间不同

例如：

• 在二分类问题中 $y = \lbrace +1,-1 \rbrace$
• 在多分类问题中 $y = \lbrace 1,2, \mathellipsis,N \rbrace$ ，其中 $N$ 为问题种类
• 在回归问题中 $y = \mathbb{R}$ ，其中 $\mathbb{R}$ 为列向量

对于样本空间中的 $(x,y) \in \mathcal{X} \times \mathcal{Y}$ ，假设 $x$ 和 $y$ 之间的关系可以通过一个未知的 真实映射函数 $y = g(x)$ 或 真实条件概率分布 $p_{r}(y|x)$ ，机器学习的目标就是找到这个函数或是这种概率分布

开始我们并不知道这个函数 $g(x)$ 或条件概率分布 $p_{r}(y|x)$ 的具体形式，只能根据经验来假设一个函数集合 $\mathcal{F}$ ，称为 假设空间（Hypothesis Space） ，然后通过观测其在训练集 $\mathcal{D}$ 上的特性，从中选择一个理想的 假设（Hypothesis） $f^* \in \mathcal{F}$

• 假设空间通常为一个参数化的函数族

$$\mathcal{F} = \lbrace f(x;\theta)|\theta \in \mathbb{R}^D \rbrace \tag{5}$$

其中 $f(x; \theta)$ 是参数为 $\theta$ 的函数，也称为 模型（Model） ， $D$ 为参数的数量

常见的假设空间分为线性和非线性两种，对应的模型 $f$ 分别称为线性模型和非线性模型

（1）线性模型

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

$$f(x; \theta) = \omega^{T}x + b \tag{6}$$

• 其中参数 $\theta$ 包含了权重向量 $\omega$ 和偏置 $b$

（2）非线性模型

广义的非线性模型可以写为多个非线性 基函数 $\phi(x)$ 的线性组合

$$f(x; \theta) = \omega^{T} \phi(x) + b \tag{7}$$

• $\phi(x) = [\phi_1(x), \phi_2(x), \mathellipsis, \phi_K(x)]^{T}$ 为 $K$ 个非线性基函数组成的向量，参数 $\theta$ 包含了权重向量 $\omega$ 和偏置 $b$

✏️

如果 $\phi(x)$ 本身为可学习的基函数，例如

$$\phi_{k}(x) = h(\omega^{T}_{k} \phi^{'}(x) + b_k) , \forall 1 \leq k \leq K \tag{8}$$

其中 $h(.)$ 为非线性函数， $\phi^{'}(x)$ 为另一组基函数，$\omega_k$ 和 $b_k$ 为可学习的参数， $f(x; \theta)$ 就等价于 神经网络 模型

---

二、学习准则

训练集 $\mathcal{D} = {\lbrace (x^{(n)}, y^{(n)})\rbrace}^{N}_{n=1}$ 是由 $N$ 个独立同分布的样本组成

每个样本 $(x,y) \in \mathcal{X} \times \mathcal{Y}$ 是从 $\mathcal{X}$ 和 $\mathcal{Y}$ 的联合空间中按照某种未知分布 $p_r(x, y)$ 独立地随机产生

• 要求样本分布 $p_r(x, y)$ 必须是固定的，不会随时间变化，如果样本分布本身可变，就无法通过这些数据进行学习

一个好的模型 $f(x, \theta^*)$ 应该在所有样本的可能取值上都与真实 映射函数 $y = g(x)$ 一致，即

$$|f(x, \theta^*) - y| < \epsilon, \qquad \forall(x, y) \in \mathcal{X} \times \mathcal{Y} \tag{9}$$

或者与真实条件概率分布 $p_r(x|y)$ 一致，即

$$|f_y(x, \theta^*) - p_r(x|y)| < \epsilon, \qquad \forall(x, y) \in \mathcal{X} \times \mathcal{Y} \tag{10}$$

• 其中 $\epsilon$ 是一个很小的正数， $f_y(x, \theta^*)$ 为模型预测的条件概率分布中 $y$ 对应的概率

模型 $f(x; \theta)$ 的好坏可通过 期望风险（Expected Risk） $\mathcal{R}(\theta)$ 来衡量，其定义为

$$\mathcal{R}(\theta) = \mathbb{E}_{(x,y) \sim p_r(x,y)}[\mathcal{L}(y, f(x; \theta))] \tag{11}$$

• 其中 $p_r(x,y)$ 为真实的数据分布， $\mathcal{L}(y, f(x; \theta))$ 为损失函数，用来量化两个变量之间的差异

损失函数

损失函数是一个非负实数函数，用来量化模型预测和真实标签之间的差异

几种常用的损失函数：

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

$$\mathcal{L}(y, f(x; \theta)) = \left\{ \begin{matrix} 0 ~, \qquad y=f(x;\theta)\\ 1 ~, \qquad y \neq f(x;\theta) \end{matrix} \right. \tag{12}$$

• 也可以看做是指示函数 $I(.)$

$$\mathcal{L}(y, f(x; \theta)) = I(y \neq f(x;\theta)) \tag{13}$$

✏️

虽然 0-1 损失函数 能够客观地评价模型的好坏，但是也有缺点

• 不连续且导数为0，难以优化

因此常用连续可微的损失函数替代

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

$$\mathcal{L}(y, f(x; \theta)) = \frac{1}{2}(y - f(x; \theta))^2 \tag{14}$$

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

交叉熵损失函数 交叉熵损失函数（Cross-Entropy Loss Function） 一般用于分类问题

假设样本的标签 $y \in \lbrace{1,\mathellipsis,N}\rbrace$ 为离散的类别，模型 $f(x; \theta) \in [0,1]^N$ 的输出位类别标签的条件概率分布，即

$$p(y = c|x; \theta) = f_c(x; \theta) \tag{15}$$

并满足

$$f_c(x; \theta) \in [0, 1], \qquad \sum_{c=1}^{N} f_c(x; \theta) = 1 \tag{16}$$

🍉

假设现在有 $N$ 个水果，可以用一个 $N$ 维的 ont-hot 向量 $y$ 来表示样本的标签，假设第 $k$ 个水果是西瓜，那么标签向量 $y$ 中只有第 $k$ 维的元素为 1 ，其余所有元素都为 0

标签向量 $y$ 可以看作样本标签的真实条件概率分布 $p_r(y|x)$ ，即第 $c$ 维 $(y_c, 1\leq c \leq N)$ 是类别为 $c$ 的真实条件概率

西瓜类别为 $k$ ，那么它属于第 $k$ 类的概率为 1 ，属于其他类的概率为 0

对于两个概率分布，一般可以用交叉熵来衡量差异

标签的真实分布 $y$ 和模型预测分布 $f(x; \theta)$ 之间的交叉熵为

$$\begin{aligned} \mathcal{L}(y, f(x; \theta)) &= -y^{T} logf(x; \theta)\tag{17,~18}\\ &= - \sum_{c=1}^{N} y_clogf_c(x; \theta) \end{aligned}$$

eg.

例如一个三分类问题，一个样本的标签向量为 $y = [0, 0, 1]^T$ ，模型预测的标签分部为 $f(x; \theta) = [0.3, 0.3 , 0.4]^T$ ，则它们的交叉熵为

$$-(0 \times log(0.3) + 0 \times log(0.3) + 1 \times log(0.4)) = - log(0.4)$$

• 因为 $y$ 为 one-hot 向量，公式 $\color{blue}{(18)}$ 也可以写为

$$\mathcal{L}(y, f(x; \theta)) = -logf_y(x; \theta) \tag{19}$$

• 其中 $f_y(x; \theta)$ 可以看作真实类别 $y$ 的似然函数

因此，交叉熵损失函数也就是 负对数似然函数（Negative Log-Likelihood）

Hinge 损失函数 对于二分类问题，假设 $y$ 的取值为 $\lbrace +1,-1 \rbrace$ ， $f(x; \theta) \in \mathbb{R}$

Hinge 损失函数（Hinge Loss Function） 为

$$\begin{aligned} \mathcal{L}(y, f(x; \theta)) &= max(0, 1 - yf(x;\theta))\\ &\triangleq [1 - yf(x;\theta)]_{+} \tag{20, ~21} \end{aligned}$$

• 其中 $[x]_{+} = max(0,x)$

风险最小化准则

一个好的模型 $f(x; \theta)$ 应当有一个比较小的期望错误

由于不知真实的数据分部和映射函数，无法计算期望风险 $\mathcal R(\theta)$

给定一个训练集 $\mathcal{D} = {\lbrace (x^{(n)}, y^{(n)})\rbrace}_{n=1}^{N}$ ，我们可以计算的是 经验风险（Empirical Risk） ，即在训练集上的平均损失

$$\mathcal{R}_{\mathcal{D}}^{emp} (\theta) = \frac{1}{N} \sum_{n=1}^{N} \mathcal{L}(y^{(n)},f(x^{(n)}; \theta)) \tag{22}$$

✏️

• 一个可行的学习准则时找到一组参数 $\theta^*$ 使经验风险最小，即

$$\theta^* = \mathop{argmin}\limits_{\theta} \mathcal{R}_{\mathcal{D}}^{emp} \tag{23}$$

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

过拟合与欠拟合

过拟合

当训练集大小 $|\mathcal{D}|$ 趋向于无限大时，经验风险会越来越趋于期望风险，但是我们并不能获得无限的训练样本，而且训练样本通常是真实数据的一个很小的子集或者样本中包含一定的噪声数据，不能很好的反应全部数据的真实分布

经验风险最小化的原则很容易导致模型在训练集上错误率很低，但是在新的数据上错误率很高，这就是 过拟合（Overfitting）

📌

定义-过拟合：给定一个假设空间 $\mathcal{F}$ ，一个假设 $f \in \mathcal{F}$ ，如果存在其他的假设 $f^{'} \in \mathcal{F}$ ，使得在训练集上 $f$ 的损失比 $f^{'}$ 小，但是在整个样本空间上 $f^{'}$ 的损失比 $f$ 小，就说假设 $f$ 过度拟合训练数据

过拟合问题往往是由于训练数据少和噪声以及模型能力强等原因造成的

为了解决过拟合问题，一般在经验风险最小化的基础上在引入参数的 正则化(Regularization) 来限制模型能力，使其不要过度的最小化经验风险

• 就是 结构风险最小化（Structure Risk Minimization，SRM） 准则

$$\begin{aligned} \theta^* &= \mathop{argmin}\limits_{\theta} \mathcal{R}_{\mathcal{D}}^{struct}(\theta)\\ &=\mathop{argmin}\limits_{\theta} \mathcal{R}_{\mathcal{D}}^{emp} + \frac{1}{2} \lambda ||\theta||^{2}\\ &=\mathop{argmin}\limits_{\theta} \frac{1}{N} \sum_{n=1}^{N} \mathcal{L}(y^{(n)}, f(x^{(n)}; \theta)) + \frac{1}{2} \lambda ||\theta||^{2} \tag{24,~25,~26} \end{aligned}$$

• 其中 $||\theta||$ 是 $\ell_{2}$ 范数的正则化项，用来减少参数空间，避免过拟合； $\lambda$ 用来控制正则化的强度

📌

正则化项也可以使用其他函数，如 $\ell_{1}$ 范数

• 参数正则化

欠拟合

欠拟合（Underfitting） 是与过拟合相反的概念，即模型不能很好的拟合训练数据，在训练集上的错误率比较高

欠拟合一般是由于模型能力不足造成的

✏️

• 关于过拟合和欠拟合

机器学习中的学习准则并不仅仅是拟合训练集上的数据，同时也要使得繁华错误最低

• 可以将机器学习看做一个从有限、高维、有噪声的数据上得到更一般性规律的泛化问题

---

三、优化算法

训练集、假设空间和学习准则确定之后，如何找到最优的模型就成了一个 最优化问题（Optimization） 问题

• 机器学习的训练过程其实就是最优化问题的求解过程

参数与超参数

在机器学习中，优化可以分为参数优化和超参数优化

模型 $d(x; \theta)$ 中的 $\theta$ 称为模型的参数，可以通过优化算法进行学习

还有一类参数是用来定义模型结构或优化策略的，这类参数叫做 超参数（Hyper-Parameter）

常见的超参数包括：

• 聚类算法中的类别个数
• 梯度下降法中的步长
• 正则化项的系数
• 神经网络的层数
• 支持向量机中的核函数等

✏️

超参数的选取一般都是组合优化问题，很难通过优化算法来自动学习

• 超参数优化 是机器学习的一个经验性很强大技术，通常按照经验设定，或者通过搜索的方法对一组超参数组合进行不断试错调整

梯度下降法

• 局部最优解

梯度下降法 是机器学习中最简单最常用的优化算法，首先初始化参数 $\theta_{0}$ ，然后按以下迭代公式来计算训练集 $\mathcal{D}$ 上风险函数的最小值

$$\begin{aligned} \theta_{t+1} &= \theta_{t} - \alpha \frac{\partial \mathcal{R}_{\mathcal{D}} \theta}{\partial \theta}\\ &= \theta_{t} - \alpha \frac{1}{N} \sum_{n=1}^{N} \frac{\partial \mathcal{L}(y^{(n)},f(x^{(n); \theta}))}{\partial \theta} \tag{27, ~28} \end{aligned}$$

• 其中 $\theta_{t}$ 为第 $t$ 次迭代时代参数， $\alpha$ 为搜索步长，也被称为 学习率（Learning Rate）

提前停止

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

除了训练集和测试集之外，有时还会使用一个 验证集（Validation Set） 来进行模型选择，测试模型在验证集上是否最优

在每次迭代时，把新得到的模型 $f(x; \theta)$ 在验证集上进行测试，并计算错误率，如果在验证集上的错误率不再下降，就停止迭代，这种策略就叫 提前停止（Early Stop）

✏️

如果没有验证集，可以在训练集上划分出一个小比例的子集作为验证集

随机梯度下降法

在公式 $\color{blue}{(27)}$ 的梯度下降法中，目标函数是整个训练集上的风险函数，这种方式成为 批量梯度下降法（Batch Gradient Descent，BGD）

这种方法每次迭代时需要计算每个样本上损失函数的梯度并求和，当训练集中的样本数量很大时，算法会有很高的空间复杂度，每次迭代计算的开销也很大

为了减少每次迭代的计算复杂度，我们也可以在每次迭代的时候只采集一个样本，计算这个样本损失函数的梯度并更新参数，即 随机梯度下降法（Stochastic Gradient Descent，SGD） ，也叫做 增量梯度下降法

• 经过足够次数的迭代时，随机梯度下降也可以收敛到局部最优解

小批量梯度下降法

随机梯度下降法的一个缺点是无法充分利用计算机的并行计算能力， 小批量梯度下降法（Mini-Batch Gradient Descent） 是批量梯度下降和随机梯度下降的折中

每次迭代时随机选取一部分训练样本来计算梯度并更新参数，即能兼顾随机梯度下降法的优点，也可以提高训练效率

第 $t$ 次迭代时，随机选取含 $K$ 个样本的子集 $\mathcal{S}_{t}$ ，计算这个子集上每个样本的损失函数的梯度并取平均，然后更新参数

$$\theta_{t+1} \leftarrow \theta_{t} - \alpha \frac{1}{K} \sum_{(x,y) \in \mathcal{S}_{t}} \frac{\partial \mathcal{L} (t, f(x; \theta))}{\partial \theta \tag{29}}$$

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

---

参考

• 邱锡鹏，神经网络与深度学习，机械工业出版社，https://nndl.github.io/, 2020.