一、些基本定义

线性性：所谓的线性性就是加分和数乘。距离：距离的定义必须满足如下三个条件： 非负性：$d(x,y)\ge 0,x=y$时等号成立。对称性：$d(x,y)=d(y,x)$三角不等式：$d(x,y)+d(y,z)\ge d(x,z)$ 范数：$\Vert x\Vert$满足三个条件为范数： 非负性：$\Vert x\Vert \ge 0$线性性：$\Vert ax\Vert =|a|\Vert x\Vert$三角不等式：$\Vert x\Vert +\Vert y\Vert \ge \Vert x+y\Vert$范数可以看成从$x$到原点的距离；所以由范数可以定义距离,即：$d(x,y)=||x-y||$，但是距离不可以定义范数因为距离的定义，不满足范数的第二条条件。 内积： $⟨x,y⟩$为内积的条件： 对称性：$⟨x,y⟩=⟨y,x⟩$线性性质： $⟨x,y⟩+⟨x,z⟩=⟨x,y+z⟩$ ,$⟨ax,y⟩=a⟨x,y⟩$正定性：$⟨x,y⟩\ge 0$

二、各种空间

1、各种空间关系图

2、线性空间

若某个空间中的任意向量线性组合(加法和数乘)形成的新向量仍然属于该空间，则该空间就是线性空间。线性空间中可以找到一组基，它能够通过线性组合得到空间中所有的向量(点)。

3、函数空间

一个函数可以看成一个无穷维的向量。对函数$f(x)$按照自变量$x$进行采样，将样本的函数值组成一个向量：$$(f(x_1),f(x_2),\dots f(x_n))$$如果采样的间隔变得无穷的小，则这个向量就为一个无穷维的向量。 所以一个函数空间的内积可以定义为：$$⟨f,g⟩=\int f(x),g(x)dx$$多元函数：用$x$表示$R^n$中的一个向量(点)，$f$代表函数本身，也就是无穷向量。$f(x)$表示点$x$处的函数值与向量基类似，我们可以使用函数基表示其他函数。与向量基不同的是，在向量空间中我们只需要有限个向量去构造一组向量基，函数空间中则需要无限个基函数。

4、完备性

其中完备性的意思就是空间中的极限运算不能跑出该空间，如有理数空间中的$\sqrt{2}$ 的小数表示，其极限随着小数位数的增加收敛到$\sqrt{2}$，但$\sqrt{2}$属于无理数，并不在有理数空间，故不满足完备性。一个通俗的理解是把学校理解为一个空间，你从学校内的宿舍中开始一直往外走，当走不动停下来时（极限收敛），发现已经走出学校了（超出空间），不在学校范围内了（不完备了）。希尔伯特就相当于地球，无论你怎么走，都还在地球内（飞出太空除外）一般指函数空间

5、特征值分解

特征值：

定义：设$A$是$n$阶矩阵，λ是一个实数，若存在$n$维非零向量$\xi ̸=0$，使得下式成立： $$A\xi =\lambda \xi$$则称$\lambda$是$A$的一个特征值，$\xi$是$A$的对应于特征值$\lambda$的特征向量。性质： 不同特征值的特征向量线性无关。同一特征值的特征向量的线性组合依然是该特征值的特征向量。不同特征值的特征向量的线性组合依然不再是矩阵A的特征向量。$K$重特征值$\lambda$至多有$k$个线性无关的特征向量。

一般矩阵的特征值分解：

