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

　　对称正定看起来像是矩阵的条件。实际上，对于函数K(x,y):Rn×Rm→RK(x,y):Rn×Rm→R，将向量x∈Rnx∈Rn的所有实数取值按顺序视为矩阵的行号，将向量y∈Rmy∈Rm的所有实数取值按顺序视为矩阵的列号，行列号对应的元素值为相应的函数值K(x,y)K(x,y)，则可以得到形状为n∞×m∞n∞×m∞的无穷宽高的矩阵KK。

1  充分性#

　　下面介绍，如果函数K(x,y)K(x,y)（或者矩阵KK）对称正定，则其可以成为核函数（即正定核），也就是存在ϕ(x):Rn→RNϕ(x):Rn→RN，使得K(x,y)=<ϕ(x),ϕ(y)>K(x,y)=<ϕ(x),ϕ(y)>。

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

K=QΛQTK=QΛQT.

　　其中特征向量矩阵Q=[q1,q2,...,qn∞]Q=[q1,q2,...,qn∞]，每个向量qiqi都有n∞n∞维，可以被视为函数qi(x):Rn→Rqi(x):Rn→R。特征向量之间单位正交，从而有qTiqi=1qiTqi=1、qTiqj=0qiTqj=0（或∫qi(x)qj(x)dx=0∫qi(x)qj(x)dx=0）。特征值矩阵Λ=diag(λ1,...,λn∞)Λ=diag(λ1,...,λn∞)。则KK可以被表示为

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

K(x,y)=[λ1−−√q1(x),...,λn∞−−−−√qn∞(x)]⋅[λ1−−√q1(y),...,λn∞−−−−√qn∞(y)]TK(x,y)=[λ1q1(x),...,λn∞qn∞(x)]⋅[λ1q1(y),...,λn∞qn∞(y)]T

　　令ϕ(x)=[λ1−−√q1(x),...,λn∞−−−−√qn∞(x)]ϕ(x)=[λ1q1(x),...,λn∞qn∞(x)]，即有K(x,y)=<ϕ(x),ϕ(y)>K(x,y)=<ϕ(x),ϕ(y)>。

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

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

2  必要性#

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

　　根据条件，K(x,y)=<ϕ(x),ϕ(y)>K(x,y)=<ϕ(x),ϕ(y)>，其中ϕ(x):Rn→RNϕ(x):Rn→RN。则可以表示为

K(x,y)=[ϕ1(x),...,ϕN(x)]⋅[ϕ1(y),...,ϕN(y)]TK(x,y)=[ϕ1(x),...,ϕN(x)]⋅[ϕ1(y),...,ϕN(y)]T

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

K=∑i=1NϕiϕTiK=∑i=1NϕiϕiT

　　其中K∈Rn∞×n∞,ϕ∈Rn∞K∈Rn∞×n∞,ϕ∈Rn∞。对于任意x∈Rn∞x∈Rn∞，有

xKxT=∑i=1NxϕiϕTixT=∑i=1Nxϕi(ϕix)T≥0xKxT=∑i=1NxϕiϕiTxT=∑i=1Nxϕi(ϕix)T≥0

　　所以对称正定。

3  参考#

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