Category: All

Machine Learning Foundations 13: Hazard of Overfitting


 
 

内容

  • Ocerfitting 的概念: Ein 变低, Eout 变高
  • Overfitting 很危险很容易发生,原因是:两种noise,数据不够,目标太复杂
  • 怎么解决 Overfitting:data cleaning/hinting/pruning, 等等,下面的课程继续介绍

     
     


     
     

    上一次我们讲到原来我们的model是线性的,如果我们把linear model配上non-linear的transform,那就产生的非线性的model来扩展我们的学习,代价是付出额外的model的complexity。

     
     

    今天我们从 complexity 出发,说到这额外的 model complexity 会造成机器学习里面一个很大的困难叫做 overfitting。我们首先将这个困难是如何产生的,然后说要怎么样解决它。

     
     


     
     

    我们先从一个例子出发:

     
     

    有五个资料点,X是随机产生的,Y则是X代入某个二次函数,再加上一些noise产生。

     
     

    如果我们假设我们用一四次的多项式来做回归分析,配合五个点,那就是有唯一解,也就是 Ein = 0,就是右边的红色的线,但是你会发现和蓝色的目标函数差距很大,也就是 Eout 很大。

     
     

    这个叫做:Bad Generation

    已有资料做得很好,未知资料结果就不好。

    当 Dvc 很大的时候,就会发生这样子 Ein 很小, Eout 很大的情况。

     
     


     
     

    前面提到过如果你用 1126 次方的多项式来做 learning,就会导致 Ein 很小,Eout 很大,这是不好的。

    同样讲过右边的图,Eout 会有一个先下降后上升的趋势,最低点就是最好的 Dvc 的位置。

     
     

    Overfitting: Ein越小,Fitting越好,但是会过头,造成Eout上升。

    Underfitting:fit的不够好。

     
     

    Underfitting 相对比较好解决,增加 Dvc 就可以,上次nonlinear transform就是来处理这个问题;overfitting比较不好解决,下面我们来探讨这个问题。

     
     

    Bad Generalization:描述的是一个当前状态的情况。

    Overfitting:描述的是变化的过程。

     
     


     
     

    如果选了一个好的如左图,右边是overfit的情况。

     
     

    我们如何来看这个问题,通过使用一些比喻来了解:

    overfit:好像出了车祸

    原因:开太快,等等(主观的)

    noise:路不平(客观的)

    资料量:路况(资料点够密,路熟悉)

     
     

    所以会发生overfitting:所以会发生车祸

     
     


     
     

    小测验

     
     


     
     

    为了让大家更了解 overfitting ,这里继续做一系列试验,来说明。

     
     

    还是考虑一维的回归分析,资料的产生:

     
     

    左边:

    用一个十次多项式来当作目标函数,X随机取样,Y由多项式值加上一些杂讯产生。

    右边:

    考虑一个五十次的多项式,不考虑杂讯生成 XY。

     
     

    我们用两个不同的 learning model:一个是2次的(绿色),一个是10次的(红色)。

    看哪个会表现得比较好。

     
     


     
     

    左边:g10 overfitting

    Ein: g10 < g2

    Eout:g10 >> g2

     
     

    右边:g10 overfitting

    Ein:g10 << g2

    Eout:g10 >> g2

     
     


     
     

    我们发现:

    G10,G2 如果今天这两个人都知道目标多项式,那么 G10 应该要比好吧?但是 G2 的结果反倒比较好。

     
     

    这叫做: concession for advantage (以退为进)

     
     


     
     

    为什么会这样?

     
     

    来看看 learning curve:描述得是资料量的多少和error的变化。

    上面左边的是 h2的 linear regression,其他h2类似。

    上面右边的是 h10的 linear regression,其他h10类似。Ein/Eout拉大了,因为 model complexity。

    重要的是左边的灰色区域 Eout_10 >> Eout_2。

     
     

    结论:资料量不够多的时候不用想太复杂的 model 。

     
     


     
     

    再来看没有 noise 的例子:这个时候还是 g2 做的好。

     
     

    你觉得这个时候真的是没有 noise 么?

    这里的noise的意思是:50次的 2/10 次理论上都做不到,而之间的差距就是 noise。

     
     

    结论:当你学的事情很复杂的时候,这个复杂度也可以当作是noise对结果产生影响。

     
     


     
     

    小测验。

     
     


     
     

    下面来做更细节的实验来告诉你说什么时候你要小心 overfit 会发生。

     
     

    产生资料分成三个变量:

    • Target function : 某个次方的多项式 ,多项式是 f 次。
    • Noise : Gaussion noise 强度不一样的时候对我的 overfitting 的影响,强度是 sigma^2。
    • 资料量:N

     
     

    这里要注意的是要产生真正的50次多项式,需要做一些手脚:正规化保证真正的50次。

    因为产生随机数的很多时候高次项系数为0的可能性很高。

     
     

    我们来探讨这三个变量对结果的影响。

     
     


     
     

    同样我们用两个学生来学习:

     
     

    G2: 只会最多2次多项式

    G10: 只会最多10次多项式

     
     

    结论:

    Ein_10 < Ein_2

    Overfitting 衡量: Eout_2 – Eout_10

     
     

    下面使用图示来 show overfit 的程度:

     
     


     
     

    左边:

    目标函数复杂度固定在20,横轴是资料量,纵轴是 gaussion noise 的程度 sigma^2。

    红色表示非常overfit,蓝色表示没有什么overfit。

    N 小,noise大会造成 overfit。

     
     

    右边:

    纵轴是目标复杂度,使用一样的gaussian sigma。

    目标越复杂,资料量不够会造成 overfit。

     
     

    这里的图就是 课程的 logo

     
     


     
     

    我们加上的 gasussion noise 是会对结果产生蛮大影响的,我们把它叫做 stochastic noise(随机噪声)

    我们的目标复杂度也会对结果产生很大的影响,我们把它叫做 deterministic noise(固定噪声)

     
     

    从上可以看出四个会发生 overfitting 的时间点:

    • 资料太少
    • 随机噪声太多
    • 固定噪声太大
    • 精力过剩(当今天目标函数是10次以下的时候,对于G10来说太简单,更容易 overfit)

     
     

    Overfit 很容易发生!!!

    就像小孩开大车。

     
     


     
     

    上面讲到如果今天目标函数太复杂的话和 noise 没什么区别。

    在CS里面常用:pseudo-random generator 随机数生成器 用的就是这个概念做的。

     
     

    如右图:蓝色标识的目标函数和红色标识的h之间是有差距的,当目标函数太过复杂,h没有办法表述的时候。灰色的区域就是 确定噪声。

     
     

    确定噪声特点:

    和 H 的复杂度相关

    对同一个 X 来说是一样的

     
     

    除了上面两点就是一般噪声

     
     


     
     

    小测验

     
     


     
     

    接下来我们要怎么样对付 overfitting 呢?

     
     

    机器学习:对比开车

     
     

    用简单一点的model:开慢一点

    Data cleaning/pruning:了解更精确的路况资料(下面讲)

    Data hinting(从现有的资料或者对这个问题的了解产生更多的资料):收集更多的路况资料(下面讲)

    Regularization:适时踩刹车(后面的课程讲)

    Validation:看看仪表板(后面的课程讲)

     
     

    综合使用多种工具来避免 overfitting。

     
     


     
     

    二分 1、5:

     
     

    如果把资料表示到 2d 平面就会有一群 1/5 。

    对于左上角的一个点被表示成5,你需要去确认他是 outline:

    如果标错了就改过来(Data Cleaning)。

    如果是没用的(data pruning)

     
     

    但是这里的难点是怎么去确认这个点有问题。

     
     


     
     

    Data Hinting:

     
     

    识别手写字,已有上面的这些资料,没办法再加了,但是根据我有的一些知识,对现有资料做一些小的变化,来创造出新的虚拟的资料,用在 model 里面。

     
     


     
     

    小测验。

     
     


     
     

    总结:

    • Ocerfitting 的概念: Ein 变低, Eout 变高
    • Overfitting 很危险很容易发生,原因是:两种noise,数据不够,目标太复杂
    • 怎么解决 Overfitting:data cleaning/hinting/pruning, 等等,下面的课程继续介绍

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

Machine Learning Foundations 12: Nonlinear Transformation


 
 

今天讲的是非线性的变换

 
 


 
 

上次讲到三个linear model都可以用在各式的classification问题上面,包括二元分类和多元分类的问题。但是这些model的重点是linear的,用线性的方式算一个分数,今天我们要把这个model衍生到non-linear的情况。

 
 


 
 

Linear hypotheses

 
 

如果今天是二元分类的话,视觉上就像切一条线,数学上表示就是 分数 = 权重 * X

这样带来的好处是 VC 维度是受到控制的,复杂度可控,Ein/Eout 不会差别太远。坏处是有些资料不可能用直线可以切分。

 
 

因此下面讲的就是如何去突破linear model的限制。

 
 


 
 

怎么做呢?

 
 

对于上面图示的资料来说

资料 D 不是线性可分的,就是不能用直线切分。但是如果我们采用圆圈来切分的话,看起来我是可以把ooxx分开来的。

比较方式是点到圆心的距离的平方,把它跟0.6比,这样一个hypotheses是可以区分这些资料的。

 
 

那么可以说上面的资料是圆圈圈可分,这样我们就可以重新设计怎么杨用圆圈圈来做PLA, regression等等。

 
 

但是这样太麻烦了吧,因此我们要来考虑怎么样系统化的设计这些演算法。

 
 


 
 

那我们首先来看看怎么用圆圈圈的方式来做到资料分类呢?

 
 

先把上面扯到的圆圈圈的方程式列出来,0.6代表圆的半径的平方,与点到圆心的距离的平方做减法,拆分出来就会有三个系数 w0, w1, w2,系数代表了hypotheses的圆的大小,系数同时配合输入x决定在圈内还是圈外。

 
 

上面的公式符号化表示也同样可以是 sign( w z ),和线性的时候是相似的,都是向量内积。

 
 

这样你就会发现:

这里面使用圆圈圈来区分可以看作是把 原来 x 空间里面的点 都转化到 Z 空间里面去。这里就是 z1 = xa^2, z2 = x2^2,也就是说对每一个点的值取平方画到新的空间中去,这样以后得到的就是右图。

这样就线性可分了,这条直线对应到原来的空间就是曲线。

 
 

上面做的 x -> z 的过程就是 feature transform(特征转换),这样后就可以继续使用线性分类了。

 
 

那么反过来也是对的么?就是说新的资料线性可分,那么可以得出旧的资料可以用圆圈分开这个结论么?

 
 


 
 

上面的转换的数学表示

新的资料线性可分:Z0, Z1, Z2

新的 hypotheses:w * 转换过的x

 
 

我们上面探讨的情形就是 w0, w1, w2 对应 0.6, -1, -1 正圆里面是oo

反过来的话 -0.6, 1, 1 正圆外面是oo

再如果是 0.6, -1, -2 得到的是椭圆

再来 0.6, -1, 2, 得到的是双曲线

还有 0.6, 1, 2 是常量

 
 

所以z空间里的每一条线对应到的可能是 圆/椭圆/双曲线/常量 等等,但这里面三个数值对应到的二次曲线也不是完整的一般二次曲线。

 
 


 
 

如果你要对应到所有可能的二次曲线,则你需要所有的 0/1/2 次项,这样你在Z空间里面的perceptions 对应到的就是 x空间里面的某一个分类方式。

 
 

这些就是我们目前可以考虑的分类方式:二次的 H_phine2 就是先把 x 透过 phine2(二次) 转化到 z 空间,再用某个线性分类器分类。

 
 

所以举个例子:如上式子表示的椭圆,则需要的就是橘色标识的那些系数来表示,对应到上面通用公示的六度空间的系数。

 
 

直线其实也已经包含在这个式子里面了。

 
 

到这里我们讲了我们怎么定义一个二次的hypotheses, 下面讲我们怎么学到好的二次hypotheses。

 
 


 
 

小测验

如果要是抛物线,系数会是什么样子?

 
 


 
 

我们现在已经建立的关系是这样:

 
 

