Kernal

引入

??在實際數據中常常遇到不可線性分割的情況，此時通常需要將其映射到高維空間中，使其變得線性可分。例如二維數據：

通過映射$?(x_1,x_2)=(x_1^2,\sqrt{2}{x}_1{x}_2,x_2^2)$，將數據投影到三維空間，下面展示的是一個二維投影（三維畫不出來）：

??于是我們可以找到一個超平面（如$x_1^2+x_2^2=c$）來把兩類數據分開。這種投影方法被稱為顯式投影法，即構造出一個函數$?(x)$將數據從原始空間投影到高維空間。

??在一些模型中（如SVM），需要計算高維空間下數據點之間的內積$x_1^{?}{x}_2$，反映數據點之間的相似度。然而將數據點投影后再計算會產生許多時間花費和空間花費。那有沒有什么方法能直接計算出內積，跳過投影的過程呢？~~有的兄弟，有的。~~于是核方法誕生了。

定義

??核方法（Kernel Methods）是一類機器學習算法，旨在通過將數據從原始空間隱式映射到高維特征空間來解決非線性問題，同時利用核函數高效計算特征空間中的內積，而無需顯式計算高維特征向量。
??設輸入空間為$\mathcal{X}$，如下形式的函數稱為核函數：
$$\mathcal{K}:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$$
滿足其對應的Gram矩陣是正定的或半正定的，這保證了核函數在數學上定義了一個有效的內積空間。
??則這個核函數一定能寫成某個高維空間的內積$\mathcal{K}(x,x^{\prime })=?(x{)}^{?}?(x^{\prime })$，這由Mercer定理支持。

Mercer定理

描述

??如果核函數$\mathcal{K}:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$滿足Mercer條件，即正定性，則存在一個映射$?:\mathcal{X}\to \mathcal{H}$，將$x$映射到某個希爾伯特空間，使得：
$$\mathcal{K}(x,x^{\prime })=?(x{)}^T?(x^{\prime })$$

有限情形證明

先在有限數據集 { x 1 , . . . , x N } ? X \set{x_1, ..., x_N} \subset \mathcal{X} {x1?,...,xN?}?X上證明：由于$\mathcal{K}$是對稱正定矩陣，則可以分解為
$$\begin{gathered} \mathcal{K}=U^{?}\Lambda U \\ \Lambda =\text{diag?}({\lambda }_1,...,{\lambda }_N),{\lambda }_i\ge 0 \end{gathered}$$
$U$是正交矩陣，$U^{?}U=I$，列向量$u_1,...,u_N$是特征向量。
定義特征映射為$?:\mathcal{X}\to {\mathbb{R}}^N$為：
$$?(x_i)={\Lambda }^{1/2}{u}_i$$
其中${\Lambda }^{1/2}=\text{diag?}\left(\sqrt{{\lambda }_1},...,\sqrt{{\lambda }_N}\right)$
驗證內積：
$$?(x_i{)}^{?}?(x_j)=u_i^{?}\Lambda u_j=\mathcal{K}(x_i,x_j)$$
補充：若$\mathcal{K}$的秩$r<N$，（可能有零特征值），特征空間的維度可以降為$r$，即只保留非零特征值對應的分量。
這證明了對于有限數據集，核函數可以通過特征分解構造一個有限維特征空間的內積。

一般情形證明

??為了嚴謹性，對于一般核函數$\mathcal{K}(x,x^{\prime })$，輸入空間$\mathcal{X}$可能是連續的（如$\mathcal{X}={\mathbb{R}}^d$或緊致域），且核函數可能定義在無窮多點上。Mercer定理的完整形式需要函數空間的理論，特別是再生核希爾伯特空間（RKHS）。
??假設：
（1）$\mathcal{X}$是緊致集
（2）$\mathcal{K}(x,x^{\prime })$是對稱的、連續的，且滿足Mercer條件（正定性）。
（3）正定性在連續情形下定義為：對于任意平方可積函數$f\in {\mathcal{L}}^2(\mathcal{X})$，有：
$${?}_{\mathcal{X}\times \mathcal{X}}f(x)\mathcal{K}(x,x^{\prime })f(x^{\prime })dxd{x}^{\prime }\ge 0$$
??然后對$\mathcal{K}$進行特征展開，核函數$\mathcal{K}(x,x^{\prime })$作為一個對稱正定算子，可以通過特征值分解表示。定義積分算子：
$$(T_{K}f)(x)={\int }_{\mathcal{X}}\mathcal{K}(x,x^{\prime })f(x^{\prime })d{x}^{\prime }$$
$T_K$是一個緊致、自我伴隨的算子（因為$\mathcal{K}$對稱且連續）。根據希爾伯特-施密特理論，$T_K$有可數個特征值${\lambda }_i\ge 0$和對應的特征函數${\psi }_i(x)$，滿足：
$$T_K{\psi }_i={\lambda }_i{\psi }_i,{\int }_{\mathcal{X}}\mathcal{K}(x,x^{\prime }){\psi }_i(x^{\prime })d{x}^{\prime }={\lambda }_i{\psi }_i$$
特征函數 { ψ i } \left\{\psi_i\right \} {ψi?}構成了${\mathcal{L}}^2(\mathcal{X})$的正交基，滿足：
$${\int }_{\mathcal{X}}{\psi }_i(x){\psi }_j(x)dx={\delta }_{ij}$$
核函數可以表示為特征展開：
$$\mathcal{K}(x,x^{\prime })=\underset{i=1}{\sum ^{\infty }}{\lambda }_i{\psi }_i(x){\psi }_i(x^{\prime })$$
這一級數在$\mathcal{X}\times \mathcal{X}$上均勻收斂（因為$\mathcal{K}$連續且$\mathcal{X}$緊致）

然后我們構造特征映射$?:\mathcal{X}\to \mathcal{H}$，其中$\mathcal{H}$是希爾伯特空間（通常是$l^2$，無窮維序列空間），可以理解為無限維的歐幾里得空間。
$$?(x)=\left(\sqrt{{\lambda }_1}{\psi }_1(x),\sqrt{{\lambda }_1}{\psi }_2(x),...\right)$$
每個$?(x)$是一個無窮序列，其分量為$\sqrt{{\lambda }_i}{\psi }_i(x)$
在$\mathcal{H}$中的內積定義為：
$$?(x{)}^{?}?(x^{\prime })=\underset{i=1}{\sum ^{\infty }}\left(\sqrt{{\lambda }_i}{\psi }_i(x)\right)\left(\sqrt{{\lambda }_i}{\psi }_i(x^{\prime })\right)=\underset{i=1}{\sum ^{\infty }}{\lambda }_i{\psi }_i(x){\psi }_i(x^{\prime })=\mathcal{K}(x,x^{\prime })$$