Categories
读书有感

Bootstrap + subsample: simple, efficient, then elegant?

继续昨天。早晨一起来,看到施老师的一句简短评论,瞬间人就清醒了。然后跟做错了事的小孩子似的,惴惴不安的跑到office里面,翻墙,开始下paper。

现在的节奏基本上是白天开会写代码,晚上回家看paper,哎,不看心里总觉得好惶恐。还好中间等车等了蛮久的,顺便就借着六七点昏黄的路灯把这篇不算太长的paper看完了。有趣的是等车的时候碰到一位同事,然后我俩就开始呱唧呱唧的聊起来统计推断了...不知道当时旁边的路人是不是一道黑线,幸好当时把ebay的牌牌藏在了衣服里面...

这篇不算长的paper是:Bootstrapping Big Data,UC Berkeley 计算机系一群人鼓捣出来的。idea很简单(符合第一标准,simple),就是在大数据上(无放回的随机抽样)取一些subsamples,然后在这些subsamples上面做bootstrap,然后把结果取平均数。

这样的好处显而易见,天生的分布式算法,把数据随机分布到各个计算节点就可以了。然后bootstrap也不用占那么大的内存了,空间时间都省掉了,所以符合第二标准:efficient。

最后,就是还是比较effective的,有着良好的渐进收敛性质。和直接的bootstrap相比,它不仅保持渐进一致,而且有着更高的收敛速度,还是天生并行的...过年回济南的时候joke童鞋(高中同学)去火车站接我,然后我们就兴致昂扬的聊起来大数据和算法并行问题了...是不是有点天雷滚滚?哇咔咔,大过年的...好久没见竟然是如斯叙旧,汗。

此外,还可以结合binning的思路做一些weighted calculation,这样又进一步节省了时间。

不知道这样是不是就足够的elegant了...我看了一眼converging rate 还是比较好看的。伪代码思路也是简单得很。还可以用在各种现成的线形非线性、参数非参数模型上,真是瞬间变身并行高富帅。貌似和前段时间看到的rmr2包里面做OLS并行的思路有点像,待我细细研究一下。

algorithm

唯一的concern就是这东西更适合hadoop而不适合teradata,哎。我没法在TD上控制节点的分配,这个比较讨厌。Hadoop可以直接写并行map reduce,就会方便很多了。

 

先看了这一篇简介,后面慢慢地研究一些理论证明什么的,有点too good to believe...还是先找点数据测试玩玩吧^_^
efficiency

Categories
读书有感

再读「数学之美」

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

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

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

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

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

Categories
网络新发现

Machine learning for KIDS?

在慢慢火车旅途上,看看书还是不错的消遣。第二个kindle也挂了之后,只能借助ipad勉强看看书了。还好吧,至少还能集中注意力,不会手贱的不停刷微博什么的。

离开上海之前,两天奋战看完了备受推崇的「三体」三部曲,不禁对作者的想象力、天文、物理功底所深深折服。总有一段时间觉得自己的思维格外的开阔,喜欢这样智力上的挑战。而接下来打定主意在路上看的,第一本就是说「machine learning for hackers」,听说是R与数据挖掘教程之一,很多人多次提及过,思喆大哥貌似还评论过,却忘了大家是褒是贬。当然,这其中还有一层原因是,适合自己的才是最好的,就像我从来不能如同在经济学家面前声称自己学过经济学一样,在统计学phd面前号称自己学过统计学(cannot speak the statistics language well)。根基差太远。

然而看过了这本书之后,只想问一句,are you kidding?通篇都是各种回归就罢了,还常常一整页就一幅图(至少我看的版本中如此),每个例子都有配图(当然我不否认可视化对于帮助理解数据的意义,但亲啊,是不是有点多了啊?),这样稀哩哗啦的居然凑了300多页。我只想说,如果我的小册子也这么写,突破500页指日可待啊。

好吧,回到价值评价。这本书信息量真的不怎么大。我不是machine learning科班出身,没学过这东西的发展史,不知道这些模型的历史地位和演化过程,只是断断续续、这里一点、那里一片的接触了一些模型(当然回归模型除外,计量的招牌菜啊,虽然我一度觉得我计量学的也不咋地)。看完这本书,先是简单的线性回归,然后polynomial拟合,然后是logit回归等等,中间加上一些莫名其妙的检验指标,各种看着不爽。至少,以一种检验和model selection的形式出现好不好,显得多少严格一点嘛。

后面是支持向量机,然后居然还简单的涉及了sna。不过当我看到gephi的时候....好吧。这作者真心喜欢可视化啊。

说到机器学习,可能我没什么评头论足的资格。不过仗着最近看了一下「数学之美」(虽然只是06年的google黑板报版),还是觉得对这个领域的大致思路有所了解的。关于learning,个人认为除了各种回归等常规prediction之外就是bayesian规则下的模拟了。后者的话,个人倾向于"按需定制",模拟还是好好的从头开始写代码比较稳妥。搞不懂这本书的思路,不知道target group是哪群。

