Kernel Methods

约 5884 个字 预计阅读时间 20 分钟

Feature Maps

回想一下在我们讨论线性回归时，我们考虑了从房屋的居住面积（用 \(x\) 表示）预测房屋价格（用 \(y\) 表示）的问题，并且我们拟合了 \(x\) 的线性函数到训练数据上。如果价格 \(y\) 可以被更准确地表示为 \(x\) 的非线性函数呢？在这种情况下，我们需要比线性模型更具表达力的模型族。

我们首先考虑拟合立方函数 \(y = \theta_3 x^3 + \theta_2 x^2 + \theta_1 x + \theta_0\)。事实证明，我们可以将立方函数视为在一组不同特征变量上的线性函数（定义如下）。具体来说，让函数 \(\phi: \mathbb{R} \to \mathbb{R}^4\) 定义为

\[\begin{aligned} \phi(x) = \begin{bmatrix} 1 \\ x \\ x^2 \\ x^3 \end{bmatrix} \in \mathbb{R}^4. \end{aligned}\]

令 \(\theta \in \mathbb{R}^4\) 为包含 \(\theta_0, \theta_1, \theta_2, \theta_3\) 作为元素的向量。那么我们可以将 \(x\) 的立方函数重写为：

\[\begin{aligned} \theta_3 x^3 + \theta_2 x^2 + \theta_1 x + \theta_0 = \theta^T \phi(x) \end{aligned}\]

因此，变量 \(x\) 的立方函数可以看作是变量 \(\phi(x)\) 上的线性函数。为了在核方法的上下文中区分这两组变量，我们将"原始"输入值称为问题的输入属性（在这种情况下，即 \(x\)，居住面积）。当原始输入被映射到一组新的量 \(\phi(x)\) 时，我们将这些新量称为特征变量。（不幸的是，不同作者在不同上下文中使用不同术语来描述这两个概念。）我们将 \(\phi\) 称为特征映射，它将属性映射到特征。

LMS with Features

我们将推导用于拟合模型 \(\theta^T \phi(x)\) 的梯度下降算法。首先回顾普通最小二乘问题，其中我们要拟合 \(\theta^T x\)，批量梯度下降更新为（参见第一讲笔记的推导）：

\[\begin{aligned} \theta := \theta + \alpha \sum_{i=1}^n \left(y^{(i)} - h_\theta(x^{(i)})\right) x^{(i)} \\ := \theta + \alpha \sum_{i=1}^n \left(y^{(i)} - \theta^T x^{(i)}\right) x^{(i)}. \end{aligned}\]

令 \(\phi: \mathbb{R}^d \to \mathbb{R}^p\) 为特征映射，将属性 \(x\)（在 \(\mathbb{R}^d\) 中）映射到特征 \(\phi(x)\) 在 \(\mathbb{R}^p\) 中。（在前一小节的激励例子中，我们有 \(d=1\) 且 \(p=4\)。）现在我们的目标是拟合函数 \(\theta^T \phi(x)\)，其中 \(\theta\) 是 \(\mathbb{R}^p\) 中的向量而非 \(\mathbb{R}^d\) 中的向量。我们可以在上面的算法中将所有 \(x^{(i)}\) 的出现替换为 \(\phi(x^{(i)})\) 以获得新的更新规则：

\[\begin{aligned} \theta := \theta + \alpha \sum_{i=1}^n \left(y^{(i)} - \theta^T \phi(x^{(i)})\right) \phi(x^{(i)}) \end{aligned}\]

类似地，相应的随机梯度下降更新规则为：

\[\begin{aligned} \theta := \theta + \alpha \left(y^{(i)} - \theta^T \phi(x^{(i)})\right) \phi(x^{(i)}) \end{aligned}\]

LMS with the Kernel Trick

当特征 \(\phi(x)\) 高维时，上述梯度下降更新或随机梯度更新在计算上变得昂贵。例如，考虑方程 (5.1) 中特征映射的直接扩展到高维输入 \(x\)：假设 \(x \in \mathbb{R}^d\)，并且 \(\phi(x)\) 是包含 \(x\) 所有度数 \(\leq 3\) 的单项式的向量：

