Categories
读书有感

≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记(十七):神经网络

神经网络,这是要开始Deep Learning了么?

神经网络的历史和大起大落还是可以八卦一下的...

第一波:人工神经网络起源于上世纪40年代,到今天已经70年历史了。第一个神经元模型是1943年McCulloch和Pitts提出的,称为thresholdlogic,它可以实现一些逻辑运算的功能。自此以后,神经网络的研究分化为两个方向,一个专注于生物信息处理的过程,称为生物神经网络;一个专注于工程应用,称为人工神经网络。

第二波:上世纪80年代神经网络的研究热潮。带反馈的神经网络开始兴起,其中以Stephen Grossberg和John Hopfield的工作最具代表性。很多复杂的认知现象比如联想记忆都可以用反馈神经网络进行模拟和解释。一位在神经网络领域非常资深的学者跟我聊天时说,在那个年代,只要你的文章跟神经网络扯上点关系,无论什么杂志,都很容易发表。

第三波:直到2006年深度网络(deep network)和深度学习(deep learning)概念的提出,神经网络又开始焕发一轮新的生命。深度网络,从字面上理解就是深层次的神经网络。至于为什么不沿用以前的术语“多层神经网络”,个人猜测可能是为了与以前的神经网络相区分,表示这是一个新的概念。这个名词由多伦多大学的GeoffHinton研究组于2006年创造。事实上,Hinton研究组提出的这个深度网络从结构上讲与传统的多层感知机没有什么不同,并且在做有监督学习时算法也是一样的。唯一的不同是这个网络在做有监督学习前要先做非监督学习,然后将非监督学习学到的权值当作有监督学习的初值进行训练。

上述来自:http://www.caai.cn/contents/118/1934.html

有没有感觉最近deep learning热得一塌糊涂?好像是个人都知道有这么个词儿但是真正知道他干什么的、怎么来的的人却不怎么多。嗯,貌似从这节课开始,要掀起deep

learning的篇章咯。顿时感觉好洋气哇。

----------正文的分割线-----------

这节课先介绍七十多年前的Perceptron模型。

1. 神经元

大致就是这样一张图片。神经元细胞有个大大的细胞核,然后有个轴突。如果神经元细胞拼在一起,可以构成一个神经网络。

perceptron

(我觉得这个细胞模型和后面的东西其实没太直接的联系...就是一个很好看的图...)

2. Perceptron模型

Perceptron模型有若干输入:,标记为序列。

每个输入都有一个权重(某种程度上可以理解为信息损失):,标记为序列。

最后每个“细胞”还有一个偏(门限):b,即我们常说的常数项截距。

最终的状态:

输出:,比较简单的情况下,可以是一个二元输出函数,比如或者写作。但是比较讨厌的是这个函数不可微,所以我们可以转成一个可微的函数(有点类似logistic regression的思路,用概率的密度函数来做)。

sigmoid

可微的情况下,这个输出就是:,这样就可以做成一个光滑的曲线了。

3. Perceptron算法

给定一批数据, 我们希望求得使得,如果;否则,(即

算法:先是我们可以不断重复的无限复制数据:

然后初始化:,

开始循环:

For

IF ,then

定理 如果存在w使得成立(即平面线性可分),则Perceptron算法在有限步收敛。

证明:

  • (仅计算改过的)
  • 存在使得,那么我们有,同时我们有这样就会有,当k趋近无穷大的时候,显然左式不成立。所以必有在某个k的时候停止迭代。

4. 推广至多类——Collins算法(2002)

(1) Collins表述

给定 ,求w使得,除了外最大。这样

(2)算法:,

初始化:,.

For

计算

输出:

(3)定理。若为线性平面可分,则在有限步内收敛。

Categories
读书有感

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

第十五章 随机森林(Random Forest)

终于讲到这个神奇的算法了...若是百年前的算命术士们知道有此等高深之术,怕是要写成一本《随机真经》作为武林宝典世代相传了吧?猜得准才是王道嘛。

p.s. 以前没看过的童鞋不要急,这节课只是从boosting直接跳讲到十五章,并不是已经快结课啦。

---------------

1.定义和算法

算法:

  • 1. For b = 1 to B
    • 生成一个自生样本(via bootstrap)
    • 生成树:
      • 随机选取m()个变量(相应的,取了m维子集)。一切的神奇都在于这里是随机降维的。
      • 生成树
  • 输出(即森林)。

随机森林算法的参数主要就是决策树的参数,用来控制树的生长的:保证每个叶子中的实例数不大于

应用

1) 回归 在回归的情况下采取均值,最终输出的就是.

