SVM在線性不可分的情況下，利用核函數升維後就一定線性可分嗎？

12-12

SVM在線性不可分的情況下，利用升維使得其線性可分，那麼如何證明升維之後就一定線性可分？如果依然線性不可分怎麼辦？升維是指數級增長的，那麼SVM是怎麼處理維度災難的？

謝邀。
從原理上說，把高維向量映射到無窮維的hilbert空間以後基本線性可分了（也有線性不可分的情況！）。
但是，無窮維是沒法愉快的做內積的（svm的拉格朗日對偶就需要內積），所以我們可以搞一種東西叫正定核函數，由原來的向量直接做內積，再變換一下就知道hilbert空間的內積了——這也就是處理維度災難的原理。
我們再也不關心數據的維度，而是他們之間的內積了。內積的矩陣，叫Gram矩陣。
就是線性可分了，你這樣去分也沒什麼卵用——測試數據精度低成狗，所以有結構風險最小化。我得保證測試集也有不錯的精度。
要知道映射以後也不一定線性可分啊，舉個栗子，兩個一樣的向量有不一樣的label，不過沒關係，咱們還有個懲罰因子ξ嘛，允許幾個數據不可分也沒什麼不可。
很久不看svm了。
如果有錯漏，請指出，我可不想誤人子弟。

更多補充看評論。

升維後不一定線性可分，我們也不需要它線性可分。
不過一般情況下升維後會更接近線性可分，這就夠了。

我的結論：線性不可分情況下，投影到甚高維上會有好處，但可能依然線性不可分。

首先，你必須對 SVM 有比較深入的了解，依據 SVM 的性質，我們可以證明如下的誤差期望上界： $mathbb{E}{mathcal{L}_{test}} le frac{N_{SV}}{N}$ ,其中左側方程表示測試集上錯誤率的期望，右側 $N_{SV}$ 表示支持向量數目， $N$ 表示樣本總數。他的意義是：支持向量越多，測試集上錯誤率可能會越高。這其實很容易理解，如果數據離分界面很遠，那麼支持向量一般會很少，測試性能自然會不錯；反之，如果數據全部分布在分界面上，那表明數據纏繞很嚴重，測試集效果基本不靠譜。

回到我們的問題，在線性不可分情況下，一切線性不可分的樣本點，也就是 $xi_i ge 0$ 的樣本點，都可看做支持向量。你在一維情況下，毫無疑問的所有交疊的樣本點全部都是支持向量，這樣測試集錯誤率基本沒有保證，反之如果把這些交疊的樣本點投射到二維，他們中只有一部分會是支持向量，而其餘的交疊的樣本點，由於空間自由度的提高，他們的 $xi_i$ 會發生戲劇性的變化。如下圖，一維中那些交疊的點被投影到二維空間中，支持向量數目大大的減少了。依據我們上一段講解的測試集誤差期望和支持向量關係可知，測試集錯誤率期望大大下降。

利用高維投影是不是一定線性可分！答案是未必。
利用高維投影是不是一定保證更好的效果！答案亦然是未必。
高維投影通過增加空間靈活度，減少支持向量，提高了測試集上低錯誤率的保證。期望意義下，錯誤率會下降，但未必絕對。
核函數之後依然不能保證線性可分，所以還得要用軟邊際 SVM ， $u$ -SVM 等擴展方法。至於 SVM 如何處理維度災難，這個太基礎了，還請詳細閱讀文獻，而且別的答主已經說的很詳細了。如果題主對我說的這些內容比較感興趣，我推薦你一本書——Vapnik 《統計學習理論》，可能有些頗為難讀。

從是否導致線性可分的角度比較難分析。

下面這段注釋文字說得不對，我先搞明白再回來修改。
//Gaussian kernel確實被認為升維度到無限維（利用泰勒展開說明），
//說明高斯核能夠使得任意數據集可分的意思其實是指是用Gaussian kernel後數據可以被
//shattered，也就是說此時的VC-dimension是infinite的（所以可分），
//但是這個說明確實比較模糊。

更加直觀得認識Gaussian kernel的方式是直接觀察Gaussian kernel的形式： $K(x_1,x_2) = exp(-frac{|x_1 - x_2|_2^2}{delta})$ ，其直接作用就是定義了 $x_1$ 和 $x_2$ 的在高維空間的內積是由歐氏距離加上指數函數得到的，觀察指數函數的話，能看出，這個設定減小了這個歐式空間中大距離的差異（比如說，距離是10和100之間的差異被縮小，距離1和2之間差異被放大）。這個作用導致制定出的損失函數（比如dual svm的損失函數）對離support vector近的樣本非常敏感而遠的不敏感。當一類數據出現明顯的聚集情況的時候（比如：形成一個環），很容易被分割出來。

