smo演算法

❶ SMO演算法為什麼要選兩個變數

SMO演算法由Microsoft Research的John C. Platt在1998年提出，並成為最快的二次規劃優化演算法，特別針對線性SVM和數據稀疏時性能更優。關於SMO最好的資料就是他本人寫的《Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines》了。
我拜讀了一下，下面先說講義上對此方法的總結。
首先回到我們前面一直懸而未解的問題，對偶函數最後的優化問題：

要解決的是在參數上求最大值W的問題，至於和都是已知數。C由我們預先設定，也是已知數。
按照坐標上升的思路，我們首先固定除以外的所有參數，然後在上求極值。等一下，這個思路有問題，因為如果固定以外的所有參數，那麼將不再是變數（可以由其他值推出），因為問題中規定了

因此，我們需要一次選取兩個參數做優化，比如和，此時可以由和其他參數表示出來。這樣回帶到W中，W就只是關於的函數了，可解。
這樣，SMO的主要步驟如下：

意思是，第一步選取一對和，選取方法使用啟發式方法（後面講）。第二步，固定除和之外的其他參數，確定W極值條件下的，由表示。
SMO之所以高效就是因為在固定其他參數後，對一個參數優化過程很高效。
下面討論具體方法：
假設我們選取了初始值滿足了問題中的約束條件。接下來，我們固定，這樣W就是和的函數。並且和滿足條件：

由於都是已知固定值，因此為了方面，可將等式右邊標記成實數值。

當和異號時，也就是一個為1，一個為-1時，他們可以表示成一條直線，斜率為1。如下圖：

橫軸是，縱軸是，和既要在矩形方框內，也要在直線上，因此
，
同理，當和同號時，
，
然後我們打算將用表示：

然後反代入W中，得

展開後W可以表示成。其中a,b,c是固定值。這樣，通過對W進行求導可以得到，然而要保證滿足，我們使用表示求導求出來的，然而最後的，要根據下面情況得到：

這樣得到後，我們可以得到的新值。
下面進入Platt的文章，來找到啟發式搜索的方法和求b值的公式。
這邊文章使用的符號表示有點不太一樣，不過實質是一樣的，先來熟悉一下文章中符號的表示。
文章中定義特徵到結果的輸出函數為

與我們之前的實質是一致的。
原始的優化問題為：

求導得到：

經過對偶後為：

s.t.

這里與W函數是一樣的，只是符號求反後，變成求最小值了。和是一樣的，都表示第i個樣本的輸出結果（1或-1）。
經過加入鬆弛變數後，模型修改為：

由公式（7）代入（1）中可知，

這個過程和之前對偶過程一樣。
重新整理我們要求的問題為：

與之對應的KKT條件為：

這個KKT條件說明，在兩條間隔線外面的點，對應前面的系數為0，在兩條間隔線裡面的對應為C，在兩條間隔線上的對應的系數在0和C之間。
將我們之前得到L和H重新拿過來：

之前我們將問題進行到這里，然後說將用表示後代入W中，這里將代入中，得

其中

這里的和代表某次迭代前的原始值，因此是常數，而和是變數，待求。公式（24）中的最後一項是常數。
由於和滿足以下公式

因為的值是固定值，在迭代前後不會變。
那麼用s表示，上式兩邊乘以時，變為：

其中

代入（24）中，得

這時候只有是變數了，求導

如果的二階導數大於0（凹函數），那麼一階導數為0時，就是極小值了。
假設其二階導數為0（一般成立），那麼上式化簡為：

將w和v代入後，繼續化簡推導，得（推導了六七行推出來了）

我們使用來表示：

通常情況下目標函數是正定的，也就是說，能夠在直線約束方向上求得最小值，並且。
那麼我們在（30）兩邊都除以可以得到

這里我們使用表示優化後的值，是迭代前的值，。
與之前提到的一樣不是最終迭代後的值，需要進行約束：

那麼

在特殊情況下，可能不為正，如果核函數K不滿足Mercer定理，那麼目標函數可能變得非正定，可能出現負值。即使K是有效的核函數，如果訓練樣本中出現相同的特徵x，那麼仍有可能為0。SMO演算法在不為正值的情況下仍有效。為保證有效性，我們可以推導出就是的二階導數，，沒有極小值，最小值在邊緣處取到（類比），時更是單調函數了，最小值也在邊緣處取得，而的邊緣就是L和H。這樣將和分別代入中即可求得的最小值，相應的還是也可以知道了。具體計算公式如下：

