機器學習有很多關於核函數的說法，核函數的定義和作用是什麼？

11-15

機器學習，具體以RBF網路裡面的核函數為例，有評論說是通過徑向基核函數可以把原始數據投影到更高維的空間里去（從而增加數據可分的概率），對於這種說法，實在不是很理解（怎麼就投影到高維空間裡面去了呢）？求解釋

最近，自己整理了一下筆記，可參考：專家坐堂：機器學習中對核函數的理解，望各位批評和指正

為了幫助大家梳理思路，我要寫一個更加嚴謹的回答：

0. kernel在SVM中的應用真心只是冰山一角，做kernel的人基本不關心這個問題，就像用SVM的人也不關心kernel是啥一樣。

1. kernel 和 SVM 完全是兩個正交的概念，早在SVM提出以前，reproducing kernel Hilbert space（RKHS）的應用就比較廣泛了。一個經典的例子就是信號處理中signal detection的問題：給一條time series我如何知道它不是一個random walk的噪音而是有一個特定的pattern在裡面呢？在這個情景下，RKHS理論就給出了一個通過現實求解likelihood ratio的假設檢驗方案，其中的kernel實際上是某個隨機過程 R(t) 在兩個不同時間點的correlation。

2. 很多人覺得kernel定義了一個從低維度到高維度的映射，這是不準確的。首先，並不是所有空間都像歐式空間那樣有所謂「維度」的良好定義，很多空間是沒有維度的意義的，或者可以認為維度都是無窮大，這樣就無法區分不同的RKHS了。但是kernel確實可以定義一個映射，而且確實是一個非常強大的映射，很多方法在這個映射下是可以直接推廣到kernel space的，包括SVM，logistic regression, least squre，dimension reduction。

3. 那麼這個映射是什麼呢？我略過數學的setup（估計也沒有人看）簡單講講RKHS是什麼一個故事：實際上RKHS的定義是反過來的，首先在原空間上考慮所有連續函數，這些連續函數可以做加法和數乘，所以真主給他們（中的一部分）施加一個內積結構，比如所有二階多項式其係數在歐式空間展開構成的內積就是高票主提供的例子；這個內積實現中的一部分就可以對應到原空間中的兩兩之間點的kernel。所以RKHS是先有內積才有kernel的，但是另個一個牛逼的定理說，只要kernel滿足一些條件，就存在這樣一個（唯一的）內積結構與之對應。（其實這部分的數學，一個普通大學數學系的本科生就能看懂了或者學過了，並不是什麼高深的內容）

4. kernel有什麼作用？kernel不僅可以建立點對點的映射（如SVM那樣），還可以建立原空間上一個分布對點的映射，有興趣的讀者請谷歌 kernel embedding of distributions。在這一個映射下，人們會關心這麼一個問題，給兩組數據，我如何知道他們是不是從同一個分布中來的呢？在kernel map下，兩組數據被map成了kernel space的兩個點，我們可以看看在那個空間里他們距離是遠還是近，如果很近就很可能是同一個點加上一點sample variance，以此來判斷兩組數據是不是同一個分布（two sample test）。

5. 最後談一談不同的核函數，應用中最常見的估計就是RBF kernel了比如Gaussian kernel，這類kernel的強大之處在於他們提供的embedding space非常豐富（當然有人可以理解為維度非常高，但是既然是無窮維，談維度已經沒有意義了），以至於原空間中不同的分布可以被直接map到不同的點，這類kernel有個名字叫characteristic kernel。回到我們最初的kernel 定義到底什麼樣的kernel才能reproduce如此豐富的embedding 空間呢？答案是能把整個連續函數空間填滿(dense)的kernel。比如一般的多項式kernel就不行，因為二階多項式的線性組合不能表示更高階的多項式函數了。這種能把整個連續函數空間填滿的kernel，叫universal kernel。一個重要的結果是universal kernel就是characteristic kernel，換句話說只要你能把連續函數空間填滿，那麼原空間上不同的分布在這個map下都會變成不同的點。

說了這麼多，我只想吐槽初學者太容易被幾個大牛寫的tutorial忽悠了，我剛學SVM的時候也不知道原來kernel是一個獨立的概念，直到很多年後＝。＝吃了很多虧才長了一點姿勢。

