李宏毅机器学习课程笔记10：Ensemble、Deep Reinforcement Learning

台湾大学李宏毅老师的机器学习课程是一份非常好的ML/DL入门资料，李宏毅老师将课程录像上传到了YouTube，地址：NTUEE ML 2016 。
这篇文章是学习本课程第27-28课所做的笔记和自己的理解。

Lecture 27: Ensemble

Ensemble类似于“打群架”“大家一起上”，在Kaggle中是重要的方法。
Ensemble的Framework是：

1. 先找到若干分类器，这些分类器是彼此不同；
2. 再将这些分类器妥当地集合起来。

Ensemble的不同方法，是为了应对不同的状况。

Ensemble: Bagging

Bagging 是 Bootstrap Aggregation 的简写。

model变复杂时，error会先降后升，这是因为简单的model（underfitting）有小的variance、大的bias, 而复杂的model（overfitting）有大的variance、小的bias。如果模型很复杂，可以训练出多个复杂的模型，取平均，以减小variance，提高泛化能力。

实际中的做法是Bagging。在模型比较复杂（variance大、bias小）、比较容易overfitting时才用Bagging。其实NN不是很容易overfitting，而是卡在训练集上得不到好的结果，而像decision tree就很容易在训练集上很低(0%)的错误率、容易overfitting。
对decision tree做bagging就是random forest。

随机森林的做法：若是对训练数据重采样，那么得到的各棵树太像了。所以在每次分裂节点时随机限制哪些feature可用哪些feature不可用，避免各棵树长得太像。
Out-of-bag方法：假设现在有训练数据x1, x2, x3, x4，每次采样出部分数据训练function，如用x1, x2训练f1，用x3, x4训练f2，用x1, x3训练f3，用x2, x4训练f4。这样，x1没有被用于训练f2, f4，所以可用f2, f4组成随机森林来测试x1, 其余x2, x3, x4同理。
Out-of-bag (OOB) error是对测试集上错误率的一个很好的估计。
之前要切出验证集才知道在测试集上的错误率，而用OOB就不用验证集了，因为部分训练数据没有被包含在训练中，它们可以拿来当做验证集。

OOB样本可以用来估计变量的重要性

下面是单棵决策树和100棵决策树组成的随机森林用来拟合“初音函数”的结果：

Bagging并不是为了提升在训练集上的performance。在初音这个任务上并没有什么训练、测试，目标是看有多能拟合初音函数，与你的函数的泛化特性无关。所以现在加上随机森林并不能更加拟合初音函数，原来深度为5的单棵决策树不能拟合初音函数，那么加上随机森林还是不能拟合初音函数。但是Bagging可以让variance比较小，得到的function比较平滑。

Ensemble: Boosting

Bagging是要把已经很容易overfitting的model让它不那么容易overfitting。
Boosting是对没法fit训练数据的model, 想办法提升它的performance：Improving Weak Classifiers.

如果分类器在训练数据上有大于50%的正确率，那么在Boosting之后会得到100%的正确率。
Boosting的流程是：先有最初的分类器f1, 然后找到与f1互补的分类器f2，……
在Bagging中每个分类器都是独立的，训练时不相干，可以同时训练。而在Boosting中，要先训练完f1，再根据f1的特性训练f2……

在不同训练数据上训练就会得到不同的分类器，不同的训练数据一般通过re-weighting training data得到，实际上修改了目标函数。
Adaboost的做法就是，训练好f1后，调整training set的weight，让f1在新的training set上错误率达到50%, 再用新的training set训练f2……
调整training set的weight 的方法是，对f1正确分类的example, 其weight除以一个大于1的值；对f1错误分类的example, 其weight乘以相同的值，这个值可以计算出来。

Adaboost算法如下：

$u_{t+1}^n← u_t^n×exp(-\hat y^n f_t(x^n) \alpha_t)$
在aggregate classifiers时，用uniform weight的方式比较不好，因为不同的分类器有强弱之别。

下面证明随着$T$ 的增大，$H(x)$ 会在训练数据上取得越来越小的错误率。
首先给出训练错误率的upper-bound，然后证明这个upper-bound恰好等于$\frac{1}{N}Z_{T+1}$，之后往证$T↑, Z_{T+1}↓$

随着轮数$T$ 的增加，$H(x)$ 在训练数据上的错误率降为0，但是训练错误率为0之后，测试错误率还在继续下降。
我们将$\hat y g(x)$ 作为margin，margin越“正”表示越正确。可见，5个分类器的组合已经有0%的训练错误率，但再增加新的分类器margin会被往右推，也就是说就算训练错误率为0，Adaboost也会继续放大margin。放大margin，相当于在减小penalty。

Adaboost是Boosting的特例，一般的Boosting算法是：

用gradient descent最小化objective function, 希望下图中两个红框中的项是同向的：

用$exp(...)$ 作为Gradient Boosting 的 loss function的话，所找出来的$f_t, \alpha_t$ 就是Adaboost中的$f_t, \alpha_t$。
Gradient Boosting是更一般化的想法，因为可以改loss function。

Gradient Boosting Interactive Playground

Ensemble: Stacking

注意训练数据的划分：前面的四个系统和final classifier要使用不同的训练数据。
final classifier决定各系统的weight.

参考阅读：A Kaggler’s Guide to Model Stacking in Practice

Lecture 28: Deep Reinforcement Learning

李宏毅机器学习课程笔记

李宏毅机器学习课程笔记1：Regression、Error、Gradient Descent
李宏毅机器学习课程笔记2：Classification、Logistic Regression、Brief Introduction of Deep Learning
李宏毅机器学习课程笔记3：Backpropagation、”Hello world” of Deep Learning、Tips for Training DNN
李宏毅机器学习课程笔记4：CNN、Why Deep、Semi-supervised
李宏毅机器学习课程笔记5：Unsupervised Learning - Linear Methods、Word Embedding、Neighbor Embedding
李宏毅机器学习课程笔记6：Unsupervised Learning - Auto-encoder、PixelRNN、VAE、GAN
李宏毅机器学习课程笔记7：Transfer Learning、SVM、Structured Learning - Introduction
李宏毅机器学习课程笔记8：Structured Learning - Linear Model、Structured SVM、Sequence Labeling
李宏毅机器学习课程笔记9：Recurrent Neural Network
李宏毅机器学习课程笔记10：Ensemble、Deep Reinforcement Learning