Tag: NTU

Machine Learning Techniques Lecture 15: Matrix Factorization


 
 

内容:

Matrix Factorization(矩阵分解)模型,一开始先讲linear network里面通过对ID这样的特征编码来萃取特征,然后讲基本的 matrix factirization演算法,要做的事情就是在两个特征之间交互的 做 linear regression,同时你也可以用SGD来做,这是一个有效率的方法,而且可以根据应用做适当的调整,最后总结了一下 extraction model。

 
 


 
 

上一讲:

Raidal Basis Function Network,就是把原来的原始数据通过k-means算法来找出代表,通过使用RBF函数来替代,然后整个方法就可以转化成linear aggregation问题来求解了。

 
 

这里:

Matrix Factorization

 
 


 
 

我们首先来回到机器学习基石课程最早讲过的,机器学习的目标就是从资料里面学习的到技能。例如从很多使用者那里收集的到了很多喜欢的电影的数据,每一笔资料就是某个使用者给某一部电影的分数,我们目标是得到那个使用者喜不喜欢还没上映的那部电影。棕色框就是一个实际问题的例子。

 
 

在上面的例子里面,x是一个抽象的特征,是一个编号。这样的数据怎么去做机器学习,就是这里要讲解的问题。

 
 


 
 

X 是抽象的,就是数值上没有意义,只是用来分类别的数据,比如ID,血型,程序语言。

 
 

但是我们目前学过的ML Model都作用于有数值特征的数据,例如线性模型,算分数的方式的前提就是数值有举例意义,NN等基于线性模型的方法也有这个要求。只有很少数的机器学习方法可以直接处理类别特征数据,比如讲过的 decision tree。

 
 

所以如果我们要对类别特征做机器学习,那么第一步就是将类别特征数据转换成数字数据特征,这个过程叫做encoding。

 
 

一种简单的encoding方法叫做 Binary Vector Encoding。比如血型有四种,用一个四维的向量来表示,每一种可能性占一行,1表示是的。

 
 


 
 

原来的数据每一条,都是一个( 类别 x_n, 分数 y_n)的向量表示,可以把数据整合一下,把所有相同的x_n数据合成一个,就有(类别x_n,分数向量(分数向量里面存在不知道的数据用?表示))。

 
 

我们怎么样从这么复杂的抽象数据里面做特征萃取呢,NN是典型的特征转换模型,NN里面每一层都可以看作是特征的萃取。例如电影偏好的问题,可以把NN里面的x看作是用户,y看作是电影,整个学习参数的过程就是特种萃取。N-d~-M NNet,N表示的是使用者的个数,M表示的是电影的个数,d~就是中间节点的个数。

 
 

tanh在这里不是必要的,因为这里的输入向量的特征是,里面只有一个1,其他都是0,也就是进出都是sparse的,简单,不需要转换了,因此可以使用这个特征来简化模型,也就是linear Network。

 
 


 
 

因此我们考虑 Linear Network,先来命名如上面所述,这样以后就有 h(x) = W^T * V * X。因为X只有n列是1,其他都是0,因此我们可以用 V_n 来表示 V * X 的结果,这样就有了上面表示的 hypothesis 结果。

 
 


 
 

练习

 
 


 
 

上面我们讲到了 Linear Network Model,在电影这个应用里面 V * x 的意义是对所有的电影序列 x 做了转换,然后再跟 w 做线性组合就是结果。或者对于某一部电影m来讲,关心的就只是 h_m(x) ,对应的x的那一行只有m列是1,其他都是0,这就是一个转换过了以后的线性模型。

 
 

我们想要的输出是 r_nm = W_m(权重)* V_n(n个使用者),这个结果要和我们已知的一些数据 y_n 接近,那么对于总体来说就可以写成一个Ein最小化的公式,如上面所示, r_nm – W_m^T * V_n 表示的就是已知的使用者评价和模型输出结果的误差,灰色的部分不影响最佳化结果。Ein 最小化,表示的是这个网路我们可以学到的是,一个是怎么做转换,一个是第二层的权重是多少。

 
 


 
 

矩阵化:

 
 

R每一行代表一个使用者,每一列代表一部电影,格子里面就是评分;原来的目标求解公示就可以表示成矩阵形式,如上面所示。如果我们可以把不健全的R分解成V,W,那我们就得到了使用者的特征,得到了每一部电影怎么样对这个特征做线性组合来做最佳化预测。我们从已经知道的评分出发,想办法去反推到底对于使用者来说哪些特征是重要的,对于电影来说他有那些元素,也就是说对于R的每一格都有这样的物理上的意思。举例说就是这个用户喜欢喜剧片,这部电影是喜剧片,那么用户喜欢,反之侧不然。

 
 

矩阵分解这样的方法常常被用来把抽象的特征转化成真正有意义可以进一步处理的特征。

 
 


 
 

我们怎么来做学习呢?

 
 

上面已经得到了一个最佳化问题,变数是W,V,也就是说有两个Sum动作。这个问题有两组变数,因此可以考虑 alternating minimization方法,k-means里面讲过。首先固定V,最佳化W,就是一堆的线性模型,对于每一部电影就是一个线性模型,就是做linear regression解决问题。然后固定W,最佳化V,由于上面的问题WV的角色可以看作是对称的,因此也是一个linear regression求解。这个算法叫做 alternating least squares algorithm。

 
 


 
 

alternating least squares algorithm

  1. 初始化随机的设定值,
  2. 固定V求解W,固定W求解V,
  3. 交叉迭代第二步优化直到Converge,而且一定会收敛。

 
 


 
 

这两者都存在着矩阵分解的概念,来做比较。

 
 

Linear Autoencoder:X = W(W^T * X)

第一层的W做编码,第二层的W做解码,出发点是特别的线性NN,可以看作是分解成一号矩阵W,二号矩阵(W^T * X);错误衡量用的是平方错误,但是矩阵中每一格都知道,因此算所有格子;解是全局最优,就是eigenvector;适合用来做资料的降维。

 
 

Matrix Factorization:R = V^T * W

也是一个线性NN,分解成一号矩阵V,二号矩阵W;错误衡量用的是平方错误,但是矩阵中有很多不知道,因此只算知道的;解是局部最优;适合萃取特征。

 
 

Linear autoencoder 可以看作是 matrix factorization 的特例。

 
 


 
 

练习

 
 


 
 

我们上面讲了 alternating least squares algorithm 来解决 Matrix Factorization 的问题,这里带大家来看能不能使用 Stochastic gradient descent (随机的从资料里面选取一笔资料,在这比资料有关的error衡量上面去算梯度,做梯度下降,好处是每一轮只涉及到一个点,计算很有效率,程序实现容易,可以使用不同的错误衡量方式)来求解 Matrix Factorization。

 
 


 
 

首先写出错误衡量公式,用的是平方错误。然后对模型里面所有的变数做偏微分,同样因为W,V是只有一行有意义,对于每一个nm对来说,所以就有蓝色的部分结果。

 
 

我们来看 Gradient 其包含两项,第一项是 residual(余数,我们的目标和现实的差距),第二项是 the other feature vector(另外一个特征向量)。

 
 


 
 

由上面就可以得到用 SGD 做矩阵分解的方法:

一开始的WV是随机的设置一些值,然后

  1. 随机选择一个点
  2. 计算余数项
  3. 更新SGD,公式如上面所示

 
 

非常的有效率,非常的常用。

 
 


 
 

最后给一个例子。

 
 

训练的资料比测试的资料获得的时间是比较早的,也就是有时间上的分布关系。这时候需要注重时间比较晚的资料。

 
 


 
 

练习

 
 


 
 

到此的四讲里面我们讲的是 Extraction Model,就是把资料的转换纳入到机器学习的过程中来,通过资料的转换来学习到隐藏的特征,再使用线性模型来求解的完整过程。

 
 

NN/DL :前面所有的层都是在做特征转换,最后一层就是线性模型

RBF Network:最后是一个线性模型,前面求RBF的中心就是转换后的特征

Matrix Factorization:同样最后一层是线性模型W,前面在做特征转换V,但是这里面WV是对称的,可以互换。

Adaptive/Gradient Boosting:其中的hypothesis可以看作是资料转换,最后一层就是带权重的线性转换。

K Nearest Neighbor:可以看作是用最近的中心点当作是原来的特征,就是特征转换,最后也是一个线性模型得结果。

 
 


 
 

除了模型之外,我们还通过模型来交给大家一些技巧:怎么从你的资料里面萃取出有用的特征。

 
 

NN/DL :SGD,透过 backprop 来很有效率的算出梯度的值;autoencoder,通过非监督式的方法让整个方法在一个比较好的权重开始。

RBF Network:介绍了 k-means clustering,非监督式的方式来获得分群的资料

Matrix Factorization:SGD,alternating leastQSR 交互的做线性回归

Adaptive/Gradient Boosting:functional gradient descent 来推导出怎么萃取g。

K Nearest Neighbor:lazy learning 方法,就是训练的时候不做什么事情,而是测试的时候做事情。

 
 


 
 

Extraction Models

 
 

好处:对人来说容易使用,不用拍脑袋设计特征;非常的powerful;

坏处:不是凸函数,容易得到局部最优解而不是全局最优解;容易overfitting,

 
 


 
 

练习

 
 


 
 

总结:

Matrix Factorization(矩阵分解)模型,一开始先讲linear network里面通过对ID这样的特征编码来萃取特征,然后讲基本的 matrix factirization演算法,要做的事情就是在两个特征之间交互的 做 linear regression,同时你也可以用SGD来做,这是一个有效率的方法,而且可以根据应用做适当的调整,最后总结了一下 extraction model。

 
 

下一讲:

给大家一些机器学习技法方面的总结

Machine Learning Techniques Lecture 14: Radial Basis Function Network


 
 

内容:

Radial Basis Function Network 模型,其hypothesis就基本是一堆RBF,比如高斯函数,用这些RBF作为代表来取代NN里面的神经元;学习的过程中如果决定了中心是哪些之后,剩下的就是做一步linear aggregation;然后我们介绍了k-means演算法来用于决定中心,其算法的核心就是 alternating potimization,对里面的变数交叉做最佳化;最后我们举例图示加深印象。

 
 


 
 

回顾:Deep Learning 是NN的延伸,NN很多很多层的时候,要怎么克服一些困难,比如训练的时候需要好的初始值,denoising autoencoder 就是一种做法(non-linear PCA),其和统计里面用来做资料处理的PCA 有一定的关联性

 
 

这里: Radial Basis Function Network

 
 


 
 

回顾一下很早以前讲的 Gaussian SVM,在SVM里面配合上gaussian kernel,就可以做到在一个无线多维转换的空间里面想办法找一个胖胖的边界。

 
 

如果从最后的结果得到的hypothesis来看,我们也可以说Gaussian SVM做的事情就是拿一堆Gaussian来,然后把他们做线性组合,他们的中心在Support Vector这些资料点上。

 
 

Gaussian Kernel 也叫做 Radial Basis Function(RBF) kernel,radial 代表你今天算的函数值只和x与中心点的距离有关,basis function 表示的是我们要拿来做线性组合的系数。

 
 

我们如何看待Gaussian SVM输出的函数呢,如果我们定义g_n如上面所示,其物理意义是看新的x与xn到底够不够近,越近的就给他越多的票用来投y_n是正一还是负一。我们的SVm就可以表达出那这些g_n来做加权线性组合,也就是以g_n为基础的linear aggregation。

 
 

Radial Basis Function (RBF) Network 就是这个概念的延伸,就是说怎么去线性组合radial hypothesis(只和半径有关的函数)。

 
 


 
 

为什么叫Network?

 
 

我们来看看NN和RBF的图如上面所示,RBF的第一层是Centers,就是点到中心点的距离,最后一层则是投票的动作。因此两者再输出的部分都是线性模型,类似;不一样的是第一层,NN里面是做内积在经过tanh转换,RBF是算距离,也可以把RBF看作是NN的一个分支。

 
 


 
 

蓝色部分公式就是RBF Network的hypothesis长相,蓝色部分就是RBF Basis长相,中心点是mu,Gaussian是其中一种;红色部分就是投票权重。

 
 

重要的参数:mu表示的是中心点,beta就是投票权重。

 
 

上面举得例子,RBF就是gaussian;Output就是binary classification。

 
 


 
 

kernel是把我原来的两个点转换到某个Z空间,在Z空间里面算一个向量内积。因为这样的操作关系,所以kernel就需要受到Mercer’s condition的保障,就是说其转换矩阵要是半正定的。Kernel描述的可以说是一种相似性,两个原来的向量的相似性通过转换到z空间来描述这种相似性。

 
 

RBF 则可以看作是在描述一种相似性,这个相似性则是可以直接用当前空间内的距离来描述。

 
 

因此 Kernel 和 RBF 可以看作是两种对相似性的衡量方式。Gaussian则是两者都可以解释。他们两个之外也有一些其他的不一样的相似性的表达方式,比如NN里面每一个神经元做的事情也是在比较两个向量的相似性,一个是输入的向量,一个是权重的向量,再比如DNA序列的比较,两者的相似性来源于两者互相变化的最小修改代价。

 
 

RBF Network 告诉我们的是,相似性是一个很好的定义特征转换的方法。

 
 


 
 

练习

 
 


 
 

上面讲了RBF network的基本概念,就是要找到一些中心,然后这些中心对应的RBF用beta这些系数做线性组合。那怎么找中心,干脆就把所有我们看见过的资料点统统当作是中心,这样的RBF Network叫做 full RBF Network(N笔资料就有N个中心)。他的物理意义就是我们看过的每一笔资料都应该对它周围的那些点有beta大小的影响力。举例说假设每个点有同样的影响力,相当于用距离的远近作为权重来投票,就如上面的公示所示,新的点的权重就是周围所有点的影响力的加权和(aggregation)。

 
 


 
 

这样的方法和机器学习里面的另外一些方法有有趣的相似性。我们看我们上面去确认full RBF Network结果的时候算的是一堆高斯函数来投票。这里面和你的x最近的已知点的高斯函数的权重是最高的。高斯函数衰减很快,里面最大的一项很容易掌握全局结果,因此很多时候找出最大一项作为结果就好,不需要去计算全部(selection instead of aggregation)。新的物理意义就是通过最接近x的已知点的结果来决定x,这个方法叫做好邻居法(nearest neighbor)。还可以扩展这个方法,让几个邻居来投票,这样的方法叫做 k-nearest neighbor。

 
 

