第4章 非線性分類器及神經(jīng)網(wǎng)絡

第4章非線性分類器與神經(jīng)網(wǎng)絡

NonlinearClassifiersandNeuralNetworks§1引言§2異或問題§3兩層感知器§4反向傳播算法§5徑向基函數(shù)網(wǎng)絡§6支持向量機§7其他非線性分類法1.分段線性分類器2.樹狀分類器3.二次判別函數(shù)§1引言第3章討論了由線性判別函數(shù)g(x)=WTx+w0=ATY描述的線性分類器設計。從訓練集樣本得到權值W和w0或者A。若兩類間是線性可分的，單層感知器方法可計算出g(x)的權值。例：第k+1次疊代得到的直線方程對于線性不可分的，線性分類器的最優(yōu)方法是使平方誤差最小。

例：線性分類器的MSE方法對于非線性分類，選擇一個合適的非線性判別函數(shù)是很困難的，如圖AD,BD,CD。解決方法：⑴神經(jīng)網(wǎng)絡(即多層感知器)具有很強的處理非線性的能力，適合非線性分類。神經(jīng)網(wǎng)絡中要解決的主要問題：①學習方法－目的修改權值，如反向傳播算法。②網(wǎng)絡結構－層數(shù)，每層神經(jīng)元數(shù)及連接方式。③用支持向量機(網(wǎng)絡)可得到最優(yōu)分界面。⑵用樹分類器進行多級決策。在樹分類器上用線性判別函數(shù)，就構成了一個分段線性分類器。⑶對一些特殊的問題可用二次判別函數(shù)。§2異或問題（XOR）異或布爾函數(shù)是非線性可分問題的典型例子。將布爾函數(shù)理解為分類任務，即根據(jù)輸入x1、x2的不同，輸出為0(B類)或1(A類)。圖中給出了類在空間的位置。一條直線不能將這兩類分開。

“與”(AND)和“或”(OR)布爾函數(shù)是線性可分的。用一個感知器可實現(xiàn)“或門”或“與門”。由感知器實現(xiàn)的決策面方程

異或(XOR)問題必須用兩層感知器實現(xiàn)。g∑§2兩層感知器一條直線不能解決異或問題，可用“或”和“與”二條直線解決，即使用兩層感知器來解決。

g1(x)=x1+x2－1/2=0

g2(x)=x1+x2－3/2=0二個神經(jīng)元分別實現(xiàn)或和與運算。二條直線將空間分成三個區(qū)域g1(x)>0

g2(x)<0

g1(x)<0

g2(x)>0因此，這個問題可分兩階段處理。

(B類)(A類)d兩層感知器結構f1.兩層感知器⑴兩層感知器的結構與單層感知器相比增加了一個隱層。第一層為隱層，可由p個神經(jīng)元組成。所有隱層神經(jīng)元輸入節(jié)點為xi的d個特征，i=1,2,···,d；

權wi是要通過學習調(diào)整的參數(shù)；每個神經(jīng)元的輸出yi不相同。第二層為輸出層，圖中為一個神經(jīng)元，輸出運算結果。若輸入節(jié)點稱為輸入層，則也稱為三層網(wǎng)絡。d單層感知器結構wiwiwi⑵異或問題用兩層感知器分兩階段解決第一階段輸入x＝[x1x2]T

，輸出新向量y＝[y1y2]Ty1相對于g1(x)進行“或”運算

