Learning Boosting Algorithms for Better Predictions (with R code)
Photo Source: http://www.datasciencecentral.com
在國外許多Data science 競賽中, Boosting algorithms是一個被廣泛使用的演算法, 用以提升預測模型的準確率, 尤其最近一段時間各大Data Hack比賽, 前3名的獲勝者幾乎都使用XGBoost模型取得關鍵性的突破。 與Random Forest algorithm一樣, Boosting algorithms也是ensemble models的一種machine learning approach, 讓我們能在相同的數據資料下, 使用較少的時間獲得大幅的預測效能躍進。在這篇文章, 我將簡單描述Boosting的原理概念, 讓大家能初步了解到Boosting algorithms的運作想法, 最後同樣附上一個簡單的實例, 展示如何利用Boosting algorithms進行數據的分類預測。
Introduction to Boosting
Boosting
algorithms最初開發用以解決分類(classification)預測的問題,
其概念在於藉由合併(combine)許多的weak
learner(classifier, predictor, etc) , 創造出一個高準確預測的模型(稱之為strong
learner/classifier). 所謂的weak learner可以視之為其模型的預測能力,
僅僅高於隨機猜測的結果。我們先簡單地以垃圾郵件辨識為例子, 說明為何ensemble
models(以Boosting為例-
combine many weak learners), 能產生出較強的預測模型。假設我們使用下列5條rules來判斷email是否為垃圾郵件:
1.
Email僅包含一張圖片 è 促銷圖片,
此封為垃圾郵件
2.
Email僅包含一個超鏈結網址 è 垃圾郵件
3.
Email內文包含”您贏得了 大獎
$” è 垃圾郵件
4.
Email寄件者為任職公司的網站 è 非垃圾郵件
5.
Email寄件者存在於聯絡人清單中 è 非垃圾郵件
這5條rules可分別視作weak
classifier, 單獨使用其中任何一個rule來進行垃圾郵件分類, 其辨識效果可想而知。但若我們將5條rules合併使用,
並將5條rules預測結果,
以簡單平均或是加權平均的方式計算出預測結果, 那麼我們將可以獲得一個較佳的預測能力模型。以上述為例, 3條rules認定為垃圾郵件,
2條rules認定為非垃圾郵件, 因此我們認定該封email為垃圾郵件。
Boosting algorithms並非簡單地以majority
votes(多數決)或平均數的方式, 來進行model
building. 不同類型的Boosting algorithms, 各自有不同的數學模型與建置邏輯。目前主流的Boosting
algorithms有:
- AdaBoost (Adaptive Boosting)
- Gradient Boosting
- XGBoost (eXtreme Gradient Boosting)
AdaBoost
下列之Algorithm 1(a), 參考Applied Predictive Modeling這本書中第14章Algorithm 14.2, 以處理分類問題為例(分成兩個類別, 例如:Yes/No), 描述AdaBoost的演算法。
AdaBoost Algorithm的核心概念, 在於將專注力放在那些較難處理的數據資料上。甚麼是較難處理的資料? 就是(前幾次)不斷預測錯誤的資料數據; 藉由不斷提升預測錯誤數據點的權重(直到此數據點被正確分類為止), 後續的分類模型必須調整專注在這些資料點上, 才能獲得最佳的分類錯誤比率。因此依據此處理邏輯, AdaBoost會有兩個特徵。
首先, 每次迴圈(for loop)的模型學習, 會受到前次的模型預測結果所影響(這就是有些解釋AdaBoost Algorithms的文章, 所說的後續訓練與前次訓練有依賴性或相關性). 因為前次預測正確的數據點,其權重會下降, 反之分類錯誤的資料全權重會增加。也因此後續每一次迴圈中, 每一個模型訓練所關注分析的資料區塊都會有所不同, 但方向上會是傾向那些最難分析,也就是一直分類錯誤的數據點。
第二, 基於上列邏輯, 隨著迴圈次數增加, AdaBoost模型會產生overfitting。一直預測錯誤的資料, 有可能是數據集中最難解決的部分, 因此就問題解決的角度來說, 解決最難處理的部分, 就表示我們完成了一個能處理整體的解決方案了; 然而若以另一角度來看, 一直預測錯誤的數據也可能是偏差值, 這些偏差(有人稱做noise), 僅僅是一時出現的特殊情況, 不會出現在將來未知的資料中, 將這些偏差值納入模型建置的考量, 會讓我們產生一個非通用型(general)的模型, 這樣的偏差模型, 在實際應用到非訓練資料的實際資料時, 將會產生極差的預測績效。
Algorithm 1(a)中的stage value,是依據該次的分類錯誤率計算得出。因此, 若該次的模型其錯誤率低, 則stage value就會比較高。不過由於AdaBoost使用week classifier模型, 因此stage value通常趨近於0。
我另外在這篇Post發現下列圖示說明, 能讓我們更容易理解AdaBoost Algorithm, 我參考該篇文章的內容, 重新整理並繪製圖型如下
Box 1: 一開始, 所有的資料權重都是一樣的, 我們使用了一個weak classifier(例如Decision stump, 將在稍後的文章解釋)進行數據分類, Decision stump產生了直線於D1的位置進行分類, D1左邊(藍色區塊)分為一個類別, 右邊則歸類成為另外一個類別。根據此結果, 可以發現右邊有3個菱形資料(Box1圖中標示為紅色的3個菱形圖示)分類錯誤。我們將此3個菱形資料權重增加, 也就是說, 再下一個模型建置時, “一定”要想辦法把這3筆資料分類正確。
Box 3: 與Box 2方式一樣, Decision stump產生了水平線於D3的位置進行分類。
Box 4: 將D1,D2,和D3 combine, 產生了如Box 4的strong classifier. 我們可以看到在Box 4圖示中, 菱形資料和星型資料完全正確的分類成兩個區塊。
AdaBoost其中一個經典的use case為Face Detection(臉部辨識)
簡單觀察上圖可以發現臉部辨識的分析流程, 與上例子Box1~4十分類似。更多的相關資訊, 讀者可以自行搜尋” AdaBoost Face Detection”等關鍵字結果。除了臉部辨識, 2000年之後, AdaBoost亦廣泛應用在gene expression, chemometrics, music genre identification等領域。
看起來還是很模糊? 我用另一個簡單的方式再來解釋描述一次。
上例中的error就是殘差(gradient/residual), 然後針對每一個error, 我們都繼續訓練建立model, 最後予以加總取得預測模型。
與AdaBoost一樣, Gradient Boosting同樣普遍使用CART model做為weak learner. 除了Tree model容易設計成為weak learner之外, CART model的模型建立速度快,而且加總多個CART models的預測結果也相對容易。當使用CART model進行Gradient Boosting時,基本上有兩個參數需設定, 一個為上述所提的迴圈(LOOP)次數, 另外一個是CART model的depth (又稱做為interaction depth)
Gradient Boosting與AdaBoost同樣會有over-fitting的問題產生。為了解決這個問題, Friedman使用了regularization(或稱為shrinkage)策略。其方法是在Gradient Boosting每一次LOOP中, 模型產生的預測值, 將不會全部更新至所有的訓練資料數據預測數字, 而是只取部分預測值更新。此比率數值稱之為learning rate, 以λ符號表示, 其數值介於0~1之間, 是Gradient Boosting需要訓練調整的參數。Friedman之後又引進了bagging的random sampling概念, 創造了stochastic gradient boosting模型。此模型在gradient boosting的每一次迴圈的第一步,改成隨機選取訓練數據進行後續模型訓練, 此隨機選取的比率稱為bagging fraction, 一樣介於0~1之間, 同樣也成為可以訓練調整的參數。
由於Boston Dataset要預測的response-medv 為continuous variable, 所以此為regression problem, 我們將distribution設定為gaussian. 首先我們建立一個training set, 並用此training Data建立Boost模型.
summary() function可以產生圖表和統計數字, 針對變數對於模型的影響程度進行排序.
由上圖可以看出, 最重要的兩個變數為lstat和rm. 我們可以針對此兩個變數產生partial dependence plots. 此圖可以看出選定之特定參數” integrate out”其他參數之後,對於response變數的的邊際影響(marginal effect)
從上圖可以看出, 當變數rm增加或變數lstat降低時, 預測的response-medv(median house prices) 會隨之上漲。
最後,我們使用上述boost模型,針對test data進行預測, 並使用test MSE檢測預測績效。
gbm的shrinkage參數預設值為0.001.我們可以使用不同的數值訓練產生不一樣模型來進行預測.
將shrinkage參數改為0.2之後,我們將test MSE從11.8478微幅下降至11.4231.
AdaBoost Algorithm的核心概念, 在於將專注力放在那些較難處理的數據資料上。甚麼是較難處理的資料? 就是(前幾次)不斷預測錯誤的資料數據; 藉由不斷提升預測錯誤數據點的權重(直到此數據點被正確分類為止), 後續的分類模型必須調整專注在這些資料點上, 才能獲得最佳的分類錯誤比率。因此依據此處理邏輯, AdaBoost會有兩個特徵。
首先, 每次迴圈(for loop)的模型學習, 會受到前次的模型預測結果所影響(這就是有些解釋AdaBoost Algorithms的文章, 所說的後續訓練與前次訓練有依賴性或相關性). 因為前次預測正確的數據點,其權重會下降, 反之分類錯誤的資料全權重會增加。也因此後續每一次迴圈中, 每一個模型訓練所關注分析的資料區塊都會有所不同, 但方向上會是傾向那些最難分析,也就是一直分類錯誤的數據點。
第二, 基於上列邏輯, 隨著迴圈次數增加, AdaBoost模型會產生overfitting。一直預測錯誤的資料, 有可能是數據集中最難解決的部分, 因此就問題解決的角度來說, 解決最難處理的部分, 就表示我們完成了一個能處理整體的解決方案了; 然而若以另一角度來看, 一直預測錯誤的數據也可能是偏差值, 這些偏差(有人稱做noise), 僅僅是一時出現的特殊情況, 不會出現在將來未知的資料中, 將這些偏差值納入模型建置的考量, 會讓我們產生一個非通用型(general)的模型, 這樣的偏差模型, 在實際應用到非訓練資料的實際資料時, 將會產生極差的預測績效。
Algorithm 1(a)中的stage value,是依據該次的分類錯誤率計算得出。因此, 若該次的模型其錯誤率低, 則stage value就會比較高。不過由於AdaBoost使用week classifier模型, 因此stage value通常趨近於0。
我另外在這篇Post發現下列圖示說明, 能讓我們更容易理解AdaBoost Algorithm, 我參考該篇文章的內容, 重新整理並繪製圖型如下
Box 1: 一開始, 所有的資料權重都是一樣的, 我們使用了一個weak classifier(例如Decision stump, 將在稍後的文章解釋)進行數據分類, Decision stump產生了直線於D1的位置進行分類, D1左邊(藍色區塊)分為一個類別, 右邊則歸類成為另外一個類別。根據此結果, 可以發現右邊有3個菱形資料(Box1圖中標示為紅色的3個菱形圖示)分類錯誤。我們將此3個菱形資料權重增加, 也就是說, 再下一個模型建置時, “一定”要想辦法把這3筆資料分類正確。
Box
2: 由於一定要將上方3個菱形資料分類正確(我將菱形圖示放大,並將邊框加粗以表示此3筆資料此時擁有較高的權重),
在這個資料情況下, Decision stump產生了直線於D2的位置進行分類。此時上方3個菱形資料成功分類正確,
D2右邊的資料也分類正確, 但卻
另外產生3個星型資料(Box2圖中標示為紅色的3個星型圖示)的分類錯誤。同樣, 我們將此3個星型資料權重增加。Box 3: 與Box 2方式一樣, Decision stump產生了水平線於D3的位置進行分類。
Box 4: 將D1,D2,和D3 combine, 產生了如Box 4的strong classifier. 我們可以看到在Box 4圖示中, 菱形資料和星型資料完全正確的分類成兩個區塊。
AdaBoost其中一個經典的use case為Face Detection(臉部辨識)
簡單觀察上圖可以發現臉部辨識的分析流程, 與上例子Box1~4十分類似。更多的相關資訊, 讀者可以自行搜尋” AdaBoost Face Detection”等關鍵字結果。除了臉部辨識, 2000年之後, AdaBoost亦廣泛應用在gene expression, chemometrics, music genre identification等領域。
Boosting可以應用於結合任何的機器學習技術,
但絕大部分是使用CART(Classification And RegressionTree)演算法技術。原因在於, 藉由限制Decision tree depth, 例如,
只split一次(我們稱這種split次數非常少的結構為Decision
stump), 我們可以很容易的建立Boosting演算法的基礎分類器-
weak classifier. Breiman L (1998) 於這篇文章中解釋了為何CART model特別適合運用Boosting:
由於CART
model是一種low bias(針對模型訓練資料的錯誤率極低,預測效果極佳)
/ high variance(一更換資料數據, 預測效果就會落差極大)的機器學習技術,
而藉由Boosting演算法”ensemble”多個CART
model, 我們可以建立出一個
low bias而且low variance的預測模型。也因此, 對於其他像是KNN, Regression等low variance的演算法, Boosting能夠改善的預測績效就不明顯了。Gradient Boosting
2001年Friedman將AdaBoost與統計學的理論
- loss functions, additive modeling, and logistic regression結合,
創造出了新的Boosting演算法 - Gradient Boosting
(GBM). Gradient Boosting的基本原則如下:
1.
應用loss function(例如迴歸模型的squared
error)以及 weak learner(例如regression
trees)
2.
訓練additive model以最小化(minimize)這個loss
function
3.
演算法的第一步, 先以簡單的猜測(例如平均數)產生第一個預測
4.
計算殘差(gradient/residual), 即將每一筆訓練資料數據(response)扣減預測值
5.
針對上列殘差數據進行模型訓練, 最小化(minimize)
loss function
6.
利用上述(5.)建立的模型產生預測值,產生完畢之後更新訓練資料數據預測數字(例如,若為第一次LOOP,則更新猜測的平均數)
7.
將這一個LOOP的模型與上一個LOOP的模型相加,
此LOOP一直持續到事先選定之次數為止
看起來還是很模糊? 我用另一個簡單的方式再來解釋描述一次。
我們假設Y值可以用一個function
M(x),加上一個誤查值產生:
Y=M(x) + error
其中上述的error值, 一樣可以用另外一個function
G(x),加上一個誤查值表示:
error = G(x) + error2
同樣地,error2一樣可透過function
H(x)描述
error2 = H(x) + error3
讓我們將上述的model合併,
我們就可以得到:
Y= M(x) + G(x) + H(x) + error3
我們也可以再優化上列的公式, 將不同的function給予不同的權重
Y= a1*M(x) + a2*G(x) + a3*H(x) +
error4
上例中的error就是殘差(gradient/residual), 然後針對每一個error, 我們都繼續訓練建立model, 最後予以加總取得預測模型。
與AdaBoost一樣, Gradient Boosting同樣普遍使用CART model做為weak learner. 除了Tree model容易設計成為weak learner之外, CART model的模型建立速度快,而且加總多個CART models的預測結果也相對容易。當使用CART model進行Gradient Boosting時,基本上有兩個參數需設定, 一個為上述所提的迴圈(LOOP)次數, 另外一個是CART model的depth (又稱做為interaction depth)
Gradient Boosting與AdaBoost同樣會有over-fitting的問題產生。為了解決這個問題, Friedman使用了regularization(或稱為shrinkage)策略。其方法是在Gradient Boosting每一次LOOP中, 模型產生的預測值, 將不會全部更新至所有的訓練資料數據預測數字, 而是只取部分預測值更新。此比率數值稱之為learning rate, 以λ符號表示, 其數值介於0~1之間, 是Gradient Boosting需要訓練調整的參數。Friedman之後又引進了bagging的random sampling概念, 創造了stochastic gradient boosting模型。此模型在gradient boosting的每一次迴圈的第一步,改成隨機選取訓練數據進行後續模型訓練, 此隨機選取的比率稱為bagging fraction, 一樣介於0~1之間, 同樣也成為可以訓練調整的參數。
Application with R code
在這篇Post, 我使用An Introduction to Statistical Learning書中第八章關於Boosting的範例程式, 說明Boosting演算法的應用。書中使用R package - MASS中的Boston資料集(Boston Housing values and other information about Boston suburbs), 進行分析。首先, 可以使用下列程式碼取得Boston資料集的簡單說明library(MASS)
?Boston
n
distribution參數: 此參數用於設定分析預測目標(response)的型態。若是regression
problem, 則distribution = " gaussian", 其weak learner即使用regression
trees建立模型; 若為binary classification
problem, 則distribution = "bernoulli",其weak
learner即使用classification trees建立模型.
要注意的是gbm function僅能處理2-Class的分類問題,
也就是說,預測結果僅能分成兩個類別, 若要分類成3個以上,
gbm 無法處理。
n
針對classification problem,
gbm function的預測回傳值為0或1. 若想取得class
probability, 則可在執行predict function指定type=”response”.
gbmPredict
<- predict(gbmModel, type = "response")
n
n.tree參數: 模型要產生幾個tree模型,
也就是上列說明中的LOOP次數。如前所述, 若此參數設定過大,
Boosting容易over-fitting. 我們可以使用cross-validation來調校(tuning)此參數數值。
n
shrinkage參數:即learning
rate, λ. 一般設定值為0.01 或
0.001
n
interaction.depth參數:每個tree模型的splits數量;
此參數控制boosting模型的複雜度。一般設定1, 即single
split, 即可獲得不錯的績效結果。
由於Boston Dataset要預測的response-medv 為continuous variable, 所以此為regression problem, 我們將distribution設定為gaussian. 首先我們建立一個training set, 並用此training Data建立Boost模型.
library(gbm)
set.seed(1)
train = sample(1: nrow(Boston), nrow(Boston)/2)
boost.boston =gbm(medv~.,data=Boston[train,], distribution= "gaussian",n.trees =5000,interaction.depth =4)
summary() function可以產生圖表和統計數字, 針對變數對於模型的影響程度進行排序.
由上圖可以看出, 最重要的兩個變數為lstat和rm. 我們可以針對此兩個變數產生partial dependence plots. 此圖可以看出選定之特定參數” integrate out”其他參數之後,對於response變數的的邊際影響(marginal effect)
par(mfrow =c(1,2))
plot(boost.boston ,i="rm")
plot(boost.boston ,i="lstat")
從上圖可以看出, 當變數rm增加或變數lstat降低時, 預測的response-medv(median house prices) 會隨之上漲。
最後,我們使用上述boost模型,針對test data進行預測, 並使用test MSE檢測預測績效。
par(mfrow =c(1,2))
plot(boost.boston ,i="rm")
plot(boost.boston ,i="lstat")
yhat.boost=predict(boost.boston ,newdata =Boston [-train,],n.trees =5000)
boston.test=Boston[-train,"medv"]
mean((yhat.boost - boston.test)^2)
gbm的shrinkage參數預設值為0.001.我們可以使用不同的數值訓練產生不一樣模型來進行預測.
boost.boston=gbm(medv~.,data=Boston[train,], distribution="gaussian",n.trees =5000, interaction.depth =4, shrinkage =0.2,
verbose =F)
yhat.boost=predict(boost.boston ,newdata =Boston[-train ,],
n.trees =5000)
mean((yhat.boost - boston.test)^2)
將shrinkage參數改為0.2之後,我們將test MSE從11.8478微幅下降至11.4231.
by J.D.
