让人惊叹的Johnson-Lindenstrauss引理:应用篇
By 苏剑林 | 2021-09-24 | 35334位读者 |上一篇文章中,我们比较详细地介绍了Johnson-Lindenstrauss引理(JL引理)的理论推导,这一篇我们来关注它的应用。
作为一个内容上本身就跟降维相关的结论,JL引理最基本的自然就是作为一个降维方法来用。但除了这个直接应用外,很多看似不相关的算法,比如局部敏感哈希(LSH)、随机SVD等,本质上也依赖于JL引理。此外,对于机器学习模型来说,JL引理通常还能为我们的维度选择提供一些理论解释。
降维的工具 #
JL引理提供了一个非常简单直接的“随机投影”降维思路:
给定$N$个向量$v_1,v_2,\cdots,v_N\in\mathbb{R}^m$,如果想要将它降到$n$维,那么只需要从$\mathcal{N}(0,1/n)$中采样一个$n\times m$矩阵$A$,然后$Av_1,Av_2,\cdots,Av_N$就是降维后的结果。
这个思路简单快速是毋庸置疑的,读者随之而来的疑问就是:它跟PCA、t-SNE等降维方法相比效果如何?
其实,正如“存在就是合理的”,更复杂的PCA、t-SNE等方法既然还没有被淘汰,那就说明它肯定有比随机投影更好的地方。事实上,JL引理的随机投影只是提供了一种非常基本的降维方法,显示出哪怕在这么简单的方法之后,降维后的维度也只需要$\mathcal{O}(\log N)$,它更多的是一个理论证明。
所以,真要追求降维精度的话,多数情况下PCA、t-SNE等这些专门的降维方法,效果肯定是要比随机投影要好的。而且上一篇文章中我们也提过,JL引理是一个非常充分的条件,它得到的$n > \frac{24\log N}{\varepsilon^2}$甚至$n > \frac{16\log N}{\varepsilon^2}$都只是非常充分的界,比如取$\varepsilon=0.1$的话,就有$n > 1600\log N$了,基本没有实用价值。而换用PCA、t-SNE等更精准的降维方法,可以放宽这个要求,即在更小的维度下达到更好的效果。
局部的哈希 #
局部敏感哈希(Locality-Sensitive Hashing,LSH),是近似查找某种度量下的最邻近元素的一种方案。通常来说,我们很少将LSH与JL引理联系起来,但笔者认为,LSH的哈希函数选择上,其实跟JL引理也是紧密相关的。简单来说,LSH就是一个将向量二值化的算法,并且二值化之后的向量能近似保持度量不变。常见的一种方案是通过随机投影来(近似)保持cos值的不变性。
具体来说,根据JL引理,我们从$\mathcal{N}(0,1/n)$中采样一个$n\times m$矩阵$A$,那么对于任意$v_i,v_j\in\mathbb{R}^m$,都有$\cos(v_i,v_j)\approx \cos(Av_i, Av_j)$。当然,随机投影还不是LSH的全部,我们留意到,经过$A$的投影后,$Av_i,Av_j$的正负分布情况是比较均匀的,所以我们进一步做近似
\begin{equation}\cos(v_i,v_j)\approx \cos(Av_i, Av_j)\approx \cos(\text{sign}(Av_i), \text{sign}(Av_j))\end{equation}
即每个元素我们根据正负号二值化为$\pm 1$,这就实现了向量的二值化,并且保持了余弦值近似不变。有了二值化向量后,我们可以建索引、分通等,以加快检索速度,这些就不细说了。
总之,在LSH过程中,关键的一步也是随机投影,这一步本身与JL引理也是紧密相关的。当然,二值化通常会比较明显地牺牲精度,所以根据实际场景的不同,我们并不总是“降维”,即$n$并不会总是小于$m$,有时候我们可能还会选择$n > m$。相关的讨论读者可以参考笔者之前写的《一个二值化词向量模型,是怎么跟果蝇搭上关系的?》。
随机的分解 #
矩阵分解是解决许多机器学习问题的强大工具,而奇异值分解(SVD)则是其中的典型方法之一。然而,当矩阵比较大的时候,计算精确的SVD分解成本相当大,而实际场景中,待分解矩阵虽然大,但往往也是低秩的,计算精确的SVD分解也没有必要。这时候,“随机SVD分解”便派上用场了。
设待分解矩阵为$M\in\mathbb{R}^{m\times n}$,$m,n$都比较大。根据JL引理,我们可以选择比较小的$k < \min(m,n)$,使得从$\mathcal{N}(0,1/k)$中采样出来$n\times k$矩阵$Q$依然能比较高精度地满足$QQ^{\top}\approx I$(近似正交矩阵),从而$M\approx MQQ^{\top}$。这样,我们可以只对$m\times k$矩阵$B=MQ$做SVD分解,得到$MQ=B=U_B\Sigma_B V_B^{\top}$,那么
\begin{equation}M\approx MQQ^{\top} = U_B\Sigma_B V_B^{\top}Q^{\top} = U_B \Sigma_B (QV_B)^{\top}\end{equation}
就得到了原始矩阵$M$的一个近似SVD分解。注意,上述$Q$还只是近似正交矩阵,我们可以通过QR分解(或施密特正交化)使得它变成严格正交,这是一个小细节。在整个过程中,JL引理所告诉我们的是$k$可以选得比较小,以至于对$B=MQ$做SVD是比较低成本的,但总体精度也不会太差。
词向量维度 #
我们说JL引理的通俗理解是“塞下$N$个向量只需要$\mathcal{O}(\log N)$维空间”,那么回到词向量维度选择问题上,也就是说如果词表大小为$N$,那么词向量维度是$\mathcal{O}(\log N)$就够了。
非常让人惊震的是,在笔者之前的文章《最小熵原理(六):词向量的维度应该怎么选择?》中,曾计算出了一个Skip Gram词向量模型的维度选择公式:
\begin{equation}n > 8.33\log N\end{equation}
其结果与JL引理所给出的$\mathcal{O}(\log N)$如出一辙!上述公式是基于熵的思想进行估计的,与JL引理的出发点几乎没有交集之处,但竟然殊途同归地得到了$\log N$。
而且,不仅仅是主体$\log N$,我们还看到,基于熵的估计,我们还把$\log N$前面的系数$8.33$也计算出来了,并且以往的实验经验还显示,$8.33\log N$这个结果还是挺符合经验的,虽然未必是最优,但至少范围上差不远。这是不是可以反过来说,我们可以通过熵来比较精确地估计具体问题下$\log N$前面的系数?
多头注意力 #
关于Attention机制,常见的面试题就是“为什么要多头?”、“head_size为768的单头注意力,跟head_size为64的12头注意力有什么区别?”等,也就是说,像BERT这样的Attention模型,为什么要先把head_size降低到64再做内积?64真的够了吗?
这个问题本质上来说Attention机制是否足以拟合任何概率模式的问题。具体来说,Attention的计算公式为:
\begin{equation}a_{i,j} = \frac{e^{\langle q_i, k_j\rangle}}{\sum\limits_{j=1}^L e^{\langle q_i, k_j\rangle}}\end{equation}
其中$q_i,k_j\in\mathbb{R}^{d}$,所谓“够不够”,就是指对于任意给定的概率矩阵$p_{i,j}$,上述定义的$a_{i,j}$是否都能很好地逼近它?
看到$a_{i,j}$的定义,不知道有没有读者觉得熟悉的?如果我们抛开Attention的背景,将$q_i,k_j$分别视为两个“词向量”,那么$a_{i,j}$的定义跟Skip Gram模型一模一样!也就是说,单纯看Attention矩阵的计算公式,它跟Skip Gram模型本质上是一样的,所以Attention的head_size选择,本质上也就是词向量的维度选择。
让我们再来捋一捋过程。我们要回答的是“head_size多少才够”的问题,这变成了“$a_{i,j}$能否逼近任意概率矩阵$p_{i,j}$”的问题,也就是说,对于给定$p_{i,j}$,我们是否能找到一组$q_1,\cdots,q_L,k_1,\cdots,k_L\in\mathbb{R}^d$,使得$a_{i,j}$与$p_{i,j}$足够近似,这个问题跟Skip Gram词向量模型的维度选择是数学等价的。
因此,词向量维度选择的结果,也就可以用于Attention的head_size选择,只不过词表大小变成了序列长度,即$d > 8.33\log L$,常见的预训练长度是$L=512$,代入计算约等于52,同样非常让人震惊,跟常见的head_size=64确实相差无几!所以,64真的够了,再大也不会有明显提升,倒不如将多出来的计算量用来增加head的数目~
(注:相关讨论还可以参考文献《On the Expressive Power of Self-Attention Matrices》。)
又到了小结 #
本文主要介绍了Johnson-Lindenstrauss引理(JL引理)的几个直接或间接的应用,可以看到,从降维、哈希的方法,到词向量维度、Attention的头大小等,多多少少都与JL引理有所关联,这进一步显示了JL引理的适用范围之广。
转载到请包括本文地址:https://spaces.ac.cn/archives/8706
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Sep. 24, 2021). 《让人惊叹的Johnson-Lindenstrauss引理:应用篇 》[Blog post]. Retrieved from https://spaces.ac.cn/archives/8706
@online{kexuefm-8706,
title={让人惊叹的Johnson-Lindenstrauss引理:应用篇},
author={苏剑林},
year={2021},
month={Sep},
url={\url{https://spaces.ac.cn/archives/8706}},
}
October 9th, 2021
head_size 为什么定义为64,终于看到了令我信服的解释!
July 14th, 2024
苏神太强了,我从本科遇到不懂的问题搜到最好的答案是苏神的,现在读博了,搜到的最好的答案还是苏神的