这里的 k nearest neighbor 方法和 full RBF network 一样都是偷懒的方法(只有在输出的时候才去使用资料来决定,也就是说训练的时候不花力气,测试的时候花很大力气)。

 
 


 
 

这里假设中心已经确定是看过的已知点,我们还要想办法最佳化一下beta。

 
 

这里考虑平方错误的regression当作例子,这样output这层的转换就不考虑了。那我们要做的就是使用这些中心点的RBF函数来转换我们的资料,转换过后beta这边就是一个线性组合的问题,只需要通过linear regression就可以得到结果了。因此我们来看BETA的结果,里面包含的Z是一个方阵,方阵里面的每一格算的是两个向量之间的相似度,因此还是一个对称矩阵。如果你对对称方阵采用高斯函数,只要你所有的X都不一样(每笔资料都不一样),矩阵Z就会是可逆的。因此上面的beta的公式可以化简为 beta = z^-1 * y。

 
 


 
 

我们将上一页得到的结果喂到RBF函数里面去,就有上面橘色部分的推导结果,也就是说RBF网络的结果是,送入 xn 会得到 yn,也就是说Ein = 0!

 
 

这样的性质在 Function approximation(函数逼近)里面应用的很好(内差完美 exact interpolation),但是对于ML来说不好,overfitting!

 
 

因此加上regularization,比如对上面的beta计算改造一下使用ridge regression,这样的beta解如上面所示。我们回想一下,Z这个矩阵可以看作是里面包含了一堆高斯函数,就类似于 gaussian kernel matrix K,其用到的kernel ridge regression的表示如上面所示。两者类似,区别在于以前是无限多维度,这里是有限多维度做regression。

 
 


 
 

我们上面就讲到了如果你把所有的已知资料当作是center点的话,可能会有overfitting的情况,因此你需要regularization。

 
 

我们来考虑SVM的时候是没有把所有的资料都是用进去,只用了support vector。因此这里另外一种可能的regularization的方式是让center的数量少于资料的数量。物理意义是要从原来的资料里面找出一些代表来,用这些代表来表示意见。

 
 


 
 

练习

 
 


 
 

因此我们现在的目标是找出好的代表。

 
 

上面原来是每一个人都是一个代表,但是如果当两个点非常接近的时候,这两个人可以共用同一个代表。也就是说可以把资料分群,每一个群都用一个点来代表。因此要解决的问题是分群并且选择出代表,是一个典型的非监督式学习的问题,分群问题我们的期望是如果由两个点是属于同一群的话,这个代表点和原始的两个点都很接近,因此可以得到如上面Ein的公式,公式的意义是对于每一个点来说其到自己的代表点的距离平方和要是最小,Ein表示的就是选民和代表的意见的一致程度。

 
 

目标:在很好的把资料分群后Ein要最小。

 
 


 
 

我们来看一下这个最佳化问题,这是一个困难的组合最佳化问题,既要组合最佳化,又要数值最佳化。问题里面有两群变数,我们看能不能个别的对他们最佳化。

 
 

假设固定下来所有的mu,来看怎么最佳化分群。中心选定了,对于每个点只能选一个加入离他距离最近的群。

 
 


 
 

假设固定了哪些点是一群,看怎么来最佳化中心点位置mu。也就是对每一群重新去计算Ein最小得到新的mu。

 
 


 
 

从上面我们就得到了一个非常知名的演算法 K-Means Algorithm,其具体的算法描述如上面所示。

 
 

一开始的时候需要决定mu,从原始的资料里面随便选择k个;结束条件是 Converge,就是一步内S不再会有任何变化,这个算法一路收敛的,一定会有最佳结果并停止。

 
 


 
 

我们有了k-means的概念用于RBF Network,算法如下:

  1. 一开始我们采用k-means算法来得到中心点
  2. 配合使用RBF做特征转换
  3. 跑线性模型就可以得到beta
  4. 最后回传回去的就是beta和转换结果

 
 

这里使用了非监督式演算法(k-means)来萃取特征,前面提到的auto-encoder也是相思的概念。

 
 

RBF Network现在似乎不那么流行使用了。

 
 


 
 

练习

 
 


 
 

K-means 算法很漂亮,这里给一个demo,这里有四群资料,开始分群。

 
 


 
 

随机得到mu,对每一个资料点分群

 
 


 
 

决定新的中心点位置

 
 


 
 

新分群

 
 


 
 

得到新的mu

 
 


 
 

以此类推,只要你的群的数量选择适当,结果就会很好。

 
 


 
 

一开始群的数量设的不同,结果很不一样。也就是说这个算法对 初始值 和 k 敏感,也就是说最终得到的也是局部最佳解。

 
 


 
 

分完群以后做RBF Network,结果是上面这样,也就是说如果这个算法的第一步k-means结果不错,第二步再做RBF Network结果也就会比较好。

 
 


 
 

我们来看看几个方法的比较,左边是full RBF Network,右边是nearest neighbor,这两个实际上很少被使用,计算量很庞大。

 
 


 
 

练习

 
 


 
 

总结:

Radial Basis Function Network 模型,其hypothesis就基本是一堆RBF,比如高斯函数,用这些RBF作为代表来取代NN里面的神经元;学习的过程中如果决定了中心是哪些之后,剩下的就是做一步linear aggregation;然后我们介绍了k-means演算法来用于决定中心,其算法的核心就是 alternating potimization,对里面的变数交叉做最佳化;最后我们举例图示加深印象。

 
 

下一讲:

我们怎么从更加抽象的资料里面萃取特征出来。

 
 

 
 

 
 

 
 

Machine Learning Techniques Lecture 13: Deep Learning


 
 

内容:

Deep Learning模型,是之前讲的类神经网路的延伸,他是一个困难的问题,要经过很多层层层淬炼;然后讲了autoencoder,在deep learning里面它的作用就是帮我们预训练出好的weight,本质上做的事情是从资料里面找出最好的表现方式,做法是用一个浅浅的NN来找到一个好的表现方式;进一步讲到denoising autoencoder 就是在原来的资料里面埋了一些杂讯进去做学习已达到可以抗杂讯的autoencoder的效果;最后讲到这些非线性的autoencoder如果退回来变成线性的话,其实就是PCA方法,作用都是帮助我们降低资料的维度。

 
 


 
 

回顾:NN模型里面有一层一层的神经元,他们的作用就是帮我们萃取出资料面的模式(特征),通过backprop工具来计算梯度,从而通过GD/SGD法来学习的到NN模型里面的w参数。

 
 

这一讲:Deep Learning

 
 


 
 

类神经网络的核心就是一层一层的神经元和他们之间的连接关系。那么问题是我们要用多少个神经元呢?我们要用多少层呢?我们的NN结构是怎么样的呢?或者你可以主动的去设计;或者你可以把模型的结构当作是参数,通过validation来选择最好的。

 
 

在NN里面决定使用什么样的网络结构是非常核心,也是非常困难的问题。

 
 


 
 

我们这课里面不会把所有的网络结构列出来比较好坏,而是来比较基本的两种。

 
 

Shallow(浅):

相对来说学习效率很高,计算量比较小;结构简单,参数比较少;层数比较少,但是每一层放足够多的神经元,一样可以做到很复杂的事情。

 
 

Deep(深):

训练的时候一定会花更多的力气,计算量大;对结构的决定会很复杂,参数量大;层数足够多,一样可以做到很复杂的事情;deep这几年很流行的一大关键原因就是其可以得到比较有物理意义的特征。

 
 


 
 

什么叫做 Meaningful?这里举例手写识别来说明。比如我们要辨识1/5,那么每一层萃取出越来越复杂的各个部位的特征,也就是每一层代表了不一样的物理意义,最后再做辨识。越多层就可以表示越多种不一样的变化,每一层要做的事情相对就变简单了,层与层之间的物理意义就是从简单到复杂的转换。

 
 

如果今天你最终要区分的是比较复杂的高级特征,你不能一步登天,像这样每一层做的都是区分非常简单的特征,一层一层的处理合成起来也就可以处理复杂的辨识。在计算机视觉,语音等领域很流行。

 
 


 
 

深度学习里面的困难点和对应的关键技术如下。

 
 

  1. 决定整个网络的架构

除了前面提到的validation方法,研究者还会加上其自身对这个问题的了解(Domain Knowledge)。比如 Convolutional Nnet (CNN) 用来处理图像,用的就是像素之间的物理上的位置关系是很大的影响因素,因此在设计网络的时候让附近的像素连到同一个下一层的神经元,隔太远的像素之间就不管了。

 
 

  1. 模型的复杂度非常高

在资料量足够多的时候这不见得是一个很大的问题,但同时加重了计算复杂度。而对于控制模型复杂度问题本身,其基本工具就是regularization,想办法在你的模型里面踩刹车,让你的模型在即使存在杂讯的情况下依旧是稳固的。

比如最近流行的方法 Dropout,模拟的事情就是如果网络里面存在坏掉的神经元,希望在这样的情况下最终结果还是能保持比较好。

还有一种方法叫做 Denoising,如果我的输入坏掉的情况下,我的整个网络还是可以大概给我一个适当的输出。

 
 

  1. 这是一个困难的最佳化问题,非常容易卡在局部最优

既然backdrop是在帮助梯度下降(GD),梯度下降是起始点敏感的,因此现在需要比较谨慎的选择起始点,而不是random。这个会有一连串的方法来讲解怎么选起始点,一般叫做 Pre-training。

 
 

  1. 计算复杂度很高

这边是这次AI大爆发的重要原因就是有30年前难以想象的硬件计算资源GPU。

 
 

讲者个人观点里面最重要的进步来自于 regularization 和 initialization 思维方法的创新。

 
 


 
 

一个简单的深度学习框架的例子:

  1. 决定一开始比较好的权重,可以一层一层的来决定。上图最下面时输入,第一次决定的就是第一层的初始权重,然后暂时固定下来第一层去确定第二层,以此类推。
  2. 然后再通过训练来获得更好的w。

 
 


 
 

练习

 
 


 
 

上面讲了一个基本的深度学习的架构,我们现在来考虑怎么做 pre-training,也就是帮助我们的权重决定初始值。

 
 

权重的物理意义是什么,其代表的是我们要怎么做资料转换,或者说资料怎么去编码,怎么去表现资料。问题是在做完pre-training之后,我们是不知道这个权重未来会怎么被使用的。也就是说比如我们得到了第一层的权重,对于第一层的权重我们是不知道其在第二,第三层等是怎么被使用的。

 
 

好的权重就应该是能保持我要的资料的特征信息就好了。也就是说资料转换过去后原来和新的资料说明的事情没有变化。举例上面的1/5分类,做了上面图示的资料转换,前三个表示的是1,后三个标识的是5,这三个可以轻易的转换回去。

 
 

如果能够轻易的将资料转换回去(重建),那就是一个好的资料转换。因此我们也希望预训练的时候想办法做的特征转换,是一个好的资料转换。

 
 


 
 

怎么做 pre-training 呢,同样是使用一个 NN 来求解:把原始的资料转换到中间的某一些神经元,这些神经元的输出是我的心的表达方式之后,我还能够试着重建回来。

 
 

这样的NN叫做 autoencoder(自动编码器,自动从原始资料编码得到中间层,编完码之后还可以解码,其输出就是解码结果,和原来输出类似),公式表示就是 g(X) ≈ X ,图中蓝色的w就是 encoding weight,红色的叫做 decoding weight。

 
 

那么 Approximating Identity Function 有什么好处? (就是为什么要编码后的还能解码)

 
 


 
 

假设我们可以 Approximating Identity Function ,那么其必然依赖原来资料的 hidden structure,这样的方式对于 supervised/unsupervised 都有用。

 
 

For supervised learning:学习信息表示

如果能通过这个学习方式得到这个潜藏的结构的化,我们就可以通过这个潜藏结构来当作特征转换。也就是说这些潜藏结构告诉我们怎么用有效的方法来表示我们原始的资料。

 
 

For unsupervised learning:学习得到典型资料

如果我要做的是 density estimation,看看哪边是比较稠密的,哪边是稀疏的。 Approximating Identity Function 做了以后对于新进来的资料,我们可以看他是落在稠密区还是稀疏区,稠密区就是改编码器做得比较好的地方。透过编码器做得好不好,就可以挑出来哪些点不合群,也就是说可以判断到底哪些是典型的资料。

 
 

对于这里自动编码器的重点是得到符合要求的中间层,得到资料的表现方式。

 
 


 
 

我们来看看基本的自动编码器如上面黄色框公式所示。

 
 

  1. 是一个浅的NN,可以通过Backprop轻易地来训练得到。
  2. 通常情况下我们考虑的是得到的中间层比原来的资料维度更小,这样就压缩了表现形式。
  3. 这里的资料不用考虑真正的原始网络的输出结果,要扔进去的资料是(Xi, Xi),可以看作是一个unsupervised学习技术。
  4. 一般情况下用来编码的权重和用来解码的权重是一致的,加上这个条件就是 regularization 的过程,限制能力。

 
 

满足这四条的就是一个基本的 autoencoder, 就是 NN 的 pre-training 的步骤。

 
 


 
 

再回头来看 Deep Lerning 的基本算法,第一步的合理做法就是使用 auto-encoder:每次都是拿前一层的输出训练出初始化的w,同时得到输出用于下一层。

 
 

大部分的 autoencoder 都是大同小异,在这基础上做变化的。

 
 


 
 

练习

 
 


 
 

前面用 autoencoder 解决了 Deep-Learning 里面 Pre-training 的问题,这里谈一下 如何来使用 Regularization 的机制来控制模型复杂度。

 
 

上图是一个之前提到的 NN 示意图,里面有很多神经元以及层次关系,我们要小心overfit,因此我在很多时候使用 Regularization。

 
 

  1. 决定结构的时候,加上一些条件,例如前面举过的CNN的例子。
  2. 在决定权重的时候,加上一些条件
  3. 在early stoppping的时候,确定其条件

 
 

下面讲一个很有用的 regularization 方法。

 
 


 
 

先来复习一下 overfitting 的成因,上面是点的资料量和杂讯的量坐标系内overfitting的可能性,越红越容易。杂讯对于overfitting来说是极其重要的原因,因此要去处理它。

 
 


 
 

