⑴ 支持向量機(SVM)基本原理
看了很多關於SVM的博客，但是常常只能保存書簽之後看，有時候有的博客就突然沒了，這里就作為搬運工總結一下之後自己看吧。主要內容來自於：
支持向量機通俗導論（理解SVM的三層境界）
線性回歸
給定數據集 , 其中, ,線性回歸試圖學習到一個線性模型,盡可能地輸出正確標記.
如果我們要用線性回歸演算法來解決一個分類問題,(對於分類,y 取值為 0 或者 1),但如果你使用的是線性回歸,那麼假設函數的輸出值可能遠大於 1,或者遠小於 0,就算所有訓練樣本的標簽 y 都是 0 或 1但是如果演算法得到的值遠大於 1 或者遠小於 0 的話,就會感覺很奇怪。所以我們在接下來的要研究的演算法就叫做邏輯回歸演算法,這個演算法的性質是:它的輸出值永遠在 0 到 1 之間。
所以邏輯回歸就是一個分類演算法,這個演算法的輸出值永遠在 0 到 1 之間.
我們先看二分類的LR,具體做法是:利用sigmoid 函數,將每一個點的回歸值映射到0,1之間.sigmoid函數特性如下:
如圖所示,令 , 當 z > 0 , z 越大, sigmoid 返回值越接近1(但永遠不會超過1). 反之,當z < 0時,z 越小, sigmoid 返回值越接近0(但永遠不會小於0).
支持向量機 ，因其英文名為support vector machine，故一般簡稱SVM，通俗來講，它是一種二類分類模型，其基本模型定義為 特徵空間 上的間隔最大的線性分類器，其學習策略便是間隔最大化，最終可轉化為一個凸二次規劃問題的求解。
線性分類器
給定一些數據點，它們分別屬於兩個不同的類，現在要找到一個線性分類器把這些數據分成兩類。如果用x表示數據點，用y表示類別（y可以取1或者-1，分別代表兩個不同的類），一個線性分類器的學習目標便是要在n維的數據空間中找到一個超平面（hyper plane），這個超平面的方程可以表示為（ wT中的T代表轉置）：
logistic回歸目的是從特徵學習出一個0/1分類模型，而這個模型是將特性的線性組合作為自變數，由於自變數的取值范圍是負無窮到正無窮。因此，使用logistic函數（或稱作sigmoid函數）將自變數映射到(0,1)上，映射後的值被認為是屬於y=1的概率。
假設函數:
其中x是n維特徵向量，函數g就是logistic函數。
圖像為：
在超平面w x+b=0確定的情況下，|w x+b|能夠表示點x到距離超平面的遠近，而通過觀察w x+b的符號與類標記y的符號是否一致可判斷分類是否正確，所以，可以用(y (w*x+b))的正負性來判定或表示分類的正確性。於此，我們便引出了函數間隔（functional margin）的概念。
定義函數間隔 （用表示）為
而超平面(w，b)關於T中所有樣本點(xi，yi)的函數間隔最小值（其中，x是特徵，y是結果標簽，i表示第i個樣本），便為超平面(w, b)關於訓練數據集T的函數間隔：
但這樣定義的函數間隔有問題，即如果成比例的改變w和b（如將它們改成2w和2b），則函數間隔的值f(x)卻變成了原來的2倍（雖然此時超平面沒有改變），所以只有函數間隔還遠遠不夠。
事實上，我們可以對法向量w加些約束條件，從而引出真正定義點到超平面的距離--幾何間隔（geometrical margin）的概念。
假定對於一個點 x ，令其垂直投影到超平面上的對應點為 x0 ，w 是垂直於超平面的一個向量， 為樣本x到超平面的距離，如下圖所示：
根據平面幾何知識，有
其中||w||為w的二階范數（范數是一個類似於模的表示長度的概念）， 是單位向量（一個向量除以它的模稱之為單位向量）。
又由於x0 是超平面上的點，滿足 f(x0)=0，代入超平面的方程 ,可得 ，即
隨即讓此式 的兩邊同時乘以 ，再根據 和 ，即可算出 ：
為了得到 的絕對值，令 乘上對應的類別 y，即可得出幾何間隔（用 表示）的定義：
從上述函數間隔和幾何間隔的定義可以看出：幾何間隔就是函數間隔除以||w||，而且函數間隔y (wx+b) = y f(x)實際上就是|f(x)|，只是人為定義的一個間隔度量，而幾何間隔|f(x)|/||w||才是直觀上的點到超平面的距離。
對一個數據點進行分類，當超平面離數據點的「間隔」越大，分類的確信度（confidence）也越大。所以，為了使得分類的確信度盡量高，需要讓所選擇的超平面能夠最大化這個「間隔」值。這個間隔就是下圖中的Gap的一半。
通過由前面的分析可知：函數間隔不適合用來最大化間隔值，因為在超平面固定以後，可以等比例地縮放w的長度和b的值，這樣可以使得 的值任意大，亦即函數間隔 可以在超平面保持不變的情況下被取得任意大。但幾何間隔因為除上了 ，使得在縮放w和b的時候幾何間隔的值 是不會改變的，它只隨著超平面的變動而變動，因此，這是更加合適的一個間隔。換言之，這里要找的最大間隔分類超平面中的「間隔」指的是幾何間隔。
於是最大間隔分類器（maximum margin classifier）的目標函數可以定義為
同時需滿足一些條件，根據間隔的定義，有
回顧下幾何間隔的定義 ，可知：如果令函數間隔 等於1（之所以令等於1，是為了方便推導和優化，且這樣做對目標函數的優化沒有影響），則有 = 1 / ||w||且 ，從而上述目標函數轉化成了：
相當於在相應的約束條件 下，最大化這個1/||w||值，而1/||w||便是幾何間隔。
據了解，
由於這個問題的特殊結構，還可以通過拉格朗日對偶性（Lagrange Duality）變換到對偶變數 (al variable) 的優化問題，即通過求解與原問題等價的對偶問題（al problem）得到原始問題的最優解，這就是線性可分條件下支持向量機的對偶演算法，這樣做的優點在於：一者對偶問題往往更容易求解；二者可以自然的引入核函數，進而推廣到非線性分類問題。
那什麼是拉格朗日對偶性呢？簡單來講，通過給每一個約束條件加上一個拉格朗日乘子 ,（Lagrange multiplier），定義拉格朗日函數（通過拉格朗日函數將約束條件融合到目標函數里去，從而只用一個函數表達式便能清楚的表達出我們的問題）
然後令：
容易驗證，當某個約束條件不滿足時，例如 ，那麼顯然有 （只要令 即可）。而當所有約束條件都滿足時，則最優值為 ，亦即最初要最小化的量。
因此，在要求約束條件得到滿足的情況下最小化 ，實際上等價於直接最小化 （當然，這里也有約束條件，就是 ≥0,i=1,…,n） ，因為如果約束條件沒有得到滿足， 會等於無窮大，自然不會是我們所要求的最小值。
具體寫出來，目標函數變成了：
這里用 表示這個問題的最優值，且和最初的問題是等價的。如果直接求解，那麼一上來便得面對w和b兩個參數，而 又是不等式約束，這個求解過程不好做。不妨把最小和最大的位置交換一下，變成：
交換以後的新問題是原始問題的對偶問題，這個新問題的最優值用 來表示。而且有 ≤ ，在滿足某些條件的情況下，這兩者相等，這個時候就可以通過求解對偶問題來間接地求解原始問題。
換言之，之所以從minmax 的原始問題，轉化為maxmin 的對偶問題，一者因為 是 的近似解，二者，轉化為對偶問題後，更容易求解。
下面可以先求L 對w、b的極小，再求L對 的極大。
KKT條件
≤ 在滿足某些條件的情況下，兩者等價，這所謂的「滿足某些條件」就是要滿足KKT條件。
要讓兩者等價需滿足strong ality （強對偶），而後有學者在強對偶下提出了KKT條件，且KKT條件的成立要滿足constraint qualifications，而constraint qualifications之一就是Slater條件。所謂Slater 條件，即指：凸優化問題，如果存在一個點x，使得所有等式約束都成立，並且所有不等式約束都嚴格成立（即取嚴格不等號，而非等號），則滿足Slater 條件。對於此處，Slater 條件成立，所以 ≤ 可以取等號。
一般地，一個最優化數學模型能夠表示成下列標准形式：
其中，f(x)是需要最小化的函數，h(x)是等式約束，g(x)是不等式約束，p和q分別為等式約束和不等式約束的數量。
KKT條件的意義：它是一個非線性規劃（Nonlinear Programming）問題能有最優化解法的必要和充分條件。
而KKT條件就是指上面最優化數學模型的標准形式中的最小點 x* 必須滿足下面的條件：
我們這里的問題是滿足 KKT 條件的（首先已經滿足Slater條件，再者f和gi也都是可微的，即L對w和b都可導），因此現在我們便轉化為求解第二個問題。
也就是說，原始問題通過滿足KKT條件，已經轉化成了對偶問題。而求解這個對偶學習問題，分為3個步驟：首先要讓L(w，b，a) 關於 w 和 b 最小化，然後求對 的極大，最後利用SMO演算法求解對偶問題中的拉格朗日乘子。
對偶問題求解的3個步驟
將以上結果代入之前的L：
得到：
具體推導過程是比較復雜的，如下所示：
最後，得到：
「倒數第4步」推導到「倒數第3步」使用了線性代數的轉置運算，由於ai和yi都是實數，因此轉置後與自身一樣。「倒數第3步」推導到「倒數第2步」使用了(a+b+c+…)(a+b+c+…)=aa+ab+ac+ba+bb+bc+…的乘法運演算法則。最後一步是上一步的順序調整。
從上面的最後一個式子，我們可以看出，此時的拉格朗日函數只包含了一個變數，那就是 （求出了 便能求出w，和b，由此可見，則核心問題：分類函數 也就可以輕而易舉的求出來了）。
上述式子要解決的是在參數上 求最大值W的問題，至於 和 都是已知數。要了解這個SMO演算法是如何推導的，請跳到下文第3.5節、SMO演算法。
總結
讓我們再來看看上述推導過程中得到的一些有趣的形式。首先就是關於我們的 hyper plane ，對於一個數據點 x 進行分類，實際上是通過把 x 帶入到 算出結果然後根據其正負號來進行類別劃分的。而前面的推導中我們得到:
因此分類函數為：
這里的形式的有趣之處在於，對於新點 x的預測，只需要計算它與訓練數據點的內積即可（表示向量內積），這一點至關重要，是之後使用 Kernel 進行非線性推廣的基本前提。此外，所謂 Supporting Vector 也在這里顯示出來——事實上，所有非Supporting Vector 所對應的系數 都是等於零的，因此對於新點的內積計算實際上只要針對少量的「支持向量」而不是所有的訓練數據即可。
為什麼非支持向量對應的 等於零呢？直觀上來理解的話，就是這些「後方」的點——正如我們之前分析過的一樣，對超平面是沒有影響的，由於分類完全有超平面決定，所以這些無關的點並不會參與分類問題的計算，因而也就不會產生任何影響了。
回憶一下我們通過 Lagrange multiplier得到的目標函數：
注意到如果 xi 是支持向量的話，上式中紅顏色的部分是等於 0 的（因為支持向量的 functional margin 等於 1 ），而對於非支持向量來說，functional margin 會大於 1 ，因此紅顏色部分是大於零的，而 又是非負的，為了滿足最大化， 必須等於 0 。這也就是這些非Supporting Vector 的點的局限性。
至此，我們便得到了一個maximum margin hyper plane classifier，這就是所謂的支持向量機（Support Vector Machine）。當然，到目前為止，我們的 SVM 還比較弱，只能處理線性的情況，不過，在得到了對偶al 形式之後，通過 Kernel 推廣到非線性的情況就變成了一件非常容易的事情了(通過求解對偶問題得到最優解，這就是線性可分條件下支持向量機的對偶演算法，這樣做的優點在於：一者對偶問題往往更容易求解；二者可以自然的引入核函數，進而推廣到非線性分類問題」)。
事實上，大部分時候數據並不是線性可分的，這個時候滿足這樣條件的超平面就根本不存在。在上文中，我們已經了解到了SVM處理線性可分的情況，那對於非線性的數據SVM咋處理呢？對於非線性的情況，SVM 的處理方法是選擇一個核函數 κ(⋅,⋅) ，通過將數據映射到高維空間，來解決在原始空間中線性不可分的問題。
具體來說，在線性不可分的情況下，支持向量機首先在低維空間中完成計算，然後通過核函數將輸入空間映射到高維特徵空間，最終在高維特徵空間中構造出最優分離超平面，從而把平面上本身不好分的非線性數據分開。如圖所示，一堆數據在二維空間無法劃分，從而映射到三維空間里劃分：
而在我們遇到核函數之前，如果用原始的方法，那麼在用線性學習器學習一個非線性關系，需要選擇一個非線性特徵集，並且將數據寫成新的表達形式，這等價於應用一個固定的非線性映射，將數據映射到特徵空間，在特徵空間中使用線性學習器，因此，考慮的假設集是這種類型的函數：
這里ϕ：X->F是從輸入空間到某個特徵空間的映射，這意味著建立非線性學習器分為兩步：
首先使用一個非線性映射將數據變換到一個特徵空間F，
然後在特徵空間使用線性學習器分類。
而由於對偶形式就是線性學習器的一個重要性質，這意味著假設可以表達為訓練點的線性組合，因此決策規則可以用測試點和訓練點的內積來表示：
如果有一種方式可以在特徵空間中直接計算內積〈φ(xi · φ(x)〉，就像在原始輸入點的函數中一樣，就有可能將兩個步驟融合到一起建立一個非線性的學習器，這樣直接計演算法的方法稱為核函數方法：
核是一個函數K，對所有x，z，滿足 ，這里φ是從X到內積特徵空間F的映射。
來看個核函數的例子。如下圖所示的兩類數據，分別分布為兩個圓圈的形狀，這樣的數據本身就是線性不可分的，此時咱們該如何把這兩類數據分開呢(下文將會有一個相應的三維空間圖)？
事實上，上圖所述的這個數據集，是用兩個半徑不同的圓圈加上了少量的噪音生成得到的，所以，一個理想的分界應該是一個「圓圈」而不是一條線（超平面）。如果用 和 來表示這個二維平面的兩個坐標的話，我們知道一條二次曲線（圓圈是二次曲線的一種特殊情況）的方程可以寫作這樣的形式：
注意上面的形式，如果我們構造另外一個五維的空間，其中五個坐標的值分別為 ，那麼顯然，上面的方程在新的坐標系下可以寫作：
關於新的坐標 ，這正是一個 hyper plane 的方程！也就是說，如果我們做一個映射 ，將 按照上面的規則映射為 ，那麼在新的空間中原來的數據將變成線性可分的，從而使用之前我們推導的線性分類演算法就可以進行處理了。這正是 Kernel 方法處理非線性問題的基本思想。
再進一步描述 Kernel 的細節之前，不妨再來看看上述例子在映射過後的直觀形態。當然，你我可能無法把 5 維空間畫出來，不過由於我這里生成數據的時候用了特殊的情形，所以這里的超平面實際的方程是這個樣子的（圓心在 軸上的一個正圓）
因此我只需要把它映射到 ，這樣一個三維空間中即可，下圖即是映射之後的結果，將坐標軸經過適當的旋轉，就可以很明顯地看出，數據是可以通過一個平面來分開的
核函數相當於把原來的分類函數：
映射成：
而其中的 可以通過求解如下 al 問題而得到的：
這樣一來問題就解決了嗎？似乎是的：拿到非線性數據，就找一個映射
⑵ SVM演算法原理
一、決策面方程
以二維空間為例，二維空間中任意一條直線方程可以寫為
我們將其向量化，可以得到
設用向量w代表矩陣a1和a2，用向量x代表矩陣x1和x2，標量γ代表b，則方程可化表示為
從方程可知，一個n維空間的超平面在二維空間上的表現，可以是一條直線，或者一個曲線（二維空間中只能看到這個n維超平面穿過而無法看到其模樣）， 超平面方程即是我們的決策面方程
二、函數間隔和幾何間隔
在SVM監督學習中，我們規定標簽數據為+1和-1兩個值，這么做的目的， 可以計算出任意一個樣本點在超平面方程上的表現結果的符號，與標簽符號是否一致來判斷分類的正確性 ，為此我們可以引入函數間隔的概念
但是當我們成比例的縮放w和γ，函數間隔的值也將成比例的變化，可是超平面的位置並沒有發生任何變化，所以函數間隔並不是我們想要的分類間隔，為此，我們需要引入幾何間隔的概念
還是以二維空間出發，任意一點到直線的距離可以寫成
我們將其拓展到n維空間，直線方程即是我們的超平面方程，則n維空間中任何一點到超平面的距離可以寫成
為此，我們引入幾何間隔概念，其中||w||表示向量w的二范數
從幾何間隔可以看出，就算等比例縮放w和γ，由於除上了||w||使得幾何間隔的值不會改變，它只隨著超平面位置的變化而變化，因此， 我們要尋找的分類間隔是幾何間隔
三、不等式約束條件
SVM演算法的目的是找到一個將分類效果達到最合理化的超平面，這個超平面即是分類器 。而評估分類器的好壞的標准就是分類間隔的大小
我們定義分類間隔的距離為d，好的分類器應該讓所有樣本點到決策面的幾何間隔都大於等於d
化簡上式，不等式兩邊同時除以d可得
由於||w||和d都是標量，可定義
則上式可化簡為
在不等式兩邊同時乘以yi，即將兩個式子化簡為一個式子（這里體現了正是因為標簽數據為+1和-1，才方便將約束條件變成一個約束方程）
這個約束方程的意義 即是任何樣本點到超平面（分類器）的幾何間隔都大於等於分類間隔
四、SVM最優化模型的數學描述
評估分類器的優劣是分類間隔的大小，且對於任意樣本點都滿足約束方程
由約束方程可知，當樣本點落在支持向量邊界上有如下關系
則分類間隔d可以表示為支持向量點到超平面的幾何間隔
要讓任何樣本點都在d之外，即求分類間隔d的最大值，則目標函數可以寫成
為了方便在後續最優化處理中對目標函數的求導，我們將目標函數做等效變化
由目標函數是二次的，而約束條件是線性的，則 SVM的數學模型即是：不等式約束條件下的二次型函數優化 ，而求解這一類優化問題，接下來我們需要構造 拉格朗乘子函數
五、引入拉格朗函數
目標函數是求解在約束條件g(x)下的二次型函數f(x)的最小值，直觀上我們希望構造一個函數L(x)，使得L(x)在f(x)的可行解區域內的求出的值和f(x)求出的值完全一樣，而在f(x)的可行解區域外，L(x)的值又接近無窮大，這么做的目的，使得我們可以用一個函數L(x)來等效表示原問題的g(x)和f(x)
拉格朗函數的目的，就是將約束條件融合到目標函數中，構造一個新函數來表示目標函數，將有約束的優化問題轉化為無約束的優化問題
下面，我們構造拉格朗函數來表示目標函數
其中αi是拉格朗日乘子，每一個約束條件對應一個拉格朗日乘子，其中αi大於等於0
則原優化問題可以轉化為
討論如下條件(1)(2)：
(1) 當樣本點不滿足約束條件時，即說明在 可行解區域外
此時將αi置為正無窮大，那麼θ(w)顯然也是正無窮大
(2) 當樣本點滿足約束條件時，即說明在 可行解區域內
此時θ(w)的最小值就是原目標函數，於是綜上所述，引入拉格朗乘子函數後，可以得到新的目標函數
我們用p*表示優化目標函數後的最優解，且與最初的目標函數等價
觀察新的目標函數，如果直接求偏導數求解，那麼一上來將面對w和b兩個未知參數，而αi又是不等式約束，求解過程將非常復雜。換一個角度思考，如果將max和min的位置對調，變成如下新的目標函數
上式變化使用了 拉格朗日函數的對偶性，交換後的新問題即是原目標函數的對偶問題 ，我們用d*來表示對偶目標函數的最優解，可見d*的求導過程比p*相對容易，且d*<=p*，而當滿足下列條件時，d*= p*
因為目標函數本身已經是一個凸函數，而優化問題又是求解最小值，所以目標函數的最優化問題就是凸優化問題，則接下來就要重點討論KKT條件
六、KKT條件的描述
一個最優化模型能夠表示成下列標准形式
其中f(x)是需要最小化的函數，h(x)是等式約束，g(x)是不等式約束，m和n分別是等式約束和不等式約束的數量
KKT條件即是規定f(x)的 最優值 必須滿足以下(1)(2)(3)條件， 只有滿足KKT條件，目標函數的最優化問題依然可以用拉格朗日乘子法解決
很明顯，我們需要優化的目標函數屬於帶有不等式約束函數g(x)，所以條件二顯然滿足，下面我們來分析條件一和條件三的理論
七、目標函數的等高線與約束條件的最優值分析（條件一）
對於KKT條件一的分析，我們假設目標函數是f(x1,x2)的二元函數，它的圖像在三維空間里是一個曲面，准確的來說是一個凸曲面
其中g(x1,x2)是約束方程，要求目標函數f(x1,x2)的最小值，即轉化為 求g(x1,x2)=c這條曲線上的一點，使得f(x1,x2)取得最小值，換個比喻，就是在山上（目標函數曲面）尋找一條山路（約束條件曲線）的最低點
我們畫出目標函數的等高線，來分析目標函數最優值和約束條件的關系
對於研究目標函數z=f(x1,x2)，當z取不同的值，即將曲線z投影在(x1,x2)組成的空間中（這里指的是二維空間），也就是曲面的等高線，上圖中d1和d2即是兩條目標函數的等高線，可以看出，當約束函數g(x1,x2)與目標函數的等高線有共同的交點， 即證明這組值同時滿足在目標函數的可行域中，也符合約束條件的約束關系
如果等高線與g(x1,x2) 相交 ，則是一組目標函數的解，但是這個解一定不是最優解， 因為相交意味著肯定存在其它等高線在該條等高線的內部或者外部 ，可能會使得新的等高線與g(x1,x2)的交點更大或者更小，這就意味著只有當等高線與g(x1,x2) 相切 ，才可能得到最優解（切線可能多條）
所以最優解必須滿足： 目標函數的負梯度方向與約束函數的梯度方向一致
而上式恆成立的條件就是： 拉格朗日乘子α >= 0 ，且這個式子就是目標函數對各個參數求偏導數的結果，即KKT的第一個條件：目標函數對各個參數的導數為0
八、分類討論約束條件和拉格朗日乘子的組合（條件三）
對於KKT條件三，可以看出，因為所有的約束函數gi(x)<=0，所有的拉格朗日乘子αi>=0，要使得求和後結果為0，要麼某個約束函數gi(x)=0，要麼其對應的αi=0
從一個案例出發來分析KKT條件三的邏輯，假設目標函數和約束函數是
將不等式約束構造出拉格朗日函數，並分別對x1和x2求偏導數
而KKT的條件三要求最優解滿足 ∑α*g(x) = 0，在這個案例里α和g(x)只有一個，結合條件一，可以得到
根據之前的分析，最優值滿足條件三的話，要麼α=0，要麼g(x)=0
（i）：如果α=0，則x1=1，x2=-2，代入g(x1,x2) =10-1-10*(-2)=29>0，發現這組解違背了約束函數g(x)<0，則舍棄這組解
（ii）: 如果g(x1,x2)=0，則代入x1和x2的表達式到g(x)中，解出α=58/101>0，發現這組解不違背約束函數，則代入α解出x1=130/101，x2=88/101，則這組解有可能是最優解
綜上(i)(ii)討論，目標函數的最優值符合KKT條件三，也說明了 滿足強對偶條件的優化問題的最優值必須滿足KKT條件
九、求解對偶問題
上面分析了目標函數滿足凸優化和KKT條件，則問題轉化為求解原問題的對偶問題（即p*=d*）
根據對偶問題描述，先要求內側w和b關於L(w,b,α)的最小化值，即求L對w和b的偏導數
將w和b的偏導數帶入拉格朗函數化簡得
整理一下最終化簡結果為
從上述結果可以看出，樣本的x和y是已知的，此時的 L(w,b,α)函數只有一個變數，即αi
我們歸納一下現在的目標函數為
現在目標函數變成了如上形式，其中αi>=0，這里隱含著一個假設，即數據100%線性可分，但是現實生活中，數據往往是不會那麼規則的線性化，為此我們需要引入鬆弛變數
十、引入鬆弛變數
由於現實世界中的數據都是帶有噪音的，也就是數據可能出偏離其正常的位置很遠，而出現這種極端現象後往往會影響超平面的選擇，也許將無法構造出將數據徹底分開的超平面出來
所以對於處理這種情況， SVM需要允許（妥協）出某些噪音很大的數據點能夠偏離超平面，即允許其出現在超平面的錯誤的一側 ，為此我們引入鬆弛變數C，這樣我們的目標函數又變為
接下來為了研究討論αi的取值范圍，我們加上一個負號將目標函數等價轉化為
十一、討論拉格朗乘子的取值意義和其值域
回顧一下最初的約束條件為
設ui為該約束條件，可以歸納出αi關於約束函數的取值意義
αi只有滿足上述3種情況，才能求出最優解，所以 當αi與約束條件ui沖突的時候，需要更新這些αi ，這也就是滿足目標函數的第一個約束限制，即0<=αi<=C
而同時目標函數還受到第二個約束條件的限制，即
所以不能只更新一個αi因子，需要同時再次更新第二個αj因子，也就是 α因子總是成對的更新（αi對總是和αj配對），一增一減，此消彼長，才能保證加權和為0的約束 ，同時這也就是下面提及SMO演算法的思想和多元函數化簡為二元函數，在從二元函數化簡為一元函數的難點
根據這個約束和α因子需要成對更新，假設我們選取的兩個拉格朗乘子為α1和α2，則更新之前是old，更新之後是new，且更新前後需要滿足和為0的約束
兩個因子同時更新顯然非常困難，所以需要先求出第一個αj的解，再用αj的解去表示更新第二個αi的解 ，後文的SMO演算法會闡述這一點。因此需要先確定αj的取值范圍，假設L和H分別為它的下界和上界，結合目標函數的約束限制來綜合討論L和H的取值關系
（i）：當y1和y2異號時，可以得到
移項可得a2 = a1 - A，此時α的取值范圍如下圖所示
所以此時α的上下界H和L為
（ii）：當y1和y2同號時，可以得到
移項可得a2 = -a1 + A，此時α的取值范圍如下圖所示
所以此時α的上下界H和L為
綜上(i)(ii)的討論，通過y1和y2的異號或者同號，可以推導出α更新後的上下界分別為
這個公式顯得非常的重要，它將α因子限制在有效的矩形范圍內，在SMO演算法中，當我們更新完α後，由於α可能會被更新得很大或很小，因此需要經過裁剪來保證α的在約束條件內
12、SMO演算法的思想
回顧之前第九，第十，第十一步的分析，目標函數為
目標函數只包含n個變數α的 多元函數 ，且帶有兩個約束條件，我們的 目的是求出目標函數的最小值，即找到一組α的組合，使得目標函數取得最小值
由第十一步的分析，我們需要不斷更新這n個α因子，通過迭代來逼近函數達到最小值，但是如果一次性更新n個參數，將會有n!種組合，那麼時間復雜度將會非常高，為此我們首先想到 坐標上升（下降）法
來通過一個例子來說明坐標上升法的思路
可知案例中要求一個三元函數的最大值， 演算法的思想是每次迭代時只更新一個維度，通過多次迭代直到收斂來優化函數的最值 ，求出三個變數的偏導數推出其關系
通過迭代即就可以求出其最值
SMO演算法借鑒了坐標上升（下降）法的思想來優化α因子組合，但是由於目標函數的第二個約束條件有加權和為0的限制，導致每次迭代時候不能只更新一個因子αi，必須同時更新與之配對的另一個因子αj，此消彼長才能保證加權和為0（第十一步中已提及）
所以SMO演算法思想是將原始問題中，求解n個參數的二次規劃問題，分解成了多個子二次規劃問題來分別求解，每一個子問題只需要求解2個參數，即將多元函數推導為二元函數，再將二元函數推導為一元函數
13、多元函數推導為二元函數
目標函數是關於α的N元函數，通過SMO的演算法思想，假設每次迭代更新，選取一對α1和α2的組合，其餘的乘子不變， 首先需要將α1和α2從目標函數中分離出來 ，也就是將多元函數推導為二元函數
從N元函數中分離出α1和α2因子
由於上式推導結果過於復雜，我們定義2個表達式來表示上式常量部分，用來簡化上式
又由於單獨存下的常數項對以後的求導沒有貢獻，所以我們提出單獨的常數項定義為Constant
帶入vi和Constant表達式，則結果化簡為
至此，我們將 多元函數推導為含有α1和α2變數的二元函數 ，接下來將這個二元函數推導為一元函數
14、二元函數推導為一元函數
我們需要推導出α1和α2的關系，然後用α2來表示α1帶入二元函數，就可以推導出關於α2的一元函數了
由目標函數的第二個約束條件
同理根據SMO演算法思想，從約束條件中分離出α1和α2
將等式兩邊同時乘以y1，可推導出α1和α2的關系
同理，我們定義兩個表達式r和s來表示上式的常量部分，用來簡化上式關系
帶入r和s後，α1和α2的關系推導為
下面將α1帶入我們的二元函數中，可得
至此， 我們將二元函數推導為只含有一個變數α2的一元函數 ，接下來終於可以對目標函數求導了
15、求解一元函數的偏導數，推導出第一個拉格朗乘子的遞推關系
我們對一元函數求α2的偏導數為0
帶入s=y1*y2和y2*y2=1，整理上式可求出α2
⑶ 拉格朗日對偶性
在約束最優化問題中，拉格朗日對偶性將原始問題轉換為對偶問題，通過解對偶問題而得到原始問題的解。該方法在統計學習方法中得到廣泛的應用
假設 f(x)，ci(x),hj(x) 是連續可微函數，考慮約束最優化問題：
討論原始問題與對偶問題的關系：
《統計學習方法》李航
⑷ 求解原始問題和對偶問題常用的優化演算法有哪些
1. 支持向量機的目的是什麼？
對於用於分類的支持向量機來說，給定一個包含正例和反例（正樣本點和負樣本點）的樣本集合，支持向量機的目的是尋找一個超平面來對樣本進行分割，把樣本中的正例和反例用超平面分開，但是不是簡單地分看，其原則是使正例和反例之間的間隔最大。
超平面是什麼呢？簡單地說，超平面就是平面中的直線在高維空間中的推廣。那麼，對於三維空間，超平面就是平面了。對於更高維的空間，我們只能用公式來表達，而缺少直觀的圖形了。總之，在n維空間中的超平面是n-1維的。
超平面的公式為。公式中的w為可以調整的系數向量，b為bias。注意我們的表達習慣，所有的向量都是列向量，所以在第一項的內積中向量w需要進行轉置。
現在考慮樣本集合{xi，di}，xi是輸入的特徵，di是樣本對應的分類。現在規定當樣本xi屬於第一類時，di為1，當xi屬於第二類時，di為-1。
那麼，線性可分的意思就是一個超平面可以把兩類樣本完全地分割開來。用公式表達就是：
你現在可能會問，那麼如果不是線性可分的情況應該怎麼辦呢？事實是這些會在後面處理到。在這里我們首先討論線性可分的情況，然後將其拓展到線性不可分的情況.
現在假設對於線性可分的樣本集，我們有了一個分割超平面，現在我們想通過調整w0和b0讓它分割的正樣本和負樣本保持最大的間隔，這樣我們就獲得了最優的超平面。實際上在操作過程中，我們最大化的是離超平面最近的點到超平面的距離。也就是說，我們要讓超平面盡量遠離最近的點。從圖中可見超平面到正樣本最近點的距離和超平面到負樣本最近點的距離是相等的。這是個巧合么？
假設我們已經找到了一個超平面，它離正樣本最近點的距離大於離負樣本最近點的距離，那麼這個離超平面最近的點就是負樣本中的最近點。而考慮到我們的目標，我們還會調整超平面的位置使它還可以增大一些，即使這樣會犧牲離正樣本最近點的距離。所以調整到最後的結果肯定是超平面離兩側最近點的距離是等距的。
為了更形象地表現正負樣本的間隔，我們可以在分割超平面的兩側再定義兩個超平面H1和H2（如圖中虛線所示），這兩個超平面分別通過正樣本和負樣本中離分割超平面最近的樣本點（圖中加了外圈）。從以上分析可以知道，超平面H1和H2離分割超平面是等距的。
我們定義超平面H1和H2上面的點叫做支持向量。正負樣本的間隔可以定義為超平面H1和H2之間的間隔，它是分割超平面距最近正樣本點距離和最近負樣本點距離之和。
從圖中可以看出，支持向量對於分割超平面的位置是起到關鍵作用的。在優化分割超平面位置之後，支持向量也顯露出來，而支持向量之後的樣本點則對分類並不關鍵。為什麼這樣說呢？因為即使把支持向量以外的樣本點全部刪除，再找到最優的分割超平面，這個超平面的位置跟原先的分割超平面的位置也是一樣的。總結起來就是：
支持向量包含著重構分割超平面所需要的全部信息！
2. 樣本點到超平面距離的表示
如何求一點到超平面的距離呢？
現在我們來看看系數向量w0是什麼含義？回憶一下，w0實際上是超平面的法向量！
那麼，對於任意一個樣本點x，它可以表示為：
其中xp是x在超平面上的投影，r是x到超平面的幾何距離（幾何間隔）。
設 ，
現在由定義有g(xp)為0，則有。
現在我們開看，g(x)實際上度量了樣本點x到超平面的距離，在||w0||恆定的情況下，g(x)絕對值的大小反映了幾何間隔r的大小。我們給g(x)起個名字叫做函數間隔。注意幾何間隔r和函數間隔g(x)都是有正負號的，代表著處於超平面的不同側。
3. 最大化間隔
我們已經知道了函數間隔和幾何間隔的表示，現在回到正題，我們需要最大化支持向量到分割超平面的距離，當然在最開始我們不知道哪些向量是支持向量。
我們的目的是最大化支持向量到分割超平面的幾何間隔r，而不是最大化函數間隔g(x)，為什麼呢？因為超平面方程的系數可以同比例增大或者減小，而不改變超平面本身。所以||w0||是不固定的，這就會影響函數間隔g(x)的大小。
所以我們需要最大化的是幾何間隔r，這等價於我們固定||w0||，然後最大化函數間隔g(x)。但是實際上我們不會這么做，通常的處理方法是固定函數間隔g(x)的絕對值為1，然後最小化||w0||。也就是說我們把支持向量到分割超平面的函數間隔g(x)的絕對值設定為1，然後最小化||w0||。
4. 正式的表述
現在我們可以正式地表述這個問題了。我們需要最小化||w0||，也就是最小化超平面權重向量w0的歐幾里得范數。但是有沒有限定條件呢？還記得上一節最後一句話么？
「也就是說我們把支持向量到分割超平面的函數間隔g(x)設定為1，然後最小化||w0||」
所以最小化||w0||是有限定條件的，如何表述限制條件呢？我們把支持向量對應的g(x)定為+1或者-1（取決於支持向量處於分割超平面的哪一側，也就是說是正樣本還是負樣本），也就表明了對於所有的正樣本點來說，g(x)是>=+1的，而對於負樣本來說，g(x)是<=-1的。
回想g(x)的定義：
，
我們可以把限制條件寫下來：
現在我們可以把上面的問題寫的更簡練：
目標函數：
限制：
1/2是為了以後計算方便所加的，N是樣本點的個數。
現在我們的第一個任務結束了，我們把要尋找最優的分割超平面的問題轉化為帶有一系列不等式約束的優化問題。這個最優化問題被稱作原問題。我們不會直接解它，而是把它轉化為對偶問題進行解決。至於如何將其轉化為對偶問題，這是以後幾節的內容。
等式約束極小的最優性條件
對支持向量機的求解都是將上節說的原問題轉化為對偶問題進行求解的，這些內容都是最優化課程中的內容。
回憶上節的內容，我們的目標是尋找函數在若干約束條件下的最小值。在上節的原問題中，約束條件是包含不等式的，本節先考慮簡單的問題，即考慮只包含等式約束的最優化問題：
（1）
其中f(x)被稱作目標函數，而下面是一系列的等式約束。回想一下，當沒有任何約束存在的時候，應該怎樣尋找最優點呢？事實上x*是最優點的必要條件是：
而如果函數f(x)是凸函數的話，這個條件也是充分條件。
插入一個說明，如果函數f(x)是一個實值函數，x是一個n維向量，那麼f(x)對向量x的導數被定義為：
回到目前的問題，當我們尋找約束存在時的最優點的時候，約束的存在雖然減小了需要搜尋的范圍，但是卻使問題變得更加復雜。為了使問題變得易於處理，我們的方法是把目標函數和約束全部融入一個新的函數，即拉格朗日函數，再通過這個函數來尋找最優點。
為了形象化地分析這個問題，我們考慮目標函數是三變數的函數並且只有一個約束的情況：
（2）
從幾何上來看，上面的問題（2）就是從曲面上來尋找函數的最小值。假設問題（2）的最優解是。我們現在做曲面Ω上任一條通過點x的光滑曲線l：（由於曲線l是在曲面Ω上的，所以自然有）。
令最優點對應的t為t*。因為x*是曲面Ω上的最優點，所以x*也是曲線l上的最優點，所以t*是一元函數的最優點，所以在這一點它的導數是0。通過鏈式法則我們得到：
這個式子說明了在x*這一點，函數的梯度向量 和曲線l在x*處的切線是垂直的。由於曲線l是任意的，所以梯度向量和曲面Ω是垂直的。
回憶高等數學的結論，的方向就是曲面Ω的法線方向，所以和必然在同一直線的方向上，所以必定存在一個常數μ*，有。
我們可以把它寫成更加精煉的形式。如果我們構造二元函數，上面的結論就可以表達為必定存在著常數μ*，使。
我們把構造的函數稱作拉格朗日函數，而其中的μ稱作拉格朗日乘子。
關於只有等式約束的拉格朗日函數的引入，也可以參考維基網路中的兩個變數函數的例子。
以上是一個特殊情形的分析，並且只包含了一個約束。那麼包含等式約束的一般情況，也就是問題（1）來說，我們同樣可以構造拉格朗日函數，不過由於包括多個等式約束，表達稍微不同：
。
也就是說，每一個等式約束都對應著一個拉格朗日乘子。那麼x*是最優點的必要條件就是，存在相應的拉格朗日乘子μ*，使得以下兩個式子成立：
（實際上就是原問題（1）的約束條件換了種寫法）
這兩個式子就是最優點的必要條件，當然如果函數是凸函數的話，這兩個式子也是充分條件。
現在我們的目標達到了，也就是把目標函數和一系列的等值約束融合到了一個函數（拉格朗日函數）裡面，這樣只需要解（3）和（4）這兩個式子就可以找到最優點，其優點是不言而喻的。而在下一節中我們將會討論包含不等式約束的最優化問題。
尋找最優值的下界
我們首先要引入包含不等式約束的優化問題，標准形式如下：
（1）
f(x)是目標函數，而後面分別是一系列的不等式約束和等式約束。
我們首先明確幾個概念：
可行點（可行解）：所有滿足約束的點x。
可行域：所有可行點組成的點集，記為R。正式寫出來就是：
最優點（最優解）：滿足約束（也就是處於可行域之內）並且使目標函數達到最小的點，記為x*。
最優值：如果找到了x*，p* = f(x*) 就是最優值。
明確了這些概念以後我們就接著說下面的內容了。
與上節所說的只包含等式約束的情況類似，我們定義拉格朗日函數如下：
我們來看看，這與上節的拉格朗日函數有什麼不同？多了一系列的不等式約束對應的項，所以也多了一系列的拉格朗日乘子。在這里需要強調的是，所有的λi必須是大於等於0的（也即是不等式約束對應的乘子要求大於等於0，我們記為λ≥0，意思是每個都λi≥0）。至於為什麼要這樣要求，後面自然可以看出來。
接下來我們定義一個重要的函數，我們定義拉格郎日對偶函數（the Lagrange al function）如下：
（2）
所以拉格朗日對偶函數就是把看成x的函數所找到的最小值。找到這個最小值有什麼意義呢？
我們先把結論寫下來，這個結論十分重要，是本節論述的目的：
對偶函數產生了原問題（1）最優值p*的一個下界，也就是說，對於任意的λ≥0和任意的μ來說，有：
（3）
那麼如何證明（3）呢？
這個證明步驟十分簡潔。假設x*是原問題（1）中的最優解，也就是f(x*) = p*。
最後兩行的推導是考慮到x*是在可行域R內的，所以肯定有，當然前提是λ≥0，這也就是為什麼在一開始要做這個規定的原因了。
我們如何理解這個不等式（3）呢？下面給出兩個直觀的解釋：
解釋一：線性逼近的解釋
我們首先重寫問題（1），就是把問題（1）換個更加緊湊的方式來表達，首先我們定義示性函數：
同樣我們也可以定義另外一個示性函數：
有了這兩個示性函數的幫助，現在我們可以把問題（1）重新寫成一個沒有約束的形式：
（4）
我們來看看這個優化問題（4）和問題（1）是等價的么？我們可以把（4）的後面兩大項看做是對違反約束條件的x的懲罰函數。起的作用是對違反不等式約束的x進行「無限的」懲罰，也就一旦，懲罰就等於無窮大。而起的作用是對違反等式約束的x進行懲罰，一旦，懲罰就為無窮大。這樣對（4）中目標函數的優化跟對（1）中目標函數在約束條件下的優化就是同一回事，是不是？也就是說，（1）和（4）這兩個問題是等價的問題，但是在（4）中約束被融合到目標函數中來了。
現在我們再回頭看看（2），也就是拉格朗日對偶函數，它也是個優化問題，我們對比它所優化的函數和（4）中所優化的函數，把它們重寫在一起：
（2）中的目標函數
（4）中的目標函數
可見在問題（2）和問題（4）中，我們優化的目標函數區別在於懲罰項不同，（4）中的懲罰項是無限的，就是說一旦違反約束，就施加無窮大的懲罰；而在（2）中我們的懲罰項是線性的，就是說隨著gi(x)和hi(x)的不同，懲罰項是線性變化的。所以（2）和（4）中需要優化的目標函數有很大的不同，用（2）來逼近（4）是很不準確的。但是我們可以看出，對於任意的u，任意的λ≥0和任意的μ來說都有：
（我們把λ限制為大於等於0了）
所以在任意點，（2）中的目標函數的值都是小於（4）中的目標函數的值，所以（2）中找到的最優值肯定是小於（4）中找到的最優值的。再結合前面說的（1）和（4）是等價的問題，所以不等式（3）是成立的。
解釋二：交換max和min的次序
我們首先可以看出：
為什麼會有這個結果呢？當x滿足約束的時候，也就是對所有的i來說有並且，如果我們想通過調整λ和μ讓變大怎麼辦呢？只有讓λ全部為0（注意λ只能大於等於0），這樣就消去了小於0的項，至於，無論μ怎麼變都是沒有影響的。所以當x屬於可行域的時候上式的結果是f(x)。如果x違反了約束呢？在做sup運算的時候只需要對滿足和的項對應的乘子定為+∞，而把其他的項對應的乘子設為0，就可以讓整個式子的結果變為無窮大。
所以我們可以看出來，在問題（1）中的帶約束的優化問題和直接優化是一回事，也就是說：
現在我們把inf和sup兩個運算符調換次序，顯然有：
我們重寫（2）式：
（2）
可以看出結論了，也就是λ≥0時（3）式成立：
（3）
好了，費了半天的勁我們說明了一個問題，就是不等式（3）是怎麼來的。
總結一下，不等式（3）用文字敘述就是：
如果我們把拉格朗日函數看做是x的函數，然後取下確界（注意：是在整個定義域里取下確界，而不是僅僅在可行域里取值，也就是說取下確界時對x是沒有約束的），那麼得到的結果就是原優化問題（1）的最優值的一個下界。
至於我們得到這個結果有什麼用，下節再說。
對偶問題
回憶上一節，對如下的原問題：
（1）
我們定義了拉格朗日對偶函數：
然後我們證明了：，其中p*是原問題的最優值。
也就是說我們找到了原問題最優值的一個下界。既然我們找到了一個下界，顯然我們要找到它最好的下界。什麼是最好的下界的？顯然就是所有下界當中最大的那一個。所以我們要把最大化，當然我們還要記得我們需要限制。我們把要優化的函數和約束條件正式寫下來就是：
（2）
與原問題（1）相對應，我們把上面的問題（2）稱作拉格朗日對偶問題（Lagrange al problem）。顯然，對偶問題的最優值d*就是我們可以獲得的p*的最優下界，也就是所有下界中離p*最近的一個，它們的關系是：
（3）
我們把這個不等式叫做弱對偶性質（Weak Duality）。
順其自然，我們可以引出一個重要的概念，對偶間隙，其定義為，用文字敘述就是原問題的最優值與通過拉個郎日對偶函數獲得的其最好（最大）的下界之差。由不等式（3）可以看出，對偶間隙肯定是大於等於0的。
那麼有沒有可能在某種情況下，對偶間隙消失了呢？也就是說對偶問題的最優值與原問題的最優值相等了呢？
我們將要敘述一下Slater條件：
Slater條件：
存在x滿足：
Slater條件即是說存在x，使不等式約束中的「小於等於號」要嚴格取到「小於號」。
可以證明，對於凸優化問題（關於凸優化問題，請參考維基網路），如果Slater條件滿足了，則：
這種情況稱為強對偶性質（Strong Duality）。
下面的問題是，如果對偶間隙消失了，會發生什麼有趣的現象呢？
如果對偶間隙消失了，也就是說，如果對偶問題存在著最優點λ*,μ*並且使其對應的最優值等於p*，這時會發生什麼情況呢？還記得上一節我們證明的過程么：
（4）
在對偶間隙消失的情況下，中間所有的不等號都要變成等號：
（5）
注意，（5）中的λ和μ都加了星號，表示它們是對偶問題的最優點。（5）中有兩個重要的等號，已經加了標記。
我們能得出什麼結論？
1 .我們先來看等號1：
它說明了原問題的最優點x*是使取得最小值的點。
2. 我們再來看等號2：
它說明了：
由於我們限制了每一個λi≥0，所以上式中每一項都是非正的。這樣我們又可以得出結論：
(6)
等式（6）被稱作是互補性條件，我們可以把它換種寫法：
或者寫成它的等價形式（逆否命題）：
也就是說，只要一個不為0，另一個就必為0！
互補性條件有著重要的意義。它說明了當時，x*是處於可行域的內部的，這時不等式約束並不起作用，此時；而的點肯定是可行域邊界的點（）。也就是說只有積極約束才有不為0的對偶變數。而這在支持向量機中有著重要的意義。回想在第一節我們最後的結論，支持向量機尋找最大間隔超平面可以歸結為一個優化問題：
目標函數：
限制：
那麼哪些不等式約束對應著不為0的對偶變數呢？顯然，只有當時，這個約束對應的對偶變數才可能不為0，而意味著什麼？意味著這個約束對應的樣本點xi是支持向量！也就是說：
只有支持向量才對應不為0的拉格朗日乘子！
⑸ 如何求拉格朗日對偶問題中的參數
任何優化問題的拉格朗日對偶函數，不管原問題的凸凹性，都是關於拉格朗日乘子的凹函數 為理解這個問題，首先有個結論：對於一凹函數族F:{f1,f2,f3...}，取函數f在任意一點x的函數值為inf fi(x)，即F中所有函數在這一點的值的下限，則f為凹函數。
⑹ 支持向量機（SVM）
參考Jerrylead 和 july-支持向量機通俗導論
再回憶一下邏輯回歸：Logistic回歸目的是從特徵學習出一個0/1分類模型，而 這個模型是將特徵的線性組合作為自變數 ，由於自變數的取值范圍是負無窮到正無窮。因此，使用logistic函數（或稱作sigmoid函數） 將自變數映射到(0,1)上，映射後的值被認為是屬於y=1的概率 。
中間那條線是θ T x=0，logistic回歸強調 所有點 盡可能地遠離中間那條線。學習出的結果也就中間那條線。
但是：
考慮上面3個點A、B和C。從圖中我們可以確定A是×類別的， 然而C我們是不太確定的 ，B還算能夠確定。這樣我們可以得出結論， 我們更應該關心靠近中間分割線的點，讓他們盡可能地遠離中間線，而不是在所有點上達到最優（引出了下面的函數間隔與幾何間隔） 。
我想這就是支持向量機的思路和logistic回歸的不同點：
支持向量機考慮局部（不關心已經確定遠離的點），
邏輯回歸一個考慮全局（已經遠離的點可能通過調整中間線使其能夠更加遠離，但是也可能使一部分點靠近中間線來換取另外一部分點更加遠離中間線。）
上面已經知道，θ T x=0是分類的線，在svm中，只考慮局部，只考慮θ T x的正負問題，而不用關心g（z）。因此，在這里，用w T x+b代替θ T x，並 對g(z)做一個簡化 ，將其簡單映射到類別標簽y=1和y=-1上。
這里的y取值為1和-1（在svm中，只考慮局部，只考慮θ T x的正負問題），是為了方便定義：在分類正確的情況下，函數間隔（確信度 ）的大小
比如，在分類正確的情況下，y等於1，wx+b應該為正數越大，則情況越好，是正例的確定度就越大。就如上圖的A點。y等於-1，wx+b應該為負數越大，則情況越好是負例的確信度就越大。
所以， 函數間隔越大，說明分類正確的置信度越大。函數間隔越小 ，比如上圖c點，說明越不能確定c點屬於哪一類。
可以為 別的值，只是為了方便。這一點在參考的第二個博客上也已經說明了。
由上面解釋，已知可以用y(wT x + b) 的正負性來判定（或表示）分類的正確性。
定義函數間隔如下：
也就是，這個樣本點x與超平面之間的間隔（但是現在有些不準確，所以有下面的幾何間隔）。
此時，若根據SVM的思想，最大化這個間隔，就能提高分類正確的確信度了嗎？
答案是否定的，因為，如果成比例的改變w 和b（如將它們改成2w 和2b），則函數間隔的值f(x) 卻變成了原來的2 倍（ 雖然函數值增大了，達到了目標，但是此時超平面沒有改變 ），所以只有函數間隔還遠遠不夠。
我們真正關心的，其實是「幾何上」的點到平面的距離，於是可以用幾何知識推理出來的幾何間隔。 而不是一開始人們想當然定義的函數間隔。
事實上，我們可以對法向量w 加些約束條件（ 這就是調優問題的思考了 )，從而引出真正定義點到超平面的距離——幾何間隔（geometrical margin）的概念。
又因為x 0 是超平面w T x + b=0上的點，利用向量之間的運算
再令上式乘上對應的類別y，即可得出幾何間隔
從上述函數間隔和幾何間隔的定義可以看出：幾何間隔就是函數間隔除以∥w∥，而 函數間隔實際上就是，只是人為定義的一個間隔度量，而幾何間隔才是直觀上的點到超平面的距離。
接下來就是我們的目標：尋找一個超平面， 使得離超平面比較近的點能有更大的間距。 也就是我們不考慮所有的點都必須遠離超平面，我們關心求得的超平面能夠讓所有點中離它最近的點具有最大間距。也就是找到最大的幾何間隔。
由上一小節可以知道，我們這里要找的最大間隔分類超平面中的「間隔」指的是幾何間隔。
上面兩個式子的意思是（ 注意，函數間距上面是折線，幾何間距上面是波浪線 ）：
最大化幾何間隔
約束條件是，每個樣例的函數間隔都要大於全局的那一個函數間隔（也就是所有訓練集里的最小的那個）
用函數間隔表示幾何間隔
於是得到了這個式子：
然而這個時候目標函數不是凸函數，約束條件也不是線性的，沒法直接代入優化軟體里計算。我們還要改寫。前面說到 同時擴大w和b對結果沒有影響 ，因此，我們將全局的函數間隔值定義為1。於是，上述的函數轉變成了
由於求1/||w||的最大值，相當於求||w||²的最小值，因此結果為：
因為現在的 目標函數是二次的，約束條件是線性的，所以它是一個凸二次規劃問題 。這個問題可以用現成的QP (Quadratic Programming) 5優化包進行求解。一言以蔽之：在一定的約束條件下，目標最優，損失最小。
根據前面幾個文章的話，SVM作為判別模型，它的的模型，就是 w T x i + b 。參數就是w和b。學習完參數以後，新來的樣例作為x i ，得到結果大於1，說明在超平面上面，所以是正例。反之亦然。
根據SVM的思想，SVM的初步目標函數，就是所有樣例的幾何間隔盡可能的大
至此，得到了SVM的目標函數，算是初步解決了SVM的這個問題，用優化包求解得到wb，即可得到具有最大幾何間距的超平面，提高分類每個點的確信度，分類目標完成。
接下來介紹的是手工求解w和b的方法了，一種更優的求解方法。
從上可以看出 ，就同時擴大w和b就相當於等式兩邊同時除以函數間隔 γ，而新的w和b仍然是舊的wb的函數，所以最大化仍然可以進行。
效果等價於，令函數間隔γ=1，綜上所述，零γ=1是合理的，而且也方便了原優化問題的計算 。
由拉格朗日對偶（線性可分條件下SVM的對偶演算法）引入核函數（非線性可分條件下SVM的演算法）
上一篇說到，得到了 如下的線性可分的SVM的目標函數 ，可以利用優化包進行求解。
此外，由於這個問題的特殊結構，還可以通過拉格朗日對偶性（Lagrange Duality）變換到對偶變數(al variable) 的優化問題，即通過求解與原問題等價的對偶問題（al problem）得到原始問題的最優解，這就是線性可分條件下支持向量機的對偶演算法。
引入對偶的優點：
因為 引入拉格朗日運算元可以求出極值。 （參考最優化方法的解釋）
這種極值問題怎麼求
首先，同樣定義拉格朗日公式，希望可以利用拉格朗日運算元法求得最優解，得到：
但是，出現問題了，此時加入的約束條件g已經不再等於0了，所以，此時可以調整運算元alpha變成很大很大的 值，使結果負無窮， 這顯然是不合理的。
所以，我們需要 排除在滿足條件下，也會無解的情況。
因此，我們定義下面的函數
要看這個函數有什麼優點，就要看看這個函數相比於L(ω,α,b)有什麼變化： 加了max，加了α I 大於等於零。
所以，當g和h不滿足約束時，總可以調整α i 和β i 來使thetap具最大值為正無窮。
只有當g和h滿足約束時，此時g<0，我們可以調整α i 和β i （使α i 等於0，β i 任意），得到最大值，即θ p =f(w)。
於是函數等價於這樣
於是原來的極值問題min f(w) 就等價於求min θ p 了，
即：
也就是說，最小化 θ p ，就是為了得到最小的 f(w)，而能有f(w)就說明了滿足約束條件。所以這個等價於原來的極值問題。
至此， 相比於拉格朗日公式L(ω,α,b)，現在即加入了拉格朗日運算元，又排除了純粹的拉格朗日公式中出現無窮的情況。
但是，又出現了新的問題，也就是，如果直接求解，首先面對的就是兩個參數（最裡面的是max，這個max問題有兩個參數），而且alpha也是不等式約束，再在w上求最小值，這個過程並不容易做。那麼應該怎麼辦呢？
在最優化課程里，當遇到不好解的優化問題時，可以轉化為原問題的對偶問題試試。
此處，d代表對偶。D--al
我們定義函數
θ D 將問題轉化為先求L(ω,α,b)關於 ω 的最小值（此時α和β是固定值），之後再求θ D 的最大值。 上來面對的是一個參數，相對簡單些。
相對於原問題，更換了min和max的順序，得到了它的對偶問題。
--------------------------------------------------------------------------------------------------------------
一般的更換順序的結果是MaxMin(X) <= MinMax(X)。也就是，此時有
對偶問題已經表示出來了，這個對偶問題也相對原問題好求，那麼，這兩個問題等價嗎？或者說，對偶問題的解是不是原問題的解呢？
需要用KKT條件來判斷了。
對於拉格朗日運算元的深入理解可以看看《最優化方法》，講義的最後一頁。
含有不等式約束的問題，常常 用KKT條件求得候選最優解
對於一般化的拉格朗日公式：
最優值 w 必須滿足以下三個條件：
----------1、L對 w 求導為零
----------2、h(w)=0
----------3、α i g i =0 ，i = 1，...，k
注意此時
第三個條件表明了KKT的思想：極值會在可行域邊界取得。 ----解釋：
-----對於一個特定的自變數w1，當自變數w1在 第 i 個 可行域邊界（g i (w1)=0）時，說明此時這個約束是起到了作用的。 這個約束是w1被g i 約束了。此時只能到g i 的平面上（即邊界），再多就出界了。。。 而對於最優解來說，就是f(w)達到最優，所以L中，除了f(w)部分，其餘應該都等於0，所以此時α>0(或許等於零也可以？疑問）
----而此時，w1在其他的約束條件g 非i 下，有g 非i (w1)<0），說明W1可以隨意些，說明此時這個約束並沒有起到作用，但是作為最優解，為了 除了f(w)部分，其餘應該都等於0 ，所以其系數α應該等於零。
----------------------------------------------------------------------------------------
注意：這個是傳統最優化問題的一般式，這個問題有k個不等式約束方程，所有的點都要滿足這k個不等式約束。 。假設有一百個樣本點，只有有三個極值N1，N2，N3，那麼說明其餘97個點帶入這k個方程中去都會小於零。 另外對於這三個極值點，可能會有g i (N1) = 0,除了第i個g以外，g(N1)都小於0 。然後對於極值N2，g j (N2)=0，除了第j個約束以外，其餘的g(N2)都小於0。
而本節一開始討論的問題，只有一個約束方程（因為參數只有w和b）即：y（w T x+b）>=1，所有的點（一共m個）都要滿足這個約束方程。 而關於為什麼非支持向量的系數alpha會等於零呢？也就是相當於前面的，k=1（有k個約束條件）的情況下，m個樣本點中，非支持向量的約束g<0，為了最優解，除了f(w)應該都等於零，所以alpha應該等於零。
另外可以參考這段話：
即，若d* = p* <==> x * 滿足KKT條件
由上面那句話可以知道，
折騰這么長時間，也就是為了說明，已經知道原問題
是凸優化問題，所以，只要對偶問題的自變數w滿足了KKT條件，那麼它就是對偶問題的最優解w * ，同時也是原問題的最優解了。
所以，由上可知，只要解出了2.1.3中的問題的參數w和b，也就是原問題的解了。
重新回到SVM的優化問題（其中每個約束式實際就是一個訓練樣本）：
我們將約束條件改寫為拉格朗日的形式：
由KKT條件可知，只有當函數間隔是1（g=0）的時候，α i >0。此時，這個樣例 w i 在約束平面上受到約束 。對於其它的不在線上的樣例點（g<0），極值不會在其范圍內去的，所以這些樣例點前面的系數α i =0.
實線是最大間隔超平面，假設×號的是正例，圓圈的是負例。在虛線上的點就是函數間隔是1的點，他們前面的系數α i >0， 這三個點被稱作 支持向量。
由上面問題，構造拉格朗日函數如下（沒有等式約束，所以沒有β）：
————————————————————————————————
下面我們按照對偶問題的求解步驟來一步步進行，由2.1.3可知，對偶問題的形式為：
首先求解L的最小值（最裡面的先求），此時αi是固定的，L的最小值只與w和b有關。對w和b分別求偏導數。
得到
將上式帶回到拉格朗日函數中得到，此時得到的是該函數的最小值（目標函數是凸函數）， 即裡面的min L已經求出，接下來就是求max了
代入後，化簡過程如下：
最後得到
由於最後一項是0，因此簡化為
這里，上式中左右邊的向量內積，用方括弧表示。
到這一步，拉格朗日函數只包含了一個變數α i 。接著進行下一步 ，最大化的過程，求得α i 。
假設求得了α i 就能根據求導得到的結果
求得w，然後就能得到b。
b 就是 距離超平面最近的正的函數間隔要等於離超平面最近的負的函數間隔。 （其實，由前面的那個x和圈的圖，可以認為b就是截距，這個截距b等於上下兩條虛線的截距的平均值。）
注意，這里的w，b，alpha都是 向量，都是m維的向量
至於這里的α怎麼求得，即上面的最大化問題怎麼求解，將留給下一篇中的SMO演算法來闡明。
也就是說，手動解的話，還是需要利用SMO演算法，求得α才行。
————————————————————————————————
這里考慮另外一個問題，由於前面求解中得到
用α i 代替w帶入判別模型w T x+b，得到：
也就是說， 利用判別模型對新來樣本進行判別時 ，以前新來的要分類的樣本首先根據w和b做一次線性運算，然後看求的結果是大於1還是小於1來判斷正例還是負例。大於1，說明在超平面的上面，說明是正例。同理，小於1說明在超平面的下面，說明是負例。
約束條件是wx+b-1小於等於零，所以判斷就是wx+b與1進行大小比較
現在有了alpha，不需要求出w （那b呢，b怎麼求呢，前面已經解釋，b是由離超平面最近的間隔和負的函數間隔相等。。。得到的。所以，將新來的樣本與訓練數據中 支持向量 做內積以後，再確定最大的正數函數間隔以及最小的負數函數間隔，即可。）
就沖上面這段話，支持向量的系數alpha，也不能等於0。
另外，那有人會說，與前面所有的樣本都做運算是不是太耗時了？其實不然，我們從KKT條件中得到，只有支持向量的α i >0 （不等於零）其他情況α i 是等於零的。 比如，像前面那個x和圈的圖，新來的樣本只需要和三個支持向量做運算即可 。
由此可以看到，求出α i 以後，只需要利用支持向量，就可以來判斷新來的樣例是正例還是負例了。也許這也是是為什麼叫支持向量機吧。
上面這個公式，為下面要提到的核函數（kernel）做了很好的鋪墊。
下面，先把沒求得的alpha放一放，趁著剛剛得到的這個公式的熱乎勁，再去看看核函數。
⑺ 一文理解拉格朗日對偶和KKT條件
目標函數: , 引入Lagrange運算元:
目標函數:
約束條件:
根據約束條件和目標函數的類型分為3類:
KKT條件指在滿足某些規則條件下, 非線性規劃 問題能有最優解的 充要條件 , 是廣義拉格朗日乘數的重要成果
一般優化問題(含等式和不等式約束約束):
引入Lagrange運算元 :
KKT條件指上述問題的最優點 必須滿足:
(1) 約束條件滿足:
(2)
即,
最優點 處, 必須是 和 的 線性組合
引入拉格朗日運算元可以求出極值的原因 :
(3) 且
不等式約束一直是優化問題中的難題，求解對偶問題可以將支持向量機原問題約束中的不等式約束轉化為等式約束；
支持向量機中用到了高維映射，但是映射函數的具體形式幾乎完全不可確定，而求解對偶問題之後，可以使用核函數來解決這個問題。
並不一定要用拉格朗日對偶。要注意用拉格朗日對偶並沒有改變最優解，而是改變了演算法復雜度：
在原問題下，求解演算法的復雜度與樣本維度（等於權值w的維度）有關；
而在對偶問題下，求解演算法的復雜度與樣本數量（等於拉格朗日運算元a的數量）有關。
因此，
支持向量機實現非線性的方法的數學本質是升維，升維升到無窮維則無法表達w, 所以還是使用拉格朗日對偶方法更好一點。准確的說，可以用一些優化演算法直接求最小間距，但是，升維的時候核要是正定的，且升維可數，而且不是很大的時候可以用。
任意一個帶約束的優化均可寫成:
將上述帶約束的優化問題轉化為無約束優化問題, 定義拉格朗日(Lagrangian)函數如下:
最大化Lagrangian, 令
z(x)滿足原始約束條件的x, 其值等於 :
滿足初始約束, 則 , 拉格朗日函數第三項被消去:
又因為 , 所以 的最大值在 處取得.
所以原始帶約束優化問題等價於以下無約束優化問題:
等價於:
上述問題稱為 primal problem
總結:
al problem 只是將primal proble調換了min和max位置:
注意上式和 並不等價.
令:
上式中 為拉格朗日對偶函數(Lagrange al function), 是primal function的一個下界.
即, 若將primal proble的最小值記為 , 則對於所有的 , 有:
證明:
對所有滿足約束條件的x, 總有:
因此
假設 在 處取得極值, 則
代入上式:
於是
這樣, 的上界是 ,於是:
是primal problem的 最大下界 !
記al problem 的最優值為 , 得到:
該性質稱為weak ality, 對所有的優化問題都成立.
此外,
稱為ality gap.
基於weak ality的重要結論:
當
成立時,稱為strong ality.
嚴格滿足約束條件的點x, 指 嚴格到 , 即存在x滿足:
原始問題是convex且滿足slater條件,則strong ality成立:
特例: 對某些 非convex optimization,strong ality也成立
條件(2)中若 必有 , 反之, 若 可得 , 此條件在SVM中用來證明非支持向量 對應的系數
complementary slacknes 加上其他約束條件即為KKT條件:
通過al problem可求primal problem的解:
⑻ 為什麼支持向量機要用拉格朗日對偶演算法來解最大化間隔問題
首先，對偶理論和方法是最優化的基本工具，也是整數規劃中內容最豐富、應用最廣泛的鬆弛方法之一。在簡單的實際問題中，可以利用拉格朗日鬆弛和對偶產生線性整數規劃的界，從而用分支定界法求解規劃問題的最優解。
⑼ 支持向量機（SVM）
支持向量機（support vector machine），故一般簡稱SVM，通俗來講，它是一種二分類模型，其基本模型定義為特徵空間上的間隔最大的線性分類器，這族分類器的特點是他們能夠同時最小化經驗誤差與最大化幾何邊緣區，因此支持向量機也被稱為最大邊緣區分類器。其學習策略便是間隔最大化，最終可轉化為一個凸二次規劃問題的求解。SVM在很多諸如文本分類，圖像分類，生物序列分析和生物數據挖掘，手寫字元識別等領域有很多的應用。
支持向量機將向量映射到一個更高維的空間里，在這個空間里建立有一個最大間隔超平面。在分開數據的超平面的兩邊建有兩個互相平行的超平面，分隔超平面使兩個平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。
假設給定一些分屬於兩類的2維點，這些點可以通過直線分割， 我們要找到一條最優的分割線，如何來界定一個超平面是不是最優的呢?
如圖：
在上面的圖中，a和b都可以作為分類超平面，但最優超平面只有一個，最優分類平面使間隔最大化。 那是不是某條直線比其他的更加合適呢? 我們可以憑直覺來定義一條評價直線好壞的標准:
距離樣本太近的直線不是最優的，因為這樣的直線對雜訊敏感度高，泛化性較差。 因此我們的目標是找到一條直線（圖中的最優超平面），離所有點的距離最遠。 由此， SVM演算法的實質是找出一個能夠將某個值最大化的超平面，這個值就是超平面離所有訓練樣本的最小距離。這個最小距離用SVM術語來說叫做間隔(margin) 。
描述：給定一些數據點，它們分別屬於兩個不同的類，現在要找到一個線性分類器把這些數據分成兩類。如果用x表示數據點，用y表示類別（y可以取1或者-1，分別代表兩個不同的類），一個線性分類器的學習目標便是要在n維的數據空間中找到一個超平面（hyper plane），這個超平面的方程可以表示為（ wT中的T代表轉置）：
例如：現在有一個二維平面，平面上有兩種不同的數據，分別用圈和叉表示。由於這些數據是線性可分的，所以可以用一條直線將這兩類數據分開，這條直線就相當於一個超平面，超平面一邊的數據點所對應的y全是-1 ，另一邊所對應的y全是1。
我們令分類函數為：
當f(x) 等於0的時候，x便是位於超平面上的點，而f(x)大於0的點對應 y=1 的數據點，f(x)小於0的點對應y=-1的點，如下圖所示：
一個點距離超平面的遠近可以表示分類預測的確信或准確程度，如何確定這個超平面呢？從直觀上而言，這個超平面應該是最適合分開兩類數據的直線。而判定「最適合」的標准就是這條直線離直線兩邊的數據的間隔最大。所以，得尋找有著最大間隔的超平面。
補充知識點： 點到平面的距離
支持向量機學習的基本想法是求解能夠正確劃分訓練數據集並且幾何間隔最大的分離超平面.。對線性可分的訓練數據集而言，線性可分分離超平面有無窮多個(等價於感知機)，但是幾何間隔最大的分離超平面是唯一的。這里的間隔最大化又稱為硬間隔最大化。
間隔最大化的直觀解釋是:對訓練數據集找到幾何間隔最大的超平面意味著以充分大的確信度對訓練數據進行分類。也就是說，不僅將正負實例點分開，而且對最難分的實例點(離超平面最近的點)也有足夠大的確信度將它們分開。這樣的超平面應該對未知的新實例有很好的分類預測能力。
按照我們前面的分析，對一個數據點進行分類， 當它的margin越大的時候，分類的confidence越大。 對於一個包含n個點的數據集，我們可以很自然地定義它的margin為所有這n個點的margin值中最小的那個。於是，為了使得分類的confidence高，我們希望所選擇的超平面hyper plane能夠最大化這個margin值。讓所選擇的超平面能夠最大化這個「間隔」值，這個間隔就是下圖中的Gap的一半：
為什麼用幾何間隔求最大的分離超平面而不用函數間隔？
例題：
我們構造了約束最優化問題，就是下面這個：
此外，由於這個問題的特殊結構，還可以通過拉格朗日對偶性（Lagrange Duality）變換到對偶變數 (al variable) 的優化問題，即通過求解與原問題等價的對偶問題（al problem）得到原始問題的最優解，這就是線性可分條件下支持向量機的對偶演算法，這樣做的優點在於：一者對偶問題往往更容易求解；二者可以自然的引入核函數，進而推廣到非線性分類問題。
補充知識點： 拉格朗日乘子法學習
拉格朗日KKT條件
KKT條件介紹
拉格朗日對偶
通過給每一個約束條件加上一個拉格朗日乘子（Lagrange multiplier）α，定義拉格朗日函數（通過拉格朗日函數將約束條件融合到目標函數里去，從而只用一個函數表達式便能清楚的表達出我們的問題）：
求解這個式子的過程需要拉格朗日對偶性的相關知識。
例題：
接下來談談線性不可分的情況，因為 線性可分這種假設實在是太有局限性 了。下圖就是一個典型的線性不可分的分類圖，我們沒有辦法用一條直線去將其分成兩個區域，每個區域只包含一種顏色的點。
要想在這種情況下的分類器，有兩種方式， 一種是用曲線 去將其完全分開，曲線就是一種 非線性 的情況，跟之後將談到的 核函數 有一定的關系：
另外一種還是用直線，不過不用去保證可分性 ，就是包容那些分錯的情況，不過我們得加入懲罰函數，使得點分錯的情況越合理越好。其實在很多時候，不是在訓練的時候分類函數越完美越好，因為訓練函數中有些數據本來就是雜訊，可能就是在人工加上分類標簽的時候加錯了，如果我們在訓練（學習）的時候把這些錯誤的點學習到了，那麼模型在下次碰到這些錯誤情況的時候就難免出錯了。這種學習的時候學到了「雜訊」的過程就是一個過擬合（over-fitting），這在機器學習中是一個大忌。
我們可以為分錯的點加上一點懲罰，對一個分錯的點的 懲罰函數 就是 這個點到其正確位置的距離：
對於線性不可分的情況，我們可以用核函數讓空間從原本的線性空間變成一個更高維的空間 ， 在這個高維的線性空間下，再用一個超平面進行劃分 。 這兒舉個例子，來理解一下如何利用空間的維度變得更高來幫助我們分類的：
上圖是一個線性不可分的圖，當我們把這兩個類似於橢圓形的點映射到一個高維空間後，映射函數為：
用這個函數可以將上圖的平面中的點映射到一個三維空間（z1,z2,z3)，並且對映射後的坐標加以旋轉之後就可以得到一個線性可分的點集了。
形象說明：例如世界上本來沒有兩個完全一樣的物體，對於所有的兩個物體，我們可以通過增加維度來讓他們最終有所區別，比如說兩本書，從(顏色，內容)兩個維度來說，可能是一樣的，我們可以加上作者這個維度，是在不行我們還可以加入頁碼，可以加入擁有者，可以加入購買地點，可以加入筆記內容等等。當維度增加到無限維的時候，一定可以讓任意的兩個物體可分了。
核函數定義：
核技巧在支持向量機中的應用：
常用核函數：
非線性支持向量機學習演算法：
支持向量機的學習問題可以形式化為求解凸二次規劃問題。這樣的凸二次規劃問題具有全局最優解，並且有許多最優化演算法可以用於這一一問題的求解。但是當訓練樣本容量很大時，這些演算法往往變得非常低效，以致無法使用。所以，如何高效地實現支持向量機學習就成為一一個重要的問題。目前人們已提出許多快速實現演算法.本節講述其中的序列最小最優化(sequential minimal optimization, SMO)演算法。
上述問題是要求解N個參數(α1,α2,α3,...,αN)，其他參數均為已知，序列最小最優化演算法(SMO)可以高效的求解上述SVM問題，它把原始求解N個參數二次規劃問題分解成很多個子二次規劃問題分別求解，每個子問題只需要求解2個參數，方法類似於坐標上升，節省時間成本和降低了內存需求。每次啟發式選擇兩個變數進行優化，不斷循環，直到達到函數最優值。
整個SMO演算法包括兩部分，求解兩個變數的 二次規劃 問題和選擇這兩個變數的 啟發式 方法。
上面求得的(α1)new和(α2)new是在η>0的情況下求得的：
當時為了推導公式我們直接默認它是大於0了，現在我們需要重新審視這一項（η）。這一項是原來關於的二次項的系數。我們可以分下面三種情況討論：
（1）當η>0時 ：這個二次函數開口向上，所以要求這個二次函數的最小值，如果說極值點不在計算出的可行域的范圍內，就要根據這個極值點和可行域邊界值的關系來得到取最小值的地方：
①如果這個極值點在可行域左邊，那麼我們可以得到這個可行域內二次函數一定在單增，所以此時L應該是那個取最小值的地方。就如大括弧的第三種情況。
②如果這個極值點在可行域右邊，那麼此時可行域內一定單減，所以此時H就是那個取最小值的地方，就是大括弧里的第一種情況。
（2）當η=0時： 這個二次函數就變成了一個一次函數，那麼不管這個一次函數的單調性怎樣，最小值一定是在邊界處取到。所以到時候計算可行域的兩個邊界的值，看哪個小就用哪個。
（3）當η<0時: 這個二次函數開口向下，那麼此時怎麼得到取最小值的點呢？很容易就能想到：最小值也是在可行域的邊界處取到。很容易理解，此時開口向下，當極值點在區間內時，最小值只能在端點處取，因為極值點處是最大的。而當極值點在區間外時，區間內一定是單調的，此時最小值也只能在端點處取。通過計算比較邊界處的目標函數值，哪個小取哪個。
通過以上判斷求出(α2)new以後，再根據公式求出(α1)new，然後帶入目標函數（1）中。即如下過程：
上述分析是在從N個變數中已經選出兩個變數進行優化的方法，下面分析如何高效地選擇兩個變數進行優化，使得目標函數下降的最快。
⑽ 拉格朗日函數及其對偶性
拉格朗日函數主要用來求解在約束條件下的最優化問題，
稱此約束最優化問題為原始最優化問題。
這里， 是拉格朗日乘子， .考慮 x 的函數：
這里，下標 表示原始問題。
假設給定某個 ,如果 違反原始問題的約束條件
所以當都滿足約束條件時， 可以得到所有的 都為 0。另一項恆為 0。此時
再最小化
與原始問題相同 。
定義原始問題的最優值
又叫做廣義拉格朗日函數的極小極大問題。
定義
之前的原始問題，第一步是把 當做常數，求 。現在的對偶問題，第一步是把 當做常數求
在考慮極大化
這又叫做， 廣義拉格朗日函數的極大極小問題
定義最優值
這才是關鍵！！！ 如果求解不一樣，那對偶函數有什麼用！
在 最大熵模型 中，正是因為對偶問題和原始問題的解一樣，才能互相轉換。
現在來探討這個 對偶問題和原始問題的解一樣 的條件
詳見這篇文章