Note 6 核， 核方法與核函數

到目前為止，我們所討論的機器學習算法的成功都依賴于對輸入數據分布的假設。例如，PCA的效果越好，數據圍繞線性子空間分布。或者在線性判別分析中，我們假設類的高斯分布，甚至有相同的協方差矩陣。

為了更好地考慮輸入數據的其他更復雜的分布，擴展方法的一種方式是采用所謂的核方法。它允許概括所有基本上只有標準內積作為輸入數據的方法。

更確切地說，考慮一個ML算法，其輸入數據可以是無標簽的，即${\mathbf{x}}_1,\dots ,{\mathbf{x}}_n$或有標簽的，即$\left({\mathbf{x}}_1,{\mathbf{y}}_1\right),\dots ,\left({\mathbf{x}}_n,{\mathbf{y}}_n\right)$ 。此外，假設該算法實際上只使用了輸入數據的$?{\mathbf{x}}_i,{\mathbf{x}}_j?:={\mathbf{x}}_i^{?}{\mathbf{x}}_j$。然后，將$?{\mathbf{x}}_i,{\mathbf{x}}_j?$替換為某個函數$\kappa \left({\mathbf{x}}_i,{\mathbf{x}}_j\right)$，該函數是內積的適當概括（即核），稱為核方法，參見圖6.1。由此產生的學習方法通常被命名為 "核 "一詞的前綴。這個技巧通常可以將基于數據分布的線性假設的方法擴展到更復雜的非線性分布。

圖6.1：核方法的說明。用核代替機器學習算法中的標準內積，以獲得該方法的 "核 "版本。

Kernel method${}^{[1]}$

[1] 這部分來自于wikipedia，對于核有更詳細的說明與介紹。

核方法可以被認為是基于實例的學習器：它們不是學習一些與輸入特征相對應的固定參數集，而是 "記住"第$i$個訓練實例$({\mathbf{x}}_i,y_i)$，并為其學習相應的權重$w_i$。對未標記的輸入，即那些不在訓練集中的輸入的預測，是通過應用一個相似性函數$k$，稱為核。核是在未標記的輸入${\mathbf{x}}^{\prime }$和每個訓練輸入${\mathbf{x}}_i$之間的相似度函數，它衡量它們之間的相似性。例如，一個核的二元分類器通常計算相似性的加權和

$$\hat{y}=\mathrm{sgn}\sum _{i=1}^n{w}_i{y}_{i}k({\mathbf{x}}_i,{\mathbf{x}}^{\prime }),$$
其中

• y^∈{?1,+1}{\hat {y}}\in \{-1,+1\}y^?∈{?1,+1} 是核化二元分類器對未標記的輸入的預測標簽。

• ${\mathbf{x}}^{\prime }$ 其隱藏的真實標簽y是我們感興趣的。

• $k:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ 是衡量任何一對輸入$\mathbf{x},{\mathbf{x}}^{\prime }\in \mathcal{X};$之間相似性的內核函數。

• $\sum$的范圍是分類器訓練集中的$n$個已標記的例子，${({\mathbf{x}}_i,y_i)}_{i=1}^n$，其中yi∈{?1,+1}y_{i} \in \{-1,+1\}yi?∈{?1,+1}。

• $w_i\in \mathbb{R}$ 是訓練實例的權重，由學習算法決定。

• 符號函數$sgn$決定了預測的分類$\hat{y}$的結果是正還是負。

核分類器早在20世紀60年代就被描述過，當時發明了核感知器。隨著支持向量機（SVM）在20世紀90年代的流行，核分類器的地位大為提高，當時SVM被發現在手寫數字識別等任務上可以與神經網絡相競爭。

---

因此，核的定義如下。它概括了標準的內積。

Definition 6.1

一個（半正定）核是一個函數$\kappa :{\mathbb{R}}^p\times {\mathbb{R}}^p\to \mathbb{R}$ 對于所有有限集合 X={x1,…,xn}\mathbf{X}=\left\{\mathbf{x}_{1}, \ldots, \mathbf{x}_{n}\right\}X={x1?,…,xn?} 的 $n\times n$矩陣
$$\mathbf{K}:=?\begin{array}{ccc}\kappa \left({\mathbf{x}}_1,{\mathbf{x}}_1\right)& \dots & \kappa \left({\mathbf{x}}_1,{\mathbf{x}}_n\right)\\ ?& ?& ?\\ \kappa \left({\mathbf{x}}_n,{\mathbf{x}}_1\right)& \dots & \kappa \left({\mathbf{x}}_n,{\mathbf{x}}_n\right)\end{array}?\text{\hspace{1em}(6.1)}$$

是對稱的和正半定的。矩陣$\mathbf{K}$被稱為$\kappa$和X的Gram-Matrix。 對于一個給定的函數$\kappa$，通常很難說它是否是一個核函數。然而，必要的條件，如對稱性和正定性是很容易檢查的。