2) 分类 分类的情况下进行投票,,得票最多的那类获胜。

参数

总结的来看,参数主要有如下几个:

  • B:试验次数。一般为几百到几千,所以是computational intensive.
  • m:降维的力度。作者建议回归的情况下采用,然后分类的情况下采用
  • :建议回归的时候设为5,分类的时候设为1(彻底分到底)

伪代码

其实上面已经写的比较清楚了...我只是再抄个伪代码过来而已。

select m variables at random out of the M variables

For j = 1 .. m

If j'th attribute is categorical

(see Information Gain)

Else (j'th attribute is real-valued)

(see Information Gain)

Let (this is the splitting attribute we'll

use)

If j{*} is categorical then

For each value v of the j'th attribute

Let = subset of rows of X in which . Let

= corresponding subset of Y

Let = LearnUnprunedTree

Return a decision tree node, splitting on j'th attribute. The number

of children equals the number of values of the j'th attribute, and

the v'th child is Childv

Else j{*} is real-valued and let t be the best split threshold

Let = subset of rows of X in which . Let

= corresponding subset of Y

Let = LearnUnprunedTree

Let = subset of rows of X in which . Let =

corresponding subset of Y

Let = LearnUnprunedTree

Return a decision tree node, splitting on j'th attribute. It has two

children corresponding to whether the j'th attribute is above or below

the given threshold.

2. 为什么要“随机”

bootstrap:通过多次重抽样减小误差。

考虑下面的情况:

1) 为随机变量,且,

(i)当相互独立的时候,,且

(ii)当相互不独立的时候,我们有。这样接下来就有

如斯,仅使用bootstrap的话压缩的是方差的第二部分,而随机选的的M可以减小样本之间的相关性,从而减少不同树之间的相关性。

2)OOB(out of bag)实例

OOB的概率:。这样就是说,在一次抽样中约有1/3的样本没有被抽到。

两次bootstrap抽样的话,样本约有40%的重叠,这样的重叠概率会影响到上面的(ii)中,两次抽样得到的样本重叠很高,相互不独立。

这样我们用67%的样本训练数据,用剩下33%来测试。

3. 其他应用

1)变量的重要性(feature selection,俗称的特征选择)

第一种方法可以和上节课梯度树那里的一样,用来刻画变量的重要性。

第二种方法则是比较有意思。对于一棵树,我们用OOB样本可以得到测试误差1。

OOB样本大概长成这个样子:

,样本量足够大的情况下

然后随机改变OOB样本的第j列:保持其他列不变,对第j列进行随机的上下置换,得到误差2。至此,我们可以用误差1-误差2来刻画变量j的重要性。当然这里loss function可以自己定。这里的大致思想就是,如果一个变量j足够重要,那么改变它会极大的增加测试误差;反之,如果改变它测试误差没有增大,则说明该变量不是那么的重要。(典型的实用主义啊!管用才是真,才不管他什么证明不证明呢!自从开始接触机器学习的这些算法,我真的是被他们的各种天真烂漫的想法打败的一塌糊涂,只要直觉上过得去、实际效果看起来比较好就可以了呢,规则真简单)。

2) 相似图(proximity plots)

除了用户变量选择之外,Random Forest也可以给出各个观测实例之间的相似度。

Proximity plots记作在一个叶子结点同时出现的次数,其实大致就是一个相关性矩阵的样子。思想其实就是,如果两个观测样本之间比较相关,他们在树分枝的过程中就比较难以分开,所以会经常一起出现。我们故而可以用一起出现的次数给这种相似程度打分。

树类算法

至此,我们大概一口气过掉了所有跟树相关的算法。

先是单一的决策树,然后是基于已有弱分类器的改良算法,比如梯度树,然后就是和梯度树不相伯仲的随机森林。我感觉随机森林真的是起了一个好名字,在我没学机器学习之前就听到无数人跟我说起随机森林,而梯度树却只是正儿八经开始看了才记住的名字...

下下周开始,会依次讲到神经网络和SVM...看来supervised learning就快拉上帷幕咯。

Categories
读书有感

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

梯度树提升算法(GTBA, gradient tree boosting algorithm)

继续boosting类算法哎。小小预告一下,下节课会直接跳到随机森林,老师貌似是想把各种分类器都一下子讲到,然后有点前后照应的比较~真有意思,若是以前扔给我这种问题我肯定run一个logit regression就不管了,现在倒是有各种线性的、广义线性的、非线性的模型可以试着玩了,爽哎~

