How to Measure the Sparsity of Data?

如何度量数据的稀疏程度？ 苏剑林 · 2023-05-05 · Mathematics probability entropy metric sparse

In machine learning, we often talk about sparsity — for example, we frequently say that attention matrices are usually very sparse. However, I wonder if you've noticed that we seem to have never given a standard way of measuring the degree of sparsity. In other words, our past discussions about sparsity have only ever been intuitive impressions, without any quantitative analysis. So the question arises: is there a standard method for measuring sparsity?

After some searching, I found that there are indeed some usable metrics, such as $l_1/l_2$, entropy, etc., but because people focus on different aspects, there is no single standard answer when it comes to measuring sparsity. This post simply records my own findings on the matter.

Basic results

In the narrow sense, "sparse" refers to data containing a large number of zeros, so the simplest sparsity metric is to count the proportion of zeros. But if that were all there was to it, attention matrices couldn't be considered sparse at all, since the output of softmax is always positive. So we need to generalize the notion of sparsity. One naive idea is to count the proportion of elements whose absolute value doesn't exceed $\epsilon$, but how do we determine this $\epsilon$?

1 is very large compared to 0.0001, but very small compared to 10000, so the notions of "large" and "small" aren't absolute. Intuitively, a sparse vector has many entries close to zero, so the average of its absolute values should be relatively small. And since "large" and "small" are relative notions, we might as well divide this average by the maximum value to obtain a relative quantity. So a seemingly reasonable metric is

\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}

where $\boldsymbol{x}=[x_1,x_2,\cdots,x_n]\in\mathbb{R}^n$ is the vector whose sparsity we want to evaluate (below we always assume $\boldsymbol{x}$ is not a constant vector, i.e., it has at least two distinct elements); the smaller this metric, the sparser the vector. However, although this metric has some reasonableness to it, it isn't "smooth" enough — mainly because the $\max$ operation is extremely sensitive to outliers and doesn't reflect the statistical properties of the data very well.

Smooth and homogeneous

So, following the approach in Seeking a Smooth Maximum Function, let's replace $\max$ with a smooth approximation of it. $\max$'s standard smooth approximation is $\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}

However, if we replace $\text{logsumexp}$ with $\max$ here, it doesn't lead to a good improvement. One reason is that, due to the amplifying effect of $e^{k|x_i|}$, $\text{logsumexp}$ is likewise easily affected by outliers; the other is that $\text{logsumexp}$ lacks positive homogeneity, which is aesthetically unsatisfying (if all $x_i$ are multiplied by a positive number $\alpha$, sparsity should remain unchanged). In Seeking a Smooth Maximum Function we also gave a smooth approximation of $\max$ that has positive homogeneity, and it turns out to be exactly the $l_p$ norm ($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}

Looking again at equation $\eqref{eq:start}$, we can see that its numerator is exactly $l_1(\boldsymbol{x}) / n$, so putting the above results together, we arrive at a sparsity metric:

\begin{equation}S_{1,p}(\boldsymbol{x})=\frac{l_1(\boldsymbol{x})/n}{l_p(\boldsymbol{x})}\label{eq:s1p}\end{equation}

If we're only comparing vectors of a fixed dimension, then $/n$ can be dropped. A common choice is $p=2$, which gives the $l_1/l_2$ sparsity metric; if we take $p\to\infty$, this is actually the metric $\eqref{eq:start}$.

Ideal properties

In Entropy Isn't Boring: From Entropy and the Maximum Entropy Principle to the Maximum Entropy Model (Part 1), when introducing the concept of "entropy," we found that we could pin down the mathematical form of entropy by requiring a few ideal properties that entropy ought to satisfy. Can we do something similar for sparsity?

The paper Comparing Measures of Sparsity makes an attempt in this direction. It proposes that a sparsity measure $S(\boldsymbol{x})$ should have the following ideal properties (without loss of generality, assume here that $\boldsymbol{x}$ is a non-negative vector; if not, simply take the absolute value element-wise):

