模式識別第二章線性分類器

1、第二章 線性分類器一、 判別函數(shù)1、 決策論方法在模式識別中，如果根據(jù)模式特息，按照決策論的思路，以一定的數(shù)量規(guī)則來采取不同的分類決策， 將待識別的模式劃分到不同的類別中去，就稱為模式識別的決策論方法。在決策論方法中，特征空間被劃分成不同的區(qū)域，每個區(qū)域?qū)?yīng)一個模式類，稱為決策區(qū)域（DeciRegion）。當(dāng)判定待識別的模式位于某個決策區(qū)域時，就它可以劃歸到對應(yīng)的類別中。圖 1 決策區(qū)域需要注意的是：決策區(qū)域包含模式類中樣本的分布區(qū)域，但不等于模式類的真實(shí)分布范圍。2、 判別函數(shù)如果特征空間中的決策區(qū)域邊界（DeciGi ( x) 0Boundary）可以用一組方程來表示，則將一個模式對應(yīng)的特

2、征向量 x 代入邊界方程中的 Gi ( x) ，確定其正負(fù)符號，就可以確定該模式位于決策區(qū)域邊界的哪一邊，從而可以判別其應(yīng)當(dāng)屬于的類別， Gi ( x) 稱為判別函數(shù)（Discriminant Function）。判別函數(shù)的形式可以是線性的（ Linear）或非線性（第 1 頁-linear） 的。例如圖 2 就顯示了一個非線性判別函數(shù)，當(dāng) G(x)0 時，可判別模式 x1；當(dāng) G(x)0 且 G13(x)0 時，x2；當(dāng) G13(x)0 且 G21(x)0 時，x3；當(dāng) G21(x)0 時，x1；當(dāng) G21(x)0 且 G13(x)0 時，可判別模式 x1；當(dāng) G(x)0，可判別 x1；若

3、G(x)0TFFTTFFG2(x)0FTFTFTFG3(x)0FFTFTTF分類決策x 1x 2x 3IR1IR2IR3IR4此時分類決策規(guī)則可以用判定表表示為：兩兩可分的分類不確定區(qū)域減少，但至少需要進(jìn)行 2 次判別才能確定模式的類別劃分。（3） 最大值可分如果每個模式類都對應(yīng)有一個判別函數(shù)，一個模式被劃歸到判別函數(shù)值最大的那個模式類中，就稱為最大值可分。此時若有 m 個模式類，就有m 個判別函數(shù)。圖 11 多類問題最大值可分顯然，最大值可分是兩兩可分的特殊情況。此時的分類決策規(guī)則為：x k ,當(dāng)Gk x maxGi (x)1im3、 線性判別函數(shù)的幾何意義當(dāng)一個模式位于線性決策邊界上時，該

4、模式與決策邊界的距離為 0，對應(yīng)的判別函數(shù)值也為 0。直觀地可以發(fā)現(xiàn)，當(dāng)一個模式距離決策邊界越遠(yuǎn)時，判別函數(shù)的絕對值也應(yīng)當(dāng)越大，也就是說判別函數(shù)是模式到?jīng)Q策超平面距離遠(yuǎn)近的一種度量。那么判別函數(shù)的幾何意義究竟如何呢？下面以二類問題為例來進(jìn)行分析。如果判別函數(shù) G x 可以將兩類分開，則決策邊界方程為： G x w x w 0T0設(shè)模式 x 距離決策邊界的距離為r ，則向量 x 可以表示為其在決策邊界上的w投影點(diǎn)所代表的向量 x 和向量r的和，即p第 7 頁wG12(x)0TF*FG23(x)0*TFFG31(x)0F*TF分類決策x 1x 2x 3IRwx x rp圖 12 線性判別函數(shù)的幾何

5、意義代入判別函數(shù)中，得wT wwG x wx w0 w ( xp r) w0 w xp w0 r rTTTw所以r G x w由此可見，模式 x 到?jīng)Q策邊界的距離正比于判別函數(shù)值，判別函數(shù)的符號代表了距離r 的符號，表示該模式位于決策邊界的正側(cè)還是負(fù)側(cè)。更一般的情況，權(quán)向量w 僅代表決策超平面的法線方向，其長度不會影響決 1，此時的判別函數(shù)值就是模式到策邊界在特征空間中的位置，完全可以取w決策邊界的距離。思考：此時的判別函數(shù)與原判別函數(shù)相比區(qū)別嗎？三、 線性分類器設(shè)計（DLC， Design of Linear Classifier）1、 線性分類器設(shè)計思路（1） 設(shè)計目標(biāo)對于任意兩個類之間，

