如何度量数据的稀疏程度？

2023-05-07 15:05

©PaperWeekly 原创 · 作者 | 苏剑林

单位 | 追一科技

研究方向 | NLP、神经网络

在机器学习中，我们经常会谈到稀疏性，比如我们经常说注意力矩阵通常是很稀疏的。然而，不知道大家发现没有，我们似乎从没有给出过度量稀疏程度的标准方法。也就是说，以往我们关于稀疏性的讨论，仅仅是直观层面的感觉，并没有过定量分析。那么问题来了，稀疏性的度量有标准方法了吗？

经过搜索，笔者发现确实是有一些可用的指标，比如、熵等，但由于关注视角的不同，在稀疏性度量方面并没有标准答案。本文简单记录一下笔者的结果。

基本结果

狭义上来讲，“稀疏”就是指数据中有大量的零，所以最简单的稀疏性指标就是统计零的比例。但如果仅仅是这样的话，注意力矩阵就谈不上稀疏了，因为softmax出来的结果一定是正数。所以，有必要推广稀疏的概念。一个朴素的想法是统计绝对值不超过的元素比例，但这个怎么确定呢？

1 相比于 0.0001 很大，但是相比 10000 又很小，所以大和小的概念不是绝对的。直观来想，稀疏的向量存在很多接近于零的数，那么它的绝对值的平均肯定会比较小，又因为大和小的概念是相对的，我们不妨将这个平均值跟最大值做除法，以获得相对结果，所以一个看上去比较合理的指标是

其中是需要评估稀疏性的向量（下面都假设并非全等向量，即至少有两个不同的元素），指标越小的向量越稀疏。不过，尽管这个指标有一定的合理性，但它却不够“光滑”，主要是这个操作极易受到异常值的影响，不能很好地反应数据统计特性。

光滑齐次

于是，我们按照《寻求一个光滑的最大值函数》[1] 的思路，将换成它的光滑近似。标准的光滑近似是：

然而，如果这里用替代，并不能起到较好的改进效果。一是因为有的放大作用，同样容易受到异常值的影响，二是因为没有正齐次性，反而不美（所有乘以正数，稀疏性应该不改变）。在《寻求一个光滑的最大值函数》[1] 中我们也给出了一个的具备正齐次性的光滑近似，它正好是范数（）：

再次观察式（1），我们可以发现它的分子正好是，所以综合上面的结果，我们得到了度量稀疏性的一个指标为

如果只是固定维度的向量比较，那么可以略掉。常见的是取，那么就得到稀疏性度量的指标。

理想性质

在《“熵”不起：从熵、最大熵原理到最大熵模型（一）》[2] 介绍“熵”的概念时，我们发现可以通过几条熵应当具备的理想性质来把熵的数学形式确定下来。那么稀疏性可否效仿这一点呢？

论文《Comparing Measures of Sparsity》[3] 做了这方面的尝试，它提出稀疏性度量应该具备以下几点理想性质（不失一般性，这里假设是非负向量，如果不是的话，逐项取绝对值即可）：

D1、

，其中且。这点性质说的是如果总和不变，那么越均匀越不稀疏。

D2、，其中。这点容易理解，就是指稀疏是一个相对的性质，所有元素乘以一个相同的倍数，不改变相对大小，也就不改变稀疏性。

D3、，其中。这点也容易理解，全体元素加上一个正数，那么全体都更加远离了零，稀疏性自然要降低。

D4、

，这里的指两个向量拼接。这点也不难理解，就是单纯的数据复制不改变稀疏性。

P1、任意给定，存在，使得对于任意，都有

。这条性质想表达的是当某个元素足够大的时候，整个向量的稀疏性就由它主导了。

P2、。这个就很朴素了，给向量添加零，应该导致稀疏性增加。

原论文对稀疏性的各种常用指标做了推导，发现只有一个名为 “Gini 指数”的指标同时满足以上 6 点性质（但这个 Gini 指数比较复杂，这里就不介绍了）。不过需要提醒的是，读原论文的读者需要仔细留意一下推导过程，因为笔者发现它证明不满足 D3 的证明是错的，事实上是满足 D3 的，至于其他推导笔者也没有细看，读者需要自行甄别正误。

参考证明

对于本文的两个指标，指标（1）同时满足除 D1 外的另外 5 点性质（如果 D1 的改为，那么也满足），这些性质的判断是比较平凡的，这里不详细讨论了，请读者自行完成。

至于指标（4），可以证明它同时满足除 D4 外的另外 5 点性质，其中 D3、P1 的证明稍微复杂一些，这里给出它们的参考证明。

为了证明 D3，只需要证明

关于是单调递增的。两边取对数，得到

我们只需要证明。直接求导得到

等价于

这由幂均值不等式 [4] 直接可得。

P1 的证明思路是类似的，只需要证明当足够大的时候，

关于是单调递减的。两边取对数，得到

我们只需要证明。直接求导得到

等价于

只要各并非全零，那么当足够大时，总可以使得上式对恒成立。

完美指标

尽管指标（4）不满足 D4，但我们将它简单修改为

后，它是满足 D4 的，并且也可以检验它也满足 P2，至于其他几点性质并不涉及到维度 n 的改变，因此跟指标（4）一样也满足。也就是说，是同时满足 6 点性质的“完美指标”！

由幂均值不等式 [4] 可知，所以；此外，由于

所以。综上，。

当时，有

这个结果可以回答关于稀疏化的一些问题。比如为什么 L1 正则有利于稀疏化？因为 L1 出现在上式的分子中，它越小越稀疏。为什么 L2 正则不利于稀疏化？因为 L2 出现在上式的分母中，它越小越不稀疏。如果要更准确地实现稀疏，应该以为正则项，它既最小化 L1，又最大化 L2，直接优化稀疏指标。

熵的联系

现在回到注意力矩阵上，它的特点是每一行对应一个概率分布，即自动满足且。最确定的概率分布是 one hot 分布，此时它也最稀疏；最不确定的分布是均匀分布，很显然此时它也最不稀疏。从这两个极端可以猜测，概率分布的稀疏性与不确定性有一定的关联。

我们知道，概率分布的不确定性一般用（香侬）熵来度量：

而此时指标（13）则变为，它是范数的衍生物。既然稀疏性与不确定性可能有一定的关联，那么是否意味着熵与范数存在一定程度的相关性呢？

确实如此。事实上，基于范数我们可以构造出 Rényi 熵 [5]：

可以证明

，即时正好对应于经典的香侬熵，而当时就是一般的 Rényi 熵（有些场景 Rényi 熵也特指时的情形）。每种 Rényi 熵都可以作为不确定性的某种度量，它们的值域都是，都是在 one hot 分布取的最小值、在均匀分布取得最大值。从这个意义上来说，所有的 Rényi 熵在一定程度上都是等价的，这就解释了熵与范数的关联。