非线性支持向量的核函数，核技巧与正定核判定

https://cuijiahua.com/blog/2017/11/ml_9_svm_2.html

SVM通过某种事先选择的非线性映射（核函数）将输入变量映到一个高维特征空间，将其变成在高维空间线性可分，在这个高维空间中构造最优分类超平面。

image.png

将原空间的非线性空间（ $x_1,x_2$ ）投影到（ $z_1$ , $z_2$ ）

x->z 变换的公式： $z=\phi=(x_1^2,x_2^2) ^T$

边界函数： $w_1(x_1^2)+w_2(x_2^2)+b=0=>w_1(z_1)+w_2(z_2)+b$

可能上面那个例子看不出来是低纬到高纬的映射，那我们再举个例子：

红点集代表 $x^2+y^2=9$ ，蓝点集代表 $x^2+y^2=1$

image.png

将 $(x,y)$ 映射为 $(x,y,x^2+y^2)$

image.png

可见红色和蓝色的点被映射到了不同的平面，在更高维空间中是线性可分的（用一个平面去分割）

再举个例子：

$a_1x_1+a_2x_1^2+a_3x_2+a_4x_2^2+a_5x_1x_2+a_6=0$

$z_1=x_1 , z_2=x_1^2 , z_3=x_2 , z_4=x_2^2 , z_5=x_1x_2$

$\sum_{i=1}^{5}a_iz_i+a_6=0$

这个新的坐标 $z_1$ , $z_2$ , $z_3$ , $z_4$ , $z_5$ 的方程，就是一个超平面方程，它的维度是5

image.png

核函数的定义：

$\phi(x): x \rightarrow 另一个（高维）的x'$

核函数： $K(x_1,x_2)=\phi(x_1)*\phi(x_2)$ ，乘是 $\phi(x)$ 的向量内积，即 $\vec{(a1,a2)}\vec{(b1,b2)}=a1b1+a2b2$

在实际中，对一个非线性可分数据，我们不是先去定义转换函数数 $\phi(x)$ ，再找出其对应的核函数K，而是直接用一些常用核函数代入非线性可分支持向量机，然后查看分类效果，再调整核函数的类型，这样就隐式地实现了低维到高维的映射，而不用显式地定义映射函数 $\phi(x)$ 和特征空间，这种方法叫核技巧。

在SVM中的具体应用：

目标函数： $W(a)=\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}a_ia_jy_iy_j\phi(x_i)\phi(x_j)-\sum_{i=1}^{N}a_i=$
$\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}a_ia_jy_iy_jK(x_i,x_j)-\sum_{i=1}^{N}a_i$

分类决策函数： $f(x)=sign(\sum_{i=1}^{N}a_i^*y_i\phi(x_i)\phi(x)+b^*)=sign(\sum_{i=1}^{N}a_i^*y_iK(x_i,x)+b^*)$

怎么证明一个给定函数 $K(x_i,x_j)$ 是核函数？

核函数 $K(x,x′)$ 是对称函数。
对任意属于样本集X中的 $xi$ , 核函数 $K(x,x′)$ 对应的Gram矩阵是半正定矩阵。
Gram矩阵定义为： $G=[K(x_i,x_j)]_{mm}$ ，其实就是把不同样本点放到核函数中去计算，因此G的shape和样本数量m相关，为mm。

补充：

半正定：若任意不为0的实列向量X，都有 $X^TAX≥0$
正定：若 $A=A^T$ ，对任意 $0 \ne X$ ，有 $XAX^T>0$
Gram矩阵： $[K_{ij}]_{m*m}=[K(x_i,x_j)]_{m*m}$

证明：

$K(x,z)=\phi(x)\phi(z)$

对任意 $c_1,c_2,...,c_m \in R$ ，有
$\sum_{i,j=1}^{N}c_ic_jK(x_i,x_j)=(\sum_{i}c_i\phi(x_i))(\sum_{j}c_j\phi(x_j))=(\sum_{i}c_i\phi(x_i))^2>=0$ 说明Gram矩阵是正定的。