GZ Cloudhome Logo

再生核希尔伯特空间

发布于：2023 年 6 月 9 日
更新于：2024 年 1 月 16 日 at 11:42

我最近的研究兴趣包括再生核希尔伯特空间（Reproducing Kernel Hilbert Space，RKHS），花了一些时间学习这方面的相关知识，这篇文章算是对我的理解的一个回顾。

RKHS 的定义

正式地讲，一个定义在非空集合 X\mathcal{X} 上的 RKHS HK\mathcal{H}_K 是一个希尔伯特空间。此外，它的所有的逐点求值泛函（point-wise evaluator）Fx:f↦f(x)F_x: f \mapsto f(x) 是线性且有界的。这意味着 ∀x∈X\forall x \in \mathcal{X}，存在 Cx<∞C_x < \infty，使得

∣f(x)∣≤Cx∥f∥HK,    ∀f∈HK.\big| f(x) \big| \le C_x \| f \|_{\mathcal{H}_K}, ~~~~ \forall f \in \mathcal{H}_K.

RKHS 和核函数的关系

从 RKHS 到核函数

前面讲述的 RKHS 的定义似乎和核函数没有关系，那么 RKHS 中的“再生核”又是什么意思呢？很快我们就会发现，RKHS 和正定核函数有着密切的关系。事实上，基于 Riesz Representation Theorem，对于一个希尔伯特空间 H\mathcal{H}，一个泛函 L:H→RL: \mathcal{H} \rightarrow \mathbb{R} 是线性且有界的，当且仅当存在一个唯一的 η∈H\eta \in \mathcal{H}，使得

⟨η,f⟩H=L[f].\langle \eta, f \rangle_\mathcal{H} = L[f].

把 Riesz Representation Theorem 和 RKHS 的定义联系起来，不难发现，一个 RKHS 的所有逐点求值泛函 FxF_x 都有他们自己的 representer ηx∈H\eta_x \in \mathcal{H}，使得

⟨ηx,f⟩HK=Fx[f]=f(x),\langle \eta_x, f \rangle_{\mathcal{H}_K} = F_x[f] = f(x),

而这就会导出一个核函数

K(x,y)=⟨ηx,ηy⟩HK.K(x, y) = \langle \eta_x, \eta_y \rangle_{\mathcal{H}_K}.

因此，我们还有核片段（kernel section）Kx=ηx,∀x∈XK_x = \eta_x, \forall x \in \mathcal{X}，以及

⟨Kx,f⟩HK=f(x),\langle K_x, f \rangle_{\mathcal{H}_K} = f(x),

这就是 RKHS 的再生性质。

从核函数到 RKHS

反过来，任何一个正定核函数都可以导出一个 RKHS。我们有下面的定理：

对于一个定义在一个紧凑的度量空间 X\mathcal{X} 上的 Mercer 核函数 K(x,y)K(x, y)，存在一个唯一的 RKHS HK\mathcal{H}_K，满足

  1. 所有的核片段都属于 HK\mathcal{H}_K；
  2. 具有再生性质

对应的 RKHS HK\mathcal{H}_K 可以是所有核片段所张成的线性空间的完备空间：

HK=span({Kx}x∈X)‾.\mathcal{H}_K = \overline{\mathrm{span}(\{ K_x \}_{x \in \mathcal{X}})}.

在这个 RKHS HK\mathcal{H}_K 中，假设 f∈HK=∑i=1pciKxi,g∈HK=∑i=1qdiKyif \in \mathcal{H}_K = \sum_{i=1}^p c_i K_{x_i}, g \in \mathcal{H}_K = \sum_{i=1}^q d_i K_{y_i} (pp 或者 qq 可以是无穷)，内积定义为

⟨f,g⟩HK=∑i=1p∑j=1qcidjK(xi,yj).\langle f, g \rangle_{\mathcal{H}_K} = \sum_{i=1}^p \sum_{j=1}^q c_i d_j K(x_i, y_j).

RKHS 的频谱表示

给定核函数 KK，我们可以定义一个线性算子 LKL_K：

LK[f](x)=∫XK(x,y)f(y) dμ(y).L_K [f] (x) = \int_{\mathcal{X}} K(x, y) f(y) ~ \mathrm{d} \mu(y).