最後補一個最近剛看到的視頻，裡面對kernel machine的應用講的比較全面(大家可以注意一下台下都有誰。。）：https://royalsociety.org/events/2014/11/milner-lecture/

我來舉一個核函數把低維空間映射到高維空間的例子。

下面這張圖位於第一、二象限內。我們關注紅色的門，以及「北京四合院」這幾個字下面的紫色的字母。我們把紅色的門上的點看成是「+」數據，紫色字母上的點看成是「-」數據，它們的橫、縱坐標是兩個特徵。顯然，在這個二維空間內，「+」「-」兩類數據不是線性可分的。

我們現在考慮核函數 $K(v_1,v_2) = <v_1,v_2>^2$ ，即「內積平方」。
這裡面 $v_1=(x_1,y_1), v_2=(x_2,y_2)$ 是二維空間中的兩個點。

這個核函數對應著一個二維空間到三維空間的映射，它的表達式是：
$P(x,y)=(x^2,sqrt{2}xy,y^2)$
可以驗證，
$egin{align} <P(v_1),P(v_2)> = , <(x_1^2,sqrt{2}x_1y_1,y_1^2),(x_2^2,sqrt{2}x_2y_2,y_2^2)> \ = , x_1^2x_2^2 + 2x_1x_2y_1y_2+y_1^2y_2^2 \ = , (x_1x_2 + y_1y_2)^2 \ = , , <v_1,v_2>^2 \ = , K(v_1,v_2) end{align}$

在P這個映射下，原來二維空間中的圖在三維空間中的像是這個樣子：

（前後軸為x軸，左右軸為y軸，上下軸為z軸）

注意到綠色的平面可以完美地分割紅色和紫色，也就是說，兩類數據在三維空間中變成線性可分的了。

而三維中的這個判決邊界，再映射回二維空間中是這樣的：

這是一條雙曲線，它不是線性的。

================================================

如上面的例子所說，核函數的作用就是隱含著一個從低維空間到高維空間的映射，而這個映射可以把低維空間中線性不可分的兩類點變成線性可分的。

當然，我舉的這個具體例子強烈地依賴於數據在原始空間中的位置。
事實中使用的核函數往往比這個例子複雜得多。它們對應的映射並不一定能夠顯式地表達出來；它們映射到的高維空間的維數也比我舉的例子（三維）高得多，甚至是無窮維的。這樣，就可以期待原來並不線性可分的兩類點變成線性可分的了。

================================================

在機器學習中常用的核函數，一般有這麼幾類，也就是LibSVM中自帶的這幾類：
1) 線性： $K(v_1,v_2)=<v_1,v_2>$
2) 多項式： $K(v_1,v_2)=(gamma<v_1,v_2>+c)^n$
3) Radial basis function： $K(v_1,v_2)=exp(-gamma||v_1-v_2||^2)$
4) Sigmoid： $K(v_1,v_2)= anh(gamma<v_1,v_2>+c)$

我舉的例子是多項式核函數中 $gamma=1, c=0, n=2$ 的情況。

在實用中，很多使用者都是盲目地試驗各種核函數，並掃描其中的參數，選擇效果最好的。至於什麼樣的核函數適用於什麼樣的問題，大多數人都不懂。很不幸，我也屬於這大多數人，所以如果有人對這個問題有理論性的理解，還請指教。

================================================

核函數要滿足的條件稱為Mercer"s condition。

由於我以應用SVM為主，對它的理論並不很了解，就不闡述什麼了。

使用SVM的很多人甚至都不知道這個條件，也不關心它；有些不滿足該條件的函數也被拿來當核函數用。

謝邀

詳細的公式什麼的，網路上搜索kernel function, kernel methods 有很多，我就不仔細說了，簡單地說說背後的intuition。

intuition也很簡單，比如我們有一個一維的數據分布是如下圖的樣子，你想把它用一個直線來分開，你發現是不可能的，因為他們是間隔的。所以不論你畫在哪，比如綠色豎線，都不可能把兩個類分開。

但是我們使用一個簡單的升維的方法，把原來一維的空間投射到二維中，x-&>(x, x^2)。比如:
0-&>(0,0)
1-&>(1,1)
2-&>(2,4)

這時候就線性可分了

再舉個例子，在一個二維平面裡面，這樣的情況是不可能只用一個平面來分類的，但是只要把它投射到三維的球體上，就可能很輕易地分類。

理論上，由於train set是有限的，當你把data投射到無限維度的空間上是一定可以在train set上完美分類的，至於在test set上當然就呵呵了。

記得要選取合適（試試各種）kernel function來「避免過擬合」。

核函數就是內積。

故事應該從一個簡單的二維世界講起。從前有一個世界X，X裡面有很多很多的數據點，這些數據點屬於兩個幫派，正類和負類。正類點居住在y軸右邊，負類點居住在y軸左邊，他們以y軸為分界線，涇渭分明，互不侵犯。

突然有一天，不知道是X紀年的幾年幾月幾日，負類開始大舉進攻正類領地的第四象限。正類很快失去了很多領地，又被迫簽訂了和平條約，從此X世界的居民們發現了一個問題，他們不能再用y軸作為國界了！

還好，在負類點中有一位聰明的數學家，他發現兩國的地盤可以用一條直線分開，把平面上每一點坐標放進直線方程ax+by+c里，如果大於零，這就是正類的領地，小於零是負類的領地，中間這條線後來被命名為分類面，於是X世界裡第一個線性分類器誕生了。有了數學的幫助，X世界太平了很多年。

