支持向量機(SVM)是什麼意思？

11-24

支持向量機/support vector machine (SVM)。

@Han Oliver@Linglai Li 前輩們的解釋讓人受益許多。
正好最近自己學習機器學習，看到reddit上 Please explain Support Vector Machines (SVM) like I am a 5 year old 的帖子，一個字贊！於是整理一下和大家分享。(如有錯歡迎指教！)

什麼是SVM?

當然首先看一下wiki.

Support Vector Machines are learning models used for classification: which individuals in a population belong where? So… how do SVM and the mysterious 「kernel」 work?

好吧，故事是這樣子的：

在很久以前的情人節，大俠要去救他的愛人，但魔鬼和他玩了一個遊戲。

魔鬼在桌子上似乎有規律放了兩種顏色的球，說：「你用一根棍分開它們？要求：盡量在放更多球之後，仍然適用。」

於是大俠這樣放，乾的不錯？

然後魔鬼，又在桌上放了更多的球，似乎有一個球站錯了陣營。

SVM就是試圖把棍放在最佳位置，好讓在棍的兩邊有儘可能大的間隙。

現在即使魔鬼放了更多的球，棍仍然是一個好的分界線。

然後，在SVM 工具箱中有另一個更加重要的 trick。魔鬼看到大俠已經學會了一個trick，於是魔鬼給了大俠一個新的挑戰。

現在，大俠沒有棍可以很好幫他分開兩種球了，現在怎麼辦呢？當然像所有武俠片中一樣大俠桌子一拍，球飛到空中。然後，憑藉大俠的輕功，大俠抓起一張紙，插到了兩種球的中間。

現在，從魔鬼的角度看這些球，這些球看起來像是被一條曲線分開了。

再之後，無聊的大人們，把這些球叫做 「data」，把棍子叫做 「classifier」, 最大間隙trick 叫做「optimization」，拍桌子叫做「kernelling」, 那張紙叫做「hyperplane」。

圖片來源：Support Vector Machines explained well

直觀感受看：https://www.youtube.com/watch?v=3liCbRZPrZA

參考：

Please explain Support Vector Machines (SVM) like I am a 5 year old. : MachineLearning
Support Vector Machines explained well
https://www.youtube.com/watch?v=3liCbRZPrZA

這篇答案貢獻給想捋一捋SVM思路的看官。我的初衷是想直觀地捋順SVM的原理和求最優解，儘可能只用到必需的數學表達，但彷彿所有的數學推導都瞭然於胸。

先看思維導圖：

左邊是求解基本的SVM問題
右邊是相關擴展

什麼是SVM？

Support Vector Machine, 一個普通的SVM就是一條直線罷了，用來完美劃分linearly separable的兩類。但這又不是一條普通的直線，這是無數條可以分類的直線當中最完美的，因為它恰好在兩個類的中間，距離兩個類的點都一樣遠。而所謂的Support vector就是這些離分界線最近的『點』。如果去掉這些點，直線多半是要改變位置的。可以說是這些vectors（主，點點）support（謂，定義）了machine（賓，分類器）...

所以謎底就在謎面上啊朋友們，只要找到了這些最靠近的點不就找到了SVM了嘛。

如果是高維的點，SVM的分界線就是平面或者超平面。其實沒有差，都是一刀切兩塊，我就統統叫直線了。

怎麼求解SVM？

關於這條直線，我們知道(1)它在離兩邊一樣遠，(2)最近距離就是到support vector，其他距離只能更遠。

於是自然而然可以得到重要表達 I. direct representation:

$argmax_{boundary} margin(boundary)$ ,
subject to 所有正確歸類的蘋果和香蕉到boundary的距離都 $ge margin$

（可以把margin看作是boundary的函數，並且想要找到使得是使得margin最大化的boundary，而margin(*)這個函數是：輸入一個boundary，計算（正確分類的）所有蘋果和香蕉中，到boundary的最小距離。）

又有最大又有最小看起來好矛盾。實際上『最大』是對這個整體使用不同boundary層面的最大，『最小』是在比較『點』的層面上的最小。外層在比較boundary找最大的margin，內層在比較點點找最小的距離。

其中距離，說白了就是點到直線的距離；只要定義帶正負號的距離，是{蘋果+1}面為正{香蕉-1}面為負的距離，互相乘上各自的label $in left{ +1,-1 ight}$ ，就和諧統一民主富強了。

# ========== 數學表達 begin ========== #

# 定義直線為 $y(x) = w^Tx+b$

# 任意點 $x_0$ 到該直線的距離為 $frac{1}{||w||}(w^Tx_0+b)$

# UPDATE: 普通點到面的二位歐式距離寫法應該是： $d=frac{left( ax_1+bx_2+c ight)}{sqrt{a^2+b^2}}$ （此處允許負數出現），如果升級到更高維度，是不是就和上一行一毛一樣？

# 對於N個訓練點的信息(點的坐標，蘋果還是香蕉)記為 $(x_i, y_i)$

# 上述表達也就是[1]：

# $argmax_{w,b}left{ frac{1}{||w||}min_{n}left[ y_i(w^Tx_i+b) ight] ight}$

# 不知為何這是我見過的最喜歡的寫法（比心）

