5.3错误修正算法 5.3错误修正算法 口算法步骤 口算法步骤 2.检测与修正：对每次迭代所得增广权向量用训练 2.检测与修正 样本检测，如发生错误分类，则利用错分的信息 口如果存在某个或几个子类不满足上述条件，即存 进行修正： 在子类ω·的现有权向量，)使得 口先将某一j类的增广样本向量y:,与该类所有增广 权向量求内积a'因y,找到其中的最大值 a'y,≤ay,i≠J Wy,产，ry 则y,被错分类，需修正有关权向量。 口将y与其它非j类的权向量求内积，如 设y,=maxy aky,>ay,i=l1,2,,c,i≠方1=l,2, 则修正算法为a(k+)=a)+P, 则a《阳不影响y,的正确分类，不需修改。 a(k+1)=a"(k)-Py, 16 5.3错误修正算法 5.3错误修正算法 口算法步兼 口未知子类数目的情况（简介) 3.迭代与停止：利用新的权向量值对下一个训练样 ■树状分段线性分类器：先设计一个线性分类器， 本重复步骤二，直到算法收敛或者强迫其收敛。 将所有样本分成两个子类；若子类中有错分，则 在其中再分，直到全部样本正确分类。 口收敛性 ■在样本集确实能被分段线性判别函数正确划分的 情况下，迭代算法是收敛的。当该条件不满足 时，则需逐步减小p的数值，迫使其“收敛”，显 然会有相应的分类错误率存在，13 5.3 错误修正算法  算法步骤 2. 检测与修正：对每次迭代所得增广权向量用训练 样本检测，如发生错误分类，则利用错分的信息 进行修正； 先将某一 j 类的增广样本向量 yj ，与该类所有增广 权向量求内积 aj l(k) T yj ，找到其中的最大值 将 yj与其它非 j 类的权向量求内积，如 则 ai l (k) 不影响 yi的正确分类，不需修改。 ( ) max  ( ) , 1,2, , j l T j l l j m T j k k j a y a y    ( ) ( ) , 1,2, , , , 1, 2, , , mT lT j j i j i a ya y k k i ci       j l l 14 5.3 错误修正算法  算法步骤 2. 检测与修正 如果存在某个或几个子类不满足上述条件，即存 在子类 ωi n 的现有权向量 ai n(k) 使得 则 yi被错分类，需修正有关权向量。 设 则修正算法为 ( ) ( ) , mT nT j ji j a ya y k ki   j   ' ' , ( ) max ( ) , n T nT j ij i i n a y ay k k  ' ' ' ' ( 1) ( ) . ( 1) ( ) m m j j k j n n i ik j k k k k           a ay a ay 15 5.3 错误修正算法  算法步骤 3. 迭代与停止：利用新的权向量值对下一个训练样 本重复步骤二，直到算法收敛或者强迫其收敛。  收敛性  在样本集确实能被分段线性判别函数正确划分的 情况下，迭代算法是收敛的。当该条件不满足 时，则需逐步减小ρk的数值，迫使其“收敛”，显 然会有相应的分类错误率存在。 16 5.3 错误修正算法  未知子类数目的情况（简介）  树状分段线性分类器：先设计一个线性分类器， 将所有样本分成两个子类；若子类中有错分，则 在其中再分…，直到全部样本正确分类