Machine Learning
  • Introduction
  • man
  • Linear model
    • Linear Regression
    • Generalized Linear Models
    • Nonlinear regression
  • bayes
    • bayesian network
    • Variational Bayesian inference
    • Gaussian Process Regression
  • Logistic Regression
    • L1 regularization
    • L2 regularization
    • softmax
    • Overflow and Underflow
  • SVM
    • C-SVM
    • C-SVM求解
  • EM
    • GMM
  • Maximum Entropy
    • IIS
  • HMM
    • viterbi algorithm
  • CRF
  • Random Forest
    • bagging
    • random forest
  • boosting
    • catboost
    • gradient boosting
    • Newton Boosting
    • online boosting
    • gcForest
    • Mixture models
    • XGBoost
    • lightGBM
    • SecureBoost
  • LDA
  • rank
    • RankNet
    • LambdaRank
    • SimRank
  • Factorization Machine
    • Field-aware Factorization Machine
    • xdeepFM
  • Clustering
    • BIRCH
    • Deep Embedding Clustering
  • Kalman filtering
  • word2vec
  • 关联规则挖掘
  • MATH-Mathematical Analysis
    • measure
  • MATH-probability
    • Variational Inference
    • Dirichlet分布
    • Gibbs Sampling
    • Maximum entropy probability distribution
    • Conjugate prior
    • Gaussian Process
    • Markov process
    • Poisson process
    • measure
    • Gumbel
  • MATH-Linear Algebra
    • SVD
    • SVD-推荐
    • PCA
    • Linear Discriminant Analysis
    • Nonnegative Matrix Factorization
  • MATH-Convex optimization
    • 梯度下降
    • 随机梯度下降
    • 牛顿法
    • L-BFGS
    • 最速下降法
    • 坐标下降法
    • OWL-QN
    • 对偶问题
    • 障碍函数法
    • 原对偶内点法
    • ISTA
    • ADMM
    • SAG
  • MATH-碎碎念
    • cost function
    • Learning Theory
    • sampling
    • Entropy
    • variational inference
    • basis function
    • Diffie–Hellman key exchange
    • wavelet transform
    • 图
    • Portfolio
    • 凯利公式
  • ML碎碎念
    • 特征
    • test
    • TF-IDF
    • population stability index
    • Shapley Values
  • 课件
    • xgboost算法演进
  • Time Series
  • PID
  • graph
    • SimRank
    • community detection
    • FRAUDAR
    • Anti-Trust Rank
    • Struc2Vec
    • graph theory
    • GNN
  • Anomaly Detection
    • Isolation Forest
    • Time Series
  • Dimensionality Reduction
    • Deep Embedded Clustering
  • Federated Learning
  • automl
  • Look-alike
  • KNN
  • causal inference
Powered by GitBook
On this page
  • 理解boosting
  • AdaBoost
  • AdaBoost解释
  • AdaBoost变种
  • LogitBoost
  • 误差分析
  • 参考佳文

Was this helpful?

boosting

Previousrandom forestNextcatboost

Last updated 4 years ago

Was this helpful?

理解boosting

boosting假定模型为加性模型：Fm(x)=∑m=1Mβmfm(x;γm)F_m(x) = \sum_{m=1}^M \beta_m f_m(x;\gamma_m)Fm​(x)=∑m=1M​βm​fm​(x;γm​) 优化目标：min⁡βm,γm∑i=1NL(yi,∑m=1Mβmfm(xi;γm))\min_{\beta_m,\gamma_m} \sum_{i=1}^N L(y_i, \sum_{m=1}^M \beta_m f_m(x_i;\gamma_m))minβm​,γm​​∑i=1N​L(yi​,∑m=1M​βm​fm​(xi​;γm​)) boosting过程： 1. initialise f0(x)=0f_0(x)=0f0​(x)=0 2. for m=1 to M

  • compute (βm,γm)=arg⁡min⁡∑i=1NL(yi,Fm−1(xi)+βmfm(xi;γm))(\beta_m,\gamma_m) = \arg \min \sum_{i=1}^N L(y_i, F_{m-1}(x_i) + \beta_m f_m(x_i;\gamma_m))(βm​,γm​)=argmin∑i=1N​L(yi​,Fm−1​(xi​)+βm​fm​(xi​;γm​))

  • set Fm(x)=∑m=1Mβmfm(x;γm)F_m(x) = \sum_{m=1}^M \beta_m f_m(x;\gamma_m)Fm​(x)=∑m=1M​βm​fm​(x;γm​)

