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

梦里梦外; 2023-03-04 08:25 11阅读 0赞

在[再谈SVM（hard-margin和soft-margin详细推导、KKT条件、核技巧）][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)][logistics regression]中，我们考虑了这样一个问题：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]  
  考虑一个简单的二分类问题，有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)的距离，处理后如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70_pic_center]  
  这时候我们发现，就能够找到一条直线将两类点分开，**但在实际应用中，我们往往不能够找到比较好的特征变换的方法。**  
  上面这种其实还是只是二维到二维的转换，实际上我们可以是二维到三维的转换，比如下面这种情况：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]  
  同样形状与颜色的点代表同一类别。观察上图我们发现，在二维平面上，我们**不可能找到一条直线恰好可以将两类样本点分开**，但假设我们做如下处理：  
![在这里插入图片描述][20200802200741702.gif_pic_center]  
这样我们就将二维的点变换到了三维，这个时候我们再看看分布情况：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]

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

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

# 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矩阵：  
    ![在这里插入图片描述][20200802203210584.gif_pic_center]  
    该矩阵是一个N X N的矩阵，比如（1，1）这个位置就是 K ( x 1 , x 1 ) K(x\_\{1\},x\_\{1\}) K(x1,x1)  
    什么是半正定？我们任取一个N维的列向量 α \\alpha α，如果满足：  
    ![在这里插入图片描述][20200802203515444.gif_pic_center]  
    则说明这个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矩阵半正定呢？根据半正定的定义：  
![在这里插入图片描述][20200802213250146.gif_pic_center]  
因此正推可以实现。反推暂时不太会。。后期补上。  
  因此上述两个定义是相通的。在定义一中，我们得找到一个 ϕ \\phi ϕ，这个通常不好找。而在定义二中，我们只需要自己定义一个函数K，然后取任意N个样本，联合K求它们的Gram矩阵，**只要该矩阵满足半正定性质，那么我们定义的函数K就是一个正定核函数。**

# 3.核技巧 #

什么是核技巧？在SVM的推导中，我们看到：  
![在这里插入图片描述][20200728120230659.gif_pic_center]

注：上述 x j x\_\{j\} xj只是为了便于区分才这样写，实际上是 x i x\_\{i\} xi。我们令：  
![在这里插入图片描述][20200728115823933.gif]  
于是有：  
![在这里插入图片描述][20200728120349956.gif]  
  所谓核技巧，就是指我们可以直接计算 K ( x i , x j ) K(x\_\{i\},x\_\{j\}) K(xi,xj)（这个K是已知的，根据定义二可以构造），而不需要真正的去找一个 ϕ ( x ) \\phi(x) ϕ(x)（通常是很难找的）。也就是说，我们并不关心低维到高维的映射 ϕ \\phi ϕ是什么样子的，我们只需要构造一个函数K，使得该函数可以表示为映射后空间里数据的内积，这样就可以了。

# 4.常见的核函数 #

伟大的前人已经帮我们定义好了很多的核函数，常见的有：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]

[SVM_hard-margin_soft-margin_KKT]: https://blog.csdn.net/Cyril_KI/article/details/107601621
[logistics regression]: https://blog.csdn.net/Cyril_KI/article/details/106984794
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]: /images/20230208/bf756ed5008a48ab89ebf4624e5b1fec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70_pic_center]: /images/20230208/f1d7f0276c5e40b6908d8ed63ee3fbe9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]: /images/20230208/76081f3d810c4b24b8a091a4042cda63.png
[20200802200741702.gif_pic_center]: /images/20230208/3c806685cd684c9b8db6fbcfe6dd0916.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]: /images/20230208/35ad71187b554f97b8e09fb4b460cd26.png
[20200802203210584.gif_pic_center]: /images/20230208/bb6234ab7c864301b59004e1c9e62518.png
[20200802203515444.gif_pic_center]: /images/20230208/6a97fdf0f8ac4f5997b652d09f03cb19.png
[20200802213250146.gif_pic_center]: /images/20230208/ffe1dc01bf8a4f51812e54500a16918d.png
[20200728120230659.gif_pic_center]: /images/20230208/8c6203bf7f2244f6a5b630af739eee46.png
[20200728115823933.gif]: /images/20230208/089a880cb5934e8ba65d069daef0237a.png
[20200728120349956.gif]: /images/20230208/acfede4f259d4c12b8538432b87afb89.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]: /images/20230208/9c2bc4a29074497f921d05c6425c5c98.png