注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

行走的馒头

Stay Hungry, Stay Foolish

 
 
 

日志

 
 

七、Additive Models and Trees  

2012-09-09 21:59:50|  分类: 统计学习初探索 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

这里我们讨论某一类特定的supervised learning的方法,他们都把自变量空间分割成一些结构化的小区域,然后在这些小区域上去拟合数据,这在一定程度上缓解了curse of dimensionality的问题。

 

Generalized Additive Models

Linear regression在数据分析中可以说占据了半壁江山,无论是预测连续的值还是处理分类问题,其都可以有不错的表现。从前面的讨论我们可以看到,很多的方法其实都可以从linear regression的角度去看待。然而我们知道,在实际应用中,很多时候因变量和自变量间并不是简单的线性关系,这时我们可以用generalized additive models去刻画,在regression中,其可以表示为

其中对应于自变量X的每一维特征。是不特定的smoothing函数,换言之,也就是一些非参数函数(比如前面提到的cubic spline, kernel smoother等等)。如果我们能够把看做是一系列的Basis Expansion,我们就可以用前面讨论的最小二乘去解这个问题,此时可以从另外一个角度来解这个问题。

对于二分类问题,,像在logistic regression中一样,我们可以通过下面的式子来表示additive logistic regression。

    广而言之,用,我们可以通过link function 来扩展regression定义的generalized additive model。其可以表示为

  1. 叫做identity link,被用来刻画线性additive模型下产生的高斯响应数据
  2. 被用来刻画二分类问题。
  3. 被用来刻画泊松问题。

    上面的所有这些问题其实都属于exponential family models,除上面这些之外还包括gamma分布,负二项式分布等等。如果数据产生于exponential family distribution,其实都可以用前面稍微提到过的广义线性模型去刻画,当然也都可以推广到generalized additive model。

    注意在generalized additive model中,不必每一个都是非线性的,线性和非线性可以交织在一起,当然除了连续特征,也可以包含离散的特征。对于离散的特征,我们甚至可以对其取值空间上的每一个值刻画一个对应的

 

Fitting Additive Models

    Generalized additive model也可以写成下面的形式

其中是高斯误差。使用squared error和前面讨论过的regularization,目标函数可表示如下

这里被称之为tuning parameter。正如前面Spline中讨论过的类似,上面的式子其实是对一个addtive cubic spline 模型,是关于特征的cubic spline,并且在每个都有一个结点(knot)。可以看到,这里的的解并不唯一,因为我们对每个都添加或者减少一个常数,而只需要对应的减少或者增加一个常数而已。通常的作法是使。这时可以看到。此外如果我们的样本矩阵是列满秩,那么上面的是就是一个凸函数,存在全局唯一最优解。

    Generalized additive model可以使用backfitting算法来求解,其表示如下

  1. 初始化
  2. For 

        

  3.  ,重复Step 2直至收敛

先来看看 是什么。在第二步中拟合  之前,此时在除第维以外的其他每一维特征上,拟合出来的结果可表示为 ,这时第i个样本点处的真实值 和用除第维以外的其他特征拟合的预测值之差叫做此时在第i样本点处的残差,这时 就是要对现在的残差数据集 用某种Smooth的方法进行拟合,比如可以使用cubic spline或者kernel smoother等等,可以看出这个拟合是针对第j维特征的。然后我们用拟合出来的模型去更新 。 是为了让 。最后,收敛的标准可以是,在迭代中每一维拟合的 都基本保持不变。

可以看到,用backfitting 算法来求解generalized additive model是非常简单和有效地,GAM在实际中很受统计学家的欢迎,因为我们可以在特征空间的每一维度都各有自己的特点,我们可以使用不同的方法去拟合不同的维度。

 

 

Tree-Based Methods

    Tree-based methods 把整个特征空间划分为较小的矩形区域,然后在每个矩形区域内做regression或者分类。这类方法非常简单,高效,并且易于理解。

 

Regression Trees

    在Tree-based methods中,我们构建的Tree都是二分树,可以想象,这棵树的这些叶节点把整个特征空间划分为一些不相交的矩形区域,每个叶节点对应一个特定的区域。现在假设这棵树把特征空间划分为M个区域 。我们的模型在每个区域上拟合一个常量值 。那这个模型可以表示为

