模式識別中從Kernel方法的本質來看，是否真的有效？

01-02

在模式識別中常常對線性分類器引入核方法（Kernel），使之得以解決線性不可分的問題。我的問題就是，Kernel的本質是不是把原本線性分類器中的超平面改為了一種與核函數有關的曲面，來實現對非線性可分特徵的分類。如果回答是肯定的，那麼在此基礎上我還想質疑核方法的有效性。
我對Kernel的理解是，原先線性演算法中的點乘可以替換為核函數，核函數隱含了把低維向量映射到高維甚至無窮維空間，在高維空間中進行點乘運算的步驟，卻不需要真正的構造這個映射。在各種書籍里提到的線性不可分的例子，經過高維映射後就變得線性可分了。這個過程體現了高維空間中，存在使原問題線性可分的可能性。
以SVM為例，非嚴謹的描述下，線性SVM相當於尋找一個超平面，使得兩類樣本的向量邊緣到超平面的距離儘可能的大。當我們把線性核替換為其他核後，本質上SVM仍然是把樣本空間依據訓練集的分布劃分為兩類（也許每類空間不一定是相連的）。這個劃分曲面的形狀顯然是由核函數與支撐向量共同決定的。

我認為對於一個特定的模式分類問題，能否有效對其進行分類，應該取決於特徵空間中問題的分布。最簡單的情況下線性分類已經可以滿足，而複雜的時候才需要引入核函數，把超平面映射為某種曲面，利用曲面對樣本分類。而分類能否有效顯然是取決於曲面的形狀是否能夠適應於此問題。
對於高維空間中的樣本分布，我們很難直觀的根據數據來選擇分割曲面的形狀與位置。另一方面，即使目前已知的核函數已經不少，但是對於核函數所最適用的範圍，或是換句話說，如何根據遇到的問題構造合適的核函數也是十分困難的。
這就導致了一連串的問題：
1. 如果我們無法通過數據有效的選擇核函數，也無法根據樣本特性來構造合適的核函數，那麼對於任何一個線性不可分的問題，直接選擇Kernel-based分類器，是否真的有其道理？
2. 既然核函數只能改變分割超平面的形狀，在我們對特徵向量的分布一無所知的情況下就嘗試選用核函數來進行分類，是否更大的可能性是找不到一個合適的核函數呢？僅僅從主觀感受上出發，已知的核函數佔全集的比例應該是非常小的一部分，為何可以認為從常用的核函數中就可以找到一個合適的函數？

3. 我對模式識別的理解還停留在十分淺顯的層次，我也對上面自己做的推測持懷疑態度。如果核函數真的有「化腐朽為神奇」的能力，可以解決大多數，或者僅僅一大類線性不可分的問題，那麼我又推測，是否在核方法中有一種類似中心極限定理的規則存在，使得對於不同的問題，最終可以通過恰當的方法殊途同歸的利用核函數來解決？
以上就是我的困惑，希望能夠得到指點。

樓主的理解已經很深了，涉及到了問題的本質，即這句話：「另一方面，即使目前已知的核函數已經不少，但是對於核函數所最適用的範圍，或是換句話說，如何根據遇到的問題構造合適的核函數也是十分困難的。」

我更熟悉智能優化領域，先自引這篇回答的第二段越來越多的群體智能演算法（蛙跳演算法、貓群演算法、蟑螂演算法等等）有存在的必要嗎？引用的原因是，根據No Free Lunch Theorem，任何有效的演算法其實都是問題相關的，研究優化的要去研究被優化函數的response surface的特殊結構才能更好設計出有效的演算法，做語音識別的那麼多年的經驗告訴大家HMM演算法是有效的。所以，樓主最後這個問題實際上是所有演算法研究者都必須面對的終極問題。

