Machine Learning Techniques 笔记：2-11 Gradient Boosted Decision Tree
Random Forest基本上就是一堆的decision tree，在一堆的decision tree上，利用bagging方法做出不同的decision tree，再把他们合起来，除了基本的bagging，decison tree外，又在decision tree里面加入了更多的randomness，然后有了这个机制之后，这个模型可以自动validation，利用这个validation机制和permutation test还可以做到feature selection
Random Forest：外层是个bagging，用bootstrapping 方式的到一堆不一样的资料，内层是decision tree，当然有做一些randomized
如果将decision tree与Adaboost套在一起，每一轮会给资料新的weight u(t)，结合weight，利用decision tree学到g，得到g的票数后，把他们用linear的方式合起来。
需要结合weight
在Adaboot中有学到，有权重的演算法，应该要根据权重，想办法最佳化根据权重加权化的Ein
如何让下面的演算法确实应用权重呢？1>将演算法打开来看，看看原来在哪里处理Ein，在那些处理Ein的地方把权重放进去，例如SVM，SVM与Ein有关系的是它的最佳化里面的hinge那一项，可以把hinge那一项乘以相对应的权重，就可以让SVM根据这些权重得到不一样的g。
有的时候，像decision tree这类演算法，除了给大家的这些基本步骤之外，还有很多条作者的巧思，如果将演算法摊开来，看每一条巧思，看跟Ein是否相关，然后将权重放进去，这件事情会很麻烦。
2>我们想做的事情是，将原来的演算法当作是黑盒子完全不动，这是想办法在外面送进去演算法的资料，做一些手脚，只在资料上做一些变化，不更改演算法的部分。（这件事有可能做到，我们是如何得到权重的？我们从bagging出发，bootstrap重复的抽到几份，就给它权重是多少，权重为n，表示重复抽到n次，资料复制了n份），如果根据我的权重，先把我的资料做sampling（比如权重为30%，则给30%的几率选到资料），就可以得到一组新的资料，跟bagging那边很类似。这组新的资料中，每一种example的比例就大概就跟里面的比例u差不多，因而它就可以表达我们需要的权重的信息。
原来在bagging里面的做法是：先透过bootstrap得到好几份，这个好几份可以变成权重，利用权重的方式告诉底下的演算法。现在是底下的演算法不吃权重了，可不可以喂没有权重的data进来，可是我又想告诉它权重的资讯，怎么办？退回来一部，在资料那边作处理，根据我的权重，先把我的资料做抽样，做sample，根据权重抽样完之后，大体上权重的比例就会根资料里面的重要性的比例差不多，送进去原来的演算法，大概就可以根据它没有看到的权重信息得到不一样的g。
AdaBoot Decision Tree：演算法没有变，Decison Tree没有变，但通过权重u(t)做sampling，得到有点类似与bagging里面的Dquota，再送进去Adaboost
当我们送进adaboost里面之后，得到这个g，最终要决定g的票数，先算带权重的g的错误率有多少
如果是一个完全长成的树，所有的资料都不一样，这样切割先去之后会切的非常的碎，这样就可以保证每一笔看过的资料都能做对，Ein=0，加权后的Ein（u）=0，epsilo t=0，票数alpha t = 无限大
问题在于你把所有的data都丢下去，做成了一颗完全长成的树，怎么办？不要把所有的data都丢下去，做修剪，否则Adaboost只会告诉那一棵树，无法选择。
sampling：利用部分资料
Pruned：限制树的高度，只做大概的事情就好，不要做最好的。
什么是最弱的树？1层高
一层高是，CART只切一刀，想办法让两面加权的impurity越小越好，这样就是AdaBoost-Stump。这样，不用担心epsilo t = 0， 也不见得用做sampling的动作。 做sampling是因为decision tree很复杂，不想要到每个地方都看看什么时候要把权重加进去，做samping。 Desicion-stump 直接将sample丢进去，不做sampling，一般的decision tree则会做sampling。
sample出来之后error 为0，但原来完全资料上的weighted error不太一定，什么样的epsilo都有可能，因为什么样的alpha都有可能。
Adaboot的权重是根据前一轮的权重乘以或除以方块得到，用乘以或除以要看该资料在该轮的结果到底是错误还是正确。
yn（g（xn））同号，则正确，不同号则错误。
最后的u为原来的u一路的乘积===》变成连加
橘色的部分：volting score，利用分数的正负号，做G的判断。
与SVM相比，差别是没有截距b，
希望每个点的权重越小越好。 AdaBoost可以达到SVM largin margin的效果
Adaboost error band类似于SVM hinge error
Gradient Decent：如果要最小化某一个函数，可以从现在所在的点出发，看看附近往哪个方向走一小步，会变得比较好。以现有点处做taylor展开，会发现，沿着负梯度方向走，就会发现比现有的结果好一点点，一路走到谷底。
如果将函数g当作一个向量（函数与向量，只是index不同而已，函数的自变量是实数，向量为整数），找函数的最好的方向。
在原点附近做taylor展开
AdaBoost：steepest decent
exp（- eta）= -1， exp（+eta）= +1
如果看待指数error的话，Adaboost就是每一轮在这个error上面逐步做最优化，每一步找出一个h，把h当作g（t），决定这个g（t）要走多长距离，最终变成g（t）的票数就是a（t）。里面有两个部分，一部分关于h，另一部分关于eta，同样的概念，可否对不同的error function做优化？
里面的error function不一定是指数函数，换成任意何符合平滑条件的error函数，即是GradientBoost。
最常见的是使用实数输出的hypothesis，每一轮决定一个好的方向h，当作g（t）。选择一个新的eta，决定每一步走多远。像Ada Boost，比Adaboost更多元化。
Regression中用平方错误。当s-y为负，则给乘以正h；s-y为正，则乘以负h