0. 前言
先回忆一下， 在随机森林中， 用bagging + decision tree训练了一堆小决策树，然后用投票的方式将这些树组合起来形成随机森林：
那么AdaBoost是否也可以与决策树结合呢？
1. Weighted Decision Tree Algorithm
在决策树中，对于输入数据是平等对待的，也就是说所有数据的权重是一样的。那么如果我们想要一个可以接受权重的决策树$DTree(\mathcal{D},u^{(t)})$，该怎么做呢？
第一个方法就是修改决策树内部的error function，使每一个样本的error值乘上对应的权重：
但是这个方法要修改算法内部，更多的时候我们希望把决策树当成一个黑盒子。所以第二个方法就是在输入数据上动手脚：按照权重比例对数据进行采样。即权重更大的数据有更高的概率被采到。
2. AdaBoost
简单的说AdaBoost是将一堆estimators线性组合起来，现在我们的base estimator是决策树，剩下要决定的就是每棵决策树的权重$\alpha_t$：
$$\alpha_t = ln\sqrt{（1-\epsilon_t） / \epsilon_t}$$
其中$\epsilon_t$是对应决策树的weighted error rate。这样error越大的树占的权重就越小。
但是如果有一颗在所有数据集上fully growned的树，它的$\epsilon_t$是0，那么对应的$\alpha_t$就是无穷大，这显然不是我们想要的结果。所以有两个措施需要采取来避免这种独裁情况：
-
pruned：对决策树进行剪枝（限制树的高度）
-
sampling：对数据进行部分采样，用于训练
base estimator
3. AdaBoost Decision Tree
所以，总结起来以下就是AdaBoost Decision Tree：
4. Weights of AdaBoost
那么问题来了，如何更新权重$u^{(t)}$呢？
