(四) 再生核(Reproducing Kernels) PAR

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

(四) 再生核(Reproducing Kernels) PAR
(五) 再生核(Reproducing Kernels) PAR
2019-01-07 kernels(核函数)
核函数（Kernels）
机器学习与深度学习模型复现与知识点汇总指南
（六）核主元分析 PART1
给i386写驱动 -2
跟着白泽读paper丨kAFL: Hardware-Assist
再生（四）
2019-10-18

Author: Pan

Date: 2020/7/21

"A complete pattern-classification problem cast in a hight-dimension space nonlinearly is more likely to be linearly separable than in a low-dimension space." --Cover's Theorem

1.核的定义与性质，从异或问题谈起。

在解释上面这段话之前，我们需要先讨论一个二维的异或问题。

Fig.1 异或问题

在Fig.1 中，有两类的点，第一类是X形点，还有一类是圆形的点。我们要做的事情是用一条直线将图中的已知点分开(注意，只能用一条直线，将图中平面切成两半，每一半的空间里只有一种类别,要么X,要么O)。想象自己是象棋棋盘上的車,想要凭借一己之力将它们划分个“楚河汉界”....这貌似是在开我玩笑，图中这些有颜色的线没有一条完成它们的使命，其实任何一条这个平面内的直线都做不到。

那么怎么办呢? 炮带着車从棋盘上飞了起来，那一刻，車泪流满面，他看见了新世界Fig.2。也就是一开始的那一段话，高维是比低维更容易线性可分的。要是所有问题都能这样映射到高维就好了。

Fig.2 三维上看原来的异或问题

这想法好到让人感动到想哭，好到不真实，好到令我困惑第三个维度是怎么出现在我的生命中的。。。

我们并不懂这样一个从低维到高维的映射 $\phi$ 是如何发生的：

$Input:\vec{x}\in R^{p}\rightarrow \vec{\phi}(\vec{x})\in R^{r}；p<r$

当然，我们可以选择找 $\phi$ ,像神经网络一样去找 $\phi$ ,即便假设空间大到让模型哭泣，经常需要解决过拟合的问题，但神经网络本身也是个神迹。令人遗憾的是,今天我是个懒人,我能否在不通过这个 $\phi$ 的情况下，显式的在低维里完成隐式的高维里的线性分类过程？

首先，我们既然不想知道这个映射到底是什么，那么我们需要知道什么，才能让我们洞见高维分类的过程？

我们知道，在Fig.2中，是那个(超)平面让我们将两类分开，那么本质上是什么左右了我们的分类结果？其实是超平面与点的内积将其映射成一个数，那个数的符号决定了类别。

Oh,内积！

好的，也许我只需要知道内积的结果就够了。

所以定义我们的核来作为我们内积的结果：

$X\subset R^{p} 是非空集合；\\K:X\times X \rightarrow R \\=K(\vec{x_{i}},\vec{x}_{j})$

这个核可以看作高维内积。

我们的目的是将特征空间上的点(原来空间中的点)映射到再生核希尔伯特空间(reproducing kernel Hilbert space；RKHS)（高维空间）

我们知道无穷维希尔伯特空间是有限维欧式空间的拓展，有限维欧式空间是它的一个特例。

今天我们手上有个线性空间(向量空间)，我们知道基，我们可以线性相加减，可以数乘，可以定位到空间里的每个点。

我们想知道距离这样的概念怎么办呢，我们可以在其上定义范数，于是我们就有了赋范线性空间空间。(假如我们在这里定义完备性,即空间里的柯西列都是收敛到该空间中的某个量，见Fig.3，我们将得到巴纳赫空间。)我们想知道向量之间的角度怎么办呢，我们可以在其上定义内积，于是我们就有了内积空间。我们想在有限维数的空间中定义完备性，就可以得到有限维欧式空间。假如我们想在无限维空间中定义完备性，我们就可以得到希尔伯特空间。

Fig.3 柯西列收敛后的量依旧在这个空间中[1]

为什么要无穷维呢？那是因为之后有可能映射到无穷维，比如高斯核(泰勒展开后无穷维)，所以我们希望能映射到这上面来探索下内积。

2. 核的性质

既然我们想要探索内积，那么我们就需要定义什么样的条件下，我们的操作可以叫做内积：

1. 对称性：

$<\vec{\phi}(\vec{x}_{i}),\vec{\phi}(\vec{x}_{j})>=$

2. 线性：

$<a\vec{\phi}(\vec{x}_{i})+b\vec{\phi}(\vec{x}_{j}),\vec{\phi}(\vec{x}_{k})>=a+b$

3. 正定性：

$\forall a_{i},a_{j}\in R; \space \sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}K(\vec{x}_{i},\vec{x}_{j})\geq0$