6、都可以使用一個線性判別函數(shù)來進(jìn)行區(qū)分， 決第 8 頁www策邊界方程為： x wT x w 0Gij0其中x n ，即模式對應(yīng)的特征向量Tw= w , w , w T ，稱為權(quán)向量12n將其寫成n+1 維增廣（Augmented）形式，即 x wT xGijx n ,1 ，即n+1 維增廣特征向量Tw= w , w , w , w T ，即n+1 維增廣權(quán)向量12n0此時分類決策規(guī)則為：若Gij j ;如果給定一個分好類的樣本集，則其中每個樣本對應(yīng)的增廣特征向量都是已知的，此時要設(shè)計一個線性分類器可以實(shí)現(xiàn)兩個類的分類決策，就是要求解出一個能使得樣本集內(nèi)所有樣本都能劃分到正確的類別中的增廣權(quán)向量

7、w ，這就是線性分類器的設(shè)計目標(biāo)。（2） 求解條件假設(shè)用于學(xué)習(xí)的樣本集中有 l 個樣本，其中有 li 個屬于i 類，對應(yīng)的特征向量分別為(li ) ；有 l 個屬于 類，對應(yīng)的特征向量分別為jjy(1) , y(2) , y(lj ) 。則增廣權(quán)向量 w 應(yīng)當(dāng)滿足G( x(1) ) wT x(1)0ijG( x(2) ) wT x(2) 0ijG ( x) w x 0(l )T (l ) iiijG( y(1) ) wT y(1) 0ij) w y 0Gij ( y(2)T(2)G( y(lj ) ) wT y(lj ) 0ij當(dāng)樣本數(shù) l n 時，該不等式方程組為不定的，沒有有意義的解；當(dāng)樣

8、本 l n 時，該不等式方程組為適定或超定的，有無窮多個解，但是這些解有一定的分布區(qū)域，稱為解區(qū)域。第 9 頁圖 13 線性分類器設(shè)計的解區(qū)域如果i 和j 兩類線性不可分，則解區(qū)域不存在。思考：增廣權(quán)向量有幾個未知數(shù)？至少需要幾個樣本才能求解？（3） 設(shè)計思路如果用于學(xué)習(xí)的訓(xùn)練樣本集是線性可分的，則一定有無窮多個解向量 w滿足判別函數(shù)不等式方程組，設(shè)計出的線性分類器也有無窮多個，因此，求取線性分類器的設(shè)計結(jié)果一定是一個尋找最優(yōu)解的過程。一般設(shè)計思路是：a、 設(shè)定一個標(biāo)量函數(shù) J (w) 為準(zhǔn)則函數(shù)（Criterion Function）；b、 使準(zhǔn)則函數(shù) J (w) 取得極小值的增廣權(quán)向量w

9、，就是最優(yōu)解；由于準(zhǔn)則函數(shù) J (w) 求極值一般無法直接依據(jù)J (w) 0 獲得解，只能設(shè)w計一個逐步 近的算法來根據(jù)訓(xùn)練集求取最優(yōu)增廣權(quán)向量w 。（4） 梯度法梯度法（Gradient Method）是傳統(tǒng)的求極小值算法之一，它是從一個初始的權(quán)向量 w(0) 出發(fā)，在每一遞推中沿當(dāng)前準(zhǔn)則函數(shù) J (w) 的負(fù)梯度方向前進(jìn)一步，對權(quán)向量進(jìn)行修正（Amend），逐步減小準(zhǔn)則函數(shù)的值，直至其取得最小值，或近似取得最小值為止，即在第k 1 步遞推中w(k 1) w(k ) (k 1)J (w(k)第 10 頁其中J (w(k) 是準(zhǔn)則函數(shù) J (w) 在w(k) 處的梯度值。因?yàn)榻饪臻g中每一點(diǎn)的負(fù)

10、梯度方向就是準(zhǔn)則函數(shù)值減少最快的方向，因此梯度法又稱為“最速下降法”。梯度法中 (k 1) 0 是第k 1 步遞推時對權(quán)向量的修正步長（Step-length）。(k 1) 取值越大，求解的速度越快，但求解精度越差，容易過沖甚至振蕩；(k 1) 取值越小，求解的速度越慢，但求解精度越高。2、 感知器法（1） 感知器模型感知器（Perceptron）是計算機(jī)科學(xué)家（F. Rosenblatt）狀態(tài)，是對多個輸入量加在 1957 年神經(jīng)元模型，它沒有反饋和權(quán)求和后決定輸出的值。圖 14 感知器模型感知器輸出是一個階躍函數(shù)，其輸入輸出關(guān)系為：n( wi xi ) 1,y i1n( wi xi ) 0

11、,i1其中 為輸出閾值。顯然，感知器可以作為兩類的線性分類器。如果已有線性可分的訓(xùn)練樣本集，證明，通過分類錯誤信息調(diào)整權(quán)值的算法，總可以使權(quán)向量收斂到分類錯誤為 0 的最優(yōu)解。（2） 樣本特征向量的規(guī)范化為求解權(quán)向量 w ，需要求解不等式方程組第 11 頁G( x(1) ) wT x(1)0ijG( x(2) ) wT x(2) 0( x(li ) ) wT x(li ) ( y(1) ) wT y(1) 0ij0GijGij(2) w y 0T (2)Gij ( yG( y(lj ) ) wT y(lj ) 0ij該方程組的不等式有兩種形式，不便于處理，因此把屬于j 類的樣本的增廣特征向量取

12、負(fù)號，即得到G ( x(1) ) wT x(1) 0ijG( x(2) ) wT x(2) 0ijG ( x) w x 0(l ) T(l ) iiijG ( y(1) ) wT y(1)0ij) w y 0(2)T (2)Gij ( yG( y(lj ) ) wT y(lj ) 0ij此時可用的形式G ( x) wT x 0ij來表示判別函數(shù)對所有訓(xùn)練樣本集中的樣本的取值條件，只是其中屬于j類的樣本對應(yīng)的增廣特征向量每一分量都為原始值的負(fù)值。這一過程稱為樣本特征向量的“規(guī)范化（Normalization）”。（3） 感知器算法感知器算法（PA, Perceptron Algorithm）采用

13、梯度法來求取權(quán)向量的最優(yōu)值。其準(zhǔn)則函數(shù)定義為：-wT x J (w) xX0其中 X 0 是規(guī)范化后的樣本集中分類錯誤的子集。當(dāng)存在錯分樣本時，J (w) 0 ；當(dāng)不存在錯分樣本時， J (w) 0 ，取得極小值，此時的權(quán)向量 w 就是最優(yōu)解。根據(jù)梯度法，每一步遞推時的權(quán)向量都由前一步的權(quán)向量向當(dāng)前準(zhǔn)則函數(shù)J (w) 的負(fù)梯度方向修正得到，即w(k 1) w(k ) (k 1)J (w(k)而第 12 頁J (w(k) ( J (w(k) , J (w(k ) , J (w(k ) , J (w(k ) ) -x w1w1wnw0 xX0即等于規(guī)范化后的錯分樣本特征向量取負(fù)號后之和，則w(k

14、1) w(k) (k 1)xxX0這就是感知器算法的遞推公式。感知器算法的具體步驟為：設(shè)定初始權(quán)向量 w(0) ， k 0 ；對訓(xùn)練樣本集的所有規(guī)范化增廣特征向量進(jìn)行分類，將分類錯誤a、b、的樣本（即不滿足 G ( x) wT x 0 的樣本）放入集合 X 中；ij0修正權(quán)向量： w(k 1) w(k) (k 1)c、xxX0k k 1，返回步驟b，直至所有樣本都能被正確分類為止。d、也可采取單樣本修正的算法，步驟為：設(shè)定初始權(quán)向量 w(0) ， k 0 ；從訓(xùn)練樣本集中順序抽取一個樣本，將其規(guī)范化增廣特征向量 x代入到判別函數(shù)中計算；a、b、若分類正確（即 G ( x) wT x 0 ）返回

15、到步驟b，抽取下一個樣本；c、ij若分類錯誤（即不滿足 G ( x) wT x 0 ），修正權(quán)向量：d、ijw(k 1) w(k) (k 1) x返回到步驟b，抽取下一個樣本；直至訓(xùn)練樣本集中所有樣本均被正確分類。e、（4） (k 1) 的選擇感知器算法中遞推步長 (k 1) 決定了每次對權(quán)向量修正的幅度，它的大小會影響權(quán)向量求解的速度和精度。一般 (k 1) 的選擇有以下一些方式：固定值即 (k 1) 選擇固定的非負(fù)數(shù)；絕對修正在單樣本修正算法中，為保證分類錯誤的樣本在對權(quán)向量進(jìn)行一次第 13 頁修正后能正確分類，需要滿足wT (k 1) x 0w(k 1) w(k) (k 1) x ，得代

16、入遞推修正公式wT (k 1) x wT (k)0即(k 1) xT x滿足該條件的 (k 1) 稱為絕對修正因子。部分修正若取(k 1) ,0 2xT x則稱為部分修正。變步長法可以取按照某種規(guī)律逐步減少的 (k 1) ，使得算法開始時收斂較快，接近最優(yōu)解時收斂速度變慢，以提高求解的精度。比較常用的變步長法是取(k 1) 1 , 0k最優(yōu)步長法在每一步時，通過求準(zhǔn)則函數(shù) J (w(k 1) 對于不同的 (k 1) 可以取得的最小值，來確定最優(yōu)的 (k 1) 。該方法在于：相比采用小步長帶來的遞推次數(shù)增加，每步求最優(yōu)步長會帶來更大的計算量。感知器法例題一：有 4 個訓(xùn)練樣本如下：1 類: (0

17、,0)T，(0,1)T2 類: (1,0)T，(1,1)T用感知器算法求其判別函數(shù)。解：樣本的規(guī)范化增廣特征向量為X(1)=(0,0,1)T，X(2)=(0,1,1)T，X(3)=(-1,0,-1)T，X(4)=(-1,-1,-1)T， W(0)=(1,1,1)，取 1第 14 頁wT (k ) xwT (k) x 01 1) 0 1X (1W T (0)(1) 1 0 1 1) 1 2 0WT (1X (0)(2) 1 11 1) 0 2 0WT (1X(0)(3) 1W(1)=W(0)+X(3)=(0,1,0)T 1 (010) 1 1 0WT X(1)(4) 1W(2)=W(1)+X(4

18、)=(-1,0,-1)T 0 (101) 0 1 0WTX (2)(1) 1 W(3)=W(2)+X(1)=(-1,0,0)T 0 (100) 1 0WTX (3) (2) 1 W(4)=W(3)+X(2)=(-1,1,1)T 1 (1 1 1) 0 0WTX(4)(3) 1W(5)=W(4)+X(3)=(-2,1,0)T 1 (2 10) 1 1 0WTX(5)(4) 1 0 (2 10) 0 0WTX (5)(1) 1 W(6)=W(5)+X(1)=(-2,1,1)T第 15 頁 0 1 1) 1 2 0X (2WT (6)(2) 1 11 1) 0 1 0WT (2X(6)(3) 1 1

19、1 1) 1 0WT (2X(6)(4) 1W(7)=W(6)+X(4)=(-3,0,0)T 0 (300) 0 0WTX (7)(1) 1 W(8)=W(7)+X(1)=(-3,0,1)T 0 0 1) 1 1 0WT (3X (8) (2) 1 10 1) 0 2 0WT (3X(8) (3) 1101) 1 2 0WT (3X(8) (4)1 0 01) 0 1 0X (3WT (8) (1) 1 解得權(quán)向量為（-3,0,1），決策邊界方程為3x1 1 0第 16 頁圖 15 感知器法例題一感知器法例題二：有 4 個訓(xùn)練樣本如下：1 類: (1,0,1)T，(0,1,1)T2 類: (1

20、,1,0)T，(0,1,0)T用感知器算法求其判別函數(shù)。解：樣本的規(guī)范化增廣特征向量為X(1)=(1,0,1,1)T，X(2)=(0,1,1,1)T，X(3)=(-1,-1,0,-1)T，X(4)=(0,-1,0,-1)T， W(0)=(0,0,0,0)，取 1 1 0 00 0WTX00 1 1 (0)(1) W(1)=W(0)+X(1)=(1,0,1,1)T 0 1 1 2 0 1WT X01 1 1 (1)(2) 1 11 2 0 1WT X0 1 0 (1)(3) 1W(2)=W(1)+X(3)=(0,-1,1,0)T第 17 頁 0 1 00 1 01WTX1 0 (2)(4) 1

21、1 0 00 1 01WTX1 1 1 (2)(1) 0 1 00 01WTX1 1 1 (2)(2) W(3)=W(2)+X(2)=(0,0,2,1)T 1 11 1 0 0WTX020 (3)(3) 1W(4)=W(3)+X(3)=(-1,-1,2,0)T 0 1 10 1 01WTX2 0 (4)(4) 1 1 0 10 1 01WTX2 1 1 (4) (1) 0 1 10 1 01WTX2 1 1 (4)(2) 1 1 10 2 01WTX2 0 (4)(3) 1第 18 頁解得權(quán)向量為（-1,-1,2,0），決策邊界方程為3 0圖 16 感知器法例題二（5） 感知器算法分析感知器算

22、法簡單明了，對線性可分問題收斂性有理論保證，但它以減少錯分樣本為求解目標(biāo)，其最優(yōu)解為無錯分樣本的權(quán)向量，因此該算法存在以下問題：求解結(jié)果落入解區(qū)域中則算法停止，不能在解區(qū)域的所有解中求得最優(yōu)解；求解結(jié)果與初始權(quán)向量、樣本處理順序、遞推步長都有關(guān)系，即求解結(jié)果不確定；對于線性不可分問題無法在允許錯分的情況下求得次優(yōu)解。算法3、（1）線性分類器的松弛求解（Relaxation Solution）對于兩類問題，設(shè)樣本集有 l 個樣本，在對所有樣本的增廣特征向量規(guī)范化后，線性分類器的求解即求滿足線性不等式方程組G ( x(1) ) wT x(1) 0ijG( x(2) ) wT x(2)0ijGij

23、( x) w x 0(l )T (l )的權(quán)向量w ，如該不等式方程組有解，其解為一個區(qū)域，包含無窮多個解。對該不等式方程組松弛化， 任意給定一個裕量向量（ Margin Vector ）b (b , b , b ) ，令T1 2l第 19 頁G ( x(1) ) wT x(1) b 0ij1G ( x(2) ) wT x(2) b 0ij2Gij ( x) w x bl 0(l )T(l ) 則求解線性不等式方程組再令矩陣轉(zhuǎn)化為求解線性方程組。 x(1)T x(2)T X (l )T x上述線性方程組可寫為Xw b當(dāng)訓(xùn)練樣本數(shù)l 小于樣本特征維數(shù)n 時，權(quán)向量 w 有無窮多個解，不存在有意義

24、的類別分界線。當(dāng)l 等于n 時，權(quán)向量 w 也有無窮多個解，但這些解是線性相關(guān)的，其所決定的分類決策邊界均滿足：G (x) wT x 0ij所以，分類決策邊界有精確解（Exact Solution）。當(dāng)訓(xùn)練樣本數(shù)l 大于樣本特征維數(shù) n 時，且方程組中的各方程不是線性相關(guān)的話，則線性方程組是超定的（Over-determined），權(quán)向量 w確解。但是對于此類問題，可采用最小二乘法的方法，求得一個盡可能滿足方程的近似解。（2）最小均方誤差算法設(shè)定誤差向量為： e Xw b2 Xw b 2均方誤差準(zhǔn)則函數(shù)為： J (w) e則當(dāng)均方誤差 J (w) 取得最小值時，所求得的權(quán)向量w 是最優(yōu)的。仍然

25、采用梯度法，權(quán)向量的遞推公式為w(k 1) w(k ) (k 1)J (w(k)因?yàn)閘l ( xw(k) b ) (w (k ) x bi )2J (w(k ) Xw(k ) b(i )T 2T(i)2ii 1i1所以均方誤差準(zhǔn)則函數(shù) J (w) 在w(k) 處的梯度為lliJ (w(k) (w (k ) x b ) 2(w (k ) x b ) x 2XT (Xw(k) b)T(i) 2T(i) (i )ii1i 1所以第 20 頁w(k 1) w(k) (k 1) 2XT (Xw(k ) b) w(k) (k 1)XT (Xw(k) b)即對任意給定的裕量向量 b ，可根據(jù)以上遞推公式逐步

26、求解最優(yōu)的權(quán)向量w ，(k 1) 0 是遞推修正的步長。該算法稱為最小均方誤差算Mean Square Error）。值得注意的是，如果任意給定b ，最小均方誤差算法得到的最優(yōu)權(quán)向量可能MSE（Least把一個原本線性可分變成一個線性不可分。也就是說，均方誤差準(zhǔn)則函數(shù)取得最小值和線性分類器的不等式方程組成立這兩個條件可能無法同時滿足。（3）最優(yōu)的裕量向量 b前述最小均方誤差算法中裕量向量 b 是任意給定的，其值將影響最終分類器設(shè)計結(jié)果。對于一般的線性分類器設(shè)計， 希望在求解權(quán)向量w 的過程中b也能取得最優(yōu)值。設(shè)求解過程中權(quán)向量 w 和裕量向量 b 都可變，若兩類線性可分，則最小均方誤差準(zhǔn)則函數(shù)

27、可取得最小值 0，此時決策邊界與所有以各樣本為中心，以最優(yōu)裕量向量 b 的各分量為半徑指標(biāo)的圓相切。求取最優(yōu)裕量向量 b 的過程同樣可采用梯度法，在第 k 1 步遞推中，有b(k 1) b(k ) (k 1) J (w(k )b(k 1) 0 是遞推修正的步長。因?yàn)? J (w(k) 2(Xw(k ) b)bb所以b(k 1) b(k) (k 1) 2(Xw(k ) b(k) b(k) 2(k 1)(Xw(k ) b(k) b(k) 2(k 1)e(k )第 21 頁Xw(k) b圖 17 最優(yōu)裕量向量 b由于誤差向量e(k ) 有可能大于 0 也可能小于 0，而遞推過程必須始終保證b(k 1

28、) 0 ，一種做法是只在e(k ) 0 時進(jìn)行修正，即取b(k 1) b(k ) (k 1)(e(k )+ e(k ) )若在已知每一步的 b(k ) 后利用J (w(k) 2XT (Xw(k) b) 0w (k )來求取最優(yōu)的w(k) ，則w(k ) (T b(k)因此有w(k +1) ( ( (T b(k +1)T b(k) (k 1)(e(k)+ e(k) )T b(k) (k 1)(T (e(k)+ e(k) )(k) ) w(k) (k 1)( w(k) (k 1)(XT X)1 w(k)+(k 1)(Te(k )Te(k )Te(k )此時得到一種可同時求取最優(yōu)權(quán)向量w 和最優(yōu)裕量

29、向量 b 的遞推算法，步驟為：a、 設(shè)定初始裕量向量b(0) 0 ，初始權(quán)向量w(0) (T b(0) ，k=0；第 22 頁b、 計算誤差向量： e(k ) Xw(k) b(k ) ；c、 對權(quán)向量進(jìn)行遞推修正： w(k +1) w(k )+(k 1)(Te(k ) ；d、 對裕量向量進(jìn)行遞推修正： b(k 1) b(k ) (k 1)(e(k )+ e(k ) ) ；e、 k=k+1，返回步驟 b，直至e(k ) 0 ，求得最優(yōu)解；或者e(k ) 0 ，證明訓(xùn)練樣本集線性不可分。T 稱為X 的偽逆，可以記為 X# 。該算法稱為 Ho-Kashyap 算其中，(法，其收斂性性可分和1 (k

30、1) 0 的條件下已得到證明。思考：為什么可以通過只在e(k ) 0 時修正b(k ) 來保證b(k 1) 0 ？ b(k ) 的絕對值只增不減對最后的最優(yōu)權(quán)向量有影響嗎？H-K 算法例題：有 4 個訓(xùn)練樣本如下：1 類: (0,0)T，(0,1)T2 類: (1,0)T，(1,1)T用 H-K 算法求其判別函數(shù)。解：樣化增廣特征向量的特征矩陣為0010 1101X 1 1 1 1偽逆為1001010111 0111 01100011011101 001) 1 XT1111 11 11121 01 011 0.50 1 0 121220111011 12 01 0 0.50 12 4 1 0.

31、50.50.251 0.5 0.50.75 1 1 0.5 0.5 0.50.5 0.25 0.5 0.5 0.750.25 第 23 頁取b(0) 1,1,1,1T ，則0.5 10.50.5 10.50.5 2, 0,1Tw(0) X#b(0) 5 10.75 11 211100001011 1110e(0) Xw(0) b(0) 0 11 1 1110 11 0111 所以， w(0) 2, 0,1T 就是所求的最優(yōu)權(quán)向量。圖 18 H-K 算法例題4、支持向量機(jī)（SVM）（1）分類間隔和支持向量對于線性可分的兩類問題，其分類決策邊界為一 n 維

32、特征空間中的超平面 H，其解有無窮多個。可以在一定的范圍內(nèi)平移超平面 H，只要不達(dá)到或者越過兩類中距離 H 最近的樣本，分類決策邊界都可以正確地實(shí)現(xiàn)線性分類，中間的裕量為 d，稱為分類間隔（Margin of Classification）。在所有線性分類器的解中，雖然都能實(shí)現(xiàn)線性分類，但隨著權(quán)向量的方向不同，分類間隔也會隨之變化。顯然，具有最大分類間隔的權(quán)向量 w優(yōu)于其他的權(quán)向量，因?yàn)槿绻Q策邊界到兩類最近的樣本的距離相等（也就是“居中”劃分），此時分類錯誤的可能性是最小的。第 24 頁圖 19 分類間隔和支持向量當(dāng)找到分類間隔最大的最優(yōu)權(quán)向量 w 后，可以發(fā)現(xiàn)它是由距離決策邊界最近的樣本

33、所決定的，這些樣本與整個訓(xùn)練集相比數(shù)量并不多， 并且除它們以外，其他的樣本都不會影響到最優(yōu)權(quán)向量的確定。這些訓(xùn)練集中的少量樣本就稱為“支持向量（Support Vector）”。（2）支持向量機(jī)分類間隔可以由支持向量到分類決策邊界的距離來決定，即d 2設(shè) Gij ( xs ) =1，則此時最大的分類間隔，等效長度最小的權(quán)向量，即max d max minw如何求取到具有最大分類間隔的最優(yōu)線性分類器，轉(zhuǎn)化為如何求取到長度最小的權(quán)向量。支持向量機(jī) SVM（Support Vector Machine）是 Vapnik 和 Cortes 于 1995年首次基于統(tǒng)計學(xué)習(xí)理論的模式識別方法，由于它在解決

34、有限數(shù)量樣本、非線性及度模式識別問題上所具有的優(yōu)秀性能，以及很強(qiáng)的泛化能力，得到了研究者普遍的重視和廣泛的應(yīng)用。支持向量機(jī)的主要特點(diǎn)有：所需樣本少真正決定具有最大分類間隔的最優(yōu)線性分類器的是少量的“支持向量”，因此即時用于訓(xùn)練的樣本個數(shù)少，只要能包含合理的支持向量，就能得到一個最優(yōu)的訓(xùn)練結(jié)果。泛化能力強(qiáng)分類器設(shè)計過程是使用訓(xùn)練樣本集來實(shí)現(xiàn)的， 所得到的分類器一第 25 頁2Gij ( x)wGij ( xs )w般都能對訓(xùn)練集實(shí)現(xiàn)良好的分類，但是否能對未知的其它樣本也取得好的分類結(jié)果，就體現(xiàn)了分類器設(shè)計算法的泛化能力（ Generalization Ability）。分類器的泛化能力一般用泛化

35、誤差界來表示，公式為R(w) Remp (w) (n / h)其中 R(w) 代表設(shè)計出的分類器分類錯誤的總的風(fēng)險，稱為結(jié)構(gòu)風(fēng)險。它的上界由兩部分：一部分是分類器對訓(xùn)練集中的樣本分類的誤差，稱為經(jīng)驗(yàn)風(fēng)險 Remp (w) ，另一部分是設(shè)計出的分類器對訓(xùn)練集以外的其它樣本分類的誤差，稱為置信風(fēng)險(n / h) ，它由訓(xùn)練集中的樣本數(shù)多少和分類決策面方程的非線性程度決定。支持向量機(jī)不僅能針對訓(xùn)練集找到最優(yōu)的分類決策邊界， 而且具有最簡單的線性形式， 因此其設(shè)計出的分類器結(jié)構(gòu)風(fēng)險小，泛化能力強(qiáng)。能處理非線性分類問題事實(shí)上，任意能用非線性方程表達(dá)的決策邊界，都可以通過向高維度特征空間機(jī)來解決。來轉(zhuǎn)化為線性