提升方法与前向分步算法

提升方法

考虑加法模型(additive model)
[f(x)=sum limits_{m=1}^M eta_m b(x;gamma_m) ]
其中,(b(x;gamma_m))为基函数，(eta_m)为基函数的系数，(gamma_m)为基函数参数
给定训练数据及损失函数(L(y, f(x)))条件下，学习加法模型成为经验风险极小化即损失函数极小化问题
[mathop{min} limits_{eta,gamma} sum limits_{i=1}^N L(y_i, eta b(x_i; gamma)) ]
前向分步算法如下：
- 输入：训练集，损失函数(L)，基函数集({b(x;gamma)})
- 输出：加法模型(f(x))
  1. 初始化(f_0(x)=0)
  2. 对(m=1,2,cdots,M)
  - 极小化损失函数,得到参数
    [(eta_m, gamma_m)=mathop{argmin}limits_{eta, gamma}sum limits_{i=1}^N L(y_i, f_{m-1}(x)+eta b(x; gamma)) ]
  - 更新
    [f_m(x)=f_{m-1}(x) + eta_m b(x;gamma_m) ]
  1. 得到加法模型
  [f(x)=f_M(x)=sum limits_{m=1}^M eta_m b(x; gamma_m) ]

如果将输入空间(mathcal{X})划分为(J)个互不相交的空间(R_j)(回归树叶节点个数)，并且在每个区域确定输出的常量(c_j)((c_j)就是回归或者分类的值)，那么树可以表示成
[T(x;Theta)=sum limits_{j=1}^J c_j I(x in R_j) ]
回归问题提升树使用以下前向分步算法：
[f_0(x)=0 ]
[f_m(x)=f_{m-1}(x)+T(x;Theta_m) ]
[f_M(x)=sum limits_{m=1}^M T(x;Theta_m) ]
在第(m)步，需求解
[hat{Theta}_m=mathop{arg min}limits_{Theta_m} sum limits_{i=1}^N L(y_i, f_{m-1}(x_i)+T(x_i; Theta_m)) ]
平方误差损失函数
[L(y, f_{m-1}(x)+T(x;Theta_m))=[y-f_{m-1}(x)+T(x;Theta_m)]^2=[r-T(x;Theta_m)]^2 ]
(r=y-f_{m-1}(x))是残差。因此只需要简单地拟合当前模型的残差
回归问题的提升树算法：
- 输入：训练集
- 输出：提升树(f_M(x))
  1. 初始化(f_0(x)=0)
  2. 对(m=1,2,cdots,M)
    - 计算残差
      [r_{mi} = y_i-f_{m-1}(x_i) ]
    - 拟合残差(r_{mi})，学习一个回归树，得到(T(x;Theta_m))
    - 更新
      [f_m(x)=f_{m-1}(x) + T(x;Theta_m) ]
  3. 得到回归问题提升树
    [f_M(x)=sum limits_{m=1}^M T(x;Theta_m) ]

优点：
- 预测阶段计算速度快，树与树之间可以并行计算
- 分布稠密的数据集上，泛化能力和表达能力好
- 使用决策树的GBDT具有可解释性和鲁棒性，能自动发现特征间的高阶关系，不需要对数据做特殊预处理如归一化等
局限性：
- 高维稀疏数据集上，表现不如SVM或者神经网络
- 处理数值型特征效果明显，文本分类特征上不是最好
- 训练过程需要串行训练