然而好景不長，貪得無厭的負類君主再一次發起了遠征，這一次他們佔領了第一象限之外的大量領土，吞併了整個第四象限。然而由於進軍過於激進，導致戰線過長，負類遠征的腳步也不得不停滯於此，開始休養生息。但是國界怎麼辦呢？

聰明的數學家苦思冥想，發現這麼一個事實：之前兩國的分類面是直線時，分類面可以用分類面兩側的兩個點（兩點中垂線是分類面）表示。如果叫這兩個點(x+,y+),(x-,y-)的話，那麼正類領地的所有點和(x+,y+)的內積都大於它們和(x-,y-)的內積；反之對負類領地也成立。數學家還發現，對於任意一群世界X中的點，(x+,y+)和(x-,y-)都能表示成它們的線性組合，對於一個新來的點，它和這兩個點的內積就可以表示成所有點和所有其它點的內積的加權和。所以給定一些兩個國家的點之後，我們可以計算兩兩點之間的內積，並把分類面表達成這些內積的線性加權和。後來人們把這些點的內積放在了一個矩陣里，並叫它核矩陣，核矩陣定義了世界的分類。在這個核矩陣里，矩陣里每個點的值是兩個X世界點的線性內積，它定義的分類面在原來的X世界裡是一條直線，所以這個核矩陣後來被成為線性核矩陣，而以兩個點生成矩陣中每個點的映射被成為線性核函數。

這個發現可不得了。等數學家發現這一點之後，負類的領地已經進一步擴張了，現在正類的領地已經只剩下第一象限里一個拋物線的內部了。但有了新的核理論，這個國界問題難不倒數學家，他定義了一個映射，把X世界的點映射到
$phi([x;y])=[1;x;y;xy]$
的四維世界，把這個世界的內積定義為新的核函數，在兩個類的領地分別取了幾個點作為基礎之後，一個拋物線的分類面就被定義了出來。這是X世界裡第一個被成功推導並得到公認的非線性分類面，而這裡用到的核函數是上述映射的內積，也就是點坐標的多項式表示，所以這個核函數（矩陣）又被稱為多項式核函數（矩陣）。

歷史總是一遍遍重演，但這一次正類將歷史推動到了前所未有的境地。X紀年若干年後的某一天，負類境內的第三象限突然因為正類策反發生嘩變，同時正類也大舉進攻第一象限的負類領地，希望收復失地。經過若干年的戰爭，最後兩類將領地用第一、三象限的兩條雙曲線隔開，負類保有包括原點在內的第二、四象限和坐標軸附近的區域；正類則佔領了第一、三象限的大部分。

現在的問題是，這麼一來國界要怎麼劃分呢？

這回一個來自正類世界的懶惰的數學家想到了一個基於核方法的解決方案：我們不如跳過映射和內積的步驟，直接定義一個核函數吧！這種異想天開的方法被負類數學界嗤之以鼻，但在正類卻大獲成功。很快正類的數學家們發現兩點之間距離的平方的指數的倒數（其實沒這麼複雜，就是正比於兩點距離所定義的高斯概率）是一個不錯的核函數，這樣在分類面附近兩類中分別選一些點，就可以定義任意的非線性分類面了。為了紀念這個偉大的正類數學家，後世用這位數學家生平最喜歡的三種食物：拉麵、牛肉和和薯條命名了這個核函數，稱之為RBF核（誤）。

這個發現為推動後來兩類數學界的統一做出了巨大的貢獻，而發明RBF核的數學家也因為一句「數學家是有分類的，但數學是無分類的」的名言獲得了菲爾茨和平獎（誤）。

至於內積？後來有負類的數學家研究了一下RBF核是否對應一個向量映射，結果是如果想把RBF核表達成一個向量內積，我們需要一個映射將向量映射到一個無窮維的線性空間去。發現了這一點的數學家又發展了Mercer定理和重建核希爾伯特空間（Reproducing Kernel Hilbert Space）理論，但這就是另外一個故事了。

=======================

故事都是扯淡的，但數學道理大概是這麼個回事兒，看看就好莫認真…

關於這點的誤解實在太多。

核函數和映射沒有關係。核函數只是用來計算映射到高維空間之後的內積的一種簡便方法。

一般英文文獻對Kernel有兩種提法，一是Kernel Function，二是Kernel Trick。從Trick一詞中就可以看出，這只是一種運算技巧而已，不涉及什麼高深莫測的東西。

具體巧在哪裡呢？我們如果想進行原本就線性不可分的數據集進行分割，那麼選項一是容忍錯誤分類，即引入Soft Margin；選項二是我們可以對Input Space做Feature Expansion，把數據集映射到高維中去，形成了Feature Space。我們幾乎可以認為（引用Caltech的課堂用語「We are safe but not certain」）原本在低維中線性不可分的數據集在足夠高的維度中存在線性可分的超平面。

圍繞選項二，那麼我們所做的就是要在Feature Space套用原本在線性可分情況下的Input Space中使用過的優化方法，來找到那個Maximaizing Margin的超平面。原理機制一模一樣，是二次規劃，唯一不同是代入數據的不同，我們需要代入 $phi(x_i)$ 而不是 $x_i$ 。這時（在假設我們已知了如何選取mapping之後）才有了核函數的概念。

