Machine Learning Foundations 11: Linear Models for Classification | Cheney Shen

Technology blog

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。

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

 
 

下一节:

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

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 


2 Comments

Post a Comment

Your email address will not be published. Required fields are marked *

  • Categories

  • Tags