\[\begin{aligned} \phi(x) = \begin{bmatrix} 1 \\ x_1 \\ x_2 \\ \vdots \\ x_1^2 \\ x_1 x_2 \\ x_1 x_3 \\ \vdots \\ x_2 x_1 \\ \vdots \\ x_1^3 \\ x_1^2 x_2 \\ \vdots \end{bmatrix}. \end{aligned}\]

特征 \(\phi(x)\) 的维度在 \(d^3\) 数量级上。[此处有图片] 这对于计算目的来说是一个过长的向量 — 当 \(d=1000\) 时，每次更新至少需要计算和存储一个 \(1000^3 = 10^9\) 维向量，这比普通最小二乘更新规则 (5.2) 慢 \(10^6\) 倍。

乍一看，这种每次更新 \(d^3\) 运行时间和内存使用似乎是不可避免的，因为向量 \(\theta\) 本身维度为 \(p \approx d^3\)，我们可能需要更新 \(\theta\) 的每个条目并存储它。然而，我们将介绍核技巧，借此我们将不需要显式存储 \(\theta\)，并且运行时间可以大大改善。

为简单起见，我们假设初始化值 \(\theta = 0\)，并且我们关注迭代更新 (5.3)。主要观察是，在任何时候，\(\theta\) 都可以表示为向量 \(\phi(x^{(1)}), \ldots, \phi(x^{(n)})\) 的线性组合。确实，我们可以通过如下归纳法证明这一点。在初始化时，\(\theta = 0 = \sum_{i=1}^n 0 \cdot \phi(x^{(i)})\)。假设在某一点，\(\theta\) 可以表示为

\[\begin{aligned} \theta = \sum_{i=1}^n \beta_i \phi(x^{(i)}) \end{aligned}\]

对于某些 \(\beta_1, \ldots, \beta_n \in \mathbb{R}\)。然后我们声称在下一轮中，\(\theta\) 仍然是 \(\phi(x^{(1)}), \ldots, \phi(x^{(n)})\) 的线性组合，因为

\[\begin{aligned} \theta := \theta + \alpha \sum_{i=1}^n \left(y^{(i)} - \theta^T \phi(x^{(i)})\right) \phi(x^{(i)}) \\ = \sum_{i=1}^n \beta_i \phi(x^{(i)}) + \alpha \sum_{i=1}^n \left(y^{(i)} - \theta^T \phi(x^{(i)})\right) \phi(x^{(i)}) \\ = \sum_{i=1}^n \left(\beta_i + \alpha \left(y^{(i)} - \theta^T \phi(x^{(i)})\right)\right) \phi(x^{(i)}) \end{aligned}\]

你可能意识到我们的总体策略是通过一组系数 \(\beta_1, \ldots, \beta_n\) 隐式表示 \(p\) 维向量 \(\theta\)。为此，我们推导出系数 \(\beta_1, \ldots, \beta_n\) 的更新规则。使用上面的方程，我们看到新的 \(\beta_i\) 取决于旧的 \(\beta_i\) 通过

\[\begin{aligned} \beta_i := \beta_i + \alpha \left(y^{(i)} - \theta^T \phi(x^{(i)})\right) \end{aligned}\]

这里我们在等式右侧仍然有旧的 \(\theta\)。将 \(\theta = \sum_{j=1}^n \beta_j \phi(x^{(j)})\) 代入得到

\[\begin{aligned} \forall i \in \{1, \ldots, n\}, \beta_i := \beta_i + \alpha \left(y^{(i)} - \sum_{j=1}^n \beta_j \phi(x^{(j)})^T \phi(x^{(i)})\right) \end{aligned}\]

我们经常将 \(\phi(x^{(j)})^T \phi(x^{(i)})\) 重写为 \(\langle\phi(x^{(j)}), \phi(x^{(i)})\rangle\) 以强调它是两个特征向量的内积。将 \(\beta_i\) 视为 \(\theta\) 的新表示，我们已成功将批量梯度下降算法转化为迭代更新 \(\beta\) 值的算法。看起来在每次迭代中，我们仍然需要计算所有 \(i,j\) 对的 \(\langle\phi(x^{(j)}), \phi(x^{(i)})\rangle\) 值，每次计算可能需要大约 \(O(p)\) 操作。然而，有两个重要属性来救援：