AdaBoost

算法过程见《统计学习方法》p138，这里备注下细节。

  • 分类错误：迭代到m时，算分类误差，算的仅仅是当前这步分类器分类错误的，而不是前m步加权累加的分类错误。

  • 迭代终止条件：仅仅人为指定M（分类器数量）。（倘若第n步（n<Mn \lt Mn<M）时，分类准确率已经很高了。。。）

AdaBoost解释

优化目标函数 E=∑n=1Nexp⁡(−ynFm(Xn))E=\sum_{n=1}^N \exp(-y_n F_m(X_n))E=∑n=1N​exp(−yn​Fm​(Xn​)),n是样本数。

这个分类错误为什么不是0-1损失，而是指数形式？ 这个指数损失是0-1的凸上界。会有一些良好的性质，比如优化快。 但是，对异常值敏感，鲁棒性差。可能一个噪音点能将分界面拉动很远。（所以后来有了 LogitBoost）

序列最小化指数函数Fm(x)=∑m=1Mβmfm(x)F_m(x) = \sum_{m=1}^M \beta_m f_m(x)Fm​(x)=∑m=1M​βm​fm​(x)， 所以

E=∑n=1Nexp⁡(−ynFm(Xn))=∑n=1Nexp⁡(−ynFm−1(Xn)−ynβmfm(Xn))=∑n=1Nwnmexp⁡(−ynβmfm(Xn))=e−βm∑n∈Tmwnm+eβm∑n∈Mmwnm=e−βm∑n∈Tmwnm+e−βm∑n∈Mmwnm−e−βm∑n∈Mmwnm+eβm∑n∈Mmwnm=e−βm∑n=1Nwnm+(eβm−e−βm)∑n=1NwnmI(fm(Xn)≠yn)=e−βm∑n=1Nwnm+(eβm−e−βm)∑n=1NwnmI(fm(Xn)≠yn)\begin{align} E &= \sum_{n=1}^N \exp(-y_n F_m(X_n)) \\ &=\sum_{n=1}^N \exp(-y_n F_{m-1}(X_n) - y_n \beta_m f_m(X_n) ) \\ &=\sum_{n=1}^N w_n^m \exp(- y_n \beta_m f_m(X_n) ) \\ &= e^{- \beta_m} \sum_{n \in T_m} w_n^m + e^{\beta_m} \sum_{n \in M_m} w_n^m \\ &= e^{- \beta_m} \sum_{n \in T_m} w_n^m + e^{- \beta_m} \sum_{n \in M_m} w_n^m - e^{- \beta_m} \sum_{n \in M_m} w_n^m + e^{\beta_m} \sum_{n \in M_m} w_n^m \\ &= e^{- \beta_m} \sum_{n=1}^N w_n^m + (e^{\beta_m} - e^{- \beta_m}) \sum_{n=1}^N w_n^m I(f_m(X_n) \neq y_n) \\ &= e^{- \beta_m} \sum_{n=1}^N w_n^m + (e^{\beta_m} - e^{- \beta_m}) \sum_{n=1}^N w_n^m I(f_m(X_n) \neq y_n) \\ \end{align}E​=n=1∑N​exp(−yn​Fm​(Xn​))=n=1∑N​exp(−yn​Fm−1​(Xn​)−yn​βm​fm​(Xn​))=n=1∑N​wnm​exp(−yn​βm​fm​(Xn​))=e−βm​n∈Tm​∑​wnm​+eβm​n∈Mm​∑​wnm​=e−βm​n∈Tm​∑​wnm​+e−βm​n∈Mm​∑​wnm​−e−βm​n∈Mm​∑​wnm​+eβm​n∈Mm​∑​wnm​=e−βm​n=1∑N​wnm​+(eβm​−e−βm​)n=1∑N​wnm​I(fm​(Xn​)=yn​)=e−βm​n=1∑N​wnm​+(eβm​−e−βm​)n=1∑N​wnm​I(fm​(Xn​)=yn​)​​

