Category: Machine Learning

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的技巧来做学习。下面我们开始讲如果我们有很多的机器学习的方法的时候,我能不能融合各种方法的好坏处,调出一个最佳解。

 
 

 
 

 
 

 
 

 
 

 
 

Machine Learning Techniques Lecture 5: Kernel Logistic Regression


 
 

内容:kernel logistic regression

一开始先把soft-margin SVM解释成一个和logistic regression有关的模型,他所在做的就是L2 regularization,对应到一个特别的hinge error measure。然后把SVM和logistic regression连上关系,SVM几乎就是L2-regularized logistic regression。如果是这样的话,有一个SVM的解,可以透过第二个阶段的训练的方式把它变成一个适用于soft binary classification的。如果硬要在z空间里面真的求解一个logistic regression的问题,也可以透过representer theorem做到,付出的代价是求解用的beta很多都不是0,计算量很大。

 
 

 
 


 
 

上一讲:

如果我们容许SVM对于已有的资料分类犯错误的话,就从原来的hard-margin改成了soft-margin。我们用C来代表容许错误的参数,这样经过推到以后你会发现dual SVM问题下soft-margin带来的是alpha_n有一个上限就是C。

 
 

今天从soft-margin继续延伸,如果我们要把kernel的技巧用在logistic regression这个问题上,怎么去处理。

 
 


 
 

回顾以前的对比:

  1. Hard-margin Primal:找到能完全分开的最胖的分隔线;

    Hard-margin Dual:对应primal的对偶问题,使得求解的过程与z空间的维度没有关系。

  2. Soft-margin Primal:允许存在已知的数据点没有分对的最胖的分隔线;

    Soft-margin Dual:对应primal的对偶问题,同hard的处理方式,唯一的区别是alpha存在上限C。

 
 

Soft-margin 才是真的大家常用的SVM。

推荐两个特别好用的SVM工具:LIBLINEAR, LIBSVM

 
 


 
 

再来看看Soft-margin里面做了什么事情:

我们把违反胖胖的边界的部分记录下来存储在kesi_n,然后把SVM的有条件问题写出来,再转化成对偶问题求解。

 
 

从另外一个角度来看我们在求解这个问题的时候到底在做什么事情:

给定任何一条分割边界b,w,那么对于任何一个点来说有两种情形,第一种是如果这个点违反了胖胖的边界,则kesi_n记录的就是违反的位置到胖胖的边界的边界的距离。第二种是如果这个点没有违反胖胖的边界,则kesi_n的值就是0.

所以综合上面两种情况,kesi_n 就可以表示成 max(…, 0) 这个公式。有了这个kesi_n的表示公示,则SVM可以写成一个新的公式如上面的PPT所示,也就意味着我们在最佳化里面不再有kesi_n这个变量了。

 
 


 
 

有了上面的那个式子特点是:我们要最小化的是两项加起来,其中一项是和w的长度有关,另外一项就是拿b,w的值来算一些结果。

再来看我们以前在做regularization的时候,我们有一个替代的error要做最小化的动作,但是我们加上了一个w的长度来作为regularization,两者公式在形式上面一致。

 
 

既然形式是一致的,那么为什么不从regularization开始介绍SVM呢?

原因1:这不是一个QP问题,不能用上dual,kernel的技巧求解;

原因2:两个值之间取最大值的函数,可能存在不能微分的点,直接拿来最佳化很难。

 
 


 
 

SVM 和 regularization 的关系:

 
 

Regularization:想要E_in变小,但是存在 w^T * W <= C 的条件;

Hard-margin SVM:想要 W^T * W 最小,但是存在 E_in = 0 的条件,正好相反。

 
 

L2 regularization:把 regularization 的条件丢到目标函数里面去;

Soft-margin SVM:把 hard-margin SVM的条件丢到目标函数里面去。

 
 

所以:

 
 

Large margin 就是 regularization 的实现,代表了我们可以找到的 pyherplane 能比较少,就和L2 regularization 很接近。

Soft margin 对应到特别的计算err的方式。

蓝色的C,红色的C,不管是哪个,比较大的话对应的就是比较小的 lamda,也就代表了越少的 regularization。

 
 

这里对比的意义是:思考可不可以把SVM延伸到其他问题上,比如regression的问题。

 
 


 
 

练习

 
 


 
 

上面我们已经把 soft-margin SVM 写成了新的形式。

 
 

我们首先来看看里面的max函数的两个项和我们一般在二元分类里面所在意的Err_0/1有什么关系:

我们想办法把err对于不同的 y * 分数 画出来。如果两者同号,那么01误差就是0;如果两者是异号的,那么01误差就是1,有图就是图解(横轴是y*分数,err_0/1是纵轴)。

 
 


 
 

如果是 err_svm 怎么来画:

也是两个部分,第一个部分是 y * 分数 比 1 还来得小的时候,则结果是max的前面那一个项,图中前面线性的部分,就是记录要扣几分;否则,就是不扣分,就是0。(图解紫色的折线)

 
 

Err_SVM是E_0/1的上限,因此可以由这个上限推导出一些演算法来间接的把 Err_0/1 做好。soft-margin SVM就可以看作是在做这件事情。

 
 


 
 

我们在logistic regression的时候就讲过了这个上限的概念,我们来看看logistic regression到底在做什么事情,如果把logistic regression印出来的话就是橙色的那条线,同样他也是盖在Err_0/1的上面。

 
 

我们来看 SVM 和 logistic regression 的err,两者是比较像的,当ys像两个极端逼近的时候,两者的结果也是相似的。

 
 

因此可以想象说 SVM 其实也很像是在做 L2 regularization。

 
 


 
 

因此可以来做 binary classification 的 linear model 有:

  1. PLA:最小化Err_0/1,只有在线性可分的时候很好求解。
  2. Soft-margin SVM:通过QP来获得Err_SVM,同样求解很容易,存在模型复杂度保护,但是最佳化的结果只是Err_0/1的上限。
  3. Regularized logistic regression for classification:通过GD/SGD来获得Err_SCE,函数很平滑,最佳化比较容易,有一些些模型复杂度的保护,但是最佳化的结果只是Err_0/1的上限。

 
 

至此,我们可以认为 regularized logistic regression 几乎就是再做 SVM,反之也是。

 
 


 
 

练习

 
 


 
 

因此我们来看看怎么把 SVM 用在 Soft binary classification。

 
 

想法一:

既然两者那么像,那么通过求解SVM得到b,w,然后直接把b,w当作是logistic regression的近似解,也就是直接如上面那样构建g当作是 soft binary classification。这里直接使用了两者的相似性,使用上通常表现得还不错,但是这里丧失了logistic regression的特性。

 
 

想法二:

如果想要logistic regression的特性的话,势必要做一些原来做的一些maximun likelihood这样的learning的动作,做法是首先从SVM里面得到一个解b,w,然后把这个解当作是logistic regression的起始点,然后再使用GD/SGD这样的去学的话应该可以得到一个不错的结果。这样做和你直接跑个logistic regression的结果应该差不多,几乎没有SVM的特性在。

 
 

这两个方法都存在问题,我们有没有办法去融合来做出一个不一样的方式。

 
 


 
 

我们考虑的一个不一样的模型:

首先做SVM出来的结果实际上是一个分数,然后我们在这个分数上面加上两个自由度,一个是放缩(A),一个是平移(B),在这两个参数上做logistic regression的训练,让他可以比较吻合我们在logistic regression里面所需要的manimum likelihood的需求。

