科学空间|Scientific Spaces

这几天读到论文《Exploring and Exploiting Hubness Priors for High-Quality GAN Latent Sampling》，了解到了一个新的名词“Hubness现象”，说的是高维空间中的一种聚集效应，本质上是“维度灾难”的体现之一。论文借助Hubness的概念得到了一个提升GAN模型生成质量的方案，看起来还蛮有意思。所以笔者就顺便去学习了一下Hubness现象的相关内容，记录在此，供大家参考。

坍缩的球

“维度灾难”是一个很宽泛的概念，所有在高维空间中与相应的二维、三维空间版本出入很大的结论，都可以称之为“维度灾难”，比如《n维空间下两个随机向量的夹角分布》中介绍的“高维空间中任何两个向量几乎都是垂直的”。其中，有不少维度灾难现象有着同一个源头——“高维空间单位球与其外切正方体的体积之比逐渐坍缩至0”，包括本文的主题“Hubness现象”亦是如此。

点击阅读全文...

在之前的文章《最小熵原理（六）：词向量的维度应该怎么选择？》中，我们基于最小熵思想推导出了一个词向量维度公式“$n > 8.33\log N$”，然后在《让人惊叹的Johnson-Lindenstrauss引理：应用篇》中我们进一步指出，该结果与JL引理所给出的$\mathcal{O}(\log N)$是吻合的。

既然理论上看上去很完美，那么自然就有读者发问了：实验结果如何呢？8.33这个系数是最优的吗？本文就对此问题的相关内容做一个简单汇总。

词向量

首先，我们可以直接，当$N$为10万时，$8.33\log N\approx 96$，当$N$为500万时，$8.33\log N\approx 128$。这说明，至少在数量级上，该公式给出的结果是很符合我们实际所用维度的，因为在词向量时代，我们自行训练的词向量维度也就是100维左右。可能有读者会质疑，目前开源的词向量多数是300维的，像BERT的Embedding层都达到了768维，这不是明显偏离了你的结果了？

点击阅读全文...

上一篇文章中，我们比较详细地介绍了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$就是降维后的结果。

点击阅读全文...

今天我们来学习Johnson-Lindenstrauss引理，由于名字比较长，下面都简称“JL引理”。

个人认为，JL引理是每一个计算机科学的同学都必须了解的神奇结论之一，它是一个关于降维的著名的结果，它也是高维空间中众多反直觉的“维度灾难”现象的经典例子之一。可以说，JL引理是机器学习中各种降维、Hash等技术的理论基础，此外，在现代机器学习中，JL引理也为我们理解、调试模型维度等相关参数提供了重要的理论支撑。

对数的维度

JL引理，可以非常通俗地表达为：

通俗版JL引理： 塞下$N$个向量，只需要$\mathcal{O}(\log N)$维空间。

点击阅读全文...

一般来说，如果原函数容易找到的话，牛顿-莱布尼兹公式是定积分的通用方法。但是牛顿-莱布尼兹公式只适合连续函数的积分，如果积分区间含有奇点，那就不成立了。比如，我们考虑积分
$$\int_{-1}^1 \frac{1}{x^2}dx$$
当然，从严格的数学上来说，这种写法是不成立的，因为被积函数在原点没有意义。当然，从物理的角度来考虑，由于对称性，我们确信
$$\int_{-1}^1 \frac{1}{x^2}dx=2\int_{0}^1 \frac{1}{x^2}dx=\lim_{\varepsilon\to 0}2\int_{\varepsilon}^1 \frac{1}{x^2}dx$$
从而得出积分发散的结论。这种处理某种程度上是可以接受的，但是却不是让人满意的，因为它导致了分段。有什么办法可以直接处理这种情况呢？确实有的，同样引入参数，并且最终让参数为0，考虑带参数的积分
$$\int_{-1}^1 \frac{1}{x^2+\varepsilon^2}dx$$
只要参数为正，这个被积函数就在$\mathbb{R}$上处处连续了，也就是奇点消失了，这样子就可以用牛顿-莱布尼兹公式了
$$\int_{-1}^1 \frac{1}{x^2+\varepsilon^2}dx=\left.\frac{1}{\varepsilon}\arctan\left(\frac{x}{\varepsilon}\right)\right|_{-1}^{1}$$
考虑$\varepsilon\to 0$的情况，就自动得到了积分发散的结论。

点击阅读全文...

这篇文章其实在年初就完成了。

众所周知，我们生活在一个平坦的世界中。正如我们能够感受到的那样，在这个被称为“欧几里得平直空间”的世界里，空间里两点间的最短曲线是两点间的直线段，空间里的任意直角三角形都满足勾股定理，每个物体都有着自己的长、宽、高，它们都随着时间的流逝而运动着。这种世界观把时间独立于空间之外，作为一个独特的研究对象。但是自爱因斯坦在1905年发表狭义相对论以来，我们的宇宙就被描述成为了由三维空间和一维时间组成的“四维时空”，在这里，时间和空间的地位是等价的。不少同好们也许会感到非常困惑：即使证明了时间与空间的确存在着某种联系，也不必要把时间描述成是世界的一维吧？在我们的感官里，时间明明就和空间的三维差别甚大，时间和空间怎么能够等同起来呢？其实答案很简单：为了美。把时间看成与空间等价的一维之后，整个力学体系体现出一种前所未有的对称美，这种美不仅让人赏心悦目，而且极大地方便了我们进一步处理问题。

对称

点击阅读全文...