机器学习核武器: 核方法

高维映射跟核方法的概念很容易混淆.

高维映射通过将样本从原始空间映射到一个更高维的特征空间, 从而解决了低纬下难以解决的问题.
核方法往往跟高维映射配合使用, 可以看做是一种技巧, 可以通过它来避免这种映射带来的复杂计算量.

1. Mapping to High Dimensional Space

我们知道, 线性回归是用一条直线来拟合数据. 但是我们往往会遇到数据并不服从线性分布的情况, 比如:

import numpy as np
import matplotlib.pyplot as plt

x = np.linspace(0,4,40)
y = [-(num-2)**2+4+np.random.normal(0,0.1) for num in x]
plt.scatter(x,y,marker='o',c='r')
plt.xlabel("x")
plt.ylabel("y")
plt.show()

上图这种情况, 明显是一个二次函数的分布. 如果我们仍旧用线性回归方程 $y=w_1x+b$ , 那结果是拟合了一条直线, 这条直线无论如何也不能完美拟合出这样的二次函数的分布.

f1 = np.polyfit(x,y,1)
params = np.poly1d(f1)

line_x = np.linspace(0,4,100)
line_y = [params[1]*num+params[0] for num in line_x]
plt.scatter(x,y,marker='o',c='r')
plt.plot(line_x,line_y,linestyle='--')
plt.xlabel("x")
plt.ylabel("y")
plt.show()

于是，我们选择变成一个二次方程来拟合:

$y=w_2x^2+w_1x+b$

它虽然是个二次函数, 其实仍然可以看成是一个线性回归. 但是现在不是对 $x$ 的线性回归, 而是对于一个更高维度的向量 $\boldsymbol{t}$ 的

$\boldsymbol{t}= \begin{bmatrix} t_1\\ t_2 \end{bmatrix} = \begin{bmatrix} x\\ x^2 \end{bmatrix}$

f2 = np.polyfit(x,y,2)
params = np.poly1d(f2)

line_x = line_x = np.linspace(0,4,100)
line_y = [params[2]*(num**2)+params[1]*num+params[0] for num in line_x]
plt.scatter(x,y,marker='o',c='r')
plt.plot(line_x,line_y,linestyle='--',c='b')
plt.xlabel("x")
plt.ylabel("y")
plt.show()

我们如果把输入 $\boldsymbol{x}$ 看成是一个 1 维的向量, 那么 $\boldsymbol{t}$ 其实就是一个关于 $\boldsymbol{x}$ 的更高维度的向量. 我们把这种能够把一个向量提升维度的函数叫做 $\phi$, 且 $\phi(\boldsymbol{x})=\boldsymbol{t}$. 直观上来讲, 在应用 $\phi$ 以后, 向量 $x$ 被拉长了, 所以我们把它叫做拉伸函数好了.

拉伸函数是一类函数, 表面上看, 只要是能把一个向量经过各种修改让它的维度变高, 这样的函数都能当成拉伸函数来用. 然而并不是这样的, 假如你只是单纯地对向量 $\boldsymbol{x}$ 的分量做线性组合, 你会发现实际上并没有提升它的空间, 比如我设计一种纯线性组合的拉伸的函数:

比如我们将 $\boldsymbol{x}=\begin{bmatrix}x_1\\x_2\end{bmatrix}$ 拉伸为 $\boldsymbol{t}=\begin{bmatrix}x_1+x_2 \\ x_1-x_2 \\ 5x_1+4x_2 \\ -3x_1+2x_2 \end{bmatrix}$, 那么 $\phi(\boldsymbol{x})=\begin{bmatrix}1&1 \\ 1&-1 \\ 5&4 \\ -3&2\end{bmatrix}\boldsymbol{x}$. 那么对于提升后的方程 $y=\boldsymbol{w}^T\boldsymbol{t}$, 乍一看是把2维提升到了4维. 其实通过变换以后, 相当于还是在对 $\boldsymbol{x}$ 做线性组合.

因此, 在选择拉伸函数时, 我们需要选择确确实实提升了维度的拉伸函数. 而且, 我们的拉伸函数得把原来向量的每个维度都得照顾到. 这里分布是一个二次函数, 如果我们遇到了更加复杂的函数, 我们依然可以通过选取合适的拉伸函数来变成线性的问题. 幸运的是可以证明, 只要数据的分布在维度有限的空间上, 我们总是能够找到一个更高维度的空间, 使得它的分布是线性的.