具體Trick的意義，就是簡化計算二次規劃中間的一步內積計算。也即中間步驟有一步必須求得 $phi(x_i)$ ，而我們可以定義核函數 $K(x_i,x_j)=phi(x_i)$ ，使得我們在不需要顯式計算每一個 $phi(x_i)$ 、甚至不需要知道 $phi(cdot )$ 長什麼樣的情況下，直接求出 $phi(x_i)$ 的值來。

也就是說，核函數、內積、相似度這三個詞是等價的。因為inner product其實就是一種similarity的度量。核函數和映射是無關的。

但為什麼這麼多的認知中核函數是一種映射呢。一來這兩件事一般先後進行，所以常常被混為一談。二來就像前面所述，核函數讓人們不需要知道 $phi(cdot )$ 長什麼樣，不需要知道怎麼選取映射，就能夠算出內積。因此這常常被認作是一種implicit mapping。這是由Mercer Theorem保證的，即只要核函數滿足一定條件，那麼映射空間一定存在。

其實吧，核函數提供了數據點間兩兩的相似信息（並不嚴格）。如果把歐式空間上兩點之間的內積作為他們是否相似的評判標準的話，核函數就是其直接拓展。注意，這裡所謂的相似並不是嚴格意義下的，只是一種很粗糙的解讀。

而很多機器學習的演算法，比如（dual）svm,其實只用到了數據間的相似信息（linear SVM只用到內積），所以這就提供了一種系統性的擴展方式：把內積換成其他的核函數！

當然了，想從理論的角度很好的理解核函數需要將其理解成一個兩步的方法，1）將原數據映射到另一個（低維高維無窮維）空間；2）在那個空間上做內積。這對核函數的選擇造成了限制，但是實際中，下蛋的母雞才是好母雞，你可以任意選擇效果好的核函數！

對於 @陳然的例子，映射是 x -&> (x,x^2), 那麼等價的核函數就是 k(x,y) = x*y+x^2*y^2. 而很多時候，我們只需要核函數，而不需要那個映射，也無法顯式的寫出那個映射（當然，如果你想分析解釋學到的分類器的話，這就會給你造成麻煩）

註：並非Kernel Method Researcher, 理解難免有偏頗，見諒。

核函數只是滿足某些必要條件的函數，其作用要與具體的演算法結合才能顯示出來。

我來簡明說一下SVM中核技巧(kernel trick)的作用，一句話概括的話，就是降低計算的複雜度，甚至把不可能的計算變為可能。

核函數有如下一個性質：

$K(x_1,x_2) = phi (x_1)*phi(x_2)$
其中 $phi(x)$ 是對 $x$ 做變換的函數，有些變換會將樣本映射到更高維的空間，如果這個高維空間內 $x_1$ 與 $x_2$ 是線性可分的，那麼我們就做了一次成功的變換。核函數是二元函數，輸入是變換之前的兩個向量，其輸出與兩個向量變換之後的內積相等（這個性質非常重要）

而我們知道，求解SVM時，其原始形式(這裡我們假設已經對原始的輸入做了變換，即輸入模型的樣本變成了 $phi(x)$ )

$frac{1}{2}w^{T}w + Csum_{1}^{N}{eta_i}$
st.
$y_i(w^{T}phi(x_i)+b) geq 1 - eta_i$

$eta_i geq 0$
i = 1 , 2... N(N為樣本個數)

這是個二次規劃，因為未知量的個數是參數w的維度，而w的維度與樣本的維度相等，即等於變換後的 $phi(x)$ 的維度，所以其求解複雜度與樣本的維數正相關，這意味著，如果我們把原始樣本從十維空間變換到一萬維的空間，那麼求解該問題的時間複雜度提升了1000倍或者更多，我們知道有些變換可以將樣本換邊到無窮維空間，那麼這種變化之後直接是不可求解的。
上面的問題可以使用對偶 + 核技巧的組合來解決。

我們也知道，SVM原始形式的對偶問題是：

$sum_{i=1}^{N}sum_{j=1}^{N}{alpha_ialpha_jy_iy_jphi(x_i)^{T}phi(x_j)} - sum_{i=1}^{N}{alpha_i}$
st.
$0leqalpha_ileq C$
$sum_{i=1}^{N}{y_ialpha_i} = 0$

