核方法|机器学习推导系列（八）
一、线性不可分问题
有时线性可分的数据夹杂一点噪声，可以通过改进算法来实现分类，比如感知机的口袋算法和支持向量机的软间隔。但是有时候数据往往完全不是线性可分的，比如下面这种情况：
在异或问题中数据往往不是线性可分的，但通过将数据映射到高维空间后就可以实现线性可分。可以认为高维空间中的数据比低维空间的数据更易线性可分。对于异或问题，我们可以通过寻找一个映射\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