这里，μ\mu 是 X\mathcal{X} 的一个 σ\sigma-finite 且非退化的测度。对于空间 L2μ\mathcal{L}_2^\mu，内积定义为

⟨f,g⟩L2μ=∫Xf(x)g(x) dμ(x).\langle f, g \rangle_{\mathcal{L}_2^\mu} = \int_{\mathcal{X}} f(x) g(x) ~ \mathrm{d} \mu(x).

因此， LKL_K 可以表示为

LK[f](x)=⟨Kx,f⟩L2μ.L_K [f] (x) = \langle K_x, f \rangle_{\mathcal{L}_2^\mu}.

这里需要注意 LKL_K 不是一个泛函。相反，它的输入是一个函数，输出仍然是一个函数。

基于 Mercer Theorem，给定一个紧凑度量空间 X\mathcal{X} 和一个非退化且 σ\sigma-finite Borel 测度 μ\mu，令 KK 是一个 Mercer 核函数，定义在 X×X\mathcal{X} \times \mathcal{X}。那么，存在一个 L2μ\mathcal{L}_2^\mu 的完整的单位正交基，他们可以由可数的连续函数 {ρi}i∈J\{\rho_i\}_{i \in \mathcal{J}} 来表示，满足

LK[ρi]=ζiρi,L_K[\rho_i] = \zeta_i \rho_i,

其中，i∈Ji \in \mathcal{J} 且 ζ1≥ζ2≥⋯≥0\zeta_1 \ge \zeta_2 \ge \dots \ge 0.

若 KK 是严格正定的，ζi>0\zeta_i > 0；如果特征值的个数是无限的，lim⁡n→∞ζi=0\lim_{n \rightarrow \infty} \zeta_i = 0。

那么，核函数就可以表示为

K(x,y)=∑i∈Jζiρi(x)ρi(y).K(x, y) = \sum_{i \in \mathcal{J}} \zeta_i \rho_i(x) \rho_i(y).

这可以由下面的式子推出：

LK[ρi](x)=⟨Kx,ρi⟩L2μ=ζiρi(x),L_K [\rho_i] (x) = \langle K_x, \rho_i \rangle_{\mathcal{L}_2^\mu} = \zeta_i \rho_i (x),

因此

K(x,y)=Kx(y)=∑i∈Jζiρi(x)ρi(y).K(x, y) = K_x(y) = \sum_{i \in \mathcal{J}} \zeta_i \rho_i(x) \rho_i(y).

到此，我们就可以把基于核函数 KK 的 RKHS HK\mathcal{H}_K 表示为

HK={f ∣ f(x)=∑i∈Jciρi(x),  s.t.  ∑i∈Jci2ζi<∞}.\mathcal{H}_K = \left\{ f ~ \Bigg| ~ f(x) = \sum_{i \in \mathcal{J}} c_i \rho_i(x), ~~ \mathrm{s.t.} ~~ \sum_{i \in \mathcal{J}} \frac{c_i^2}{\zeta_i} < \infty \right\}.

如果 f=∑i∈Jciρif = \sum_{i \in \mathcal{J}} c_i \rho_i， g=∑i∈Jdiρig = \sum_{i \in \mathcal{J}} d_i \rho_i，那么

⟨f,g⟩HK=∑i∈Jcidiζi.\langle f, g \rangle_{\mathcal{H}_K} = \sum_{i \in \mathcal{J}} \frac{c_i d_i}{\zeta_i}.

因此我们可以看到，ζiρi\sqrt{\zeta_i} \rho_i 可以看作是 HK\mathcal{H}_K 的单位正交基。

有趣的是，L2μL_2^\mu 和 HK\mathcal{H}_K 之间存在同构映射。基于测度 μ\mu 的平方可积函数空间可以表示为

L2μ={f ∣ f(x)=∑i∈Jciρi(x),  s.t.  ∑i∈Jci2<∞}.\mathcal{L}_2^\mu = \left\{ f ~ \Bigg| ~ f(x) = \sum_{i \in \mathcal{J}} c_i \rho_i(x), ~~ \mathrm{s.t.} ~~ \sum_{i \in \mathcal{J}} c_i^2 < \infty \right\}.

