統(tǒng)計(jì)機(jī)器學(xué)習(xí)-序列最小最優(yōu)化算法（SMO）

SMO算法要解如下凸二次規(guī)劃的對(duì)偶問(wèn)題：
$\min_\alpha\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^N\alpha_i\tag1$

$\mathrm{s.t.}\ \ \sum_{i=1}^N\alpha_iy_i=0\tag2$

$0\leq\alpha_i\leq C,\ \ i=1,2,\cdots,N\tag3$

在這個(gè)問(wèn)題中尔艇，變量是拉格朗日乘子羡忘，一個(gè)變量 $\alpha_i$ 對(duì)應(yīng)于一個(gè)樣本點(diǎn) $(x_i,y_i)$ 。變量的總數(shù)等于訓(xùn)練樣本的容量 $N$ 案狠。

SMO算法是一種啟發(fā)式算法服傍，其基本思路是：如果所有變量的解都滿(mǎn)足此最優(yōu)化問(wèn)題的 $KKT$ 條件，那么這個(gè)最優(yōu)化問(wèn)題的解就得到了骂铁，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=KKT" alt="KKT" mathimg="1">條件是該最優(yōu)化問(wèn)題的充分必要條件吹零。于是，每次只選擇兩個(gè)變量進(jìn)行優(yōu)化拉庵，使其滿(mǎn)足 $KKT$ 條件灿椅，然后不斷迭代，直至所有變量滿(mǎn)足 $KKT$ 條件，得到最優(yōu)解茫蛹。在優(yōu)化變量的選取上操刀，一般一個(gè)是違反 $KKT$ 條件最嚴(yán)重的一個(gè)，另一個(gè)由約束條件自動(dòng)決定婴洼。

兩個(gè)變量二次規(guī)劃的求解方法

根據(jù)SMO算法骨坑，公式(1)-(3)的問(wèn)題可以通過(guò)多次選擇變量 $\alpha_1$ ， $\alpha_2$ 柬采，求解下列子問(wèn)題得到：
$\min_{\alpha_1,\alpha_2}W(\alpha_1,\alpha_2)=\frac12K_{11}\alpha_1^2+\frac12K_{22}\alpha_2^2+y_1y_2K_{12}\alpha_1\alpha_2-(\alpha_1+\alpha_2)+y_1\alpha_1\sum_{i=3}^Ny_i\alpha_iK_{i1}+y_2\alpha_2\sum_{i=3}^Ny_i\alpha_iK_{i2}\tag4$

$\mathrm{s.t.}\ \ \alpha_1y_1+\alpha_2y_2=-\sum_{i=3}^Ny_i\alpha_i=\varsigma\tag5$

$0\leq\alpha_i\leq C,\ \ i=1,2\tag6$

上述優(yōu)化問(wèn)題欢唾，因?yàn)榭梢酝ㄟ^(guò)公式(5)可以用 $\alpha_2$ 來(lái)表示 $\alpha_1$ ，所以可以考慮為對(duì) $\alpha_2$ 的最優(yōu)化問(wèn)題粉捻。如果 $y_1\neq y_2$ 礁遣，則 $\alpha_1-\alpha_2=k$ ， $k$ 為常數(shù)：

y1!=y2

根據(jù)公式(6)杀迹， $\alpha_1$ 亡脸， $\alpha_2$ 在正方形內(nèi)部，加上公式(5)树酪，所以 $\alpha_1$ 浅碾， $\alpha_2$ 為直線(xiàn)和正方形交線(xiàn)上的點(diǎn)。同理续语，如果 $y_1=y_2$ 垂谢，則 $\alpha_1+\alpha_2=k$ ，如下圖：

y1=y2

假設(shè)問(wèn)題(4)-(6)優(yōu)化前 $\alpha_1$ 疮茄， $\alpha_2$ 的值為 $\alpha_1^{old}$ 滥朱， $\alpha_2^{old}$ ，優(yōu)化后的最優(yōu)解為 $\alpha_1^{new}$ 力试， $\alpha_2^{new}$ 徙邻，并且假設(shè)在沿著約束方向未經(jīng)剪輯時(shí) $\alpha_2$ 的最優(yōu)解為 $\alpha_2^{new,unc}$ 。

