第7讲

Aggreation Model：a rich family

• select： 选一个最好的（E_val最小 ）

前提假设：有一个是好的，有一堆或这一些好的模型，才能从里面
选出来好的

• mix：uniformly投票得到（权重一样）

• mix：non-uniformly的投票（带权重的投票）【包含前两个例子】

• 通过某一个函数决定哪些g起作用 combine the predictions conditionally

Why Might Aggregation Work?

1. 可以扩展模型的能力[ feature transform]
2. 投票决定可以看做是选择一个中庸的结果（和SVM有类似的效果）[ regularization]

blending

手上已经有了g，怎么把它们合起来

• uniform blending

当g相同的时候，结果不会提升。不同的时候才有效。

分类问题：投票，回归问题：求平均

对于分类问题而言：多数可以纠正少数
对于回归问题而言:
very different g_t (diversity + democracy):
some g_t (x) > f(x), someg_t(x) < f(x)
⇒ average could be more accurate than individual

结论：even simple uniform blending can be better than any single hypothesis

理论的角度

理论证明

• Linear Blending(线性组合)

• Any Blending（Stacking）

• 总结：

  
  

• 如何得到不一样的g
  不通的模型，同样的模型不通的参数；模型本身的随机，数据的随机性。

Bagging（uniform的）

• 没有g的时候可以通过bootstrapping（又放回的抽取）选取数据学习得到不一样的g

第八讲

从一个辨认苹果的例子出发

• 学生：简单的g_t
• 整个班级：复杂的G
• 老师：演算法-关注犯过错误的那些点。

演算法长什么样子：

1. Bagging：通过bootstrap产生u_n然后用演算法取最小化带u的E_in。
2. 带u的如何训练--让u乘以错误。即u_n*err。对于SVM来说，a_n的上限改变，对LR来说，抽样的比例发生变化。

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

3. 从上一讲得知g越不一样，最后的结果越好。如何改变u让g尽可能的不一样。
   
   可以让g_t在新的数据上跟抛硬币没有什么区别。所有犯错的u和没有犯错误的u各占1/2。
   
   一边求g，一边求系数a。，
   则adaboost最终的流程为
   
   
   理论证明
   
   从boosting的角度：只要演算法正确率>1/2,那么通过Ada的方式得到的结果就非常好。

实践中的例子：

1. Decision Stump的例子。
2. 人脸识别。

总结：Bagging用的是unique的方式，Ada用的是linear(non-uniform)的方式（权重不同）

第九讲

之前学过的总结

Decision Tree可以看成是有条件的聚合
优点：

1. 可解释，易于理解
2. 模型简单（even freshmen can implement one）
3. 相对有效率

缺点：

1. 理论保证少
2. 如何选择合适的树结构对初学者来说比较困惑
3. 决策树代表性的演算法比较少

对于决策树来说需要关注的四点：划分为几部分，分支条件，终止条件，算法的返回值是什么

cart树：

1. 分两部分
2. g_t是常数

左-回归，右-分类

停止条件

cart算法过程
正则化：后剪枝
对类别数据的处理：one vs all
对缺失数据的处理（如果是分支条件）：选择一个和这个类别划分结果类似的属性划分，同时需要保存此属性(替代品)。
比较

比较

cart树的优点

9 -- Decision Tree

第十讲-随机森林

回顾：
Bagging算法：演算法不稳定，通过投票的方式可以降低variance。
DecisionTree：对不同的资料很敏感——large variance[especially if fully-grown]。

RF

优点：

• 容易并行化（bagging的特点）
• 继承了cart树的优点
• 多棵树投票，解决容易单颗树容易过拟合的问题

回到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. 大约只有三分之一的样本没有被选择到。

   
   

3. 右边：用验证资料衡量g_t因为这些资料从来没有见过，所以左边的也是这样的。

4. 然而我们需要的是验证G的表现。这一笔资料什么时候可以当做val的资料，没有用这笔资料训练的那些g，即可以用来当做G^-的验证资料。每一行都可以做出来一个G^-,然后求平均。不用另外做val的过程

5. val原来的用途：训练，验证，再训练-选择模型得出g
   自我验证的优点：不需要重复训练，通过self-validation调整完随机森林的系数之后，就完成了模型的建立。

RF用途：Feature Selection

数据存在冗余、或者和label无关的信息。如何自动的移除这些信息。

1. 做完Feature Selection

• 优点：有效率，剔除了噪音，不容易过拟合，可解释性强
• 缺点：如何选出来在计算上不太容易，可能会选择到了overfit，可能是错误的解释（关联性而不是因果关系）

2. 做法：
   1）看feature的重要性（线性模型里面|w_i|的大小代表着重要性）
   2）非线性的比较困难，使用RF解决（random test）原来的特征用别的信息替换，模型的表现变化情况。
   　　(1). uniform的，使用高斯分布生成数据
   　　(2). permutation test：把第i个维度的数据随便打乱。
   通过permutation test 的方式可以看出哪个特征重要。

• 如何衡量performance（需要val，自然的想到RF里面的OOB）
• 每一个特征都需要重新训练出来一个模型，因此作者又提出了一个改进，在OOB的资料上面做permutation ，这样最后的结果比较好
  
  供上PPT

总结

1. 使用很多棵树的时候得到的分类边界是平滑的，而且得到了large-margin的效果。
2. 在有噪音的数据上实验结果：noise corrected by voting
3. 树的个数越多模型的稳定性越好。RF的缺点：

第11讲 Gradient Boosted Decision Tree

一颗树完全的生长，在G中的权重变的无限大，则会变成独裁。所以需要解决这个问题：剪枝，只使用一部分样本也就是之前说到的抽样。

当限制树的高度=1的时候，AdaBoost-Stump = special case of AdaBoost-DTree

把每个点的权重都加起来，随着adaboost进行的过程希望这个值越小越好。就代表ada想要每个点的margin都越来越正，越来越大。

之后讲解了回归的GBDT找时间再次记录