[By A.Singer] From graph to manifold Laplacians: The convergence rate.
From graph to manifold Laplacians: The convergence rate
Author: A. Singer
Appl. Comput. Harmon. Anal. 21(2006) 128--134
以下是论文的读书笔记.
1. 介绍
图拉普拉斯在机器学习中被广泛用到, 主要用于维数约减、半监督学习(semi-supervised learning)和谱聚类(spectral clustering)(参考 [3--9] 及其所列文献).
设 $\mathcal{M}\subset\mathbb{R}^m$ 是维数为 $d < m$ 的黎曼流形, 给定 $N$ 个数据点 $\{x_1, x_2, \ldots, x_N\}\subset\mathcal{M}$. 这些点被视为所在空间 $\mathbb{R}^m$ 中的向量. 任务是找到未知的底层流形 $\mathcal{M}$ 以及该流形的几何和低维表示.
谱方法的出发点是从如下所示的一个合适的半正定核(semi-positive kernel) $k$ 中抽取出一个 $N\times N$ 的权重矩阵 $W$,
\[
W_{ij}=k\Bigl(\|x_i-x_j\|^2/(2\varepsilon)\Bigr),
\]
这里 $\|\cdot\|$ 是外围空间 $\mathbb{R}^m$ 中的欧氏距离, $\varepsilon > 0$ 是核的带宽(bandwidth of the kernel). 关于核的一个流行选择是选用指数核 $k(x)=e^{-x}$, 当然选用其他核也是可以的.
加权矩阵 $W$ 被归一化为行随机矩阵，方法是将其除以对角矩阵 $D$，其对角线元素是 $W$ 相应行的行和.
\[
D=(D_{ij})_{N\times N},\quad D_{ij}=0, \text{若}\ i\neq j;\quad D_{ii}=\sum_{j=1}^{N}W_{ij}.
\]
并且（负）图拉普拉斯((negative defined) graph Laplacian) $L$ 定义如下:
\[
L=D^{-1}W-I,
\]
其中 $I$ 是 $N\times N$ 单位阵.
当数据点 $\{x_i\}_{i=1}^{N}$ 在流形 $\mathcal{M}$ 上是独立一致分布的(independently uniformly distributed), 图拉普拉斯收敛到流形上的连续 Laplace-Beltrami 算子 $\Delta_M$. 这种说法有两种表现形式. 首先, 若 $f:\mathcal{M}\rightarrow\mathbb{R}$ 是一光滑函数, 则关于偏差项(bias term)的以下结果已经由不同的作者([1, 5, 6] 等)建立.
\[
\frac{1}{\varepsilon}\lim_{N\rightarrow\infty}\sum_{j=1}^{N}L_{ij}f(x_j)=\frac{1}{2}\Delta_M f(x_i)+O(\varepsilon^{1/2}).\tag{1.4}
\]
其次, Hein 等[1] 建立了关于 $N$ 和 $\varepsilon$(方差项, the variance term)误差的一致估计, 即当 $N\rightarrow\infty$ 时按 $\frac{1}{\sqrt{N}}$ 递减; 但当 $\varepsilon\rightarrow 0$ 时以 $\frac{1}{\varepsilon^{1+d/4}}$ 递增,
\[
\frac{1}{\varepsilon}\sum_{j=1}^{N}L_{ij}f(x_j)=\frac{1}{2}\Delta_M f(x_i)+O\biggl(\frac{1}{N^{1/2}\varepsilon^{1+d/4}},\varepsilon^{1/2}\biggr).\tag{1.5}
\]
Footnote: 这里记号 $O(\cdot,\cdot)$ 意思是存在(不依赖于 $N$ 和 $\varepsilon$ 的)正常数 $C_1$, $C_2$, 使得
\[
\Biggl|O\biggl(\frac{1}{N^{1/2}\varepsilon^{1+d/4}},\varepsilon^{1/2}\biggr)\Biggr|\leqslant C_1\frac{1}{N^{1/2}\varepsilon^{1+d/4}}+C_2\varepsilon^{1/2},
\]
对充分大的 $N$ 和足够小的 $\varepsilon$ 成立.
在实际中, 我们不能取非常小的 $\varepsilon$, 即使较小的 $\varepsilon$ 可以减少偏差错误(bias error) (1.4), 因为 $\frac{1}{N^{1/2}\varepsilon^{1+d/4}}$ 关于 $\varepsilon$ 发散. 据 [1] 推测，收敛率(convergence rate) $\frac{1}{N^{1/2}\varepsilon^{1+d/4}}$ 不太可能被提高, 因为在非参数回归(nonparametric regression)中估计二阶导数的速率是相同的.
本文我们证明方差错误(variance error)为 $O(\frac{1}{N^{1/2}\varepsilon^{1/2+d/4}}$, 这对于 (1.5) 中的收敛率来说提高了一个渐近因子 $\sqrt{\varepsilon}$. 此改进源于观察到噪声项 $Wf$ 和 $Df$ 高度相关, 相关系数(correlation coefficient)是 $1-O(\varepsilon)$. 在 $\nabla_M f=0$ 的点收敛率会更快. 并且, 我们通过一个对称参数将偏差细化为 $O(\varepsilon)$ 而非 $O(\varepsilon^{1/2})$. 最后, 将两个误差项作平衡导出 $\varepsilon$ 的一个自然的优化选择,
\[
\varepsilon=\frac{C(\mathcal{M})}{N^{1/(3+d/2)}},
\]
这给出了连续 Laplace-Beltrami 和离散的图 Laplacian 逼近之间的一个最小误差.
常数 $C(\mathcal{M})$ 是关于流形 $\mathcal{M}$ 的一个函数, 其取决于该流形的几何、维数、曲率和体积, 但独立于样本点的数量 $N$. 方差估计(variance error)取决于流形的内在维数及其体积, 它可以用 $O(1/N)$ 的精度作估计[11], 而不是 $O(1/\sqrt{N})$. 然而, 偏差估计(bias error)依赖于流形的局部曲率, 而这并不知道(which is unknown in advance). 因此, 在处理现实生活中的应用程序时, 仍然需要使用一些试错实验, 以便为给定的 $N$ 找到最佳的 $\varepsilon$, 因为 $C(\mathcal{M})$ 是未知的. 当引入一个不同的 $N$, 参数 $\varepsilon$ 可根据 (1.6) 来选取.
我们的结论总结如下:
\[
\frac{1}{\varepsilon}\sum_{j=1}^{N}L_{ij}f(x_j)=\frac{1}{2}\Delta_M f(x_i)+O\biggl(\frac{1}{N^{1/2}\varepsilon^{1/2+d/4}},\varepsilon\biggr).\tag{1.7}
\]
关键字: 图拉普拉斯(Graph Laplacians)
相关阅读
(11条消息) 一文读懂 Bias（偏差）、Error（误差）、Variance（方差）_bias偏差_Suprit的博客-CSDN博客