Z 空间里面的直线 对应到 X 空间里面的所有的二次曲线

Z 空间里面找到一个好的分类直线 对应到 X空间里面的好的分类二次曲线

 
 

现在我们想要在 Z 空间里面找出好的直线,我们知道的是X空间的数据,应此做法就是先通过变换讲X空间的数据统统变化到Z空间上面,然后在Z空间上面找一条好的直线。

 
 


 
 

如上图所示将 (x, y) 转化成 (z, y),然后在右上图找到一条好的直线来做分类,然后再反对应到X空间,就可以看作是通过二次曲线在(x, y)空间做分类。

 
 


 
 

在这个流程里面有两件是我们可以选择的事情:

  1. 怎么做转换,转换到什么空间中去
  2. 用什么样的linear model:上面我们使用binarg classification来和大家做就讲解,但是同样的方式可以延伸到linear regression/logistic regression等等方法以及多类分类上面。


潘多拉盒子:

现在我们可以做很多很多事情,原来学过的所有东西都可以二次化,三次化,等等。

 
 


 
 

其实我们早就说过 feature transform 很重要,在之前讨论在做机器学习的时候可以用哪些feature(第三课):收集到的资料你可以把它做一些整理,处理。

 
 

原来是把 raw feature(原始资料) 透过我们对这个问题的了解,来做转换变成 比较容易吸收的资料的过程。

 
 

特征转换 这个是 机器学习里面的 the force(原力)。

 
 

但是这边特征转换听起来是那么的好,但是使用它是否也会有代价呢?下面来回答这个问题。

 
 


 
 

小测验

 
 


 
 

这么多个项的意思是什么呢?

如果我们今天想要general的情况的表示,就是 phine_Q = 0次的部分 + 1次的部分 + … + Q次的部分。

 
 

这里有多少个dimension呢?

1 + d:1代表常数,其他非常数的维度 = 有多少种不同的方法来组成 Q 那么多的项。

对应到概率论就是 重复组合 问题:d种东西可以重复取的化,一共有多少种不同的组合,结果就是 (Q+d / Q) 这么多种情况,大概就是 Q^d 这么多项,也就是说你今天就要花大么多的力气去计算。

 
 

所以特性转换的一个大的代价就是,计算和存储都需要花额外的力气,特别是Q很大的时候,这件事情非常困难。

 
 


 
 

上面讲到这个展开式有 Q^d 这么多项,也就是说需要 那么多个 W ,也就是 自由度,也就是说 Dvc 非常大,自由度大量的增加。

 
 

怎么办?

事实上我们可以证明的是 Dvc <= d+1,因为任何一个 Z 空间里面的 d+2 个点是没有任何办法 shatter 的,也就是说回到X空间里面 d+2 个点也不能够被 Q 次曲线来 shatter,这样就对我们的Dvc产生了限制。

因此上限就是 d+2

 
 

所以第二个代价就是,当Q变大的时候,Dvc也变大。

 
 


 
 

那么这件事情有什么坏处呢?

 
 

看上面两张图,同一资料两种不同的分类方式,左边说用一条线分类,右边说用一个四次曲线来分类。请问你会选择哪种分类方式?

 
 

你有没有更加觉得左边的图更加符合资料的特性,右边那个是不是可能太过头。

 
 

今天我们使用不同的 hypotheses 的时候,会冒出不同的问题来,两个核心的问题:Ein/Eout 接近不接近;Ein 够不够小。两个问题的 trade off 是不一样的。

 
 

如果 d(Q) 特征变换 大的时候 Ein小 Ein/Eout 隔得比较元远,反过来就相反。这是 ML 领域里面最重要的 trade off。

 
 

所以问题就来了:我们要怎么去选择适当的变换。

 
 


 
 

用眼睛来决定会存在问题:

 
 

如果资料在10维度空间,你可以做到?

如果是低维度,你用的是 phine_2, 原本是6参数,但是你算一下发现这里不那么复杂不用6维度,是不是只需要三个维度就能解决,再来,两个维度,第二个维度是 x1^2 + x2^2 也能解决,这样是不是都可以?

还有最聪明的方式,把结果 sign(0.6-x1^2-x2^2) 当作变换,这样是不是Dvc就是1,可以么?

 
 

上面你的化简,都是你聪明的小脑袋经过了一些运算和学习过程,把适合的变换用在了这个资料上。这里使用了你的主观感受,也就是说这是 humen learning,你替代了机器做了选择。

 
 

你没有把你脑袋的 Dvc 算到整个 model 里面去,那么你就会变得很乐观,但是你的 model 不会是你想象的那样好。

 
 


 
 

小测验。

 
 


 
 

这边我们来看看上面提到的多项式变换,首先来定义一下变换的次项:

 
 

这里 phine_0 表示0维的变换,就是常数项,phine_1表示1维的变换,就是所有的一次项加上phine_0的变换,以此类推,直到phine_Q = phine_Q-1 + 所有的Q次项。

 
 

也就是说你的每一变换都包含了前面的变换,也就是说高维的变换包含低维,低维的就是高维的特例。他们的 hypotheses set 也就是包含关系,画成图就如上面所示。

 
 

图示就是 hypotheses set structure。

 
 


 
 

这个结构告诉我们:

Hypotheses set 大包含小;H越大Dvc越大;hypotheses set大对应的最好的Ein小。 三串关系。

 
 

画成图就如上面所示。

 
 


 
 

这告诉我们:

如果你一开始就用一个超级高纬度的变换,结果一定也不好,在这个曲线的右边。

 
 

安全的做法是从 低维度开始做起,如果Ein(g1) 结果就很好,那就是好的结果,如果Ein不够小,就增加维度。

其实你会发现线性很多时候就已经可以得到很好的结果了。

 
 


 
 

小测验。

 
 


 
 

总结:

今天把大家熟悉的原来的 linear model 延伸到 nonlinear model。

一开始说怎么做二次的事情,然后还能继续扩展;然后说完整的nonlinear流程到底是什么样子;接着说这虽然看起来很好用,但实际上是要付出代价的,最重要的代价就是model complexity;最后告诉大家说你要付出这代价的情况下最安全的做法是从简单的model开始试。

 
 

这边我们就讲完了在 linear/nonlear model 上最基本的工具是哪一些。

我们提到过 变换 就是 the force(原力),下一次我们要和大家说的 the force 的黑暗面到底是什么,造成了什么不好的影响,怎么去控制黑暗势力。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

Machine Learning Foundations 11: Linear Models for Classification


 
 

我们要从之前学过的binary classification开始来看看我们学过的这些model怎样延伸出来处理更复杂的multi-classification的问题。

 
 

内容:

  1. 证明可以使用 linear/logistic regression 来求解 binary classification
  2. Logistic regression 的加速算法 stochastic gradient descent (SGD):做法就是使用随机梯度来替代真实梯度。
  3. 分多类的基本方法 One-Versus-All (OVA):二元就是 二元分类组 求解概率最大的。
  4. 分多类的第二种方法 One-Versus-One (OVO):两两配对形成二元分类组,结果当作是投票取最大的。

 
 

这一课丰富了 linear classification 下的算法,首先先讲 以前讲的三个 linear 分类方法 都可以来做 binary classificaiotn;再把 logistic regression 延伸到 SGD,然后你会发现其和 PLA 很有关系;最后讲了两种不一样的做 多类别分类的方法 OVO/OVA。

 
 

 
 


 
 

我们上一次讲了logistic regression,怎样去定义里面的error function,它是平滑可微的,因此使用gradient descent的方式来找出一个好的logistic hypothesis。

我们来看如何延伸这个问题。

 
 


 
 

我们来看一下已经讲过的三个模型。

共同点就是他们都算一个分数,分数来自特征的加权和。

算完分数后,

Linear classification: 分数取正负号,只看对或者不对,但是算分数比较难求解。

Linear regression: 直接把分数输出出去,不再处理,求解很容易。

Logistic regression: 把算完的分数通过一个sigma函数转化一下,可以用gradient descent的方式求解。

 
 

我们首先来探讨的问题是:

Linear regression/logistic regression 能否作为求解linear classification的工具?

 
 


 
 

因此我们来限制这里的 y 都必须是 正负1.

对于 logistic regression 来说本来其值就在实数区间,现在就是两个特别的实数,也就可以直接来用。

 
 

我们要来推导三种方法的相似性之前,首先要想办法把他们所用的error function稍微整合一下,也就是从 分数 变成 Ein function的过程都串起来。

 
 

Linear classification:

(方框内头两行)原来有两个步骤,首先是算hypothese(取正负号),再是看hypothises他和y一样不一样。

(方框内下面三行)Error换一种写法:现在假设Error Function如上面所示: err0/1(s, y) s表示对hypothises的值的映射操作,譬如这边取0/1,y就还是表示y。

 
 

通过用sy来表示Error function,则 Linear regression/Logistic regression 也都可以一同同这种方式表示出来。

 
 

接下来我们要做的事情就是看看这个 error function 和 y s 的关系。在做这件事之前我们先来看看 Y S 的物理意义。

Y 可以说是 correctness, s 表示 score, 因此我们希望的是 correctness score 越大越好。

 
 


 
 

要比较这三个error function,我们先想办法把他们画出来看看。

 
 

横轴是 y * s

纵轴是 error function 到底是多少

 
 

例如说

我们画 0/1,我们要看的是 sin(ys) 到底是不是正1,也就是说在 ys 轴向上正的那边 error 就是 0, 如果是负的 error 就是1。

 
 


 
 

如果对于平方错误 sqr

Ys 与 1 比较取平方,就是图上红色的线。

 
 

特点是:

抛物线左边来看是和 01 错误一样,越偏离原点就是错误;

对于右边来讲,偏离越大错误越大,这和01错误的右边都是对的区别很大。

 
 

但是有一个结论:

如果今天有一个在 平方错误的时候错误值很低, 那么他在 01 错误上面也会得到很低的错误值,反之不成立。

 
 


 
 

如果是 logistic regression 的错误,画出来如上面黑线所示。

 
 

他是一个平滑的曲线, ys 越来越大, 错误越小; ys越小, 错误越大。

 
 

这里也有一个结论:

如果今天有一个在logistic regression的时候错误很大,那么在01错误的时候也很大;反之 logistic regression的时候错误很小,那么01错误的时候错误也很小。

 
 


 
 

对 logistic regression 做一个倍数的变化,从 ln 变成 log2,为的是更好的比较和推导。

 
 

这样就有了在 ys = 0 这一个点,就可以看到 logistic regression 和 01 的 ys 错误比一样。

 
 

下一页会看到这些 error function 怎么样帮助我们证明 linear/logistic regresison 可以是一个好的 binary classification.

 
 


 
 

如果我们今天在意的是 Err_01

 
 

他的上限是 Err_sce,就上面的图所示,同样 Ein_01 / Eout_01 也有相关式子。

同样,Ein/Eout VC bound 也能作如下推倒

所有这些 E_01 都和 E_sce 相关联起来了。

 
 

结论:

如果把 logistic regression 的 E_sce 做好的话,就可以说是把 E_01 做的不错。

 
 

另外:

类似的使用 E_01 和 E_sqr 的关系,同样可以得出结论,把 E_sqr 做得不错的话, E_01 的结果也会不错的。

 
 


 
 

上面讲的方式叫做 regression for classification

 
 

做法:

  1. 使用 regression
  2. 回传 g 的时候,对 regression 的结果做一个函数映射到 classification 空间

 
 

对于 binary classification

使用 linear regression 来做:优化求解最容易,err_sqr 和 err_01 的实际差距比较大。

使用 logistic regression 来做:优化求解也比较容易,err_sce 比 err_01 宽松,因为是上限。

使用 PLA: linear separable 的时候不错可以求解,其他时候就要用 pocket 问题大。

 
 

建议:

  1. 使用 linear regression 来初始化设置 w0。
  2. Logistic regression 会比较常用。

 
 


 
 

小测验

 
 


 
 

我们之前讲过的 PLA/Logistic regression 都可以看作是 iterative optimization 方法,就是说是一步一步的让结果变得更好。

 
 

PLA 里面我们做的事情是:

