Tag Archives: Adaboost

[repost ]机器学习中的数学(3)-模型组合(Model Combining)之Boosting与Gradient Boosting

original:http://www.cnblogs.com/LeftNotEasy/archive/2011/01/02/machine-learning-boosting-and-gradient-boosting.html

版权声明:

本文由LeftNotEasy发布于http://leftnoteasy.cnblogs.com, 本文可以被全部的转载或者部分使用,但请注明出处,如果有问题,请联系wheeleast@gmail.com

 

前言:

本来上一章的结尾提到,准备写写线性分类的问题,文章都已经写得差不多了,但是突然听说最近Team准备做一套分布式的分类器,可能会使用Random Forest来做,下了几篇论文看了看,简单的random forest还比较容易弄懂,复杂一点的还会与boosting等算法结合(参见iccv09),对于boosting也不甚了解,所以临时抱佛脚的看了看。说起boosting,强哥之前实现过一套Gradient Boosting Decision Tree(GBDT)算法,正好参考一下。

最近看的一些论文中发现了模型组合的好处,比如GBDT或者rf,都是将简单的模型组合起来,效果比单个更复杂的模型好。组合的方式很多,随机化(比如random forest),Boosting(比如GBDT)都是其中典型的方法,今天主要谈谈Gradient Boosting方法(这个与传统的Boosting还有一些不同)的一些数学基础,有了这个数学基础,上面的应用可以看Freidman的Gradient Boosting Machine。

本文要求读者学过基本的大学数学,另外对分类、回归等基本的机器学习概念了解。

本文主要参考资料是prml与Gradient Boosting Machine。

 

Boosting方法:

Boosting这其实思想相当的简单,大概是,对一份数据,建立M个模型(比如分类),一般这种模型比较简单,称为弱分类器(weak learner)每次分类都将上一次分错的数据权重提高一点再进行分类,这样最终得到的分类器在测试数据与训练数据上都可以得到比较好的成绩。

image

上图(图片来自prml p660)就是一个Boosting的过程,绿色的线表示目前取得的模型(模型是由前m次得到的模型合并得到的),虚线表示当前这次模型。每次分类的时候,会更关注分错的数据,上图中,红色和蓝色的点就是数据,点越大表示权重越高,看看右下角的图片,当m=150的时候,获取的模型已经几乎能够将红色和蓝色的点区分开了。

Boosting可以用下面的公式来表示:image

训练集中一共有n个点,我们可以为里面的每一个点赋上一个权重Wi(0 <= i < n),表示这个点的重要程度,通过依次训练模型的过程,我们对点的权重进行修正,如果分类正确了,权重降低,如果分类错了,则权重提高,初始的时候,权重都是一样的。上图中绿色的线就是表示依次训练模型,可以想象得到,程序越往后执行,训练出的模型就越会在意那些容易分错(权重高)的点。当全部的程序执行完后,会得到M个模型,分别对应上图的y1(x)…yM(x),通过加权的方式组合成一个最终的模型YM(x)。

我觉得Boosting更像是一个人学习的过程,开始学一样东西的时候,会去做一些习题,但是常常连一些简单的题目都会弄错,但是越到后面,简单的题目已经难不倒他了,就会去做更复杂的题目,等到他做了很多的题目后,不管是难题还是简单的题都可以解决掉了。

 

Gradient Boosting方法:

其实Boosting更像是一种思想,Gradient Boosting是一种Boosting的方法,它主要的思想是,每一次建立模型是在之前建立模型损失函数的梯度下降方向。这句话有一点拗口,损失函数(loss function)描述的是模型的不靠谱程度,损失函数越大,则说明模型越容易出错(其实这里有一个方差、偏差均衡的问题,但是这里就假设损失函数越大,模型越容易出错)。如果我们的模型能够让损失函数持续的下降,则说明我们的模型在不停的改进,而最好的方式就是让损失函数在其梯度(Gradient)的方向上下降。

下面的内容就是用数学的方式来描述Gradient Boosting,数学上不算太复杂,只要潜下心来看就能看懂:)

    可加的参数的梯度表示:

假设我们的模型能够用下面的函数来表示,P表示参数,可能有多个参数组成,P = {p0,p1,p2….},F(x;P)表示以P为参数的x的函数,也就是我们的预测函数。我们的模型是由多个模型加起来的,β表示每个模型的权重,α表示模型里面的参数。为了优化F,我们就可以优化{β,α}也就是P。

image

我们还是用P来表示模型的参数,可以得到,Φ(P)表示P的likelihood函数,也就是模型F(x;P)的loss函数,Φ(P)=…后面的一块看起来很复杂,只要理解成是一个损失函数就行了,不要被吓跑了。

