模式識(shí)別專項(xiàng)培訓(xùn)

1、School of Electronic Information Engineering , Tianjin University模式識(shí)別 概論 決策函數(shù)支持向量機(jī)School of Electronic Information Engineering , Tianjin University模式（模式（patternpattern）：）：意指供模仿用的完美無(wú)缺的標(biāo)本。模式識(shí)別：模式識(shí)別：識(shí)別出給定的事物與那一個(gè)標(biāo)本相同或相近。模式分類(lèi)：模式分類(lèi)：把供模仿的標(biāo)本分成若干類(lèi)，再判斷給定的 事物屬于那一類(lèi)。例如：文字識(shí)別，疾病診斷，-1.1 模式與模式模式與模式School of Electron

2、ic Information Engineering , Tianjin University 模式識(shí)別通常表示為對(duì)一組過(guò)程或事件的判別或分類(lèi)。 模式識(shí)別研究的中心問(wèn)題：模擬大腦的思維過(guò)程，實(shí)現(xiàn)腦力勞動(dòng)自動(dòng)化。模式識(shí)別屬于人工智能的研究范疇。 人機(jī)互補(bǔ)，人機(jī)對(duì)話，交互式模式識(shí)別。School of Electronic Information Engineering , Tianjin University 有監(jiān)督的模式識(shí)別：有監(jiān)督的模式識(shí)別：除了待識(shí)別樣本外，還提供已經(jīng)類(lèi)別 樣本集（訓(xùn)練樣本集），用來(lái)先行訓(xùn) 練計(jì)算機(jī)，使之積累經(jīng)驗(yàn)，獲得識(shí)別 能力，再對(duì)未知樣本識(shí)別、分類(lèi)。無(wú)監(jiān)督的模式識(shí)別：無(wú)

3、監(jiān)督的模式識(shí)別：無(wú)訓(xùn)練樣本。采用集群（聚類(lèi)）分析1.2 模式識(shí)別的兩種情況School of Electronic Information Engineering , Tianjin University1.3 識(shí)別錯(cuò)誤率分類(lèi)結(jié)果與一定的錯(cuò)誤率相聯(lián)系。錯(cuò)誤率估計(jì)。分類(lèi)結(jié)果與一定的錯(cuò)誤率相聯(lián)系。錯(cuò)誤率估計(jì)。1.4 模式識(shí)別系統(tǒng)數(shù)據(jù)獲取數(shù)據(jù)獲取預(yù)處理預(yù)處理特征抽取特征抽取特征選擇特征選擇決策分類(lèi)決策分類(lèi)School of Electronic Information Engineering , Tianjin University特征抽?。禾卣鞒槿。喊岩粋€(gè)物理模式變成一個(gè)隨機(jī)向量，如抽取 了m個(gè)特

4、征，則構(gòu)成m維向量),(21mxxxX 特征選擇：特征選擇：把m維特征向量經(jīng)數(shù)學(xué)變換壓縮為n維向量Y， ),(21nyyyY mn 決策分類(lèi)：決策分類(lèi)：找出決策函數(shù) 若已知待識(shí)別樣本完整的先驗(yàn)知識(shí)，則可據(jù)此確定決策函數(shù)的數(shù)學(xué)表達(dá)式；若僅知待識(shí)別樣本的定性知識(shí)，則在確定決策函數(shù)時(shí)，須經(jīng)過(guò)學(xué)習(xí)（訓(xùn)練）、調(diào)整過(guò)程。School of Electronic Information Engineering , Tianjin University統(tǒng)計(jì)模式識(shí)別：統(tǒng)計(jì)模式識(shí)別：用特征向量表示模式，用決策函數(shù)進(jìn) 行分類(lèi)。句法模式識(shí)別：句法模式識(shí)別：把模式與語(yǔ)言中的句子類(lèi)比，借鑒語(yǔ) 言中句子的構(gòu)成、產(chǎn)生及識(shí)別，

5、用于 模式的處理。1.5 模式識(shí)別的理論和方法School of Electronic Information Engineering , Tianjin University成員花名冊(cè)概念（模板匹配）共性概念（特征匹配）集群（聚類(lèi)）概念（最下距離 ）三種設(shè)計(jì)思想三種設(shè)計(jì)思想：School of Electronic Information Engineering , Tianjin University三種方法：三種方法：?jiǎn)l(fā)式方法：基于人的直觀和經(jīng)驗(yàn)。對(duì)專門(mén)的識(shí)別任務(wù)導(dǎo)出特定的方法，很少有廣義化的原理。取決于設(shè)計(jì)者的聰明和經(jīng)驗(yàn)。數(shù)學(xué)的方法：依數(shù)學(xué)骨架導(dǎo)出，構(gòu)成特定的規(guī)則。語(yǔ)言的方法；句法識(shí)