------------------

1. 自适应基函数模型

小小的复习一下上节课那个框架。

1. 数据。

2. 模型。 为基函数模型,其中成为基函数集合。为参数。

3. 损失函数(准则)。 为损失函数,然后就转为一个优化问题:

4. 算法。 前向分步算法。

  • 初始化:
  • 迭代:For m=1 to M,
  • 输出

在此框架之下,除了上节课的Adaboost之外,还可以套用多种其他的基函数,然后1)定义损失函数 2)给出迭代那一步的优化算法,就可以实现一种boost提升算法了。

2. 应用回归问题

先采用均方误差的损失函数,定义,这样就可以得到

然后定义:

。这里之后用回归树来求的话,就是梯度回归树算法。

梯度回归树提升算法

  • 初始化:
  • 迭代:For m=1 to M,计算。由用回归树求得.
  • 输出

3. GTBA,梯度树提升算法

先吹捧一下:这个算法就是此书作者本人开发的,然后已经搞出来了软件包,可以做回归也可以做分类,貌似效果还胜过随机森林(当然是作者自己给出的那些例子...)。

损失函数为可微的。

我们的优化目标是,也就是说实际上我们不是直接对进行优化,而是仅仅在所有观测的数据点上优化,所以仅跟在这些观测点上的值有关。感觉这里就是说,我们使用有限的观测到的信息来推断一个连续的函数,然后类推并用于其他未观测到的点。

定义:

,这样这个问题就从一个直接优化的泛函问题转化为一个优化多元函数的问题...而对于一个多元函数,我们可以直接用梯度下降法。定义梯度为:

,这样。类似的,我们可以定义,其中。累加起来,就是

,这里可以是常量也可以随着改变。

定义完梯度下降之后,就是GTBA算法了。

  • 初始化。
  • 迭代:For m=1 to M,计算,然后由用回归树求得
  • 输出

一些梳理

1. 参数。这里显然有如下参数需要设定:

  • M:迭代次数。这是这个算法最主要的参数,需要用Cross-validation来算。
  • J:树的大小。建议4-8,默认为6。
  • :收缩系数。这里可以加上这个参数,决定收缩的速度,0-1之间。
  • :次采样率,0-1直接,默认0.5。用于做subsampling。

2. 特征变量评价

这个算法的一大优势就是可以给出各个自变量的评价。比如的时候我们可能面临特征变量选择问题。

用t表示树中的节点,表示t节点所用的变量,表示t节点产生的均方误差的减小值。之后定义:

,可用这个值来刻画变量的重要性,从而进行特征评价。

3. 通用工具

该算法对于数据无特殊要求,有一批都可以扔进去试试,故可以作为其他算法的benchmark。

此外,从贝叶斯分类器的角度,我们要找的是,这样除了原有可以观测到的之上,还可以衍生出一个向量,即,第k个位置为1如果观测到的对应第k类。一下子就可以扩展整个数据集,也可以进一步对每类都赋一个概率,不单单是0-1这样。

Categories
读书有感

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

开春,复课。

一句无关的话...今天打开Google Reader看到7月份要关的提示,无限悲伤。看着落园若干RSS源里面累计800+的读者,只能说句bless...2008年开始使用,到现在,伴我度过了多少读书时光呀。不过确实也衰落了,高峰的时候一个RSS源就有600+读者,现在也只剩一半了。写博客,越来越像一件出力不讨好的事情了。

--------正文开始---------

提升与梯度树

1. Boost(AdaBoost)

这里讲的AdaBoost是仅针对二类分类器的提升。大致的思想就是,给我一个弱分类器,还你一个强分类器。听起来蛮神奇的对不对?

先说算法实现。

第一步:初始化。,权重初始值

第二步:迭代。

for m = 1 to M

  • 根据已有算法(即弱分类器)和{}得到一个分类器.
  • 计算误差:,这里我们把权重进行归一化。
  • 计算权重:
  • 修改样本权重

也就是说,我们不断的生成新的权重,当分类器分错的时候更改权重。

第三步:输出。最终的分类器为前面的加权。

这样就实现了从一个弱分类器改善到一个强分类器。这里弱分类器是指误差比随机猜的1/2少一点。