1. 我们可以在循环开始前预先计算所有 \(i,j\) 对的成对内积 \(\langle\phi(x^{(j)}), \phi(x^{(i)})\rangle\)。

2. 对于在 (5.5) 中定义的特征映射 \(\phi\)（或许多其他有趣的特征映射），计算 \(\langle\phi(x^{(j)}), \phi(x^{(i)})\rangle\) 可以是高效的，并且不需要明确计算高维特征向量 \(\phi(x^{(i)})\) 和 \(\phi(x^{(j)})\)。

第二项特别重要，所以让我们仔细研究。例如，对于上面定义的立方特征映射，我们有：

\[\begin{aligned} \langle\phi(x), \phi(z)\rangle &= \left\langle\begin{bmatrix} 1 \\ x \\ x^2 \\ x^3 \end{bmatrix}, \begin{bmatrix} 1 \\ z \\ z^2 \\ z^3 \end{bmatrix}\right\rangle \\ &= 1 \cdot 1 + x \cdot z + x^2 \cdot z^2 + x^3 \cdot z^3 \\ &= 1 + xz + (xz)^2 + (xz)^3 \\ &= 1 + xz + (xz)^2 + (xz)^3 \\ &= 1 + xz + (xz)^2 + (xz)^3 \\ &= (1 + xz)^3 \end{aligned}\]

更一般地，假设 \(\phi(x)\) 包含所有 \(x\) 的单项式，其度数最多为 \(k\)。那么我们有：

\[\begin{aligned} \langle\phi(x), \phi(z)\rangle &= \sum_{i_1=0}^k \sum_{i_2=0}^k \cdots \sum_{i_d=0}^k (x_1^{i_1}x_2^{i_2}\cdots x_d^{i_d})(z_1^{i_1}z_2^{i_2}\cdots z_d^{i_d}) \\ &= \sum_{i_1=0}^k \sum_{i_2=0}^k \cdots \sum_{i_d=0}^k (x_1z_1)^{i_1}(x_2z_2)^{i_2}\cdots (x_dz_d)^{i_d} \\ &= \prod_{j=1}^d \sum_{i_j=0}^k (x_j z_j)^{i_j} \\ &= \prod_{j=1}^d \frac{1-(x_jz_j)^{k+1}}{1-x_jz_j} \\ &= \prod_{j=1}^d (1 + x_jz_j + (x_jz_j)^2 + \cdots + (x_jz_j)^k) \end{aligned}\]

对于 \(k=3\) 且 \(x, z \in \mathbb{R}\)（即 \(d=1\)），这个公式简化为我们之前计算的 \((1 + xz)^3\)。

重要的观察是：计算两个向量 \(\phi(x)\) 和 \(\phi(z)\) 的内积，尽管这些向量可能是高维的（大小为 \(O(d^k)\)），但计算它们的内积的时间复杂度只有 \(O(dk)\)，远低于明确形成向量所需的 \(O(d^k)\) 时间。

我们将这个概念推广一步。定义核函数 \(K(x,z) = \langle\phi(x), \phi(z)\rangle\)，这是 \(x\) 和 \(z\) 的函数，它直接计算特征向量的内积。我们称这个函数为核，因为我们可以验证它满足 Mercer 定理的条件，即它是对称的，并且对任意 \(x_1, ..., x_m\) 和 \(c_1, ..., c_m\)，核矩阵 \(K\) 是半正定的，其中 \(K_{ij} = K(x_i, x_j)\)。

使用核函数，我们可以重写 \(\beta\) 的更新规则：

\[\begin{aligned} \beta_i := \beta_i + \alpha \left(y^{(i)} - \sum_{j=1}^n \beta_j K(x^{(j)}, x^{(i)})\right) \end{aligned}\]

这个算法现在避免了直接计算高维特征向量的需要。我们称之为核技巧。

给定一个训练样本 \(S = \{(x^{(1)}, y^{(1)}), \ldots, (x^{(n)}, y^{(n)})\}\)，且我们运行算法来拟合参数 \(\beta\)。我们如何对新点 \(x\) 进行预测呢？回想一下我们的预测函数是：

