核方法|機器學習推導系列（八）
一、線性不可分問題
有時線性可分的數據夾雜一點雜訊，可以通過改進演算法來實現分類，比如感知機的口袋演算法和支援向量機的軟間隔。但是有時候數據往往完全不是線性可分的，比如下面這種情況：
在異或問題中數據往往不是線性可分的，但通過將數據映射到高維空間後就可以實現線性可分。可以認為高維空間中的數據比低維空間的數據更易線性可分。對於異或問題，我們可以通過尋找一個映射\phi (x)將低維空間中的數據x映射成高維空間中的z來實現數據的線性可分，例如：
\underset{二維}{\underbrace{x=(x_{1},x_{2})}}\overset{\phi (x)}{\rightarrow}\underset{三維}{\underbrace{z=(x_{1},x_{2},(x_{1}-x_{2})^{2})}}
然後在新的空間中，該數據就可以實現線性可分：
二、核方法的引出
映射到高維空間以後出現的問題是計算複雜度的加大，例如在支援向量機的求解過程中求解的優化問題可以轉換為如下的優化問題：
\left\{\begin{matrix}
\underset{\lambda }{min}\; \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}x_{i}^{T}x_{j}-\sum_{i=1}^{N}\lambda _{i},i=1,2,\cdots ,N\\
s.t.\; y_{i}(w^{T}x_{i}+b)>0,i=1,2,\cdots ,N\\
\sum_{i=1}^{N}\lambda _{i}y_{i}=0\\
\lambda _{i}\geq 0,i=1,2,\cdots ,N
\end{matrix}\right.
將數據映射到高維空間後也就需要求解以下優化問題：
\left\{\begin{matrix}
\underset{\lambda }{min}\; \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}{\color{Red}{\phi (x_{i})^{T}\phi (x_{j})}}-\sum_{i=1}^{N}\lambda _{i},i=1,2,\cdots ,N\\
s.t.\; y_{i}(w^{T}x_{i}+b)>0,i=1,2,\cdots ,N\\
\sum_{i=1}^{N}\lambda _{i}y_{i}=0\\
\lambda _{i}\geq 0,i=1,2,\cdots ,N
\end{matrix}\right.
將數據拓展到高維的方法可以用來解決完全非線性的問題：
| 線性可分 | 允許一點點錯誤 | 嚴格非線性 |
|---|---|---|
| PLA | Pocket Alorithm | \phi (x)+PLA |
| Hard-Margin SVM | Soft-Margin SVM | \phi (x)+Hard-Margin SVM |
然而在上面的方法中如果先將\phi (x_{i})與\phi (x_{j})計算出來然後再做點積，由於維度特別高加之得到\phi (x_{i})與\phi (x_{j})也需要計算量，因此計算量是相當大的，因此就有了核方法。
通過使用核函數我們可以直接得到\phi (x_{i})與\phi (x_{j})的內積，正定核函數定義如下：
\forall x,x^{‘}\in \mathcal{X} ,\exists \phi \in \mathcal{H} 😡 \mapsto z,s.t.\; K(x,x^{‘})=\phi (x_{i})^{T}\phi (x_{j})=<\phi (x_{i}),\phi (x_{j})>,則稱K(x,x^{‘})是一個正定核函數。
其中\mathcal{H}是Hilbert空間（完備的可能是無限維的被賦予內積的線性空間），如果去掉內積這個條件我們簡單地稱為核函數。
Hilbert空間定義中的完備指的是對極限是封閉的，被賦予內積代表空間中的元素滿足以下性質：
①\; <f,g>=<g,f>\\
②\; <f,f>\geq 0,「=」\Leftrightarrow f=0\\
③\; <r_{1}f_{1}+r_{2}f_{2},g>=r_{1}<f_{1},g>+r_{2}<f_{2},g>
因為支援向量機的求解只用到內積運算，所以使用核函數會大大簡化運算量。
三、正定核函數的證明
正定核函數還有另外一個定義：
如果核函數滿足以下兩條性質：
①對稱性
②正定性
則稱核函數K(x,z)為正定核函數。
這個定義也就是正定核函數的充要條件，其中兩條性質分別指的是：
①對稱性\Leftrightarrow K(x,z)=K(z,x);
②正定性\Leftrightarrow任取N個元素x_{1},x_{2},\cdots ,x_{N}\in \mathcal{X},對應的Gram\; matrix\; K=[K(x_{i},x_{j})]是半正定的。
證明K(x,z)=\phi (x)^{T}\phi (z)\Leftrightarrow對稱性+矩陣K半正定：
①\Rightarrow:
首先證明對稱性
K(x,z)=<\phi (x),\phi (z)>\\
K(z,x)=<\phi (z),\phi (x)>\\
又內積具有對稱性，即<\phi (x),\phi (z)>=<\phi (z),\phi (x)>\\
\therefore K(x,z)=K(z,x)\\
\therefore K(x,z)滿足對稱性
然後證明
欲證Gram\; matrix:K=[K(x_{i},x_{j})]_{N\times N}半正定\\
即證：\forall \alpha \in \mathbb{R}^{n},\alpha ^{T}K\alpha \geq 0\\
\because \alpha ^{T}K=\begin{pmatrix}
\alpha _{1} & \alpha _{2} & \cdots & \alpha _{N}
\end{pmatrix}_{1\times N}\begin{bmatrix}
a_{11}& a_{12}& \cdots & a_{1N}\\
a_{21}& a_{22}& \cdots & a_{2N}\\
\vdots & \vdots & \ddots & \vdots \\
a_{N1}& a_{N2}& \cdots & a_{NN}
\end{bmatrix}_{N\times N}\begin{pmatrix}
\alpha _{1}\\
\alpha _{2}\\
\vdots \\
\alpha _{N}
\end{pmatrix}_{N\times 1}\\
=\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha _{i}\alpha _{j}K_{ij}\\
=\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha _{i}\alpha _{j}<\phi (x_{i}),\phi (x_{j})>\\
=\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha _{i}\alpha _{j}\phi (x_{i})^{T}\phi (x_{j})\\
=\sum_{i=1}^{N}\alpha _{i}\phi (x_{i})^{T}\sum_{j=1}^{N}\alpha _{j}\phi (x_{j})\\
=\begin{bmatrix}
\sum_{i=1}^{N}\alpha _{i}\phi (x_{i})\end{bmatrix}^{T}\sum_{j=1}^{N}\alpha _{j}\phi (x_{j})\\
=<\sum_{i=1}^{N}\alpha _{i}\phi (x_{i}),\sum_{j=1}^{N}\alpha _{j}\phi (x_{j})>\\
=\left \|\sum_{i=1}^{N}\alpha _{i}\phi (x_{i}) \right \|^{2}\geq 0\\
\therefore K是半正定的。
②\Leftarrow:
\;對K進⾏特徵分解，對於對稱矩陣K=V\Lambda V^{T}，那麼令\phi (x_{i})=\sqrt{\lambda _{i}}V_{i}，\\其中V_{i}是特徵
向量，於是就構造了K(x,z)=\sqrt{\lambda _{i}\lambda _{j}}V_{i}^{T}V_{j}。
得證。
說明一下證明矩陣半正定的兩種方法：
①特徵值\geq 0
②\forall \alpha \in \mathbb{R}^{n},\alpha ^{T}A\alpha \geq 0
