机器学习：经验风险最小化概述

经验风险最小化（ERM，Empirical Risk Minimization）是机器学习中的一个基本概念，但令人惊讶的是，许多实践者并不熟悉它。理解ERM是理解机器学习算法极限性的必要条件，是解决实际问题的基础。ERM背后的理论是解释 VC-dimension的理论。任何认真对待机器学习的人都应该知道ERM。我将尽可能简单地解释这些基本概念

让我们从一个简单的监督学习分类问题开始。假设我们想对垃圾邮件进行分类，这可能是机器学习中最常用的例子(注意，这不是一篇关于naive Bayes的文章)。每封邮件都有一个标签0或1，要么是垃圾邮件，要么不是垃圾邮件。我们用X表示域空间用Y表示标签空间，我们还需要一个函数把域集空间映射到标签集空间，f: X -> Y。

现在我们有了问题定义，我们需要一个机器学习模型来进行预测:是否时垃圾邮件。模型的同义词是假设h，这个假设，是一个函数它从定义域X中获取输入，并产生一个标签0或1，即函数h: X -> Y。

最后，我们实际上想找到最小化误差的假设。Empirical意味着我们基于域集X中的样本集S来最小化我们的误差。从概率的角度来看，我们说我们从域集X中对S进行采样，其中D是在X上的分布。因此，当我们从域中进行采样时，我们用D(S)表示从域X对该域的子集进行采样的可能性。

在下面的等式中，我们可以定义真正的误差，它基于整个域X：

假设h的误差。从左到右，我们根据域分布D和标签映射f计算误差L，误差等于从D中采样x的概率，使得假设产生的标签与实际标签映射不同。

因为我们只能访问输入域的子集S，所以我们基于训练样本的实例进行学习。我们无法得到真实的误差，但可以得到经验误差

m表示训练样本的数量。您可以从等式中看出，我们有效地将经验误差定义为集合S中错误分类的示例的分数。

经验误差有时也称为泛化误差。原因是，在大多数问题中，我们不能访问输入的整个域X，而只能访问训练子集S，我们想基于S进行泛化，也叫归纳学习。这种误差也称为风险，因此在经验风险最小化中称为风险。如果这让您想起了小批量梯度下降，您是对的。这个概念在现代机器学习中是普遍存在的。

现在我们可以讨论过拟合的问题。也就是说，由于我们只有数据的一个子样本，我们可以最小化经验误差，但实际上增加了真实误差。这个结果可以在一个简单的曲线拟合问题中观察到。假设我们有一个机器人我们想要控制它，我们想要把一些传感器数据X映射到扭矩上。传感器数据具有一定的噪声（因为传感器从来都不是完美的），在这种情况下，我们将对传感器数据使用简单的高斯噪声。我们拟合一个神经网络来做这个，我们得到如下结果:

绿色的点是用来拟合机器学习模型的点，我们的样本s。考虑到训练点的数量较少，模型实际上是很好的，可以看到与最优曲线的偏差。

我们可以看下泛化误差，注意，在某一点上，真实误差开始增加，而经验误差进一步减少。这是机器学习模型对训练数据过度拟合的结果。

现在我们已经定义了我们的经验风险和实际风险，也就是说，我们希望产生机器学习模型误差的上限。上限的含义就是我们保证误差不会大于这个界限。

这就给出了采样集S(或者说训练数据)与数据过拟合的概率，即真实误差（L）将大于某个数字epsilon。

在目前的情况下，我们将在可实现性假设下运作。简而言之，这个假设表明在所有可能的假设H的空间中存在一个假设h在某种意义上是最优的，它的真实风险是0，这也意味着在子集S上找到的假设达到了0经验误差。当然，在真实的用例中，这通常是不正确的，并且有一些学习范例可以放松这种假设。

让我们定义真实误差高于epsilon的假设集：

对于这组假设，很明显，要么他们接受了一个非代表性的学习集合，这导致了低经验误差（risk）和高真实误差（risk），或者他们不足以学习任何东西。

我们想要分离那些导致低经验误差和高真实误差(过拟合的情况)假设的误导性训练集，这推导上界时将会很有用:

采样非代表性样本的特定子集S的概率在逻辑上等于或低于采样M的概率，因为S是M的子集，因此我们可以这样写:

我们将并集引理应用到方程的右边，它表明对两个集合的并集采样的概率小于对它们单独采样的概率。这就是为什么我们可以把和写在右边:

此外，我们假设这些例子是独立且恒等分布的(iid)，因此我们可以把经验误差为零的概率写成单个预测正确的概率的乘积:

常数m表示集合S中的训练样本的数量

假设在某一数据点正确的概率可以写成1减去真实风险。这是因为我们将风险定义为错误分类的例子的比例。不等式的成立是因为我们假设误差小于或等于上界。

如果我们结合前两个方程式，我们得出以下结果：

右边的指数来自一个可证明的不平等

如果我们将上面的等式与我们应用了并集的前一个等式结合起来，我们得出以下结果：

这里| H | 是假设空间的基数，显然，当我们有无数个假设时，这个表述没有意义。

我们可以用一个常数1-delta替换左侧，其中delta是我们希望误差不会高于epsilon的置信度。我们可以简单地重新排列等式，以便说明以下内容：

最后的结果告诉我们我们需要多少个实例（m），以便ERM不会导致错误高于具有一定置信度delta的epsilon，即当我们选择足够的ERM实例时，它的误差可能不会大于epsilon。这里我用"可能"这个词是因为它取决于置信常数delta，介于0和1之间。这是一个直观的说法。

在ERM中，有许多假设。我提到了可实现性假设（即在我们的假设池中存在一个最优假设），ERM是学习理论中的一个基本概念，对于任何认真的机器学习实践者来说都是必不可少的。