第七篇:前向分步算法

前向分步算法

前向分步算法引入

  假设Nick的年龄是25岁。

  1. 第1棵决策树

把Nick的年龄设置成初始值0岁去学习,如果第1棵决策树预测Nick的年龄是12岁,即残差值为$25-12=13$

  1. 第2课决策树
    1. 把Nick的年龄设置成残差值13岁去学习,如果第2棵决策树能把Nick分到13岁的叶子节点,累加两棵决策树的预测值加和$12+13=25$,就是Nick的真实年龄25岁
    2. 如果第2棵决策树的得到的是10岁,残差值为$25-12-10=3$
  2. 第3课决策树

把Nick的年龄设置成残差值3岁去学习……

  1. 继续重复上述过程学习,不断逼近Nick的真实年龄

前向分步算法详解

加法模型

  加法模型(additive model)一般表示为弱学习器加和
$$
f(x) = \sum_{t=1}^T\theta_tb(x;\gamma_t)
$$
其中$b(x;\gamma_t)$为弱学习器,$\gamma_t$为弱学习器的参数,$\theta_t$为弱学习器的系数。

加法模型目标函数优化问题

  给定训练数据以及目标函数$L(y,f(x))$,加法模型的经验风险最小化问题既可以变为目标函数最小化问题
$$
\underbrace{min}_{\theta_t,\gammat}\sum{i=1}^mL(yi,\sum{t=1}^T\theta_tb(x_i;\gammat))
$$
  上述加法模型的目标函数优化问题是一个很复杂的优化问题,但是通过前向分布算法(forward stagewise algorithm)可以解决这一问题,它的思想是:因为学习问题是加法模型,所以每一步只学习一个弱学习器及其系数,然后逐步逼近优化目标函数,也就是说,每一步只需要优化如下所示的目标函数
$$
\underbrace{min}
{\theta,\gamma}\sum_{i=1}^mL(y_i,\theta{b(x_i;\gamma)})
$$

前向分步算法流程

输入

  有$m$个数据$n$个特征的训练数据集$T={(x_1,y_1),(x_2,y_2),\cdots,(x_m,y_m)}$;目标函数$L(y,f(x))$;弱学习模型集${b(x;\gamma_t)},\quad(t=1,2,\cdots,T)$,在Boosting算法中$T$相当于弱学习器的个数。

输出

  加法模型$f(x)$。

流程

  1. 初始化$f_0(x)=0$
  2. 对$t=1,2,\cdots,T$
    1. 极小化目标函数
      $$
      (\theta_t,\gammat)=\underbrace{arg\,min}{\theta,\gamma}\sum_{i=1}^mL(yi,f{t-1}(x_i)+\theta{b(x_i;\gamma)})
      $$
      得到参数$\theta_t,\gamma_t$
    2. 更新
      $$
      ft(x)=f{t-1}(x)+\theta_tb(x;\gamma_t)
      $$
  3. 得到加法模型

$$
f(x)=fT(x)=\sum{t=1}^T\theta_tb(x;\gamma_t)
$$

上一篇
下一篇
Copyright © 2022 Egon的技术星球 egonlin.com 版权所有 帮助IT小伙伴学到真正的技术