D1: $S([\cdots,x_i - \alpha,\cdots,x_j + \alpha,\cdots]) > S(\boldsymbol{x})$, where $x_i > x_j$ and $0 < \alpha < \frac{x_i - x_j}{2}$. This property says that if the total sum stays the same, then the more uniform the vector, the less sparse it is.
D2: $S(\alpha\boldsymbol{x}) = S(\boldsymbol{x})$, where $\alpha > 0$. This is easy to understand: sparsity is a relative property, and multiplying all elements by the same factor doesn't change their relative magnitudes, hence doesn't change sparsity.
D3: $S(\alpha + \boldsymbol{x}) > S(\boldsymbol{x})$, where $\alpha > 0$. This is also easy to understand: adding a positive number to every element moves everything further away from zero, so sparsity should naturally decrease.
D4: $S(\boldsymbol{x}) = S(\boldsymbol{x}\circ\boldsymbol{x}) = S(\boldsymbol{x}\circ\boldsymbol{x}\circ\boldsymbol{x}) = \cdots$, where $\circ$ denotes concatenation of two vectors. This isn't hard to understand either: simply duplicating the data shouldn't change sparsity.
P1: For any given $i\in\{1,2,\cdots,n\}$, there exists $\beta_i > 0$ such that for any $\alpha > 0$, we have $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])$. What this property expresses is that once some element is large enough, the sparsity of the whole vector is dominated by it.
P2: $S(\boldsymbol{x}\circ[0]) < S(\boldsymbol{x})$. This one is quite straightforward: appending zeros to a vector should increase its sparsity.

The original paper works out derivations for various commonly used sparsity metrics, and finds that only one, called the "Gini index," satisfies all six properties simultaneously (but the Gini index is fairly complicated, so I won't go into it here). That said, I should warn readers to read the derivations carefully, because I found that the paper's proof that $l_1/l_2$ fails to satisfy D3 is actually wrong — in fact $l_1/l_2$ does satisfy D3. As for the other derivations, I haven't checked them carefully either, so readers should verify correctness for themselves while reading.

Reference proofs

For the two metrics discussed in this post, the metric $\eqref{eq:start}$ satisfies all 5 properties other than D1 (and if D1's $ > $改为$\geq $, then it also satisfies D1). Checking these properties is fairly routine and I won't go through it in detail here — I leave it to the reader.

As for the metric $\eqref{eq:s1p}$, one can show it satisfies all 5 properties other than D4, where the proofs of D3 and P1 are a bit more involved. I give reference proofs for them here.

To prove
D3,
it suffices to show that
\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}
is monotonically increasing in $\alpha > 0$. Taking logarithms of both sides gives
\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}
We only need to show that $f'(\alpha) > 0$. Differentiating directly gives
\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$ is equivalent to
\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}
which follows directly from the
power mean inequality.

The proof idea for
P1
is similar: it suffices to show that when $x_i$ is sufficiently large,
\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}
is monotonically decreasing in $\alpha > 0$. Taking logarithms of both sides gives
\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}
We only need to show that $g'(\alpha) < 0$. Differentiating directly gives
\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$ is equivalent to
\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}
As long as the $x_j$ are not all zero, when $x_i$ is sufficiently large we can always make the above hold for all $\forall \alpha > 0$.

A perfect metric

Although the metric $\eqref{eq:s1p}$ does not satisfy D4, if we simply modify it to

\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}

then it does satisfy D4, and one can also check that it satisfies P2. Since the remaining properties don't involve any change in dimension $n$, it satisfies them just as $\eqref{eq:s1p}$ does. In other words, $S_{1,p}^*(\boldsymbol{x})$ is a "perfect metric" that simultaneously satisfies all 6 properties!

By the power mean inequality we know that $l_p(\boldsymbol{x})/n^{1/p} \geq l_1(\boldsymbol{x})/n$, so $S_{1,p}^*(\boldsymbol{x})\leq 1$; furthermore, since

\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}

we have $S_{1,p}^*(\boldsymbol{x})\geq n^{(1-p)/p}$, and combining these gives $S_{1,p}^*(\boldsymbol{x})\in[n^{(1-p)/p},1]$. Moreover, $S_{1,p}^*(\boldsymbol{x})$ can be generalized further as:

\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}

As long as $p > q > 0$, this is also a "perfect metric" satisfying all 6 properties.