直觉上，对称性和线性再正常不过，那为什么要满足一个正定性？

那么我们想想这个东西 $\vec{x}\cdot K\cdot \vec{x}^{T}$ ，他是我们判定一个矩阵是否正定的条件;假如 $K=E(单位矩阵)$ ; 这个其实就是我们平时的向量点积。那么，假如K是个半正定矩阵，即 $\vec{x}\cdot K\cdot \vec{x}^{T}\geq0$ ，这究竟与平时我们理解的点积有什么渊源呢？由于K是个半正定矩阵，我们又都是在实空间内讨论的，所以K一定是个实对称矩阵，对于任意实对称矩阵，我们都能进行特征分解，将矩阵分解成一个特征向量组成的正交矩阵的转置 $U^{T}$ ，一个对角线上全是特征值的对角矩阵 $\Lambda$ ，以及特征向量组成的正交矩阵 $U$ 。

即： $K=U^{T}\cdot \Lambda\cdot U$ ,我们将这个式子代入上面那个式子，可以得到： $\vec{x}^{T}K\vec{x}=\vec{x}^{T}U^{T}\cdot \Lambda\cdot U\vec{x}=(U\vec{x})^{T}\cdot \Lambda\cdot (U\vec{x})$

我们知道正交变换具有保范性，经过正交变换后的向量具有相同的距离，且两个向量经过同一个正交变换后具有相同的角度。也就是原向量经过正交变换后其实只是将坐标基旋转了一下，而 $\Lambda$ 则是将向量在各个维度上进行特征值倍数的拉伸。所以本质上是经过矩阵变换后的内积形式。由于平时自己和自己做点积都必须大于0，这也可想而知，为什么我们需要正定性。

其实我们这里说的正定性并不代表矩阵是正定的，而是对应于正定核的概念，当矩阵是半正定时，对应的K核是正定核。

由此，我们的核具有了对称性，线性，以及正定性。

3. 核与距离度量

既然我们引出了核正定的概念，我们继续定义一个条件正定性，这个条件正定性，是之后一些证明的基础。

我们定义核的条件正定性： $\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}K(\vec{x}_{i},\vec{x}_{j})\geq0;\vec{a}=[a_{1},a_{2},...a_{i}...a_{j},...,a_{n}],\sum_{i=1}^{n}a_{i}=0$

定义核的条件正定性是为了引出一个定理：

定理1：如果K是条件正定核，-K是负定的。

为什么要关心负定这样的性质呢？

实际上这与我们的距离度量有关，令 $\sum_{i=1}^{n}a_{i}=0$ ； $\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}||\phi(\vec{x_{i}})-\phi(\vec{x_{j}})||^{2}_{2}=\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}(\phi(\vec{x_{i}})^{T}\cdot\phi(\vec{x_{i}})-2\cdot\phi(\vec{x_{i}})^{T}\cdot\phi(\vec{x_{j}})+\phi(\vec{x_{j}})^{T}\cdot\phi(\vec{x_{j}}))\\=\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}\phi(\vec{x_{i}})^{T}\cdot\phi(\vec{x_{i}})-\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}2\cdot\phi(\vec{x_{i}})^{T}\cdot\phi(\vec{x_{j}})+\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}\phi(\vec{x_{j}})^{T}\cdot\phi(\vec{x_{j}}))\\=\sum_{j=1}^{n}a_{j}\sum_{i=1}^{n}a_{i}\phi(\vec{x_{i}})^{T}\cdot\phi(\vec{x_{i}})-\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}2\cdot\phi(\vec{x_{i}})^{T}\cdot\phi(\vec{x_{j}})+\sum_{i=1}^{n}a_{i}\sum_{j=1}^{n}a_{j}\phi(\vec{x_{j}})^{T}\cdot\phi(\vec{x_{j}}))\\=-\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}2\cdot\phi(\vec{x_{i}})^{T}\cdot\phi(\vec{x_{j}})=-\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}2\cdot\ K(\vec{x}_{i},\vec{x}_{j})=\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i}a_{j}2\cdot\ [-K(\vec{x}_{i},\vec{x}_{j})]$

从结果上来说，当K条件正定时，-K是负定的，那么我们的距离度量的矩阵是半负定的(2是常数不影响正负判定，距离的核是负定核)。这也说明，内积是可以诱导出距离度量的。

上面的只是一个引导性的例子，那么我们如何在度量核与再生核之间建立关系呢？

定理2：令 $X$ 是非空集合, $\vec{x_{0}}\in X$ 且令 $D :X\times X\rightarrow R$ 是个对称核。

$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$ 为负定核时， $K$ 为正定核。

