经验风险最小化

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

背景

以下情况是许多有监督学习问题的一般设置。存在两个空间，输入空间$X$和输出空间$Y$，目标是学习（拟合）一个函数$h:X\to Y$ （通常称为假设 ），这个函数在给定$x\in X$，输出一个对象$y\in Y$ 。为此可以使用一个包含 $n$个例子的训练集$(x_1,y_1),\dots ,(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),\dots ,(x_n,y_n)$IID地从$P(x,y)$ 抽取。请注意，联合概率分布的假设可以对预测中的不确定性进行建模（例如，来自数据中的噪声），因为$y$不是关于$x$的确定性函数 ，而是在固定$x$ 时具有条件分布$P(y|x)$的随机变量 。

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

$R(h)=𝐄[L(h(x),y)]=\int L(h(x),y)dP(x,y).$

理论上常用的损失函数是0-1损失函数 ： $L(\hat{y},y)=\{\begin{array}{cc}1& \text{ If }\hat{y}\ne y\\ 0& \text{ If }\hat{y}=y\end{array}$ 。

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

$h^{*}=\arg \underset{h\in \mathscr{H}}{\min }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 \underset{h\in \mathscr{H}}{\min }{R}_{\text{emp}}(h).$

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

性质

计算复杂度

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

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

參見

• 最大似然估计
• M估计器

扩展阅读

• Template:Cite book Template:Cite book Template:Cite book