北京大学：《模式识别》课程教学资源（课件讲稿）线性判别函数（第二部分）

第四章 线性判别函数 2010-10-27

第四章 线性判别函数 2010-10-27

2 例解 设两类样本的类内离散矩阵分别 S, 为S1,S2,各类样本均值分别为 1 m=(2,0),m2=(2,2),试用Fisher准 一方 则求其决策面方程。 20 S。=S+$2= 02 e-a 图中绿线为最佳分界面 y三W*X=y0; m+形2w*(m,+m) %= 三一→ 2 2 即(0，-1) 水3=-1 X2

2 例解 1 2 2 0 ; 0 2 wS SS        1 1 2 0.5 0 0 0 () ; 0 0.5 2 1 wS                      w mm 12 1 2 0 ( ) 1; 2 2 T m m y        w mm 0 2 1 2 ; (0, 1) 1. T x y y x x               w x 即

感知准则函数 (Perceptron)

感知准则函数 （Perceptron ）

5 基本概念 口线性可分性：在特征空间中可以用一个线性分 界面正确无误地分开两类样本。 口在线性可分时，对合适的增广权向量a应有： 如果y∈o,则a'y>0; 如果y∈o2,则ay0 i=1,..N

5 基本概念  线性可分性：在特征空间中可以用一个线性分 界面正确无误地分开两类样本。  在线性可分时，对合适的增广权向量 a 应有：  样本的规范化：将第二类样本取其反向向量 1 2 , 0; , 0; T T         y ay y ay 如果 则 如果 则 1 2        y y y y y 如果 = 如果 0 1,..., . T i a y  i N

7 基本概念 解向量：满足ay:'>0,i=1,…,N的权向量 a; 口解区：权值空间中所有解向量组成的区域： solution solution region y2 region y2 a separating plane "separating plane

7 基本概念  解向量：满足 aTyi ′> 0, i =1,…,N 的权向量 a；  解区：权值空间中所有解向量组成的区域；

8 基本概念 0氵 对解区的限制：引入余量b,要求解向量满足 ay;'≥b>0,i=1,…,N,防止求解增广权向量 的算法收敛到解区的边界。 a solution solution region region bllly ll y2

8 基本概念  对解区的限制：引入余量 b，要求解向量满足 aTyi ′≥ b > 0，i = 1,…,N，防止求解增广权向量 的算法收敛到解区的边界

9 感知准则函数及求解 Jp(a)=∑(-ay) 口当且仅当Jp(a)=min Jp(a)=0时，无错分样本。 口求解：梯度下降法 Algorithm 1 (Basic gradient descent) begin initialize a,criterion 0,n(),k =0 2 dok←-k+1 3 a←-a-(k)V.J(a) 4 unti业n(kc)V.J(a)<9 5 return a 6 end

9 感知准则函数及求解  当且仅当 JP ( a *) = min JP ( a) = 0 时，无错分样本。  求解：梯度下降法 () ( ) k T P Y J    y a a y ( ) ( ) ( ); k i p p i Y J J       y a a y a ( 1) ( ) ( ) ( ) () () . k i p i Y k k kJ k k         y aa a a y

10 感知准则函数及求解 Jp(a)=∑(-a'y) 口当且仅当Jp(a)=min Jp((a)=0时，无错分样本。 口求解：梯度下降法 ∑(-y) y∈Y a(k+1)=a(k)-(k)VJ,(a) =a(k)+7(k)∑y

10 感知准则函数及求解  当且仅当 JP ( a *) = min JP ( a) = 0 时，无错分样本。  求解：梯度下降法 () ( ) k T P Y J    y a a y ( ) ( ) ( ); k i p p i Y J J       y a a y a ( 1) ( ) ( ) ( ) () () . k i p i Y k k kJ k k         y aa a a y

11 批量/单样本迭代算法 Algorithm 3 (Batch Perceptron) 1 begin initialize a,n(),criterion 0,k =0 2 do kk+1 3 a-a+)∑y y∈Jyk 4 untl(k)∑y<9 y∈Jyk 5 return a 6 end Algorithm 4(Fixed-increment single-sample Perceptron begin initialize a,=0 1 2 dok←(k+1)modn 3 if yk is misclassified by a then a-a-yk 4 until all patterns properly classified 5 return a 6 end

11 批量/单样本迭代算法

12 单样本修正法 口收敛性讨论 a(k+1)'y =a(k)'y+n(k)y'y a(k)'y 口理论结论：只要训练样 本集是线性可分的，对 于任意的初值a(1), 经过有限次叠代，算法 必定收敛

12 单样本修正法  收敛性讨论  理论结论：只要训练样 本集是线性可分的，对 于任意的初值 a(1) ， 经过有限次叠代，算法 必定收敛。 ( 1) () () ( ) T T T T k k k k      a y a y yy a y