y2相對于g2(x)進行“與”運算由第一隱層兩個神經(jīng)元實現(xiàn)。第二階段y＝[y1y2]T為輸入，輸出為類別。g(y)由一個神經(jīng)元實現(xiàn)。g(y)=y1-y2-1/2＝0y1y2⑶兩層感知器模型第一層隱層(hiddenlayer)神經(jīng)元完成第一階段的計算，是x到y(tǒng)的映射，即隱層神經(jīng)元作用是將輸入X空間映射到二維(因為二個神經(jīng)元)Y空間中單位邊長的正方形頂點上(00,10,10,11)。第二層的一個神經(jīng)元,稱為輸出層(outputlayer)完成第二階段計算,輸出分類用判別函數(shù)的值。三個神經(jīng)元決策線的方程y2d⑴隱層神經(jīng)元：d維,隱層有p個神經(jīng)元，其作用是將輸入X空間映射到p維Y空間中單位邊長的超立方體頂點yi上，即輸入空間到超立方體頂點的映射是通過創(chuàng)建p個(gi=0)超平面實現(xiàn)的。隱層作用，也可說是產(chǎn)生超平面Hp的交集，即將輸入拆分為由超平面交集構成的多面體。每個超平面由隱層中的一個神經(jīng)元實現(xiàn)，神經(jīng)元輸出為0或1。2.兩層感知器分類能力y1y2y3設d=2，p=3。根據(jù)輸入x與三個平面g1,2,3(x)=0的相對位置，由平面交集定義的每個區(qū)域?qū)娜S立方體的一個頂點。如100頂點對應的區(qū)域為g1的(+)側,g2的(-)側,g3的(-)側。即將輸入拆分為由超平面交集構成的多面體。每個區(qū)域中所有向量映射到立方體(y1y2

y3)的頂點,yi∈0或1。w1∈[011,001,000]；w2∈[111,010,110,100]。⑵輸出神經(jīng)元超平面將超立方體分為兩部分，一部分頂點位于一側，其余為另一側。上例d=2,p=3則該平面將三維幾何空間(R3)分為兩個區(qū)域：一側(類A)頂點是000∪001∪011；另一側(類B)頂點是010∪100∪110∪111。而101不與任一區(qū)域?qū)?。平面方程g(y)=-y1-y2+y3+0.5=0兩層感知器不能解決所有的問題，如下列類域的分離：類A－(000∪111∪110)；類B－(001∪011∪010∪100)。這取決于每個神經(jīng)元的gp(x)所構成的平面位置。⑶例：兩層感知器結構為2:3:1(d=2,p=3,j=1)，用分段線性方法將非線性兩類分開。第一隱層三個神經(jīng)元有相同的輸入x，由于gi(x)

的不同，有不同的輸出。i=1,2,3。其分類空間是三維的。gi(x)＝0建立的三個超平面H1H2H3將d維特征空間分割成正負兩個半空間。圖中的三個超平面圍成7個區(qū)域，共兩類(w1w2)，每個區(qū)域映射到超立方體頂點。

w2∈100∪000∪010∪011∪111∪101

w1∈110輸出層組織輸出。j個p個d個3.三層感知器第一層的隱層神經(jīng)元構成超平面。即將有類別標記的訓練樣本集，先用分段線性算法gi(x)確定一組超平面的參數(shù)(權值)，超平面的數(shù)目就是神經(jīng)元數(shù)，設為p個。這就構成p維空間。第二隱層有j個神經(jīng)元，每個神經(jīng)元在p維空間中建立一個超平面。通過選擇該層的權值，決定這些超平面的組合和連接方式，構成區(qū)域。第三層輸出層的神經(jīng)元確定類別。這種結構稱為前饋神經(jīng)網(wǎng)絡。三層網(wǎng)絡可以實現(xiàn)任何復雜類型的映射?？梢宰C明，由于在分類空間中超立方體的凸性，對于無論多么復雜的分類問題，一般來說用兩個隱層已足夠。圖a單層感知器只能一個線性判別；圖b兩層感知器中每個隱層神經(jīng)元都有線性判別能力，就可建立復雜的凸區(qū)域；圖c三層感知器的前二層已得到了超體立方，在第三層再次建立超平面劃分區(qū)域。多層感知器簡稱MLP。Multi-Layer-Perceptron§3反向傳播算法神經(jīng)網(wǎng)絡的輸出取決于輸入和連接的權值。其工作過程主要分兩個階段：①學習期－通過不斷地學習修改權值。②工作期－權值確定后，可計算輸出。單層感知器可通過感知器算法進行學習，調(diào)整權值，完成線性分類。它的輸入是訓練集的樣本，輸出是期望值，對外是透明的。多層感知器中的中間隱層學習算法，對外是不透明的，隱層權值調(diào)整有困難。在20世紀80年代提出了誤差反向傳播算法，來計算隱層的權值。1.神經(jīng)網(wǎng)絡的學習方式：⑴有監(jiān)督學習向網(wǎng)絡輸入訓練樣本，期望輸出已知。比較實際輸出與期望輸出之誤差，該誤差或準則函數(shù)是權值的某種標量函數(shù)，使之達到最小，以使每個輸出單元的實際輸出逼近期望值。這個過程稱為學習過程。準則函數(shù)可用沒有錯分樣本或最小均方差規(guī)則，優(yōu)化算法可采用梯度下降法。學習方法：如果一節(jié)點輸出正確，一切不變；如果輸出本應為1而為0，則權值增加一增量ΔW；反之減少ΔW，如同感知器算法。2.反向傳播算法(BP法)Back-Propogation用BP算法的網(wǎng)絡也稱為BP網(wǎng)絡。算法原理：從后向前逐層傳播誤差,間接算出隱層誤差。采用最小二乘和梯度搜索法，以使實際輸出值與期望輸出值之間的誤差均方值最小。工作信號：輸入信號向后(正向)傳播直到輸出端，是輸入和權的函數(shù)。誤差信號：網(wǎng)絡實際輸出與期望輸出之差，由輸出端向前傳播(反向)，逐層算出隱層誤差，修改前一層的權值，以使誤差最小。后前⑴BP算法推導計算某一層的第j個單元，i和k分別為其前層和后層的單元，Oj代表本層輸出,netj為輸入。從前到后對每層各單元計算(正向算法)

