#

机器学习(八)

机器学习 李航版
机器学习
发布日期:   2021-10-30
文章字数:   2.1k

提升方法

笔记摘要

  • 在PAC（概率近似正确(PAC, Probably approximately correct)）学习框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。
  • 提升方法的两个问题
  1. 在每一轮如何改变训练数据的权值或概率分布
  2. 如何将弱分类器组合成一个强分类器
  • Adaboost的解决方案：
  1. 提高那些被前一轮弱分类器错误分类样本的权值，降低那些被正确分类的样本的权值
  2. 加权多数表决的方法，加大分类误差率小的弱分类器的权值，减小分类误差率大的弱分类器的权值

AdaBoost算法

  • 输入：弱学习算法和训练数据集
    T={(x1,y1),(x2,y2),...,(xN,yN)},x∈X⊆RnT=\{(x_1,y_1), (x_2,y_2),...,(x_N,y_N)\}, x\in X \subseteq R^n
  • 输出：最终分类器G(x)G(x)
  • 步骤
  1. 初始化训练数据的权值分布 D1=(w11,⋯ ,w1i,⋯ ,w1N,w1i=1N)​D_1=(w_{11},\cdots,w_{1i},\cdots,w_{1N},w_{1i}=\frac{1}{N})​
  2. m = 1,2, ⋯\cdots,M
    ( a ) 使用具有权值分布DmD_m的训练数据集学习，得到基本的分类器

    Gm(x):X→{−1,+1}G_m(x):X→\{-1,+1\}

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

    em=∑i=1NP(Gm(xi)≠yi)=∑i=1NwmiI(Gm(xi)≠yi)e_m=\sum_{i=1}^{N}P(G_m(x_i)\not= y_i)=\sum_{i=1}^{N}w_{mi}I(G_m(x_i)\not=y_i)

    ( c ) 计算Gm(x)G_m(x)的系数

    αm=12log1−emem\alpha_m=\frac{1}{2}log\frac{1-e_m}{e_m}

    ( d ) 更新训练数据集的权值分布

    wm+1,i=wmiZmexp(−αmyiGm(xi))​w_{m+1,i}=\frac{w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i))​

    Zm=∑i=1Nwmiexp(−αmyiGm(xi))Z_m=\sum_{i=1}^Nw_{mi}exp(-\alpha_my_iG_m(x_i))

  3. f(x)=∑m=1MαmGm(x)f(x)=\sum_{m=1}^M\alpha_mG_m(x)
  4. 最终分类器G(x)=sign(f(x))=sign(∑m=1MαmGm(x))G(x)=sign(f(x))=sign(\sum_{m=1}^M\alpha_mG_m(x))
  • 误分类样本在下一轮学习中起更大的作用。不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同的作用， 这是AdaBoost的一个特点
  • 利用基本分类器的线性组合构建最终分类器使AdaBoost的另一特点

AdaBoost算法的训练误差分析

  • AdaBoost算法最终分类器的训练误差界为

1N∑i=1NI(G(xi)≠yi)≤1N∑iexp⁡(−yif(xi))=∏mZm\frac{1}{N}\sum\limits_{i=1}\limits^N I(G(x_i)\neq y_i)\le\frac{1}{N}\sum\limits_i\exp(-y_i f(x_i))=\prod\limits_m Z_m

这个的意思就是说指数损失是0-1损失的上界，这个上界使通过递推得到的，是归一化系数的连乘

AdaBoost算法的解释

  • 模型为加法模型， 损失函数为指数函数， 学习算法为前向分步算法时的二分类学习方法。根据这些条件可以推导出AdaBoost

前向分步算法

  • 输入：训练数据集T=(x1,y1),(x2,y2),...,(xN,yN),xi∈X⊆Rn,yi∈{−1,1}T={(x_1,y_1),(x_2,y_2),...,(x_N, y_N)}, x_i \in X \subseteq R^n, y_i\in \{-1, 1\}， 损失函数L(y,f(x))L(y, f(x)); 基函数集合{b(x;γ)}\{b(x;\gamma)\}

  • 输出：加法模型f(x)f(x)

  • 步骤：

  1. 初始化f0(x)=0f_0(x)=0

  2. 对m=1,2,⋯ ,Mm=1,2,\cdots,M, 极小化损失函数

    (βm,γm)=arg⁡min⁡β,γ∑i=1NL(yi,fm−1(xi)+βb(xi;γ))(\beta_m,\gamma_m)=\arg\min \limits_ {\beta,\gamma}\sum_{i=1}^NL(y_i, f_{m-1}(x_i)+\beta b(x_i;\gamma))

  3. 更新

    fm(x)=fm−1(x)+βmb(x;γm)f_m(x)=f_{m-1}(x)+\beta _mb(x;\gamma_m)

  4. 得到加法模型

    f(x)=fM(x)=∑m=1Mβmb(x;γm)f(x)=f_M(x)=\sum_{m=1}^M\beta_m b(x;\gamma_m)

提升树

  • 提升树是以分类树或回归树为基本分类器的提升方法，被认为是统计学习中性能最好的方法之一
  • 提升方法实际采用加法模型（即基函数的线性组合）与前向分步算法