若$A$是$n$阶矩阵，并且具有$n$个线性无关的特征向量： $${\xi }_1,{\xi }_2,\dots ,{\xi }_n$$这些特征向量对应的特征值分别是：$${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$$特征值可能有重根。则有下面式子成立：$A{\xi }_i={\lambda }_i{\xi }_i$$$[A{\xi }_1,A{\xi }_2,\dots ,A{\xi }_n]=[{\lambda }_1{\xi }_1,{\lambda }_2{\xi }_2,\dots ,{\lambda }_n{\xi }_n]$$$$A[{\xi }_1,{\xi }_2,\dots ,{\xi }_n]=[{\xi }_1,{\xi }_2,\dots ,{\xi }_n]\left[\begin{array}{cccc}{\lambda }_1& 0& \cdots & 0\\ 0& {\lambda }_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {\lambda }_n\end{array}\right]$$记：$[{\xi }_1,{\xi }_2,\dots ,{\xi }_n]=Q$ $$P=\left[\begin{array}{cccc}{\lambda }_1& 0& \cdots & 0\\ 0& {\lambda }_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {\lambda }_n\end{array}\right]$$则有： $A=QP{Q}^{-1}$

实对称矩阵性质：：

实对称矩阵$A$的不同特征值对应的特征向量是正交的实对称矩阵$A$的特征值都是实数，特征向量都是实向量。$n$阶实对称矩阵$A$必可相似对角化(有$n$个线性无关的特征向量)，且相似对角阵上的元素即为矩阵本身特征值。若$\lambda$是$k$重特征值，则必有k个线性无关的特征向量。 如果矩阵$A$是实对称矩阵，则必定存在一个正交矩阵$Q$，使得$Q^{T}AQ=P$，即$A=QP{Q}^T$其中$P$是对角矩阵

正交矩阵性质：：

$Q$正交矩阵，则$Q^T=Q^{-1}$

施密特正交化：：

设${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n$是$R^n$中的一个线性无关向量组，若令:$${\beta }_1={\alpha }_1$$$${\beta }_2={\alpha }_2-\frac{⟨{\alpha }_2,{\beta }_1⟩}{⟨{\alpha }_1,{\beta }_1⟩}{\beta }_1$$$$\dots$$$${\beta }_n={\alpha }_n-\frac{⟨{\alpha }_n,{\beta }_1⟩}{⟨{\alpha }_1,{\beta }_1⟩}{\beta }_1-\frac{⟨{\alpha }_n,{\beta }_2⟩}{⟨{\alpha }_2,{\beta }_2⟩}{\beta }_2-\dots -\frac{⟨{\alpha }_n,{\beta }_{n-1}⟩}{⟨{\alpha }_{n-1},{\beta }_{n-1}⟩}{\beta }_{n-1}$$则${\beta }_1,{\beta }_2,\dots ,{\beta }_n$就是一个正交向量组。再进行单位化： $$e_i=\frac{{\beta }_i}{||{\beta }_i||}$$利用线性无关向量组，构造出一个标准正交向量组的方法，就是施密特正交化方法。由上面公式我们可以看出，${\beta }_1,{\beta }_2,\dots ,{\beta }_n$都是由${\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n$线性组合形成的。

证明：如果矩阵A是实对称矩阵，则必定存在一个正交矩阵$Q$，即$A=QP{Q}^T$

这个就是实对称矩阵的特征值分解，上面所有的铺垫都是为了轻松的证明这个定理。假设$A$是$n$阶实对称矩阵，其不重复特征值为：${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_d$若$d=n$，则$A$有$n$个不相等的特征值，所有每个特征值都有一个特征向量为：${\xi }_1,{\xi }_2,\dots ,{\xi }_n$，则他们相互正交。然后由上面的特征值分解方法有：$$A=QP{Q}^{-1}$$由于$[{\xi }_1,{\xi }_2,\dots ,{\xi }_n]=Q$，所以$Q$为正交矩阵，则$Q^T=Q^{-1}$,所以有：$$A=QP{Q}^T$$若$d<n$，则$A$有重根特征值，对每个重根特征值做下面处理： - 若λ_i 是k重特征值，则必有$k$个线性无关的特征向量: ${\xi }_{i1},{\xi }_{i2},\dots ,{\xi }_{ik}$,将他们进行施密特正交化得到：${\xi }_{i1}^{\prime },{\xi }_{i2}^{\prime },\dots ,{\xi }_{ik}^{\prime }$,由于${\xi }_{i1}^{\prime },{\xi }_{i2}^{\prime },\dots ,{\xi }_{ik}^{\prime }$是由${\xi }_{i1},{\xi }_{i2},\dots ,{\xi }_{ik}$线性组合形成的，根据特征值性质可知${\xi }_{i1}^{\prime },{\xi }_{i2}^{\prime },\dots ,{\xi }_{ik}^{\prime }$也是${\lambda }_i$的特征向量并且相互正交。 经过上面处理，${\xi }_1,{\xi }_2,\dots ,{\xi }_n$相互正交，后面的处理和上一种情况一样。

现在经过上面的一系列铺垫证明，我们得到这样一个结论：

若$A$是$n$阶是对称矩阵，那么A可以被如下分解： $$A=QP{Q}^T$$其中：$$[{\xi }_1,{\xi }_2,\dots ,{\xi }_n]=Q$$$$P=\left[\begin{array}{cccc}{\lambda }_1& 0& \cdots & 0\\ 0& {\lambda }_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {\lambda }_n\end{array}\right]$$中间特征值于特征向量是对应关系，我展开公式：$$A=QP{Q}^T=\sum _{i=1}^n{\lambda }_i{\xi }_i{\xi }_i^T$$

为了顺利理解下面的部分，我们需要知道矩阵与线性变换的一个关系：

每个矩阵与一个线性变换对应，所以矩阵可以看作是一个映射或一个函数。详细讲述可以参考：https://blog.csdn.net/ACM_hades/article/details/90518653

三、核函数

函数$\phi (x)$可视为一个无穷维向量，那么二元函数$K(x,y)$就可以可以视为一个无穷维矩阵，这个地方有点抽象，解释如下： 假设$A$为$m\times n$的矩阵，$x$为$n\times 1$的列向量，则可以通过对$A$与$x$做内积将$x$映射为一个$m$维空间中的$y$($m\times 1$的列向量)，所以矩阵$A$就是一个函数： $$Ax=y$$现在我对函数$f(x)$与$K(x,y)$做内积：$$⟨K(x,y),\phi (x)⟩=\int K(x,y)\phi (x)dx$$这个积分的结果是一个$y$的函数$\mu (y)$，也是无限维的向量。所以从这个角度讲$K(x,y)$就是函数空间中的矩阵。 假设二元函数$K(x,y)$满足下面条件，就是核函数(或者叫核矩阵) 对称性(对称矩阵)：$K(x,y)=K(y,x)$正定性: $\iint f(x)K(x,y)f(y)dxdy$满足上述条件我们称为对称半正定核函数。 特征值$\lambda$与特征函数$\psi (x)$：与上面一致$$⟨K(x,y),\psi (x)⟩=\int K(x,y)\psi (x)dx=\lambda \psi (y)$$这样我可以将核函数像是实对称矩阵那样进行特征分解，所以得到下面公式： 假设无穷多个特征值为：$\{{\lambda }_i{\}}_{i=1}^{\infty }$,对应的无穷多个正交的特征函数为：$\{\psi (x{)}_i{\}}_{i=1}^{\infty }$所以有：$$K(x,y)=\sum _{i=1}^{\infty }{\lambda }_i\psi (x{)}_i\psi (y{)}_i^T=\sum _{i=1}^{\infty }{\lambda }_i\psi (x{)}_i\psi (y{)}_i$$$\{\psi (x{)}_i{\}}_{i=1}^{\infty }$也是当前函数空间的一组标准正交组基。即满足： $$\langle \psi (x{)}_i,\psi (x{)}_j\rangle =\int \psi (x{)}_i\psi (x{)}_{j}dx=0$$$$\langle \psi (x{)}_i,\psi (x{)}_i\rangle =\int \psi (x{)}_i\psi (x{)}_{i}dx=1$$

四、再生核希尔伯特空间

$\{\psi (x{)}_i{\}}_{i=1}^{\infty }$也是原函数空间(希尔伯特空间)的一组标准正交组基,现在我们将$\{\sqrt{{\lambda }_i}\psi (x{)}_i{\}}_{i=1}^{\infty }$做为一组正交基,形成新的函数空间叫做RKHS空间(再生核希尔伯特空间)，记为$H$空间$H$空间中的任一向量或函数可以表示为基的线性组合: $f={\sum }_{(}i=1{)}^{\infty }{f}_i\sqrt{{\lambda }_i}\psi (x{)}_i,$则函数可以用坐标(系数)表示：$$f=[f_1,f_2,\dots {]}^T,g=[g_1,g_2,\dots {]}^T$$,这样内积可以表示为：$$⟨f,g⟩=\int \sum _{i=1}^{\infty }{f}_i\sqrt{{\lambda }_i}\psi (x{)}_i\sum _{i=1}^{\infty }{g}_i\sqrt{{\lambda }_i}\psi (x{)}_{i}dx=\int \sum _{i=1}^{\infty }{f}_i{g}_i\psi (x{)}_i\psi (x{)}_{i}dx$$$$=\sum _{i=1}^{\infty }{f}_i{g}_i\int \psi (x{)}_i\psi (x{)}_{i}dx=\sum _{i=1}^{\infty }{f}_i{g}_i$$在$H$空间的这组基下，这样我们可以改写核函数：$$K(x,y)=\sum _{i=1}^{\infty }\sqrt{{\lambda }_i}\psi (x{)}_i\sqrt{{\lambda }_i}\psi (y{)}_i$$我们对核函数中的$y$每取一个特定值，都会得到一个$x$的函数，那么我们可以将核函数看作是向量$y$到$x$函数的一个函数，记作：$$G(y)=K(x,y)=\sum _{i=1}^{\infty }\sqrt{{\lambda }_i}\psi (x{)}_i\sqrt{{\lambda }_i}\psi (y{)}_i$$函数$G(y)$的定义域是欧几里得空间，值域为函数空间。那么$G(y)$在$H$空间的坐标表示：$$G(y)=[\sqrt{{\lambda }_i}\psi (y{)}_1,\sqrt{{\lambda }_i}\psi (y{)}_2,\dots \dots ]$$则$y$每取一个具体值，都会是一个函数，并且可以得到这个函数在$H$空间的坐标表示，例如$y=y_0$:$$G(y_0)=[\sqrt{{\lambda }_i}\psi (y_0{)}_1,\sqrt{{\lambda }_i}\psi (y_0{)}_2,\dots \dots ]$$表示的函数为：$$G(y_0)=K(x,y_0)=\sum _{i=1}^{\infty }\sqrt{{\lambda }_i}\psi (x{)}_i\sqrt{{\lambda }_i}\psi (y_0{)}_i$$那么两个函数：$G(y_0),G(y_1)$的内积为：$$\langle G(y_0),G(y_1)\rangle =\sum _{i=1}^{\infty }\sqrt{{\lambda }_i}\psi (y_0{)}_i\sqrt{{\lambda }_i}\psi (y_1{)}_i=K(y_0,y_1)$$这就是核的可再生性，即用核函数再生两个核函数的內积。函数空间$H$被称为再生核希尔伯特空间（RKHS）。这个性质是非常好的，因为原本函数之间计算内积需要算无穷维的积分，但是现在只需要算核函数就好了。

五、核技术：

上面我们说过如果我们对$y$进行特定值，核函数$K(x,y)$就变成了一个x的函数，这样我们可以对$y$进行任意取值得到一个$x$的函数：$$G(y)=K(x,y)=\sum _{i=1}^{\infty }\sqrt{{\lambda }_i}\psi (x{)}_i\sqrt{{\lambda }_i}\psi (y{)}_i$$

$G(y)$的定义域是欧几里得空间，值域是一个函数空间。就是一个欧几里得空间到函数空间(希尔伯特空间)的映射(函数).并且$G(y)$值域空间中的任意两个函数$(G(y_0),G(y_1))$的内积都可以通过核函数直接算出$(K(y_0,y_1))$需要进行无穷积分。

这样，我们无需知道这个映射$G(y)$及其值域空间$H$的具体形式，只需要一个对称半正定的核函数，就必然存在映射$G(y)$和其值域空间$H$，使得：$$\langle G(y_0),G(y_1)\rangle =\sum _{i=1}^{\infty }\sqrt{{\lambda }_i}\psi (y_0{)}_i\sqrt{{\lambda }_i}\psi (y_1{)}_i=K(y_0,y_1)$$这就是Kernel trick。

SVM的核技术：

我们的原始数据$x$是欧几里得空间的一个向量，当我们的原始数据线性不可分时，我们就希望有一个映射$G(x)$，它能把原始数据$x$映射到一个无穷维的函数空间（希尔伯特空间）中去，使的数据在这个无穷维的空间中变得线性可分。并且在svm的优化中，我们只需要两个样本的内积$\langle x_1,x_2\rangle$,那么经过映射$G(x)$后我们也只需要任意两个样本映射后的内积$\langle G(x_0),G(x_1)\rangle$，并不需要这个映射$G(y)$及其值域空间的具体形式。这样问题就变成了我们只要一个对称半正定的核函数就ok了。

参考链接：

http://songcy.net/posts/story-of-basis-and-kernel-part-1/http://songcy.net/posts/story-of-basis-and-kernel-part-2/