经验风险最小化

经验风险最小化 （ERM）是统计学习理论里的一项原则，该原则下有一系列学习算法 ，经验风险最小化用于为这些算法的性能提供理论上的界。核心思想是，我们无法确切知道算法在实际中的运行情况（真正的“风险”），因为我们不知道算法将在其上运行的数据的真实分布，但借助经验风险最小化，我们可以在一组已知的训练数据（“经验”风险）上衡量其性能。

背景

以下情况是许多有监督学习问题的一般设置。我们有两个空间，输入空间${\displaystyle X}$ 和输出空间${\displaystyle Y}$ ，我们的目标是学习（拟合）一个函数${\displaystyle \ h:X\to Y}$  （通常称为假设 ），这个函数在给定${\displaystyle x\in X}$ ，输出一个对象${\displaystyle y\in Y}$  。为此，我们可以使用一个包含 ${\displaystyle n}$ 个例子的训练集${\displaystyle \ (x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$ ，其中${\displaystyle x_{i}\in X}$ 是输入， ${\displaystyle y_{i}\in Y}$ 是我们希望从${\displaystyle \ h(x_{i})}$ 中得到的相应输出 。

更正式地说，我们假设${\displaystyle X}$ 和${\displaystyle Y}$ 服从联合概率分布 ${\displaystyle P(x,y)}$  ，并且训练集包括${\displaystyle n}$ 个实例${\displaystyle \ (x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$ IID地从${\displaystyle P(x,y)}$  抽取。请注意，联合概率分布的假设使我们可以对预测中的不确定性进行建模（例如，来自数据中的噪声），因为${\displaystyle y}$ 不是关于${\displaystyle x}$ 的确定性函数 ，而是在固定${\displaystyle x}$  时具有条件分布${\displaystyle P(y|x)}$ 的随机变量 。

我们还假定给定非负实值损失函数 ${\displaystyle L({\hat {y}},y)}$ 来衡量预测${\displaystyle {\hat {y}}}$ 与真实结果${\displaystyle y}$ 的差异。则假设${\displaystyle h(x)}$ 的风险定义为损失函数的期望值 ：

${\displaystyle R(h)=\mathbf {E} [L(h(x),y)]=\int L(h(x),y)\,dP(x,y).}$ 

理论上常用的损失函数是0-1损失函数 ： ${\displaystyle L({\hat {y}},y)={\begin{cases}1&{\mbox{ If }}\quad {\hat {y}}\neq y\\0&{\mbox{ If }}\quad {\hat {y}}=y\end{cases}}}$  。

学习算法的最终目标是在固定函数类${\displaystyle {\mathcal {H}}}$ 中找到风险${\displaystyle R(h)}$ 最小的假设${\displaystyle h^{*}}$ ：

${\displaystyle h^{*}=\arg \min _{h\in {\mathcal {H}}}R(h).}$ 

经验风险最小化

通常，无法计算风险${\displaystyle R(h)}$ ，因为学习算法不知道分布${\displaystyle P(x,y)}$ （这种情况称为无知学习）。但是，我们可以通过对训练集上的损失函数取平均值来计算一个近似值，称为经验风险：

${\displaystyle \!R_{\text{emp}}(h)={\frac {1}{n}}\sum _{i=1}^{n}L(h(x_{i}),y_{i}).}$ 

经验风险最小化原理^[1]指出学习算法应选择一个假设${\displaystyle {\hat {h}}}$ 将经验风险降到最低：

${\displaystyle {\hat {h}}=\arg \min _{h\in {\mathcal {H}}}R_{\text{emp}}(h).}$ 

因此，由ERM原理定义的学习算法在于解决上述优化问题。

性质

计算复杂度

对于具有0-1损失函数的分类问题，即使对于像线性分类器这样的相对简单的函数类，经验风险最小化也被认为是NP难题。 ^[2]但是，当最小经验风险为零（即数据是线性可分离的）时，可以有效解决。

在实践中，机器学习算法可以通过对0-1损失函数（例如SVM的铰链损失）采用凸近似来解决该问题，这种方法更容易优化，或者对分布进行假设${\displaystyle P(x,y)}$  （因此不再是上述结果适用的不可知论学习算法）。

參見

• 最大似然估计
• M估计器

参考文献

1. V. Vapnik (1992). Principles of Risk Minimization for Learning Theory. （页面存档备份，存于互联网档案馆）
2. V. Feldman, V. Guruswami, P. Raghavendra and Yi Wu (2009). Agnostic Learning of Monomials by Halfspaces is Hard. (See the paper and references therein)

进一步阅读

• Vapnik, V. The Nature of Statistical Learning Theory. Information Science and Statistics. Springer-Verlag. 2000. ISBN 978-0-387-98780-4.  Vapnik, V. The Nature of Statistical Learning Theory. Information Science and Statistics. Springer-Verlag. 2000. ISBN 978-0-387-98780-4.  Vapnik, V. The Nature of Statistical Learning Theory. Information Science and Statistics. Springer-Verlag. 2000. ISBN 978-0-387-98780-4.