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

上一篇文章中，我们比较详细地介绍了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引理的随机投影只是提供了一种非常基本的降维方法，显示出哪怕在这么简单的方法之后，降维后的维度也只需要$\mathscr{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$个向量只需要$\mathscr{O}(\log N)$维空间”，那么回到词向量维度选择问题上，也就是说如果词表大小为$N$，那么词向量维度是$\mathscr{O}(\log N)$就够了。

非常让人惊震的是，在笔者之前的文章《最小熵原理（六）：词向量的维度应该怎么选择？》中，曾计算出了一个Skip Gram词向量模型的维度选择公式：
\begin{equation}n > 8.33\log N\end{equation}
其结果与JL引理所给出的$\mathscr{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://kexue.fm/archives/8706

更详细的转载事宜请参考：《科学空间FAQ》

打赏

微信打赏

支付宝打赏

因为网站后台对打赏并无记录，因此欢迎在打赏时候备注留言。
你还可以点击这里或在下方评论区留言来告知你的建议或需求。