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

苏剑林 分类:思考

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

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

给定NN个向量v1,v2,⋯,vN∈Rmv1,v2,⋯,vN∈Rm,如果想要将它降到nn维,那么只需要从N(0,1/n)N(0,1/n)中采样一个n×mn×m矩阵AA,然后Av1,Av2,⋯,AvNAv1,Av2,⋯,AvN就是降维后的结果。
 

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

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

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

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

具体来说,根据JL引理,我们从N(0,1/n)N(0,1/n)中采样一个n×mn×m矩阵AA,那么对于任意vi,vj∈Rmvi,vj∈Rm,都有cos(vi,vj)≈cos(Avi,Avj)cos⁡(vi,vj)≈cos⁡(Avi,Avj)。当然,随机投影还不是LSH的全部,我们留意到,经过AA的投影后,Avi,AvjAvi,Avj的正负分布情况是比较均匀的,所以我们进一步做近似

cos(vi,vj)≈cos(Avi,Avj)≈cos(sign(Avi),sign(Avj))(1)(1)cos⁡(vi,vj)≈cos⁡(Avi,Avj)≈cos⁡(sign(Avi),sign(Avj))

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

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

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

设待分解矩阵为M∈Rm×nM∈Rm×n,m,nm,n都比较大。根据JL引理,我们可以选择比较小的k<min(m,n)k<min(m,n),使得从N(0,1/k)N(0,1/k)中采样出来n×kn×k矩阵QQ依然能比较高精度地满足QQ⊤≈IQQ⊤≈I(近似正交矩阵),从而M≈MQQ⊤M≈MQQ⊤。这样,我们可以只对m×km×k矩阵B=MQB=MQ做SVD分解,得到MQ=B=UBΣBV⊤BMQ=B=UBΣBVB⊤,那么

M≈MQQ⊤=UBΣBV⊤BQ⊤=UBΣB(QVB)⊤(2)(2)M≈MQQ⊤=UBΣBVB⊤Q⊤=UBΣB(QVB)⊤

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

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

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

n>8.33logN(3)(3)n>8.33log⁡N

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

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

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

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

ai,j=e⟨qi,kj⟩∑j=1Le⟨qi,kj⟩(4)(4)ai,j=e⟨qi,kj⟩∑j=1Le⟨qi,kj⟩

其中qi,kj∈Rdqi,kj∈Rd,所谓“够不够”,就是指对于任意给定的概率矩阵pi,jpi,j,上述定义的ai,jai,j是否都能很好地逼近它?

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

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

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

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

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

转载到请包括本文地址:https://www.kexue.fm/archives/8706

回复

我来回复
  • 暂无回复内容

The maamx guide has been replaced with a new version. The contents of the original version have become invalid. Thank you for your visit.