第四章支持向量機(jī)與圖像分類(lèi)(1)

1、支持向量機(jī)與圖像分類(lèi)蔡超授課內(nèi)容1.簡(jiǎn)介簡(jiǎn)介2.logistic回歸回歸3.函數(shù)間隔（函數(shù)間隔（functional margin）和幾何間隔（）和幾何間隔（geometric margin）4.最優(yōu)間隔分類(lèi)器（最優(yōu)間隔分類(lèi)器（optimal margin classifier）5.拉格朗日對(duì)偶拉格朗日對(duì)偶（Lagrange duality）6.最最優(yōu)間隔分類(lèi)器（優(yōu)間隔分類(lèi)器（optimal margin classifier）7.核函數(shù)核函數(shù)（Kernels）1.核函數(shù)核函數(shù)有效性判定有效性判定8.規(guī)則化規(guī)則化和不可分情況處理（和不可分情況處理（Regularization and the

2、non-separable case）9.坐標(biāo)坐標(biāo)上升法（上升法（Coordinate ascent）10. SMO優(yōu)化算法（優(yōu)化算法（Sequential minimal optimization）11. SMO中拉格朗日乘子的啟發(fā)式選擇方法中拉格朗日乘子的啟發(fā)式選擇方法4:57:041 引言引言一一. SVM (Support Vector Machine)的歷的歷史史 神經(jīng)網(wǎng)絡(luò)分類(lèi)器，Bayes分類(lèi)器等是基于大樣本大樣本學(xué)習(xí)的分類(lèi)器。 Vapnik 等從19601960年開(kāi)始關(guān)于統(tǒng)計(jì)學(xué)習(xí)理論統(tǒng)計(jì)學(xué)習(xí)理論的研究。統(tǒng)計(jì)學(xué)習(xí)理論統(tǒng)計(jì)學(xué)習(xí)理論是關(guān)于小樣本小樣本的機(jī)器學(xué)習(xí)理論。 19921992年

3、支持向量機(jī)支持向量機(jī)首次被引入。19951995年Vapnik發(fā)展了支持向量機(jī)支持向量機(jī)理論。支持向量機(jī)支持向量機(jī)是基于統(tǒng)計(jì)學(xué)統(tǒng)計(jì)學(xué)習(xí)理論習(xí)理論的一種實(shí)用的機(jī)器學(xué)習(xí)機(jī)器學(xué)習(xí)方法。4:57:04二二. SVM 的發(fā)展的發(fā)展 SVM理論的發(fā)展理論的發(fā)展: 最小二乘支持向量機(jī)(LS SVM) 多分類(lèi)支持向量機(jī)(M-SVM) 支持向量回歸(SVR) 支持向量聚類(lèi)(SVC) SVM與計(jì)算智能的融合與計(jì)算智能的融合: 神經(jīng)網(wǎng)絡(luò)+支持向量機(jī) 模糊邏輯+支持向量機(jī) 遺傳算法+支持向量機(jī) 小波分析+支持向量機(jī) 主分量分析+支持向量機(jī) 粗糙集理論+支持向量機(jī)4:57:05三三. SVM的應(yīng)用的應(yīng)用 數(shù)據(jù)與文本分類(lèi)

4、 系統(tǒng)建模及預(yù)測(cè) 模式識(shí)別(圖像及語(yǔ)音識(shí)別，生物特征識(shí)別) 異常檢測(cè)(入侵檢測(cè)，故障診斷) 時(shí)間序列預(yù)測(cè)4:57:052 logistic回歸回歸 Logistic回歸目的是從特征學(xué)習(xí)出一個(gè)0/1分類(lèi)模型，而這個(gè)模型是將特性的線性組合作為自變量，由于自變量的取值范圍是負(fù)無(wú)窮到正無(wú)窮。因此，使用logistic函數(shù)（或稱(chēng)作sigmoid函數(shù)）將自變量映射到(0,1)上，映射后的值被認(rèn)為是屬于y=1的概率。假設(shè)函數(shù)其中x是n維特征向量，函數(shù)g就是logistic函數(shù)。Sigmoid 函數(shù)在有個(gè)很漂亮的“S”形,可以看到，將無(wú)窮映射到了(0,1)。 4:57:054:57:054:57:06中間這條

