统计学习那些事
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 Forest (今天微软的Kinect里面就采用了Random Forest，相关论文Real-time Human Pose Recognition in Parts from Single Depth Images是CVPR2011的best paper)。