Kernel Methods

Feature Maps

Considering fitting cubic functions $y={\theta }_3{x}^3+{\theta }_2{x}^2+{\theta }_{1}x+{\theta }_0$, we can view the cubic function as a linear function over a different set of feature variables. Concretely, let the function $\varphi :\mathbb{R}\to {\mathbb{R}}^4$ be defined as

$$\varphi (x)=\left(\begin{array}{c}1\\ x\\ x^2\\ x^3\end{array}\right)\in {\mathbb{R}}^4$$

Let $\theta \in {\mathbb{R}}^4$ be the vector containing ${\theta }_0,\dots ,{\theta }_3$ as entries. Then we can rewrite the cubic function in $x$ as

$$y={\theta }^T\varphi (x)$$

Thus, a cubic function of the variable $x$ can be viewed as a linear function over the variables $\varphi (x)$. To distinguish between these two sets of variables, in the context of kernel methods, we will call the “original” input value the input attributes of a problem. When the original input is mapped to some new set of quantities $\varphi (x)$, we will call those new quantities the features variables. We will can $\varphi$ a feature map, which maps the attributes to the features.

LMS with the kernel trick

The update rule of Least Squares Method in linear case is

$$\theta \leftarrow \theta +\alpha \sum _{i=1}^n\left(y^{(i)}-{\theta }^T{x}^{(i)}\right)x^{(i)}$$

If we use a feature map function $\varphi (x)$

$$\theta \leftarrow \theta +\alpha \sum _{i=1}^n\left(y^{(i)}-{\theta }^T\varphi (x^{(i)})\right)\varphi (x^{(i)})$$

This update becomes computationally expensive when the features $\varphi (x)$ is high-dimensional. Let $\varphi (x)$ be the vector that contains all the monomials of $x_1,x_2,x_3$ with degree $\le d$, then the dimension of $\varphi (x)$ would be on the order of $d^3$.

It may appear at first that such $d^3$ runtime per update and memory usage are inevitable, because the vector $\theta$ itself is of dimension $p\approx d^3$, and we may need to update every entry of $\theta$ and store it. However, we will introduce the kernel trick with which we will not need to store $\theta$ explicitly, and the runtime can be significantly improved.

For simplicity, we assume the initialize the value $\theta =0$. At initialization, $\theta =0={\sum }_{i=1}^{n}0\cdot \varphi (x^{(i)})$. Assume at some point, $\theta$ can be represented as

$$\theta =\sum _{i=1}^n{\beta }_i\varphi (x^{(i)})$$

for some ${\beta }_1,\dots ,{\beta }_n\in \mathbb{R}$. Then we claim that in the next round, $\theta$ is still a linear combination of $\varphi (x^{(1)}),\dots ,\varphi (x^{(n)})$ because

$$\begin{array}{rl}\theta & :=\theta +\alpha \sum _{i=1}^n\left(y^{(i)}-{\theta }^T\varphi (x^{(i)})\right)\varphi (x^{(i)})\\ & =\sum _{i=1}^n\left({\beta }_i+\alpha y^{(i)}-\alpha {\theta }^T\varphi (x^{(i)})\right)\varphi (x^{(i)})\end{array}$$

Our general strategy is to implicitly represent the $p$-dimensional vector $\theta$ by a set of coefficients ${\beta }_1,\dots ,{\beta }_n$. Towards doing this, we derive the update rule of the coefficients ${\beta }_1,\dots ,{\beta }_n$. Using the equation above, we see that the new ${\beta }_i$ depends on the old one via

$${\beta }_i\leftarrow {\beta }_i+\alpha \left(y^{(i)}-{\theta }^T\varphi (x^{(i)})\right)$$

Here we still have the old $\theta$ on the RHS of the equation. Replacing $\theta$ by $\theta ={\sum }_{i=1}^n{\beta }_i\varphi (x^{(i)})$ gives

