看《A Course in ML》第十一章ensemble learning所做的笔记:

In this chapter, you will learn about various ways of combining into ensembles. One of the shocking results we will see is that you can take a learning model that only ever does slightly better than chance, and turn it into an arbitrarily good learning model, through a technique known as boosting. You will also learn how ensembles can decrease the variance of predictors as well as perform regularization.

Learning Objectives:

Implement bagging and explain how it reduces variance in a predictor.

实现bagging并解释为什么它可以降低方差

Explain the difference between a weak learner and a strong learner.

解释弱学习器和强学习器的不同

Derive the AdaBoost algorithm.

提出AdaBoost-adaptive boosting algorithm

Understand the relationship between boosting decision stumps and linear classification.

理解决策树桩的提升和线性分类器的关系

boosting方法的优点：

比随机猜测好一点点的弱分类器提升为一个很好的分类器

天生并行，训练和测试效率更高

降低方差，实施正则化的另一种方法

11.1 多个分类器投票

训练很多基础分类器：DT,perceptron,KNN,NN of different architectures,多者胜出

不是所有分类器都会犯同一个错误，如果每一个错误只有少数分类器犯下，那么你就会得到优化的分类器

不幸的是不同的算法倾向于饭同一类错误

对降低方差有效

二分类容易扩展到多分类问题，但不容易扩展到一下问题，因为很难得到相同的输出：回归：均值；排序，聚类需要不同的方法

在一个相通数据集上训练或者平分原来的数据集都不是很好的方法

一个数据集获得多个数据集：bootstrap resampling，原理：独立同分布，bagging

一个样例不被选中的概率：1-1/N 在一个集合中不出现的概率1-1/N的N次方，1/e==0.3679 N=1000（集合样本数量）是已经精确到4位小数

所以约有63%的原始样本会出现在所有的集合中

正则化-降低方差：通过使用超参数或bagging方法

尽管每一个分类器都overfit，但是对不同的特征overfit，通过投票，可以去除掉很大一部分overfit

图形对比：错误率-DT depth 错误率-num of bags

11.2 boosting weak learners

提升弱学习器：想起文件压缩-不断压缩直至1b

强学习算法定义-第十章：PAC (probably approximately correct)learning，以成功率y学习到一个算法,错误率必须降低到e

可以容易得到一个弱学习器：49%错误率，只要比随机猜测好就行

boosting相对来说是一种学习框架而不是一个算法

特定的boosting algorithm-AdaBoosting-adaptive boosting algorithm

第一个实用的boosting算法：多项式复杂度，不需定义很多的超参数，自动适应训练数据

与准备考试相比较，答对的问题降低注意力，答错的问题提高注意力（权重）

在训练数据上的权重分布d（初始化每个样本权重都是1/N），在这个有权重的数据集上训练弱学习器（假设可以接受加权样本数据，基本都是可以的），Fk的错误率用来决定这个函数的适应参数a，表示这个分类器结果的重要性。只要分类器的错误率小于50%，那么a就会大于零，如果错误率为0，那么这个分类器的适应参数就会无限大，相当于只需要这一个分类器的结果就够了。

a计算出来后，权重分布d在新一轮迭代中得到更新。分类正确的样本权重下降，分类错误的样本权重上升，Z是正则项，保证d的和为1。

算法最终返回结果：多个分类器的加权投票结果

一个具体的例子：对每个样本加权之后，如果要取得小于50%的错误率，就要有所更新。

shallow DT：with small depth

图形对比：一层的DT,多个boost 和 一个DT,深度逐渐增加的对比

decision stumps-AdaBoost起到了线性分类器的效果

一个具体的例子：
更进一步：最近的研究表明,AdaBoost算法优化目标为exponential loss

另一个例子：linear classifier-AdaBoost起到了两层神经网络的效果
K个线性分类器，K个隐藏单元，
仅仅是结构相同-但是参数学习方法不同，一旦学习到了线性分类器的W和b参数，就再也不会更新了。

11.3 random ensembles随机集成算法

选择决策树的结构非常耗时，树桩算法很高效

固定树的结构，随机选择特征（一个特征甚至可以在一个分支当中多次出现）：随机森林
D（数据），depth（树深），K（决策树的数量）

最终分类器：多个随机树的投票

这种方法效果很好：不同特征之间不相关时效果最好，因为每一棵树可能用到的特征很少。一些树会query无用的特征，产生随机猜测结果，可以作为噪声数据，最终只有好的决策树有效。