\[\begin{aligned} h(x) &= \theta^T \phi(x) \\ &= \left(\sum_{i=1}^n \beta_i \phi(x^{(i)})\right)^T \phi(x) \\ &= \sum_{i=1}^n \beta_i \phi(x^{(i)})^T \phi(x) \\ &= \sum_{i=1}^n \beta_i K(x^{(i)}, x) \end{aligned}\]

因此，我们可以将预测函数表示为核函数的加权和。

虽然我们是从多项式特征映射开始的，但许多其他核函数也是可行且有用的。例如，高斯核（也称为 RBF 核）定义为：

\[\begin{aligned} K(x, z) = \exp\left(-\frac{\|x-z\|^2}{2\sigma^2}\right) \end{aligned}\]

其中 \(\sigma\) 是带宽参数。这对应于一个无限维的特征空间。核技巧的强大之处在于，我们可以在这些高维甚至无限维的特征空间中工作，而无需明确形成特征向量。

总结一下，核方法通过以下步骤工作： 1. 选择一个特征映射 \(\phi\)，将原始属性转换为可能是高维的特征 2. 选择一个核函数 \(K(x,z)\)，直接计算特征向量的内积 3. 使用核函数重新表述学习算法，避免直接在高维特征空间中操作

这种方法使我们能够使用简单的线性方法（如线性回归、逻辑回归或支持向量机）来捕获输入空间中的非线性模式，而不会产生显式计算高维特征向量的计算成本。

Properties of Kernels

在上一小节中，我们从一个显式定义的特征映射 \(\phi\) 开始，它导出了核函数 \(K(x,z) \triangleq \langle\phi(x), \phi(z)\rangle\)。然后我们看到核函数是如此内在，以至于只要定义了核函数，整个训练算法就可以完全用核的语言编写，而不需要引用特征映射 \(\phi\)，测试样本 \(x\) 的预测也是如此（方程 (5.12)）。

因此，我们会尝试定义其他核函数 \(K(\cdot,\cdot)\) 并运行算法 (5.11)。注意，算法 (5.11) 不需要显式访问特征映射 \(\phi\)，因此我们只需要确保特征映射 \(\phi\) 的存在性，但不一定需要能够显式地写出 \(\phi\)。

那么，什么样的函数 \(K(\cdot,\cdot)\) 可以对应于某个特征映射 \(\phi\)？换句话说，我们能否判断是否存在某个特征映射 \(\phi\) 使得对所有 \(x,z\) 都有 \(K(x,z) = \phi(x)^T\phi(z)\)？

如果我们能够通过给出有效核函数的精确特征来回答这个问题，那么我们就可以完全改变接口，从选择特征映射 \(\phi\) 到选择核函数 \(K\)。具体来说，我们可以选择一个函数 \(K\)，验证它满足特征化（这样就存在一个特征映射 \(\phi\) 与 \(K\) 对应），然后我们可以运行更新规则 (5.11)。这里的好处是我们不必能够计算 \(\phi\) 或者在分析上写出它，我们只需要知道它的存在性。在这个小节结束时，我们将在经过几个具体的核例子后回答这个问题。

假设 \(x,z \in \mathbb{R}^d\)，首先考虑定义如下的函数 \(K(\cdot,\cdot)\)：

\[\begin{aligned} K(x,z) = (x^Tz)^2. \end{aligned}\]

我们也可以将其写为：

\[\begin{aligned} K(x,z) &= \left(\sum_{i=1}^d x_iz_i\right)\left(\sum_{j=1}^d x_jz_j\right) \\ &= \sum_{i=1}^d\sum_{j=1}^d x_ix_jz_iz_j \\ &= \sum_{i,j=1}^d (x_ix_j)(z_iz_j) \end{aligned}\]

因此，我们看到 \(K(x,z) = \langle\phi(x), \phi(z)\rangle\) 是对应于特征映射 \(\phi\)（这里为 \(d=3\) 的情况）的核函数：

\[\begin{aligned} \phi(x) = \begin{bmatrix} x_1x_1 \\ x_1x_2 \\ x_1x_3 \\ x_2x_1 \\ x_2x_2 \\ x_2x_3 \\ x_3x_1 \\ x_3x_2 \\ x_3x_3 \end{bmatrix}. \end{aligned}\]