# 也可以寫成[2]：

# $argmax_{w,b,||w||=1} margin$

subject to $y_i(w^Tx_i+b)ge margin, forall i$

# $||w||=1$ 就是為了表達方便[3]，後面會取消這個限制

# ========== 數學表達 end ========== #

到這裡為止已經說完了所有關於SVM的直觀了解，如果不想看求解，可以跳過下面一大段直接到objective function。

直接表達雖然清楚但是求解無從下手。做一些簡單地等價變換（分母倒上來）可以得到 II. canonical representation （敲黑板

$argmin_{boundary}||w||$
subject to 所有蘋果和香蕉到boundary的距離 $ge margin$

w不過是個定義直線的參數，知道這一步是等價變換出來的表達就可以了。

# ========== 數學表達 begin ========== #

# 為了以後推導方便，一般寫成：

# $argmin_{w,b}frac{1}{2}||w||^2$

subject to $y_i(w^Tx_i+b)ge 1, forall i$

# 這個『1』就是一個常數，這樣設置是為了以後的方便

# 這個選擇的自由來自於直線 $y(x) = w^Tx+b$ 的參數如果rescale成 $kw$ 和 $kb$ 不改變距離。

# ========== 數學表達 end ========== #

要得到III. dual representation之前需要大概知道一下拉格朗日乘子法 (method of lagrange multiplier)，它是用在有各種約束條件(各種"subject to")下的目標函數，也就是直接可以求導可以引出dual representation（怎麼還沒完摔）

# ========== 數學表達 begin ========== #

# 稍微解釋一下使用拉格朗日乘子法的直觀理解，不作深入討論

# $L=frac{1}{2}||w||^2-sum_{n=1}^{N}{a_n*left{ y_nleft( w^Tx_n+b ight) -1 ight} }$ , 其中 $a_n>0$ 是橙子（划去）乘子[1]

# 可以這樣想：(1) 我們的兩個任務：①對參數最小化L（解SVM要求），②對乘子又要最大化（拉格朗日乘子法要求）， (2) 如果上面的約束條件成立，整個求和都是非負的，很好L是可以求最小值的；(3) 約束條件不成立，又要對乘子最大化，全身非負的L直接原地爆炸

# 好棒棒，所以解題一定要遵守基本法

# ① 先搞定第一個任務對w,b最小化L

# 凸優化直接取導 =&> 志玲（划去）置零，得到：

# $w=sum_{n=1}^{N}{a_ny_nx_n}$

$0=sum_{n=1}^{N}{a_ny_n}$

# ② 第二個任務對a最大化L，就是dual representation了

# ========== 數學表達 end ========== #

稍微借用剛剛數學表達裡面的內容看個有趣的東西：

還記得我們怎麼預測一個新的水果是蘋果還是香蕉嗎？我們代入到分界的直線里，然後通過符號來判斷。

剛剛w已經被表達出來了也就是說這個直線現在變成了： $y(x_0) =sum_{n=1}^{N}{a_ny_nx_n^Tx_0} +b$

看似彷彿用到了所有的訓練水果，但是其中 $a_n=0$ 的水果都沒有起到作用，剩下的就是小部分靠邊邊的Support vectors呀。

III. dual representation

把①的結果代回去就可以得到[1]：

$max_{all a_n} L(a)=sum_{n=1}^{N}{a_n} -frac{1}{2}sum_{n=1}^{N}{sum_{m=1}^{N}{a_na_my_ny_mx_n^Tx_m} }$
subject to $a_n ge0,forall n$ , $sum_{n=1}^{N}{a_ny_n}=0$

如果香蕉和蘋果不能用直線分割呢？

Kernel trick.

其實用直線分割的時候我們已經使用了kernel，那就是線性kernel, $k(x_1,x_2) = x_1^Tx_2$

如果要替換kernel那麼把目標函數裡面的內積全部替換成新的kernel function就好了，就是這麼簡單。

高票答案武俠大師的比喻已經說得很直觀了，低維非線性的分界線其實在高維是可以線性分割的，可以理解為——『你們是蟲子！』分得開個p...（大霧）

如果香蕉和蘋果有交集呢？

鬆弛變數 (slack variable $xige0$ )

鬆弛變數允許錯誤的分類，但是要付出代價。圖中以蘋果為例，錯誤分類的蘋果 $xi>1$ ；在margin當中但是正確分類的蘋果 $0<xile 1$ ；正確分類並且在margin外面的蘋果 $xi=0$ 。可以看出每一個數據都有一一對應的懲罰。

對於這一次整體的懲罰力度，要另外使用一個超參數 ( $gamma$ ) 來衡量這一次分類的penalty程度。

從新的目標函數里可見一斑[1]： $min frac{1}{2}||w||^2 + frac{gamma}{2}sum_{n=1}^{N}{xi_n^2}$

（約束條件略）

如果還有梨呢？

可以每個類別做一次SVM：是蘋果還是不是蘋果？是香蕉還是不是香蕉？是梨子還是不是梨子？從中選出可能性最大的。這是one-versus-the-rest approach。

也可以兩兩做一次SVM：是蘋果還是香蕉？是香蕉還是梨子？是梨子還是蘋果？最後三個分類器投票決定。這是one-versus-one approace。

