經驗風險最小化

經驗風險最小化 (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)

進一步閱讀

編輯