也许你会很困惑定理2中间那个式子，但是假如我给出 $\vec{a}\cdot \vec{b}=|\vec{a}||\vec{b}|cos(\theta)=\frac{1}{2}(|\vec{a}|^{2}+|\vec{b}|^{2}-|\vec{c}|^{2})$

这个余弦定理的式子是不是很熟悉，而实际上余弦定理中的是向量，基于零点做的余弦定理，没有最后一项，相当于零点是这个余弦定理的见证人，而上面那个式子中这个见证人换成了点 $x_{0}$ 。

下面我们将对定理2进行证明。

证明：

必要性：即K为正定核时，D为负定核。

当K为正定核时，那么K也一定条件正定。

所以设 $\sum_{i=1}^{n}a_{i}=0$ ；

$\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}K(\vec{x}_{i},\vec{x}_{j})=\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{0})+\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{0},\vec{x}_{j})-\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{j})-\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{0},\vec{x}_{0})\\=\sum _{j=1}^{n}a_{j}\sum _{i=1}^{n}a_{i}D(\vec{x}_{i},\vec{x}_{0})+\sum _{i=1}^{n}a_{i}\sum _{j=1}^{n}a_{j}D(\vec{x}_{0},\vec{x}_{j})-\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{j})-\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{0},\vec{x}_{0})\\=-\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{j})$

所以 $K(\vec{x}_{i},\vec{x}_{j})=-D(\vec{x}_{i},\vec{x}_{j})$ ；由定理1可知，K条件正定时，-K负定。所以D为负定核

充分性：即D为负定核时，K为正定核。

D为负定核，则D一定条件负定。

引入 $a_{0}=-\sum_{i=1}^{n}a_{i}$ ;所以 $\sum_{i=0}^{n}a_{i}=0$ ；

$\sum _{i=0}^{n}\sum _{j=0}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{j})=\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{j})-\sum _{j=1}^{n}a_{0}a_{j}D(\vec{x}_{0},\vec{x}_{j})-\sum _{i=1}^{n}a_{i}a_{0}D(\vec{x}_{i},\vec{x}_{0})+\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{0},\vec{x}_{0})$

将a0代入： $\sum _{i=0}^{n}\sum _{j=0}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{j})=\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{j})-\sum _{j=1}^{n}(-\sum_{i=1}^{n}a_{i})a_{j}D(\vec{x}_{0},\vec{x}_{j})-\sum _{i=1}^{n}a_{i}(-\sum_{i=1}^{n}a_{i})D(\vec{x}_{i},\vec{x}_{0})+\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}D(\vec{x}_{0},\vec{x}_{0})$

合并同类项后可得：

$\sum _{i=0}^{n}\sum _{j=0}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{j})=-\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}K(\vec{x}_{i},\vec{x}_{j})$

因为D负定，即 $\sum _{i=0}^{n}\sum _{j=0}^{n}a_{i}a_{j}D(\vec{x}_{i},\vec{x}_{j})\leq0$ 所以 $\sum _{i=1}^{n}\sum _{j=1}^{n}a_{i}a_{j}K(\vec{x}_{i},\vec{x}_{j})\geq 0$

K为正定核。

证毕。

这个定理使得我们能在度量与内积之间建立关系，为什么距离这么重要呢，那是因为日后再SVM的应用中，我们需要得到点到超平面的距离来作为其合页损失函数的组成部分。本质上来说这里解释了用核来描述距离来作为损失函数可能性。

在PART2中，我们即将开始打造自己的核，包括有限维的多项式核，无穷维的高斯核等等。

(四) 再生核(Reproducing Kernels) PAR
Author: Pan Date:2020/7/21 "A complete pattern-classifica...
(五) 再生核(Reproducing Kernels) PAR
Author: Pan Date:2020/7/22 在Part1中，我们解释了内积是如何诱导距离的，接下来我们将...
2019-01-07 kernels(核函数)
kernels(核函数)
核函数（Kernels）
高斯核函数：靠近我们设定的点的点约等于1，远离我们设定的点的点约等于0。如何获取标记点？
机器学习与深度学习模型复现与知识点汇总指南
Awesome Deep Learning Models?Learning and reproducing cla...
（六）核主元分析 PART1
Author: Pan Date:2020/7/25 我们在(四)(五)再生核中，我们谈到了如何将低维的数据映射到...
给i386写驱动 -2
https://arjunsreedharan.org/post/82710718100/kernels-101-...
跟着白泽读paper丨kAFL: Hardware-Assist
kAFL: Hardware-Assisted Feedback Fuzzing for OS Kernels 主...
再生（四）
峰彦不可能违抗她的期待,不得已却又不能形诸于色,说:“那么我就留下来,你先回家好了,何况,你还有很多事情要做...
2019-10-18
https://www.kaggle.com/kernels/scriptcontent/20478888/dat...