Udacity
Ensemble Learners
Boosting Algorithm
不需要絞盡腦汁去想很復(fù)雜的 Rules，只需要一些簡(jiǎn)單的 Rules，這就是 Ensemble 的基本主張，先找到簡(jiǎn)單的規(guī)則，每一條都有意義，但是單獨(dú)應(yīng)用都無法給出最佳答案，然后將這些規(guī)則結(jié)合起來成為一個(gè) Complex Rule，最后可以找到足夠好的答案。
比如：
Spam Email 是一個(gè)分類問題，除了用 Decision Tree，KNN，NN，還可以用 Boosting。
基本流程是：訓(xùn)練數(shù)據(jù)集的一個(gè)子集，得到一個(gè) simple rule，再訓(xùn)練另一個(gè)子集，得到另一個(gè) rule，訓(xùn)練多個(gè)后，得到多個(gè) simple rule，讓后將它們結(jié)合起來。
例如：只訓(xùn)練有圖片的郵件集，只訓(xùn)練有鏈接的郵件集，它們對(duì)于自己的相應(yīng)的子集是足夠好的，但是不是必須要對(duì)整個(gè)數(shù)據(jù)集很好。
如果用整個(gè)數(shù)據(jù)集來訓(xùn)練的話，會(huì)很難發(fā)現(xiàn)這些 simple rule。
訓(xùn)練子集和綜合，這兩步都可以由最簡(jiǎn)單的方法去完成，比如在訓(xùn)練每個(gè)子集時(shí)，得到10個(gè)數(shù)值，那最后就可以取平均值作為最終結(jié)果。
Bagging
隨機(jī)取點(diǎn)再去平均的方法叫做 Bagging 或者 Bootstrap Aggregation
例如：
紅色是訓(xùn)練數(shù)據(jù)集，綠色是測(cè)試數(shù)據(jù)，這是簡(jiǎn)單的 Cross Validation。
1.隨機(jī)抽取一個(gè)子集，每次隨機(jī)抽5個(gè)點(diǎn)，一共抽5次，并且每次的數(shù)據(jù)集不重復(fù)
2.要訓(xùn)練3階多項(xiàng)式
3.最后取平均值
比較不同方法得到的結(jié)果：
紅色：是用平均值算出的 Ensemble 的三階結(jié)果
藍(lán)色：是用四階回歸出來的
結(jié)果是：藍(lán)色在 Training 集上表現(xiàn)比紅色好，而紅色在 Testing 集上比藍(lán)色好
Boosting詳細(xì)
比起隨機(jī)挑取子集，我們應(yīng)該看看我們想要學(xué)習(xí)的是什么，去挑取我們不擅長(zhǎng)的數(shù)據(jù)，也就是這些例子是不是很難。
1.什么是hard problem
2.怎樣確保已經(jīng)訓(xùn)練過的子集 不再被訓(xùn)練
Error
如果是 vote，就是正確的有多少，錯(cuò)誤的有多少
如果是 value，就是類似于 mean squared error
只有當(dāng) Testing 和 Training 有相同的分布時(shí)，學(xué)習(xí)算法才會(huì)比較有效，
D：Distribution，這些 error 一定是符合某種分布的
h：hypothesis，是學(xué)習(xí)算法的結(jié)果
c：concept，是真正的結(jié)果
所以 Error 的定義是，在一個(gè) Distribution 下，h 不等于 c 的概率
和錯(cuò)誤個(gè)數(shù)算出來的區(qū)別是，有些是重要的，需要去學(xué)習(xí)的，有些是不重要的，而且這個(gè)概率表示的是有多少時(shí)候是對(duì)或者錯(cuò)的。
Weak Lerner：不管你的分布是怎樣的，得到的 Error 都小于0.5，
每一列代表一個(gè) hypothesis，每一行代表 instance space 的一個(gè)，即一共有4個(gè)example，要在三個(gè)h中找到 weak learner，也就是 error 大于0.5.
good：
如果四個(gè) example 都有相同的 weight，那么 h1 有三個(gè)對(duì)的，比0.5好，
evil：
如果把所有的 weight 都放在 x1 上，那么 h1,h2 做的特別差，但是 h3 做的特別好，同理，看 x2－x4，總是能找到某個(gè) h 得到好的結(jié)果，所以可能并沒有 evil distribution。
但其實(shí)，如果選擇 h1-h3，它們都有50%的error，
下面這個(gè)是個(gè)沒有 weak learner 的例子：
Boosting Algorithm
循環(huán)內(nèi)：
建立分布：是建立在某個(gè)時(shí)間t的examples之上的
在這個(gè)分布上：找到 weak classifier，這個(gè) weak learner 的 output 是某個(gè) hypothesis（ht），這個(gè) hypothesis 是有一些小 error 的，并不是非常小，而是只要小于 0.5 即可，
它在當(dāng)前分布的 training 數(shù)據(jù)集上表現(xiàn)還好
在當(dāng)前分布下，它錯(cuò)誤的概率很?。阂簿褪呛?training lable 不同的概率是小的
經(jīng)過循環(huán)，將找到最終的 hypothesis。
High Level Boosting：
1.如何找到 weak classifier
2.怎樣找到 distribution，怎樣找到 final hypothesis
例如：
最開始什么都不會(huì)的時(shí)候，分布可以是 uniform，得到 D1
遞推式解釋：
下一步的分布是以上一步為基礎(chǔ)，根據(jù)當(dāng)前的 hypothesis 表現(xiàn)的有多好，來變大或者變小，
yi 和 ht 都是返回 ＋1 或者 －1，所以當(dāng)二者 agree 時(shí)，結(jié)果是1，否則結(jié)果是 －1.
alpha 是正數(shù)，
所以 e 上面的指數(shù)，要么大于0，要么小于0，
那這個(gè)系數(shù)對(duì) D 的影響就是，要么增，要么減。
?Final Hypothesis
如何得到 final hypothesis？
weighted average － conbination
weight ＝ alpha t
sgn是個(gè)函數(shù)，ht是weak classifier，alpah t的公式如上圖， 和 underlining error 相關(guān)，如果你訓(xùn)練的好，weight就大，否則就小。
3 boxes 例子：
square rigon，要分類
先確認(rèn) hepothesis 的空間：在二維空間里，這個(gè)H要么是橫向，要么是縱向，它的一邊是正的，另外一邊是負(fù)的
第一個(gè)圖里，這個(gè) classifier，左邊都是正的，負(fù)的都在右邊，但是有三個(gè)正的被分到了右邊
所以在下一個(gè) distribution，會(huì)發(fā)生什么呢？
被分配正確的點(diǎn)其 weight 比較小，分配錯(cuò)的點(diǎn)其 weight 比較大
然后繼續(xù)得到第二個(gè) output，它只把 3個(gè)負(fù)的弄錯(cuò)了，剩下5個(gè)紅的在左邊，兩個(gè)負(fù)的在右邊
繼續(xù)在下一個(gè) distribution里，中間的3個(gè)負(fù)的，因?yàn)閯澐皱e(cuò)了，它們變得更突出，中間的3個(gè)正的，分對(duì)了，所以權(quán)重減小，但是仍然比最開始的要突出，比如最左邊的2個(gè)正的，一直都被劃分正確，那他們會(huì)消失
如上圖，最后得到三個(gè) hypothesis，將它們 combine 在一起，只是簡(jiǎn)單的 sum，就可以發(fā)現(xiàn)得到一個(gè)非常漂亮的分界線，將正負(fù)分開，這個(gè)效果很像 Decision Tree，Neural Network，和 Weighted Nearest Neighbor
