精华内容
下载资源
问答
  • 泰勒级数的理解

    千次阅读 2018-02-13 10:56:36
    通俗的理解:把质的困难转化成量的复杂。展开前求解函数的值很困难,展开后是幂函数的线性组合,虽然有很多很多项,但是每一项都是幂函数,因此每一项都容易求解。于是只要展开后的求和,就能得到展开前的函数的值...

    泰勒级数:用多项式函数逼近光滑函数。

    泰勒级数的原理出于很朴素的想法:把一切函数表达式都转化为多项式函数来近似,尤其是复杂函数。

    通俗的理解:把质的困难转化成量的复杂。展开前求解函数的值很困难,展开后是幂函数的线性组合,虽然有很多很多项,但是每一项都是幂函数,因此每一项都容易求解。于是只要对展开后的求和,就能得到展开前的函数的值。

    机器学习算法的本质上是优化问题求解,如梯度下降、牛顿法、共轭梯度法等常见的优化方法,这些都离不开泰勒级数的应用。



    参考:

    http://www.matongxue.com/madocs/7.html#/madoc

    展开全文
  • 今天的文章我们来讨论大名鼎鼎的泰勒公式,泰勒公式[1]真的非常有名,我相信上过高数...泰勒公式的用途在看具体的公式和证明之前,我们先来了解一下它的用途,然后带着用途的理解再去思考它出现的背景以及原理会容...

    今天的文章我们来讨论大名鼎鼎的泰勒公式泰勒公式[1]真的非常有名,我相信上过高数课的一定都记得它的大名。即使你翘掉了所有的课,也一定会在考前重点里见过。

    我对它的第一映像就是比较难,而且感觉没有太多意思,就是一个近似的函数而已。最近重温了一下有了一些新的心得,希望尽我所能讲解清楚。

    泰勒公式的用途

    在看具体的公式和证明之前,我们先来了解一下它的用途,然后带着对用途的理解再去思考它出现的背景以及原理会容易许多。这也是我自学这么久总结出来的规律。

    泰勒公式本质解决的是近似的问题,比如说我们有一个看起来很复杂的方程,我们直接计算方程本身的值可能非常麻烦。所以我们希望能够找到一个近似的方法来获得一个足够近似的值。

    从这里,我们得到了两个重点,一个是近似的方法,另一个是近似的精度。我们既需要找到合适的方法来近似,同时也需要保证近似的精度是可控的。否则一切都没有意义,结合实际其实很好理解,比如我们用机床造一个零件。我们都知道世界上不存在完美的圆,实际上我们也并不需要完美,但是我们需要保证偏差是可控的,并且在一定的范围内。泰勒公式也是一样,它既可以帮助我们完成近似,也可以保证得到的结果是足够精确的。

    泰勒公式的定义

    我们下面来看看泰勒公式的定义,我们已经知道了它的用途是求一个函数的近似值。但是我们怎么来求呢,其实一个比较朴素的思路是通过斜率逼近

    举个例子:

    f02b1b0e4c9b931de69af748ec7eb2f6.png

    这是一张经典的导数图,从上图我们可以看到,随着Δx的减小,点 P0 和 P 也会越来越接近,这就带来了 Δy 越来越接近 Δx f'(x0)。

    当然,当 Δx 比较大的时候显然误差就会比较大,为了缩小误差,我们可以引入二阶导数、三阶导数以及高阶导数。由于我们并不知道函数究竟可以有多少阶导数,我们不妨假设f(x)在区间内一直有(n+1)阶导数,我们试着写出一个多项式来逼近原函数:

    678ba60eb22c8c16c1e53adcfc654605.png

    我们希望这个式子与原值的误差越小越好,究竟要多小才算足够好呢?数学家们给出了定义,希望它是

    (x-x0)^n 的高阶无穷小。也就是说误差比上 (x-x0)^n 的极限是0。

    我们前面说了,我们是通过导数来逼近的,所以我们假设:

    0f6ee13c85f3576690ba076aff65c90d.png

    按照这个假设我们可以很方便地得到系数了,其实很简单,我们构造系数使得求导之后相乘的常数项全部约掉。

    2a28f25d6b5f693fc2fb875af8ac9098.png

    我们把这两个式子带入一下,可以得到:

    3bc060b588f8d8d84d035dca2dcb29ce.png

    泰勒公式的证明

    其实上面的式子就是泰勒公式的内涵了,也就是说我们通过高阶导数来逼近了原函数。最后我们只需要证明这个式子就是我们想要的,也就是它的误差足够小。

    我们同样用一个函数 R(x) 来表示 P_n(x) 与原函数 f(x) 的差值。我们直接比较比较困难,所以数学家采取了一系列花里胡哨、叹为观止的操作。

    我们带入一下可以发现,R(x0) = 0,不仅如此:

    960b2b77c295c92abd533cf00843af77.png

    以上步骤完全不需要证明,我们直接带入求导就可以得到。因为存在 x - x0 的项,很明显当 x = x0 的时候,可以得到如上的结论。

    到这里,我们需要进行一个猜测,这里的步骤有一点跳跃。就连课本上都没有详细的解释,没有详细解释的原因也很简单,因为需要用到积分的知识。而读者在这里是还没有接触过积分的,不过,我们不是严谨的论文,可以稍稍放松一些。其实根据上面的公式,我们是可以有些猜测的。根据上面的规律,以及我们的目标——证明这个 R(x) 函数是一个关于 (x-x0)^n 的无穷小,所以我们可以猜测它应该是一个与 (x - x0)^(n+1) 相关的函数。

    有了这个猜测之后,我们套用一下柯西中值定理:

    8d964617d63f9806feabbb8e169ae10a.png

    我们令 f(x)=R_n(x), F(x)=(x-x0)^(n+1),套用中值定理可以得到:

    b8a0373af9a3cf4ce722c0f404e04932.png

    有了这个结论之后,我们再对函数 R'_n(x) 和(n+1)(x-x0)^n 在区间 (x0, ξ1) 上再次应用柯西中值定理:

    fee3ab9450e7261d7df516675386cdbc.png

    接下来就是熟悉的套娃环节了,经过一共n+1次套娃之后,我们可以得到:

    211b5e467d7f74740c352c7adfdc37ac.png

    我们对 P_n(x) 求n+1次导数,可以得到0,因为所有项最多只有n次,求n+1次导数之后全部变成0。也就是说

    a3d3b8cb4d9b88ca838b9076f28e1708.png

    所以

    b3e5dd31a96b98b09aba8f81e644409e.png

    我们把这项代入上式,可以得到:

    c6523cf5e29216879ec3839b9a8acce8.png

    证明一下误差

    接下来我们要证明这个误差 R_n(x) 是 (x-x0)^n 的高阶无穷小。

    到这里,证明就很简单了,在固定的区间(a, b)中,很明显函数 f^(n+1)(x) 存在最大值,我们假设这个最大值是M。也就是说

    d577f657993d489c613980629c667425.png

    那么:

    9fa6cbfcdf357d7b68778aafc5ea6282.png

    由于x逼近 x0,M是一个常数,所以这个极限趋向于0,我们可以用极限的定义很容易证明。于是我们证明了,误差 R_n(x) 是比 (x-x0)^n 更高阶的无穷小。

    所以我们可以得到:

    ab7fc836823e928be85618da8d8ad62e.png

    由于我们一共用到了n阶导数来表达原函数,所以我们称为这是原函数f(x)的n阶泰勒展开。最后的

    R_n(x) ,我们称它为拉格朗日余项。我们也可以简写为 o[(x-x0)^n] ,它称为佩亚诺型余项,其实和拉格朗日余项是一回事,只是写的形式不同。

    我们如果令 x0 = 0 的话,还可以将式子进一步化简。由于 ξ 在0和x中间,所以我们可以令 ξ = θx,原公式可以写成:

    406554b5f7c416a10f752debf19a9293.png

    和上面的式子相比,这个式子要简单许多,它也有一个名字,叫做麦克劳林公式。在麦克劳林公式下的佩亚诺余项写成o(x^n),看起来非常简单。

    如果觉得上面的式子有点多记不过来可以忽略原式,只需要记住麦克劳林公式即可。对于拉格朗日余项,我们也只会在计算误差的时候用到,在不需要考虑误差的场景下也可以忽略。

    举例

    下面我们来看一个实际的例子,来感受一下泰勒公式的强大。

    我们都知道有一些函数的值我们很难直接计算,比如 f(x)=e^x,和正弦余弦函数等。由于e本身就是一个无理数,有没有想过我们怎么来求一个带e的函数值?其实很多时候,就是用的泰勒公式。

    我们就用f(x)=e^x 举例,看看怎么利用泰勒公式来计算。

    为了简化计算,我们显然考虑麦克劳林公式。由于 x=0 时,e^x=1,并且 f'(x)=e^x=1。

    所以我们可以得到:

    c06548d7859365a442c06c0bdfd90ec4.png

    我们代入泰勒公式,可以得到:

    40a287bc4b39fb960ccb482bae7e9f9f.png

    我们如果把最后一项当成误差,那么可以得到:

    3ca9d2f4566325c7c59ff80909d5b9e0.png

    当n=10时,x=1,产生的误差为:

    f98a411fa5c84f4bc713615c4e188613.png

    我们稍微算一下就可以知道,这个误差小于1e-6,已经足够接近了。也就是说我们把原本不太好计算的函数转化成了若干个多项式的和,可以非常简单地获得一个足够接近的近似值。并且除此之外,我们还能算出它的最大误差,实在是非常完美了。

    思考

    到这里还没有结束,看完所有的推导和计算之后,不知道你们有没有一个疑惑,这么一个牛叉并且复杂并且有用的公式,泰勒是怎么灵光一闪想到的?好像用一时的灵感很难解释。毕竟人的灵感往往都是一瞬间对某个点的顿悟,而这么多公式和结论是很难顿悟的。

    之前上学的时候我完全没有意识到这个问题,这次重温的时候才觉得不对。当然你可能会说这里有这么多数学家的名字,显然不是一个人的功劳。但即使是这样,我仍然好奇,究竟是什么起因引出了这么伟大的公式?

    直到我无意间看到知乎撒欢大神[2]的回答才恍然大悟。

    我们设想一个问题,如果f(x)=g(x),那么显然f(x)和g(x)的各阶导数全都相等。那么问题来了,如果我们人为地构造一个函数h(x),使得它的各阶导数和g(x)吻合,那么是不是可以认为这个我们人为构造出来的函数也和g(x)相等呢?

    然而有些函数的高阶导数是无穷无尽的,我们不可能人工全部拟合,所以只能退而求其次,拟合其中的n项。显然这样会有误差,那么我们需要知道误差的大小。于是就有了后面的拉格朗日余项大小的推算。

    泰勒公式的出现和推导过程正是基于这样的思路,想到这里,我又有了新的想法。如果把各阶导数的项看成是特征,那么这个问题其实转化成了机器学习当中的回归问题,只不过在机器学习当中我们是设定优化目标和优化方法,让模型自行训练来拟合逼近,而泰勒公式其实是通过思维和数学的力量推算出了结果,两者的目的和结果是一样的,但是过程完全迥异,两个看似完全风马牛不相及的问题殊途同归,不得不说数学的魅力真的令人折服。

    今天的文章就是这些,如果觉得有所收获,请顺手点个关注或者转发吧,你们的举手之劳对我来说很重要。

    参考资料

    [1]

    高等数学(上海交大第五版): https://book.douban.com/subject/2112359/

    [2]

    撒欢大神的回答: https://www.zhihu.com/question/20887356

    展开全文
  • Xgboost的理解和复习

    2019-10-09 16:10:19
    文本主要是Xgboost复习, 温故而知新,进一步理解Xgboost~ 原理-损失函数: 1、XGB损失函数同GBDT有什么区别 Xgboost正则化方法有哪些 前文中GBDT损失函数进行了一阶泰勒展开,轻松地知道下一棵树需要去...

    文本主要是对Xgboost的复习,温故而知新,进一步理解Xgboost~

    原理-损失函数:

    1、XGB的损失函数同GBDT有什么区别

    Xgboost正则化的方法有哪些

    前文中GBDT的损失函数进行了一阶泰勒展开,轻松地知道下一棵树需要去拟合损失函数的负梯度。而在Xgboost中,损失函数增加了正则项,增加正则项后下一棵树优化的目标是什么呢,接下来会针对这些问题进行理解分析。

    1、Xgboost的损失函数中增加了正则项

    • XGB目标函数中新增了正则项,正则项对每棵回归树的复杂度进行了惩罚,使得学习出来的模型更加不容易过拟合

    XGB中衡量树的复杂度公式为:

    Ω(f)=γT+12λw2 \Omega(f) = \gamma T + \frac{1}{2}\lambda||w||^2

    其中T为叶子结点的个数,w为叶结点的分数

    • 关于叶子结点的个数好理解,因为内部采用二叉树,叶子结点个数越多,说明树越深,模型越复杂
    • 但是关于叶结点分数这个刚开始有个疑惑,为啥要用叶结点分数做正则化呢?
    • 1、参考以下解读,发现以残差为例,模型最后是去拟合 ynsny_n-s_n, 这里 sns_n是上一轮学习器预测的结果,也就是叶子节点的分数!!!
    • 2、因为最后每个基学习器的叶子结点的得分要加起来,防止一棵树过于强大,所以增加了对叶子结点得分的正则,相当于L2正则
    • 所以对叶子节点的分数做了限制,是为了防止一个基学习器过于强大,占总学习器的主导,产生过拟合
      (参考理解:https://stats.stackexchange.com/questions/178012/definition-of-complexity-of-a-tree-in-xgboost)

    2、XGB的损失函数怎么进行推导,得到最终下一棵树的目标?

    推导过程见手写公式(二阶泰勒展开)

    3、回归树的学习策略(暴力枚举 -> 贪心)

    贪心法,每次尝试分裂一个叶节点,计算分裂前后的增益,选择增益最大的

    3-1、XGboost的打分函数

    3-2、树节点的分裂方法

    以二阶导数作为权重进行分位值划分

    理解:为什么以二阶导数作为权重进行划分?
    
    这块很神奇,在刚开始没有了解XGB的分裂方法时,我想的是单纯按照特征排序后样本数目的分位数进行划分。但是实际并不是这样,需要结合XGB的损失函数进行理解:

    参考:https://zhuanlan.zhihu.com/p/38297689

    数据角度-不同数据特点分析

    1、Xgboost对缺失值处理

    一图胜千言
    在这里插入图片描述

    2、Xgboost对高维稀疏特征(树模型适不适合高维稀疏特征)

    理解:极端情况下的完美划分

    Xgboost其他特性

    1、Xgboost采样方法(防止过拟合):

    • 行采样:Bagging,每次抽取部分样本进行训练。
      
    • 列采样:两种方式
      • colsample_bylevel: 按层随机,对同一层内每个结点分裂之前,先随机选择一部分特征,于是我们只需要遍历这部分的特征,来确定最优的分割点。
      • colsample_bytree: 按树随机,建树前就随机选择一部分特征,然后之后所有叶子结点的分裂都只使用这部分特征。
        

    2、Xgboost的Shrinkage = learning rate (防止过拟合)

    learning rate调小,有正则化的作用
    Shrinkage: 每个迭代中树中,对叶子结点乘以一个缩减权重eta。该操作的作用就是减少每颗树的影响力,留更多的空间给后来的树提升。

    3、支持自定义损失函数

    理解:从上文损失函数的优化中,下一棵树的优化目标同损失函数本身定义无关,同损失函数的二阶导有关。所以只要损失函数可以二阶泰勒展开,那么损失函数都可以当做XGB的损失函数。

    一些问题总结

    1、树模型不适合高维稀疏特征
    2、Xgboost正则化方法

    工程系统角度:

    1、更快:

    1-1、Column Block

    特征预排序:

    • 只需要在建树前排序一次,后面节点分裂时,直接根据索引得到梯度信息。可以加速Split finding的过程。
      在这里插入图片描述
    • block中的数据按照csc存储
    • Block 中特征还需存储指向样本的索引,这样才能根据特征的值来取梯度
    • 一个Block中存储一个或多个特征的值

    1-2、cache aware access

    • 在预排序后,特征对梯度的访问是一种随机访问,并且不同的特征访问的顺序不一样,降低CPU cache的命中率。
    • 缓存优化方法:对每个线程分配一个连续的buffer,预读梯度数据到buffer中(非连续 -> 连续), 再统计梯度信息。
      

    2、内存空间

    1-1、DMatrix优化

    XGBoost自定义了一个数据矩阵类DMatrix
    压缩存储空间:csr_matrix

    >>> indptr = np.array([0, 2, 3, 6])
    >>> indices = np.array([0, 2, 2, 0, 1, 2])
    >>> data = np.array([1, 2, 3, 4, 5, 6])
    >>> sparse.csr_matrix((data, indices, indptr), shape=(3, 3)).toarray()
    array([[1, 0, 2],
           [0, 0, 3],
           [4, 5, 6]])
    
    # 按row行来压缩
    # 对于第i行,非0数据列是indices[indptr[i]:indptr[i+1]] 数据是data[indptr[i]:indptr[i+1]]
    # 在本例中
    # 第0行,有非0的数据列是indices[indptr[0]:indptr[1]] = indices[0:2] = [0,2]
    # 数据是data[indptr[0]:indptr[1]] = data[0:2] = [1,2],所以在第0行第0列是1,第2列是2
    # 第1行,有非0的数据列是indices[indptr[1]:indptr[2]] = indices[2:3] = [2]
    # 数据是data[indptr[1]:indptr[2] = data[2:3] = [3],所以在第1行第2列是3
    # 第2行,有非0的数据列是indices[indptr[2]:indptr[3]] = indices[3:6] = [0,1,2]
    # 数据是data[indptr[2]:indptr[3]] = data[3:6] = [4,5,6],所以在第2行第0列是4,第1列是5,第2列是6
    

    csr_matrix和csc_matrix的区别

    • csr_matrix 在行切片很高效,比如取第N行的数据
    • csc_matrix 在列切片很搞笑,比如取第N列的数据

    1-2、Xgboost实现并行化

    • Xgboost的并行并不是tree粒度上的并行
    • xgboost的并行是在特征粒度上的,Xgboost对数据进行了预排序,然后保存为block结构
    • 这个block结构也使得并行成为了可能,在进行节点的分裂时,需要计算每个特征的增益,最终选增益最大的那个特征去做分裂,那么各个特征的增益计算就可以开多线程进行

    其他问题

    1、Xgboost和GBDT的不同

    • 直观学习层面:
      • 行列采样
      • 传统GBDT是CART树,XGboost支持线性分类器
    • 损失函数层面:泰勒展开+正则化
    • 特殊值的处理:缺失值
    • 工程上的优化:
      • 特征的预排序,结点分裂时计算每个特征的增益并行化
      • 数据压缩:csr、csc、DMatrix

    2、Xgboost防止过拟合的方法

    • 损失函数的正则项:叶子结点的个数+叶子结点的分数
    • 行列采样
    • 学习率Shrinkage
    • EarlyStopping:根据验证集的情况,提前停止

    参考资料

    https://www.displayr.com/how-is-splitting-decided-for-decision-trees/

    https://www.jianshu.com/p/c558d0448ac7

    https://zhuanlan.zhihu.com/p/38297689

    展开全文
  • XGBoost基本原理

    千次阅读 2018-08-14 21:44:27
    XGBoost实现,我觉得主要还是在于GBDT改良上。对于GBDT还是不太熟悉朋友,请看我这一篇文章《GBDT》。我个人认为这两者区别主要还是在于细节上,理解了GBDT我认为就差不多等于理解了XGBoost。 我重点比较...

    XGBoost的实现,我觉得主要还是在于对GBDT的改良上。对于GBDT还是不太熟悉的朋友,请看我这一篇文章《GBDT》。我个人认为这两者区别主要还是在于细节上,理解了GBDT我认为就差不多等于理解了XGBoost。

    我重点比较一下XGBoost与GBDT两种算法的不同:

    XGBoost的目标函数与GBDT存在泰勒展开项的不同:

    最基本的差距就在于XGBoost比GBDT多了两项泰勒展开式。具体这个泰勒展开式是怎么得到的,是对于什么展开的呢?我们看:
    XGBoost算法可以看成是由K棵树组成的加法模型:

     

    XGBoost加法模型

    XGBoost加法模型

     

    其中F为所有树组成的函数空间(这里的回归树也就是一个分段函数,不同分段的不同取值就构成了一颗树),与一般机器学习算法不同的是,加法模型不是学习d维空间的权重,而是直接学习决策树的集合。
    上述加法模型的目标函数定义为:

     

    目标函数

    目标函数

     

    其中Ω表示决策树的复杂度,那么该如何定义树的复杂度呢?比如,可以考虑树的节点数量、树的深度或者叶子节点所对应的分数的L2范数等等。
    如何来学习加法模型呢?
    解这一优化问题,可以用前向分布算法(forward stagewise algorithm)。有了之前GBDT的基础,我们知道,加法模型的学习器每次都用函数来拟合上一棵树没有拟合完整的残差,最后将这些残差全部加起来就会得到对于目标完整的预测,这也叫做Boosting。具体地,我们从一个常量预测开始,每次学习一个新的函数,过程如下:

    加法学习器的Boosting

    加法学习器的Boosting

     

    这个公式看起来还是比较拗口,想要理解的话建议看我之前的文章《GBDT》,了解了工作模式这公式就好理解了。

    这就会产生一个新的问题,那个新加入的函数f到底怎么得到的呢?这个原则还是最小化目标函数。我们可以将我们的目标函数写为:

     

    目标函数变式

    目标函数变式

     

    我们再用平方误差来衡量我们的损失函数:

     

    平方误差衡量损失函数

    平方误差衡量损失函数

     

    其中 就是我们所谓的残差(residual)。我们每一次使用平方函数的时候,算法都是为了拟合这个残差。
    可能有的朋友对于泰勒公式不是非常熟悉,我将基本的泰勒公式用法写在这:

     

    泰勒公式基本形式

    泰勒公式基本形式

     

    我们都知道,泰勒级数展开其实是有无穷多项的,在无穷多项形式里是严格等于,这里我们暂且只取了前三项省略了后面,所以就是约等于。
    那有了泰勒公式的基础,我们将前面的目标函数变式可以转化为:

     

    目标函数泰勒级数展开三项

    目标函数泰勒级数展开三项

     

    其中,g与h分别是损失函数的一阶偏导数和二阶偏导数,具体数学形式如下:

     

    泰勒展开的一次微分项与二次微分项

    泰勒展开的一次微分项与二次微分项

     

    我们也可以将常数项直接去掉,并不会影响,那就使得目标函数是这个样子:

     

    去掉常数项的目标函数

    去掉常数项的目标函数

     

    由于要学习的函数仅仅依赖于目标函数,从“去掉常数项的目标函数”可以看出只需为学习任务定义好损失函数,并为每个训练样本计算出损失函数的一阶导数和二阶导数,通过在训练样本集上最小化目标函数即可求得每步要学习的函数,从而根据加法模型可得最终要学习的模型。

     

    GBDT的目标函数

    GBDT的目标函数

     

    就简单提一句GBDT与XGBoost的区别,明显可以看出,GBDT没有采用二次泰勒展开,这个看似很简单的区别,实际上带来更快的拟合,也大大缩减了生成树的规模,减少了运行时间。

    XGBoost相比于GBDT加入了正则化项(Regularization)

    我们使用损失函数优化是为了避免欠拟合,而使用正则化项就是为了避免过拟合。正则化项与损失函数共同组成了我们的目标函数。XGBoost比GBDT多添加了以树复杂度构成的正则化项,也是XGBoost实际表现更为优秀的原因之一

    何为正则化项?正则化项的作用是什么?
    我们都知道,我们在优化目标函数的时候,总是希望它更加的“小”,也就是优化一般是最小化的意思。现在我们如果给目标函数加入一个变量的平方,那么如果这个变量一旦变大,那么目标函数为了“最小化”,一定很不喜欢这个变量变大的事实,选择的时候就会刻意避开会使变量变大的路径。这大概就是正则化的简单解释了。在XGBoost中,我们是将树的复杂度作为正则项加入,那么优化器在工作的时候,会尽量不让这个树更加复杂,也就达到我们的效果。

    我们假设XGBoost决策树的叶子节点个数为T,该决策树是由所有叶子节点对应的值组成的向量w,以及一个把特征向量映射到叶子节点索引(Index)的函数 组成的,我们将树可以写成:
    ,我们也可以将决策树的复杂度定义成正则项:

     

    决策树复杂度定义的正则化项

    决策树复杂度定义的正则化项

     

    则目标函数我们可以写成:

    完整正则项的目标函数

    完整正则项的目标函数

     

    用G与H代换一下原来的式子,我们就得到了简化后的式子:

     

    简化后的目标函数

    简化后的目标函数

     

    假设树的结构是固定的,即函数q(x)为固定的,令目标函数的一阶导数为0,则可以求出叶子节点j对应的值为:

     

    叶子节点j对应的值

    叶子节点j对应的值

     

    于是在这种条件下,目标函数的值就变成了:

    目标函数的值

    目标函数的值

     

    为什么要计算这两个值呢?
    是为了给大家描述单棵决策树的生成过程:

    1. 枚举所有可能的树的结构q
    2. 用目标函数值为每个q计算对应的分数Obj,分数越小说明结构越好
    3. 根据上一步结果,找到分数最小的子节点,生成新的分支,并为每个子节点计算预测值

    XGBoost的分裂增益与GBDT的比较

    树结构数量是无穷的,所以实际上我们不可能枚举所有可能的树结构。通常情况下,我们采用贪心策略来生成决策树的每个节点。

    我们来看看这个贪心算法是怎么工作的:

    1. 从深度为0的树开始,对每个叶节点枚举所有的可用特征
    2. 针对每个特征,把属于该节点的训练样本根据该特征值升序排列,通过线性扫描的方式来决定该特征的最佳分裂点,并记录该特征的最大收益(采用最佳分裂点时的收益)
    3. 选择收益最大的特征作为分裂特征,用该特征的最佳分裂点作为分裂位置,把该节点生长出左右两个新的叶节点,并为每个新节点关联对应的样本集
    4. 回到第1步,递归执行到满足特定条件为止

    如何计算每次分裂的收益呢?假设当前节点记为C,分裂之后左孩子节点记为L,右孩子节点记为R,则该分裂获得的收益定义为当前节点的目标函数值减去左右两个孩子节点的目标函数值之和:Gain=ObjC-ObjL-ObjR,具体地,根据目标函数值公式可得:

    XGBoost的增益

    XGBoost的增益


    作者:香橙云子
    链接:https://juejin.im/post/5a13c9a8f265da43333e0648
    来源:掘金
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    转载:https://juejin.im/post/5a13c9a8f265da43333e0648

    展开全文
  • XGBoost本质上还是一个GBDT,但是速度和效率发挥到...在损失函数求解时进行了二阶泰勒展开,而且XGBoost块结构可以很好支持并行计算。一,原理理解1.1,目标函数相比GBDT,Xgboost考虑了树复杂度来防止模型...
  • 学习笔记:XGBoost原理解析

    千次阅读 2017-09-19 10:54:56
    要想理解的原理XGBoost,就要GBDT,CART很熟悉,XGBoost的原理还是很新颖,XGBoost用了泰勒展开式,求二阶导数,推导过程并不难,就是式子很难写,我在关键地方都标注了详细解析,如果有不懂地方,请...
  • XGBoost实现,我觉得主要还是在于GBDT改良上。对于GBDT还是不太熟悉朋友,请看我这一篇文章《GBDT》。我个人认为这两者区别主要还是在于细节上,理解了GBDT我认为就差不多等于理解了XGBoost。我重点比较一下...
  • 【首先需要声明的是,这里面不少是我自己的理解,供参考;如果错了请指正】 文章目录1.纵向LR的损失函数2.损失函数展开成多项式2.1 用到的泰勒展开式2.2 原损失函数展开并计算梯度3.关于同态加密4.纵向LR整体流程5....
  • 概述 是一种基于图像灰度方法通过计算点曲率和梯度来检测角点。 基本原理 如果在各个方向上移动窗口,窗口中灰度值都会发生较大变化,那么认定在...其中后面那一项进行泰勒展开 写成自相关函数(二次型)形
  • XGBOOST学习过程

    2018-10-29 17:45:03
    1、XGBOOST入门原理 https://blog.csdn.net/github_38414650/article/details/76061893 2、XGBOOST公式推导 https://blog.csdn.net/guoxinian/article/details/79243307 重点是对泰勒展开的理解 ...

空空如也

空空如也

1 2 3 4 5
收藏数 83
精华内容 33
关键字:

对泰勒原理的理解