取一个点看它的分类结果有没有错,如果有错就根据接过来修正错误方向,因此每一轮只需要找一个点就行。

 
 

Logistic regression做的事情是:

不仅仅是看一个点,而是看所有点的贡献的加权结果,再根据结果的梯度方向去做更新。

 
 

如果只看一轮的化,logistic regression在每一轮花的力气会比PLA大很多。

接下来我们探讨的话题就是我们能不能让 logistic regression 和 PLA 一样快?

从目前的角度看 logistic regression 和 pockate 一样快,因为每一轮都是需要看N个点。

 
 


 
 

所以首先来看一下 logistic regression 的演算法长什么样子:

 
 

我们要更新的式子如上面所示, w_(t) + 反向梯度方向上面走一段路 = W_(t+1),这里计算梯度这边存在N,但是我们不想那么慢,怎么办?

 
 

处理 sum(…)/N

一个可能的想法:看作是一个随机抽一个点,平均。

 
 

举个例子:你有100000个点的信息要的平均,不想全部加起来求解,那就随机抽取X个取平均获得的值与总的平均差不多。

这里就只抽一个,用来代替整体的平均。

 
 

这个数字叫做 stochastic gradient(随机梯度)。

真正的梯度 可以看作是 这个随机梯度的期望值。

 
 


 
 

这样的话:

 
 

我们可以把 随机的梯度 = 真正的梯度 + 某些 noise。

 
 

从这里我们可以写下新的演算法: stochastic gradient descent

做法:使用随机的梯度来做下降,而不是采用真实的梯度来做下降。

原理:当我今天走了足够的步数的时候,真实的梯度和随机的梯度应该差不多。

好处:简单,快速,每一步只用算一个点;资料量特别大的时候(big data) 或者 资料是一笔一笔的线性获得的时候(online learning) 非常适用。

坏处:less stable

 
 

因此公式就化简到上面所示:

Err 主要包含两部分 theta表示ys的乘积是走多远,yx表示跟新的方向往哪走。

 
 


 
 

上面的公式这么一化简,你就会发现:

 
 

PLA:选一个点出来,看它的结果对不对,不对的话就往他的方向做更新,没错的话不更新。也可以看作是 binary 的 SGD logistic regression。当 wx 的乘积很大的时候 SGD logistic regression theta 部分的值不是接近0就是接近1,就差不多是 PLA。

 
 

也就是说 SGD logistic regression 可以看作是 soft PLA:不只是看 有没有错,而是错多少。错的多就多更新点,错的少就少更新一点。

 
 

使用的两个要注意的问题:

  1. 你怎么决定演算法结束? SGD 决定什么时候停很难,很多人使用的时候就是让他跑足够的时间。
  2. 每一步走多远怎么确定? 经验上使用 0.1。

 
 


 
 

练习

 
 


 
 

接下来讲如何延伸讲过的方法来做多类别的分类,是非题变成选择题。

 
 


 
 

假设这里我们有四个类别。

 
 

先把其中的一个类别分出来,譬如右上角的方块;做法就是把右上角的方块当作oo,其他当作xx,这样用以前的方法做是非题,就可以把右上角的方块分出来。

 
 


 
 

同样的方法,可以把菱形和其他分开。

 
 


 
 

三角也可以。

 
 


 
 

星形也是。

 
 


 
 

这样我们就得到了四个不同类型的分类器。

 
 

使用的时候期待的是四个分类器中有且只有一个分类器告诉我是这个类别,其他的都告诉我不是这个类别。

 
 

譬如方块,会有一块区域就会出现上面所期待的结果,但是有部分区域出现的就不是我们所期待的那样。

这时候怎么办?

 
 


 
 

所以也许使用 soft binary classification 工具可以处理这个问题。

 
 

也就是来估计上面 P(方块|x) 这个的值,可能得到上面那张图来替代原来的二元分类结果图。

 
 


 
 

同样的适用于 菱形。

 
 


 
 

三角也是

 
 


 
 

星形也是。

 
 


 
 

这时候得到的组合就是各个分类器的概率。

 
 

然后你就是从结果中选择一个概率最大的结果,就是你想要的。最终你会得到上面的彩色图来表示的分类结果。

 
 

公式当中theta意思是不用考虑,因为四个分类器采用的是一致的theta,theta因此也就不影响比较大小的结果,不用考虑。

 
 


 
 

通过上面的推导,这边就可以和大家介绍一个简单的演算法(One-Versus-All (OVA) ):

(这是一个非常常用的方法)

 
 

  1. 对于每一个类别跑一个 logistic regression;
  2. 跑完之后对于每一个的结果,选择分数最高的。

 
 

好处:有效率,快;支持任意的regression二元分类方法。

坏处:当类别很多的时候,形成的二元分类方法会趋向于得到错误结果,这样会让结果变得不够好。

 
 

下面讲怎样克服这个问题。

另外,统计上有更加系统的多类别问题的基础推导,和这边讲的过程会不一样。

 
 


 
 

小练习

 
 


 
 

我们上面讲到 One versus All 里面最麻烦的问题就是:类别大了以后很有可能面对的是一个 unbalance 的问题(正确的例子很少,错误的例子很多)

 
 

解决:想办法平衡正确错误的例子数。

 
 

那么可以尝试从所有的 类别 里面选两个出来,先看看这两个里面哪个比较像正确的例子。

 
 


 
 

例如,这里可以一对一的,把方块当oo,菱形当xx,然后做 binary classification,就可以得到右边比较像方块。

 
 


 
 

同样的 方块和三角形

 
 


 
 

方块和星形

 
 


 
 

菱形和三角

 
 


 
 

菱形和星形

 
 


 
 

三角和星形

 
 


 
 

这样一共就得到了 6 种二元分类结果。

 
 

有三个是和方块有关的分类器,这三个分类器在很接近方块的地方都是蓝色,也就是认为是方块,我们只需关系心这三个。

通过这三个分类器,如果有方块的分类器都说是方块,那就是方块。

 
 

那么

对于任一点走这6个分类器,其给出的6个结果中数量最多的就是最终结果,得到上图四色标识的结果。

 
 

其实就看作是 6个人投票说这是什么。

 
 


 
 

这就是介绍给大家的另外一个方法 One-Versus-One (OVO) :

 
 

  1. 所有类型两两配对形成 binary classification 分类器;
  2. 使用所有的分类器 当作 选票,选出票数最多的结果就是最终结果。

 
 

优点:有效率,很多组但是每一组资料量比较少,可以使用任何的binary classification。

缺点:需要存储大量的中间结果,预测时间长。

 
 

K不多的时候,简单好用,稳定。

 
 


 
 

小练习

 
 


 
 

这一课

丰富了 linear classification 下的算法,首先先讲 以前讲的三个 linear 分类方法 都可以来做 binary classificaiotn;再把 logistic regression 延伸到 SGD,然后你会发现其和 PLA 很有关系;最后讲了两种不一样的做 多类别分类的方法 OVO/OVA。

到此都集中在线性分类领域。

 
 

下一节:

从线性讲到非线性的问题如何去处理。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

Machine Learning Foundations 10: Logistic Regression


 
 

内容:

  1. 问题模型
  2. 推导Ein
  3. 找到 w 使得 Ein 最小
  4. 通过梯度下降法计算得到最小的 W

 
 


 
 

上一次介绍的是 linear regerssion,使用平方错误可以很方便的算出来最好的情况在哪里。

今天我们来看一下 logistic regression 可以用在哪些地方。

 
 


 
 

我们先来看看 学习流程图:

这里的例子还是医院的系统,我们用机器学习来判断病人有没有心脏病。

 
 

左上角说我们拿到的资料是有noise的,我们可以用一个target distribution来描述这个问题,对于这里的这个二元分类问题,target distribution会是一个理想的目标分类函数,就是把目标的分布是大于还是小于1/2,直接得出预测结论。

在这里我们在意的是 classification error,就是二元分类结论对不对。

 
 


 
 

类似的问题:如果我们想要知道的是病人两三个月后心脏病发的几率是多少。

表示:我们有兴趣的是一个 0-1 的值,不再是二元分类的结论,而是分类结果的可能性值。

 
 

这就是我们今天想要探讨的问题 soft binary classification。

 
 


 
 

我们今天要怎样做,才能找出一个好的hypothsis,来跟这个target function很接近。

 
 

我们想要输出的是 P(1|xi) 这个 0-1 的数值

我们需要的输入是 期望是直接有与x对应的P的值

剩下的事情就是找一个 hypothesis G,让资料的预测差异越小越好

 
 

事实上我们拿不到期望的输入,我们能有的是

譬如心脏病发这件事情,我们有的资料是: 以前的病人XX在过了几个月后 病发了还是没有病发,但是不会有他的资料是说他几个月后并发的概率是多少;对于所有的病人(单笔资料)都是得到这样的数据。

 
 

这样的资料和我们以前做 binary classification 的时候是一样的,我们手上有的是xxoo这样的01结论。

 
 


 
 

因此我们可以把手上的资料(上一页ppt的actual data:OOXX) 转换看作是 我们想要的资料的带 noisy 的版本(这一页PPT的actual data:0011 ),这样也就有0-1数值了,只是有noise。

 
 

我们今天要做的就是

输入是 OOXX 这样的 binary classification 结论的时候,如何去求解得到一个好的 hypothesis 来求解 P。

 
 


 
 

要得到一个好的 h,我们首先需要设定一下 hypothesis 的长相。

Feature 和以前一样表示为 xi, 有了这个以后可以算一个加权分数。

 
 

然后

我们今天有兴趣的不是这个分数本身(采用分数本身求解就是linear regression);

我们今天有兴趣的是得到一个0-1之间的值。

 
 

因此我们采用右图所示转换函数函数图:横轴是分数,纵轴是0-1。通过分数(可能是 -无穷 到 +无穷)来直接转换得到0-1的目标值。这个函数命名为 theta (logistic funtion)

 
 

因此我们下面看的就是如何找出一个 logistic hypothesis 来和我们的目标函数f接近。

 
 


 
 

最常用的logistic funtion长成这样(蓝色框所示,就是图中蓝色线一样的长相)。

 
 


 
 

小测验

 
 


 
 

图中三种模式对照

 
 

相同点:

使用权重数据来算分数

 
 

不同点:

Linear classification: 直接根据分数大于还是小于0来判断,error 就是分对还是分错(01值)

Linear Regression: 直接输出的就是分数,error 就是数值差的平方

Logistic Regression: 算完分数再透过一个logistic function来转换得到 0-1 的数值, error 会是什么?

 
 


 
 

来定义 error function 长什么样子。

 
 

我们来看 target function 可以写成上边黄色框内右边的结果。

然后我们来看假设我们有一笔资料集D(x0-xn),那这个资料产生的几率是多少? 就是粉色框内的结果和推到(f是我们不知道的,假装h来替代)。

 
 

因此得到的观念:

如果我们今天 h/f 很接近的话,那么 h的可能性/f的几率 也很接近

通常f产生这些资料的几率是很大的

 
 


 
 

因此根据上面的观念推演出:

g 就是可能性最高的那个h

 
 

另外对于 logistic regression,如图函数存在对称性,就是棕色框框公式所述。

 
 

因此对于原来的 likelihood(h):

P灰色部分对于所有的h来说都是一样的,不用在意。

不一样的是h/1-h的部分,可以根据对称性替换得到下一张PPT所示的结果。

 
 


 
 

因此得到:h可能性 正比于 h(ynxn)乘起来

 
 


 
 

因此我们来看这个正比公式:

可以把h换掉成w(权重),得到下一页所示

 
 


 
 

这里面出现的是连乘,取log去掉连乘,为了运算。

 
 


 
 

这里是max,我们希望能使minimize的动作,也是为了方便运算,如下页所示处理。

 
 

因此我们要做的就是 minimize 连加,就和以前的计算方式类似,我们就是要找一个w使得整个式子的结果最小。

 
 


 
 

我们把 theta 的公式代入式子,就可以做上面的推导。

 
 

Ein 部分就是把 Err(w, xn, yn) 累加结果。

 
 


 
 

小练习

 
 


 
 

