一、简介

​ 从核算的视点，该办法叫$KernelTrick$：防止一步一步先把(x)求出，再把内积求出来，而是一步到位，直接把样本点带进核办法就能够把内积求出来。减少核算量

​ 从思想的视点，该办法叫$KernelMethod$：把一个低维空间的非线性问题转化到高维空间的线性问题，运用核函数的性质来求解。

​ 该部分最重要的叫做$KernelFunction$，它的来历便是由于在咱们做分类问题时，例如非线性的不可分给咱们带来了一些窘境，咱们能够运用高维转化进而运用$KernelFunction$去处理它，又或者是对偶表示带来内积，假如你是高维空间，那么(x)就很难求，假如咱们先去找到一个核函数，就能直接求出内积（核函数蕴含了一个非线性转化以及非线性转化后的一个内积）

​ 接下来咱们就详细的介绍一下核办法涉及到的一些知识点。

二、线性不可分问题

有时线性可分的数据夹杂一点噪声，能够经过改进算法来完成分类，比方感知机的口袋算法和支撑向量机的软距离。但是有时候数据往往彻底不是线性可分的，比方下面这种情况：

在异或问题中数据往往不是线性可分的，但经过将数据映射到高维空间后就能够完成线性可分。能够以为高维空间中的数据比低维空间的数据更易线性可分。关于异或问题，咱们能够经过寻找一个映射$(x)$将低维空间中的数据$x$映射成高维空间中的$z$来完成数据的线性可分，例如：

x=(x1,x2)⏟二维→(x)z=(x1,x2,(x1−x2)2)⏟三维\underset{二维}{\underbrace{x=(x_{1},x_{2})}}\overset{\phi (x)}{\rightarrow}\underset{三维}{\underbrace{z=(x_{1},x_{2},(x_{1}-x_{2})^{2})}}二维x=(x1​,x2​)​​→(x)三维z=(x1​,x2​,(x1​−x2​)2)​​

然后在新的空间中，该数据就能够完成线性可分：

三、核办法的引出

映射到高维空间以后出现的问题是核算复杂度的加大，例如在支撑向量机的求解过程中求解的优化问题能够转化为如下的优化问题：