这样一来,我们骨子里面使用的是SVM,因此SVM里面讲的dual/kernel等都可以用上,然后再在logistic regression层面操作,它的特性也都统统可以用。

在几何上的意义是用SVM找出分隔线得法向量,然后法向量就不会变化了,但是我们能在法向量基础之上,加上一下放缩和平移来更吻合maximum likelihood的需求。

完美融合,通常情况下,如果SVM求解合理,A一般是要>0的,B很接近0。

 
 

这样我们就得到了新的 logistic regression 的问题,红色框框所示。

这里可以看作是两步,第一步SVM把所有的高维度x转化为单一维度的分数,然后第二步就是对单一维度分数求解logistic regression。

 
 


 
 

这是SVM常用的一个方法,最开始是由 Platt 提出来的,步骤是:

  1. 跑SVM,把结果当作转换,转换到某一个很特别的单维度的z空间,用SVM的分数来当作转换。
  2. 跑Logistic regression微调。两个变数的求解很简单。
  3. 把结果传回去。

 
 

做完你就可以得到 soft binary classifier,这个结果和原来的SVM结果略微有差别,在于A(缩放),B(平移)。

 
 

到此讲的是我们如何从 kernel SVM 到 logistic regression 在 Z 空间里面的估计结果。做法不是真的在z空间求解 logistic regression,而是通过SVM来解z空间的结果,再用logistic regression微调。

但是这不是在Z空间里面最好的logistic regression的结果。

那么怎么去找真的z空间最好的解?

 
 


 
 

练习

 
 


 
 

我们想要的是z空间里面真的最好的logistic regression的解,怎么做?

 
 

当我们存在z的内积的时候,就可以使用kernel来求解。而最开始的w是一堆z的线性组合,才是推倒后可以使用kernel的关键。

 
 

最大的w是一堆z的线性组合:

  1. SVM:系数就是对偶问题的解
  2. PLA:系数就是每个z到底参与了多少次次数修正的过程
  3. LogReg by SGD:系数就是gradient告诉我们跨步多大

这些都能表示成一堆z的线性组合,也就可以猜测这些方法都能使用kernel方式来求解。

 
 

那么什么时候最好的w可以透过这些z表达出来呢?

 
 


 
 

数学上的答案:如果你今天解的是L2 regularized 的linear model问题,也就是 W^T * W 在你的模型里面,那么一定有一个最好的W,可以表示成这些Z原始资料的线性组合。

 
 

证明:

如果有一个最佳解W_*,拆成两个部分,一部分可以用z表示(W平行),一部分不可以(W垂直)。所以当W垂直=0的时候,就是证明的上述公式。

如果W垂直!=0,首先来看看W平行

第一点讲的是垂直的部分相乘z一定是0,所以原来式子第二项err部分 W_* 和 W平行 结果应该一样。

原来式子中第一部分式子分解的情况,这里的大于号会导致:原来说的是找到的已经是最佳解,现在有出现了比最佳解还要好的解,这就矛盾了。

所以 w_* 式最佳解,则w垂直就是0。

 
 

所以结论是只要你解决L2 regularized 线性问题,就可以把kernel套上去。

 
 


 
 

我们来看怎么把这个式子kernel化:

因为 W_* 一定是 Z 的线性组合,因此我们要求解的就是最佳的线性组合的系数 beta_n。把结论代入原来的式子,然后两个z内积相乘就可以轻易的换成kernel来计算。剩下就是求解beta就好了,这时候是一个没有条件的最佳化问题,求解方法很多种多样。

 
 

这通常叫做: kernel logistic regression

 
 


 
 

我们怎么去理解这个公式在做什么?

后面这一项,把一堆kernel和beta做内积,也就是把原来的x转化成了k,在这基础上使用beta(权重)得结果。

前面这一项,beta^T * kernel matrix * beta 的形式,可以看作是 beta^T * beta 的结果再做一些放缩转换的动作。

所以 kernel logistic regression 可以看作是 beta 的 linear model 作用在用kernel 转换过的资料,kernel还用在regularizer。(原来看作是w的线性模型作用在w的藏起来的转换和L2 regularizer)

 
 

这些解释都可以套用在SVM上面。

 
 

警告:这里和原来求解SVM的alpha不一样,beta大部分都不是0。

 
 


 
 

练习

 
 


 
 

总结:kernel logistic regression

一开始先把soft-margin SVM解释成一个和logistic regression有关的模型,他所在做的就是L2 regularization,对应到一个特别的hinge error measure。然后把SVM和logistic regression连上关系,SVM几乎就是L2-regularized logistic regression。如果是这样的话,有一个SVM的解,可以透过第二个阶段的训练的方式把它变成一个适用于soft binary classification的。如果硬要在z空间里面真的求解一个logistic regression的问题,也可以透过representer theorem做到,付出的代价是求解用的beta很多都不是0,计算量很大。

 
 

下一讲:

Kernel for 一般的 regression 的问题

 
 

Machine Learning Techniques Lecture 4: Soft-Margin Support Vector Machine


 
 

内容:soft-margin SVM

首先列出soft-margin SVM的形式表达,出发点是不坚持所有的已知数据点不一定全部要分对,所以增加了一个参数用来控制设定违反分类结果的程度。推倒的时候也是一个QP问题,所以同样通过对偶问题来化简求解。soft-margin SVM可以告诉我们的是可以把数据通过alpha的值分为三类,边界上的,边界内的,边界外的,对于我们做资料分析很有用。另外我们还提到可以使用cross validation来选择模型参数。

 
 


 
 

上一讲:Kernel SVM

目的是通过把Dual SVM的转换和算内积步骤合起来成为Kernel消除空间维度对计算量的影响,这样以后对于任意维度的SVM都能做到。

 
 

Soft-margin support vector machine:

原来讲的都是不能违反任意一个数据的结果叫做Hard-Margin,这里放宽这个限制。从上一讲出发,gaussian svm太复杂了,我们有没有办法来减少overfitting。

 
 


 
 

上一讲我们得到的信息是:SVM可能会overfitting。

 
 

一个原因是转换太powerful了;另外一个原因是我们坚持要把资料完美的分开,不能出错。

如图所示,如果一定要分开的话就会像右边的图一样边界非常复杂,但不见得这样是合理的。

 
 

也就是看作资料里面存在noise,怎么去处理。

 
 


 
 

我们首先来看看我们以前是怎么处理资料里面存在noise的问题的。

 
 

Pocket 模型

没有办法找一条线分开,那么就找一条线犯最少的错误。

 
 

Hard-margin 模型

所有的圈圈叉叉都要分对,而且还要选择w最小的。

条件太多,所以我们应该像pocket一样容忍一些错误。

 
 

其中一个方式是(可以看作是 pocket 和 hard-margin 的合体):

和原来的SVM一样,我们希望的是w长度最短的,对于做对的点要符合原来的条件来求解,做错的点就不管了。

如果只是这样的话不行,机器会默认偏向统统做错,因此我们需要的是做错的越少越好。

 
 

我们又要W最小,又要做错的最少,因此加上一个参数C来做平衡。C越大表示越不要犯错越好,C比较小的时候表示W越短越好。

 
 


 
 

所以这是我们的新问题 soft-margin SVM,上面黄底表示的公式。

 
 

公式的问题:

存在boolean运算,不是线性的运算,也就是说不是QP问题,也就不能再使用Dual,Kernel机制。