回到問題本身，根據奧卡姆剃刀原則，如果能用線性分類器（線性核）做得足夠好的時候，當然不會再用非線性核；而非線性核又有許多許多，樓主的問題就在於怎麼知道哪個核是更有效的呢？根據我粗淺的了解（非專業出身，以下回答輕拍），高斯核是被廣泛應用的，可以說在許多線性分類器不適應的場合下被default選取使用的magic，其背後的原因我想還是RBF Neural Network is Universal Approximator (參見wiki的 Universal approximation theorem 和 Radial basis function network ），而採用高斯核的SVM可以被視作是一個簡化的RBF網路——因此，現實可能的確如 @謝鍇所言缺乏對問題本身的理論分析，而更多是工程化的思路，用高斯核或者某個核去試錯，如果看似結果還不錯那就OK，如果不好那就調調參數，做些修修補補的改進，弄好了一篇文章就有了，至於為什麼這樣就有效了，理論上可能並不知道，好一點的可能可以定性做些分析，聽起來make sense。

核方法可以看成是對數據分布的一個先驗。

對於一些問題，特定的核函數對問題是有很好的解釋性的，比如針對圖像採用Gaussian Kernel，針對直方圖採用Chi^2 Kernel等。

還有一些場景，比如說用二次函數作為kernel替代線性方法，本身就是線性方法的一個擴展，把舊的feature作為一個子集，分類器本身可以做特徵的選擇。

當數據量足夠充分，且對數據的分布不了解的情況下，首選的肯定還是線性方法。另外，kernel函數本身有很強的限制，還有很多非線性的方法是沒辦法kernel函數表示的，比如一些流形學習的降維演算法，也是基於對數據分布的一些manifold的假設，但並不能簡單寫成kernel function的形式。

最後你說的「是否在核方法中有一種類似中心極限定理的規則存在，使得對於不同的問題，最終可以通過恰當的方法殊途同歸的利用核函數來解決」，我理解有的話，應該是最大熵方法（Maximum Entropy），最大熵相當於對數據沒有任何先驗分布的假設，去最大化事件發生的概率。這個滿足你所說的情景，不過對於這個方法，我也沒有太多經驗，你可以自己尋找相關資料閱讀。

看這個網頁上的解釋(迄今我見過的最適合初學者的kernel trick的解釋)：

The Kernel Trick

1. 2. 我的看法是classification問題中的kernel trick是典型的performance over interpretability，當然教學用的toy example都是可以讓你肉眼看出該用什麼樣的feature map從而決定kernel function的。這可以類比為線性回歸中，一個函數讓你一眼看出是二次型 $y=ax^2+bx+c$ 從而決定選取 $(1, x, x^2)$ 去解釋 $y$ ；而強調performance的時候可以用一個足夠大的dictionary，比如 $(1, x, x^2,ldots,x^{10})$ 去解釋 $y$ ，如果 $y=f(x)$ 而 $f$ 不是二次型，這種解釋未必interpretable，比如有很多非零係數，但是解釋 $y$ 的效果有可能很好。kernel方法也是如此，很多時候只要比linear情形好就差不多。

3. 我覺得這句話很有道理：The more you know about a machine learning technique, (likely) the less you expect from it.

我覺得，核函數就是一個trick,或者說,magic。對於高維數據，鬼知道他是線性可分，還是不可分。

所以，在學術圈，貌似都是把所有著名的核函數都試一遍，哪個效果好，就選哪個。

工業界的話，就不知道了。

kernel trick

說點自己的理解。Kernel方法之所以流行，一是由於其在線性和非線性之間架起了一座橋樑，使得在解決相對複雜的非線性問題時候可以回到比較熟悉的線性問題中來，二是kernel trick這個東西，即題主所說的高維的點積可以通過低維點積的核映射得到，而且我認為正是第二點使得kernel方法在計算上可行從而使其得到廣泛關注的。題主所提的問題確實是比較難解決的，我看大家用得多的也就是Gaussian核和多項式核函，至於為啥這麼選，大多數是為了糊弄篇文章的，選了有效果就成，對為啥這麼選這麼深奧的問題，who cares啊。

樓主說的問題是有人在研究的。也就是說模式識別不是簡單的用用別人的工具包，跑跑公開的例子。

正式回答問題：第一個問題，核方法的理論基礎是RKHS(Reproducing Kernel Hilbert Space）上的表示定理，也就是說在該空間上的任意函數都是可以由有限內積表示的，也就是說，表示定理把無限的函數用有限的內積形式線性組合的方式表示出來。這也就回答了以上問題，有限的核怎麼解決無限的可能的問題。幾乎所有的「大行其道」的方法都是有理論背景的，不是完全拍腦袋拍出來的。即使最開始是，後面會有人不斷地完善理論基礎。

第二個問題，如何選擇核的問題，這個不完全是試湊的，否則那機器學習還學個啥。其中主要的方法包括，以NARMAX方法（OFR演算法）為代表的基於2範數的matching pursuit方法，和以lasso為代表的基於1範數的basis pursuit方法。

最後一句話大家共勉：學而不思則罔，思而不學則殆。不光要勤思，還要勤學。