二、機器學習面試之有必要手推SVM嗎?

作者： milter

原文鏈接：https://www.jianshu.com/p/bce3b2850406

查看更多的專業文章，請移步至「人工智慧LeadAI」公眾號，查看更多的課程信息和產品信息，請移步至全新打造的官網：www.leadai.org.

正文共3166個字，17張圖，預計閱讀時間9分鐘。

上篇文章中，我們介紹了SVM的基本思想，並將其推導成了一個數學問題，今天的任務，就是解決如何求解這個數學問題，同時，回答上篇文章中提出的第二個問題： 如果將正負樣本分開的超平面不存在，那麼如何找一個儘可能將正負樣本分開的超平面？

SVM的數學問題求解

上篇文章中，我們將SVM轉化成了如下的最優化問題：

s.t.

這裡，我們再做一個小小的轉化，將求最大值轉化成求最小值，因為總的來說，我們對求最小值的問題更加熟悉一點，轉化後是這個樣子：

這個問題的求解，數學家們已經給出了完美的辦法。就是拉格朗日對偶法,但是要徹底講清楚這個方法涉及到很多數學知識，如果粗略講講，忽略那些數學知識，就容易造成理解上的困惑。所以，搞機器學習，到底需要多少數學知識？

這個問題沒有一定的正確答案，完全取決於你工作的需要和個人的興趣 。如果你的工作只是理解這些模型的原理以便正確地使用它，那麼，只要你覺得你的數學知識能夠讓你理解這個模型就可以了，如果你的工作可能會需要對模型求解的性能進行優化(這樣的工作崗位我覺得是比較少的)，那麼肯定是理解地越透徹越好，數學知識多多益善。

最後，如果你對數學上的原理很感興趣，那麼 follow your heart即可。

本文的目的是在於說明模型的原理，所以只會在不得已時給出一些數學知識，而且也會儘可能以結論的形式給出。即數學只是我們的工具，我們的目的在於理解模型。

上面的問題， 在求解上，數學上給出了一個拉格朗日對偶求解法。該方法簡單明了，我覺得對這個方法的數學證明，可以留給對數學特別有興趣的朋友，一般情況下，我們只要知道具體的過程就可以了。這就像將大象關進冰箱，我們只需知道打開冰箱門，將大象放進去，關上冰箱門就可以了。好了，相信你已經準備好接受這個方法了，其步驟如下：

1、定義拉格朗日函數

這個函數其實就是將上面的m個大於等於0的約束條件，兩邊乘以-1轉為小於等於0的約束條件，然後每一個約束條件左側表達式乘以一個alpha再與目標函數相加就可以了。請注意，這裡的alpha都是大於等於0的。

2、對w，b求導，令導數為0，求解

3、將第2步求得的結果代回拉格朗日函數，得到對偶問題

4、求解對偶問題，解出alpha，進而求出w，b

你可能對這樣的方法為什麼可行有疑問，還是那句話，這只是數學家告訴我們的一個辦法，他們也證明過了，做機器學習的我們，直接拿來使用就可以了。如果你非要問清楚為什麼，請參閱wiki。

你還可能覺得這個問題成對偶問題後，和原來問題相比，難度一樣啊，還是一個二次規劃問題，為什麼非要費這麼大勁呢。

答案同樣是簡單的，因為這個對偶的二次規劃問題，已經有了高效的求解方法，就是SMO演算法。我有篇文章就是專門講解SMO演算法的，請參閱（絕對原創，絕對心血結晶，強烈推薦閱讀！）。第二呢 ，就是對偶問題會更便於引入核函數的概念。後續會專門講解核函數。

當樣本線性不可分時，SVM還能使用嗎？

在上面的求解過程中，我們的目標是找到一個超平面，將正負樣本分開。這裡的一個前提假設是確實存在一個超平面，能夠將正負樣本分開。但理想很豐滿，現實很骨感，大部分情況下，正負樣本都不是能嚴格分開的，原因是多樣的，比如數據採集有誤差，或者數據本身就是不能完全分開的。

那怎麼辦呢？

此時，我們要回到SVM最初的思想上，SVM就是找一個將正負樣本分得最開的超平面，從這個思想出發，我們一路推導，最後得出了一個數學上的最優化問題：

