经验风险最小化（，縮寫：ERM）是统计学习理论里的一项原则，该原则下有一系列学习算法 ，经验风险最小化用于为这些算法的性能提供理论上的界。核心思想是，人們无法确切知道算法在实际中的运行情况（真正的“风险”），是因为不知道算法将在其上运行的数据的真实分布，但借助经验风险最小化，可以在一组已知的训练数据（“经验”风险）上衡量其性能。
背景
以下情况是许多有监督学习问题的一般设置。存在两个空间，输入空间X和输出空间Y，目标是学习（拟合）一个函数\ h: X \to Y （通常称为假设 ），这个函数在给定x \in X，输出一个对象y \in Y 。为此可以使用一个包含 n个例子的训练集\ (x_1, y_1), \ldots, (x_n, y_n)，其中x_i \in X是输入， y_i \in Y是希望从\ h(x_i)中得到的相应输出 。
更正式地说，可假设X和Y服从联合概率分布 P(x, y) ，并且训练集包括n个实例\ (x_1, y_1), \ldots, (x_n, y_n)IID地从P(x, y) 抽取。请注意，联合概率分布的假设可以对预测中的不确定性进行建模（例如，来自数据中的噪声），因为y不是关于x的确定性函数 ，而是在固定x 时具有 x)的随机变量 。
还可假定给定非负实值损失函数 L(\hat{y}, y)来衡量预测\hat{y}与真实结果y的差异。则假设h(x)的风险定义为损失函数的期望值 ：
: R(h) = \mathbf{E}[L(h(x), y)] = \int L(h(x), y)\,dP(x, y).
理论上常用的损失函数是0-1损失函数 ： L(\hat{y}, y) = \begin{cases} 1 & \mbox{ If }\quad \hat{y} \ne y \\ 0 & \mbox{ If }\quad \hat{y} = y \end{cases} 。
学习算法的最终目标是在固定函数类\mathcal{H}中找到风险R(h)最小的假设 h^*：
: h^* = \arg \min_{h \in \mathcal{H}} R(h).
经验风险最小化
通常，无法计算风险R(h)，因为学习算法不知道分布P(x, y)（这种情况称为无知学习）。但是可以通过对训练集上的损失函数取平均值来计算一个近似值，称为经验风险：
: \! R_\text{emp}(h) = \frac{1}{n} \sum_{i=1}^n L(h(x_i), y_i).
经验风险最小化原理指出学习算法应选择一个假设\hat{h}将经验风险降到最低：
: \hat{h} = \arg \min_{h \in \mathcal{H}} R_{\text{emp}}(h).
因此，由ERM原理定义的学习算法在于解决上述优化问题。
性质
计算复杂度
对于具有0-1损失函数的分类问题，即使对于像线性分类器这样的相对简单的函数类，经验风险最小化也被认为是NP难题。 但是，当最小经验风险为零（即数据是线性可分离的）时，可以有效解决。
在实践中，机器学习算法可以通过对0-1损失函数（例如SVM的铰链损失）采用凸近似来解决该问题，这种方法更容易优化，或者对分布进行假设P(x, y) （因此不再是上述结果适用的不可知论学习算法）。
參見
- 最大似然估计
- M估计器
参考文献
扩展阅读
*
评论 (0)