$\alpha_2^{new}$ 需要滿(mǎn)足不等式
$L\leq\alpha_2^{new}\leq H$
其中畸裳， $L$ 和 $H$ 是 $\alpha_2^{new}$ 所在對(duì)角線(xiàn)段的界缰犁，如果 $y_1\neq y_2$ ，則
$L=\max(0,\alpha_2^{old}-\alpha_1^{old}),\ \ H=\min(C,C+\alpha_2^{old}-\alpha_1^{old})$
因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Calpha_1%5E%7Bnew%7D-%5Calpha_2%5E%7Bnew%7D%3Dk%3D%5Calpha_1%5E%7Bold%7D-%5Calpha_2%5E%7Bold%7D" alt="\alpha_1^{new}-\alpha_2^{new}=k=\alpha_1^{old}-\alpha_2^{old}" mathimg="1">怖糊，所以 $\alpha_2^{new}$ 在直線(xiàn) $\alpha_1^{new}-\alpha_2^{new}=\alpha_1^{old}-\alpha_2^{old}$ 和正方形的交線(xiàn)段上帅容，通過(guò)上下平移就能夠得到上面 $\alpha_2^{new}$ 的界。同理伍伤，如果 $y_1=y_2$ ，則
$L=\max(0,\alpha_2^{old}+\alpha_1^{old}-C),\ \ H=\min(C,\alpha_2^{old}+\alpha_1^{old})$
于是通過(guò)公式(5)得到 $\alpha_1$ 用 $\alpha_2$ 的表示：
$\alpha_1=(\varsigma-y_2\alpha_2)y_1$
代入公式
$W(\alpha_1,\alpha_2)=\frac12K_{11}\alpha_1^2+\frac12K_{22}\alpha_2^2+y_1y_2K_{12}\alpha_1\alpha_2-(\alpha_1+\alpha_2)+y_1\alpha_1\sum_{i=3}^Ny_i\alpha_iK_{i1}+y_2\alpha_2\sum_{i=3}^Ny_i\alpha_iK_{i2}$
并求導(dǎo)等于0便可以得到未經(jīng)剪輯時(shí) $\alpha_2$ 的最優(yōu)解 $\alpha_2^{new,unc}$ ，最后根據(jù)上述 $L$ 和 $H$ 裁剪得到 $\alpha_2^{new}$ 荐开。

最優(yōu)化問(wèn)題(4)-(6)沿著約束方向未經(jīng)剪輯時(shí)的解是
$\alpha_2^{new,unc}=\alpha_2^{old}+\frac{y_2(E_1-E_2)}{\eta}\tag7$
其中，
$\eta=K_{11}+K_{22}-2K_{12}=||\Phi(x_1)-\Phi(x_2)||^2\tag8$
$\Phi(x)$ 是輸入空間到特征空間的映射， $E_i$ 初斑， $i=1,2$ 為
$E_i=g(x_i)-y_i=\bigg(\sum_{j=1}^N\alpha_jy_jK(x_j,x_i)+b\bigg)-y_i,\ \ i=1,2\tag9$
表示對(duì)輸入 $x_i$ 的預(yù)測(cè)值與真實(shí)輸出 $y_i$ 之差，其中
$g(x)=\sum_{i=1}^N\alpha_iy_iK(x_i,x)+b\tag{10}$
經(jīng)剪輯后 $\alpha_2$ 的解是
$\alpha_2^{new}= \begin{cases} H,&\alpha_2^{new,unc}\gt H\\ \alpha_2^{new,unc},&L\leq\alpha_2^{new,unc}\leq H\\ L,&\alpha_2^{new,unc}\lt L \end{cases}$
然后根據(jù)公式
$\alpha_1^{new}=(\varsigma-y_2\alpha_2^{new})y_1\tag{11}$
計(jì)算 $\alpha_1^{new}$ 鹃答。

變量的選擇方法

SMO算法每次都要選擇兩個(gè)變量進(jìn)行優(yōu)化，其中至少一個(gè)變量是違反 $KKT$ 條件的锋八。

第一個(gè)變量的選擇

