经验风险最小化

经验风险最小化 (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)

进一步阅读

  • 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.