lec-24-2 Ensemble Learning

Boosting 的框架是一种【不断补强】的框架，这就要求

1. f is diversity
2. framework is sequencial

为了保证获取到不同的分类器，可以用以下措施：
1. 从【数据集】中放回取样形成新的子数据集用来训练不同的分类器
2. 给不同的【数据点】以不同的权重－－相当于【模拟其出现次数】，0.4 就是这个点出现 0.4 次
   2 就是这个点出现 2 次。这样不同的点不同的权重，就可以获得不同的分类器。
   那么新的数据点的表达方式就从 (x1,y1) ---> (x1,y1,u1)
   其实改变数据点的权重就相当于改变其出现次数 ---> 相当于改变数据集的 distribution_
3. 2 中会产生不同的 loss-fn, 因为每个点出现次数不同了，所以 loss-fn 计算所有点出
   错之和，也应该根据这个点【出现次数】来相应增加他 error 的比重

>>> 如何产生【互补】的效果
让 f2 的训练集是 f1 没有看过的并且在 f1 上表现很差的数据

>>> 如何找到让 f1 表现很差的数据
调整 f1 的训练集数据点的 weight: u1 --> u2, 用 u2 去训练 f2.
ppt 上 u_1^n : 第 '1' 个分类器的训练集中的第 'n' 个 data

>>> 新的衡量分类器在某个数据集表现好坏的标准：ε
ε1 = 1 号分类器有错的数据点的 weight 之和 / 1 号分类器所有的数据点的 weight 之和
ε1 总是 < 0.5 的，可以保证这一点，为甚么呢？ 如果他大于 0.5 我就把他贰元分类的输出结果
反过来，就保证他又是 < 0.5 的了。

目标是，让 u2 在 1 号分类器上的 ε = 0.5
(刚才分析过 ε 永远 <= 0.5)取其最差情况就是 0.5, 接近 random -- 瞎猜。
>>> 如何调整 u1 成 u2 呢？
u2 = 让 u1 中做错的数据权重变大，u1 中做对的数据权重变小
u1 right: u2 <- u1*d1
u1 wrong: u2 <- u1/d1
d1 = sqrt((1-ε1)/ε1)

T: 找 T 个弱鸡分类器

如何整合这个 T 个分类器呢？民主政治：每人投一票（分类器的权重），然后加总计算，看【加总之后结果的正负号】就可以得到贰元结果。精英政治：每个人按照自己的错误率的某个函数 αt 来给不同的票数，余同。

改变 weight 其实就相当于 改变出现次数，也就相当于改变分布（distribution）

注意每次搞出一个 f ,都要记录下其对应 α，他会是 f 的权重，最后总和所有 f 的时候，要用到。

三个 f 把整个平面分成 6 块，每一块的判定结果，都是三个 f 的输出的权重和的符号

As we have more and more ft (T increases), H(x) achieves smaller and smaller error rate on training data. 证明：num of ft ^^^ ===> error-rate of H(x) ↓

绿色式子有一个 upbound 也就是蓝色划线式子

如果能证明 Zt+1 随着 t 越来越大，他越来越小的话，就可以证明这个 error-rate 的 upbound 越来越小。

随着 error-rate 的 upbound 越来越小，error-rate 最终就会变成 0