不能区分错误的大小。

 
 

因此提出了下面黄底表示的新的问题公式。

我们把错误记录在 kesi_n 的变数里面, kesi_n >= 0,表示的是离我想要的那个值到底有多远。

这样我们minimize的式子里面也就可以来衡量你犯了多大的错误用kesi的和来表示。

这样就符合了线性变化的条件,同时也可以衡量错误大小的要求了。

 
 


 
 

Margin voilation:意思就是错误可以衡量,图示就是违规的数量的图解。

C:描述的是违反margin的程度,C越大表示允许违反的越小,反之边界会比较平滑和胖。

变数数量:d+1+N,N表示的是每个点到底违反了多少margin,因为只记录违反的N个点,所以多了N个条件。

 
 


 
 

练习

 
 


 
 

黄色底公式就是我们上面推导得到的soft-margin SVM公式。下面就是根据这个问题推导他的对偶问题,然后就可以和hard-margin时候一样,享用容易做feature transform的特性。

 
 

所以先写出 lagrange multipliers,步骤和原来一样,把条件合并到目标函数里面去。然后就得到了 lagrange dual,之后和之前一样用KKT condition来化简。

 
 


 
 

问题写下来如上面的黄底框所示。

化简的第一步是对整个式子求kesi的偏导等于0,就得到一个alpha,beta相关的等式,所以可以把beta换掉用alpha表示,同时alpha的限制条件加强了,得到的结果和原来的hard-margin问题化简结果相似。

 
 


 
 

式子就变得如上面黄底那样简单了。到这里首先是minimize,然后是maxmize,这个式子在hard-margin SVM几乎一样,同样里面的部分去微分求解,和第二讲讲过的dual一致,具体见那边的推导。

 
 


 
 

然后你就会得到一个几乎和hard-margin SVM一样的式子,唯一的差别就是对alpha_n有了一个最大值C的限制。

 
 

因此现在这个问题有N个变数,2N+1个条件。

 
 


 
 

练习

 
 


 
 

推倒完了以后就可以得到 Kernel soft-margin SVM的算法了:

  1. 求解这个问题的时候加上了额外的upper-bound条件。
  2. 一样去求解QP问题
  3. 一样去算b
  4. 得到最后的hypothesis SVM长什么样子

 
 

C的值就是来控制你想要得到边界是更细致变化还是更粗变化。

 
 

这里还需要探讨的问题是,这里面我们算b的方式与原来一样么?

 
 


 
 

Hard-margin里面就是列出KKT条件,图中所示一条的乘积的前后两部分必须有一个为0,那么因为alpha>0,所以后半部分就必须=0,就可以直接告诉我们b是多少。

Soft-margin一样依葫芦画瓢,列出不能同时存在的条件,这里不一样的就是多了一个kesi用来记录到底违反多少点。还存在另外一个条件。通过这两个条件,和原来的方式一样,先找一个support vector,也就是alpha>0,这样就会有 b = 一个和kesi相关的式子,如果kesi = 0,b就可以直接求出来。

 
 

所以求解b的方法总结来说就是:找一个可以使得kesi=0的support vector(命名为free support vector,不再是任意的support vector),这样b就可以很容易得到解。

 
 

实际中也有极少数的情况不存在free support vector,就只能用一堆不等式来限制,就可能存在一堆b,都是可以的答案。

 
 


 
 

然后我们来看看 soft-wargin SVM 的表现怎么样。

当C取不同的值的时候的结果如上面图示,C越大表示越不想犯错误,边界越复杂。C值越大越容易overfit,所以需要好好的去选择参数。

 
 


 
 

我们刚才就是使用 complementary slackness 这个条件来求解b,我们再通过这个来看看 soft-margin SVM 到底告诉我们一些什么信息。

 
 

Soft-margin SVM 的两个 complementary slackness 条件如黄底所示,根据这两个条件我们可以把手上的资料点分成三种。

第一种是free support vector,特点是0<alpha<C,kesi=0,可以用种点来唯一的算出b,这些点就是刚刚好在胖胖的边界上的点。

第二种是non-support vector,特点是alpha=0,kesi=0的点,也就是没有违反边界的点,分得非常好的点,在胖胖的边界外面。

第三种是bounded support vector,特点是alpha=C,kesi != 0的一个值,记录了违反多少,就是图中处于胖胖的边界内的点。

 
 

通过alpha的值就可以把手上的数据点分成三种,这三种对于你做资料分析很有用。

 
 


 
 

练习

 
 


 
 

讲完了model,我们来看看怎么选参数。

 
 

上面的九张图统统都是用的Gaussian kernel的SVM,但是采用了不同的C,garma的组合。横轴是表示的C,纵轴表示的是garma。

 
 

怎么选?

最好用的工具就是Validation。

 
 


 
 

通过采用 Cross Validation,算一下每一种情况下的Error,选一个最好的。

 
 


 
 

如果把 cross validation 递推到极限的话,就是每一份资料只包含一个的话,这时候就有一个特殊的名字叫做 leave-one-out CV Error,这个在SVM上面会有一个有趣的结果。

 
 

E_loocv 的结果和 support vector 的数量是有关系的,可以证明 E_loocv <= SV数量/资料量。