When $p=2,q=1$, we have

\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}

This result can answer some questions about sparsification. For instance, why does L1 regularization encourage sparsity? Because L1 appears in the numerator of the above expression — the smaller it is, the sparser. Why does L2 regularization discourage sparsity? Because L2 appears in the denominator — the smaller it is, the less sparse. If one wants to promote sparsity more precisely, one should use $S_{1,2}^*(\boldsymbol{x})$ as the regularization term, since it simultaneously minimizes L1 and maximizes L2, directly optimizing the sparsity metric.

In particular, when all of $\boldsymbol{x}$ are nonzero, we also have the relation

\begin{equation}S_{1,2}^*(\boldsymbol{x})=\cos(\text{sign}(\boldsymbol{x}),\boldsymbol{x})\end{equation}

where $\text{sign}$ denotes taking the sign function of each component of the vector. This equation is quite illustrative: $\text{sign}(\boldsymbol{x})$ can be seen as the "densest" derived vector of $\boldsymbol{x}$, and the degree of sparsity is precisely the similarity between $\boldsymbol{x}$ and this densest derived vector — the smaller the similarity, naturally the sparser it is.

If we regard the elements of $\boldsymbol{x}$ as sampled values of a random variable $x$, then we can also write

\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}

Taken on its own, the square of $\frac{\mathbb{E}[|x|]}{\sqrt{\mathbb{V}ar[|x|]}}$ is precisely the "signal-to-noise ratio" of $|x|$ (the ratio of the squared mean to the variance), so this tells us: "the lower the signal-to-noise ratio of $|x|$, the sparser $x$ is."

Connection to entropy

Now let's go back to attention matrices. Their defining characteristic is that each row corresponds to a probability distribution, i.e., it automatically satisfies $x_i \geq 0$ and $x_1+\cdots+x_n=1$. The most deterministic probability distribution is the one-hot distribution, which is also the sparsest; the most uncertain distribution is the uniform distribution, which is clearly also the least sparse. From these two extremes, we might guess that the sparsity of a probability distribution is related to its uncertainty in some way.

We know that the uncertainty of a probability distribution is generally measured by (Shannon) entropy:

\begin{equation}H(\boldsymbol{x}) = -\sum_{i=1}^n x_i \log x_i\in[0,\log n] \end{equation}

and in this case the metric $\eqref{eq:s1p-plus}$ becomes $\frac{n^{(1-p)/p}}{l_p(\boldsymbol{x})}$, which is a derivative of the $l_p$ norm. Since sparsity and uncertainty may be related, does that mean entropy and the $l_p$ norm have some degree of correlation?

Indeed they do. In fact, based on the $l_p$ norm, we can construct the Rényi entropy:

\begin{equation}H_p(\boldsymbol{x}) = -\frac{1}{p-1}\log \sum_{i=1}^n x_i^p \end{equation}

One can show that $H_1(\boldsymbol{x}) = \lim\limits_{p\to 1} H_p(\boldsymbol{x}) = H(\boldsymbol{x})$, i.e., $p\to 1$ corresponds exactly to the classical Shannon entropy, while $p \neq 1$ gives the general Rényi entropy (in some contexts "Rényi entropy" specifically refers to the case $p=2$). Each type of Rényi entropy can serve as some measure of uncertainty, and all of them have the range $[0,\log n]$, attaining their minimum at the one-hot distribution and their maximum at the uniform distribution. In this sense, all the Rényi entropies are, to some extent, equivalent — and this explains the connection between entropy and the $l_p$ norm.

It's worth noting that the Rényi entropy for $p \neq 1$ tends to be more numerically friendly, because $\sum\limits_{i=1}^n x_i^p$ is necessarily a positive, bounded result, so the $\log$ operation doesn't need to worry about the $\log 0$ issue, and we only need to take $\log$ once on the final result. In contrast, the standard Shannon entropy requires computing $\log$ for every $x_i$, which increases the computational cost, and we also need to be careful to $\text{clip}$ in order to avoid the appearance of $\log 0$.

Summary

This post has systematically laid out the question of how to measure sparsity, and discussed its connections to concepts such as L1, L2, and entropy.