机器学习笔记之核方法(一)核方法思想与核函数介绍

引言

本节将介绍核方法以及核函数。

回顾：支持向量机的对偶问题

在支持向量机——引出对偶问题中介绍了将原问题$\to$ 无约束原问题 $\to$ 对偶问题的转化过程。最终得到如下优化问题：
该公式位于‘西瓜书’123页最下方，详细推导过程见链接。
$$\{\begin{array}{l}\underset{\lambda }{\max }-\frac{1}{2}\left[{\sum }_{i=1}^N{\sum }_{j=1}^N{\lambda }^{(i)}{\lambda }^{(j)}{y}^{(i)}{y}^{(j)}{\left[x^{(i)}\right]}^T{x}^{(j)}\right]+{\sum }_{i=1}^N{\lambda }^{(i)}\\ s.t.\{\begin{array}{l}{\lambda }^{(i)}\ge 0\\ {\sum }_{i=1}^N{\lambda }^{(i)}{y}^{(i)}=0\end{array}\end{array}$$
其中$x^{(i)},x^{(j)}(i,j=1,2,\cdots ,N)$均表示样本集合$\mathcal{X}$的样本；$y^{(i)},y^{(j)}$分别表示样本$x^{(i)},x^{(j)}$对应的标签结果；${\lambda }^{(i)},{\lambda }^{(j)}$表示样本$x^{(i)},x^{(j)}$对应的拉格朗日因子。

可以看出，${\lambda }^{(i)},{\lambda }^{(j)},y^{(i)},y^{(j)}$均表示实数，而${\left[x^{(i)}\right]}^T{x}^{(j)}$表示两样本向量$x^{(i)},x^{(j)}$的内积结果。在线性分类任务的讨论中，我们假设样本集合$\mathcal{X}=(x^{(1)},x^{(2)},\cdots ,x^{(N)})$是线性可分的，也就是说：存在一条直线或者超平面(基于不同维度)，能够将样本空间中的样本点正确划分。

但在现实任务中，样本空间中样本可能不是线性可分的。即可能并不存在一个能够将两分类样本正确划分的直线/超平面。基于这种问题，需要引入核方法思想。

核方法思想介绍

线性可分与线性不可分

线性可分是指：在二分类线性分类任务中，使用一个线性函数将样本空间中的样本正确划分。这里的正确划分指的是划分过程中不存在任何错误。常见的线性可分算法有：

• 感知机算法(Perceptron Algorithm,PLA)：基于错误驱动方式，找到满足条件的参数结果。
  $$\hat{\mathcal{W}}=\underset{\mathcal{W}}{\mathrm{argmin}}\sum _{x^{(i)},y^{(i)}\in \mathcal{D}}-y^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)$$
  针对这种无约束优化问题，使用梯度下降方法寻找最优参数的变化方向：
  $${\mathcal{W}}^{(t+1)}\leftarrow {\mathcal{W}}^{(t)}-\lambda {\nabla }_{\mathcal{W}}\mathcal{L}(\mathcal{W},b)$$
• 支持向量机(Support Vector Machine,SVM)。
  这里指的是硬间隔(Hard Margin) SVM算法。

相反，线性不可分是指使用线性函数进行划分时，会产生分类错误的现象。

• 图像(右)中描述的是仅存在少量错误的情况，此时使用感知机算法会导致模型无法收敛；硬间隔SVM无论如何构建直线，都无法实现线性可分：
  
  而具有代表性的解决方法有软间隔SVM：
  $$\{\begin{array}{l}\underset{\mathcal{W},b}{\min }\frac{1}{2}{\mathcal{W}}^T\mathcal{W}+\mathcal{C}{\sum }_{i=1}^N{\xi }^{(i)}\\ s.t.\{\begin{array}{l}{y}^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)\ge 1-{\xi }^{(i)}\\ {\xi }^{(i)}\ge 0\end{array}\end{array}$$
  其中：
  • ${\xi }^{(i)}$表示当前错误分类的样本点$\left(x^{(i)},y^{(i)}\right)$到超平面$y^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)=1$的距离；
  • $1-{\xi }^{(i)}$表示当前错误分类的样本点$\left(x^{(i)},y^{(i)}\right)$到分类直线${\mathcal{W}}^T{x}^{(i)}+b$的距离。
• 不同于上述因少量误差产生的线性不可分问题，真实情况可能是样本本身就是线性不可分问题。例如：
  sklearn中的make_circle样本集合。
  

上述样本空间中的样本显然是非线性的，无法使用直线/超平面对上述两类样本进行划分。
基于上述的非线性可分问题，存在一种思路：将样本特征进行非线性转换，转换的目标是将非线性可分问题转化为线性可分问题。

非线性带来高维转换

非线性带来高维转换 的言下之意是，将当前样本空间中无法线性可分的原因归结为样本空间维度过低。以二维特征的亦或问题为例：

二维空间亦或问题图像描述如下：

基于上图的两类样本分布(蓝色样本点(0,1),(1,0);橙色样本点(0,0),(1,1))，我们没有办法使用一条直线 对样本分类进行正确划分。
如果在当前样本特征的基础上，添加一维新的特征：
由于‘亦或问题’比较简单，可以直接将非线性转换的函数描述出来。并且这个非线性转换并不是唯一的，也可以通过其他的非线性转换方式进行描述。
$$x^{(i)}=\left[x_1^{(i)},x_2^{(i)},(x_1^{(i)}-x_2^{(i)}{)}^2\right]i=1,2,3,4$$
基于新特征的样本点表示如下：
$$(0,0,0),(0,1,1),(1,0,1),(1,1,0)$$
对应三维图像表示如下：

发现，原始样本点从二维特征延伸至三维特征后，很容易地找到平面对样本点进行划分。
这里引用了Cover定理(Cover Theonem)的思想：将复杂的模式分类问题非线性地投射到高维空间将比投射到地位空间更容易线性可分。
同理，我们可以尝试对上述make_circle样本集合设计相应的核函数，具体代码表示如下：

• 这里设计的核函数是基于高斯分布的核函数，并且两维度相互独立。非线性转换后的样本特征表示如下：
  $$\begin{array}{rl}{x}^{(i)}& =\left[x_1^{(i)},x_2^{(i)},\mathcal{N}({\mu }_1,\sigma )+\mathcal{N}({\mu }_2,\sigma )\right]\\ {\mu }_k& =\frac{1}{N}\sum _{i=1}^N{x}_k^{(i)}k=1,2\end{array}$$
• 方差$\sigma$作为超参数进行调整。

import matplotlib.pyplot as plt
import math
import numpy as np
from sklearn.datasets import make_circles

def kernel_function(input_space,mean,sigma):

    def pdf(x,mean,sigma):
        return (1 / (sigma * math.sqrt(2 * math.pi))) * math.exp(-0.5 * (((x - mean) ** 2)/(sigma ** 2)))
    return np.array([pdf(i,mean,sigma) for i in input_space])


def get_new_sample(x_space,sigma):
    mean_1 = np.mean(x_space[:,0])
    mean_2 = np.mean(x_space[:,1])
    kernel_1 = kernel_function(x_space[:,0],mean_1,sigma)
    kernel_2 = kernel_function(x_space[:,1],mean_2,sigma)
    kernel_space = kernel_1 + kernel_2
    kernel_space = np.expand_dims(kernel_space,axis=1)
    new_space = np.concatenate((x_space,kernel_space),axis=1)
    return new_space

def draw_make_circle():
    X_circle, Y_circle = make_circles(n_samples=200, noise=0.1, factor=0.1)
    new_sample = get_new_sample(X_circle,sigma=2)
    ax = plt.axes(projection="3d")
    ax.scatter(new_sample[:, 0],new_sample[:, 1],new_sample[:,2],marker="o",edgecolors='m', c=Y_circle)
    plt.show()

if __name__ == '__main__':
    draw_make_circle()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

返回图像结果如下：

对偶表示带来内积

基于非线性带来高维转换的思路，针对线性不可分问题，将样本$x$的特征进行非线性转换，从而将$x$特征转化为高维特征：
以数据集合$\mathcal{X}$的某具体样本点$x^{(i)}$为例。
$$x^{(i)}\to \varphi \left(x^{(i)}\right)$$
以支持向量机为例，因而特征空间中的划分超平面 对应模型可表示为：
$$f(x)={\mathcal{W}}^T\varphi (x)+b$$
同理，得到的对偶问题可表示如下：
$$\{\begin{array}{l}\underset{\lambda }{\max }-\frac{1}{2}\left[{\sum }_{i=1}^N{\sum }_{j=1}^N{\lambda }^{(i)}{\lambda }^{(j)}{y}^{(i)}{y}^{(j)}{\left[\varphi \left(x^{(i)}\right)\right]}^T\varphi \left(x^{(j)}\right)\right]+{\sum }_{i=1}^N{\lambda }^{(i)}\\ s.t.\{\begin{array}{l}{\lambda }^{(i)}\ge 0\\ {\sum }_{i=1}^N{\lambda }^{(i)}{y}^{(i)}=0\end{array}\end{array}$$

• 其中原始对偶问题中$[x^{(i)}{]}^T{x}^{(j)}$表示$x^{(i)},x^{(j)}\in {\mathbb{R}}^p$自身特征的内积；

• 而${\left[\varphi \left(x^{(i)}\right)\right]}^T\varphi \left(x^{(j)}\right)$表示$x^{(i)},x^{(j)}$经过非线性转换得到的高维特征 的内积。

• 上面介绍的亦或例子，相比于原始特征，仅增加了一个特征；但在真实环境中，样本$x$经过转换得到的新特征$\varphi (x)$，其特征空间维数可能远远超过了原始特征空间的维数$p$，甚至是 无限维。

  因此，首先求解$\varphi (x^{(i)}),\varphi (x^{(j)})$本身计算量极高。并且还要计算${\left[\varphi \left(x^{(i)}\right)\right]}^T\varphi \left(x^{(j)}\right)$，从而计算量更加庞大了。

继续观察对偶问题的表达形式，实际上我们仅关心${\left[\varphi \left(x^{(i)}\right)\right]}^T\varphi \left(x^{(j)}\right)$内积的最终结果，而并不需要单个的$\varphi (x^{(i)}),\varphi (x^{(j)})$结果。因此，求解思路转化为：是否存在这样一种方法，避免求解$\varphi (x^{(i)}),\varphi (x^{(j)})$，从而直接求解内积${\left[\varphi \left(x^{(i)}\right)\right]}^T\varphi \left(x^{(j)}\right)$？

核函数(Kernal Function)的引入就是为了解决该问题。

核函数

核函数$\kappa$的定义表示如下：
核函数被定义的核心就是避免求解$\varphi (x)$.
$$\kappa \left[x^{(i)},x^{(j)}\right]=⟨\varphi (x^{(i)}),\varphi (x^{(j)})⟩={\left[\varphi \left(x^{(i)}\right)\right]}^T\varphi \left(x^{(j)}\right)$$
将核函数带入，对偶问题最终可重写为：
$$\begin{array}{rl}& \{\begin{array}{l}\underset{\lambda }{\max }-\frac{1}{2}\left[{\sum }_{i=1}^N{\sum }_{j=1}^N{\lambda }^{(i)}{\lambda }^{(j)}{y}^{(i)}{y}^{(j)}{\left[\varphi \left(x^{(i)}\right)\right]}^T\varphi \left(x^{(j)}\right)\right]+{\sum }_{i=1}^N{\lambda }^{(i)}\\ s.t.\{\begin{array}{l}{\lambda }^{(i)}\ge 0\\ {\sum }_{i=1}^N{\lambda }^{(i)}{y}^{(i)}=0\end{array}\end{array}\\ \Rightarrow & \{\begin{array}{l}\underset{\lambda }{\max }-\frac{1}{2}\left[{\sum }_{i=1}^N{\sum }_{j=1}^N{\lambda }^{(i)}{\lambda }^{(j)}{y}^{(i)}{y}^{(j)}\kappa \left[x^{(i)},x^{(j)}\right]\right]+{\sum }_{i=1}^N{\lambda }^{(i)}\\ s.t.\{\begin{array}{l}{\lambda }^{(i)}\ge 0\\ {\sum }_{i=1}^N{\lambda }^{(i)}{y}^{(i)}=0\end{array}\end{array}\end{array}$$
从而对上述优化问题进行求解，得到最优模型参数${\mathcal{W}}^{\ast }$：
支持向量机——模型参数求解传送门
$${\mathcal{W}}^{\ast }=\sum _{i=1}^N{\lambda }^{(i)}{y}^{(i)}\varphi (x^{(i)})$$
最终得到如下超平面模型表达式：
${\lambda }^{(i)},y^{(i)}$均是实数，其转置等于自身。
$$\begin{array}{rl}f(x)& =({\mathcal{W}}^{\ast }{)}^T\varphi (x)+b\\ & ={\left[\sum _{i=1}^N{\lambda }^{(i)}{y}^{(i)}\varphi (x^{(i)})\right]}^T\varphi (x)+b\\ & =\sum _{i=1}^N{\lambda }^{(i)}{y}^{(i)}{\left[\varphi (x^{(i)})\right]}^T\varphi (x)+b\\ & =\sum _{i=1}^N{\lambda }^{(i)}{y}^{(i)}\kappa (x,x^{(i)})+b\end{array}$$
如果将核函数$\kappa (\cdot ,\cdot )$找出来，上述超平面表达式中，$x^{(i)},y^{(i)},{\lambda }^{(i)}$均是已知量，它就是一个关于$x$的函数。这样就避免了一个一个求解${\left[\varphi (x^{(i)})\right]}^T\varphi (x)$的情况。
这种‘避免求解$\varphi (x^{(i)}),\varphi (x)$从而直接求解${\left[\varphi (x^{(i)})\right]}^T\varphi (x)$的思想’被称作核技巧(Kernal Trick)。
在支持向量机中，这种基于‘核函数’的展开式被称作‘支持向量展开式’(Support Vector Expansion)。

核函数的定义(2022/11/23)

首先，核(Kernal)本质上是一个映射，关于两个样本空间 相关的映射：
$$\kappa (x^{(i)},x^{(j)})$$
其中$x^{(i)},x^{(j)}$均是样本集合$\mathcal{X}$中的元素，因而满足：$x^{(i)},x^{(j)}\in {\mathbb{R}}^p$。
核函数的定义表示如下：
$$\begin{array}{rl}& \kappa :\mathcal{X}\times \mathcal{X}\to \mathbb{R}\\ & \forall x^{(i)},x^{(j)}\in \mathcal{X}\to \kappa (x^{(i)},x^{(j)})\end{array}$$
解释一下这个定义描述了什么。
$\mathcal{X}$表示样本的特征空间，而核函数的作用在于 对两个样本的特征空间做内积，而最终的内积结果是将原始的多维特征空间映射到一维的实数域中，只要具备这种功能的函数就可以称之为核函数。

正定核函数

上述核函数的定义比较简单，我们可以根据自身需要定义核函数。例如上述两个例子的核函数：
$$\{\begin{array}{l}\kappa (x_1,x_2)=(x_1-x_2{)}^2\\ \kappa (x_1,x_2)=\mathcal{N}({\mu }_1,\sigma )+\mathcal{N}({\mu }_2,\sigma )\end{array}$$

而正定核函数$\kappa (x^{(i)},x^{(j)})$相比于核函数的定义，差别在于正定核函数的返回结果等价于将原始特征空间$x^{(i)},x^{(j)}$经过非线性转换得到的高维特征空间$\varphi (x^{(i)}),\varphi (x^{(j)})$的内积：
这里假设'非线性转换'得到的$\varphi (x^{(i)}),\varphi (x^{(j)})$的特征维度是$m$维，核函数$\kappa (x^{(i)},x^{(j)})$的特征空间维度表示如下。
$$\begin{array}{rl}\kappa (x^{(i)},x^{(j)})& =⟨\varphi (x^{(i)}),\varphi (x^{(j)})⟩\\ & ={\left[\varphi (x^{(i)})\right]}_{1\times m}^T\varphi (x^{(j)}{)}_{m\times 1}\in \mathbb{R}{x}^{(i)},x^{(j)}\in \mathcal{X}\end{array}$$

关于正定核函数的等价定义表示如下：
$$\kappa :\mathcal{X}\times \mathcal{X}\to \mathbb{R},\forall x^{(i)},x^{(j)}\in \mathcal{X}\to \kappa (x^{(i)},x^{(j)})$$
如果$\kappa (x^{(i)},x^{(j)})$满足：

• 对称性：$\kappa (x^{(i)},x^{(j)})=\kappa (x^{(j)},x^{(i)})$；
• 正定性：从样本集合$\mathcal{X}$中任取$N$个样本数据$x^{(1)},\cdots ,x^{(N)}$，对应的 “核矩阵”(Kernal Matrix)总是半正定的。其中$x^{(1)},\cdots ,x^{(N)}$对应的核矩阵$\mathcal{K}$表示如下：
  $$\mathcal{K}={\left[\begin{array}{c}\kappa (x^{(1)},x^{(1)}),\kappa (x^{(1)},x^{(2)}),\cdots ,\kappa (x^{(1)},x^{(N)})\\ \kappa (x^{(2)},x^{(1)}),\kappa (x^{(2)},x^{(2)}),\cdots ,\kappa (x^{(2)},x^{(N)})\\ ⋮\\ \kappa (x^{(N)},x^{(1)}),\kappa (x^{(N)},x^{(2)}),\cdots ,\kappa (x^{(N)},x^{(N)})\end{array}\right]}_{N\times N}$$

称$\kappa (x^{(i)},x^{(j)})$是正定核函数。
由于正定核函数的‘标准定义’确实很难理解，因此这里并没有去过多描述‘标准定义’，有感兴趣的小伙伴移步正定核 ——vincen 的学习笔记

下一节将介绍正定核函数的充分必要性证明。

相关参考：
机器学习-周志华著
机器学习-核方法（1）-背景介绍
机器学习-核方法（2）-正定核的两个定义
正定核 ——vincen 的学习笔记