从计算效率的角度重新审视核，注意计算高维的 \(\phi(x)\) 需要 \(O(d^2)\) 时间，而计算 \(K(x,z)\) 只需要 \(O(d)\) 时间——与输入属性的维度呈线性关系。

另一个相关的例子，也考虑 \(K(\cdot,\cdot)\) 定义为：

\[\begin{aligned} K(x,z) &= (x^Tz + c)^2 \\ &= \sum_{i,j=1}^d (x_ix_j)(z_iz_j) + \sum_{i=1}^d (\sqrt{2c}x_i)(\sqrt{2c}z_i) + c^2. \end{aligned}\]

（自行验证这一点。）这个函数 \(K\) 是对应于特征映射（再次以 \(d=3\) 为例）的核函数：

\[\begin{aligned} \phi(x) = \begin{bmatrix} x_1x_1 \\ x_1x_2 \\ x_1x_3 \\ x_2x_1 \\ x_2x_2 \\ x_2x_3 \\ x_3x_1 \\ x_3x_2 \\ x_3x_3 \\ \sqrt{2c}x_1 \\ \sqrt{2c}x_2 \\ \sqrt{2c}x_3 \\ c \end{bmatrix}, \end{aligned}\]

参数 \(c\) 控制了 \(x_i\)（一阶）和 \(x_ix_j\)（二阶）项的相对权重。

更广泛地说，核 \(K(x,z) = (x^Tz + c)^k\) 对应于一个特征映射到 \(\binom{d+k}{k}\) 维特征空间，对应于所有形式为 \(x_{i_1}x_{i_2}...x_{i_k}\) 的单项式，其阶数最高为 \(k\)。然而，尽管在这个 \(O(d^k)\) 维空间中工作，计算 \(K(x,z)\) 仍然只需要 \(O(d)\) 时间，因此我们永远不需要在这个非常高维的特征空间中显式表示特征向量。

核作为相似度度量。现在，让我们谈论核的一个略有不同的视角。直观地讲（虽然这种直觉有问题，但暂且不管），如果 \(\phi(x)\) 和 \(\phi(z)\) 彼此接近，那么我们可能期望 \(K(x,z) = \phi(x)^T\phi(z)\) 会很大。相反，如果 \(\phi(x)\) 和 \(\phi(z)\) 相距较远——比如说几乎相互正交——那么 \(K(x,z) = \phi(x)^T\phi(z)\) 将会很小。所以，我们可以把 \(K(x,z)\) 看作是 \(\phi(x)\) 和 \(\phi(z)\) 相似度的某种度量，或者说 \(x\) 和 \(z\) 的相似度。

基于这种直觉，假设你在处理某个学习问题时，你想出了一个函数 \(K(x,z)\)，你认为它可能是 \(x\) 和 \(z\) 相似度的合理度量。例如，也许你选择了：

\[\begin{aligned} K(x,z) = \exp\left(-\frac{\|x-z\|^2}{2\sigma^2}\right). \end{aligned}\]

这是 \(x\) 和 \(z\) 相似度的合理度量，当 \(x\) 和 \(z\) 接近时接近 1，当 \(x\) 和 \(z\) 相距较远时接近 0。是否存在某个特征映射 \(\phi\) 使得 \(K(x,z) = \phi(x)^T\phi(z)\)？换句话说，核函数 \(K\) 是否是有效的？

事实证明，上面定义的高斯核 \(K\) 确实对应于某个特征映射 \(\phi\)。准确地说，可以证明它对应于一个无限维的特征映射。尽管如此，如果我们直接使用核函数 \(K\)，我们仍然只需要 \(O(d)\) 的时间来计算 \(K(x,z)\)。

更一般地，Mercer 定理告诉我们，\(K\) 是有效核当且仅当对应的核矩阵是半正定的。更准确地说，对于核函数 \(K\) 是有效的——即存在某个特征映射 \(\phi\) 使得对所有 \(x,z\) 都有 \(K(x,z) = \phi(x)^T\phi(z)\)——的必要充分条件是，对于任意 \(\{x^{(1)}, \ldots, x^{(m)}\}\)，相应的核矩阵 \(K \in \mathbb{R}^{m \times m}\) 是对称半正定的，其中 \(K_{ij} = K(x^{(i)}, x^{(j)})\)。

