數(shù)據(jù)挖掘與處理論(編輯修改稿)
2025-02-02 06:19 本頁面
【文章內(nèi)容簡(jiǎn)介】 的上界由幾何間隔決定?。ó?dāng)然，是樣本已知的時(shí)候） 。 至此我們就明 白為何要選擇幾何間隔來作為評(píng)價(jià)一個(gè)解優(yōu)劣的指標(biāo)了，原來幾何間隔越大的解，它的誤差上界越小。因此 最大化幾何間隔 成了我們訓(xùn)練階段的目標(biāo)，而且，最大化分類間隔并不是 SVM 的專利，而是早在線性分類時(shí)期就已有的思想。 尋優(yōu)問題 上節(jié)說到我們有了一個(gè)線性分類函數(shù)，也有了判斷解優(yōu)劣的標(biāo)準(zhǔn) —— 即有了優(yōu)化的目標(biāo)，這個(gè)目標(biāo)就是最大化幾何間隔，但是看過一些關(guān)于 SVM 的論文的人一定記得什么優(yōu)化的目標(biāo)是要最小化 ||w||這樣的說法，這是怎么回事呢？回頭再看看我們對(duì)間隔和幾何間隔的定義： 間隔：δ =y(wx+b)=|g(x)| 注 意到幾何間隔與 ||w||是成反比的，因此最大化幾何間隔與最小化 ||w||完全是一回事。而我們常用的方法并不是固定 ||w||的大小而尋求最大幾何間隔，而是固定間隔（例如固定為 1），尋找最小的 ||w||。 而凡是求一個(gè)函數(shù)的最小值（或最大值）的問題都可以稱為尋優(yōu)問題（也叫作一個(gè)規(guī)劃問題），又由于找最大值的問題總可以通過加一個(gè)負(fù)號(hào)變?yōu)檎易钚≈档膯栴}，因此我們下面討論的時(shí)候都針對(duì)找最小值的過程來進(jìn)行。一個(gè)尋優(yōu)問題最重要的部分是目標(biāo)函數(shù)，顧名思義，就是指尋優(yōu)的目標(biāo)。不難看出當(dāng) ||w||2達(dá)到最小時(shí)， ||w||也達(dá)到最 小，反之亦然（前提當(dāng)然是 ||w||描述的是向量的長(zhǎng)度，因而是非負(fù)的）。之所以采用這種形式，是因?yàn)楹竺娴那蠼膺^程會(huì)對(duì)目標(biāo)函數(shù)作一系列變換。 接下來我們自然會(huì)問的就是，這個(gè)式子是否就描述了我們的問題呢？（回想一下，我們的問題是有一堆點(diǎn)，可以被分成兩類，我們要找出最好的分類面） 如果直接來解這個(gè)求最小值問題，很容易看出當(dāng) ||w||=0的時(shí)候就得到了目標(biāo)函數(shù)的最小值。但是你也會(huì)發(fā)現(xiàn)，無論你給什么樣的數(shù)據(jù)，都是這個(gè)解！反映在圖中，就是 H1與 H2兩條直線間的距離無限大，這個(gè)時(shí)候，所有的樣本點(diǎn)（無論正樣本還是負(fù)樣本）都跑 到了 H1和 H2中間，而我們?cè)镜囊鈭D是， H1右側(cè)的被分為正類， H2 左側(cè)的被分為負(fù)類，位于兩類中間的樣本則拒絕分類（拒絕分類的另一種理解是分給哪一類都有道理，因而分給哪一類也都沒有道理）。這下可好，所有樣本點(diǎn)都進(jìn)入了無法分類的灰色地帶。 造成這 種結(jié)果的原因是在描述問題的時(shí)候只考慮了目標(biāo)，而沒有加入約束條件，約束條件就是在求解過程中必須滿足的條件，體現(xiàn)在我們的問題中就是樣本點(diǎn)必須在 H1或 H2的某一側(cè)（或者至少在 H1 和 H2上），而不能跑到兩者中間。我們前文提到過把間隔固定為 1，這是指把所有樣本點(diǎn)中間隔最小的那一點(diǎn)的間隔定為 1（這也是集合的間隔的定義，有點(diǎn)繞嘴），也就意味著集合中的其他點(diǎn)間隔都不會(huì)小于 1，按照間隔的定義，滿足這些條件就相當(dāng)于讓下面的式子總是成立： yi[(w xi)+b]≥ 1 (i=1,2,? ,l) （ l是總的樣本數(shù)） 但我們常常習(xí)慣讓 式子的值和 0比較，因而經(jīng)常用變換過的形式： yi[(w xi)+b]1≥ 0 (i=1,2,? ,l) （ l是總的樣本數(shù)） 因此我們的兩類分類問題也被我們轉(zhuǎn)化成了它的數(shù)學(xué)形式，一個(gè)帶約束的最小值的問題 ， 從最一般的定義上說，一個(gè)求最小值的問題就是一個(gè)優(yōu)化問題（也叫尋優(yōu)問題），它同樣由兩部分組成，目標(biāo)函數(shù)和約束條件 。 約束條件用函數(shù) c來表示，你可以看出一共有 p+q個(gè)約束條件，其中 p 個(gè)是不等式約束， q個(gè)等式約束。 關(guān)于這個(gè)式子可以這樣來理解：式中的 x是自變量，但不限定它的維數(shù)必須為 1（視乎你解決的問題空間維數(shù)，對(duì)我 們的文本分類來說，那可是成千上萬?。?。要求 f(x)在哪一點(diǎn)上取得最小值（反倒不太關(guān)心這個(gè)最小值到底是多少，關(guān)鍵是哪一點(diǎn)），但不是在整個(gè)空間里找，而是在約束條件所劃定的一個(gè)有限的空間里找，這個(gè)有限的空間就是優(yōu)化理論里所說的可行域。注意可行域中的每一個(gè)點(diǎn)都要求滿足所有 p+q 個(gè)條件，而不是滿足其中一條或幾條就可以（切記，要滿足每個(gè)約束），同時(shí)可行域邊界上的點(diǎn)有一個(gè)額外好的特性，它們可以使不等式約束取得等號(hào)！而邊界內(nèi)的點(diǎn)不行。 關(guān)于可行域還有個(gè)概念不得不提，那就是凸集，凸集是指有這么一個(gè)點(diǎn)的集合，其中任取兩個(gè)點(diǎn)連一 條直線，這條線上的點(diǎn)仍然在這個(gè)集合內(nèi)部，因此說“凸”是很形象的（一個(gè)反例是，二維平面上，一個(gè)月牙形的區(qū)域就不是凸集，你隨便就可以找到兩個(gè)點(diǎn)違反了剛才的規(guī)定）。 回頭再來看我們線性分類器問題的描述，可以看出更多的東西。 在這個(gè)問題中，自變量就是 w，而目標(biāo)函數(shù)是 w的二次函數(shù)，所有的約束條件都是 w的線性函數(shù)（哎，千萬不要把 xi當(dāng)成變量，它代表樣本，是已知的），這種規(guī)劃問題有個(gè)很有名氣的稱呼 —— 二次規(guī)劃（ Quadratic Programming， QP），而且可以更進(jìn)一步的說，由于它的可行域是一個(gè)凸集，因此它是一個(gè) 凸二次規(guī)劃。 一下子提了這么多術(shù)語，實(shí)在不是為了讓大家以后能向別人炫耀學(xué)識(shí)的淵博，這其實(shí)是我們繼續(xù)下去的一個(gè)重要前提，因?yàn)樵趧?dòng)手求一個(gè)問題的解之前（好吧，我承認(rèn)，是動(dòng)計(jì)算機(jī)求??），我們必須先問自己：這個(gè)問題是不是有解？如果有解，是否能找到？ 對(duì)于一般意義上的規(guī)劃問題，兩個(gè)問題的答案都是不一定，但凸二次規(guī)劃讓人喜歡的地方就在于，它有解（教科書里面為了嚴(yán)謹(jǐn)，常常加限定成分，說它有全局最優(yōu)解，由于我們想找的本來就是全局最優(yōu)的解，所以不加也罷），而且可以找到?。ó?dāng)然，依據(jù)你使用的算法不同，找到這個(gè)解的速度，行話叫 收斂速度，會(huì)有所不同） 還可以發(fā)現(xiàn)，我們的線性分類器問題只有不等式約束，因此形式上看似乎比一般意義上的規(guī)劃問題要簡(jiǎn)單，但解起來卻并非如此。 因?yàn)槲覀儗?shí)際上并不知道該怎么解一個(gè)帶約束的優(yōu)化問題。如果你仔細(xì)回憶
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1