跳转到内容

经验风险最小化

维基百科,自由的百科全书

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

背景

[编辑]

以下情况是许多有监督学习问题的一般设置。我们有两个空间,输入空间和输出空间,我们的目标是学习(拟合)一个函数 (通常称为假设 ),这个函数在给定,输出一个对象 。为此,我们可以使用一个包含 个例子的训练集,其中是输入, 是我们希望从中得到的相应输出 。

更正式地说,我们假设服从联合概率分布 ,并且训练集包括个实例IID地从 抽取。请注意,联合概率分布的假设使我们可以对预测中的不确定性进行建模(例如,来自数据中的噪声),因为不是关于的确定性函数 ,而是在固定 时具有条件分布随机变量

我们还假定给定非负实值损失函数 来衡量预测与真实结果的差异。则假设的风险定义为损失函数的期望值

理论上常用的损失函数是0-1损失函数

学习算法的最终目标是在固定函数类中找到风险最小的假设

经验风险最小化

[编辑]

通常,无法计算风险,因为学习算法不知道分布(这种情况称为无知学习)。但是,我们可以通过对训练集上的损失函数取平均值来计算一个近似值,称为经验风险

经验风险最小化原理[1]指出学习算法应选择一个假设将经验风险降到最低:

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

性质

[编辑]

计算复杂度

[编辑]

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

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

參見

[编辑]

参考文献

[编辑]
  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)

进一步阅读

[编辑]