上面已经推到得到了 Ein,剩下的问题是 我们怎么去找到一个 w 使得 Ein 最小。

 
 

之前我们讲到 linear regression 里面函数是平滑的 甚至是 convex 的,因此找到梯度为o的地方就是目标W。

 
 

这里 logistic regression 你去推到一下的话也会发现这个函数是 convex 的,这里就不推到了。因此同样我们要做的事情就是想办法找出谷底在哪里,就也是梯度为0的地方。因此下面就是算上面公示的梯度。

 
 


 
 

直接不能处理,就定义一些中间变量:这里就是定义 方块和圈圈

 
 

这个方法是解微分的基本方法之一,请看高等数学相关内容。

 
 


 
 

求解过程。

最终得到 Ein 的梯度。

 
 


 
 

因此下一步我们是不是就是去求解梯度为0呢?

 
 

但是你会发现:

Theta 全部都是 0 的话,那么Ein梯度就是0。

也就是说 Theta() 里面的东西都要是 -无穷,代表 ywn 相关部分就是要 正无穷;wx 是分数,y*分数 是正的代表同号,也就是说 w 是好的w,所有的都满足。

那就是说整体上要线性可分才会满足 theta 全部都是 0.

 
 

因此

Weight sum = 0

今天我们要解的是非线性方程式,要算出其谷底在哪里很困难,没有close-form solution。

 
 


 
 

我们回头到 PLA 方法里面找灵感:

 
 

PLA的特点就是从某一个出发,一步一步修正结果。

每次看看这个w在哪里犯了错误,然后从犯错的地方看怎么去修正,直到不用做更新。

 
 


 
 

为了后续方便讨论,我们把两个步骤简化成一个步骤:

 
 

随便取一个点,如果点是错的,则加上ynxn;如果点是对的,则加上0.

这和原来的两步是一样的内容。

 
 


 
 

这个更新的式子里面有两样东西:

  1. 更新的方向是什么 v
  2. 常数项:要在更新的方向走多远 n

 
 

对 (n, v) 做不同的改变就是不同的演算法,但是所有的统称为 iterative optimization approach.

下面会介绍一个特别的 iterative optimization approach.

 
 


 
 

小测验。

 
 


 
 

所以迭代优化要做的事情就是:找一个V,决定一个他要跨多大步出去,就这样一直的更新w,得到最好的w。

 
 

PLA 里面: v 来自于错误的修正,这里是离散的

Logistic regresiion 里面:这个是平滑的,我们能怎么做?

 
 

如图所示,假设我们把一个球放在山坡的某一个地方,让它自然的滚下去,我们知道他最终会停留在谷底,就是最佳解。而现在我们要做的就同样是找一个滚下去的方向来让他到达最佳位置。

 
 


 
 

一开始我们假设v长度是相对固定的1,然后我们想先跨一步最大的,就是能让我们的Ein一下子下降最多的,那么就是向最陡得方向跨一步。

 
 

那么这样的情况下:

仍然是非线性优化,而且还多了个条件,这样再做最佳化感觉上问题反倒变得更难了一些。

 
 

如何他这个问题变得容易呢?

目前我们学到的容易解的问题都是线性的问题,因此我们想办法把问题变成线性的。

我们来看上坡弧线,如果只专注一小段,则可以看作是直线,就是线性。如蓝色框框公式的约等于标识的情况那样,可以约等于 上个位置 + 梯度方向走了一个单位。(泰勒展开)

 
 

所以我们的问题就可以变成一个线性问题。我们要解决的是v在这样一个线性的式子里面取什么值是最好的。

 
 


 
 

所以怎么去求解呢?

上面公式灰色部分表示不是那么的重要,因为是常数而已。因此就变成了 v乘上一个我们已经知道的向量的结果 到底怎么会越小越好。

 
 

完全反方向的时候 值会最小!

所以得到蓝色框内的v的最佳解。

 
 

所以把最好的v代入就会得到w的变化的式子,解释就是从Wt开始向Wt的梯度反方向走一步。

这个方法就是 gradient descent

 
 


 
 

上面确定了我们要走的方向,接下来考虑我们一步要跨多远。

如果走的太小就如左图,慢

如果走的太大就如中图,不准

比较好的如右图,如果坡度比较大夸比较大的步伐,坡度比较小就跨比较小的步伐,比较有道理。

 
 

因此 步长 和坡度 因该是正相关。

 
 


 
 

如果步长和坡度成比例,你会发现原来的式子可以化简。这个方法叫做 fixed learning rate,就是最佳化的n。

 
 

我们最终要用的式子就是 黄色框内的公式

 
 


 
 

所以总结一下 logistic regression 方法:

 
 

从 W0 开始,每一步都是:

先算一下梯度是多少,然后向梯度的方向走紫色的n那么多路;

直到梯度接近为0的时候(或者走了足够的步数)停下,最终的Wn就是目标g。

 
 


 
 

小测验

 
 


 
 

总结:

介绍了 logistic regression,

从他的问题出发,他的问题是 输入是logistic function 输出是 P(1/x)

他的Error是 cross-entropy,如果我们要最小化他的error,我们就需要计算梯度,通过梯度下降的方法一步一步的得到最小的 Ein,就得到目标g。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

Machine Learning Foundations 9: Linear Regression


 
 

内容:

  1. Linear regression 的原理和推导过程,就是求解Ein最小化的解。极其重要!
  2. Linear regression 的理论 Ein/Eout 平均错误是 2(d+1)/N
  3. 证明 linear regression 这个方法可以被用在classification 求解上面,只要其错误衡量是classification的上限

 
 


 
 

上一节我们讲了再前面花力气证明的二元的VC Bound可以扩展用在各种情况下,也包括这里面要讲的linear regression的情况。

 
 

我们来看看演算法上面我们要怎样去设计。

 
 


 
 

回过头来看银行发信用卡的例子。这里考虑的不是银行要不要给顾客发信用卡,而是要给用户发多少额度的信用卡。

 
 

可以继续用前面二元分类使用的learning流程,改动的地方在于学习公式变成了一个输出实数的公式,输出的是给顾客的信用额度数值。

 
 

regression问题的特征就是:输出空间是整个实数。

 
 


 
 

那么我们来考虑到底Hypothesis到底长什么样子输出的才会是实数。

 
 

比如例子:顾客资料分数的加权值 和 给用户的信用额度是需要接近的。

和原来perception的区别在于,原来perception算完分数后为了回答正负的问题,需要取正负号来获得最终的结果,而这里直接算完分数就是一个实数,而regression要得就是实数。

 
 


 
 

如图来表示 linear hypothese:

 
 

如果我们今天输入是一维的话,就如左图,x是一个维度,y就是结果,而衡量标准就是最能fit这些(x,y)的线,找出这线的一个方法就是所有点到线的距离总和最小。

如果是二维输入的话,就如右图,这里我们的衡量标准就是一个平面。

 
 

找出衡量标准这就是 linear regression要做的事情。实际点到预测平面(线or其他)的差就是余数(residuals/误差),这个余数总和尽量是越小越好。

 
 


 
 

那么我们怎么去衡量余数总和到底是小还是不小?

 
 

这个问题就是错误衡量方式,传统做法就是错误的平方和,这样 Ein/Eout的求解公式就会如上图。

 
 

到这边就已经知道了如何去衡量Ein,下一步就是考虑我们如何去使得Ein最小化。

这里大家可以回顾一下1-8课讲的内容,这里的流程完全fit以前讲的流程。

 
 


 
 

小测验。

 
 


 
 

列出Ein的公式,考虑我们怎么样求到一个w,使得Ein最小化。

 
 

WXn:实际的预测是什么样子

Yn:期望的预测会是什么样子

平方就是错误的衡量方式:取错误的平方

1/N:为了化简

 
 

第一步 是 W转置*Xn 变成 Xn转置*W 交换一下,目的只是让大家看得更清楚。

第二步 这是一个连加公式,可以写成向量形式

第三步 化简向量,提出公用的部分W

第四步 红色的部分就是一个X矩阵,紫色部分就是一个y向量,整理一下就是一个简单的式子。

 
 


 
 

上面得到的式子,化简后如上式。

这个式子中唯一的变量就是W,这是一个可微的凸函数!如示意图。

也就是说最低点就是梯度(做微分)值为0!如右边公式。

 
 

所以:我们现在的任务变成了 希望找到一个wi希望其梯度为0.

 
 


 
 

求解:

上面公式中的平方展开,得到三个项命名为:A矩阵, b向量, c常数。

 
 

假设w是一个维度,整个就是一元二次方程式,就可以直接求解,如左边公式。

如果w是一个向量,解就如右边公式(见线性代数的内容)。

 
 

最终要求的梯度就如上面的公式。

 
 


 
 

我们要得就是梯度 = 0

这个式子里面我们唯一不知道的就是w,整个其实就是一元一次方程组。

 
 

也就是说X存在反矩阵就可以直接求解得到w。(实际上大部分情况下X都存在反矩阵,因为只要满足 N 大于等于 d+1 就行,这个基本都满足的。不满足的时候线性代数也能求解,具体不详细说明了,参见pseudo-inverse函数实现。)

 
 


 
 

所以 linear regression 算法总结一下要做的分为三步:

 
 

第一步 通过资料获得两个矩阵;

第二步 从X算 pseudo-inverse矩阵;

第三步 pseudo-inverse矩阵和y乘起来,就是你要回传的权重,就是结果。

 
 


 
 

小测验。

 
 


 
 

上面这个真的是一个机器学习算法么?

 
 

  1. 不是:上面是一个 analytic solution,就是一步就算出结果了,没看到学习过程,没有观察到进步的过程。
  2. 是:有一个好的Ein,保证有好的Eout,看起来是一步登天,实际上算pseudo-inverse的过程就是学习的过程。Pseudo-inverse矩阵运算的时候也是一个高斯收敛的过程。

 
 

只要保证 Eout 是好的,就是学习算法。

 
 


 
 

来说明怎样保证 Eout 是好的,看 Ein 的平均来分析 linear regression 可以work的很好。

 
 

现列出 Ein 平均的公式,计算一下会如上式 (噪声 * (1 – 自由度d+1/资料量N))。

具体推算如蓝色部分,prediction y可以用资料代替掉,就会得到上面的推导结果。

 
 

X * X(serudo-inverse) 叫做帽子矩阵(hat matrix)

 
 


 
 

上面是线性代数的复习,图讲的是:

粉红色:X的各个分量的展开,w的作用就是让x的风量来做所有的组合。

Linear regression 要做的就是 y 和 y_ 差别越小越好,就是y要投影到这个线性空间里面,就是上面的绿色线最小。

H表示的就是投影,I-H 表示的是余数的部分,我们关心的就是余数最小。

 
 

Trace(I – H)[就是I – H结果的对角线的部分] = N – (d + 1)

这个的物理意义:N个自由度的向量投影到d+1维的空间取余数,余数的自由度最多最多就是 N – (d+1)。

 
 


 
 

再来看 Ein 的平均,就可以用上面的推导拿过来,蓝色框内的推导可以那么改写。

也就可以得到黄色的结果。

 
 

类似的 Eout 也可以那么去得到。

 
 


 
 

从上面 Ein / Eout 的式子可以得到 learning curve 图,描述的是我们的资料量和错误率。

 
 

sigma平方就是 noise

平均错误率就是 2倍的(d+1)/N

 
 

这里说的事平均的情况是什么样,以前讨论的VC bound则是考虑的最坏情况,但是结果类似。

 
 

因此学习其实真的已经发生了。

 
 

上面整个部分数学推倒不那么重要,但是其物理意义要理解。

 
 


 
 

小测验。

 
 


 
 

Linear classification

输出是正负,求解比较困难

 
 

Linear regression

输出是实数,很好求解

 
 

正负1也是一种实数,那么能不能直接用linear regression来求解classification?

 
 


 
 

Linear classification/regression 最大的差别在于错误的衡量方式。

 
 

如图所示的例子,左边假设想要1,右边假设想要-1,错误用红色和蓝色线表示.你会发现不管怎么衡量,平方的错误一定比01错误来得大。

 
 


 
 