很明顯，未知量 $alpha$ 的個數與樣本的個數是相等的，那麼這個對偶問題計算的時間複雜度是與訓練樣本的個數正相關的(這也是為啥樣本個數太多的時候不推薦使用帶核技巧的SVM的原因)。
僅僅做對偶還沒有解決問題，因為在 $sum_{i=1}^{N}sum_{j=1}^{N}{alpha_ialpha_jy_iy_jphi(x_i)^{T}phi(x_j)} - sum_{i=1}^{N}{alpha_i}$ 中還要求 $phi(x_i)^{T}phi(x_j)$ ，這就需要將樣本先變換到高維空間，然後再求在高維空間內的內積，這樣的變換還是需要很多計算資源。等等，我們說過核函數的作用是「核函數是二元函數，輸入是變換之前的兩個向量，其輸出與兩個向量變換之後的內積相等」，所以我們可以用 $K(x_i,x_j)$ 來代替 $sum_{i=1}^{N}sum_{j=1}^{N}{alpha_ialpha_jy_iy_jphi(x_i)^{T}phi(x_j)} - sum_{i=1}^{N}{alpha_i}$ 中的 $phi(x_i)^{T}phi(x_j)$ ，避免了顯式的特徵變換。
於是，使用對偶+核技巧，我們成功解決了問題。

使用核技巧之後，學習是隱式地在特徵空間進行的，不需要顯式地定義特徵空間和映射函數(李航)

還有一個問題，就是對新樣本預測的時候怎麼辦？眾所周知，SVM學習出來的權值 $w$ 是支撐向量（所謂支撐向量就是對應的 $alpha_i$ 不為0的樣本）的線性組合，即 $w=sum_{i=1}^{N}{alpha_iy_iphi(x_i)}$ ,所以求解 $f(x) = w^{T}phi(x)+b$ 也可以使用核技巧，來避免顯式地變換。即 $f(x) = w^{T}phi(x) + b = sum_{i = 1}^{N}{alpha_iy_iK(x_i,x)} + b$

這麼看，SVM和核技巧簡直是天作之合！

參考資料：
《機器學習技法》（https://www.youtube.com/playlist?list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2）
統計學習方法

同意@文鴻郴的說法「核函數和映射沒有關係」，還有 @Xi Yang的截圖。
根據Mercer"s_theorem，我們可以知道任意滿足核函數可以表示成某個Hilbert space 上的內積，同樣只要滿足定理條件的函數都可以通過定義Hilbert space 上的內積來構造核函數。

當然核函數在金融機器學習中可以看作一些時間序列相關性的度量，這個只是一個應用罷了，並不是核心解釋。另外我們知道核函數對於機器學習至關重要的，也正因此可以選擇合適的核函數進行機器學習，當然每個領域都有一些適合每個領域自己的核函數。通過Mercer"s_theorem，當然我們也可選擇適合的函數，通過內積的方式去構造適合某個特定領域的核函數以達到較為良好的學習效果。

其實這些在eproducing kernel Hilbert space（RKHS）中有比較性詳細的解釋。

另外，在直觀解釋我在另一個回答上有詳細的。
機器學習里的kernel是指什麼？ - 驀風的回答

先看人話版：SVM，Kernel

再看科幻版：

RBF 核函數怎麼就投影到高維空間裡面去了呢

要徹底解決「怎麼就投影到」這個問題，我想最好的（唯一的？）辦法就是把這個到高維空間的特徵映射求出來，要看結果的直接拉到最後。不過在跳進數學的海洋之前，我們先回顧一下SVM

SVM 基礎回顧

SVM 的分類函數:

$f(mathbf{x}) = sign(sum_ialpha_i mathbf{x_i} cdot mathbf{x} + mathbf{b})$

對於所有 $alpha_i eq 0$ 的 $i$ , $mathbf{x_i}$ 就是支持向量 (support vector)，或者說，比較難分類的點。例如在性別分類的問題中，就是那些「不男不女」的臉。對於一個新的數據點，我們只需要關心這個數據點和所有支持向量的點積，然後線性組合一下，就可以算出這個分類函數的值。

有些時候，訓練集不是線性可分的，但是可以通過映射到高維空間中進行線性分割。

我們就需要在高維空間中計算分類函數：

$f(mathbf{x}) = sign(sum_ialpha_i mathbf{varphi(x_i)} cdot mathbf{varphi(x)} + mathbf{b})$

幸運的是，我們其實並不需要高維空間中的向量，而只是高維空間中兩個向量的點積。定義函數 $K$ 使得: $K(mathbf{x_1}, mathbf{x_2}) = mathbf{varphi(x_1)} cdot mathbf{varphi(x_2)}$

高維空間中的分類函數就變成了：

$f(mathbf{x}) = sign(sum_ialpha_i K(mathbf{x_i}, mathbf{x})+ mathbf{b})$

所以選擇對高維空間的映射，就相當於選擇函數 $K$ 。計算在高維空間中的分類，就相當於用函數 $K$ 代替原來的向量點積。無論是選還是算，都只和函數 $K$ 有關。至於高維空間的映射究竟是什麼，其實不重要。哦對了，這個函數 $K$ 有一個名字，叫做核函數 (Kernel Function)。

不過有時候算算映射究竟是什麼，也有助於更好得理（zhuāng）解（bī）。既然這裡題主問到RBF核函數的特徵映射是什麼，激發了我的好奇心（隨手推了一下，哪知道這麼複雜！），那我就正好回答一下吧！在求 RBF 核函數的特徵映射之前，我們先要求多項式核函數（Polynomial Kernel）的特徵映射。