5、線是 logistic回顧強(qiáng)調(diào)所有點(diǎn)盡可能地遠(yuǎn)離中間線。學(xué)習(xí)出的結(jié)果也就中間這條線?？紤]3個(gè)點(diǎn)A、B和C。從圖中我們可以確定A是類(lèi)別的，然而C我們是不太確定的，B還算能夠確定。這樣我們可以得出結(jié)論，我們更應(yīng)該關(guān)心靠近中間分割線的點(diǎn)，讓他們盡可能地遠(yuǎn)離中間線，而不是在所有點(diǎn)上達(dá)到最優(yōu)。因?yàn)槟菢拥脑?，要使得一部分點(diǎn)靠近中間線來(lái)?yè)Q取另外一部分點(diǎn)更加遠(yuǎn)離中間線。這就是支持向量機(jī)的思路和logistic回歸的不同點(diǎn)，一個(gè)考慮局部（不關(guān)心已經(jīng)確定遠(yuǎn)離的點(diǎn)），一個(gè)考慮全局（已經(jīng)遠(yuǎn)離的點(diǎn)可能通過(guò)調(diào)整中間線使其能夠更加遠(yuǎn)離）。4:57:06Notation4:57:064:57:073 函數(shù)函數(shù)間隔（間隔（fu

6、nctional margin） 幾何幾何間隔（間隔（geometric margin）4:57:074:57:07幾何間隔4:57:07進(jìn)一步得到通常,對(duì)于訓(xùn)練集 我們定義幾何間隔（w,b）為：4:57:08 回想前面我們提到我們的目標(biāo)是尋找一個(gè)超平面，使得離超平面比較近的點(diǎn)能有更大的間距。也就是我們不考慮所有的點(diǎn)都必須遠(yuǎn)離超平面，我們關(guān)心求得的超平面能夠讓所有點(diǎn)中離它最近的點(diǎn)具有最大間距。形式化表示為：4最最優(yōu)間隔分類(lèi)器（優(yōu)間隔分類(lèi)器（optimal margin classifier）4:57:084:57:08然而這個(gè)時(shí)候目標(biāo)函數(shù)仍然不是凸函數(shù)，沒(méi)法直接代入優(yōu)化軟件里計(jì)算。4:57:0

7、9這下好了，只有線性約束了，而且是個(gè)典型的二次規(guī)劃問(wèn)題（目標(biāo)函數(shù)是自變量的二次函數(shù)）。代入優(yōu)化軟件可解。4:57:09 先拋開(kāi)上面的二次規(guī)劃問(wèn)題，先來(lái)看看存在等式約束的極值問(wèn)題求法，比如下面的最優(yōu)化問(wèn)題： 引入拉格朗日算子，得到拉格朗日公式 這里的稱(chēng)為拉格朗日乘子。5拉格朗日對(duì)偶（拉格朗日對(duì)偶（Lagrange duality）參考最優(yōu)化與KKT條件4:57:09 然后分別對(duì)w和 求偏導(dǎo)，使得偏導(dǎo)數(shù)等于0，然后解出w和 。 不等式約束的極值問(wèn)題 定義一般化的拉格朗日公式4:57:09 這里的 i和 i都是拉格朗日乘子。如果按這個(gè)公式求解，會(huì)出現(xiàn)問(wèn)題，因?yàn)槲覀兦蠼獾氖亲钚≈担@里的 gi(w)

8、 0或者h(yuǎn)i(w) 0 ，那么我們總是可以調(diào)整 i和 i來(lái)使得 P(w)有最大值為正無(wú)窮。而只有g(shù)和h滿足約束時(shí)。4:57:10 因此我們可以寫(xiě)作這樣我們?cè)瓉?lái)要求的min f(w)可以轉(zhuǎn)換成求如果直接求解，首先面對(duì)的是兩個(gè)參數(shù)和 ，然后再在w上求最小值。這個(gè)過(guò)程不容易做，那么怎么辦呢？我們先考慮另外一個(gè)問(wèn)題D的意思是對(duì)偶（ dual ）。 該式將問(wèn)題轉(zhuǎn)化為先求拉格朗日關(guān)于w的最小值，將 和 看作是固定值。4:57:10于是我們的對(duì)偶優(yōu)化問(wèn)題為：這個(gè)問(wèn)題是原問(wèn)題的對(duì)偶問(wèn)題，相對(duì)于原問(wèn)題只是更換了min和max的順序，而一般更換順序的結(jié)果是Max Min(X) = MinMax(X)。用 d*來(lái)表