因此通过高维映射以后, 不管原来是不是线性的, 总能通过对向量 $\boldsymbol{x}$ 做拉伸变化, 转化成一个高维空间里的线性回归问题:

$y=\boldsymbol{w}^T\phi(\boldsymbol{x})$

1.1 Solving Equation

如果我们不做高维映射的话, 线性回归的解时:

$\boldsymbol{w}=(\boldsymbol{X}^T\boldsymbol{X}+\lambda \boldsymbol{I})^{-1}\boldsymbol{X}^Ty$

如果我们要对这个公式进行高维映射, 也就是说我们对 $X$ 里的每个样本, 也就是每一行向量都进行了拉伸变换, 得到一个新的矩阵 $\boldsymbol{\Phi}$, 因此我们用 $\boldsymbol{\Phi}$ 来替代公式里的 $\boldsymbol{X}$, 从而得到:

$\boldsymbol{w}=(\boldsymbol{\Phi}^T\boldsymbol{\Phi}+\lambda \boldsymbol{I})^{-1}\boldsymbol{\Phi}^Ty$

好了, 右边全都是已知量, 我们已经解出来了这个模型了. 我们做完高维映射之后的线性方程, 要如何去预测模型呢? 来模拟一下这个过程:

现在假设我们有 $N$ 个训练数据, 每个数据是 $D$ 维的.

(1) 根据公式计算 $\boldsymbol{w}$:

$\boldsymbol{w}=(\boldsymbol{\Phi}^T\boldsymbol{\Phi}+\lambda \boldsymbol{I})^{-1}\boldsymbol{\Phi}^Ty$

(2) 假如我们需要预测 $\boldsymbol{x}_d$ 的输出值 $y_d$, 我们首先得对变量 $\boldsymbol{x}_d$ 做一次拉伸, 得到 $\phi(\boldsymbol{x}_d)$, 在乘上权重, 我们才能求出其预测值 $y_d$.

$y_d=\boldsymbol{w}^T\phi(\boldsymbol{x}_d)$

看看上面的过程中, 我们用了多少次拉伸函数. 在训练过程中, 我们对训练集里面每个样本都用了一次拉伸. 在预测的时候, 我们又要对预测集里面的每个样本做一次拉伸. 现在我告诉你, 拉伸函数往往计算量非常大, 那么计算这个拉伸显然是一个非常大的开销.

虽然说理论上, 因为有限维度的数据必然存在一个拉伸函数将数据映射到高维并且满足线性分布. 也就是说必然存在一个完美的拉伸函数. 然而, 我们往往并不知道到底怎么样的函数才是完美的拉伸函数, 选择合适的拉伸函数也是一个非常麻烦的问题.

现在我告诉你, 我们有一种取巧的办法. 使得我们根本不用计算拉伸函数, 有时候甚至你都不需要知道拉伸函数是什么, 我们依然能够做预测. 这个无比巧妙的简便方法, 帮助我们跳过了拉伸的步骤, 这个方法就叫做核方法.

2. Kernel Function

你可能非常迫切地想知道这个巧妙的核方法到底是什么. 但是我要在这里卖个关子, 不直接告诉你核方法是怎么来的, 我们从定义出发一步一步慢慢推导出来.

现在我要转换一下话题, 我们先研究研究这个拉伸函数 $\phi(\boldsymbol{x})$. 我们给它搭配一个兄弟, 假设向量 $\boldsymbol{y}$ 是某个跟 $\boldsymbol{x}$ 同样维度的某个向量, 我们对 $\boldsymbol{y}$ 也做拉伸. 并且拉伸完之后, 我们把这两个向量求内积.

$\phi(\boldsymbol{x})^T\phi(\boldsymbol{y})=k$

我们知道, 两个向量做内积得到的是一个值. 这个过程中, 我们先是把两个向量拉伸到高维, 然后又通过求内积变回一维.

在数学里面, 有这样一类函数, 它的参数是2个向量, 它的输出是一个标量值. 它有个特点, 就是对于任何相同形状的输入向量, 它总能改写成这样的形式:

$k(\boldsymbol{x},\boldsymbol{y})=\phi(\boldsymbol{x})^T\phi(\boldsymbol{y})$