一般的思路就是把高杂讯的资料丢掉清理一下,看起来我们可以把学习的结果做得更好一些。

 
 

新的思路是如果我们没办法很容易把杂讯找出来并处理的话,我们把杂讯加到资料里面。

 
 

如果我们想要一个好的自动编码器,有输入输出差不多,你丢进去干净的资料,希望他出来干净的结果, G(x)=x;如果今天给带杂讯的资料,你丢进去带杂讯的资料,你还是希望输出干净的结果,G(X’)=X。

 
 

所以我们要的是 denoising autoencoder。做法基本和基本的一致,输入不一样,资料是干净的资料+人工的杂讯,最后得到干净的结果。有了这种自动编码器,理论上经过DL可以得到更好的结果。

 
 

意义在于,学习得到编码器的时候就加入杂讯,使得其有去杂讯的功能,这样再次使用该编码器处理真正的带杂讯的资料的时候其就具有了去杂讯的功能。

 
 

人工加入杂讯这件事情也是一种regularization的方式,因为它告诉了机器到底要把怎么样的资料处理得更好,这个想法可以用于任何机器学习的模型中。

 
 


 
 

练习

 
 


 
 

前面的部分讲的是 nonllinear autoencoder,是相对来说比较复杂的模型,那为什么不是从线性模型开始讲?(not linear first)是因为我们这里考虑的NN,DL本身已经是非线性模型,这样的架构下非线性转换比较有用。

 
 

那么对于线性的autoencoder可以怎么来做?如果是线性模型,就没有了tranh,见上面的蓝色框第一行公式。考虑一些要用到的特点,首先是把X0拿掉,会让输出和输入范围比较一致;编解码权重一致,也就是蓝色的和红色的是一致的;中间维度比原来的维度小。有了这些H(x)就可以用矩阵表示,非常的简洁,如上面的黄色框所示。

 
 

那么接下来要做的就是对W矩阵做最佳化。

 
 


 
 

今天要对h最佳化,就是对w最佳化,Ein公式如上面所示,使用的是平方错误。我们要做的就是找到一个w矩阵让这个Ein最小。

 
 

下面我们来推导得到这个W的公式解。

 
 

我们先来复习一下线性代数知识。

  1. W *W^T 是一个半正定矩阵,可以做 eigen value decomponsition,得到 V(特征向量), garma(特征值)

    特性:V 向量互相垂直,自己和自己乘就是单位矩阵;garma是对角阵,矩阵维度会小于等于原来的d。

  2. 因此上面第一步*X就也有上面表示了

    特性:V^T(Xn) 代表的就是坐标转换,几何上就是旋转和镜面反射;在乘上garma,就是scale的过程;在V,就是旋转或者镜面反射回到原来的空间,看看变成什么样的资料了。

  3. 用上面的示意对于原来的资料也可以表示成这个形式,只是在V空间变换后啥也没做就变换回去了。

 
 

因此我们可以把W的最佳化问题转换成 V和garma 的最佳化问题。

 
 


 
 

先对garma做最佳化。

 
 

灰色部分表示不对最佳化产生影响,先把w表示成V,garma,后面的变化不会影响的是长度,所以可以把红色的V涂掉,对garma最佳化没有影响。所以就有了 上面蓝色框第二条所示公式,唯一的最小化的机会就是 (I – garma) 里面0最多。因为garma是对角矩阵,因此只需要考虑对角线,因此garma矩阵对角线1越多越好,也就是说最多可以塞 d~ 个1, 因为garma矩阵有效的不大于d~ 大小,所以最后你要得到的garma就长成蓝色框右下角所示情况。【这里是几何概念推理】

 
 

剩下的交给V的最佳化求解。

 
 


 
 

对V做最佳化。

 
 

首先把最小化变成最大化,因为最大化问题看起来比较干净。最小化的时候考虑的是留下哪些维度,最大化则是考虑的要拿掉哪些维度,上图中间矩阵部分的表示。

 
 

假设今天d~是1,也就是V也只需要考虑第一行有用。然后对于平方,则可以写进去如上面灰色部分第二行所示。V * V^T = 1 则是有前面提到的线性代数性质决定的。

由上面可以得到最好的V会满足的条件,绿色的部分可以由lamda替代,原因是第二行的式子部分微分得到的三行的式子,第二航的条件V^T * V 微分得到 V 本身,有 lagrange multipier 知道最佳解两者的微分要平行,所以乘上lamda就可以有上面的等式。然后你再看V,就是eigenvector of X^T * X,而且还是最大的eigen vector,这样才是最大解。

 
 

所以当d~等于1的时候,公式解就是最大的eigen vectoe。所以整体的公式解也可以类似的推导出就是最大的d~个eigen vectors。

 
 

所以你今天在这里要做的事情就是得到资料然后做eigen value decomponsition,得到的最好的那些eigen vector方向,就是你应该投影做特征转换的方向。

 
 


 
 

这就有了非常重要的算法 PCA (Principal Component Analysis),只做2,3两步就是这里讲的linear autoencoder。

 
 

  1. 先把你的资料对应他的平均值做一个转换,得到平均值是0的资料。
  2. 再通过上面的资料计算出最大的d~个eigenvectors就是你需要的这些W的结果。
  3. 有了这些W你就可以构建特征转换,资料进来通过W计算之后送出去的就是资料转换的结果。

 
 

物理意义就是投影过去后在那个方向上的统计学上的变化量越大越好,上面步骤第一步就是做了一个平移的动作,第三部就是做一个投影的动作。

 
 

任何资料拿来,如果你要找到线性的最好的表现形式的化呢,就做PCA来降维度。

这也就是linear dimension reduction。

 
 


 
 

练习

 
 


 
 

总结:

Deep Learning模型,是之前讲的类神经网路的延伸,他是一个困难的问题,要经过很多层层层淬炼;然后讲了autoencoder,在deep learning里面它的作用就是帮我们预训练出好的weight,本质上做的事情是从资料里面找出最好的表现方式,做法是用一个浅浅的NN来找到一个好的表现方式;进一步讲到denoising autoencoder 就是在原来的资料里面埋了一些杂讯进去做学习已达到可以抗杂讯的autoencoder的效果;最后讲到这些非线性的autoencoder如果退回来变成线性的话,其实就是PCA方法,作用都是帮助我们降低资料的维度。

 
 

下一讲:

这两讲NN, DL都讲了些萃取特征的方式,下一课再讲一种,怎么从资料里面找代表。

 
 

Machine Learning Techniques Lecture 12: Neural Network


 
 

内容:

Neural Network模型,出发点是把原来的perceptron变成更多层来达到越来越复杂,越来越powerful的效果,这样的链接在生物学上模仿的就是神经元的连结。在NN里面一个网络w固定了的话就是一个hypothesis,每一层做的事情就是根据这些权重来萃取pattern,一层一层萃取出来到最后一层是直接输出。NN学到这些权重的基本方法就是gradient descent(GD),透过backprop的方去很快的算这些梯度到底是多少。最后讲到这样的基本模型还需要小心的是怎么去初始化,用什么regularizer,以及透过early stopping的机制来避免overfit。

 
 


 
 

上一讲:

Gradient Boosted Decision Tree 模型透过 functional gradient 的方式去得到一棵棵不一样的树,然后再给每一棵树以 steepest descent 的方式得到其对应的权重,合起来以后可以做到处理任何的error measure。

 
 

这一讲:

Neural Network

 
 


 
 

我们已经学过了 Perceptron 模型,就是把你的输入乘上一堆权重算出一个分数,然后判断这个分数大于0就是正一,小于0就是负一。

 
 

如果我们今天把一堆 Perceptron 用 linear aggregation 的方式组合起来的话,就如上面的图所示,从输入出发,乘上第一组的权重得到g1,乘上第二组权重得到g2,以此类推得到一堆的 Perceptron,之后各个g乘上各自的权重alpha,组合起来得到最后的G。

 
 

数学表达式如右边所示:

这个过程里面有两组权重,第一组是从输入乘上对应的权重得到一堆的g,权重是w_t;第二组是g_t投票的权重alpha_t。

这个过程里面还有两次取sin的过程,第一次是得到g,第二次是得到G。图示中使用红色的阶梯函数来表示这个动作。

 
 

这样的模型到底可以做到什么样的边界。

 
 


 
 

例如如图所示,我们有两个 perceptron g1 和 g2,把两者通过 linear aggregation 合起来可能可以做到右边图所示的结果。然后我们构造了下面的图示的函数,公式就是下右表示的那样,其G所描述的就是和上面所述的AND是一样的。

 
 

也就是说我们在第一层g上面构造一些些逻辑运算,到第二层的时候就可以得到比较复杂的边界,比如上面的AND就已经不是线性边界了,OR,NOT也可以类似的得到。

 
 


 
 

linear aggregation of perceptron 是非常 powerful 的,非常复杂的。

 
 

比如上面的例子,我们的目标是一个圆圈圈,园内是1,圆外是-1,如果用单一的perceptron就可以切出左图所示,16个的话就如中间所示的图,最终的目标是使用一堆的perceptron来逼近得到平滑的边界。也就是说我们可以任意的切出二维平面内的凸多边形,这时候的Dvc是无限大(以前有过证明),也就是说能力足够。

 
 

但是还是有做不到的事情,比如 XOR(有且只有一个true) 就做不到。我们把g当作是资料空间转化,在我们转化完以后,资料还是线性不可分的,这时候就没有办法做到。

 
 

那我们要怎么做到 XOR ?

 
 


 
 

转换一次得不到好的结果,那就得再来一次转换。

 
 

比如上面XOR的例子我们考虑两层的转换,第一层做AND,第二层做OR,这样转换的得到的就可以线性分割,就可以得到XOR的结果,图示如上面。

 
 

这里我们的perceptron就开始分层了,这就是我们这一课要讲的神经网络的基本长相。单一的 perceptron 比较简单,多个 perceptron 比较复杂,这里我们迈向更加复杂的 multi-layer perceptron。

 
 


 
 

这种层次化的perceptron组织方式一开始就是学习生物学的神经元信息处理的方式得来的,神经元对应到node,他们之间有传递关系就用权重代表,最后都会得到反馈,就是生物工程的抽象化结果。

 
 

只是模仿,不是模拟!

 
 


 
 

练习

 
 


 
 

上面讲的就是一个简单的神经网络的运作过程,我们从输入出发,经过一层一层的运算,最后一层得到输出。从数学上可以看作是对原始的输入做一次再一次的特征转换,最后通过最后一层的权重去算一个分数,然后输出结果。

 
 

我们可以看到在输出层其实就是一个线性的模型,我们学过的 linear classification(线性分类)/ linear regression(线性回归分析) / logistic regression(软性的分类) 这些线性的分类器都可以放入到这个网络里面。下面为了讲解简单,我们采用 linear regression 方法来讲,你可以轻易的延伸到其它的方法。

 
 


 
 

上面讲了输出的部分,这里说中间的部分,中间的每一步每一个节点都是在做转换。在转换的时候我们应该采用什么样的函数呢?

 
 

如果你每个节点用的都是线性函数,那么整个网路就是一个线性函数,那你直接用一个线性函数替代整个网络就可以了。

如果你每个节点用的都是阶梯函数,是离散的,很难最佳化。

 
 

因此最为常用的就是平滑的s型函数,其中最为代表性的就是 tanh(t) 函数。

 
 

图示和公式如右边,大范围的时候和阶梯函数接近,小范围的时候和线性函数接近,整体上就是大概的逼近我们原来采用的sin函数。这个函数是连续的,最佳化比较容易。tanh(s) = 2 theta(2s) -1 :就是两倍的原来logistic regression函数取2s再减去1的结果。也就是原来的logistic regression函数做放缩平移后的结果。

 
 


 
 

然后我们来描述下我们要讲的 Neural Network Hypothesis 长什么样。

 
 

如果我们固定了hypothesis的一些参数以后,我们就能从一开始的输入得到最终的输出。中间则每一层都是根据前一层的输出当作是输入,再乘上相应的权重之后,得到这一层的输出当作是下一层的输入,直到最后一层直接输出。

 
 

我们把第一次处理叫做第一层,第二次处理叫做第二层,以此类推,输入的部分叫做第0层,层数用L表示。输入层是0 – d-1层,输出层就是 1 – d 层。这样以后这个过程就可以用公式表示出来如上面所示。紫色的 S_j^L 表示的是 第L层第j个节点的输入,红色的 X_j^L 表示的是 第L层第j个节点的输出,除了最后一层其他层都需要做tanh转换再输出出去。

 
 

绿色框框的标题


表示的是我们用每一层有多少个节点来描述这个神经网络。

 
 


 
 

这网络的物理意义:每一层做的事情就是转换,权重就是从资料里面学习得来的。也可以看作是把前一层的结果x向量 和 这里的权重向量 的内积是不是比较一致,如果两个向量比较重合,则表示两者比较接近。

 
 

NNET :每一层在做 pattern extraction,每一层都是从资料中找出潜藏的模式,一层一层的把这些模式做转换匹配,看是否相似。

 
 


 
 

练习

 
 


 
 

如果我们已经有一组特定的权重的话,NN做法就是从输入开始就是一层一层的透过w和tanh来得到一层一层的输出变成下一层的输入一路计算下去,直到最后一层不做tanh而是直接输出。

 
 

现在问题是怎么学习得到权重?

 
 

如果你的网络只有一层,学习的方法我们就已讲过了,就是aggregation of perceptrons。我们可以用 Gradient boosting 每次加一个节点(神经元)进来,一个一个加直到你觉得结果可以为止。

 
 

但是现在你有很多层的话,这个可能就行不通了。现在进过很多层以后最终一定是有一个结果输出,我们希望输出的结果和y是接近的。所以我们可以定义类神经网络的输出结果和y的错误平方是e_n,如果我们可以知道这个e_n和网络中的每个w的变化关系(就是 e_n/w 的偏微分),就可以用 GD/SGD (梯度下降)的方法来一步一步做最佳化。

 
 

因此关键点就是我们怎么算出这个 e_n/w 的偏微分?

 
 


 
 

我们来看怎么计算 平方错误 对于 每一个w 的偏微分。我们从错误对于最后一层的偏微分开始处理,也就是L这一层(输出层),神经元的数量是1,前一层的神经元数量则是i,最后用 W_i1^L 表示。

 
 