多項式核函數的特徵映射

多項式核函數: $K_d(mathbf{x_1}, mathbf{x_2}) = (mathbf{x_1}^Tmathbf{x_2})^d$

尋找 $mathbf{Phi}_d(mathbf{y})^Tmathbf{Phi}_d(mathbf{x}) = K_d(mathbf{x}, mathbf{y}) = (mathbf{y}^Tmathbf{x})^d = (sum_{i=1}^{n}x_iy_i)^d$

根據多項式定理 (Multinomial theorem)
$(x_{1}+cdots +x_{m})^{n}=sum _{{|alpha |=n}}{n choose alpha }mathbf{x}^{alpha }, alpha = (alpha_1,alpha_2, cdots,alpha_m)$

這裡用到了三個記號,
$|alpha| = sum_{i=1}^malpha_i,$

$mathbf{x}^alpha = x_1^{alpha_1}x_2^{alpha_2}cdots x_m^{alpha_m},$

${n choose mathbf{alpha} } = {n choose alpha_1,alpha_2,cdots,alpha_m } = frac{n!}{alpha_1!alpha_2!cdotsalpha_m!}$

帶入上面的式子，

$egin{align} mathbf{Phi}_d(mathbf{y})^Tmathbf{Phi}_d(mathbf{x}) = (sum_{i=1}^{n}x_iy_i)^d \ = sum _{{|alpha |=d}}{d choose alpha }mathbf{x}^{alpha }mathbf{y}^{alpha }\ = sum _{{|alpha |=d}}sqrt{{d choose alpha }}mathbf{x}^{alpha }sqrt{{d choose alpha }}mathbf{y}^{alpha }\ = langle sqrt{{d choose alpha}} mathbf{y}^alpha angle^T langle sqrt{{d choose alpha}} mathbf{x}^alpha angle, forall |alpha|= d end{align}$

於是我們找到了d次多項式核函數的特徵映射：
$mathbf{Phi}_d(mathbf{x}) = langle sqrt{{d choose alpha_1, alpha_2, cdots, alpha_n }} x_1^{alpha_1}x_2^{alpha_2}cdots x_n^{alpha_n} angle , forall sum_{i=1}^n alpha_i= d$

考慮簡單的情況做個驗證:

$n=2, d=2$ 時
$mathbf{Phi}_2(langle x_1, x_2 angle) = langle x_1^2, x_2^2, sqrt{2}x_1x_2 angle$

$n=2, d=3$ 時
$mathbf{Phi}_3(langle x_1, x_2, x_3 angle) = langle x_1^3, x_2^3, x_3^3, sqrt{3}x_1^2x_2, sqrt{3}x_1^2x_3, sqrt{3}x_2^2x_1, sqrt{3}x_2^2x_3, sqrt{3}x_3^2x_1, sqrt{3}x_3^2x_2, sqrt{6}x_1x_2x_3 angle$

上面的圖片也就是一個把向量從2維投影到3維的例子。

RBF 核函數的特徵映射: $K(mathbf{x_1}, mathbf{x_2})= exp(-frac{||mathbf{x_1}-mathbf{x_2}||^2}{2sigma^2})$

尋找 $mathbf{Phi(x)}$ 使得 $K(mathbf{x},mathbf{y}) = mathbf{Phi(y)}^Tmathbf{Phi(x)}$

$mathbf{Phi(x)}$ 就是我們要尋找的從低維到高維的映射函數。

$egin{align} K(mathbf{x}, mathbf{y}) = exp(-frac{||mathbf{x}-mathbf{y}||^2}{2sigma^2})\ = exp(-frac{1}{2sigma^2}(mathbf{x}-mathbf{y})^T(mathbf{x}-mathbf{y}))\ = exp(-frac{1}{2sigma^2}(mathbf{x}^Tmathbf{x} + mathbf{y}^Tmathbf{y}- 2mathbf{y}^Tmathbf{x}))\ = exp(-frac{1}{2sigma^2}(||mathbf{x}||^2+||mathbf{y}||^2))cdot exp(frac{1}{sigma^2}mathbf{y}^Tmathbf{x})\ = C cdot exp(frac{1}{sigma^2}mathbf{y}^Tmathbf{x})\ = C cdot sum_{i=0}^{infty}frac{(frac{1}{sigma^2}mathbf{y}^Tmathbf{x})^i}{i!}\ = sum_{i=0}^{infty}frac{C}{sigma^{2i}i!}(mathbf{y}^Tmathbf{x})^i\ end{align}$

因此，RBF Kernel 是所有多項式核函數的線性組合。其實到這裡就已經可以看出RBF所對應的特徵映射函數就是由多項式核函數所對應的特徵映射函數組合而成。不過既然都寫了這麼多了，乾脆一口氣把準確的表達式也寫出來吧。