我们定义 LK1/2L_K^{1/2} 为

LK1/2[ρi]=ζiρi,L_K^{1/2} [\rho_i] = \sqrt{\zeta_i} \rho_i,

对于 f=∑i∈Jciρif = \sum_{i \in \mathcal{J}} c_i \rho_i，若 f∈L2μf \in \mathcal{L}_2^\mu，我们有 ∑i∈Jci2<∞\sum_{i \in \mathcal{J}} c_i^2 < \infty。那么 LK1/2[f]=∑i∈JζiciρiL_K^{1/2} [f] = \sum_{i \in \mathcal{J}} \sqrt{\zeta_i} c_i \rho_i， 显然 ∑i∈J(ζici)2ζi=∑i∈Jci2<∞\sum_{i \in \mathcal{J}} \frac{(\sqrt{\zeta_i}c_i)^2}{\zeta_i} = \sum_{i \in \mathcal{J}} c_i^2 < \infty。因此 LK1/2f∈HKL_K^{1/2} f \in \mathcal{H}_K。这个映射也是一个双射。

我们也能得出，LK1/2L_K^{1/2} 保持内积：

⟨f,g⟩L2μ=⟨LK1/2f,LK1/2g⟩HK.\langle f, g \rangle_{\mathcal{L}_2^\mu} = \langle L_K^{1/2} f, L_K^{1/2} g \rangle_{\mathcal{H}_K}.

因此，我们说 LK1/2L_K^{1/2} 是 L2μ\mathcal{L}_2^\mu 到 HK\mathcal{H}_K 的同构映射。

表示定理

一般形式

给定希尔伯特空间 H\mathcal{H} （注意这不一定是 RKHS）以及下面的优化问题

arg⁡min⁡f∈HΦ(L1[f],L2[f],…,LN[f],∥f∥H),\begin{align*} \underset{f \in \mathcal{H}}{\arg \min} && \Phi(L_1 [f], L_2[f], \dots, L_N[f], \| f \|_\mathcal{H}), \end{align*}

其中

  1. 每个 Li:H→RL_i: \mathcal{H} \rightarrow \mathbb{R} 是线性且有界的；
  2. 目标函数 Φ\Phi 关于最后一个参数 ∥f∥H\| f \|_\mathcal{H} 是严格递增的；
  3. 优化问题至少有一个解。

这个优化问题的解可以表示为如下形式，

f∗=∑i=1Nαiηi,f^* = \sum_{i=1}^N \alpha_i \eta_i,

其中 ηi\eta_i 是泛函 LiL_i 的 representer。

RKHS 情况

若 H\mathcal{H} 是一个核函数 KK 诱导的 RKHS HK\mathcal{H}_K，LiL_i 的 representer 则为

ηi(x)=⟨ηi,Kx⟩HK=Li[Kx].\eta_i (x) = \langle \eta_i, K_x \rangle_{\mathcal{H}_K} = L_i[K_x].

更具体地，如果 LiL_i 是逐点求值泛函，xi∈Xx_i \in \mathcal{X}，那么优化问题为

arg⁡min⁡f∈HΦ(f(x1),f(x2),…,f(xN),∥f∥H),\begin{align*} \underset{f \in \mathcal{H}}{\arg \min} && \Phi(f(x_1), f(x_2), \dots, f(x_N), \| f \|_\mathcal{H}), \end{align*}

此时 KxiK_{x_i} 即为 LiL_i 的 representer，那么

f∗=∑i=1NαiKxi.f^* = \sum_{i=1}^N \alpha_i K_{x_i}.

这即表示定理在 RKHS 情形下的形式。

在机器学习中的应用

表示定理在机器学习中非常有用。给定一个损失函数，我们可以在这个损失函数上添加约束项，得到约束的目标函数

Obj=1N∑i=1Nl(yi,f(xi))+γ∥f∥HK2,\mathrm{Obj} = \frac{1}{N} \sum_{i=1}^N l(y_i, f(x_i)) + \gamma \| f \|_{\mathcal{H}_K}^2,