{min  12∑i=1N∑j=1NijyiyjxiTxj−∑i=1Ni,i=1,2,⋯ ,Ni≥0,i=1,2,⋯ ,N\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 \\ \lambda _{i}\geq 0,i=1,2,\cdots ,N \end{matrix}\right.{min​21​∑i=1N​∑j=1N​i​j​yi​yj​xiT​xj​−∑i=1N​i​,i=1,2,⋯,Ni​≥0,i=1,2,⋯,N​

将数据映射到高维空间后也就需求求解以下优化问题：

{min  12∑i=1N∑j=1Nijyiyj(xi)T(xj)−∑i=1Ni,i=1,2,⋯ ,Ni≥0,i=1,2,⋯ ,N\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 \\ \lambda _{i}\geq 0,i=1,2,\cdots ,N \end{matrix}\right.{min​21​∑i=1N​∑j=1N​i​j​yi​yj​(xi​)T(xj​)−∑i=1N​i​,i=1,2,⋯,Ni​≥0,i=1,2,⋯,N​

将数据拓展到高维的办法能够用来处理彻底非线性的问题：

但是在上面的办法中假如先将 (xi)\phi\left(x_i\right)(xi​) 与 (xj)\phi\left(x_j\right)(xj​) 核算出来然后再做点积，由于维度特别高加之得到 (xi)\phi\left(x_i\right)(xi​) 与 (xj)\phi\left(x_j\right)(xj​) 也需求核算量，因而核算量是相当大的，因而就有了核办法。 经过运用核函数咱们能够直接得到 (xi)\phi\left(x_i\right)(xi​) 与 (xj)\phi\left(x_j\right)(xj​) 的内积，正定核函数界说如下:

其间 $\mathcal{H}$ 是$HilbertSpace$（齐备的可能是无限维的被陚予内积的线性空间），假如去掉内积这个条件咱们简单地称为核函数。 Hilbert空间界说:

• 齐备指的是对极限是关闭的，例如有一个序列{kn}\{ k_n \}{kn​}是Hilbert空间的一个元素，那么limn−>∞kn=K∈H\underset{n-> ∞} {lim} k_n = K ∈ \mathcal{H}n−>∞lim​kn​=K∈H

• 被赋予内积代表空间中的元素满意以下性质:

• 线性空间即向量空间

由于支撑向量机的求解只用到内积运算，所以运用核函数会大大简化运算量。

四、正定核函数的证明

正定核函数还有别的一个界说：

假如核函数满意以下两条性质： ①对称性 ②正定性 则称核函数$K(x,z)$为正定核函数。

这个界说也便是正定核函数的充要条件，其间两条性质分别指的是：

①对称性$\iff K(x,z)=K(z,x)$; ②正定性$\iff$任取$N$个元素x1,x2,⋯ ,xN∈Xx_{1},x_{2},\cdots ,x_{N}\in \mathcal{X}x1​,x2​,⋯,xN​∈X,对应的Gram  matrix  K=[K(xi,xj)]Gram\; matrix\; K=[K(x_{i},x_{j})]GrammatrixK=[K(xi​,xj​)]是半正定的。

证明K(x,z)=(x)T(z)⇔K(x,z)=\phi (x)^{T}\phi (z)\LeftrightarrowK(x,z)=(x)T(z)⇔对称性+矩阵$K$半正定：

①$\Rightarrow$: 首先证明对称性

$$K(x,z)=<(x),(z)>K(z,x)=<(z),(x)>又内积具有对称性，即<(x),(z)>=<(z),(x)>\therefore K(x,z)=K(z,x)\therefore K(x,z)满意对称性$$

然后证明

PS：先说明一下证明矩阵半正定的两种办法：

①特征值$\ge 0$ ②∀∈Rn,TA≥0\forall \alpha \in \mathbb{R}^{n},\alpha ^{T}A\alpha \geq 0∀∈Rn,TA≥0

欲证Gram  matrix:K=[K(xi,xj)]NN半正定即证：∀∈Rn,TK≥0∵TK=(12⋯N)1N[a11a12⋯a1Na21a22⋯a2N⋮⋮⋱⋮aN1aN2⋯aNN]NN(12⋮N)N1=∑i=1N∑j=1NijKij=∑i=1N∑j=1Nij<(xi),(xj)>=∑i=1N∑j=1Nij(xi)T(xj)=∑i=1Ni(xi)T∑j=1Nj(xj)=[∑i=1Ni(xi)]T∑j=1Nj(xj)=<∑i=1Ni(xi),∑j=1Nj(xj)>=∥∑i=1Ni(xi)∥2≥0∴K是半正定的。欲证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是半正定的。欲证Grammatrix:K=[K(xi​,xj​)]NN​半正定即证：∀∈Rn,TK≥0∵TK=(1​​2​​⋯​N​​)1N​⎣⎡​a11​a21​⋮aN1​​a12​a22​⋮aN2​​⋯⋯⋱⋯​a1N​a2N​⋮aNN​​⎦⎤​NN​⎝⎛​1​2​⋮N​​⎠⎞​N1​=i=1∑N​j=1∑N​i​j​Kij​=i=1∑N​j=1∑N​i​j​<(xi​),(xj​)>=i=1∑N​j=1∑N​i​j​(xi​)T(xj​)=i=1∑N​i​(xi​)Tj=1∑N​j​(xj​)=[∑i=1N​i​(xi​)​]Tj=1∑N​j​(xj​)=<i=1∑N​i​(xi​),j=1∑N​j​(xj​)>=∥∥​i=1∑N​i​(xi​)∥∥​2≥0∴K是半正定的。

②$\Leftarrow$:

  对K进⾏特征分化，关于对称矩阵K=VVT，那么令(xi)=iVi，其间Vi是特征向量，于是就结构了K(x,z)=ijViTVj。\;对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}。对K进⾏特征分化，关于对称矩阵K=VVT，那么令(xi​)=i​​Vi​，其间Vi​是特征向量，于是就结构了K(x,z)=i​j​​ViT​Vj​。

得证。

“开启生长之旅！这是我参与「日新计划 2 月更文应战」的第 3 天，点击检查活动概况”