Representor Theorem and Kernels

本文严格建模了一般监督学习，并由此引出了（机器学习中）表示定理的严格定义。接下来本文从再生核希尔伯特空间的角度介绍了核技巧，最后给出了 Mercer's Theorem 。

一般监督学习

• 为了引入表示定理这一强大的工具，我们先要建模一般¹的监督学习框架。考虑：

  • 【定义 1. General Supervised Learning】假设数据集为 ，其中 为数据空间 中的数据点，标注 。我们希望建立某个模型 ，使其对于任意的数据点 预测其标签 。具体方式服从：

    1. 限定模型假设 落在一定的赋范函数空间 中。

    2. 选择某一损失函数 与不减的正则化函数 ，以构建优化目标： 其中 为 上的范数。

    3. 令上述问题的最优解 作为最终的模型假设 。

  容易验证，先前介绍的线性回归、逻辑回归等问题都是符合该框架的。

Reproducing Kernel Hilbert Space

• 为了得到理论上好的结果，我们需要对以上的框架提一些要求。首先便是函数空间 必须是再生核希尔伯特空间（RKHS）。尽管本文的重点并不是数学基础，为了清晰的脉络我们还是要简要的介绍这一套理论。

  • 【定义 2. Hilbert Space】希尔伯特空间 可以看作对于欧式空间的扩展，具体的，我们要求：
    1. 是一个线性空间。
    2. 上可以定义内积 ，并由内积定义范数 。具体的，内积要服从对称性、线性性与正定性。对于 ，范数 定义为 。
    3. 是完备的。即对于 上任一柯西列，其收敛于 上一点。

  在此基础上进一步要求再生核性质：

  • 【定义 3. RKHS】对于集合 与 RKHS 使得 为 的全体函数的子集。若 ，存在函数 使得 有 ，则称 为再生核希尔伯特空间，该性质称再现性。

  • Remark. 再生核是一个很有趣的名字。这里并不打算详细的介绍 RKHS 的性质，这一方面是出于节约篇幅，另一方面也是因为作者的数学基础不好。不过我猜“再生核”指的可能是从函数空间 本身通过内积进行求值操作，而不依赖于 ，即 。

  RKHS 有一些很有趣的性质。由于 本身就是 的函数，有： 因此，若将 视作 的函数，则 应满足对称性和正定性。更严格的说法是，对于 的任意子集 ，若矩阵 都是半正定的，则称 为正定核。

Representer Theorem

• 表示定理在数学上应有更强的形式，但在这里我们主要关注可以被用于监督学习的表达。²

  • 【定理 1. Representer Theorem】对于 RKHS 与其再生核 ，以及任何服从框架【定义 1. General Supervised Learning】的监督学习模型，式 的最优解 必然可以被写成数据点的再生核的线性组合，即对于 有：

  证明：[Admitted]

  • Remark. 在机器学习中，以上定理说的意思基本上是，将优化目标中的 直接写成数据点的再生核的线性组合并不会丢失最优性。另一方面，这样做也更利于参数化，即只需考虑对 个参数的线性函数做优化。

A Simplified Version

• 这部分是 CS229 的 Lecture Notes 里面讲的东西，不过我觉得比较平凡，暂时不写了。

Kernel Trick

• 根据以上的讨论，要优化给定数据集的目标函数，可以做参数化： 从而得到： 这个形式里只涉及到再生核的内积计算。在实际应用中，RKHS 本身的维度可能很高（甚至无穷），所以表示 是一件很难的事。但所幸我们只需要快速计算再生核的内积就够了，这种思想就被称作核方法。常见的核包括多项式核和高斯核，而后者的 RKHS 的维度是无穷的，并且具备通用逼近（Universal Approximate）性质。

• 以上，我们可以看出监督学习框架加上核方法是一个非常强大的工具，其给出了在复杂的 RKHS 中最优化给定数据集的经验风险时的有效方式。另一方面，注意到给定参数 时， 实际上是 RKHS 中的线性函数，这就是说对 RKHS 中的函数做优化等价于训练 RKHS 上的线性模型。这是一个令人非常震惊的结论，证明了“在高维特征空间中做线性拟合”这一看似简单的思路的意外优越性。

• 既然核方法的表达能力是如此强大，我们好奇为什么其被新兴的深度学习全面击败。我猜最可能的原因是，虽然我们可以通过选择非常复杂的 RKHS 来让模型具备（理论上）极强的拟合能力，但是我们很难得到充分大的数据集，使其充分的刻画了极高维的空间，³这导致最终模型学习到的分布是不够好的。体现到表达式上就是可以用于线性组合的再生核项数随数据规模线性增加，所以我们需要足够的数据量才可以充分的利用高维信息。

A Simplified Interpretation

• 以上的表示定理揭示了一个非常深刻的观点：使用核函数将数据投射到高维 RKHS 中，再考虑 中由核函数内积的线性组合所表达的线性函数，其利用了 全部的最优性。大部分基础的文献并不会从这样高的观点解读，而将其简单的视作通过特征函数（此处对应再生核 ）将数据点投射到高维空间 中，然后在 中建立线性模型的方法。此时 中的线性分类边界投影到 上是非线性的，从而可以拟合更复杂的分布。

• 以下我们将以多项式核为例，比较这两种解读。对于 ，定义核 为： 对于 ，记 为 的各维之和。对于 ，定义 为： 对于 ，记 为多项式系数： 对于 ，记 为多项式系数： 那么进一步得到： 将其视作两个 中服从形式： 的 维向量内积，我们就说通过特征函数 可以将数据空间 投射到高维空间 中，这样便可以通过优化 中的线性模型来得到 中的非线性模型。

  若更进一步，按照表示定理的假设，应有 ，因此定义再生核： 这是一个具备 项的多元多项式函数 。构造希尔伯特空间 为： 其包含所有次数不超过 的 元多项式。对于任意： 定义其内积为： 容易验证其符合内积的性质，这基本是将 看作 维向量空间。验证再现性： 这说明如上定义的核 是希尔伯特空间 的再生核。那么按照表示定理，对数据点的再生核的线性组合做优化便利用了 RKHS 中所有函数的最优性。

  以上，通过朴素的“映射到高维空间中建立线性模型”的观点便可以看出 Kernel Trick 直觉上的好处；而通过 RKHS 和表示定理，我们则可以定量的刻画特定核的能力。

Mercer's Theorem

• 以上我们将再生核 视作希尔伯特空间 的派生，从理论上讲这样推理是自然且正确的。然而有时我们希望设计新的核函数 ，此时直接寻找 RKHS 可能是困难的。我们希望直接验证 的正确性，这由 Mercer's Theorem 保障。⁴

  • 【定理 2. Mercer's Theorem】对于对称且连续的核函数 ，若 是正定的，即对于 的任意子集 ，矩阵 都是半正定的，则存在 RKHS 使得 恰为 的再生核。

  证明：[Admitted]

  • Remark. 容易看出对称、连续且正定是再生核的充分必要条件。

---

1. 我们尽量做到一般，但可能还是有“更一般”的模式的。↩︎

2. 即便如此，不同文献中的表示定理常常有不同的叙述，本文给出的表示定理也不是最强的。↩︎

3. 如果我们希望数据点可以尽量均匀的填满 维空间，可以想象需要的数据点是关于 的指数级别。↩︎

4. 这里的表述也不是最强的。说到底此处的叙述是为机器学习的理论建立服务的，最为严格的定理叙述和证明估计要到泛函分析的教材上找。↩︎