VC bound 曾经告诉我们:

classification Eout <= classification Ein + …

 
 

上面一页则告诉我们:

Classification Ein <= regression Ein + …

 
 

也就有

Classification Eout <= regression Ein + …

 
 

所以可以回答一开始的问题,可以用linear regression来求解classification,这是对的。

 
 

也可以解释成:

因为 01错误 不好求解,因此换一个 平方错误 作为hat来求解(宽松一点的bound),也可以得到一样的结果,这是对的。【应用up bound】

 
 


 
 

小测验:上面三个都对应很重要的机器学习演算法

 
 


 
 

小结:

 
 

介绍了linear regression演算法。从问题出发:找一个平面或者函数来描述我们所看到的实数的资料是怎么样的;讲了他的演算法,非常简单一步到位得到解析解;我们做了分析得到其平均来说的错误率是2(d+1)/N;最后我们证明了linear regression这个方法可以被用在classification上面,只要其错误衡量是classification的上限。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

Machine Learning Foundations 8: Noise and Error


 
 

如何在有noise的情况衡量错误。

 
 

内容:

再有杂讯的情况下,我们使用probabilistic函数来做描述(就是y由直接公式得到变成了几率分布)。

错误的衡量方式方式是和使用场景强相关的,我们考虑plausible/friendly的方式来挑选。

最后说 weighted classification 的理论。

 
 


 
 

到上一节,我们已经讲完了机器学习最重要的工具Dvc。

如果我们的H集合的Dvc是有限的,我们有足够多的资料,且Ein又很低,那么我们就大概学到了东西。

 
 

这里我们将说的是在原来Dvc推倒的时候设立了一些假设,我们怎么样放宽一些假设让Dvc可以应用到更广泛的机器学习问题中去。

 
 


 
 

以前讲到:

我们有一个 distribuction,由此得到 examples 的 x,未来做测试的时候我们采用的也是同样的 distribuction。

我们有一个 target function,这个target function会产生一堆的 examples 的 y。

我们需要通过这些带有 (x,y) 的资料,在一堆 h集合里面找出好的 h (Ein 很小,且 Ein 等于 Eout)

 
 

在这基础之上我们来考虑noise,会不会对之前的整个理论推到产生影响呢?

 
 


 
 

资料存在 noise 是非常常见的。

举例:银行发信用卡,可能因为用户资料的的填写错误,收集的资料不准确;对于同一个用户申请两次,也有可能因为人为的原因一个发,一个不发。这些都会导致模型产生noise。

 
 


 
 

我们需要看一下 VC bound 在有 noise 的时候还会不会work。

 
 

来考虑 VC bound的核心,我们是从下面的例子引出来的:如果我们要估计罐子里面的弹珠数量,我们可以从里面抓一把,然后通过分析抓出来的来估计罐子里面的结果。

每一颗单株看作是x;从某一个几率p抽出来,我们来看这里通过example得出的预测和目标函数是否一致,不一样就切成橘色,一样就是绿色。

 
 

noise表示的是今天我们存在有些x不满足条件 fx = hx。

因此我们可以引入一种特别的弹珠:颜色会不断的发生变化。但是如果我们从整个罐子来看,橘色和绿色弹珠的比例还是基本保证一个恒定的状态。

我们怎么知道这个比例:做抽样的动作,抽出来记录抽出的瞬间的弹珠颜色。通过记录这个瞬间抽出来的弹珠的颜色比例来估计这个瞬间罐子里面的弹珠颜色比例。

这里就有杂讯的发生:原来是绿色瞬间是橘色,原来是橘色瞬间是绿色。

 
 

既然我们还是同样使用抽样的方式来做估计,那么原来的整个分析过程还是统统可以采用的,VC bound还是work的。区别在于在这里我们不仅仅x是取样来的,y也同样是取样来的。

 
 


 
 

P(y|x) 叫做 target distribuction.也就是说这里不再说目标函数,而是一个目标分布。也就是说我们原来对于 x来说通过函数获得y,这里我们对于每一个x都有一个理想的对应y,但是因为存在的是分布,也就使的这个x可能获得分布中任意的y。

最理想的是y,不理想的是杂讯。

 
 

譬如上面的例子 0.7 表示的是想要的分布情况,但是y落入0.3的时候这个 (x,y)点 就是杂讯。

 
 

另外这个目标分布可以看作是 二分的:


y与目标函数结论一致的时候就是有效数据点,不等的时候就是杂讯。

 
 

所以学习的目标是:

P(x) 告诉你的是哪些点是重要的,值大代表经常会被sample到,Ein里面经常遇到,计算权重大,因此要预测的接近mini target(P(y|x))。

 
 


 
 

因此更新一下learning图:左上角从目标函数替换成了target distribuction,产生的y用来training,我们用同样的distribuction来产生测试数据,来看学到的和产生的一样不一样。

 
 

Pocket 算法: 让Ein 越小越好,就是让Eout越小越好,这个结论还是成立的。

 
 


 
 

小练习:选正确的

 
 


 
 

讲了noise的来历,来看看整个learning里面的最后一步:g约等于f。

 
 

之前g的特性:

  1. Out of sample;这里衡量的数据是这个model来说还没有使用过的数据
  2. pointwise:我们可以在每一个x单独衡量
  3. classification:我们衡量的是对或者不对(0/1分类)

 
 


 
 

很多时候我们所碰到的错误衡量的方式都是pointwise的方式:就是每个点独立的可以衡量。这里用 err 来表示pointwise error measure。

 
 

所以我们的 Ein 就可以标示为上面所示;Eout 也就可以标示为上面的结果。我们衡量的是 g 和 y 差别到底是多少。

 
 

这种错误的衡量方式是最常用的。

 
 


 
 

有哪些pointwaise的方式:

 
 

  1. 已经涉及的:0/1 看对还是错,通常用在classification
  2. Squred error:你今天的预测和目标y的差距的平方,同样用在regression

 
 

未来会涉及到更多的错误衡量方式,我们对错误的衡量会影响到学习。

 
 


 
 

举例子来说明错误的衡量方式会影响到学习过程。

 
 

上面有三个可能的输出,我们分别采用上面讲的两种错误衡量方式,来计算各个可能的y的错误率。左边的例子错误率最小的是2,右边却是1.9。

 
 


 
 

再来看学习的flow里面,我们必须要告诉演算法的是错误衡量方式。

 
 

这里还要说的是:VC的理论和精神,对于不同的h和err来说,都会work。

VC bound 理论是非常非常的通用的。

 
 


 
 

练习

 
 


 
 

这里呢我们采用一个例子来和大家说怎样去选择错误衡量方式。

 
 

要做一个指纹辨识的问题:正负1表示是不是你的指纹。

 
 

分类器可能会犯两种不同的错误:

  1. False accept:你应该不可以用,但是电脑判断你可以用。
  2. False reject:你应该可以用,但是电脑判断你不可以用。

 
 

如果只采用第一种简单的 0/1 判断错误的方式,这两种错误是一样的。

 
 


 
 

但是实际应用场景,例如超市会员的识别,如果一个顾客是会员但是识别不出来导致没有折扣,这是一个很大的损失;另外如果一个顾客不是会员但是给了折扣,这是一个不大的损失。

 
 

因此还需要存在一个成本表来衡量错误的严重性,付出的代价是多少。

 
 


 
 

再举个例子如果是 CIA 判断某个员工能不能进入机密系统,那么他的成本表会完全不一样。

 
 


 
 

所以错误衡量方式是基于应用场景的

 
 

在我们设计演算法的时候我们要考虑错误衡量方式,但是这个不容易做。譬如CIA那个1000倍是如何衡量出来的,很难有理论依据,也没有人会告诉你到底应该是多少。

 
 

因此选择的原则可以是:

 
 

plausible(考虑原因来说服自己):

  1. 找一些有意义的衡量方式,譬如01对错判断
  2. 相信noise是高斯分布,采用平方衡量法

 
 

friendly(为了比较好优化算法的错误衡量方式):

  1. 算解容易
  2. 凸的

 
 


 
 

修正一下图,原来的err变成了 err上划线,表示的是经过人为考虑依据使用场景优化的err。

 
 


 
 

小测验

 
 


 
 

不同的错误有不同的重要性,因此带来了带权重的classification。

引入 Cost Matrix/Error Matrix/Loss Matrix(成本矩阵)

 
 

这里使用上面CIA的例子,列出其Ein/Eout,原来的错误计算公式+权重。

 
 


 
 

我们怎么求解这样的问题。VC任然可以用,也就是说我们要考虑的是Ein要最小,因此我们来看Ein。

 
 

这个时候来看:

  1. PLA:不用管权重直接跑也就有结果
  2. pocket:如果今天找到的比我口袋里的还好,就换掉口袋里的。这里比好坏使用的是加权错误。

    那是不是这样做就好了?

    pocket原来理论上的保证是可以让Ein(01)最好,今天换成带权重的还能保证吗?

 
 


 
 

这里讲我们怎么样修改pocket演算法,来得到和原来的pocket一样有类似的保证。

 
 

要让Win(w)和Ein(01)扯上关系:

我们可以考虑的是一个一个考虑资料,如果是正的我们不做修正,如果资料是负的我们复制1000倍,这样我们就得到了新的数据资料库。

那么对于这个新的数据库,如果其中一个负的点犯错误,就会发生1000个点犯错误的情况,但对于每个资料来说就不存在权重的问题,也就是等于原来的权重的表示。任何一个负的资料都会是这样。

就是说 新的资料的Ein(01) = 旧的资料的Ein(w),也就是说带权重的pocket演算法也是可以保证的。

 
 


 
 

因此你就可以得到 weighted pocket 算法。这里比起pocket算法来说需要做的修改是:

  1. 使用 Ein(w) 来做错误检查
  2. 拜访权重高的点的几率要增加,对应资料复制n次

 
 

Systematic route: 系统的将方法做延伸扩展。

 
 


 
 

小测验

 
 


 
 

总结:

再有杂讯的情况下,我们使用probabilistic函数来做描述(就是y由直接公式得到变成了几率分布)。

错误的衡量方式方式是和使用场景强相关的,我们考虑plausible/friendly的方式来挑选。

最后说 weighted classification 的理论。

 
 

到此机器学习理论部分结束,接下来讲机器学习算法。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

Machine Learning Foundations 7: The VC Dimension


 
 

介绍Dvc是什么:最大的non break point。

从 perception 上来说就正好是 d+1。

从物理意义上来说就是有多少个自由度。

Dvc可以用来决定我们大概需要多少资料,让你不需要再去考虑H的细节,一个变量就决定了其性质。

 
 


 
 

上节课讲过的:我们可以确保我们的Ein(训练时的表现)和Eout(测试的时候的表现)一致,当我们的成长函数露出一线曙光且资料量足够大。

 
 

从这里触发我们可以引入 VC 维度的概念。

 
 


 
 

如果我们的成长函数在K处露出一线曙光,这个成长函数会被某个上限函数bound住,这个上限函数又会被某个多项式bound住,这个多项式的次方是K-1次方。

 
 

我们把上限函数的表格列出来,然后再把N的k-1次方列出来,我们来做比较。当N,K比较大的时候(这里N>2,K>3的时候),我们发现 N的K-1 次方就已经比我们的上限函数都大了,也就是说比我们的成长函数来得大。

 
 

因此我们就可以得到 我们的成长函数 会被 N的K-1次方 bound住。就化简了多项式。

 
 


 
 

上一节课证明的是:如果在我的H集合里面有任何一个h发生坏事情,这件事的几率很小很小,小的边界是:


 
 

这个结论的意义是,既然我们保证了大部分的时候都不会有坏的事情发生,也就是说我们的演算法被bound的情况下做的选择,这时候做出的选择g,这个g的Ein,Eout离得很远的几率也很小很小。

 
 

然后我们将上面的成长函数里面的 m 也可以替换成 N的K-1次方,如上面的式子的结论。这个替换的要求是N,k够大,原来的推倒的条件是N够大,这里更加严格要求k也要够大。

 
 

结论:所以下面两个条件让我们可以做机器学习:

  1. 我们要有一个好的h,就是他的成长函数要在某个地方存在一线曙光
  2. 我们要有一个好的data,就是说数据量够大