当我们使用核函数 \(K\) 对应的特征映射时，有一个有趣的属性：核函数 \(K\) 仅仅是在原始属性上定义的，但对应的特征映射 \(\phi\) 可能会创建非常丰富的特征。例如，如果特征映射 \(\phi\) 是多项式的（例如，包含所有二次项 \(x_ix_j\)），那么我们的模型可以学习包含这些高阶项的模式。再举一个例子，我们可以证明高斯核对应于一个包含所有可能多项式阶数的特征映射。因此，通过使用核函数，我们可以在高维特征空间中工作，同时避免显式计算这些特征。

这就是核方法的优雅之处：通过定义一个有效的核函数，我们可以隐式地在高维特征空间中工作，而不必显式构建这些特征。这使得我们可以使用线性算法（如线性回归、对数回归和SVM）来学习复杂的非线性决策边界。

Common Kernel Choices

实践中，有几个常用的核函数：

1. 线性核：\(K(x,z) = x^Tz\) 这相当于没有应用任何特征映射，直接在原始特征空间中工作。

2. 多项式核：\(K(x,z) = (x^Tz + c)^d\) 如我们所见，这对应于特征映射到所有阶数最高为 \(d\) 的单项式空间。

3. 高斯核/RBF核：\(K(x,z) = \exp\left(-\frac{\|x-z\|^2}{2\sigma^2}\right)\) 这对应于一个无限维的特征空间，\(\sigma\) 参数控制了特征的"宽度"。

4. 字符串核、图核和其他结构化数据核： 对于文本、图形等结构化数据，我们可以定义专门的核函数来测量它们的相似度。

核函数的选择通常取决于具体的应用和数据特性。例如，对于具有明显非线性特征的数据，高斯核可能是一个好选择；而对于文本数据，字符串核可能更合适。

Advantages and Disadvantages of Kernel Methods

优点：

• 能够在高维甚至无限维的特征空间中有效工作
• 避免了显式特征映射的计算成本
• 可以捕获复杂的非线性模式
• 适用于多种学习算法（不仅仅是回归）

缺点：

• 计算核矩阵的时间复杂度为 \(O(n^2)\)，对于大数据集可能会成为瓶颈
• 核函数的选择和参数调整可能需要经验和交叉验证
• 结果模型可能难以解释，因为我们在一个隐式的特征空间中工作

在下一节中，我们将看到核方法如何应用于其他学习算法，特别是支持向量机。

Necessary Conditions for Valid Kernels

假设存在一个特征映射 \(\phi\) 使得上面定义的核 \(K\) 满足 \(K(x,z) = \phi(x)^T\phi(z)\)？在这个特定例子中，答案是肯定的。这个核被称为高斯核，对应于一个无限维的特征映射 \(\phi\)。我们将给出关于函数 \(K\) 需要满足什么性质才能成为对应于某个特征映射 \(\phi\) 的有效核函数的精确描述。

假设现在 \(K\) 确实是对应于某个特征映射 \(\phi\) 的有效核，我们首先看看它满足什么性质。考虑一个有限的 \(n\) 个点集合（不一定是训练集）\(\{x^{(1)}, \ldots, x^{(n)}\}\)，并让一个方阵 \(K\) 的 \((i,j)\) 元素由 \(K_{ij} = K(x^{(i)}, x^{(j)})\) 给出。这个矩阵被称为核矩阵。注意，我们重载了符号，既用 \(K\) 表示核函数 \(K(x,z)\)，也用 \(K\) 表示核矩阵 \(K\)，这是由于它们明显的密切关系。

现在，如果 \(K\) 是有效核，那么 \(K_{ij} = K(x^{(i)}, x^{(j)}) = \phi(x^{(i)})^T\phi(x^{(j)}) = \phi(x^{(j)})^T\phi(x^{(i)}) = K(x^{(j)}, x^{(i)}) = K_{ji}\)，因此 \(K\) 必须是对称的。此外，令 \(\phi_k(x)\) 表示向量 \(\phi(x)\) 的第 \(k\) 个坐标，我们发现对于任意向量 \(z\)，有：

