Category: Machine Learning

Machine Learning Foundations 15: Validation


 
 

总结:Validation(验证)

从要选择一个好的模型来做切入:如果用 Ein 做选择是很危险的,但是你没有办法用 Etest 来做选择,我们用 Validation来做选择,我们做了相应的理论证明。

再讲 leave one out cross validation:假设validation最小达到1,然后做很多次取平均结果,理论上结果会比较好,但是这要花很大的计算上的时间。

实际上 leave one out vross validation没有那么可行,常用的是 v-fond cross validation,就是切5/10份就可以。

 
 


 
 

Validation (验证)

 
 

上一次讲到避免 overfitting 的一种方式叫做 regularization:在 Ein 上面加上 regularizer 项变成 E_aug,对此做 minimize 的动作,这样可以有效的限制 model complexity。

 
 

面临的问题的是:整个过程当中有很多的选择要做,这里 validation 就是用来帮助你作出合理的选择。

 
 


 
 

即使你要做 binary classification,根据当前所学,你已经可以使用 PLA, pocket, linear regression, logistic regression 等很多种方法。

 
 

这些方法存在的一些需要做选择的地方:迭代次数T,每一步步长n,特征转换sigma,错误衡量regularizer方法omega,regularizer强度lamda,等等。

 
 

你面临那么多的选择,而且组合还是叠加的,那么我们怎么来做选择?

 
 


 
 

我们之前其实就引导大家做过选择了,譬如光看着两个图的话,你会选择几次曲线?但是以前没有系统的来阐述这个问题。

 
 

已知:我们有 M 个模型,每个模型由他自己的 hypothiesis set,有他相对应的演算法。

目标:我们希望从 M 个里面选出某一个,然后把资料用在这个模型上面,最后得到的那个 g 会很小,选出来的那个用星号来标识表示最好的 Eout(gm*)。

但是 Eout 不知道,所以不能够直接用 Eout做选择,因此要思考新的方法。

这就是ML里面最重要的问题。

 
 

因此怎么选择?

 
 

肉眼看:

不可以,那是人的学习不是机器学习。

 
 


 
 

选择 Ein 最小的:

 
 

在这样的情况下,你用 1126 维度的phine 一定要比 phine1 好,因为曲线越复杂,Ein可以做到的越小,所以你会去选择高维度的曲线。不加 regularizer一定比加上好,因为加regularizer会导致曲线fit已知信息的能力下降。

这样子会导致 overfitting。

 
 

如果算法1选出h1 的时候Ein最小,算法2选出h2的时候Ein最小。这样整体来看就是要选一个 H1并上H2的hypothiesis set 里面选择最好的,增加了复杂度。(这边的例子莫名其妙,我的理解是各个H都是从整个目标model出来的,而这里最好的是用所有的已知数据的Ein最小,所以才会存在各个H的并集。)

 
 

因此用 Ein 来选择是很危险的。

 
 


 
 

找一串测试的资料,来看看到底哪个模型的表现最好:

 
 

可以得到的保证是 finite-bin hoeffding


以前的课推到过,这样确实可以得到比较好的效果。

 
 

问题是你找得到测试资料么?

 
 


 
 

比较:

 
 

Ein 做决定:只需要已知的资料,拿得到这些资料,但是这些资料决定了H,容易overfitting

Etest 做决定:需要额外的测试资料,但事实上根本没有这些资料,但是这些资料是没被使用过的,不会出问题。

 
 

综合上面两种:

 
 

Eval 做决定:对于所有已有的资料,一部分用于H,留下一部分只用于测试并做选择。

 
 


 
 

小测验

 
 


 
 

从已知的资料里面分出一部分做测试,这部分资料的大小定义为K,叫做验证资料,用来模拟测试资料,验证的时候产生的错误叫做 Eval(验证的错误)

 
 