SMO稱(chēng)選擇第1個(gè)變量的過(guò)程為外層循環(huán)。外層循環(huán)在訓(xùn)練樣本中選取違反 $KKT$ 條件最嚴(yán)重的樣本點(diǎn)樊销，并將其對(duì)應(yīng)的變量作為第1個(gè)變量裤园，具體的拧揽，檢驗(yàn)訓(xùn)練樣本點(diǎn) $(x_i,y_i)$ 是否滿(mǎn)足 $KKT$ 條件痒谴，即
$\alpha_i=0\Leftrightarrow y_ig(x_i)\geq1\tag{12}$

$0\lt\alpha_i\lt C\Leftrightarrow y_ig(x_i)=1\tag{13}$

$\alpha_i=C\Leftrightarrow y_ig(x_i)\leq1\tag{14}$

其中意鲸， $g(x_i)=\sum_{j=1}^N\alpha_jy_jK(x_i,x_j)+b$ 。

該檢驗(yàn)是在 $\varepsilon$ 范圍內(nèi)進(jìn)行的槐雾。在檢驗(yàn)過(guò)程中，外層循環(huán)首先遍歷所有滿(mǎn)足條件 $0\lt\alpha_i\lt C$ 的樣本點(diǎn)擎值，即間隔邊界上的支持向量點(diǎn)，檢驗(yàn)它們是否滿(mǎn)足 $KKT$ 條件捆交，如果這些樣本點(diǎn)都滿(mǎn)足 $KKT$ 條件品追，那么遍歷整個(gè)訓(xùn)練集肉瓦，檢驗(yàn)它們是否滿(mǎn)足 $KKT$ 條件。

第二個(gè)變量的選擇

SMO稱(chēng)選擇第2個(gè)變量的過(guò)程為內(nèi)層循環(huán)鲫趁。第2個(gè)變量的選擇標(biāo)準(zhǔn)是希望能使 $\alpha_2$ 有足夠大的變化堡僻。由于
$\alpha_2^{new,unc}=\alpha_2^{old}+\frac{y_2(E_1-E_2)}{\eta}$
所以 $\alpha_2$ 的變化依賴(lài)于 $|E_1-E_2|$ 。于是選擇使 $|E_1-E_2|$ 最大的 $\alpha_2$ 牲阁，當(dāng) $E_1$ 是正的，選擇最小的 $E_i$ 作為 $E_2$ ，如果 $E_1$ 是負(fù)的法瑟，選擇最大的 $E_i$ 作為 $E_2$ ，為了節(jié)省計(jì)算時(shí)間酥夭，將所有的 $E_i$ 值保存在一個(gè)列表中。

如果這種內(nèi)層循環(huán)找不到一個(gè)有足夠下降的 $\alpha_2$ 讶隐，則遍歷在間隔邊界上的支持向量點(diǎn)地消，依次將其對(duì)應(yīng)的變量作為 $\alpha_2$ 試用疼阔，直到有足夠的下降竿开，如果還不可以，則遍歷訓(xùn)練集列荔。再不可以，換一個(gè) $\alpha_1$ 。

計(jì)算閾值 $b$ 和差值 $E_i$