Example 6.2

函數 $\kappa (\mathbf{x},\mathbf{y})=\Vert \mathbf{x}\Vert \Vert \mathbf{y}\Vert ?1$不能是核，因為存在一個有限集合，即 {0}?Rp\{0\} \subset \mathbb{R}^{p}{0}?Rp，這樣相關的Gram-Matrix（在這種情況下是$1\times 1$）$\mathbf{K}=?1$是負定的。

或者考慮函數 $\kappa (\mathbf{x},\mathbf{y})={\mathrm{e}}^{?\Vert \mathbf{x}?\mathbf{y}\Vert ?\Vert \mathbf{y}\Vert }$。很容易看出，一般來說，$\kappa (\mathbf{x},\mathbf{y})=\kappa (\mathbf{y},\mathbf{x})$，因此它不可能是一個核函數。

幾個常見的核是

• the linear Kernel $\kappa (\mathbf{x},\mathbf{y})={\mathbf{x}}^{?}\mathbf{y}+c,c\ge 0$;

• the polynomial Kernel $\kappa (\mathbf{x},\mathbf{y})={\left(\alpha {\mathbf{x}}^{?}\mathbf{y}+c\right)}^d,c,\alpha ,d\ge 0$;

• the Gaussian Kernel $\kappa (\mathbf{x},\mathbf{y})=\exp \left(?\frac{\Vert \mathbf{x}?\mathbf{y}{\Vert }^2}{2{\sigma }^2}\right),\sigma >0$;

• the exponential Kernel $\kappa (\mathbf{x},\mathbf{y})=\exp \left(?\frac{\Vert \mathbf{x}?\mathbf{y}\Vert }{2{\sigma }^2}\right),\sigma >0;$

從半正定矩陣的屬性中可以直接得出，如果${\kappa }_1$和 ${\kappa }_2$ 是核，并且如果$c>0$，那么也就是

• $C{\kappa }_1$

• $c+{\kappa }_1$

• ${\kappa }_1+{\kappa }_2$

• ${\kappa }_1{\kappa }_2$.

此外，對于任何實值函數$f:{\mathbb{R}}^p\to \mathbb{R}$，我們可以通過$\kappa :=$ $f(\mathbf{x})?f(\mathbf{y})$構造一個核。注意，在這種情況下，相應的Gram-Matrix的秩最多為1。

圖6.2：${\mathbb{R}}^2$中的數據集和映射$?:{\mathbb{R}}^2\to {\mathbb{R}}^3,?\left(x_1,x_2\right)={\left[x_1,x_2,x_1^2+x_2^2\right]}^{?}$。

Mercer’s Theorem

Theorem 6.3 （Mercer）

對于任何對稱函數 $\kappa :\mathcal{X}\times \mathcal{X}$在$\mathcal{X}\times \mathcal{X}$中是平方可積的，并且滿足 ${\int }_{\mathcal{X}\times \mathcal{X}}f(x)\kappa (x,y)f(y)dxdy\ge 0$ 對于所有$f\in L_2(\mathcal{X})$存在函數 ${?}_i$和標量${\lambda }_i\ge 0$的情況。因此有

$$\kappa (x,y)=\sum _i{\lambda }_i{?}_i(x){?}_i(y)\text{?for?all?}x,y\in \mathcal{X}.\text{\hspace{1em}(6.2)}$$

核是一個連續函數，它取兩個變量$x,y$并將它們映射為一個實值，$\kappa (x,y)=\kappa (y,x)$。當且僅當 $?f(x)\kappa (x,y)f(y)dxdy\ge 0$時，核是正半定的。與核$\kappa$相關，我們可以定義一個積分算子$T_{\kappa }$，當它應用于一個函數$f(x)$時，會產生另一個函數。

$$T_{\kappa }(f(x))=\int \kappa (x,y)f(y)dy=\left[T_{\kappa }f\right](x).$$

這是一個線性函數，因此有特征值${\lambda }_i$和特征函數${?}_i(?)$。它們被定義為

$$T_{\kappa }\left({?}_i(x)\right)=\int \kappa (x,y)?(y)dy={\lambda }_i{?}_i(x)$$

特征值${\lambda }_i$是非負的，特征函數${?}_i(x)$是正定的，即$\int {?}_i(x){?}_j(x)dx={\delta }_{ij}$。一組基礎函數的非零特征值所對應的特征函數，以便內核可以通過以下方式進行分解
$$\kappa (x,y)=\sum _{i=1}^{\infty }{\lambda }_i{?}_i(x){?}_i(y).\text{\hspace{1em}(6.3)}$$

總結

以上是生活随笔為你收集整理的机器学习与高维信息检索 - Note 6 - 核， 核方法与核函数（Kernels and the Kernel Trick）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。