機器學習里的 kernel 是指什麼？

11-25

在機器學習相關的論文或者書籍裡面經常見到kernel這個詞。請問kernel的含義及本質到底是什麼呢？

學渣來談談機器學習中的kernel method, 材料主要來自CS229.

很多人提到kernel是將數據映射到更高維的空間實現線性可分,這不太準確, 因為映射到高維的辦法很多, 比如直接將數據x先顯式地轉化成高維的形式 $phi(x)$ 然後丟進沒有 kernel 的演算法里, 一樣可以實現我們的目標, 但為什麼我們用 kernel?

Kernel 是隱式地將兩個向量轉換到其他形式然後求內積, 相比顯式的轉換可以極大的減少計算複雜度, 甚至可以將有限維的 x 轉換到無限維. 與其先求出 $phi(x)$ 再計算 $phi(x)^Tphi(z)$ , 不如直接算 $K(X,Z)$ , 這就是 kernel相對於手動(顯式)轉化的優勢.

$K(X,Z)=phi(x)^Tphi(x)$ .

==========================以下是啰嗦的詳細解釋

以支持向量機SVM舉例, 假設我們有一些有m個有標籤的數據,
${(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),...,(x^{(m)},y^{(m)})}$

比如二維空間中, 如圖

SVM 的目標就是尋找一個超平面(hyperplane)來對數據進行分類, 並且使幾何間距(geometric margins)最大化.

超平面:
$w^Tx+b = 0$
幾何間距:
$gamma^i = frac{w^Tx^i+b}{||w||}$
$gamma = min gamma^i$

函數間距以及其與幾何間距的關係:
$hat{gamma}^i = w^Tx^i+b$
$hat{gamma }= min hat{gamma}^i$
$frac{hat{gamma}}{||w||} = gamma$

用數學語言來描述, 該問題即

然而這個形式難以求解, 因此科學家們又將其變換了一個形式:
Let 函數間距 = 1, 最大化幾何間距就成了最小化 w 的L2範數

該問題只需要用拉格朗日對偶Lagrange duality 進行變換, 具體求 $alpha$ 的過程略, 得到:

其中尖括弧&<&>代表內積, 需要註明的是, 該變換過程中所有涉及 x 的運算均是內積的形式, 直覺上, 內積代表了兩個向量的重合度或者相似度.
顯然, 此時的 SVM 還是一個線性分類器, 因為是直接對 x 的一次項進行內積操作, 但很多時候線性分類是不夠的.

所以, 我們可以對x變換到高次項來實現非線性分類, 比如轉換成兩兩相乘的形式:

在計算中全部實用 $phi(x)$ 來替換 x, SVM 就實現了非線性分類, 即
$<x,z> Rightarrow <phi(x),phi(z)>$

然而問題就在於, 我們不得不寫一個函數來先把 x 轉換成我們想要的形式(比如上面的 $phi(x)$ ), 如果數據的維度為 n, 光這個二次項的轉化需要的時間複雜度就是O(n^2), 如果我們想試試三次項甚至多次項, 轉化x的複雜度就會指數級增長. 這顯然不可接受, 因為如果我們不對 x 進行映射, 內積操作只不過是 O(n) 的複雜度而已.

但如果我們能找到一個魔法般的kernel (記為 K )能實現直接計算出我們想要的非線性結果, 那我們即使不把 x 顯式的轉換為 $phi(x)$ , 也能計算出我們想要的內積了. 比如上圖的二次項例子, kernel 為

證明過程:

所以 $K(X,Z)=phi(x)^Tphi(x)$

使用了kernel 之後, 我們把原來的一次項內積結果平方一下, 就能得到我們想要的二次項內積結果, 而該操作的複雜度只是 O(n).

進一步的, 一些 kernel, 比如gaussian kernel 將 x 隱式的轉換為了無限維的 $phi(x)$ , 這也是顯式的轉化無法達到的.

因為很多演算法都是需要計算一些形如&的式子, 所以 kernel 被廣泛的運用了, 至於如何選擇 kernel, 這個就很難了, 很少有人能搞得很清楚, 基本都是靠運氣和經驗了.

PS: 驗證一個 kernel 是否有對應的 $phi(x)^Tphi(z)$ 的Mercer方法如下:

構造一個m階方陣K, $K_{ij} = K(X_i,Z_j)$ , 對於任何長度為 m 的向量 a, 如果 $a^TKa ge 0$ , 則 K(X,Z) 是有效 kernel, 該定義同樣意味著 K 矩陣為正半定矩陣positive semi-definite Matrix

寫過關於 RKHS (Reproducing Kernel Hilbert Space) 的博客，分為上下兩篇，寫的是自己對 kernel method 的理解。當時想盡量簡單的從數學角度把RKHS問題說清楚。博客地址如下，語言為英文，希望有所幫助：
第一篇： A Story of Basis and Kernel - part 1
第二篇：A Story of Basis and Kernel - part 2

