十五恋脚、初始β變量的選擇
回顧: 可以發(fā)現(xiàn)SMO算法中，是選擇兩個(gè)合適的β變量做迭代焰手，其它變量作為常量來(lái)進(jìn)行優(yōu)化的一個(gè)過(guò)程糟描，那么這兩個(gè)變量到底怎么選擇呢???
1、每次優(yōu)化的時(shí)候册倒，必須同時(shí)優(yōu)化β的兩個(gè)分量蚓挤；因?yàn)槿绻粌?yōu)化一個(gè)分量的話(huà)，新的β值就沒(méi)法滿(mǎn)足初始限制條件中的等式約束條件了驻子。
2灿意、每次優(yōu)化的兩個(gè)分量應(yīng)該是違反g(x)目標(biāo)條件比較多的。也就是說(shuō)崇呵，本來(lái)應(yīng)當(dāng)是大于等于1的缤剧，越是小于1違反g(x)目標(biāo)條件就越多；
1域慷、第一個(gè)β變量的選擇
SMO算法在選擇第一個(gè)β變量的時(shí)候荒辕，需要選擇在訓(xùn)練集上違反KKT條件最嚴(yán)重的樣本點(diǎn)。一般情況下犹褒，先選擇0<β<C的樣本點(diǎn)(即支持向量)抵窒，只有當(dāng)所有的支持向量都滿(mǎn)足KKT條件的時(shí)候，才會(huì)選擇其它樣本點(diǎn)叠骑。因?yàn)榇藭r(shí)違反KKT條件越嚴(yán)重李皇，在經(jīng)過(guò)一次優(yōu)化后，會(huì)讓變量β盡可能的發(fā)生變化宙枷，從而可以以更少的迭代次數(shù)讓模型達(dá)到g(x)目標(biāo)條件掉房。
2、第二個(gè)β變量的選擇
在選擇第一個(gè)變量β1后卓囚，在選擇第二個(gè)變量β2的時(shí)候瘾杭，希望能夠按照優(yōu)化后的β1和β2有盡可能多的改變來(lái)選擇，也就是說(shuō)讓|E1-E2|足夠的大哪亿，當(dāng)E1為正的時(shí)候粥烁，選擇最小的Ei作為E2；當(dāng)E1為負(fù)的時(shí)候锣夹，選擇最大的Ei作為E2擦剑。
PS：如果選擇的第二個(gè)變量不能夠讓目標(biāo)函數(shù)有足夠的下降浅役，那么可以通過(guò)遍歷所有樣本點(diǎn)來(lái)作為β2，直到目標(biāo)函數(shù)有足夠的下降肥隆，如果都沒(méi)有足夠的下降的話(huà)恤左，那么直接跳出循環(huán)贴唇，重新選擇β1；
3飞袋、計(jì)算閾值b和差Ei
在每次完成兩個(gè)β變量的優(yōu)化更新之后戳气，需要重新計(jì)算閾值b和差值Ei。當(dāng)0<βnew<C時(shí)巧鸭，有：
同樣的當(dāng)β2的取值為: 0<β2<C的時(shí)候瓶您，我們也可以得到：
最終計(jì)算出來(lái)的b為：
當(dāng)更新計(jì)算閾值b后，就可以得到差值Ei為：
十六纲仍、SMO算法流程總結(jié)
輸入線(xiàn)性可分的m個(gè)樣本數(shù)據(jù){(x1,y1),(x2,y2),...,(xm,ym)}呀袱，其中x為n維的特征向量，y為二元輸出郑叠，取值為+1或者-1夜赵；精度為e；
取初值β0=0乡革，k=0寇僧；
選擇需要進(jìn)行更新的兩個(gè)變量: β1k和β2k，計(jì)算出來(lái)新的β2new,unt沸版；
按照下列式子求出具體的β2k+1;
按照β1k和β2k的關(guān)系嘁傀，求出β1k+1的值：
按照公式計(jì)算bk+1和Ei的值；
檢查函數(shù)y(i)*Ei的絕對(duì)值是否在精度范圍內(nèi)视粮，并且求解出來(lái)的β解滿(mǎn)足KKT相關(guān)約束條件细办，那么此時(shí)結(jié)束循環(huán)，返回此時(shí)的β解即可馒铃，否則繼續(xù)迭代計(jì)算β2new,unt的值蟹腾。