因此，Gaussian kernel至少是對這一類數據特別有效。

SVM在線性不可分的情況下，利用升維使得其線性可分，那麼如何證明升維之後就一定線性可分？
沒有任何理論支持升維將使得線性不可分的數據線性可分。
如果依然線性不可分怎麼辦？
換一種映射（升高維度或者僅僅是改變映射方式），有人（具體哪一個記不太清了）稱將低維數下數據映射到足夠高的維數下，數據線性可分的概率會上升（上升趨勢好像沒有說明）。
如果僅僅應用於分類的話實際上支持向量機是有一個鬆弛因子的，專門用來針對非嚴格線性可分的情況。
升維是指數級增長的，那麼SVM是怎麼處理維度災難的？
支持向量機的核函數作用是就是降低了計算的複雜度。

Vapnik和Shapire他們從來沒說過映射後一定線性可分，但如果假定數據本身無雜訊（比如樓上說的同樣樣本不同標籤），那麼理論上是會存在一個核函數，使得映射後的數據線性可分。

但這裡又是一個數學理論為我們挖好的大坑：怎樣才能找到這個神奇的核函數呢？

我不知道，作者們也不知道，整個領域的學者們也不知道。如果有人能找到一個有效的系統化的方法，那將是為推動人工智慧領域發展做出的巨大的貢獻。

這是個正好懂點的問題，試答一下。
先從頭捋：
如果線性可分，那麼感知機一定可以找到分界面。
SVM引入懲罰因子，相比感知機，SVM要求不止分得對，而且分得好(分得好，就是large margin, 簡單理解就是抗高斯雜訊)，這個SVM叫hard-SVM, 有對偶(via 強對偶條件，KKT)和primal解法(via QP)。

這裡先說維度災難。
核函數在對偶表示里引入。所說的無窮維升維，舉個栗子，高斯核可以展開成無窮級數。維度高了，即容易過擬合。抑制過擬合，SVM也沒什麼特殊的，和logistic regression一樣，PRML開頭就講了。基本原則就是不讓w的值過大(限制模型的variance)，這樣輸出趨於穩定，泛化性更好。

下面到線性不可分。
數據線性不可分，那hard-SVM中的「分得對」就做不到了，「分得好」的標準也得改。改進的方法，從理解的角度來說，就是在犯了多少錯誤的情況下，可以分得對。(統計合計犯了多大的錯誤 via margin violation)。為了區分，這個叫做soft-SVM. 它是專門應對線性不可分數據的。

題主的問題我們轉化一下看，把是不是任何非線性數據，用SVM一定可分，轉化為soft-SVM可以構建任意複雜的分類超平面。經驗的說法，通過核函數極其參數選擇，可以構建很複雜，相當複雜，極其複雜的超平面。具體情況確實要結合數據說。

題外話，個人認為SVM有一點局限就是它限定一定要劃一個平面來分類(比如二分類，sign(w"x＋b))，如果有很多的sub clusters，其表現可能不如random forest)。

車上答題，如有錯誤，忘指正

不一定線性可分，你用核函數只是希望在非線性核函數的基表示下，線性可分而已。總存在及其奇怪的構造case。。。

當然不是.
Exp. X_1=X_2, Y_1!=Y_2

升維太高，容易過擬合

由線性不可分變成線性可分是特徵空間變換做的事情，而核方法只是將特徵變換的過程變得更加容易。這樣SVM就可以就可以將原始特徵空間映射到更高維(成百上千乃至無窮維的hilbert空間)。

另外，使用了特徵變換一般是可以保證變換之後的數據是線性可分的，然而並不能保證它的泛化能力。也就是說你可能找到了一條完美的超平面可以將原始數據在新的特徵空線性可分，然而該分類面可能受極少部分點的影響特別大，以至於在訓練樣本之外不能得到很好的預測效果。例如下圖：

右圖中的最上方的圓圈導致最大邊緣分類面偏離了。嚴格限制分類條件，可能會為了這極少的點而降低泛化能力。這裡就需要引入鬆弛的概念，放寬對分類面的限制：允許一部分點被誤分。 SVM具體的解讀可以看這篇文章：Support Vector Machine

1目前無法證明。我認為也不可能證明。kernel的選擇也沒有嚴格的理論指導，只有經驗結論。
2參見其他答案
3不是SVM如何處理維數災難，svm是個分類器，而是kernel處理了維數災難。kernel跟svm不綁定呀。

當你知道有Bayes Loss這玩意之後，你就不會這麼想了

我也提過類似的問題，希望能有所幫助吧。
如何理解在二維空間內線性不可分的數據，可以在五維空間內線性可分？ - 機器學習

如果高斯kernel則一定是線性可分的（因為相當於在一個無限維空間中進行分類）