Categories
读书有感

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

继续一周一次的课堂笔记 昨天去晚了站着听讲,感觉好好啊,注意各种集中。想想整个教室里面就是我和老师是站着的,自豪感油然而生。

第二次课讲的东西依旧比较简单,是这本书第二章的前半部分。作为一个好久之前已经预习过的孩子,我表示万分的得意(最小二乘法难道不是三四年前就学过的?话说以后我再面人的时候,就让他推导最小二乘估计量,嘻嘻...考验一下基本功)。

------------原谅我的废话,笔记开始------------

简单预测方法:最小二乘法(以下沿用计量经济学的习惯,简称OLS)

OLS实在是太普遍了,我就不赘述细节了。OLS的思想就是,基于已有的样本信息,找出一条直线,让预测值与真实值之间的残差平方和最小,即最小。其中,为真实的样本观测值(已有样本),而是OLS的预测值。用图来讲的话,X为一维向量的时候,就是用一条直线来最好的拟合各个样本点。

这里就很明显了,首先OLS假设是一条直线。那么就是一个参数模型,即我们需要假设一个未知的参数,构成一个线性方程,然后再去估计的值。然后呢,直线会有很多条,所以我们要找到一个目标——比如这里,就是最小化残差平方和RSS。换言之,我们寻找的就是最优的向量使得RSS最小。

解这个最优化问题很简单,我就不重复了。最后解得的最优估计量为:

这里写成矩阵形式,比较简单。X为一维向量的时候,可以改写成形式,我个人不大喜欢,就不展开了。

简单预测方法:K近邻(k nearest neighbor)

K近邻的思想就更简单了。不就是想预测某个点x对应的y么?那么就把它的邻居都找来,平均一下好了。不是有句话叫做什么“一个人的收入就大概是他的圈子收入的平均值么?”

所以 ,这里表示点x的K近邻。至于这个近邻怎么定义嘛,嘻嘻,很简单啊,欧几里德距离就可以嘛~

评语:吴老师对于这两个算法的直观评价是,OLS呢就是勤奋的学生,预测前先做足功课,预测的时候只要知道X,噼里啪啦一下子y就估计出来了。然而knn则是一个临时抱佛脚的学生,预测的时候开始找自己的k近邻,然后把它们平均一下就好了。哈哈,大意如此,大家可以体会一下这种精神。我个人感觉呢,OLS属于以不变应万变的,而knn则是见机行事的。

统计决策理论(Statistical Decision Theory)

说了这么多,这个模型好不好到底怎么判读呢?凡事总得有个标准呢。这一系列的标准或者说准则,就是统计决策理论了。

首先呢,大致我们需要对X,Y有个分布上的描述:用记作向量的联合分布,然后为其对应的密度函数。之后为了估计Y,我们会有很多很多模型,即各种,而这些组成的函数空间记为

然后我们定义一个损失函数,比如在均方误差意义下,,这样就有了一个选择的标准——使得损失函数的期望最小:。接下来就是,到底在空间里面,哪一个最符合这个标准呢?

首先自然是把联合分布变为条件分布。这个idea显而易见——我们总是知道X的(原谅我吧,全中文确实比较难写,偶尔穿插英文一下 ^_^)。所以conditional on X,我们就有了

去解最小化问题,最终我们得到的就是在每个点X上, 。通俗的讲就是,对于每个点预测,把和它X向量取值一样的样本点都找出来,然后取他们的平均值就可以了。很直观的不是么?这里也有点最大似然的想法呢——比如预测一个男孩的身高,最保险的就是把和它同龄的其他男孩的身高平均一下,不是么?

但是说来简单啊,很多时候都是未知的,根本无法计算嘛。所以只能近似:

  • 回忆一下knn,就是放松了两点:1) 取的是x的近邻,而不一定是x; 2)用样本平均数代替了期望
  • 而OLS呢,也是最后在这里,用样本平均代替了期望。

近似嘛,自然有好的近似和不好的近似。很显然的,当样本比较大、尤其是比较密集的时候,x的邻居应该都离x很近,所以这个误差可以减小;此外,当样本很大的时候,根据大数定律,平均数收敛于期望。所以,这两种算法应该说,都在大样本下会有更好的效果。

模型选择、训练误差与测试误差、过拟合

