具有自學習(Self-paced learning)的集成學習(Boosting)分類器--(IJCAI 2016)--論文筆記

論文《Self-Paced Boost Learning for Classification》

論文地址：http://www.isee.zju.edu.cn/dsec/pdf/ijcai16_586.pdf

此論文被IJCAI2016收錄，工作的核心思想是將Boosting演算法和Self-paced learning演算法結合在一起，它們能夠分別解決監督學習中的有效性和魯棒性的問題。通過帶self-paced樣本選擇法的max-margin boosting最優化，能夠對數據分類的同時，保證良好的採樣方式。

貢獻：

1、第一次將self-paced方法和boosting方法相結合的分類演算法；

2、提出了相應的優化方法。

演算法內容

Self-paced learning(SPL)：簡單來說是指在訓練模型時，先學習簡單的樣本，後學習複雜的樣本，這個過程就好像人類學習新知識的過程，具體可參考[1]。

Boosting：在深度學習出來之前，集成學習可以說是使用得最多、效果最好的方法之一。它的核心思想是將多個弱分類器集成在一起，著重訓練分類正確率低的分類器，集成的分類器有著很好的分類能力，並且不容易出現過擬合。

定義一個監督學習問題，設訓練集為{x,y}，分別代表訓練集樣本及其類別標籤。標準的監督學習問題會學習一個得分函數F()，這個函數對應輸入樣本通過模型得到的每個類別的得分情況，即預測結果，有：

其中， 表示樣本x屬於類別r的置信度， 表示模型的參數，目標函數可以定義為：

其中 表示xi通過模型得到類別r的置信度和ground truth y的置信度之間的差異（margin）；L()表示loss function，R()表示對模型參數的正則化；v表示一個trade-off超參數。

同時可以定義得分函數F的形式，它其實就是Boosting的一般形式，多個弱分類器h(x)的集合：

其中，h可以定義為

wrj指分類器的權重，h(x)為一個{0,1}的二值弱分類器。

將[1]中的SPL方法進入的到目標函數中可以得：

其中H表示弱分類器的結果，有

表示SPL的權重，它體現了樣本xi學習的「容易」程度。 表示樣本的選擇方式。

將L定義為一個logistic loss，R(W)定義為l2,1-範數，可得：

其中SPL方法學習vi，boosting方法學習權重W。

最優化

這裡分別交替優化SPL的v和boosting的權值W。

最優化v

目標函數可以寫成

表示樣本xi的loss，且有

最終可以得到最優的vi

最優化W

目標函數可以寫成

這是一個帶約束的最優化問題，可是利用拉格朗日乘子法對其進行求解。設拉格朗日乘子為 ，可以寫出其對偶形式，來求 ，推到過程可以參考[2]中的(36)~(38).

有

對於 ，通過觀察可以發現，當 的值越小時， 的值越大；當 的值越大時， 的值越大。這表明， 可以控制模型去選擇學習不充分的弱分類器和簡單的樣本，這樣就集合了Boosting和SPL的特點。

這裡使用列生成（column generation）方法，對於每一類，從弱分類器集合中選擇一個最好的 ，有

r表示對應的類別。

演算法的更新方式如圖1所示，演算法偽代碼如表1所示。

圖1 演算法計算流程圖

表1 偽代碼

總結

本文的核心思想是將Boosting和Self-paced learning結合在一起，從而獲得一種兼具有效性和魯棒性的分類方法，該方法具有比較強的通用性，可以應用到多種分類問題中。

參考

[1]Self-Paced Learning for Matrix Factorization.

[2]A Direct Approach to multi-class Boosting and Extentions.