(五) 再生核(Reproducing Kernels) PAR

作者: Pan_Ziheng | 来源:发表于2020-07-23 17:22 被阅读0次

Author: Pan

Date: 2020/7/22

在Part1中，我们解释了内积是如何诱导距离的，接下来我们将具体化核的应用,在此之前给出如下定理：

定理3： 令 $X$ 是非空集合,且令 $D :X\times X\rightarrow R$ 是个对称核。

当且仅当 $e^{-tD}$ 正定时， $D$ 是负定的

证明：

充分性: 当 $e^{-tD}$ 正定时， $D$ 是负定的。

因为 $e^{-tD}$ 正定，所以 $e^{-tD}$ 一定条件正定。

所以设 $\vec{a}=(a_{1},a_{2},...,a_{n})^{T};\sum_{i=1}^{n}a_{i}=0;$

$\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}e^{-tD(\vec{x_{i}},\vec{x_{j}})}\geq 0$ ;

因为 $\sum_{i=1}^{n}a_{i}=0;$ 所以 $\sum_{i=1}^{n} a_{i}a_{j}=0$ ;

所以可以得到： $\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}-\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}e^{-tD(\vec{x_{i}},\vec{x_{j}})}\leq 0$ ;

那么 $\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}\frac{1-e^{-tD(\vec{x_{i}},\vec{x_{j}})}}{t}\leq 0$ ;

因为 $\lim_{t\to0} \frac{1-e^{-tD(\vec{x_{i}},\vec{x_{j}})}}{t}=D(\vec{x_{i}},\vec{x_{j}})$

可以得出 $\lim_{t\to0}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}\frac{1-e^{-tD(\vec{x_{i}},\vec{x_{j}})}}{t}=\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}D(\vec{x_{i}},\vec{x_{j}})\leq 0$

所以 $\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}(-D(\vec{x_{i}},\vec{x_{j}}))\geq 0$ ,

因为从上述式子可以得出：-D是条件正定的，根据定理1，当-D条件正定时，D是负定的。

因而充分性得证。

必要性：即当 $D$ 是负定时， $e^{-tD}$ 是正定的。

根据定理2，可构造 $K(\vec{x_{i}},\vec{x_{j}})=D(\vec{x_{i}},\vec{x_{0}})+D(\vec{x_{0}},\vec{x_{j}})-D(\vec{x_{i}},\vec{x_{j}})-D(\vec{x_{0}},\vec{x_{0}})$ ；

那么， $D(\vec{x_{i}},\vec{x_{j}})=D(\vec{x_{i}},\vec{x_{0}})+D(\vec{x_{0}},\vec{x_{j}})-K(\vec{x_{i}},\vec{x_{j}})-D(\vec{x_{0}},\vec{x_{0}})$

$e^{-tD(\vec{x_{i}},\vec{x_{j}})}=e^{-tD(\vec{x_{i}},\vec{x_{0}})}e^{-tD(\vec{x_{0}},\vec{x_{j}})}e^{tK(\vec{x_{i}},\vec{x_{j}})}e^{tD(\vec{x_{0}},\vec{x_{0}})}$

由于K正定，那么 $e^K$ 也一定正定(泰勒展开可以看出)

又 $e^{tD(\vec{x_{0}},\vec{x_{0}})}\geq0$ ;

所以

$\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}e^{-tD(\vec{x_{i}},\vec{x_{j}})}=\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}e^{-tD(\vec{x_{i}},\vec{x_{0}})}e^{-tD(\vec{x_{0}},\vec{x_{j}})}e^{tK(\vec{x_{i}},\vec{x_{j}})}e^{tD(\vec{x_{0}},\vec{x_{0}})}\\=e^{tD(\vec{x_{0}},\vec{x_{0}})}\sum_{i=1}^{n}\sum_{j=1}^{n}(a_{i}e^{-tD(\vec{x_{i}},\vec{x_{0}})})(a_{j}e^{-tD(\vec{x_{0}},\vec{x_{j}})})e^{tK(\vec{x_{i}},\vec{x_{j}})} \geq 0$

所以 $e^{-tD}$ 是正定的,

必要性得证。

从定理3可以看出， $e^{-tD}$ 是正定的，那么其关于概率测度的拉普拉斯变换也是正定的，即