这样我们就可以说:训练的表现和未来测试的表现会是一致的,也就是可以机器学习。

这个时候如果配合一个好的演算法,能够选出一个g使得Ein很小的话,那就是学到东西了。

最后以上都是绝大几率的情况,不能做出完全的保证,应此还需要一点点运气。

 
 


 
 

VC 维度是什么?

 
 

我们试图给 break point 一个正式的名称,在这里我们真正标记的是最大的 non-break point。

VC 维度是:到这个点(维度)为止都是可以shatter的,超过这个点(维度)就是不能够shatter的,就是露出一线曙光的。

 
 

符号代表: Dvc = 最小的 breakpoint – 1。

不存在就是无限大。

 
 

N <= Dvc 表示有可能shatter,也就是存在某个资料会被shatter

k > Dvc 表示一定不能被shatter

 
 

符号换一下就可以说:

当N够大,Dvc也够大的时候,我们的成长函数比N的Dvc次方来的小。

 
 


 
 

再来看一下以前的例子怎么说。

 
 

所以:什么是好的h,就是露出一线曙光的h,也就是Dvc是有限的的时候。

 
 


 
 

那我们来看一下如果是一个好的h的时候,到底有什么好事。

好事就是 Ein/Eout 接近,且这个结论和演算法无关,和我们的资料的生成模型无关,和我们的目标f长什么样也没关系。

也就是说在最坏最坏的情况下我们都能确保Ein.Eout是非常接近的。

 
 


 
 

小练习。

 
 


 
 

有了上面的理论基础,我们重新回头来看我们讲过的第一种机器学习的方法:二维的PLA。我们来对应理论来分析一下这个算法。

 
 

资料线性可分PLA才可行,也就是说Ein=0。

资料都是从某个目标函数产生的,那就可以确保 Ein,Eout 有很大机会接近。

最后可以得到Eout接近0,也就是说这个演算法可用。

 
 

那接下来我们考虑在多维度的时候,这演算法还好不好用。

 
 


 
 

我们来分析如果今天是多维度的话,Dvc会是多少。

例子:

1维的时候,Dvc是2

2维的时候,Dvc是3

d维的时候,Dvc是d+1?

 
 

我们如何来证明 d维的时候就是 d+1,那就同时要满足下面两个条件,就可以满足:

Dvc <= d+1

Dvc >= d+1

 
 


 
 

先来个小练习

任意d+1笔资料都要能够shatter

 
 


 
 

首先来举一个特别的例子。

一共 d+1 笔资料,第一笔是原点,第二笔是在第一个维度有一个分量,第三笔是在第二个维度有一个分量。其他的都是0,以此类推,d 维度总共有 d + 1 笔资料。

把所有的资料排列成一个矩阵,矩阵最左边一列都是1,就是我们塞进去的 x0,第0个维度那个常数thershold所代表的资料。

 
 

譬如如果今天是二维,这个矩阵就包含原点,10这个点,01这个点三笔数据,这三个点是可以被shatter的。

我们要证明的是在d维度,这个矩阵我们也是可以被shatter的。

 
 

在数学上这个矩阵是存在反矩阵的,而且是唯一的。

 
 


 
 

要可以shatter,就意味着我们给任意一种排列组合y(任意一组ooxx组合),我们都能够做到 X乘上w等于正负y。

由于反矩阵的存在,也就是说如果 X乘上w等于负y,就可以有 X的-1次方乘上y等于w,用这个新的w,就有 X乘上新的w等于y 的存在。就是说我shatter了这一组y。

 
 

因此在这一组特别的资料上任意一组y都可以得到这个结论,所以这里就有 Dvc >= d+1 成立。

 
 


 
 

小练习。

任意D=2笔资料我们都不能够shatter。

 
 


 
 

我们要证明所有可能性比较麻烦,这里先回到上面的例子。在上面的基础上再加一笔资料来处理。

 
 

这里首先举一个2笔资料的情况,我们穷举就会有四种情况(00,10,01,11)。那么如图如果上下脚是oo,左下角是x的话,问号的那个点是x的话是不行的。

 
 

公式表示来解释:

因为有线性依赖的关系就可以得到


每项都乘上w以后也是相等的,就得到上面的情况。

蓝色红色各自對應,就会有


也就是说 wx4 这一项是大于0的,就是o,不可能是x。

 
 

也就解释了不能是oxox的情况。

 
 

结论就是:如果今天我们把x4表示成其他三个的线性组合,那么这个线性依赖的关系就会限制我们产生dichotomies的数量。

 
 


 
 

上面是特例,这里考虑d+2笔资料的情况。列出d+2笔的公式如上面,因为存在线性依赖就可以这么表示,每一项的正负号标识的ox。

 
 

我们考虑 d+1 的情况,都已经确定,也就是有


这个项存在正负号,也就决定了d+2这个项的符号是正还是负。也就是说我们没办法产生所有的dichotomies。也就是说任意的 d+2 个点我们都没有办法shatter。也就是证明了 Dvc <= d+1。

 
 


 
 

练习。

 
 


 
 

从上面就可以发现维度的重要性,h的参数可以用w的数量来表示,表示有多少自由度,每个自由度都可以自由调整。

 
 

VC 维度的物理意义就是 hypothiese自由度的维度。

 
 


 
 

举个例子:

positive ray的时候,我们有一个自由度可以调整。

Positive interval的时候,我们有两个自由度。

 
 

Dvc 的物理概念大概是:hypothiese的自由度。

 
 


 
 

我们回过头来看 learning 里面的两个关键问题:

  1. Ein,Eout是否接近。
  2. Ein是否够小。

 
 

以前我们用M来衡量:

M不太大的话对于第一个问题来说很好;M很大的时候对于第二个问题来说是好的。

 
 

现在我们用Dvc来衡量:

如果Dvc很小:对第一个问题很好,自由度小,坏事情几率小

如果Dvc很大:对第二个问题很好,自由度高,坏事情发生几率变大

 
 

因此我们再来看h的时候,Dvc就是我们要关注的h的性质。

 
 


 
 

小测验。

过原点的线性分割,去掉了w0,所以是d

 
 


 
 

我们再继续深入了解Dvc的意义。

首先我们用Dvc来更新一下 vc bound 的公式,得到如上面的写法,公示右边的项很小很小,我们用delta来表示。

 
 

坏事情发生的机会很小,也就是好事情发生的机会很大,也就是 1 – delta 的可能性。通过如上面的推导,我们可以得到:有很高的机会,Ein/Eout的差别会限制在e这个数值内。

 
 

 
 


 
 

这样进一步整理这个公式,就可以得到Eout的范围会被限制在两个范围内,见上式。在统计上就可以看作是置信区间。

 
 

注意:

左边的部分标做灰色,因为通常我们不大重视这部分;右边部分表示的是Eout最糟糕的情况会是怎样,这个我们比较重视。

根号里面的部分我们叫做model complexity。就是用来表示的意义是我们的 hypothiese 到底有多么的powerful。用大写的omgia来表示(三个变量:N表示多少个点,H表示Dvc是多少,dltea表示你觉得你有多幸运)。

 
 


 
 

VC 告诉我们的事情就是 有很高的几率Eout <= Ein + omega

 
 

也就是说我们可以用上面的图来表示,横轴Dvc,纵轴Error,趋势是Dvc变大的时候,Ein变小,omega变大,Eout是一个山谷型,最好的Ein会在中间。我们在未来会利用这个图来想办法设计更好的机器学习演算法。

 
 

这类也可以看出强大的h也不一定是最好的选择,因为你会付出更高的modelcomplexity的代价。因此我们不是要把Ein做到最低就好,而是要考虑在h的付出成本。

这一点非常重要,是机器学习算法设计的重要考虑因素。

 
 


 
 

VC bound 还包含另外一层意思就是样本的复杂度。

举例解释:你的老板想要的是Ein、Eout差最多0.1,我希望坏事情发生的机会最多10%,learning model的Dvc是3,那么我们需要多少资料才够?

我们先来试如果你采用100笔资料,这样你带入公式算一下会发现bound达到10的7次方,1000笔资料,10000笔资料的结果如上面所示,如果是100000笔资料的化,就会变得非常小,这样才算是真的学到东西了。

而这个满足上面所描述的规格,代入公式差不多会发现需要29300笔资料就可以满足要求。

 
 

你会发现需要的资料量理论上大概是 10000倍的Dvc 这么多。 但事实上确实不需要那么多,大概 10倍的Dvc 就够了。

这边就是说明了这个VC bound是非常宽松的。

 
 


 
 

宽松的来源是:

  1. Hoeffding 对于任何的分布,任何的目标函数都可以确保满足这个结论。
  2. 采用 mh(成长函数) 来替代 H,就是说我们可以采用里面的任何的资料集都满足这个结论。
  3. 用一个多项式来替代 mh(成长函数),这里取的是上限的上限的上限,这样使得我们只需要看Dvc就可以知道能不能机器学习,不用去管H的细节。
  4. 我们对于最差的状况采用了union bound,也就是说我们考虑最差的情况,但事实上我们没那么容易踩到最差的状况。

 
 

这边就解释了为什么理论上需要那么多资料。

 
 


 
 

练习

怎么减少坏事情发生的机会。

 
 


 
 

总结:

介绍Dvc是什么:最大的non break point。从 perception 上来说就正好是 d+1。从物理意义上来说就是有多少个自由度。Dvc可以用来决定我们大概需要多少资料。

 
 

这里只是说资料从某个distribuction出来经过某个目标函数,没考虑noise,只能对于binary classification。下一节我们尝试延伸Dvc的概念到不同的learning问题上面。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

Machine Learning Foundations 6: Theory of Generalization


 
 

一般化理论:机器是如何做到举一反三的

 
 

内容:

只要你有一个breakpoint,他其实是对未来每一个的数量都加上了很大的限制,也就是上面公式的数学归纳法,最后可以得到上限可以用一个多项式来表示,这个多项式可以取代原来公式中的M,从而证明2维情况下有了一个breakpoint一定是可以学习的。

 
 


 
 

上一节讲到:

因为M无限大的时候没有办法做机器学习,因此提出了成长函数m来取代M。

 
 

这里将探讨两个问题:

  1. 这个m到底是不是长得很慢
  2. 这个m如果真的长得很慢,那到底其能不能取代M

 
 


 
 

首先回顾一下m的定义:

这个有 N 个资料的 h 到底最多能有多少个 dichotomies(二分)

Break point就是第一个小于 2 的 N 次方个 dichotomies 的地方

 
 

再是四个上次的举例的情况回顾。

 
 

上次讲的一个非常重要的知识点就是:当k是breakpoint的时候,K + … 都是breakpoint。

 
 


 
 

假设:

我有一个hypotheses,他最小的breakpoint在2的地方。意思就是任意取h中两个点都不存在完整的四种情况(oo/ox/xo/xx)。

 
 

也就是说:

如果 N=1,m 一定等于 2(o/x),也就是说如果今天只有一个点一定有两种 dichotomies。

如果 N=2,因为breakpoint在2的地方,因此 m 就需要小于4,也就是说最多会是三个 dichotomies(oo/xx/ox/xo 任选3个)

 
 

如果 N=3(三个点),产生一种 dichotomy, 如下图的情况就是。这时候 breakpoint 也是在 k=2,也就是说随便找两个点,你都不能够产生四种不同的二分情况。也就是满足上面的假设最小的breakpoint在k=2。

 
 

看图理解:随便找两个点就是竖着选两行,这两行是否存在(oo,ox,xo,xx)。

 
 


 
 

如图,如果是两个 dichotomies。同样没有四种情况

 
 


 
 

三个 dichotomies 的情况:没有四种情况

 
 


 
 

四个 dichotomies,例如如图所示的情况。

 
 

如果看 x2,x3 上面,你就会发现存在四种情况了。这就和我们的假设,任何两个点都不存在四种情况(2的N次方)存在冲突。

因此不能加进这种情况。

 
 


 
 

因此我们回到原来的三种的情况,再加入另外的第四个,就符合假设(任意取两个点都不存在完整的四种情况)

 
 


 
 