$$\forall i\in \left\{1,\dots ,n\right\},{\beta }_i:={\beta }_i+\alpha \left(y^{(i)}-\sum _{j=1}^n{\beta }_i\varphi (x^{(j)}{)}^T\varphi (x^{(i)})\right)$$

We often rewrite $\varphi (x^{(j)}{)}^T\varphi (x^{(i)})$ as $⟨\varphi (x^{(j)}),\varphi (x^{(i)})⟩$ to emphasize that it's the inner product of the two feature vectors. It may appear that at every iteration, we still need to compute the values of $⟨\varphi (x^{(j)}),\varphi (x^{(i)})⟩$ for all pairs of $i,j$, each of which may take roughly $O(p)$ operation. However, two important properties come to rescue:

1. We ca pre-compute the pairwise inner products $⟨\varphi (x^{(j)}),\varphi (x^{(i)})⟩$ for all pairs $i,j$ before the loop starts
2. Compute the inner product can be efficient and does not necessarily require computing $\varphi (x^{(i)})$ explicitly. This is because

$$\begin{array}{rl}⟨\varphi (x),\varphi (z)⟩& =1+\sum x_i{z}_i+\sum x_i{x}_j{z}_i{z}_j+\sum x_i{x}_j{x}_k{z}_i{z}_j{z}_k+\cdots +\\ & =1+\sum x_i{z}_i+{\left(\sum x_i{z}_i\right)}^2+{\left(\sum x_i{z}_i\right)}^3\\ & =1+⟨x,z⟩+{⟨x,z⟩}^2+{⟨x,z⟩}^3+\cdots \end{array}$$

Therefore, to compute $⟨\varphi (x),\varphi (z)⟩$, we can first compute $⟨x,z⟩$ with $O(d)$ time and then take another constant number of operations to compute $1+⟨x,z⟩+{⟨x,z⟩}^2+\cdots +$.

We define the Kernel corresponding to the feature map $\varphi$ as a function that maps $\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ satisfying:

$$K(x,z):=⟨\varphi (x),\varphi (z)⟩$$

Now we can pre-compute the values $K\left(x^{(i)},x^{(j)}\right)$, and define $K\in {\mathbb{R}}^{n\times n}$ as $K_{ij}=K\left(x^{(i)},x^{(j)}\right)$, we have the new update rule

$$\beta \leftarrow \beta +\alpha (y-K\beta )$$

Properties of Kernels

AI Summary

这段文字的核心思想是介绍机器学习中的 核方法 (Kernel Methods), 特别是 核技巧 (Kernel Trick) 的概念和动机.

1. 起点: 特征映射与核函数

   • 我们通常从一个明确的 特征映射 (feature map) $\varphi$ 开始. 这个函数将原始输入数据 $x$ 转换到一个 (可能更高维度的) 特征空间 $\varphi (x)$ .
   • 基于这个特征映射, 可以定义一个 核函数 (kernel function) $K(x,z)$ , 它计算两个原始输入 $x$ 和 $z$ 在特征空间中的 内积 (inner product): $K(x,z)\triangleq ⟨\varphi (x),\varphi (z)⟩$ . 在实数空间中, 这通常就是点积 $\varphi (x{)}^T\varphi (z)$ .

