如何度量数据的稀疏程度?
By 苏剑林 | 2023-05-05 | 31204位读者 |在机器学习中,我们经常会谈到稀疏性,比如我们经常说注意力矩阵通常是很稀疏的。然而,不知道大家发现没有,我们似乎从没有给出过度量稀疏程度的标准方法。也就是说,以往我们关于稀疏性的讨论,仅仅是直观层面的感觉,并没有过定量分析。那么问题来了,稀疏性的度量有标准方法了吗?
经过搜索,笔者发现确实是有一些可用的指标,比如$l_1/l_2$、熵等,但由于关注视角的不同,在稀疏性度量方面并没有标准答案。本文简单记录一下笔者的结果。
基本结果 #
狭义上来讲,“稀疏”就是指数据中有大量的零,所以最简单的稀疏性指标就是统计零的比例。但如果仅仅是这样的话,注意力矩阵就谈不上稀疏了,因为softmax出来的结果一定是正数。所以,有必要推广稀疏的概念。一个朴素的想法是统计绝对值不超过$\epsilon$的元素比例,但这个$\epsilon$怎么确定呢?
1相比于0.0001很大,但是相比10000又很小,所以大和小的概念不是绝对的。直观来想,稀疏的向量存在很多接近于零的数,那么它的绝对值的平均肯定会比较小,又因为大和小的概念是相对的,我们不妨将这个平均值跟最大值做除法,以获得相对结果,所以一个看上去比较合理的指标是
\begin{equation}S_0(\boldsymbol{x})=\frac{(|x_1|+|x_2|+\cdots+|x_n|)/n}{\max(|x_1|,|x_2|,\cdots,|x_n|)}\label{eq:start}\end{equation}
其中$\boldsymbol{x}=[x_1,x_2,\cdots,x_n]\in\mathbb{R}^n$是需要评估稀疏性的向量(下面都假设$\boldsymbol{x}$并非全等向量,即至少有两个不同的元素),指标越小的向量越稀疏。不过,尽管这个指标有一定的合理性,但它却不够“光滑”,主要是$\max$这个操作极易受到异常值的影响,不能很好地反应数据统计特性。
光滑齐次 #
于是,我们按照《寻求一个光滑的最大值函数》的思路,将$\max$换成它的光滑近似。$\max$标准的光滑近似是$\text{logsumexp}$:
\begin{equation}\max(|x_1|,|x_2|,\cdots,|x_n|)\approx \frac{1}{k}\log\sum_{i=1}^n e^{k|x_i|}\end{equation}
然而,如果这里用$\text{logsumexp}$替代$\max$,并不能起到较好的改进效果。一是因为有$e^{k|x_i|}$的放大作用,$\text{logsumexp}$同样容易受到异常值的影响,二是因为$\text{logsumexp}$没有正齐次性,反而不美(所有$x_i$乘以正数$\alpha$,稀疏性应该不改变)。在《寻求一个光滑的最大值函数》中我们也给出了一个$\max$的具备正齐次性的光滑近似,它正好是$l_p$范数($p > 1$):
\begin{equation}\max(|x_1|,|x_2|,\cdots,|x_n|)\approx \left(\sum_{i=1}^n |x_i|^p\right)^{1/p}\triangleq l_p(\boldsymbol{x})\end{equation}
再次观察式$\eqref{eq:start}$,我们可以发现它的分子正好是$l_1(\boldsymbol{x}) / n$,所以综合上面的结果,我们得到了度量稀疏性的一个指标为
\begin{equation}S_{1,p}(\boldsymbol{x})=\frac{l_1(\boldsymbol{x})/n}{l_p(\boldsymbol{x})}\label{eq:s1p}\end{equation}
如果只是固定维度的向量比较,那么$/n$可以略掉。常见的是取$p=2$,那么就得到稀疏性度量的$l_1/l_2$指标;如果取$p\to\infty$,那么其实就是指标$\eqref{eq:start}$。
理想性质 #
在《“熵”不起:从熵、最大熵原理到最大熵模型(一)》介绍“熵”的概念时,我们发现可以通过几条熵应当具备的理想性质来把熵的数学形式确定下来。那么稀疏性可否效仿这一点呢?
论文《Comparing Measures of Sparsity》做了这方面的尝试,它提出稀疏性度量$S(\boldsymbol{x})$应该具备以下几点理想性质(不失一般性,这里假设$\boldsymbol{x}$是非负向量,如果不是的话,逐项取绝对值即可):
D1、$S([\cdots,x_i - \alpha,\cdots,x_j + \alpha,\cdots]) > S(\boldsymbol{x})$,其中$x_i > x_j$且$0 < \alpha < \frac{x_i - x_j}{2}$。这点性质说的是如果总和不变,那么越均匀越不稀疏。
D2、$S(\alpha\boldsymbol{x}) = S(\boldsymbol{x})$,其中$\alpha > 0$。这点容易理解,就是指稀疏是一个相对的性质,所有元素乘以一个相同的倍数,不改变相对大小,也就不改变稀疏性。
D3、$S(\alpha + \boldsymbol{x}) > S(\boldsymbol{x})$,其中$\alpha > 0$。这点也容易理解,全体元素加上一个正数,那么全体都更加远离了零,稀疏性自然要降低。
D4、$S(\boldsymbol{x}) = S(\boldsymbol{x}\circ\boldsymbol{x}) = S(\boldsymbol{x}\circ\boldsymbol{x}\circ\boldsymbol{x}) = \cdots$,这里的$\circ$指两个向量拼接。这点也不难理解,就是单纯的数据复制不改变稀疏性。
P1、任意给定$i\in\{1,2,\cdots,n\}$,存在$\beta_i > 0$,使得对于任意$\alpha > 0$,都有$S([\cdots,x_{i-1},x_i + \beta_i + \alpha,x_{i
+1},\cdots]) < S([\cdots,x_{i-1},x_i + \beta_i,x_{i+1},\cdots])$。这条性质想表达的是当某个元素足够大的时候,整个向量的稀疏性就由它主导了。P2、$S(\boldsymbol{x}\circ[0]) < S(\boldsymbol{x})$。这个就很朴素了,给向量添加零,应该导致稀疏性增加。
原论文对稀疏性的各种常用指标做了推导,发现只有一个名为“Gini指数”的指标同时满足以上6点性质(但这个Gini指数比较复杂,这里就不介绍了)。不过要提醒读者的是,读原论文时需要仔细留意一下推导过程,因为笔者发现它证明$l_1/l_2$不满足D3的证明是错的,事实上$l_1/l_2$是满足D3的,至于其他推导笔者也没有细看,读者请在阅读过程中自行甄别正误。
参考证明 #
对于本文的两个指标,指标$\eqref{eq:start}$同时满足除D1外的另外5点性质(如果D1的$ > $改为$\geq $,那么也满足),这些性质的判断是比较平凡的,这里不详细讨论了,请读者自行完成。
至于指标$\eqref{eq:s1p}$,可以证明它同时满足除D4外的另外5点性质,其中D3、P1的证明稍微复杂一些,这里给出它们的参考证明。
为了证明D3,只需要证明
\begin{equation}\frac{\left(\sum\limits_{i=1}^n (x_i + \alpha)\right)^p}{\sum\limits_{i=1}^n (x_i + \alpha)^p}\end{equation}
关于$\alpha > 0$是单调递增的。两边取对数,得到
\begin{equation}p\log\sum\limits_{i=1}^n (x_i + \alpha) - \log\sum\limits_{i=1}^n (x_i + \alpha)^p\triangleq f(\alpha)\end{equation}
我们只需要证明$f'(\alpha) > 0$。直接求导得到
\begin{equation}f'(\alpha) = \frac{pn}{\sum\limits_{i=1}^n (x_i + \alpha)} - \frac{p\sum\limits_{i=1}^n (x_i + \alpha)^{p-1}}{\sum\limits_{i=1}^n (x_i + \alpha)^p}\end{equation}
$f'(\alpha) > 0$等价于
\begin{equation}\frac{1}{n}\sum\limits_{i=1}^n (x_i + \alpha)^p > \left(\frac{1}{n}\sum\limits_{i=1}^n (x_i + \alpha)\right)\left(\frac{1}{n}\sum\limits_{i=1}^n (x_i + \alpha)^{p-1}\right)\end{equation}
这由幂均值不等式直接可得。
P1的证明思路是类似的,只需要证明当$x_i$足够大的时候,
\begin{equation}\frac{\left(x_i + \alpha + \sum\limits_{j\neq i} x_j\right)^p}{(x_i + \alpha)^p + \sum\limits_{j\neq i} x_j^p}\end{equation}
关于$\alpha > 0$是单调递减的。两边取对数,得到
\begin{equation}p\log\left(x_i + \alpha + \sum\limits_{j\neq i} x_j\right) - \log\left((x_i + \alpha)^p + \sum\limits_{j\neq i} x_j^p\right)\triangleq g(\alpha)\end{equation}
我们只需要证明$g'(\alpha) < 0$。直接求导得到
\begin{equation}g'(\alpha) = \frac{p}{x_i + \alpha + \sum\limits_{j\neq i} x_j} - \frac{p (x_i + \alpha)^{p-1}}{(x_i + \alpha)^p + \sum\limits_{j\neq i} x_j^p}\end{equation}
$g'(\alpha) < 0$等价于
\begin{equation}p \sum\limits_{j\neq i} x_j^p < p(x_i+\alpha)^{p-1}\sum\limits_{j\neq i} x_j\end{equation}
只要各$x_j$并非全零,那么当$x_i$足够大时,总可以使得上式对$\forall \alpha > 0$恒成立。
完美指标 #
尽管指标$\eqref{eq:s1p}$不满足D4,但我们将它简单修改为
\begin{equation}S_{1,p}^*(\boldsymbol{x})=\frac{l_1(\boldsymbol{x})/n}{l_p(\boldsymbol{x})/n^{1/p}}=n^{(1-p)/p}\frac{l_1(\boldsymbol{x})}{l_p(\boldsymbol{x})}\label{eq:s1p-plus}\end{equation}
后,它是满足D4的,并且也可以检验它也满足P2,至于其他几点性质并不涉及到维度$n$的改变,因此跟指标$\eqref{eq:s1p}$一样也满足。也就是说,$S_{1,p}^*(\boldsymbol{x})$是同时满足6点性质的“完美指标”!
由幂均值不等式可知$l_p(\boldsymbol{x})/n^{1/p} \geq l_1(\boldsymbol{x})/n$,所以$S_{1,p}^*(\boldsymbol{x})\leq 1$;此外,由于
\begin{equation}\frac{l_p(\boldsymbol{x})}{l_1(\boldsymbol{x})}=\left(\left(\frac{x_1}{l_1(\boldsymbol{x})}\right)^p+\cdots+\left(\frac{x_n}{l_1(\boldsymbol{x})}\right)^p\right)^{1/p}\leq\left(\frac{x_1}{l_1(\boldsymbol{x})}+\cdots+\frac{x_n}{l_1(\boldsymbol{x})}\right)^{1/p}=1\end{equation}
所以$S_{1,p}^*(\boldsymbol{x})\geq n^{(1-p)/p}$,综上即$S_{1,p}^*(\boldsymbol{x})\in[n^{(1-p)/p},1]$。此外,$S_{1,p}^*(\boldsymbol{x})$还可以更一般地推广为:
\begin{equation}S_{q,p}^*(\boldsymbol{x})=\frac{l_q(\boldsymbol{x})/n^{1/q}}{l_p(\boldsymbol{x})/n^{1/p}}=n^{1/p-1/q}\frac{l_q(\boldsymbol{x})}{l_p(\boldsymbol{x})}\in\left[n^{1/p-1/q},1\right]\end{equation}
只要$p > q > 0$,那么它也是符合6点性质的“完美指标”。
当$p=2,q=1$时,有
\begin{equation}S_{1,2}^*(\boldsymbol{x})=\frac{1}{\sqrt{n}}\frac{l_1(\boldsymbol{x})}{l_2(\boldsymbol{x})}\in\left[\frac{1}{\sqrt{n}},1\right]\end{equation}
这个结果可以回答关于稀疏化的一些问题。比如为什么L1正则有利于稀疏化?因为L1出现在上式的分子中,它越小越稀疏。为什么L2正则不利于稀疏化?因为L2出现在上式的分母中,它越小越不稀疏。如果要更准确地实现稀疏,应该以$S_{1,2}^*(\boldsymbol{x})$为正则项,它既最小化L1,又最大化L2,直接优化稀疏指标。
特别地,当$\boldsymbol{x}$全不为零时,我们还有关系式
\begin{equation}S_{1,2}^*(\boldsymbol{x})=\cos(\text{sign}(\boldsymbol{x}),\boldsymbol{x})\end{equation}
其中$\text{sign}$是对向量的每一个分量都取符号函数。这个式子很形象,$\text{sign}(\boldsymbol{x})$可以说是$\boldsymbol{x}$的最稠密的衍生向量,稀疏程度就是$\boldsymbol{x}$与最稠密那个衍生向量的相似度,相似度越小自然是代表越稀疏。
如果我们将$\boldsymbol{x}$的元素视为随机变量$x$的采样结果,那么还可以写出
\begin{equation}S_{1,2}^*(\boldsymbol{x})=\frac{\mathbb{E}[|x|]}{\sqrt{\mathbb{E}[x^2]}}=\frac{\mathbb{E}[|x|]}{\sqrt{\mathbb{E}[|x|]^2 + \mathbb{V}ar[|x|]}} = \frac{1}{1 + \mathbb{V}ar[|x|] / \mathbb{E}[|x|]^2}\end{equation}
单独拎出来,$\frac{\mathbb{E}[|x|]}{\sqrt{\mathbb{V}ar[|x|]}}$的平方正是$|x|$的“信噪比”(均值平方与方差之比),所以这告诉我们“$|x|$的信噪比越低,那么$x$就越稀疏”。
熵的联系 #
现在回到注意力矩阵上,它的特点是每一行对应一个概率分布,即自动满足$x_i \geq 0$且$x_1+\cdots+x_n=1$。最确定的概率分布是one hot分布,此时它也最稀疏;最不确定的分布是均匀分布,很显然此时它也最不稀疏。从这两个极端可以猜测,概率分布的稀疏性与不确定性有一定的关联。
我们知道,概率分布的不确定性一般用(香侬)熵来度量:
\begin{equation}H(\boldsymbol{x}) = -\sum_{i=1}^n x_i \log x_i\in[0,\log n] \end{equation}
而此时指标$\eqref{eq:s1p-plus}$则变为$\frac{n^{(1-p)/p}}{l_p(\boldsymbol{x})}$,它是$l_p$范数的衍生物。既然稀疏性与不确定性可能有一定的关联,那么是否意味着熵与$l_p$范数存在一定程度的相关性呢?
确实如此。事实上,基于$l_p$范数我们可以构造出Rényi熵:
\begin{equation}H_p(\boldsymbol{x}) = -\frac{1}{p-1}\log \sum_{i=1}^n x_i^p \end{equation}
可以证明$H_1(\boldsymbol{x}) = \lim\limits_{p\to 1} H_p(\boldsymbol{x}) = H(\boldsymbol{x})$,即$p\to 1$时正好对应于经典的香侬熵,而当$p \neq 1$时就是一般的Rényi熵(有些场景Rényi熵也特指$p=2$时的情形)。每种Rényi熵都可以作为不确定性的某种度量,它们的值域都是$[0,\log n]$,都是在one hot分布取的最小值、在均匀分布取得最大值。从这个意义上来说,所有的Rényi熵在一定程度上都是等价的,这就解释了熵与$l_p$范数的关联。
值得一提的是,$p \neq 1$时的Rényi熵往往对数值计算更加友好,这是因为$\sum\limits_{i=1}^n x_i^p$必然是一个正的、有界的结果,$\log$运算不用担心$\log 0$问题,而且只需要对最后的结果做一次$\log$;相反标准的香侬熵,需要对每个$x_i$都算$\log$,计算量增加而且还要特别$\text{clip}$一下以防$\log 0$的出现。
文章小结 #
本文系统整理了一下关于稀疏性的度量问题,并且讨论了它与L1、L2、熵等概念的联系。
转载到请包括本文地址:https://kexue.fm/archives/9595
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (May. 05, 2023). 《如何度量数据的稀疏程度? 》[Blog post]. Retrieved from https://kexue.fm/archives/9595
@online{kexuefm-9595,
title={如何度量数据的稀疏程度?},
author={苏剑林},
year={2023},
month={May},
url={\url{https://kexue.fm/archives/9595}},
}
May 6th, 2023
应该有个笔误,幂均值不等式中,p次均值应该是大于等于1次均值,这样后面的推导才成立
已经修正,感谢指出。
May 13th, 2023
稀疏性会不会也和用来优化$l_1(x)$的算法有关?比如用proximal gradient (soft thresholding) 算法来优化Lasso, 优化的结果是有一些$x_i$会恰好等于$0$。但是如果用另外的算法(比如:subgradient),那么就不会出现“有一些$x_i$恰好等于$0$”的情况。
但这里讨论的稀疏性,并非绝对等于0才稀疏。另外,从数值计算的角度来说,除非模型做了特殊设计(比如加了relu),否则绝对等于0的概率几乎为零。
May 30th, 2023
您好,本人学渣,想问一下您这个稀疏的度量可以加入到损失函数当中作为神经网络训练过程中的稀疏约束吗?
它本身是可导的,所以应该可以吧。不过我没有尝试过。
请问,矩阵的稀疏程度可以用此度量吗?
一般情况下可以,就当向量来处理就行。
您的这个方法对我的可以帮助很大,请问可以在我的毕业论文里对您致谢吗?博客文章好像不能作为参考文献。
可以,谢谢。
December 14th, 2023
你好,我搜了下这个l1 /l2,和这个论文说的l1 l2 norm ratio被用于鼓励稀疏性和这个相关吗
Ratio and Difference of l1 and l2 Norms and Sparse Representation with Coherent Dictionaries:"The ratio of l1 and l2 norms is a widely used empirical non convex scale invariant penalty for encouraging sparsity for non convex problems such as non negative matrix factorization(NMF) and blind deconvolution applications"
是的,应该是同一意思。
February 27th, 2024
想问下怎么去算一个矩阵的稀疏性,看奇异值的稀疏性?
就当是向量就行了吧
November 29th, 2024
想简单和苏神探讨一下,我其实想衡量一下注意力稀疏性(后文都针对于注意力向量而言)然后问GPT给我说l1-l2 ratio可以衡量稀疏性,然后我将$\frac{l_{2}(x)}{l_{1}(x)}$做一个值域变换的时候意外发现了这个指标其实是个完美指标的。首先$\frac{l_{2}(x)}{l_{1}(x)}$的值域是$[\frac{1}{\sqrt{n}}, 1]$,然后我想将其变成值域为$[0, 1]$。就做了个非常简单的变换:
\begin{equation}
\frac{1}{\sqrt{n}} \le \frac{l_{2}(x)}{l_{1}(x)} \le 1, \\
0 \le \frac{l_{2}(x)}{l_{1}(x)} - \frac{1}{\sqrt{n}} \le \frac{\sqrt{n} - 1}{\sqrt{n}}, \\
0 \le \frac{l_{2}(x)}{l_{1}(x)} - \frac{1}{\sqrt{n}} \le \frac{\sqrt{n} - 1}{\sqrt{n}}, \\
0 \le \frac{\sqrt{n}}{\sqrt{n} - 1} (\frac{l_{2}(x)}{l_{1}(x)} - \frac{1}{\sqrt{n}}) \le 1, \\
0 \le \frac{1}{\sqrt{n} - 1} (\sqrt{n} \frac{l_{2}(x)}{l_{1}(x)} - 1) \le 1, \\
\end{equation}
然后我发现这指标有个很不好的地方就是连D4都不满足,但是我后面一看中间那玩意儿$\sqrt{n} \frac{l_{2}(x)}{l_{1}(x)}$好像全都满足,当然看起来算是苏神推导的一个特例。因为注意力向量${l_{1}(x)}=1$,所以可以简写为$\sqrt{n} \cdot l_{2}(x)$,这个指标的值域为$[1, \sqrt{n}]$,本来是想找个值域为$[0, 1]$均匀分布的指标可以直观体现稀疏性的,看起来好像是找不到的。
这个指标的问题在于它并不是一个均匀分布,这个时候我们就只能说算出来值接近1向量就越不稀疏,越接近$\sqrt{n}$就越稀疏。那么问题就来了,它到底稀疏程度是多少呢,这里我将稀疏程度定义为:穷举该n维度向量算出所有稀疏值,$S(x)$这个值所在的分位。这样就很好量化了,比如说一个向量$S(x)$稀疏程度为80%,就是说它超过了80%同维向量的稀疏值,这是一个高稀疏的向量。那这个分位点该怎么计算呢,想了一晚上发现其实S(x)是一个带约束的多元函数:
\begin{equation}
S(x) = \sqrt{n} \cdot \sqrt{x_{1}^2 + x_{2}^2 + ... + x_{n}^2}, \\
\text{其中} \ x_{1} + x_{2} + ... + x_{n} = 1, \\
\end{equation}
这玩意能算出来分位点吗,理论上其实是可以的,先用二维举例
\begin{equation}
\begin{aligned}
S(x) &= \sqrt{2} \cdot \sqrt{x_{1}^2 + x_{2}^2}, \\
&= \sqrt{2} \cdot \sqrt{x_{1}^2 + (1 - x_{1})^2}, \\
&= \sqrt{2} \cdot \sqrt{2x_{1}^2 - 2x_{1} + 1}, \text{其中} x_{1} \in [0, 1]
\end{aligned}
\end{equation}
那么80分位点就很简单了,$x_{1}=0.1$或者$x_{1}=0.9$时的函数值$S(x)=\sqrt{1.64}$。同理可以扩展到n维的情况,当然这个会稍微有点麻烦,但是个人感觉这条路子就可以定量的衡量稀疏程度了,想问下苏神这个思路有问题吗
@Jincheng Dai|comment-25863
又想了一下,算高维好像非常简单,假如要算$t$分位(比如t=80%),对于n维向量$x = {x_{1}, x_{2}, ..., x_{n}}$,只需要求解一个方程:
\begin{equation}
(1-2m)^{n-1} = t * 1
\end{equation}
求解$m$的值然后$x = (m, m, ..., 1-nm)$带入指标算$S(x)$的值就是t分位值了
November 29th, 2024
@Jincheng Dai|comment-25864
前提是需要$S(x)$的曲面图一定是一个对称的曲面图,这个我倒没细看了
看了下好像算高维这个解不对,我再研究一下能不能解这个值