经验风险最小化
![]() | 此条目不当使用第一人称(我、我们)或第二人称(你、你们)
。 (2019年11月12日) |
经验风险最小化 (ERM)是统计学习理论里的一项原则,该原则下有一系列学习算法 ,经验风险最小化用于为这些算法的性能提供理论上的界。核心思想是,我们无法确切知道算法在实际中的运行情况(真正的“风险”),因为我们不知道算法将在其上运行的数据的真实分布,但借助经验风险最小化,我们可以在一组已知的训练数据(“经验”风险)上衡量其性能。
背景
[编辑]以下情况是许多有监督学习问题的一般设置。我们有两个空间,输入空间和输出空间,我们的目标是学习(拟合)一个函数 (通常称为假设 ),这个函数在给定,输出一个对象 。为此,我们可以使用一个包含 个例子的训练集,其中是输入, 是我们希望从中得到的相应输出 。
更正式地说,我们假设和服从联合概率分布 ,并且训练集包括个实例IID地从 抽取。请注意,联合概率分布的假设使我们可以对预测中的不确定性进行建模(例如,来自数据中的噪声),因为不是关于的确定性函数 ,而是在固定 时具有条件分布的随机变量 。
我们还假定给定非负实值损失函数 来衡量预测与真实结果的差异。则假设的风险定义为损失函数的期望值 :
理论上常用的损失函数是0-1损失函数 : 。
学习算法的最终目标是在固定函数类中找到风险最小的假设:
经验风险最小化
[编辑]通常,无法计算风险,因为学习算法不知道分布(这种情况称为无知学习)。但是,我们可以通过对训练集上的损失函数取平均值来计算一个近似值,称为经验风险:
经验风险最小化原理[1]指出学习算法应选择一个假设将经验风险降到最低:
因此,由ERM原理定义的学习算法在于解决上述优化问题。
性质
[编辑]计算复杂度
[编辑]对于具有0-1损失函数的分类问题,即使对于像线性分类器这样的相对简单的函数类,经验风险最小化也被认为是NP难题。 [2]但是,当最小经验风险为零(即数据是线性可分离的)时,可以有效解决。
在实践中,机器学习算法可以通过对0-1损失函数(例如SVM的铰链损失)采用凸近似来解决该问题,这种方法更容易优化,或者对分布进行假设 (因此不再是上述结果适用的不可知论学习算法)。
参见
[编辑]- 最大似然估计
- M估计器
参考文献
[编辑]- ^ V. Vapnik (1992). Principles of Risk Minimization for Learning Theory. (页面存档备份,存于互联网档案馆)
- ^ 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.