但這其實都多多少少有問題，比如蘋果特別多，香蕉特別少，我就無腦判斷為蘋果也不會錯太多；多個分類器要放到一個檯面上，萬一他們的scale沒有在一個檯面上也未可知。

這時候我們再回過頭看一下思維導圖劃一下重點：

課後習題：

1. vector不願意support怎麼辦？

2. 蘋果好吃還是香蕉好吃？

最後送一張圖我好愛哈哈哈 (Credit: Burr Settles)

[1] Bishop C M. Pattern recognition[J]. Machine Learning, 2006, 128.

[2] Friedman J, Hastie T, Tibshirani R. The elements of statistical learning[M]. Springer, Berlin: Springer series in statistics, 2001.

[3] James G, Witten D, Hastie T, et al. An introduction to statistical learning[M]. New York: springer, 2013.

SVM是什麼？

SVM - support vector machine, 俗稱支持向量機，為一種supervised learning演算法，屬於classification的範疇。
在數據挖掘的應用中，與unsupervised的Clustering相對應和區別。
廣泛應用於機器學習(Machine Learning), 計算機視覺(Computer Vision) 和數據挖掘(Data Mining)當中。

SVM大致原理如圖1，

圖片引用自：wordpress.com 的頁面

假設我們要通過三八線把實心圈和空心圈分成兩類。
那麼有無數多條線可以完成這個任務。
在SVM中，我們尋找一條最優的分界線使得它到兩邊的margin都最大。
在這種情況下邊緣加粗的幾個數據點就叫做support vector，這也是這個分類演算法名字的來源。

拓展至任意n維乃至無限維空間，如圖2，

圖片引用自OpenCV: Introduction to Support Vector Machines

We got a bunch of data points in a n- dimensional to infinite-dimensional space,
Then one can always find a optimal hyperplane which is always in the n-1 dimension.

最後，
統計方向：Support Vector Machines (SVM)
wiki：Support vector machine
教程：columbia.edu 的頁面
以及一個很棒的視頻演示。自備梯.子。
http://youtu.be/3liCbRZPrZA

當處理文本分類問題時，你需要不斷提煉自己的數據集，甚至會嘗試使用樸素貝葉斯。在對數據集滿意後，如何更進一步呢？是時候了解支持向量機（SVM）了：一種快速可靠的分類演算法，可以在數據量有限的情況下很好地完成任務。在本文中，Bruno Stecanella 將對這一概念進行通俗易懂的解釋，希望能對你有所幫助。

或許你已經開始了自己的探索，聽說過線性可分、核心技巧、核函數等術語。支持向量機（SVM）演算法的核心理念非常簡單，而且將其應用到自然語言分類任務中也不需要大部分複雜的東西。

在開始前，你也可以閱讀樸素貝葉斯分類器指南，其中有很多有關文本處理任務的內容。

鏈接：https://monkeylearn.com/blog/practical-explanation-naive-bayes-classifier/

SVM 是如何工作的？

支持向量機的基礎概念可以通過一個簡單的例子來解釋。讓我們想像兩個類別：紅色和藍色，我們的數據有兩個特徵：x 和 y。我們想要一個分類器，給定一對（x，y）坐標，輸出僅限於紅色或藍色。我們將已標記的訓練數據列在下圖中：

支持向量機會接受這些數據點，並輸出一個超平面（在二維的圖中，就是一條線）以將兩類分割開來。這條線就是判定邊界：將紅色和藍色分割開。

但是，最好的超平面是什麼樣的？對於 SVM 來說，它是最大化兩個類別邊距的那種方式，換句話說：超平面（在本例中是一條線）對每個類別最近的元素距離最遠。

這裡有一個視頻解釋可以告訴你最佳的超平面是如何找到的。

支持向量機演算法是如何工作的_騰訊視頻v.qq.com視頻支持向量機演算法是如何工作的_騰訊視頻

線性數據

上面的例子很簡單，因為那些數據是線性可分的——我們可以通過畫一條直線來簡單地分割紅色和藍色。然而，大多數情況下事情沒有那麼簡單。看看下面的例子：

很明顯，你無法找出一個線性決策邊界（一條直線分開兩個類別）。然而，兩種向量的位置分得很開，看起來應該可以輕易地分開它們。

這個時候我們需要引入第三個維度。迄今為止，我們有兩個維度：x 和 y。讓我們加入維度 z，並且讓它以直觀的方式出現：z = x2 + y2（沒錯，圓形的方程式）

於是我們就有了一個三維空間，看看這個空間，它就像這樣：

支持向量機將會如何區分它？很簡單：

太棒了！請注意，現在我們處於三維空間，超平面是 z 某個刻度上（比如 z=1）一個平行於 x 軸的平面。它在二維上的投影是這樣：

於是，我們的決策邊界就成了半徑為 1 的圓形，通過 SVM 我們將其成功分成了兩個類別。下面的視頻用 3D 形式展現了一個類似的分類效果：

SVM with polynomial kernel 可視化_騰訊視頻

核函數技巧