j的輸入

j的輸出對輸出層而言，為實際輸出，yj為期望值

局部梯度定義誤差權值對誤差影響

權值修正應使誤差減少，修正量為

j單元分兩種情況(反向計算)

①j是輸出節(jié)點

②j不是輸出節(jié)點,Oj對后層的全部節(jié)點都有影響在實際使用時，為了加快收斂速度，要加入前一次的修正量第t次的實際修正量a稱為慣性系數(shù)，h為學習系數(shù)。⑵反向傳播算法步驟：初始化：設可調(diào)參數(shù)(每個權值和閾值)為均勻分布的較小數(shù)，如±0.3均勻分布隨機數(shù)。對每個樣本作如下計算，直到收斂：①輸入一個樣本x

=(x1,x2,..,xd)即Oi；輸入網(wǎng)絡的期望輸出yj，若輸出為兩個單元則j=1,2。②從前向后計算各層(正向)，各神經(jīng)元輸出Oj③對輸出層計算dj④從后向前計算各隱層δj

（反向）

⑤計算并保存各權值修正量

⑥修正權值t=t+1，輸入新的樣本(或新的周期樣本)，直到誤差達到要求，訓練結束。訓練時各周期中樣本的輸入順序要重新隨機排序。這是對每個樣本作權值修正。也可對全部樣本計算dj后求和，按總誤差修正權值，稱為批處理方法。⑶學習曲線在訓練開始誤差很高，隨著學習進展，誤差越來越小，由此生成學習曲線。誤差與訓練樣本的數(shù)量、網(wǎng)絡輸入、所有神經(jīng)元的權值和閾值、以及網(wǎng)絡的結構有關。測試集：獨立選取的樣本，誤差達到或接近訓練集樣本，則說明該網(wǎng)絡有推廣能力。檢驗集：用非訓練樣本測試網(wǎng)絡的現(xiàn)場運行性能。訓練總量用回合數(shù)表示，每輸入一次全部樣本,稱為一個回合。將新的樣本或老樣本隨機排序后再輸入，進行下一個回合的訓練。3.實際應用中的有關問題：⑴有關概念神經(jīng)網(wǎng)絡是一種軟件，它是通過軟件編程來實現(xiàn)的。它是與“模型-無關”的，是一種基于距離度量的數(shù)據(jù)分類方法，通過不斷的自學習來調(diào)整權值，以得到期望的輸出。神經(jīng)網(wǎng)絡具有逼近任意非線性函數(shù)的能力。根據(jù)已有的輸入輸出數(shù)據(jù)來訓練神經(jīng)網(wǎng)絡的權值，使它能精確地近似給定的非線性系統(tǒng)。神經(jīng)網(wǎng)絡基本上執(zhí)行線性判別，執(zhí)行過程是在輸入信號的非線性映射空間中進行的，利用分段線性技術實現(xiàn)。⑵樣本數(shù)據(jù)要保證訓練好的網(wǎng)絡有好的推廣性，訓練結果應該有效的逼近樣本蘊含的內(nèi)在規(guī)律。將總樣本隨機分為訓練樣本和非訓練樣本(測試樣本),若測試樣本的誤差接近訓練樣本，則可行。輸入預處理：應用Sigmoid函數(shù)會受到飽和影響，應將所有的輸入特征變換到一個合適的范圍,如(0,1)。輸出處理：若三類設三個名義值。用閾值，可將網(wǎng)絡的輸出值變換為-1和1。⑶學習參數(shù)的選擇

