Categories
读书有感

≪统计学习精要(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就快拉上帷幕咯。

Categories
读书有感

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

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

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

MARS

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

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

mars1

这样就可以定义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,听起来像是一个智囊团的感觉。画出来呢,就是一个树的形状。

hme

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

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

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

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

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

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

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

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

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

Categories
读书有感

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

2. 树模型(Tree Model)

(1) 树的一般概念:见过二叉树么?差不多的样子可以有多个叉叉...自行脑补一下分形去吧。

(2) 回归树(regression tree)

还是数据集,然后我们可以根据不同的门限来分类,比如x<;1分在左边枝子上放在右边枝子上。然后在下一层继续分叉分叉...一层又一层。感觉当初发明树模型的孩子一定很喜欢生物学尤其是植物学吧!有没有类似于顶端优势的定理呢?嘻嘻,可以叫做歪脖子树定理嘛!

D09AE40BF1CAAEF145604494C7945E06八卦来源

对于一颗树T,我们采用如下记号:

:叶子的总数

,某个叶子或者根节点。

:叶子节点 中的样本数。

,这个点y的平均值。

,每个

中的均方误差(方差)。

这样一颗树的质量就可以定义为。这样给定一棵树,有了一个函数,然后就可以预测了。

树的生长:这就是叶子和层次的选择,显然我们一共有中选择。需要从中选出最好的。当生长不动的时候,停止。而长得太大的时候,就是过拟合的问题。所以我们需要剪枝。

树的剪枝:准则需要变,,即加入一个惩罚项,然后就可以使用cross-validation或者bootstrap了。

(3) 分类树

同样的,只是我们需要定义新的准则,类似于0-1准则。,也就是节点中属于第k类的比例,所以

这样我们就有,即主导类别占据该节点。

定义1:我们的预测误差就是,就可以定义

定义2:熵。我们定义,这样就可以定义

定义3: 基尼准则(Gini),定义函数,然后

有了准则之后,我们就可以生长、剪枝和预测了。

为啥我觉得这就是决策树呢?喵了个咪的,就是一个质量定义问题嘛。回归和分类器之鸿沟一直延续呀,无论是线性模型还是树模型...

Categories
事儿关经济 经济、IT观察与思考

社会实验的特殊性(三)

在上一篇[cref %e7%a4%be%e4%bc%9a%e5%ae%9e%e9%aa%8c%e7%9a%84%e7%89%b9%e6%ae%8a%e6%80%a7%ef%bc%88%e4%ba%8c%ef%bc%89]里面回顾了费歇尔的实验设计三原则之后,那么归根结底,我们为什么要做实验?

从一个纯经济学的角度来看,社会实验的目的之一就是在我们面对现有的数据受到各种局限、从而无法完美的回答我们关心的问题的时候(说到底还是各种内生性问题),采取的一种主动出击寻求答案的方式。故而,实验之前我们一般是有一个基本的思路和方向的,然后更多的想去看一下这个东西到底是不是在现实中就是这个样子。从这个角度而言,社会实验是在很明确的我们知道想得到什么信息的方向上去设计的。

说一下从我个人的感觉上的最大的在业界和在学术界的不同,可能就是data上。在学术界,难得会有非常好的data,所以很多的时候我们都是在有限的数据资源的基础上、去力求用最完美的方法估计我们感兴趣的值。数据源有限的原因有些是历史上的,比如我们研究几十年前的事情,自然当时没有电脑等东西可以完善的记录所有的事情;有些是数据本身的性质决定的,比如宏观里面常用的gdp等东西,中国的数据是1978年之后才有的,而且一般都是年度数据,更受限于国民统计汇总的层级汇报,自然会有一些测量偏差;有些是业界有数据,但是没法得到,这里就牵扯到一些隐私等法律权益、或者数据接口API等开放的幅度的问题;还有些是知道数据在哪里、也可以得到,但是成本太高,比如个人层面的数据,除了全民普查外很难有全覆盖的数据,一般只是小规模样本;最后的就是信息并不是直接以数字的方式记录的,比如twitter上面的用户微博记录,因此需要借助文本挖掘等手段进一步深究。

业界主要提供的就是第三类,大量的个人用户的数据,比如淘宝上各种买卖双方交易的数据。现在淘宝的交易量真的是非常大,而且每笔交易都是真实的现金往来的(我们不考虑非法的洗钱状况),其实背后对应的就是一个真实的微观交易的集合。但是这个交易数据怎么用?最简单的,我们可以看价格,对于同质品之间竞争已然白热化的,已然相差无几,那么价格几乎就等同于scanner price,可以用来衡量物价的波动。当然,网络交易有不同于实体交易的地方,比如受限于运输成本和采购的规模效应,肯定会和超市里的价格有所区别。另一方面,网络上的价格信息流动非常充分,越来越接近于理想中的完全竞争市场对于信息的要求,所以多少也让人兴奋。

另外一个有趣的数据可能就是微博,因为其实质上是一种“短平快”的信息传播渠道,会把信息通过简单的几个信息源极快的扩散到整个网络中去(所谓的influencer model)。所以现在很多人炒得很热的微博营销也是背后有着深刻的渊源的。但是同样的,信息传输成本降低的背后就是噪音的增加,因此对于微博的信息分析起来除了文本挖掘技术实现之外,就是怎么去在大量的噪音数据中寻找到有用的信息。从这个角度而言,就是在进行任何文本挖掘或者信息提取之前,是不是有一个主导的思路去明确的知道需要挖掘的信息。业界很多时候不是数据太少了,而是太多了,以至于大家根本不知道这些数据可以怎么用,所以data mining成为了救命稻草,一窝蜂的上去看看能不能挖到金矿。从我的角度看,每一个data mining算法背后必然是有一种主导的思想来支撑的,比如决策树,不过是分类统计最优化路径的感觉,这样的直觉还是蛮强的。所有数据分析的任务无外乎两个字:降维,怎么在一个多维的好烦的数据海中找到自己最感兴趣的数据,可能是几个变量之间的关系,可能是一个综合指标的创建。最简单的,GDP就是对于国民生产消费活动的降维衡量指标,所以他既然降维了自然有损失,能够多么真切的反应经济活动的现实就必然要打个折扣。

经济学里面常用的“降维”的方法就是回归,无论回归在统计学或者其他学科里面被批判的多么体无完肤,但是回归最大的好处在我看来就是最容易融入经济学直觉。在[cref %e5%b0%8f%e7%aa%a5%e2%80%9c%e9%ab%98%e7%bb%b4%e6%95%b0%e6%8d%ae%e9%99%8d%e7%bb%b4%e2%80%9d-2]里面我曾经提到一些最新的高维数据降维的算法,然而算法本身必然是有直觉甚至是(经济)理论来支撑的。当数据挖掘方法被应用在一个经济活动或者经济问题的时候,如果完全脱离了经济直觉和经济思维衍生的分析方法,我觉得未免有点太过于高傲了。有的时候,如果分析思路足够敏锐,那么基于这样思路的各种算法的出来的结果可能是殊途同归。正所谓“万变不离其宗”,这也是我觉得很多data mining的方法应该和经济学、商科的思维更好的融合在一起的缘故。就像挖矿,我们除了要有先进的挖掘机以外,事前的各种勘探和经验思路还是有非常大的价值的,至少可以降低找到金矿位置的成本、尤其是时间成本。这也是我觉得经济学在业界的应用天地断然不仅仅限于和金融相关的那些而已的缘故。

另外,如果“降维”说的广义一点,就是科学的目标。可能不同的人对科学有不同的定义,我除了喜欢一种“概率”角度的定义之外,刚看到一种定义也是蛮受启发的,

The object of science is the discovery of relations.., of which the complex may be deduced from the simple. John Pringle Nichol, 1840

然而,说到底,经济直觉总要来源于实践经验,只要经济学还是定位于“研究人类行为活动的科学”。实践中信息不足的时候,信息是制约的瓶颈,因此我们要借助更多的数学建模工具来力求完美精细的刻画现有的数据构成的轮廓。反之,如果数据是可选择的,那么更多的精力就应该放在如何去“选择”数据上。我认为,实验最大的好处就是数据完全是由实验设计阶段决定的,实验设计的好数据自然会更好的告诉我们所关心的答案。

忘了是哪位大牛在Handbook of Econometrics里面写的了,大意是“与其寻求更好的估计方法,不如寻找更高质量的数据”,言下之意就是在数据可以被“设计”而获得的情况下,我们可以把精力更多的放在实验设计而不是估计模型的选择上。我并不是一个纯粹的reduced form鼓吹者,相反,我是更欣赏structural model后面的经济学思维的。因此,在实验的方法被付诸实践之前,我更希望更多的按照一种经济学model的模式去考量这些问题,去更精巧的让实验告诉我们想知道的答案。除了社会实验的特殊性考量之外,必然的,我们没有任何理由抛弃现有的经济理论、尤其是微观经济理论去完全随意的“检查”几个变量之间的实验上的因果关系。且不论efficiency,社会实验的对象为参与经济活动的人、这一特质决定了我们在设计实验的时候便要充分利用现有对于人类行为的认识成果,更好的一步步设计实验的流程——可能不只是一次实验的流程,更多的是一环扣一环的一个个实验如何按部就班进行下去。一个动态的实验设计会更好的考量实验设计者对于经济学的理解,也是社会实验较之于费歇尔三原则下的自然科学实验、要求更高的方面之一。