王杰(博士/教授/博導(dǎo))鄭州大學(xué)電氣工程學(xué)13837106273wj@模式識(shí)別PatternRecognitionChapter3(I)11/5/20251王杰(博士/教授/博導(dǎo))鄭州大學(xué)電氣工程學(xué)13837106273wj@模式識(shí)別PatternRecognition

Ch.3線性分類器

3.1線性分類器(LINEARCLASSIFIERS)-引言TheProblem:Consideratwoclasstaskwithω1,ω2

Hence:3.2線性判別函數(shù)和決策超平面11/5/20252王杰(博士/教授/博導(dǎo))鄭州大學(xué)電氣工程學(xué)13837106273wj@模式識(shí)別PatternRecognition

Ch.3線性分類器

Fig.3-1GraphofDecisionLine；Onesidesatisfysg(x)>0(+)andtheothersideg(x)<0(-)3.2線性判別函數(shù)和決策超平面(3-1)11/5/20253王杰(博士/教授/博導(dǎo))鄭州大學(xué)電氣工程學(xué)13837106273wj@模式識(shí)別PatternRecognition

Ch.3線性分類器

3.3感知器算法(ThePerceptronAlgorithm)我們關(guān)心計(jì)算未知參數(shù)ωi(i=1,2,…,l)以定義決策超平面。Assumelinearlyseparableclasses,i.e.,上式也包含不經(jīng)過(guò)原點(diǎn)的超平面的情況：作變換：

(3-2)可以得到：(3-3)(3-4)11/5/20254王杰(博士/教授/博導(dǎo))鄭州大學(xué)電氣工程學(xué)13837106273wj@模式識(shí)別PatternRecognition

Ch.3線性分類器

3.3感知器算法(ThePerceptronAlgorithm)Ourgoal:Computeasolution,i.e.,ahyper

plane(超平面)

w,

sothatThestepsDefineacostfunctiontobeminimized(定義代價(jià)函數(shù)并極小化)Chooseanalgorithmtominimizethecostfunction(尋找算法)Theminimumcorrespondstoasolution(求得與之相應(yīng)的解)TheCostFunction其中，Y是被w錯(cuò)誤分類的向量的子集，當(dāng)

Y=(emptyset)則獲得了一個(gè)解并且(3-5)(3-6)11/5/20255王杰(博士/教授/博導(dǎo))鄭州大學(xué)電氣工程學(xué)13837106273wj@模式識(shí)別PatternRecognition

Ch.3線性分類器

3.3感知器算法(ThePerceptronAlgorithm)如果在上式中定義：(3-7)則有：當(dāng)代價(jià)函數(shù)取最小值0時(shí)，則意味著所有的訓(xùn)練向量的分類都是正確的。事實(shí)上，式(3-6)表示的代價(jià)函數(shù)是分段線性的，平滑改變權(quán)向量也導(dǎo)致代價(jià)函數(shù)線性變化，直到分類向量個(gè)數(shù)改變代價(jià)函數(shù)會(huì)有非線性改變。在這些點(diǎn)，其梯度沒(méi)有意義。為計(jì)算代價(jià)函數(shù)的最小值，梯度下降法是一個(gè)合理的方法，即：(3-8)、(3-9)

(3-10)、(3-11)這就是著名的感知器算法(PerceptronAlgorithm)11/5/20256Fig.3-2感知器算法的幾何解釋，在唯一錯(cuò)誤分類點(diǎn)x，δx

=-1王杰(博士/教授/博導(dǎo))鄭州大學(xué)電氣工程學(xué)13837106273wj@模式識(shí)別PatternRecognition

Ch.3線性分類器

3.3感知器算法(ThePerceptronAlgorithm)Perceptron在x方向修正權(quán)向量，其作用是修正超平面，使x能夠被正確分到ω1類。修正的幅度和迭代次數(shù)取決于修正系數(shù)，滿足分類的超平面不唯一，且不是一般的梯度算法，因而有必要證明其收斂性。11/5/20257王杰(博士/教授/博導(dǎo))鄭州大學(xué)電氣工程學(xué)13837106273wj@模式識(shí)別PatternRecognition

Ch.3線性分類器