h對收斂性影響大，在0.1~3之間試探。通常0.5左右。

a開始在0.9~1之間選擇，a>1時不收斂。訓練中可不斷減小。初始權值在-0.5~0.5之間選擇。由于BP算法存在多個局部極小點，必須通過多次改變初始權值，通過訓練求得相應的極小點，以比較網(wǎng)絡的誤差，確定全局極小點，從而得到最優(yōu)的權值。上述的參數(shù)僅供參考，需要在學習過程中不斷的嘗試，以求達到收斂速度快，誤差小。⑷神經(jīng)網(wǎng)絡結構的選擇隱層：隱層節(jié)點數(shù)就是提供的超平面數(shù)。多,可降低誤差，但也有可能產(chǎn)生“過學習”。隱層節(jié)點個數(shù)：增加節(jié)點數(shù)可提高精度。如果樣本的維數(shù)較大時，第一隱層中神經(jīng)元作用相當于降低維數(shù)，因此其個數(shù)應當接近于樣本數(shù)協(xié)方差矩陣擁有的顯著本征值個數(shù)。網(wǎng)絡結構往往憑經(jīng)驗選擇，在設計過程中可用幾種不同的結構、初始參數(shù)分別進行試驗。BP算法的優(yōu)缺點優(yōu)點：理論基礎牢固推導過程嚴謹物理概念清晰通用性好所以，它是目前用來訓練多層前向網(wǎng)絡（BP網(wǎng)絡）較好的算法。BP算法的優(yōu)缺點缺點：BP算法的收斂速度一般來說比較慢；BP算法只能收斂于局部最優(yōu)解，不能保證收斂于全局最優(yōu)解；當隱層元的數(shù)量足夠多時，網(wǎng)絡對訓練樣本的識別率很高，但對測試樣本的識別率有可能很差，即網(wǎng)絡的推廣能力有可能較差。BP算法的實用技術輸出函數(shù)（激活函數(shù)）輸入信號尺度變換c類問題的目標輸出帶噪聲的訓練法人工“制造”數(shù)據(jù)隱單元數(shù)權值初始化學習率沖量項權值衰減BP算法的實用技術輸出函數(shù)（激活函數(shù)）應具備的性質(zhì)非線性：非線性特征映射，否則三層網(wǎng)絡將等同于兩層網(wǎng)絡的計算能力飽和性：存在最大和最小值，即輸出有上下界連續(xù)性：在整個自變量范圍內(nèi)都有定義光滑性：在整個自變量范圍內(nèi)一階導數(shù)存在最好有單調(diào)性：導數(shù)在自變量范圍內(nèi)不變號，避免引入不必要的局部極值Sigmoid函數(shù)滿足上述性質(zhì)，因此被廣泛采用激活函數(shù)f(·)，一般選用Sigmoid函數(shù)xBP算法的實用技術輸入信號尺度變換魚分類的例子：x1:質(zhì)量x2:長度x1=1500克，x2=0.3米，則網(wǎng)絡權值的調(diào)整主要由x1控制x1=1.5千克，x2=300毫米，則網(wǎng)絡權值的調(diào)整主要由x2控制解決方案：輸入特征尺度變換，使得每個特征在整個訓練集上的均值為零每個特征的方差相同，如都為1.0規(guī)范化BP算法的實用技術c類問題的目標輸出Sigmoid函數(shù)的飽和值±1.716永遠不可能達到，存在誤差c類問題的判決準則：如果樣本x屬于第i類，則第i個輸出單元的目標輸出為+1，其他輸出單元為-1例如：四類情況，x屬于第3類，則目標輸出為（-1，-1,+1，-1）BP算法的實用技術帶噪聲的訓練法當訓練集很小時，可以構造一個虛擬的或替代的訓練模式來使用（建立概率模型），就好像它們是從源分布中抽樣出來的正常的訓練模式在沒有具體特定信息時，一個自然的假設就是此代替模式應該加入一個d維噪聲，以獲得真實的訓練點這種有噪聲的訓練方法實際上可用于任一分類方法，盡管對于高度局部化的分類器（如最近鄰分類器）它通常并不改善準確率BP算法的實用技術人工“制造”數(shù)據(jù)在訓練模式不足的情況下，有時可以人工制造一些訓練樣本需要利用問題的先驗知識，如某種“幾何不變性”，制造出一些能傳達更多信息的訓練樣本數(shù)據(jù)變換：例如字符識別問題中（如：dataaugmentation）旋轉(zhuǎn)縮放字符筆畫寬窄變化BP算法的實用技術隱單元數(shù)：隱單元個數(shù)決定了網(wǎng)絡的表達能力，從而決定了判決邊界的復雜度簡單問題需要較少的隱單元復雜問題需要較多隱單元過少隱單元造成神經(jīng)網(wǎng)絡表示能力下降過多隱單元造成對訓練集的“過擬合”經(jīng)驗規(guī)則選取隱單元個數(shù)，使得網(wǎng)絡中總的權值數(shù)大致為樣本數(shù)的1/10BP算法的實用技術權值初始化若則無法更新權值初始化方法：從均勻分布中選取權值規(guī)格化后（方差為1.0）的d個變量作為輸入，平均凈激活為希望的凈激活范圍：-1<net<+1因此：BP算法的實用技術權值初始化輸入層到隱含層的權值初始化隱含層到輸出層的權值初始化與輸出層連接的隱單元數(shù)BP算法的實用技術學習率：不同學習率的收斂效果Sigmoid網(wǎng)絡的學習率：初始化學習率約為0.1；如果發(fā)散，則調(diào)小學習率；如果學習速度過慢，則調(diào)大學習率。BP算法的實用技術沖量項（momentum）問題：在的區(qū)域，權值無法更新BP算法的實用技術沖量項（momentum）誤差曲面的“平坦區(qū)”較小，學習速度慢解決方法：如果讓當前學習保持上一步學習的“慣性”，則可以較快通過“平坦區(qū)”“慣性”的度量：沖量BP算法的實用技術沖量項（momentum）上一步（第m步）的更新量第m+1步的BP算法更新量帶沖量的反向傳播學習規(guī)則退化為BP算法勻速學習通常?。築P算法的實用技術帶沖量的隨機反向傳播算法BP算法的實用技術帶沖量的隨機反向傳播算法BP算法的實用技術權值衰減簡化網(wǎng)絡以及避免過擬合的方法：可以采用加入一個啟發(fā)式規(guī)則：即權值應當比較小實踐中，較小的權值往往可以提高神經(jīng)網(wǎng)絡性能。小權值更加適合線性的模型基本方法：從具有“非常多”的權值網(wǎng)絡開始，在訓練中衰減所有的權值§4徑向基函數(shù)網(wǎng)絡

