查看“︁经验风险最小化”︁的源代码

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

== 背景 ==
以下情况是许多[[監督式學習|有监督学习]]问题的一般设置。存在两个空间，输入空间<math>X</math>和输出空间<math>Y</math>，目标是学习（拟合）一个函数<math>\ h: X \to Y</math> （通常称为''假设'' ），这个函数在给定<math>x \in X</math>，输出一个对象<math>y \in Y</math>  。为此可以使用一个包含 <math>n</math>个例子的''训练集''<math>\ (x_1, y_1), \ldots, (x_n, y_n)</math>，其中<math>x_i \in X</math>是输入， <math>y_i \in Y</math>是希望从<math>\ h(x_i)</math>中得到的相应输出 。

更正式地说，可假设<math>X</math>和<math>Y</math>服从[[联合分布|联合概率分布]] <math>P(x, y)</math> ，并且训练集包括<math>n</math>个实例<math>\ (x_1, y_1), \ldots, (x_n, y_n)</math>[[独立同分布|IID]]地从<math>P(x, y)</math> 抽取。请注意，联合概率分布的假设可以对预测中的不确定性进行建模（例如，来自数据中的噪声），因为<math>y</math>不是关于<math>x</math>的确定性函数 ，而是在固定<math>x</math> 时具有[[条件概率分布|条件分布<math>P(y | x)</math>]]的[[随机变量]] 。

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

: <math>R(h) = \mathbf{E}[L(h(x), y)] = \int L(h(x), y)\,dP(x, y).</math>

理论上常用的损失函数是[[损失函数|0-1损失函数]] ： <math>L(\hat{y}, y) = \begin{cases} 1 & \mbox{ If }\quad \hat{y} \ne y \\ 0 & \mbox{ If }\quad \hat{y} = y \end{cases}</math> 。

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

: <math>h^* = \arg \min_{h \in \mathcal{H}} R(h).</math>

== 经验风险最小化 ==
通常，无法计算风险<math>R(h)</math>，因为学习算法不知道分布<math>P(x, y)</math>（这种情况称为无知学习）。但是可以通过对训练集上的损失函数取平均值来计算一个近似值，称为''经验风险''：

: <math>\! R_\text{emp}(h) = \frac{1}{n} \sum_{i=1}^n L(h(x_i), y_i).</math>

经验风险最小化原理<ref>V. Vapnik (1992). [http://papers.nips.cc/paper/506-principles-of-risk-minimization-for-learning-theory.pdf ''Principles of Risk Minimization'' for Learning Theory.''] {{Wayback|url=http://papers.nips.cc/paper/506-principles-of-risk-minimization-for-learning-theory.pdf |date=20160804050339 }}''</ref>指出学习算法应选择一个假设<math>\hat{h}</math>将经验风险降到最低：

: <math>\hat{h} = \arg \min_{h \in \mathcal{H}} R_{\text{emp}}(h).</math>

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

== 性质 ==

=== 计算复杂度 ===
对于具有[[损失函数|0-1损失函数]]的分类问题，即使对于像[[线性分类器]]这样的相对简单的函数类，经验风险最小化也被认为是[[NP困难|NP]]难题。 <ref>V. Feldman, V. Guruswami, P. Raghavendra and Yi Wu (2009). [[arxiv:1012.0729|''Agnostic Learning of Monomials by Halfspaces is Hard.'']] (See the paper and references therein)</ref>但是，当最小经验风险为零（即数据是线性可分离的）时，可以有效解决。

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

== 參見 ==

* [[最大似然估计]] 
* M估计器

== 参考文献 ==
{{Reflist}}

== 扩展阅读 ==

* {{Cite book|last=Vapnik|first=V.|authorlink=Vladimir Vapnik|title=The Nature of Statistical Learning Theory|publisher=[[Springer-Verlag]]|series=Information Science and Statistics|year=2000|isbn=978-0-387-98780-4}} <bdi> {{Cite book|last=Vapnik|first=V.|authorlink=Vladimir Vapnik|title=The Nature of Statistical Learning Theory|publisher=[[Springer-Verlag]]|series=Information Science and Statistics|year=2000|isbn=978-0-387-98780-4}} </bdi> {{Cite book|last=Vapnik|first=V.|authorlink=Vladimir Vapnik|title=The Nature of Statistical Learning Theory|publisher=[[Springer-Verlag]]|series=Information Science and Statistics|year=2000|isbn=978-0-387-98780-4}}

[[Category:机器学习]]