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

4.最小平方误差准则(MSE) 口线性分类器的表达式 第四章线性判别函数 ■原始表达式： 8)=wx+@-2x+a: 2009-11-3 ■增广样本、权向量： a=[oo,w,…,w]g y=l,x,…,x]; ■判别函数的齐次表达式： g'(y)=a'y≡g(x方 4.最小平方误差准则(MSE) 4.最小平方误差准则(M$E) 口规范化增广样本向量y,增广权向量a,正确分 口引入余量（目标向量）b=[b,b2,b,b为 类要求：ay>0,i=1,…, 任意给定正常数，a'片=b,>0: 口设计线性分类器分求解一组N个线性不等式； 口N个线性方程的的矩阵表示： 分类器的理想输出 Ya = 口样本集增广矩阵Y及一组N个线性不等式的矩 阵表示： 口定义误差向量： e=Ya-b; y 〔yo y Ya>0. 口定义平方误差准则函数J,(a: Ja=f=a-af-立a-6 NXd+)维 4.最小平方误差准则（MSE) 4.最小平方误差准则(MSE) 口最小二乘近似解(MSE解)： VJ,(a)=∑2(ay,-b,y,=2y'(Ya-b)片 a*=argminJ,(a方 MSE方法的思想：对每个样本，设定一个“理 VJ,(a)=0台YrYa=Yrb; 想”的判别函数输出值，以最小平方误差为准 则求最优权向量。 a'=(YY)-YTb=Y+b Y的 伪逆矩阵

第四章 线性判别函数 2009-11-3 2 4. 最小平方误差准则（MSE）  线性分类器的表达式  原始表达式：  增广样本、权向量：  判别函数的齐次表达式： ( ) ; 0 1  0     d i i i T g x w x w x [1, , , ] ; [ , , , ] ; 1 0 1 T d T d x x w w     y a  '( ) ( ); T g g y   a y x 3 4. 最小平方误差准则（MSE）  规范化增广样本向量 yi，增广权向量 a，正确分 类要求： aT yi > 0, i=1,…,N；  设计线性分类器求解一组 N 个线性不等式；  样本集增广矩阵 Y 及一组 N 个线性不等式的矩 阵表示： 1 10 11 1 1 20 21 2 0 1 ... ... ; ... ... ... ... ... ... T d T d T N N N Nd yy y yy y Y yy y                       y y y Ya  0. N×(d+1)维 4 4. 最小平方误差准则（MSE）  引入余量（目标向量） b = [b1, b2, …, bN]T，bi 为 任意给定正常数，aT yi = bi > 0；  N 个线性方程的的矩阵表示：  定义误差向量：  定义平方误差准则函数 Js(a): Y a b  ; 分类器的理想输出 e  Ya -b; 2 2 2 1 () ( ); N T s ii i JY b  a e a b ay     5 4. 最小平方误差准则（MSE）  最小二乘近似解（MSE解）： * argmin ( ); s  J a a a MSE方法的思想：对每个样本，设定一个“理 想”的判别函数输出值，以最小平方误差为准 则求最优权向量。 6 4. 最小平方误差准则（MSE） 1 ( ) 2( ) 2 ( ); N T T s i ii i J b YY      a ay y a b  * 1 () . T T YY Y Y   a bb   * * () 0 ; T T s   J YY Y a ab  Y 的 伪逆矩阵

4.最小平方误差准则(MSE) 4.最小平方误差准则(MSE) 口例： 口与Fisher线性判别的关系 ·o:(1,2yand(2.0y ■两类样本数分别为N,N2(N=N+N2) ·o2(3,1yand(2,3y ■如令 b=(6,…,b,b…,b)月 Sample Matrix (d1+2,n■ 「1121 第一美第二类 r- 120 即同类样本对应相同的余量值： 1 →MSE的解a*等价于Fisher判别器所得结果， Pseudo-inverse 「51413/123/47/12 其中%=-mw'=-N(N,m,+N,m2)'w,相当于 -1/2-1/6-1/2-1/6 「11/3 0-1/30-1/3 -4/3 Fisher判别中%=m. -2/3 10 4.最小平方误差准则(MSE) 4.最小平方误差准则(MSE) 口与Fisher线性判别的关系 口与Fisher线性判别的关系 a-bf-2ay,-b2=∑ay,-b,2+∑(ay-h a-bf-∑(ay,-b,2+∑a'y,-b 最小化Ya-b→ =∑(w+@。-b,尸+∑(w+a-b尸 nma -wm'+Σ-m 点=三=三*a小wm -wSw+wS:w-wS.w. 给定类间距 解释：最小平方误差相当于给定类间距的条件 →w'(m,-m2)=b-b 下，使类内矩最小。 11 4.最小平方误差准则（MSE) 4.最小平方误差准则(MSE) 口与Bayes判别函数的关系 口与Bayes判别函数的关系 ■当N→0，b=(L,…,l,-1,…,-l)时，MSE的 解以最小均方误差逼近Bayes判别函数： J,(a=∑(ay,-12+∑(a'y,+12 8o(x)=p(@lx)-p(@.lx)=P(@.X)-pl@..x). p(x) =货2-旷旷 口定义均方逼近误差 e2=∫a'y-8oxpx)k 根据大数定理，当N→o时： 则 a'=Y'b=argmine2 文：a2:a

7 4. 最小平方误差准则（MSE）  例： 8 4. 最小平方误差准则（MSE）  与 Fisher 线性判别的关系  两类样本数分别为N1, N2 (N=N1+N2)。  如令 即同类样本对应相同的余量值；  MSE 的解 a* 等价于 Fisher 判别器所得结果， 其中 相当于 Fisher 判别中   ** * 0 11 2 2 1 , T T     mw m m w NN N . ~ y0  m   ,,,,, T b bb b b       第一类 第二类 9 4. 最小平方误差准则（MSE）  与 Fisher 线性判别的关系 1 2 2 222 1 ( ) ( ) ( ); i i N TT T ii i i i Y bb b               x x a b ay ay ay     1 1 2 2 2 0 10 1 1 0 20 2 1 1 1 ; 1 1 ; i i i i T TT i i T TT i i Y b N N b N N                             x x x x a b ay wx wm ay wx wm 最小化   1 2 . T b b  wm m     给定类间距 10 4. 最小平方误差准则（MSE）  与 Fisher 线性判别的关系    1 2 1 2 1 2 2 2 2 2 2 0 0 2 2 1 2 1 2 ( )( ) ( )( ) ; i i i i i i T T i i T T i i TT TT i i T w T T Y bb b b                                       x x x x x x a b ay ay wx wx wx wm wx wm w Sw w S w wSw 解释：最小平方误差相当于给定类间距的条件 下，使类内矩最小。 11 4. 最小平方误差准则（MSE）  与 Bayes 判别函数的关系  当 时，MSE的 解以最小均方误差逼近 Bayes 判别函数： 定义均方逼近误差 则 , 1, ,1, 1, , 1  T N     b   1 2 01 2 ( ,) ( ,) () ( | ) ( | ) ; ( ) p p gp p p       x x xxx x   ( ) ( ) ; 2 0 2 e a y g x p x dx T    * 2 Y e arg min .  a b   12 4. 最小平方误差准则（MSE）  与 Bayes 判别函数的关系 1 2 1 2 2 2 1 2 2 2 1 2 ( ) ( 1) ( 1) 1 1 ( 1) ( 1) ; i i i i T T si i T T i i J N N N NN NN                         x x x x a ay ay ay ay ( ); 2 ( ), 1 1 P 2 N N P N N N       根据大数定理，当 时：

4.最小平方误差准则(MSE) 4.最小平方误差准则(MSE) 口与Bayes判别函数的关系 口求解MSE解 J.(a) ■计算a=Y*b,其中Y*=(WY)yT:yy可能 N 是奇异矩阵；计算量大，计算误差较大。 =P(o)[(a'y-1)p(x)dx+P(@)[(a'y+1)p(x)dx ■实际中常用梯度下降法求解： =(a'y-l)p(x)dx+[(a'y-1)p(x.)d -j[+小-2，x-aA w,a-22a-6w,=2r0a- 批量样本 =ay'p)h-2ayg)px)本+ a(),任意初始化 修正法 a(k+1)=a(k)-n(k)Y'(Ya-b) =J[ay-g]nx达+[l-∫gx)px)h] until V/,(a)≤0或者a(k+l)-a(k)圳≤0： =e2+1-∫gpx)d] 与a无关 可选k)=7)/k(7)>0). 4.最小平方误差准则(MSE) 5.最小错分样本数准则（简介） 口求解MSE解 口线性可分性： ■单样本修正法(Widrow-Hof算法，最小均方算法) a),任意初始化 a(k+1)=a(k)+n(k)(b -a(k)y)y 其中y是使得a(k)y≠b的样本。 Algorithm 10 (LMS) 线性可分 线性不可分 begin initialize a,b,criterion)= d如k-k+1 口判断线性可分一若存在增广权向量对规范化 a-a十k)s-ayy unt过k)(bk-ay*)yk0,i=l,2,…,N 5.最小错分样本数准则（简介） 6.线性支持向量机（线性SVM0 口基本思想：对于规范化的增广样本向量，要找增 口SVM的理论基础 广权向量使得不等式组a'y,>0,i=1,2,…,N,中 ■传统的统计模式识别方法只有在样本趋向无穷大 尽可能多的不等式成立。 时，其性能才有理论的保证。统计学习理论 口增加解的可靠性，引入余量b。 (STL)研究有限样本情况下的机器学习问题。 SVM的理论基础就是统计学习理论。 口准则函数：只考虑被错分样本，即只有被错分的 样本a'y,<b有页献 ■传统的统计模式识别方法在进行机器学习时，强 调经验风险最小化，而单纯的经验风险最小化会 J(a)=(Ya-b)-Ya-b 产生“过学习问题”，其推广能力较差。 ■求解：无约束最优化的各种算法，如共轭梯度 法；带约束的二次规划

