[repost ]统计学习那些事

original:http://ift.tt/1jqkj07 编辑部按：本文转载Yang Can主页中的文章，稍有修改，原文链接请点击此处。 作者简介：杨灿，香港科技大学电子与计算机工程系。 主页：http://ift.tt/XUPHzP 在港科大拿到PhD，做的是Bioinformatics方面的东西。Bioinformatics这个领域很乱，从业者水平参差不齐，但随着相关技术（比如Microarray, Genotyping）的进步，这个领域一直风风光光。因为我本科是学计算机电子技术方面的，对这些技术本身并没有多大的兴趣，支持我一路走过来的一个重要原因是我感受到统计学习(Statistical learning)的魅力。正如本科时代看过的一本网络小说《悟空传》所写的：“你不觉得天边的晚霞很美吗？只有看着她，我才能坚持向西走。” 离校前闲来无事，觉得应该把自己的一些感受写下来，和更多的爱好者分享。 1. 学习经历 先介绍一下我是如何发现这个领域的。我本科学自动化，大四时接触到一点智能控制的东西，比如模糊系统，神经网络。研究生阶段除了做点小硬件和小软件，主要的时间花在研究模糊系统上。一个偶然的机会，发现了王立新老师的《模糊系统与模糊控制教材》。我至今依然认为这是有关模糊系统的最好的书，逻辑性非常强。它解答了我当年的很多困惑，然而真正令我心潮澎湃的是这本书的序言，读起来有一种“飞”的感觉。后来我终于有机会来到港科大，成为立新老师的PhD学生，时长一年半（因为立新老师离开港科大投身产业界了）。立新老师对我的指导很少，总结起来可能就一句话：“你应该去看一下Breiman 和Friedman的文章。”立新老师在我心目中的位置是高高在上的，于是我就忠实地执行了他的话。那一年半的时间里，我几乎把他们的文章看了好几遍。开始不怎么懂，后来才慢慢懂了，甚至有些痴迷。于是，我把与他们经常合作的一些学者的大部分文章也拿来看了，当时很傻很天真，就是瞎看，后来才知道他们的鼎鼎大名，Hastie, Tibshirani, Efron等。文章看得差不多了，就反复看他们的那本书“The Elements of Statistical learning”（以下简称ESL）。说实话，不容易看明白，也没有人指导，我只好把文章和书一起反复看，就这样来来回回折腾。比如为看懂Efron的“Least angle regression”，我一个人前前后后折腾了一年时间（个人资质太差）。当时国内还有人翻译了这本书（2006年），把名字翻译为“统计学习基础”。我的神啦，这也叫“基础”！还要不要人学啊！难道绝世武功真的要练三五十年？其实正确的翻译应该叫“精要”。在我看来，这本书所记载的是绝世武功的要义，强调的是整体的理解，联系和把握，绝世武功的细节在他们的文章里。 2. 关于Lasso与Boosting 由于篇幅有限，我就以Lasso和Boosting为主线讲讲自己的体会。故事还得从90年代说起。我觉得90年代是这个领域发展的一个黄金年代，因为两种绝世武功都在这个时候横空出世，他们是SVM和Boosted Trees。 先说SVM。大家对SVM的基本原理普遍表述为，SVM通过非线性变换把原空间映射到高维空间，然后在这个高维空间构造线性分类器，因为在高维空间数据点更容易分开。甚至有部分学者认为SVM可以克服维数灾难(curse of dimensionality)。如果这样理解SVM的基本原理，我觉得还没有看到问题的本质。因为这个看法不能解释下面的事实：SVM在高维空间里构建分类器后，为什么这个分类器不会对原空间的数据集Overfitting呢？要理解SVM的成功，我觉得可以考虑以下几个方面：第一，SVM求解最优分类器的时候，使用了L2-norm regularization，这个是控制Overfitting的关键。第二，SVM不需要显式地构建非线性映射，而是通过Kernel trick完成，这样大大提高运算效率。第三，SVM的优化问题属于一个二次规划（Quadratic programming），优化专家们为SVM这个特殊的优化问题设计了很多巧妙的解法，比如SMO（Sequential minimal optimization）解法。第四，Vapnika的统计学习理论为SVM提供了很好的理论背景（这点不能用来解释为什么SVM这么popular，因为由理论导出的bound太loose）。于是SVM成功了，火得一塌糊涂！ 再说Boosted Trees。它基本的想法是通过对弱分类器的组合来构造一个强分类器。所谓“弱”就是比随机猜要好一点点；“强”就是强啦。这个想法可以追溯到由Leslie Valiant教授（2010年图灵奖得主）在80年代提出的probably approximately correct learning (PAC learning) 理论。不过很长一段时间都没有一个切实可行的办法来实现这个理想。细节决定成败，再好的理论也需要有效的算法来执行。终于功夫不负有心人， Schapire在1996年提出一个有效的算法真正实现了这个夙愿，它的名字叫AdaBoost。AdaBoost把多个不同的决策树用一种非随机的方式组合起来，表现出惊人的性能！第一，把决策树的准确率大大提高，可以与SVM媲美。第二，速度快，且基本不用调参数。第三，几乎不Overfitting。我估计当时Breiman和Friedman肯定高兴坏了，因为眼看着他们提出的CART正在被SVM比下去的时候，AdaBoost让决策树起死回生！Breiman情不自禁地在他的论文里赞扬AdaBoost是最好的现货方法（off-the-shelf，即“拿下了就可以用”的意思）。其实在90年代末的时候，大家对AdaBoost为什么有如此神奇的性能迷惑不解。1999年，Friedman的一篇技术报告“Additive logistic regression: a statistical view of boosting”解释了大部分的疑惑（没有解释AdaBoost为什么不容易Overfitting，这个问题好像至今还没有定论），即搞清楚了AdaBoost在优化什么指标以及如何优化的。基于此，Friedman提出了他的GBM（Gradient Boosting Machine，也叫MART或者TreeNet）。几乎在同时，Breiman另辟蹊径，结合他的Bagging (Bootstrap aggregating) 提出了Random […]



via WordPress http://ift.tt/1mJNJOT