$\int_{0}^{∞}e^{-tD}f(t)dt$ 也是正定的(因为这个积分事实上是一堆正定的东西加在一起）

4. 多项式核

$\forall \alpha \geq 0;d\in N;\vec{x},\vec{y}\in R^{p};K(\vec{x},\vec{y})=(\vec{x}^{T}\vec{y}+\alpha)^{d};$

显然根据定理0，这个核是对称正定的，存在唯一的希尔伯特空间可以将向量从低维映射到高维。

且总是将 $p$ 维向量,映射到 $C_{p+d}^{d}$ 维项向量

e.g. 假设 $\vec{x},\vec{y}\in R^{2};d=2$ ;

$\vec{x}=[x_{1},x_{2}]^{T};\vec{y}=[y_{1},y_{2}]^{T}$

$K(\vec{x},\vec{y})=(x_{1}y_{1}+x_{2}y_{2}+\alpha)^{2}\\=(x_{1}y_{1})^{2}+(x_{2}y_{2})^{2}+\alpha^{2}+2x_{1}x_{2}y_{1}y_{2}+2\alpha x_{1}y_{1}+2\alpha x_{2}y_{2}\\=(x_{1}^{2},x_{2}^{2},\alpha,\sqrt{2}x_{1}x_{2},\sqrt{2\alpha} x_{1},\sqrt{2\alpha} x_{2} )^{T}(y_{1}^{2},y_{2}^{2},\alpha,\sqrt{2}y_{1}y_{2},\sqrt{2\alpha}y_{1},\sqrt{2\alpha }y_{2} )\\=G(\vec{x})^{T}G(\vec{y})$

可见，核将原来的2维的内积映射到了6维的内积,实际上我们并不需要映射G的形式，即得到的结果并不需要显式的计算G，计算内积直接在低维里进行。

5.高斯核

前面有提到欧氏距离 $||\vec{x}-\vec{y}||^{2}$ 是负定的，那么根据定理3， $e^{(-\frac{||\vec{x}-\vec{y}||^{2}}{2\sigma^{2}})}$ 是对称正定核。
$\vec{x},\vec{y}\in R^{p};K(\vec{x},\vec{y})=e^{(-\frac{||\vec{x}-\vec{y}||^{2}}{2\sigma^{2}})}$

因为 $e^{(-\frac{||\vec{x}-\vec{y}||^{2}}{2\sigma^{2}})}=e^{(-\frac{||\vec{x}||^{2}}{2\sigma^{2}})}e^{(\frac{||\vec{x}^{T}\vec{y}||}{\sigma^{2}})}e^{(-\frac{||\vec{y}||^{2}}{2\sigma^{2}})}$

又

$e^{(\frac{||\vec{x}^{T}\vec{y}||}{\sigma^{2}})}=1+\frac{1}{1!}(\frac{||\vec{x}^{T}\vec{y}||}{\sigma^{2}})+\frac{1}{2!}(\frac{||\vec{x}^{T}\vec{y}||}{\sigma^{2}})^2+...\\=(1,\sqrt\frac{1}{1!}(\frac{\vec{x}}{\sigma}),\sqrt\frac{1}{2!}(\frac{\vec{x}}{\sigma})^{2}+...)^{T}(1,\sqrt\frac{1}{1!}(\frac{\vec{y}}{\sigma}),\sqrt\frac{1}{2!}(\frac{\vec{y}}{\sigma})^{2}+...)$

上面这个泰勒展开可以看出，高斯核将原向量映射到无穷维做内积，且 $e^{(-\frac{||\vec{x}||^{2}}{2\sigma^{2}})}，e^{(-\frac{||\vec{y}||^{2}}{2\sigma^{2}})}$ 事实上是对数据做了一个归一化。

回到一开始的异或问题，核其实对应了一个非线性变换，若我们采用多项式核处理异或问题，那么其中一个分类平面在二维里的投影将变成这样：

Fig.4 用多项式核来解决异或问题

它将空间看似划分为四块，但高维内积结果大于0的在左下和右上区域，小于0的在左上和右下区域。

如Fig.5所示：

Fig.5 续图

(五) 再生核(Reproducing Kernels) PAR

4. 多项式核

5.高斯核

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

人工智能/模式识别/机器学习精华专题

机器学习与数据挖掘