提升树模型

  • 以决策树为基函数的提升方法称为提升树
  • 提升树模型可以表示成决策树的加法模型

fM(x)=∑m=1MT(x;Θm)f_M(x)=\sum_{m=1}^MT(x;\Theta_m)

提升树算法

  • 针对不同问题的提升树学习算法， 其主要区别在于使用的损失函数不同：
  1. 平方误差损失函数用于回归问题
  2. 指数损失函数用于分类问题
  3. 一般损失函数的一般决策问题

回归问题的提升树算法

  • 输入：训练数据集T=(x1,y1),(x2,y2),...,(xN,yN),xi∈X⊆Rn,yi∈Y⊆RT={(x_1,y_1),(x_2,y_2),...,(x_N, y_N)}, x_i \in X \subseteq R^n,y_i \in Y \subseteq R

  • 输出：提升树fM(x)f_M(x)

  • 步骤：

  1. 初始化f0(x)=0f_0(x)=0
  2. 对m=1,2,…,Mm=1,2,\dots,M
    1. 计算残差

    rmi=yi−fm−1(xi),i=1,2,…,Nr_{mi}=y_i-f_{m-1}(x_i), i=1,2,\dots,N

    1. 拟合残差rmir_{mi}学习一个回归树，得到T(x;Θm)T(x;\Theta_m)
    2. 更新fm(x)=fm−1(x)+T(x;Θm)f_m(x)=f_{m-1}(x)+T(x;\Theta_m)
  3. 得到回归问题提升树

    f(x)=fM(x)=∑m=1MT(x;Θm)f(x)=f_M(x)=\sum_{m=1}^MT(x;\Theta_m)

梯度提升(GBDT)

输入： 训练数据集T=(x1,y1),(x2,y2),…,(xN,yN),xi∈x⊆Rn,yi∈y⊆RT={(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)}, x_i \in x \subseteq R^n, y_i \in y \subseteq R；损失函数L(y,f(x))L(y,f(x))
输出：回归树f^(x)\hat{f}(x)
步骤：

  1. 初始化

    f0(x)=arg⁡min⁡c∑i=1NL(yi,c)f_0(x)=\arg\min\limits_c\sum_{i=1}^NL(y_i, c)

  2. 对m=1,2,⋯ ,Mm=1,2,\cdots,M

（ a ）对i=1,2,⋯ ,Ni=1,2,\cdots,N,计算

rmi=−[∂L(yi,f(xi))∂f(xi)]f(x)=fm−1(x)r_{mi}=-\left[\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}\right]_{f(x)=f_{m-1}(x)}

（ b ）对rmir_{mi}拟合一个回归树，得到第mm棵树的叶节点区域Rmj,j=1,2,…,JR_{mj}, j=1,2,\dots,J

（ c ） 对j=1,2,…,Jj=1,2,\dots,J，计算

cmj=arg⁡min⁡c∑xi∈RmjL(yi,fm−1(xi)+c)c_{mj}=\arg\min_c\sum_{xi\in R_{mj}}L(y_i,f_{m-1}(x_i)+c)

  1. 更新

    fm(x)=fm−1(x)+∑j=1JcmjI(x∈Rmj)f_m(x)=f_{m-1}(x)+\sum_{j=1}^Jc_{mj}I(x\in R_{mj})

  2. 得到回归树

    f^(x)=fM(x)=∑m=1M∑j=1JcmjI(x∈Rmj)\hat{f}(x)=f_M(x)=\sum_{m=1}^M\sum_{j=1}^Jc_{mj}I(x\in R_{mj})

习题解答

  • 比较支持向量机、 AdaBoost 、逻辑斯谛回归模型的学习策略与算法。

    • 支持向量机的学习策略是当训练数据近似线性可分时，通过软间隔最大化，学习一个线性分类器，其学习算法是SMO序列最小最优化算法
    • AdaBoost的学习策略是通过极小化加法模型的指数损失，得到一个强分类器，其学习算法是前向分步算法
    • 逻辑斯谛回归模型的学习策略是在给定的训练数据条件下对模型进行极大似然估计或正则化的极大似然估计，其学习算法可以是改进的迭代尺度算法（IIS），梯度下降法，牛顿法以及拟牛顿法
文章作者: 王胜鹏
文章链接: https://wspwhut6666.gitee.io/posts/f7d407e6.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 王胜鹏 !
机器学习 李航版
赏
评论
 上一篇
李群与李代数 李群与李代数
李群与李代数 在 SLAM 中位姿是未知的，而我们需要解决什 么样的相机位姿最符合当前观测数据这样的问题。一种典型的方式是把它构建成一个优化 问题，求解最优的 R;t，使得误差最小化。 通过李群——李代数间的转换关系，旋转矩阵自身是带有约束
2022-01-04 SLAM
SLAM十四讲
下一篇 
机器学习(七) 机器学习(七)
支持向量机 笔记摘要 SVM的基本模型是定义在特征空间上的间隔最大的线性分类器 线性可分支持向量机和线性支持向量机假设输入空间和特征空间的元素一一对应，并将输入空间中的输入映射为特征空间的特征向量；非线性支持向量机利用一个从输入空间到特征
2021-10-30 机器学习
机器学习 李航版
  目录