先給個定義：核函數K（kernel function）就是指K(x, y) = &，其中x和y是n維的輸入值，f(·) 是從n維到m維的映射（通常而言，m&>&>n）。&是x和y的內積（inner product），嚴格來說應該叫歐式空間的標準內積，也就是很多人常說的點積（dot product）。

光看這一段還是不明白kernel是什麼，用來幹什麼的...對吧？不要急。一個好的知識分享者是不會把一篇空洞的定義扔下就不管的，TA會告訴你這個概念的intuition，然後給你舉個小小的栗子，最後告訴你幾個應用場景。Andrew Ng的Machine Learning為什麼會成為一門現象級的MOOC？原因之一就是因為他除了是個學術上的大神，也同樣是個極有質素的知識分享者。所以我要學習他。

好了，intuitively（這也模仿得太生硬了吧…），要計算&，我們要先分別計算f(x)和f(y)，然後再求它們的內積。上面的定義里也說了，經過映射後的x和y，維數大大增加，計算內積的成本可能會非常之大，而且在高位空間費力牛勁兒地計算內積，內積又是一個scalar，相當於說又把我們的計算從高維空間拉回到一維空間！所以我們特別想要一個「簡便運演算法」，幫助我們不需要奔向高維空間就能在家門口計算得到想要的內積。這時候該輪到我們的豬腳——kernel登場了，它能幫我們做到這一點。

舉個小小栗子。
令 x = (x1, x2, x3, x4); y = (y1, y2, y3, y4);
令 f(x) = (x1x1, x1x2, x1x3, x1x4, x2x1, x2x2, x2x3, x2x4, x3x1, x3x2, x3x3, x3x4, x4x1, x4x2, x4x3, x4x4); f(y)亦然；
令核函數 K(x, y) = (&)^2.
接下來，讓我們帶幾個簡單的數字進去看看是個什麼效果：x = (1, 2, 3, 4); y = (5, 6, 7, 8). 那麼：
f(x) = ( 1, 2, 3, 4, 2, 4, 6, 8, 3, 6, 9, 12, 4, 8, 12, 16) ;
f(y) = (25, 30, 35, 40, 30, 36, 42, 48, 35, 42, 49, 56, 40, 48, 56, 64) ;
& = 25+60+105+160+60+144+252+384+105+252+441+672+160+384+672+1024
= 4900.
好累，對不對？可誰讓f(·)把四維空間的數據映射到十六維空間里呢？
如果我們用核函數呢？
K(x, y) = (5+12+21+32)^2 = 70^2 = 4900.
就是這樣！

所以現在你看出來了吧，kernel其實就是幫我們省去在高維空間里進行繁瑣計算的「簡便運演算法」。甚至，它能解決無限維空間無法計算的問題！因為有時f(·)會把n維空間映射到無限維空間去，對此我們常常束手無策，除非是用kernel，尤其是RBF kernel（K(x,y) = exp(-||x-y||^2) ）。

在有kernel之前，做machine learning的典型的流程應該是：data --&> features --&> learning algorithm，但kernel給我們提供了一個alternative，那就是，我們不必定義從data到feature的映射函數，而是可以直接kernel(data) --&> learning algorithm，也可以是data --&> features --&> kernel(features) --&> learning algorithm。
所以雖然我們看到kernel常被應用在SVM（SVM中的kernel應該是後一種用法，後文再說），但其實要用到內積的learning algorithm都可以使用kernel。「用到內積的learning algorithm」其實並不少見，不信你可以想一想最普通不過的linear classifier/regressor有沒有一個步驟是計算特徵向量（feature vectors）。

那麼kernel在SVM究竟扮演著什麼角色？
初學SVM時常常可能對kernel有一個誤讀，那就是誤以為是kernel使得低維空間的點投射到高位空間後實現了線性可分。其實不然。這是把kernel和feature space transformation混為了一談。（這個錯誤其實很蠢，只要你把SVM從頭到尾認真推導一遍就不會犯我這個錯。）
還是簡單回顧一下吧。SVM就是 y = w"·φ(x) + b，其中φ(x)是特徵向量（feature vectors），並且是φ(x)使得數據從低維投射到高位空間後實現了線性可分。而kernel是在解對偶問題的最優化問題時，能夠使φ(x)更方便地計算出來，特別是φ(x)維數很高的時候。

------------------------------正文完，附上幾個鏈接--------------------------------
kernel的種類繁多，如果想詳細了解，可以看看這個帖子 Kernel Functions for Machine Learning Applications
Caltech的機器學習： Learning From Data
台灣大學林軒田《機器學習基石》：Coursera - Free Online Courses From Top Universities

