核技巧使用核函数直接计算两个向量映射到高维后的内积，从而避免了高维映射这一步。本文用矩阵的概念介绍核函数$K(x,y)$的充分必要条件：对称（半）正定。

(资料图)

对称正定看起来像是矩阵的条件。实际上，对于函数$K(x,y):\R^n\times \R^m\rightarrow \R$，将向量$x\in \R^n$的所有实数取值按顺序视为矩阵的行号，将向量$y\in \R^m$的所有实数取值按顺序视为矩阵的列号，行列号对应的元素值为相应的函数值$K(x,y)$，则可以得到形状为$n\infty\times m\infty$的无穷宽高的矩阵$K$。

下面介绍，如果函数$K(x,y)$（或者矩阵$K$）对称正定，则其可以成为核函数（即正定核），也就是存在$\phi(x):\R^n\rightarrow \R^N$，使得$K(x,y)=<\phi(x),\phi(y)>$。

由于矩阵$K$对称正定，则可以进行正交分解

$K=Q\Lambda Q^T$.

其中特征向量矩阵$Q=[q_1,q_2,...,q_{n\infty}]$，每个向量$q_i$都有$n\infty$维，可以被视为函数$q_i(x):\R^n\rightarrow \R$。特征向量之间单位正交，从而有$q_i^Tq_i=1$、$q_i^Tq_j=0$（或$\int q_i(x)q_j(x)dx=0$）。特征值矩阵$\Lambda=\text{diag}(\lambda_1,...,\lambda_{n\infty})$。则$K$可以被表示为

\begin{aligned}K&=\sum\limits_{i=1}^{n\infty}\lambda_iq_iq_i^T \\&=\sum\limits_{i=1}^{n\infty}\sqrt{\lambda_i}q_i\sqrt{\lambda_i}q_i^T \\&= [\sqrt{\lambda_1}q_1,...,\sqrt{\lambda_{ n\infty}}q_{ n\infty}]\cdot [\sqrt{\lambda_1}q_1^T,...,\sqrt{\lambda_{ n\infty}}q_{ n\infty}^T]^T\end{aligned}

给上面的矩阵$K$和向量$q_i$加上索引$x,y$，就变成函数的形式，得到

$K(x,y) = [\sqrt{\lambda_1}q_1(x),...,\sqrt{\lambda_{ n\infty}}q_{ n\infty}(x)]\cdot [\sqrt{\lambda_1}q_1(y),...,\sqrt{\lambda_{ n\infty}}q_{ n\infty}(y)]^T$

令$\phi(x)=[\sqrt{\lambda_1}q_1(x),...,\sqrt{\lambda_{ n\infty}}q_{ n\infty}(x)]$，即有$K(x,y)=<\phi(x),\phi(y)>$。

可以看出，正定核一定可以被视为先经过某个维度的映射后再计算内积的过程。那么如何判断某个函数$K(x,y):\R^n\times \R^n\rightarrow \R$是否正定？

以上证明的是在整个实数域内正定的核，称为Mercer核，而常用的正定核只要求在实数域的某个子集正定即可。因此正定核的条件比Mercer核更宽松，正定核包含Mercer核。通常我们处理的数据只属于实数域中的某个区间，并不需要Mercer核这么严格的要求。以上证明假定了矩阵的行列序号为按顺序排列的实数，实际上只要行列号一一对应，不按顺序同样成立，只要在矩阵$K$的左右分别乘上相同的行列交换矩阵即可。也就是常见的证明要求使任意的Gram矩阵正定。

下面证明，如果函数$K(x,y)$是核函数，则其对称正定。

根据条件，$K(x,y) = <\phi(x),\phi(y)>$，其中$\phi(x):\R^n\rightarrow \R^N$。则可以表示为

$K(x,y) = [\phi_1(x),...,\phi_N(x)]\cdot [\phi_1(y),...,\phi_N(y)]^T$

转换成矩阵和向量的形式有

$K=\sum\limits_{i=1}^N\phi_i\phi_i^T$

其中$K\in\R^{n\infty\times n\infty},\phi\in \R^{n\infty}$。对于任意$x\in \R^{n\infty}$，有

$xKx^T=\sum\limits_{i=1}^Nx\phi_i\phi_i^Tx^T=\sum\limits_{i=1}^Nx\phi_i(\phi_ix)^T\geq 0$

所以对称正定。

https://zhuanlan.zhihu.com/p/29527729