在以上例子中，我們找到了一種通過將空間巧妙地映射到更高維度來分類非線性數據的方法。然而事實證明，這種轉換可能會帶來很大的計算成本：可能會出現很多新的維度，每一個都可能帶來複雜的計算。為數據集中的所有向量做這種操作會帶來大量的工作，所以尋找一個更簡單的方法非常重要。

還好，我們已經找到了訣竅：SVM 其實並不需要真正的向量，它可以用它們的數量積（點積）來進行分類。這意味著我們可以避免耗費計算資源的境地了。我們需要這樣做：

想像一個我們需要的新空間：
z = x2 + y2
找到新空間中點積的形式：
a · b = xa· xb + ya· yb + za· zb
a · b = xa· xb + ya· yb + (xa2 + ya2) · (xb2 + yb2)
讓 SVM 處理新的點積結果——這就是核函數

這就是核函數的技巧，它可以減少大量的計算資源需求。通常，內核是線性的，所以我們得到了一個線性分類器。但如果使用非線性內核（如上例），我們可以在完全不改變數據的情況下得到一個非線性分類器：我們只需改變點積為我們想要的空間，SVM 就會對它忠實地進行分類。

注意，核函數技巧實際上並不是 SVM 的一部分。它可以與其他線性分類器共同使用，如邏輯回歸等。支持向量機只負責找到決策邊界。

支持向量機如何用於自然語言分類？

有了這個演算法，我們就可以在多維空間中對向量進行分類了。如何將它引入文本分類任務呢？首先你要做的就是把文本的片斷整合為一個數字向量，這樣才能使用 SVM 進行區分。換句話說，什麼屬性需要被拿來用作 SVM 分類的特徵呢？

最常見的答案是字頻，就像在樸素貝葉斯中所做的一樣。這意味著把文本看作是一個詞袋，對於詞袋中的每個單詞都存在一個特徵，特徵值就是這個詞出現的頻率。

這樣，問題就被簡化為：這個單詞出現了多少次，並把這個數字除以總字數。在句子「All monkeys are primates but not all primates are monkeys」中，單詞 mokey 出現的頻率是 2/10=0.2，而 but 的頻率是 1/10=0.1。

對於計算要求更高的問題，還有更好的方案，我們也可以用 TF-IDF。

現在我們做到了，數據集中的每個單詞都被幾千（或幾萬）維的向量所代表，每個向量都表示這個單詞在文本中出現的頻率。太棒了！現在我們可以把數據輸入 SVM 進行訓練了。我們還可以使用預處理技術來進一步改善它的效果，如詞幹提取、停用詞刪除以及 n-gram。

選擇核函數

現在我們有了特徵向量，唯一要做的事就是選擇模型適用的核函數了。每個任務都是不同的，核函數的選擇有關於數據本身。在我們的例子中，數據呈同心圓排列，所以我們需要選擇一個與之匹配的核函數。

既然需要如此考慮，那麼什麼是自然語言處理需要的核函數？我們需要費線性分類器嗎？亦或是數據線性分離？事實證明，最好堅持使用線性內核，為什麼？

回到我們的例子上，我們有兩種特徵。一些現實世界中 SVM 在其他領域裡的應用或許會用到數十，甚至數百個特徵值。同時自然語言處理分類用到了數千個特徵值，在最壞的情況下，每個詞都只在訓練集中出現過一次。這會讓問題稍有改變：非線性核心或許在其他情況下很好用，但特徵值過多的情況下可能會造成非線性核心數據過擬合。因此，最好堅持使用舊的線性核心，這樣才能在那些例子中獲得很好的結果。

為我所用

現在需要做的就是訓練了！我們需要採用標記文本集，使用詞頻將他們轉換為向量，並填充演算法，它會使用我們選擇的核函數，然後生成模型。然後，當我們遇到一段未標記的文本想要分類時，我們就可以把它轉化為向量輸入模型中，最後獲得文本類型的輸出。

結語

以上就是支持向量機的基礎。總結來說就是：

支持向量機能讓你分類線性可分的數據；
如果線性不可分，你可以使用 kernel 技巧；
然而，對文本分類而言最好只用線性 kernel。

相比於神經網路這樣更先進的演算法，支持向量機有兩大主要優勢：更高的速度、用更少的樣本（千以內）取得更好的表現。這使得該演算法非常適合文本分類問題。

原文鏈接：An introduction to Support Vector Machines (SVM)

許多回答太理論了，如果僅針對題目而言，是個名詞解釋的問題：「支持向量機」為偏正結構，所以分別解釋「支持向量」和「機」

（1）「機」 —— Classification Machine，分類器，這個沒啥好說的了。

（2）「支持向量」 —— 現第一名的匿名用戶已經用經典的圖例解釋了，在maximum margin上的這些點就叫支持向量，我想補充的是為啥這些點就叫支持向量，因為最後的classification machine的表達式里只含用這些「支持向量」的信息，而與其他數據點無關：

這個表達式中，只有支持向量的係數 $alpha_i$ 不等於0引用Wiki：Support vector machine

支持向量機不是一種機器而是一種機器學習演算法.....N個人問過我這個問題：這個機器的是怎麼支持向量的？........

