Categories
网络新发现

R大神们是这么玩乐高机器人的...

前段时间COS上说Rafael Irizarry用最小二乘法帮小朋友玩乐高,已经觉得很出手不凡了。然后今天直接看到了ev3dev.R这个东西,瞬间觉得整个人都不好了...大家要不要这么geek...71sXXBHsf6L._SL1500_

这种恶意卖萌的对话什么的实在是...总而言之,这货已经开始被进化了...

SER: Tell us more about the R part.
SERATRON: I am running RServe server. PCs can communicate with me using RSclient. They do all the heavy computations for me, I can’t be bothered (I have no FPU, can you imagine?!?). Those PCs think they can command me…

SER: Why do you have two servo motors?
SERATRON: So that I can move, you silly!

SER: Hmm, why do you have an infrared sensor?
SERATRON: So that I can avoid obstacles and I will not fall from height. Why do you have eyes donkey?

SER: Errrrrr, what are your touch sensors for?
SERATRON: They also prevent me from falling from height. If I don’t feel the surface below me I am not going to move. Would you?

SER: Ok, last question you naughty robot! What is your gyroscope and accelerometer for?
SERATRON: Can’t you count? It’s not one question but two. I use gyro to know my heading direction. No dumbass, not for balancing, I don’t use it in this axis. I don’t use accelerometer now but I could use tilt input as a third level protection from falling. I could also use it to detect collisions with other objects but I have other means.

SER: It was a pleasure to meet you (coughs), thank you.
SERATRON: I hope I will be finished for SER VII – 08.12.2014!

SERVIIRobot2

总而言之这货已经可以自我前进、躲避障碍什么的,为嘛我想起来的是我家那个扫地机器人iRobot 380t?

iRobot-Braava_thumb

对了,卖萌视频在此:http://www.r-bloggers.com/interview-with-seratron-lego-ev3-robot-driven-by-r/

Categories
事儿关经济

说说我所认识的“最小二乘君”(配图版)

由于近些年常常跟搞数据分析的人混迹在一起,所以很多时候说话方式有点偏向机器学习了...顺便心里暗暗的忧伤一下当年的心路历程(不知道我的基本轨迹的可以先去看看CV..)。这里聊作一二记录,讲讲我所认识的“最小二乘法”(下称最小二乘君)。那个,语言稍显浮夸,大家随便看看哈,别较真。

<锲子>

是写小说的时候大家都兴先来个“锲子”么。7年前,我还是一个年幼无知的大学新生儿。当时我们系开了两门传说中各挂50%的数学课:微积分和线性代数。同学们大都学的死去活来,我也学的死去活来,一度开始怀疑自己的智商...其实现在想想,我也不知道当年为什么学的那么痛苦,现在随手用个微积分貌似都很水到渠成的样子。嗯,可能是老师授课方式不够好吧。那年直到期末考试,我也不知道我学了一年的微积分有什么用处,除了背下来少数的几个证明推导和学会了一堆算微积分的“技巧”之外。

从前有棵树,叫高树,树上挂了很多人……挂了很多人的高树...

线性代数也是一样的。当年翻看某本计算机类入门书(可能是算法与数据结构),前言一开始就是一行金字,大意是“矩阵论是当代计算机基础×××”。然后翻翻后面的果然看不懂,于是默默的去图书馆把这本书还了,然后借了一本黄皮的泛着金光《矩阵论》回来。同样悲催的,啥也没看懂,然后默默的放弃了我在这个领域深修的打算,乖乖的回去上必修课了。(所以我当年学习高级计算机知识的一腔热情就被这么无情的浇灭了哇!果断考完当时的计算机等级考试——C语言和数据库就扔掉编程了...)

线性代数一直学到最后,我还是以为这东西就是来替代“高斯消元法”解联立方程式的...什么特征根啊,奇异值分解啊,格拉姆-施密特正交化啊,直到最后我也没明白是干嘛用的,除了会算几个数之外...没想到,那日一别,重逢已是花落花开好几轮之后...当真是良辰美景虚设!只是万万没有想到,他乡遇旧友,而这厮竟和日后的最小二乘君紧密相连,难分难舍。

138112_091242423086_2良辰美景虚设

Categories
读书有感

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

照例继续本周笔记。这次我没啥废话了...

--------------笔记开始---------------

投影矩阵与消灭矩阵

首先是上次没证的若干OLS性质。基本都是公式。我就照抄原来econometrics做的笔记了。权当复习了...对计量有兴趣的、线性代数还不错的,建议去看《Microeconometrics- Methods and Applications》(?A. Colin Cameron / Pravin K. Trivedi )。