为什么从最后一层开始,e_n表示的是我们的观察结果和网络输出结果的比较误差的平方,网络的输出就是最后一层的输出,因此公示网络输出的部分可以替换为 S_1^L (就是L层1节点的输出),就是这一层权重的和。如上面黄色框表示的公式那样,整个关系就是从权重到分数到错误表示的过程链。

 
 

有了这个我们再来看权重和错误的偏微分,就可以用微积分里面的连锁律(就是依靠中间人分数S)就可以轻易的求解。【绿色框所示】,会求解了最后一层,我们再来看前几层,做法也是类似的方式求解,只是其中的分数没有那么容易求解出来,所以先使用delta来表示,delta_j^L 表示的是L层第j个节点的错误相对于分数的变化量【红色框所示】。

 
 

有了delta的定义,前面绿色框里面的delta_1^L就是一个特殊的可以求解的结果,表述如上面PPT所示。我们怎么来求解其他的delta呢?

 
 


 
 

我们来看delta怎么计算,那么我们先来分析一下这个分数怎么会影响到最后的错误e_n。在类神经网络里面,这个分数再经过神经元的转换变成神经元的输出,就是s变成x,然后再经过下一层的权重变成很多不同的神经元的分数,一路以此类推,最后最后才得到e_n。【上面黄色框所示】

 
 

所以我们来看蓝色的s和错误e_n的关系,他们俩之间的中间人很多层,每一层还好几个。因此如果在这么复杂的式子上面用连锁率,可以有蓝色框所示的内容(把中间人的影响要全部加起来),求解后用delta表示的结果如上。

 
 

这个结果表示的是,如果你今天后面那一层的delta你知道是多少,那你就可以推导得到前面那一层的delta的解。同时我们还知道最后一层的delta的结果,因此可以一路往回推得到所有的结果。【绿色的部分可以求解】

 
 

同时你还需要知道蓝色部分的解,tanh的微分可以直接求解【蓝色部分可以求解】

 
 

至此你就可以求解出所有的w,就可以总结出计算w的演算法。

 
 


 
 

算法叫做 Backpropagation (Backprop) Algorithm:

 
 

一开始随便设定一些权重w_ij,每一次

  1. 【Stochastic】随机选一个点算他的梯度是多少,这个梯度可以拆解成两项,一项是x,一项是delta,所以每一个权重他的更新量就和它前一层时候的x和这一层的delta的变化量有关。要更新我们就需要算出红色的值和蓝色的值。
  2. 求红色的值,把资料喂进去,一层一层的求解。
  3. 求解delta,倒着算回来,上面讲的那样。
  4. 【Gradient descent】更新w_ij

更新了足够轮的时候,每一个w_ij就应该在一个比较好的范围内了,让Ein比较小了,就把结果回传形成神经网络模型。

 
 

你每次选择一个点,你都需要从前向后算得到x,从后往前算结果得到delta,才能球解一个,感觉时间会很久。实际操作的时候,第一步到第三步可以并行的做,然后我们把这些并行结果去平均梯度结果来更新第四步,可以加速运算,这个做法叫做 mini-batch。

 
 

这就是基本的类神经网络算法。

 
 


 
 

练习

 
 


 
 

上面介绍了NN里面最佳化的基本方法,其关键就是通过GD的方式去最佳化Ein,Ein包含的是原始的输入一层一层处理最后得到的输出和y在某个错误衡量上的比较结果。这里讲的是NN常用的一些优化方法。

 
 

上面的例子是平方错误衡量,你可以替换使用其他错误衡量。我们这边的重点不是错误衡量,而是在讲经过了那么多层tanh的转换,使用GD来得到的可能是局部最低谷(就是好多山峰的中间的山坳,而不是真的全局最低谷)。

 
 

也就是说NN不是简单的像单层的二次曲线求山谷谷底(non-convex)就是全局最优,而是有多个山峰山谷,你从当前点出发得到的是局部最优。换个角度就是说你从不同的起点出发,你可能得到不一样的局部最优解。

 
 

那有什么技巧可以让我们避免不好的山谷呢?

 
 

我们来看tanh函数,前面有图示意其函数,在两头权重很大的时候,其x的变化带来的y的变化量非常小,如果在这里每次走一小步,你走老半天也可能是原地踏步。所以一开始你需要一个小一点的随机权重,这样你不会卡住走不动,随机则意味着你可以走到不同的山谷。

 
 

NN不是一个容易的最佳化问题,里面包含很多技巧去尝试。

 
 


 
 

我们来看看这个模型的复杂度,大概的结果是 Dvc = V(神经元的数量) * D(权重,就是图中连线的数量),也就是说图的节点和连线越多,这个NN的能力(Dvc表示)就越强,但是就越容易overfit。

 
 


 
 

避免overfit的一个经典方法就是 regularizer,最佳化的过程里面加入regularizer让权重不要太大是对整体复杂度的一个限制,具体可以见以前讲regularizer的时候的推导。

 
 

这边如果我们采用以前讲过的 L2 regularizer,也就是平方和,越小越好。但是有一些缺点:权重的变化是成比例的,原来比较大的权重缩小后相对还是比较大,原来比较小的权重缩小后还是比较小。也就是说权重缩小也不会是0,也就没有办法做到通过让w是稀疏的来降维度。

 
 

我们的目标是通过让W稀疏来降低Dvc的复杂度,那么可以考虑的是 L1 regularizer。L1 是把w的绝对值得和当作是ergularizer。但是因为绝对值函数是非连续的不可微分,就很难计算(原来的函数是微分导向的性质会被破坏)。

 
 

因此可以考虑的是 weight-elimination (Scaled L2) regularizer,也就是说原来weight很大的话就把它缩小,原来很小的话也缩成一个中等分量,这样的话原来很小的就会消失不见,让w变成sparse的。常用的 weight-elimination ergularizer 如上面所示。

 
 


 
 

NN里面还有一招常用的 regularizer 机制叫做 Early Stopping。

 
 

我们看GD/SGD做的事情就是考虑其周围一个范围内的w走一小步走到另外一个地方,然后在考虑新地点的一个范围内的w再走一小步。所以虽然w很大,但是每一次你都是在一个小范围内做选择;另外你走的步越多,你看过的w就越多。所以说如果考虑的是有效的Dvc,你走的路越多,有效的Dvc就越大。那么反过来考虑你不要走太多的的路,Dvc就会比较小。

 
 

我们来看Dvc的图,山谷形状,好的Dvc会在中间。套到这里,就可以用最佳化的步数来控制Dvc的大小,就是走了一些步数感觉结果可以了就停下来。NN里面步数和Ein/Etest的关系就是上面第二张图所示,我们要的是中间步数的结果是最好的。

 
 

可以通过validation来确定什么时候要停下来比较好。

 
 


 
 

练习

 
 


 
 

总结:

Neural Network模型,出发点是把原来的perceptron变成更多层来达到越来越复杂,越来越powerful的效果,这样的链接在生物学上模仿的就是神经元的连结。在NN里面一个网络w固定了的话就是一个hypothesis,每一层做的事情就是根据这些权重来萃取pattern,一层一层萃取出来到最后一层是直接输出。NN学到这些权重的基本方法就是gradient descent(GD),透过backprop的方去很快的算这些梯度到底是多少。最后讲到这样的基本模型还需要小心的是怎么去初始化,用什么regularizer,以及透过early stopping的机制来避免overfit。

 
 

下一讲:

这里讲的是基本的类神经网路,下一讲继续做延伸变成好多好多层。

Machine Learning Techniques Lecture 11: Gradient Boosted Decision Tree


 
 

内容:

Gradient Boosted Decision Tree,一开始现讲怎么把adaboost和decision tree搭配起来,需要引进sampling 和pruning才能搭配得很好;然后讲了怎么从优化的角度来看adaboost,找到好的 hypothesis 就是找一个好的方向,找到alpha其实就是走一个适当的步长,对应到adaboost里面的exponential error这样的函数就是优化问题;我们可以把优化观点下的adaboost延伸到其他不同种的错误衡量,映入了gradientboost,他做的事情就是residual fitting,根据余数还剩多少来更新regression的问题,看看能不能做得更好;最后总结了一下aggregation的方法。

 
 


 
 

上一讲:

Random forest模型,就是一堆的decision tree,利用bagging的方式做出一些不一样的decision tree,再把他们合起来。除了基本的bagging和decision tree之外,再加上一些额外的random机制,做到了自动的validation和特征选择。

 
 

这里:

Gradient boosted decision tree

 
 


 
 

上一次讲的random forest,外层是个bagging,里面是decision tree。这里把decision tree结合到adaboost一起的话,就是 Adaboost-Dtree:

  1. 每一轮给我们的资料一群新的weight;
  2. 通过这些weight来使用decision tree学一个g;
  3. 使用linear的方式把g合起来成为G

 
 

要把decision tree搭配adaboost的话,需要把decision tree改造成可以接受权重的形式。

 
 


 
 

带权重的decision tree算法应该要根据权重来最佳化Ein。

 
 

做法:

  1. 打开演算法看看到底哪些地方涉及到权重带来的影响,然后在这些地方代入权重来计算结果。
  2. 但是像decision tree这样的演算法包含很多作者的优化和特殊处理,对于做法一很难做到,因此考虑的做法是原来的演算法不动,而是考虑外面送进演算法的资料做些手脚,把权重的影响用资料来代替。

 
 

比如bagging里面权重为n,则复制资料n份,在此基础上再抽样。因此这里也可以通过已考虑权重的资料来做sampling,这样就可以得到一组可以表达权重信息的资料。

 
 

所以Adaboost-DTree:Adaboost + sampling(通过权重来抽样) + Dtree;这就是其典型做法。

 
 


 
 

当我们通过adaboost得到g以后是怎么决定g票数的:先算一下g的错误率,然后根据上面公式得到g的票数,这是adaboost做的事情。

 
 

问题是:对于完全长成的树,把所有的资料用于训练,Ein为0,加权中后Ein应该也是0,alpha_t则会是无限大,也就是说得到一个跟强很强的权重是无限大,也就是说只要这棵树决定就好了,其他的都是无用的。

问题在于你把所有的资料都用于训练,且让树完全长成。

 
 

改进:砍树不让完全长成;不用所有的资料来训练;… 简单地说就是需要弱一点的树。

做法:我们用的是sampling后的资料,也就是说是部分的资料而不是全部的资料;不让完全长成的方法则是和前面讲的一样,那些方法都可以拿来用。

 
 


 
 

什么样的是最弱的树?

一层高的树,C&RT里面做的事情就是切一刀,想办法让两边加权的纯度越低越好,这样的再结合decision tree就是adaboost-stump。

 
 

也就是说 Adaboost -stump 是 adaboost-Dtree的一个特例。当树的层数那么小的时候,一般都不会出现Ein=0,也就不用担心上面出现权重为无穷大的情况了,这时候就不见得要做sampleing。

 
 


 
 

练习

 
 


 
 

前面复习了一下Adaboost,以及讨论了一下怎么搭配decision tree,现在进一步来看看adaboost算法的奥妙,然后再据此延伸成今天要讲的griendent boosted decision tree模型。

 
 

Adaboost 里面的权重是根据前一轮的权重乘(正确:y_n = g_t(X_n))或者除(错误:y_n != g_t(X_n))方块t,我们简化一下上面的公式变成一行,用符号来控制正负;再化简一下就变成了一个递归推进的式子,也就是U^t+1与U^t相关。根据递推来算Un就是一个连乘的形式,再化为连加的形式。

 
 

橘色的部分:voting score,是小g做投票的结果,是G的分数。

 
 


 
 

Linear model可以看作是两步,第一步是使用hypothesis做特征转换,再用线性模型组合起来,这个线性模型会告诉我们每个g是几票(灰色的条件是说投票权重不能为负的条件),

 
 

我们把g_t(Xn)看作是phine,alpha看作是每个转换过的特征的权重,voting score就是w*phine。我们在SVM里面讲过,w*phine/abs(w) 就是到分割线的距离(SVM里面的常数项b不影响理解)。所以voting score可以看作是某个空间里面还没有正规化的点到分隔线的距离。

 
 

所以 y_n(voting score) 就是 unnormalized margin,所以同样我们希望margin 越大越好,所以我们希望 exp(-y_n(voting score)) 越小越好,所以希望每一个点的权重越小越好。Adaboost 一轮一轮的进行下去,就会使得这个值越来越小,这是Adaboost的一个重要性质。也就是说Adaboost可以达到large margin的效果。

 
 


 
 

Adaboost 可以让公示里面紫色的部分越来越小,也就可以看作是其可以让上面等式的右半部分越来越小,也就是说在最后一轮括号内的部分红色和蓝色相乘是很大的,也就是达到了large margin的效果。

 
 

我们特别的来看看蓝色红色相乘的结果:

  1. 01错误的时候,如图黑色线所示,同号错误为0,异号错误为1;
  2. adaboost错误(紫色部分)的时候,如紫色线所示,是01错误的上限函数。因为是上限函数,类似以前讲过的SVM,logistic regression等等,可以大概的用它来把0/1问题做的比较好。

 
 


 
 

证明:

基本工具是 gradient descent(梯度下降法):如果你要最小化一个函数的话,你做的事情是从你当前的点出发,选择一个方向使得最靠近目标。数学上就是做泰勒展开,梯度描述的就是方向,求一个最好的方向,最终的结果就是负梯度的方向走上n大小的一步。

 
 

这里我们把g_t这个函数当作是方向(原来是向量,向量的ab相互对应,这里是函数,函数的xy相互对应),同样目标是向h(x_n)方向走n远,加入公式后就如上面所示,然后目标是变成最上面的相似公式。首先整理一下公式就出现了U_n^t,式子就简洁多了,再做泰勒展开,原来的公式就可以拆分为两部分,前半部分就是现在的Ein,那么后面一项就应该越小越好,这样就最佳化了Err。

 
 

所以目标就是找到一个好的h让后面这一项越小越好。

 
 


 
 

对于后面那一项,如果做的是binary classification,y,h都是正负1,那么就只有两种情况,yh同号和异号,结果如上面所示。然后再平移出一个项,然后就可以化简为如上所示的结果,所以结论就是要Ein^u越小越好。

 
 

Adaboost 里面的 A 做的事情就是找到一个好的g_t=h,就是好的方向,这个方向代表函数。

 
 


 
 

