第7章 分類方法(續(xù))

1、第第7章章 分類方法（續(xù)）分類方法（續(xù)） 7.5 神經(jīng)網(wǎng)絡(luò)算法神經(jīng)網(wǎng)絡(luò)算法 人工神經(jīng)網(wǎng)絡(luò)（人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Network，ANN）是）是對人類大腦系統(tǒng)特性的一種描述。簡單地講，它是一種數(shù)對人類大腦系統(tǒng)特性的一種描述。簡單地講，它是一種數(shù)學(xué)模型，可以用電子線路來實(shí)現(xiàn)，用計(jì)算機(jī)程序來模擬，學(xué)模型，可以用電子線路來實(shí)現(xiàn)，用計(jì)算機(jī)程序來模擬，是人工智能的一種方法。是人工智能的一種方法。神經(jīng)網(wǎng)絡(luò)通過對大量歷史數(shù)據(jù)的計(jì)算來建立分類和預(yù)神經(jīng)網(wǎng)絡(luò)通過對大量歷史數(shù)據(jù)的計(jì)算來建立分類和預(yù)測模型。測模型。 7.5.1 7.5.1 生物神經(jīng)元和人工神經(jīng)元生物神經(jīng)元和人工神經(jīng)元典型的神

2、經(jīng)元即神經(jīng)細(xì)胞結(jié)構(gòu)組成：胞體、樹突、軸突、突觸。典型的神經(jīng)元即神經(jīng)細(xì)胞結(jié)構(gòu)組成：胞體、樹突、軸突、突觸。胞體：胞體：神經(jīng)細(xì)胞的本體，完成普通細(xì)胞的生存功能。神經(jīng)細(xì)胞的本體，完成普通細(xì)胞的生存功能。樹突：樹突：有大量的分枝，接受來自其他神經(jīng)元的信號。有大量的分枝，接受來自其他神經(jīng)元的信號。軸突：軸突：用以輸出信號。用以輸出信號。突觸：突觸：神經(jīng)元相聯(lián)系的部位，對樹突的突觸為興奮性的，使神經(jīng)元相聯(lián)系的部位，對樹突的突觸為興奮性的，使下一個(gè)神經(jīng)元興奮；對胞體的突觸為抑制性的，阻止下一個(gè)下一個(gè)神經(jīng)元興奮；對胞體的突觸為抑制性的，阻止下一個(gè)神經(jīng)元興奮。神經(jīng)元興奮。1、生物神經(jīng)元、生物神經(jīng)元p神經(jīng)元的兩種

3、工作狀態(tài)：神經(jīng)元的兩種工作狀態(tài)：興奮興奮和和抑制抑制。p動(dòng)態(tài)極化原則：在每一個(gè)神經(jīng)元中，信息以預(yù)知的確定方動(dòng)態(tài)極化原則：在每一個(gè)神經(jīng)元中，信息以預(yù)知的確定方向流動(dòng)，即從神經(jīng)元的接收信息部分傳到軸突的電脈沖起向流動(dòng)，即從神經(jīng)元的接收信息部分傳到軸突的電脈沖起始部分，再傳到軸突終端的突觸，以與其它神經(jīng)元通信。始部分，再傳到軸突終端的突觸，以與其它神經(jīng)元通信。p連接的專一性原則：神經(jīng)元之間無細(xì)胞質(zhì)的連續(xù)，神經(jīng)元連接的專一性原則：神經(jīng)元之間無細(xì)胞質(zhì)的連續(xù)，神經(jīng)元不構(gòu)成隨機(jī)網(wǎng)絡(luò)，每一個(gè)神經(jīng)元與另一些神經(jīng)元構(gòu)成精確不構(gòu)成隨機(jī)網(wǎng)絡(luò)，每一個(gè)神經(jīng)元與另一些神經(jīng)元構(gòu)成精確的聯(lián)接。的聯(lián)接。神經(jīng)元的基本工作機(jī)制：神經(jīng)

4、元的基本工作機(jī)制：信號的傳遞過程：信號的傳遞過程：接受興奮電位；接受興奮電位；信號的匯集和傳導(dǎo)；信號的匯集和傳導(dǎo)；信號的輸出。信號的輸出。2. 人工神經(jīng)元人工神經(jīng)元人工神經(jīng)元用于模擬生物神經(jīng)元，人工神經(jīng)元可以看做人工神經(jīng)元用于模擬生物神經(jīng)元，人工神經(jīng)元可以看做是一個(gè)多輸入、單輸出的信息處理單元，它先對輸入變量進(jìn)是一個(gè)多輸入、單輸出的信息處理單元，它先對輸入變量進(jìn)行線性組合，然后對組合的結(jié)果做非線性變換。行線性組合，然后對組合的結(jié)果做非線性變換。因此可以將神經(jīng)元抽象為一個(gè)簡單的數(shù)學(xué)模型。因此可以將神經(jīng)元抽象為一個(gè)簡單的數(shù)學(xué)模型。 其中其中n個(gè)輸入個(gè)輸入xi表示其他神經(jīng)元的輸出值，即當(dāng)前神經(jīng)表示其

5、他神經(jīng)元的輸出值，即當(dāng)前神經(jīng)元的輸入值。元的輸入值。n個(gè)權(quán)值個(gè)權(quán)值wi相當(dāng)于突觸的連接強(qiáng)度。相當(dāng)于突觸的連接強(qiáng)度。f是一個(gè)非是一個(gè)非線性輸出函數(shù)。線性輸出函數(shù)。y表示當(dāng)前神經(jīng)元的輸出值。表示當(dāng)前神經(jīng)元的輸出值。神經(jīng)元的神經(jīng)元的工作過程工作過程一般是：一般是： 從各輸入端接收輸入信號從各輸入端接收輸入信號xi。 根據(jù)連接權(quán)值根據(jù)連接權(quán)值wi，求出所有輸入的加權(quán)和，即。，求出所有輸入的加權(quán)和，即。 對對net做非線性變換，得到神經(jīng)元的輸出，即做非線性變換，得到神經(jīng)元的輸出，即=f(net)。niiixwnet1f稱為稱為激活函數(shù)激活函數(shù)或或激勵(lì)函數(shù)激勵(lì)函數(shù)，它執(zhí)行對該神經(jīng)元所獲得輸，它執(zhí)行對該神經(jīng)

6、元所獲得輸入的變換，反映神經(jīng)元的特性。常用的激活函數(shù)類型如下。入的變換，反映神經(jīng)元的特性。常用的激活函數(shù)類型如下。（1）線性函數(shù)）線性函數(shù)f(x)=kx+c其中，其中，k、c為常量。線性函數(shù)常用于線性神經(jīng)網(wǎng)絡(luò)。為常量。線性函數(shù)常用于線性神經(jīng)網(wǎng)絡(luò)。（2）符號函數(shù)）符號函數(shù)f(x)=1當(dāng)當(dāng)x0f(x)=0當(dāng)當(dāng)x0；任何位于決策邊界下方的樣本（；任何位于決策邊界下方的樣本（）Xc，可以證明有，可以證明有WXc+b0Yz=- -1當(dāng)當(dāng)WXz+b0如果如果Yi=1WXi+b0如果如果Yi=- -1上述表達(dá)式可以用下面的不等式統(tǒng)一表示：上述表達(dá)式可以用下面的不等式統(tǒng)一表示：Yi(WXi+b)1在滿足上述約

7、束條件下，可以通過最小化在滿足上述約束條件下，可以通過最小化W2獲得具有最大獲得具有最大分類間隔的超平面對。也就是說，最大化決策區(qū)間的邊緣分類間隔的超平面對。也就是說，最大化決策區(qū)間的邊緣等價(jià)于在滿足上述約束條件下最小化以下目標(biāo)函數(shù)：等價(jià)于在滿足上述約束條件下最小化以下目標(biāo)函數(shù)：2)(2WWf或者，在可分情況下，線性或者，在可分情況下，線性SVM的學(xué)習(xí)任務(wù)可以形的學(xué)習(xí)任務(wù)可以形式化描述為以下優(yōu)化問題：式化描述為以下優(yōu)化問題：22WMINW受限于受限于Yi(WXi+b)1，i=1，2，N4. 線性可分線性可分SVM的求解過程的求解過程通過標(biāo)準(zhǔn)的拉格朗日乘子方法求解上述優(yōu)化問題。通過標(biāo)準(zhǔn)的拉格朗日

8、乘子方法求解上述優(yōu)化問題。首先，必須改寫目標(biāo)函數(shù)，考慮施加在解上的約束。新目首先，必須改寫目標(biāo)函數(shù)，考慮施加在解上的約束。新目標(biāo)函數(shù)稱為該優(yōu)化問題的拉格朗日函數(shù)：標(biāo)函數(shù)稱為該優(yōu)化問題的拉格朗日函數(shù)：NiiiiPbXWYWL12) 1)(21其中，其中，i稱為稱為拉格朗日乘子拉格朗日乘子。拉格朗日函數(shù)中的第一項(xiàng)。拉格朗日函數(shù)中的第一項(xiàng)與原目標(biāo)函數(shù)相同，而第二項(xiàng)則捕獲了不等式約束。與原目標(biāo)函數(shù)相同，而第二項(xiàng)則捕獲了不等式約束。（1）求拉格朗日乘子）求拉格朗日乘子i關(guān)于關(guān)于W、b最小化最小化LP，令，令LP關(guān)于關(guān)于i所有的導(dǎo)數(shù)為零，要所有的導(dǎo)數(shù)為零，要求使得約束求使得約束i0（稱此特殊約束集為（稱此

9、特殊約束集為C1）。）。由于是凸優(yōu)化問題，它可以等價(jià)地求解對偶問題：由于是凸優(yōu)化問題，它可以等價(jià)地求解對偶問題：最大化最大化LP，使得，使得LP關(guān)于關(guān)于W、b的偏導(dǎo)數(shù)為零，并使得的偏導(dǎo)數(shù)為零，并使得i0（稱此特殊約束集為（稱此特殊約束集為C2）。這是根據(jù)對偶性得到的，）。這是根據(jù)對偶性得到的，即在約束即在約束C2下最大化下最大化LP所得到的所得到的W、b值，與在約束值，與在約束C1下下最小化最小化LP所得所得W、b的值相同。的值相同。令令LP關(guān)于關(guān)于W、b的導(dǎo)數(shù)為零，即：的導(dǎo)數(shù)為零，即：由于對偶形式中的等式約束，代入由于對偶形式中的等式約束，代入LP得得拉格朗日乘子有不同的下標(biāo)，拉格朗日乘子有

10、不同的下標(biāo)，P對應(yīng)原始問題，對應(yīng)原始問題，D對應(yīng)對應(yīng)對偶問題，對偶問題，LP和和LD由同一目標(biāo)函數(shù)導(dǎo)出，但具有不同約束。由同一目標(biāo)函數(shù)導(dǎo)出，但具有不同約束。也就是說，線性可分情況下的支持向量訓(xùn)練相當(dāng)于在也就是說，線性可分情況下的支持向量訓(xùn)練相當(dāng)于在約束及約束及i0條件下，關(guān)于條件下，關(guān)于i最大化最大化LD。需要注意的是，該問題仍然是一個(gè)有約束的最優(yōu)化問需要注意的是，該問題仍然是一個(gè)有約束的最優(yōu)化問題，需要進(jìn)一步使用題，需要進(jìn)一步使用數(shù)值計(jì)算技術(shù)數(shù)值計(jì)算技術(shù)通過訓(xùn)練樣本數(shù)據(jù)求解通過訓(xùn)練樣本數(shù)據(jù)求解i。NiiiY10（2）求）求W參數(shù)參數(shù)通過求解出通過求解出W。NiiiiXYW1（3）求）求b參數(shù)

11、參數(shù)b需滿足約束條件為需滿足約束條件為Yi(WXi+b)1不等式。不等式。處理不等式約束的一種方法就是把它變換成一組等式處理不等式約束的一種方法就是把它變換成一組等式約束。只要限制約束。只要限制i非負(fù)，這種變換是可行的。這種變換導(dǎo)非負(fù)，這種變換是可行的。這種變換導(dǎo)致如下拉格朗日乘子約束，稱為致如下拉格朗日乘子約束，稱為Karuch-kuhn-Tucher（KKT）條件：）條件：i0i(Yi(WXi+b)- -1)=0上述上述KKT條件轉(zhuǎn)化為條件轉(zhuǎn)化為Yi(WXi+b)- -1=0，即：當(dāng)，即：當(dāng)Yi=1時(shí)，時(shí)，b=1- -WXi；當(dāng)；當(dāng)Yi=- -1時(shí)，時(shí)，b=- -1- -WXi。由于由于i

12、采用數(shù)值計(jì)算得到，可能存在誤差，計(jì)算出的采用數(shù)值計(jì)算得到，可能存在誤差，計(jì)算出的b可能不唯一，通常使用可能不唯一，通常使用b的平均值作為決策邊界的參數(shù)。的平均值作為決策邊界的參數(shù)。當(dāng)求出當(dāng)求出W、b的可行解后，可以構(gòu)造出決策邊界，分類的可行解后，可以構(gòu)造出決策邊界，分類問題即得以解決。問題即得以解決?！纠纠?.67.6】對于二維空間，以表對于二維空間，以表7.14所示的所示的8個(gè)點(diǎn)作為訓(xùn)個(gè)點(diǎn)作為訓(xùn)練樣本，求出其線性可分練樣本，求出其線性可分SVM的決策邊界。假設(shè)已求出每的決策邊界。假設(shè)已求出每個(gè)訓(xùn)練樣本的拉格朗日乘子。個(gè)訓(xùn)練樣本的拉格朗日乘子。點(diǎn)編號點(diǎn)編號iXiYi拉格朗日乘子拉格朗日乘子i

13、x1x210.38580.4687-165.526120.48710.611165.526130.92180.41031040.73820.89361050.17630.0579-1060.40570.3529-1070.93550.81321080.21460.0099-10令令W=(w1，w2)，b為決策邊界的參數(shù)。這里為決策邊界的參數(shù)。這里N=8。則：。則：對于訓(xùn)練樣本對于訓(xùn)練樣本1（Y1=- -1），有：），有：對于訓(xùn)練樣本對于訓(xùn)練樣本2（Y2=1），有：），有：取取b1、b2的平均值得到的平均值得到b=- -7.93，則決策邊界為：，則決策邊界為： 6.64x1+9.32x2- -7

14、.93=0對應(yīng)該決策邊界的顯示如下圖所示。對于訓(xùn)練樣本對應(yīng)該決策邊界的顯示如下圖所示。對于訓(xùn)練樣本X=(x1，x2)，若，若6.64x1+9.32x2- -7.930，則劃分于類別，則劃分于類別1中；中；若若6.64x1+9.32x2- -7.930，則劃分于類別，則劃分于類別- -1中。中。7.6.2 7.6.2 線性不可分時(shí)的二元分類問題線性不可分時(shí)的二元分類問題 在實(shí)際情況中，很多問題是線性不可分的，如圖在實(shí)際情況中，很多問題是線性不可分的，如圖7.51所所示的樣本集便是如此，無法找到一個(gè)理想的超平面，能將兩示的樣本集便是如此，無法找到一個(gè)理想的超平面，能將兩類樣本完全分開。類樣本完全分

15、開。由于樣本線性不可分，原來對間隔的要求不能達(dá)到，由于樣本線性不可分，原來對間隔的要求不能達(dá)到，可以采用一種稱為軟邊緣的方法，學(xué)習(xí)允許一定訓(xùn)練錯(cuò)誤可以采用一種稱為軟邊緣的方法，學(xué)習(xí)允許一定訓(xùn)練錯(cuò)誤的決策邊界。的決策邊界。也就是在一些類線性不可分的情況下構(gòu)造線性的決策也就是在一些類線性不可分的情況下構(gòu)造線性的決策邊界，為此必須考慮邊緣的寬度與線性決策邊界允許的訓(xùn)邊界，為此必須考慮邊緣的寬度與線性決策邊界允許的訓(xùn)練錯(cuò)誤數(shù)目之間的練錯(cuò)誤數(shù)目之間的折中折中。對于線性不可分的問題，原目標(biāo)函數(shù)仍然是對于線性不可分的問題，原目標(biāo)函數(shù)仍然是可用的，但原決策邊界不再滿足可用的，但原決策邊界不再滿足Yi(WXi+

16、b)1給定的所有約給定的所有約束。為此使約束條件弱化，以適應(yīng)線性不可分樣本。束。為此使約束條件弱化，以適應(yīng)線性不可分樣本?？梢酝ㄟ^在優(yōu)化問題的約束中引入正值的可以通過在優(yōu)化問題的約束中引入正值的松弛變量松弛變量來實(shí)來實(shí)現(xiàn)（松弛變量現(xiàn)（松弛變量用于描述分類的損失），即：用于描述分類的損失），即：2)(2WWfWXi+b1- -i，如果，如果Yi=1WXi+b- -1- -i， 如果如果Yi=- -1其中，對于任何訓(xùn)練樣本其中，對于任何訓(xùn)練樣本Xi，i0。理解松弛變量理解松弛變量i的含義的含義:顯然希望松弛變量顯然希望松弛變量最小化（如果最小化（如果=0，則就是前面的線，則就是前面的線性可分問題）

17、。于是，在優(yōu)化目標(biāo)函數(shù)中使用性可分問題）。于是，在優(yōu)化目標(biāo)函數(shù)中使用懲罰參數(shù)懲罰參數(shù)C來來引入對引入對最小化的目標(biāo)。這樣，修改后的目標(biāo)函數(shù)如下：最小化的目標(biāo)。這樣，修改后的目標(biāo)函數(shù)如下：kNiiCWWf122)(這樣，求解的問題變?yōu)椋哼@樣，求解的問題變?yōu)椋?kNiibWCWMIN12,2受限于受限于Yi(WXi)+b)+1)1- -i，i=1，2，N這個(gè)優(yōu)化問題仍然是一個(gè)凸優(yōu)化問題。采用與前一節(jié)這個(gè)優(yōu)化問題仍然是一個(gè)凸優(yōu)化問題。采用與前一節(jié)類似的方法求解。類似的方法求解。 C是一個(gè)必須事先指定的值是一個(gè)必須事先指定的值 除了上述軟邊緣的方法外，還有一種非線性硬間隔方法，除了上述軟邊緣的方法外，

18、還有一種非線性硬間隔方法，其基本思路是：將低維空間中的曲線（曲面）映射為高維空其基本思路是：將低維空間中的曲線（曲面）映射為高維空間中的直線或平面。數(shù)據(jù)經(jīng)這種映射后，在高維空間中是線間中的直線或平面。數(shù)據(jù)經(jīng)這種映射后，在高維空間中是線性可分的。性可分的。 SVM有如下主要有如下主要幾個(gè)特點(diǎn)幾個(gè)特點(diǎn)：（1）由于）由于SVM的求解最后轉(zhuǎn)化成二次規(guī)劃問題的求解，的求解最后轉(zhuǎn)化成二次規(guī)劃問題的求解，因此因此SVM的解是的解是全局唯一的最優(yōu)解全局唯一的最優(yōu)解。（2）SVM在解決在解決小樣本、非線性及高維模式識別問題小樣本、非線性及高維模式識別問題中表現(xiàn)出許多特有的優(yōu)勢中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應(yīng)用到函數(shù)擬合等，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問題中。其他機(jī)器學(xué)習(xí)問題中。（3）SVM是一種是一種有堅(jiān)實(shí)理論基礎(chǔ)有堅(jiān)實(shí)理論基礎(chǔ)的新穎的小樣本學(xué)習(xí)的新穎的小樣本學(xué)習(xí)方法。它基本上不涉及概率測度及大數(shù)定律等，因此不同方法。它基本上不涉及概率測度及大數(shù)定律等，因此不同于現(xiàn)有的統(tǒng)計(jì)方法。從本質(zhì)上看，它避開了從歸納到演繹于現(xiàn)有的統(tǒng)計(jì)方法。從本質(zhì)上看，它避開了從歸納到演繹的傳統(tǒng)過程，實(shí)現(xiàn)了高效的從訓(xùn)練樣本到預(yù)報(bào)樣本的的傳統(tǒng)過程，實(shí)現(xiàn)了高效的從訓(xùn)練樣本到預(yù)報(bào)樣本的“轉(zhuǎn)轉(zhuǎn)導(dǎo)推理導(dǎo)推理”，大大簡化了通常的分類和回歸等問題。，大大簡化了通常的分類和回歸等問題。（4）SVM的最終決策