让人惊叹的Johnson-Lindenstrauss引理：理论篇

原创苏剑林 PaperWeekly

©PaperWeekly 原创 · 作者 | 苏剑林

单位 | 追一科技

研究方向 | NLP、神经网络

今天我们来学习 Johnson-Lindenstrauss 引理，由于名字比较长，下面都简称“JL 引理”。

个人认为，JL 引理是每一个计算机科学的同学都必须了解的神奇结论之一，它是一个关于降维的著名的结果，它也是高维空间中众多反直觉的“维度灾难”现象的经典例子之一。可以说，JL 引理是机器学习中各种降维、Hash 等技术的理论基础，此外，在现代机器学习中，JL 引理也为我们理解、调试模型维度等相关参数提供了重要的理论支撑。

对数的维度

JL 引理，可以非常通俗地表达为：

通俗版 JL 引理：塞下个向量，只需要维空间。

具体来说，JL 引理说的是，不管这个向量原来是多少维的，我们都可以将它们降到，并将相对距离的误差控制在一定范围内。可以想象，这是一个非常强、非常反直觉、非常实用的结论，比如我们要做向量检索，原本的向量维度可能非常大，这样全量检索一次的成本也非常大，而 JL 引理告诉我们，可以将它们变换到维，并且检索效果近似不变，这简直就是“天上掉馅饼”的好事！

可能读者会有疑问：这么强的结论，那么对应的降维方法会不会特别复杂？答案是刚刚相反，降维过程仅仅用到随机线性投影！甚至有评价说，JL 引理是一个“证明比理解更容易的结论”，也就是说，从数学上证明它还真不算特别困难，但如何直观地理解这个反直觉的结论，反而是不那么容易的。

无独有偶，我们之前其实就介绍过两个反直觉的结果：在文章《n 维空间下两个随机向量的夹角分布》[1] 中，我们就介绍过“高维空间中任意两个向量几乎都是垂直的”，这显然与二维、三维空间的结果差距甚远；在文章《从几何视角来理解模型参数的初始化策略》[2] 中，这个结果进一步升级为“从采样出来的矩阵几乎是一个正交矩阵”，这更与我们一直理解的“正交性是非常苛刻的（要求转置等于逆）”有严重出入。

但事实上，这两个结论不仅对，而且还跟 JL 引理直接相关。可以说，JL 引理可以看成是它们的细化和应用。所以，我们需要先用更定量的语言来刻画这两个结论，比如“几乎垂直”，那垂直的概率究竟有多少，比如“近似正交”，那误差究竟有多大。

概率不等式

为此，我们需要一些概率知识，其中最主要是“马尔可夫不等式”：

马尔可夫不等式：如果是非负随机变量，，那么

注意该不等式并没有对所服从的分布有其他特别的限制，只要求随机变量的取值空间是非负的（或者等价地，负的的概率恒为 0），证明其实非常简单：

马尔可夫不等式要求随机变量是非负的，但我们平时要处理的随机变量不一定是非负的，所以通常需要变换一下才能用。比如不是非负的，但是非负的，于是利用马尔可夫不等式有：

这就是“切比雪夫不等式”。

另外一个经典技巧称为“Cramér-Chernoff方法”，也是我们后面主要利用到的方法，它通过指数函数将随机变量变成非负的：对于任意，我们有

所以利用马尔可夫不等式有

最左端是跟无关的，但是最右端有一个，而这不等式是对于任意都成立的。所以理论上，我们可以找到使得最右端最小的，以获得最高的估计精度：

引理的引理

现在，我们可以引入如下结果，它是 JL 引理的引理，甚至可以说，它是本文一切结论的理论基础：

单位模引理：设是独立重复采样自的向量，是给定常数，那么我们有：

该引理告诉我们，当足够大的时候，的模长明显偏离 1 的概率是非常小的（给定后，将以的指数形式递减至 0），所以从采样出来的维向量将会非常接近单位向量。

它的证明正是用到“Cramér-Chernoff方法”：首先意味着或，我们需要分别进行推导，不失一般性，先推导的概率，根据 Cramér-Chernoff 方法，有：