13 4. 最小平方误差准则（MSE）  与 Bayes 判别函数的关系           2 1 2 1 2 1 2 2 2 1 12 2 2 2 1 2 2 0 0 (, ) (, ) (, ) (, ) 2 () (, ) (, ) ( ) ( ) ( 1) ( | ) ( ) ( 1) ( | ) ( 1) ( , ) ( 1) ( , ) () 2 () () 1 ( ( ) T T T T T T T T T s p p p p pp p d p P p dP p d pd pd pd g pd g J N                               x x ay x x ay x x x x x ay x x ay x x ay x x ay x x ay x x ay x x x a y a  2 0 2 0 2 2 ) () 1 () () 1 () () ; pd g p e gp d d                    x xx x xx x xx 与a无关 14 4. 最小平方误差准则（MSE）  求解 MSE 解  计算 其中 ： 可能 是奇异矩阵；计算量大，计算误差较大。  实际中常用梯度下降法求解： * Y ,  a b  1 ( ) T T Y YY Y    T Y Y 1 ( ) 2( ) 2 ( ) N T T s i ii i J b YY     a a  y y a b (1), ( 1) ( ) ( ) ( ) until ( ) ( 1) ( ) ; ( ) (1) ( (1) 0). T s k k kY Y J kk k k                  a a a ab a aa 任意初始化 或者 可选 批量样本 修正法 15 4. 最小平方误差准则（MSE）  求解 MSE 解  单样本修正法(Widrow-Hoff 算法，最小均方算法) (1), ( 1) ( ) ( )( ( ) ) ( ) Tk k k k Tk k k k kb k k b         a a a a yy y ay 任意初始化 其中 是使得 的样本。 16 5. 最小错分样本数准则（简介）  线性可分性：  判断线性可分 —— 若存在增广权向量对规范化 的增广样本向量满足： T 0, 1,2, , . i a y  i N  17 5. 最小错分样本数准则（简介）  基本思想：对于规范化的增广样本向量，要找增 广权向量使得不等式组 中 尽可能多的不等式成立。  增加解的可靠性，引入余量 b。  准则函数：只考虑被错分样本，即只有被错分的 样本 有贡献  求解：无约束最优化的各种算法，如共轭梯度 法；带约束的二次规划。 T 0, 1, 2, , , i a y  i N  J () ( ) . a Ya b Ya b    T i i a y  b 18 6. 线性支持向量机 (线性SVM)  SVM 的理论基础  传统的统计模式识别方法只有在样本趋向无穷大 时，其性能才有理论的保证。统计学习理论 (STL) 研究有限样本情况下的机器学习问题。 SVM 的理论基础就是统计学习理论。  传统的统计模式识别方法在进行机器学习时，强 调经验风险最小化。而单纯的经验风险最小化会 产生“过学习问题”，其推广能力较差

