Tag: 统计学习

读书有感

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

Post author By Liyun
Post date March 30, 2013
11 Comments on ≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记（十六）

第十五章随机森林(Random Forest)

终于讲到这个神奇的算法了...若是百年前的算命术士们知道有此等高深之术，怕是要写成一本《随机真经》作为武林宝典世代相传了吧？猜得准才是王道嘛。

p.s. 以前没看过的童鞋不要急，这节课只是从boosting直接跳讲到十五章，并不是已经快结课啦。

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

1.定义和算法

算法：

1. For b = 1 to B
- 生成一个自生样本(via bootstrap)
- 由生成树:
  - 随机选取m()个变量（相应的，取了m维子集）。一切的神奇都在于这里是随机降维的。
  - 由生成树。
输出(即森林）。

随机森林算法的参数主要就是决策树的参数，用来控制树的生长的：保证每个叶子中的实例数不大于。

应用

1) 回归在回归的情况下采取均值，最终输出的就是.

2) 分类分类的情况下进行投票，，得票最多的那类获胜。

参数

总结的来看，参数主要有如下几个：

B：试验次数。一般为几百到几千，所以是computational intensive.
m：降维的力度。作者建议回归的情况下采用，然后分类的情况下采用。
：建议回归的时候设为5，分类的时候设为1（彻底分到底）

伪代码

其实上面已经写的比较清楚了...我只是再抄个伪代码过来而已。

select m variables at random out of the M variables

For j = 1 .. m

If j'th attribute is categorical

(see Information Gain)

Else (j'th attribute is real-valued)

(see Information Gain)

Let (this is the splitting attribute we'll

use)

If j{*} is categorical then

For each value v of the j'th attribute

Let = subset of rows of X in which . Let

= corresponding subset of Y

Let = LearnUnprunedTree

Return a decision tree node, splitting on j'th attribute. The number

of children equals the number of values of the j'th attribute, and

the v'th child is Childv

Else j{*} is real-valued and let t be the best split threshold

Let = subset of rows of X in which . Let

= corresponding subset of Y

Let = LearnUnprunedTree

Let = subset of rows of X in which . Let =

corresponding subset of Y

Let = LearnUnprunedTree

Return a decision tree node, splitting on j'th attribute. It has two

children corresponding to whether the j'th attribute is above or below

the given threshold.

2. 为什么要“随机”

bootstrap：通过多次重抽样减小误差。

考虑下面的情况：

1) 为随机变量，且,。

(i)当相互独立的时候，，且。

(ii)当相互不独立的时候，我们有。这样接下来就有

如斯，仅使用bootstrap的话压缩的是方差的第二部分，而随机选的的M可以减小样本之间的相关性，从而减少不同树之间的相关性。

2）OOB(out of bag)实例

OOB的概率：。这样就是说，在一次抽样中约有1/3的样本没有被抽到。

两次bootstrap抽样的话，样本约有40%的重叠，这样的重叠概率会影响到上面的(ii)中，两次抽样得到的样本重叠很高，相互不独立。

这样我们用67%的样本训练数据，用剩下33%来测试。

3. 其他应用

1)变量的重要性（feature selection，俗称的特征选择）

第一种方法可以和上节课梯度树那里的一样，用来刻画变量的重要性。

第二种方法则是比较有意思。对于一棵树，我们用OOB样本可以得到测试误差1。

OOB样本大概长成这个样子：

，样本量足够大的情况下。

然后随机改变OOB样本的第j列：保持其他列不变，对第j列进行随机的上下置换，得到误差2。至此，我们可以用误差1-误差2来刻画变量j的重要性。当然这里loss function可以自己定。这里的大致思想就是，如果一个变量j足够重要，那么改变它会极大的增加测试误差；反之，如果改变它测试误差没有增大，则说明该变量不是那么的重要。（典型的实用主义啊！管用才是真，才不管他什么证明不证明呢！自从开始接触机器学习的这些算法，我真的是被他们的各种天真烂漫的想法打败的一塌糊涂，只要直觉上过得去、实际效果看起来比较好就可以了呢，规则真简单）。

2) 相似图(proximity plots)

除了用户变量选择之外，Random Forest也可以给出各个观测实例之间的相似度。

Proximity plots记作在一个叶子结点同时出现的次数，其实大致就是一个相关性矩阵的样子。思想其实就是，如果两个观测样本之间比较相关，他们在树分枝的过程中就比较难以分开，所以会经常一起出现。我们故而可以用一起出现的次数给这种相似程度打分。

树类算法

至此，我们大概一口气过掉了所有跟树相关的算法。

先是单一的决策树，然后是基于已有弱分类器的改良算法，比如梯度树，然后就是和梯度树不相伯仲的随机森林。我感觉随机森林真的是起了一个好名字，在我没学机器学习之前就听到无数人跟我说起随机森林，而梯度树却只是正儿八经开始看了才记住的名字...

下下周开始，会依次讲到神经网络和SVM...看来supervised learning就快拉上帷幕咯。

Tags boosting, bootstrap, GTBA, oob, out of bag, proximity plots, supervised learning, 决策树, 分类器, 变量选择, 损失函数, 有监督学习, 树模型, 特征选择, 相似图, 相关性矩阵, 统计学习, 统计学习精要, 随机森林

读书有感

≪统计学习精要(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 March 19, 2013
15 Comments on ≪统计学习精要(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雏形了吧？

Tags AdaBoost, boost, boosting, 分类器, 前向分步算法, 基函数, 广义线性模型, 指数损失函数与, 提升, 统计学习, 统计学习精要, 自适应基函数模型

读书有感

≪统计学习精要(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这个深潭里面到底涉足多深了，但是可以明显的感觉统计学习的一些思维已经开始影响我的思维方式了...需要再继续融会贯通一下。