核方法

機器學習中，核機是一類用於模式分析的算法，最知名的成員是支持向量機（SVM）。 這些方法用線性分類器解決非線性問題。^[1]模式分析的一般任務是在數據集中發現並研究一般類型的關係（如聚類分析、排名、主成分分析、相關性分析、統計分類）。對許多解決此類任務的算法來說，原始表示的數據必須通過用戶指定的特徵映射明確轉換為特徵向量表示；相反，核方法只需要用戶指定核，即用內積計算所有數據點對的相似性函數。核機中的特徵映射是無限維的，但根據表示定理，只需輸入有限維矩陣。在不並行處理的情況下，核機的計算速度會很慢。

核方法得名於核函數的使用，使其能在高維隱特徵空間中運行，而無需計算空間中數據的坐標，只需計算特徵空間中所有數據對的像之間的內積。這種運算比顯式計算坐標更節約，稱為「核技巧」。^[2]核函數已被引入序列數據、圖核函數、文本、圖像及向量處理中。

能使用核的算法有核感知器、支持向量機（SVM）、高斯過程、主成分分析（PCA）、典型相關分析、嶺回歸、譜聚類、自適應濾波器等等很多算法。 大多數核算法都基於凸優化或特徵問題，有很好的統計學基礎。通常用統計學習理論（如拉德馬赫複雜度）分析其統計特性。

動機與非正式解釋

