精华内容
下载资源
问答
  • AdaBoost指数损失

    2020-05-05 20:11:58
    自适应增强(Adaptive Boosting,AdaBoost)是Boosting算法簇的先祖,通过集成多个弱模型成为一个强模型。 H(x;Θ)=∑τατh(x;θτ) H(\pmb x;\Theta)=\sum_{\tau}\alpha_{\tau}h(\pmb x;\theta_{\tau}) H(xxx;Θ)...

    集成学习综述

    将多个不同算法、同一算法不同参数或不同数据集的弱模型组合为强模型.

    以加性模型表示为
    H ( x ; Θ ) = ∑ τ α τ h ( x ; θ τ ) , Θ = arg ⁡ min ⁡ α , θ E D [ L ( y , ∑ τ α τ h ( x ; θ τ ) ) ] H(\pmb x;\Theta)=\sum_{\tau}\alpha_{\tau}h(\pmb x;\theta_{\tau}),\quad\Theta=\arg\min_{{\alpha,\theta}}\Bbb E_{\mathcal D}[L(y,\sum_{\tau}\alpha_{\tau}h(\pmb x;\theta_{\tau}))] H(xxx;Θ)=τατh(xxx;θτ),Θ=argα,θminED[L(y,τατh(xxx;θτ))]
    假设集成M个分类误差为 ϵ < 0.5 \epsilon<0.5 ϵ<0.5且相互独立的弱模型,则集成分类器的误差率
    P ( H ( x ) ≠ f ( x ) ) = ∑ m = 0 M / 2 C M m ( 1 − ϵ ) m ϵ M − m ≤ exp ⁡ ( − 1 2 M ( 1 − 2 ϵ ) 2 ) P(H(\pmb x)\neq f(\pmb x))=\sum_{m=0}^{M/2}\Bbb C_M^m(1-\epsilon)^m\epsilon^{M-m} \leq\exp\left(-\frac{1}{2}M(1-2\epsilon)^2\right) P(H(xxx)=f(xxx))=m=0M/2CMm(1ϵ)mϵMmexp(21M(12ϵ)2)
    随着基分类器数量M的增大,集成分类器的误差以指数级下降.


    Bagging

    基模型无强依赖关系、可并行生成,一般为强模型,适合用于集成高方差低偏差的over-fitting模型(关注降低方差),如决策树模型所有样本均为叶结点时,错误率为0.

    随机森林是典型的的bagging算法,使用cart决策树作为基模型,单个模型训练的样本集和特征集具有随机性,即:

    • 随机地从样本集中有放回采样一定数量样本;
    • 随机地从特征集选取一定数量特征,若 d d d为特征总数,一般采样 log ⁡ 2 d \log_2d log2d个特征;

    Boosting

    基模型存在强依赖关系、串行生成,新基模型是对之前总体模型的提升,基模型一般为正确率略优于随机猜测的弱模型.
    根据之前迭代结果训练新基模型并更新总体模型,由于全局优化计算复杂,一般通过贪婪方法逐个求解最优基模型参数. Boosting的前向加性模型及求解方法为
    H t ( x ) = H t − 1 ( x ) + α t h ( x , θ t ) , ( α t , θ t ) = arg ⁡ min ⁡ α , θ E D t [ L ( y , H t − 1 ( x ) + α h ( x ; θ ) ) ] H_t(\pmb x)=H_{t-1}(\pmb x)+\alpha_th(\pmb x,\theta_t),\quad (\alpha_t,\theta_t)=\arg\min_{\alpha,\theta}\Bbb E_{\mathcal D_t}[L(y,H_{t-1}(\pmb x)+\alpha h(\pmb x;\theta))] Ht(xxx)=Ht1(xxx)+αth(xxx,θt),(αt,θt)=argα,θminEDt[L(y,Ht1(xxx)+αh(xxx;θ))]


    CART

    基模型一般使用CART决策树,模型表示为
    T ( x ; Θ ) = ∑ j = 1 J γ i I ( x ∈ R j ) T(\pmb x;\Theta)=\sum_{j=1}^J\gamma_i\Bbb I(\pmb x\in R_j) T(xxx;Θ)=j=1JγiI(xxxRj)
    其中 R j R_j Rj γ j \gamma_j γj分别为第 j j j个叶结点对应区域和结点输出值.


    AdaBoost

    自适应增强(Adaptive Boosting,AdaBoost)是Boosting算法簇的先祖,通过集成多个弱模型成为一个强模型。
    H ( x ; Θ ) = ∑ τ α τ h ( x ; θ τ ) H(\boldsymbol x;\Theta)=\sum_{\tau}\alpha_{\tau}h(\boldsymbol x;\theta_{\tau}) H(x;Θ)=τατh(x;θτ)
    式中 h τ h_\tau hτ α τ \alpha_\tau ατ分别表示第 τ \tau τ次迭代所得基模型及其所占总体的权重。



    AdaBoost算法属于前向分布算法的特例,AdaBoost的基本思想:

    • 调整样本分布:根据新模型的表现调整样本分布,使下次基模型(弱学习器)的注意力集中在错分样本。
    • 基模型权重:基模型集成到总体模型的权重与其训练误差成正比。
    • 损失函数:对于回归问题使用均方差损失,则新模型的训练实际是拟合当前模型的残差(GBDT);对于分类问题使用指数损失,新模型的训练实际是在调整后的分布上进行。

    本文主要通过理论推导说明AdaBoost的学习过程,解释以下几个问题:

    • AdaBoost的学习过程为什么是通过不断调整样本分布进行的?
    • 如何学习基模型?
    • 如何设定基模型权重?

    AdaBoost理论推导

    用于二分类的AdaBoost算法等价于基于指数损失的前向加性模型是在算法提出后之后才发现,典型的思想在前理论证明在后的算法,以不断调整分布的方式学习基模型,恰好可通过最小化指数损失得到解释。
    H t ( x ) = H t − 1 ( x ) + α t h t ( x ) H_t(\boldsymbol x)=H_{t-1}(\boldsymbol x)+\alpha_th_t(\boldsymbol x) Ht(x)=Ht1(x)+αtht(x)
    令训练集样本分布表示为 D \mathcal D D,初始分布一般为均匀分布
    D = ( w 1 , ⋯   , w m ) , w i = 1 m \mathcal D=(w_1,\cdots,w_m),\quad w_i=\frac{1}{m} D=(w1,,wm),wi=m1

    对于二分类模型 y = ± 1 y=\pm 1 y=±1,基于最小化指数损失训练模型,则第 t t t步所得基模型 h t h_t ht,应使得之前所得总体模型 H t − 1 H_{t-1} Ht1集成 h t h_t ht后,能在原始样本分布上最小化指数损失,因此优化目标函数可表示为

    ( α t , h t ) = arg ⁡ min ⁡ α , h E D [ exp ⁡ ( − y ( H t − 1 ( x ) + α h ( x ) ) ) ] = arg ⁡ min ⁡ α , h ∑ i w i exp ⁡ ( − y i ( H t − 1 ( x ) ) ) ⋅ exp ⁡ ( − α y i h ( x ) ) = arg ⁡ min ⁡ α , h ∑ i w i ( t ) exp ⁡ ( − α y i h ( x i ) ) \begin{aligned} (\alpha_t,h_t) &=\arg\min_{\alpha,h}\Bbb E_{\mathcal D}[\exp(-y(H_{t-1}(\boldsymbol x)+\alpha h(\boldsymbol x)))]\\[1ex] &=\arg\min_{\alpha,h}\sum_iw_i\exp(-y_i(H_{t-1}(\boldsymbol x)))\cdot\exp(-\alpha y_ih(\boldsymbol x))\\ &=\arg\min_{\alpha,h}\sum_iw_i^{(t)}\exp(-\alpha y_ih(\boldsymbol x_i)) \end{aligned} (αt,ht)=argα,hminED[exp(y(Ht1(x)+αh(x)))]=argα,hminiwiexp(yi(Ht1(x)))exp(αyih(x))=argα,hminiwi(t)exp(αyih(xi))

    其中可将 w ( t ) w^{(t)} w(t)视为第 t t t次迭代每个观测的权重
    w i ( t ) = w i exp ⁡ ( − y i H t − 1 ( x i ) ) w_i^{(t)}=w_i\exp(-y_iH_{t-1}(\boldsymbol x_i)) wi(t)=wiexp(yiHt1(xi))
    样本权重计算公式等价于以下递推的形式
    w i ( t + 1 ) = w i ( t ) exp ⁡ ( − y i α t h t ( x i ) ) \quad w_i^{(t+1)}=w_i^{(t)}\exp(-y_i\alpha_th_t(\boldsymbol x_i)) wi(t+1)=wi(t)exp(yiαtht(xi))
    实际计算过程中,样本分布也是通过迭代更新,这也解释了每次迭代完之后会调整样本分布的特性


    如何在第 t t t步训练基模型 h t h_t ht

    固定 α t \alpha_t αt并假定 α t > 0 \alpha_t > 0 αt>0,则最优 h t h_t ht满足
    h t = arg ⁡ min ⁡ h ∑ i w i ( t ) exp ⁡ ( − y i h ( x i ) ) ≈ arg ⁡ min ⁡ h ∑ i w i ( t ) ( 1 − y i h ( x i ) ) = arg max ⁡ h E D t [ y h ( x ) ] = arg ⁡ max ⁡ h [ h ( x ) P ( y = 1 ∣ D t ) − h ( x ) P ( y = − 1 ∣ D t ) ] \begin{aligned} h_t &=\arg\min_h\sum_iw_i^{(t)}\exp(-y_ih(\boldsymbol x_i)) \approx\arg\min_h\sum_iw_i^{(t)}(1-y_ih(\boldsymbol x_i))\\ &=\argmax_h\Bbb E_{\mathcal D_t}[yh(\boldsymbol x)]\\ &=\arg\max_h[h(\boldsymbol x)P(y=1|\mathcal D_t) - h(\boldsymbol x)P(y=-1|\mathcal D_t)] \end{aligned} ht=arghminiwi(t)exp(yih(xi))arghminiwi(t)(1yih(xi))=hargmaxEDt[yh(x)]=arghmax[h(x)P(y=1Dt)h(x)P(y=1Dt)]
    显然,最优解满足
    h ( x ) = { 1 , P ( y = 1 ∣ D t ) > P ( y = − 1 ∣ D t ) − 1 , o t h e r w i s e h(\boldsymbol x)= \begin{cases} 1,&P(y=1|\mathcal D_t) > P(y=-1|\mathcal D_t)\\ -1,&otherwise\\ \end{cases} h(x)={1,1,P(y=1Dt)>P(y=1Dt)otherwise
    因此,基模型(一般为CART决策树)的优化目标函数为
    h t ( x ) = arg ⁡ min ⁡ h ∑ i w i ( t ) I ( y i ≠ h ( x i ) ) , h t ( x ) ∈ { − 1 , + 1 } h_t(\boldsymbol x)=\arg\min_h\sum_i w_i^{(t)}\Bbb I(y_i\neq h(\boldsymbol x_i)),\quad h_t(\boldsymbol x)\in\{-1,+1\} ht(x)=arghminiwi(t)I(yi=h(xi)),ht(x){1,+1}

    因此,基模型的学习就可以看作为在加权的样本集中训练CART二分类决策树。


    如何计算第 t t t步基模型所占总体权重 α t \alpha_t αt

    固定 h t h_t ht,则最优 α t \alpha_t αt满足
    α t = arg ⁡ min ⁡ α ∑ i w i ( t ) exp ⁡ ( − α y i h t ( x i ) ) \alpha_t=\arg\min_{\alpha}\sum_iw_i^{(t)}\exp(-\alpha y_ih_t(\boldsymbol x_i)) αt=argαminiwi(t)exp(αyiht(xi))

    对上述求偏导令其为0,由于 y ± 1 y\pm 1 y±1,易得
    α t = 1 2 ln ⁡ 1 − ϵ t ϵ t , ϵ t = ∑ i w i ( t ) I ( y i ≠ h t ( x i ) ) ∑ i w i ( t ) \alpha_t=\frac{1}{2}\ln\frac{1-\epsilon_t}{\epsilon_t},\quad \epsilon_t=\frac{\sum_iw_i^{(t)}\Bbb I(y_i\neq h_t(\boldsymbol x_i))}{\sum_iw_i^{(t)}} αt=21lnϵt1ϵt,ϵt=iwi(t)iwi(t)I(yi=ht(xi))


    实例

    给定训练数据如下表所示,假设弱分类器由 x < v x < v x<v x > v x > v x>v产生,其阈值 v v v是该分类器在训练集上分类误差率最低

    序号12345678910
    x x x0123456789
    y y y111-1-1-1111-1

    解: 初始化数据权值分布
    D 1 = ( w 11 , w 12 , ⋯   , w 10 ) , w 1 i = 0.1 , i = 1 , 2 , ⋯   , 10 \mathcal D_1=(w_{11}, w_{12}, \cdots,w_{10}), \quad w_{1i}=0.1, \quad i=1,2,\cdots,10 D1=(w11,w12,,w10),w1i=0.1,i=1,2,,10
    i. m = 1 m=1 m=1,训练弱学习器,计算基分类器权重,更新样本分布

    • 阈值 v = 2.5 v=2.5 v=2.5时,基本分类器 h 1 ( x ) h_1(x) h1(x)分类误差最低,故
      h 1 ( x ) = { 1 , x < 2.5 − 1 , x > 2.5 h_1(x)= \begin{cases} 1, &x<2.5 \\ -1, &x > 2.5 \end{cases} h1(x)={1,1,x<2.5x>2.5

    • h 1 ( x ) h_1(x) h1(x)在分布 D 1 \mathcal D_1 D1上的分类误差率
      e 1 = ∑ i = 1 10 e 1 i I ( y i ≠ h 1 ( x ) ) = 0.3 e_1=\sum_{i=1}^{10}e_{1i}\Bbb I(y_i\neq h_1(x))=0.3 e1=i=110e1iI(yi=h1(x))=0.3

    • 计算 h 1 h_1 h1的权重系数
      α 1 = 1 2 ln ⁡ 1 − e 1 e 1 = 0.4236 \alpha_1=\frac{1}{2}\ln\frac{1-e_1}{e_1}=0.4236 α1=21lne11e1=0.4236

    • 更新训练数据的权值分布
      D 2 = ( w 21 , ⋯   , w 2 i , ⋯   , w 2 , 10 ) , w 2 i = w 1 i ⋅ e − α 1 y i h 1 ( x i ) Z 1 , i = 1 , 2 , ⋯   , 10 \mathcal D_2=(w_{21}, \cdots, w_{2i}, \cdots,w_{2,10}), \quad w_{2i}=\frac{w_{1i}\cdot e^{-\alpha_1y_ih_1(x_i)}}{Z_1}, \quad i=1,2,\cdots,10 D2=(w21,,w2i,,w2,10),w2i=Z1w1ieα1yih1(xi),i=1,2,,10

      D 2 = ( 0.071 , 0.071 , 0.071 , 0.071 , 0.071 , 0.071 , 0.167 , 0.167 , 0.167 , 0.071 ) \mathcal D_2=(0.071, 0.071, 0.071, 0.071, 0.071, 0.071, 0.167, 0.167, 0.167, 0.071) D2=(0.071,0.071,0.071,0.071,0.071,0.071,0.167,0.167,0.167,0.071)


    ii. m = 2 m=2 m=2,训练弱学习器,计算基分类器权重,更新样本分布:

    • 阈值 v = 8.5 v=8.5 v=8.5时,基本分类器 h 2 ( x ) h_2(x) h2(x)分类误差最低,故
      h 2 ( x ) = { 1 , x < 8.5 − 1 , x > 8.5 h_2(x)= \begin{cases} 1, &x<8.5 \\ -1, &x > 8.5 \end{cases} h2(x)={1,1,x<8.5x>8.5

    • h 2 ( x ) h_2(x) h2(x)在分布 D 2 \mathcal D_2 D2上的分类误差率
      e 2 = ∑ i = 1 10 w 2 i I ( y i ≠ h 2 ( x ) ) = 0.2143 e_2=\sum_{i=1}^{10}w_{2i}\Bbb I(y_i\neq h_2(x))=0.2143 e2=i=110w2iI(yi=h2(x))=0.2143

    • 计算 h 2 h_2 h2的权重系数
      α 2 = 1 2 ln ⁡ 1 − e 2 e 2 = 0.6496 \alpha_2=\frac{1}{2}\ln\frac{1-e_2}{e_2}=0.6496 α2=21lne21e2=0.6496

    • 更新训练数据的权值分布,则
      D 3 = ( 0.046 , 0.046 , 0.046 , 0.167 , 0.167 , 0.167 , 0.106 , 0.106 , 0.106 , 0.046 ) \mathcal D_3=(0.046, 0.046, 0.046, 0.167, 0.167, 0.167, 0.106, 0.106, 0.106, 0.046) D3=(0.046,0.046,0.046,0.167,0.167,0.167,0.106,0.106,0.106,0.046)


    iii. m = 3 m=3 m=3,训练弱学习器,计算基分类器权重,更新样本分布

    • 阈值 v = 5.5 v=5.5 v=5.5时,基本分类器 h 3 ( x ) h_3(x) h3(x)分类误差最低,故
      h 3 ( x ) = { 1 , x < 5.5 − 1 , x > 5.5 h_3(x)= \begin{cases} 1, &x<5.5 \\ -1, &x > 5.5 \end{cases} h3(x)={1,1,x<5.5x>5.5

    • h 3 ( x ) h_3(x) h3(x)在分布 D 3 \mathcal D_3 D3上的分类误差率
      e 3 = ∑ i = 1 10 w 3 i I ( y i ≠ h 3 ( x ) ) = 0.1820 e_3=\sum_{i=1}^{10}w_{3i}\Bbb I(y_i\neq h_3(x))=0.1820 e3=i=110w3iI(yi=h3(x))=0.1820

    • 计算 h 3 h_3 h3的权重系数
      α 3 = 1 2 ln ⁡ 1 − e 3 e 3 = 0.7514 \alpha_3=\frac{1}{2}\ln\frac{1-e_3}{e_3}=0.7514 α3=21lne31e3=0.7514

    • 更新训练数据的权值分布,则
      D 4 = ( 0.125 , 0.125 , 0.125 , 0.102 , 0.102 , 0.102 , 0.065 , 0.065 , 0.065 , 0.125 ) \mathcal D_4=(0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.065,0.125) D4=(0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.065,0.125)


    IV. 构建强分类器
    sign [ f 3 ( x ) ] = sign [ 0.4236 h 1 ( x ) + 0.6496 h 2 ( x ) + 0.7514 h 3 ( x ) ] \text{sign}[f_3(x)] = \text{sign}[0.4236h_1(x)+0.6496h_2(x)+0.7514h_3(x)] sign[f3(x)]=sign[0.4236h1(x)+0.6496h2(x)+0.7514h3(x)]

    Reference

    1.Boosting algorithm: AdaBoost
    2.The Elements of Statistical Learning (Second Edition) (P341-345)

    展开全文
  • AdaBoost

    千次阅读 2020-12-19 13:04:17
    AdaBoost AdaBoost是典型的Boosting算法,即找到相对容易的弱学习算法,然后通过反复...由于采用的损失函数不同,Boosting算法也因此有了不同的类型,AdaBoost就是损失函数为指数损失的Boosting算法 流程 输入:训练数

    AdaBoost

    AdaBoost是典型的Boosting算法,即找到相对容易的弱学习算法,然后通过反复学习得到一系列弱分类器,组合这些弱分类器得到一个强分类器。Boosting算法要涉及到两个部分,加法模型和前向分步算法。

    1. 加法模型就是说强分类器由一系列弱分类器线性相加而成。
    2. 前向分步就是说在训练过程中,下一轮迭代产生的分类器是在上一轮的基础上训练得来的。

    由于采用的损失函数不同,Boosting算法也因此有了不同的类型,AdaBoost就是损失函数为指数损失的Boosting算法

    流程

    输入:训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),(x_N,y_N)\} T={(x1,y1),(x2,y2),(xN,yN)},其中, x i ∈ X ⊆ R n x_i∈X⊆R^n xiXRn y i ∈ Y = − 1 , 1 y_i∈Y={-1,1} yiY=1,1,迭代次数M

    a. 初始化训练样本的权值分布: D 1 = ( w 1 , 1 , w 1 , 2 , … , w 1 , i ) , w 1 , i = 1 N , i = 1 , 2 , … , N D_1=(w_{1,1},w_{1,2},…,w_{1,i}),w_{1,i}=\frac{1}{N},i=1,2,…,N D1=(w1,1,w1,2,,w1,i),w1,i=N1,i=1,2,,N
    b. 对于 m = 1 , 2 , … , M m=1,2,…,M m=1,2,,M

    1. 使用具有权值分布 D m D_m Dm的训练数据集进行学习,得到弱分类器 G m ( x ) G_m(x) Gm(x)
    2. 计算 G m ( x ) G_m(x) Gm(x)在训练数据集上的分类误差率 e m = ∑ i = 1 N w m , i I ( G m ( x i ) ≠ y i ) e_m=\sum_{i=1}^Nw_{m,i} I(G_m (x_i )≠y_i ) em=i=1Nwm,iI(Gm(xi)=yi)
    3. 计算 G m ( x ) G_m(x) Gm(x)在强分类器中所占权重 α m = 1 2 l o g 1 − e m e m α_m=\frac{1}{2}log \frac{1-e_m}{e_m} αm=21logem1em
    4. 更新训练数据集的权值分布, z m z_m zm是归一化因子,可将样本概率分布和为1 w m + 1 , i = w m , i z m e x p ⁡ ( − α m y i G m ( x i ) ) , i = 1 , 2 , … , 10 w_{m+1,i}=\frac{w_{m,i}}{z_m}exp⁡(-α_m y_i G_m (x_i )),i=1,2,…,10 wm+1,i=zmwm,iexp(αmyiGm(xi))i=1,2,,10
      z m = ∑ i = 1 N w m , i e x p ⁡ ( − α m y i G m ( x i ) ) z_m=\sum_{i=1}^Nw_{m,i}exp⁡(-α_m y_i G_m (x_i )) zm=i=1Nwm,iexp(αmyiGm(xi))

    c. 最终分类器
    F ( x ) = s i g n ( ∑ i = 1 N α m G m ( x ) ) F(x)=sign(\sum_{i=1}^Nα_m G_m (x)) F(x)=sign(i=1NαmGm(x))

    证明与推导

    adaboost的损失函数为指数函数:
    L ( y , f ( x ) ) = e x p [ − y f ( x ) ] L(y,f(x))=exp[-yf(x)] L(y,f(x))=exp[yf(x)]
    对于分类模型而言,上述损失函数,在分类正确的时候,指数部分为负数;在分类错误的时候,指数部分为正数,符合损失函数的意义。
    前向分步为: f m ( x ) = f m − 1 ( x ) + α m G m ( x ) f_m(x)=f_{m-1}(x)+\alpha_mG_m(x) fm(x)=fm1(x)+αmGm(x)
    将前向分步代入损失函数,可得:
    L o s s = ∑ i = 1 N e x p ⁡ ( − y i f m ( x i ) ) = ∑ i = 1 N e x p ⁡ ( − y i ( f m − 1 ( x i ) + α m G m ( x i ) ) ) Loss=\sum_{i=1}^Nexp⁡(-y_i f_m (x_i ))=\sum_{i=1}^Nexp⁡(-y_i (f_{m-1} (x_i )+α_m G_m (x_i ))) Loss=i=1Nexp(yifm(xi))=i=1Nexp(yi(fm1(xi)+αmGm(xi)))此时 f m − 1 ( x ) f_{m-1}(x) fm1(x)已知,即:

    L o s s = ∑ i = 1 N w m , i ~ e x p ⁡ ( − y i α m G m ( x i ) ) Loss=\sum_{i=1}^N\widetilde{w_{m,i}} exp⁡(-y_i α_m G_m (x_i )) Loss=i=1Nwm,i exp(yiαmGm(xi)) w m , i ~ = e x p ⁡ ( − y i ( F m − 1 ( x ) ) ) \widetilde{w_{m,i}}=exp⁡(-y_i (F_{m-1} (x))) wm,i =exp(yi(Fm1(x)))
    于是分类器 G m ( x ) G_m(x) Gm(x)和这个分类器的权重 α m \alpha_m αm 可以表示成:
    在这里插入图片描述
    先求 G m ( x ) G_m(x) Gm(x),分类器的权重可以认为是一个确定的数, G m ( x ) G_m(x) Gm(x)是使得分错的(带权重的)样本里损失函数最小的那个,可以写成:
    在这里插入图片描述
    得到 G m ∗ ( x ) G^*_m(x) Gm(x)以后,求 α m ∗ \alpha^*_m αm
    在这里插入图片描述
    把上式对 α 求导,再令导函数为 0 ,得
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    更新权重
    在这里插入图片描述

    相关考点

    1. Adaboost 由于采用boosting算法,而Boosting 算法会倾向于一直分错的样本,如果样本中有离群的错误样本,boosting就会出现效果不好的情况。即Adaboost对离群值、异常值敏感。
    2. Adaboost和GBDT的异同点
      (1) 关注点:分错权值,残差:Adaboost每轮学习的一个基本学习器是通过改变样本的权值,关注上轮分类错误的样本的权值,以逐步减少在训练集上的分类误差率。而GBDT每轮学习一个基本学习器是通过改变输出值,每轮拟合的值为真实值与已有的加法模型的差值(即残差)。
      (2) 异常点: adaboost存在异常点敏感的问题, gbdt一定程度上优化了adaboost异常点敏感的问题,但是存在难以并行的缺点
      (3)树: GBDT无论是进行分类还是回归问题,都用的CART回归树,adaboost对分类问题用二叉分类树,回归问题用二叉回归树。
      (4)方差偏差: 两者的目标都是优化偏差bias,必然导致训练出来的数据方差var的不稳定

    实战

    https://blog.csdn.net/FontThrone/article/details/78834807
    https://louisscorpio.github.io/2017/11/28/%E4%BB%A3%E7%A0%81%E5%AE%9E%E6%88%98%E4%B9%8BAdaBoost/

    展开全文
  • 无心啰嗦,本文结合邹博之决策树与Adaboost的PPT,跟他讲Adaboost指数损失函数推导的PPT(第85~第98页)、以及《统计学习方法》等参考资料写就,可以定义为一篇课程笔记、读书笔记或学习心得,有何问题或意见,欢迎...

    0 引言

        无心啰嗦,本文结合邹博之决策树与Adaboost 的PPT,跟他讲Adaboost指数损失函数推导的PPT(第85~第98页)、以及《统计学习方法》等参考资料写就,可以定义为一篇课程笔记、读书笔记或学习心得,有何问题或意见,欢迎于本文评论下随时不吝指出,thanks。

     

     

    1 Adaboost的原理

    1.1 Adaboost是什么    

        AdaBoost,是英文"Adaptive Boosting"(自适应增强)的缩写,由Yoav Freund和Robert Schapire在1995年提出。它的自适应在于:前一个基本分类器分错的样本会得到加强,加权后的全体样本再次被用来训练下一个基本分类器。同时,在每一轮中加入一个新的弱分类器,直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。

        具体说来,整个Adaboost 迭代算法就3步:

    1. 初始化训练数据的权值分布。如果有N个样本,则每一个训练样本最开始时都被赋予相同的权值:1/N。
    2. 训练弱分类器。具体训练过程中,如果某个样本点已经被准确地分类,那么在构造下一个训练集中,它的权值就被降低;相反,如果某个样本点没有被准确地分类,那么它的权值就得到提高。然后,权值更新过的样本集被用于训练下一个分类器,整个训练过程如此迭代地进行下去。
    3. 将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后,加大分类误差率小的弱分类器的权重,使其在最终的分类函数中起着较大的决定作用,而降低分类误差率大的弱分类器的权重,使其在最终的分类函数中起着较小的决定作用。换言之,误差率低的弱分类器在最终分类器中占的权重较大,否则较小。

    1.2 Adaboost算法流程

        给定一个训练数据集T={(x1,y1), (x2,y2)…(xN,yN)},其中实例x \in \mathcal{X},而实例空间\mathcal{X} \subset \mathbb{R}^n,yi属于标记集合{-1,+1},Adaboost的目的就是从训练数据中学习一系列弱分类器或基本分类器,然后将这些弱分类器组合成一个强分类器。

        Adaboost的算法流程如下:

    • 步骤1. 首先,初始化训练数据的权值分布。每一个训练样本最开始时都被赋予相同的权值:1/N。

    • 步骤2. 进行多轮迭代,用m = 1,2, ..., M表示迭代的第多少轮

    a. 使用具有权值分布Dm的训练数据集学习,得到基本分类器(选取让误差率最低的阈值来设计基本分类器):

    b. 计算Gm(x)在训练数据集上的分类误差率

    由上述式子可知,Gm(x)在训练数据集上的 误差率em就是被Gm(x)误分类样本的权值之和。

    c. 计算Gm(x)的系数,am表示Gm(x)在最终分类器中的重要程度(目的:得到基本分类器在最终分类器中所占的权重):

    由上述式子可知,em <= 1/2时,am >= 0,且am随着em的减小而增大,意味着分类误差率越小的基本分类器在最终分类器中的作用越大。

    d. 更新训练数据集的权值分布(目的:得到样本的新的权值分布),用于下一轮迭代

    使得被基本分类器Gm(x)误分类样本的权值增大,而被正确分类样本的权值减小。就这样,通过这样的方式,AdaBoost方法能“重点关注”或“聚焦于”那些较难分的样本上。

        其中,Zm是规范化因子,使得Dm+1成为一个概率分布:

    • 步骤3. 组合各个弱分类器

    从而得到最终分类器,如下:

    1.3 Adaboost的一个例子

     

        下面,给定下列训练样本,请用AdaBoost算法学习一个强分类器。

        

     

        求解过程:初始化训练数据的权值分布,令每个权值W1i = 1/N = 0.1,其中,N = 10,i = 1,2, ..., 10,然后分别对于m = 1,2,3, ...等值进行迭代。

        拿到这10个数据的训练样本后,根据 X 和 Y 的对应关系,要把这10个数据分为两类,一类是“1”,一类是“-1”,根据数据的特点发现:“0 1 2”这3个数据对应的类是“1”,“3 4 5”这3个数据对应的类是“-1”,“6 7 8”这3个数据对应的类是“1”,9是比较孤独的,对应类“-1”。抛开孤独的9不讲,“0 1 2”、“3 4 5”、“6 7 8”这是3类不同的数据,分别对应的类是1、-1、1,直观上推测可知,可以找到对应的数据分界点,比如2.5、5.5、8.5 将那几类数据分成两类。当然,这只是主观臆测,下面实际计算下这个具体过程。

    迭代过程1

    对于m=1,在权值分布为D1(10个数据,每个数据的权值皆初始化为0.1)的训练数据上,经过计算可得:

      1. 阈值v取2.5时误差率为0.3(x < 2.5时取1,x > 2.5时取-1,则6 7 8分错,误差率为0.3),
      2. 阈值v取5.5时误差率最低为0.4(x < 5.5时取1,x > 5.5时取-1,则3 4 5 6 7 8皆分错,误差率0.6大于0.5,不可取。故令x > 5.5时取1,x < 5.5时取-1,则0 1 2 9分错,误差率为0.4),
      3. 阈值v取8.5时误差率为0.3(x < 8.5时取1,x > 8.5时取-1,则3 4 5分错,误差率为0.3)。

    可以看到,无论阈值v取2.5,还是8.5,总得分错3个样本,故可任取其中任意一个如2.5,弄成第一个基本分类器为:

    上面说阈值v取2.5时则6 7 8分错,所以误差率为0.3,更加详细的解释是:因为样本集中

      1. 0 1 2对应的类(Y)是1,因它们本身都小于2.5,所以被G1(x)分在了相应的类“1”中,分对了。
      2. 3 4 5本身对应的类(Y)是-1,因它们本身都大于2.5,所以被G1(x)分在了相应的类“-1”中,分对了。
      3. 但6 7 8本身对应类(Y)是1,却因它们本身大于2.5而被G1(x)分在了类"-1"中,所以这3个样本被分错了。
      4. 9本身对应的类(Y)是-1,因它本身大于2.5,所以被G1(x)分在了相应的类“-1”中,分对了。

    从而得到G1(x)在训练数据集上的误差率(被G1(x)误分类样本“6 7 8”的权值之和)e1=P(G1(xi)≠yi) = 3*0.1 = 0.3

    然后根据误差率e1计算G1的系数:

    这个a1代表G1(x)在最终的分类函数中所占的权重,为0.4236。
    接着更新训练数据的权值分布,用于下一轮迭代:

    值得一提的是,由权值更新的公式可知,每个样本的新权值是变大还是变小,取决于它是被分错还是被分正确。

    即如果某个样本被分错了,则yi * Gm(xi)为负,负负得正,结果使得整个式子变大(样本权值变大),否则变小。

    第一轮迭代后,最后得到各个数据的权值分布D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715,  0.0715,0.1666, 0.1666, 0.1666, 0.0715)。由此可以看出,因为样本中是数据“6 7 8”被G1(x)分错了,所以它们的权值由之前的0.1增大到0.1666,反之,其它数据皆被分正确,所以它们的权值皆由之前的0.1减小到0.0715。

    分类函数f1(x)= a1*G1(x) = 0.4236G1(x)。

    此时,得到的第一个基本分类器sign(f1(x))在训练数据集上有3个误分类点(即6 7 8)。

        从上述第一轮的整个迭代过程可以看出:被误分类样本的权值之和影响误差率,误差率影响基本分类器在最终分类器中所占的权重。

      迭代过程2

    对于m=2,在权值分布为D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715,  0.0715, 0.1666, 0.1666, 0.1666, 0.0715)的训练数据上,经过计算可得:

      1. 阈值v取2.5时误差率为0.1666*3(x < 2.5时取1,x > 2.5时取-1,则6 7 8分错,误差率为0.1666*3),
      2. 阈值v取5.5时误差率最低为0.0715*4(x > 5.5时取1,x < 5.5时取-1,则0 1 2 9分错,误差率为0.0715*3 + 0.0715),
      3. 阈值v取8.5时误差率为0.0715*3(x < 8.5时取1,x > 8.5时取-1,则3 4 5分错,误差率为0.0715*3)。

    所以,阈值v取8.5时误差率最低,故第二个基本分类器为:

     

    面对的还是下述样本:

    很明显,G2(x)把样本“3 4 5”分错了,根据D2可知它们的权值为0.0715, 0.0715,  0.0715,所以G2(x)在训练数据集上的误差率e2=P(G2(xi)≠yi) = 0.0715 * 3 = 0.2143。

    计算G2的系数:

     

     

    更新训练数据的权值分布:

    D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667,  0.01667, 0.1060, 0.1060, 0.1060, 0.0455)。被分错的样本“3 4 5”的权值变大,其它被分对的样本的权值变小。
    f2(x)=0.4236G1(x) + 0.6496G2(x)

    此时,得到的第二个基本分类器sign(f2(x))在训练数据集上有3个误分类点(即3 4 5)。

      迭代过程3

    对于m=3,在权值分布为D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667,  0.01667, 0.1060, 0.1060, 0.1060, 0.0455)的训练数据上,经过计算可得:

      1. 阈值v取2.5时误差率为0.1060*3(x < 2.5时取1,x > 2.5时取-1,则6 7 8分错,误差率为0.1060*3),
      2. 阈值v取5.5时误差率最低为0.0455*4(x > 5.5时取1,x < 5.5时取-1,则0 1 2 9分错,误差率为0.0455*3 + 0.0715),
      3. 阈值v取8.5时误差率为0.1667*3(x < 8.5时取1,x > 8.5时取-1,则3 4 5分错,误差率为0.1667*3)。

    所以阈值v取5.5时误差率最低,故第三个基本分类器为:

    依然还是原样本:

    此时,被误分类的样本是:0 1 2 9,这4个样本所对应的权值皆为0.0455,

    所以G3(x)在训练数据集上的误差率e3 = P(G3(xi)≠yi) = 0.0455*4 = 0.1820。

    计算G3的系数:

     

     

    更新训练数据的权值分布:

     

     

    D4 = (0.125, 0.125, 0.125, 0.102, 0.102,  0.102, 0.065, 0.065, 0.065, 0.125)。被分错的样本“0 1 2 9”的权值变大,其它被分对的样本的权值变小。

    f3(x)=0.4236G1(x) + 0.6496G2(x)+0.7514G3(x)

    此时,得到的第三个基本分类器sign(f3(x))在训练数据集上有0个误分类点。至此,整个训练过程结束。

        现在,咱们来总结下3轮迭代下来,各个样本权值和误差率的变化,如下所示(其中,样本权值D中加了下划线的表示在上一轮中被分错的样本的新权值):

    1. 训练之前,各个样本的权值被初始化为D1 = (0.1, 0.1,0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1);
    2. 第一轮迭代中,样本“6 7 8”被分错,对应的误差率为e1=P(G1(xi)≠yi) = 3*0.1 = 0.3,此第一个基本分类器在最终的分类器中所占的权重为a1 = 0.4236。第一轮迭代过后,样本新的权值为D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715,  0.0715, 0.1666, 0.1666, 0.1666, 0.0715);
    3. 第二轮迭代中,样本“3 4 5”被分错,对应的误差率为e2=P(G2(xi)≠yi) = 0.0715 * 3 = 0.2143,此第二个基本分类器在最终的分类器中所占的权重为a2 = 0.6496。第二轮迭代过后,样本新的权值为D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667,  0.01667, 0.1060, 0.1060, 0.1060, 0.0455);
    4. 第三轮迭代中,样本“0 1 2 9”被分错,对应的误差率为e3 = P(G3(xi)≠yi) = 0.0455*4 = 0.1820,此第三个基本分类器在最终的分类器中所占的权重为a3 = 0.7514。第三轮迭代过后,样本新的权值为D4 = (0.125, 0.125, 0.125, 0.102, 0.102,  0.102, 0.065, 0.065, 0.065, 0.125)。

        从上述过程中可以发现,如果某些个样本被分错,它们在下一轮迭代中的权值将被增大,反之,其它被分对的样本在下一轮迭代中的权值将被减小。就这样,分错样本权值增大,分对样本权值变小,而在下一轮迭代中,总是选取让误差率最低的阈值来设计基本分类器,所以误差率e(所有被Gm(x)误分类样本的权值之和)不断降低。

        综上,将上面计算得到的a1、a2、a3各值代入G(x)中,G(x) = sign[f3(x)] = sign[ a1 * G1(x) + a2 * G2(x) + a3 * G3(x) ],得到最终的分类器为:

    G(x) = sign[f3(x)] = sign[ 0.4236G1(x) + 0.6496G2(x)+0.7514G3(x) ]。

     

     

    2 Adaboost的误差界

      通过上面的例子可知,Adaboost在学习的过程中不断减少训练误差e,直到各个弱分类器组合成最终分类器,那这个最终分类器的误差界到底是多少呢?

    事实上,Adaboost 最终分类器的训练误差的上界为:

    下面,咱们来通过推导来证明下上述式子。

    当G(xi)≠yi时,yi*f(xi)<0,因而exp(-yi*f(xi))≥1,因此前半部分得证。

    关于后半部分,别忘了:

    整个的推导过程如下:

        这个结果说明,可以在每一轮选取适当的Gm使得Zm最小,从而使训练误差下降最快。接着,咱们来继续求上述结果的上界。

        对于二分类而言,有如下结果:

     

     

        其中,

        继续证明下这个结论。

        由之前Zm的定义式跟本节最开始得到的结论可知:

     

     

        而这个不等式可先由e^x和1-x的开根号,在点x的泰勒展开式推出。

        值得一提的是,如果取γ1, γ2… 的最小值,记做γ(显然,γ≥γi>0,i=1,2,...m),则对于所有m,有:

     

     

        这个结论表明,AdaBoost的训练误差是以指数速率下降的。另外,AdaBoost算法不需要事先知道下界γ,AdaBoost具有自适应性,它能适应弱分类器各自的训练误差率 。

        最后,Adaboost 还有另外一种理解,即可以认为其模型是加法模型、损失函数为指数函数、学习算法为前向分步算法的二类分类学习方法,下个月即12月份会再推导下,然后更新此文。而在此之前,有兴趣的可以参看《统计学习方法》第8.3节或其它相关资料。

     

     

    3 Adaboost 指数损失函数推导

        事实上,在上文1.2节Adaboost的算法流程的步骤3中,我们构造的各个基本分类器的线性组合

        是一个加法模型,而Adaboost算法其实是前向分步算法的特例。那么问题来了,什么是加法模型,什么又是前向分步算法呢?

    3.1 加法模型和前向分步算法

        如下图所示的便是一个加法模型

        其中,称为基函数,称为基函数的参数,称为基函数的系数。

        在给定训练数据及损失函数的条件下,学习加法模型成为经验风险极小化问题,即损失函数极小化问题:

        随后,该问题可以作如此简化:从前向后,每一步只学习一个基函数及其系数,逐步逼近上式,即:每步只优化如下损失函数:

        这个优化方法便就是所谓的前向分步算法。

        下面,咱们来具体看下前向分步算法的算法流程:

    • 输入:训练数据集
    • 损失函数:
    • 基函数集:
    • 输出:加法模型
    • 算法步骤:
      • 1. 初始化
      • 2. 对于m=1,2,..M
      • a)极小化损失函数

    得到参数

    • b)更新

      • 3. 最终得到加法模型

        就这样,前向分步算法将同时求解从m=1到M的所有参数()的优化问题简化为逐次求解各个(1≤m≤M)的优化问题。

    3.2 前向分步算法与Adaboost的关系

        在上文第2节最后,我们说Adaboost 还有另外一种理解,即可以认为其模型是加法模型、损失函数为指数函数、学习算法为前向分步算法的二类分类学习方法。其实,Adaboost算法就是前向分步算法的一个特例,Adaboost 中,各个基本分类器就相当于加法模型中的基函数,且其损失函数为指数函数。

        换句话说,当前向分步算法中的基函数为Adaboost中的基本分类器时,加法模型等价于Adaboost的最终分类器

     

     

        你甚至可以说,这个最终分类器其实就是一个加法模型。只是这个加法模型由基本分类器及其系数组成,m = 1, 2, ..., M。前向分步算法逐一学习基函数的过程,与Adaboost算法逐一学习各个基本分类器的过程一致。

        下面,咱们便来证明:当前向分步算法的损失函数是指数损失函数

        时,其学习的具体操作等价于Adaboost算法的学习过程

         假设经过m-1轮迭代,前向分步算法已经得到

        而后在第m轮迭代得到。其中,为:

     

        而未知。所以,现在咱们的目标便是根据前向分步算法训练,使得最终在训练数据集T上的指数损失最小,即

        针对这种需要求解多个参数的情况,可以先固定其它参数,求解其中一两个参数,然后逐一求解剩下的参数。例如我们可以固定,只针对做优化。

        换言之,在面对 这2m个参数都未知的情况下,可以:

    1. 先假定已知,求解出
    2. 然后再逐一求解其它未知参数。

        且考虑到上式中的既不依赖也不依赖G,所以是个与最小化无关的固定值,记为,即,则上式可以表示为(后面要多次用到这个式子,简记为):

        值得一提的是,虽然与最小化无关,但依赖于,随着每一轮迭代而发生变化。

        接下来,便是要证使得上式达到最小的就是Adaboost算法所求解得到的

        为求解上式,咱们先求再求

        首先求。对于任意,使上式最小的G(x)由下式得到:

        别忘了,

        跟1.2节所述的误差率的计算公式对比下:

     

     

        可知,上面得到的便是Adaboost算法的基本分类器,因为它是在第m轮加权训练数据时,使分类误差率最小的基本分类器。换言之,这个便是Adaboost算法所要求的,别忘了,在Adaboost算法的每一轮迭代中,都是选取让误差率最低的阈值来设计基本分类器。

        然后求。还是回到之前的这个式子上:

        这个式子的后半部分可以进一步化简,得:

     

        接着将上面求得的

        代入上式中,且对求导,令其求导结果为0,即得到使得一式最小的,即为:

        这里的跟上文1.2节中的计算公式完全一致。

        此外,毫无疑问,上式中的便是误差率:

        即就是被Gm(x)误分类样本的权值之和。

       就这样,结合模型,跟,可以推出

       从而有:

        与上文1.2节介绍的权值更新公式

        相比,只相差一个规范化因子,即后者多了一个

        所以,整个过程下来,我们可以看到,前向分步算法逐一学习基函数的过程,确实是与Adaboost算法逐一学习各个基本分类器的过程一致,两者完全等价。

        综上,本节不但提供了Adaboost的另一种理解:加法模型,损失函数为指数函数,学习算法为前向分步算法,而且也解释了最开始1.2节中基本分类器及其系数的由来,以及对权值更新公式的解释,你甚至可以认为本节就是对上文整个1.2节的解释。

     

     

    4 参考文献与推荐阅读

    1. wikipedia上关于Adaboost的介绍:http://zh.wikipedia.org/zh-cn/AdaBoost
    2. 邹博之决策树与Adaboost PPT:http://pan.baidu.com/s/1hqePkdY
    3. 邹博讲Adaboost指数损失函数推导的PPT:http://pan.baidu.com/s/1kTkkepD(第85页~第98页);
    4. 《统计学习方法 李航著》第8章;
    5. 关于adaboost的一些浅见:http://blog.sina.com.cn/s/blog_6ae183910101chcg.html
    6. A Short Introduction to Boosting:http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.5148&rep=rep1&type=pdf
    7. 南大周志华教授做的关于boosting 25年的报告PPT:http://vdisk.weibo.com/s/FcILTUAi9m111
    8. 《数据挖掘十大算法》第7章 Adaboost;
    9. http://summerbell.iteye.com/blog/532376
    10. 统计学习那些事:http://cos.name/2011/12/stories-about-statistical-learning/
    11. 统计学习基础学习笔记:http://www.loyhome.com/%E2%89%AA%E7%BB%9F%E8%AE%A1%E5%AD%A6%E4%B9%A0%E7%B2%BE%E8%A6%81the-elements-of-statistical-learning%E2%89%AB%E8%AF%BE%E5%A0%82%E7%AC%94%E8%AE%B0%EF%BC%88%E5%8D%81%E5%9B%9B%EF%BC%89/
    12. PRML第十四章组合模型读书笔记:http://vdisk.weibo.com/s/DmxNcM5_IaUD
    13. 顺便推荐一个非常实用的在线编辑LaTeX 公式的网页:http://private.codecogs.com/latex/eqneditor.php?lang=zh-cn
    展开全文
  • 目录10.1 Boosting方法10.2 Boosting拟合加性模型10.3 前向逐渐加性模型10.4 指数损失AdaBoost10.5 为什么是指数损失10.6 损失函数和鲁棒性10.7 数据挖掘的现成(Off-the-Shelf)过程10.8 10.1 Boosting方法 P337...

    10.1 提升(Boosting)方法

    • P337 Boosting和Bagging的联系是表面上的,boosting在根本上存在不同
    • P339 AdaBoost.M1,也称为Discrete AdaBoost,如果基分类器返回实值预测,如映射到[-1, 1]的的概率,可修改得到Real AdaBoost,见Firedman et al. (2000)
    • P340 单树桩和400Boosting的结果对比,和244结点树的对比

    10.2 Boosting拟合加性模型

    • P341 Boosting是用基本的“基函数”拟合加性展开additive expansions,这里基函数 G m ( x ) ∈ { − 1 , 1 } G_m(x)\in \{-1, 1\} Gm(x){1,1}
    • P341 加性展开是本书许多方法的核心:单层神经网络;小波;MARS;树。这类函数优化如下loss
      在这里插入图片描述
      对许多损失函数和基函数,需要计算密集型的数值优化技术,但如果能快速求解单一基函数的子问题时,经常能找到代替方案

    10.3 前向分段加性模型

    • P342 前向分段加性模型forward stagewise additive modeling(注意该模型和P298 backfitting算法的区别,backfitting时一个个特征扫过去,该方法是一个个基模型)

    10.4 指数损失和AdaBoost

    • P344 AdaBoost通过forward-stagewise additive modeling的方式优化指数损失(有一个细节,PRML和ESL对于指数损失函数的推导差个系数2,不过最终结果一致)

    10.5 为什么是指数损失

    • P345 AdaBoost.M1算法最初是不是从这个角度得到的,它与基于指数损失的向前逐步加性建模的等价性在提出五年后被发现.通过研究指数损失函数准则的性质,可以深入了解这个过程并且找出可能改善的方式.
    • P345 优化指数损失的期望得到log-odd/2,(另见PRML第14章P661)**所以AdaBoost可以看作是估计 P ( Y = 1 ∣ x ) P(Y=1|x) P(Y=1x)的log-odds的一半,进而用它的符号进行分类是合理的. 另一方面,考虑逻辑回归 P ( Y = 1 ∣ x ) = 1 1 + e − 2 f ( x ) P(Y=1|x)=\frac{1}{1+e^{-2f(x)}} P(Y=1x)=1+e2f(x)1的形式直接建模,其二项分布负对数似然——也即交叉熵的期望极值也能算出是log-odd/2,其实就是在逻辑回归概率为真实值的时取到。所以对数似然和指数损失的极值相等。但要注意指数损失不是任何二值变量的概率密度函数对数似然。(深入思考,其实最大似然就是在优化交叉熵,给定概率p,要用q估计它,采用对数最大似然,就是优化 E p ( ln ⁡ q ) \mathbb E_p(\ln q) Ep(lnq),变分法,得到最优时 q = p q=p q=p,所以最大似然估计的极值解是合理的,这应该也说明最大似然是渐近无偏的)

    10.6 损失函数和鲁棒性

    • P347 边缘margin y f ( x ) yf(x) yf(x),分类算法的损失函数应该对负边缘惩罚比正边缘大
    • P347-348 指数损失对更负的边缘惩罚更大,从而更关注分的很错的点. 交叉熵损失则接近线性,在所有数据点上更均匀,在有噪声的情况,即贝叶斯误差率不接近0时,更鲁棒,尤其是训练数据有错标签时。这些情况下AdaBoost的表现显著退化
    • P348 Huberized平方合页损失Huberized square hinge loss结合了交叉熵、平方损失和hinge loss的优良性质,图见P426. y f > 1 yf>1 yf>1时为0, y f < − 1 yf<-1 yf<1时为线性,中间为均方误差(这看起来有点像回归中Smooth L1)。因为二项函数比指数更容易计算,经验表明这是交叉熵的有用替代
    • P349 回归中均方误差和绝对值误差作为损失函数,也有类似分类中指数函数和交叉熵的讨论,两者分别在条件分布的期望和中位数处取极值。在有限样本上拟合过程中,平方误差损失更强调具有大的绝对值残差,因此更不鲁棒,尤其是对于长尾误差分布和异常值M回归采用Huber损失准则,看起来就是Smooth-L1,小区域平方,大区域线性,注意0阶和1阶导连续,它对适度厚尾数据更好

    10.7 数据挖掘的现成(Off-the-Shelf)过程

    • P351 用表总结各个方法的特点
      在这里插入图片描述
    • P351 偏度意味着长尾。用log变换,能得到更好的拟合
    • P352 "off-the-shelf"现成方法是指可以直接应用于数据,不用做太多预处理或学习过程的调整。数据挖掘对速度、可解释性、数据本身混乱的需求限制了off-the-shelf方法的使用。对数据挖掘来说,决策树是最能达到off-the-shelf过程的:1建树快;2解释性强,如果层不多的话;3易处理连续or类别特征和缺失值;4免疫单调变换;5抗离群点;6能抗无关特征
    • P352 树的问题是预测不好,boosting决策树提高了准确率,但牺牲了一些树的优点:计算速度、可解释性、对AdaBoost而言的重叠类鲁棒性和噪声标注(应该是指数损失造成). gradient boosted model(GBM)是tree boosting的一般化,试图缓解这些问题,以便为数据挖掘提供准确而有效的off-the-shelf procedure(所以GBDT的出现动机是明确的,其受欢迎也是因为它的构建满足了这一动机,也即让树的预测更好一些)

    10.8 垃圾邮件例子

    • P353 McNemar检验,检验两模型的二分类能力是否相同。见习题10.6,西瓜书P40
    • P353 偏相依图partial dependence plot两变量偏相依图two-variable partial dependence plots
    • P353 odds把概率从 [ 0 , 1 ] [0,1] [0,1]变为 R + \mathbb R^+ R+,log-odds进一步变为 R \mathbb R R

    10.9 提升树Boosting Trees

    • P356 提升树Boosting Trees是一堆树加起来,第 m m m步为
      在这里插入图片描述
    • P357 AdaBoost可看作是在树被限制为缩放分类树scaled classification tree时,Boosting Trees优化指数损失的特例。缩放分类树是指 β T \beta T βT,其中 T T T对不同区域进行1和-1的二分类。如果不限制缩放分类树,则第 m m m棵树的叶子区域的最优拟合值为
      在这里插入图片描述
      从而导出另一种优化指数损失的算法(这看起来还不是梯度提升的思路,因为每个样本的目标值不知道)
    • P357 用Huber loss代替均方误差,或者交叉熵代替指数损失,得到更鲁棒的提升树boosting trees,不过这些鲁棒准则不会得到简单快速的boosting算法.
    • P357 对于一般的损失函数。叶子区域找拟合值容易;但是如何划分区域生成一棵树,则很难,要看损失函数,不存在一般的准则,类似式(10.27)的近似就很重要了

    10.10 梯度提升的数值优化

    10.10.1 最速下降

    • P358 写了一页Gradient boosting。这里的优化是最速下降steepest descent,梯度方向,线搜索优化走多远(回忆最优化课上学的,这里是完整的无约束最优化方法Methods with direction determination and line optimization)

    10.10.2 梯度提升

    • P359 式10.30找叶子节点拟合值和已知方向的线搜索有类似的感觉,区别就在于前者只针对单独的叶子区域
    • P359 梯度提升中,损失函数变成了对梯度的均方误差。虽然这种方法和式10.29的提升树并不一致,但已经足够近似(拟合区域
    • P360 常用损失函数的梯度,注意分类中的交叉熵形式

    10.10.3 梯度提升的实现

    • P361 算法10.3中,梯度作为近似的loss只用来算树的划分区域,对于每个叶子节点,还是要用原先的Loss算拟合值(这里没有直接用梯度值的均值,我又看了一下统计学习方法,也是这么写的,woc以前我理解的gbdt是错的!也就是说梯度给出了树划分。GBDT很像线搜索,GBDT中的叶子表示这一堆点梯度差不多,可以看作是优化了约束方向,类似线搜索方向。而单纯的泛函中的梯度下降无法用于未见过的点。决策树中对特种空间中的附近位置没有训练样本的地方也起作用。这是GBDT的真正原理。) (所以提升树其实是一个更广泛的含义,比我之前理解的要广,GBDT只是借用了一下梯度)(xgboost则把原有loss function真的用二阶泰勒展开代替,树的划分和拟合都依据为带有正则的二阶近似loss。所以看来xgboost和书上这种只用一阶loss求划分区域的方式还是有一些不同的)

    10.11 提升中树的合适大小

    • P362 把树的叶子节点数固定,作为超参数。以防止前期树过大,降低模型效果增加计算量
    • P362 一种考虑 J J J取值的方式是用方差分析ANOVA(analysis of variance)展开,
      在这里插入图片描述
      把拟合函数分成主影响main effect、二阶交叉项second-order interactions等等。对许多实际问题,低阶交叉影响占主要地位.如果模型有太高阶交叉项,比如过大的决策树,则可能性能不好。树的大小 J J J近似交叉项的阶数,不存在大于 J − 1 J-1 J1阶的交叉项。 J = 2 J=2 J=2的树桩仅得到单变量的影响, J = 3 J=3 J=3允许有两变量交叉项影响
    • P363 许多应用问题中, J = 2 J=2 J=2不够,但也不可能要求 J > 10 J>10 J>10,经验值是 4 ⩽ J ⩽ 8 4\leqslant J\leqslant 8 4J8

    10.12 正则化

    • P364 用CV找迭代轮次 M M M,该参数类似早停

    10.12.1 收缩

    • P365 类似学习率 ν \nu ν. 经验表明,比0.1小的 ν \nu ν测试误差更小,需要大 M M M,用早停确定
    • P365 16.2.1节给出了前向分段收缩和L1正则的联系

    10.12.2 子采样subsampling

    • P365 随机梯度提升stochastic gradient boosting(这名字和sgd就差一个单词)。每次建树用子集,典型比例 η \eta η 1 / 2 1/2 1/2,对于大数据集,可以更小些
    • P365 这种操作有效的原因和Bagging可能类似,放到15章讨论
    • P367 一般,通过前期尝试确定 J , ν , η J,\nu,\eta J,ν,η,将 M M M留下作为主要超参(感觉这意思类似训网络时看线)

    10.13 解释性

    10.13.1 特征的相对重要性Relative Importance

    • P368 给出了决策树中特征重要性的一种度量方式,进一步该方式可扩展到加性树当中。是用平方损失的增益度量的。平方相关重要度squared relative importance,这种度量结果是平方相关的squared relevance,实际相关性还要开平方。由于这些度量相对,所以可以缩放,让最大的为100
    • P368 该方法有一个多分类版本

    10.13.2 偏相依图partial dependence plot

    • P369 对于输入特征,一维二维都好画,维度再高就画以某个输入为条件的一堆图,称为网格图a trellis of plots
    • P369 偏相依函数partial dependence functions的计算方法为:偏相依算模型中某特征子集对label的影响,可以以这一组特征子集的值为输入,其他所有补集特征求期望得到,求期望用训练集代替。这种方式计算量很大,因为特征子集的每一组取值都要扫一遍训练集中补集特征的值
      在这里插入图片描述

    在这里插入图片描述
    但决策树模型可以加速计算,不用引用数据集,见习题10.11(没做。。)

    • P370, 偏相依的解释需要注意是在考虑完其他补集特征在 f f f上的平均影响之后,所选子集特征再在 f f f上的影响,不是忽略掉补集特征,直接对 f f f的影响,后者由条件期望给出
      在这里插入图片描述
      该式是仅用 X S X_S XS f f f的最优最小二乘近似。只有 X S X_S XS X C X_C XC独立时,两者才相等(后者这式子意思是,给定子集 X S X_S XS,然后求 p ( X C ∣ X S ) p(X_C|X_S) p(XCXS)分布下的期望,这有点像是贝叶斯派。 f f f关于 X S X_S XS的不确定性有 p ( X C ∣ X S ) p(X_C|X_S) p(XCXS)的成分,所以求个期望,这也即最小二乘近似的最优解。或者换一种说法,前者偏相依函数是 ∫ p ( X C ) f ( X S , X C ) d X C \int p(X_C)f(X_S,X_C)dX_C p(XC)f(XS,XC)dXC,后者是 ∫ p ( X C ∣ X S ) f ( X S , X C ) d X C \int p(X_C|X_S)f(X_S,X_C)dX_C p(XCXS)f(XS,XC)dXC,两者的分布差一个条件,如果 X S X_S XS X C X_C XC独立,两者自然相等了)
    • P370 子集很多,但通常只有强相关性的小子集有信息量(这里强相关性应该指的是相对重要的特征)
    • P370 对于多分类,也可以看特征如何影响每一类 f k f_k fk,进一步如何影响对应类别概率的log-odds

    10.14 例子

    10.14.1 加州住房

    • P371 测试误差看起来随着基模型数量M的单调降低,因此,M的具体值不重要,只要别太小.在许多应用中都趋向于是这种形式.收缩策略趋向于消除过拟合的问题,特别是对较大的数据集

    10.14.2 新西兰鱼

    • P376 处理这个问题的方式很有趣。想知道某个地方有没有鱼,以及鱼的产量。用两个模型,第一个判断有没有,是一个分类问题;第二个在有的地方判断数量,是一个回归问题,这样训练集也被过滤的更干净。其中第二个模型把label进行log变换,因为假设物种数量服从了泊松分布(这里做log的理论依据我不太清楚,看起来是为了降偏度?)

    10.14.3 人口数据的职业预测

    文献笔记

    • P384 关于AdaBoost的训练误差界,可以参考李航《统计学习方法》8.2节

    参考文献:
    [1] Trevor Hastie, Robert Tibshirani, Jerome Friedman. The Elements of Statistical Learning, Second Edition
    [2] ESL CN

    展开全文
  • 本文结合机器学习班决策树与Adaboost 的PPT,跟邹讲Adaboost指数损失函数推导的PPT(第85~第98页)、以及李航的《统计学习方法》等参考资料写。 ##原理部分基本参考[大神博客]...
  • Adaboost

    2020-05-27 15:46:21
    Adaboost 1.思想 通过改变数据概率分布,来得到一系列的弱分类器。 主要有两个问题: (1)如何改变数据分布 将上一弱分类器误分样例的权重提高,正确分类样例的权重降低 (2)如何将若分类器组合为强分类器 加权...
  • adaboost

    千次阅读 2016-07-04 21:51:44
    1 Adaboost的原理 1.1 Adaboost是什么 AdaBoost,是英文"Adaptive Boosting"(自适应增强)的缩写,由Yoav Freund和Robert Schapire在1995年提出。它的自适应在于:前一个基本分类器分错的样本会得到加强,...
  • AdaBoost原理

    2015-09-04 08:11:05
    AdaBoost算法的理论推导,AdaBoost的本质是指数损失函数的梯度下降
  • 结论:提升树的损失函数选指数损失函数时,退化为adaboost 证明见《统计学习方法-第一版》 p145-146 scikit-learn 梯度提升树(GBDT)调参小结 对于分类模型,有**对数似然损失函数"deviance"和指数损失函数...
  • Adaboost总结

    2019-10-13 16:50:41
    Adaboost总结回顾boosting算法的基本原理Adaboost算法的基本思路AdaBoost分类问题的损失函数优化(推导过程)AdaBoost二元分类问题算法流程Adaboost小结 回顾boosting算法的基本原理     从图中可以看出,...
  • 基于距离函数和损失函数正则化的权值更新模式,使用相关熵距离函数,Itakura-Saito距离函数,指数一次近似距离和相关熵损失函数结合,实现了三种AdaBoost弱分类器权值更新算法。使用UCI数据库数据对提出的三种算法...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,881
精华内容 1,552
关键字:

adaboost指数损失