这里讲的比较简单。模型选择就是的选择,即选择哪一类函数空间,然后再其中找/估计最优的。很显然,如果只有若干个有限的样本,我们总能把各个样本用直线或者曲线依次连起来,这样的话就有无数个f可以作为此问题的解。显然这不是我们想要的——这样的称为“不设定问题”,即可能无解、可能多个解、还可能因为一点点X的变化导致整个解的解答变化。因此我们需要先设定一个解的类别。

训练误差:预测模型估计值与训练数据集之间的误差。RSS就是一个典型的训练误差组成的残差平方和。

测试误差:用训练集以外的测试数据集带来的误差,显然我们更关心的是测试误差——训练总能训练的很好,让损失函数期望最小,然而测试集则不一定这样。一般说来,测试误差>训练误差。

过拟合:选择一个很复杂的f,使得训练误差很小,而实际的测试误差不一定小。最极端的就是刚才说的,把训练集的点一个个依次连起来...训练误差肯定是0是不是?

我们关心的自然是怎么降低测试误差。显然这东西会跟训练误差有关,但是它还跟f的复杂度有关。最最棘手的就是,f的复杂度是一个难以衡量的问题。早期的研究有用自由度来衡量这个复杂度的,但是也不是那么的靠谱...后面的有人鼓捣出来PAC(使得近似正确的概率最大——吴老师原话),还有一个VC来衡量复杂度——但几乎实践中无法计算,没几个计算出来的。嗯,水很深哇。

Categories
事儿关经济

R并行做大数据时间序列分析与bootstrap

好久没写关于经济学的文章了...今天看到两个搞matching的人拿到诺奖,瞬间想起当年和一个学心理学出身的童鞋一起搞的考虑到心理学因素的matching game...可惜最后没有时间完善,就放在那里当雏形了。我们的idea应该还是蛮有新意的呢~matching需要设计机制,然后用博弈来解,哎,很好玩的...

很多人都知道我是不搞时间序列分析的,尤其不喜欢基于时间序列的因果推断(格兰杰因果检验几乎是被我打入黑名单的一个词)。但这次为什么专门写这么一篇blog post呢?其实,我不反对时间序列作预测嘛~而google这篇paper,目的在于预测,又是latex排版的(搞不好还有sweave或者knitr的功劳),读起来赏心悦目的多。

这篇paper题目是:

Large-Scale Parallel Statistical Forecasting Computations in R

地址见:http://research.google.com/pubs/pub37483.html