另注:在修改权重那一步的时候,也可以定义,然后,这样在最后的时候也可以改成。总之这里的直觉是,如果分对了,那么权重下降;反之,分错的时候这些样本的权重上升。最后take average就可以了。

2. 自适应基函数模型、前向分布算法

之所以上面又引入,便是为了更好地理解这一类模型:自适应基函数模型。

1. 我们称 为基函数模型,其中成为基函数基。注意这里和GLM有很大的不同,广义线性模型后面的为确定的。

2. 前向分步算法。

数据集记作。定义一个损失函数,比如常见的均方误差,

,或者0-1准则。

然后步骤为:

  • 初始化:
  • 迭代:For m=1 to M,
  • 输出

这样我们就把这个最优化问题转变成了M步,每步只做一个参数的最优化(近似方法)。

3. 指数损失函数与AdaBoost

有了这么一个一般性的框架,我们就可以套用具体的形式。

1. 定义指数损失函数:

2. 两类分类、指数损失函数的自适应基函数模型。

前向分布算法:

(i)

定义

这样上式就可以化作

(ii) 固定,优化.

然后最小化,则。假定已被优化,然后继续。

(iii)优化

取一阶条件FOC,则有

这样最后

这样就看出来上面那个AdaBoost里面的是怎么来的了吧?

(iv) 回到AdaBoost

看出来最后的AdaBoost雏形了吧?

Categories
读书有感

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

呃,我觉得我的笔记稍稍有点混乱了...这周讲的依旧是线性分类器,logit为主。anyway,大家将就着看吧。

logistic regression

首先我们考虑最一般的,有K种分类的场合。依旧,我们用来代替作为观测到的分类结果,那么则有:

为最优的预测结果。这里我们希望找到一种线性的形式,还需要使用一些单调变换保证预测值在之间。因此,我们对于每个分类,假设

进一步的,我们取任意类K作为对照组,且各组相加概率之和必为1,所以有:

所以,最终得到两组之间的概率比值为:

最后求解的时候,就是直接用最大似然准则,来求解

这个最大似然函数计算起来比较麻烦,通常很多是数值解。下面以为例,来展示求解过程。

首先我们这个时候有两类,不妨记作1和0,则

则它的对数似然函数:

然后我们求导可得:

之后可以用牛顿法迭代求数值解:

其中二阶导数部分可以化简为:

经过简化之后,这里相当于加权的最小二乘法,目标函数为

所以整个算法可以写作:

0. 令或任意起始值

1. 计算矩阵.

2. 新的.

3. 重复1,2步直至收敛。

这类方法成为IRLS(不断重写的加权最小二乘法)。

LDA和logit选择

其实也没什么定论,两者均为线性,只是一般我们认为LDA需要假设联合正态且方差相等,比较强;而logit假设没有这么强,相比而言更稳定。

perceptional分类器

perceptional分类器是一类相对简单的分类算法,以两类场合为例。为了方便起见,我们假设两类为1和-1,则目标是找出一条直线可以完全分割出来两群点。这里转化成数学的语言,就是找到W使得

或者简化为:

算法也很简单:

1. 给定任意的W值,比如0. 如果,出错。

2. 令新的,重复第一步。

这里可证一个定理:如果原数据集是线性可分的(即W存在),那么在有限步内perceptional算法收敛。其实从第二步可以看出,这样的改进总是趋近于目标的:,一定是在逐步增加的。

同样的算法推广到多累场合,我们就需要引入特征向量,使得条件概率。这样我们的目标就是找到使得

同样的,从0开始,当时,,直至收敛。

不过有意思的是,实践证明,最后使用训练过程中的的平均值效果会更好,而不是最终的值。

--------笔记结束,废话开始--------

到这里,分类器吴老师已经介绍了三类:LDA,Logit和perceptional。其实我一直觉得比较好玩的是分类器和聚类方法的对比——虽然一个是有监督,一个是无监督的学习,不过有的时候我们就算有的观测值也不一定直接就去用——聚类方法某种程度上显得更加自然一些。这也是大家把模型与实际业务相结合起来的成果吧,总要更符合业务上的直觉才可以。是自然的展现群落的形态,还是给定一些条条框框只是去预测?实践中真的是,都去试试才知道那种更符合一个具体案例的需求。这也是在industry玩的比较开心的缘故,没有那么多条条框框,没有那么多“约定俗成“的规矩,需要自己去一步步挖掘这些算法的用武之地。看着一个个自己熟悉或者陌生的模型被逐渐的改造和应用,也是一件蛮开心的事情呢。