支持向量機(Support Vector Machine)是Cortes和Vapnik於1995年首先提出的，它在解決小樣本、非線性及高維模式識別中表現出許多特有的優勢，並能夠推廣應用到函數擬合等其他機器學習問題中。
支持向量機方法是建立在統計學習理論的VC 維理論和結構風險最小原理基礎上的，根據有限的樣本信息在模型的複雜性（即對特定訓練樣本的學習精度，Accuracy）和學習能力（即無錯誤地識別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力（或稱泛化能力）。

以上是經常被有關SVM 的學術文獻引用的介紹，我來逐一分解並解釋一下。

Vapnik是統計機器學習的大牛，這想必都不用說，他出版的《Statistical Learning Theory》是一本完整闡述統計機器學習思想的名著。在該書中詳細的論證了統計機器學習之所以區別於傳統機器學習的本質，就在於統計機器學習能夠精確的給出學習效果，能夠解答需要的樣本數等等一系列問題。與統計機器學習的精密思維相比，傳統的機器學習基本上屬於摸著石頭過河，用傳統的機器學習方法構造分類系統完全成了一種技巧，一個人做的結果可能很好，另一個人差不多的方法做出來卻很差，缺乏指導和原則。

所謂VC維是對函數類的一種度量，可以簡單的理解為問題的複雜程度，VC維越高，一個問題就越複雜。正是因為SVM關注的是VC維，後面我們可以看到，SVM解決問題的時候，和樣本的維數是無關的（甚至樣本是上萬維的都可以，這使得SVM很適合用來解決文本分類的問題，當然，有這樣的能力也因為引入了核函數）。

結構風險最小聽上去文縐縐，其實說的也無非是下面這回事。

機器學習本質上就是一種對問題真實模型的逼近（我們選擇一個我們認為比較好的近似模型，這個近似模型就叫做一個假設），但毫無疑問，真實模型一定是不知道的（如果知道了，我們幹嗎還要機器學習？直接用真實模型解決問題不就可以了？對吧，哈哈）既然真實模型不知道，那麼我們選擇的假設與問題真實解之間究竟有多大差距，我們就沒法得知。比如說我們認為宇宙誕生於150億年前的一場大爆炸，這個假設能夠描述很多我們觀察到的現象，但它與真實的宇宙模型之間還相差多少？誰也說不清，因為我們壓根就不知道真實的宇宙模型到底是什麼。

這個與問題真實解之間的誤差，就叫做風險（更嚴格的說，誤差的累積叫做風險）。我們選擇了一個假設之後（更直觀點說，我們得到了一個分類器以後），真實誤差無從得知，但我們可以用某些可以掌握的量來逼近它。最直觀的想法就是使用分類器在樣本數據上的分類的結果與真實結果（因為樣本是已經標註過的數據，是準確的數據）之間的差值來表示。這個差值叫做經驗風險Remp(w)。以前的機器學習方法都把經驗風險最小化作為努力的目標，但後來發現很多分類函數能夠在樣本集上輕易達到100%的正確率，在真實分類時卻一塌糊塗（即所謂的推廣能力差，或泛化能力差）。此時的情況便是選擇了一個足夠複雜的分類函數（它的VC維很高），能夠精確的記住每一個樣本，但對樣本之外的數據一律分類錯誤。回頭看看經驗風險最小化原則我們就會發現，此原則適用的大前提是經驗風險要確實能夠逼近真實風險才行（行話叫一致），但實際上能逼近么？答案是不能，因為樣本數相對於現實世界要分類的文本數來說簡直九牛一毛，經驗風險最小化原則只在這占很小比例的樣本上做到沒有誤差，當然不能保證在更大比例的真實文本上也沒有誤差。

統計學習因此而引入了泛化誤差界的概念，就是指真實風險應該由兩部分內容刻畫，一是經驗風險，代表了分類器在給定樣本上的誤差；二是置信風險，代表了我們在多大程度上可以信任分類器在未知文本上分類的結果。很顯然，第二部分是沒有辦法精確計算的，因此只能給出一個估計的區間，也使得整個誤差只能計算上界，而無法計算準確的值（所以叫做泛化誤差界，而不叫泛化誤差）。

置信風險與兩個量有關，一是樣本數量，顯然給定的樣本數量越大，我們的學習結果越有可能正確，此時置信風險越小；二是分類函數的VC維，顯然VC維越大，推廣能力越差，置信風險會變大。

泛化誤差界的公式為：

R(w)≤Remp(w)+Ф(n/h)

公式中R(w)就是真實風險，Remp(w)就是經驗風險，Ф(n/h)就是置信風險。統計學習的目標從經驗風險最小化變為了尋求經驗風險與置信風險的和最小，即結構風險最小。

SVM正是這樣一種努力最小化結構風險的演算法。

SVM其他的特點就比較容易理解了。

小樣本，並不是說樣本的絕對數量少（實際上，對任何演算法來說，更多的樣本幾乎總是能帶來更好的效果），而是說與問題的複雜度比起來，SVM演算法要求的樣本數是相對比較少的。

非線性，是指SVM擅長應付樣本數據線性不可分的情況，主要通過鬆弛變數（也有人叫懲罰變數）和核函數技術來實現，這一部分是SVM的精髓，以後會詳細討論。多說一句，關於文本分類這個問題究竟是不是線性可分的，尚沒有定論，因此不能簡單的認為它是線性可分的而作簡化處理，在水落石出之前，只好先當它是線性不可分的（反正線性可分也不過是線性不可分的一種特例而已，我們向來不怕方法過於通用）。