\[\begin{aligned} z^TKz &= \sum_i\sum_j z_iK_{ij}z_j \\ &= \sum_i\sum_j z_i\phi(x^{(i)})^T\phi(x^{(j)})z_j \\ &= \sum_i\sum_j z_i\sum_k \phi_k(x^{(i)})\phi_k(x^{(j)})z_j \\ &= \sum_i\sum_j\sum_k z_i\phi_k(x^{(i)})\phi_k(x^{(j)})z_j \\ &= \sum_k \left(\sum_i z_i\phi_k(x^{(i)})\right)^2 \\ &\geq 0. \end{aligned}\]

倒数第二步使用了事实 \(\sum_{i,j} a_ia_j = (\sum_i a_i)^2\)，其中 \(a_i = z_i\phi_k(x^{(i)})\)。由于 \(z\) 是任意的，这表明 \(K\) 是半正定的（\(K \geq 0\)）。

因此，我们已经证明了如果 \(K\) 是有效核（即，如果它对应于某个特征映射 \(\phi\)），那么相应的核矩阵 \(K \in \mathbb{R}^{n \times n}\) 是对称半正定的。

Sufficient Conditions for Valid Kernels

更一般地，上述条件不仅是必要的，而且也是充分的，这使得 \(K\) 成为有效核（也称为 Mercer 核）。以下结果归功于 Mercer：

定理（Mercer）：令 \(K: \mathbb{R}^d \times \mathbb{R}^d \mapsto \mathbb{R}\) 给定。那么对于 \(K\) 成为有效（Mercer）核，必要且充分的条件是对于任意 \(\{x^{(1)}, \ldots, x^{(n)}\}\)（\(n < \infty\)），相应的核矩阵是对称半正定的。

给定一个函数 \(K\)，除了尝试找到与之对应的特征映射 \(\phi\) 外，该定理提供了另一种测试其是否为有效核的方法。你将有机会在问题集2中更多地探讨这些想法。

在课堂上，我们还简要讨论了其他几个核的例子。例如，考虑数字识别问题，其中给定一个手写数字（0-9）的图像（16x16像素），我们需要判断它是哪个数字。使用简单的多项式核 \(K(x,z) = (x^Tz)^k\) 或高斯核，SVM 能够在这个问题上获得极佳的性能。这特别令人惊讶，因为输入属性 \(x\) 只是256维的图像像素强度值向量，系统对视觉没有先验知识，甚至不知道哪些像素与哪些像素相邻。

另一个我们在讲座中简要讨论的例子是，如果我们试图分类的对象 \(x\) 是字符串（例如，\(x\) 是氨基酸列表，串在一起形成蛋白质），那么对于大多数学习算法来说，构造一个合理的、"小"的特征集似乎很困难，尤其是当不同字符串具有不同长度时。然而，考虑让 \(\phi(x)\) 成为一个特征向量，它计算 \(x\) 中每个长度为 \(k\) 的子串的出现次数。如果我们考虑英文字母的字符串，那么有 \(26^k\) 个这样的字符串。因此，\(\phi(x)\) 是一个 \(26^k\) 维的向量；即使对于适中的 \(k\) 值，这也可能太大，无法有效处理（例如，\(26^4 \approx 460000\)）。然而，使用（类似动态规划的）字符串匹配算法，可以有效地计算 \(K(x,z) = \phi(x)^T\phi(z)\)，这样我们就可以隐式地在这个 \(26^k\) 维特征空间中工作，但无需在此空间中显式计算特征向量。

Applications of Kernel Methods

我们已经看到了核方法在线性回归中的应用。在下一部分，我们将介绍支持向量机，核方法可以直接应用于其中。事实上，核的思想具有比线性回归和SVM更广泛的适用性。具体来说，如果你有任何学习算法，可以仅用输入属性向量之间的内积 \(\langle x, z \rangle\) 来表达，那么通过用 \(K(x, z)\) 替换这个内积（其中 \(K\) 是核），你就可以"神奇地"让你的算法在对应于 \(K\) 的高维特征空间中高效工作。例如，这个核技巧可以应用于感知器，从而推导出核感知器算法。我们将在本课程后面看到的许多算法也可以应用这种方法，这种方法已经被称为"核技巧"。