定義 $a_k= sqrt{frac{C}{sigma^{2k}k!}}$ , 其中 $C = exp(frac{||mathbf{x}||^2+||mathbf{y}||^2}{-2sigma^2})$

結合 $mathbf{Phi}_k(mathbf{y})^Tmathbf{Phi}_k(mathbf{x}) = (mathbf{y}^Tmathbf{x})^k$ ，我們得到，

$a_kmathbf{Phi}_k(mathbf{y})^Ta_kmathbf{Phi}_k(mathbf{x}) = frac{C}{sigma^{2k}k!}(mathbf{y}^Tmathbf{x})^k$

帶入 $K(mathbf{x}, mathbf{y})$ 得到，
$egin{align} K(mathbf{x}, mathbf{y}) = sum_{i=0}^{infty}frac{C}{sigma^{2i}i!}(mathbf{y}^Tmathbf{x})^i\ = sum_{i=0}^{infty}a_imathbf{Phi}_i(mathbf{y})^Ta_imathbf{Phi}_i(mathbf{x})\ = mathbf{Phi(y)}^Tmathbf{Phi(x)} end{align}$

其中，
$mathbf{Phi(x)} = langle a_0mathbf{Phi}_0(mathbf{x}), a_1mathbf{Phi}_1(mathbf{x}), a_2mathbf{Phi}_2(mathbf{x}), cdots angle$

Oh yeah！搞定了！我們最終找到了這個無限維向量的明確定義（擦汗-_-\）。但這裡還是不得不回到前面的話，我們其實完全不需要在意這個核函數對應的高維映射是什麼，也不用去計算高維映射。直接拿核函數來用就行了！我們只需要計算核函數，就相當於計算了在高維空間中的點積，從而相當於在高維空間中做了劃分。簡單粗暴，這就是它的美妙之處。

以上內容在我們的機器學習中有詳細的視頻講述。偏好視頻講解的同學們也可以去那裡看看。

同意@文鴻郴的說法「核函數和映射沒有關係」。實際中我們根本就不知道映射到底是什麼形式的。我們一般就略過這一步，直接計算映射後的值（通過核函數）。然而這點並不與 @王贇 Maigo 說的矛盾， @王贇 Maigo 把映射列舉出來能夠更好的闡述。

核函數的本質就是高維空間中兩個向量的內積。

看到校友貼了Yiming Yang的Slides，我也貼一張701的Slide：

翻譯：核函數是在集合X上定義的函數K，從X^2映射到實數（應為非負實數）

翻譯：核函數是在集合X上定義的函數K，從X^2映射到實數（應為非負實數）
核函數表示高維空間的一種內積。

核函數必須滿足對稱性(K(x,y) = K(y, x))及半正定性(K(x,y)&>=0)。根據Mercer"s_theorem，我們知道任何滿足對稱性和半正定型的函數都是某個高維希爾伯特空間的內積。

主要思想就是一個feature map，然而現在這種map不如deep learning generate出來的好用=。=

kernal主要作用就是把低維度的非線性空間映射到高維度的線性空間。

找個地方記錄一下最近學習心得。這裡可以打公式，是個不錯的選擇。

--------------------------------------------------------

SVM是什麼？

首先在某個數據集上，通過某種演算法（如何解SVM是下一步學習目標，這裡不討論）找到一個最優（結構化風險最小，也就是max margin）的超平面 $p$ ，該平面的特徵向量 $n$ 就是支持向量support vector（嚴格來說， $n$ 只是定義了方向。超平面還有另外一個特徵截距 $b$ 這裡省略了）；預測階段就是求待預測向量 $x$ 與 $p$ 的位置關係（在 $p$ 的一側還是另一側，距離 $p$ 有多遠）。所以不嚴格來說，SVM是 instance-based learners，這裡的instance就是support vector。

假設特徵向量已經求解出來了，那麼（點與點，向量與向量）位置關係（長度，夾角）應該如何度量？

答案是通過範數norm。範數空間normed vector space是已定義範數的空間，一般表示為 $(V,|.|)$ 。範數運算需要滿足三個條件：零向量的範數為零，其他向量的範數一定為正； $|alpha x|=|alpha||x|$ ；三角不等式。

內積inner product。內積數學表達式為 $langle.,. angle:V imes V o F$ ，即一個空間到標量域的二元映射，同時這個映射還需要滿足三個條件：共軛對稱性，第一元線性性，正定性。由此可見，內積運算是範數運算的充分非必要條件。也就是說內積空間一定是範數空間。因此在此內積空間中，向量的範數norm，定義為 $|x| = sqrt{langle x,x angle}$ ；兩個向量之間的夾角，定義為 $operatorname {angle} (x,y)=arccos {frac {langle x,y angle }{|x|cdot |y|}}$ 。直觀上來說，在我們熟知的歐氏空間中，內積即為點積dot product，距離和夾角都是通過點積運算而來。

