14 核方法
Contents
14 核方法¶
14.1 引言¶
截止目前，对于那些我们希望进行分类、聚类或者以任何其他方式处理的对象而言，都假设它们可以被一个固定长度的向量表示，即 \(\mathbf {x}_i \in \mathbb {R}^D\)。然而，对于某些类型的目标，我们并不清楚如何以一个固定长度的向量表示它。比如说，我们如何表示诸如一个文本文件或者蛋白质序列的具备不定长度的目标？或者一个具备复杂 3D 结构的分子结构？或者一个具备不定长度和形状的进化树？
一种解决这类问题的方法是针对数据建立一个生成式模型，然后使用推理得到的潜在表示和（或者）模型的参数作为特征，并将这些特征用于其他标准的方法中。举例来说，在第 28 章，我们会介绍深度学习，它是一种可以学习很好的特征表示的无监督方法。
另一种方法是假设我们有一些衡量对象之间相似度的方法，在这种方法中，我们不需要将对象处理成向量形式。举例来说，当我们比较字符串时，我们可以比较它们之间的编辑距离。令 \(\kappa (\mathbf {x},\mathbf {x}^\prime)\ge0\) 为目标 \(\mathbf {x},\mathbf {x}^\prime\in\chi\) 的某种相似度测量，其中 \(\chi\) 是某个抽象的空间，我们称 \(\kappa\) 为一个核函数 (kernel function)。需要注意的是，此处的 “核 (kernel)” 可以表示几种含义，我们会在 14.7.1 节介绍一种不同的解释。
本章，我们将介绍几种核函数。然后描述几种算法，这些算法可以写成只需要核函数计算的形式。当我们无法（或者选择不去这么做）深入对象 \(\mathbf {x}\) 内部时（译者注：即我们并不关心或者无法将对象 \(\mathbf {x}\) 以固定长度表示），这种方法可以被使用。
14.2 核函数¶
我们定义一个 核函数（ kernel function ） 为关于两个参数的实函数，即 \(\kappa (\mathbf {x},\mathbf {x}^\prime)\in\mathbb {R}\), 其中 \(\mathbf {x},\mathbf {x}^\prime\in\chi\)。核函数满足对称性（ \(\kappa (\mathbf {x},\mathbf {x}^\prime)=\kappa (\mathbf {x}^\prime,\mathbf {x})\) ），非负性（ \(\kappa (\mathbf {x},\mathbf {x}^\prime)\ge 0\) ），所以可以被解释为相似性的衡量，但这种解释并非必须的要求。下文会给出几个例子。
14.2.1 RBF 核¶
平方指数核（ squared exponential kernel, SE ） 或者 高斯核（ Gaussian kernel ） 定义为：
如果 \(\mathbf {\Sigma}\) 是对角矩阵，上式可以被写成：
可以将 \(\sigma_j\) 解释为维度 \(j\) 的 特征长度尺度（ characteristic length scale）。如果 \(\sigma_j=\infty\)，则对应的维度将被忽略；所以这又被称为ARD kernel。如果 \(\mathbf {\Sigma}\) 是球状的矩阵，我们可以得到各向同性的核函数 $\( \kappa (\mathbf {x},\mathbf {x}^\prime)=\exp\left (-\frac {||\mathbf {x}-\mathbf {x}^\prime||^2}{2\sigma^2}\right) \tag {14.3} \)\( 其中 \)\sigma^2\( 被称为**带宽 (bandwidth)**。式 14.3 是**径向基函数 (radial basis function)**或者**RBF**核的一个例子，因为它只是关于 \)||\mathbf {x}-\mathbf {x}^\prime||$ 的函数。
14.2.2 用于比较文本的核¶
在我们进行文本分类或者检索时，需要有一种衡量两个文本 \(\mathbf {x}_i\) 和 \(\mathbf {x}_j\) 相似度的方法。 如果我们使用词袋法对向量进行表示，其中 \(x_{ij}\) 表示在文本 \(i\) 中单词 \(j\) 出现的次数，我们使用余弦相似度 (cosine similarity)，定义为： $\( \kappa (\mathbf {x}_i,\mathbf {x}_{i^\prime})=\frac {\mathbf {x}_i^T\mathbf {x}_{i^\prime}}{||\mathbf {x}_i||_2||\mathbf {x}_{i^\prime}||_2} \tag {14.4} \)$
上式表示向量 \(\mathbf {x}_i\) 和 \(\mathbf {x}_j\) 之间的夹角的余弦值。因为 \(\mathbf {x}_i\) 是一个计数向量（非负），所以余弦相似度的区间为 0 到 1。，其中 0 表示向量正交，也就是说两个文本之间不存在相同的单词。
不幸的是，这种方式并不一定有效，原因有二。首先，如果 \(\mathbf {x}_i\) 与 \(\mathbf {x}_{i^\prime}\) 之间有相同的单词，那使用这种方式计算出来的结果，肯定说明两个文本是相似的，哪怕相同的单词在大部分文本中都会出现，比如 “the”或者“and”，这些单词往往不具备判别性。（这些被称为停用词 (stop words)）。其次，如果一个具有判别性的单词在文本中出现多次，那么相似度将被人为的提升，尽管单词的使用往往具有突发性 (bursty)，也就是说一旦一个单词在文本中出现过一次，那么它再次被使用的概率将会很大（见 3.5.5 节）。
幸运的是，使用一些预处理的方式，我们可以大幅地提高性能。这种方式使用一种新的特征向量取代单词计数的向量，这种新的向量被称为逆文档频率 (TF-IDF, term frequency inverse documnet frequency)。该向量定义方式如下，首先，定义频率为计数的函数： $\( {\rm {tf}}(x_{ij})=\log (1+x_{ij}) \tag {14.5} \)$
通过上述方法，我们可以降低那些在一个文本中出现频率特别高的单词的影响。其次，逆文档频率定义为： $\( {\rm {idf}}(j)=\log \frac {N}{1+\sum_{i=1}^N \mathbb {I}(x_{ij}>0)} \tag {14.6} \)$
其中 \(N\) 表示文档的数量之和，分母表示含单词 \(j\) 的文档数量的总和。最后定义： $\( {\rm {tf}}-{\rm {idf}}(\mathbf {x}_i) \triangleq [{\rm {tf}}(x_{ij}) \times {\rm {idf}}(j)]_{j=1}^V \tag {14.7} \)$
（存在一些其他的方式定义 \(\rm {tf}\) 和 \(\rm {idf}\)，更多细节参考 (Manning et al.2008))。基于上述定义，使用余弦相似度，也就是说，新的核函数定义为： $\( \kappa (\mathbf {x}_i,\mathbf {x}_{i^\prime})=\frac {\mathbf {\phi}(\mathbf {x}_i)^T\mathbf {\phi}(\mathbf {x}_{i^\prime})}{\left \| \mathbf {\phi}(\mathbf {x}_i) \right \|_2 \left \| \mathbf {\phi}(\mathbf {x}_{i^\prime}) \right \|_2} \tag {14.8} \)\( 其中 \)\mathbf {\phi}(\mathbf {x})={\rm {tf-idf}}(\mathbf {x})$。该方式在信息检索领域十分有效。
关于 \(\rm {tf-idf}\) 核的概率解释可参考 (Elkan 2005)。
14.2.3 梅塞（正定）核¶
在我们研究的一些方法中，需要核函数满足：对于输入 \(\{\mathbf {x}_i\}_{i=1}^N\) 的任意子集，格拉姆 (Gram) 矩阵为正定矩阵，矩阵定义为： $\( \rm {\mathbf {K}}= \begin {pmatrix}\kappa (\mathbf {x}_1,\mathbf {x}_1) & \cdots & \kappa (\mathbf {x}_1,\mathbf {x}_N) \\& \vdots \\\kappa (\mathbf {x}_N,\mathbf {x}_1) & \cdots & \kappa (\mathbf {x}_N,\mathbf {x}_N)\end {pmatrix} \tag {14.9} \)$ 我们称这样的核为**梅塞 (Mercer)核，或者正定 (positive definite)**核。结果表明 (Schoelkopf and Smola 2002)，高斯核和余弦相似度核都是梅塞核 (Sahami and Heilman 2006)。
梅塞核的重要性在于梅塞理论 (Mercer’s theorem)。如果格拉姆矩阵为正定矩阵，我们可以计算它的特征向量分解： $\( \mathbf {K}=\mathbf {U}^T\mathbf {\Lambda}\mathbf {U} \tag {14.10} \)\( 其中 \)\mathbf {\Lambda}\( 为对角矩阵，对角线元素为奇异值 \)\lambda_i\gt0\(。现在考虑 \)\mathbf {K}\( 中的一个元素： \)\( k_{ij}=(\mathbf {\Lambda}^{\frac {1}{2}}\mathbf {U}_{:,i})^T (\mathbf {\Lambda}^{\frac {1}{2}}\mathbf {U}_{:,j}) \tag {14.11} \)\( 定义 \)\mathbf {\phi}(\mathbf {x}i)=\mathbf {\Lambda}^{\frac {1}{2}}\mathbf {U}{:,i}\(。则上式可以写成： \)\( k_{ij}=\mathbf {\phi}(\mathbf {x}_i)^T\mathbf {\phi}(\mathbf {x}_j) \tag {14.12} \)\( 所以我们发现，核矩阵中的元素可以通过计算某个特征向量之间的内积得到，这些向量本质上通过特征向量 \)\mathbf {U}\( 定义。事实上，对于梅塞核而言，必然存在一个函数 \)\mathbf {\phi}\( 将 \)\mathbf {x}\in {\chi}\( 映射到空间 \)\mathbb {R}^D\(，从而使得： \)\( k (\mathbf {x},\mathbf {x}^\prime)=\mathbf {\phi}(\mathbf {x})^T\mathbf {\phi}(\mathbf {x}^\prime) \tag {14.13} \)\( 其中 \)\phi\( 取决于 \)\kappa\( 的特征方程式（所以 \)D\( 本质上是无穷维度的空间）。 举例来说，考虑一个（非定常）的**多项式核 (polynomial kernel)**\)\kappa (\mathbf {x},\mathbf {x}^\prime)=(\gamma\mathbf {x}^T\mathbf {x}^\prime+r)^M\(，其中 \)r\gt0\(。我们发现对应的特征向量 \)\phi (\mathbf {x})\( 包含所有阶数的项。比如，对于 \)M=2,\gamma=r=1\(，且 \)\mathbf {x},\mathbf {x}^\prime \in \mathbb {R}^2\(，我们有： \)\( \begin {align}(1+\mathbf {x}^T\mathbf {x}^\prime)^2 & = (1+x_1x_1^\prime+x_2x_2^\prime)^2 \tag {14.14} \\& = 1+ 2x_1x_1^\prime + 2x_2x_2^\prime + (x_1x_1^\prime)^2 + (x_2x_2^\prime)^2 + 2x_1x_1^\prime x_2x_2^\prime \tag {14.15} \end {align} \)\( 上式可以写成 \)\phi (\mathbf {x})^T\phi (\mathbf {x^\prime})\( 的形式，其中 \)\( \mathbf {\phi}(\mathbf {x})=[1, \sqrt {2} x_1,\sqrt {2} x_2,x_1^2, x_2^2, \sqrt {2} x_1x_2]^T \tag {14.16} \)$ 所以使用该核等价于在一个 6 维空间中进行相似度度量。对于一个高斯核，则对应一个无穷维度的空间。在这种情况下，显然没有办法明确的表示出特征向量。
另一个非梅塞核的例子为sigmoid核，定义为： $\( \kappa (\mathbf {x},\mathbf {x}^\prime)={\rm {tanh}}(\gamma\mathbf {x}^T\mathbf {x}^\prime+r) \tag {14.17} \)$ （需要注意的是尽管它被称为 sigmoid 核，但使用的却是 tanh 函数）。这个核的灵感来自于多层感知机（见 16.5 节），但是没有真正的理由使用它。(15.4.5 节将介绍一个真正的正定的 “神经网络核”)
通常情况下，构造一个梅塞核是十分困难的，需要泛函分析的相关技术。然而，基于一些简单形式的核，并且使用一些标准的规则，则有可能构建一个新的梅塞核。举例来说，如果 \(\kappa_1\) 和 \(\kappa_2\) 都是梅塞核，那么 \(\kappa (\mathbf {x},\mathbf {x}^\prime)=\kappa_1 (\mathbf {x},\mathbf {x}^\prime)+\kappa_2 (\mathbf {x},\mathbf {x}^\prime)\) 也是一个梅塞核。
14.2.4 线性核¶
通常情况下，由一个核推导出特征向量是相当困难的，而且只有在梅塞核的前提下才有可能。然而，基于特征向量推导一个核却是容易的，我们只需要对向量进行内积，即： $\( \kappa (\mathbf {x},\mathbf {x}^\prime)=\phi (\mathbf {x})^T\phi (\mathbf {x}^\prime)=\left\langle \phi (\mathbf {x}),\phi (\mathbf {x}^\prime) \right\rangle \tag {14.18} \)\( 如果 \)\phi (\mathbf {x})=\mathbf {x}\(，我们将得到一个**线性核 (linear kernel)**: \)\( \kappa (\mathbf {x},\mathbf {x}^\prime)=\mathbf {x}^T\mathbf {x}^\prime \tag {14.19} \)$ 当原始的数据本身已经具备很高的维度时，线性核将十分有用。也就是说，如果原始的特征向量的单个维度可以提供足够的信息，比如说，在词库量巨大的情况下的通过词袋法得到的向量，或者大量基因的表达水平。在这种情况下，决策边界很有可能是原始特征向量的线性组合，而没有必要在其他空间对数据进行处理。
当然，并不是所有的高维数据都是线性可分的。比如说，图片是高维数据，但单个像素并不能提供有价值的信息，所以在图片分类领域中一般使用非线性核（见 14.2.7 节）。