什么是Boosted Trees

本文主要基于陈天奇师兄的著名的 Boosted Trees 介绍英文版中文版),是边学习边梳理的结果:

  • 有监督学习的组成部件:模型,参数和目标函数
    • 模型——给定 输入 如何去预测 输出
    • 参数——我们需要学习的东西
    • 目标函数——如何寻找一个比较好的参数
      • 误差函数——鼓励模型尽量拟合训练数据
      • 正则化项——鼓励更加简单的模型
  • Tree Ensemble
    • ,RF 和 BT 的构造(学习)模型参数的方法不同
    • 上述参数包括:树的结构,叶子上的预测分数
    • 如何学习这些参数
      • 定义合理的目标函数
      • 优化这个目标函数

\[\hat{y}_i=\sum_{k=1}^{K}f_k(x_i),\ \ f_k\in\mathcal{F}\]

\[Obj(\Theta)=\sum_i^nl(y_i,\hat{y}_i)+\sum_{k=1}^{K}\Omega(f_k)\]

  • Boosting = Additive Training
    • 每次迭代加入一个新函数
    • 选取的 使目标函数尽量最大地降低
  • 误差函数使用泰勒展开近似
    • 只依赖于每个数据点的在误差函数上的一阶导数 和二阶导数 
    • \(\hat{y}^{t-1}_i\) 求导时,涉及到前 t−1 个基学习器(CART)
  • 正则化项把树拆分成结构部分 和叶子权重部分 w
    • \(f_t(x)=w_{q(x)},\, w\in\mathcal{R}^{T},\ q: \mathcal{R}^{d}\rightarrow\{1,2,\cdots,T\}\)
    • e.g. \(\Omega(f_t)=\gamma T+\frac{1}{2}\lambda \sum_{j=1}^{T}w_j^2\)
  • 关键步骤: 

\[w_j^*=-\frac{G_j}{H_j+\lambda}, \quad Obj=-\frac{1}{2}\sum_{j=1}^{T}\frac{G_j^2}{H_j+\lambda}+\gamma T\]

where,

\[g_i = \partial_{\hat{y}^{(t-1)}} l(y_i, \hat{y}^{(t-1)}), \quad h_i = \partial_{\hat{y}^{(t-1)}}^2 l(y_i, \hat{y}^{(t-1)})\]


还有几个相关的内容,以后学习完善:随机森林(Random Forest),随机梯度下降(SGD),吉尼系数(Gini's Index),决策树的学习算法(ID3,C4.5等).

文章归档

阅读更多

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注