第7講

Aggreation Model：a rich family

• select： 選一個(gè)最好的（E_val最小 ）

前提假設(shè)：有一個(gè)是好的，有一堆或這一些好的模型，才能從里面
選出來(lái)好的

• mix：uniformly投票得到（權(quán)重一樣）

• mix：non-uniformly的投票（帶權(quán)重的投票）【包含前兩個(gè)例子】

• 通過(guò)某一個(gè)函數(shù)決定哪些g起作用 combine the predictions conditionally

Why Might Aggregation Work?

1. 可以擴(kuò)展模型的能力[ feature transform]
2. 投票決定可以看做是選擇一個(gè)中庸的結(jié)果（和SVM有類似的效果）[ regularization]

blending

手上已經(jīng)有了g，怎么把它們合起來(lái)

• uniform blending

當(dāng)g相同的時(shí)候，結(jié)果不會(huì)提升。不同的時(shí)候才有效。

分類問(wèn)題：投票，回歸問(wèn)題：求平均

對(duì)于分類問(wèn)題而言：多數(shù)可以糾正少數(shù)
對(duì)于回歸問(wèn)題而言:
very different g_t (diversity + democracy):
some g_t (x) > f(x), someg_t(x) < f(x)
? average could be more accurate than individual

結(jié)論：even simple uniform blending can be better than any single hypothesis

理論的角度

理論證明

• Linear Blending(線性組合)

• Any Blending（Stacking）

• 總結(jié)：

  
  

• 如何得到不一樣的g
  不通的模型，同樣的模型不通的參數(shù)；模型本身的隨機(jī)，數(shù)據(jù)的隨機(jī)性。

Bagging（uniform的）

• 沒(méi)有g(shù)的時(shí)候可以通過(guò)bootstrapping（又放回的抽取）選取數(shù)據(jù)學(xué)習(xí)得到不一樣的g

第八講

從一個(gè)辨認(rèn)蘋果的例子出發(fā)

• 學(xué)生：簡(jiǎn)單的g_t
• 整個(gè)班級(jí)：復(fù)雜的G
• 老師：演算法-關(guān)注犯過(guò)錯(cuò)誤的那些點(diǎn)。

演算法長(zhǎng)什么樣子：

1. Bagging：通過(guò)bootstrap產(chǎn)生u_n然后用演算法取最小化帶u的E_in。
2. 帶u的如何訓(xùn)練--讓u乘以錯(cuò)誤。即u_n*err。對(duì)于SVM來(lái)說(shuō)，a_n的上限改變，對(duì)LR來(lái)說(shuō)，抽樣的比例發(fā)生變化。

延伸example-weighted learning: extension of class-weighted learning in Lecture 8 of ML Foundations

3. 從上一講得知g越不一樣，最后的結(jié)果越好。如何改變u讓g盡可能的不一樣。
   
   可以讓g_t在新的數(shù)據(jù)上跟拋硬幣沒(méi)有什么區(qū)別。所有犯錯(cuò)的u和沒(méi)有犯錯(cuò)誤的u各占1/2。
   
   一邊求g，一邊求系數(shù)a。，
   則adaboost最終的流程為
   
   
   理論證明
   
   從boosting的角度：只要演算法正確率>1/2,那么通過(guò)Ada的方式得到的結(jié)果就非常好。

實(shí)踐中的例子：

1. Decision Stump的例子。
2. 人臉識(shí)別。

總結(jié)：Bagging用的是unique的方式，Ada用的是linear(non-uniform)的方式（權(quán)重不同）

第九講

之前學(xué)過(guò)的總結(jié)

Decision Tree可以看成是有條件的聚合
優(yōu)點(diǎn)：

1. 可解釋，易于理解
2. 模型簡(jiǎn)單（even freshmen can implement one）
3. 相對(duì)有效率

缺點(diǎn)：

1. 理論保證少
2. 如何選擇合適的樹結(jié)構(gòu)對(duì)初學(xué)者來(lái)說(shuō)比較困惑
3. 決策樹代表性的演算法比較少

對(duì)于決策樹來(lái)說(shuō)需要關(guān)注的四點(diǎn)：劃分為幾部分，分支條件，終止條件，算法的返回值是什么

cart樹：

1. 分兩部分
2. g_t是常數(shù)

左-回歸，右-分類

停止條件