如果是五个 dichotomies 的情况,如图所示,看x1,x3 就不符合假设。

 
 


 
 

五个的情况再换一个,一样不行。

 
 


 
 

再换一个,也不行。

 
 


 
 

经过一番尝试你会发现,在坚持假设的前提下,四个dichotomies就是极限,第五个dichotomies是加不进来的。

 
 


 
 

所以总结一下 N=3 的情况,最多最多就是4种,然后你会发现4和2的三次方已经差了很多了。

 
 

因此这边可以作如下猜想:

如果mh的最多可能性是小于一个多项式表示的,那么,mh本身也就是一个多项式级别的递增而已。

 
 


 
 

小练习

你假设的条件是一个都不能不一样,对于每一列,那么一定是最多只能有一种情况。

 
 


 
 

有了上面一小节追踪的概念,我们来为这个下一个定义。

 
 

Bounding function:我们有一个成长函数,这个成长函数的breakpoint在k的位置,你告诉我这个成长函数最多最多有多少种dichotomies。

 
 

换句话说:我不想要管我的成长函数到底长什么样子,而关心的是在排列组合上我到底能做出多少种排列组合。

在换句话说:我有一堆的向量由ooxx组成的,长度是N;但是我做出一个限制:对于这些向量我只看他其中K个维度(K列)都不希望看到满情形(2的k次方种情况)。

 
 

因此有了 bounding function的性质,我们就可以替代成长函数的作用;因此我们需要证明的是这个bounding function是一个多项式成长的。

 
 


 
 

我们来看这个 bounding function,有两个参数,一个是N(有几个点),一个是k(breakpoint位置)。

 
 

我们已知的两个加进表格。

 
 


 
 

再来考虑 k=1,这也是知道的。

 
 


 
 

我们还可以填充表的右上半部分:当N比K还来得小的时候,你最多产生的是2的N次方种。

 
 


 
 

再看一下 N=K 的情况:其中k=1/2 已知,得出的理由是不能是全部,因此就是满选择减去一种(2的N次方-1),同样的道理可以填充所有的其他k的情况。

 
 


 
 

先来个小练习

这里想说的是bounding function是上限,不一定有等号的发生。

 
 


 
 

我们接下来就要开始填表中比较困难的部分。

 
 

譬如我们开始填表中B(4,3),来考虑它与前面已知的关系。想办法让B(4,x)与B(3,x)建立联系来解。

 
 


 
 

来程式化解决这个问题:

搜寻所有种可能性16种,然后在里面选,一个个加进去看是否符合假设,符合加入,不符合不加入。做法和前面的人工解释B(3,2)一样。

结果会如上面的左图,最多可以是11种情况,可以填入表中。

 
 

又有了更多的一种情况,再去分析表中B(4,x)与B(3,x)的关系

 
 


 
 

我们把这个B(4,x)的解做一个整理:

橘色的解是成双成对的;紫色的是形单影只的。

 
 


 
 

B(4,3)就是这两部分相加,分别用 alpha/beta表示。

 
 

如果我们只看x1,x2,x3的话,我们得到的情况如上面左图:原来成双成对的减半算成一个了,原来形单影只的还在。

 
 

再有假设:B(4,3)的意思就是任何的三个点都不能满选择。

也就是说这里上面左图的 alpha+beta 也不能满选择,也就是说 alpha + neta <= B(3,3)。

 
 

这里得到第一个 B(4,x) 和 B(3,x) 的关系。

 
 


 
 

我们再来考虑:只看橘色的部分的x1,x2,x3,不管紫色的部分。

 
 

(shatter的意思就是满选择,符合2的N次方的情况)

 
 

Alpha 部分 x1,x2,x3 如果 shatter 那么就是不符合条件,因此 B(4,3) no shatter 意味着 B(3,2) 也因该是 no shatter。

 
 

因此获得第二个相关关系条件: alpha < B(3,2)

 
 


 
 

整理起来得到的结论就是 B(4,3) <= B(3,3) + B(3,2)

 
 


 
 

再推到 N,k 的情况也符合: B(N,k) <= B(N-1,k) + B(N-1, k-1)

 
 

也就是说可以把表填满了,填的是上限。

也就是说我们知道了bounding function的上限。

 
 


 
 

有了上面的这些,我们就可以证明一件事情:B(N,k) <= 上限的上限组合多项式

 
 

上限的上限组合 的最高项就是 N的k-1次方。

证明的方式就是表格和上面的推导公式,数学归纳法。

 
 

因此就得到了我们的预期:B(N,k) 一定是一个多项式级别的递增。

 
 


 
 

然后再检查一下以前的例子是否符合现在的结论。

 
 


 
 

小练习

 
 


 
 

好有了成长函数,我们来考虑能不能把其上限函数丢到原来的公式里面,然后事情就解决了。

然而没有那么简单。

 
 

我们能得到的是青色公式。这个证明非常复杂,这里我们不来推导怎么证明,只来和大家解释原理和常数的来源。证明当中的一下技巧很值得学习,得到了这些常数。

 
 


 
 

证明有三个步骤,第一个步骤:

 
 

我们有兴趣的是坏事发生的几率,一堆h里面只要有一个不满足条件就是不好的。

Ein 是有限多个,Eout还是无限多个。因此我们不能直接使用上面的公式,我们需要把Eout也变成有限多个。

我们采用一个数据集D’来验证估计结果,D’也可以得到一个估计结果Ein’,我们看能不能让Ein’来取代Eout。

这是可以的

我们来看有右边图解:Ein好的都在Eout周围,坏的Ein远离Eout。现在我们求出的Ein如果验证的时候Ein’原理Ein,也可以看作是不好的,相反如果很近就是好的。

 
 

换掉Eout后就得到最上面的公式。

 
 


 
 

Ein属于D,Ein’属于D’。也就是说如果我的h在D,D’上面的结果好,Ein,Ein’就会很近,也就是说我们可以在H里面挑好的h了。

 
 

右边的图解讲的是:分门别类(以前讲过)

你使用untion bound每次会有一个错误,当你不考虑重叠的时候,你会觉得像中间的图一样到处是问题,但是你考虑顶点归类后其实如最右边的图。

 
 

这里就引入了mh(2N)

 
 


 
 

现在我们就有了一个固定的h,然后想知道两次sampling的差别。

 
 

也就是说我们抓2N个出来,然后比较差别,通过hoeffding。

 
 


 
 

总结来说我们证明了一个定理: Vapnik-Chervonenkis(VC) bound

 
 

整理一下上面的那些参数也就出来了。

 
 

到此,我们解决了2D的perceptrons的证明。还没有证明的是任意维度的perceptrons。

 
 


 
 

小练习

这里要说明的是,这里花了大力气来推导出的bound并不是那么的准的,如何做下一步的改进,请看下一堂课的内容。

 
 


 
 

小结:

只要你有一个breakpoint,他其实是对未来每一个的数量都加上了很大的限制,也就是上面公式的数学归纳法,最后可以得到上限可以用一个多项式来表示,这个多项式可以取代原来公式中的M,从而证明2维情况下有了一个breakpoint一定是可以学习的。

 
 

下节课我们继续来探讨breakpoint。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

Machine Learning Foundations 5: Training versus Testing


 
 

训练和测试过程:

 
 

首先把learning拆解成两个问题: Ein/Eout相似;Ein约等于0

然后考虑合并M的情况能有几种,也就是成长函数 growth function

再考虑成长函数的性质,到底从哪里开始出现曙光,就是break point

 
 

 
 


 
 

上一节讲到在一定条件下机器学习是可行的。

这里开始探讨无限大的 h 会造成什么样的问题。

 
 


 
 

当前的learning的整个流程图:

学习算法透过学习资料和g,通过前面的概率理论基础选择一个h。

上一节加上了两个条件:

  1. 训练资料和测试方法都来自同样的足够大的资料集,保证Ein、Eout相似
  2. 选一个Ein最小的h就可以得到一个Eout最接近0的最好结果

即可达到学习的效果。

 
 

上面12分别解释一下其实就是:

  1. 让Ein 接近0,让结果符合当前资料
  2. 让Ein 接近 Eout,让结果符合未知的资料,测试更准确

 
 


 
 

回顾一下过去四堂课学的内容

  1. 我们的数据符合的是位置的规则f,我们的盐酸法希望找出的是g,两者接近。也就是Eout(g)接近0。
  2. 我们从已有的资料可以让 Ein(g) 接近0。
  3. 我们是在一个很特定的情况下去做机器学习,就是有哪些学习类别。
  4. 处理Ein/Eout的关系:Eout 接近 Ein 最好

     
     

这里是回过头来理一遍得出上面的相同的结论的过程。

 
 

这里我们是把learning的核心问题拆解成了两个问题:

  1. 到底Ein/Eout接近不接近
  2. 怎么让Ein变得越小越好

 
 

我们再来看 H(M) 就是 所有h的集合 的重要性。

 
 


 
 

M 的两种可能性是否能满足上面的两个核心问题:

  1. M 数字比较大:坏事情发生的几率增加了,不能保证Ein/Eout相似,有足够选择能有一个Ein=0。
  2. M 数字比较小:Ein/Eout可以很接近,Ein的选择很有限,不一定能有一个可以接近0。

 
 

这里看出了 M 的重要性,选择正确的 M 和学习结果有很大关系。

无限大的M根本不好learning。

 
 


 
 

所以到这里问题是:我们要想办法解决无限大的M的问题,选择一个合适的有限大的M解决问题。

 
 

我们要把无限大的M换成一个有限大的m来解决learning的问题。如果可以换,则可以通过有限的m来解决无限M的问题。

 
 

如果能换,按上一节理论就有可能可以做机器学习。

 
 


 
 

先来个小练习。

 
 


 
 

我们首先要回答的是为啥 M 无限大的时候,没办法learning。

 
 

推导:

我们有一堆不好的事情(Ein/Eout差距太大);

我们今天有非常多的h,通过上一节讲的方法,对于一个h把所有的会发生不好的情况的几率级联起来。

问题在于: 几率的级联 小于等于 各个独立几率相加

当M无线大且有很多不好的事情的情况下,右边部分很多项不是0,则加起来的总和很有可能是无限大。这样这个上限就没有任何意义。

 
 

这个上限的

 
 


 
 

我们来看看这个上限出了什么问题:

 
 

以前我们可以使用这个上限的原因是坏事情不会重叠。1好h发生坏事情的dataset和2号h发生坏事情的dataset是不一样的dataset。

 
 

但是这件事情不大对吧。

如果存在两个很接近的h的dataset,则:Eout(h1)和Eout(h2)就很会接近,Ein(h1)=Eout(h2),也就是说发生坏事情dataset可能长成上图那样,会有很大的重叠。

我们前面在做这个上限的时候没有考虑这个叠加的情况,这样就会造成我们的上显示 over estimate,就造成了我们没有办法处理无限大的M。

 
 

所以我们要找出这些重叠的部分。

做法是看能不能把无线多的h分成有限多类,每一类里面是长得差不多像的。

 
 

下面我们讨论怎么样来对h归类。

 
 


 
 

举个例子:

考虑平面上的分割线,有无限多条。

 
 


 
 

只有一笔资料,则如果从这笔资料看出去的话,只有两种线,说这资料是正1,说这个资料是负1。

 
 



再来考虑俩个点的情况,对于两个点整体来说就有四种线。

 
 


 
 


 
 

对于三个资料,则有8种情况。

 
 


 
 

但是如果三个资料在同一直线上,则如果线性可分的化,就只有6种情况。

 
 


 
 

对于四笔资料的情况,也要注意非线性可分的情况要去掉。

 
 


 
 

因此,我们如果只从资料点看出去的话,得到的划分情况是有限的。

 
 

注意点:对于N个资料点

是小于等于2的N次方,因为要去掉非线性可分的情况。

最好是比2的N次方小很多,则原来公示里面的无限大的 M 可以被有限大的数值取代掉,当N够大的时候,整个就接近0。也就是说基本上都是好事。

 
 

条件:这个有限数字要比2的N次方小很多。