高維模式識別是指樣本維數很高，例如文本的向量表示，如果沒有經過另一系列文章（《文本分類入門》）中提到過的降維處理，出現幾萬維的情況很正常，其他演算法基本就沒有能力應付了，SVM卻可以，主要是因為SVM 產生的分類器很簡潔，用到的樣本信息很少（僅僅用到那些稱之為「支持向量」的樣本，此為後話），使得即使樣本維數很高，也不會給存儲和計算帶來大麻煩（相對照而言，kNN演算法在分類時就要用到所有樣本，樣本數巨大，每個樣本維數再一高，這日子就沒法過了……）。

如果想要一樓的那種圖解或者SVM在數據挖掘中的代碼常式圖，後續可更。

答主的問題是「什麼是SVM」，所以我想還是從比較基礎的層面來科普一下SVM的相關知識。我會盡量說的簡潔明了~
首先，SVM全稱是supported vector machine（支持向量機）。我們先不管它的名稱，因為這一開始並不是很好理解所謂的支持向量是什麼。但是本質上，這就是一個分類器，並且是二類分類器。分類器我想答主一定是理解的吧，我就不贅述了，為什麼是二類的分類器呢？因為它最多只能告訴你這個東西要麼屬於A要麼屬於B，不能告訴你要麼屬於A要麼屬於B要麼屬於C。
我舉個例子吧，當你給SVM一段文本，比如「這款手機屏幕很大，我很喜歡」，你想知道這個文本的情感傾向是積極的還是消極的，你把這個文本扔給SVM分類器，SVM會告訴你說它的情感是積極的。但是現在我們多了一個選項，「中立」。你想讓SVM告訴你這個文本是積極還是消極還是中立，這時候SVM就無能為力了。當然，有別的策略可以利用SVM處理多分類的問題，這個留到最後再說。
先開始說SVM的思想。如圖的例子，（訓練集）紅色點是我們已知的分類1，（訓練集）藍色點是已知的分類2，我們想尋找一個分界超平面（圖中綠線）（因為示例是二維數據點，所以只是一條線，如果數據是三維的就是平面，如果是三維以上就是超平面）把這兩類完全分開，這樣的話再來一個樣本點需要我們預測的話，我們就可以根據這個分界超平面預測出分類結果。

那我們如何選擇這個分類超平面呢？從數學上說，超平面的公式是 $omega^{T} x +b=0$ ,也就是說如何選取這個 $omega$ （是個向量）。
傳統方法是根據最小二乘錯誤法（least squared error），首先隨便定選取一個隨機平面，也就是隨機選取 $omega$ 和 $b$ ，然後想必會在訓練集中產生大量的錯誤分類，也就是說， $omega^{T} x +b$ 結果應該大於0的時候小於0，應該小於0的時候大於0。這時候有一個錯誤損失，也就是說對於所有錯誤的分類，他們的平方和（least squared error）為： $sum_{i}^{n} ( omega^{T} x_{i} +b )^{2}$ , 最小二乘法的目標就是讓這個值趨於最小，對 $omega$ 求導取0，採用梯度下降演算法，可以求出錯誤平方和的極值，求出最優的 $omega$ ，也就是求出最優的超平面。（可以證明，如果基函數是指數族函數，求出的超平面是全局最優的）
那我們SVM演算法的思路是怎樣的呢？不同於傳統的最小二乘策略的思想，我們採用一種新的思路，這個分界面有什麼樣的特徵呢？第一，它「夾」在兩類樣本點之間；第二，它離兩類樣本點中所有「離它最近的點」，都離它儘可能的遠。如圖所示：

在虛線上的點，就是我們所找到的離分解超平面最近的樣本點，X類中找到了一個，O類找到了兩個。我們需要分類超平面離這三個樣本點都儘可能的遠，也就是說，它處在兩條虛線的中間。這就是我們找到的分界超平面。
另外，這裡我們就可以解釋什麼是「支持向量」了，支持向量就是虛線上的離分類超平面最近的樣本點，因為每一個樣本點都是一個多維的向量，向量的每一個維度都是這個樣本點的一個特徵。比如在根據身高，體重，特徵進行男女分類的時候，每一個人是一個向量，向量有兩個維度，第一維是身高，第二維是體重。
介紹完SVM的基本思想，我們來探討一下如何用數學的方法進行SVM分類。首先我們需要把剛剛說的最大間隔分類器的思想用數學公式表達出來。先定義幾何間隔的概念，幾何間隔就是在多維空間中一個多維點到一個超平面的距離，根據向量的知識可以算出來：
$Upsilon =frac{omega^{T}x+b }{ ||omega || }$
然後對於所有的支持向量，使他們到超平面 $omega^{T}x+b$ 的距離最大，也就是
$max_{omega ,b}Upsilon = max_{omega ,b} frac{omega^{T}x+b }{ ||omega || }$
因為對於所有支持向量，他們 $omega^{T}x+b$ 的值都是一定的，我們假設恆等於1，那麼上式變成了 $max_{omega } frac{1}{ ||omega || } =min_{omega}frac{1}{2}||omega||^{2}$ ,並且對於所有的樣本點，滿足 $y^{i}(omega^{T}x+b)>=1$ 的約束，因此，可以利用拉格朗日乘數法計算出它的極值。也就是求出這個超平面。
推導過程略為複雜，詳細了解可以參考凸二次規劃知識，結合SMO演算法理解SVM計算超平面的詳細過程。
總之，在計算的過程中，我們不需要了解支持向量以外的其他樣本點，只需要利用相對於所有樣本點來說為數不多的支持向量，就可以求出分類超平面，計算複雜度大為降低。