解释一下, 这类函数对于任何输入向量 $\boldsymbol{x},\boldsymbol{y}$, 它都能改写成分别对两个输入向量做拉伸以后再求内积的表达形式. 这类核函数每个都有各自的表达式, 举两个例子:

(1) 线性核: $k(\boldsymbol{x},\boldsymbol{y})=\boldsymbol{x}^T\boldsymbol{y}$

(2) 多项式核: $k(\boldsymbol{x},\boldsymbol{y})=$ $(\boldsymbol{x}^T\boldsymbol{y}+c)^d$

注意到, 这些表达式里面是不含有拉伸函数的. 但是它既然满足核函数的条件, 它一定是能改写成两个向量拉伸求内积的形式. 线性核里面隐藏的变换就是做线性拉伸变换 (我们之前讨论过, 光用线性拉伸是不能解决非线性问题的). 多项式核自然就是做几次方的拉伸变换. 换句话说, 每一个能被叫做核函数的函数, 里面都藏着一个对应拉伸的函数. 这些核函数的命名通常也跟如何做拉伸变换有关系.

总结一下, 我们现在反了过来, 先找满足核函数条件的的表达式, 再倒推出一种映射关系. 我们选哪个核函数, 实际上就是在选择用哪种方法映射. 通过核函数, 我们就能跳过映射的过程.

2.1 Kernel Method

好了, 现在我们打定主意, 要利用核函数来跳过做映射了. 我们假如找到了一个核函数, 也就是说我们的拉伸函数也定下来了. 我们改写一下核函数的参数, 写成这样的形式:

$k(\boldsymbol{t},\boldsymbol{x})=\phi(\boldsymbol{t})^T\phi(\boldsymbol{x})$

到底要怎么利用呢? 先观察一下高维映射以后的模型表达式:

$y=\boldsymbol{w}^T\phi(\boldsymbol{x})$

观察一下上面两个公式, 你一定能够联想到, 肯定要从这个 $\boldsymbol{w}$ 上面做点文章. 没错, 我们现在就是要想办法从 $\boldsymbol{w}$ 里面分离出一个 $\phi(\boldsymbol{t})^T$ 项出来, 跟我们的 $\phi(\boldsymbol{x})$ 搭配在一起组成我们的核函数的表达式.

我们首先来看看 $\boldsymbol{w}$ 的计算公式:

$\boldsymbol{w}=(\boldsymbol{\Phi}^T\boldsymbol{\Phi}+\lambda \boldsymbol{I})^{-1}\boldsymbol{\Phi}^Ty$

在这里跟拉伸项最有关系的一项就是 $\boldsymbol{\Phi}$ 了, 注意这里全都是在做线性组合, 我们可以令 $\boldsymbol{w}=\boldsymbol{\Phi}^T\boldsymbol{\alpha}$, 这里的 $\boldsymbol{\alpha}$ 我们也不知道是什么东西, 只知道它是一个向量. 使用 $\boldsymbol{\Phi}^T\boldsymbol{\alpha}$ 有什么好处呢?

试着把它展开一下, 矩阵乘向量的怎么写成求和的形式呢. 其实矩阵右乘一个向量, 相当于对矩阵的每一列都乘对于向量位置的分量再累加, 如下所示:

$\begin{bmatrix} x_{11}&x_{12}&x_{13} \\ x_{21}&x_{22}&x_{23} \\ x_{31}&x_{32}&x_{33} \end{bmatrix} \begin{bmatrix} \alpha_1 \\ \alpha_2 \\ \alpha_3 \end{bmatrix} =\alpha_1 \begin{bmatrix} x_{11} \\ x_{21} \\ x_{31} \end{bmatrix} +\alpha_2 \begin{bmatrix} x_{12} \\ x_{22} \\ x_{32} \end{bmatrix} +\alpha_3 \begin{bmatrix} x_{13} \\ x_{23} \\ x_{33} \end{bmatrix}$

矩阵 $\boldsymbol{\Phi}^T$ 是转置过的, 它的每一列代表一个训练数据, 为了避免混淆, 我们用 $\boldsymbol{t}_n$ 表示第 $n$ 个训练数据, 可以表示为:

$\boldsymbol{w}=\boldsymbol{\Phi}^T\boldsymbol{\alpha}=\sum_{n=1}^N\alpha_n\phi(\boldsymbol{t}_n)$

用右边这个替换我们模型里面的 $\boldsymbol{w}$:

$\begin{aligned} y=&\boldsymbol{w}^T\phi(\boldsymbol{x}) \\ =&(\sum_{n=1}^N\alpha_n\phi(\boldsymbol{t}_n))^T\phi(\boldsymbol{x}) \\ =&\sum_{n=1}^N\alpha_n\phi(\boldsymbol{t}_n)^T\phi(\boldsymbol{x}) \end{aligned}$

看到没有, 我们右边已经出现了一个核函数的表达形式了. 我们可以直接根据公式 $k(\boldsymbol{t},\boldsymbol{x})=\phi(\boldsymbol{t})^T\phi(\boldsymbol{x})$ 来替换右边, 从而得到:

$y=\sum_{n=1}^N\alpha_nk(\boldsymbol{t}_n,\boldsymbol{x})$

现在的y表达式中, 已经不含有拉伸函数项了, 这样我们就避开了求拉伸函数的过程. 但是你会发现, 我们并不知道 $\boldsymbol{\alpha}$ 是什么, 现在我们就来求一求它.

我们得从求 $\boldsymbol{w}$ 的表达式开始, 假设我们用最小二乘并同时加入了 $l2$ 正则, 那我们的损失函数可以表示为:

$loss=F(\boldsymbol{w})=(\boldsymbol{\Phi}\boldsymbol{w}-\boldsymbol{y})^T(\boldsymbol{\Phi}\boldsymbol{w}-\boldsymbol{y})+\lambda||\boldsymbol{w}||_2^2$

我们令 $\boldsymbol{K}=\boldsymbol{\Phi}\boldsymbol{\Phi}^T$, $\boldsymbol{w}=\boldsymbol{\Phi}^T\boldsymbol{\alpha}$ 代入到上面这个损失函数中, 我们能够得到:

$\begin{aligned} F(\boldsymbol{w})=F(\boldsymbol{\Phi}^T\boldsymbol{\alpha}) =&(\boldsymbol{\Phi}\boldsymbol{\Phi}^T\boldsymbol{\alpha}-\boldsymbol{y})^T(\boldsymbol{\Phi}\boldsymbol{\Phi}^T\boldsymbol{\alpha}-\boldsymbol{y})+\lambda||\boldsymbol{\Phi}^T\boldsymbol{\alpha}||_2^2 \\ =&(\boldsymbol{K}^T\boldsymbol{\alpha}-\boldsymbol{y})^T(\boldsymbol{K}^T\boldsymbol{\alpha}-\boldsymbol{y}) + \lambda||\boldsymbol{\Phi}^T\boldsymbol{\alpha}||_2^2 \\ =& \boldsymbol{\alpha}^T(\boldsymbol{K}^2+\lambda\boldsymbol{K})\boldsymbol{\alpha}-2\boldsymbol{y}^2\boldsymbol{K}\boldsymbol{\alpha}+\boldsymbol{y}^T\boldsymbol{y} \end{aligned}$

我们对 $\boldsymbol{\alpha}$ 求偏导, 并令其为 0, 可以得到:

$\boldsymbol{\alpha}=(\boldsymbol{K}+\lambda\boldsymbol{I})^{-1}\boldsymbol{y}$

并且 $\boldsymbol{K}$ 的表达式也很容易得到:

$\begin{aligned} \boldsymbol{K}=\boldsymbol{\Phi}\boldsymbol{\Phi}^T =& \begin{bmatrix} \phi(x_1)^T\phi(x_1) &\phi(x_1)^T\phi(x_2) & ... & \phi(x_1)^T\phi(x_n)\\ \phi(x_2)^T\phi(x_1) &\phi(x_2)^T\phi(x_2) & ... & \phi(x_2)^T\phi(x_n) \\ ...\\ \phi(x_n)^T\phi(x_1) &\phi(x_n)^T\phi(x_2) & ... & \phi(x_n)^T\phi(x_n) \end{bmatrix} \\ =& \begin{bmatrix} k(x_1,x_1) & k(x_1,x_2) & ... & k(x_1,x_n)\\ k(x_2,x_1) & k(x_2,x_2) & ... & k(x_2,x_n)\\ ...\\ k(x_n,x_1) & k(x_n,x_2) & ... & k(x_n,x_n) \end{bmatrix} \end{aligned}$