PS：本來草稿里存的話是想告訴題主，這樣的問題好好去翻教材，或者看Caltech的Abu-Mostafa教授的公開課Learning from Data，或者看台灣大學林軒田的《機器學習基石》，（前者是後者的導師，而且師徒倆講課都很萌），弄懂kernel這個概念是不成問題的。
但當時沒有就這樣草率地發出來。原因倒不是怕被扣友善度，而是接連地追問了我自己到底弄明白kernel了沒有。所以謝謝題主問這個問題，你又驅使我把這個概念完整地思考一遍，並記錄下來。

拋個磚。

machine learning里有kernel的內容至少有以下幾個：1. kernel density estimation, 2. kernel smoothing, 3.kernel method, 4.RKHS.

1. kernel density estimation 與 kernel smoothing指的是同一個kernel，這裡的kernel function $K(x,y)$ 指的是定義在 $R^d imes R^d$ 上，取值於 $R_{+}$ 的二元函數，用來反映 $x$ 和 $y$ 之間的距離。
最常用的例子可能是Gaussian kernel $K(x,y) = expBigl (-frac{(x-y)^2}{2sigma^2}Bigr)$ .
可以參考wiki 的 Kernel smoother 和 Kernel density estimation

2. kernel method (kernel trick) 指的kernel function $K(x,y)$ 也是定義在 $R^d imes R^d$ 上的二元函數，但取值在 $R$ 上，它可以看成 $x$ 和 $y$ 的「內積」. 事實上， $K(x,y)$ 的定義要求存在某個Hilbert space $mathcal{V}$ 和函數 $psi:R^d ightarrow mathcal{V}$ 使得 $K(x,y) = langle psi(x),psi(y) angle$ ,這裡的內積是Hilbert space $mathcal{V}$ 上的內積. 這樣定義的kernel function滿足對稱性和正定性。
另外Mercer 定理說，任何滿足對稱性和正定性的二元函數 $K(x,y)$ 都能找到Hilbert space $mathcal{V}$ 和函數 $psi:R^d ightarrow mathcal{V}$ 使得 $K(x,y) = langle psi(x),psi(y) angle$ . 這樣一來，我們無需知道 $mathcal{V}$ 和 $psi$ ，只需定義一個kernel function，就能得到新的「內積」，這個「內積」是某個Hilbert space $mathcal{V}$ 上的歐氏內積。以Kernel SVM為例，在低維空間里的點可能無法用線性hyperplane分開，但可能投影到某個高維空間之後，這些點是Linear separable的，所以往往kernel svm會比linear svm有更大的靈活性。
可以參考wiki 的 Kernel method

3.Reproducing Kernel Hilbert Space 里的reproducing kernel 指的是一個二元函數 $K(cdot,cdot)colon mathcal{X} imes mathcal{X} ightarrow R$ 滿足 $K(x,y) = langle K_x,K_y angle _{mathcal{H}}$ , $K_x,K_yin mathcal{H}$ ,其中 $mathcal{H}$ 是一個由 $mathcal{X}$ 上函數構成的Hilbert space，且對於任何 $xinmathcal{X}$ ,存在唯一的 $K_xinmathcal{H}$ 使得
$forall fin mathcal{H}, f(x) = langle f, K_x angle _{mathcal{H}}$ (reproducing property).
這個公式的意思是，RKHS里的任何一個元素 $f$ ,它在 $mathcal{X}$ 上的取值可以通過在 $mathcal{H}$ 上做內積得到。另外RKHS還要求取值泛函(evaluation functional)是連續的，即
$forall xin mathcal{X}, L_xcolon mathcal{H} ightarrow R$ $L_x(f) = f(x)$ 是 $mathcal{H}$ 上的連續泛函。
Moore-Aronszajn定理說 $K(cdot,cdot)colon mathcal{X} imes mathcal{X} ightarrow R$ 是一個reproducing kernel當且僅當它是對稱和正定的。

另外值得一提的是，reproducing kernel 可以用來做kernel method里的kernel, 只要讓 $psi(x) = K_x$ 即可。反之，有了kernel method 的feature mapping $psi$ ,也可以定義一個RKHS, 見Reproducing kernel Hilbert space-Feature Maps一節。

kernel跟kernel trick是不一樣的，kernel其實就是個函數，怎麼在低維空間算高維空間的值那是kernel trick

你是指kernel是怎麼來的是嗎？

這個其實是一個數學上的叫法。數學上把比如 $int f(x)g(x,y)dx$ 乘起來這樣的積分裡面的g(x,y)叫成一個核函數。這東西最早是出現在積分方程裡面的。然後因為你看到這個積分自然可以聯繫到所謂的希爾伯特空間（內積就是這樣一個形式，L2空間裡面內積就是這樣一個積分，只不過這個希爾伯特空間裡面的內積加了一個核函數，離散的時候你可以理解成加了一個正定矩陣），所以後面g(x,y)就和可能是你指的SVM裡面的那個核函數聯繫在一起了，一般SVM裡面寫成K(x,y)（順便SVM用的是RKHS，就是是再生核的希爾伯特空間，換言之內積可以把函數給換出來，我不知道這麼說是不是有點不太明白）。實在弄不懂你看點泛函分析就明白了。

