核方法概述----正定核以及核技巧（Gram矩阵推导正定核）

  在再谈SVM（hard-margin和soft-margin详细推导、KKT条件、核技巧）中我们大致谈到了核函数以及为什么要用核函数，今天在这里更加详细的介绍一下。

核方法

• 1.核函数概述
• 2.正定核
• 2.1定义
• 2.2证明
• 3.核技巧
• 4.常见的核函数

1.核函数概述

  从前面的学习中我们可以看出来，无论是Hard margin SVM还是Soft margin SVM构建的都是一个线性的决策边界，从而把数据集分到各自的类中，如果数据集是一个非线性的，直接使用SVM，得不到一个理想的结果，那么使用线性分类器求解非线性分类问题，需要特殊的处理：

1. 首先，使用一个变换将原空间的数据映射到新空间中
2. 然后，在新空间中使用线性分类器求解

在机器学习之逻辑回归(logistics regression)中，我们考虑了这样一个问题：

  考虑一个简单的二分类问题，有x1,x2两个特征，两个特征值都为0 or 1为C2，否则为C1。在逻辑回归中，输入某一个样本的两个特征值x1，x2，与各自的权重w1,w2相乘，也就是求inner product，最后加上一个bias，得到z，再将z用Sigmoid函数处理，最后与0.5进行比较，就可以判断属于哪一个类别。但是我们将两个特征映射到到一个二维坐标系上，发现根本不可能找到一条直线将两类样本完全分开。这种限制与数据量无关，是逻辑回归自己本身的限制。
  鉴于上面这种情况，就需要用到
Teature Transformation，即特征转换。用特征转换处理后，使得我们能够用一条直线将C1和C2，也就是上面的红点和蓝点分开。图里面的处理方法是：定义新的x1,x2，x1为点到(0,0)的距离，x2为到点(1,1)的距离，处理后如下图所示：

  这时候我们发现，就能够找到一条直线将两类点分开，但在实际应用中，我们往往不能够找到比较好的特征变换的方法。
  上面这种其实还是只是二维到二维的转换，实际上我们可以是二维到三维的转换，比如下面这种情况：

  同样形状与颜色的点代表同一类别。观察上图我们发现，在二维平面上，我们不可能找到一条直线恰好可以将两类样本点分开，但假设我们做如下处理：

这样我们就将二维的点变换到了三维，这个时候我们再看看分布情况：

这个时候两个蓝点在一个平面上，两个红点在另一个平面上，在它们之间很容易找到一个超平面来使得它们分开。

  上面啰嗦了一大堆，总结一下就是：当我们在低维空间对样本数据处理时，我们发现用线性的模型无法处理。于是我们便把低维数据引入到高维中，这样就可以用线性的模型去处理。

2.正定核

  我们所说的核函数大部分都是正定核。在下面的探讨中，输入空间为 χ \chi χ， x , z ∈ χ x,z\in\chi x,z∈χ。

2.1定义

正定核的定义有两种：

• 对于 ∀ x , z ∈ χ \forall x,z\in\chi ∀x,z∈χ，若存在一个函数 ϕ \phi ϕ，使得 K ( x , z ) =   < ϕ ( x ) , ϕ ( z ) > K(x,z)=\ <\phi(x),\phi(z)> K(x,z)= <ϕ(x),ϕ(z)>，则称 K ( x , z ) K(x,z) K(x,z)为正定核函数
• 对于 ∀ x , z ∈ χ \forall x,z\in\chi ∀x,z∈χ，如果 K ( x , z ) K(x,z) K(x,z)满足对称性以及正定性，则我们也称 K ( x , z ) K(x,z) K(x,z)为正定核函数

   对第一条定义的说明：我们要将低维样本映射到高维，则我们需要一个映射函数，如果我们能够找到一个 ϕ \phi ϕ函数，使得我们定义的 K ( x , z ) K(x,z) K(x,z)恰好是两个高维样本 ϕ ( x ) , ϕ ( z ) \phi(x),\phi(z) ϕ(x),ϕ(z)的内积，则 K ( x , z ) K(x,z) K(x,z)就是一个正定核函数。但上面我们也说了，这个映射函数很不好找。
  为啥一定要是内积？因为内积恰恰是数据挖掘中非常重要的一种计算方式，数据挖掘的很多方法都是借助内积来完成的，所以核函数具有强大的功能。
   对第二条定义的说明：

• 所谓对称性，是指 K ( x , y ) = K ( y , x ) K(x,y)=K(y,x) K(x,y)=K(y,x)。
• 所谓正定性：对低维空间中任意N个样本 x 1 , x x , . . . , x N x_{1},x_{x},...,x_{N} x1​,xx​,...,xN​，其对应的Gram矩阵是半正定的。什么是Gram矩阵？我们令K表示那N个样本的Gram矩阵：
  
  该矩阵是一个N X N的矩阵，比如（1，1）这个位置就是 K ( x 1 , x 1 ) K(x_{1},x_{1}) K(x1​,x1​)
  什么是半正定？我们任取一个N维的列向量 α \alpha α，如果满足：
  
  则说明这个N X N的矩阵K是一个半正定的矩阵。
  
  
  
  
  

2.2证明

  我们一再强调，映射函数 ϕ \phi ϕ不好找。 那么我们该怎么定义一个正定核？瞎猜吗？显然不是，我们可以根据第二个定义来构造。因此我们需要证明一二两个定义式互通的。
  将一二两个定义结合起来就是：
   K ( x , z ) = < ϕ ( x ) , ϕ ( z ) > K(x,z)=<\phi(x),\phi(z)> K(x,z)=<ϕ(x),ϕ(z)> ⇔ \Leftrightarrow ⇔ Gram矩阵半正定且K满足对称性。
  下面我们将证明这个结论。先看从左到右，假设已知了 K ( x , z ) = < ϕ ( x ) , ϕ ( z ) > K(x,z)=<\phi(x),\phi(z)> K(x,z)=<ϕ(x),ϕ(z)> ，因为是求内积，所以对称性是显而易见的。那么我们怎么推导出Gram矩阵半正定呢？根据半正定的定义：

因此正推可以实现。反推暂时不太会。。后期补上。
  因此上述两个定义是相通的。在定义一中，我们得找到一个 ϕ \phi ϕ，这个通常不好找。而在定义二中，我们只需要自己定义一个函数K，然后取任意N个样本，联合K求它们的Gram矩阵，只要该矩阵满足半正定性质，那么我们定义的函数K就是一个正定核函数。

3.核技巧

  什么是核技巧？在SVM的推导中，我们看到：

注：上述 x j x_{j} xj​只是为了便于区分才这样写，实际上是 x i x_{i} xi​。我们令：

于是有：

  所谓核技巧，就是指我们可以直接计算 K ( x i , x j ) K(x_{i},x_{j}) K(xi​,xj​)（这个K是已知的，根据定义二可以构造），而不需要真正的去找一个 ϕ ( x ) \phi(x) ϕ(x)（通常是很难找的）。也就是说，我们并不关心低维到高维的映射 ϕ \phi ϕ是什么样子的，我们只需要构造一个函数K，使得该函数可以表示为映射后空间里数据的内积，这样就可以了。

4.常见的核函数

伟大的前人已经帮我们定义好了很多的核函数，常见的有：