在SVM預測階段中，就可以用內積的形式來表達待預測向量 $x$ 與 $p$ 的位置關係。如果 $x$ 與 $n$ 的夾角小於90°，就是同方向的，預測值為正例；如果大於90°，就是反方向的，預測值為反例；如果等於90°，就是正交的orthogonal，無法預測。 $left | frac{langle n,x angle + b}{|n|} ight |$ 就是預測的置信程度（距離）。

由此可見，內積是similarity的一種度量基礎。

在很多情況下，數據集是線性不可分的，但是可以對數據集 $A$ 建立一個高維映射 $A$ ，在 $A$ 中可能就線性可分，因此在高維數據集下訓練一個SVM往往獲得更好的效果，高票答案已經解釋的非常清晰了。那麼如何定義這個高維映射？如何減少映射的計算複雜度？在解決這兩個問題之前，首先需要了解核函數。

核函數（kernel function）是什麼？

核函數 $kcolon {mathcal {X}} imes {mathcal {X}} o mathbb {R}$ 是一個度量任意一對屬於空間 $mathcal {X}$ 中的向量的相似度的函數。其實這裡可以注意到，內積也是一種核函數。

核方法（kernel method）是什麼？摘自Wikipedia

Kernel methods owe their name to the use of kernel functions, which enable them to operate in a high-dimensional, implicit feature space without ever computing the coordinates of the data in that space, but rather by simply computing the inner products between the images of all pairs of data in the feature space. This operation is often computationally cheaper than the explicit computation of the coordinates. This approach is called the "kernel trick"

定義核函數 $k(x,z)=langle x,z angle^2$ ，那麼這個核函數對應了某種高維映射 $varphi$ 使得 $k(x,z)=langle varphi(x),varphi(z) angle$ 嗎？答案是肯定的

， $n$ 代表 $A$ 的維度。這裡核函數的計算複雜度為 $O(n)$ ，高維映射之後的內積計算複雜度為 $O(n^2)$ ，可見計算改核函數，就相當於將元數據集隱形的映射到了高維空間，並計算了映射之後的向量內積。

這就是核函數的優雅之處。

當然核函數要滿足一定條件 Mercer『s condition ，才有隱含的特徵映射與之對應。

那麼什麼是 Mercer『s condition？未完待續...

電腦只有2進位。

前面的解答依然過於抽象，不夠直觀。
很多演算法，都是要基於一個「距離」的概念。比如：

層次聚類要先聚離得近的點，然後再逐漸把更遠的點往裡聚。
支持向量機要找一個東西，讓兩組點的邊界離得最遠。

那麼問題就來了：什麼叫距離？
你可以簡單地使用兩點之間幾何距離，就是sqrt(x2 + y2 + z2 + .....)。但是有的時候，用別的距離定義會有特別的效果。
定義這個距離的東西，就叫核函數。

分享一個比較靠譜的東西 Kernel Functions for Machine Learning Applications

我的理解,kernel 的作用就是把你的數據集上下左右前後拉扯揉捏，直到你一刀下去正好把所有的0分到一邊，所有的1分到另一邊。這個上下左右前後拉扯揉捏的過程就是你的kernel. 不管是svm還是cnn，都可以這樣來解釋。

比如上面這個例子，右邊的紅藍點無法直接一刀切開。那如果你把所有的藍色點往下拉，把所有的紅色點往上推，那你就可以一刀把他們從中間劈開了。那這個推拉的過程就是kernel乾的事。

在這個例子里，這個函數如下

希望有所幫助。

直白的說:

問題中的映射:
首先，將數據映射到高維空間是為了解決數據在低維空間線性不可分，否則在SVM中分類超平面和最大間隔的思想也就無從談起。

問題中的核函數:
但是，如果維數太高甚至無窮維，就會帶來計算量的問題，這時候就需要核函數。
利用核函數，可以直接在低維空間中完成計算，而不需要顯式地寫出映射後的結果，避免了在高維的計算，結果卻是等價的！

問題中的徑向基核:
另外，問題提到的徑向基核很常見是因為在實際運用中確實能得到不錯的效果，此外還有線性核多項式核甚至字元串核等等等。很多時候選擇要取決於具體的問題，樣本量以及特徵量等綜合考慮，如果少樣本多特徵可能線性核就表現不錯了，如果多樣本少特徵高斯核確實經常有喜人的表現，如果樣本量巨大可能又要看著辦，總之一個字:多試試

希望簡單直白的回答對你有用。

svm的學習是需要計算相似度的，而又以餘弦相似度最常用，就是大家說的內積，
svm中低維下線性不可分的情況可以通過把它映射到高維上實現線性可分。這個過程可能會存在兩個困難:一，如何尋找映射函數f；二，可能映射f會把低維映射到高維甚至無窮維，這樣就會產生維災難，計算內積是不現實的。
這時候，核函數出場了，它是一個變換，使得計算一對向量的核函數等價與在變換後的空間中計算這對向量的內積，這樣就解決了上面提到的兩個困難。