Tag: 回归树

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

Post author By Liyun
Post date March 23, 2013
3 Comments on ≪统计学习精要(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这样。

Tags boost, boosting, GTBA, 分类器, 前向分步算法, 回归树, 基函数, 广义线性模型, 损失函数, 提升, 梯度, 梯度下降, 梯度树提升算法, 统计学习, 统计学习精要, 自适应基函数模型, 贝叶斯分类器

读书有感

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

Post author By Liyun
Post date January 13, 2013
3 Comments on ≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记（十三）

本学期最后一堂课的笔记...就这样，每周上班的时候都没有惦念的了，我是有多么喜欢教室和课堂呀。或者说，真的是太习惯学校的生活方式了吧...

这一节主要是在上一节的基础上，介绍一些可加模型或者树模型的相关（改进）方法。

MARS

MARS全称为Multivarible Adaptive Regression Splines，看名字就能猜出来大致他是做啥的。MARS这家伙与CART一脉相承（话说CART的竞争对手就是大名鼎鼎的C4.5）。不过，还是先说一下MARS到底是怎么玩的吧。

数据集依旧记作，然后就是splines的思想：我们定义，其中和，画出图形来就是:

这样就可以定义I函数了：，以及，越来越有spines味道了是不是？

之后就是定义f函数：，然后有意思的就来了：是中函数或者几个函数的乘积，选定了之后我们就可以用最小二乘法来求解相应的了。然后在接下来的每一步，我们都添加这样，一步步的，就开始增长。当我们用完了之后，显然有

over-fit的嫌疑，所以开始逐步的减少一些——考虑移除那些对减少残差平方和贡献比较小的项目。沿着cross-validation的思路，就可以定义函数。

PRIM

PRIM的全称为Patient Rule Induction Method，呃看名字貌似是一种比较耐心的一步步递归的方法。果不其然，最开始就是我们要先定义“削皮”：选取区间内任意的，比如0.1，然后开始削皮～削皮的策略大概就是，选定一个维度，去掉这个维度比如最大10\%或者最小10\%的样本，然后看剩余部分的y均值有没有增长。总共有p个维度，所以我们有中削皮法。选择其中上升最高的方法，削皮。然后继续来一遍，直到不能再增长的时候，停止，最终得到一块“精华”（贪心的算法）。之后，我们又要开始粘贴，即再贴上去一块儿，看看是否能涨。这样我们得到一个区，区域均值为。

从总体中扔掉这区中的样本，然后继续做下去，比如一共J次，得到J个区域（这些区域的空间可能是有交集的），这样的策略称为Bump-Hunting（肿块寻找），最终得到若干个区域，各区域中的样本均值作为（以第一次出现的空间为准）。

HME

HME的全称为Hierarchical Mixture of Experts，听起来像是一个智囊团的感觉。画出来呢，就是一个树的形状。

大致的思想就是，以概率分配到各个枝条（软分类器），这样有。对于最下面一层的expert

net，可以用分类树或者其他任何的分类器。对于HME，可用EM算法来解。两类的情形，就有，有点像logit的变形有没有？

一句话的总结呢，就是这些方法看上去合理，比较容易follow the intuition，但是树类的结构弄得很难用现有的方法证明原理和一些相关性质（完全非线性呀）。

模型的总结：广义线性模型和基函数模型

从第一章到第九章，我们探索了很多个模型。说到底，模型就是，然后我们有参数模型，其中，。

最简单的来说，就是线性模型，形式为，其中。显然，线性模型便是参数模型。

然后就是广义线性模型（GLM），我们可以先扩张x，就有。说到底，就是已知的把数据从空间映射到一个新的空间。然后还可以把y再广义化，用一个可逆的已知函数变成。这样，就有，最终说来和这两个空间实现了一种线性的映射关系。

接下来我们就会看到一种形状很类似的树模型，但不是GLM：。显然这里远非线性的，而且是变量。

接着参数化，我们就有，若未知，即可变，则非GLM。这类的模型更适合的名字是：自适应基函数模型，即我们试图构造一些可以自适应的基函数，然后通过其线性组合构造最终的模型。这类模型经典如：树模型、GMM（高斯混合模型）、神经网络等。

Tags B-splines, bootstrap, Bump-Hunting, cross-validation, HME, logit, MARS, PRIM, 决策树, 分类树, 回归树, 基函数, 广义线性模型, 树模型, 统计学习, 统计学习精要, 自适应基函数模型, 高斯混合模型

读书有感

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

Post author By Liyun
Post date January 1, 2013
1 Comment on ≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记（十二）

第九章可加模型、树模型相关方法

1. 可加模型（additive model）

大家都知道线性模型是最简单好用的，但是往往现实中很多效应都是非线性的。前面举过一个学历的例子，再抄一下：

一方面，学历是你受教育的体现，也就是在取得学历的过程中完成了一定程度的知识积累。当然一定程度的学校录取证实了你一定程度的才智，但是也不是只有天才没有汗水就可以毕业的。更有意思的是，知识的积累往往是厚积而薄发，或者说是个非线性的...这也是为什么在衡量劳动者劳动价值的时候会放入受教育年限和其二次方的一个缘故（至少我是这么理解那个著名的xx公式中的二次方项的）。

也就是说，在线性模型中，我们最简单的方法就是利用多项式拟合非线性，不是有个著名的魏尔斯特拉斯（Weierstrass）逼近定理么？闭区间上的连续函数可用多项式级数一致逼近。

这个定理貌似在数分、实变、复变、泛函都有证明（如果我没记错名字的话）...泰勒（局部展开）也是一种局部使用多项式逼近的思路。不过人类的智慧显然是无穷的，自然有了应对各种各样情况的“万能药”和“特效药”，任君对症下药什么的。

这一节主要是讲generalized additive models，即广义可加模型。广义可加模型假设的是：各个自变量之间不相关，即可以被拆分开（虽然书上是用期望定义为，但是我觉得加入一些人为认定的交叉项再扩展开是没有问题的～）。数学表达式就是：

(1) 定义：，其中是已知的，而和是需要估计的。可见，如果只是从我们线性模型的进化到，那么我们是放松了对于是线性的要求，可以对每个自变量进行非线性回归，但y和这些之间依旧是线性关系；如果进一步放松，那么就可以引入新的非线性函数，那么y和那一堆之外还可以再套一层非线性函数。不过这里就要求给定一个g了，常用的就是那些指数函数对数函数等。

不过这里我们还要要求有一些比较优良的性质，首当其中就是可逆...（对于连续函数来说，可逆必定单调...因为可逆一一映射，又是连续的函数，不单调这就没法玩了呀！）好在我们一般就用一些比较简单的exp和log...常用的有：，，，这样...其中最后一个就是我们常用的logit regression。这样我们就可以定义“广义可加的logit模型”：。

(2) 算法。还是一样的，有了大致的idea我们还得有好用的算法。下面介绍一种比较一般性的方法。

数据集依旧记作：，然后我们使用OLS准则：。然后我们有迭代算法：即已知，如何迭代到t+1？

p个小步：每一次我们都是用给定的其他，其中，求得，来最小化计算第k个变量的系数，求的。这样的方法称为一维平滑值（one dimension smoother）。而在这个过程中，需要利用B-splines来求。所以“其实本来该模型的卖点是非参数，但是最后做一维平滑的时候还要利用参数化的B-splines...”，所以有点打折扣的感觉对不？

每p个小步构成一个的大步。如果最后是用B-splines来拟合，那么其实一开始就可以代入各种参数一次性完成参数化计算。

唯一值得考量的就是，这个迭代可能是局部最优化而不是全局最优化，有点取决于起始值的味道...我有点怀疑这个起始函数要怎么给...

(3) Na?ve Bayes Assumption（朴素贝叶斯假定）

有个有趣的结论：在Na?ve Bayes 假定下，分类器一定是可加模型。

直觉上讲，Na?ve Bayes假定其实也是假定分量独立：。

这样就很容易推导这个结论了：我们有后验概率。取个对数，我们有，所以就成了可加模型的形式。这样，Na?ve Bayes 假定比可加模型的假定就更弱一点。关于这点，我又去搜了一下，呃，找到了一点有关的信息，抄如下：

In supervised classification, inputs x and their labels y arise from an unknown joint probability p(x; y). If we can approximate p(x,y) using a parametric family of models G = {p_θ(x,y),θ in Θ}, then a natural classifier is obtained by first estimating the class-conditional densities, then classifying each new data point to the class with highest posterior probability. This approach is called generative classification.
However, if the overall goal is to find the classification rule with the smallest error rate, this depends only on the conditional density p(y|x). Discriminative methods directly model the conditional distribution, without assuming anything about the input distribution p(x). Well known generative-discriminative pairs include Linear Discriminant Analysis (LDA) vs. Linear logistic regression and naive Bayes vs. Generalized Additive Models (GAM). Many authors have already studied these models e.g. [5,6]. Under the assumption that the underlying distributions are Gaussian with equal covariances, it is known that LDA requires less data than its discriminative counterpart, linear logistic regression [3]. More generally, it is known that generative classifiers have a smaller variance than.
Conversely, the generative approach converges to the best model for the joint distribution p(x,y) but the resulting conditional density is usually a biased classifier unless its p_θ(x) part is an accurate model for p(x). In real world problems the assumed generative model is rarely exact, and asymptotically, a discriminative classifier should typically be preferred [9, 5]. The key argument is that the discriminative estimator converges to the conditional density that minimizes the negative log-likelihood classification loss against the true density p(x, y) [2]. For finite sample sizes, there is a bias-variance tradeoff and it is less obvious how to choose between generative and discriminative classifiers.

简单的说，就是“判别式模型与生成式模型”的问题。如果我们使用参数方法逼近联合分布，那么就是生成式模型（generative models）；相对的，如果我们直接对条件密度p(y|x)建模而不对p(x)进行任何假定，那么就是判别式模型（Discriminative methods）。我们常见的就是LDA和线性logit模型、朴素贝叶斯和广义可加模型。在一些已知如高斯分布的情况下，我们发现LDA优于logit并且有更小的方差，但是生成式模型的问题就是他的参数假定不满足...所以估计可能是有偏的。所以现实中，我们需要在无偏性和方差之间做一个trade off。关于这里的总结我搜到一篇：Discriminative vs Informative Learning - Stanford University，习惯中文的可以参考一下这个。其实这里看看这些概念和思想之争也挺好玩的，以前完全没有从这个角度看过回归模型...可见计量经济学关心的完全不是这些东西。我现在完全没概念我在machine learning这个深潭里面到底涉足多深了，但是可以明显的感觉统计学习的一些思维已经开始影响我的思维方式了...需要再继续融会贯通一下。