注意： 我们可以 boosting weak classifiers
我们能否 boosting a boosted weak classifier 么？
很显然，不行，boosting 是通过不断更新每个样本点的权重 u 来做的。
而更新权重 ul <- ul-1*d or ul <- ul-1/d
d = sqrt((1-ε)/ε）
boosting weak classifier 本身就是 error-rate = 0
嵌套 boost, 就会让 d 变成 无穷大， 所以 boosting 的对象只能是 weak classifier

boosting 5 个 classifier 已经让 error-rate 为 0 了。 boosting >5 个 classifier 会让 margin 越来越大。也就是 adaboost 即使在 error-rate 为 0 时，还是会使劲让 margin 更大。

Adaboost 虽然没有明确的最小化某个函数，但是他确实让 upbound 这个表达式越来越小。

Bagging -> random forest Boosting -> Adaboost

s 可以看到：

>>> Bagging and Boosting
---------------------------------------------------------------------------
Bagging 只是降低 overfitting 增加函数 smoothness, Bagging 之后的模型的能力没有增强
Boosting 没有增加函数 smoothness, 但是 Boosting 之后模型的能力却加强了
这也符合 Boosting 的特点－－所有的 classifer 都是互补的
---------------------------------------------------------------------------

>>> Bagging
. | Bagging-num of DT ↑  | variance-error ↓  | smoothness ↑  | overfitting ↓     |
. |                      | bias-error =      | fittness =    | power of model =  |
. |----------------------+-------------------+---------------+-------------------|
. | RF-num of DT ↑       | variance-error ↓  | smoothness ↑  | overfitting ↓     |
. |                      | bias-error =      | fittness =    | power of model =  |
. |----------------------+-------------------+---------------+-------------------|
. | DT-depth ↑           | variance-error ↑  | smoothness =  | overfitting ↑     |
. |                      | bias-error =      | fittness ↑    | power of model ↑  |

>>> Boosting

. | Boosting-num of f ↑  | variance-error = | smoothness ↑  | overfitting ↑     |
. |                      | bias-error ↓     | fittness ↑    | power of model ↑  |
. |----------------------+------------------+---------------+-------------------|
. | Adaboost-num of f ↑  | variance-error = | smoothness ↑  | overfitting ↑     |
. |                      | bias-error ↓     | fittness ↑    | power of model ↑  |
. |----------------------+------------------+---------------+-------------------|
. | power of f =         | variance-error = | smoothness =  | overfitting =     |
. |                      | bias-error =     | fittness =    | power of model =  |

看似单个 classifier 没有 loss-fn, 但是整体看统合后的模型 g(x) 是有 loss-fn 的。定这个 loss-fn 可以自主定义。比如这里使用 Σexp(-y^*g(x))

因为之前通过推导已经得到过 gt 与 gt-1 的关系，是一种类似递归的关系，而回忆 GD 是如何优化 w 的，发现 GD 方法最后给出的表达式，也是这样的关系。所以，只要这两项（红方框）是方向相同的即可。

那怎么找一个 ft 与 上面那个红方框具有 same direction 呢？
把所有的 ft 与 所有的 exp 都各自组成向量，同方向就代表我希望
他们两个向量的内积越大越好，内积展开出来就是
Σexp(...)(y)ft
maximize 这个和式就代表 尽量让上图两个红方框 具有相同的方向

    每次做 adaboost 的时候，每次都会给 sample 乘以这样的一个 weight.
    循环到 t 次时，每一个 smaple 累积下来都扩大了 ∏exp(xxx) 倍了。
    我们现在要找一个 ft,他能够 minize training data 上的 error.
    每一个 data 都用这样的 weight(t 次累乘).

    所以你会发现，如果用 Gradient Boosting 的想法，你定义的 loss-fn 就是
    刚才的 exp(xxx) 的话。你找出来的 ft,他其实就是 adaboost 里面找出来的 ft.

    今天用 Gradient boosting,他是一个更 general 的想法。因为，你可以更改
    各种不同的 loss-fn.

    从另一个角度可以看出，Adaboost 其实就是在 minized 那个 exp(xxx) 的 loss-fn

    利用 Gradient descent 来优化 loss-fn,
    为了确定 αt,最理想的方法是【穷举】所有可能的取值，看哪个会让 loss-fn
    最小。 但是既然已经有了 ft,不如直接复用 ft:
    我就看，固定 ft 的前提下，αt 取什么值可以让 loss-fn 最小。

    解 αt 看哪个 αt 可以让 loss-fn 的微分是 0 即可。

• http://arogozhnikov.github.io/2016/07/05/gradient_boosting_playground.html