假设今天你有一万个点,如果你解完这个问题以后,对于第一万个点刚好他的alpha=0。意味着只踢掉第10000个点,前面的9999笔资料都丢进SVM,这组alp[ha还会是最佳解,也就意味着最后一个没有用,alpha=0。也就是说把non-support vector 拿掉对于解SVM一点影响也没有。

同样的对于 non-support vector 对于 cross validation 的贡献也是0。

所以就有上面的结论。

 
 


 
 

也可以通过上面的结论来做模型的选择。

 
 

把所有的情况的support vector的数量列出来如上面的图示,但要注意的是这个公式说的只是个上限,不是实际的错误率。

把上限做到最好不代表把真正的错误率做到最好,因此这个结论通常是拿来排除比较危险的结果,就比如上面的三张图所示的结果,先予以排除。

 
 


 
 

练习

 
 


 
 

总结:soft-margin SVM

首先列出soft-margin SVM的形式表达,出发点是不坚持所有的已知数据点不一定全部要分对,所以增加了一个参数用来控制设定违反分类结果的程度。推倒的时候也是一个QP问题,所以同样通过对偶问题来化简求解。soft-margin SVM可以告诉我们的是可以把数据通过alpha的值分为三类,边界上的,边界内的,边界外的,对于我们做资料分析很有用。另外我们还提到可以使用cross validation来选择模型参数。

 
 

下一讲:

至此对SVM进行了一个完整的介绍,但这些都是在binary classification的情况下,下面开始讲如何将SVM延伸到更复杂问题的求解。

Machine Learning Techniques Lecture 3: Kernel Support Vector Machine


 
 

内容: kernel SVM

首先讲了把原来的dual SVM的转换和内积的两步合并为Kernel,通过这样回避了原来SVM计算涉及到的对空间维度的依赖,然后讲了多项式kernel和Gaussian kernel,最后对这些kernel做了简单的比较,如果想要的是效率的话往linear走,想要复杂边界的话往高纬度走。

 
 


 
 

上一次我们看的是SVM的对偶形式,其新的形式好像跟空间维度D没有关系,可以使用二次规划来求解。

 
 

今天来看一下 Kernel support vector machine,把好像拿掉,使SVm的形式真的和空间维度没有关系。

 
 


 
 

这是我们上一次推到出来的对偶问题:

从条件的数量和变数的数量来看,这个问题好像都和空间维度D没有关系。但是如果计算Q_d这个矩阵,就需要用到D空间的维度,维度越大越难求解,这里就是瓶颈。

 
 

怎么做?

 
 

求解 Q_d 对于Z空间来说是做内积,但是如果从x空间的角度,其实是两个步骤。步骤是先把x做转换,再做内积,每一步都和维度相关。我们能不能把这两个步骤合起来算得快一些?

 
 


 
 

先考虑一个简单的例子:二次的多项式转换

 
 

使得有 0次项,1次项,2次项,x1x2,x2x1同时存在;

这样转换了再做内积,如上面的推导,就会得到只和 x * x’ 内积的结果。

可以将运算复杂度降低到了O(d)!

 
 


 
 

Kernel function: 转换操作 + 内积操作

 
 

上面的例子所对应的 kernel function 表示为黄底所示部分。

 
 

接下来我们来看SVM里面怎么使用kernel function:

  1. SVM用到内积的地方首先是 二次项系数q,是Z空间里面的内积,可以换成x的kernel function求解。
  2. svm里面算出了alpha以后需要再求得b,w,算出alpha之后通过挑一个support vector来求得b,这里有 w * Z 的内积求解问题,可以转换成Z空间的内积,同样就可以转换成x的kernel function来求解。
  3. 最后得到SVM的结果的这一步,也存在 w * phine 的内积,phine函数就是z,w可以转化成z相关,这样同样可以转换成x的kernel function来求解。

 
 

也就是说没有任何一个时刻真的在z空间做,所有的运算都是在x空间完成,就不会受到空间维度d的影响了,就会很有效率。

 
 


 
 

Kernel SVM 的表示(就是原来的z的内积全部替换为kernel function):

  1. 算Q的时候全部换成Kernel function来求解
  2. 同样的求解alpha
  3. 再算b的时候也是使用kernel function来求解,这里只需要一个support vector就能得到b。
  4. 最后预测函数的表达式求解的时候也是使用kernel function来求解

 
 

时间复杂度:

1的是 算kernel的力气 * N平方

2的是 QP 只有N个变数,N+1个条件

3、4的是 O(SV)

 
 

Kernel SVM 就和空间维度d没有关系了,而且和原来一样,只需要support vector就可以对未来做预测。

 
 


 
 

练习

 
 


 
 

对于二次多项式来说,有些很容易写出 kernel function,有些就比较难,下面介绍一些常用的二次多项式转换。

 
 

蓝色的是原来的,在这基础上做一些些放缩,比如*根号2,对应的kernel函数的一次项前面就会有一个2,如上面红色的公式,再复杂如绿色phine标识的那样。

 
 

整理起来,这里讲的是二次项转换中一次项系数的扩展的方法。这里的变化都是相同的空间内的(power),不同的形式(内积,geometry特性,不同的边界)

 
 


 
 

不同的转换对应到不同的几何定义,不同的距离。

 
 

上面三幅图就是不同的一次项系数对应到的边界变化。相对来说你比较难比较哪个比较好,这里想给大家建立的概念是,换掉kernel,就可能会得到不一样的解。

所以我们要对kernel做选择,才能有比较好的分类结果的表现。

 
 



从二次出发,还能一路推导下去,这里对常数部分做手脚加上theta,然后你能考虑q次方。

 
 

grama:控制一次项系数;

theta:控制常数项;

Q:控制次方。

 
 

这样以后,你做高次转换的复杂度和维度无关,计算也就很简单,只要能把kernel计算出来。

右边的图就是10次方做出来的图,虽然特别高次方,但是边界还算简单,large-margin相对来说可以帮你控制overfitting。

 
 

Polynomail SVM 就是 Polynomial Kernel 配合 SVM 来使用。

 
 


 
 

如果我们回到一次转换,也可以做,通常叫做linear kernel。

 
 

Linear 是值得你最先尝试的一种方式!

 
 


 
 

练习

 
 


 
 

如果我们可以用kernel有效率的解决高纬度空间的运算的话,那么对于无限多维的转换是不是也能解决?

 
 

特例:

原始资料只有一个维度,考虑一个特别的函数如上面所示的高斯函数

经过一翻推导你会发现最终也是一个x函数phine(x)的内积,而且是无限多维的高斯函数。

 
 


 
 

这是后来考虑G_SVM,是一堆中心在support vector上面的高斯函数的线性组合。

所以也被叫做 Radial Basis Function(RBF) kernel

 
 

Gaussian SVM:使用高斯函数来做kernel的SVM,意思是把x映射到无限多维的空间里面,在这里面找出一个最胖的分割情况。

 
 


 
 

通过 kernel SVM 可以有效率的做到 large-margin + hyperplanes + transform。

 
 

不再去算Z,直接用kernel替代;

不再存储W,只存w的表现方式support vector和alpha;

 
 

现在还可以做无限多维度的SVM,比如通过Gaussian kernel实现的 Gaussian SVM,large-margin在这些过程中提供不overfitting的保障。

 
 


 
 

真的那么美好么?

 
 

举一个gaussian kernel的例子,不同的gaussian kernel得到的结果如上面三幅图。

参数不合理还是会overfit,还是要慎重选择kernel!Gaussian SVM里面不建议使用太大的garma,garma越大fit越强烈。

 
 


 
 

练习

 
 


 
 

我们接下来分析一下各种kernel的好坏处:

 
 

  1. Linear Kernel

其实就是把原始的内积丢进去就好,各种求解方式的效率差很小。

好处是最简单最安全最优先尝试的方法;不牵扯到特别转换,所以可以设计特别的QP solver,计算得更快;对于人来说可以很容易的看出来到底怎么去做分类。

坏处是有限制的,如果data不具有线性则没有办法做

 
 


 
 

  1. Polynomial kernel

有限情况下的kernel。

好处是比linear更加宽松,高次解决了非线性data不能处理的限制;可以通过对Q的设定来表达你对这个模型的想象。

坏处是你要算kernel的值的时候比较困难,Q越大越难求解;参数多而且需要你去选择,比较困难。

 
 


 
 

  1. Gaussian Kernel

无限情况下的kernel。

好处是表达能力是无限的,因为是无限多维的转换;比起polynormial来说数值求解的难度比较低;只有一个参数garma所以比较容易选择。

缺点是无限多维度的转换,不直观;比起linear来说计算相对比较慢;能力太强可能会overfitting。

 
 


 
 

  1. 其他的kernel

kernel代表的是x和x’转换以后在z空间的相似性(内积表示的就是一种相似性)。

那么从相似性来考虑采用什么样的kernel?

不见得可以,因为kernel是一种相似性,一种向量的内积在Z空间的相似性。

如果你要用自己的kernel的话,要注意的是你要想办法证明它到底为什么是个kernel。

 
 

kernel的充分必要条件:

对称,从矩阵角度看kernel矩阵是两个z矩阵相乘,也就是说kernel矩阵是半正定的。

 
 


 
 

练习

 
 


 
 

总结: kernel SVM

首先讲了把原来的dual SVM的转换和内积的两步合并为Kernel,通过这样回避了原来SVM计算涉及到的对空间维度的依赖,然后讲了多项式kernel和Gaussian kernel,最后对这些kernel做了简单的比较,如果想要的是效率的话往linear走,想要复杂边界的话往高纬度走。

 
 

下一讲:如何避免高纬度SVM(Gaussian SVM)的overfitting

Machine Learning Techniques Lecture 2: Dual Support Vector Machine

 
 


 
 

内容:dual(对偶) support vector machine

 
 

告诉大家一个新的SVM问题:SVM的对偶问题。对偶问题的出发点是希望移除维度d对于non-linear SVM运算的影响,然后推导出透过 KKT 条件就可以得到对偶的SVM,KKT条件可以转化为QP形式来求解对偶SVM,但最好需要根据SVM来优化QP的运算过程。解的结果你会发现那些活下来的alpha>0的点有重要意义,就是support vector,就这些直接决定了最胖的分隔线。

 
 

 
 


 
 

回顾:linear SVM

可以通过QP求解得到比较robust的分隔线

 
 

今天把linear SVM转成另外一种形式以便更加容易的应用到不同的领域。

 
 


 
 

复习一下上一次上的内容:

 
 

求解:

可以通过二次规划来解SVM,应用于多维的话就是把x转换成Z空间即可,就是对z的线性二次规划求解,这对于x来说就是非线性的SVM。

 
 

作用:

控制模型的复杂度的同时,透过特征转换降低Ein。

 
 

我们Z空间的维度d越大,相对来说求解的难度就越高。

那么如果d无限大的话,还能不能求解。

 
 

因此我们的目标是移除 d 对于SVM求解的影响。

 
 


 
 

原来的VSM:d+1 个变量,N个限制条件

目标(看作是dual)的SVM:只会有N个变数,N+1个限制条件

 
 

这样变数的数量就不会和特征转换的维度增加而增加。

 
 

这里的数学很复杂!涉及到很多深入的最佳化理论,因此这里只讲有助于了解SVM特性的重点,其他就略过了

 
 


 
 

regularization时候的思路:

原来做 regularization 要解决的是有条件的最佳化问题,这个不好解,我们则把这个条件塞到最小化的公式里面,把问题转化为没有条件的公式的最佳化问题。

 
 

工具:

lagrange multipliers – 把条件乘上一定的系数加到目标函数里面去的东西

regularization里面原来每个条件都带一个参数C表示的是我们的w最长可以是多长,他会对应到一个lamda,这个lamda通过最佳解(梯度要往一个方向走但是已经无路可走了,这时候就是最佳解)要满足的条件来得到。

这时候呢,使用者只需要提供lamda而不是原来的C就可以求解问题了。

 
 

这里同样要使用 lagrange multipliers 来求解这里的 有条件的最佳化问题。但是这里的使用方式会比较不一样,这里会直接把 lagrange multipliers 当作是变数,而不是使用者直接给我们的已知量,然后去求解。

 
 

总结:

SVM 里面的每一个条件对应到一个 lagrange multiplier,然后把它当作是变数,去求解和这个变数有关的最佳化问题,这个问题其实最后就是对偶问题。

SVM 里面有 N 个条件,所以就有N个lagrange multiplier,就是有这么多变数。

 
 


 
 

做法:

Lagrange multipliers 在regularization里面叫lamda,但是这里通常用alpha表示。

原来的有条件问题可以写成一个看似没有条件的问题,上面绿框所示,包含红色部分表示原来想要的最佳化的目标,再加上蓝色部分所有的条件乘上其对应的alpha。整个定义为 lagrange function (L(b,w,alpha)表示)。

 
 

SVM 就可以转化成一个看起来没有条件的最小化问题了,黄框所示。

SVM 等式的含义是:每一个b,w的时候我都能算出一个值,这个值是把所有的alpha作为变量得到的最大的lagrange function的值,SVM要获得的就是所有b,w的对应的值的最小值。

证明:

任意的b,w:算分数的过程可能是好的(符合原来的那些限制条件),可能是坏的(不符合原来的那些限制条件至少一条),

  1. 坏的的情况下这个分数会是无限大(原来的有一条蓝色部分大于1,所以lapha越大的结果就是无限大)。
  2. 好的情况下条件这部分这个分数会是0,因此结果就只有原来式子中红色部分的结果(蓝色部分小于1,所以alpha越小越好趋近于0)

所以通过最小化b,w的值就可以淘汰掉那些原来的不符合条件的b,w。

 
 

至此,原来的SVM就转化成了一个看似没有条件的式子来求解。

 
 


 
 

练习

 
 


 
 

灰色公式:

 
 

现在有了一个新的问题:

有了一个lagrange函数,先对alpha做最佳化的动作,然后再对b,w做最小化的动作。

 
 

特性:

如果今天只考虑一个固定的alpha’,这个alpha’的最大值会比任意的最大值小,所以有了式子中的大于等于符号,有了右边部分去掉了max的式子。

任意的alpha’都有此等式,所以先做minb,w以后再考虑取最大的alpha’也是满足的,因此就有了蓝色底的公式。

 
 

像上面一样对掉了最佳化的过程的问题叫做 lagrange dual problem

 
 

对调关系还存在一个大于等于关系,也就是说如果我们解决了这个对偶问题,这个解就是没有对调前的式子的下限解。

 
 


 
 

>= : 叫做 weak duality(弱对偶关系)

= :叫做strong duality(强对偶关系)

  1. 问题是凸的
  2. 问题是有解的,原来的条件没有限制到说找不到任何的解
  3. 条件是线性的

    满足这三点叫做constraint qualification,强对偶关系,可以直接解右边的问题来当作左边的问题的解。也就是说存在一组b,w,alpha的组合对于左边来说是最好的,最右边来说也是最好的。

 
 


 
 

求解右边的问题:

  1. 里面的min部分是没有条件最佳化问题,那么就是求梯度是0的地方,谷底就是最佳解。先来对b微分就得到上面蓝色部分第一点的式子。

    上一步得到的一个等于0的式子代入,原来式子各个+0,则可以把b化简掉,没有b了。

 
 


 
 

  1. 同样的方式来对于w求偏微分得到一个=0的式子,同样的方式加入到原来的式子,可以将原来的式子消掉w,所以得到的式子就只剩下alpha了。所以minimize这一个步骤被化简掉了。

 
 


 
 

剩下一个只有alpha的问题,就是lagrange对偶问题的简化版。

 
 

结论:

如果是强对偶关系的话,需要满足下面的条件(KKT conditions):

  1. 满足原来问题的条件
  2. 满足对偶问题的条件
  3. 满足微分以后产生的条件
  4. Alpha * 里面部分原来的条件要等于0,也就是说这个式子的两部分至少一部分等于0

 
 

下面就是用这些条件来求解最佳的b,w,alpha

 
 


 
 

练习

 
 


 
 

上一步就得到了对偶问题的简化版,这里首先将其转化成我们常看到的SVM的对偶问题,会有一些些小小的变化:

将最大化变成最小化操作,通过取负号保证正的,然后通过导数来做到。

条件部分只是写法不一样,没变化,一共N+1个条件,w的条件用不着了(隐藏了),这里只需要专心求解alpha。

目标函数的二次式做了个展开的动作

 
 

至此得到了SVM的QP问题,而后就继续求解QP(二次规划)问题。

 
 


 
 

求解QP问题,代入模版。

 
 


 
 

SVM对偶问题的Q取名为 Q_d,d代表对偶的意思。

至此我们就可以解出来了,但是这个求解过程真的有那么容易么,我们来看看这个Q_d有多大。

 
 

Q_d:

每一格的内容是: y_n * y_m * z_n * z_m 相乘,一般不会是0。

如果是3000笔资料,其存储量差不多会是3G的大小

需要特殊处理:不存整个Q,而是用到再算,或者是使用特殊的条件来加速求解

也就是说需要用特别为SVM设计的二次规划来求解,不然的话计算会特别慢。

 
 


 
 

上面因此就可以得到中间产物alpha,然后我们怎么来得到b,w呢

 
 

使用KKT条件由最好的alpha来得到最好的b,w。

  1. w和alpha的关系就一个条件而已,直接解得。
  2. 两个条件和b有关,alpha大于0的时候最后一条后面的部分必须等于0,则可以求解得到b。(这里后半部分等于0可以得到那个点就是在胖胖的边界上,也就是support vector)

 
 


 
 

练习

 
 


 
 

Support Vector:就是在胖胖的分界线边界的那些点,这些是我们所需要的,其他的则是不需要的。【SV candidate】

求解SVM得到说:如果alpha>0的话,这个点一定在胖胖的边界上。【SV positive】

所以:我们将alpha_n>0的这些点叫做 support vector(SV positive)。

SV positive 可能会比原来我们所定义的 SV candidate 少一些,也可能一样多。

 
 

SV 重要性:

由原来w的求解公示可以看到W 是 alpha的线性组合,也就是说alpha=0就不需要计算。也就是说求解w只需要用到alpha>0的值。

同样你会发现求解b的时候使用的也是alpha>0的点。

也就是说w,b都是只靠support vector来求解得到的,所以和SV的定义相一致。

 
 

SV 就直接可以区分资料对结果是有用的还是无用的。

 
 


 
 

SVM里面的W表示成alpha相关的公式:alpha是对偶解

PLA里面也有相似的定义:beta表示的是犯错几次

 
 

两者w都是原始资料的线性组合

不完全是偶然,一般来说你做gradient decent这些演算法,和PLA一样从0出发,你也会得到类似的式子,这样的结果叫做:最佳的w可以被我们的资料 represent。

 
 

SVM特别的是:只需要资料里面的support vector就可以表示出来。

PLA特别的是:只需要用资料里面的犯错的点表示出来。

 
 


 
 

总结来说,从上一讲到这一共介绍了SVm的两种表示方式:

 
 

第一种是原始的(Primal SVM):让w越小越好,有一堆的条件限制;变数的数量和哪一个空间有关,空间维度越高越难求解;原来是通过对b,w的特别的放缩来得到最佳解。

第二种是对偶的(Dual SVM):切换到alpha空间去求解;问题的大小和资料的数量有关,资料量越大越难求解;通过最佳化求解得到support vector和对应的alpha,用这些来得到b,w最佳解。

都是得到最佳的b,w来创建SVM的式子来分类。

 
 


 
 

我们做完了没有?

 
 

我们想要求解SVM但是不想要碰d,因为d可能是很大很大。

然后这里讲的新的推导看起来只和N有关,和D无关,但真的是这样么?

D藏到了计算Q矩阵的地方,计算Q_n,m的内积,d越大越难以求解。

 
 

所以我们要想办法避开Q里面的D相关运算,这是下一讲的内容。

 
 


 
 

练习

 
 


 
 

总结:

告诉大家一个新的SVM问题:SVM的对偶问题。对偶问题的出发点是希望移除维度d对于non-linear SVM运算的影响,然后推导出透过 KKT 条件就可以得到对偶的SVM,KKT条件可以转化为QP形式来求解对偶SVM,但最好需要根据SVM来优化QP的运算过程。解的结果你会发现那些活下来的alpha>0的点有重要意义,就是support vector,就这些直接决定了最胖的分隔线。

 
 

下一讲:

移除 Q 对 D 的依赖。

Machine Learning Techniques Lecture 1: Linear Support Vector Machine


 
 

这里讲的是 linear support vector machine

 
 

我们的出发点是想要找那个比较胖的分隔线,更加兼容测量错误,然后把问题公式化以后开始简化他直到得到一个二次规划的标准问题,然后就可以求解了,这就是一个完整的方法。然后我们再回头来看这个方法的理论保障是减少了有效的Dvc,这样就可以做得更好,这就是SVM。

 
 


 
 

课程基本信息。

 
 

Coursera 前8周是基石课程,后面8周是技法课程。

华语授课,投影片授课。

 
 


 
 

与机器学习基石的课程的异同点:

一样的是:哲学的讨论,理论分析,算法和实现,笑话。

不一样的是:把基石课程提到的基本理论工具延伸成为实用的学习模型,围绕在一个主要的点就是特征转换上面:

  1. 有大量的特征转换怎么运用,如何控制复杂度 – SVM
  2. 找出一些比较具有预测性质的特征以及混合应用 – AdaBoost
  3. 学习资料的一些隐藏特征 – Deep Learning

 
 

通过往这三个方向的学习来使得你能够专业的使用相关工具。

 
 


 
 

练习。

 
 


 
 

第一讲:线性支持向量机

 
 


 
 

先来看看之前讲过的 linear classification,他做的事情就是如图所示,通过画一条直线来区分圈圈叉叉。数学上的意义就是资料拿过来算一个分数,看分数的值是正的还是负的来决定其是圈圈还是叉叉。

 
 


 
 

PLA 是以前课程讲过的算法,在确定存在线的时候,此方法可以帮助我们找出这条线。

 
 

但是如上图所示,如果资料给定,有可能不会只存在一条线可以区分这些资料。问题是,从上面三幅图,哪一条线来区分圈圈叉叉比较好?

 
 

PLA 算法会选择的是随机一条线。

VC Bound 理论上看,上面三条线是一样好的。

而你是不是会选择最右边的线是比较好的吧,为什么?

 
 


 
 

简单的解释:

假设我们已经得到原始资料xn,未来我们用到的资料是和原始资料相近的一些资料,因为存在误差不可能是完全一样的,那么上面的三条线对相近的容错能力就是在能区分的情况下每个原始资料对的点所能画的圆圈的最大半径,就如上图所示,第三张图的线对于圆圈的容错能力最好,所以的三条线比较好。

 
 

也就是说每一个点离得线越远,那么能容忍的测量误差越大,反过来说就是找出一条线,离每一个点越远越好。

More robust:离最近的训练资料的距离来判断。

 
 

 
 


 
 

从线的角度看就是如下面三图:看线能长的多胖,越胖的线越robust。

 
 


 
 

也就是原来的问题可以变为一个最佳化的问题:找出一条最胖的线满足可以很好的分开所有的圈圈叉叉。

胖的定义:算一下线到每一个点的距离,取两边最小的。

 
 

下面要做的事情就是把这个最佳化问题变成可以数学求解的最佳化问题。

 
 


 
 

margin:线的边界,就是学术上线有多胖的说词。

 
 


 
 

练习

 
 


 
 

上面的最佳化问题里面有一个重要问题:找出的这条线你需要去看一下他和每一个点的距离是多远,取最小的距离。

 
 

探讨距离的运算:

 
 

分开w0和其他的wi,w0单独处理,w0取名为b,就是截距的意思。

所以公示里面的部分包括了 W^T*X + b

 
 


 
 

所以我们要算的是:一个用b,w表示的平面到一个点x的距离

 
 

假设我们已经有一个平面在手上,考虑平面上的两个点:x’和x”

因为都在平面上,所以有:w * x’ +b = 0, w * x” + b = 0

所以有上面的标号1的结论,然后两个相减,就得到标号2的结果。

x” – x’ 表示的是平面上的向量,w 与平面上任意的 (x” – x’) 向量都等于0,也就是说 w 垂直于平面,也就是说 w 是平面的法向量。

有了法向量任意一点x到平面的距离就比较好求解了。也就是说标号3所示:将(x-x’)向量投影到垂直于平面的方向w。

所以结果就是黄色所示公式:线性代数里面的投影距离公式。

然后做一下化简你会发现:就是 绝对值(W^t * x + b) / 绝对值 w 【这里只是除以w的长度,所以上面要把b分出来的原因】

 
 


 
 

因此有了点到一条线的距离,但是我们需要的是点到分隔线的距离。

 
 

分隔线的性质:我们要的分数(W^T * Xn + b)和结果(yn)是同号的。因此上面的距离公式的绝对值可以化简掉。

 
 


 
 

至此得到的新的式子,但还是不会解。

 
 

世界上其实没有那么多条线,也就是说同一条线能用不同的方程式来表示,例如蓝色框框的第一点所述,也就是说线的系数可以放缩。

所以我们可以用特殊放缩使得式子更简单。

蓝色框框第二点所述,那部分最小的话刚好等于1,则margin就可以表示为 1/w长度。

所以可以把 margin 换掉为 1/||w||,但是要求yxb相关部分要取最小值1.这个条件就包含了原来的要求yxb相关部分要大于0。

 
 


 
 

所以得到了上面的黄色狂所述的简洁的表示,还是不会解,因为最大化的问题里面还包含一个最小化的问题。

 
 

所以考虑放松一下条件,看能不能化简求解。但是我们首先要证明的是,就算我们把条件放松,最后的到的解还是落在原来的区域。

 
 

条件放松为 大于等于1,而不是等于1.

反证法:如果放松后最佳解落在外面(min yxb 部分最小的大于1),例如大于1.126,那么bw都除以1.126的结果比bw更好,这就矛盾了,所以可以证明:即使条件放宽到大于等一1,也会有不落在外面的结果。

 
 

所以原来的公式可以放松得到第二个黄色框所示,大大的简化了原来的问题。

这里还做了两个变化:最大化变成了最小化,求导,去掉根号部分,加上1/2。

 
 


 
 

练习

 
 


 
 

因此接下来我们要求解的是黄色框所示公式。

 
 

先举例一个特殊的例子,蓝色框所示,四个点就有四个条件,目标是最小化 W^t * W。

1式和3式 得到 W1 >= 1

2式和3式 得到 W2<=-1

所以就有了 W^T * W >= 1

所以就得到最终解了。

 
 

SVM 就冒出来了。

 
 


 
 

最胖的线就一定会有几个点离他最近。

如果我们去掉除这些最近点以外的点,在去找分隔线,会得到一样的结果。

也就是说这条分隔线就是由这些最近点决定的,其他点都不重要。

 
 

也就是说原来的资料可以看作两种:

一部分资料:告诉我们分隔线在哪 – support vector

另一部分资料:不需要

 
 

Support vector machine:可以看作一种找出最胖平面的方法,就是考虑分隔线最边边的点,就是上面的图示所标识的方法。

 
 


 
 

上面是解特例,那么通用解怎么解。

 
 

坏消息:不容易

好消息:目标最小化的是二次函数,条件是b,w的一次式,也就是二次规划(quadratic programming)的问题【线性规划进阶版】。数学上是可以求解的。

 
 

所以下一步:把问题变成二次规划的一般形式,然后使用已有的数学工具求解。

 
 


 
 

左边是目前的公式形式。

右边是二次规划的标准型。最小化u向量的二次函数,二次项系数Q,一次项系数P,条件是U向量的一次式,条件有M个,一次项系数A,常数项c。

 
 

因此我们要把这些系数向量提出来,如红色部分。Q里面与w有关的系数用I矩阵表示,其他都为0。P就是0向量。

 
 

直接使用matlab解QP问题。

 
 


 
 

因此这里就得到了一个新的演算法(linear hard-margin svm altorithm):

  1. 算系数
  2. 二次规划求解
  3. 得到的就是最胖的分隔线

 
 

Hard-margin:坚持圈圈叉叉一定是要完全分开的,不能有犯错误。

linear:使用直线分

 
 

如果你要非线性的,那就是把x做一个转换,基石里面有类似的方法来说明从直线到曲线的变化转换,此处类似。

 
 


 
 

练习

 
 


 
 

此处黄色公式用z代替x表示的就是非线性,在z空间做SVM。

 
 

此处我们再从理论上来解释为什么SVm可以得到好的结果。

 
 

与 regularization 比较,有趣的是条件和优化对调了:

Regularization:Ein 越小越好,条件是 W^T * W <= C 为的是不 overfit

SVM: W^T * W 越小越好,条件是 Ein = 0,就是上面那句话反着说

 
 

因此:SVM可以看作是一种 weight-decay 的 regularization。

 
 


 
 

另外一种解释:

 
 

Dvc:解决的是我想要知道我的线到底能产生多少种圈圈叉叉的排列组合。

 
 

现在考虑:

如果我今天喜欢的是胖的线,定一个胖的标准,如果资料拿来能找到达标的胖的线就是好的结果,找不到足够胖的线就没有结果

那么同样考虑在一组特定的资料上,到底能够找出多少足够胖的区分圈圈叉叉的组合

 
 

举例:

不计较胖瘦,绿色图示,三个点八种情况,都能分开。

计较胖瘦,红色图示,线的粗度要超过1.126,那么三个点,八种情况下都不一定能分开(具体和数据点相关)。

 
 

Dvc 有你能够做出几种情况来决定,情况越少复杂度越低。因此线越粗,有效的Dvc就可能越低,就是越好的分类。

 
 


 
 

我们考虑线的胖度来算演算法的Dvc,就看其最多最多能shatter多少个点。

(演算法的Dvc是没有绝对定义的,其结果与实际拿到的资料有关)

 
 

shatter的意思就是所有圈圈叉叉的排列组合。

 
 

如图平面上有三个点,在一个单位圆的边上。

如果不在乎分隔线的胖瘦,区分这三个点的所有排列组合都能做出来,Dvc就是3。

如果线要有 (根号3)/2 那么胖,那么圆上任意三点你做不到所有情况都产生出来(存在两个差异点之间的距离小于根号3就不能产生出区分情况),所以 Dvc 小于3。

 
 

数学上证明结论如上面公式,其Dvc与两个事情相关:资料的空间大小R,你容许的胖的程度p。

就是说:透过设定胖瘦条件,真的可以降低Dvc,所以理论上SVM就是一种控制复杂度的方式。

 
 


 
 

一开始我们喜欢 hyperplanes 的原因是它的有效数量不是很多,Dvc比较小,可以有效控制复杂度,但是呢太简单的平面不一定能把事情做好。 – not many

反过来我们考虑更复杂的平面,通过feature transform来实现,虽然可以处理很复杂的情况了,但是数量就变多了,Dvc就变得很大。- sophisticated(复杂)

原来只能二选一。

 
 

这里我们讲了一个新的概念 large-margin ,就是要胖的 hyperplanes,作用是控制数量,Dvc变比较小。

 
 

Large-margin hyperplanes + feature transform

可以做到的是,降低Dvc,但同时还能透过transform得到复杂的boundary。- not many & sophisticated

 
 

SVM 的好处:有了一种新的控制复杂度的方法,这样就可以尽情的采用各式各样不同的 feature transform。

 
 


 
 

练习

 
 


 
 

总结:

这里讲的是 linear support vector machine

我们的出发点是想要找那个比较胖的分隔线,更加兼容测量错误,然后把问题公式化以后开始简化他直到得到一个二次规划的标准问题,然后就可以求解了,这就是一个完整的方法。然后我们再回头来看这个方法的理论保障是减少了有效的Dvc,这样就可以做得更好,这就是SVM。

 
 

下一讲

我们开始讲将SVM的复杂度控制配合非线性的转换,看可以做到什么事情。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

Machine Learning Foundations 16: Three Learning Principles


 
 

总结:

Occam’s Razer: 简单是好的

Sampling Bias: 小心抽样的偏差

Data Snooping: 小心不要偷看资料

 
 


 
 

上一节:

很重要的工具 validation,留下一定的验证资料来模拟测试程序,来衡量和选择比较好的训练模型。

 
 

这一节:

三个做机器学习时候的精囊妙计。

 
 


 
 

第一个: occam’s razor (occam 的剃刀)

 
 

今天你要对你的资料作解释的话,越简单越好。(爱因斯坦说的?)

不要对一个东西做过多的处理。(William of occam)

 
 

我们不要对资料过分解释。

 
 


 
 

举例:

两张图,左边的比较简单,比较好。

 
 

问题是:

什么样叫做简单的解释?

为什么简单的比较好?

 
 


 
 

什么是简单的?

 
 

简单的 hypothesis:

看起来很简单(就像上面大大的圆)表示只需要少出参数就能描述。

 
 

简单的 model:

有效的 hypothesis 不是很多的话就是简单的,Dvc 很小。

 
 

关联性:

Hypothesis set 有 2^L 次方个 h,那么一个 h 有L个参数来描述。

所以整个hypothesis set 数量不多的话,单个h也相对简单。

 
 

所以只要得到上面的两者之一简单,那么就可以说资料是简单的。

 
 


 
 

为什么简单是好的?

 
 

直觉的解释:

想象你有一个简单的model,也就是成长函数很小,成长很慢的。

成长函数很小意味着:给随机的数据,只有很小的机会模型的Ein会很小;给非随机的数据,模型的Ein会很小。

如果是复杂的模型,不管给什么样的资料统统都可以分开,那就不知道这个资料到底是不是具有显著性了。

 
 

所以一般都从线性模型开始考虑,使用了模型以后一定要思考一下还有没有更简单的来做。

 
 


 
 

小测验

 
 


 
 

1948 年的总统选举电话民调,根据民调结果说 deway defeats truman。

 
 


 
 

结果是 Truman(杜鲁门) 赢了。

 
 

为什么?

编辑搞错 – 不是

运气不好 – 不是

 
 

提示:电话当时是很贵的,所以抽样的是有钱人。

 
 


 
 

第二个:Sampling Bias

 
 

抽样有偏差的时候,学习的结果也是有偏差的。

 
 

训练和测试要在同样的分布下做。

 
 


 
 

经验;

Netflix 办的一个比赛,比原来的好10%就可以获得100万美金;

老师第一次尝试采用标准的随机 Dval 的结果就好了 13%;

但是没有拿到奖金。

 
 

为什么?

比赛的测试环境:前7部电影用来训练,后3部电影用来测试,测试的资料具有时间关系,不是随机取样。

所以 随机取样的Dval 和 具有时间关系的 Dtest 是不一样的。

 
 


 
 

怎么办?

 
 

了解你的测试环境,让你的训练环境和你的测试环境尽可能的接近。

 
 

上个例子:

可以是:后面的资料权重比较多。

也可以是:不随机的验证资料,而是已有资料的比较靠后的资料来做验证资料。

 
 

回到我们所讲的第一个机器学习的问题:银行发卡,问题在哪?

银行已有的资料都是已经经过筛选的发了卡片的客户的资料,而排除了那些没有资格获得卡片的用户的资料,这两者是有区别的。

 
 


 
 

小测验

 
 


 
 

用眼睛看资料,用人脑学很危险。

 
 

第三个: visual data snooping(不要偷看资料)

 
 


 
 

不仅仅是用眼睛偷看图

在使用资料的任何一个过程都是在偷看资料,脑袋里的任何决策都是污染了 model complexity。

 
 

例如:

有8年的训练资料来预测未来两年的走势。

比如:用前面六年做训练,后两年做验证,是蓝色的线;如果偷用8年的数据来做训练,后两年的再做验证,结果就是红色的线。乍一看红线投资报酬率非常高,但是那是不可信的。

 
 

偷看是自欺欺人的做法。

 
 


 
 

其他偷看的例子:研究的例子,一篇比一篇好

 
 

后面的论文是在前面的论文的测试结果的好坏基础上再继续做的,可以看作是间接的偷看了测试资料的表现特征。所以越后面的论文越容易被污染。

 
 


 
 

所以:你要仔细的去考虑偷看这件事情。

 
 

做法:

要么完全不偷看

做 validation

避免用资料做决定,比如做语音的,先考虑语音的特性建模再输入资料,不要去看了一遍资料再来建模处理问题。

时时刻刻存着怀疑,时时刻刻考虑污染的问题。

 
 

能在 KDDCup 表现那么好,诀窍:

非常小心的平衡两件事情:data-driven modeling(snooping) & validation()。

也就是说靠 validation 而不是 snooping 来做合理的选择。

 
 


 
 

小测验

 
 


 
 

总结课程(3的魅力):

 
 

  1. 介绍了3个和机器学习相关的领域

Data mining:数据挖掘,和ML高度相关

Artificial Intelligence:人工智能,ML是实现Ai的一个方法

Statistics:统计学,ML使用了大量的统计工具

 
 


 
 

  1. 3个理论上的保障

 
 

Hoeffding:抽样的动作,用在测试。测试的时候只有一个 hypothesis,hoeffding告诉你怎样一个结果保障。

Multi-Bin Hoeffding:很多个选择的 hoeffding,validation/model selection 的时候,有限多个选择的时候用,告诉你对结果的限制。

VC:无限多的选择的时候用,描述机器学习在训练的时候的保证。

 
 


 
 

  1. 三个线性模型

 
 

PLA/Pocket:采用01错误,flipping noise 越小越好

Linear regression:线性回归,采用平方错误,公式解

Logistic regression:把分数透过一个s型的函数再输出出去,梯度下降求解

 
 


 
 

  1. 三个很重要的工具

 
 

Feature Transform:扩大维度使得Ein变小,代价是Dvc变大

Regularization:让Dvc变小,代价是维度变小Ein变大

Validation:留下一块干净的资料来做validation,选择比较少,代价是train用的数据变少了

 
 


 
 

  1. 三个锦囊妙计

 
 

Occam’s Razer: 简单是好的

Sampling Bias: 小心抽样的偏差

Data Snooping: 小心不要偷看资料

 
 


 
 

  1. 三个未来的学习方向

 
 

More Transform:更多的数据转换方式

More Regularization:更进阶的regularzation

Less Label:更少的label,unsupervised怎么弄

 
 

大量的名词

 
 


 
 

小测验

 
 


 
 

总结:

Occam’s Razer: 简单是好的

Sampling Bias: 小心抽样的偏差

Data Snooping: 小心不要偷看资料

 
 

下一课程:机器学习技法