6、別。School of Electronic Information Engineering , Tianjin University第二章 決策函數(shù)2.1 用決策函數(shù)實(shí)現(xiàn)模式識(shí)別 模式識(shí)別系統(tǒng)為實(shí)現(xiàn)模式識(shí)別和分類(lèi)必須建立規(guī)則，決策函數(shù)是解決該問(wèn)題的重要方法之一。School of Electronic Information Engineering , Tianjin University圖2.1 兩類(lèi)模式識(shí)別的簡(jiǎn)單決策函數(shù)0)(32211wxwxwd X21, xx321,www分界線方程： 式中： （廣義）坐標(biāo)變量 權(quán)參數(shù)（2-1）0)(Xd0)(Xd 任一模式，若屬于1，則；若屬于2，

7、則School of Electronic Information Engineering , Tianjin University)(Xd)(Xd決策函數(shù)的概念不僅限于上述兩維、兩類(lèi)、線性邊界 的情況，可以擴(kuò)展到多維、多類(lèi)、非線性邊界的一般情況。 的構(gòu)成（形式與系數(shù)）；的能力。 1.2.人們確定 上述模式分類(lèi)方案成功與否取決于兩個(gè)因素：School of Electronic Information Engineering , Tianjin University2.2 線性決策函數(shù) 1T012211)(nnnnwwxwxwxwdXWX(2-2)其中 T210),(nwwwW權(quán)向量 由式（2

8、-1）容易推廣到n維情況 School of Electronic Information Engineering , Tianjin University 為方便，式（2-2）改寫(xiě)為 XWXT)(d（2-3）其中， T21) 1 ,(nxxxX 增廣模式 T121),(nnwwwwW 增廣權(quán)向量 兩類(lèi)情況下的決策規(guī)則：21T,0,0)(XXXWX若若d （2-4）School of Electronic Information Engineering , Tianjin University情況1：每一類(lèi)模式可用一個(gè)簡(jiǎn)單決策面同另外的所有 模式類(lèi)別分開(kāi)，M類(lèi)模式有M個(gè)決策函數(shù)，并有多類(lèi)問(wèn)題的

9、決策規(guī)則可由兩類(lèi)問(wèn)題決策方法導(dǎo)出：否則若,0,0)(TiiidXXWXM, 2 , 1 i（2-5） 其中 T1,21),(niniiiiwwwwW第i個(gè)決策函數(shù)的權(quán)向量 School of Electronic Information Engineering , Tianjin University情況2：每一類(lèi)與其他類(lèi)由不同的決策面單個(gè)地分開(kāi)，即類(lèi)別間成對(duì)可分，共有2/)1(MM個(gè)決策界面。決策函數(shù)形式為XWXT)(jijid決策規(guī)則：若 iX則 ijdji,0（2-6） 特性： )()(XXi jj iddSchool of Electronic Information Engineer

10、ing , Tianjin University情況3：M類(lèi)有M個(gè)決策函數(shù) XWXTkkd)(M,2, 1k決策規(guī)則：若 iX則ijddji,)()(XX（2-7） School of Electronic Information Engineering , Tianjin University2.3 廣義線性決策函數(shù)非線性決策函數(shù)可由線性決策函數(shù)的概念推廣到下列形式得到 )()()()()(112211XXXXXkkkkfwfwfwfwd)(11Xikiifw（2-8） 式中 kifi, 2 , 1,)(X是模式X的單值實(shí)函數(shù)， 1)(1XkfSchool of Electronic Inf

11、ormation Engineering , Tianjin University)(Xif取決于函數(shù) 的選擇和表達(dá)式的項(xiàng)數(shù)，上式可以代表決策函數(shù)的無(wú)限變化。但總可以通過(guò)直觀的變換將這些函數(shù)當(dāng)作線性的。為此，定義矢量 （2-9）T211)()()(XXXYkfff此時(shí)決策函數(shù)可表示為YWYTd)(（2-10） 其中， T121),(kkwwwwWSchool of Electronic Information Engineering , Tianjin Universitykifi, 2 , 1,)(X一旦進(jìn)行計(jì)算， 就是一組數(shù)值，Y是一個(gè)簡(jiǎn)單的 維矢量，式 （2-10）代表對(duì)新的模式Y(jié)的一個(gè)

12、線性決策函數(shù)。式（2-8）表示了任意的決策函數(shù)，其可用式（2-10）當(dāng)作線性表示，因此我們可以限于討論線性決策函數(shù)而不失普遍性。 1k需說(shuō)明，如果X是n維的，Y是k維的，k可能顯著大于n。例：若非線性決策函數(shù)為1)(2413222211xwxwxwxwd X令 T212221T54321) 1()(xxxxyyyyyY則 1)()(44332211ywywywywddTYWYXSchool of Electronic Information Engineering , Tianjin University支持向量機(jī)支持向量機(jī)兩類(lèi)、線性可分離情況兩類(lèi)、線性可分離情況 訓(xùn)練集： 21, 2 , 1

13、,:iiXNiXX 目標(biāo)：設(shè)計(jì)一超平面0)(0TwgXWX （3-59） 其應(yīng)能將全部訓(xùn)練矢量正確分類(lèi)。這種超平面不是唯一的，訓(xùn)練算法（例如感知算法）可以收斂到任一可能的解。圖3-7畫(huà)出兩個(gè)可能的超平面。 School of Electronic Information Engineering , Tianjin University圖3-7 具有兩個(gè)可能的線性分類(lèi)器的線性可分兩類(lèi)問(wèn)題的例子顯然，實(shí)線畫(huà)的那個(gè)更好。因?yàn)閷?shí)際應(yīng)用中還需對(duì)訓(xùn)練集之外的樣本分類(lèi)。實(shí)線所畫(huà)的超平面的兩邊都留出了較大空間，兩類(lèi)樣本可以有多一些移動(dòng)自由，而較小錯(cuò)分風(fēng)險(xiǎn)。此處所涉及的是分類(lèi)器設(shè)計(jì)中的一個(gè)重要問(wèn)題分類(lèi)器的廣義化