9、示對(duì)偶問(wèn)題如下：然而在一些限定條件下兩者相等。4:57:10 成立的條件假設(shè)f和g都是凸函數(shù)，h是仿射的（ affine ）：并且存在w使得gi(w) 0 。在這種假設(shè)下，一定存在 使得 是原問(wèn)題的解， 是對(duì)偶問(wèn)題的解。還有 并且 滿足庫(kù)恩-塔克條件（Karush-Kuhn-Tucker, KKT condition）： （*）4:57:10 所以如果 滿足了庫(kù)恩-塔克條件，那么他們就是原問(wèn)題和對(duì)偶問(wèn)題的解。公式（*）稱(chēng)作是KKT對(duì)偶互補(bǔ)條件（KKT dual complementarity）。這個(gè)條件隱含了如果 ，那么 =0 。也就是說(shuō)， =0 時(shí)，w處于可行域的邊界上，這時(shí)才是起作用的約束

10、。而其他位于可行域內(nèi)部（ 的）點(diǎn)都是不起作用的約束 。 （1）4:57:106最最優(yōu)間隔分類(lèi)器（優(yōu)間隔分類(lèi)器（optimal margin classifier） 重新回到SVM的優(yōu)化問(wèn)題：我們將約束條件改寫(xiě)為：4:57:10從KKT條件得知只有函數(shù)間隔是1（離超平面最近的點(diǎn)）的線性約束式前面的系數(shù) ，也就是說(shuō)這些約束式 =0 ，對(duì)于其他的不在線上的點(diǎn)( 0 )，極值不會(huì)在他們所在的范圍內(nèi)取得，因此前面的系數(shù) =0。注意每一個(gè)約束式實(shí)際就是一個(gè)訓(xùn)練樣本。實(shí)線是最大間隔超平面，假設(shè)號(hào)的是正例，圓圈的是負(fù)例。在虛線上的點(diǎn)就是函數(shù)間隔是1的點(diǎn)，那么他們前面的系數(shù)其他點(diǎn)都是這三個(gè)點(diǎn)稱(chēng)作支持向量。4:5

11、7:11構(gòu)造拉格朗日函數(shù)如下：注意到這里只有 i，沒(méi)有i 是因?yàn)樵瓎?wèn)題中沒(méi)有等式約束，只有不等式約束。下面我們按照對(duì)偶問(wèn)題的求解步驟來(lái)一步步進(jìn)行，4:57:11首先求解 的最小值，對(duì)于固定的i ， 的最小值只與w和b有關(guān)。對(duì)w和b分別求偏導(dǎo)數(shù)。將上式帶回到拉格朗日函數(shù)，此時(shí)得到的是該函數(shù)的最小值（目標(biāo)函數(shù)是凸函數(shù)）代入后，化簡(jiǎn)過(guò)程如下：于是（2）（3）4:57:114:57:11由于公式（3）最后一項(xiàng)是0我們將向量?jī)?nèi)積表示為： 此時(shí)的拉格朗日函數(shù)只包含了變量 。我們求出了i 才能得到w和b。接著是極大化的過(guò)程4:57:11前面提到過(guò)對(duì)偶問(wèn)題和原問(wèn)題滿足的幾個(gè)條件，首先由于目標(biāo)函數(shù)和線性約束都是凸函數(shù)，而且這里不存在等式約束h。存在w使得對(duì)于所有的i， 。因此，一定存在 使得 是原問(wèn)題的解， 是對(duì)偶問(wèn)題的解。在這里，求 就是求 了。即可求出b。即離超平面最近的正的函數(shù)間隔要等于離超平面最近的負(fù)的函數(shù)間隔。關(guān)于上面的對(duì)偶問(wèn)題如何求解，將留給下一篇中的SMO算法來(lái)闡明4:57:11如果求出了 ，根據(jù) 即可求出w（也是 ，原問(wèn)題的解）。然后考慮另外一個(gè)問(wèn)題，由于前面求解中得到我們通篇考慮問(wèn)題的出發(fā)點(diǎn)是 ，根據(jù)求解得到的 ，代入前式得到也就是說(shuō)，以前新