Categories
读书有感

≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记(十五)

梯度树提升算法(GTBA, gradient tree boosting algorithm)

继续boosting类算法哎。小小预告一下,下节课会直接跳到随机森林,老师貌似是想把各种分类器都一下子讲到,然后有点前后照应的比较~真有意思,若是以前扔给我这种问题我肯定run一个logit regression就不管了,现在倒是有各种线性的、广义线性的、非线性的模型可以试着玩了,爽哎~

------------------

1. 自适应基函数模型

小小的复习一下上节课那个框架。

1. 数据。

2. 模型。 为基函数模型,其中成为基函数集合。为参数。

3. 损失函数(准则)。 为损失函数,然后就转为一个优化问题:

4. 算法。 前向分步算法。

  • 初始化:
  • 迭代:For m=1 to M,
  • 输出

在此框架之下,除了上节课的Adaboost之外,还可以套用多种其他的基函数,然后1)定义损失函数 2)给出迭代那一步的优化算法,就可以实现一种boost提升算法了。

2. 应用回归问题

先采用均方误差的损失函数,定义,这样就可以得到

然后定义:

。这里之后用回归树来求的话,就是梯度回归树算法。

梯度回归树提升算法

  • 初始化:
  • 迭代:For m=1 to M,计算。由用回归树求得.
  • 输出

3. GTBA,梯度树提升算法

先吹捧一下:这个算法就是此书作者本人开发的,然后已经搞出来了软件包,可以做回归也可以做分类,貌似效果还胜过随机森林(当然是作者自己给出的那些例子...)。

损失函数为可微的。

我们的优化目标是,也就是说实际上我们不是直接对进行优化,而是仅仅在所有观测的数据点上优化,所以仅跟在这些观测点上的值有关。感觉这里就是说,我们使用有限的观测到的信息来推断一个连续的函数,然后类推并用于其他未观测到的点。

定义:

,这样这个问题就从一个直接优化的泛函问题转化为一个优化多元函数的问题...而对于一个多元函数,我们可以直接用梯度下降法。定义梯度为:

,这样。类似的,我们可以定义,其中。累加起来,就是

,这里可以是常量也可以随着改变。

定义完梯度下降之后,就是GTBA算法了。

  • 初始化。
  • 迭代:For m=1 to M,计算,然后由用回归树求得
  • 输出

一些梳理

1. 参数。这里显然有如下参数需要设定:

  • M:迭代次数。这是这个算法最主要的参数,需要用Cross-validation来算。
  • J:树的大小。建议4-8,默认为6。
  • :收缩系数。这里可以加上这个参数,决定收缩的速度,0-1之间。
  • :次采样率,0-1直接,默认0.5。用于做subsampling。

2. 特征变量评价

这个算法的一大优势就是可以给出各个自变量的评价。比如的时候我们可能面临特征变量选择问题。

用t表示树中的节点,表示t节点所用的变量,表示t节点产生的均方误差的减小值。之后定义:

,可用这个值来刻画变量的重要性,从而进行特征评价。

3. 通用工具

该算法对于数据无特殊要求,有一批都可以扔进去试试,故可以作为其他算法的benchmark。

此外,从贝叶斯分类器的角度,我们要找的是,这样除了原有可以观测到的之上,还可以衍生出一个向量,即,第k个位置为1如果观测到的对应第k类。一下子就可以扩展整个数据集,也可以进一步对每类都赋一个概率,不单单是0-1这样。

Categories
读书有感

≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记(十四)

开春,复课。

一句无关的话...今天打开Google Reader看到7月份要关的提示,无限悲伤。看着落园若干RSS源里面累计800+的读者,只能说句bless...2008年开始使用,到现在,伴我度过了多少读书时光呀。不过确实也衰落了,高峰的时候一个RSS源就有600+读者,现在也只剩一半了。写博客,越来越像一件出力不讨好的事情了。

--------正文开始---------

提升与梯度树

1. Boost(AdaBoost)

这里讲的AdaBoost是仅针对二类分类器的提升。大致的思想就是,给我一个弱分类器,还你一个强分类器。听起来蛮神奇的对不对?

先说算法实现。

第一步:初始化。,权重初始值

第二步:迭代。

for m = 1 to M

  • 根据已有算法(即弱分类器)和{}得到一个分类器.
  • 计算误差:,这里我们把权重进行归一化。
  • 计算权重:
  • 修改样本权重

也就是说,我们不断的生成新的权重,当分类器分错的时候更改权重。

第三步:输出。最终的分类器为前面的加权。

这样就实现了从一个弱分类器改善到一个强分类器。这里弱分类器是指误差比随机猜的1/2少一点。

另注:在修改权重那一步的时候,也可以定义,然后,这样在最后的时候也可以改成。总之这里的直觉是,如果分对了,那么权重下降;反之,分错的时候这些样本的权重上升。最后take average就可以了。

2. 自适应基函数模型、前向分布算法

之所以上面又引入,便是为了更好地理解这一类模型:自适应基函数模型。

1. 我们称 为基函数模型,其中成为基函数基。注意这里和GLM有很大的不同,广义线性模型后面的为确定的。

2. 前向分步算法。

数据集记作。定义一个损失函数,比如常见的均方误差,

,或者0-1准则。

然后步骤为:

  • 初始化:
  • 迭代:For m=1 to M,
  • 输出

这样我们就把这个最优化问题转变成了M步,每步只做一个参数的最优化(近似方法)。

3. 指数损失函数与AdaBoost

有了这么一个一般性的框架,我们就可以套用具体的形式。

1. 定义指数损失函数:

2. 两类分类、指数损失函数的自适应基函数模型。

前向分布算法:

(i)

定义

这样上式就可以化作

(ii) 固定,优化.

然后最小化,则。假定已被优化,然后继续。

(iii)优化

取一阶条件FOC,则有

这样最后

这样就看出来上面那个AdaBoost里面的是怎么来的了吧?

(iv) 回到AdaBoost

看出来最后的AdaBoost雏形了吧?