至此，迭代關系式出了b的推導式以外，都已經推出。
b每一步都要更新，因為前面的KKT條件指出了和的關系，而和b有關，在每一步計算出後，根據KKT條件來調整b。
b的更新有幾種情況：

來自羅林開的ppt
這里的界內指，界上就是等於0或者C了。
前面兩個的公式推導可以根據
和對於有的KKT條件推出。
這樣全部參數的更新公式都已經介紹完畢，附加一點，如果使用的是線性核函數，我們就可以繼續使用w了，這樣不用掃描整個樣本庫來作內積了。
w值的更新方法為：

根據前面的

公式推導出。
12 SMO中拉格朗日乘子的啟發式選擇方法
終於到了最後一個問題了，所謂的啟發式選擇方法主要思想是每次選擇拉格朗日乘子的時候，優先選擇樣本前面系數的作優化（論文中稱為無界樣例），因為在界上（為0或C）的樣例對應的系數一般不會更改。
這條啟發式搜索方法是選擇第一個拉格朗日乘子用的，比如前面的。那麼這樣選擇的話，是否最後會收斂。可幸的是Osuna定理告訴我們只要選擇出來的兩個中有一個違背了KKT條件，那麼目標函數在一步迭代後值會減小。違背KKT條件不代表，在界上也有可能會違背。是的，因此在給定初始值=0後，先對所有樣例進行循環，循環中碰到違背KKT條件的（不管界上還是界內）都進行迭代更新。等這輪過後，如果沒有收斂，第二輪就只針對的樣例進行迭代更新。
在第一個乘子選擇後，第二個乘子也使用啟發式方法選擇，第二個乘子的迭代步長大致正比於，選擇第二個乘子能夠最大化。即當為正時選擇負的絕對值最大的，反之，選擇正值最大的。
最後的收斂條件是在界內（）的樣例都能夠遵循KKT條件，且其對應的只在極小的范圍內變動。
至於如何寫具體的程序，請參考John C. Platt在論文中給出的偽代碼。
13 總結
這份SVM的講義重點概括了SVM的基本概念和基本推導，中規中矩卻又讓人醍醐灌頂。起初讓我最頭疼的是拉格朗日對偶和SMO，後來逐漸明白拉格朗日對偶的重要作用是將w的計算提前並消除w，使得優化函數變為拉格朗日乘子的單一參數優化問題。而SMO裡面迭代公式的推導也著實讓我花費了不少時間。
對比這么復雜的推導過程，SVM的思想確實那麼簡單。它不再像logistic回歸一樣企圖去擬合樣本點（中間加了一層sigmoid函數變換），而是就在樣本中去找分隔線，為了評判哪條分界線更好，引入了幾何間隔最大化的目標。
之後所有的推導都是去解決目標函數的最優化上了。在解決最優化的過程中，發現了w可以由特徵向量內積來表示，進而發現了核函數，僅需要調整核函數就可以將特徵進行低維到高維的變換，在低維上進行計算，實質結果表現在高維上。由於並不是所有的樣本都可分，為了保證SVM的通用性，進行了軟間隔的處理，導致的結果就是將優化問題變得更加復雜，然而驚奇的是鬆弛變數沒有出現在最後的目標函數中。最後的優化求解問題，也被拉格朗日對偶和SMO演算法化解，使SVM趨向於完美。

❷ 如何用python實現smo演算法