Adaboost 通过上面所示的式子的最佳化找出g_t,但是每次走一小步代价比较大,能不能走大步一点,或者说干脆找一个最好的n(也就是g固定的时候,n越大步越好)。

 
 

也就是说这里不再和以前gradient descent一样每次步长是一样的,每次一小步,而是一次就走一大步到离目标最近,这是greedily(贪心的)faster(快速的)的n。

这个叫做: steepest descent

 
 

运用 steepest descent 则可以把原来的式子改写成灰色框最后一行所示的结果。绿色表示所有的 正确的U_n^t/所有U_N^t,红色表示的是所有的 错误的U_N^t/所有的U_N^t(epthon_t)。

至此公式只有n是变数,其他都是已知的,单变数做最佳化的问题,微分=0就可以得到结果。

 
 

结果 steepest n = alpha_t。

所以Adaboost:把函数当作是向量一样在gradient上面走了最大的一步。

 
 


 
 

练习

 
 


 
 

上面部分对Adaboost的解释是:Adaboost就是在Err_ada上面每一步都在做最佳化,每一步的时候找出一个h,把它当作g_t,然后决定在这个g_t上面走多长的距离,最终变成这个g_t的票数就是alpha_t。

所以对于公式来说就包含两个部分,一个部分是对h做最佳化,一个部分是对n做最佳化。

 
 

根据这个概念做延伸,拿来对不同的error function做最佳化,扩展为 GradientBoost,做法思想和上面一致,只是把里面计算err的部分换成任何你想要的平滑的error function,这就是adaboost的延伸。

在这架构下你就可以使用不一样的hypothesis,而不再必须是binary classification,最常见的是使用real-output hypothesis,就是实数输出的hypotheris。同样在这里有两个步骤,第一步决定一个最佳化的h,再决定一个最佳化的n。

 
 


 
 

例如说通过GradientBoost方式来做regression:

 
 

regression里面用的err就是平方错误;把紫色部分命名为S_n表示的是当前已经算出来的err,然后再向某个方向的移动(红色蓝色乘积);

灰色框第一步:将红色蓝色部分提出到sum外面的时候做的是 err对s 的偏微分,在s_n的位置取值,这是对于每一个点。

灰色框第二步:微分后的结果。

因为前面一项可以看作是常数,我们要做的是最小化,因此就是后面那一项越小越好。后面这一项只要保证两个乘数的符号不同,结果就是负的就是在减小。我们关注的是正负,对于大小要做限制,不然无限大就是最佳解了。

 
 



上面讲到我们要对h的大小做限制,因为其大小对于我们来说不重要,大小的解决是靠后面计算中的n来解决的。

 
 

如果我们直接限制n=1这样来做限制的话,我们求解的就是有条件的最佳化问题,比较难求解;这边类似以前解决有条件最佳化问题的方法,把条件当作是最佳化问题的一个惩罚项直接加入到式子里面去。就是上面蓝色框内的红色括号部分,一个平方项。然后再可以凑出平方来化简,用来凑数的常数项这里都可以随便加,不影响结果。

 
 

常数对于最佳化都没有影响,只有最后的平方项才会影响最佳化,上面式子里面剩下的部分的意思是:我想要找一个最好的h,那么他就是要和y减掉s的平方误差上尽可能的接近,那就是做regression。因此上面问题的最佳解就是拿 (x, y-s) 来做regression,y-s就是余数。

 
 


 
 

上一步说明的是怎么找出一个好的g_t,就是求解一个(x_n, y_n – s_n)的regression问题,下一步就是怎么得到权重n,意思就是在g_t这个方向上面我们要走做大一步。

 
 

这个问题公式化就是蓝色所示,包括分数s部分,y部分,n*g_t部分,其中g_t是固定的。同样我们可以把这个式子化简为一个平方式:里面包含g_t*n,y-s两项。也就是说g_t和余数y-s越靠近越好,通过调节n使得两个越靠近越好的最佳化问题。这就是一个单变数的linear regression的问题。

 
 

这样就得到了每个g的权重n。

 
 


 
 

把上面的概念都合在一起,就得到了 Gradient Boosted Decision Tree(GBDT) 算法:
 

算法经过T轮之后回传一堆g和alpha,然后直接加权就会得到一个比较好的G。

每一轮:首先想办法求解一个regression问题,使用某一个A(base learn method,这里用的就是decision tree)求解从x_n到余数y_n-s_n得到一个g_t;然后通过一个单变数的linear regression就可以得到对应的alpha_t;然后跟新分数s_n。

 
 

这算法可以看作是 Adaboost Decision Tree 的 regression 版本,这算法在资讯检索领域应用广泛。

 
 


 
 

练习

 
 


 
 

至此介绍了这课里面要提到的所有aggregation model,我们来复习一下。

 
 

首先讲的是blending model,就是如果今天我们手上已经有了一些g,我们希望把他们合起来。

 
 

我们讲了三个基本的blending方法:第一个是uniform blending,每一个g地位一样,直接就是民主投票;第二个是non-uniform blending,就是加权投票,这里通过拿g做特征转换,然后再做一个阶段的linear model就可以得到这个权重应该是多少;第三种是conditional blending,就是在不同的时候使用不同的g,这个其实也可以看作是第二种方式的扩展,只是使用的不是linear model,而是non-linear model来得到权重。

特点:越uniform,越是追求的是稳定性,通过不同的g来修正彼此之间的错误;越non-uniform(conditional),越追求的是能力的强大,但同时带来的就是需要非常的小心避免overfitting。

 
 


 
 

然后讲的是learning model,就是手上还没有g,我们需要边学习g边决定怎么把他们混合起来。

 
 

同样讲了三种learning的面向:第一个是uniform的时候:代表性的是bagging方法,通过bootstripping的方法去学到不一样的g,最后直接就是平均就得到G;第二个是non-uniform的时候,就是linear的时候:Adaboost通过改变资料的权重的方式来得到不一样的g,边得到不一样的g边依据他们的表现来决定他们的最终的权重,从最佳化的角度就是要走最大的一步来决定这个g的票数;第三种是conditional,在不同的时候使用不同的g,有一个代表性的方法是decision tree,透过branching,在树里面通过分叉条件去使用不同的g。

 
 

在这一讲里面还把Adaboost延伸到GradientBoost,同样是需要找到一些不一样的g,不同的是不像adaboost一样重新改变权重,而是在regression的设定里面,透过看看剩下多少余数,在余数上面做learning,做完以后同样看能走多大步的方式来得到权重。

 
 

这四个就是aggregation learning model,都非常实用。

 
 


 
 

至此我们有了这些 aggregation model,我们还能进一步融合他们做一些不一样的事。

 
 

  1. Bagging + Decision Tree = Random Forest:使用的是完全长成的decision tree,还透过投影到不同的方向上让decision tree更为强大。

 
 

  1. Adaboost + Decision Tree = Adaboost D-Tree:使用的则是比较弱的decision tree,因为adaboost就是要把很多弱弱的东西合起来把它变强,一开始用太强的没意义。

 
 

  1. Gradientboost _ Decision Tree = Gradient D-Tree:同样使用的也是比较弱的decisiontree。

 
 


 
 

Aggregation 这个把g合起来变成G的概念为什么会做的好?

 
 

  1. 解决的是underfitting:一对弱弱的合起来会变强,原因是aggregation代表的就是feature transform。
  2. 解决的是overfitting:把很多个合起来以后会找到一个比较中庸的选择,原因是aggregation存在regularization的性质。

 
 

适合的使用会得到比较好的结果。

 
 


 
 

练习

 
 


 
 

总结:

Gradient Boosted Decision Tree,一开始现讲怎么把adaboost和decision tree搭配起来,需要引进sampling 和pruning才能搭配得很好;然后讲了怎么从优化的角度来看adaboost,找到好的 hypothesis 就是找一个好的方向,找到alpha其实就是走一个适当的步长,对应到adaboost里面的exponential error这样的函数就是优化问题;我们可以把优化观点下的adaboost延伸到其他不同种的错误衡量,映入了gradientboost,他做的事情就是residual fitting,根据余数还剩多少来更新regression的问题,看看能不能做得更好;最后总结了一下aggregation的方法。

 
 

下一讲:

至此讲完了aggregation,下面开始探讨说如何让机器自动的学到更多更复杂更不一样的特征,不见得是hypothesis的特征转换,而是多种多样。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

Machine Learning Techniques Lecture 10: Random Forest


 
 

内容:

Random forest,演算法就是做bagging,然后在bagging里面做decision tree,为了让decision tree更加随机一点,通常会做randomly projected subspaces,就是随机的选择features下刀。在这样的模型里面,因为采用了bagging,可以得到Out-of-bag(OOB)结果,用来代替validation达到self-validation的效果。有了这个机制,配合premutation test(采用随机排序的特征)来测试每一个特征到底是不是你需要的,其重要性。最后图示该算法的表现。

 
 


 
 

上一讲:

决策树模型,演算法的核心是想办法通过递归的方式切割资料,切割资料的标准就是希望你的资料越纯越好。切开后就得到conditional aggregation的效果,就是根据不同的情况使用不同的小g,就是树叶。

 
 

这一讲:

随机森林

 
 


 
 

先来复习一下两个机器学习模型

 
 

Bagging:通过bootstraooing的方式得到不一样的资料,然后把这些不一样的资料送到base算法里面得到不同的小g,最后让这些不同的小g来投票得到结果。

特点是:小g的变化越大,bagging降低variance的效果越明显。

 
 

Decision Tree:拿到资料后想办法建立一棵树,通过递归的方式利用条件分割资料得到g,分割的依据是资料的纯度。

依据是:variance很大,资料稍微变一点点得到的树可能就差很多。

 
 

两者结合是不是能取长补短呢?

 
 


 
 

Random forest:random(Bagging过程里面的随机性) + forest(Baggin下面的hypothesis是由fully-grown C&RT decision tree得到)

 
 

基本算法:

每一轮的时候想办法用bootstripting的方式得到不同的资料,然后送到完全长成的Decision Tree里面得到g,然后把结果公平的投票得到大G。

 
 

优点:

Bagging的过程用以并行计算,各个独立资料运算无依赖;decision tree的过程也是很有效率;因此整个过程就是很有效率的。

C&RT这个算法有很多好处,可以处理missing feature,multi-class等(见上一课),random算法继承这些好处。

C&RT的问题在于对于资料太敏感,容易overfit,这里通过bagging来缓和这个问题。

 
 


 
 

如何让random forest做的更好。(优化:到处充满随机)

 
 

  1. Bagging + random-subspace C&RT

基本的方法通过bootstript在原来数据里面抽样来得到资料算出小g;这里我们除了在资料端做抽取,还能在feature端做抽取,这个可以看作是特征转换,将原来的高纬度特征投影到低维度空间里面,例如原来有100个特征,每轮随机选择10个特征来处理。这样可以得到更不一样的树。

 
 


 
 

  1. Bagging + random-combination C&RT tree

就是在特征投影的基础上,再选择feature数量也是随机的,而不是使用全部。例如有100个特征,选三个合起来算一个加权的分数再在上面做切割,下一次选五个再在上面做切割,也就是投影的时候不是每次把100个都投影进去。

 
 


 
 

练习

 
 


 
 

Random forest 里面的核心就是 bagging bootstript,这里再来看看 bootstript这个机制告诉了些什么东西给我们。这个机制就是通过在原始资料库里面有放回的随机抽取资料,用来学得小g。把这个随机的结果列成表就如上面所示,在算某个g的时候资料选到就标蓝色,没有就是红色,某个资料从来没被选到过就是 out-of-bag(OOB) data,我们来看看这些资料的奥秘。

 
 


 
 

到底有多少out-of-bag的资料?


假设一共有N笔资料,没被选到的资料数量是N’,如果你抽了N轮的话,一笔资料从没被选到的概率是(1 – 1/N)^N,如果N很大的话可以约等于1/e,也就是差不多1/3左右。

 
 


 
 

Validation的时候:我们把所有的资料切成两个部分,训练资料和验证资料,用验证资料来衡量g的表现,然后选择最好的。验证资料可以这么做的理由是其没有参与训练。

 
 

OOB 资料的特性:对照validation,红色部分没有参与训练,那么就可以用来做validation类似的事情。所以我们可以采用OOB来做g的好坏的验证,但是RT方法的目的是得到G而不是好的小g,这个做法不需要。我们需要的是对G的验证。

 
 

做法:

对于(Xn, Yn),可以当作是g2-gT(G_n^-)这些的validation的资料,但是不能当作g1的validation的资料。每一行都有一个G_n^-。

E_oob(G) = avg(Err(yn, G_N^-(xn))):每一笔资料X_n做出G_n^-来,然后根据yn看看表现就是err,最后把所有的做平均。估算的是G到的表现的是好还是不好。

 
 

通过 E_oob,对于bagging/Random forest来说训练完就可以马上知道G到底好不好。

 
 


 
 

Validation:训练的资料D_train通过算法A得到结果,再比较验证看结果是否正确来得到E_m。

 
 

RF:通过得到资料D的random forest,然后就可以自验证得到 E_oob 来衡量G到底好不好。而且不存在re-training。E_oob衡量G的表现通常相当准确。

 
 


 
 

练习

 
 


 
 

假设你的资料的特征维度是很高的,比如10000个维度,这时候你就比较想减低资料的维度。

  1. 把冗余的特征移掉。(比如年龄和生日两个特征)
  2. 把和你的目标无关的特征移掉。(比如病人的保险状况和是否癌症的判断无关)

 
 

好处:可以看作是对杂讯的排除,不容易overfit,结果会比较好;后续的训练测试效率更高。

缺点:降维度可能在计算上就需要花费很多力气;降维没做好的话就很容易overfit。

 
 

决策树的算法过程本身就包含特征选择的过程,每一步你用什么特征来切分就是。

 
 


 
 

Feature selection 是一个组合爆炸的问题,解决这个问题的一个方法是:把feature根据重要性排序,然后取前n重要的就好了,这种方式在线性模型里面最好用,因为权重决定了影响力。对于非线性模型要理清特征的权重就比较困难,random forest就是非线性模型,但是因为其具有的一些特征使得做特征选择相对比较容易。

 
 


 
 

基本想法:random test

