让人惊叹的Johnson-Lindenstrauss引理:理论篇
By 苏剑林 | 2021-09-17 | 83660位读者 |今天我们来学习Johnson-Lindenstrauss引理,由于名字比较长,下面都简称“JL引理”。
个人认为,JL引理是每一个计算机科学的同学都必须了解的神奇结论之一,它是一个关于降维的著名的结果,它也是高维空间中众多反直觉的“维度灾难”现象的经典例子之一。可以说,JL引理是机器学习中各种降维、Hash等技术的理论基础,此外,在现代机器学习中,JL引理也为我们理解、调试模型维度等相关参数提供了重要的理论支撑。
对数的维度 #
JL引理,可以非常通俗地表达为:
通俗版JL引理: 塞下$N$个向量,只需要$\mathcal{O}(\log N)$维空间。
具体来说,JL引理说的是,不管这$N$个向量原来是多少维的,我们都可以将它们降到$\mathcal{O}(\log N)$,并将相对距离的误差控制在一定范围内。可以想象,这是一个非常强、非常反直觉、非常实用的结论,比如我们要做向量检索,原本的向量维度可能非常大,这样全量检索一次的成本也非常大,而JL引理告诉我们,可以将它们变换到$\mathcal{O}(\log N)$维,并且检索效果近似不变,这简直就是“天上掉馅饼”的好事!
可能读者会有疑问:这么强的结论,那么对应的降维方法会不会特别复杂?答案是刚刚相反,降维过程仅仅用到随机线性投影!甚至有评价说,JL引理是一个“证明比理解更容易的结论”,也就是说,从数学上证明它还真不算特别困难,但如何直观地理解这个反直觉的结论,反而是不那么容易的。
无独有偶,我们之前其实就介绍过两个反直觉的结果:在文章《n维空间下两个随机向量的夹角分布》中,我们就介绍过“高维空间中任意两个向量几乎都是垂直的”,这显然与二维、三维空间的结果差距甚远;在文章《从几何视角来理解模型参数的初始化策略》中,这个结果进一步升级为“从$\mathcal{N}(0,1/n)$采样出来的$n\times n$矩阵几乎是一个正交矩阵”,这更与我们一直理解的“正交性是非常苛刻的(要求转置等于逆)”有严重出入。
但事实上,这两个结论不仅对,而且还跟JL引理直接相关。可以说,JL引理可以看成是它们的细化和应用。所以,我们需要先用更定量的语言来刻画这两个结论,比如“几乎垂直”,那垂直的概率究竟有多少,比如“近似正交”,那误差究竟有多大。
概率不等式 #
为此,我们需要一些概率知识,其中最主要是“马尔可夫不等式”:
马尔可夫不等式:如果$x$是非负随机变量,$a > 0$,那么 \begin{equation}P(x\geq a)\leq \frac{\mathbb{E}[x]}{a}\end{equation}
注意该不等式并没有对$x$所服从的分布有其他特别的限制,只要求随机变量的取值空间是非负的(或者等价地,负的$x$的概率恒为0),证明其实非常简单:
\begin{equation}\mathbb{E}[x]=\int_0^{\infty}x p(x) \geq \int_a^{\infty}x p(x) \geq \int_a^{\infty} a p(x) = a P(x\geq a)\end{equation}
马尔可夫不等式要求随机变量是非负的,但我们平时要处理的随机变量不一定是非负的,所以通常需要变换一下才能用。比如$x - \mathbb{E}[x]$不是非负的,但$|x - \mathbb{E}[x]|$是非负的,于是利用马尔可夫不等式有:
\begin{equation}P(|x - \mathbb{E}[x]|\geq a) = P((x - \mathbb{E}[x])^2\geq a^2) \leq \frac{\mathbb{E}[(x - \mathbb{E}[x])^2]}{a^2}=\frac{\mathbb{V}ar[x]}{a^2}\end{equation}
这就是“切比雪夫不等式”。
另外一个经典技巧称为“Cramér-Chernoff方法”,也是我们后面主要利用到的方法,它通过指数函数将随机变量变成非负的:对于任意$\lambda > 0$,我们有
\begin{equation}x \geq a \quad\Leftrightarrow\quad \lambda x \geq \lambda a \quad\Leftrightarrow\quad e^{\lambda x} \geq e^{\lambda a}\end{equation}
所以利用马尔可夫不等式有
\begin{equation}P(x \geq a) = P(e^{\lambda x} \geq e^{\lambda a})\leq e^{-\lambda a}\mathbb{E}[e^{\lambda x}]\end{equation}
最左端是跟$\lambda$无关的,但是最右端有一个$\lambda$,而这不等式是对于任意$\lambda > 0$都成立的。所以理论上,我们可以找到使得最右端最小的$\lambda$,以获得最高的估计精度:
\begin{equation}P(x \geq a) \leq \min_{\lambda > 0} e^{-\lambda a}\mathbb{E}[e^{\lambda x}]\end{equation}
引理的引理 #
现在,我们可以引入如下结果,它是JL引理的引理,甚至可以说,它是本文一切结论的理论基础:
单位模引理: 设$u\in\mathbb{R}^{n}$是独立重复采样自$\mathcal{N}(0,1/n)$的向量,$\varepsilon \in (0, 1)$是给定常数,那么我们有 \begin{equation}P(|\Vert u\Vert^2 - 1| \geq \varepsilon) \leq 2\exp\left(-\frac{\varepsilon^2 n}{8}\right)\end{equation}
该引理告诉我们,当$n$足够大的时候,$u$的模长明显偏离1的概率是非常小的(给定$\varepsilon$后,将以$n$的指数形式递减至0),所以从$\mathcal{N}(0,1/n)$采样出来的$n$维向量将会非常接近单位向量。
它的证明正是用到“Cramér-Chernoff方法”:首先$|\Vert u\Vert^2 - 1| \geq \varepsilon$意味着$\Vert u\Vert^2 - 1 \geq \varepsilon$或$1 - \Vert u\Vert^2\geq \varepsilon$,我们需要分别进行推导,不失一般性,先推导$\Vert u\Vert^2 - 1 \geq \varepsilon$的概率,根据Cramér-Chernoff方法,有
\begin{equation}P(\Vert u\Vert^2 - 1 \geq \varepsilon) \leq \min_{\lambda > 0} e^{-\lambda \varepsilon}\mathbb{E}\big[e^{\lambda (\Vert u\Vert^2 - 1)}\big] = \min_{\lambda > 0} e^{-\lambda (\varepsilon + 1)}\mathbb{E}\big[e^{\lambda \Vert u\Vert^2}\big]\end{equation}
将$u$写成分量形式$(u_1, u_2, \cdots, u_n)$,其中每个分量都是独立的,分布均为$\mathcal{N}(0,1/n)$,那么我们有
\begin{equation}\mathbb{E}\big[e^{\lambda \Vert u\Vert^2}\big] = \mathbb{E}\big[e^{\lambda\sum\limits_i u_i^2}\big] = \mathbb{E}\big[\prod_i e^{\lambda u_i^2}\big]=\prod_i \mathbb{E}\big[ e^{\lambda u_i^2}\big]\end{equation}
而$\mathbb{E}\big[ e^{\lambda u_i^2}\big]=\int_{-\infty}^{\infty} \frac{1}{\sqrt{2\pi}}e^{-u_i^2/2}e^{\lambda u_i^2/n} du_i=\sqrt{n/(n-2\lambda)}$,所以
\begin{equation}P(\Vert u\Vert^2 - 1 \geq \varepsilon) \leq \min_{\lambda > 0} e^{-\lambda (\varepsilon + 1)}\left(\frac{n}{n-2\lambda}\right)^{n/2}\end{equation}
右端的极小值在$\lambda = \frac{n\varepsilon}{2(1+\varepsilon)}$取到,推导过程就留给读者了,然后代入得到
\begin{equation}P(\Vert u\Vert^2 - 1 \geq \varepsilon) \leq e^{n(\log(1+\varepsilon) - \varepsilon)/2}\leq e^{-n\varepsilon^2/8}\end{equation}
其中$\log(1+\varepsilon) - \varepsilon \leq -\varepsilon^2/4$的证明也留给读者了。类似地,我们可以对$1 - \Vert u\Vert^2\geq \varepsilon$的概率进行推导,结果为:
\begin{equation}P(1 - \Vert u\Vert^2\geq \varepsilon) \leq e^{n(\log(1-\varepsilon) + \varepsilon)/2}\leq e^{-n\varepsilon^2/8}\end{equation}
其中可证$\log(1-\varepsilon) + \varepsilon \leq \log(1+\varepsilon) - \varepsilon$,所以上式沿用了$\log(1+\varepsilon) - \varepsilon$的不等关系。现在两式相加,我们得到$P(|\Vert u\Vert^2 - 1| \geq \varepsilon)\leq 2e^{-n\varepsilon^2/8}$。证毕。
从“单位模引理”出发,我们可以证明“正交性引理”:
正交性引理: 设$u,v\in\mathbb{R}^{n}$是独立重复采样自$\mathcal{N}(0,1/n)$的两个向量,$\varepsilon \in (0, 1)$是给定常数,那么我们有 \begin{equation}P(|\langle u, v\rangle| \geq \varepsilon) \leq 4\exp\left(-\frac{\varepsilon^2 n}{8}\right)\end{equation}
该引理告诉我们,当$n$足够大的时候,$u,v$的内积明显偏离0的概率是非常小的(给定$\varepsilon$后,将以$n$的指数形式递减至0),所以从$\mathcal{N}(0,1/n)$采样出来的两个$n$维向量将会非常接近正交。而结合“单位模引理”,我们就得到“从$\mathcal{N}(0,1/n)$采样出来的$n\times n$矩阵几乎是一个正交矩阵”的结论了。
有了“单位模引理”铺垫,它的证明不算难。我们知道如果$u,v\sim \mathcal{N}(0,1/n)$,那么$\frac{u\pm v}{\sqrt{2}}\sim \mathcal{N}(0,1/n)$,所以根据“单位模引理”的证明,我们有
\begin{equation}P\left(\left\Vert \frac{u+v}{\sqrt{2}}\right\Vert^2 - 1 \geq \varepsilon\right) \leq e^{-n\varepsilon^2/8},\quad P\left(1-\left\Vert \frac{u-v}{\sqrt{2}}\right\Vert^2 \geq \varepsilon\right) \leq e^{-n\varepsilon^2/8}\end{equation}
注意$\left\Vert \frac{u+v}{\sqrt{2}}\right\Vert^2 - 1 \geq \varepsilon$和$1-\left\Vert \frac{u-v}{\sqrt{2}}\right\Vert^2 \geq \varepsilon$两式相加后可以得出$\langle u, v\rangle\geq \varepsilon$,所以
\begin{equation}P(\langle u, v\rangle\geq \varepsilon) \leq P\left(\left\Vert \frac{u+v}{\sqrt{2}}\right\Vert^2 - 1 \geq \varepsilon\right) + P\left(1-\left\Vert \frac{u-v}{\sqrt{2}}\right\Vert^2 \geq \varepsilon\right) \leq 2e^{-n\varepsilon^2/8}\end{equation}
同理可证$P(-\langle u, v\rangle\geq \varepsilon) \leq 2e^{-n\varepsilon^2/8}$,两者结合就得到“正交性引理”。
证明的过程 #
现在我们就可以着手证明JL引理了,下面是它的数学表述:
数学版JL引理: 给定$N$个向量$v_1,v_2,\cdots,v_N\in\mathbb{R}^m$和$n > \frac{24\log N}{\varepsilon^2}$,而随机矩阵$A\in\mathbb{R}^{n\times m}$独立重复采样自$\mathcal{N}(0,1/n)$,$\varepsilon \in (0, 1)$是给定常数,那么至少有$\frac{N-1}{N}$的概率,使得对于所有的$i\neq j$,都成立 \begin{equation}(1-\varepsilon)\Vert v_i - v_j\Vert^2 \leq \Vert Av_i - A v_j\Vert^2 \leq (1+\varepsilon)\Vert v_i - v_j\Vert^2\label{eq:bound}\end{equation}
引理告诉我们,不管原来的向量维数$m$是多少,只需要$n > \frac{24\log N}{\varepsilon^2}$的维度,我们就可以容纳下$N$个向量,使得它们相对距离的偏离都不超过$\varepsilon$。而且JL引理还告诉我们降维方法:只需要从$\mathcal{N}(0,1/n)$随机采样一个$n\times m$的矩阵$A$,然后变换$v\to Av$就有$\frac{N-1}{N}$的可能性达到目的。真可谓是简单实用了~
证明过程也是“单位模引理”的直接应用。首先,如果$u\in\mathbb{R}^m$是给定的单位向量,而$A\in\mathbb{R}^{n\times m}$独立重复采样自$\mathcal{N}(0,1/n)$,那么$Au$的每个分量都独立地服从$\mathcal{N}(0,1/n)$。证明也并不难,根据定义每个分量$(Au)_i = \sum\limits_j A_{i,j}u_j$,由于$A_{i,j}$相互独立,所以$(Au)_i$显然相互独立,并且由于$A_{i,j}\sim\mathcal{N}(0,1/n)$,正态随机变量和的分布依然是正态分布,所以$(Au)_i$服从正态分布,其均值为$\sum\limits_j u_j\times 0=0$,其方差则为$\sum\limits_j u_j^2\times \frac{1}{n} = \frac{1}{n}$。
所以,说白了,$Au$相当于从$\mathcal{N}(0,1/n)$独立重复采样出来的$n$维向量。现在代入$u=\frac{v_i - v_j}{\Vert v_i - v_j\Vert}$,利用“单位模引理”,得到
\begin{equation}P\left(\left|\left\Vert \frac{A(v_i - v_j)}{\Vert v_i - v_j\Vert}\right\Vert^2 - 1\right| \geq \varepsilon\right) \leq 2\exp\left(-\frac{\varepsilon^2 n}{8}\right)\end{equation}
此结果对于任意$i\neq j$都成立,那么遍历所有的$i\neq j$的组合,我们得到至少有一项$\geq \varepsilon$的概率不超过
\begin{equation}P\left(\exists (i,j):\,\left|\left\Vert \frac{A(v_i - v_j)}{\Vert v_i - v_j\Vert}\right\Vert^2 - 1\right| \geq \varepsilon\right) \leq 2 {N\choose 2} \exp\left(-\frac{\varepsilon^2 n}{8}\right)\end{equation}
或者反过来说,对于任意$i\neq j$,都成立$\left|\left\Vert \frac{A(v_i - v_j)}{\Vert v_i - v_j\Vert}\right\Vert^2 - 1\right| \leq \varepsilon$(等价于$\eqref{eq:bound}$)的概率不小于
\begin{equation}1 - 2 {N\choose 2} \exp\left(-\frac{\varepsilon^2 n}{8}\right) = 1 - N(N-1)\exp\left(-\frac{\varepsilon^2 n}{8}\right)\end{equation}
代入$n > \frac{24\log N}{\varepsilon^2}$,可以得到
\begin{equation}1 - N(N-1)\exp\left(-\frac{\varepsilon^2 n}{8}\right)\geq 1 - N(N-1)N^{-3}\geq 1-N^{-1}\end{equation}
至此,证明已经完成。
上面的JL引理中保持的是欧氏距离近似不变,很多时候我们检索用的是内积(比如余弦相似度)而不是欧氏距离。对此,我们有
内积版JL引理: 给定$N$个单位向量$v_1,v_2,\cdots,v_N\in\mathbb{R}^m$和$n > \frac{24\log N}{\varepsilon^2}$,而随机矩阵$A\in\mathbb{R}^{n\times m}$独立重复采样自$\mathcal{N}(0,1/n)$,$\varepsilon \in (0, 1)$是给定常数,那么至少有$\frac{N-2}{N}$的概率,使得对于所有的$i\neq j$,都成立 \begin{equation}\left|\langle Av_i, Av_j\rangle - \langle v_i, v_j\rangle\right|\leq\varepsilon\end{equation}
证明很简单,模仿“正交性引理”的证明即可。根据JL引理的证明,我们可以得到在相同的条件下,至少有$\frac{N-2}{N}$的概率同时满足对于任意$i\neq j$有
\begin{equation}\begin{aligned}
(1-\varepsilon)\Vert v_i - v_j\Vert^2 \leq \Vert Av_i - A v_j\Vert^2 \leq (1+\varepsilon)\Vert v_i - v_j\Vert^2 \\
(1-\varepsilon)\Vert v_i + v_j\Vert^2 \leq \Vert Av_i + A v_j\Vert^2 \leq (1+\varepsilon)\Vert v_i + v_j\Vert^2
\end{aligned}\end{equation}
将第一乘上$-1$得到$-(1+\varepsilon)\Vert v_i - v_j\Vert^2 \leq -\Vert Av_i - A v_j\Vert^2 \leq -(1-\varepsilon)\Vert v_i - v_j\Vert^2$,然后加到第二式得到
\begin{equation}4\langle v_i, v_j\rangle-2\varepsilon(\Vert v_i\Vert^2 + \Vert v_j\Vert)\leq 4\langle Av_i, Av_j\rangle \leq 4\langle v_i, v_j\rangle + 2\varepsilon(\Vert v_i\Vert^2 + \Vert v_j\Vert)\end{equation}
注意到$v_i,v_j$是单位向量,所以上式等价于$\left|\langle Av_i, Av_j\rangle - \langle v_i, v_j\rangle\right|\leq\varepsilon$。
极度的充分 #
动手去推过一次JL引理证明的同学应该能感觉到,JL引理的结论中之所以能够出现$\log N$,本质上是因为“单位模引理”中的概率项$2\exp\left(-\frac{\varepsilon^2 n}{8}\right)$是指数衰减的,而我们可以放宽这个衰减速度,让其变成多项式衰减,从而出现了$\log N$。
总的来说,JL引理告诉我们,以误差$\varepsilon$塞下$N$个向量,只需要$\mathcal{O}\left(\frac{\log N}{\varepsilon^2}\right)$维的空间,至于$\frac{\log N}{\varepsilon^2}$前面的常数是多少,其实不大重要。因为事实上JL引理是一个非常充分的条件,实际情况中条件往往更加宽松。比如,在JL引理的证明中如果我们将条件改为$n > \frac{16\log N}{\varepsilon^2}$,那么式$\eqref{eq:bound}$成立的概率就不小于
\begin{equation}1 - N(N-1)\exp\left(-\frac{\varepsilon^2 n}{8}\right)\geq 1 - N(N-1)N^{-2}=1/N\end{equation}
注意$1/N$虽然小,但终究是大于0的,所以此时依然是存在$A$使得$\eqref{eq:bound}$成立,只不过寻找$A$的成本更大罢了(每次命中的概率只有$1/N$),而如果我们只关心存在性,那么这也够了。
而且,JL引理只考虑了在随机线性投影下的降维,就已经得到$n > \frac{16\log N}{\varepsilon^2}$了,如果是其他更精细的降维,比如基于SVD的降维,是有可能得到更好的结果的(前面的系数更小);如果非线性的降维方法也考虑进去,那么结果又能变得更优了。所以说,不需要太关心$\frac{\log N}{\varepsilon^2}$前面的常数是多少,我们只需要知道$\mathcal{O}\left(\frac{\log N}{\varepsilon^2}\right)$的量级,如果真要用到它,通常还需要根据实际情况确定前面的常数,而不是调用理论结果。
且待下回续 #
在这篇文章中,我们介绍了Johnson–Lindenstrauss引理(JL引理),它是关于降维的一个重要而奇妙的结论,是高维空间的不同寻常之处的重要体现之一。它告诉我们“只需要$\mathcal{O}(\log N)$维空间就可以塞下$N$个向量”,使得原本高维空间中的检索问题可以降低到$\mathcal{O}(\log N)$维空间中。
本文主要讨论了JL引理的相关理论证明细节,下一篇文章我们则尝试应用它来理解一些机器学习问题,敬请期待~
转载到请包括本文地址:https://kexue.fm/archives/8679
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Sep. 17, 2021). 《让人惊叹的Johnson-Lindenstrauss引理:理论篇 》[Blog post]. Retrieved from https://kexue.fm/archives/8679
@online{kexuefm-8679,
title={让人惊叹的Johnson-Lindenstrauss引理:理论篇},
author={苏剑林},
year={2021},
month={Sep},
url={\url{https://kexue.fm/archives/8679}},
}
August 30th, 2022
苏神你好,最近正好在学习信息论,感觉JL引理的结论形式与信息熵有点像,如果假定N个向量是均匀分布的话,其最优编码的长度也正好是logN,这可能是数据压缩的下确界?
确实跟信息熵有关,参考我之前的推导结果:https://kexue.fm/archives/7695
December 24th, 2022
苏教授你好,本文中“A从N~(1,1/n)采样”,是否应为“A从N~(1,1/√n)采样”?个人浅见,请您参考。
否。正态分布的一般记号是$\mathcal{N}(\mu,\sigma^2)$,而不是$\mathcal{N}(\mu,\sigma)$
June 1st, 2023
[...]维度选择公式:n>8.33logNJL理论:塞下N个向量,只需要
June 20th, 2023
写的不错,JL引理的证明还可以结合 $\chi^2$ R.V. 和 Bernstein-type bound 证明。https://doi.org/10.1017/9781108627771.002这本书里面有写。
另外苏神可以讲讲VC dimension(Vapnik-Chervonenkis)吗?
谢谢肯定和推荐,不过VC dimension我也不大了解,抱歉
June 20th, 2023
这个定理和现在模型量化之间有没有关系呢
挺好的问题,我估计应该会有千丝万缕的联系吧(哭笑)
July 10th, 2024
请问下,如果是随机稀疏投影支持JL引理么,怎么证明的
随机稀疏投影的投影矩阵采样自三元分布,看上去本文的所有证明过程依然可以类似地进行,所以类似的结论是存在的。
或者从直观上来讲,正态分布$\mathcal{N}(0,\sigma^2)$可以视为任意均值为0、方差为$\sigma^2$的分布的一阶近似,所以在正态分布$\mathcal{N}(0,\sigma^2)$上成立的结果,往往在一定范围内都可以推广到任意均值为0、方差为$\sigma^2$的分布。
October 6th, 2024
你好,我不是很明白(9)到(10)之间的那个积分公式,感觉不太对,不知道那个积分项怎么出来的,我觉得应该是
$\mathbb{E}[e^{\lambda u_i^2}] = \int_{-\infty}^{\infty} e^{\lambda u_i^2} \sqrt{\frac{n}{2\pi}} e^{-\frac{nu_i^2}{2}} du_i$
你这个也没错,我这个是利用了从$\mathcal{N}(0,1/n)$中采样一个$x$,等价于从$\mathcal{N}(0,1)$中采样一个$y$,然后让$x=y/\sqrt{n}$,这是简单的重参数技巧(或者说积分换元)