有的时候各个学科还真是殊途同归的。我所接触的很多学科的方法,无非的指向只有一个:如何从信息中提取信息,或者更简单的,如何降维。从这个角度看,经济学也没有落后太多嘛,只是出发点和原始信息集不一样。其实,平心而论,经济学的思维方式基本是数学分析(演绎法)+统计学(归纳法)的结合,虽然到个人层面上各有所侧重,但还是很大程度上相辅相成的,没法一条腿走路。所以,有志于挑战自己智力和创造力的同志们,可以偶尔学学经济学哦~嘻嘻。绝对是系统的对思维方式和分析能力的训练。

Categories
读书有感

略读「数学之美」

继前段时间匆匆瞄过「浪潮之巅」后,注意到最近作者又出了另一本书,「数学之美」,便寻思着一定要有时间读一下。搜了一下才发现原来早在06-07年,这些就在google黑板报上连载了。唉,当年是有多么的孤陋寡闻,才会浑然不知--说不定那年要是看到了,就会直接投奔CS去了,自此和econ无缘了。哈哈,时间不能倒流,玩笑而已。

google黑板报上的版本不长,昨天从杭州回来的高铁上匆匆便略读完了。从自然语言处理,到输入法,到语音识别,到排名算法,到anti-spam;从隐性马尔科夫模型,到贝叶斯网络,到pagerank,到"简单而有效"的必杀刃...算法的魅力在作者笔下翩然而现,不禁勾起了我心底的贪婪。看到优雅的条件概率公式,恩,世界被数学描述的真的是挺美好的。

不知道为什么,接触了很多CS出身的出色的工程师们,一边惊叹于他们卓越的coding能力和创造、组合工具的能力,另一边却又不知为什么总隐约觉得他们的统计学背景并不是那么的solid-换言之,统计分析的sense远远比不上熟练应用算法的能力。虽说术业有专攻,可是算法这么迷人的东西...好吧,我总是对于美好的事物,不由自主的表现出贪婪和心向往之。

看看接下来的一段时间,如果确实无聊,可以考虑静下心来学一段时间的算法,很多算法模型都是知道个大概却没有那么确切,心里也难免惶惶不可终日。有的时候确实是眼高手低了,好多东西都没有深深地挖掘过。浅尝辄止不是一件好事恩,还是自己推导出来的东西更能铭记于心。

话说,明天的R会议,我会发挥娱乐大众的功用,讲一些统计分析好玩的应用。基本是上次给松鼠会讲的「别让数字吓到你」的升级版,加入了一些稍稍高级的分析方法,然后案例也有增有减。为了吸引观众,我只能无情的拿cos开刀,有一些关于cos的内幕会被无情的曝光,还有依照惯例现场观众会被调戏--嘻嘻,不调戏你们一番你们怎么能记得住呢?这才不枉我又花钱又花时间跑到北京来一趟嘛。希望明天我的状态会比较好吧,喵~

Categories
读书有感

have to make a note

前几天说要看intro to algorithms,然后居然真的看起来了。我都服了自己了。现在已经达到追美剧的水平了(我就去down了个MIT的公开课,也没字幕什么的,就直接当看美剧了),频率基本一天一集,时间大都在晚上9点以后。我为什么说是看美剧呢,看美剧前总是很自责的跟自己说不要浪费时间,看一会儿就好,然后不知不觉就看完了;看这个教程也是,劝着自己要慢点要慢点,不要一口气看太多,结果每次都是欲罢不能的非要看完一集不可。OMG...我突然发现自己原来这么喜欢做学生的状态啊,恍然一下子回到了2010年冬天lugosi的real analysis课程上,那么的欲罢不能啊!

今天看完了第三集,讲的是各种奇妙的算法。前面的都还好,基本在他讲的时候我就可以跟着想出来后面大概是什么……直到Fibonacci数列,突然看到这种东西,顿时眼前一亮!怎么就没想到可以用矩阵乘法哩?后面看到了矩阵乘法的算法化简思路,明明知道可以用分块矩阵,原来是这样磨来磨去才可以达到O(N^3)一下的啊,也终于明白前阵子看到一篇文章说什么“矩阵乘法的时间复杂度降到2.xxx了”是什么缘故了;最后看到那个"H"形状的树,刹那间明白为啥那么多geek都痴迷于分形了……recursion啊,divide and conquer,真神奇!

不得不在这里稍稍记录一下,原来算法真的这么好玩啊!各种后悔当年没有去学这门课……还好,亡羊补牢,不晚不晚,至少这门课的什么先修课知识(主要是一堆数学知识)我都知道,所以现在还能跟得上看得懂,欣慰+无限庆幸中……数学,或者说逻辑,永远都是那么的好玩啊。

----
最近难得在上海的零碎时间,一直流连在上海图书馆里面。突然间发现自己还是这么喜欢书香的味道,喜欢被书架环绕的氛围(一下子仿佛回到了大三烤G的那段时间),喜欢从架子里取出红皮的AER慢慢翻看(不知为什么,看QJE什么的次数越来越少,AER仿佛成为了我和经济学的最敏感连系),喜欢获取知识的感觉。说白了,喜欢自己做学生的状态吧。清净,充实。