将 u 写成分量形式，其中每个分量都是独立的，分布均为，那么我们有：

而

，所以：

右端的极小值在取到，推导过程就留给读者了，然后代入得到：

其中的证明也留给读者了。类似地，我们可以对的概率进行推导，结果为：

其中可证，所以上式沿用了的不等关系。现在两式相加，我们得到。证毕。

从“单位模引理”出发，我们可以证明“正交性引理”：

正交性引理：设是独立重复采样自的两个向量，是给定常数，那么我们有：

该引理告诉我们，当足够大的时候，的内积明显偏离 0 的概率是非常小的（给定后，将以的指数形式递减至 0），所以从采样出来的两个维向量将会非常接近正交。而结合“单位模引理”，我们就得到“从采样出来的矩阵几乎是一个正交矩阵”的结论了。

有了“单位模引理”铺垫，它的证明不算难。我们知道如果，那么，所以根据“单位模引理”的证明，我们有：

注意和两式相加后可以得出，所以：

同理可证，两者结合就得到“正交性引理”。

证明的过程

现在我们就可以着手证明 JL 引理了，下面是它的数学表述：

数学版 JL 引理：给定个向量和，而随机矩阵独立重复采样自是给定常数，那么至少有的概率，使得对于所有的，都成立：

引理告诉我们，不管原来的向量维数是多少，只需要的维度，我们就可以容纳下个向量，使得它们相对距离的偏离都不超过。而且 JL 引理还告诉我们降维方法：只需要从随机采样一个的矩阵，然后变换就有的可能性达到目的。真可谓是简单实用了。

证明过程也是“单位模引理”的直接应用。首先，如果是给定的单位向量，而独立重复采样自，那么的每个分量都独立地服从。证明也并不难，根据定义每个分量，由于相互独立，所以显然相互独立，并且由于，正态随机变量和的分布依然是正态分布，所以服从正态分布，其均值为，其方差则为。

所以，说白了，相当于从独立重复采样出来的维向量。现在代入，利用“单位模引理”，得到：

此结果对于任意都成立，那么遍历所有的的组合，我们得到至少有一项的概率不超过：

或者反过来说，对于任意，都成立

（等价于（16））的概率不小于：

代入，可以得到：

至此，证明已经完成。

上面的 JL 引理中保持的是欧氏距离近似不变，很多时候我们检索用的是内积（比如余弦相似度）而不是欧氏距离。对此，我们有：

内积版 JL 引理：给定个单位向量和，而随机矩阵独立重复采样自是给定常数，那么至少有的概率，使得对于所有的，都成立：

证明很简单，模仿“正交性引理”的证明即可。根据 JL 引理的证明，我们可以得到在相同的条件下，至少有的概率同时满足对于任意有：

将第一乘上 -1 得到：

然后加到第二式得到：

注意到是单位向量，所以上式等价于。

极度的充分

动手去推过一次 JL 引理证明的同学应该能感觉到，JL 引理的结论中之所以能够出现，本质上是因为“单位模引理”中的概率项是指数衰减的，而我们可以放宽这个衰减速度，让其变成多项式衰减，从而出现了。

总的来说，JL 引理告诉我们，以误差塞下个向量，只需要维的空间，至于前面的常数是多少，其实不大重要。因为事实上 JL 引理是一个非常充分的条件，实际情况中条件往往更加宽松。比如，在 JL 引理的证明中如果我们将条件改为，那么式（16）成立的概率就不小于：

注意虽然小，但终究是大于 0 的，所以此时依然是存在使得（16）成立，只不过寻找的成本更大罢了（每次命中的概率只有），而如果我们只关心存在性，那么这也够了。

而且，JL 引理只考虑了在随机线性投影下的降维，就已经得到了，如果是其他更精细的降维，比如基于 SVD 的降维，是有可能得到更好的结果的（前面的系数更小）；如果非线性的降维方法也考虑进去，那么结果又能变得更优了。所以说，不需要太关心前面的常数是多少，我们只需要知道的量级，如果真要用到它，通常还需要根据实际情况确定前面的常数，而不是调用理论结果。