现在我们把所有的拉伸函数都消除掉了, 我们现在就可以用求出来的 $\boldsymbol{\alpha}$ 来做预测, 使用之前我们推出来的公式:

$y=\sum_{n-1}^N\alpha_nk(\boldsymbol{t}_n,\boldsymbol{x})$

3. Summary

在使用机器学习模型做回归或者分类的时候, 假如在低维度空间下数据集不好用, 那么可以尝试通过把输入的值做高维映射来解决. 高维映射不仅仅用于线性回归, 包括逻辑回归, 还有SVM, 尤其是SVM.

由于做高维映射的计算量比较大. 当我们遇到需要做高维映射的时候 $\phi(\boldsymbol{x})$, 可以通过核方法, 把需要学习的模型配出一项来组成 $\phi(\boldsymbol{t})^T\phi(\boldsymbol{x})$ 的形式, 然后用一个核函数 $k(\boldsymbol{t},\boldsymbol{x})$ 来替换它, 从而消除把低维向量往高维映射的过程 $\phi(\boldsymbol{x})$. 这种替换的技巧就叫做核方法, 能够实现替换目的的函数叫做核函数.

利用核方法并非没有缺点. 原来的线性模型显然是一种参数化方法, 好处是训练完成的模型只需要存储权重向量 $\boldsymbol{w}$. 然而在使用了核方法以后, 由于我们用训练集替换掉了权重项, 因此相当于转化成了非参数化的方法, 显然增加了需要存储的数据量, 同时每一次做预测都需要用到全部训练数据集.

我们来看看常见的核函数:

线性核 (Linear Kernel)
$k(x,y)=\alpha x^Ty+c$
线性核, 主要用于线性可分的情况, 但线性内核的适用场景很多, 很多线性可分, 甚至线性不可分的数据集, 使用线性的效果往往比非线性的要好. 尤其是在数据集很大, 且特征很多, 或是特征远大于数据集时, 线性内核便往往能够取得很不错的效果. 且其相对于其他非线性内核, 训练时要快的多.
多项式核函数 (Polynomia kernel)
$k(x,y)=(\alpha x^Ty+c)^d$
多项式核函数可以实现将低维的输入空间映射到高纬的特征空间, 但是多项式核函数的参数多, 当多项式的阶数比较高的时候, 核矩阵的元素值将趋于无穷大或者无穷小, 计算复杂度会大到无法计算. 通常d=2的多项式内核在用来特征选择的时候非常有用.
高斯核 (Gaussian Kernel) / 径向基核函数 (Radial Basis Function)
$k(x,y)=\exp\bigg(-\cfrac{||x-y||^2}{2\sigma^2}\bigg)$
高斯径向基函数是一种局部性强的核函数, 其可以将一个样本映射到一个更高维的空间内, 该核函数是应用最广的一个, 无论大样本还是小样本都有比较好的性能, 而且其相对于多项式核函数参数要少, 因此大多数情况下在不知道用什么核函数的时候, 优先使用高斯核函数.

SVM中, 高斯核为什么会把原始维度映射到无穷多维? - 张骞晖的回答 - 知乎 https://www.zhihu.com/question/35602879/answer/92835616
Sigmoid 核函数
$k(x,y)=\tanh(\alpha x^Tz+c)$

$\alpha$ 可以视为一个 scaling 参数, 常数 $c$ 则是一个 shifting 参数.

有这么多核函数, 那么我们如何选取使用呢?

在选用核函数的时候, 如果我们对我们的数据有一定的先验知识, 就利用先验来选择符合数据分布的核函数; 如果不知道的话, 通常使用交叉验证的方法, 来试用不同的核函数, 误差最下的即为效果最好的核函数, 或者也可以将多个核函数结合起来, 形成混合核函数. 在吴恩达的课上, 也曾经给出过一系列的选择核函数的方法:

如果特征的数量大到和样本数量差不多, 则选用LR或者线性核的SVM;
如果特征的数量小, 样本的数量正常, 则选用SVM+高斯核函数;
如果特征的数量小, 而样本的数量很大, 则需要手工添加一些特征从而变成第一种情况.