如果使用squared error,那么我们的目标是使残差平方和最小,即 。这时容易看出在每个区域 上拟合的常量值为

    假设我们的特征空间为 。现在来看看我们怎么来构建这棵树。要找到使满足的那颗最优树是非常困难的,需要尝试从根节点开始的各种可能的划分,在实际应用中这在计算上是不可行的。这时我们需要启发式的算法。首先,我们从根节点开始讨论怎么从上往下构建这棵树。明显,根节点是整个特征空间,然后我们需要在根节点处划分。假设表示X的一个特征,表示在这个特征上的某个取值。这样如果在上的处划分,在根节点处就把特征空间划分为

此时我们要找的 要满足下面的条件。

因为对于任意的一个 ,我们容易得到

因此,对于每个特征,我们就非常容易通过上面的标准找到是其最小的划分点。然后我们再从中找到使标准最小的作为我们在根节点处的划分。然后把数据集对应的放入划分的这两个子节点。然后在这些子节点处递归的进行如上的操作。

    现在问题来了,我们构建的树究竟应该多大。如果树很小的话,那么不能够很好的反应我们特征空间的结构性质,如果树很大的话,容易产生overfitting。树的大小Tree Size可以作为一个tuning parameter,来控制模型的复杂度。一般采用的方法是先构建一个足够复杂的很大的树,构建这棵树时停止的标准可以是比如所有叶节点中样本的数目都小于等于5。然后我们可以使用cost-complexity pruning的方法来进行裁枝。设是可以通过对 进行裁枝的任意一颗子树。假设中的叶节点表示为m,表示其对应的区域, 表示叶节点的数目。那么

我们的目标函数可以定义如下

对于每个特定的,我们的目标是找到对应 使得 最小。可以看出,tuning parameter 控制着tree size和拟合效果的tradeoff。当 很大的时候,这个标准倾向于选择较小的树,反之亦然。当时,选择的就是本身。对于每个特定的,我们使用weakest-link pruning来找到最优的子树。我们在树中选择移除一个中间结点,在移除这个中间结点后得到新的树,我们要选择的中间结点要满足使得 最小。然后依次的移除中间结点直至只剩下根节点。这样就产生了一个序列 ,而我们的最优子树就在这个序列中。只需比较这个序列中每个元素值,找出最小的那个即为我们的最有子树。对于的选择,我们可以使用cross validation的方法。

 

Classification Trees

    对于分类问题,我们使用classification trees。其跟regression trees不同之处在于构建树时分裂和裁剪树时的损失函数标准有点不同而已。对于每个结点m,其区域为 ,其中的样本集为 ,那么这个结点处第k类样本的比例为

在每个叶节点m处,我们的模型对这个结点处的样本的预测label为

正如在regression trees中使用squared error,在Classification Trees中,常用的损失函数有以下三种

    下面是二分类问题时,三种损失的一个示意图。可以看出cross-entroy和Gini指数比较平滑一点,都是可导的,计算起来更加容易。并且它们都在missclassification error曲线的上面,它们对节点中类的不纯度也更加敏感。

 

Other Issues

    当我们构建树时,如果分裂时的某个特征是离散变量,它拥有个unordered的值。这时把其划分为两个空间共有 钟可能性,我们要从中挑选出使选择的标准最小的那种划分。如果非常大,可以看到这在计算上是难以实现的。在二分类时,处理这种问题我们有一种比较tricky的方法。我们把的每个离散值 进行排序,使得,其中 。然后我们就把这些离散的unordered值当做是ordered的值,可以把他们映射到实数上,就相当于特征是连续的情况,找到最佳的分裂点然后再回到离散情况时对应的值。在使用cross-entroy或者Gini index时,大牛们已经证明了这种tricky的方法找到的就是遍历 种可能性所能找到的最优划分。在regression trees中,使用squared error,上面的结论也是成立的。

    树的构建过程倾向于选择那些很大的离散特征,这样会带来比较严重的overfitting,应该尽量避免使用这样的特征。

    如果把A类误分到B类和把B类误分到A类不一样,则损失函数就需要稍作修改。推而广之,我们可以定义误分类矩阵 表示把第i类误分到第j类上的损失,其中 。这时Gini index就可以修改为,在叶节点处我们的预测分类就可以修改为。

    为什么不建立三叉树、四叉树、n叉树呢?构建三叉以上的树,使得树在开始的时候分裂的非常快,使得子节点中的数据非常稀疏,不足以进行以后的分裂。而且n叉树能够实现的数据划分方式二分树都能够实现。

    Tree methods的一个主要缺点就是overfitting,拥有很高的variance。我们可以使用model average中的Bagging等方法来减小variance。

 

 