3.3感知器算法(ThePerceptronAlgorithm)感知器算法的收斂性證明：由感知器算法(3-12)兩邊取歐式范數(shù)：(3-13)(3-14)(3-15)11/5/20258王杰(博士/教授/博導(dǎo))鄭州大學(xué)電氣工程學(xué)13837106273wj@模式識(shí)別PatternRecognition

Ch.3線性分類器

3.3感知器算法(ThePerceptronAlgorithm)(3-15)(3-16)(3-17)11/5/20259王杰(博士/教授/博導(dǎo))鄭州大學(xué)電氣工程學(xué)13837106273wj@模式識(shí)別PatternRecognition

Ch.3線性分類器

3.3感知器算法(ThePerceptronAlgorithm)另外一種有用的感知器算法：(3-18)Itisarewardandpunishmenttypeofalgorithm感知器：ItisalearningmachinethatlearnsfromthetrainingvectorsviatheperceptronalgorithmThenetworkiscalledperceptronorneuron11/5/202510王杰(博士/教授/博導(dǎo))鄭州大學(xué)電氣工程學(xué)13837106273wj@模式識(shí)別PatternRecognition

Ch.3線性分類器

3.3感知器算法(ThePerceptronAlgorithm)11/5/202511Example:Atsomestagettheperceptron

algorithmresultsin Thecorrespondinghyperplaneisρ=0.7(中間結(jié)果，決策線，綠色)有兩個(gè)點(diǎn)分類仍然錯(cuò)誤(新決策線，黑色)王杰(博士/教授/博導(dǎo))鄭州大學(xué)電氣工程學(xué)13837106273wj@模式識(shí)別PatternRecognition

Ch.3線性分類器

3.3感知器算法(ThePerceptronAlgorithm)感知器算法要求的基本條件是類的線性可分。在類非線性可分的情況下，袋式算法(PocketAlgorithm,GallantS.I,PerceptronbasedlearningAlgorithms,IEEETrans.NeuralNetworks,1(2),1990:179-191)、熱量感知器算法(ThermalPerceptronAlgorithm,FreanM.,Athermalperceptron

learningrule,NeuralComputation,Vol.4,1992:946-957)、損失最小算法(LossMinimizationAlgorithm,HrycejT.,Modularlearninginneuralnetworks,NewYork：Wiley,1992)和重心修正法(BarycentricCorrectionProcedure,PoulardH.,Barycentriccorrectionprocedure:Afastmethodoflearningthresholdunits,Proc.WCNN’95,Vol.1,Washington,D.C.,July,1995:710-713)等，也可以以概率1收斂于最佳分類結(jié)果(線性分類方法能夠達(dá)到的最佳分類結(jié)果)11/5/202513王杰(博士/教授/博導(dǎo))鄭州大學(xué)電氣工程學(xué)13837106273wj@模式識(shí)別PatternRecognition

Ch.3線性分類器

3.4最小二乘法(LeastSquaresMethod)Ifclassesarelinearlyseparable,theperceptronoutputresultsinIfclassesareNOTlinearlyseparable,weshallcomputetheweightssothatthedifferencebetweenTheactualoutputoftheclassifier,,andThedesiredoutputs,e.g.tobeMinimized11/5/202514王杰(博士/教授/博導(dǎo))鄭州大學(xué)電氣工程學(xué)13837106273wj@模式識(shí)別PatternRecognition

Ch.3線性分類器

3.4最小二乘法(LeastSquaresMethod)Minimization,

在均方差意義上,意味著選擇

使得代價(jià)函數(shù)Minimizing(3-19)11/5/202515王杰(博士/教授/博導(dǎo))鄭州大學(xué)電氣工程學(xué)13837106273wj@模式識(shí)別PatternRecognition

Ch.3線性分類器

3.4最小二乘法(LeastSquaresMethod)(3-20)向多類推廣：目標(biāo)是根據(jù)MSE(最小方差)計(jì)算M個(gè)線性判別函數(shù)考慮期望輸出：令：計(jì)算11/5/202516王杰(博士/教授/博導(dǎo))鄭州大學(xué)電氣工程學(xué)13837106273wj@模式識(shí)別PatternRecognition

Ch.3線性分類器

3.4最小二乘法(LeastSquaresMethod)(3-20)上式等價(jià)與M個(gè)MSE最小化問(wèn)題，也即：設(shè)計(jì)每個(gè)權(quán)系數(shù)使得期望輸出為1