红树林曰

Statistics & Computation

[Note]ESL笔记-第12章 Flexible Discriminants

| Comments

SVM和Kernel

这一章的前半部分主要讲SVM,SVM的具体推导过程我就不赘述了,网上一堆一堆的。简单提一句,对偶问题的转换,是对求Lagrange函数的下界,转换为的优化问题,这个问题就是原问题的对偶问题,相应的就是要最大化这个对偶问题了。由于这是个凸问题,且满足Slater条件,对偶问题的解就是原问题的解了(对偶间隙为0)。

原问题:

对偶问题:

书上提到说这个对偶问题相比原问题更简单(“simpler convex quadratic programming problem”),这点我并不能理解(诚意请教)。我觉得两个问题是一样难的,只是后者的优势在于的点积,可以自然而然地引入Kernel。

Thrift 0.6.1在OSX 10.9+上的编译问题

| Comments

由于工作上的一些原因,需要用到thrift 0.6.1版本,这个版本实在过于老旧,当时C++11还处在试验阶段。其中用到很多C++11的语法特性,今天已经废弃了。而OSX自10.9起由libstdc++全面转向libc++,从而导致一些编译上的问题。

我修改了一下这个版本的thrift源代码,使它可以在OSX 10.9+上编译通过。Patch见这里,如标题所言,configure时请指定CXXFLAGS=”-std=c++11”。

[Note]ESL笔记-第11章 Neural Networks

| Comments

这一章的内容比较简单,主要介绍了三个东西:PPR, NN和Bayesian-NN。其主要思想在于从输入构造出线性特征,然后对这些特征做非线性组合,用于预测。

Projection Pursuit Regression

PPR是可加模型(additive model)的成员,在线性模型上加一个非线性变换,然后把多个这样的模型加起来,形式如下:

如果取得足够大,并且选择合适的,那么PPR可以近似任何连续函数。PPR是一个很general的模型,可以看到如果,那么类似LR这样的模型就是它的一个特例。

书上用squared loss举例,讲解了PPR的求解方法(Gauss-Newton):在处做一阶泰勒展开后求解minimum,如此迭代直至收敛。

Neural Networks

这一节主要介绍仅有一个hidden-layer的神经网络。假设我们已经把截距加入了各weight中,那么这类NN可以分解为:

  • Input: 维向量;每一维表现在图上是一个input cell
  • Hidden(bottom): ;参数为是一个标量,表现在图上就是一个neural cell
  • Hidden(top): ;参数为是由所有串起来的一个向量
  • Output: 是一个标量,表现在图上就是一个output cell,是由所有串起来的一个向量,例如softmax函数

注意到这里hidden-layer和PPR的模型形式是一致的,区别在于PPR的函数是非參的,而这里的则是一个更简单的函数;另外当是一个identity函数的时候,NN就退化为一个线性模型了。

[Note]ESL-第10章 Boosting and Additive Trees

| Comments

这一章从AdaBoost开始,讲到boosting-trees,这些方法归结起来,其实都属于additive model,即。如果选定了基函数,并且把的形式限定为系数和基函数的乘积,那么写成递归的形式就是

这就是书上Algo-10.2的Forward Stagewise Additive Modeling,其中是待优化参数,第轮的优化目标是

这其中,损失函数的不同,以及优化方式的不同,产生了不同的算法。Adaboost是取的结果;而GBM则更进一步,从优化方法下手(去fit损失函数的梯度),不再依赖exponential loss的特殊结构,从而可以apply各类损失函数,既能用于分类,也能用于回归。

[Note]ESL-第9章 Additive Models, Trees, and Related Methods

| Comments

ESL的笔记很久没有更新了,最近确实也比较忙,但更多的还是拖延症。笔记越写越详细,也间接地导致惰性越来越大,还是要经常自我鞭策才行啊。

书上对MARS的讲解其实非常简略,我特意去拜读了Friedman的原作,才对这个模型的来龙去脉有了一些大致的把握,对additive model和spline也有了更进一步的认识。

广义加法模型

顾名思义,这类模型试图用来fit一个目标,这个目标广义而言是,其中被称作『link function』,书中列举了以下三种:

  • ;对应于是是高斯的假设
  • ;就是logistic regression
  • ;对应于Possion假设

如果确定了响应变量,那么广义加法模型的loss function是这样的:

这个其实和书的(5.9)式是一样的,这不过在第5章只有一个,而这里是很多的加和,于是表达能力也更强。可以是任意的函数,从而在模型中引入非线性。PRSS的惩罚项是用于限制函数的曲率,从而限制overfitting.

书中的Backfitting算法,就是每次只求解其中一个,求解的时候固定其他的是个算子,对于cubic smoothing spline而言,就是书上(5.14)式的

基于树的模型

树模型从一般意义上讲,是additive model的一个特例,即。只不过这里的是基于对变量空间的划分,给定了个划分,则

于是,树模型的数学表达就是下面这个样子,其中是0/1 indicator函数,是未知参数:

[Note]ESL-第8章 Model Inference and Averaging (三)

| Comments

这一章的最后部分介绍了一些多模型组合的问题,这一章被称为『Model Averaging』是因为被用于组合的这些模型彼此是处于同等地位,和boosting的『提升』不同,更像是一种『平均』

Bagging

Bagging使用了bootstrap重抽样。具体来说,对一份训练集,我们可以抽样得到一组bootstrap样本集:,然后在这每一份样本集上训练得到一个模型.最终的预测值是

