【正文】 2022/5/29 1 第三章 分類器的設計 ? 線性分類器的設計 ? 分段線性分類器的設計 ? 非線性分類器的設計 2022/5/29 2 167。 31 線性分類器的設計 上一章我們論討了線性判別函數形式為 : g(x)=WTX +Wn+1 其中 X= (X1, X2… Xn) n維特征向量 W= (W1, W2 … Wn ) n維權向量 通常通過特征抽取可以獲得 n維特征向量 ， 因此 n維 權向量是要求解的 。 求解權向量的過程就是分類器的訓練過程 ， 使用已 知類別的有限的學習樣本來獲得分類器的權向量被稱為 有監(jiān)督的分類 。 12, ( ) 0, ( ) 0x g xx g x?????? ???分 類 準 則2022/5/29 3 利用已知類別學習樣本來獲得權向量的訓練過程如下 已知 x1 ∈ ω1, 通過檢測調整權向量，最終使 x1 ∈ ω1 已知 x2 ∈ ω2, 通過檢測調整權向量，最終使 x2 ∈ ω2 這樣就可以通過有限的樣本去決定權向量 x1 x2 ……. xn 1 w1 w2 wn wn+1 ∑ 0 x∈ ω1 檢測 (已知類別 ) W1 X1 W2 X2 Wn Xn Wn+1 0 x∈ ω2 g(x)=wTx ??? WW 12022/5/29 4 利用方程組來求解權向量 對二類判別函數 g(x) = W1X1+ W2X2 +W3 已知訓練集： Xa, Xb, Xc, Xd且 當 (Xa, Xb) ∈ 時 g(x)＞ 0 當 (Xc, Xd) ∈ 時 g(x)＜ 0 設 Xa = (X1a, X2a)T Xb = (X1b, X2b)T Xc = (X1c, X2c)T Xd = (X1d, X2d)T 判別函數可聯立成： X1aW1+ X2aW2+ W3＞ 0 ① X1bW1+ X2bW2+ W3＞ 0 ② X1cW1+ X2cW2+ W3＜ 0 ③ X1dW1+ X2dW2+ W3＜ 0 ④ 求出 W1 , W2, W3 1?2?2022/5/29 5 將 ③ ④式正規(guī)化，得 X1cW1 X2cW2 W3 0 X1dW1 X2dW2 W3 0 所以 g(x) =WTX 0 其中 W = (W1 , W2, W3)T 為各模式增 1矩陣 為 N*(n+1） 矩陣 N為樣本數 ， n為特征數 ???????????????????111121212121ddccbbaaXXXXXXXXX2022/5/29 6 訓練過程就是對已知類別的樣本集求解權向量 w， 這是一個線 性 聯立不等式方程組求解的過程 。 求解時： ① 只有對線 性 可分的問題 ， g(x) =WTX才有解 ② 聯立方程的解是非單值 ， 在不同條件下 ， 有不同的解 ，所以就產生了求最優(yōu)解的問題 ③ 求解 W的過程就是訓練的過程 。 訓練方法的共同點是 ，先給出準則函數 ， 再尋找使準則函數趨于極值的優(yōu)化算法 ， 不同的算法有不同的準則函數 。 算法可以分為迭代法和非迭代法 。 2022/5/29 7 一 ．梯度下降法 — 迭代法 欲對不等式方程組 WTX0求解 ， 首先定義準則函數目標 函數 )J(W)， 再求 J(W)的極值使 W優(yōu)化 。 因此求解權向量的 問題就轉化為對一標量函數求極值的問題 。 解決 此類問題的方法是梯度下降法 。 方法就是從起始值 W1開始 ， 算出 W1處目標函數的梯度 矢量 ▽ J(W1)， 則下一步的 w值為： W2 = W1ρ 1▽ J(W1) W1為起始權向量 ρ1為迭代步長 J(W1) 為目標函數 ▽ J(W1)為 W1處的目標函數的梯度矢量 2022/5/29 8 在第 K步的時候 Wk+1 = Wkρ k▽ J(Wk) ρk為正比例因子 這就是梯度下降法的迭代公式 。 這樣一步步迭代 就可以收斂于解矢量 ， ρk取值很重要 。 ρk太大 ， 迭代太快 ， 引起振蕩 ， 甚至發(fā)散 。 ρk太小 ， 迭代太慢 。 應該選最佳 ρk。 2022/5/29 9 選最佳 ρk 目標函數 J(W)二階臺勞級數展開式為 J(W)≈J(Wk)+ ▽ JT(W Wk)+(W Wk)TD(W Wk)T/2 ① 其中 D為當 W = Wk時 J(W)的二階偏導數矩陣 將 W=Wk+1 = Wkρk▽ J(Wk)代入 ① 式得： J(Wk+1) ≈J(Wk) ρk||▽ J||2+ ρk2▽ JT D▽ J 其中 ▽ J=▽ J(Wk) 對 ρk求導數 ， 并令導數為零有 最佳步長為 ρk=||▽ J||2/▽ JTD▽ J 這就是最佳 ρk的計算公式，但因二階偏導數矩陣 D的計算量太大，因此此公式很少用。 212022/5/29 10 若令 W=Wk+1上式為 J(Wk+1)=J(Wk)+▽ JT(Wk+1Wk)+(Wk+1Wk)TD(Wk+1Wk)T/2 對 Wk+1求導 ， 并令導數為零可得： 最佳迭代公式： Wk+1= Wk D1▽ J — 牛頓法的迭代公式 D1是 D的逆陣 討論：牛頓法比梯度法收斂的更快 ， 但是 D的計算量大并且要計算 D1。 當 D為奇異時 ， 無法用牛頓法 。 2022/5/29 11 二 感知器法 感知器的原理結構為： 2022/5/29 12 通過對 W的調整 ， 可實現判別函數 g(x) =WTX RT 其中 RT為響應閾值 定義感知準則函數：只考慮錯分樣本 定義： 其中 x0為錯分樣本 當分類發(fā)生錯誤時就有 WTX 0，或－ WTX 0, 所以 J(W) 總是正值，錯誤分類愈少， J(W)就愈小。 理想情況為 即求最小值的問題。 ? ?????0)(XXXWWJ T0)( ?W