cart算法過(guò)程
正則化：后剪枝
對(duì)類別數(shù)據(jù)的處理：one vs all
對(duì)缺失數(shù)據(jù)的處理（如果是分支條件）：選擇一個(gè)和這個(gè)類別劃分結(jié)果類似的屬性劃分，同時(shí)需要保存此屬性(替代品)。
比較

比較

cart樹的優(yōu)點(diǎn)

9 -- Decision Tree

第十講-隨機(jī)森林

回顧：
Bagging算法：演算法不穩(wěn)定，通過(guò)投票的方式可以降低variance。
DecisionTree：對(duì)不同的資料很敏感——large variance[especially if fully-grown]。

RF

優(yōu)點(diǎn)：

• 容易并行化（bagging的特點(diǎn)）
• 繼承了cart樹的優(yōu)點(diǎn)
• 多棵樹投票，解決容易單顆樹容易過(guò)擬合的問(wèn)題

回到Bagging的角度

Out-Of-Bag資料

1. 紅色 in t-th column: not used for obtaining g_t—called out-of-bag (OOB) examples of g _t

2. 大約只有三分之一的樣本沒(méi)有被選擇到。

   
   

3. 右邊：用驗(yàn)證資料衡量g_t因?yàn)檫@些資料從來(lái)沒(méi)有見(jiàn)過(guò)，所以左邊的也是這樣的。

4. 然而我們需要的是驗(yàn)證G的表現(xiàn)。這一筆資料什么時(shí)候可以當(dāng)做val的資料，沒(méi)有用這筆資料訓(xùn)練的那些g，即可以用來(lái)當(dāng)做G^-的驗(yàn)證資料。每一行都可以做出來(lái)一個(gè)G^-,然后求平均。不用另外做val的過(guò)程

5. val原來(lái)的用途：訓(xùn)練，驗(yàn)證，再訓(xùn)練-選擇模型得出g
   自我驗(yàn)證的優(yōu)點(diǎn)：不需要重復(fù)訓(xùn)練，通過(guò)self-validation調(diào)整完隨機(jī)森林的系數(shù)之后，就完成了模型的建立。

RF用途：Feature Selection

數(shù)據(jù)存在冗余、或者和label無(wú)關(guān)的信息。如何自動(dòng)的移除這些信息。

1. 做完Feature Selection

• 優(yōu)點(diǎn)：有效率，剔除了噪音，不容易過(guò)擬合，可解釋性強(qiáng)
• 缺點(diǎn)：如何選出來(lái)在計(jì)算上不太容易，可能會(huì)選擇到了overfit，可能是錯(cuò)誤的解釋（關(guān)聯(lián)性而不是因果關(guān)系）

2. 做法：
   1）看feature的重要性（線性模型里面|w_i|的大小代表著重要性）
   2）非線性的比較困難，使用RF解決（random test）原來(lái)的特征用別的信息替換，模型的表現(xiàn)變化情況。
   　　(1). uniform的，使用高斯分布生成數(shù)據(jù)
   　　(2). permutation test：把第i個(gè)維度的數(shù)據(jù)隨便打亂。
   通過(guò)permutation test 的方式可以看出哪個(gè)特征重要。

• 如何衡量performance（需要val，自然的想到RF里面的OOB）
• 每一個(gè)特征都需要重新訓(xùn)練出來(lái)一個(gè)模型，因此作者又提出了一個(gè)改進(jìn)，在OOB的資料上面做permutation ，這樣最后的結(jié)果比較好
  
  供上PPT

總結(jié)

1. 使用很多棵樹的時(shí)候得到的分類邊界是平滑的，而且得到了large-margin的效果。
2. 在有噪音的數(shù)據(jù)上實(shí)驗(yàn)結(jié)果：noise corrected by voting
3. 樹的個(gè)數(shù)越多模型的穩(wěn)定性越好。RF的缺點(diǎn)：

第11講 Gradient Boosted Decision Tree

一顆樹完全的生長(zhǎng)，在G中的權(quán)重變的無(wú)限大，則會(huì)變成獨(dú)裁。所以需要解決這個(gè)問(wèn)題：剪枝，只使用一部分樣本也就是之前說(shuō)到的抽樣。

當(dāng)限制樹的高度=1的時(shí)候，AdaBoost-Stump = special case of AdaBoost-DTree

把每個(gè)點(diǎn)的權(quán)重都加起來(lái)，隨著adaboost進(jìn)行的過(guò)程希望這個(gè)值越小越好。就代表ada想要每個(gè)點(diǎn)的margin都越來(lái)越正，越來(lái)越大。

之后講解了回歸的GBDT找時(shí)間再次記錄