經驗風險最小化

經驗風險最小化 （ERM）是統計學習理論里的一項原則，該原則下有一系列學習算法 ，經驗風險最小化用於為這些算法的性能提供理論上的界。核心思想是，人們無法確切知道算法在實際中的運行情況（真正的「風險」），是因為不知道算法將在其上運行的數據的真實分佈，但藉助經驗風險最小化，可以在一組已知的訓練數據（「經驗」風險）上衡量其性能。

背景

以下情況是許多有監督學習問題的一般設置。存在兩個空間，輸入空間$X$和輸出空間$Y$，目標是學習（擬合）一個函數$\ h:X\to Y$ （通常稱為假設 ），這個函數在給定$x\in X$，輸出一個對象$y\in Y$ 。為此可以使用一個包含 $n$個例子的訓練集$\ (x_{1},y_{1}),\ldots ,(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}),\ldots ,(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)=\mathbf {E} [L(h(x),y)]=\int L(h(x),y)\,dP(x,y).$

理論上常用的損失函數是0-1損失函數 ： $L({\hat {y}},y)={\begin{cases}1&{\mbox{ If }}\quad {\hat {y}}\neq y\\0&{\mbox{ If }}\quad {\hat {y}}=y\end{cases}}$ 。

學習算法的最終目標是在固定函數類${\mathcal {H}}$中找到風險$R(h)$最小的假設$h^{*}$：

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

因此，由ERM原理定義的學習算法在於解決上述優化問題。

性質

計算複雜度

對於具有0-1損失函數的分類問題，即使對於像線性分類器這樣的相對簡單的函數類，經驗風險最小化也被認為是NP難題。 但是，當最小經驗風險為零（即數據是線性可分離的）時，可以有效解決。

在實踐中，機器學習算法可以通過對0-1損失函數（例如SVM的鉸鏈損失）採用凸近似來解決該問題，這種方法更容易優化，或者對分佈進行假設$P(x,y)$ （因此不再是上述結果適用的不可知論學習算法）。

參見

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

進一步閱讀

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