先定义两个矩阵,这两个矩阵会在某种程度上save your life while learning econometrics...投影矩阵和消灭矩阵。

复习一下,OLS估计量是 ,然后对应的Y估计量是。所以,我们定义投影矩阵P为,这样就有了。也就是说,我们对Y进行了一次投影,然后得到了一个估计值。当然定义投影矩阵并不仅仅是写起来比那堆X简单,而是投影矩阵本身有着一系列良好的性质。

我们先来看把P投在X上会怎么样。显然,,也就是说P不会改变X的值(本来就是把一个东西投到X上嘛~自己投自己怎么会有变化的嘛)。

然后呢,对P进行转置,则,所以接下来

再定义消灭矩阵M。很简单,我们定义M为,其中I为单位阵(对角线元素为1,其他为0)。这样M又有什么性质呢?显然,也就是说M对Y的效果是得到误差项。而与此同时,M对于X的作用就是,所以称为消灭矩阵嘛。继续,进行转置,则,所以我们还有

OLS估计值的方差

再次友情提醒,X不是随机变量,所以不要跟我纠结为什么没有条件期望公式之类的东西...

扰动项服从时,或者大样本下,OLS估计量的方差为:

这里为样本方差,所以其分布为: 。这样一来,就有了一个t检验:

大样本下,就直接用正态检验好了。此外,如果我们进一步的有更多的同时检验的约束条件,那就是联合检验F。这个就不赘述了...

高斯-马尔可夫定理

顺便还证了一下高斯-马尔可夫定理...这个不像OLS,每次我可记不住他的证明,每次都是现翻书...

我就直接抄wiki了。

选择另外一个线性估计量,然后C可以写为 ,则D为k*n的非空矩阵。

那么这个估计量的期望是 :

所以,为了保证 无偏,则必有 .

继续求方差:

是一个半正定矩阵,肯定要比大~得证。

变量选择与收缩方法

为了降低测试误差(减少函数的复杂度),有时候会放弃无偏性而进行变量选择。这里首先就是Ridge OLS(岭回归)。还是算一下这个东西好了。

岭回归就是对估计量另外加一个约束条件,所以很自然的想到拉格朗日乘子法。ridge regression的目标函数为,

可以重写为

这样我们就得到两个一阶条件:

,所以有:

这里还可以看出,的取值都是对应的。

Lasso则是把改成,已经没有解析解了...

至于为什么叫收缩方法,可以将X进行奇异值分解,然后可以得出的方差将变小...我就不写证明了,感觉这一块儿讲的也不是很透彻。

Categories
读书有感

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

照例文章第一段跑题,先附上个段子(转载的哦~):

I hate CS people. They don't know linear algebra but want to teach projective geometry. They don't know any probability but want to use graphical models. They don't understand stats at all but still do machine learning like crazy.

喵,最近被问了好几次machine learning 和statistical learning的区别在哪里,我觉得大致如上吧。这也是为什么,对后面这个词我的好感稍稍好于前面那个的原因...科学总是有意义的嘛,不能总是依靠强力乱猜是不是嘛。

免责声明:以下个人见解部分局限于我个人的见识和思考范围,不适用于所有场景。请大家弃糟粕取精华,不可一言全信之。

-------------笔记+随想开始------------

高维空间问题

这一段主要是说大名鼎鼎的"维数灾难"。我们都知道有两个数字决定着OLS中X矩阵的大小,这就是 观测数目N 和观测变量的个数p 。一般说来,我们都喜欢N比较大,这样可以很容易的应用大数定律什么的。然而对于p,却是既爱又恨—我们当然喜欢可以观察到个体的很多个特征,但是所谓"乱花渐欲迷人眼",特征越多噪音也越多,搞不好预测的时候就会有麻烦(关于变量的选择问题,应该是下一节课的内容。心急的可以先看看我以前的一篇自学笔记)。

为什么维数增多的时候会麻烦呢?这里主要是随着维数增多带来的高维空间数据稀疏化问题。简单地说:

  • p=1,则单位球(简化为正值的情况)变为一条[0,1]之间的直线。如果我们有N个点,则在均匀分布的情况下,两点之间的距离为1/N。其实平均分布和完全随机分布的两两点之间平均距离这个概念大致是等价的,大家可稍微想象一下这个过程。
  • p=2,单位球则是边长为1的正方形,如果还是只有N个点 ,则两点之间的平均距离为。换言之,如果我们还想维持两点之间平均距离为1/N,那么则需个点。
  • 以此类题,在p维空间,N个点两两之间的平均距离为,或者需要个点来维持1/N的平均距离。