更新完 $\alpha_1^{new}$ ， $\alpha_2^{new}$ 的值，都需要重新計(jì)算閾值 $b$ ，當(dāng) $0\lt\alpha_1^{new}\lt C$ 時(shí)，由 $KKT$ 條件可知
$\sum_{i=1}^N\alpha_iy_iK_{i1}+b=y_1$
所以
$b_1^{new}=y_1-\sum_{i=1}^N\alpha_iy_iK_{i1}=y_1-\sum_{i=3}^N\alpha_iy_iK_{i1}-\alpha_1^{new}y_1K_{11}-\alpha_2^{new}y_2K_{2,1}\tag{15}$
由于未更新的 $E_1$ 為
$E_1=\sum_{i=3}^N\alpha_iy_iK_{i1}-y_1+\alpha_1^{old}y_1K_{11}+\alpha_2^{old}y_2K_{21}+b^{old}$
移項(xiàng)得到
$y_1-\sum_{i=3}^N\alpha_iy_iK_{i1}=-E_1+\alpha_1^{old}y_1K_{11}+\alpha_2^{old}y_2K_{21}+b^{old}$
代入公式(15)得到 $b_1^{new}$ 的更新公式
$b_1^{new}=-E_1-y_1K_{11}(\alpha_1^{new}-\alpha_1^{old})-y_2K_{21}(\alpha_2^{new}-\alpha_2^{old})+b^{old}\tag{16}$
同理鳞青，當(dāng) $0\lt\alpha_2^{new}\lt C$ 時(shí)，可以推出 $b_2^{new}$ 的更新公式
$b_2^{new}=-E_2-y_1K_{12}(\alpha_1^{new}-\alpha_1^{old})-y_2K_{22}(\alpha_2^{new}-\alpha_2^{old})+b^{old}\tag{17}$
如果 $\alpha_1^{new}$ ， $\alpha_2^{new}$ 同時(shí)滿(mǎn)足條件 $0\lt\alpha_i^{new}\lt C$ ， $i=1,2$ ，那么 $b_1^{new}=b_2^{new}$ ，如果 $\alpha_1^{new}$ ， $\alpha_2^{new}$ 是0或者 $C$ ，那么 $b_1^{new}$ 和 $b_2^{new}$ 以及它們之間的數(shù)都是符合 $KKT$ 條件的閾值，這時(shí)選擇它們的中點(diǎn)作為 $b^{new}$ 须教。

更新完 $\alpha_1^{new}$ ， $\alpha_2^{new}$ 后還需要更新對(duì)應(yīng)的 $E_i$ 值挤土，并保存在列表中咖杂， $E_i$ 的更新需要用到 $b^{new}$ 的值，以及所有支持向量對(duì)應(yīng)的 $\alpha_j$ ：
$E_i^{new}=\sum_Sy_j\alpha_jK(x_i,x_j)+b^{new}-y_i\tag{18}$
其中 $S$ 是所有支持向量 $x_j$ 的集合伍绳。

SMO算法

輸入：訓(xùn)練數(shù)據(jù)集 $T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$ 模蜡，其中 $x_i\in\mathcal X=\textbf R^n$ 甥绿， $y_i\in\mathcal Y= \{-1,+1\}$ 共缕， $i=1,2,\cdots,N$ ，精度 $\varepsilon$ 士复；

輸出：近似解 $\hat{\alpha}$ 图谷。

（1）選取初值 $\alpha^{(0)}=0$ ，令 $k=0$ 阱洪；

（2）選取優(yōu)化變量 $\alpha_1^{(k)}$ 便贵， $\alpha_2^{(k)}$ ，解析求解兩個(gè)變量的最優(yōu)化問(wèn)題(4)-(6)冗荸，求得最優(yōu)解 $\alpha_1^{(k+1)}$ 承璃， $\alpha_2^{(k+1)}$
$\alpha_2^{new,unc}=\alpha_2^{old}+\frac{y_2(E_1-E_2)}{\eta}$

$\alpha_2^{new}= \begin{cases} H,&\alpha_2^{new,unc}\gt H\\ \alpha_2^{new,unc},&L\leq\alpha_2^{new,unc}\leq H\\ L,&\alpha_2^{new,unc}\lt L \end{cases}$

$\alpha_1^{new}=(\varsigma-y_2\alpha_2^{new})y_1=(-\sum_{i=3}^Ny_i\alpha_i-y_2\alpha_2^{new})y_1$

其中
$\eta=K_{11}+K_{22}-2K_{12}=||\Phi(x_1)-\Phi(x_2)||^2$

$E_i=g(x_i)-y_i=\bigg(\sum_{j=1}^N\alpha_jy_jK(x_j,x_i)+b\bigg)-y_i,\ \ i=1,2$

如果 $y_1\neq y_2$
$L=\max(0,\alpha_2^{old}-\alpha_1^{old}),\ \ H=\min(C,C+\alpha_2^{old}-\alpha_2^{old})$
如果 $y_1=y_2$
$L=\max(0,\alpha_2^{old}+\alpha_1^{old}-C),\ \ H=\min(C,\alpha_2^{old}+\alpha_2^{old})$
更新 $\alpha$ 為 $\alpha^{(k+1)}$ ；