对其的优化即为一般的表示定理的一个特殊情形。

核函数隐含的特征空间

我们可以把 HK\mathcal{H}_K 当作 KK 隐含诱导的特征空间，其特征映射为 ϕ:x↦Kx\phi: x \mapsto K_x。在这个新特征空间中，

⟨ϕ(x),ϕ(y)⟩HK=⟨Kx,Ky⟩HK=K(x,y).\langle \phi(x), \phi(y) \rangle_{\mathcal{H}_K} = \langle K_x, K_y \rangle_{\mathcal{H}_K} = K(x, y).

我们将要在这个新的特征空间 HK\mathcal{H}_K 中找到一个元素 ff，使得在这个空间的“线性函数”能给我们最小的目标函数值，

min⁡f∈HK 1N∑i=1Nl(f(xi),yi)+∥f∥HK2=min⁡f∈HK 1N∑i=1Nl(⟨f,Kxi⟩HK,yi)+⟨f,f⟩HK,\begin{align*} & \underset{f \in \mathcal{H}_K}{\min} ~ \frac{1}{N} \sum_{i=1}^N l(f(x_i), y_i) + \| f \|^2_{\mathcal{H}_K} \\ =& \underset{f \in \mathcal{H}_K}{\min} ~ \frac{1}{N} \sum_{i=1}^N l(\langle f, K_{x_i} \rangle_{\mathcal{H}_K}, y_i) + \langle f, f \rangle_{\mathcal{H}_K}, \end{align*}

这正是我们在常见的欧氏空间中的岭回归——找到元素 β\beta，然后预测函数就可以表示为 βTx=⟨β,x⟩\beta^T x = \langle \beta, x \rangle。

值得一提的是，直观上分析，由于 ∥β∥HK2\| \beta \|^2_{\mathcal{H}_K} 约束项的存在以及高维空间的线性回归预测值 ⟨β,Kxi⟩\langle \beta, K_{x_i} \rangle 不受 β\beta 中垂直于 {Kxi}i=1N\big\{ K_{x_i} \big\}_{i=1}^N 的部分的影响，我们最终优化得到的最优 β\beta 只能是各个 KxiK_{x_i} 线性组合后的结果。这其实也是证明前文中的 表示定理 的思路。

常见核函数

常见的核函数包括

径向基核函数

径向基核函数的形式为

K(x,y)=exp⁡(−∥x−y∥22σ2).K(x, y) = \exp \left( -\frac{\| x - y \|^2}{2 \sigma^2} \right).

或者，另外一个常称作“Gaussian kernel”的形式，

K(x,y)=exp⁡(−∥x−y∥2ρ),K(x, y) = \exp \left( - \frac{\| x - y \|^2}{\rho} \right),

其中 ρ>0\rho > 0。高斯核是一种具有平移不变性的核函数。高斯核诱导的范数 ∥⋅∥HK\| \cdot \|_{\mathcal{H}_K}，随着 pp 的增大而越来越约束 RKHS 中的函数。我们可以这样想象——随着 pp 的增大，不同的核片段的区别将会变得更小，因此 K(x,y)K(x, y) 的特征值会变得更小，导致更大的范数值。

假设 f=∑i=1pαiKxif = \sum_{i=1}^p \alpha_i K_{x_i}。那么

∥f∥HK2=αTKα=fTK−1f.\| f \|^2_{\mathcal{H}_K} = \boldsymbol{\alpha}^T \mathbf{K} \boldsymbol{\alpha} = \boldsymbol{f}^T \mathbf{K}^{-1} \boldsymbol{f}.

从频谱的角度来看，

∥f∥HK2=∑i∈Jci2ζi.\| f \|^2_{\mathcal{H}_K} = \sum_{i \in \mathcal{J}} \frac{c_i^2}{\zeta_i}.

随着 ζi\zeta_i 的减小，∥f∥HK2\| f \|^2_{\mathcal{H}_K} 将会变得越来越大。

因此，对于一个固定的 f\boldsymbol{f}，我们有

ρ→∞⇒∥f∥HK→∞.\rho \rightarrow \infty \Rightarrow \| f \|_{\mathcal{H}_K} \rightarrow \infty.