在ml中常見的優化演算法基本都是： sgd 這種對每個單變數進行同步更新 als(交替最小二乘）/smo(序列最小優化）這種交替（固定一個單變數，優化另一個單變數）思路。如果你熟悉smo，那麼als就也可以理解了。 其它（希望更多的人補充）

❸ svm中smo演算法解決對偶問題第二個alpha的選擇的原則是什麼

alpha>0 才會有y(wx+b)=0這個條件存在，所以確定分割超平面y=wx+b之後，才可以找到那些使得alpha>0的點也即支撐向量啊~

❹ 支持向量機學習演算法

支持向量機學習演算法主要有以下五種：

（1）獲取學習樣本（xⁱ，yⁱ），i=1，2…，其中xⁱ∈Rⁿ，y∈任 ｛1，-1｝^l，對樣本進行預處理；

（2）選擇進行非線性變換的核函數及對錯分（誤差）進行懲罰的懲罰因子c；

（3）形成二次優化問題用優化方法（如：Chuknlng演算法、內點演算法、SMO演算法）；

（4）獲得a，a^*及b₀的值，代入方程中，獲得分類或函數擬合的支持向量機；

（5）將需預測或分類的數據代入支持向量機方程中獲得結果。

基坑降水環境影響評價參數選取降水方式、岩土性質、水文地質邊界、基坑側壁狀態、邊載分布、後續使用年限、基礎型式、差異沉降8級，目標輸出模式對應4個級別：優等級（Ⅰ）、良好級（Ⅱ）、中等級（Ⅲ）、差級（Ⅳ）。

用一對多多類支持向量機水質分類法：有四類等級要劃分，於是在抽取訓練集的時候，分別抽取I所對應的向量作為正集，其餘所對應的向量作為負集；Ⅱ所對應的向量作為正集，其餘所對應的向量作為負集……，這四個訓練集分別進行訓練得到四個分類器。然後，利用這四個訓練結果文件對測試集分別進行測試，最後每個測試都有一個結果，最終的結果便是這四個值中最大的一個。

利用支持向量機進行基坑降水環境影響評價就是尋找影響基坑降水環境系統和孕災環境系統的指標和基坑降水環境影響等級之間的關系，可建立以下四個分類函數：

基坑降水工程的環境效應與評價方法

❺ 機器學習實戰 SMO演算法是否寫錯了

我確定，里頭的完整版SMO演算法是寫錯了。在尋找第二個變數時，每次只找了一個，優化失敗後就放棄了，重新挑選第一個變數。這樣最後演算法結束後，還有不少變數不滿足KKT條件。我一度以為這個演算法不能收斂到全局最優。而且每次運行結果都不一樣。後來，我把代碼改了一下，在尋找第二個變數時，把所有可能符合條件的變數都嘗試一遍。這樣，演算法就能收斂了。運行結束後，所有變數都能滿足KKT條件。

❻ svm演算法是什麼

SVM(Support Vector Machine)中文名為支持向量機，是常見的一種判別方法。

支持向量機（Support Vector Machine, SVM）是一類按監督學習（supervised learning）方式對數據進行二元分類的廣義線性分類器（generalized linear classifier），其決策邊界是對學習樣本求解的最大邊距超平面（maximum-margin hyperplane）。

數值求解特點：

SVM的求解可以使用二次凸優化問題的數值方法，例如內點法和序列最小優化演算法，在擁有充足學習樣本時也可使用隨機梯度下降。

在二次凸優化問題中，SMO的每步迭代都嚴格地優化了SVM的對偶問題，且迭代會在有限步後收斂於全局極大值。SMO演算法的迭代速度與所選取乘子對KKT條件的偏離程度有關，因此SMO通常採用啟發式方法選取拉格朗日乘子。

在每次迭代時，SGD首先判定約束條件，若該樣本不滿足約束條件，則SGD按學習速率最小化結構風險；若該樣本滿足約束條件，為SVM的支持向量，則SGD根據正則化系數平衡經驗風險和結構風險，即SGD的迭代保持了SVM的稀疏性。

❼ SVM幾種核函數的對比分析以及SVM演算法的優缺點

SVM核函數的作用

SVM核函數是用來解決數據線性不可分而提出的，把數據從源空間映射到目標空間（線性可分空間）。

SVM中核函數的種類

1、線性核

優點：

• 方案首選，奧卡姆剃刀定律

• 簡單，可以求解較快一個QP問題

• 可解釋性強：可以輕易知道哪些feature是重要的

限制：只能解決線性可分問題

2、多項式核

基本原理：依靠升維使得原本線性不可分的數據線性可分；
升維的意義：使得原本線性不可分的數據線性可分；

優點：

• 可解決非線性問題

• 可通過主觀設置冪數來實現總結的預判

缺點：

• 對於大數量級的冪數，不太適用

• 比較多的參數要選擇

通常只用在已經大概知道一個比較小的冪數的情況


3、高斯核

優點：

• 可以映射到無限維

• 決策邊界更為多樣

• 只有一個參數，相比多項式核容易選擇

缺點：

• 可解釋性差(無限多維的轉換，無法算w)

• 計算速度比較慢(解一個對偶問題)

• 容易過擬合(參數選不好時容易overfitting)

4、Sigmoid核

採用Sigmoid函數作為核函數時，支持向量機實現的就是一種多層感知器神經網路，應用SVM方法，隱含層節點數目(它確定神經網路的結構)、隱含層節點對輸入節點的權值都是在設計(訓練)的過程中自動確定的。而且支持向量機的理論基礎決定了它最終求得的是全局最優值而不是局部最小值，也保證了它對於未知樣本的良好泛化能力而不會出現過學習現象。

在實戰中更多的是：

• 特徵維數高選擇線性核

• 樣本數量可觀、特徵少選擇高斯核（非線性核）

• 樣本數量非常多選擇線性核（避免造成龐大的計算量）

SVM的優缺點

1、SVM演算法對大規模訓練樣本難以實施

SVM的空間消耗主要是存儲訓練樣本和核矩陣，由於SVM是藉助二次規劃來求解支持向量，而求解二次規劃將涉及m階矩陣的計算（m為樣本的個數），當m數目很大時該矩陣的存儲和計算將耗費大量的機器內存和運算時間。針對以上問題的主要改進有有J.Platt的SMO演算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、張學工的CSVM以及O.L.Mangasarian等的SOR演算法。如果數據量很大，SVM的訓練時間就會比較長，如垃圾郵件的分類檢測，沒有使用SVM分類器，而是使用了簡單的naive bayes分類器，或者是使用邏輯回歸模型分類。

2、用SVM解決多分類問題存在困難

經典的支持向量機演算法只給出了二類分類的演算法，而在數據挖掘的實際應用中，一般要解決多類的分類問題。可以通過多個二類支持向量機的組合來解決。主要有一對多組合模式、一對一組合模式和SVM決策樹；再就是通過構造多個分類器的組合來解決。主要原理是克服SVM固有的缺點，結合其他演算法的優勢，解決多類問題的分類精度。如：與粗集理論結合，形成一種優勢互補的多類問題的組合分類器。

3、對缺失數據敏感，對參數和核函數的選擇敏感

支持向量機性能的優劣主要取決於核函數的選取,所以對於一個實際問題而言,如何根據實際的數據模型選擇合適的核函數從而構造SVM演算法。目前比較成熟的核函數及其參數的選擇都是人為的,根據經驗來選取的,帶有一定的隨意性.在不同的問題領域,核函數應當具有不同的形式和參數,所以在選取時候應該將領域知識引入進來,但是目前還沒有好的方法來解決核函數的選取問題。

❽ SVM計算復雜度是多少，有好的說明資料或者參考文獻嗎

在理解了SVM的原理的情況下 繼續理解SMO演算法 緊接著可以參考《機器學習實戰》中的SMO演算法源碼 分析其計算復雜度

網頁鏈接可以參考這里的SMO演算法講解

❾ SVM中的對偶問題，KKT條件以及對拉格朗日乘子求值得SMO演算法

拉格朗日乘子法 拉格朗日乘子（Lagrange multiplier） 基本的拉格朗日乘子法(又稱為拉格朗日乘數法)，就是求函數f(x1,x2,...)在g(x1,x2,...)=0的約束條件下的極值的方法。其主要思想是引入一個新的參數λ（即拉格朗日乘子），將約束條件函數與原

❿ SVM演算法，包括演算法原理、演算法實現、核函數參數的選取、優化、系數調整，能通俗地說明下嗎謝謝

SVM 原理，在一個超空間找一個 切分的超平面，
SVM 演算法實現，主要是解決SVM公式對偶問題，常用的是SMO，
SVM 核參數，隱含的將特徵映射到高維空間，有興趣可學習 learn with kernel.
SVM 參數調整分兩部分，1 參數調整，用上述SMO演算法，2 模型選擇。

太累，不想寫太多