因为已知的资料就是来自于 目标模型,而Dval就是来自于已知的资料,所以随机从已知资料抽取一部分K作为Dval就可以保证, Dval也来自于目标模型。

 
 

切出来N-k的数据叫做训练资料Dtrain,用于送到模型里面选一个hypothiesis。这里定义为 gm-, 因为相对来说训练资料减少了。

 
 

这里不同的数据用于训练和验证,可以得到的理论保障是:


 
 


 
 

做法过程(右图):

Dtrain 送到演算法里面,得到一群 gm- 以后,然后通过Dtest 来获得各个的验证错误,最后选择验证错误最小的。

 
 

问题是上面讲的都是 g- 而不是 g,一般来说资料量越多能选出的模型越好,因此如果你获得的 gm*- 对应的 Eout 要比 gm* 对应的差一些,就有下面的公式:


(灰色是因为,这没有经过严格证明,但实际上是这样)

 
 

这样我们结合 gm- 的 finite-bin hoeffding,就有上面黄色区域所示的公式。

 
 


 
 

如果将 validation 用在五次/十次多项式的时候的结果 。

 
 

上图横轴是你用的验证资料的数量,纵轴则是Eout,越低越好。

使用 Ein 来做选择是黑色实线,这时候选的总是10次多项式;

使用 Etest 来做选择是黑色虚线,这时候应该总是选最好的,但是你做不到这件事;

使用 Eval 来做选择,但回传 gm- ;

使用 Eval 来做选择,但回传 gm,选择5/10次多项式以后再重新算一个g5/10回传回去用。

 
 

蓝色的线总是比红色的低,验证上面的灰色公式,数据量大了以后总是相对更好。

蓝色的线总是比Ein低,就是说使用 Eval 会比 Ein 好。

红色的线有时候比 Ein 还差,因为 Dtrain 变小了,用了很少的资料算的 Eval 还不一定比 Ein 好。

 
 


 
 

上面告诉我们: 用于 validation 的数据资料的大小是很重要的。

 
 

上面的推论基于:Eout(g), Eout(g-) 够像,Eout(g-),Eval(g-)够像。因为我们是根据 Eval(g-) 做选择,选择 Eout(g) 最小的。

 
 

但是这两个等式对于 K 的大小的要求是不一样的,前面的希望 K 小,后面的希望 K 大。

大的K: 红色的和蓝色的线差很多,

小的K:Eval(g-) 和 Eout(g-) 接近不能确定。

 
 

到底 K 多大合适:一般是资料总数的五分之一。

 
 


 
 

小练习。

 
 


 
 

考虑 K 非常小,等于1.

则 g, g- 非常非常接近;Eval(g-), Eout(g-) 相似就比较难满足了。

 
 


表示留了n笔资料做validation;


表示减掉了n笔资料的g。


看看n笔资料上的错误是多少,标记为en(验证n笔资料的错误)

 
 

如果只一个 en 的话,不能保证他接近于 eout(g),但是如果我们有很多笔 en 的话,是不是可以确定 eout(g) 。

 
 

交叉验证(cross validation):每次留 n 笔数据,做很多次训练和验证,取平均结果。交叉的意思是,同一笔资料,有时候是用于训练,有时候是用于验证。

 
 

Eloocv(H, A):交叉验证的平均结果。

期望的事情是 Eout(g) 接近 Eloocv(H, A)。

 
 


 
 

假设我们有三个点,跑上面的情况,每次留一个验证,得到上面三图;在上面的结果取平均获得 Eloocv(linear)。

假设用常数来分,则有下面三幅图,也有三种情况,同样取平均得到 Eloocv(constant)

 
 

结果你会发现下面结果比较好,也就是说只有三个点这种超级简单情况常数就够用来分类了。

 
 

这就是使用 交叉验证 的方法过程步骤。

 
 



Eloocv 到底能不能告诉我们 Eout(g) 有多好?

大概可以。

 
 

目标:

我们要证明的是 N笔资料的 Eloocv