若你现在在做学习,那么对于某一个你认为很重要的特征,加入一些随机杂讯后,你学习就比较困难,但因为重要所以你一定要学会他,花比较长时间。也就是很说你只要比对学习特征的时间和学习加入杂讯后特征的时间的差值,越大说明越重要。

 
 

塞什么杂讯进去?

  1. 平均、随机、高斯分布,这些会影响到目标分布,这一点RF是敏感的,不好
  2. Bootstrip(permutation)方式,目标分布是没有变化的,比较好

 
 

Permutation test:比较我原来的表现和permutation方式做过的资料后的表现的差值。

整体做法就是每一次用permutation方式对第i个维度污染一下,计算一下差值。

 
 


 
 

最后我们怎么来衡量这些performance(i):

 
 

Performance(D):拿这些重新排列的资料来重新做一次训练,得到G然后再做validation来验证,就是使用OOB得到结果 E_oob(G)。

Performance(D^p):对应上面的结果应该是 E_oob(G^p),约等于 E_oob^p(G),这样就可以保持G不变不用再re-train一遍,而是在验证的时候动手脚,验证的时候采用p变化后的资料来算错误率。

 
 

所以:

RF 的特征选择是通过 permutation(随机排序) + OOB(错误衡量) 来得到特征的重要性,然后就选出了重要特征。

这种方式做特征选择非常好用,实际上遇到非线性特征选择的时候常用。

 
 


 
 

练习

 
 


 
 

最后是一个例子

 
 

一棵树

  1. Random combination:把特征随机的集合起来再切分,看上去就是可一切斜的刀。
  2. 粗的标起来的就是bootstript选到的,其他的没选到。

 
 


 
 

T = 100 就是100棵树,最右边的边界已经很复杂了。

 
 


 
 

200棵树,最右边更平滑

 
 


 
 


 
 


 
 


 
 


 
 


 
 


 
 


 
 

对比1000棵树和1棵树

 
 


 
 


 
 


 
 


 
 


 
 


 
 


 
 


 
 


 
 


 
 

投票机制会消除一定的杂讯,让边界平滑。

 
 


 
 

RF的缺点:随机相关,对于变化敏感,因此需要大量的树来尽量减少random对结果的影响。

 
 

树的棵树越多越好,理论上无限多棵最好,实际应用的时候看你的G是否稳定,如果树的数量增加很多G稳定的时候就差不多了。

 
 


 
 

练习

 
 


 
 

总结:

Random forest,演算法就是做bagging,然后在bagging里面做decision tree,为了让decision tree更加随机一点,通常会做randomly projected subspaces,就是随机的选择features下刀。在这样的模型里面,因为采用了bagging,可以得到Out-of-bag(OOB)结果,用来代替validation达到self-validation的效果。有了这个机制,配合premutation test(采用随机排序的特征)来测试每一个特征到底是不是你需要的,其重要性。最后图示该算法的表现。

 
 

下一讲:

这里讲完了random forest,是bagging和decision tree的结合,下面讲boosted decision tree,就是adaboost和decision tree的结合,以及延伸到不只是classification的情况下的使用。

Machine Learning Techniques Lecture 9: Decision Tree


 
 

内容:

介绍了Decision Tree模型,他的hypothesis就是对于不同的条件,不同的路径上面有不同的小g;他的算法就是把这种树形结构通过对资料越切越纯直到不能再切为止,递归的建立起来。一种实例算法C&RT则是对Decision Tree进一步做了四个决定:怎么做regression,怎么砍树,怎么处理类别输入,怎么处理特征丢失。最后可视化的举例看这个演算法的演进过程。

 
 


 
 

上一讲:

Adaptive Boosting 演算法,透过调整每一笔资料的权重的方式来得到不一样的hypothesis,同时在计算过程中决定每一个hypothesis的权重,然后用linear 的方式合起来,这样的方式被证明可以让分类结果变得比较好。

 
 

这一讲:

Decision Tree

 
 


 
 

我们先来看看 aggregation model:就是可以通过很多的g合起来变成大G来提升效果。这包括两种主要的面向。

Blending:我们已经得到了一些小g,可以透过uniform/non-uniform/conditional的方式把他们合起来,这三种情况下的blending的做法叫做 averaging/linear/stacking。

Learning:我们并不知道有哪些小g,需要边学习小g,边把他们合起来,同样可以透过uniform/non-uniform/conditional 的方式把他们合起来,这三种情况下的blending的做法叫做 Bagging/Adaboost/Decision Tree。

 
 

Decision Tree 就是补完这张表格,在不同情况下使用不同的小g,而且是边学习边合起来使用。这个方法的起源非常早,都比机器学习这个名词的出现还早,其做法就是模仿的人类的认知决策过程。

 
 


 
 

什么叫做Decision Tree?

 
 

这里是一个例子:你到底要不要下班后打开线上课程学习?

首先看是否下班早,早回则看一下是否有约会,晚回则看一下是否是作业的deadline,再确定会不会打开线上课程。

 
 

我们怎么来表达这个hypothesis?

 
 

小g:叶子节点,最后的决定;q:非叶子节点,条件,每一个都是比较简单的判断;所有的合起来就是G。

就是模仿人类的决策过程。

 
 


 
 

Decision Tree 也可以看作是:

每一个非叶子节点产生的每一个分支,都是一颗子树。b代表的就是分支,G_c就是在c的情况下的子树。

把一颗大大的树拆成几棵小树,递归定义。

 
 


 
 

在讲算法之前,先告诉大家一下有关Decision Tree的Disclaimers

 
 

优点:描述了整个做决定的过程,人很好理解,具有可解释性;非常简单;计算效率高。

缺点:基本没有什么理论保证,专注于流程设计;怎么去设计分支很难;通常没有什么比较具有代表性的好坏的算法。

 
 


 
 

练习

 
 


 
 

上面的黄色框表示的是递归公式表示的Decision Tree,够过这个公式可以把其演算法写出来:

输入是所有的资料,目标是产生一个树(G),过程中我们需要知道的是怎么产生分支(g)。

  1. 先看怎么做分支
  2. 根据分支分块
  3. 每一个分块用来学出小小的树,看是否要停下,不停下的话每棵小树再继续上面三步
  4. 所有的小树合起来就是G

 
 

一共包括四个决定:要分几支,怎么做分支,什么时候要停下开始组合G,叶子节点的结果是什么。对于每一个具体的Decision Tree演算法,都是对上面的四个决定做了独特的设计。

 
 


 
 

今天要给大家介绍的演算法: Classification & Regression Tree (C&RT)

 
 

  1. 每次一刀切成两份,就是分成两支(binary tree);
  2. 最后回传的g是constant,叶子就是一个常数,常数是由当前叶子范围内的Ein是最小的;

 
 


 
 

  1. 利用decision stump来切两半,也就是说只看一个feature,并通过这个feature把资料分成两半。

    切开后怎么样是最好呢?purifying:看切开后得到的资料看起来比较纯(y近似),用切开后两边会最纯的情况作为这次的切分。也就是说切开后纯度越来越高。

 
 


 
 

怎么衡量纯度?

可以看切开后要回传的常数是否够好来描述纯度,也就是用Ein来衡量。一般使用的时候classification的时候Gini比较常用,regression的时候regression error比较常用来衡量纯度。

 
 


 
 

  1. 所有的y都一样的话会被迫停下来,完全的纯,回传常数;

    所有的x都一样的话也会被迫停下来,完全没有下刀的情况;

    长到被迫停下来的树叫做fully-grown tree

 
 


 
 

练习

 
 


 
 

把 C&RT 做的四项选择写入到 decision tree 的算法里面就得到了 C&RT 的算法描述。上面的橙色,红色,绿色,蓝色对应的就是四个决定。

这种算法的一大好处就是处理multi-class classification和binary classification一样简单。

 
 


 
 

按照上面讲的 fully-grown tree 的切割方式来切的话,一定会得到Ein=0的树。但是这样是会比较不妙,会有overfit。

 
 

我们需要一些regularizer的机制来控制复杂度来放置overfit。

 
 

Pruned Decision Tree:

一种方式是控制树叶的数量,也就是不让切特别多刀,树叶的数目和切的刀数相关。

所以做法可以是把所有的树都做出来,看看每棵树的Ein是多少,算算其复杂度是多少,然后用lamda平衡一下,我们不要只选择切的很深的Ein很小的树。

这件事情不那么好做,我们要考虑遍历所有的可能的树的结构不现实。

 
 

实际上的做法:

首先得到一颗完全长成的树,然后尝试着去合并一次两片叶子,做所有的情况,找出只合并两片叶子Ein最小的树G_1。再从这摘掉一片叶子的树出发在同上面的方法再去摘一片叶子,得到最好的摘掉两片叶子的树G_2。以此类推得到G_n。

我们接下来就是在这些摘掉x片叶子最好的树里面做选择,找到一个平衡的最佳解,就是去确定lamda,方法是validation。

 
 


 
 

C&RT 还有一些其他的特征:

 
 

【类别支持】

  1. 输入部分不一定是数字,可能是类别,例如病人的症状等,会影响怎么去做切割。

这时候需要用 Decision Subset 来做切割:可以穷举类别,人为定义左右或者大小来做。

 
 


 
 

对于人来说:

例如我使用体重来区分人群,但是有个人进来忘了称体重,怎么办?可能是去马上去量体重;可能通过目测身高估体重,所以可以改通过身高区分。

 
 

【支持特征丢失的资料】

  1. 对于特征丢失的资料,怎么用我们的Decision Tree来处理呢?

训练的时候会为每个特征找一些替代品,通过替代品做切割得到的结果要和原来的方式类似,替代品是训练的时候就已经学习好了的。

 
 


 
 

练习

 
 


 
 

一个例子

 
 


 
 

确定下刀,两边各自组成树,合起来就是大树。

 
 


 
 

第二刀

 
 


 
 

第三刀

 
 


 
 

第四刀

 
 


 
 

区域都纯洁了

 
 


 
 

回传叶子节点的类型

 
 


 
 

递归上一层

 
 


 
 

再上一层

 
 


 
 

回到大树

 
 


 
 

和Adaboost对比:Adaboost每一刀一定是贯穿整个区域,但是decision Tree就不一定,因此相对来说比较有效率。

 
 


 
 

复杂的例子

 
 


 
 

C&RT 算法的好处:

  1. 人看得懂的决策方式
  2. 可以容易的处理多类别分类
  3. 可以容易的处理类别输入
  4. 可以支持测试资料的特征残缺
  5. 训练测试都很有效率

几乎没有其他的模型有这么多的好处,因此也是一种常用的方法。

 
 

实际上还有 C4.5 这种 decision tree 算法,自己可以去看一下做了哪些特殊决定得到的。

 
 


 
 

练习

 
 


 
 

总结:

介绍了Decision Tree模型,他的hypothesis就是对于不同的条件,不同的路径上面有不同的小g;他的算法就是把这种树形结构通过对资料越切越纯直到不能再切为止,递归的建立起来。一种实例算法C&RT则是对Decision Tree进一步做了四个决定:怎么做regression,怎么砍树,怎么处理类别输入,怎么处理特征丢失。最后可视化的举例看这个演算法的演进过程。

 
 

下一讲:

至此讲完了Aggregation的基本模型,下一讲进入一个更高的境界,开始把已有的aggregation方法混起来用,叫做Aggregation of Aggregation。

Machine Learning Techniques Lecture 8: Adaptive Boosting


 
 

内容:

介绍了 Adaboost 演算法,一开始先给大家一个小学生课堂的例子来告诉大家这个演算法想像上是长什么样子的。这算法的关键是每一轮的时候透过重新的给每一个example不一样的权重,提高错误的权重,降低正确的权重来得到不一样的g,最后再把g整合成G。最后给了一个adaboost配合decision stump以后的实例,可以工作的很好。

 
 


 
 

上一讲:开始讲aggregation model,就是想办法把很多的小g合起来变成一个更符合你需求的大G。然后讲到blending,就是如果你已经有很多小g在手上的时候,你可以让他们求平均或者加权投票或者更复杂的非线性组合它们。那如果手上只有一堆已有的资料,那么可以通过bootstrap的方式得到一堆资料集,然后得到一堆小g求大G,这样的演算法叫做bagging。

 
 

今天从这系概念出发,讲一个有趣的演算法。

 
 


 
 

举例:老师交学生辨识图中有没有苹果做法

 
 

首先去网络上手机苹果图片。

 
 


 
 

收集了10张苹果图片,10张不是苹果的图片。老师就是想通过这些数据来学到怎样区分图中有没有苹果的二元分类。

 
 


 
 

放到一起,前十张是苹果,后十张不是苹果。(对应到机器学习里面的supervised learning,告诉x,y)

 
 

第一个学生觉得:苹果是圆形的,不是苹果的很多不是圆形。

根据是不是圆形分类,有些是对的,有些是错的(蓝色的就是错的部分)。

 
 


 
 

为了让学生更认识到这种分类方式的缺陷,老师就把已经作对了的图片缩小,没做对的放大,突出错误的地方。

 
 

然后再问学生还有没有其他的规则来分类?

 
 

第二个学生觉得:苹果是红色的,不是苹果很多都不是红色的。

根据颜色分类,有些是对的,有些是错的。(蓝色标出了错误的)

 
 

同样老师标出了错误的,让后放大缩小来突出错误的。

 
 


 
 

然后再问怎样的才是苹果?

 
 

第三个学生说苹果也可能是绿色的,也是有对有错。

然后老师同样的去放大缩小,然后再以此类推。

 
 


 
 

经过这样的反复,最后会得到的分类结果一般来说总比第一个学生说的单一的分类方法效果好。

 
 


 
 

学生就是小gt,就是上图的水平垂直线;整个班级就是大G,就是把小g融合起来,就是上面弯弯曲曲的黑色边界,很顺利的分开了圈圈叉叉;老师的作用是每一次都强调一下犯错误的地方。

 
 

这就是今天讲的演算法的基本思路。

 
 


 
 

练习

 
 


 
 

我们先从Bagging开始讲起:其核心就是bootstraping抽样动作。如果我们假设得到上面所示的一笔资料四个数据,那接下来做的就是在这个数据的基础上让Ein最小。那么从原始的数据库来看,资料可以标示为资料+U(表示当前这个取出的新的data包含这个数据的个数)。这时候Ein如何方便的标识:算一笔资料的错误率,然后乘上系数U,如上图绿色框所示。

 
 

