主動學習中的經驗風險最小化

在傳統的監督學習中，學習的目標是找到一個最優的分類器，期望它能在沒有見過的數據上具有良好的泛化性能。經驗風險最小化(ERM, empirical risk minimization)是一個很好的方法。ERM要最小化的是在未知數據分布上的風險上界。這個上界通常是在可獲得數據上的經驗風險加上一個正則化項，來控制分類器的複雜度。

假定有一個data source ，樣本記為 ，服從一個未知的分布 。 是一個包含 個點的有限數據集，這 個點是從同一個分布 中採樣得到的，也就是說他們是 的。

真實風險和經驗風險滿足以下的關係：

其中， 是損失函數， , 。

真實風險定義為損失函數的期望：

.

經驗風險定義為損失函數的經驗平均值：

.

損失函數 的Rademacher複雜度為：

是獨立隨機變數，稱為Rademacher變數。

這裡要求 中的數據是獨立同分布的。然而在主動學習的背景下，這個假設是站不住腳的。因為在主動學習中，標記數據是從另一個分布 中選出來的。

為了得到主動學習下的ERM準則，重新定義風險上界不等式：

是可獲得標記的數據上的經驗風險，包括初始的已知數據和後來標記得到的數據。 是基於這些標記數據的Rademacher複雜度。 是不同分布真實風險的差。

設 是 的上界， ，

不等式右邊的項正好就是兩個分布的最大平均差異(MMD, maximum mean discrepancy term):

主動學習的ERM風險上界最終可以寫成：

通過使用核方法，將MMD限制在一個RKHS中，核為 ,到非線性空間的映射為 。

那麼主動學習的ERM準則可以歸納為以下定理(證明略)：

參考文獻

Zheng Wang, JiepingYe. Querying discriminative and representative samples for batch mode active learning. KDD 2013: 158-166.