和 N-1笔资料的 Eout


是一样的。

 
 

过程:

第一步把期望和sum交换,因为两者是线性的;

en有两个部分:训练用的 + 验证用的,en则用其定义替换;

蓝色 sum 部分以及后面的总和 就是 Eout(g-);

红色 sum (Eout(gn-)) 就是 Eout(N-1) 的平均;

N-1笔资料的 Eout 就是 Eout(g-) 的平均值。

 
 

因此上面的证明目标成立。

 
 


 
 

手写辨识的例子的结果。

 
 

横轴表示的是特征维度,纵轴是错误率,蓝色表示使用 Ein 做 validation,红线表示直接使用目标 Eout 来做 validation,黑线就是交叉验证的方式来做的结果,和用 Eout 很接近。

 
 


 
 

小测验

 
 


 
 

接下来看 Eloocv 的问题是什么?

 
 

我有1000个点就要计算 1000次,每次丢999个点训练,一个点验证,非常花时间,而且计算的时候除了有一些有特殊解,其他的计算也很复杂费时。

 
 

用单一个点做衡量,最后用平均的方式消除变动,还是很不容易的,像上面的图的曲线有跳动,因此也不算稳定。

 
 

因为有着两个问题,所以其实在实际上 Eloocv 也不是很常用。

 
 


 
 

实际上需要的是:降低在做交叉验证的时候的计算量。

 
 

Eloocv 切的实在是太细,那么这里我们不要切那么细来做,可以有效减少计算量。

 
 

这样的话也一样获得平均的错误,叫做 Ecv。

 
 

那我们怎么知道要切几份,实际上常用的是切10份。

 
 


 
 

最后讲一下实际上常用的一些 validation 原则:

 
 

通常 cross-validation 要比 single-validation 要来得好,相对比较稳定,但是计算量会比较大。

通常情况下 cross-validation 切5份/10份表现就不错了。

 
 

Validation 带来的不一样的地方:

 
 

训练模型是在大大的 hypothiesis set 里面做选择;validation 则是在有限的train model里面选。

Train 像是初赛,validation像是决赛,最终选出结果。

 
 

因为 validation 还是在做选择,因此其结果还是会比真实的结果乐观(optimistic)一点。

所以 测试的表现 才是你要注意的点,而不是把 validation做到极致。

 
 


 
 

小测验。

 
 


 
 

总结:Validation(验证)

从要选择一个好的模型来做切入:如果用 Ein 做选择是很危险的,但是你没有办法用 Etest 来做选择,我们用 Validation来做选择,我们做了相应的理论证明。

再讲 leave one out cross validation:假设validation最小达到1,然后做很多次取平均结果,理论上结果会比较好,但是这要花很大的计算上的时间。

实际上 leave one out vross validation没有那么可行,常用的是 v-fond cross validation,就是切5/10份就可以。

 
 

下一次:讲一些小秘密

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

Machine Learning Foundations 14: Regularization


 
 

这里讲的内容:

Regularizer hypothesis set 就是在原来 H 的基础上加上条件,这样以后可以把要解的问题转换成 augmented error 的问题,就是把 W 的平方加进去,这代表了我们会降低 effective 的 Dvc,最后我们说到 regularizer 是一个非常 general 的工具,我们可以设计使用 符合目标函数特性的,能说服自己的,又容易优化求解的 来使用。

 
 


 
 

回顾:

ML里面最大的问题就是overfitting,当有太多的power,存在两种noise,数据量又不够多的时候,overfitting很有可能发生。

 
 

今天讲的 regularization 可以看作是处理 overfitting 的一种方法,我们首先讲数学推倒,然后延伸到各种不同的变化情况。

 
 


 
 

右图是我们上次举例的一种典型的overfitting的情况:资料量不多有noise,用了一个高次方多项式来fit,红色线 Ein 很低,但是 Ein 和 Eout(蓝线,目标)差别很大。

 
 