核方法可被視為循例學習器：不是學習與輸入特徵相對應的固定參數集，而是「記憶」第${\displaystyle i}$個訓練樣本${\displaystyle (\mathbf {x} _{i},y_{i})}$並學習相應權${\displaystyle w_{i}}$。預測不在訓練集中的輸入（未標記輸入）是用未標記輸入${\displaystyle \mathbf {x'} }$與每個訓練輸入${\displaystyle \mathbf {x} _{i}}$的相似性函數${\displaystyle k}$（稱作核）。例如，核化二分分類器通常計算相似度的加權和

${\displaystyle {\hat {y}}=\operatorname {sgn} \sum _{i=1}^{n}w_{i}y_{i}k(\mathbf {x} _{i},\mathbf {x'} )}$,

其中

• ${\displaystyle {\hat {y}}\in \{-1,+1\}}$是核化二分分類器對無標輸入${\displaystyle \mathbf {x'} }$的預測標籤，其隱藏的真實標籤${\displaystyle y}$是我們感興趣的；
• ${\displaystyle k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R} }$是核函數，度量了任意一對輸入 ${\displaystyle \mathbf {x} ,\mathbf {x'} \in {\mathcal {X}}}$的相似性；
• 和的範圍是分類器訓練集中的n個有標示例${\displaystyle \{(\mathbf {x} _{i},y_{i})\}_{i=1}^{n}\ (y_{i}\in \{-1,+1\})}$；
• ${\displaystyle w_{i}\in \mathbb {R} }$是由學習算法確定的訓練樣本的權重；
• 符號函數${\displaystyle \operatorname {sgn} }$決定預測分類結果${\displaystyle {\hat {y}}}$屬於正類還是負類。

核分類器的描述可追溯至1960年代核感知器的發明。^[3]1990年代，隨着支持向量機（SVM）的流行，人們發現其在手寫識別等任務上的表現可與神經網絡媲美。

數學：核技巧

SVM，核為${\displaystyle \varphi ((a,b))=(a,b,a^{2}+b^{2})}$，因此${\displaystyle k(\mathbf {x} ,\mathbf {y} )=\mathbf {x} \cdot \mathbf {y} +\left\|\mathbf {x} \right\|^{2}\left\|\mathbf {y} \right\|^{2}}$。訓練點被映射到三維空間，很容易找到分離超平面。

核技巧避免了讓線性學習算法學習非線性函數或決策邊界所需的顯式映射。${\displaystyle \forall \mathbf {x} }$與${\displaystyle \mathbf {x'} \in {\mathcal {X}}}$（輸入空間），某些函數${\displaystyle k(\mathbf {x} ,\mathbf {x'} )}$可表示為另一空間${\displaystyle {\mathcal {V}}}$中的內積。函數${\displaystyle k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R} }$ 常被稱為核或核函數。「核」在數學中用於表示加權和或積分的加權函數。 機器學習中某些問題比任意權函數${\displaystyle k}$更具結構性。若核能寫成「特徵映射」${\displaystyle \varphi \colon {\mathcal {X}}\to {\mathcal {V}}}$，滿足

${\displaystyle k(\mathbf {x} ,\mathbf {x'} )=\langle \varphi (\mathbf {x} ),\varphi (\mathbf {x'} )\rangle _{\mathcal {V}}}$

那麼計算就能簡化很多。關鍵的約束是${\displaystyle \langle \cdot ,\cdot \rangle _{\mathcal {V}}}$必須是適當的內積。另一方面，只要${\displaystyle {\mathcal {V}}}$是內積空間，就不必明確表示出${\displaystyle \varphi }$。另一種方法來自默瑟定理：只要空間${\displaystyle {\mathcal {X}}}$匹配了合適的測度確保函數${\displaystyle k}$滿足默瑟條件，就存在隱定義的函數${\displaystyle \varphi }$。

默瑟定理類似於線性代數中將內積與任意正定矩陣相關聯的結果的推廣。實際上，默瑟條件可以簡化為這種更簡單的情況：若${\displaystyle \forall T\subset X}$擇計數測度${\displaystyle \mu (T)=|T|}$（計算集合${\displaystyle T}$內部的點數），那麼默瑟定理中的積分就簡化為和式

${\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{n}k(\mathbf {x} _{i},\mathbf {x} _{j})c_{i}c_{j}\geq 0.}$

若對於${\displaystyle {\mathcal {X}}}$中的所有有限點序列${\displaystyle (\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n})}$及所有${\displaystyle n}$個實值係數選擇${\displaystyle (c_{1},\dots ,c_{n})}$（參考正定核），和式都成立，那麼函數${\displaystyle k}$滿足默瑟條件。

一些依賴於原空間${\displaystyle {\mathcal {X}}}$中任意關係的算法在別的環境中會有線性解釋：${\displaystyle \varphi }$的範圍空間。線性解釋讓我們對算法有了更深入的了解。此外，在計算過程中通常無需直接計算${\displaystyle \varphi }$，支持向量機就是這樣。有人認為這種運行時間上的節省是其主要優點。研究人員也用它來證明現有算法的意義和特性。

理論上講，關於${\displaystyle \{\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n}\}}$的格拉姆矩陣${\displaystyle \mathbf {K} \in \mathbb {R} ^{n\times n}}$（有時也稱為「核矩陣」^[4]），其中${\displaystyle K_{ij}=k(\mathbf {x} _{i},\mathbf {x} _{j})}$須是正半定（PSD）矩陣。根據經驗，對於機器學習的啟發式方法來說，若${\displaystyle k}$至少近似於相似性的直觀概念，那麼不滿足默瑟條件的函數${\displaystyle k}$的選擇可能仍有合理表現。^[5]無論${\displaystyle k}$是不是默瑟核，${\displaystyle k}$仍可稱為「核」。

若核函數${\displaystyle k}$也是高斯過程中使用的協方差函數，那麼格拉姆矩陣${\displaystyle \mathbf {K} }$也可稱為協方差矩陣。^[6]

應用

核方法的應用十分廣泛，見於地理統計^[7]、克里金法、反距離加權、三維重建、生物信息學、化學信息學、信息抽取和手寫識別。

常用核函數

• Fisher核
• 圖核
• 核平滑器
• 多項式核
• 徑向基函數核
• 字符串函數核
• 神經正切核
• 神經網絡高斯過程（NNGP）核

另見

• 向量輸出的核方法
• 核密度估計
• 表示定理
• 相似性學習
• 科孚定理