其中

w_n^m = \exp(-y_n F_{m-1}(X_n) ) \\ y_n f_m(X_n) = 1 -2I(f_m(X_n) \neq y_n) \quad \mbox{就是分对了为1，分错了为-1}

然后通过∂E∂βm=0\frac {\partial E}{\partial \beta_m} = 0∂βm​∂E​=0来求解E最小值。

∂E∂βm=0⇒βm=12ln⁡(1−emem)这就是错误加权率em=∑n=1NwnmI(fm(Xn)≠yn)∑n=1Nwnm样本权重更新公式=∑n=1Nexp⁡(−ynFm−1(Xn))I(fm(Xn)≠yn)∑n=1Nwnm=∏n=1Nexp⁡(−ynβmfm(Xn))I(fm(Xn)≠yn)∑n=1Nwnm对照前面的权重更新公式，就是一直累乘起来\frac {\partial E}{\partial \beta_m} =0 \\ \Rightarrow \beta_m = \frac 12 \ln (\frac {1-e_m}{e_m}) \qquad \text{这就是错误加权率} \\ e_m = \frac {\sum_{n=1}^N w_n^m I(f_m(X_n) \neq y_n)}{\sum_{n=1}^N w_n^m} \qquad \text{样本权重更新公式} \\ = \frac {\sum_{n=1}^N \exp(-y_n F_{m-1}(X_n) ) I(f_m(X_n) \neq y_n)}{\sum_{n=1}^N w_n^m} \\ = \frac {\prod_{n=1}^N \exp(-y_n \beta_m f_m(X_n) ) I(f_m(X_n) \neq y_n)}{\sum_{n=1}^N w_n^m} \qquad \text{对照前面的权重更新公式，就是一直累乘起来} \\∂βm​∂E​=0⇒βm​=21​ln(em​1−em​​)这就是错误加权率em​=∑n=1N​wnm​∑n=1N​wnm​I(fm​(Xn​)=yn​)​样本权重更新公式=∑n=1N​wnm​∑n=1N​exp(−yn​Fm−1​(Xn​))I(fm​(Xn​)=yn​)​=∑n=1N​wnm​∏n=1N​exp(−yn​βm​fm​(Xn​))I(fm​(Xn​)=yn​)​对照前面的权重更新公式，就是一直累乘起来

AdaBoost变种

LogitBoost

既然是logit损失，那么优化的就是负对数似然：l(yn,p(xn))=−log(1+e−2ynFm(xn))l(y_n,p(x_n)) = -log(1+e^{-2 y_n F_m(x_n)})l(yn​,p(xn​))=−log(1+e−2yn​Fm​(xn​)) 。迭代时也用的是牛顿步。

误差分析

Bagging：样本分布的相似性E[∑nxin]=E[xi]E[\frac{\sum^n x_i}{n}]=E[x_i]E[n∑nxi​​]=E[xi​]，所以boostrap模型的bias与单个模型的bias差不多。各个boostrap模型之间有一定的相关性，但不完全相同，所以Aggregating之后降低了一定程度的variance。

Boosting : 有序的最小化损失函数，所以bias逐步下降

参考佳文

图来自

Real Adaboost adaboost要求输出必须是{−1,1}\{-1,1\}{−1,1},若不做此要求，然后相应的loss function改成E=∑n=1Nexp⁡(−yn(Fm−1(xn)+fm(xn)))E = \sum_{n=1}^N \exp(-y_n (F_{m-1}(x_n)+f_m(x_n)))E=∑n=1N​exp(−yn​(Fm−1​(xn​)+fm​(xn​))),则得到了Real Adaboost。（基分类器fm(x)f_m(x)fm​(x)已经没有显式的再加权重了）

Gentle Adaboost 若在Real Adaboost基础上通过牛顿步来优化loss function，则得到了Gentle Adaboost。

这些Adaboost都是指数损失。 指数损失的问题：错分的outline会得到很高的权重，导致对噪声的鲁棒性能差

http://rob.schapire.net/papers/explaining-adaboost.pdf
AdaBoost算法
AdaBoosting流程及数学证明