SVM的核技术与希尔伯特空间

一、些基本定义

• 线性性：所谓的线性性就是加分和数乘。
• 距离：距离的定义必须满足如下三个条件：
  • 非负性：$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)$$
  
  
• 这样我可以将核函数像是实对称矩阵那样进行特征分解，所以得到下面公式：
  • 假设无穷多个特征值为： { λ i } i = 1 ∞ \{λ_i \}_{i=1}^∞ {λi​}i=1∞​,对应的无穷多个正交的特征函数为： { ψ ( x ) i } i = 1 ∞ \{ψ(x)_i \}_{i=1}^∞ {ψ(x)i​}i=1∞​所以有：$$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$$
  • { ψ ( x ) i } i = 1 ∞ \{ψ(x)_i \}_{i=1}^∞ {ψ(x)i​}i=1∞​也是当前函数空间的一组标准正交组基。即满足： $$\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$$

四、再生核希尔伯特空间

• { ψ ( x ) i } i = 1 ∞ \{ψ(x)_i \}_{i=1}^∞ {ψ(x)i​}i=1∞​也是原函数空间(希尔伯特空间)的一组标准正交组基,现在我们将 { λ i ψ ( x ) i } i = 1 ∞ \{\sqrt{λ_i }ψ(x)_i \}_{i=1}^∞ {λi​ ​ψ(x)i​}i=1∞​做为一组正交基,形成新的函数空间叫做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/