PRIM: Bump Hunting

    Bump hunting就是在特种空间中寻找某块区域,这块区域能够使我们设定的某项标准尽可能的大。这些区域也是通过一些规则来划分的。举个例子,一个银行在考虑贷款业务时,肯定希望借款人的违约风险低,会拒绝那些有很高违约风险的申请者。我们假设违约分风险跟age, income,occupation等都有关系。银行现在有一批历史数据,记录了以前借款者信息,包括他们的age等特征和是否违约的信息。此时银行的目标就是在特征空间中找到某一块区域,使得违约的风险尽量的小。如果用0表示借款者违约了,1表示没有违约。那么我们所要找的区域就是要使里面值的平均值尽量的大。

Tree methods是把特征空间划分成很多的矩形区域,然后在每个区域中拟合模型和做预测。类似的,patient rule induction method (PRIM)也是在特征空间中寻找矩形区域,但是策略有所不同。PRIM是寻找在某种标准下值最大的那个区域。不像Tree methods通过二叉树来划分区域,PRIM非常耐心的来划分区域,算法可表示如下

  1. 用一个maximal box包含所有的训练数据
  2. 类似于树的分裂,对于每一维特征 ,我们选择使box lowest value处向右收缩一点比例 ,或者在highest value处向左收缩一点比例。我们要选择的收缩是使得收缩后的box中样本因变量的平均值最大。注意每次只在一个维度上收缩。通常 
  3. 不断的重复step 2,直至收敛,收敛的标准可以是box中样本点的数目少于一定数目(比如10)。
  4. 对这个box向任何一个方向进行扩张,只要扩展后会使得平均值增加。
  5. 在步骤1-4中产生了一系列的boxes, 一个自然的想法就是选择平均值最大的那个box。但是这样容易出现overfitting的情况。而且当数据非常稀疏的时候,容易选择很小的一个box,其中可能就只有几个具有较高值的样本点。这时可以用cross validation的方法把数据分成train datatest data, train data产生前面的一系列boxes, 然后用test data产生平均值最大的那个box  
  6. 移除训练集中在 中的数据,然后重复step 2-5不断的产生新的box直至能够覆盖特征空间。

相比于Tree methods,PRIM的优点就是耐心。正如师爷所说,步子迈的太大了容易扯着蛋。tree通过二分把空间切分的非常快,容易使后面的结点不足以表现出很强的规律性。

 

 

Multivariate Adaptive Regression Splines

MARS 是统计学习大牛Jerome Friedman开创的一种回归分析技术,可以认为是linear regression的扩展。它是一种非参数的adaptive的方法,因为他使用的基变换是我们前面称之为linear spline的hinge函数,并且可以在学习过程中自动发现特征的非线性关系和特征间的关系。

Hinge函数其实就是linear piecewise函数,下面是一组对称的hinge函数。

示意图如下

对于上面这种对称的hinge函数,其中被称作是knot。在下面的讨论中,我们称这两个hinge函数为一个reflected pair。现在我们构建一个基函数的集合,其表示如下

可以看到,如果样本矩阵在每一列上元素都各不相同,那么中共有个基函数。

下面我们来看看MARS的算法,其分为两步走,第一步类似于linear regression中的forward stepwise的过程,表示如下

  1. 最开始集合 , 表示我们模型会用到的基函数。这时我们的模型表示为 ,显然,这时用训练数据集拟合处的参数为 。此时 。
  2. {

        

    {

        

             ;

            

             对使用最小二乘得到的残差平方和。

            

    {

                 ;

    }

    }

    }

  3. 重复step 2直至收敛或者 。这里收敛的定义可以使每次最终计算的 都非常小,说明此时继续增加基函数使拟合的效果增加不明显。

