集成学习
思想：集成学习通过构建多个学习器来完成学习任务，即用多个弱学习器组合形成强学习器。
集成学习需要关注的问题：
- 弱学习器如何训练得到？答：改变训练数据的权值或者概率分布
- 如何组合弱学习器形成强学习器？答：线性加权或者投票
1. Boosting
个体学习器之间存在强依赖关系，必须串行生成弱分类器。
工作机制：
- 提高被前一轮弱分类器分类错误的样本权值，降低被前一轮弱分类器分类正确的样本权值，使错误样本在后续受到更多的关注。
- 加法模型将弱分类器线性加权组合得到强分类器。
1.1 Adaboost
Adaboost是一个加法模型，用来解决二分类问题（多分类需要看成多个二分类）：
\[\begin{align} f(x)&=\sum_{m=1}^M \alpha_mG_m(x)\\ &=\alpha_1G_1(x)+\alpha_2G_2(x)+...+\alpha_MG_M(x) \end{align} \]其中\(\alpha_m\)由\(G_m(x)\)的分类误差率所决定，每一个弱分类器\(G_m(x)\)训练后，会提高被该分类器分类错误的样本权值，降低被分类正确的样本权值。
算法流程
-
训练数据集：二分类数据集，标签为{-1, 1}。
-
定义基分类器：如逻辑回归
-
循环M次：1. 初始化/更新当前训练数据的权值分布
2. 根据具有权值分布的训练数据集\(D_m\)训练当前基分类器\(G_m(x)\)。
3. 计算当前基分类器权值\(a_m\)。
4. 将\(a_mG_m(x)\)更新到加法模型f(x)中。
5. 判断是否满足循环退出条件。
1.1.1 初始化/更新当前训练数据的权值分布
初始化所有样本的权值都为\(w_{1i}=\frac{1}{n}\)，得到数据集\(D_1\)。
更新所有样本权值：
\[w_{mi}=\frac{w_{m-1,i}}{Z_{m-1}}exp(-\alpha_{m-1}y_iG_{m-1}(x_i)) \]其中\(Z_{m-1}\)是规范化因子，目的是使得\(D_m\)成为一个概率分布
\[Z_{m-1}=\sum_{i=1}^Nw_{m-1,i}exp(-\alpha_{m-1}y_iG_{m-1}(x_i)) \]解释：
\[w_{m,i}= \begin{cases} \frac{w_{m-1,i}}{Z_{m-1}}exp(-\alpha_{m-1})& G_{m-1}(x_i)=y_i\\ \frac{w_{m-1,i}}{Z_{m-1}}exp(\alpha_{m-1})& G_{m-1}(x_i)!=y_i \end{cases} \]1.1.2 训练基分类器\(G_m(x)\)
根据具有权值分布的训练数据集\(D_m\)训练基分类器\(G_m(x)\)。
如选择逻辑回归为基分类器，则使用交叉熵作为损失，梯度下降作为优化方法训练模型。
1.1.3 计算当前基分类器权值\(a_m\)
- 计算当前基分类器在训练数据集上的分类误差率\(e_m\)，\(e_m\)一定在0~0.5之间。
- 根据分类误差率\(e_m\)，计算基分类器\(G_m(x)\)的权重公式
1.1.4 将\(a_mG_m(x)\)更新到加法模型f(x)中
\[\begin{align} f(x)&=\sum_{m=1}^M \alpha_mG_m(x)\\ &=\alpha_1G_1(x)+\alpha_2G_2(x)+...+\alpha_MG_M(x) \end{align} \]1.1.5 判断是否满足循环退出条件
- 分类器个数是否到达M个
- 总分类器的误差率是否低于设定的精度
1.1.6 加法模型
-
预测函数：\(f(x)=\sum_{m=1}^M \alpha_mG_m(x;r_m)\)，其中\(a_m\)为基函数系数，\(G_m(x;r_m)\)为基函数，\(r_m\)为基函数参数。
-
损失函数：自定义损失函数：\(L(y,f(x))\)，如：回归问题用均方误差，分类问题用指数损失函数。
-
优化算法：采用前向分布算法。 不采用梯度下降算法的原因：梯度下降的缺点：整体损失最小化：\(min\sum_{i=1}^NL(y_i,\sum_{m=1}^Ma_mG(x_i;r_m))\)，单词迭代过程需要优化所有基模型的所有参数，计算量过大。
1.1.7 前向分布算法
- 初始化\(f_0(x)=0\)
- 极小化损失函数：\(argmin_{a,r}\sum_{i=1}^NL(y_i,f_{m-1}(x_i)+aG(x_i;r))\)，即只对当前基模型的所有参数进行优化，固定前面n-1个基模型的参数。
- 更新当前基模型的参数\(a,r\)
- 得到加法模型\(f(x)=\sum_{m=1}^M \alpha_mG_m(x;r_m)\)
1.1.8 指数损失函数
因为二分类问题标签是{-1，1}，交叉熵损失中有log，所以会出现log（-1），所以不能用交叉熵损失。
指数损失函数：
\[\begin{aligned} L(y,f(x))&=exp[-yf(x)]\\ &=exp[-y\sum_{m=1}^Ma_mG_m(x)]\\ &=exp[-y(f_{m-1}(x)+a_mG_m(x))]\\ \end{aligned} \]当\(G(x)\)分类正确时，\(f(x)\)与\(y\)同号，\(L(y,f(x))<=1\)
当\(G(x)\)分类错误时，\(f(x)\)与\(y\)异号，\(L(y,f(x))>1\)
将损失函数视为训练数据的权值：\(w_{mi}=exp[-y_if_{m-1}(x_i)]\)
优化\(G_m\)
\[G_m(x)=argmin\sum_{i=1}^Nw_{mi}I(y_i!=G(x_i)) \]\(G_m\)要使得分类误差率最小
优化\(a_m\)
\[a_m=\frac{1}{2}log\frac{1-e_m}{e_m} \]推导过程：
\[\begin{aligned} L(y,f(x))&=\sum_{i=1}^Nexp[-y(f_{m-1}(x)+a_mG_m(x))]\\ &=\sum_{i=1}^Nexp[-yf_{m-1}(x)]\times exp[-ya_mG_m(x)]\\ &=\sum_{i=1}^Nw_{mi}\times exp[-ya_mG_m(x)]\\ &=\sum_{y_i!=G(x_i)}w_{mi}e^{-a}+\sum_{y_i=G(x_i)}w_{mi}e^{a}\\ &=e^{-a}\sum_{y_i!=G(x_i)}w_{mi}+e^{a}\sum_{y_i=G(x_i)}w_{mi}\\ &=e^{-a}\sum_{i=1}^Nw_{mi}+(e^a-e^{-a})\sum_{y_i!=G(x)}w_{mi} \end{aligned} \]求导得到：
\[\begin{aligned} \frac{\partial{e^{-a}\sum_{i=1}^Nw_{mi}+(e^a-e^{-a})\sum_{y_i!=G(x)}w_{mi}}}{\partial{a_m}} &=-e^{-a_m}\sum_{i=1}^Nw_{mi}+(e^{a_m}+e^{-a_m})\sum_{y_i!=G(x_i)}w_{mi}\\ &=-e^{-a_m}\sum_{y_i=G(x_i)}w_{mi}+e^{a_m}\sum_{y_i!=G(x_i)}w_{mi} \end{aligned} \]令导数为0，两别 取对数，得到：
\[ln(e^{-a_m}\sum_{y_i=G(x_i)}w_{mi})=ln(e^{a_m}\sum_{y_i!=G(x_i)}w_{mi}) \]化简，得到：
\[-a_m+ln(\sum_{y_i=G(x_i)}w_{mi})=a_m+ln(\sum_{y_i!=G(x_i)}w_{mi}) \]即：
\[\begin{aligned} 2a_m&=ln(\frac{\sum_{y_i=G(x_i)}w_{mi}}{\sum_{y_i!=G(x_i)}w_{mi}})\\ &=ln(\frac{\sum_{i=1}^Nw_{mi}-\sum_{y_i!=G(x_i)}w_{mi}}{\sum_{y_i!=G(x_i)}w_{mi}})\\ \end{aligned} \]右式分子分母同时除以\(\sum_{i=1}^Nw_{mi}\)得到：
\[\begin{aligned} a_m &= ln(\frac{1-\frac{\sum_{y_i!=G(x_i)}w_{mi}}{\sum_{i=1}^Nw_{mi}}}{\frac{\sum_{y_i!=G(x_i)}w_{mi}}{\sum_{i=1}^Nw_{mi}}})\\ &=ln(\frac{1-e_m}{e_m}) \end{aligned} \]1.2 GBDT
GBDT采用决策树cart算法，被认为是统计学习中性能最好的方法之一。
GBDT也采用加法模型，回归问题采用均方误差损失，二分类问题采用指数损失，多分类采用softmax损失，一般决策问题采用自定义损失函数。采用前向分步算法优化当前子树的参数。
\[L_{\theta}(y_i,f_{m-1}(x_i)+T(x_i;\theta_m)) \]1.2.1 二分类问题的提升树
基学习器：cart二分类树
损失函数：指数损失函数
相当于Adaboost算法的特殊情况：
\[f(x) = T(x;\theta_1)+T(x;\theta_2)+...+T(x;\theta_m) \]更新基分类器权重：基分类器权重a全部设置为1
更新样本权重：只要使用的是指数损失函数，就可以用指数损失调整样本权值，从而让基分类器学到不同内容。
1.2.2 回归问题的提升树
基学习器：cart回归树
损失函数：平方误差损失
\[\begin{aligned} L(y,f(x))&=(y-f(x))^2\\ &=[y-f_{m-1}(x)-T(x;\theta_m)]^2\\ &=[r-T(x;\theta_m)]^2 \end{aligned} \]优化算法：前向分步算法构建新的训练样本，让基学习器拟合新的样本
更新样本权重：损失函数中的残差r作为新一轮训练数据的样本权重
更新基分类器权重：基分类器权重a全部设置为1
1.2.3 一般决策问题的梯度提升树（GBDT）
一般决策问题采用不同于上述两种问题的损失函数，对应的凸优化问题不一样，GBDT就是求解这种凸优化问题的通用方式。
基学习器：回归树
损失函数：一般损失函数
优化算法：前向分步算法 + 梯度提升
核心目标：每增加一个基学习器，都能使得总体损失越来越小。
\[L(y,f_{m-1}(x))-L(y,f_m(x))>0 \]由于\(f_m(x)=f_{m-1}(x)+T(x;\theta_m)\)，且\(f_{m-1}(x)\)为常量，所以对\(f_m(x)\)泰勒展开，得到：
\[\begin{aligned} L(y,f_m(x))&=L(y,f_{m-1}(x))+\frac{\partial{L(y,f_m(x))}}{\partial{f_m(x)}}_{|f_m(x)=f_{m-1}(x)}(f_m(x)-f_{m-1}(x))\\ &=L(y,f_{m-1}(x))+\frac{\partial{L(y,f_m(x))}}{\partial{f_m(x)}}_{|f_m(x)=f_{m-1}(x)}T(x;\theta_m) \end{aligned} \]移项，得到：\(L(y,f_{m-1}(x))-L(y,f_m(x))=-\frac{\partial{L(y,f_m(x))}}{\partial{f_m(x)}}T(x;\theta_m)\)
因此，当\(-\frac{\partial{L(y,f_m(x))}}{\partial{f_m(x)}}=T(x;\theta_m)\)时，\(L(y,f_m(x))-L(y,f_{m-1}(x))\)为\(T^2\)一定大于等于0。
计算步骤：
- 计算当前损失函数负梯度表达式：
- 构造新的训练样本：将\((x_i,y_i)\)带入\(r_m\)，得到新一轮的训练数据集\(T_m={(x_1,r_1),(x_2,r_2),...,(x_n,r_n)}\)
- 让当前基学习器拟合上述样本，得到\(T(x;\theta_m)\)
更新样本权重：损失函数的负梯度\(r_m\)作为新一轮训练数据的样本权重
更新基分类器权重：基分类器权重a全部设置为1
1.3 XGBoost
目标函数：加法模型：\(\sum_{i=1}^NL(y_i,f_{m-1}+W_{q(x_i)})+\sum_{j=1}^t\Omega (f_i)\)
其中\(\Omega (f_i)=rT+\frac{1}{2}\lambda\sum_{j=1}^Tw_j^2\)为正则项，T表示当前回归树上叶子结点数量，\(w_j\)表示第j个叶子节点的权值，正则项会累加所有t个基分类器，而公式前一项代表会计算N个样本的损失。
基学习器：回归树
优化算法：前向分步算法，在优化第t棵子树的参数时，将目标函数中前t-1棵子树的正则项参数固定，并且将N个样本的损失转化为每个样本与它落入的叶子结点的损失，即：
\[\begin{aligned} Obj^{(t)}&=\sum_{j=1}^T\sum_{i\in I_j}L(y_i, f_{t-1}+W_{q(x_i)})+rT+\frac{1}{2}\lambda\sum_{j=1}^Tw_j^2\\ &=rT+\sum_{j=1}^T[\sum_{i\in I_j}L(y_i, f_{t-1}(x_i)+W_{j})]+\frac{1}{2}\lambda w_j^2 \end{aligned} \]由于损失函数不一定为均方误差损失，可能为任意损失函数，且决策树模型是阶跃的，不能用梯度下降求解优化问题，所以需要寻找一种通用的优化求解方法，如：GBDT采用负梯度方向优化。
XGBoost采用二阶导数进行优化这个目标函数，首先将\(L(y_i, f_{t-1}(x_i)+W_{j})\)二阶泰勒展开，其中\(f_{t-1}(x_i)\)看作定值\(f(x_0)\)，\(W_{j}\)看作\(x-x_0\):
\[\begin{aligned} L(y_i, f_{t-1}(x_i)+W_{j})&=L(y_i, f_{t-1}(x_i))+L^{'}(y_i, f_{t-1}(x_i))W_{j}+\frac{1}{2}L^{''}(y_i, f_{t-1}(x_i))W_{j}^2\\ &=g_iW_j+\frac{1}{2}h_iW_j^2 \end{aligned} \]其中，\(g_i\)代表\(L^{'}(y_i, f_{t-1}(x_i))\)的简写，\(h_i\)代表\(L^{''}(y_i, f_{t-1}(x_i))\)的简写，而\(L(y_i, f_{t-1}(x_i))\)作为定值在优化目标中省略。
\[\begin{aligned} Obj^{(t)}&=rT+\sum_{j=1}^T[\sum_{i\in I_j}L(y_i, f_{t-1}(x_i)+W_{j})]+\frac{1}{2}\lambda w_j^2\\ &=rT+\sum_{j=1}^T[\sum_{i\in I_j}(g_iW_j+\frac{1}{2}h_iW_j^2)]+\frac{1}{2}\lambda w_j^2\\ &=rT+\sum_{j=1}^T[W_j\sum_{i\in I_j}g_i+\frac{1}{2}W_j^2(\sum_{i\in I_j}h_i+\lambda)]\\ &=rT+\sum_{j=1}^T[W_jG_j+\frac{1}{2}W_j^2(H_j+\lambda)]\\ \end{aligned} \]其中，\(G_j\)代表\(\sum_{i\in I_j}g_i\)的简写，\(H_j\)代表\(\sum_{i\in I_j}h_i\)的简写，也就是说对于每一个样本，我们累加它落入的叶子节点的一阶导数和二阶导数，就可以得到目标表达式。
\[w_j^*=argmin(w_jG_j+\frac{1}{2}w_j^2(\lambda+H_j)) \]我们对于每一个叶子节点的值w，只需要计算落入它的样本的导数的和就行了，与其他样本和叶子节点的值无关。其中，G和H都当作常量。由于目标函数是一个凸函数，所以H大于0，\(\lambda\)是一个系数必然大于0，所以最小值：
\[w_j^*=-\frac{b}{2a}=-\frac{G_j}{H_j+\lambda} \]所以：
\[Obj^{(t)}=rT-\frac{1}{2}\sum_{j=1}^T\frac{G_j^2}{H_j+\lambda} \]1.3.1 确定树结构
通过二阶导数，我们可以求得最优的叶子值w和目标函数的最小值，但我们并不知道如何选择树的中间节点的值。
可以计算决策树分裂前和分裂后的增益来选择最优的树的中间节点的划分：
\[gain = obj_{before}^*-obj_{after}^* \]选择信息增益最大的gain作为中间节点的划分。
1.3.2 优化算法
由于确定树结构时会对所有的特征以及每个特征可能的划分计算信息增益，并且在对每个特征计算可能的划分时需要对样本按照该特征的取值进行排序，计算量非常大。为了减小计算开销，我们可以采用近似算法进行优化。
1.3.2.1 列采样
桉树随机：对于XGBoost的每一棵子树选择划分时进行特征列采样。
按层随机：对于XGBoost的每一棵子树的每一层选择划分时进行特征列采样。
1.3.2.2 特征值分桶
如果对于某个特征，要选择k个特征值作为可能的划分，则我们希望每个划分中包含的样本数量不会相差过大，即根据特征值将样本划分给为k+1个桶，每个桶中包含的样本数量近似相同。
样本不均衡情况下：采用加权分位法，即将关于叶子结点值W的目标函数凑成完全平方的形式，这样前面会多一个系数H，这个H就是样本落入叶子节点的二阶导数，把这个当作叶子节点的权值再进行分桶。
\[\begin{aligned} Obj^{(t)}&=rT+\sum_{j=1}^T[W_jG_j+\frac{1}{2}W_j^2(H_j+\lambda)]\\ &=rT+\sum_{j=1}^T\frac{1}{2}W_j^2\lambda+\sum_{j=1}^T\frac{1}{2}H_j(2\frac{G_j}{H_j}W_j+W_j^2)\\ &=rT+\sum_{j=1}^T\frac{1}{2}W_j^2\lambda+\sum_{j=1}^T\frac{1}{2}H_j(\frac{G_j^2}{H_j^2}+2\frac{G_j}{H_j}W_j+W_j^2)\\ &=rT+\sum_{j=1}^T\frac{1}{2}W_j^2\lambda+\sum_{j=1}^T\frac{1}{2}H_j(W_j-(-\frac{G_j}{H_j}))^2 \end{aligned} \]这样每一个样本的数量就变为\(H_j\)个，同时可以设置一个阈值作为每个桶中加权样本的最大数量，可以通过调节这个阈值从而控制桶的数量。
与列采样相似，特征值的分桶方法也分为全局策略（桉树随机）和局部策略（按层随机）。由于划分后的特征很容不再满足全局策略的划分条件，因此局部策略好于全局策略。
1.3.3 缺失值处理
————————————未完待续——————————————
2. Bagging
个体学习器之间不存在强依赖关系，可同时并行生成弱分类器。
工作机制：
- 从原始样本集中使用Bootstrapping法（有放回的抽样方法，可能抽到重复的样本，相当于改变了数据分布）抽取n个训练样本。共进行k轮抽取，得到k个训练集（k个训练集相互独立）。在随机森林算法中，还会抽取一定数量的特征。
- k个训练集分别并行训练，得到k个模型。
- 将上述的k个模型通过一定方式组合起来：分类问题用投票表决的方式得到分类结果，回归问题用k个模型的均值作为最后的结果。