2. 核技巧 (Kernel Trick) 的关键

   • 很多机器学习算法 (比如支持向量机SVM的训练和预测过程, 实际上只需要用到特征向量之间的 内积, 而不需要特征向量 $\varphi (x)$ 本身.
   • 这意味着, 只要我们能计算核函数 $K(x,z)$ 的值, 我们就可以完全用 $K$ 来表达整个算法, 而 无需显式地计算或知道 特征映射 $\varphi$ 是什么.

3. 动机: 直接定义核函数

   • 既然算法只需要 $K$ , 那我们能不能反过来, 不先定义 $\varphi$ , 而是直接 选择或设计 一个函数 $K(x,z)$ 来用呢?
   • 这样做的好处是巨大的: 我们可能选择一些 $K$ , 它们对应的 $\varphi$ 非常复杂, 甚至是无限维的, 我们根本无法显式写出或计算 $\varphi (x)$ . 但只要我们能计算 $K(x,z)$ , 算法依然可以运行.
   • 但是, 有一个前提: 我们必须 确保 我们选择的这个 $K(x,z)$ 确实是 某个 特征映射 $\varphi$ 在特征空间中的内积. 也就是说, 必须 存在 这样一个 $\varphi$ , 即使我们不知道它是什么.

4. 问题: 什么样的函数K是有效的核函数?

   • 核心问题来了: 什么样的函数 $K(x,z)$ 可以保证存在一个特征映射 $\varphi$ 使得 $K(x,z)=⟨\varphi (x),\varphi (z)⟩$ 成立?
   • 如果能回答这个问题, 我们就可以安全地选择一个满足条件的 $K$ , 然后直接在算法中使用它, 享受核技巧带来的便利 (比如计算效率, 处理非线性问题的能力) .

5. 例子: 多项式核 (Polynomial Kernel)

   • $K(x,z)=(x^{T}z{)}^2$ : 通过展开, 发现它等于 ${\sum }_{i,j=1}^d(x_i{x}_j)(z_i{z}_j)$ . 这明确展示了它对应一个特征映射 $\varphi (x)$ , 其分量是所有 $x_i{x}_j$ 的组合. 计算 $K(x,z)$ 只需要 $O(d)$ 时间, 而计算 $\varphi (x)$ 需要 $O(d^2)$ 时间.
   • $K(x,z)=(x^{T}z+c{)}^2$ : 类似地, 展开后发现它对应的 $\varphi (x)$ 包含 $x_i{x}_j$ 项、 $\sqrt{2c}{x}_i$ 项和常数项 $c$ .
   • $K(x,z)=(x^{T}z+c{)}^k$ : 推广到 $k$ 次多项式核. 它对应的特征空间维度是 $O(d^k)$ , 但计算 $K(x,z)$ 仍然只需要 $O(d)$ 时间. 这极大地体现了核技巧的 计算效率优势.

6. 核函数的直观理解: 相似度度量

   • 从直观上看, $K(x,z)=\varphi (x{)}^T\varphi (z)$ 可以被看作是衡量 $\varphi (x)$ 和 $\varphi (z)$ 之间相似度的一种方式 (内积越大, 向量越接近或方向越一致) . 因此, $K(x,z)$ 也可以被看作是衡量原始输入 $x$ 和 $z$ 之间的一种 (通过 $\varphi$ 映射后的) 相似度.
   • 这启发我们可以基于对问题 "相似性" 的理解来设计核函数.

7. 例子: 高斯核 (Gaussian Kernel)

   • $K(x,z)=\exp \left(-\frac{||x-z|{|}^2}{2{\sigma }^2}\right)$ . 当 $x$ 和 $z$ 距离近时, $K$ 接近 1; 当距离远时, $K$ 接近 0. 这符合相似度的直观概念.
   • 文中提到, 高斯核 确实 是一个有效的核函数, 但它对应的特征映射 $\varphi$ 是 无限维 的. 这再次强调了我们无法显式使用 $\varphi$ , 而必须依赖核函数 $K$ 本身.

8. 有效核函数的必要条件

   • 假设 $K$ 是一个有效的核函数, 即 $K(x,z)=⟨\varphi (x),\varphi (z)⟩$ . 它必须满足什么性质?

   • 考虑任意 $n$ 个数据点 $\{x^{(1)},...,x^{(n)}\}$ , 构造一个 $n\times n$ 的 核矩阵 (Kernel Matrix) $K$ , 其中 $K_{ij}=K(x^{(i)},x^{(j)})$ .

   • 对称性 (Symmetry): 因为内积是对称的 $⟨u,v⟩=⟨v,u⟩$ , 所以 $K_{ij}=⟨\varphi (x^{(i)}),\varphi (x^{(j)})⟩=⟨\varphi (x^{(j)}),\varphi (x^{(i)})⟩=K_{ji}$ . 因此, 核矩阵 $K$ 必须是对称的.

   • 半正定性 (Positive Semi-Definiteness, PSD): 对于任意向量 $z\in {\mathbb{R}}^n$ , 推导表明 $z^{T}Kz={\sum }_k{\left({\sum }_i{z}_i{\varphi }_k(x^{(i)})\right)}^2\ge 0$ . 这意味着核矩阵 $K$ 必须是半正定的.

   • 结论: 如果一个函数 $K(x,z)$ 是有效的核函数, 那么对于 任何 有限点集 $\{x^{(1)},...,x^{(n)}\}$ , 由它生成的核矩阵 $K$ 必须是 对称且半正定的. 这是成为有效核函数的 必要条件.

Mercer 定理 (Mercer's Theorem) 这段材料推导了有效核函数的必要条件 (对称性和半正定性) , 但没有说明这是否也是 充分条件. Mercer 定理正是回答了这个问题的关键定理.

简单来说, Mercer 定理陈述了:

设 $\mathcal{X}$ 是一个紧凑的度量空间 (例如 ${\mathbb{R}}^d$ 中的一个有界闭集) , $K:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ 是一个连续的、对称的函数. 那么, $K$ 是一个 正定核 (positive definite kernel) (即对于任何有限点集 $\{x^{(1)},...,x^{(n)}\}\subset \mathcal{X}$ 和任何非零实数 $c_1,...,c_n$ , 都有 ${\sum }_{i=1}^n{\sum }_{j=1}^n{c}_i{c}_{j}K(x^{(i)},x^{(j)})\ge 0$ , 注意这里用的是广义的半正定概念) 当且仅当 存在一个希尔伯特空间 (Hilbert Space) $\mathcal{H}$ 和一个映射 $\varphi :\mathcal{X}\to \mathcal{H}$ , 使得对于所有的 $x,z\in \mathcal{X}$ , 都有: $K(x,z)=⟨\varphi (x),\varphi (z){⟩}_{\mathcal{H}}$ 并且 $K$ 可以展开为一致收敛的级数: $K(x,z)={\sum }_{k=1}^{\infty }{\lambda }_k{\psi }_k(x){\psi }_k(z)$ 其中 ${\lambda }_k\ge 0$ 是 $K$ 对应的积分算子的特征值, ${\psi }_k(x)$ 是对应的特征函数.

Mercer 定理的关键意义:

1. 充分性: 它告诉我们, 如果一个函数 $K(x,z)$ (在适当的条件下, 如连续、对称) 能够确保对任何数据点集产生的核矩阵都是 半正定的, 那么这个函数就 一定 是一个有效的核函数. 即, 一定存在 一个特征空间和一个映射 $\varphi$ , 使得 $K(x,z)$ 是该空间中的内积.
2. 理论保证: 这为 "核技巧" 提供了坚实的数学基础. 只要我们选择或设计的函数 $K$ 满足 Mercer 定理的条件 (主要是对称性和产生半正定核矩阵) , 我们就可以放心地在算法中使用它, 即使我们不知道 $\varphi$ 是什么.
3. 连接: 材料中推导的是 "如果 $K$ 是核函数 $⟹$ 核矩阵 $K$ 是对称半正定的" (必要性) . Mercer 定理说明了 "如果核矩阵 $K$ 总是对称半正定的 $⟹K$ 是核函数" (充分性, 在一定条件下) .

总结: 材料解释了为什么我们想直接使用核函数 $K$ 而不是特征映射 $\varphi$ (核技巧) , 并推导了有效核函数必须满足的条件 (对称性和半正定性) . Mercer 定理则提供了判别一个函数是否为有效核函数的 充分条件, 即检查它生成的核矩阵是否总是半正定的. 这使得我们可以直接设计和使用满足条件的核函数, 极大地扩展了线性算法 (通过隐式映射到高维空间) 处理非线性问题的能力.