第五章線性判別函數5.1線性判別函數和判別界面線性不可分情況線性判別函數x=(x1,x2,…,xd)t:特征矢量；w=(w1,w2,…,wd)t:權矢量；w0：偏置(bias)。線性判別函數的增廣形式y=(1,x1,x2,…,xd)t:增廣的特征矢量；a=(w0,w1,w2,…,wd)t:增廣的權矢量；兩類問題線性判別準則線性分類器的分類界面分類界面的幾何解釋線性分類界面H是d維空間中的一個超平面；分類界面將d維空間分成兩部分，R1，R2分別屬于兩個類別；判別函數的權矢量w是一個垂直于分類界面H的矢量，其方向指向區域R1

；偏置w0與原點到分類界面H的距離有關：多類問題（情況一）每一類模式可以用一個超平面與其它類別分開；c類問題c個兩類問題，需要c個線性分類界面；第i類與其它類別之間的判別函數：多類問題（情況一）分類界面多類問題（情況一）判別規則若存在i，使得gi(x)>0，gj(x)<0，j≠i，則判別x屬于ωi類；其它情況，拒識。多類問題（情況二）每兩個類別之間可以用一個超平面分開；c類問題c(c-1)/2個兩類問題；第i類與第j類之間的判別函數為：多類問題（情況二）分類界面多類問題（情況二）判別準則如果對任意j≠i

，有gij(x)≥0

