麻省理工公开课人工智能笔记十六
本篇主要讲boosting算法,基于分类器,以二分类为例
有一个分类器h,他只有两种结果{+1,-1},他的出错概率为从0到1,假设概率接近0.5但是弱分类器,接近0的是强分类器,那能否使用多个弱分类器得到强分类器呢。
假设我们有一个H(x),他是所有h(x)的和,这里选三个,用h1,h2,h3表示,同时将和用符号表示,即根据和的结果决定是+1还是-1.
假设h1、h2、h3的出错点是像上左图中三个互补相交的区域,那H公式总是正确的,但如果像右图那样,却会出错。
我们可以建立一个算法来帮我们。这是①
选取特定的弱分类器,使用数据,不经任何干扰的进行h1分类,即对数据进行所有测试,选取最小的出错概率的分类。然后我们将使用夸大h1误差的数据。即更关注那些让h1出现误差的样本,给他们赋予权重或别的什么(夸大),将其给h2,然后,继续这样,夸大h1给的结果不同于h2的那些,给h3。
然后我们可以得到一个像这样的树,这是②
现在,我们考虑决策树桩
假设我们有一个二维空间,那么决策树桩是一单个测试,这不是一棵完整的将样本分为同质组的树,这里只是使用单个测试,每个可能的测试都是一个分类器,从这里我们得到了12个测试,因为考虑竖着的三条画线,我们可以将+或-放到左侧或是右侧,这就使六个测试,然后有两个维度,就使12个。
我们可以这样生成一批测试,然后用这批测试的带想要的结果。
再看,这些测试的误差率是多少,我们假定,每个 样本点对应有一个权重。w1、w2、w3,最开始,我们假定特们都是相同的,也就是说,最开始wi=1/N。N是总数。
那么,误差率就等于所有出错样本的权重值求和。
第一步中,大家都是相同的权重值,但随着过程的发展,我们会设法让权重值发生变化,比如在这里,我们夸大样本三,那么w3就会上升,不过我们还是要保证整个空间中所有权重之和等于1.
然后,我们继续向下考虑,如何将这些东西合并起来,建立一个分类器,将所有分类器合并起来,α是权重。
总的算法
最初让所有wi=1/N,然后选择一个分类器最小化t时刻的误差率,这样我们可以使用误差率确定α,这样我们就能计算出t+1时刻的w,最后,循环计算。
最后,我们需要知道如何计算t+1时刻的w,就如上图,z是某个归一化因子,作用是让新权重加起来等于1,y(x)是一个函数,值为+1或-1,就像在支持向量机中的y一样,他的值取决于输出。
对于整个式子的最小化误差如上图
同时,这个最小化误差也是H(x)这个式子产生的误差率的界限,这意味着,误差率可以随公式总项的增加而上升,而有这个式子,误差率将由一个指数式衰减的函数作为界限,他最终确保了收敛为0
现在我们做一些数学计算
得到了t+1时刻的wi的值,我们将他们求和
我们发现,分类正确和错误的情形下,所有wi求和的值都是1/2,这意味着,你取给出正确答案的那些权重,然后缩放到他们的和是1/2,就得到下一代的权重,不需要计算z,不用计算α,只需要缩放。
同时,我们还发现,在测试中只有极少需要考虑,而不用考虑全部的测试。