（3）若在精度 $\varepsilon$ 范圍內(nèi)滿(mǎn)足停機(jī)條件
$\sum_{i=1}^N\alpha_iy_i=0$

$0\leq\alpha_i\leq C,\ \ i=1,2,\cdots,N$

$y_ig(x_i)= \begin{cases} \geq1,& \{x_i|\alpha_i=0\}\\ =1,& \{x_i|0\lt\alpha_i\lt C\}\\ \leq1,& \{x_i|\alpha_i=C\} \end{cases}$
其中
$g(x_i)=\sum_{j=1}^N\alpha_jy_jK(x_j,x_i)+b$
則轉(zhuǎn)(4)蚌本；否則令 $k=k+1$ 盔粹，轉(zhuǎn)(2)；

（4）取 $\hat \alpha=\alpha^{(k+1)}$ 魂毁。

最后編輯于：2020.07.02 22:39:50

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末玻佩，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子席楚，更是在濱河造成了極大的恐慌咬崔，老刑警劉巖，帶你破解...
沈念sama閱讀 212,599評(píng)論 6贊 492
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異垮斯，居然都是意外死亡郎仆，警方通過(guò)查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,629評(píng)論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)兜蠕，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)扰肌，“玉大人，你說(shuō)我怎么就攤上這事熊杨∈镄瘢” “怎么了？”我有些...
開(kāi)封第一講書(shū)人閱讀 158,084評(píng)論 0贊 348
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵晶府，是天一觀的道長(zhǎng)桂躏。經(jīng)常有香客問(wèn)我，道長(zhǎng)川陆，這世上最難降的妖魔是什么剂习？我笑而不...
開(kāi)封第一講書(shū)人閱讀 56,708評(píng)論 1贊 284
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮较沪，結(jié)果婚禮上鳞绕，老公的妹妹穿的比我還像新娘。我一直安慰自己尸曼，他們只是感情好们何，可當(dāng)我...
茶點(diǎn)故事閱讀 65,813評(píng)論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布。她就那樣靜靜地躺著控轿，像睡著了一般垂蜗。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上解幽，一...
開(kāi)封第一講書(shū)人閱讀 50,021評(píng)論 1贊 291
城市分裂傳說(shuō)
那天贴见，我揣著相機(jī)與錄音，去河邊找鬼躲株。笑死片部，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的霜定。我是一名探鬼主播档悠，決...
沈念sama閱讀 39,120評(píng)論 3贊 410
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼望浩！你這毒婦竟也來(lái)了辖所？” 一聲冷哼從身側(cè)響起，我...
開(kāi)封第一講書(shū)人閱讀 37,866評(píng)論 0贊 268
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤磨德，失蹤者是張志新（化名）和其女友劉穎缘回，沒(méi)想到半個(gè)月后吆视，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體蚤告，經(jīng)...
沈念sama閱讀 44,308評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡逞力，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,633評(píng)論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了璃搜。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片拙寡。...
茶點(diǎn)故事閱讀 38,768評(píng)論 1贊 341
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡授滓，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出肆糕，到底是詐尸還是另有隱情般堆，我是刑警寧澤，帶...
沈念sama閱讀 34,461評(píng)論 4贊 333
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布诚啃，位于F島的核電站郁妈，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏绍申。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 40,094評(píng)論 3贊 317
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一顾彰、第九天我趴在偏房一處隱蔽的房頂上張望极阅。院中可真熱鬧，春花似錦涨享、人聲如沸筋搏。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 30,850評(píng)論 0贊 21
一樁弒父案厕隧，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)奔脐。三九已至，卻和暖如春吁讨，著一層夾襖步出監(jiān)牢的瞬間髓迎，已是汗流浹背。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 32,082評(píng)論 1贊 267
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工建丧，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留排龄，地道東北人。一個(gè)月前我還...
沈念sama閱讀 46,571評(píng)論 2贊 362
代替公主和親
正文我出身青樓翎朱，卻偏偏與公主長(zhǎng)得像橄维，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子拴曲，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,666評(píng)論 2贊 350