Complex Distributions Emerging in Filtering and Compression

In filtering, each output is produced by a certain number of different inputs. We explore the statistics of this degeneracy in an explicitly treatable filtering problem in which filtering performs the maximal compression of relevant information contained in inputs (arrays of zeros and ones). This problem serves as a reference model for the statistics of filtering and related sampling problems. The filter patterns in this problem conveniently allow a microscopic, combinatorial consideration. This allows us to find the statistics of outputs, namely the exact distribution of output degeneracies, for arbitrary input sizes. We observe that the resulting degeneracy distribution of outputs decays as $e^{-c{\log }^{\alpha }d}$ with degeneracy $d$, where $c$ is a constant and exponent $\alpha >1$, i.e., faster than a power law. Importantly, its form essentially depends on the size of the input dataset, appearing to be closer to a power-law dependence for small dataset sizes than for large ones. We demonstrate that for sufficiently small input dataset sizes typical for empirical studies, this distribution could be easily perceived as a power law. We extend our results to filter patterns of various sizes and demonstrate that the shortest filter pattern provides the maximum informative representations of the inputs.

Popular Summary

Cooperative systems such as spin glasses or deep-learning neural networks—where interactions among the components make the system more than the sum of its parts—characteristically have a complex landscape of basins of attraction for each final state. Because of the complexity of such systems, a deep understanding of the statistics of these phenomena has been elusive. Here, we introduce a simple filtering model of a cooperative system that displays the same complex statistics, but which can be calculated exactly up to relatively large system sizes.

Given an input sequence of ones and zeros, our filter produces an output marking the location of a certain short pattern. Each output may be degenerate, corresponding to multiple inputs, and the distribution of these degeneracies is broad and complex. We calculate the exact degeneracy distribution up to large input sizes and develop a theory to explain its various features. Similar distributions have been observed in deep-learning neural networks: They resemble power-law distributions for small input sizes. However, we show that the shape of the distribution depends crucially on the length of the input string and larger sizes diverge from the power-law shape.

The statistics of this problem are analogous to those in cooperative systems such as spin glasses or deep-learning neural networks. We believe our results can give insight into the statistics of problems in cooperative systems and stimulate new research aimed at the exploration of similar size effects in those systems.

Figure 1

(a) Filter extracting single ones and their positions from sequences of ones and zeros. Here the filter pattern is a single one. Ones and zeros are shown as black and white pixels, respectively. (b) A number of different inputs produce the same output. This number is the degeneracy of the output.

Figure 2

Degeneracy distribution and cumulative degeneracy distributions for alternative filters to the one used in our main results. (a),(b) Filter pattern 01010 for binary input strings of length $n=36$. (c),(d) Filter pattern 01010 for binary input strings of length $n=36$. (e),(f) Filter pattern 011010 for binary input strings of length $n=36$. (g),(h) Filter pattern (as illustrated herein) for 2D binary input grid of side length $L=6$ ($n=36$ entries total).

Figure 3

(a),(c),(e) Degeneracy distribution for the complete input dataset: number of outputs of a given degeneracy versus degeneracy. (b),(d),(f) Cumulative degeneracy distribution for the complete input dataset: number of outputs of degeneracy greater than or equal to a given degeneracy versus degeneracy. The input length is $n=21$, 50, 120. Open square symbols represent a mean-field approximation to the cumulative distribution, given by Eq. (38).

Figure 4

(a) Cumulative degeneracy distribution for $n=20$, 40, 60, 80, 100, 120. The black curves represent least-squares fittings of $\ln {\mathcal{N}}_{\mathrm{cum}}(d,n)$ as $\ln {\mathcal{N}}_{\mathrm{cum}}^{*}(n)+B_n{\ln }^{{\alpha }_n}d$ for each $n$. (b) Cumulative degeneracy distribution $\ln \{-\ln [{\mathcal{N}}_{\mathrm{cum}}(d,n)/{\mathcal{N}}_{\mathrm{cum}}^{*}(n)]\}$ versus $\ln \ln d$ for $n=20$, 40, 60, 80, 100, 120. Inset: Exponent $\alpha$ versus $1/n$.

Figure 5

The set of degeneracy values $d$ for each $n$ (logarithmic scale). (The range of $n$ was selected to make individual points visible.)

Figure 6

Total number of different degeneracies $D$ versus $n$ (symbols). The curve is the number of integer partitions of $n$ divided by $n$.

Figure 7

Number of distinct degeneracies less than or equal to $d$ versus $d$. Inset: Number of different degeneracies higher than or equal to $d$ versus $d$. The orange square symbols are full results for $n=120$. The circular blue symbols are values calculated in the limit $n\to \infty$ as described in Sec. 6. Solid black curve is the asymptotic approximation Eq. (33).

Figure 8

Double logarithmic scale plots of (a),(c),(e),(g) the degeneracy distributions and (b),(d),(f),(h) the cumulative degeneracy distributions obtained for randomly generated input datasets of different sizes $N$ for $n=21$ and $n=120$. The specific sizes of input datasets for $n=120$ are chosen to produce distributions similar to those for $n=21$.