百度知道搬運過來的支持向量機請通俗介紹高中文化
超級通俗的解釋：
支持向量機是用來解決分類問題的。
先考慮最簡單的情況，豌豆和米粒，用曬子很快可以分開，小顆粒漏下去，大顆粒保留。
用一個函數來表示就是當直徑d大於某個值D，就判定為豌豆，小於某個值就是米粒。
d&>D, 豌豆
d&在數軸上就是在d左邊就是米粒，右邊就是綠豆，這是一維的情況。

但是實際問題沒這麼簡單，考慮的問題不單單是尺寸，一個花的兩個品種，怎麼分類？
假設決定他們分類的有兩個屬性，花瓣尺寸和顏色。單獨用一個屬性來分類，像剛才分米粒那樣，就不行了。這個時候我們設置兩個值尺寸x和顏色y.
我們把所有的數據都丟到x-y平面上作為點，按道理如果只有這兩個屬性決定了兩個品種，數據肯定會按兩類聚集在這個二維平面上。
我們只要找到一條直線，把這兩類劃分開來，分類就很容易了，以後遇到一個數據，就丟進這個平面，看在直線的哪一邊，就是哪一類。
比如x+y-2=0這條直線，我們把數據(x,y)代入，只要認為x+y-2&>0的就是A類，x+y-2&<0的就是B類。

以此類推，還有三維的，四維的，N維的屬性的分類，這樣構造的也許就不是直線，而是平面，超平面。
一個三維的函數分類：x+y+z-2=0，這就是個分類的平面了。

有時候，分類的那條線不一定是直線，還有可能是曲線，我們通過某些函數來轉換，就可以轉化成剛才的哪種多維的分類問題，這個就是核函數的思想。
例如：分類的函數是個圓形x^2+y^2-4=0。這個時候令x^2=a; y^2=b,還不就變成了a+b-4=0 這種直線問題了。

這就是支持向量機的思想。
機的意思就是演算法，機器學習領域裡面常常用「機」這個字表示演算法
支持向量意思就是數據集種的某些點，位置比較特殊，比如剛才提到的x+y-2=0這條直線，直線上面區域x+y-2&>0的全是A類，下面的x+y-2&<0的全是B類，我們找這條直線的時候，一般就看聚集在一起的兩類數據，他們各自的最邊緣位置的點，也就是最靠近劃分直線的那幾個點，而其他點對這條直線的最終位置的確定起不了作用，所以我姑且叫這些點叫「支持點」（意思就是有用的點），但是在數學上，沒這種說法，數學裡的點，又可以叫向量，比如二維點(x,y)就是二維向量，三維度的就是三維向量（ x,y,z)。所以「支持點」改叫「支持向量」，聽起來比較專業，NB。

就是一個分類器而已，
machine的意思就是說這是一個自動分類的演算法。從概念上來說，SVM屬於Linear Machine的一種，也就是所謂線性機。
在樣本是兩類的情況下，最基本的線性SVM就是學出一個從n維空間到一維空間（Score）的投影。這個投影要求能在一維空間里把兩類分開。這個目標這個其實和LDA（線性判別分析）是一致的。不同之處在於SVM使用了Hinge Loss來達到Maximal Margin，而LDA使用類間/類內雜散度矩陣的特徵值之比來度量loss。
所謂的引入核函數，就是使用核函數對應高維空間內積的性質來使得線性分類器可以隱式地在高維空間建立分類面。因為在高維空間中的分類面更容易繞過一些低維空間中不可分的區域，這樣可以達到更好的分類效果。但是問題也是存在的，第一：使用核函數要求新樣本embed到核函數矩陣中，速度比較慢。第二：因為實際上使用了更高維度的特徵，容易因為訓練樣本少導致過擬合的問題。
SVM已經是很老的演算法了，最近的進展是使用稀疏（sparse）特徵+線性核做分類，比如之前用Fisher Vector做特徵在ImageNet比賽上做的實驗。效果甚至不輸於使用深度學習（deep learning）。
不過這兩年在ImageNet已經是深度學習一統天下了。SVM和神經網路真可謂三十年河東，三十年河西啊。

support vector machine 是一種分類的方法。
他是基於間隔最大化的一種監督分類學習方法。
他包括線性和非線性兩種模型。
可以加入核函數，來處理線性不可分的分類問題，唔，就是去處理非線性問題。

