本文參考整理了Coursera上由NTU的林軒田講授的《機(jī)器學(xué)習(xí)技法》課程的第七章的內(nèi)容，主要圍繞將不同hypotheses中具有預(yù)測性的features進(jìn)行融合的aggregation技術(shù)，講述了引入blending的動機(jī)，常用的blending方式（如uniform blending、linear blending和any blending等），介紹了利用bootstrapping技術(shù)的Bagging Meta Algorithm，并利用實(shí)際例子表現(xiàn)了aggregation的巨大威力和用處。文中的圖片都是截取自在線課程的講義。
歡迎到我的博客跟蹤最新的內(nèi)容變化。
如果有任何錯(cuò)誤或者建議，歡迎指出，感激不盡！
--
本系列文章已發(fā)七章，前六章的地址如下：
- 一、線性SVM
- 二、SVM的對偶問題
- 三、Kernel SVM
- 四、Soft-Margin SVM
- 五、Kernel Logistic Regression
- 六、Support Vector Regression
Blending和Bagging都是Aggregation里面非常典型的做法。
Aggregation的動機(jī)
日常選股
假設(shè)你有T個(gè)朋友g1，g2...gT預(yù)測某支股票X是否會上漲gt(X)
你會怎么做？
- 根據(jù)他們的平常表現(xiàn)選擇最可信的朋友---即validation
- 均衡(uniformly)地混合朋友們的預(yù)測---讓他們一人一票，最后選擇票數(shù)最多的結(jié)果
- 不均衡(non-uniformly)地混合朋友們的預(yù)測---每個(gè)人的票數(shù)不一，讓他們投票，而票數(shù)的分配和問題有關(guān)，比如有人擅長分析科技類股票，有人擅長分析傳統(tǒng)產(chǎn)業(yè)股票，因此在不同條件下，對不同人的信任度也不同，即如果[t 滿足某些條件]，則給朋友t多一些票。
- ...更多方式
對應(yīng)到機(jī)器學(xué)習(xí)里面，把T個(gè)人的意見融合起來以獲得更好的表現(xiàn)，就是aggregation模型，即aggregation models = mix or combine hypotheses for better performance.
數(shù)學(xué)形式
數(shù)學(xué)化以上操作：
- 選擇平常表現(xiàn)(val)最好的人
- 等額投票
- 不等額投票(包括情形1、2)
包含了：
- 選擇，即αt = [[ Eval(gt)最小 ]]
- 等額: 即αt = 1
- 根據(jù)條件合并預(yù)測(包括情形1、2、3)
- 包含了不等額投票，即qt(X)=αt。
aggregation model是一個(gè)非常豐富的家族。
aggregation與selection的對比
selection: 選擇出一個(gè)strong的hypothesis（強(qiáng)人主導(dǎo)）
aggregation: do better with many (possibly weaker) hypotheses（三個(gè)臭皮匠）
為什么aggregation可能會做得更好
- more power,more strong
如果只用垂直、水平線，怎樣都做不太好，而如果能把垂直和水平的線結(jié)合起來，則可能會做得比較好。
如果等額混合不同的弱弱的hypotheses，就可能會得到一個(gè)比較強(qiáng)的G(x)，比較復(fù)雜的邊界，類似于之前的feature transform，它也擴(kuò)展了我們的model的power。
- more moderate,more regularization
有若干條直線可以完美分割OO和XX，PLA會隨機(jī)選擇一條。如果等額混合不同的random-PLA hypotheses，則會收斂于中間那條large margin的直線，比較中庸，具有regularization的效果。因此aggregation具有more powerful和more regularization這兩種看似對立的效果。
Uniform Blending
uniform blending for classification
blending: 已知gt。
uniform blending: known gt each with 1 ballot
- 如果每個(gè)gt都一樣(獨(dú)裁政治)，則G和g的表現(xiàn)是相同的。
- 如果gt各不相同(多樣性+民主)，則多數(shù)派能糾正少數(shù)派。
- 對多類別分類，一樣的結(jié)果
對于regression如何做呢？
uniform blending for regression
- 每個(gè)gt都一樣，融合g效果變化不大
- 每個(gè)gt都不太一樣，有些gt(x) > f(x)，而有些gt(x) < f(x)，兩者抵消，平均值可能會比單一值更加準(zhǔn)確穩(wěn)定。
因此，如果我們的aggregation要起作用，很重要的前提是gt要各不一樣，暢所欲言，對于diverse hypotheses，即使使用非常簡單的uniform blending，也可以比任何單一的hypothesis表現(xiàn)得更好。
uniform blending for regression work的理論保證
先討論對于固定的確定的X
隨便選一個(gè)gt，期望意義下的square error是
將gt的期望錯(cuò)誤和G的錯(cuò)誤聯(lián)系在一起。
avg代表推廣到所有X上，對X分布取期望，得到
由此可知，最好的g是否比G好我們不得而知，但平均的g確實(shí)沒有G表現(xiàn)好，我們的uniform blending對于square error regression確實(shí)work了。
bias-variance decomposition
考慮一個(gè)虛擬迭代過程(t = 1,2...T)
- 第t輪，取得N筆資料Dt,Dt來自分布PN(i.i.d)
- 通過A(Dt)學(xué)習(xí)獲得gt
將剛剛得到的式子推廣到無窮大
把一個(gè)演算法的表現(xiàn)拆分成bias-variance decomposition。
而uniform blending就是減少variance，使表現(xiàn)更加穩(wěn)定。
Linear and Any Blending
linear blending
linear blending: known gt, each to be given αt ballot
什么樣的α是好的α?
min[αt>=0]Ein(α)
要求解的問題
有點(diǎn)類似two-level learning，先得到gt，再做LinReg。
linear blending = LinModel + hypotheses as transform + constraints
唯一的不同是要求αt>=0，而一般的LinReg沒有要求Wt>=0。
constraints on α
在實(shí)際中，我們常常故意忽略掉α的約束，如果αt<0，就把對應(yīng)的gt想象成gt'=-gt好了，對于regression可能比較奇怪，但是大部分時(shí)候constraints放在一邊沒有什么影響。
linear blending versus selection
之前我們都說gt直接給定，那么gt通常是怎么來的呢？
在實(shí)踐中，常常g1∈H1，g2∈H2 ... gT∈HT，即g是從不同的model通過求最好的Ein來得到的，就像之前在model selection中發(fā)生的事情一樣。
recall:
selection by minimum Ein --- best of best --- best of all
則 dvc = (∪Ht)，這也就是為什么我們要用Eval而不是Ein來做選擇。
recall:
linear blending 包含了 selection 作為特殊情況
即αt = [[ Eval(gt-) 最小 ]]
如果用Ein來做linear blending，即aggregation of best，模型復(fù)雜度代價(jià)比best of best還大，>= dvc = (∪Ht).
模型更加危險(xiǎn)，因此實(shí)踐中不建議使用Ein來選α，選擇α?xí)r讓Eval而不是Ein最小，gt-來自最小的E(train)。
Any Blending
從某個(gè)比較小的D(train)，訓(xùn)練得到g1-,g2-...,gT-，把Dval中的(xn,yn)轉(zhuǎn)換成(Zn=Φ-(xn),yn)，Φ-(X) = (g1-(X), g2-(X) ... gT-(X))。
linear blending
注意最后回傳的是Φ而不是Φ-，
我們不一定要用linear來合并{Zn,yn}，可以用任何方法，即Any Blending，也叫作Stacking.
對Z空間中的資料不一定用Linear model，可用Non-linear model
any blending:
- powerful，達(dá)成了根據(jù)條件來進(jìn)行blending的目的
- 有overfitting的危險(xiǎn)，要小心使用
Blending in Practice
資料來臨==>學(xué)習(xí)g==>validation set blending 得到G
- a special any blending model
E[test](squared): 519.45 ==> 456.24
- g、G 再做一次 linear blending ，test set blending: linear blending using Etest~
E[test](squared): 456.24 ==> 442.06
在實(shí)踐中，blending是非常有用的，如果不考慮計(jì)算負(fù)擔(dān)。
Bagging(Bootstrap Aggregation)
What We Have Done
blending: aggregate after getting gt
learning: aggregate as well as getting gt
gt的多樣性很重要，如何得到不一樣的g?
- 通過不同的模型: g1∈H1，g2∈H2 ... gT∈HT
- 同一模型的不同參數(shù): 如GD的不同的η,SVM中不同的C
- 演算法本來就有randomness: 如有不一樣的randome seeds的隨機(jī)PLA
- 資料的randomness: within-cross-validation hypotheses gv-
接下來，我們嘗試用同一份資料制造好多g，以產(chǎn)生多樣性。
Revisit of Bias-Variance
- consensus 比直接 A(D) 更加穩(wěn)定，但是需要很多筆資料
- 我們想要近似的g的平均，要做兩個(gè)妥協(xié)
- 無限大T(很大的T)
- 只使用手中資料D，生成T個(gè)近似的gt=A(Dt)，其中Dt~PN
我們需要用到統(tǒng)計(jì)學(xué)中的工具bootstrapping，它做的是從D中重新抽樣來模擬Dt。
Bootstrap Aggregation
sampling with replacement 有放回的抽樣
bootstrap aggregation：我們稱為BAGging，一個(gè)簡單的meta algorithm，在base algorithm A 之上。
Bagging Pocket In Action
每個(gè)Pocket演算法跑1000趟，使用25條Pocket線組合而成。
- 每個(gè)來自bagging生成的g都很不一樣
- aggregation后形成了還算合適的non-linear邊界來進(jìn)行二元分類
如果base algorithm對數(shù)據(jù)隨機(jī)性很敏感，則bagging通常工作得很好
在bootstrapping過程里，原來的N筆資料D里面再重新抽樣N個(gè)D'，則D'正好為D的可能性是N!/N^N。
Mind Map Summary
下一章我們講述是否可以得到比Bagging更加diverse的hypotheses，從而使blending后的G更加strong，即逐步增強(qiáng)法。歡迎關(guān)注！
