SVM拉格朗日對(duì)偶問(wèn)題最優(yōu)間隔分類(lèi)器.doc

《SVM拉格朗日對(duì)偶問(wèn)題最優(yōu)間隔分類(lèi)器.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

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

2、朗日函數(shù)如下：??????????注意到這里只有沒(méi)有是因?yàn)樵瓎?wèn)題中沒(méi)有等式約束，只有不等式約束。???下面我們按照對(duì)偶問(wèn)題的求解步驟來(lái)一步步進(jìn)行，???????首先求解的最小值，對(duì)于固定的，的最小值只與w和b有關(guān)。對(duì)w和b分別求偏導(dǎo)數(shù)。???????????并得到???????將上式帶回到拉格朗日函數(shù)中得到，此時(shí)得到的是該函數(shù)的最小值（目標(biāo)函數(shù)是凸函數(shù)）???代入后，化簡(jiǎn)過(guò)程如下：?????　　最后得到????由于最后一項(xiàng)是0，因此簡(jiǎn)化為???????這里我們將向量?jī)?nèi)積表示為???此時(shí)的拉格朗日函數(shù)只包含了變量。然而我們求出

3、了才能得到w和b。???接著是極大化的過(guò)程，???前面提到過(guò)對(duì)偶問(wèn)題和原問(wèn)題滿足的幾個(gè)條件，首先由于目標(biāo)函數(shù)和線性約束都是凸函數(shù)，而且這里不存在等式約束h。存在w使得對(duì)于所有的i，。因此，一定存在使得是原問(wèn)題的解，是對(duì)偶問(wèn)題的解。在這里，求就是求了。???如果求出了，根據(jù)即可求出w（也是，原問(wèn)題的解）。然后???????即可求出b。即離超平面最近的正的函數(shù)間隔要等于離超平面最近的負(fù)的函數(shù)間隔。???關(guān)于上面的對(duì)偶問(wèn)題如何求解，將留給下一篇中的SMO算法來(lái)闡明。???這里考慮另外一個(gè)問(wèn)題，由于前面求解中得到???????我們通

4、篇考慮問(wèn)題的出發(fā)點(diǎn)是，根據(jù)求解得到的，我們代入前式得到???????也就是說(shuō)，以前新來(lái)的要分類(lèi)的樣本首先根據(jù)w和b做一次線性運(yùn)算，然后看求的結(jié)果是大于0還是小于0,來(lái)判斷正例還是負(fù)例?，F(xiàn)在有了，我們不需要求出w，只需將新來(lái)的樣本和訓(xùn)練數(shù)據(jù)中的所有樣本做內(nèi)積和即可。那有人會(huì)說(shuō)，與前面所有的樣本都做運(yùn)算是不是太耗時(shí)了？其實(shí)不然，我們從KKT條件中得到，只有支持向量的，其他情況。因此，我們只需求新來(lái)的樣本和支持向量的內(nèi)積，然后運(yùn)算即可。這種寫(xiě)法為下面要提到的核函數(shù)（kernel）做了很好的鋪墊。這是上篇，先寫(xiě)這么多了。