所以Bagging做的事可以看作是透过bootstrap的方式产生一组U,然后去最小化Ein^u。

 
 


 
 

上面就是一种 Weighted Base Algorithm,就是演算法带有权重参数,可以应用在已有的各种算法里面,譬如SVM(上限发生变化),Logistic regression(抽样的时候U是抽中的权重),蓝色的部分就是原来的公式会变化的部分。

 
 


 
 

如果我们的 weighted base algorithm 会根据这些u来决定,那么我们应该怎么去改变u让得到的g越不一样越好?(上一讲提到过,如果g越不一样,aggregation做的结果越好)
 

g_t 是由 u_t 来当weight,g_t+1 由 U_t+1 来得到的。如果g_t在使用u_t+1的时候非常的不好,后续的过程中就会选到和g_t很不一样的g_t+1。比如对于binary classification,我们的期望是让g_t在u_t+1的时候分类结果最差,就是1/2,和丢铜板一样。

 
 


 
 

怎么做,如红色的部分公式,方块代表犯错误的点的u加起来是多少;圆圈代表的是没犯错的点的u加起来是多少,然后我们想做的就是让犯错的u和没犯错的u调到一样。

举个例子见上面的表格,我们先看现在t时刻的犯错的u=1126,没犯错的6211,目前不相等。然后用放大缩小的方式让两边相等,就是左边的乘6211权重,右边乘1126权重,就等了(或者可以乘以相应的对方的比例)。【简单地说就是配上系数使两边相等,这样下一轮得到的数据用这一轮的分类结果表现就应该会非常差】

 
 


 
 

练习

 
 


 
 

上一小结说的就是 optimal re-weighting:为了让g_t 和 g_t+1 很不一样,对犯错误的点放大。按照上面的求解策略,这里可以定义一个方块t参数,对于错误的和正确的点做如上蓝色框所示的参数相乘。

 
 

当错误率必定是大于1/2的时候,方块t一定大于1,也就是说错误的一定是放大,正确的一定会是缩小操作。(对应到了分苹果的例子的老师的操作)

 
 

这个就是adaboost里面得到不一样的g的方法的理论依据。

 
 


 
 

至此就有了一个初步的演算法的长相:

  1. 参数化原来的bootstrap操作,则可以看作是我们在每一轮里面得到g都是透过u得来的,u就是每个example的权重。
  2. 在每一轮的时候,透过方块t来更新u,目的是让现在的g在下一轮的分类中变的很烂,选出的g就会很不一样。
  3. 透过这些不一样的g来合成大G。

 
 

但是还存在一些问题要解决:

  1. 一开始的u是多少,就是1/N,每个点都一样,让一开始的结果和Ein最小。
  2. 合成G的时候怎么弄,g1对Ein是最好的,g2对Ein就很差了,也就是说各个的权重不一样,不要uniform。

 
 

下面要讲的算法就是在产生g的过程中顺便决定了怎么样把这些g合起来(aggregate linearily on the fly)。

 
 


 
 

算法:

一开始u = 1/N;然后对于每一步有三件事情做,

  1. 生成由u表示的dataset来得到g;
  2. 由u的当前结果来更新u为下一轮做准备;
  3. 计算合成的时候的参数alpha;

最后合成的时候直接每个g乘以自己对应的alpha得到G

 
 

我们希望每个g都很好,很好的概念是方块t应该要很大,所以alpha可以看作是方块出来的某一个单调函数的结果,方块越大,alpha越大。

Alpha = ln(方块t),这是设计这个演算法的人做的选择。物理意义会是 1/2的错误率的时候权重为0,错误率为0的时候权重为无穷大,还是很合理的。

 
 

Adaptive Boosting 包含三个元素:

  1. 通过产生的数据集得到的g(Student)
  2. 用方块t对资料放缩重要性(teacher)
  3. 由g合成成G(Class)

 
 


 
 

Adaptive Boosting (Adaboost) Algorithm 算法:

一开始u = 1/N表示所有的点重要性都一样;然后对于每一步有三件事情做,

  1. 得到一个g;
  2. 把错误的乘以方块t,正确的乘以方块t;
  3. 决定alpha;

最后合成的时候直接每个g乘以自己对应的alpha得到G

 
 


 
 

Adaboost的理论特性,我们来看看把VC bound 用在这里的话会得到什么样的保证。

 
 

Eout(G) <= Ein(G)(已经看过的资料上的表现) + 模型复杂度付出的代价(绿色部分,Dvc(h)表示的是g付出的代价,还要合上T,蓝色部分是标准的Dvc告诉我们的事)

 
 

这个演算法得很好的性质:我们可以在相对很短的时间内把第一项(红色部分)做的很小,大概只要花log(n)轮就能做到Ein(G)为0,也就会把第二项做到很小。

 
 

boosting的意思是:我们的任意g只要比乱猜好一点,那么我们就可以让整个演算法越变越强,强到Ein是0,Eout也是很小。

 
 


 
 

练习

 
 


 
 

上面讲到我们弱弱的演算法g需要比乱猜好一点,什么样的演算法可以做到这件事情呢?

 
 

回头看ML foundations作业里面有一个特殊的模型 decision stump,如上所示公式。

包含三个参数:特征是什么,你要切在那里,正方向是哪面;通过搜寻有限多的组合得到最好的decision stump。这是少数真的能把Ein做到最好的hypothesis,对于weighted Ein也可以搜寻所有的组合想办法做到最好。

物理意义就是二维平面上支持切垂直和水平刀。复杂度是 资料的数量乘以feature的数量。

 
 

Decision stump 单独用能力就是太弱了,因为只能切垂直水平刀,那么我们来配合使用adaboost。

 
 


 
 

资料

 
 


 
 

切一刀,放大的三个圈圈就是犯错误的,没犯错误的缩小。

 
 


 
 

再切,以此类推

 
 


 
 

已经得到了非线性边界

 
 


 
 


 
 


 
 

切完了

 
 


 
 

复杂的例子

 
 


 
 

Adaboost + decision stump 实际上确实也蛮好用的,用于实时人脸辨识。

 
 


 
 

练习

 
 


 
 

总结:

介绍了 Adaboost 演算法,一开始先给大家一个小学生课堂的例子来告诉大家这个演算法想像上是长什么样子的。这算法的关键是每一轮的时候透过重新的给每一个example不一样的权重,提高错误的权重,降低正确的权重来得到不一样的g,最后再把g整合成G。最后给了一个adaboost配合decision stump以后的实例,可以工作的很好。

 
 

下一讲:

Bagging 是 uniform aggregation;Adaboost 是 linear aggregation;下一讲给大家介绍 conditional aggregation 的方法。

 
 

 
 

Machine Learning Techniques Lecture 7: Blending and Bagging


 
 

内容:

介绍了Blending和Bagging的方法,两者都属于Aggregation这个大家族,Aggregation要做的事情就是把一堆的小g合起来变成一个更符合需求的大G。最基本的方法就是求平均,算术平均,更进阶的方式是如果你今天想做linear/non-linear的化其实只要做一个two-level learning就可以做到了。最后我们介绍了如何通过 bootstraping 从已有的固定资料得到不一样的hypothesis,然后再合起来的方法。

 
 


 
 

我们之前讲到的是Kernel Model,做的事情是把很多很多的feature包在kernel里面,然后用不同的机制去求解。我们把kernel model延伸到可以做regression,你可以把原来知道的ridge regression利用representer theorem来得到他的kernel的形式,你也可以参考SVM设计一个新的formulation来得到sparse solution 的Kernel 形式。

 
 

今天开启一个新的主题,如果我们得到了一些hypothesis,这些hypothesis可以帮助我们做预测,我们怎么把这些有预测性的hypothesis合起来让他们变得更好,这样的模型叫做Aggregation model。今天讲两个常用的model,blending and bagging。

 
 


 
 

先来想想为什么想要用aggrregation?

假设今天你有15个朋友,每个人都告诉你明天股市的涨跌预测分析,那你听了以后作的决策是什么。

 
 

你的决策想法可能会有:

  1. 你的朋友里面有人炒股比较厉害,可能他的预测比较有参考价值,因此选择一个可以信赖的人的结果。(就是validation)
  2. 你的朋友每个人都有不同的专长,不知道相信谁,投票决定,看猜测涨的人多就决定相信涨。
  3. 如果你的朋友的炒股能力可以参数化,那就是加权投票看结果。
  4. 你的朋友有的人擅长科技类股票,有的人擅长能源类股票等等,所以呢在不同的条件之下就相信不同的人。

 
 

我们要做的就是把这些情境的处理对应到机器学习里面。做的这件事就是叫做 aggregation model 在做的事情。

 
 


 
 

我们把上面的口语化的表述数学化。

 
 

每个朋友就是 hypothesis 就是 g_n;

  1. 就是选Err_val最小的
  2. Uniformly 和
  3. Non-uniformly 加权和
  4. 函数代表了成立条件再乘以g_n

从一到四更加的泛化,2包含1,3包含2,4包含3。

 
 

Aggregation model 就是这么非常包山包海的丰富,未来的五讲会分别去在各个方向作介绍。

 
 


 
 

先来看比较简单的,比如靠的是selection,从里面选一个最好的。

黄色框就是公式表示,其实在前面的validation的时候的方法就是用到了selection,选一个最好的。

我们使用training error而不是使用validation error是否可以?很危险,非常可能overfitting。

这种方式里面的一个重要假设是:你想要选到一个好的g^-_t最后才能够选到好的。如果你的候选结果都是不好的,那就是废渣里面再怎么选也是废渣。

 
 

如果只靠选择的话,我们只要有一个强者就好了。

但是aggregation想象的是如果今天我们一堆看起来弱弱的,但是其实还算是可以的hypothesis,我们能够不能依靠集体的智慧让最终结果变得更好。也就是说不是靠一个很强的来做最终结果。

 
 


 
 

先来思考一下为什么aggregation可以做得更好?

 
 

先看左边的图,如果要求只能用水平垂直的线来分类,单个怎么样都做得不大好,如果多条水平垂直的线合起来,那么就有左图的折线,把圈圈叉叉完美分开。可能代表aggregation相当于拓展了模型的分类能力。

如果今天有一堆hypothesis如右图,每一条结果都还不错,如果让灰色的线投票的话会很接近比较中庸的线,就如图中的黑色实线,也就大概比较宽的线。这可能代表了aggregation可以有regularization的能力。

也就是说aggregation同时具有让模型更加复杂和简单的能力,如果你能利用好的话,就能得到比较好的学习结果。

 
 


 
 

练习

 
 


 
 

下面我们开始讲怎么样把这些hypothesis合起来。

 
 

第一个概念: blending


Uniform Blending(voting) for classification

这一般使用在我们手上已经有一堆g,怎么把他们的结果合起来变的更强。黄色框表示的就是公式化的投票方式的结果的表述。如果你所有的小g大体都是相同的,那么你的大G也就和他们相同。如果你的一堆小g结果都很不同,怎么去融合?

如右边的图,在横竖分成区块后,每一个区块单独进行投票,少数服从多数,就得到了这个折线结果。也就是说如果今天分类结果很不一样,那么我们可以通过民主投票的机制来获得更加复杂的分类边界,对于多类别的分类也可以做一样的事情。

 
 


 
 

Uniform blending for regression

把大家的输出都通通的加起来求平均得到大G。如果小g统统都一样,这种方式没带来什么好处,但是如果小g比较不一样,可以抵消一些低估和高估,得到一个比较中庸的结果比较好。

 
 

从blending用在classification/regression看出,如果我们这个aggregation要起作用,很重要的是我们的小g要diverse,就是意见要有不一样,这样融合的家过会比较好。

 
 


 
 

我们来进一步分析为什么uniform blending为什么会表现更好?

 
 

x表示输入,在下面都是一样的,写着比较麻烦,就省略了,这里推到的目标是把单个的小g和f的平方错误 的平均 和 大G和f的平方错误联系在一起。

首先展开,再代入G替换一次小g平均,根据目标凑G-f平方,再凑一个大g小g平方,的结果。

蓝色框表示的是单一的小g的结果,如果是对所有的小g则是下面黄色框所示:所有的小g的E_out = 大G的E_out + 大小g的平均的期望值的差(这一项一定是正的)。所以小g的平均E_out要比大G来得大,所以就证明了uniform blending是有好处的。

 
 


 
 

如果今天有这么个抽象的机器学习过程,在每一轮里面有n笔资料,通过已有的演算法来求每一笔资料的小g,结果就是取小g的平均。把上面这件事做无限多次,求平均期望值。

灰色部分就是写出的式子

物理上的解释:演算法表现的期望值 = variance(小g的特性表现) + bias(小g的共识表现),在统计的书里面比较常见,平均的过程就是消除前面这一项,让意见趋于一致。

 
 


 
 

练习

 
 


 
 

接下来讲的是 linear blending (就是加权平均)

什么样是好得票数,能够达到E_in最低的是好的票数,也就是说我们要调整我们的alpha让Ein最低,限制是每一个alpha都是大于等于0的。

因此红色框表示的就是regression的时候的公式,换成后边的框所示,和我们之前讲过的 transform 过的 linear regression 差不多形式,区别在于有alpha>0的条件。也就是说整个学到好的alpha的过程,就是之前讲过的two-level learning,在probilitistic SVM的时候提到的。现在的two-level是先得到一堆g,在做linear regression得到alpha。

 
 


 
 

问题是有了alpha>=0的限制。

如果alpha<0,则表示的是结果是反的,所以把符号相反。举个例子比如你有一个算法做binary classification得到的结果可是说是得到的结果99%是错的,那么反过来用正确率就非常高。

所以真正在做linear blending的时候忽略这个constraint 也没啥问题。

 
 


 
 

还有个问题是小g通常是怎么来的呢?

从各自不同的model通过求最好的E_in得到的。以前曾经提到过如果你选择模型的时候用的也是E_in的时候,你选的是best of best,你要付出的代价很大,所以后来说为什么我们要用validation而不是Ein来做选择。(譬如你要选的是两个班的第一名,你要付出的代价是查询两个班的结果)

这边类似,linear bendling包含了selection,alpha是说到底我的validationerror有没有最小。也就是说如果你用E_in来做blending,你现在选的是把所有的第一名集合起来做,你要付出的代价比best of best还要高(因为你包含best of best当作你的特例),也就是更危险。因此通常我们不建议使用Ein来学alpha,因为很容易就overfit了。【就是说g用了Ein学,alpha不要用Ein再来确定了】

