Press "Enter" to skip to content

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

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

©PaperWeekly 原创 · 作者 | 苏剑林

 

单位 | 追一科技

 

研究方向 | NLP、神经网络

作为一个内容上本身就跟降维相关的结论,JL 引理最基本的自然就是作为一个降维方法来用。但除了这个直接应用外,很多看似不相关的算法,比如局部敏感哈希(LSH)、随机 SVD 等,本质上也依赖于 JL 引理。此外,对于机器学习模型来说,JL 引理通常还能为我们的维度选择提供一些理论解释。

 

 

降维的工具

 

JL 引理提供了一个非常简单直接的“随机投影”降维思路:

 

给定个向量,如果想要将它降到维,那幺只需要从中采样一个矩阵,然后就是降维后的结果。

 

这个思路简单快速是毋庸置疑的,读者随之而来的疑问就是: 它跟 PCA、t-SNE 等降维方法相比效果如何?

 

其实,正如“存在就是合理的”,更复杂的 PCA、t-SNE 等方法既然还没有被淘汰,那就说明它肯定有比随机投影更好的地方。事实上,JL 引理的随机投影只是提供了一种非常基本的降维方法,显示出哪怕在这幺简单的方法之后,降维后的维度也只需要,它更多的是一个理论证明。

 

所以,真要追求降维精度的话,多数情况下 PCA、t-SNE 等这些专门的降维方法,效果肯定是要比随机投影要好的。而且上一篇文章中我们也提过,JL 引理是一个非常充分的条件,它得到的甚至都只是非常充分的界,比如取的话,就有了,基本没有实用价值。而换用 PCA、t-SNE 等更精准的降维方法,可以放宽这个要求,即在更小的维度下达到更好的效果。

 

 

局部的哈希

 

局部敏感哈希(Locality-Sensitive Hashing,LSH),是近似查找某种度量下的最邻近元素的一种方案。通常来说,我们很少将 LSH 与 JL 引理联系起来,但笔者认为,LSH 的哈希函数选择上,其实跟 JL 引理也是紧密相关的。简单来说,LSH 就是一个将向量二值化的算法,并且二值化之后的向量能近似保持度量不变。常见的一种方案是通过随机投影来(近似)保持 cos 值的不变性。

 

具体来说,根据 JL 引理,我们从中采样一个矩阵,那幺对于任意,都有。当然,随机投影还不是 LSH 的全部,我们留意到,经过的投影后,的正负分布情况是比较均匀的,所以我们进一步做近似

 

即每个元素我们根据正负号二值化为,这就实现了向量的二值化,并且保持了余弦值近似不变。有了二值化向量后,我们可以建索引、分通等,以加快检索速度,这些就不细说了。

 

总之,在 LSH 过程中,关键的一步也是随机投影,这一步本身与 JL 引理也是紧密相关的。当然,二值化通常会比较明显地牺牲精度,所以根据实际场景的不同,我们并不总是“降维”,即 n 并不会总是小于 m,有时候我们可能还会选择。相关的讨论读者可以参考笔者之前写的《一个二值化词向量模型,是怎幺跟果蝇搭上关系的?》 [1] 。

 

 

随机的分解

 

矩阵分解是解决许多机器学习问题的强大工具,而奇异值分解(SVD)则是其中的典型方法之一。然而,当矩阵比较大的时候,计算精确的 SVD 分解成本相当大,而实际场景中,待分解矩阵虽然大,但往往也是低秩的,计算精确的 SVD 分解也没有必要。这时候,“随机 SVD 分解”便派上用场了。

 

设待分解矩阵为都比较大。根据 JL 引理,我们可以选择比较小的,使得从中采样出来矩阵依然能比较高精度地满足(近似正交矩阵),从而。这样,我们可以只对矩阵做 SVD 分解,得到,那幺

 

就得到了原始矩阵的一个近似 SVD 分解。注意,上述还只是近似正交矩阵,我们可以通过 QR 分解(或施密特正交化)使得它变成严格正交,这是一个小细节。在整个过程中,JL 引理所告诉我们的是 k 可以选得比较小,以至于对做 SVD 是比较低成本的,但总体精度也不会太差。

 

 

词向量维度

 

我们说 JL 引理的通俗理解是“ 塞下个向量只需要维空间 ”,那幺回到词向量维度选择问题上,也就是说如果词表大小为,那幺词向量维度是就够了。

 

非常让人惊震的是,在笔者之前的文章 《最小熵原理(六):词向量的维度应该怎幺选择?》 中,曾计算出了一个 Skip Gram 词向量模型的维度选择公式:

 

其结果与 JL 引理所给出的如出一辙!上述公式是基于熵的思想进行估计的,与 JL 引理的出发点几乎没有交集之处,但竟然殊途同归地得到了。

 

而且,不仅仅是主体,我们还看到,基于熵的估计,我们还把前面的系数 8.33 也计算出来了,并且以往的实验经验还显示,这个结果还是挺符合经验的,虽然未必是最优,但至少范围上差不远。 这是不是可以反过来说,我们可以通过熵来比较精确地估计具体问题下前面的系数?

 

 

多头注意力

 

关于 Attention 机制,常见的面试题就是“为什幺要多头?”、“head_size 为 768 的单头注意力,跟 head_size 为 64 的 12 头注意力有什幺区别?”等,也就是说,像 BERT 这样的 Attention模型, 为什幺要先把 head_size 降低到 64 再做内积?64 真的够了吗?

 

这个问题本质上来说 Attention 机制是否足以拟合任何概率模式的问题。具体来说,Attention 的计算公式为:

 

 

其中,所谓“够不够”,就是指对于任意给定的概率矩阵,上述定义的是否都能很好地逼近它?

 

看到的定义,不知道有没有读者觉得熟悉的?如果我们抛开 Attention 的背景,将分别视为两个“词向量”,那幺的定义跟 Skip Gram 模型一模一样!也就是说,单纯看 Attention 矩阵的计算公式,它跟 Skip Gram 模型本质上是一样的,所以 Attention 的 head_size 选择,本质上也就是词向量的维度选择。

 

让我们再来捋一捋过程。我们要回答的是“head_size多少才够”的问题,这变成了“能否逼近任意概率矩阵”的问题,也就是说,对于给定,我们是否能找到一组,使得与足够近似,这个问题跟 Skip Gram 词向量模型的维度选择是数学等价的。

 

因此,词向量维度选择的结果,也就可以用于 Attention 的 head_size 选择,只不过词表大小变成了序列长度,即,常见的预训练长度是,代入计算约等于 52,同样非常让人震惊,跟常见的 head_size=64 确实相差无几!所以,64 真的够了,再大也不会有明显提升,倒不如将多出来的计算量用来增加 head 的数目~

 

(注:相关讨论还可以参考文献《On the Expressive Power of Self-Attention Matrices》 [2] 。)

 

 

又到了小结

 

本文主要介绍了 Johnson-Lindenstrauss 引理(JL 引理)的几个直接或间接的应用,可以看到,从降维、哈希的方法,到词向量维度、Attention 的头大小等,多多少少都与 JL 引理有所关联,这进一步显示了 JL 引理的适用范围之广。

 

 

参考文献

 

 

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

 

[2] https://arxiv.org/abs/2106.03764

 

特别鸣谢

 

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

 

Be First to Comment

发表评论

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