Press "Enter" to skip to content

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

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

单位  |  追一科技

 

研究方向  |  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 的降维,是有可能得到更好的结果的(前面的系数更小);如果非线性的降维方法也考虑进去,那幺结果又能变得更优了。所以说,不需要太关心前面的常数是多少,我们只需要知道的量级,如果真要用到它,通常还需要根据实际情况确定前面的常数,而不是调用理论结果。

 

 

且待下回续

 

在这篇文章中,我们介绍了 Johnson–Lindenstrauss 引理(JL 引理),它是关于降维的一个重要而奇妙的结论,是高维空间的不同寻常之处的重要体现之一。它告诉我们“只需要维空间就可以塞下个向量”,使得原本高维空间中的检索问题可以降低到维空间中。

 

本文主要讨论了 JL 引理的相关理论证明细节,下一篇文章我们则尝试应用它来理解一些机器学习问题,敬请期待。

 

 

参考文献

 

 

[1] https://kexue.fm/archives/7076

 

[2] https://kexue.fm/archives/7180

 

特别鸣谢

 

感谢 TCCI 天桥脑科学研究院对于 PaperWeekly 的支持。TCCI 关注大脑探知、大脑功能和大脑健康。

 

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注