这里建议在算alpha的时候,不要用training的Ein来算,而是采用E_validation来操作。

 
 


 
 

因此真正的操作过程【就是只从用来验证的资料来确定alpha】:

 
 

从一个比较小的Dtrain得到你的一堆g-,然后把你的validation set里面的资料透过这些g-转换成z空间的资料,我们把这个转换叫做phine-。

做完转换后你就可以把你的linear model用在这些新的资料上面求出alpha,这时候G就是这些alpha和phine(x)的线性组合的内积。

这里用的是phine(x)而不是phine-(x)是因为我们希望透过phine,也就是真正的g而不是g-,来让我们的表现更好。

 
 

对于non-linear blending(stacking):同样是做完转换的资料z,不再用linear model,而是任何的model Any,学习到g,最后一样得到的是g和phine(x)的组合即是G回传回去。

Any-blending:模型能力强大,但更容易overfit,使用上要非常小心。

 
 


 
 

故事:

11年的时候KDDCup一个冠军的方法:先学到小g(single model),然后做any-blending,融合后变成一下更强的G,然后再做一次linear-blending,得到了最好的结果。

 
 


 
 

练习

 
 


 
 

Blending:如果你已经透过某些方法得到小g,我们怎么去合起来,我们可以非常公平的投票,也可以加权投票。

更多的时候你更想要知道小g到底是怎么来的,我们能不能一边学小g,一边把它合起来,下面我们会讨论这个问题。

我们首先来看什么时候可以得到不一样的小g:

  1. 从不一样的模型得到不一样的小g
  2. 同一个模型,不同的参数得到不同的小g
  3. 演算法本身就存在randomness产生的不同的小g
  4. 你的资料存在randomness产生的不同的小g

 
 

下面我们探讨能不能拿同一份资料来制造很多的小g?

 
 


 
 

我们回头来看之前推导的理论结果:Bias + variance 概念就是强化共识

前提是我们需要很多不同的资料来获得共识,但问题是我们这里考虑得是同一份资料,怎么处理呢?

 
 

我们的目标是无限多小g的平均,但是我们做不到,因为首先没有办法产生无限多,其次资料要是新鲜的也做不到,现在只有现存的一堆资料。

所以妥协:有限多的大量的数据,通过已有的资料产生长得像新鲜的资料的资料。

 
 

怎么做?

统计学工具:bootstrapping,从你手上已有的资料去模拟不一样的资料。

 
 


 
 

bootstrapping:

重新的从我手上的资料里面去取n笔,取一笔记录一下再放回去,再取一笔记录再放回去,以此类推。有放回的抽样得到的资料在统计学上叫做 bootstrap sample(D_t)。

 
 

Virtual aggregation:每一次找一个新的小D_t得到新的小g_t,最后平均

Bootstrap aggregation(又叫做bagging):每一次从手上资料生一个D_t得到新的g_t,最后平均

 
 

这是一个meta algorithm,就是可以附着在任何基本演算法基础上使用。

 
 


 
 

举例:

已有的资料做bootstrap后得到的资料集用Pocket 算法算出来的结果是浅灰色的线,生出了25条;然后把线合起来得到黑色的线,效果相对会比较好一点。

 
 

这边要注意的是:你的演算法对随机是敏感的,得到的小g越不一样,效果会比较好。

 
 


 
 

练习

 
 


 
 

总结:

介绍了Blending和Bagging的方法,两者都属于Aggregation这个大家族,Aggregation要做的事情就是把一堆的小g合起来变成一个更符合需求的大G。最基本的方法就是求平均,算术平均,更进阶的方式是如果你今天想做linear/non-linear的化其实只要做一个two-level learning就可以做到了。最后我们介绍了如何通过 bootstraping 从已有的固定资料得到不一样的hypothesis,然后再合起来的方法。

 
 

下一讲:

我们你能不能得到比bagging更不一样的hypothesis呢?

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

Machine Learning Techniques Lecture 6: Support Vector Regression


 
 

内容:

和大家讲了support vector regression,一开始的切入点就是把我们原来会的ridge regression变成kernel的形式,我们可以通过representer theorem来做到这件事情。不过呢这时候的beta是dence的,计算量太大,因此我们从一个 regularized tube error来做推导导出了对偶问题,根据KKT条件求解二次规划,得到sparse的beta的结果。

最后总结了一下kernel model以及使用情况,这里要特别提醒的是这里提供了无限强大的工具,但是你要仔细的去对症使用。

 
 


 
 

上一次:kernel logistic regression

如果我们想要把SVM这样的方法用在soft classification上面的话,我们可以用two-level learning的方式,先做SVM,然后再把SVM做出来的东西丢去logistic regression里面微调一下得到结果;或者是我们可以使用representer theorem直接把logistic regression变到一个kernel的形式来求解。

 
 

Support vector regression

我们从上面这个新的技巧出发,来探讨怎么把regression变成kernel的形式。

 
 


 
 

上一次讲到:representer theorem

什么时候我们的W可以变成一堆z的线性组合呢?如果你要处理的是一个有L2-regularize的linear model,那么你要处理的W=可以变成一堆Z的线性组合,也就是可以把它变成kernel的形式。

 
 

我们今天要探讨的就是怎么把regression变成kernel的形式。

regression的做法采用的是让squared error最小来达到结果。我们来看怎么在此加入kernel的概念。Ridge regression 表示的就是使用上面的错误公式计算的linear regression。

 
 


 
 

如果我们今天要做的是 Kernel Ridge Regression 的话,我们要求解的是上面黄色底框的问题。我们最后的最佳解能表示成z的线性组合。因此如上面的图示,我们可以把存在beta的公式代入原来的式子,就可以得到求解beta的式子(蓝色底框),kernel也就出现了。这也就可以看作是beta的线性模型,前面部分和beta的复杂度相关,后面的是beta通过kernel转换过的资料和。然后再考虑矩阵表达形式,就可以得到蓝色框内最后一行的结果。

 
 

这样就是把ridge regression变到了kernel的世界里了。剩下的问题是我们要怎么样去求解出最好的beta。

 
 


 
 

黄色框所示的式子就是上面一部得到的,最后ridge regression表示成了beta的函数的结果。这是一个beta的二次式,这是一个无条件的最佳化问题,算梯度=0(蓝色部分是为了后面讨论方便加入的不影响结果的变化的项),再整理一下得到最终结果。

 
 

然后我们想要的是梯度为0,其中一个是beta的系数是0,就是一个最佳解而且一定存在(lamda一定是大于0的,合法的K一定是半正定的)。这样你就可以求出最好的beta是什么,然后就有了最好的kernel ridge regression结果,但是直接求解的话,kernel矩阵大部分都不是0,复杂度是O(N的三次方)。

 
 

所以理论上我们现在可以很轻易的做non-linear regression。

 
 


 
 

比较,同一个资料做不同的学习。

左边是linear ridge regression:求解的是线性的分类结果,如要做的反矩阵是d*d大小。能力有限只能是线性,计算效率搞高。

右边是kernel ridge regression:求解的是kernel代表的分类结果,可以使非线性的,如果做的话反矩阵是N*N的大小。自由度高,计算效率低(复杂度和计算的资料的量有关)。

 
 

这里再次说到了 linear 和 kernel 的差别,效率和计算量之间的权衡。

 
 


 
 

练习

 
 


 
 

我们现在有了 kernel ridge regression,也可以拿来做classification,这时候叫做 least-squares SVM(LSSVM)。Least-sequares 描述的是这里使用的是regression的error来做classification。

 
 

我们来看拿同样的资料跑

Soft-margin gaussian SVM:只有少部分是support vector,好的性质是alpha是sparse的。

Gaussian LSSVM:每一个点都是support vector,这意味着未来做prediction的时候花费也会很高,也就是g会很肥大。这里的数学原因是求出来的beta大部分都不是0.(实际上 kernel logistic regression 求出来的也是dense的beta,也存在这个问题,train和prediction的时候花费代价都很大。)

从边界看差别不是很大。

 
 

那我们来考虑:有没有办法做出sparse beta的kernel ridge regression?

 
 


 
 

我们考虑一个很特别的问题叫做: Tube Regression

以前我们做regression的时候就是比较我们的数据和线的边界差多远,越远扣分越多。现在我们容许存在一个中立区,中立区里面的数据不扣分,中立区外面的数据才扣分。上面公式epson就是中立区的半边长,错误公式就是灰色框表示的部分,这个error叫做 espon-insensitive error。

 
 

然后,接下来做的就是把这个tube regression透过上一小结的方式来做推导求结果。

 
 


 
 

比较一下

Tube regression:蓝色里面不扣分,外面的才扣分,扣得是长度。

Squared regression:都要算扣分,扣得是长度的平方。

如果把两者的错误画出来的话,蓝色线表示的是tube,红色线表示的是squared,在比较中间的区域两者是约等于的,往外面走的时候区别就很大了,tube成长比较平缓。tube的最大好处是能够得到sparse beta solution。

 
 


 
 

然后我们来看怎么求解 L2-regularized tube regression。

 
 

如果直接去求解的话,因为是一个regularized formulation,所以理论上用任何unconstrained的方法去求解w。但是可能存在不可以微分的地方,你需要额外的考虑,比较复杂。如果要用上kernel的话,使用represerter是没有问题,但是做完之后你不能知道会不会得到你想要的sparse的beta。

 
 

那我们来看原来的SVM的求解,如果直接求解一样遇到上面的问题,但是我们把它转化成一个QP问题求解比较容易。这里是通过KKT条件的求解得到的sparse结果。

 
 

所以,我们来模仿标准的SVM求解来得到sparse的beta。所以我们来把原来的式子写成和标准SVM接近的式子,如上面底下的黄色框所示。

 
 


 
 

有了式子,怎么去化简求解呢?

 
 

原来SVM里面拆max是通过引进变数kesi_n,这里也是,然后加入到最佳化的条件里面去。然后再拆掉绝对值,变成两个部分,又多了两个条件。这样我们就得到了一个二次规划的问题,且条件是线性的。

 
 

这就是标准的 Support Vector Regression(SVR)的primal问题:两个条件下最小化regularizer。

 
 


 
 

我们从图来看这个问题:

在tube之外的部分就需要算kesi的结果,边界里面的就不需要。要求解的最佳化就是把红线的错误都加起来,以及reguarizer那一项,这样子去找出一条最好的线作为结果。

 
 

参数C:控制的是在乎regularization多一点还是tube violation。

参数epson:你的tube的宽度是两倍的epson。

二次规划问题:d+1+2N个变数,4N个条件。

 
 

然后考虑怎么把对空间维度的依赖d去掉,和之前的做法一样,转化成对偶问题,然后通过kernel trick求解,见下一节。

 
 


 
 

练习

 
 


 
 

转对偶问题:

 
 

首先需要的是 lagrange multipliers,然后写下 lagrange function,然后对里面的变数做微分,然后得到KKT condition(灰色框所示),然后替换掉得到一个新的问题。具体见第二/四课的内容。

 
 


 
 

比较来看其实对偶问题的长相是有迹可循的。

 
 

SVM Dual:绿色的部分跑到了二次项系数,蓝色的跑到了一次项系数,紫色的变成了sum条件,红色的是式子和条件的结合。

SVR Dual:同上,绿色的变成了二次项的系数,蓝色的跑到了一次项系数,紫色的变成了sum条件,红色的是式子和条件的结合。

 
 

相似的二次规划求解,相似的求解结果。

 
 


 
 

SVR的结果:beta是sparse的!!!

 
 


 
 

练习

 
 


 
 

回顾一下上过的Kernel模型

 
 

在机器学习基石里面上过的线性模型:

  1. PLA/Pocket:使用的是0/1错误
  2. Linear ridge regression:使用的是平方和错误
  3. Regularized logistic regression:使用的是GD/SGD来描述错误

 
 

在这课程里又给大家介绍了另外的几种:

  1. Linear soft-margin SVM

也是用来解决线性的分类问题,使用的错误是到分隔线的距离平方和,通过二次规划求解。

  1. Linear SVR

求解linear regression问题的一种方法,最佳化的是Err_tube,求解的是二次规划。

 
 

第二排的三种方法,就是LIBLINEAR这个工具的核心方法。

 
 


 
 

再来看看Kernel,上面讲到的这些linear的东西,只要使用regularize,你都可以把他延伸到kernel求解。

 
 

  1. Linear soft-margin SVM 延伸到 SVM

求解的是对偶问题

  1. Linear SVR 延伸到 SVR

求解的是对偶问题

  1. Linear rigid regression 延伸到 kernel rigid regression

就是上节课讲到的怎么变成kernel形式的方法

  1. Regularized logistic regression 延伸到 kernel logistic regression

做法同上面一个

  1. Kernel logistic regression 进一步可以延伸到 probilistic SVM

我们在SVM的世界里面不是很爱用kernel logistic regression,因为beta不是sparse的,因此再次处理让beta sparse就是这个

 
 

看第四行的方法就包含在 LIBSVM 这个工具里面

 
 


 
 

再来看一下这些模型的实用度:

 
 

第一排的是很少被使用的,因为分类表现相对于其他没有那么好。

第三排也是很少有人用,因为dense的beta,计算的时候数据量非常大。

 
 


 
 

这前面的6讲都是围绕着这些 kernel models,然后你可以任意配合上我们所讲过的polynormial, gaussian, 等等符合 mercer’s condition 的kernel形式来做使用。这是linear model的非常power的延伸,但是要小心使用,避免overfit。

 
 


 
 

练习

 
 


 
 

总结:

和大家讲了support vector regression,一开始的切入点就是把我们原来会的ridge regression变成kernel的形式,我们可以通过representer theorem来做到这件事情。不过呢这时候的beta是dence的,计算量太大,因此我们从一个 regularized tube error来做推导导出了对偶问题,根据KKT条件求解二次规划,得到sparse的beta的结果。

最后总结了一下kernel model以及使用情况,这里要特别提醒的是这里提供了无限强大的工具,但是你要仔细的去对症使用。

 
 

下一讲:

至此讲完了embedding numerous features:你有很多很多features的时候你可以用kernel的技巧来做学习。下面我们开始讲如果我们有很多的机器学习的方法的时候,我能不能融合各种方法的好坏处,调出一个最佳解。