上一節我學習了SVM的核函數內容，下面繼續對SVM進行證明，具體的參考連結都在第一篇文章中。
話休絮煩，要證明一個東西先要弄清楚它的根基在哪裡，即構成它的基礎是哪些理論。OK，以下內容基本上都是上文沒有學習到的一些定理的證明，包括其背後的邏輯，來源背景等東西。 同樣，在學習這些之前，我們再複習一下SVM，這裡使用 http://staff.ustc.edu.cn/~ketang/PPT/PRLec5.pdf的PPT來學習。熱身：SVM的整理 這裡直接借用別人的PPT粘貼在這裡，讓自己再梳理一遍SVM。熱身1. Hard Margin SVM
熱身2. Soft Margin SVM
熱身3. LS-SVM1. 線性學習器1.1 感知機算法 這個感知器算法是在1956年提出的，年代久遠，依然影響著當今，當然，可以肯定的是，此算法亦非最優，後續會有更詳盡闡述。不過，有一點，你必須清楚，這個算法是為了幹什麼的：不斷的訓練試錯以期尋找一個合適的超平面。 下面，舉個例子。如下圖所示，憑我們的直覺可以看出，圖中紅線是最優超平面，藍線則是根據感知機算法在不斷的訓練中，最終，若藍線能通過不斷的訓練移動到紅線位置上，則代表訓練成功。
既然需要通過不斷的訓練以讓藍線最終成為最優分類超平面，那麼到底需要訓練多少次呢？ Novikoff 定理告訴我們當間隔是正的時候感知機算法會在有限次數的迭代中收斂，也就是說 Novikoff 定理證明了感知機算法的收斂性，即能得到一個界，不至於無窮循環下去。Novikoff 定理：如果分類超平面存在，僅需要在序列 S 上迭代幾次，在界為 （2R / γ）2 的錯誤次數下就可以找到分類超平面，算法停止。 這裡的 R = max1<=i<=l||Xi|| ，γ 為擴充間隔。根據誤分次數公式可知，迭代次數與對應於擴充（包括偏置）權重的訓練集的間隔有關。 順便再解釋下這個所謂的擴充間隔 γ ， γ 即為樣本到分類間隔的距離，即從 γ 引出的最大分類間隔。之前我們推導過的內容，如下：
在給出幾何間隔的定義之前，咱們首先來看下，如上圖所示，對於一個點 x，令其垂直投影到超平面上的對應的為 x0，由於 w 是垂直於超平面的一個向量， γ 為樣本 x 到分類間隔的距離，我們有：
同時有一點值得注意：感知機算法雖然可以通過簡單迭代對線性可分數據生成正確分類的超平面，但不是最優效果，那怎麼才能得到最優效果呢，就是前面博文說的尋找最大分類間隔超平面。此外，Novikoff定理的證明請參考：https://link.zhihu.com/?target=http%3A//www.cs.columbia.edu/~mcollins/courses/6998-2012/notes/perc.converge.pdf
2. 非線性學習器2.1 Mercer定理 Mercer定理：如果函數 K 是 Rn *Rn - R 上的映射（也就是從兩個 n 維向量映射到實數域）。那麼如果K是一個有效核函數（也稱為 Mercer 核函數），那麼若且唯若對於訓練樣例 { x(1), x(2), ... x(m)}，其相應的核函數矩陣是對稱半正定的。 Mercer定理表明為了證明K是有效的核函數，那麼我們不用去尋找 Φ ，而只需要在訓練集上求出各個 Kij，然後判斷矩陣K是否是半正定（使用左上角主子式大於等於零等方法）即可。 要理解這個 Mercer定理，先要了解什麼是半正定矩陣，要了解什麼是半正定矩陣，先得知道什麼是正定矩陣（矩陣理論博大精深，關於矩陣推薦一本書《矩陣分析與應用》），然後關於Mercer定理的證明參考：https://link.zhihu.com/?target=http%3A//ftp136343.host106.web522.com/a/biancheng/matlab/2013/0120/648.html 其實，核函數在SVM的分類效果中起到了重要的作用，下面連結有個 tutorial可以看看：https://link.zhihu.com/?target=https%3A//people.eecs.berkeley.edu/~bartlett/courses/281b-sp08/7.pdf2.2 正定矩陣 在百度百科，正定矩陣的定義如下：在線性代數裡，正定矩陣（positive definite materix）有時會簡稱為正定陣。在線性代數中，正定矩陣的性質類似於複數中的正實數。與正定矩陣相對應的線性算子是對稱的正定雙線性形式。廣義的定義：設 M 為 n 階方陣，如果對任何非零向量 z，都有 zTMz > 0，其中 zT 表示 z 的轉置，就稱 M 為正定矩陣。狹義的定義：一個 n 階的實對稱矩陣 M 是正定的條件是若且唯若對所有的非零實係數向量 z，都有 zTMz > 0，其中 zT 表示 z 的轉置。2，實對稱矩陣 A 正定若且唯若 A 與單位矩陣合同3，若 A 是正定矩陣，則 A 的逆矩陣也是正定矩陣3. 損失函數 之前提到過「支持向量機（SVM）是 90 年代中期發展起來的基於統計學習理論的一種機器學習方法，通過尋找結構化風險最小來提高學習機泛化能力，實現經驗風險和置信範圍的最小化，從而達到在統計樣本量較少的情況下，亦能獲得良好統計規律的目的。」但初次看到的人可能不了解什麼是結構化風險，什麼又是經驗風險。要了解這兩個所謂的「風險」，還得從監督學習說起。 監督學習實際上就是一個經驗風險或者結構風險函數的最優化問題。風險函數度量平均意義下模型預測的好壞，模型每一次預測的好壞用損失函數來度量。它從假設空間 F 中選擇模型 f 作為決策函數，對於給定的輸入 X，由 f(x) 給出相應的輸出 Y，這個輸出的預測值 f(X)與真實值 Y 可能一致也可能不一致，用一個損失函數來度量預測錯誤的程度。損失函數記為 L(Y, f(X))。 常用損失函數有以下幾種（摘抄於《統計學習方法》）：
模型 f(X) 關於訓練數據集的平均損失稱為經驗風險，如下：
關於如何選擇模型，監督學習有兩種策略：經驗風險最小化和結構風險最小化。 經驗風險最小化的策略認為，經驗風險最小的模型就是最優的模型，則按照經驗風險最小化求最優模型就是求解如下的最優化問題：
當樣本容量很小時，經驗風險最小化的策略容易產生過擬合的現象。結構風險最小化可以防止過擬合。結構風險是在經驗風險的基礎上加上表示模型複雜度的正則化項或懲罰項，結構風險定義如下：
其中 J(f) 為模型的複雜度，模型 f 越複雜，J(f) 值就越大，模型越簡單，J(f) 值就越小，也就是說J(f)是對複雜模型的乘法。λ>=0 是係數，用以衡量經驗風險和模型複雜度。結構風險最小化的策略認為結構風險最小的模型是最優的模型，所以求最優的模型就是求解下面的最優化問題： 這樣，簡單學習問題就變成了經驗風險或結構化風險函數的最優化問題。如上式最優化問題的轉換。 這樣一來，SVM就有第二種理解，即最優化+損失最小。如網友所言：「可以從損失函數和優化算法角度看SVM，Boosting，LR等算法，可能會有不同收穫」。 關於損失函數：可以看看張潼的這篇《Statistical behavior and consistency of classification methods based on convex risk minimization》。各種算法中常用的損失函數基本都具有fisher一致性，優化這些損失函數得到的分類器可以看作是後驗概率的「代理」。此外，張潼還有另外一篇論文《Statistical analysis of some multi-category large margin classification methods》，在多分類情況下margin loss的分析，這兩篇對Boosting和SVM使用的損失函數分析的很透徹。 關於統計學習方法的問題，可以參考：https://link.zhihu.com/?target=https%3A//people.eecs.berkeley.edu/~bartlett/courses/281b-sp08/7.pdf4. 最小二乘法4.1 什麼是最小二乘法？ 下面引用《正態分布的前世今生》裡的內容稍微簡單闡述一下。 我們口頭經常經常說：一般來說，平均來說。如平均來說，不吸菸的健康優於吸菸者，之所有要加「平均」 二字，是因為凡是皆有例外，總存在某個特別的人他吸菸但由於經常鍛鍊所以他的健康狀況可能會優於他身邊不吸菸的盆友。而最小二乘的一個最簡單例子便是算術平均。 最小二乘法（又稱最小平方法）是一種數學優化技術。它通過最小化誤差的平方和尋找數據的最佳函數匹配。利用最小二乘法可以簡便的求得未知的數據，並使得這些求得的數據與實際數據之間誤差的平方和為最小。用函數表示為：
使誤差（所謂誤差，當然是觀察值與實際真實值的差量）平方和達到最小以尋求估計值的方法，就叫做最小二乘法，用最小二乘法得到的估計，叫做最小二乘估計。當然，取平方和作為目標函數只是眾多可取的方法之一。
有效的最小二乘法是勒讓得在1805年發表的，基本思想就是認為測量中有誤差，所以所有方程的累積誤差為：
最小二乘的誤差平方和最小，並在各個方程的誤差之間建立了一種平衡，從而防止某個極端誤差取得支配地位。計算中只需要求偏導後求解線性方程組，計算過程明確便捷
對於最後一點，從統計學的角度來看是很重要的一個性質。推理如下：假設真值為 Θ ，x1,xn 為 n 次測量值，每次測量的誤差為 ei = xi - Θ，按最小二乘法，誤差累積為：
求解 Θ 使 L(Θ) 達到最小，正好是算術平均 xhat，其公式如下：
由於算術平均是一個歷經考驗的方法，而以上的推理說明，算術平均是最小二乘的一個特例，所以從另外一個角度說明了最小二乘方法的優良性，使我們對最小二乘法更加有信息。 最小二乘法發布之後很快得到了大家的認可接受，並迅速的在數據分析實踐中被廣泛使用。不過歷史上又有人把最小二乘法的發明歸功於高斯，這又是怎麼一回事呢？高斯在 1809 年也發表了最小二乘法，並且聲稱自己已經使用了這個方法多年。高斯發明了小行星定位的數學方法，並在數據分析中使用最小二乘方法進行計算，準確的預測了穀神星的位置。 說了這麼多，貌似與SVM沒啥關係，但是別著急，請繼續聽，本質上說，最小二乘法即是一種參數估計方法，說到參數估計，咱們從一元線性模型說起。4.2 最小二乘法的解法 什麼是一元線性模型呢？我們引用（https://link.zhihu.com/?target=https%3A//blog.csdn.net/qll125596718/article/details/8248249）的內容，先來梳理一下幾個基本的概念：監督學習中，如果預測的變量是離散的，我們稱其為分類（如決策樹，支持向量機等），如果預測的變量是連續的，我們稱其為回歸。回歸分析中，如果只包括一個自變量和一個因變量，且二者的關係可用一條直線近似表示，這種回歸分析稱為一元線性回歸分析。如果回歸分析中包括兩個或兩個以上的自變量，且因變量和自變量之間是線性關係，則稱為多元線性回歸分析。對於二維空間線性是一條直線；對於三維空間線性是一個平面，對於多維空間線性是一個超平面。 對於一元線性回歸模型，假設從總體中獲取了 n 組觀察值（X1， Y1），（X2， Y2），...（Xn， Yn）。對於平面中的這 n 個點，可以使用無數條曲線來擬合。要求樣本回歸函數儘可能好的擬合這組值。綜合起來看，這條直線處於樣本數據的中心位置最合理。 選擇最佳擬合曲線的標準可以確定為：使總的擬合誤差（即總殘差）達到最小，有以下三個標準可以選擇：1，用「殘差和最小」確定直線位置是一個途徑。但是很快發現計算「殘差和」 存在相互抵消的問題。2，用「殘差絕對值和最小」確定直線位置也是一個途徑。但絕對值的計算比較麻煩。3，最小二乘法的原則是以「殘差平方和最小」 確定直線位置。用最小二乘法除了計算比較方便外，得到的估計量還具有優良特性。這種方法對異常值非常敏感。 最常用的是普通最小二乘法（Ordinary Least Square, OLS ）：所選擇的回歸模型應該使所有觀察值的殘差平方和達到最小，即採用平方損失函數。
則通過Q最小確定這條直線，即確定 β0hat, β1hat， β0hat, β1hat為變量，把它們看做是 Q 的函數，就變成了一個求極值的問題，可以通過求導數得到。
根據數學知識我們知道，函數的極值點為偏導為 0 的點，解得：
這就是最小二乘法的解法，就是求得平方損失函數的極值點。自此，我們可以看到求解最小二乘法和求解SVM是何等相似，尤其是定義損失函數，而後通過偏導求極值。5. SMO算法 無論Hard Margin 或 Soft Margin SVM，我們均給出了SVM的對偶問題，但並沒有說明對偶問題怎麼求解。由於矩陣Q的規模和樣本數相等，當訓練樣本數很大的時候，這個矩陣的規模很大，求解二次規劃問題的經典算法會遇到性能問題，也就是說同時求解 n 個拉格朗日乘子涉及很多次迭代，計算開銷太大，所以一般採用 Sequential Minimal Optimization（SMO）算法。 SMO算法的基本思想：每次只更新兩個拉格朗日乘子，迭代獲得最終解。 上文中，我們提到了求解對偶問題的序列最小最優化 SMO 算法，但並未提到其具體解法。首先看下最後懸而未決的問題：
1998年，Microsoft Research 的John C. Platt 在論文《Sequential Minimal Optimization：A Fast Alogrithm for Training Support Vector Machines》中提出針對上述問題的解法：SMO算法，它很快便成為最快的二次規劃優化算法，特別是針對線性SVM和數據稀疏時性能更優。這個算法的思路是每次在優化變量中挑出兩個分量進行優化，而讓其他分量固定，這樣才能保證滿足等式約束條件，這是一種分治法的思想。5.1 SMO算法的推導
註：這個 u 與我們之前定義的 f(x) 實質上是一樣的。
接著，重新定義下我們原始的優化問題，權當重新回顧，如下：
註：這裡得到的 min 函數與我們之前的 max 函數實質上也是一樣，因為把符號變下，即由 min 轉換為 max 的問題，且 yi也與之前的 y(i) 等價，yj 亦如此。
下面要解決的問題是：在 αi = { α1, α2, α3,., αn} 上求上述目標函數的最小值。為了求解這些乘子，每次從中任意抽取兩個乘子 α1 和 α2，然後固定 α1 和 α2 以外的乘子 {α3, α4,....αn}，使得目標函數只是關於 α1 和 α2 的函數。這樣，不斷的從一堆乘子中任意抽取兩個求解，不斷地迭代求解子問題，最終達到求解原問題的目的。 （注意：下面均使用兩個相同的表達式，是參考了兩個方法，並且這兩個方法均易於理解，可以說我先看第一個公式的文章，然後偶爾有次看到第二個公式的文章，發現也很好理解，所以粘貼在這裡，特地說明） 我們首先給出對於這兩個常量的優化問題（稱為子問題）的求解方法。假設選取的兩個分量為 αi, αj，其他分量都固定（即當做常數）。由於：
其中C是一個常數，前面的二次項很容易計算出來，一次項要複雜一些，並且：
這裡的變量 α* 為變量 a 在上一輪迭代後的值。上面的目標函數是一個兩變量的二次函數，我們可以直接給出最小值的解析解（公式解）。 為了解決這個子問題，首要問題便是每次如何選取 α1 和 α2。實際上，其中一個乘子是違反 KKT條件最嚴重的，另外一個乘子則由另一個約束條件選取。 根據KKT條件可以得到目標函數中 αi 取值的意義：
1，對於第一種情況，表明 αi 是正常分類，在間隔邊界內部（我們知道正確分類的點 yi * f(xi) >= 0）2，對於第二種情況，表明了 αi 是支持向量，在間隔邊界上3，對於第三種情況，表明了 αi 是在兩條間隔邊界之間 而最優解需要滿足KKT 條件，即上述三個條件都得滿足，以下幾種情況出現將會出現不滿足：1，yiui <=1，但是 αi < C 則不是不滿足的，而原本 αi = C2，yiui >=1，但是 αi > C 則不是不滿足的，而原本 αi = C3，yiui =1，但是 αi = 0 或者 αi = C 則不是不滿足的，而原本 0 < αi < C 也就是說，如果存在不滿足 KKT 條件的 αi ，那麼需要更新這些 αi ，這是第一個約束條件。此外，更新的同時還要受到第二個約束條件的限制，即：
因此，如果假設選擇的兩個乘子 α1 和 α2 ，他們在更新之前分別是 α1old 和 α2old，更新之後分別是 α1new 和 α2new，那麼更新前後的值需要滿足以下等式才能保證和為 0 的約束：
其中，ξ 是常數，（上面兩個式子都一樣，只不過第二個更容易理解）。 兩個因子不好同時求解，所以可選求第二個乘子 α2 的解（α2new），得到 α2 的解（α2new）之後，再利用 α2 的解（α2new）表示 α1 的解（α1new）. 為了求解 α2 的解（α2new），得先確定 α2new 的取值範圍。假設它的上下邊界分別為 H 和 L，那麼有：
接下來，綜合下面兩個約束條件，求解 α2new 的取值範圍：
由於 yi, yj（也可以說為 y1 y2）的取值只能為 +1 或者 -1，那麼當他們異號，也就是當 y1 != y2 時，根據：
可得：α1old - α2old = ξ （ αi - αj = ξ），它確定的可行域是一條斜率為1的直線段，因為αi αj 要滿足約束條件
上面兩條直線分別對應於 y1為 +1 和 -1 的情況。如果是上面那條直線，則 αj 的取值範圍為 [-ξ, C]。如果是下面的那條直線，則為 [0，C-ξ]。 對於這兩種情況 αj 的下界和上界可以統一寫成如下形式：
因為 αi - αj = ξ ，所以又可以寫為：L = max (0, -ξ), H = min(C, C-ξ) 下邊界是直線和 x 軸交點的 x 坐標以及 0 的較大值；上邊界是直線和的交點的 x 坐標和 C 的較小值。再來看第二種情況，如果 yi yj 同號，即當 y1 = y2 時，同樣根據：
可得：α1old + α2old = ξ （ αi + αj = ξ ），所以有：
根據 αi + αj = ξ ， 上式也可寫為：L = max (0, ξ - C), H = min(C, ξ)
如此，根據這兩個變量的等式約束條件（ y1 和 y2 異號或者同號），可以消掉α2old ，可得出 α2new 的上下界分別為：
下面我們來計算不考慮截斷時的函數極值。為了避免分 -1 和 +1 兩種情況，我們將上面的等式約束兩邊同時乘以 y1（第二種表達是乘以yi），可得：
其中 α1 可以用 α2 表示，α1 = w - s*α2，從而我們把子問題的目標函數轉換為只含 α2 的問題：
對 α2 求導（即對自變量求導），並令導數為零，可得：
然後上式兩邊同時除以 η ，得到一個關於單變量 α2 的解：
在求得 αj 之後，根據等式約束條件我們就可以求得另外一個變量的值：
目標函數的二階導數為 η，前面假設二階導數 η > 0，從而保證目標函數是凸函數即開口向上的拋物線，有極小值。如果 η < 0 或者 η = 0，該怎麼處理？對於線性核或正定核函數，可以證明矩陣K的任意一個上述子問題對應的二階子矩陣半正定，因此必定有 η >= 0。無論本次迭代時的初始值是多少，通過上面的子問題求解算法得到是在可行域裡的最小值，因此每次求解更新這兩個變量的值之後，都能保證目標函數值小於或者等於初始值，即函數值下降。 這個解沒有考慮其約束條件 0 <= α2 <= C，即是未經剪輯時的解。 然後考慮約束 0 <= α2 <= C 可得到經過剪輯後的 α2new 的解析解為：
（如果用αi，αj表示，則我們求的這個二次函數的最終極值點為：）
求出了 α2new後，便可以求出α1new ，得：
上圖中第一種情況是拋物線的最小值點在 [L, H]中；第二種情況是拋物線的最小值點大於 H，被截斷為H；第三種情況是小於L，被截斷為L。對於 α1 ，即第一個乘子，可以通過剛剛說的那3種不滿足 KKT的條件來找而對於第二個乘子 α2 可以尋找滿足條件：max |Ei - Ej| 的乘子
且每次更新完兩個乘子的優化後，都需要再重新計算 b，及對應的 Ei值。 最後更新所有的 αi，y 和 b，這樣模型就出來了，從而即可求出咱們開頭提出的分類函數：
此外，這裡有一篇類似的文章，大家可以參考下（https://link.zhihu.com/?target=https%3A//www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html）。5.2 SMO算法的步驟
1，第一步：選取一對 αi 和 αj，選取方法使用啟發式方法2，第二步：固定除αi 和 αj 之外的其他參數，確定W 極值條件下的 αi 和 αj 由 αi 表示 假定在某一次迭代中，需要更新 x1，x2 對應的拉格朗日乘子 α1，α2，那麼這個小規模的二次規劃問題寫為： 那麼在每次迭代中，如何更新乘子呢？引用下面地址（https://link.zhihu.com/?target=http%3A//staff.ustc.edu.cn/~ketang/PPT/PRLec5.pdf）的兩張PPT說明下：
知道了如何更新乘子，那麼選取哪些乘子進行更新呢？具體有以下兩個步驟：步驟一：先「掃描」所有乘子，把第一個違反KKT條件的作為更新對象，令為 a1步驟二：在所有不違反KKT條件的乘子中，選擇使 |E1 - E2|最大的 a2 進行更新，使得能最大限度增大目標函數的值（類似於梯度下降，此外 Ei = ui - yi，而 u = w*x - b ，求出來的 E 代表函數 ui 對輸入 xi 的預測值與真實輸出類標記 yi 之差） 最後，每次更新完兩個乘子的優化後，都需要再重新計算 b，及對應的 Ei 值。 綜上，SMO算法的基本思想是把 Vapnik 在 1982年提出的 Chunking方法推到極致，SMO算法每次迭代只選出兩個分量 ai 和 aj 進行調整，其他分量則保持固定不變，在得到 解 ai 和 aj 之後，再用 ai 和 aj 改進其他分量。與通常的分解算法比較，儘管它可能需要更多的迭代次數，但每次迭代的計算量比較小，所以該算法表現出較好的快速收斂性，且不需要存儲核函數，也沒有矩陣運算。5.3 SMO算法的實現 行文至此，我相信，SVM理解到了一定程度後，是的確能在腦海裡從頭到尾推導出相關公式的，最初分類函數，最大化分類間隔，max1/||w||，min1/2||w||^2，凸二次規劃，拉格朗日函數，轉化為對偶問題，SMO算法，都為尋找一個最優解，一個最優分類平面。一步步梳理下來，為什麼這樣那樣，太多東西可以追究，最後實現。 至於上文中將闡述的核函數則是為了更好的處理非線性可分的情況，而鬆弛變量則是為了糾正或約束少量「不安分」或脫離集體不好歸類的因子。 臺灣的林智仁教授寫了一個封裝SVM算法的libsvm庫，大家可以看看，此外這裡還有一份libsvm的注釋文檔。在這篇論文《fast training of support vector machines using sequential minimal optimization》中platt給出了SMO算法的邏輯代碼。5.4 SMO算法的優缺點分類器複雜度由支撐向量的個數，而非特徵空間（或核函數）的維數決定，因此較少因維數災難發生過擬合線性需要求解二次規劃問題，其規模與訓練模式量成正比，因此計算複雜度高，且存儲開銷大，不適用於需進行在線學習/訓練的大規模分類問題 本文原文連結：https://www.cnblogs.com/wj-1314/p/9489427.html
更多精彩內容請訪問FlyAI-AI競賽服務平臺官方網站（flyai.com）；為AI開發者提供數據競賽並支持GPU離線訓練的一站式服務平臺；每周免費提供項目開源算法樣例，支持算法能力變現以及快速的迭代算法模型。
挑戰者，都在FlyAI！！！
添加FlyAI小助手微信，分享競賽知識乾貨
FlyAI將有償邀請您參加直播、社區分享等活動
還有與大神battle機會等你來戰
_End_
更多優質內容關注"FlyAI社區"公眾號獲取