image   既然模型(F(x;P))是可加的,对于参数P,我们也可以得到下面的式子:image   这样优化P的过程,就可以是一个梯度下降的过程了,假设当前已经得到了m-1个模型,想要得到第m个模型的时候,我们首先对前m-1个模型求梯度。得到最快下降的方向,gm就是最快下降的方向。

image    这里有一个很重要的假设,对于求出的前m-1个模型,我们认为是已知的了,不要去改变它,而我们的目标是放在之后的模型建立上。就像做事情的时候,之前做错的事就没有后悔药吃了,只有努力在之后的事情上别犯错:

image    我们得到的新的模型就是,它就在P似然函数的梯度方向。ρ是在梯度方向上下降的距离。

image    我们最终可以通过优化下面的式子来得到最优的ρ:

image

    可加的函数的梯度表示:

上面通过参数P的可加性,得到了参数P的似然函数的梯度下降的方法。我们可以将参数P的可加性推广到函数空间,我们可以得到下面的函数,此处的fi(x)类似于上面的h(x;α),因为作者的文献中这样使用,我这里就用作者的表达方法:

image    同样,我们可以得到函数F(x)的梯度下降方向g(x)

image    最终可以得到第m个模型fm(x)的表达式:

image

 

    通用的Gradient Descent Boosting的框架:

下面我将推导一下Gradient Descent方法的通用形式,之前讨论过的:

image    对于模型的参数{β,α},我们可以用下面的式子来进行表示,这个式子的意思是,对于N个样本点(xi,yi)计算其在模型F(x;α,β)下的损失函数,最优的{α,β}就是能够使得这个损失函数最小的{α,β}。image 表示两个m维的参数:

image    写成梯度下降的方式就是下面的形式,也就是我们将要得到的模型fm(x)的参数{αm,βm}能够使得fm的方向是之前得到的模型Fm-1(x)的损失函数下降最快的方向:

image

对于每一个数据点xi都可以得到一个gm(xi),最终我们可以得到一个完整梯度下降方向

image

image    为了使得fm(x)能够在gm(x)的方向上,我们可以优化下面的式子得到,可以使用最小二乘法:

image    得到了α的基础上,然后可以得到βm。  image    最终合并到模型中:

image

算法的流程图如下

image     之后,作者还说了这个算法在其他的地方的推广,其中,Multi-class logistic regression and classification就是GBDT的一种实现,可以看看,流程图跟上面的算法类似的。这里不打算继续写下去,再写下去就成论文翻译了,请参考文章:Greedy function Approximation – A Gradient Boosting Machine,作者Freidman。

 

总结:

本文主要谈了谈Boosting与Gradient Boosting的方法,Boosting主要是一种思想,表示“知错就改”。而Gradient Boosting是在这个思想下的一种函数(也可以说是模型)的优化的方法,首先将函数分解为可加的形式(其实所有的函数都是可加的,只是是否好放在这个框架中,以及最终的效果如何)。然后进行m次迭代,通过使得损失函数在梯度方向上减少,最终得到一个优秀的模型。值得一提的是,每次模型在梯度方向上的减少的部分,可以认为是一个“小”的或者“弱”的模型,最终我们会通过加权(也就是每次在梯度方向上下降的距离)的方式将这些“弱”的模型合并起来,形成一个更好的模型。

有了这个Gradient Descent这个基础,还可以做很多的事情。也在机器学习的道路上更进一步了:)

Machine Learning Open Source software list-3

Logo Armadillo library 0.9.80

by cu24gjf – September 22, 2010, 01:20:11 CET [ Project Homepage BibTeX Download ] 8338 views, 2116 downloads, 1 subscription

Rating Whole StarWhole StarWhole StarWhole StarEmpty Star
(based on 2 votes)

About: Armadillo is a template C++ linear algebra library aiming towards a good balance between speed and ease of use. Matrix decompositions are provided through optional integration with LAPACK and ATLAS.

Changes:

  • Many speedups due to internal architecture improvements
  • Added template-based size specification of matrices
  • Added insertion/deletion of rows & columns
  • Added insertion/deletion of cube slices
  • Added set_imag() & set_real()
  • Added in-place operations on diagonals
  • Fixes for a few corner cases

Logo MultiBoost 1.0.01

by busarobi – September 21, 2010, 16:04:57 CET [ Project Homepage BibTeX BibTeX for corresponding Paper Download ] 2223 views, 337 downloads, 1 subscription