亮点自然是:大数据计算、map reduce、时间序列分析、bootstrap (所以说google是一家让人尊敬的公司,http://t.cn/zlbAYJY这里总结了他将学术成果悄无声息的服务于大众的案例)。虽说大半夜的,但看到这个东西,再也睡不着了,索性写完一吐为快。(那次沙龙还说到来着,看吧,google早把这些好玩的东西都搞定了,只是不公开拿出来给大家用罢了~)

1. 并行算法

并行算法这里,主要是map reduce。他们的任务主要有:

  • Facilitate parallelism of computations on up to thousands of machines without access to shared NFS filesystems(上千个节点的并行计算,无共享的NFS文件系统).
  • Make distribution of code and required resources as seamless as possible for analysts to minimize code modifications required to enable parallelism.(无缝衔接各环节,减少分析师写并行算法工作量)
  • No setup or pre-installation of R or specific libraries should be required on the machines in the cluster. A virtual machine for the workers should be created dynamically based on the global environment and available libraries of the caller(节点上无需事先安装R,虚拟机会自动按需构建).
  • Return results of parallel computations in list form directly back to the calling interactive session, as with lapply in R.(lapply函数直接返回并行结果)
  • Allow the parallel functions to be used recursively, so that MapReduce workers can in turn spawn additional MapReduces.(并行函数可以循环调用)

系统构架如下:

2013-12-09 16_48_39-37483.pdf - Adobe Reader

然后若干技术细节还包括,搞定R函数复制和计算的环境并行同步,搞定data.frame和list存储格式与在map函数中直接调用。搞定后,基本底层就搭建好了,剩下的就是调用R了。

2.时间序列预测

最典型的就是google trend的预测了...

2013-12-09 16_49_18-37483.pdf - Adobe Reader

这里他们直接用R包googleparallelism,然后希望用一些时序模型都尝试,做预测,然后取他们的均值(剔除上下总计20%)作为估计值以减少误差。示意图如下:

2013-12-09 16_49_35-37483.pdf - Adobe Reader
我只能说,果然是做机器学习的人啊,和random forest思路一致,弱的分类器结合起来,可能有意想不到的结果。同样的,每个模型都是多少有效的话,平均一下就更稳健啦,尤其是在大数据支撑下...

这样的平均之后已经无法直接推导方差和置信区间,所以他们采取了更依赖机器计算的bootstrap方法,直接强行算出来置信区间...喵的,我只能说谁让当年高斯那群天才整出来大数定律和中心极限定理呢?推不出来估量量方差不要紧嘛,直接重抽样模拟就好了...汗。

3.训练集

果然是做机器学习的人,接下来的思路就是直接一期期训练模拟呗。这个没啥说的了,见下图。

2013-12-09 16_49_51-37483.pdf - Adobe Reader

模拟出来的结果示意图:

2013-12-09 16_50_05-37483.pdf - Adobe Reader

至此,整个问题解决完毕。细节还请大家直接去看原文paper。我的几点感触吧:

  • 1. 机器学习之所以在业界这么受欢迎,主要是其确实能够解决问题。迅速、有效,这个是其他方法比不上的。
  • 2. 大数据、大规模计算,使得一些很简单的idea借助模拟和重抽样方法,大放异彩。
  • 3. 预测,有时候不比因果推断次要。
  • 4. 传统模型,需要适应大数据。
  • 5. 说到底,理论体系还是有待完善的。希望这类方法是下一个微积分,可以先用,然后慢慢补充完相应理论体系。这样,我们才知道什么时候,需要勒贝格测度来取代原有牛顿积分。

总之,虽然无奈,但是有用之物必有有用的道理。期待对理论研究的冲击和激发。

 

Categories
读书有感

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

前两天微博上转出来的,复旦计算机学院的吴立德吴老师在开?统计学习精要(The Elements of Statistical Learning)?这门课,还在张江...大牛的课怎能错过,果断请假去蹭课...为了减轻心理压力,还拉了一帮同事一起去听,eBay浩浩荡荡的十几人杀过去好不壮观!总感觉我们的人有超过复旦本身学生的阵势,五六十人的教室坐的满满当当,壮观啊。

这本书正好前阵子一直在看,所以才会屁颠屁颠的跑过去听。确实是一本深入浅出讲data mining models的好书。作者网站上提供免费的电子版下载,爽!http://www-stat.stanford.edu/~tibs/ElemStatLearn/

从这周开始,如无意外我会每周更新课堂笔记。另一方面,也会加上自己的一些理解和实际工作中的感悟。此外,对于data mining感兴趣的,也可以去coursera听课~貌似这学期开的machine learning评价不错。我只在coursera上从众选了一门 「Model Thinking」,相对来说比较简单,但是相当的优雅!若有时间会再写写这门课的上课感受。笔记我会尽量用全部中文,但只是尽量...

------------课堂笔记开始--------

第一次上课,主要是导论,介绍这个领域的关注兴趣以及后续课程安排。对应本书的第一章。

1. 统计学习是?从数据中学习知识。简单地说,我们有一个想预测的结果(outcome),记为Y,可能是离散的也可能是连续的。同时,还有一些观察到的特征(feature),记为X,X既可能是一维的也可能是多维的。对于每一个观测个体,我们都会得到一个行向量,对应它的p个特征的观测值,以及一个观测到的结果值。如果总共有N个个体,那么我们对于每个个体都会得到这些值,则有为观测结果的列向量以及X (n*p)矩阵。这样的数据称之为训练数据集(training set)。这里更多是约定一些notation。

2. 统计学习分类?一般说来,我们有个观测到的结果Y,然后找到一个适合的模型根据X预测Y,这样的称之为有监督的学习(supervised learning)。而有些时候,Y是无法观测到的,那么只是通过X来学习,称之为无监督的学习(unsupervised learning)。这本书主要侧重有监督的学习。

3. 回归和分类器。这个主要和Y有关。如果Y为离散,比如红黄蓝不同颜色,则称之为分类器(学习模型);反之,若Y为连续,比如身高,则称之为回归(学习模型)。这里更多只是称谓上的区别。

4. 统计学习的任务?预测。通过什么来预测?学习模型(learning models)。按照什么来学习?需要一定的准则,比如最小均方误差MSE,适用于分类器的0-1准则等。基于这些准则、优化过的实现方法称之为算法。

5. 统计学习举例?

分类器:依据邮件发信人、内容、标题等判断是否为垃圾邮件;

回归:前列腺特异抗原(PSA)水平与癌症等因素的关系;

图形识别:手写字母的识别;

聚类:根据DNA序列判断样本的相似性,如亲子鉴定。

6. 课程安排顺序?

第二章,是对于有监督的学习模型的概览。

第三章和第四章将讨论线性回归模型和线性分类器。

第五章将讨论广义线性模型(GLM)。

第六章涉及kernel方法和局部回归。

第七章是模型评价与选择。

第八章是测侧重算法,比如最大似然估计,bootstrap等。本学期预计讲到这里。所以后面的我就暂时不列出了。

目测第二节开始将变得越来越难,前阵子自学第二章痛苦不已啊...一个LASSO就折磨了我好久。当时的读书笔记见:降维模型若干感悟

--------10.15补充---------

上周写的时候只是凭着记忆,笔记没在身边。今天重新翻了翻当时记下的课堂笔记,再补充一些吧。

第九章是可加模型,即

第十章是boosting模型

第十一章讨论神经网络

第十二章讨论支持向量机 (Support Vector Machine)

第十三章设计原型方法(Prototype)

第十四章从有监督的学习转到无监督的学习(即有X有Y->有X无Y)

第十五章讨论随机森林模型(Random Forest)

第十六章是集群学习

第十七章结构图模型

第十八章高维问题(我最近一直念叨的curse of dimensionality...今年搞笑诺贝尔奖也多少与此有关,见 http://www.guokr.com/article/344117/,还有一篇相关的paper

ps. 吴老师对于随机森林等等模型的评论也挺有意思的,大致是,大家都没搞清随机森林为什么效果这么好...而且这一类模型都是computatoinal intensive的,即有一个非常简单的idea然后借助大量的计算来实现。此外,这类方法更多有“猜”的感觉,无法知道来龙去脉,在现实中显得不那么intuitive...(不像econometrics那般致力于causality呢)。

Categories
读书有感

降维模型若干感悟

前几天集中爆发了一些email,直到最后和Frank兄提起,他说我应该去看一下 Adaptive Lasso,我才终于痛下决心开始看这方面的东西。先说说为啥开始看Lasso。

需求。大数据时代,任务有很多:

  • 理论层面,要有适应大数据的模型。一方面是数据量的增加(表现为个体记录的增长),一方面是数据维度的增加(简单的说就是回归方程右边的变量),让大数据这个任务变得格外艰巨(p.s. 这个不是我总结的,照抄上次ShanghaiR沙龙时候Ming的原话...话说我别的没记住,就这句话深深的印在脑海了,哎~)。
    • 数据量的增加,对应的是大样本理论。这个好玩的有很多,暂且不表。
    • 数据维数的增加,则需要相应的降维模型。你总不能在回归方程右边放入几千个变量,“维数灾难”啊...所以变量选择是个很好玩的话题。
  • 应用层面,一个模型性质再漂亮,你也要能算得出来才行是不是?
    • 首先就是要有个好的算法,比如在「统计学习那些事」中提及的LAR对于Lasso的巨大贡献。
    • 其次,什么分布式计算啊,并行计算啊,都成为热呼呼的实践问题(当然我还是go against那些不管三七二十一、直接软件中调用模型的。任何一个模型的假设和局限性都是应该首先考虑的,要不真不知道预测到哪里去了呢~)。

好吧,好久没用这么多层级了。只是昨天稍稍理了理思路,顺便写在这里,算作「感悟一」。

然后,说到底统计学还是为其他学科服务的(好吧,我是想说数据不是无源之水,总归有自己的背景,总归有在这个背景领域的人希望借助数据来解决的问题)。那么作为一种empirical method,统计模型关心的是什么呢?在被计量经济学熏陶外加祸害了若干年后,发现它本质还是为了经济学研究的一些目的服务的,所以关注的更多是consistency,大家张口闭口就是“变量外生性”...而这多少有些直觉+经验判断的东西。显然,统计模型不仅仅是计量经济学,昨天看「The Elements of Statistical Learning: Data Mining, Inference, and Prediction」,大致的关于统计模型关心的判断标准的「感悟二」总结在这里:

  • consistency:这个还是逃不掉的,一致性在大样本下虽然比小样本的无偏要求来的弱得多(plim毕竟比期望算子好“操作”一些)。其实有一段时间我一直很抵触把计量经济学里面的causality叫做因果关系,学习计量模型的过程基本就是保证估计一致性的推导过程...想说的只是,真正的因果关系不是统计学就可以定义的,还是要回到学科本身。consistency更多包含着“internal validity”的味道,即一个结果可以期望在样本本身内重复实现。个人感觉,从经济学理论与实证研究的角度,这大概是计量经济学能达到的最多的程度了吧。再苛刻的因果真的就是经济理论本身的问题了。
  • accuracy: 统计还有一大任务,做预测。我们都知道OLS有的时候可以很简单的给出一个consistent的估计量,但是仅仅是均值意义上的估计还是不够的,对你还得给出个方差。这个方差就刻画了你的估计值是不是飘来飘去。我们当然希望一个方差比较小的估计量,所以大多数时候OLS是不能满足这样的要求的(顺便复习一下BLUE的那些条件)。
  • implementable: 有的时候我们可以用现有的数据、花费大量的时间,来拟合一个漂亮的模型。但是,模型不是放在那里就可以的,在实际应用中大家更关心的是,模型建立之后对于日后决策的指导作用。可能1000个自变量拟合出来的模型比20个好10%到20%,但是在实际应用中,20个变量显然更实用...同理,有些非线性模型漂亮的一塌糊涂,但是计算复杂度可能远远不是多项式级别的。这个时候,退而求其次也不失为一记良策。说到底,有的时候并不要求最完美的模型,总要在性能和效率之间取得一个平衡。
  • 当然说到prediction,这里更多的就有statistical learning的味道了。回归多少还算是supervised learning,至少脑海里大致有个印象什么是回归方程那一边的y。更多的时候,连y是什么都没有概念,所以就有了基于similarity的模型,比如clustering,比如协同过滤...不过有句话确实说的好(摘抄自「统计学习那些事」):

立新老师曾经有这么一句话:“If a method works well in practice, there must be some theoretical reasons for its success.” 如果一个模型在实践中表现的很好,那么一定有它好的原因。

所以基于上述三点(当然还有可能有更多的考虑),不同的模型对于不同的标准有着不同的达标水平。大家各有所长,用哪个还真得看实际任务的需求了。

「感悟三」,则是statistical learning (统计学习,有点机器学习的味道)的任务,这个是从「The Elements of Statistical Learning: Data Mining, Inference, and Prediction」上照抄的:

  • 预测准确性要高:和上面的accuracy对应。
  • 发现有价值的预测变量:更有可能从归纳法回溯到演绎法,给出更多的insights。

最后的,稍稍偏数学一点。「The Elements of Statistical Learning: Data Mining, Inference, and Prediction」里面第三章讲了很多Shrinkage Methods,关心的是varible selection(生物统计中feature selection)的问题。从大家最耳熟能详的stepwise(逐步回归),到ridge regression(岭回归),再到Lasso(或者把LAR也算进来)。基本说来,ridge和Lasso是在OLS基础上一个很有意思的变化。

  • OLS求解的最优化问题是:
  • ridge regression则是加了一个L2惩罚项,即 ,其中t是一个给定常数参数。
  • Lasso则是把这个L2变成了L1,即

就这么一个简简单单的变化,就有了后面那么多神奇的性质。「感悟四」就是,原来Lasso思想并不是那么复杂啊。

Categories
读书有感

再读「数学之美」

今天难得的一点专注时间,打开了「数学之美」,实体书的阅读果然还是比较舒服。

和Google黑板报版相比,正式出版的版本的确增加了不少的内容,如果想深入的多了解某个算法一点,会合适的多。不过某种程度上感觉,没有黑板报版那么引人入胜了,写作风格变得更严谨了。

书不是很厚,加上排版比较宽松,其实看起来还是蛮快的。看到后面,突然对“条件随机场”这种东西产生了莫名的好奇感,然后匆匆的看过去,还是蛮好玩的。在过去的一年中,慢慢的揭开了自然语言处理的各种面纱,这个领域还真的是蛮好玩的,也看到那么多聪明的中国人在此不懈耕耘造就的各种神奇。比如,我用来打这篇日志的输入法——经过很长一段时间的训练之后,他越来越聪明的可以捕捉到我想说什么,打字的过程已经不会影响到思维了。对比以前用智能ABC的日子,突然觉得生活真的是美好了许多。而这一切背后的辛勤劳动,都离不开算法的支撑和我们对于数字信息理解的深入。

此外,还顺便看了一眼奇异值分解(SVD),以及MapReduce,反正对于各种可以降低算法复杂度的思路,都是很能裨益工作的。曾经很多人不知道“线性代数”这门课有什么用...从我个人经历来说,从学完它就一直在用,各种用。简洁的神奇。

还是挺好的一本书,就是浅了一些,有些深入的东西可能确实比较难以直观的描述出来。Machine learning果然还是需要下苦工的一个领域。