14、性能。School of Electronic Information Engineering , Tianjin University由上討論知，選擇分類(lèi)器的原則是超平面分類(lèi)器要對(duì)兩類(lèi)留出最大的邊緣裕量(margin)。 每一個(gè)超平面由其方向（由W決定）和空間嚴(yán)格位 置（由w0決定）表征。因?yàn)閷?duì)于兩類(lèi)模式同等對(duì)待，所以，對(duì)每一個(gè)方向所選擇的超平面，都要求其距 中的最近點(diǎn)等距離，如圖3-8所示。我們的任務(wù)是尋找出能給出邊緣裕量最大的超平面方向。 21 和邊緣裕量的定量表示邊緣裕量的定量表示：School of Electronic Information Engineering , Tianj

15、in University圖3-8 方向2的邊緣裕量大于方向1 如圖所示，邊緣裕量等于2Z。由解析幾何可證，樣本“點(diǎn)”X至超平面的距離為WX )(gZ為規(guī)范化W和w0，令 中最近點(diǎn)的 ； 中最近點(diǎn)的 School of Electronic Information Engineering , Tianjin University11)(Xg21)(Xg這就相當(dāng)于：給定邊緣裕量 WWW2112. 要求 T01T021,1,wwW XXW XX對(duì)于樣本 ，引用符號(hào) 表示所屬類(lèi)別： iXiy21,1,1iiiyXX 我們的任務(wù)歸結(jié)為極小化 221)(WW J （3-60） 約束條件 1)(0T wy

16、iiXWNi, 2 , 1（3-61） School of Electronic Information Engineering , Tianjin University這是一個(gè)在線性不等式約束條件下的非線性（二次）優(yōu)化問(wèn)題。依Karuch-Kuhn-Tucker(KKT)條件，這要求滿足0),(0WWwL（3-63）00(, )0LwwWNii, 2 , 1,0010,1,2,Tiiiy W XwiN（3-62） （3-64） （3-65） School of Electronic Information Engineering , Tianjin University由式（3-66）、（3

17、-62）、（3-63）得Niiiiy1XW01iNiiy（3-67） （3-68） T0011(, )12NTiiiiL W wywW WW X（3-66） 其中， 為拉格郎日乘子矢量，L為拉格郎日函數(shù)，定義為T(mén)21),(NSchool of Electronic Information Engineering , Tianjin UniversityRemarks: 拉格郎日乘子可為0或正，權(quán)向量最優(yōu)解W為與 0i相聯(lián)系的 NNS個(gè)模式向量的線性組合 SNiiiiy1XW （3-69） 這些模式向量稱為支持向量支持向量，最優(yōu)超平面分類(lèi)器稱為支持向支持向量機(jī)量機(jī)。如約束條件（3-65）表示的，

18、與 相聯(lián)系的支持向量處在兩個(gè)超平面T01w W X（3-70） 其中之一的上面，即它們是最接近線性分類(lèi)器的訓(xùn)練向量，它們構(gòu)成了訓(xùn)練集中最苛刻的元素。0iSchool of Electronic Information Engineering , Tianjin University W由式（3-67）得到，而w0可由式（3-65）中的任 一約束條件得到，實(shí)際中，可由這些約束條件得出的平均值得到。式（3-60）的代價(jià)函數(shù)是嚴(yán)格的凸函數(shù)，而不等式約束由線性函數(shù)組成?？勺C，由這兩個(gè)條件保證，任何局部最小也是全局最小和唯一的，故支持向量機(jī)的最優(yōu)超平面分類(lèi)器是唯一的。如何計(jì)算？如何計(jì)算？School o

19、f Electronic Information Engineering , Tianjin University上述問(wèn)題的計(jì)算經(jīng)常不是一個(gè)很容易解決的任務(wù)，存在很多算法減少計(jì)算困難。其中涉及一些博弈論和數(shù)學(xué)規(guī)劃方面的知識(shí)。因式（3-60）的代價(jià)函數(shù)是嚴(yán)格的凸函數(shù)，而不等式（3-61）由線性函數(shù)組成，故這個(gè)問(wèn)題屬凸規(guī)劃問(wèn)題。這種問(wèn)題可利用所謂拉格郎日對(duì)偶性來(lái)解決。上述問(wèn)題可以等效于它的Wolfe對(duì)偶表示，即最大化 約束條件 0(, )LwWNiiiiy1XWNiiiy100（3-71） （3-72） （3-73） （3-74） School of Electronic Information

20、Engineering , Tianjin University式（3-72），（3-73）是式（3-71）對(duì)W和w0求導(dǎo)數(shù)取0的結(jié)果。將式（3-72），（3-73）代入式（3-71）得Nijijijijiiyy1,T21maxXX（3-75） 約束條件 Niiiy100（3-76）（3-77） 一旦通過(guò)最大化式（3-75）得到最優(yōu)拉格郎日乘子，就可由式（3-72）得到最優(yōu)超平面，w0同前由約束條件得到。 School of Electronic Information Engineering , Tianjin University例例：圖3-10二類(lèi)分類(lèi)問(wèn)題圖3-10 二類(lèi)分類(lèi) TTTT)

21、 1, 1(,) 1 , 1(:) 1, 1 (,) 1 , 1 (:21School of Electronic Information Engineering , Tianjin University由圖可以直觀看到，最優(yōu)超平面為其可由拉格朗日乘子的不同組合得到。 01x0)(02211wxwxwg X1,0102www0)(1 xg X因?yàn)樗?個(gè)點(diǎn)都成為支持向量，分割線至兩類(lèi)的margin都等于1。對(duì)于任何其他向量，例如 ， margin都小于1。 0)(1XgSchool of Electronic Information Engineering , Tianjin Universi

22、ty由由KKT條件求解條件求解:最小化 2)(2221wwJW線性不等式約束： 01021www01021www01021www01021www拉格朗日函數(shù)：) 1() 1() 1() 1(2),(02140213021202112221012wwwwwwwwwwwwwwwwwLSchool of Electronic Information Engineering , Tianjin UniversityKKT條件：4321110wwL3241220wwL0043210wL0) 1(0211www(3-94) (3-95) (3-96) (3-97) School of Electronic Inform