(RadialBasisFunction,RBF)1.特點：①屬于前饋網(wǎng)絡。只有一個隱層，隱層輸出特性為徑向基函數(shù)，輸入層到隱層間的權值均為1；②輸出節(jié)點為線性求和，輸出權值可調(diào)。徑向基函數(shù)就是沿徑向?qū)ΨQ的標量函數(shù)。定義為空間任一點x到中心xc之間歐氏距離的單調(diào)函數(shù)。高斯徑向基函數(shù)：

xc

核函數(shù)中心，

s函數(shù)寬度。函數(shù)的變量為距離。網(wǎng)絡的輸出隱層的激活函數(shù)為RBF，輸出為加權線性和。RBF網(wǎng)絡的作用：①把網(wǎng)絡看成未知函數(shù)f(x)的逼近器。任何函數(shù)可表示成一組基函數(shù)的加權和，相當于用隱層單元的輸出函數(shù)構成一組基函數(shù)逼近f(x)。②從輸入層到隱層的基函數(shù)輸出是非線性映射,而輸出是線性的。即先將原始的非線性可分的特征空間變換到一個新的線性可分的空間,然后用一個線性單元來分類。在RBF網(wǎng)絡中有3組可調(diào)參數(shù)：①xc

(或記為ci)核函數(shù)中心、質(zhì)心；