我们今天要做的就是从这么不好的情况 变成 左图所示的情况:规则化的fit

 
 

我们要怎么做呢?

就是从高次多项式走回到低次多项式的fit。

 
 

下图表示的是 高次hypotheses set包含低次的关系图,我们要做的就是从大圈圈走回小圈圈。

 
 

Ill-posed problems:意思是有很多的函数都满足我们的solution,我们不知道选择哪一个,因此我们需要做一定的限制来帮助做出一个选择,不然的话解太多会有问题。

 
 

在这里 regularzation 就是通过增加限制来解决解太多的问题。

 
 

因此下面举个例子就是怎么样从10次多项式走回到2次的多项式去。

 
 


 
 

我们还是用 高次方转换 和 linear regression 来做例子。这里用 W 来代替 W(上划线) 描述转换后的 weight。

 
 

这样的话,10次和2次 的表示如上面的公式。

10 次有 11个系数,2次有 3个系数,我们可以把2次看作是10次的3-10次项的系数都为0。这就是包含关系的解释。

 
 

10次多项式 走回 2次多项式,就是加上一个条件:3-10次项系数都为0.

 
 

 
 


 
 

也就是说(上面两个框框所讲的事情):

如果要找一个最好的10次多项式来 minimize Ein,就以前讲过的做法。

如果要找一个最好的2次多项式来 minimize Ein,我们还是考虑用10次多项式来做,但是我们加上一个限制条件说 3-10 次方的系数都是0。

 
 

也就是说:

Step back 就是所加的那个条件。

 
 

为什么要这么绕一圈往回走,而不是从低次往高次走?

 
 


 
 

为了赋予更强的范围表示能力,可以把条件放宽松:

从(H2)左边的框框是 11 维空间(H10) + 特定的 3次方及以上的项为0(特定的8个维度为0)

到(H’2)右边的框框是 11 维空间(H10) + 任意的8个维度为0

 
 

两者做比较,对于 H’2:

好消息:H’2 比 H2 条件更宽松,和 H2 一样的计算速度的情况下扩展了包含范围。H’2 比 H10 则紧很多,也就是说不会那么容易的 overfit。

坏消息:约束条件是一个离散算式,最佳化比较困难,是一个被证明的 NP 难题。

 
 

那么怎么办?

 
 


 
 

因此继续做变化:

左边是上面说的不大好解的问题;

右边把条件换掉:算W的大小,W的平方和给一个上限C。

 
 

我考率所有的W,希望所有的W平方加起来 <= C,这样的 hypotheses set 叫做 H(C)。

 
 

H(C) 和 H’2 有一定的 Overlap,HC里面一些属于H’2,H’2里面有一些也会属于HC。

HC 之间也有一定的重叠关系:C越大表示范围越大。

 
 

我们就把 HC 上面的 hypotheses set 叫做 regularized hypothesis set;而这个对应的规则叫做 W_reg。

 
 


 
 

小测验。

 
 


 
 

我们来看看怎么去求解新的这个最佳化问题?

 
 

首先把公式表示成 向量矩阵 的形式,淡蓝色框框表示。

同样条件也用 向量矩阵 表示,在几何上的意义是在一个半径为 根号C 的球里面,我们只考虑在这个球里面的W,找出这个球里最好的W来让Ein最小。

 
 


 
 

因此得到上面黄框表示公式。

 
 

来看看这个条件对于我们的最佳化问题造成了什么影响。

 
 

在没有条件的时候:

就看 目标函数朝着谷底的方向一路滚下去,谷底的方向就是梯度的反方向。

用上面的图表示,譬如在w点的位置,再一路滚下去,则继续向蓝色方向滚动,滚到 Wlin 就是做 linear regression 的 solution。Win表示的就是一个椭圆形,我们要从椭圆的周围一路滚到其中心,中心Ein最小,梯度的方向就是告诉你滚下去的路径。

 
 

有条件的时候:

W要在一个半径为根号C的球里面。

用上面的图表示,红色的球就是限制条件,我们要在球里面的才符合要求。

你可以想象一般情况下最佳解都会出现在球的边界(除非原本的最佳解就在限制条件内),因此我们来考虑如果现在的解已经在球的边边,我们怎么来判断其是否是最佳解?也就是说在符合条件的状况下还能不能往最佳方向滚。

因此目标的滚的方向可以分为 球的表面法向量方向(滚出球的方向,红线)和切线方向(还在球的方向,绿线),切线方向滚是可行的。所以当目前的位置在红色球边界上,且其目标方向(蓝色)和切线垂直,或者说与法向量平行,则就是满足要求的最好的解。

 
 

Linear regression 的理论 Ein/Eout 平均错误是 2 lamda/N

因为有与红线平行的条件,因此最终有上面的黄色表示式子。

 
 


 
 

我们的目标:


 
 

这里既要求解 lamda,又要求解 w,变得复杂了。但是假设告诉你 lamda 是多少,那么就可以有 W_reg 的线性方程式。

 
 

Ein 的梯度里面有 2(Z’Z W – Z’y)/N ,其要等于0.

所以带入上面的公式,就有:


线性方程式求解可以得到:


 
 

这个就是最佳解。

只要 lamda 大于0,lamda相关项反矩阵存在,整个就是可逆的,也就是这个解存在且唯一。这个东西在统计里面叫做 ridge regression。

 
 


 
 

如果今天不是 linear regression 的情况下怎么去求解?

 
 

首先可以反过来看:如果我们今天要解的是


这个问题的最小值,就是要去求解


这两个公式就是 微分/积分 的关系。

 
 

因此新观点:

把有条件的问题的求解 看作是 多带一项的新的问题

整个公式(augumented error)= Ein + regularizer,可以看作是在原来的基础上求解一个新的比较大一点的问题,这个问题里面没有条件限制了。

能解这个问题的条件是 lamda 是多少已知,通常情况下 lamda > 0,设成0的话就是原来的没有做规则化的问题。

 
 

这样做就是把 原来需要已知的参数 C 替换成了 lamda。

给 C:需要求解带限制条件的解,中间过程就包括找出lamda。

给 lamda:看作是解不带限制条件的多一项的新问题,只需要做给C情况下的找到lamda以后的步骤,求解方便了。

 
 


 
 

结果:

四种lamda的值用在最初的例子上。没有lamda会 overfitting,lamda很大的情况红线蓝线也差的比较远,就是underfitting。

可以说你只要加一点点regularzation就可以得到很好的结果。

 
 

Lamda/C 关系:

Lamda 越大,代表你希望的W越短越好,也就是你要比较小的C。

 
 


 
 

细节:上面讲的 regression可以和任何的 transform 做搭配使用,因此为了让结果比较好,在做transform的时候做了一点手脚:

 
 

问题:

使用 polynomial transform 有一定的缺陷:如果X在-1到1之间的话,因为q越大,x的q次方会很小很小,但是其这一项需要很大的影响力的时候,W需要很大。可以说是过度的惩罚了高纬度的项。

 
 

原因:regularization的时候因为各个基本向量不是垂直的,因此会导致不同次方的地方的地方regularization程度不同。

 
 

解决:采用垂直基底(线性代数有这个内容)

下面的五张图表示的是前五个垂直基底。

 
 


 
 

小测验

 
 


 
 

上面已经学了Regularization,我们这里来看看它和 VC Theory 的关系。

 
 

我们最初要求解的是 带限制条件的Ein最小化的问题。

因为 C 与 lamda 的替换关系,可以看作是一个扩展一项的不带限制条件的Ein的求解。

原始的问题对应到 VC Guarantee 可以看作是


 
 

也就是说做 min E_aug 就是间接的把 Dvc 做出来了。

 
 


 
 

比对 Augmented Error 与 VC Bound:

W^t * W 正则化 – 可以看作是 一个 hypothesis 到底有多复杂。

Omega(H) – 可以看作是 整个 hypothesis set 有多复杂。

 
 

因此,一种理解方式:

如果 单一的h复杂度 和 整体的 接近,也许 E_aug 相比较Ein而言,是一个好的 真正的H的Eout 的代理人。

 
 


 
 

H 而言:所有的w都是可选的,理论上 Dvc 的变数就是 d+1(就是H);

实际上,只有HC里面的w可能会出现在谷底,才是需要考虑的;

因此实际上 Dvc 的变数就是 HC 那么多,而不是 H;

也就是说可以定义一个 Dvc_eff:考虑H,同时考虑做选择的方法,得到的等效的 Dvc。

 
 

因此,另外一种理解方式:

理论上的是 Dvc, 但是 Dvc_eff 可以等效替代 Dvc 来用。

 
 


 
 

小测验

 
 


 
 

前面讲到的 regularizer 都集中在 weight-decay,如果今天换更加一般的 regularizer,那么要加上什么样的条件才是好的呢?

 
 

也就是第一个问题,挑W的计算方式。

 
 

最好的:告诉你 target function,但是对ML来说是不可行的。

告诉你好的 target function 在哪个方向,就是给你缩小范围。

 
 

所以好的 regularizer 特点(Regularizer 常用选择方式):

  1. 知道taget的一些特性,用上去。
  2. 选择使用一些可以说服我们的对象,比如用上的 regularizer 可以帮我选出 比较平滑简单的 h(overfitting来源于noise,noise就是不平滑的,target就应该选比较平滑的),比如使用 L1。
  3. 容易做优化的,比如 L2。

 
 

如果你选到不好的,加入lamda=0,就等于是不使用 regularizer,就不会导致结果比原来更差。

 
 

回忆一下第八堂课,错误的衡量有三个可能性:

  1. User 告诉我们她真的想要什么
  2. User不知道,选一个我们能说服我们自己的
  3. 选一个容易 optimize 的

 
 

这就是设计ML的时候很重要的考虑范围:

Augmented error = error(三条意见)+regularizer(三条意见)

 
 


 
 

L2 regularizer : W的平方和

特点:平滑,凸的,可以微分,容易最佳化

 
 

L1 regularizer:所有的W的绝对值加起来

特点:凸的,w=0的地方是不可以微分的,因为有些尖的转角比较难解,解通常是 sparse 的,就是有很多个0,少数是1。

sparse:如图边界的normal一般是一致的,因此最后的解常常发生在顶点上,因此在做预测的时候,使用L1就可以直接去猜测顶点结果使用就行,很快就可以求解。

 
 


 
 

第二个问题:lamda 选多少

 
 

左图表示加入 stochastic noise 的时候,sigma取三个定值的时候,lamda与Eout的关系。颜色的点就是Eout的最小的点。

右图表示加入 deterministic noise 的时候,sigma取三个定值的时候,lamda与Eout的关系。颜色的点就是Eout的最小的点。

 
 

最好的lamda取决于你的noise有多少,noise越高,lamda越大。类比就是 路况越不好,刹车要踩的越重,regularizer就是踩刹车。

 
 

但是你不知道noise是多少,因此你很有可能需要在不同的lamda里面挑一个好的lamda,才能让regularizer发挥作用。

下一堂课就是来讲怎么选择 lamda,phine,linear model。

 
 


 
 

小测验

 
 


 
 

总结:

Regularizer hypothesis set 就是在原来 H 的基础上加上条件,这样以后可以把要解的问题转换成 augmented error 的问题,就是把 W 的平方加进去,这代表了我们会降低 effective 的 Dvc,最后我们说到 regularizer 是一个非常 general 的工具,我们可以设计使用 符合目标函数特性的,能说服自己的,又容易优化求解的 来使用。

 
 

下次讲怎么做选择。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

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。