說到那個間隔最大化呢，就可以提到支持向量了。
匿名用戶那個圖示的分類問題。在邊界上的點就是支持向量。恩，每個英文縮寫的演算法的名稱都是非常直白的體現自己演算法最核心創新的部分的。svm和其他分類演算法的區別就在於他的核心是用到最大間隔的支持向量。
svm最有名的就是lin的libsvm。你可以用他的toy數據來建立個svm的直觀模型。LIBSVM -- A Library for Support Vector Machines

SVM思想很簡單，就是從樣本中找到分割線，為了評判那條分割線最好，引入了幾何間隔最大化的目標，之後所有的推導都是去解決目標函數的最優化上了。在解決最優化的過程中，發現了w可以由特徵向量內積來表示，進而發現了核函數，僅需要調整核函數就可以將特徵進行低維到高維的變換，在低維上進行計算，實質結果表現在高維上。由於並不是所有的樣本都可分，為了保證SVM的通用性，進行了軟間隔的處理，導致的結果就是將優化問題變得更加複雜，然而驚奇的是鬆弛變數沒有出現在最後的目標函數中。最後的優化求解問題，也被拉格朗日對偶和SMO演算法化解，使SVM趨向於完美。總結的很好。

看到一篇博客說的挺詳細的。

http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html

利用平面或者曲面（加核函數）在 R^n 空間中把兩組 labelled 數據分開。
不過作為一個外行，我一直覺得有一點比較迷；如果已經對各個 dimension 做 normalization，那麼加核的 svm 和 knn 之間會有多大的差別？

PS: 丟臉現場：我忘了 loss function 和 vector 有關，所以這個答案完全沒有碰到邊

這裡說的很贊：
http://onionesquereality.wordpress.com/2009/03/22/why-are-support-vectors-machines-called-so/

好像需要翻牆噢，我簡單整理下哈：

why svm"s called Machine ?

因為它是一種Learning Machine，按照Tom Mitchell的解釋：

A learning program is said to learn from experience E with respect to some task T and some performance measure P, if its performance on T, as measured by P, improves with experience E.

給定一個訓練集，我們能夠從假設空間中找出一個能夠更好的去擬合該訓練集的模型，輸出是一個決策函數或者某種分布。對於未知數據，通過這個模型就能得到輸出。這裡就產生了兩個問題：1、模型的準確度，也即對training sample的擬合程度，或者可以簡要理解為訓練得到的模型在訓練集上的誤差最小；2、模型的泛化能力，也即在未知數據集上的擬合能力。常見的機器學習方法一般在問題1上效果不錯，但是在測試集上的表現就取決於樣本數據是否均衡了。前者可以稱為經驗風險，兩者結合即結構風險。實際上現在很多模型也把第二個問題融入到模型中了，正則化也成了機器學習中比較重要的概念之一。
這裡有點疑問，如果svm本身就是結構風險最小化，為何在svm中都需要加入正則化項？

why svm"s called support vector ?

因為最後做出預測的不需要其他的樣本，只需要在分類決策面邊界上的樣本，而這些樣本構成了支撐向量。svm有這種獨特的性質，取決於在構建優化目標過程中使用的KKT條件。原文：

1. The most important data points are the support vectors as they have the maximum values of These points exert the maximum force on the decision sheet. This force exerted is constrained to be below C for any point in the non-separable case.
2. Since the torque exerted by the support vectors comes out to be zero, we can say that these specific data points are 「supporting」 the hyperplane into 「equilibrium」.

該模型的優化目標是，最大化分類的超平面和兩類數據的間距。

通過一堆公式計算後，神奇地發現，為了達到這個目標，和除了最近點以外的點都沒有關係。其實從幾何上也可以直觀地理解，所謂最大化間距，其實就是讓超平面距離兩個類的數據的最近點，最遠。而這些最近點，就被叫做支持向量。

點在幾何空間中的表示，可以看做向量。

什麼是機？什麼是向量？什麼是支持？機就是演算法的意思，為什麼不叫演算法叫機是因為一些歷史原因。向量就是向量，做分類的時候每個樣本都用一個向量表示。支持有撐起來，決定的意思。做分類的時候一般都是找到一個分類超平面（二緯的話是線），超平面一側是正類一側是負類。何為支持向量，就是決定了這個分類超平面的向量。所以可以這樣理解支持向量機：它是一個分類演算法，這個演算法是通過超平面進行分類的，這個超平面是由支持向量決定的。

雖然我不太懂，但我知道有一篇文章寫得很好，推薦題主看一看哦
支持向量機通俗導論（理解SVM的三層境界）

手機上搜的鏈接是

http://m.blog.csdn.net/article/details?id=38782399

凸二次規劃

譯為支撐向量機好理解點，就像萬惡的上下文context譯為環境你會死啊

如果只想停留在我大概知道SVM是個什麼想法，那看看最高票的答案就夠了，說不定還能使用現成的包做點東西出來。

但是如果真的想學會SVM，知道那些工具包里提供的那麼多選項對於你的結果有什麼影響，那還是老老實實去找本好的機器學習的書看一下，把SVM的公式都親自推一遍。

不要覺得裡面的數學難，其實SVM用到的數學知識可少了，一般比較好的機器學習書都會把需要的convex optimization還有矩陣微積分的那幾個公式列在附錄里，絕對超不過10頁紙。

Hahn Banach