6.线性支持向量机（线性SVM① 6.线性支持向量机（线性SV① 口SVM的理论基础 口支持向量机(SVM) ■“推广能力”是指：将学习机器（即预测函数，或称 ■根据统计学习理论，学习机器的实际风险由经验 学习函数、学习模型)对未来输出进行正确预测 风险值和置信范围值两部分组成。而基于经验风 的能力。 险最小化准则的学习方法只强调了训练样本的经 验风险最小误差，没有最小化置信范围值，因此 ■“过学习问题”：某些情况下，当训练误差过小反 其推广能力较差。 而会导致推广能力的下降。 ■Vapnik提出的支持向量机以训练误差作为优化问 ■例如：对一组训练样本(K,y),x分布在实数范围 题的约束条件，以置信范围值最小化作为优化目 内，y取值在[0,1]之间。无论这些样本是由 标，即SVM是一种基于结构风险最小化准则的 什么模型产生的，我们总可以用y=sin(w*x)去拟 学习方法，其推广能力明显优于一些传统的学习 合，使得训练误差为0。 方法。 6.线性支持向量机（线性SVM①） 6.线性支持向量机（线性SVM) 口支持向量机(SVMD 口线性可分情形下的最优分类面(optimal ■形成时期在1992一1995年； hyperplane) ■最优化准则是类间边界距离，故也被称为最大边 界距离分类器： ·denotes+1 。denotes-l ■由于SVM的求解最后转化成线性约束的二次规 划问题的求解，因此SVM的解是全局唯一的最 优解： 问题：哪个分 类面最好？ ■SVM在解决小样本、非线性及高维模式识别问 题中表现出许多特有的优势，并能够推广应用到 函数拟合等其他机器学习问题中。 24 6.线性支持向量机（线性SV0 6.线性支持向量机（线性SVM0 口线性可分情形下的最优分类面 口线性可分情形下的最优分类面 ·denotes+1 ·denotes+1 。denotes-1 。denotes-l 线性分类器/分类面的边 界距离(margin,分类间 隔)：通过各类中距离分 最优分类面：边界距离/ 类面最近的样本且平行 分类间隔最大的线性分 类面。 于分类面的两个超平面 一最简单的SVM,LSVM 之间的距离

19 6. 线性支持向量机 (线性SVM)  SVM 的理论基础  “推广能力”是指: 将学习机器（即预测函数,或称 学习函数、学习模型）对未来输出进行正确预测 的能力。  “过学习问题”：某些情况下，当训练误差过小反 而会导致推广能力的下降。  例如：对一组训练样本 (x,y), x 分布在实数范围 内, y 取值在 [0，1] 之间。无论这些样本是由 什么模型产生的，我们总可以用 y=sin(w*x)去拟 合，使得训练误差为0。 20 6. 线性支持向量机 (线性SVM)  支持向量机 (SVM)  根据统计学习理论，学习机器的实际风险由经验 风险值和置信范围值两部分组成。而基于经验风 险最小化准则的学习方法只强调了训练样本的经 验风险最小误差，没有最小化置信范围值，因此 其推广能力较差。  Vapnik 提出的支持向量机以训练误差作为优化问 题的约束条件，以置信范围值最小化作为优化目 标，即 SVM 是一种基于结构风险最小化准则的 学习方法，其推广能力明显优于一些传统的学习 方法。 21 6. 线性支持向量机 (线性SVM)  支持向量机 (SVM)  形成时期在1992—1995年；  最优化准则是类间边界距离，故也被称为最大边 界距离分类器；  由于 SVM 的求解最后转化成线性约束的二次规 划问题的求解，因此 SVM 的解是全局唯一的最 优解；  SVM 在解决小样本、非线性及高维模式识别问 题中表现出许多特有的优势，并能够推广应用到 函数拟合等其他机器学习问题中。 22 6. 线性支持向量机 (线性SVM)  线性可分情形下的最优分类面(optimal hyperplane) denotes +1 denotes -1 问题：哪个分 类面最好？ 23 6. 线性支持向量机 (线性SVM)  线性可分情形下的最优分类面 denotes +1 denotes -1 线性分类器/分类面的边 界距离 (margin，分类间 隔)：通过各类中距离分 类面最近的样本且平行 于分类面的两个超平面 之间的距离。 24 6. 线性支持向量机 (线性SVM)  线性可分情形下的最优分类面 denotes +1 denotes -1 最优分类面：边界距离/ 分类间隔最大的线性分 类面。 —最简单的SVM, LSVM

6.线性支持向量机（线性SV④ 6.线性支持向量机（线性SVM 口线性可分情形下的最优分类面 口数学表示 ·denotes+1 ■训练数据的集合： 。denotes-1 (k,片(2,2…，（kw,yw月 x,∈，y∈{-1，}→ y=1表示x,∈0 y=-1表示x,∈2 支持向量(support vector):各类中距 ■分类超平面： 离分割平面最近的 wx+0,=0, 样本。 ■决策函数： f(x)=sgn(w'x+@o). 6.线性支持向量机（线性SVM 6.线性支持向量机（线性SVM) 口样本到分类超平面的距离 口样本X到分类超平面的距离必须满足 r=8) y8≥b,b>0, wll 证明：令，+问则有 口问题：分类超平面的参数可以增大或缩小任意正 的尺度而不影响分类结果中无数多解。 g(x)=w" ,+=m,++ ww w 口解决方策：不妨把距离分类面最近样本的决 策函数值归一化为1，即 =8(x)+r w w =0 (where 6.线性支持向量机（线性SV0 6.线性支持向量机（线性SV 口几何描述 口线性可分情形，求解最优分类面 (wx)+b=+ ■就是在线性可分的情况下，要求分类线不但能将 x(wx)+b=+1 (w.x)+b=-1 两类无错误的分开，而且要使得两类的边界距离 {x1(wx)+b=-1升 => (w(x1-x》=2 最大。 (高品 Primal form: ◆ maximize margin =-1 minwf: S.t [(w-x)+b=0) correct classification y(w'x,+o)21,i=1,…,N margin=2/w=2/(w·w) 二次规划问题 等号成立的点一支持向量

25 6. 线性支持向量机 (线性SVM)  线性可分情形下的最优分类面 denotes +1 denotes -1 支持向量(support vector)：各类中距 离分割平面最近的 样本。 26 6. 线性支持向量机 (线性SVM)  数学表示  训练数据的集合：  分类超平面：  决策函数：      ； 表示 表示             2 1 1 1 2 2 1 1 , { 1,1} , , , , , , ,   i i i i i d i N N y y y y y y x x x x x  x 0 0; T w x      0 ( ) sgn . T f x wx   27 6. 线性支持向量机 (线性SVM)  样本到分类超平面的距离  证明：令 则有 ( ); g r  x w , p   r w x x w 0 0 2 ( ) () . T T T p p p gr r g r r               w ww x w x wx w w w x w w =0 28 6. 线性支持向量机 (线性SVM)  样本 xi 到分类超平面的距离必须满足  问题：分类超平面的参数可以增大或缩小任意正 的尺度而不影响分类结果  无数多解。  解决方案：不妨把距离分类面最近样本的决 策函数值归一化为1，即 ( ) , 0; || || i i y g   b b x w 1 ( ) 1, 1, , (where ). || || i i yg i N b x   w  29 6. 线性支持向量机 (线性SVM)  几何描述 30 6. 线性支持向量机 (线性SVM)  线性可分情形，求解最优分类面  就是在线性可分的情况下，要求分类线不但能将 两类无错误的分开，而且要使得两类的边界距离 最大。 2 0 : 1 maximize margin min ; 2 . . correct classificat Primal form ion ( ) 1, 1, , ; T i i s t y iN      w w x  二次规划问题 等号成立的点—支持向量

6.线性支持向量机（线性SV① 6.线性支持向量机（线性SVM) 口线性可分情形，求解最优分类面 口线性可分情形， 求法向登是样本 的线性组合！ 。利用Lagrange乘子法 ■根据Karush-Kuhn-Tucker(KKT)条件，函数LO 存在最优解的充分必要条件： m,a,a=wf-立a(wx+a)-a,≥0 oL(w,@o:a) w-2ax=0→=x ow we seek to .minimize L()w.r.t w and 2 (w,0@=-立ay=0 只有（很少） 00 -部分的a maximize L()w.r.t.a; 3. y,(w'x+0)-120,i=L,…,N; 不为零，它 们对应的样 a,20,i; 本就是支持 5. a,(y,(w'x+a)-)=0,i 向量SV). 6.线性支持向量机（线性SVM①） 6.线性支持向量机（线性SVM 口线性可分情形，求解最优分类面 口线性可分情形，求解最优分类面 ■几何意义：超平面法向量是支持向量的线性组合 立ay=0带入函数0，则有 Support Vectors i:a(y(wx+)-l)=0 Dual form: w:x+0 =0 for non-support vectors max (a)= g≠for support vectors ial jal W=点awH S.I. 立4=0 g20,i=1,…,N; Decision boundary is determined only by those wx+%=- support vectors! 二次规划问题 26 6.线性支持向量机（线性SV0 6.线性支持向量机（线性SV 口线性可分情形，求解最优分类面 口线性可分情形，求解最优分类面 ■假设a,i=l,N是上述二次规划问题的解，则有 ■判别函数 ∑ayx f(x)=sgn(w"x+@) SV是所有支 can be obtained from 持向量的集合 = sgn 三+a a(y(w'x,+@p)-1)=O,Vx,ESV; 口只包含待分类样本与训练样本中的支持向量的内 or 积运算，可见要解决一个特征空间中的最优线性 分类问题，只需要知道这个空间中的内积运算即 可

31 6. 线性支持向量机 (线性SVM)  线性可分情形，求解最优分类面  利用 Lagrange 乘子法 2 0 0 1 0 1 ( , , ) || || [ ( ) 1], 0; 2 we seek to minimize () w.r.t and ; maximize () w.r.t. ; N T ii i i i i L y L L              w w wx  w 32 6. 线性支持向量机 (线性SVM)  线性可分情形，求解最优分类面  根据 Karush-Kuhn-Tucker (KKT) 条件，函数 L() 存在最优解的充分必要条件：   0 1 1 0 0 1 0 0 (, ,) 1. 0 ; (, ,) 2. 0; 3. ( ) 1 0, 1, , ; 4. 0, ; 5. ( ) 1 0, . N N iii iii i i N i i i T i i i T ii i L y y L y y iN i y i                                     w w xw x w w w x w x  法向量是样本 的线性组合！ 只有(很少) 一部分的αi 不为零，它 们对应的样 本就是支持 向量(SV)。 33 6. 线性支持向量机 (线性SVM)  线性可分情形，求解最优分类面  几何意义：超平面法向量是支持向量的线性组合。 Decision boundary is determined only by those support vectors ! k αkkk y   x w x SV    i y : 10   ii i  w x 0   i = 0 for non-support vectors i  0 for support vectors Support Vectors w 0 w x   1 0 w x    1 34 6. 线性支持向量机 (线性SVM)  线性可分情形，求解最优分类面  将 带入函数 L() ，则有 1 1 , 0 N N iii ii i i   y y   w x     1 11 1 : 1 max ( ) , 2 0, . . 0, 1 Dual for ; m , , N NN T D i i ji ji j i ij N i i i i L yy y s t i N                  x x  二次规划问题 35 6. 线性支持向量机 (线性SVM)  线性可分情形，求解最优分类面  假设 是上述二次规划问题的解，则有 i ,i 1, , N 0   *0 0 1 ; i N i ii i ii i   y y      x wx x SV   * 0 0 * 0 * 0 can be obtained from ( ) 1 0, ; or . i i T ii i i T i i y N y               x x wx x w x sv SV SV SV SV 是所有支 持向量的集合 36 6. 线性支持向量机 (线性SVM)  线性可分情形，求解最优分类面  判别函数 只包含待分类样本与训练样本中的支持向量的内 积 运算，可见要解决一个特征空间中的最优线性 分类问题，只需要知道这个空间中的内积运算即 可。     * * 0 0 * 0 1 ( ) sgn sgn . T N i i i i T f y                x x x x w