可以看到,MARS里面使用的基函数会存在两个hinge函数相乘的情况,下面是一个示意图,其中 。

可以看出hinge函数相当于Tree methods中划分空间,几个hinge函数相乘相当于不断的划分,只是这里MARS用的是一种additive的策略。

MARS的forward过程往往会构建一个overfit的模型,我们需要对模型进行一些裁剪。这时类似于linear regression中的backard stepwise过程,我们需要每次从基函数集合中丢弃掉一个基函数,使得在某种标准下损失最小或者收益最大。逐渐的丢弃直至中基函数的个数小于某个阈值或者继续丢弃任何一个基函数都会带来较大的损失。这里我们采用的标准是generalized cross validation,类似于cross validation和AIC、BIC等,它是一种用training error估计test error的标准。GCV可表示如下

 ,其中RSS用训练数据计算的残差平方和, 是指有效的参数个数,可表示为 ,通常 。注意这里 惩罚的是基函数的个数, 惩罚的是knot的个数。

可以看出,MARS通过使用hinge函数,只在那些特征空间中因变量不为0的区域增加基函数,这样一来在迭代过程中参数就增长的非常缓慢,实用于在高维空间中建模。这也是为什么要用MARS而不是直接把中全部hinge函数当做基函数然后用最小二乘来求解。

MARS也可以处理分类问题。对于二分类问题,我们可以简单把把其映射到0/1上面做regression。对于多分类问题也可以像用linear regression做分类那样来做。

可以看出MARS和Tree Methods都是都是属于贪婪式的扩张算法。通过对MARS进行一些变换,比如使用 而不是hinge函数,我们可以看到其可以转化为Tree methods。

 

 

    Hierarchical Mixtures of Experts

在前面讨论的决策树中,我们在划分特征空间的时候,是逐渐的把其划分成较小的区域,然后把样本数据放入对应的区域,这里给样本分配区域的时候,是一种hard的分配方式,因为对于一个父区域划分出来的两个不相交的子区域,父区域中的每个数据只能选择放入其中的一个子区域。如果我们每次给数据分配区域的时候木有那么肯定,我们可以引入probability,这时称之为soft分配。通过使用soft的分配方式,相比于Cart等树方法,我们可以提高模型拟合的效果,预测值的精度等,然而HME不如Cart易于理解,模型本身的解释性不强,可以像neural network一样看做是一个黑盒子。

HEM和决策树相比细节处还存在一些不同,比如在叶节点处决策树一般用其中样本点的平均值去拟合,而HEM一般都是用linear regression或者logistic regression去拟合。而且HEM在层次构建的时候,分裂的方式不一定是二分的,可以是多分的。

下面是一个具有两层结构的HEM的示意图。其中的叶节点叫做experts,中间结点叫做gating networks。因在在每个叶节点处都相当于有一个专家提供了一些参考意见,然后通过中间结点把这些意见综合起来考虑。可以看出这是一种mixture模型。

Figure(7.1)

下面来看看这个两层的HEM是怎样model的。首先,在最上层的gating network处,我们使用类似多分类的logistic regression。

这里是参数,  表示把样本分给第个子gating network的概率。图(7.1)对应着,这是就相当于二分类的logistic regression。

在第二层上,这些gating networks的soft分配可类似表示

在每个expert处,我们有 。如果是regression,我们可以使用gaussian linear regression,其中 , 。如果是二分类问题,可以使用 。所以这里我们的参数空间为

所以最终模型可以表示为

这时,我们得到似然函数,对似然函数求最大值。显然这个函数非常复杂,无法直接求解,这是我们可以使用前面讨论过的EM算法来求解。这里的隐变量是第一层处选择的子区域 和第二层处选择的expert 。相比于决策树要找出最优树是一个组合优化的问题,HEM使用似然函数来求解一个数值优化问题则容易得多。


  评论这张
 
阅读(5191)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017