核方法计算

2023-11-16

什么是核方法？

往简单里说，核方法是将一个低维的线性不可分的数据映射到一个高维的空间、并期望映射后的数据在高维空间里是线性可分的。我们以异或数据集为例：在二维空间中、异或数据集是线性不可分的；但是通过将其映射到三维空间、我们可以非常简单地让其在三维空间中变得线性可分。比如定义映射：

该映射的效果如下图所示：

可以看到，虽然左图的数据集线性不可分、但显然右图的数据集是线性可分的，这就是核工作原理的一个不太严谨但仍然合理的解释

从直观上来说，确实容易想象、同一份数据在越高维的空间中越有可能线性可分，但从理论上是否确实如此呢？1965 年提出的 Cover 定理从理论上解决了这个问题，我们会在文末附上相应的公式，这里暂时按下不表

至此，似乎问题就转化为了如何寻找合适的映射、使得数据集在被它映射到高维空间后变得线性可分。不过可以想象的是，现实任务中的数据集要比上文我们拿来举例的异或数据集要复杂得多、直接构造一个恰当的 $\phi$ 的难度甚至可能高于解决问题本身。而核方法的巧妙之处就在于，它能将构造映射这个过程再次进行转化、从而使得问题变得简易：它通过核函数来避免显式定义映射 $\phi$ 。往简单里说，核方法会通过用能够表示成 $K(x_i,x_j)=\phi(x_i)\cdot\phi(x_j)$ 的核函数 $K(x_i,x_j)$ 替换各算式中出现的内积 $x_i\cdot x_j$ 来完成将数据从低维映射到高维的过程。换句话说、核方法的思想如下：

将算法表述成样本点内积的组合（这经常能通过算法的对偶形式实现）
设法找到核函数，它能返回样本点 $x_i$ 、 $x_j$ 被 $\phi$ 作用后的内积
用替换 $x_i\cdot x_j$ 、完成低维到高维的映射（同时也完成了从线性算法到非线性算法的转换）

当然了，不难想象的是，并不是所有的函数都能够对应一个映射（亦即不是所有的 $K(x_i,x_j)$ 都能拆成 $\phi(x_i)\cdot\phi(x_j)$ ；比如说，显然 $K(x_i,x_j)$ 至少需要是一个对称函数）。幸运的是，1909 年提出的 Mercer 定理解决了这个问题，它的具体叙述会在文末给出

Mercer 定理为寻找核函数带来了极大的便利。可以证明如下两族函数都是核函数：

多项式核
径向基（Radial Basis Function，常简称为 RBF）核：

那么核方法的应用场景有哪些呢？在 2002 年由 Scholkopf 和 Smola 证明的表示定理告诉我们它的应用场景非常广泛。定理的具体内容同样会附在文末，这里就暂时按下不表

核模型的表现

还是用 GIF 来说明问题最为形象。当我们对感知机应用核方法后，它就能对非线性数据集（比如螺旋线数据集）进行分类了，训练过程将如下：

怎么应用核方法？

简单来说，就是把算法中涉及到样本（

）的地方都通过某种变换、弄成样本的内积形式（

）。以感知机为例，感知机的原始损失函数为

为了让损失函数中的样本都变成内积形式，考虑令

（也有令

的）

则

在此之上应用核方法是平凡的：设核函数为，只需把所有的 $x_i\cdot x_j$ 换成 $K(x_i,x_j)$ 即可：

于是优化问题变为

预测步骤则变为

对于 LinearSVM 而言，用同样的手法不难得出其核形式：

预测步骤则仍然是

（有没有发现核形式和对偶形式很像？( σ'ω')σ）

如何训练核模型？

【注意：为简洁，从此往后的推导和实现均以核感知机为例，核 SVM 的相关讨论会放在下一章介绍 SMO 算法时进行】

简洁起见，我们还是用梯度下降法来进行训练，为此我们需要进行求导工作。假设当前模型参数为， $x_i$ 在参数 $\alpha$ 下的预测值为 $\hat y_i$ ，则：

$\frac{\partial L}{\partial b}=-\sum_{y_j\hat y_j<0}y_j$

为了加速训练，我们需要将该算式向量化，为此我们需要定义核矩阵。假设现在我们有两组样本：和 $(x^{(2)}_1, x^{(2)}_2,...,x^{(2)}_N)^T$ ，那么它们的核矩阵即为

对于训练过程而言，我们关心的是训练样本之间的核矩阵

利用它，不难写出相应的向量化代码：

# 假设 k_mat 存储着原样本之间的核矩阵
# 1、计算损失
err = -y * (k_mat.dot(alpha) + b)
# 2、找出使得损失不小于 0 的样本
mask = err >= 0
# 3、进行相应梯度下降，lr 是学习速率
delta = lr * y[mask]
alpha += np.sum(delta[..., None] * k_mat[mask], axis=0)
b += np.sum(delta)

对于预测过程，我们关心的是原样本和新样本之间的核矩阵。假设新样本为，则

那么预测过程即为

于是关键就在于如何定义计算核矩阵的核函数了。对于多项式核来说，核函数的实现是直观的：

@staticmethod
def _poly(x, y, p):
    return (x.dot(y.T) + 1) ** p

但对于 RBF 来说就没那么直观了，用到了 Numpy 的高级实用技巧之一——升维：

@staticmethod
def _rbf(x, y, gamma):
    return np.exp(-gamma * np.sum((x[..., None, :] - y) ** 2, axis=2))

当然直接用 for 来实现也是可以的，不过那将会非常非常慢……

核模型的实现

如果思路能够整理清楚，那么核模型相比原模型来说只有如下两点改变：

需要定义核函数并计算出核矩阵
计算预测值时不是，而是，其中
- 在训练时， $\bold K$ 为原样本之间的核矩阵
- 在测试时， $\bold K$ 为原样本和新样本的核矩阵

所以实现起来的话会有许多重复代码，这里就只展现其中最核心的部分（仍以核感知机为例）：

# 训练代码
def fit(...):
    ...
    self._alpha = np.zeros(len(x))
    self._b = 0.
    self._x = x
    # self._kernel 即为核函数，能够计算两组样本的核矩阵
    k_mat = self._kernel(x, x)
    for _ in range(epoch):
        err = -y * (self._alpha.dot(k_mat) + self._b)
        if np.max(err) < 0:
            continue
        mask = err >= 0
        delta = lr * y[mask]
        self._alpha += np.sum(delta[..., None] * k_mat[mask], axis=0)
        self._b += np.sum(delta)

# 预测代码
def predict(self, x, raw=False):
    x = np.atleast_2d(x).astype(np.float32)
    # 计算原样本与新样本的核矩阵并根据它来计算预测值
    k_mat = self._kernel(self._x, x)
    y_pred = self._alpha.dot(k_mat) + self._b
    if raw:
        return y_pred
    return np.sign(y_pred).astype(np.float32)