，則決策x屬于ωi。其它情況，則拒識。多類問題（情況三）情況三是情況二的特例，不存在拒識區域。多類問題（情況三）判別函數c個類別需要c個線性函數：判別準則：5.2線性判別函數的學習問題的提出：假設有一個包含n個樣本的集合y1,y2,…,yn,一些標記為ω1,另一些標記為ω2，用這些樣本來確定一個判別函數g(y)=aty的權矢量a。在線性可分的情況下，希望得到的判別函數能夠將所有的訓練樣本正確分類；線性不可分的情況下，判別函數產生錯誤的概率最小。訓練樣本的規范化非規范化：規范化：解區域的幾何解釋(特征空間中）特征空間中：矢量a是垂直于分類界面的矢量：解區域的幾何解釋(權空間中）權空間中，atyi=0是一個通過原點的超平面，yi是法向量，而a是空間中一個點。一般求解方法—梯度下降法求解不等式組采用最優化的方法：定義一個準則函數J(a)，當a是解向量時，J(a)為最小；采用最優化方法求解標量函數J(a)的極小值。最優化方法采用最多的是梯度下降法，設定初始權值矢量a(1)，然后沿梯度的負方向迭代計算：其中η(k)稱為學習率，或稱步長。5.3感知器算法(Perceptron)最直觀的準則函數定義是最少錯分樣本數準則：

JN(a)=樣本集合中被錯誤分類的樣本數；感知器準則以錯分樣本到判別界面距離之和作為準則（感知器準則）：感知器算法(批量調整版本)begininitialize,,θ,k0do

kk+1

untilreturnaend感知器算法(單樣本調整版本)begininitialize,k0dok(k+1)modnifyk

ismisclassifiedbyathenuntilallpatternsproperlyclassifiedreturnaend例5.1有兩類模式的訓練樣本：

ω1：{(0,0),(0,1)}

ω2：{(1,0),(1,1)}

用感知器算法求取判別函數，將兩類樣本分開。感知器算法的特點當樣本線性可分情況下，學習率合適時，算法具有收斂性；收斂速度較慢；當樣本線性不可分情況下，算法不收斂，且無法判斷樣本是否線性可分。5.4最小平方誤差算法(LMSE)LMSE方法的基本思想是將求解線性不等式組的問題轉化為求解線性方程組：最小平方誤差的準則函數定義誤差矢量e，用e長度的平方作為準則函數（LMSE準則）：權值矢量的求解(偽逆求解法)稱為偽逆矩陣例5.2有兩類模式的訓練樣本：

ω1：{(0,0),(0,1)}

ω2：{(1,0),(1,1)}

用LMSE算法求取判別函數，將兩類樣本分開。權值矢量的求解(迭代求解法)begininitializea(0),b,θ,η(?),k0；

dokk+1；

untilreturnaendLMSE算法的特點算法的收斂依靠η(k)的衰減，一般取η(k)=η(1)/k；算法對于線性不可分的訓練樣本也能夠收斂于一個均方誤差最小解；取b=1時，當樣本數趨于無窮多時，算法的解以最小均方誤差逼近貝葉斯判別函數；當訓練樣本線性可分的情況下，算法未必收斂于一個分類超平面。LMSE算法5.5支持矢量機(SVM,SupportVectorMachine)問題的提出：函數間隔和幾何間隔函數間隔：樣本xi到分類界面g(x)=0的函數間隔定義為：幾何間隔：最優分類界面樣本集與分類界面之間的間隔定義為樣本與分類界面之間幾何間隔的最小值。最優分類界面：給定線性可分樣本集，能夠將樣本分開的最大間隔超平面。支持矢量距離最優分類界面最近的這些訓練樣本稱為支持矢量；最優分類界面完全由支持矢量決定，然而支持矢量的尋找比較困難。SVM的準則函數給定兩類問題的線性可分樣本集合{(y1,z1),…,(yn,zn)}，其中z為樣本的類別標號：可分性約束：能夠將樣本線性分開的分類界面滿足： 亦即可以通過調整權值w和w0將樣本集合的最小函數間隔調整為1。SVM的準則函數樣本集到分類界面的幾何間隔：最大，亦即||w||最小，所以SVM可以變為如下的優化問題：在滿足 的條件下，最小化準則函數（SVM準則）：Kuhn-Tucker構造法構造Lagrange函數分別對參數w和w0求導：Kuhn-Tucker構造法因此有：帶入Lagrange函數，有：Kuhn-Tucker構造法因此SVM的優化問題可以轉化為一個經典的二次規劃問題： 約束條件：SVM解的討論這是一個典型的不等式約束條件下的二次優化問題，其解法的基礎是Kuhn-Tucker定理；首先求解的是n個Lagrange乘子，n為訓練樣本數。但根據Kuhn-Tucker定理，有：滿足第2，3個條件的yi稱為支持矢量。支持向量和Lagrange系數SVM解的討論根據找到的支持矢量yi以及相應的Lagrange乘子αi，計算權矢量w：偏置w0可以用支持矢量滿足的條件求得：Matlab實現BioinformaticsToolbox中包含了LibSVM的實現函數；學習函數：

SVMSTruct=svmtrain(X,L,

’KERNELFUNCTION’,

’linear’,‘BOXCONSTRAIN’,C,

‘AUTOSCALE’,false）；

X:n*d矩陣，L：n*1矢量識別函數：

Labels=svmclassify(X,SVMSTruct);5.6多類別線性判別函數的學習方法一：根據5.1節介紹的前兩種情況，分別轉換為c個兩類問題，或c(c-1)/2個兩類問題分別處理；方法二：對于情況三，可以采用Kesler構造法訓練；方法三：設計感知器網絡進行識別。Kesler構造法（擴展的感知器算法）初始化c個權向量ai(1)，k1；輸入增廣特征矢量yk（只增加一維1，不改變特征的符號），計算c個判別函數的輸出：修改權矢量：

若yk屬于ωi類，而存在gi(yk)≤gj(yk)，則：

ai(k+1)=ai(k)+yk；

aj(k+1)=aj(k)-yk

al(k+1)=al(k)，l≠j,i重復上述過程，直到全部樣本被正確分類為止。兩類問題的感知器網絡多類問題的感知器網絡兩層感知器網絡的訓練樣本給定樣本集合(y1,t1),(y2,t2),…,(yn,tn)，其中yi為增廣特征矢量，ti稱為期望輸出；c個輸出層神經元時，可設定期望輸出為：

第1類樣本：(+1,-1,-1,-1)第2類樣本：(-1,+1,-1,-1)

第3類樣本：(-1,-1,+1,-1)第4類樣本：(-1,-1,-1,+1)編碼輸出時：

第1類樣本：(-1,-1)

第2類樣本：(-1,+1)

第3類樣本：(+1,-1)

第4類樣本：(+1,+1)兩層感知器網絡的訓練方法可以采用最小均方誤差算法，權值調整公式為：

其中A為權值矢量矩陣，ti為第i個樣本yi

的期望輸出矢量。5.7線性分類器的局限性線性分類器的分類能力不強，能夠很好地解決線性可分的問題，而對非線性可分的問題無法解決，如著名的異或問題：解決途徑廣義線性判別函數；分段線性判別函數；多層感知器；核函數方法。廣義線性判別函數增加特征