其實這些東西在數學上都是相通的，就是說白了核心就是Mercer定理（學過泛函的肯定不會陌生）。你要是學過泛函的話去看看泛函書上面的這個定理，或者看這個：Mercer"s theorem。當然SVM還加上了一大票的二次優化的內容就是了。

還有誰告訴我知乎怎麼用Latex輸公式？（好了我自己摸索出來了）

我是初學者對這方面了解不深，但是我還是希望大家看那個最高票答案（多圖的那個）的時候保持冷靜和警惕，因為這個答案有一定誤導性。我推薦 @郭小賢和其他幾位答主的解釋，非常到位。

最高票答案圖很漂亮，語言也很漂亮，很直觀，也很popular，但解釋的是將低維空間中線性不可分的數據變換到高維空間找到一個線性可分的分類的過程，並不能與kernel trick等價，更不能與kernel等價。Kernel Trick只是解決這個變換到高維後如何避開維數影響進行有效率的計算的問題，本身並不是投射到高維的手段，Kernel Function（核函數）只是一個關於特徵向量的函數，本質是變換後的空間中的內積，這個函數的構造和引入的初衷只是為了提高SVM在高維的計算效率。

比如我們把特徵向量空間從 $d$ 變換 $d$ 維，變換後的特徵向量記為 $[{f{z}}_n^{d$ 其中上標代表維數，下標表示第幾個sample。那麼利用Dual Lagrange找到分類函數的係數（向量） $f{w}$ 所需要優化的目標函數就是 $[mathop {min }limits_{f{alpha }} [frac{1}{2}{{f{alpha }}^T}{{f{Q}}_D}{f{alpha }} - {{f{1}}^T}{f{alpha }}]]$ （這裡已經轉成二次規劃需要的形式了）其中 $alpha$ 是需要求解的Lagrange multipliers向量，矩陣 $f{Q}_D$ 第n行第m個元素為 $[{q_{n,m}} = {y_n}{y_m}{f{z}}_n^T{{f{z}}_m}]$ ，所以我們可以看到這裡會頻繁計算這個變換後的向量 $f{z}$ 之間的內積，而如果我們需要變換到維數很大的空間的話，這樣的計算會變得很麻煩。那麼我們不妨把這樣的計算往變換前的特徵向量靠，變換後的空間的內積運算可以寫作 $[{{f{z}}^T}{f{z}}$ ,那我們就規定我們的核函數為 $[{K_phi }({f{x}},{f{x$ ，至於這個核函數具體是什麼值怎麼算就取決於我們想作什麼樣的變換，總之最後是要變換到關於 $f{x}$ 的內積形式，比如需要的變換是 $[{phi _2}({f{x}}) = (1,{x_1},{x_2} ldots ,{x_d},x_1^2,{x_1}{x_2}, ldots ,{x_1}{x_d},x_2^2, ldots ,{x_2}{x_d}, ldots x_d^2)]$ ，那麼我們就可以自己動筆代入一下公式求得核函數是 $[{K_{{phi _2}}}({f{x}},{f{x$ ，計算的時候代入核函數求內積，就比直接用變換後的空間向量點乘硬求快多了。複雜度從 $[o({d^2})]$ 下降到了 $[o({d})]$ .

這樣思路其實我們在初中就接觸過，比如有個代入求值題 $[f(a,b,c) = {a^2} + 2ab + {b^2} + {c^2} - 2bc - 2ac]$ 求 $[f(1,2,3)]$ 的值，直接代進去算6個項加起來會顯得很蠢，但是整理成 $[f(a,b,c) = {(a + b - c)^2}]$ 再代入求值就方便的多了。

以上思路是已經確認空間變換方法的情況下使用這種「化簡」在計算中偷懶的技巧，但實際上也有為了用現成的性質較好的核函數而硬湊變換空間的應用情況，而且並不少見。比如ls-svm工具箱提供的就是可以選擇參數的核函數（次數和係數），所以實際選擇了核函數的形式也就是選擇了變換空間的方法。Gaussian Kernel則是一種把原空間投影到無窮維空間的變換中用於計算的核函數。但是，不能因此說Kernel Trick是完成低維變換到高維的過程，Kernel Trick只是為這種變換之後的計算服務的一個小技巧，真正的變換在定義 $[{f{z}}_n^{d$ 並將其作為特徵空間的時候就已經完成了，硬算內積不通過kernel不是不可以只是不方便。不能因為應用中經常把核函數類型作為變換類型就本末倒置說kernel是變換的過程。

另外，總是濫用空間想像能力和類比能力試圖理解classification和regression並不是一個很好的習慣，話至此。

保持內積結構不變，嵌入到希爾伯特空間。

其實「再生核希爾伯特空間」翻譯成「重內積核希爾伯特空間」會不會好點

非常好的一個問題，當然已經也有非常好的回答。
不過作為曾經也困惑的過的過來人，我試圖直觀的去解釋一下問題。
1.Kernel是什麼？
Kernel是一個函數，一個二元函數，一個從 $R^{n} imes R^{n} ightarrow R^{+}$ 的二元函數。至於什麼是二元函數，這個。。。這個就不用解釋了吧，你懂的。。。
2.關於Kernel的一些。。。
首先如kernel直接翻譯過來一樣就是核心，而kernel就是machine learning中最核心的部分的東西。它有效的描述了點和點之間的關係，或者說是距離，當然這裡的距離嚴格的說應該是廣義的距離。所以按照其作用kernel原本的名字應該叫「covariance function」. 有人會問，明明字母都不像么，為什麼是一樣的呢？其實這就好像，一個人叫張三，然後做了公司老闆，你可以叫他老闆，而且你叫習慣了，因為在公司中就是無可替代的老闆，但是他的真名就是張三。可能有人還是不明白，為什麼這是一致的。那麼下一個直觀的問題是，什麼是machine learning中最要的部分呢，也就是核心呢？Of course, training learning! 那什麼是traininglearning中最重要的呢？對，那就是點與點之間的關係，無論是training點之間的關係還是training與learning點之間的關係都是這整個過程的必不可少的信息。好的，那我們再來看看covariance function 的意義吧。wiki上說，在概率論與統計學中，covariance是一種兩個變數如何相關變化的度量，而covariance function 是自然就是描述對應協方差的函數嘍！OK，現在看著應該很像了吧，不是像，應該說是一樣的嘛。

3. Kernel心中的kernel
之前說了，Kernel是描述點和點之間關係的，或者說是距離。距離是一個非常的有趣的詞語。北京到上海的距離是1463 公里，而你到我距離卻只有那心動的一瞬間。好了，不文藝了，事實上距離是一個有歧義的詞語，因為在不同的情況下距離有著不同的描述方法，比如常用的歐氏距離(Euclidean Distance) 和曼哈頓距離(Manhattan Distance)，當然還有更複雜的，比如切比雪夫距離 ( Chebyshev Distance )，閔可夫斯基距離(Minkowski Distance)，馬氏距離(Mahalanobis Distance)，漢明距離(Hamming distance)，這裡就不多說了，其實我也不知道具體這些東東具體是做什麼的，不過有人知道，比如「機器學習中的各種距離」。
好了，問題又來了，距離有那麼多定義，可是萬一弱水三千就沒有我需要的一瓢怎麼辦呢？沒關係，數學如此博大精深，自然有辦法的，那就是去定義嘛。深奧的functional data analysis (泛函分析)告訴我們，從距離空間出發，我們可以一步步往前走可以得到賦范向量空間，內積空間，然後是優美的希爾伯特空間。對就是你了，希爾伯特空間，這裡面有好多概念，這裡就不多說了，主要就是一個範數，一個內積。那什麼是範數呢，範數就是我們之前強調的距離，或者說廣義的距離。而什麼又是內積呢？沒錯，內積就是這個距離的定義的方式。這就是為什麼說由內積可以誘導出範數的原因了。因此，如果我們用到相關希爾伯特空間的知識的話，這個「自定義」距離的問題就不在話下嘍。OK，現在我們回到這個kernel的問題，既然kernel是用來描述點與點之間的關係或者說距離的話，那麼一種可行的有效的方法就是用內積去刻畫，也就是說 $k(x,y)=<x,y>$ ,根本不同的內積定義，我們就可以構造出不同的核函數。當然由於這是內積定義的，那麼自然學過一點泛函的小朋友都知道，這裡的kernel也就會有正定和對稱的性質啦，回頭想想我們的發出點，這兩個性質是不是也理所應當的是kernel所應該具備的呢？Definitely! 然而，現實的問題是，內積雖然可以有各種定義方式，但是局限性還是蠻大的，玩來玩去一共就那麼幾種，如果我們可以得到更加一般化的結論怎麼辦呢？沒錯，只能動一動內積裡面的東西啦，也就是 $k(x,y)=<psi(x),psi(y)>$ 。這樣一來的好處就是，無論x,y 本身是如何的，維數也好，形式也罷，我們都可以調整這個 $psi$ 來保證一般的常見的內積定義，而其中這裡的 $psi$ 呢，自然可以看做了一個映射，從一個從 $R^{n}$ 映射到一個一般的希爾伯特空間 $mathcal{V}$ 的映射，而此時內積仍舊是定義在希爾伯特空間 $mathcal{V}$ 的內積。這也就是好多小夥伴正在說到的所謂高維到低維還是不知是從低維到高維的feature mapping。（事實上，就我所知比較多用的應該是從低維到高維的投射吧，因為這會讓一些低維空間上不明顯的feature在高維空間容易顯示出來）。當然這一切都可以有個大神叫Mercer 給出的定理去解釋，Mercer定理說，任何滿足對稱性和正定性的二元函數 $k(x,y)$ 都能找到Hilbert space $mathcal{V}$ 和函數 $psi$ 使得 $k(x,y) = langle psi(x),psi(y) angle$ . 不過實際問題中，feature space 下計算feature 的複雜度極高，所以說定義一個合格kernel可以大大降低這個計算feature 的複雜度。從而這邊又可以引出kernel第二個別名，kernel trick。
另外也有小夥伴提到Reproducing Kernel Hilbert Space （RKHS），這個嘛，事實上也就是一種在希爾伯特這個大的游泳池裡面一種複雜而漂亮的游泳方式啦，如果你各方面條件合適，事實上你也可以直接創造一種優美的游泳方式，是不是很炫酷，想試試？呵呵，真的似乎好難。。。一旦涉及泛函，事實上沒有一定的功底，基本就是舉步維艱。

4. Kernel有什麼用？
這個就海了去了。。。這就是machine learning中的一大塊，kernel learning嘛，其中最為典型的要數Support Vector Machine (SVM), Gaussian Process (GP),還有Principal Component Analysis (PCA)。看到這裡有木有覺得非常熟悉，叱吒風雲的SVM和PCA，不過這裡怎麼還有個似乎顯得那麼冷門的Gaussian process呢，這是什麼東東呢，詳見Carl Edward Rasmussen and Christopher K. I. Williams大神寫的書Gaussian Processes for Machine Learning。簡單的說呢，這也是一種非常有效的supervised leaning的方法，至於什麼是supervised leaning呢，簡單理解就是有一個學習明確的學習方向的learning。這邊還需要強調一下的是，這些learning的方法都是有classification和regression的，大多數小夥伴都知道SVM吧，不過大多數中的大多數或許只知道SVM可以做classification，所以也多在說kernel對SVM的作用。我弱弱的想說一句是regression和classification大家都有，只是在大多數情況下，SVM在classification方面比較有優勢而GP會在regression上有較好的結果，僅此而已。不過總的來說還是一句話，kernel不論對regression還是classification都是意義重大的，誰叫人家叫kernel呢！至於具體的作用么，本人做的是GP的regression，我可以確認是在GP的regression中，kernel主要是對應數據的pattern的，直接想想就是如果數據是一維，那麼這個所謂的pattern就是這個圖形走勢啦，圖形長的想什麼函數，就對應著是什麼具體的經典kernel，有光滑的無限可微的Squared Exponential （SE），有具有完全周期性的（Periodic），還有一些奇奇怪怪的kernel，比如Rational Quadratic (RQ), Matern(MA) 等等，這裡還有更詳細的Kernel Functions for Machine Learning Applications。

我又回去複習了一下，也來試著回答一下。

首先如 @Yang Zhuoran 所說機器學習里有好幾個 kernel，他們在數學上很類似但是在應用上不太一樣，我覺得核密度估計的kernel 也特別常見，那個是為了用有限的觀測點估計連續的概率密度，其實很容易理解。

大家多數好像都認為題主問的是 kernel method 的 kernel。
這個我感覺 @郭小賢回答的很好了。（唯一感覺最後太過強調不是kernel把點變換到高維有點誤導，實際上就是kernel啊）
我就補充一點個人理解：

我覺得一般來說其實很容易理解兩點：
1. kernel function 是一個距離函數。
2. kernel 是用來實現所謂的 "為了線性可分變換到高維空間" 的。

但是這兩者之間的關係不太容易理解。
我個人感覺 kernel method 其實是基於這樣一種思路：
如果我們把數據變換到高維只進行了求距離的計算，那不如直接對「變換到高維後的距離函數」建模。
（目的就是像 @郭小賢說的那樣是為了好算。）
（P.S. 這和判別主義的「如果我們只是為了把兩個分布分開不如直接對判別函數（分類面）建模」還有點像。）

首先你把數據變換到高維一般數據之間的距離都是得變的。（貌似保距變換隻能是線性變換吧，維度只可能降低，這個我不太確定。）

如果我們直接對變換到高維的變換函數建模，距離函數一定可以由變換函數求出來。

而如果我們對「變換後的距離函數」建模，則不一定有唯一的變換函數對應。
也就是說有些 kernel function 對應的高維變換具體是什麼樣可能是不太清楚的，而且還有 kernel function 形式很簡單，但對應的變換是無窮維的情況。

實際操作中我們也不關心我們到底變換到了怎樣的高維空間，只要我們用選擇的核函數對應的高維空間可以使得類型線性可分就行了。

在原始維度線性不可分的情況，可以通過將維度擴展到更高維度中，從而使得可以線性分隔。這部分也就是最高票答案所說的。

然而當維度擴展之後，相應的高維下的內積計算也變得更為困難。而在這時候，他們發現了可以直接通過原始維度的特徵向量來計算得到維度擴展後的向量的內積，而這種映射關係就是核函數。

即，直接輸入原始特徵向量，不用進行顯式的維度擴展然後用高維特徵向量運算，就可以直接得到對應的高維特徵向量的內積。

另外分享一篇我覺得很好的文章，對kernel的理解很有幫助~（今天恰好在看svm，就看到這個問題了）
http://cos.name/2014/02/svm-series-3-kernel/

一會兒去圖書館回來填坑。
@Yang Zhuoran，PDS Kernel 的定義是 Gram Matrix symmetrical and semidefinite

首先，高分答案說了大多數的博客都會講到的一個點，也就是核函數可以隱式升維，但是核函數並不僅僅有這麼一個作用，否則就不會有人專門寫一本書來講核函數了 [1, 2, 3]。但是的確，高斯過程和支持向量機是最主要的應用，而核函數的引入確實為SVM帶來了很強的非線性特性。

假設分類器為判別型，核函數的引入可以進一步引入生成模型，從而引入隱變數 [4, 5]。
核函數的輸入也不僅僅局限為特徵空間，集合、圖、字元串等均可以作為核函數的輸入。

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

核函數的定義是feature space中向量的內積，因此不含有方向信息：

$k(mathbf{x}, mathbf{x}$

同時，向量空間中兩向量的內積可度量其距離，在構造核的時候多會考慮這一點。

通過顯示地將核函數表達為向量的內積，我們可以檢驗核的合法性以及其具體是如何「升維」的。考慮具有如下形式的核函數：

$egin{aligned} k(mathbf{x}, mathbf{x}$

其中, $[oldsymbol{phi}(mathbf{x})]_{k}=x_ix_j$ ，k的取值範圍是1到 $D^2$ ，D是x的維度。這個核等價於考慮輸入向量中所有維度的乘積和，因此將維度平方了。同理可以考察任意向量內積的M次方，為輸入向量項所有能組合成的M階多項式的和。

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

合理核的構造可以通過兩種方式：

根據已有的核構建新的核，規則見構造表。
直接構造Gram矩陣（Gram矩陣 $mathbf{K}$ 的n, m項為 $k(mathbf{x}_n, mathbf{x}_m)$ 。該核合理的充要條件是Gram矩陣要半正定 [6]。有一個例外的核是sigmoidal核 $k(mathbf{x}, mathbf{x}$ ）

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

核函數的應用場景很廣泛，因為回歸問題核分類問題通過整理都能表達為核函數的形式。
回歸問題中，平方誤差損失，也就是權重的一個二階多項式，可以寫作一般的核表達。這個很多書上都會講，SVM的目標函數引入了拉普拉斯乘子或regularized quadratic loss都可以寫做此形式。
分類問題中，交叉熵也可以被寫作類似的形式（因為對數的出現因此只能寫作核向量，不能寫作Gram矩陣的形式）。以二分類的邏輯回歸做例子：

$egin{aligned} frac{partial E}{partial mathbf{w}}=partialsum_{n=1}^N-igg{t_nlnsigma(mathbf{w}^ ext{T}oldsymbol{phi}_n)+(1-t_n)lnBig[1-sigma(mathbf{w}^ ext{T}oldsymbol{phi}_n))Big]igg}+frac{lambda}{2}mathbf{w}^ ext{T}mathbf{w}igg/partial mathbf{w}\ =sum_{n=1}^NBig[sigma(mathbf{w}^ ext{T}oldsymbol{phi}_n)-t_nBig]oldsymbol{phi}_n^ ext{T}+lambdamathbf{w}^ ext{T}=0 end{aligned}$

解出權重 $mathbf{w}=oldsymbol{Phi}^{ ext{T}}mathbf{a}$ ，其中 $a_n=-frac{1}{lambda}Big[sigma(mathbf{w}^{ ext{T}}oldsymbol{phi}_n)-t_nBig]$ ，設計矩陣 $oldsymbol{Phi}$ 的第i行為 $oldsymbol{phi}_i^{ ext{T}}$ 。
代回誤差函數以後整理E為 $oldsymbol{Phi}oldsymbolphi_n$ 和 $oldsymbol{Phi}oldsymbolPhi^ ext{T}$ 的函數，
$oldsymbol{Phi}oldsymbolphi_n=mathbf{k}(oldsymbol{phi}_n)$ ，其中 $[mathbf{k}(oldsymbol{phi}_n)]_i=k(oldsymbol{phi}_n, oldsymbol{phi}_i)$ ，為Gram矩陣的n, i項；
$oldsymbol{Phi}oldsymbolPhi^ ext{T}=mathbf{K}$ 為Gram矩陣）。

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

假設特徵向量 $oldsymbol{phi}$ 取為一個概率分布，則可以引入一個生成式模型以構造核函數：

$k(mathbf{x}, mathbf{x}$

核函數的值當兩輸入在同一個分量i處的概率均較大時越大。我們可以用混合高斯分布來理解這個問題。假設分量i的均值和協方差分別為 $oldsymbolmu_i, oldsymbolSigma_i$ ，即

$egin{aligned} k(mathbf{x}, mathbf{x}$

可知當兩輸入與分量均值的馬氏距離越大時核函數值越大。也即，兩輸入在此混合高斯中分布越相似，核函數值越大。隱馬爾科夫模型類似。注意這裡兩輸入都是由相同的隱變數（參數）生成的。

======================================================================
其他輸入形式等以後有機會再說～

Refs:
[1] Sch?lkopf B, Smola A J.
Learning with kernels: support vector machines, regularization,
optimization, and beyond[M]. MIT press, 2002.
[2] Herbrich R. Learning kernel classifiers: theory and algorithms[M]. Mit Press, 2002.
[3] Cristianini N,
Shawe-Taylor J. An introduction to support vector machines and other
kernel-based learning methods[M]. Cambridge university press, 2000.
[4] Haussler D. Convolution
kernels on discrete structures[R]. Technical report, Department of
Computer Science, University of California at Santa Cruz, 1999.
[5] Jaakkola T S, Diekhans M,
Haussler D. Using the Fisher kernel method to detect remote protein
homologies[C]//ISMB. 1999, 99: 149-158.
[6] Shawe-Taylor J, Cristianini N. Kernel methods for pattern analysis[M]. Cambridge university press, 2004.

kernal表示的是具體的映射關係，ML里很多演算法的核心思想里需要一個映射關係把問題轉化，但是實現的方法多種多樣，具體的映射函數就叫kernal啦。

其他人說的都比較詳細了。

我就加點我自己的理解：繞開各種數學定義和高位空間映射的解釋，我覺得其實kernel就是個similarity measurements.

各種kernel method其實就是 KNN的推廣，用相似點來預測未知點，然後kernel來算相似度。

當然，各種方法譬如regularized network，SVM等方法的推導和出發點都不一樣。但最後預測函數形式都是差不多的。

看了樓上那麼多答案感覺茅塞頓開，現在說說我的理解。之前一直認為Kernel是將高維向量映射到低維進行計算，但是這並不是Kernel的真正用處，我的理解是K通過將映射 $phi(x)$ , $phi(z)$ 的內積進行數學變換，變成直接用x，z進行計算的函數關係，從而避免計算複雜的映射 $phi$ ，來達到簡化高維內積運算的目的。所以我認為實際上Kernel是一個函數，這個函數可以簡化內積運算，由於是初學者，可能存在理解上的錯誤，希望各位大神批評指正。

在這個問題和之前的一些關於kernel的問題下面的回答已經說的很透徹了，我就不班門弄斧了。只從一名初學者的角度澄清三個容易弄錯的概念，其實大家的貼子里也都有提及，我只不過再啰嗦一遍：

1. kernel和SVM並不是綁定的，同意之前有人回的帖子說，這兩個概念可以認為是正交的。kernel的出現要遠遠早於SVM，應用範圍也遠不止SVM；

2. 引入kernel的目的不是為了升維，而是升維後的簡化計算。這個可以作為面試題，答錯率相當高，可能都是被一些機器學習入門課程忽悠的；

3. 並不是所有情況下的kernel都要求滿足Mercer條件，SVM和GP（高斯過程）要求滿足，但L1VM、L2VM、RVM都不要求kernel必須滿足Mercer條件。這個在MLaPP書里說的很清楚。

相似度度量

那想請問，用RBF kernel可以直接得到X,Y的對應關係，那麼y=f(x)的近似表達式可以顯示錶達嗎？我現在要用RBF kernel核函數進行擬合後，想對擬合的函數進行求導。

Kernel是一個函數，利用這個函數可以在低維度進行高維度的向量內積運算（向量內積其實是一種相似性）。現有的很多演算法比如SVM,Kernel Logisitic Regression, SVR等等的，都是在求解問題過程中將問題轉化為可以表示兩個樣本內積的形式。比如SVM利用primal SVM的對偶問題將w*z表示成sigma(y_n*alpha_n*z*z)這樣的形式，這裡z*z內積可以在低維度空間進行;同樣的道理Kernel Logistics Regression利用w一定是樣本的線性組合，將ringe regression 替換成樣本線性組合的形式構造出一個z*z;SVR和SVM類似