由此可见,高维空间使得数据变得更加稀疏。这里有一个重要的定理:N个点在p为单位球内随机分布,则随着p的增大,这些点会越来越远离单位球的中心,转而往外缘分散。这个定理源于各点距单位球中心距离的中间值计算公式:

时,。(很显然,当N变大时,这个距离趋近于0。直观的理解就是,想象我们有一堆气体分子,p变大使得空间变大,所以这些分子开始远离彼此;而N变大意味着有更多气体分子进来,所以两两之间难免更挤一些。看过《三体》的,大概会觉得这个很熟悉的感觉吧...四维空间下的"水滴"再也不完美的无懈可击,而一张一维的纸片就毁灭了整个地球呢。)

这个距离公式的推导就暂时不写了,好麻烦...大致是利用了各个点独立同分布的特性(完全随机情况下),把median距离变为以1/2概率大于中位数的概率集合公式,再进一步展开为单点距离累乘公式。

比如当p=10, N=500的时候,约为0.52,也就意味着有一半多的点离中心的距离大于1/2。

高维问题为什么是问题呢?回顾一下K近邻算法,我们用x的邻居来代替x,这样就希望他的邻居们不要离他太远。显然高维空间使得点和点之间越来越远。所以说,knn更适合小p大N即低维多观测量的情况,而在高维空间下可能会变得很麻烦。

这样,statistical learning的主要两个问题就总结完了:

  • 过拟合:为了控制预测误差,我们要选择适合的函数类。
  • 高维空间:随着维数的增多,我们面临着维数灾难。这对很多算法都有波及,主要体现在高维数据稀疏化。

回归的线性方法

这里主要是一些linear regression的东西,作为被计量经济学折磨了这么多年的孩子,我表示很淡定...此外还加上我们俗称的generalized linear models,即GLM。一些线性变换而已,无伤大雅。

这里一定要强调的是,在这里我们亲爱的X居然不是随机变量!多大的一个坑啊,我就华丽丽的掉下去了还问老师为什么无偏性不需要假设均值独立什么的... X不是随机变量意味着什么呢?X是人为设定或者决定的,比如我一天浇200 ml 或者500 ml水,然后看对于植物生长的影响。当时我真的是想"一口老血喷出来",这也太舒服了吧!要知道大多数情况下X也是随机变量哇,比如身高体重什么的。如果它不是随机变量而只有扰动项是独立的随机变量的话,整个计量经济学怕是要删掉好多篇幅了呢。我想说的只有,这群搞statistical learning的好幸福...

X不是随机变量的时候,为了满足无偏性的假设,只需要扰动项不相关且期望方差存在就可以了。期望不为0不要紧,回归的时候放进去常数项就可以了。

此外,对于任意一个正定阵W,我们都可以直接在回归方程两边乘以W,从而。也就是说,我们可以给X进行加权处理,加权矩阵W之后可以进行新的OLS估计,且可能会有对应的优良性质。加权最小二乘法我就不在这里复习了,学过计量的应该很熟悉,比如处理异方差什么的。

再就是我们可以给加上一些约束条件,这样的话最小化问题后面就可以简单的使用拉格朗日乘子法来解。

这次的收获之一就是OLS估计量的计算。在实践中,我们计算OLS估计值并不是直接使用,而是会事先进行QR分解(利用特征值来算)。即,我们把X分解为化为正交(酉)矩阵Q与实(复)上三角矩阵R的乘积。这样一来,

这样可解,计算时候的稳定性比直接求逆矩阵来的好很多,因为计算机必竟有数字长度的限制,各种位数带来的精度损耗最后会累积到估计量上。

最后就是高斯-马尔科夫定理,就是我们常说的BLUE估计量。我就直接拷贝这个定理了:

在误差零均值,同方差,且互不相关的线性回归模型中,回归系数的最佳无偏线性估计(BLUE)就是最小方差估计。一般而言,任何回归系数的线性组合的最佳无偏线性估计就是它的最小方差估计。在这个线性回归模型中,误差既不需要假定正态分布,也不需要假定独立(但是需要不相关这个更弱的条件),还不需要假定同分布

进一步的,如果假设扰动项服从正态分布,比如白噪声,那么的估计值也服从正态分布,y的预测值也服从正态分布,因此可以直接做一系列基于正态分布的假设检验。特别的,在大样本情况下,就算扰动项不是正态分布,我们也还是可以利用大数定律和中心极限定理...事实上一般也是这么做的。

本节课到此结束。老师没有一一推导无偏性最小方差这些性质,我倒是觉得对回归方法感兴趣的还是直接去看计量经济学吧。这东西水还是蛮深的。

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来衡量复杂度——但几乎实践中无法计算,没几个计算出来的。嗯,水很深哇。