机器学习：提升算法简介

提升算法概论：

Boosting（提升）是一族可将弱学习器提升为强学习器的算法。在分类问题中，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类的性能。

提升算法基于这样一种思想： 对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独判断好。

强可学习： 

在概率近似正确学习框架(PAC)中，一个概念（类），如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么称这个概念为强可学习的。

弱可学习：

一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅仅比随机猜测略好，那么这个概念为弱可学习。

提升：

Schapire 证明强可学习和弱可学习是等价的，就是在概率近似正确学习框架(PAC)中一个概念强可学习的充分必要条件是这个概念是弱可学习的。

因此，如果发现了 弱学习 算法，理论上就存在 强学习算法，通常弱学习算法更容易发现，将弱学习算法 转化为强学习算法的方法便是提升。

提升算法基本思路：

从弱分类学习算法出发，反复学习，获取一系列弱分类器（基本分类器），然后组合这些弱分类器，构成一个强分类器。

提升算法的两个主要问题： 

     1. 如何构建弱分类器

      2. 如何将弱分类器组合成一个强分类器

围绕这两个问题，人们提出了很多提升算法，常见提升算法如下:

常见提升算法

AdaBoost （Adaptive）

   1. 提高那些被前一轮弱分类器错误分类的样本的权重，弱化正确分类的权重，这样一来，后续分类器重点关注之前分类器未关注到的样本，分类问题被一系列弱分类器分而治之。

   2. 采用加权多数表决来组合弱分类器。 加大误差小的分类器权重，减小误差大的权重。

Boosting Tree()  提升树

    以分类树，回归树作为基本分类器（弱分类器），对基本分类器进行线性组合（加法模型），采用前向分步算法。

    对于分类问题采用二叉分类树，回归问题采用二叉回归树。

    提升算法是统计学习中性能最好的方法之一。

Gradient boosting(GB)  梯度提升

   优化算法采用损失函数的负梯度作为残差的 近视值。

Gradient boosting Decision Tree(GBDT)  

    GBDT是GB和DT的结合，以决策时作为基函数，梯度提升算法为优化算法。

Xgboost  

   XGBoost是提升算法的高效实现，在各项机器学习、大数据比赛中的效果非常好。

  XGBoost与GBDT主要的不同在于其目标函数使用了正则项并且利用了二阶导数信息