以后会证明。

 
 


 
 

小练习 22 种情况。

 
 


 
 

前面讲的是在平面上用线区分,那么对于高纬度的区分方法,我们怎么来确定到底有几种区分情况。

 
 

一个hypotheses到底可以做出多少种dichotomy?

Dichotomy: 二分

 
 

我们把h用在N个点上,用 h(x1…xn) 表示,代表的是 Dichotomy,不是 hypotheses。

两者的区别见上面的表格:主要是将无限多变成了有限多。

 
 

我们接下来会用 Dichotomy 的大小来换掉M。

 
 


 
 

Dichotomy 的大小取决于预先选好的 x1, x2 … xn,作为理论分析最好移除掉对这个预设的依赖,因此我们算最多有多少种。

也就是说我们有各式各样x的可能性,我选最大的dichotomy的大小,用mh来表示。

mh在上面平面的例子就是最多情况的那个数值。

 
 

这里给mh取个名字叫 growth function,这个值一定是有限的,最大就是2的N次方。

 
 

那我们考虑下到底能不能真的把函数数值公式写出来呢?

 
 


 
 

先看一个简单的hypothese:positive rays。

 
 

我们的输入就是一维的实数

我取某一个门槛值来区分正负1,任意一个hypothese(门槛值)结果就不一样

 
 

那么用这个hypotheses,我给你N个点可以切处多少种不一样的dichotomy。

N个点都不一样的情况切出的数量最多,最多就是N+1种。

也就是成长函数的长相: mh = N + 1

 
 

注意 N+1 远远小于 2的N次方

 
 


 
 

再看一个例子: positive intervals

某一个范围内正1,其余都为负1.

 
 

同样这样子的成长函数可以直接计算出来,如上图。

 
 

同样注意: 这个成长函数比2的n次方小很多。

 
 


 
 

再来一个例子:conves sets

凸的几何体内是正的,其余为负的

 
 


 
 

把所有的输入排在一个圆圈边上,这样保证凸,就很容易区分。

 
 

因此这个成长函数是 2的N次方。

 
 


 
 

小练习

 
 


 
 

上面讲了四个不同的成长函数。

上面也讲了我们原来想要的是用成长函数去取代原来的无限大的M

 
 

看式子右边如果成长函数小到不再是指数,当N足够大,则可以确保这个式子就会约等于0。

所以上面的例子前两个可以保证这个式子约等于0,后面两个不行。

 
 

因此重点是确认成长函数到底是多项式形式还是指数形式。

 
 


 
 

我们想要找出这个成长函数中第一个看起来很有希望的点在哪里。这样的点叫做 break point。

 
 

举例子1中:

三个点8种情况,四个点最多小于16种情况,也就是从四个点开始漏出了小于2的n次方的一线希望,这时候叫做break point。

 
 

找到第一个 break point,后面的也就统统都是 break point

 
 

 
 


 
 

因此原来的四个例子的break point在哪里,紫色字体就是答案。

 
 

通过上面的观察

会有猜想:

没有 break point 的时候一定是指数形式。

有 break point 的时候我们的成长函数的速度大概和N的k-1次方有关。

 
 

下一课的重点就是来证明。

 
 


 
 

小练习

 
 


 
 

小结:

首先把learning拆解成两个问题: Ein/Eout相似;Ein约等于0

然后考虑合并M的情况能有几种,也就是成长函数

再考虑成长函数的性质,到底从哪里开始出现曙光,就是break point

 
 

下一次课就是要来证明是不是有break point的时候,成长函数就和一个多项式差不多,远小于指数结果。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

Machine Learning Foundations 4: Feasibility of Learning

 
 


 
 

这里探讨的是:机器学习是否是可行的

 
 

一开始说机器学习做不到

但是加上一些统计上的假设,譬如资料的产生方式,表现衡量方法,就可以做推论做验证,就是机器学习。

 
 


 
 

上一节主要说的是机器学习的分类

这一节首先说什么情况下机器学习做不到,在做不到情况下怎样处理可以变的做得到。

 
 


 
 

首先看个小问题:

 
 

上面三张属于 -1 类,下面三张属于 +1 类

则下面的你会判断属于哪一类

 
 


 
 

答案是非常多的,根据不同的分类方式得到的结果是不同的。

 
 


 
 

再来一个例子:

 
 

输入是一个三个维度的向量,输出还是正负1

然后给了你5笔资料,则g会是怎样的?

 
 

做法可以是:

列出所有的可能性,然后标注5比资料,然后找一条线来区分资料。(类PLA算法)

 
 


 
 

你会发现符合5个资料的结果非常多,用他们再用来预测其他,结果会完全不一样。

 
 

想一下你会发现:

我们想要的不是把已知的都答对,而是对于未来的结果答对的最多。

我们如果不增加假设上面的问题就无法用机器学习解决

 
 


 
 

益智问题

 
 


 
 

答案:4

无答案

 
 


 
 

现在我们有个问题了,就是上面的问题机器学习做不到

 
 

因此我们现在要考虑的是:我们怎么去做推论

 
 

例如图:

有一堆弹珠,想知道里面的橘色弹珠比例占多少?

 
 


 
 

方法:

随机的抓一把弹珠,数一下看比例,就大概是罐子里橘色弹珠的比例。(推论)

 
 

所有数据 》 取样 》 样本结果v 》 数据结果u

 
 


 
 

U != V, 但是大概率情况下两者接近

 
 

接下来看数学表示:

 
 


 
 

定理: uv差距大于e的可能性很小

(具体可以见概率论)

 
 


 
 

右边这项与u无关,因此这个定理与我们不知道的假设无关,以保证准确

e设的大一点,右边的几率就更小

因此样本e够大的话,可以做出推论,uv基本类似

 
 


 
 

计算题

 
 


 
 

答案是 3

 
 


 
 

弹珠事件模型

  1. 不知道的橘色的真正占比 – 函数表示就是f,预测h是否与f一样
  2. 一堆弹珠(橘色弹珠,绿色弹珠)
  3. 做抽样

 

对应到 机器学习模型

  1. 目标f就是橘色真正占比,我们不知道,因此取值到某个x点上面。今天新来一个顾客,我们定义h来预测新来的这个的结果是不是橘色,看是否正确。
  2. 弹珠x,在这个x上面,h是否等于f,一样就是橘色,不一样就是绿色。我们就可以通过这个规则来标识弹珠。要做到这一点我们首先需要有一个固定的h。

    换句话说就是:我们手上有一个固定的预测函数h,就可以把任一弹珠x预测结果是橘色还是绿色。

    这样做的好处是:今天如果我们抓了100个球,就会有100次判断结果。

    这样就和我们的已有资料对应起来:我们已知的部分弹珠的结果加上正确的标记。

    这样就可以检查h的预测结果对不对。

 
 

结论:

如果我们的资料量够大,就相当于我们抓了一把够大的弹珠,

如果我们所有资料的x是独立的从某个地方取样出来,就相当于我们独立的从罐子里抽弹珠

那么我们大概可以说整体的h,f不一样的几率是多少,就相当于整个罐子里面h,f不一样的几率是多少。不仅仅是看得到的样本。

 
 


 
 

我们有一个几率来做从罐子里面取样,这个取样会用在两个地方:

  1. 取样产生了我们的资料
  2. 我们用这个同样的几率来衡量hf的相似程度

h就是从整个H里面的一个样本,然后我们就可以使用我们手上的资料来看hf是否一样。

 
 

Eout 就是来衡量 hf 在整个罐子里面到底一不一样

Ein 就是说在已有的sample上面 hf一不一样

 
 


 
 

这样原来的几率衡量公式可以改写成Eout、Ein的形式

 
 

说明:

这个公式对个个例子都是对的

我们不需要知道Eout,其实就是我们不需要知道f,P

 
 

这样我们就知道了:

如果Ein/Eout相似,Ein很小,那么Eout也就很小,那么如果继续从P产生资料的话 hf 还是相似。

 
 


 
 

从上面得到我们已经有的保证:

如果资料量足够大的话,固定的h的 Ein/Eout 相似。

 
 

那么在此基础上我们是否可以说 gf 是否相似,是否可以说是好的学习。g是h集合

是:选了一个固定的h有 Ein 很小,可推论到 gf 相似

否:问题是只有那个h可以做到,g可能包含很多其他的h,大部分其他h都会导致 Ein 很大。

 
 

因此:

真正的学习是有选择的选好的h

 
 


 
 

改了一下流程:重点是我们需要确认结果好不好

 
 

我们一样有资料,但是没有经过选择。

我们可以验证这个h的表现到底好不好。验证方法是再找一堆资料(verifying examples)看看这个h在这堆资料上面的表现到底好不好。这堆资料的产生和判断hf好不好的方式是一致的,那么你就可以确认这个h表现好不好。

 
 


 
 

联系:股票

 
 


 
 

答案 2

 
 

你可以选择未来的100天测试,如果其和过去十年类似,那么就可以赚大钱了。

 
 


 
 

上面讲到一个h的时候我们可以做验证

如果我们今天有很多个h的时候,则么办。

 
 

例子:

如果今天你有十个罐子,其中一个罐子抽出来全是绿色(全对),你要不要选他()是不是最好的答案。

 
 


 
 

举例丢铜板也是一样,你可以自己动手尝试一下。

 
 

譬如上课的这150个人每人丢5次,很可能出现丢五次五次都是正面,但问题是这个人的这块铜板真的比别人的好么?

 
 

你分析一下你会发现:

完全公平的铜板,上面这个情况,至少一个人出现5次正面的几率大于 99%,

但是如果你去选这150个铜板,你就会存在偏见,想去选那全对的(5次正面)的铜板。

 
 

所以:

上一节说道不好的这件事情很小,但是,这里你会发现:有选择的时候,这些选择会恶化不好的倾向。

 
 

解释:

原来只有一颗铜板,五个正面的几率是 1/32

现在你有150个选择,五个正面的几率是 > 99/100

这个五个正面的表现是不能正确反映分布的不好的倾向。

 
 


 
 

那什么是不好的资料

 
 

对于一个h

 
 

不好的sample例

铜板Eout就是1/2,但是五次正面在很多次的情况下会出现的几率很高,出现的时候Ein=0,差很远。

 
 

不好的data

表面看Ein很小,但事实Eout很大

 
 

好不好:Ein/Eout 的差距大不大

 
 

Hoeffding small 意思是:

把所有可能的资料列出一排(穷举),不好的资料加起来的几率很小。

 
 


 
 

如果今天有很多h,不好的几率会变成什么样子?

 
 

不好的资料:

演算法不能自由自在的做选择,就是很可能选到不好的那个。也就是说存在一个h的Ein/Eout差得非常远。

 
 

上图:

Hoeffding 告诉我们一行一行,bad加起来的几率不大。

竖着看,只要一列上面有一个不好的,就是overfitting,也就是说D1126才是好的,才是我们可以拿来使用的资料。

然后,我们更关心的是这个竖着的不好的资料发生的几率是多少?!也就是打问号的地方值是多少?

 
 


 
 

Pd(bad):表示的是只要对一个h来说是不好的资料的概率

 
 

如上图推导计算上限。

 
 

说明:

结论作用于各种例子都对。

我们不需要知道Eout是多少,也就是不需要知道p

每一个资料集都是安全的。也就是说,不管你怎么去做选择,你一定能选到一个g的Ein/Eout差不多。

 
 

因此:

最合理的演算法,就是选一个Ein(g)最小的g,因为这样基本表示 Ein/Eout接近。

 
 


 
 

于是我们终于可以做到一点点的learning了

 
 

意思是:

如果今天我们的h有有限多种选择,资料够多,那么不管我的演算法怎么选,Ein/Eout都会接近。

演算法就是找一个Ein最小的,就可以包装Eout也很小,就是期望的结果。

 
 

问题是:大部分情况下h是无限的,下面就会讲。

 
 


 
 

问题

 
 


 
 

答案是1

 
 


 
 

总结:

一开始说机器学习做不到

但是加上一些统计上的假设,譬如资料的产生方式,表现衡量方法,就可以做推论做验证,就是机器学习。

下面要讲是的h无线多的情况。