About: MultiBoost is a multi-purpose boosting package implemented in C++. It is based on the multi-class/multi-task AdaBoost.MH algorithm [Schapire-Singer, 1999]. Basic base learners (stumps, trees, products, Haar filters for image processing) can be easily complemented by new data representations and the corresponding base learners, without interfering with the main boosting engine.

Changes:Small bug on Trees of Haar stumps corrected.


Logo peewit 0.6

by lorenz – September 18, 2010, 16:22:01 CET [ Project Homepage BibTeX BibTeX for corresponding Paper Download ] 2838 views, 482 downloads, 1 subscription

About: peewit is a prototype implementation of a lightweight framework that provides workflow services for programming, running and result examination of machine learning experiments. It does not provide any ML algorithms and it is restricted to experiments that have a regular tree structure. On the other hand, it does not make assumptions on the type of task and fits many settings. The current version number is 0.6.7.

Changes:archiving services


Logo dlib ml 17.31

by davis685 – September 16, 2010, 05:34:32 CET [ Project Homepage BibTeX BibTeX for corresponding Paper Download ] 15927 views, 3282 downloads, 1 subscription

About: A C++ toolkit containing machine learning algorithms and tools that facilitate creating complex software in C++ to solve real world problems.

Changes:This release adds LAPACK support. In particular, now all matrix decomposition routines make use of LAPACK whenever DLIB_USE_LAPACK is #defined.


Logo OpenOpt 0.31

by Dmitrey – September 15, 2010, 11:14:46 CET [ Project Homepage BibTeX Download ] 9605 views, 2062 downloads, 1 subscription

Rating Whole StarWhole StarWhole StarWhole StarEmpty Star
(based on 2 votes)

About: Universal Python-written numerical optimization toolbox. Problems: NLP, LP, QP, NSP, MILP, LSP, LLSP, MMP, GLP, SLE etc; automatic differentiation is available

Changes:http://openopt.org/Changelog


Logo JMLR libDAI 0.2.7

by jorism – September 4, 2010, 09:39:57 CET [ Project Homepage BibTeX BibTeX for corresponding Paper Download ] 9368 views, 1567 downloads, 2 subscriptions

Rating Whole StarWhole StarWhole StarWhole StarWhole Star
(based on 1 vote)

About: libDAI provides free & open source implementations of various (approximate) inference methods for graphical models with discrete variables, including Bayesian networks and Markov Random Fields.

Changes:libDAI release 0.2.7 is a bug-fix release which fixes a bug in the junction-tree MAP inference which could yield incorrect results in some cases. This release accompanies a JMLR open source track publication about libDAI.


Logo JMLR Surrogate Modeling Toolbox 7.0.2

by dgorissen – September 4, 2010, 07:48:59 CET [ Project Homepage BibTeX BibTeX for corresponding Paper Download ] 1703 views, 382 downloads, 1 subscription

About: The SUMO Toolbox is a Matlab toolbox that automatically builds accurate surrogate models (also known as metamodels or response surface models) of a given data source (e.g., simulation code, data set, script, …) within the accuracy and time constraints set by the user. The toolbox minimizes the number of data points (which it selects automatically) since they are usually expensive.

Changes:Incremental update, fixing some cosmetic issues, coincides with JMLR publication.


Logo JMLR r-cran-mboost 2.0-6

by r-cran-robot – September 4, 2010, 07:47:13 CET [ Project Homepage BibTeX Download ] 4911 views, 1389 downloads, 1 subscription

About: Model-Based Boosting

Changes:Fetched by r-cran-robot on 2010-08-12 12:52:48.210419


Logo Moses Decoder 2010-08-13

by oliver_wilson – September 3, 2010, 13:49:43 CET [ Project Homepage BibTeX BibTeX for corresponding Paper Download ] 443 views, 142 downloads, 1 subscription

About: Moses is a statistical machine translation system that allows you to automatically train translation models for any language pair. All you need is a collection of translated texts (parallel corpus). An efficient search algorithm finds quickly the highest probability translation among the exponential number of choices.

Changes:Initial Announcement on mloss.org.


Logo jblas 1.1.1

by mikio – September 1, 2010, 13:53:51 CET [ Project Homepage BibTeX Download ] 4107 views, 934 downloads, 1 subscription

Rating Whole StarWhole StarWhole Star1/2 StarEmpty Star
(based on 2 votes)

About: jblas is a fast linear algebra library for Java. jblas is based on BLAS and LAPACK, the de-facto industry standard for matrix computations, and uses state-of-the-art implementations like ATLAS for all its computational routines, making jBLAS very fast.

Changes:Changes from 1.0:

  • Added singular value decomposition
  • Fixed bug with returning complex values
  • Many other minor improvements