②si方差，函數(shù)寬度、平滑參數(shù)；③wi輸出節(jié)點權值。2.常見的3種選擇方法：⑴根據(jù)經(jīng)驗選取函數(shù)中心xc：如在訓練樣本中根據(jù)經(jīng)驗選定M個中心xc，其中心之間距為d。則高斯核函數(shù)的方差可s為

⑵用聚類方法選擇：以各聚類中心作為核函數(shù)中心，而以各類樣本的方差作為各個基函數(shù)的寬度參數(shù)。權值wi的選擇：因為輸出單元是線性單元，它的權值wi可用基于均方差最小的最小二乘法計算。⑶將三組可調(diào)參數(shù)q通過訓練樣本用誤差d糾正算法求得。類似BP算法，分別計算d(k)對各組參數(shù)的偏導數(shù)，用為了得到較好的推廣能力，在訓練過程中可對質(zhì)心樣本點進行調(diào)整。每個函數(shù)都有自己的平滑參數(shù)s，在訓練中根據(jù)自身的情況確定。RBF除了應用歐氏距離外，也可應用馬氏距離。歐氏距離需要核函數(shù)數(shù)目多，馬氏距離需要估計更多的方差。通常用歐氏距離。3.RBF網(wǎng)絡與MLP的區(qū)別：①MLP所有隱層的神經(jīng)元的輸出形式都是相同的,MLP有好的擴展性；②RBF只對與xc中心歐氏距離相等的點輸出是相同的，隨距離不同按指數(shù)減小，因此激活響應是局部的，而MLP是全局的，所以RBF收斂快。③利用RBF網(wǎng)絡，對于任何函數(shù)f(x)都可找到一組權重系數(shù)來逼近這個函數(shù)，即有最佳逼近性質(zhì)。例：用RBF完成XOR的分類選擇隱層m=2,c1=[1,1]T,c2=[0,0]T,1/2si

2

=1,

k(x)=exp(-||x-ci||2)映射后對應的y值§5支持向量機SVM(非線性情況)在第3章中，廣義線性判別函數(shù)是通過構造新的高維特征向量，這樣可用線性判別函數(shù)解決非線性問題。同樣建立非線性支持向量機可分兩步：①將非線性樣本，從d維空間轉(zhuǎn)換到k維空間

F={f(x)：x∈X}，f：x→F②在新的特征空間中使用線性支持向量機。需將原d維非線性特征向量的空間X，映射到高維(k)的線性空間F，在此空間求廣義分類面。1.非線性空間變換方法：在線性支持向量機中的最優(yōu)分類函數(shù)在變換空間中定義適當?shù)膬?nèi)積函數(shù)K,此內(nèi)積函數(shù)可用原空間中的變量直接計算得到，這樣就不會增加計算的復雜度，即內(nèi)積xiTxj→

K(xiTxj)內(nèi)積函數(shù)統(tǒng)計學習理論指出，只要一種運算滿足Mercer條件，就可作為內(nèi)積函數(shù)。核函數(shù)就是這樣一種內(nèi)積函數(shù)。Mercer條件：

即對于滿足上面公式的函數(shù)K(x,x’),都存在用K(x,x’)定義的內(nèi)積空間。這樣的函數(shù)也稱為核。核函數(shù)也稱為勢函數(shù)。由勢能的概念引出。例如兩類模式樣本集在d維特征空間可看成一個點集，具有某種能量的點，在每類的中心(核)xc的能量最大，隨距離增大而減小。將附近空間上的點的能量用函數(shù)K(x,xc)來表示，這個函數(shù)就是核函數(shù)。兩個d維向量x和xk同時滿足下列三個條件，可作為核函數(shù)：①K(x,xk)=K(xk,x)，且當x＝xk時函數(shù)有最大值②x與xk的距離趨于無窮大時，K(x,xk)趨于零③K(x,xk)為光滑函數(shù)，且是x與xk之間距離的減函數(shù)。在支持向量機中常用的核函數(shù)：

2.支持向量機⑴算法用核函數(shù)代替最優(yōu)分類面中的點積，相當于把原特征空間變換到新的特征空間，則對偶問題求λi*，分類規(guī)則算法的其它條件均不變。⑵支持向量網(wǎng)絡輸出是中間層節(jié)點的線性組合，每一個中間層節(jié)點對應于輸入樣本與一個支持向量的內(nèi)積。該網(wǎng)絡與RBF網(wǎng)絡結構相似