Bagging通常能降低一个不稳定模型的variance,从而改善性能。对此一个简单的解释是,求平均能在保持bias不变的基础上降低variance。

书上特地指出了,对于一个0/1分类器而言,bagging会提升好模型的性能,但对于一个糟糕的模型,这会变得更坏。例如有一个数据集,所有的都是正例,有一个(随机)分类器,以0.4的概率判定为正例,0.6的概率判定为负例,那么在这个特殊的数据集上,该分类器的误判率是0.6,而bagging之后,由于大部分(60%)的会将判为负例,那么结果是所有的数据都判断失误了,误判率为1.0

更一般的Model-Averaging和Stacking

Bagging是一种基于bootstrap的averaging方法,这里我们考察更一般的averaging:我们从一份训练集上得到了多个模型,这些模型可以是同一类(比如都是岭回归),也可以是不同类(比如岭回归和决策树),怎样组合这些模型给出的预测?首先从bayesian的角度来看。

[Note]ESL-第8章 Model Inference and Averaging (二)

| Comments

1. EM算法

假设有数据,其中表示数据是可见的,而表示这个数据不可见(因为种种原因,比如数据丢失,或者是人为故意造出来的hidden variable),完整数据有分布,写成log-likelihood:

由于的值我们不知道,最简单的办法就是把积掉:

这样会带来的问题是显而易见的:对数中存在积分,当你对中任何一维求导的时候,分母上总是会出现一个积分项,这使得即便对于很简单的分布函数,你都很难将特定的参数分离出来,得到闭解几乎是不可能的。

但是,为什么要将隐变量积掉呢?EM的想法是把用它的期望代替,其中

这就是EM算法的E-step,这里把写作,是因为这是上一次迭代的结果(初始给定一个随机值),于是对于第步iteration,有

E-step:计算

M-step:最大化,得到新的,进入下一轮迭代。

注意容易计算是因为是已知的模型,除以一个归一化项就是了。

对于书上举例的高斯混合模型而言,引入了一个missing变量,表示第个高斯模型是否active,而,书上Algorithm-8.1的就是(因为是二项分布)

[Note]ESL-第8章 Model Inference and Averaging (一)

| Comments

这一章的开头4节都在讲bootstrap。Bootstrap在技术上非常简单,用『有放回的重抽样』就可以概括;但它背后的原理极其复杂,基于一个被称为Edgeworth的正态展开(类似于泰勒级数),特别当针对一个pivot做bootstrap时,可以得到二阶的精度。ESL这一章并没有探讨bootstrap的原理,而主要描述了方法和现象,Efron有一本专门的著作『An Introduction to the Bootstrap』。

通过Bootstrap抽样,我们可以通过计算机对给定数据的性质进行估计,包括样本均值的方差,样本方差的方差,估计值的置信区间,等等等等。待估计的这个估计量是任意的,举例来说,如果我们要估计某个估计量的方差,那么我们只要首先生成组(参数/非参数的,后面会解释)bootstrap样本集,然后就能得到估计

其中表示通过第组中样本得到的估计量,表示所有个估计量的平均值,一般bootstrap抽样得到的估计量都用上标星号表示。

所谓非参数bootstrap是指bootstrap样本抽样来自原始的样本,不涉及参数估计;而参数的bootstrap会假设一个样本发生模型,然后从样本中推断出模型的参数(一般是MLE),最后从估计的这个模型中sample出bootstrap样本(后面有例子具体说明)。

[Note]ESL-第7章 Model Assesment and Selection (三)

| Comments

这一章最后介绍了两个extra-sample的评测指标。这部分有些东西还是没太看明白,姑且先浅尝辄止吧。

Cross Validation

把数据集分成份,其中份用于training,份用于validation,运行次,取平均:

其中表示训练集不包含第个点的模型。如果,那么相对而言CV估计更接近于(可参考本章第一篇笔记),因为每个fold的training set都差不多;而对的CV,估计更接近于

后问介绍了使用CV的一些正确和错误的方法,关键在于要严格区分评测集和训练集,评测集中的数据不应该在训练集中出现,不管以何种方式。

Bootstrap

Bootstrap就是有放回的重抽样,产生个训练集后,进行评估:

其中表示不包含第个点的bootstrap样本集的集合。书上又说,平均而言,在一个bootstrap样本集中,大约有个样本在这个样本集中是唯一的,如此一来当模型在训练集大小为处很敏感的话(例如样本数超过对模型效果会有大的提升),那么就会高估模型的bias,于是引入了『统计量』:

[Note]ESL-第7章 Model Assesment and Selection (二)

| Comments

Laplace Approximation

这一部分是BIC推导的基础,主要参考PRML 4.4节。

在Bayesian框架中,我们常常会遇到后验分布形式较为复杂,导致诸如无法积分之类的问题。有很多近似方法来解决这类问题,比如EM、MCMC等等。这里要介绍的Laplace近似,试图用一个高斯分布来近似任意分布,假设

其中是归一化因子,后面会看到,在Laplace近似中,并不需要知道这个归一化因子。

现在我们的目的是要用高斯分布来近似,很显然,高斯的波峰应该和的波峰契合,于是我们首先求得的驻点(mode),即,也即

我们知道,高斯分布有一个性质:取对数后就是随机变量的二次函数。于是我们就想到对原分布的对数在点处做泰勒近似: