聚類算法隨堂課件svm

1、法律IT教育品牌EDUCATION TO CREATE A BRIGHT FUTURE本課件包括演示文稿、示例、代碼、題庫、和聲音等內(nèi)容，北風(fēng)網(wǎng)和講師擁有完全知識產(chǎn)權(quán)；只限于善意學(xué)習(xí)者在本課程使用，不得在課程范圍外向任何第散播。任何其他人或者機(jī)構(gòu)不得盜版、內(nèi)容，我們保留一切通過法律、仿造其中的創(chuàng)意和者的權(quán)利。課程咨詢：北風(fēng)教育：http:/IT在線教育領(lǐng)導(dǎo)品牌EDUCATION TO CREATE A BRIGHT FUTUREIT教育品牌課程要求EDUCATION TO CREATE A BRIGHT FUTURE課上課下“九字”真言認(rèn)真聽，善摘錄，勤思考多溫故，樂實踐，再發(fā)散四不原則不懶散

2、惰性，不早退不請假，不拖延作業(yè)一點注意事項“四不原則”，不包就業(yè)和推薦就業(yè)3IT教育品牌嚴(yán)格是大愛EDUCATION TO CREATE A BRIGHT FUTURE4IT教育品牌寄語EDUCATION TO CREATE A BRIGHT FUTURE5IT教育品牌課程內(nèi)容EDUCATION TO CREATE A BRIGHT FUTURE梯度下降法、拉格朗日乘子法、KKT條件回顧感知器模型回顧SVM線性可分SVM線性不可分核函數(shù)SMO6IT教育品牌梯度下降法EDUCATION TO CREATE A BRIGHT FUTURE梯度下降法(Gradient Descent， GD)常用于

3、求解無約束情況下凸函數(shù)(ConvexFunction)的極小值，是一種迭代類型的算法，因為凸函數(shù)只有一個極值點，故求解出來的極小值點就是函數(shù)的最小值點。(hq(i ) )-(i ) )2måJ (q) = 1xy2mi=1= arg min J (q)qq*7IT教育品牌梯度下降法EDUCATION TO CREATE A BRIGHT FUTURE導(dǎo)數(shù)：一個函數(shù)在某一點的導(dǎo)數(shù)描述了這個函數(shù)在這一點附近的變化率，也可以認(rèn)為是函數(shù)在某一點的導(dǎo)數(shù)就是該函數(shù)所代表的曲線在這一點的切線斜率。導(dǎo)數(shù)值越大，表示函數(shù)在該點處的變化越大。梯度：梯度是一個向量，表示某一函數(shù)在該點處的方向?qū)?shù)沿著該方向

4、取的最大值，即函數(shù)在該點處沿著該方向變化最快，變化率最大(即該梯度向量的模)；當(dāng)函數(shù)為一維函數(shù)的時候，梯度其實就是導(dǎo)數(shù)。y¢ = ¶f (x)¶xæ ¶f (x1 , x2 ) ¶f (x1 , x2 )öÑf (x1 , x2 ) = çè÷ø,¶x¶x128IT教育品牌梯度下降法EDUCATION TO CREATE A BRIGHT FUTURE梯度下降法的優(yōu)化思想是用當(dāng)前位置負(fù)梯度方向作為搜索方向，因為該方向為當(dāng)前位置的最快下降方向，所以梯度下降法

5、也被稱為“最速下降法”。梯度下降法中越接近目標(biāo)值，變量變化越小。計算公式如下：=qk -aÑf (qk )qk +1被稱為步長或者學(xué)習(xí)率(learning rate)，表示自變量x每次迭代變化的大小。收斂條件：當(dāng)目標(biāo)函數(shù)的函數(shù)值變化非常小的時候或者達(dá)到最大迭代次數(shù)的時候，就結(jié)束循環(huán)。9IT教育品牌梯度下降法EDUCATION TO CREATE A BRIGHT FUTURE由于梯度下降法中負(fù)梯度方向作為變量的變化方向，所以有可能導(dǎo)致最終求解的值是局部最優(yōu)解，所以在使用梯度下降的時候，一般需要進(jìn)行一些調(diào)優(yōu)策略：學(xué)習(xí)率的選擇：學(xué)習(xí)率過大，表示每次迭代更新的時候變化比較大，有可能會跳過

6、最優(yōu)解；學(xué)習(xí)率過小，表示每次迭代更新的時候變化比較小，就會導(dǎo)致迭代速度過慢，很長時間都不能結(jié)束；算法初始參數(shù)值的選擇：初始值不同，最終獲得的最小值也有可能不同，因為梯度 下降法求解的是局部最優(yōu)解，所以一般情況下，選擇多次不同初始值運行算法，并最終返回?fù)p失函數(shù)最小情況下的結(jié)果值；標(biāo)準(zhǔn)化：由于樣本不同特征的取值范圍不同，可能會導(dǎo)致在各個不同參數(shù)上迭代速 度不同，為了減少特征取值的影響，可以將特征進(jìn)行標(biāo)準(zhǔn)化操作。10IT教育品牌梯度下降法EDUCATION TO CREATE A BRIGHT FUTURE批量梯度下降法(Batch Gradient Descent, BGD)：使用所有樣本在當(dāng)前點

7、的梯度值來對變量參數(shù)進(jìn)行更新操作。()måqk +1=qk -aÑfxiqki=1隨機(jī)梯度下降法(Stochastic Gradient Descent, SGD)：在更新變量參數(shù)的時候，選取一個樣本的梯度值來更新參數(shù)。(xi )qk +1=qk -aÑfqk小批量梯度下降法(Mini-batch Gradient Descent, MBGD)：集合BGD和SGD的特性，從原始數(shù)據(jù)中，每次選擇n個樣本來更新參數(shù)值，一般n選擇10.t +n-Ñfqk (i )1åk +1q=q -akxi=t11IT教育品牌梯度下降法EDUCATION TO C

8、REATE A BRIGHT FUTUREBGD、SGD、MBGD的區(qū)別：當(dāng)樣本量為m的時候，每次迭代BGD算法中對于參數(shù)值更新一次，SGD算法中對于 參數(shù)值更新m次，MBGD算法中對于參數(shù)值更新m/n次，相對來講SGD算法的更新速度最快；SGD算法中對于每個樣本都需要更新參數(shù)值，當(dāng)樣本值不太正常的時候，就有可能 會導(dǎo)致本次的參數(shù)更新會產(chǎn)生相反的影響，也就是說SGD算法的結(jié)果并不是完全收斂的，而是在收斂結(jié)果處波動的；SGD算法是每個樣本都更新一次參數(shù)值，所以SGD算法特別適合樣本數(shù)據(jù)量大的情況以及學(xué)習(xí)(Online ML)。12IT教育品牌梯度下降法案例代碼EDUCATION TO CREAT

9、E A BRIGHT FUTURE13IT教育品牌梯度下降法案例代碼EDUCATION TO CREATE A BRIGHT FUTURE14IT教育品牌梯度下降法案例代碼EDUCATION TO CREATE A BRIGHT FUTURE15IT教育品牌有約束的最優(yōu)化問題EDUCATION TO CREATE A BRIGHT FUTURE最優(yōu)化問題一般是指對于某一個函數(shù)而言，求解在其指定作用域上的全局最小值問題，一般分為以下三種情況(備注：以下幾種方式求出來的解都有可能是局部極小值，只有當(dāng)函數(shù)是凸函數(shù)的時候，才可以得到全局最小值)：無約束問題：求解方式一般求解方式梯度下降法、牛頓法、坐標(biāo)

10、軸下降法等； 等式約束條件：求解方式一般為拉格朗日乘子法不等式約束條件：求解方式一般為KKT條件min f (x)min f (x)xs.t : hk (x) = 0, k = 1,2,., px £ 0, j = 1,2,., qmin f ( )xxsubject.to : hk (x) = 0, k = 1,2,., pxg j ( )16IT教育品牌拉格朗日乘子法EDUCATION TO CREATE A BRIGHT FUTURE拉格朗日乘子法就是當(dāng)我們的優(yōu)化函數(shù)存在等值約束的情況下的一種最優(yōu)化求解方式；其中參數(shù)被稱為拉格朗日乘子，要求不等于0min f (x)xs.t :

11、 hi (x) = 0, i = 1,2,., p¯pmin f (x)+ah (x)åi=1a¹ 0;iiix17IT教育品牌拉格朗日乘子法理解假設(shè)現(xiàn)在有一個二維的優(yōu)化問題EDUCATION TO CREATE A BRIGHT FUTUREmin f (x, y)x, ys.t : g(x, y) = cf (x, y)+a(g(x, y)- c);a¹ 0L(x, y,a) =ìïmin f (x, y)Þ min L(x, y,a)x, yíïîg(x, y)- c = 0x, y

12、09; x, y ,aL(x, y,a) = 0,a¹ 0數(shù)學(xué)證明:https/view/ac56710e2e3f5727a5e962a7.html18IT教育品牌對偶問題EDUCATION TO CREATE A BRIGHT FUTURE在優(yōu)化問題中，目標(biāo)函數(shù)f(x)存在多種形式，如果目標(biāo)函數(shù)和約束條件都為變量x的線性函數(shù)，則稱問題為線性；如果目標(biāo)函數(shù)為二次函數(shù)，則稱最優(yōu)化問題為二次；如果目標(biāo)函數(shù)或者約束條件為非線性函數(shù)，則稱最優(yōu)化問題為非線性優(yōu)化。每個線性性：問題都有一個對應(yīng)的對偶問題。對偶問題具有以下幾個特1. 對偶問題的對偶是原問題；2. 無論原始問題是否是凸的，對偶問題都

13、是凸優(yōu)化問題；3. 對偶問題可以給出原始問題的一個下界；4. 當(dāng)滿足一定條件的時候，原始問題和對偶問題的解是完美等價的。19IT教育品牌KKT條件EDUCATION TO CREATE A BRIGHT FUTUREKKT條件是泛拉格朗日乘子法的一種形式；主要應(yīng)用在當(dāng)我們的優(yōu)化函數(shù)存在不等值約束的情況下的一種最優(yōu)化求解方式；KKT條件即滿足不等式約束情況下的min f (x)條件。xs.t : hk (x) = 0, k = 1,2,., pg j (x) £ 0, j = 1,2,., q¯pqL(x,a,b) = f (x)+ åai hi (x)+ 

14、9;bi gi (x);ai¹ 0,bi ³ 0i=1i=1min L(x,a,b)x20min f (x)IT教育品牌KKT條件理解可行解必須在約束區(qū)域g(x)之內(nèi)，由圖可知可行解x 只能在g(x)<0和g(x)=0的區(qū)域取得；當(dāng)可行解x在g(x)<0的區(qū)域中的時候，此時直接極小 化f(x)即可得到；當(dāng)可行解x在g(x)=0的區(qū)域中的時候，此時直接等價 于等式約束問題的求解。EDUCATION TO CREATE A BRIGHT FUTURExs.t : g(x) £ 021IT教育品牌KKT條件理解當(dāng)可行解在約束內(nèi)部區(qū)域的時候，令=0即可消去約束

15、。EDUCATION TO CREATE A BRIGHT FUTURE對于參數(shù)的取值而言，在等值約束中，約束函數(shù)和目標(biāo)函數(shù)的梯度只要滿足平行即可，而在不等式約束中，若0，則說明可行解在約束區(qū)域的邊界上，這個時候可行解應(yīng)該盡可能的靠近無約束情況下的解，所以在約束邊界上，目標(biāo)函數(shù)的負(fù)梯度方向應(yīng)該遠(yuǎn)離約束區(qū)域朝無約束區(qū)域時的解，此時約束函數(shù)的梯度方向與目標(biāo)函數(shù)的負(fù)梯度方向應(yīng)相同；從而可以得出>0。- Ñ x f (x) = bÑ x g(x)22IT教育品牌KKT理解EDUCATION TO CREATE A BRIGHT FUTUREmin f (x)xs.t :L(x

16、,b) =g j (x) £ 0, j = 1,2,., qqf (x)+ åbi gi (x);bii=1³ 0b ³ 0ü Þ bg (x) £ 0iQg (x) £ 0ýiiþi f (x) = max L(x,b)bmin f (x) = min max L(x,b)bxx23IT教育品牌KKT理解EDUCATION TO CREATE A BRIGHT FUTUREmax min L(x,b) = max min f (x)+ min bg(x)b= max min f (x)+ ma

17、x min bg(x) = min f (x)+ max min bg(x)bbxb ³ 0Qiüìb0為0或者g (x)為0，()Þ min bg=xg (x) £ 0ýí- ¥，b> 0且g (x) < 0iiþîximax min bi gi (x) = 0bxmin f (x) = max min L(x,b)；b= 0或者g (x) = 0bxx24IT教育品牌KKT理解EDUCATION TO CREATE A BRIGHT FUTUREmin f (x) = min m

18、ax L(x,b)min f (x) = max min L(x,b)bbxxxxmin max L(x,b) = max min L(x,b)bbxx原問題對偶問題對偶問題的直觀理解：最小的里面的那個最大的要比最大的那個里面的最小的大；從而就可以為原問題引入一個下界25IT教育品牌KKT條件總結(jié)EDUCATION TO CREATE A BRIGHT FUTURE1. 拉格朗日取得可行解的充要條件；2. 將不等式約束轉(zhuǎn)換后的一個約束，稱為松弛互補(bǔ)條件；1).Ñ x L(x,a,b) = 02).bi gi (x) = 0, i = 1,2,., q3).hi (x) = 0, i

19、= 1,2,., p4).gi (x) £ 0, i = 1,2,., q3. 初始的約束條件；4. 初始的約束條件；5. 不等式約束需要滿足的條件。5).bi³ 0, i = 1,2,., q26IT教育品牌高中距離知識回顧EDUCATION TO CREATE A BRIGHT FUTURE點到直線/平面的距離公式：假定點p(x0,y0)，平面方程為f(x,y)=Ax+By+C，那么點p到平面f(x)的距離為:Ax0 + By0 + Cdist =A2+ B2從三擴(kuò)展到空間中，如果存在一個超平面f(X)=X+b; 那么某一個點X0到這個超平面的距離為:f (X0 )函數(shù)

20、距離dist =q幾何距離2參考https：/view/d26d2ba39e31433239689374.html27IT教育品牌感知器模型EDUCATION TO CREATE A BRIGHT FUTURE感知器算法是最古老的分類算法之一，原理比較簡單，不過模型的分類泛化能力比較弱，不過感知器模型是SVM、神經(jīng)網(wǎng)絡(luò)、深度學(xué)習(xí)等算法的基礎(chǔ)。感知器的思想很簡單：比如北風(fēng)上有很多的學(xué)員，分為男學(xué)員和女學(xué)員，感知器模型就是試圖找到一條直線，能夠把所有的男學(xué)員和女學(xué)員分隔開，如果是高維空間中，感知器模型尋找的就是一個超平面，能夠把所有的二元類別分割開。感知器模型的前提是：數(shù)據(jù)是線性可分的。28IT教

21、育品牌感知器模型對于m個樣本，每個樣本n維特征以及一個二元類別輸出y，如下：EDUCATION TO CREATE A BRIGHT FUTURE(), (),., (= 0)(1)(2)n(m )nn目標(biāo)是找到一個超平面，即：q0 +q1讓一個類別的樣本滿足：q· x > 0 ；另外一個類別的滿足：q· x < 0感知器模型為:ì+1,q· x > 0y = sign(q· x) =í-1,q· x < 0î29IT教育品牌感知器模型EDUCATION TO CREATE A BRIGHT

22、 FUTURE正確分類：yx>0，錯誤分類：yx<0；所以我們可以定義我們的損害函數(shù)為：期望使分類錯誤的所有樣本(m條樣本)到超平面的距離之和最小。- y(i )q· x(i )mL = åqi=12因為此時大，也就是說和分母中都包含了值，當(dāng)擴(kuò)大N倍的時候，分母也會隨之?dāng)U和分母之間存在倍數(shù)關(guān)系，所以可以固定或者分母為1，然后求另一個即為（分母為1）:或者分母的倒數(shù)的最小化作為損失函數(shù)，簡化后的損失函數(shù)mL = -åi=1y(i )q· x(i )30IT教育品牌mL = -å感知器模型y(i )q· x(i )EDUCAT

23、ION TO CREATE A BRIGHT FUTUREi=1直接使用梯度下降法就可以對損失函數(shù)求解，不過由于這里的m是分類錯誤的樣本點集合，不是固定的，所以我們不能使用批量梯度下降法(BGD)求解，只能使用隨機(jī)梯度下降(SGD)或者小批量梯度下降(MBGD)；一般在感知器模型中使用SGD來求解。¶L(q) = -åmy(i )x(i )¶qi=1+ ay(i )x(i )q k +1= q k31IT教育品牌SVMEDUCATION TO CREATE A BRIGHT FUTURE支持向量機(jī)(Support Vecor Machine, SVM)本身是一個二

24、元分類算法，是對感知器算法模型的一種擴(kuò)展，現(xiàn)在的SVM算法支持線性分類和非線性分類的分類應(yīng)用，并且也能夠直接將SVM應(yīng)用于回歸應(yīng)用中，同時通過OvR或者OvO的方式我們也可以將SVM應(yīng)用在多元分類領(lǐng)域中。在不考慮集成學(xué)習(xí)算法，不考慮特定的數(shù)據(jù)集的時候，在分類算法中SVM可以說是特別優(yōu)秀的。32IT教育品牌線性可分SVMEDUCATION TO CREATE A BRIGHT FUTURE在感知器模型中，算法是在數(shù)據(jù)中找出一個劃分超平面，讓盡可能多的數(shù)據(jù)分布在這個平面的兩側(cè)，從而達(dá)到分類的效果，但是在實際數(shù)據(jù)中這個符合我們要求的超平面是可能存在多個的。33IT教育品牌線性可分SVMEDUCATI

25、ON TO CREATE A BRIGHT FUTURE在感知器模型中，我們可以找到多個可以分類的超平面將數(shù)據(jù)，并且優(yōu)化時希望所有的點都離超平面盡可能的遠(yuǎn)，但是實際上離超平面足夠遠(yuǎn)的點基本上都是被正確分類的，所以這個是沒有意義的；反而比較關(guān)心那些離超平面很近的點， 這些點比較容易分錯。所以說我們只要讓離超平面比較近的點盡可能的遠(yuǎn)離這個超平面，那么我們的模型分類效果應(yīng)該就會比較不錯嘍。SVM其實就是這個思想。34IT教育品牌線性可分SVMEDUCATION TO CREATE A BRIGHT FUTURE線性可分(Linearly Separable)：在數(shù)據(jù)集中，如果可以找出一個超平面，將兩

26、組數(shù)據(jù)，那么這個數(shù)據(jù)集叫做線性可分?jǐn)?shù)據(jù)。線性不可分(Linear Inseparable)：在數(shù)據(jù)集中，沒法找出一個超平面，能夠?qū)山M數(shù)據(jù)，那么這個數(shù)據(jù)集就叫做線性不可分?jǐn)?shù)據(jù)。分割超平面(Separating Hyperplane)：將數(shù)據(jù)集分割開來的直線/平面叫做分割超平面。間隔(Margin)：數(shù)據(jù)點到分割超平面的距離稱為間隔。支持向量(Support Vector)：離分割超平面最近的那些點叫做支持向量。35IT教育品牌線性可分SVMEDUCATION TO CREATE A BRIGHT FUTURE支持向量到超平面的距離為：Q wT x + b = ±1Q y Î

27、+1,-1y(wT x + b)1=ww22備注：在SVM中支持向量到超平面的函數(shù)距離一般設(shè)置為136IT教育品牌線性可分SVMEDUCATION TO CREATE A BRIGHT FUTURESVM模型是讓所有的分類點在各自類別的支持向量的兩邊，同時要求支持向量盡可能的原理這個超平面，用數(shù)學(xué)公式表示如下：1maxww,b2s.t : y(i ) (wT x(i ) + b)³ 1, i = 1,2,., m37IT教育品牌線性可分SVMEDUCATION TO CREATE A BRIGHT FUTUREmax 1 = (w , w ,., w )wTw12nw,b2s.t :

28、 y(i ) (wT x(i ) + b)³ 1, i = 1,2,., m=+ w2 + . + w2w2w12n2min 122w2w,b¾優(yōu)¾化¾問題¾等價¾于®s.t : y(i ) (wT x(i ) + b)³ 1, i = 1,2,., m38IT教育品牌線性可分SVMEDUCATION TO CREATE A BRIGHT FUTURESVM目標(biāo)函數(shù)/損失函數(shù)為：J (w) = 122w優(yōu)化¾目¾¾標(biāo)® w*, b*= min J (w)2s.t : y(i

29、) (wT x(i ) + b)³ 1, i = 1,2,., mw,b39IT教育品牌線性可分SVMEDUCATION TO CREATE A BRIGHT FUTURE將此時的目標(biāo)函數(shù)和約束條件使用KKT條件轉(zhuǎn)換為拉格朗日函數(shù)，從而轉(zhuǎn)換為無約束的優(yōu)化函數(shù)。J (w) = 1J (w) = 122Þ22ww22s.t :1- y(i ) (wT x(i ) + b)£ 0, i = 1,2,., ms.t : y(i ) (wT x(i ) + b)³ 1, i = 1,2,., m¯b -b) b ³(b) = 1m+ å

30、;i=1(i )T(i ) +22L w, b,w1yw x,0ii240IT教育品牌w x+ b)(12må()線性可分SVM(i )T(i )22L w, b,b =+b 1- y,b ³ 0wEDUCATION TO CREATE A BRIGHT FUTUREiii=1引入拉格朗日乘子后，優(yōu)化目標(biāo)變成：min max L(w, b,b)b³0w,b根據(jù)拉格朗日對偶化特性，將該優(yōu)化目標(biāo)轉(zhuǎn)換為等價的對偶問題來求解，從而優(yōu)化目標(biāo)變成：max min L(w, b,b)b³0w,b所以對于該優(yōu)化函數(shù)而言，可以先求優(yōu)化函數(shù)對于w和b的極小值，然后再求解對于

31、拉格朗日乘子的極大值。41max min L(w, b,b)IT教育品牌線性可分SVMEDUCATION TO CREATE A BRIGHT FUTUREb³0w,bb -b) b ³1y(m+ åb) = 1(i )T(i ) +22L w, b,ww x,0ii2i=1首先求讓函數(shù)L極小化的時候w和b的取值，這個極值可以直接通過對函數(shù)L分別求w和b的偏導(dǎo)數(shù)得到：¶L = 0 Þ w - åmmå(i )(i )(i )(i )byx=0 Þw =byxii¶wi=1i=1¶L = 0 &#

32、222; -åmmå(i )(i )by= 0Þby=0ii¶bi=1i=142b -1y(b) = 1m+ å(i )T(i ) I+T b教育³22品牌L w, b,ww x線性可分SVMii2mw = åEDUCATION TO CREATE A BRIGHT FUTUREi=1må(i ) (i )(i )by= 0byxiii=1i=1將求解出來的w和b帶入優(yōu)化函數(shù)L中，定義優(yōu)化之后的函數(shù)如下：1- y(w x+ b)m+ åi=1m- ål(b) = 1(i )T(i )22bwi2

33、y(w x+ b)-1= 1(i )T(i )22bwmmiÞ l(b) = åb - 12å i(i )( j )(i ) x( j )Ti=1bb yyxm= 1 wT w - åmmijåå(i )T(i )(i )2byw x-byb +bi=1i=1, j =1iii2i=1i=1i=1mm= 1 wT åmmms.t : å(i )ååå(i ) (i )(i ) (i )(i )by= 0byx- wbyx- bby+bTiiii2ii=1i=1i=1i=1i=1m= -

34、 1 wT åmmåå i(i ) (i )(i )byx- bby+biib ³ 0, i = 1,2,., m2i=1i=1i=1iöT æ1 æömmmçåbyåå(i )x(i ) ÷(i ) (i )= -çbyx÷ +biii212è i=1ø è i=1øi=1mmmå iå iå i(i ) (i )(i ) (i )T= -byxbyx+bi=1i=1i=1m

35、12mmå iåå ij(i )( j ) (i )( j )T=b -i=1bb yyxxi=1 j =143b -1y(b) = 1m+ å(i )T(i ) +IT22b教育³品牌L w, b,ww x線性可分SVMii2EDUCATION TO CREATE A BRIGHT FUTUREi=1max min L(w, b,b)m1mål(b) = åbi - 2(i ) ( j ) (i )T( j )bibj yyxxb³0w,bi=1i=1, j =1通過對w、b極小化后，我們最終得到的優(yōu)化函數(shù)只和有

36、關(guān)，所以此時我們可以直接極大化我們的優(yōu)化函數(shù)，得到的值，從而可以最終得到w和b的值。max l(b)min- l(b)b³0b³0¾等¾價¾于®¯mms.t : åby= 0( )åi=1(i )iby=s.t :0iii=1min 1mmå ijå i(i )( j )(i )( j )Tbb yyx-bx2b³0i=1, j =1i=1ms.t : åby= 0(i )ii=1備注：值的求解使用SMO算法，后續(xù)課程中介紹。44IT教育品牌線性可分SVMEDUCA

37、TION TO CREATE A BRIGHT FUTURE假設(shè)存在最優(yōu)解*； 根據(jù)w、b和的關(guān)系，可以分別計算出對應(yīng)的w值和b值(一般使用所有支持向量的計算均值來作為實際的b值)；må i*(i )(i )=bw*yxi=1æö =y (w x + b)= ymm- ååb*(i )(i )Tb*(i )(i )Tx +1 Þb = yçb ÷sTsss*ssyxyxxiiè i=1øi=1這里的(xs,ys)即支持向量，根據(jù)KKT條件中的對偶互補(bǔ)條件(松弛條件約束)，支b(y(w x+ b)

38、-1)= 0持向量必須滿足一下公式：(i )T(i )i()(i )(i )b > 0, i = 1,2,., mx, yi45IT教育品牌線性可分SVM算法流程EDUCATION TO CREATE A BRIGHT FUTURE輸入線性可分的m個樣本數(shù)據(jù)(x1,y1),(x2,y2),.,(xm,ym)，其中x為n維的特征向量，y為二元輸出，取值為+1或者-1；SVM模型輸出為參數(shù)w、b以及分類決策函數(shù)。min 1måmå(i )( j ) (i )( j )Tbb yyxx-b構(gòu)造約束優(yōu)化問題；iji2b³0i=1, j =1i=1ms.t : 

39、29;by= 0(i )ii=1使用SMO算法求出上式優(yōu)化中對應(yīng)的最優(yōu)解*；= (x, y)(i )(i )找出所有的支持向量集合S;更新參數(shù)w*、b*的值；mb > 0, i = 1,2,., mSi1æs öSmååå(i )(i )*(i ) (i )Tw =b yx*b =çy -b÷ø*syxxiiSs=1 èi=1i=1構(gòu)建最終的分類器f (x) = sign(w* · x + b* )46IT教育品牌mm1å bb yyxx-å(i )( j )(i )(

40、 j )線性可分SVM案例TbminEDUCATION TO CREATE A BRIGHT FUTUREiji2i =1, j =1i =1ms.t : å b y= 0(i )ii =1bi ³ 0, i = 1,2,., m給定三個數(shù)據(jù)點：正例點x1=(3,3),x2=(4,3), 負(fù)例點x3=(1,1)，構(gòu)造此時的約束優(yōu)化條件。)-12b2+bb -112s.t : b1 +b2-b3 = 0bi ³ 0,i =1,2,.,m47IT教育品牌線性可分SVM總結(jié)EDUCATION TO CREATE A BRIGHT FUTURE1. 要求數(shù)據(jù)必須是線性可分

41、的；2. 純線性可分的SVM模型對于異常數(shù)據(jù)的可能會不太準(zhǔn)；3. 對于線性可分的數(shù)據(jù)，SVM分類器的效果非常不錯。48IT教育品牌SVM的軟間隔模型EDUCATION TO CREATE A BRIGHT FUTURE線性可分SVM中要求數(shù)據(jù)必須是線性可分的，才可以找到分類的超平面，但是有的時候線性數(shù)據(jù)集中存在少量的異常點，由于這些異常點導(dǎo)致了數(shù)據(jù)集不能夠線性劃分；直白來講就是：正常數(shù)據(jù)本身是線性可分的，但是由于存在異常點數(shù)據(jù)，導(dǎo)致數(shù)據(jù)集不能夠線性可分；49IT教育品牌SVM的軟間隔模型EDUCATION TO CREATE A BRIGHT FUTURE如果線性數(shù)據(jù)中存在異常點導(dǎo)致沒法直接使

42、用SVM線性分割模型的時候，我們可以通過引入軟間隔的概念來解決這個問題；硬間隔：可以認(rèn)為線性劃分SVM中的距離度量就是硬間隔，要求函數(shù)距離一定是大于1的，最大化硬間隔條件為：性劃分SVM中，2；s.t : y(i)(wT x(i) +b)³1,i =1,2,.,m12minw,bw2軟間隔：SVM對于訓(xùn)練集中的每個樣本都引入一個松弛因子()，使得函數(shù)距離加上松弛因子后的值是大于等于1；這表示相對于硬間隔，對樣本到超平面距離的要y(w x+ b)³ 1-x求放松了。(i )T(i ), i = 1,2,., m,x ³ 0ii50IT教育品牌xSVM的軟間隔模型y(

43、w x+ b)³ 1-x(i )T(i )EDUCATION TO CREATE A BRIGHT FUTURE, i = 1,2,., m,³0ii松弛因子()越大，表示樣本點離超平面越近，如果松弛因子大于1，那么表示允許該樣本點分錯，所以說加入松弛因子是有成本的，過大的松弛因子可能會導(dǎo)致模型分類錯誤，所以最終的目標(biāo)函數(shù)就轉(zhuǎn)換成為：m1+ C å xi22minw2w ,bi =1+ bs.t : y (i ) (w T x)(i )³ 1 - x , i= 1,2,., mixi³ 0, i = 1,2,., m備注：函數(shù)中的C>0是

44、懲罰參數(shù)，是一個超參數(shù)，類似L1/L2 norm的參數(shù)；C越大表示對誤分類的懲罰越大，C越小表示對誤分類的懲罰越?。籆值的給定需要調(diào)參。51IT教育品牌SVM的軟間隔模型EDUCATION TO CREATE A BRIGHT FUTURE同線性可分SVM，構(gòu)造軟間隔最大化的約束問題對應(yīng)的拉格朗日函數(shù)如下：b -x -b)- åmx b ³my(xb m) = 1måm(å(i )T(i ) +22+ Cx +0,m ³ 0L w, b,w1w xi ,iiiiii2i=1i=1i=1從而將我們的優(yōu)化目標(biāo)函數(shù)轉(zhuǎn)換為：min max L(w, b

45、,x,b,m)w,b,xb,m優(yōu)化目標(biāo)同樣滿足KKT條件，所以使用拉格朗日對偶將優(yōu)化問題轉(zhuǎn)換為等價的對max min L(w, b,x,b,m)偶問題：w,b,xb,m52IT教育品牌SVM的軟間隔模型EDUCATION TO CREATE A BRIGHT FUTURE先求優(yōu)化函數(shù)對于w、b、的極小值，這個可以通過分別對優(yōu)化函數(shù)L求w、b、的偏導(dǎo)數(shù)得，從而可以得到w、b、關(guān)于和之間的關(guān)系。¶L = 0 Þ w - åmmå(i )(i )(i )(i )byx=0 Þw =byxii¶wi=1i=1¶L = 0 Þ

46、; -åmmå(i )(i )by= 0Þby=0ii¶b¶Li=1i=1= 0 Þ C - b - m = 0ii¶xi53IT教育品牌SVM的軟間隔模型EDUCATION TO CREATE A BRIGHT FUTURE將w、b、的值帶入L函數(shù)中，就可以消去優(yōu)化函數(shù)中的w、b、，定義優(yōu)化之后的函數(shù)如下：w x+ b)-mx1-x - y(l(b,m) = 1m+ Cåx +bmmå iå i i(i )T (i )22wii2i=1i=1i=1y(w x+ b)-1+x+(C - m)x=

47、 12= 1mmå iiåi=1(i )T (i )2 -bwm12mÞ l(b) =ååii(i )( j )(i ) x( j )2Tb -bb yyxi=1my(iijw x+ b)-1å i(i )T (i )22-bwi=1i=1, j =12i=1mm= 1 wT w - åmmå(i )åå(i )T (i )(i )s.t :byw x-by b +bb= 0i yiii2i=1i=1i=1m= - 1 wT åmmi=1åå i(i ) (i )(i )byx- bby+bi=1ii2C - b - m = 0i=1i=1T1 æö æöiimmmååå(i ) (i )(i ) (i )= -