最小化目標函數(即二分之一的ω的二範數)就相當於最大化超平面與樣本的間隔。對ω的約束就是能正確分開正負樣本，並且與最近的樣本點的函數間隔是1。我們稱存在這樣的超平面的樣本集為線性可分樣本集，此時的SVM也叫做線性可分SVM。

那麼現在，滿足約束條件的超平面已經不存在了。按理說，我們的SVM就不能用了。但是，正負樣本線性不可分也是有程度之分的，一種是徹底的混亂不可分，一種是總體看來是可分，少數點使得其不可分。

對於徹底混亂不可分的情況，用核函數的辦法可以使得我們繼續使用SVM，簡單講就是將樣本集進行映射，使得映射後的樣本集正負線性可分，然後再使用SVM。如下圖所示：

這個做法要在講核函數時才能透徹說明。暫時按下不表。

對於基本線性可分，少數樣本使得其不可分的情況，我們可以「放鬆」原來的SVM的要求，從而使其能適用這種情況。放鬆的思想非常簡單，就是不再執著於尋找將正負樣本分得最開的超平面，轉而尋找將最多的樣本分開且分得儘可能開，將最少的樣本分不開，且分不開的程度儘可能低的超平面。這句話需要停下來反覆體味一下。下面就來看看怎麼來「放鬆」吧。

假設我們現在有一個超平面H，然後我們努力尋找它的特定表示，即ω，b，以便使得對每一個樣本滿足：

但是費了九牛二虎之力，找到的最好的表示ω，b仍然不能使得所有樣本滿足上面的條件。那麼，此時，我們需要一個指標來告訴我們，這個超平面在區分正負樣本方面怎麼樣？是不是達到了我們所要求的將能分開的樣本分得儘可能開，將不能分開的樣本分不開的程度降得儘可能低。

我們先來看看這個超平面對能分得開的樣本分開的程度吧，對這些樣本而言，都是滿足上面的函數間隔大於等於1的要求的，所以，超平面將這些樣本分開的程度可以用

來表示，這個值越小，表示超平面將這些樣本分得越開。

對那些不滿足函數間隔大於等於1的樣本，如何衡量超平面對它們分不開的程度呢？就是看這些樣本離滿足函數間隔大於等於1的要求有多遠。比如對樣本(xi,yi),如果對它的函數間隔加上某個數ζi,就能使得該樣本對超平面的函數間隔滿足大於等於1的要求，我們就稱超平面對這個樣本分不開的程度為ζi。將所有分不開的樣本的ζi加起來就可以衡量超平面對分不開的樣本的分不開的程度。顯然，對於那些滿足函數間隔大於等於1的樣本， 它們對應的ζi為0。

至此，我們知道了如何衡量超平面對那些滿足函數間隔大於等於1的樣本的分得開的程度，也知道了如何衡量超平面對那些不滿足函數間隔大於等於1的樣本的分不開的程度。將二者結合結合起來，就是能夠衡量一個超平面，對於一個線性不可分的樣本的分得開的程度。這就是基本線性可分SVM，如下圖所示：

對這個問題的求解仍然是使用拉格朗日對偶法，過程和上面一樣，這裡不再贅述。

對基本線性可分SVM的思考

回顧本文，我覺得最重要的不是SVM的對偶求解方法，也不是線性可分SVM（啥意思，通篇文章不就講了這兩個事兒嗎，逗我呢？）

我這麼說是認真的，因為我覺得最重要的是我們從線性可分SVM，結合現實中樣本都不是完全線性可分的實際，進而調整得到基本線性可分SVM的思維過程。這樣的思維方式體現了將理論與實踐結合的過程，這是我覺得最可貴的思維品質。

在當前AI快速發展的形勢下，新的演算法每天都在湧現，很多相關工作崗位都要求能夠跟蹤最新技術，並結合實際運用它，為公司創造利益。「結合實際」需要的就是這種將理論結合實踐的思維品質。之前，聽汪榕的智能營銷實踐課程，我最大的收穫就是學習到他那種緊緊地將理論與實際業務結合的優秀思維習慣，所以，這裡也強烈推薦下他的課程，即使你不是做智能營銷，也應該能從中受益。

所以，如果讀完本文，讓你對理論結合實際有了更深一點的體會，我覺得就值了。

軟間隔是在硬間隔的基礎上針對現實問題做出的調整，這是有普遍意義的，就是目標函數要能夠靈活結合實際變化。