分类算法之感知器学习算法PLA 和口袋算法Pocket Algorithm


我们有一堆数据,默认他们是线性可分的。
定义f为这个数据分割线的最优解,但是我们不知道他的值。
我们仅有一个函数集H,这个函数一般是无穷大的。我们的目的就是从H中找出一条线g来尽可能的接近f。但是,我刚刚说了,H内的函数一般是无穷多的,我们不可能吧H中的函数一一比较,得到最好的分割线g吧!!!

不过伟大的科学家就说,我们的目的不就是找出一条线把这些数据都分开吗!!那我随机的初始化一条分割线 ,让他一一和数据点进行比较(数据总该是有限个的吧), 如果 某一个数据点划分对了,那这条线就不动,继续比较下一个点。如果错了,那就调整 这条线,让他能把这个点分对。以此下去,知道我们发现所有的点都分隔对了为止。。。

  1. 那么问题就来了,我们怎么调整这条分隔线呢???
    首先要明确,只有当分类出错误的时候,才对分割线进行调整。
    假设我们遇到的数据点是我们第t次分类错误。那么就有这里写图片描述


    这里写图片描述
    紫色的就是更改后的

    同理

    这里写图片描述
    紫色的就是更改后的

    综上所述,当分割线遇到点就不变,如果分割错误,那么就令这里写图片描述

    注意w是分割线的法线,也就是说分割线的方向是与w的方向垂直的。。。

  2. 这个想法是挺好的,那么问题是,用这种方法到底行不行得通呢???现在,我们就来验证这个算法的正确性!!!
    这种方法到底行不行得通,其实就是说这个算法到底能不能找到正确区分所有点的线。即这个算法到底能不能收敛?(收敛就是能停下来,算法只有找到了满足要求的线才停下来,所以说法不同,但意思是一样的)
    证明:
    首先有两个前提:
    前提1:数据本就是可以线性可分的。(如果数据不是线性可分的话,那不管我们怎么找都找不到那条线)
    前提2:我们仅仅是遇到分错的点时,才改变不变。

    根据前提1,说明最终的线一定存在。
    假设是我们要的线,则有 这里写图片描述
    当线,即这里写图片描述
    遂有
    这里写图片描述

    根据前提2,有
    这里写图片描述
    又有这里写图片描述
    判断w_t,是否相近,只需他们的$/Theta尽可能为0

    我们初始化$w_0=0$,则可以怎么得,在T次误差矫正后,有![这里写图片描述](https://www.icode9.com/i/?i=20160726142319933)
    即$cos/Theta>=/sqrt T .Cconstant$,所以$w_t是越来越接近 w_f$ 又$cos/Theta<=1$,所以 $w_t$一定收敛。
    

    这个算法最大的缺点就是假设数据点是线性可分的。问题是,我们并不知道数据到底是不是线性可分的!!如果不是,也就是说最终根本没有上面的,即没有一条不犯错误的线,那么以上的推论都是“白搭”!!!

    那怎么办???有个想法是,我们能不能把找出一条犯错误最少的线呢????即这里写图片描述
    其实,从实际意义上,是不能的。这是一个著名的NP hard 问题!!!因为线有无穷多个啊!!!

    伟大的科学家又提出一条算法,来解决这个问题——-口袋算法
    口袋算法基于贪心的思想。他总是让遇到的最好的线拿在自己的手上。。。
    就是我首先手里有一条分割线不变。
    那怎样让算法停下来呢??——–我们就 自己规定迭代的次数
    由于口袋算法得到的线越来越好(PLA就不一定了,PLA是最终结果最好,其他情况就说不准了),所以我们就 自己规定迭代的次数 。
    这里写图片描述

  3. 最后一个问题,如果数据本就是线性可分,那么我们用 pocket algorithm 和用 PLA,那个更好???
    答案是PLA更好。先不说PLA可以找到最好的那条线。单从效率上来说,PLA也更好些。最主要的原因是,pocket algorithm 每次比较的时候,都要遍历所有的数据点,且两个算法都要遍历一遍,才会决定那个算法好,而这还是比较一次,如果我们让他迭代500次的,那就麻烦了!!!但是,所有前提是,数据是线性可分的。如果线性不可分,只能用pocket algorithm,因为PLA根本不会停下来(也不是PLA的每更改一次效果就会比之前的好)!!

(function () {

(‘pre.prettyprint code’).each(function () {
var lines =

(this).text().split(′/n′).length;var(this).text().split(/n).length;var

numbering = $(‘

    ‘).addClass(‘pre-numbering’).hide();
    (this).addClass(′has−numbering′).parent().append((this).addClass(hasnumbering).parent().append(numbering);
    for (i = 1; i

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/244482.html

(0)
上一篇 2022年4月17日
下一篇 2022年4月17日

发表回复

登录后才能评论