Sparling: Learning Latent Representations with Extremely Sparse Activations

## Abstract

Abstract Real-world processes often contain intermediate state that can be modeled as an extremely sparse tensor. We introduce Sparling , a technique that allows you to learn models with intermediate layers that match this state from only end-to-end labeled examples (i.e., no supervision on the intermediate state). Sparling uses a new kind of informational bottleneck that enforces levels of activation sparsity unachievable using other techniques.
We find that extreme sparsity is necessary to achieve good intermediate state modeling. On our synthetic DigitCircle domain as well as the LaTeX-OCR and AudioMnistSequence domains, we are able to precisely localize the intermediate states up to feature permutation with > 90 % absent percent 90 >90\% > 90 % accuracy, even though we only train end-to-end.

## 1 Introduction

A hallmark of deep learning is its ability to learn useful intermediate representations of data from end-to-end supervision via backpropagation. However, these representations are often opaque, with components not referring to any semantically meaningful concepts. Many approaches have been proposed to address this problem.
For instance, concept bottlenecks leverage labels for the intermediate concepts (Koh et al. ()), and information bottlenecks require that that the mutual information between the representation and the input be bounded (Bourlard & Kamp ()). Here, we consider the constraint of extreme sparsity, which, when applicable, leads to a particularly effective approach to discovering the true underlying structure purely by training on end-to-end data.

We introduce Sparling, a novel technique for learning *extremely sparse representations*, where $\geq$99% of the activations are sparse for a given input. We are motivated by settings where components of the intermediate representation correspond to spatial concepts—which we call *motifs*—that occur in only a small number of locations. For instance, in a character recognition task, each motif may encode whether the center of a given character occurs at a given position. Since even in the worst case, an image of pure text, the image has orders of magnitude fewer characters than pixels, we expect the intermediate representation to be extremely sparse. This pattern is representative of many other prediction tasks—e.g., one could predict economic signals from satellite data by identifying a small number of building types, or transcribe sentences by reading words from noisy audio.

Sparling directly enforces sparsity by setting activations below some threshold equal to zero; this threshold is iteratively updated to achieve a target sparsity level (e.g., 99%). A key challenge is that the optimization problem is very unstable for high sparsity values. To address this issue, our optimization algorithm anneals the target sparsity over time. A byproduct of this approach is that we achieve a tradeoff between sparsity values and accuracies during the course of training, enabling the user to post-hoc choose a desired sparsity level.

Figure: Figure 1: Example of the DigitCircle domain. The input $x$ is mapped by the ground truth $g^{*}$ function to a map $m$ of the positions of every digit, which is itself mapped by the ground truth $h^{*}$ function to the output $y$, the sequence 072634. Only $x$ and $y$ are available during training.
Refer to caption: extracted/5186096/top-figure.png

Example.
Figure [1](#S1.F1) shows a sample task we call DigitCircle. The input consists of noisy images that contain digits placed in a circle, and the output is a list of the digits in counterclockwise order starting from the smallest one.

In addition to solving the end-to-end task, our goal is to train a network
with an intermediate layer that precisely identifies the positions of the individual digits in the image. Such an intermediate layer might be useful as a starting point for other tasks that require identifying digits. The challenge is to discover it in the absence of any training data labeling the individual digit locations.

Sparling is able to do this by exploiting the expectation of sparsity in this intermediate representation: we know the representation will be extremely sparse because the image contains many pixels but only a small number of digits. Specifically, our training technique is able to achieve nearly the maximum sparsity possible (99.9950%; the maximum sparsity possible for this domain is 99.9955%). Enforcing this level of sparsity forces the representation to identify the correct digit positions 98.84% of the time on average (up to permutation) while achieving end-to-end accuracy of 99.26%. Alternate sparsity enforcement techniques employing $L_{1}$ and KL-divergence loss
either do not produce extreme sparsity or have accuracy below 50%, and as a result, do not lead to intermediate layers that identify individual digits.

Contributions.
We contribute a new understanding of how enforcing extreme sparsity on an intermediate representation can be used to discover underlying structure. Additionally, we contribute Sparling, an algorithm for learning intermediate representations with extremely sparse activations, along with an empirical evaluation of the effectiveness of our approach.
In particular, we demonstrate that the high motif accuracy from end-to-end training
illustrated in DigitCircle
can be achieved on two other, more realistic, domains: LaTeX-OCR, in which we predict a LaTeX sequence from a noisy image of an algebraic expression, and AudioMnistSequence, in which we predict a number from noisy audio of digits being spoken. We will follow DigitCircle throughout the paper but present motif and end-to-end accuracy results on all 3 domains.

## 2 Related Work

Concept bottleneck models. There has been work on learning models with intermediate features that correspond to known variables. Some techniques, such as Concept Bottleneck Models (Koh et al. ()) and Concept Embedding Models (Zarlenga et al. ()), involve additional supervision with existing feature labels. Other techniques, such as Cross-Model Scene Networks (Aytar et al. ()), use multiple datasets with the same intermediate representation. Sparling does not require the presence of additional datasets or annotations.

Neural Input Attribution. Sparling is useful for identifying the relevant parts of an input. One existing technique that accomplishes this goal is saliency mapping (Simonyan et al. (); Selvaraju et al. ()), which uses
gradient techniques
to find which parts of the input affect the output most. Another technique, analyzing the attention weights of an attention layer (Mnih et al. ()), only works with a single layer of attention and does not necessarily produce valid or complete explanations (Serrano & Smith ()). The main benefit a sparse annotation provides over these techniques is unconditional independence: when using sparsity, you have the ability to make the claim “region $x[r]$ of the input is not relevant to the output prediction, regardless of what happens in the rest of the input $x[\bar{r}]$”. This is a direct result of sparsity and locality and is unavailable when using saliency or attention techniques which inherently condition on the values you provide for $x[\bar{r}]$.

Latent ground truth. While deep neural networks typically have inscrutable latent variables that are not intended to correspond to any understood feature, in other settings, such as graphical models, latent variables can often represent known quantites. For example, Hidden Markov Models are commonly used in genomics (Yoon ()), where hidden states represent various hidden features of an observed DNA or RNA sequence. Our work attempts to accomplish the same goal of having an interpretable latent variable, but without having to pre-specify what it means.

Disentangled representations. *Disentangled representations* are ones where different components of the representation encode independent attributes of the underlying data (Desjardins et al. (); Higgins et al. ()).
Some work suggests there are no universal solutions to this problem, and all attempts require some prior about the kinds of representations being disentangled (Locatello et al. ()). We focus here on a prior regarding sparsity and locality.

Informational bottleneck. Other work also constrains the information content of the intermediate representation in a neural network. Intuitively, by limiting the mutual information between the input and the the intermediate representation, the model must learn to
compress the input in a way that retains performance at the downstream prediction task.
Strategies include constraining the dimension of the representation—e.g., PCA and autoencoders with low-dimensional representations (Bourlard & Kamp ()), or adding noise—e.g., variational autoencoders (Kingma & Welling ()). However, these approaches do not always learn interpretable representations of an intermediate state, as they can encourage entangling features to communicate them through a smaller number of channels.

Sparse activations. Note that this notion of sparsity differs from *sparse parameters* (Tibshirani (); Scardapane et al. (); Ma et al. (); Lemhadri et al. ()); instead this line of work attempts to constrain the information content of an intermediate representation by encouraging *sparse activations*—i.e., each component of the representation is zero for most inputs. Strategies for achieving sparse activations include imposing an $L_{1}$ penalty on the representation or a penalty on the KL divergence between the representation’s distribution and a low-probability Bernoulli distribution (Jiang et al. ()). However, these techniques typically only achieve 50%-90% sparsity, whereas Sparling can achieve $>99.9\%$. We directly compare with these in Section [5.1](#S5.SS1). Additionally, Bizopoulos & Koutsouris () uses a quantile-based activation limit equivalent to both of our ablations (see Section [1](#S5.T1)) combined, but in the simpler context of linear $h$ and $g$ models.

## 3 Preliminaries

We are interested in settings where the activations are latent variables corresponding to semantically meaningful concepts in the prediction problem. To this end, we consider the case where the *ground truth* is represented as a function $f^{*}:X\to Y$ composed $f^{*}=h^{*}\circ g^{*}$ of two functions $g^{*}:X\to M$ and $h^{*}:M\to Y$. Our goal is to learn models $\hat{g}$ and $\hat{h}$ that model $g^{*}$ and $h^{*}$ well using only end-to-end data, i.e., enforcing only that their composition $\hat{f}=\hat{h}\circ\hat{g}$ models $f^{*}$ well.

We assume that elements of $X$ are tensors $\mathbb{R}^{d_{1}\times\ldots\times d_{k}\times C}$, and $Y$ is an arbitrary label space. We typically think of the $C$ dimension as a channel dimension and $d_{1}\ldots d_{k}$ as spatial dimensions (e.g., 2D images).
We call the latent space $M$ the *motif* space. We assume it shares spatial dimensions with $X$, but may have a different number of channels.
Importantly, we do not assume that $M$ is known—we may have little or no labeled data on which components of $M$ are active.

### 3.1 Motif Identifiability

For our approach to work, we require that the output of $g^{*}$ is *sparse*,
that $g^{*}$ is *local*, and that $g^{*}$ is *necessary*.
We define a motif model $g$ as sparse if its *density* $\delta_{g}$ is low, ideally close to the minimum necessary for a task. We define $\delta_{g}$ to be the mean fraction of output activations $g(x)$ that are nonzero.
Locality is the standard property where a component only depends on a small number of inputs — e.g., convolutional layers are local. Necessity is the property that $g^{*}$ only encodes aspects of the input necessary for computing $f^{*}$—intuitively, if $g^{*}$ outputs information that is never used by $h^{*}$ to compute its output, we can not hope to recover that information from end-to-end data on $f^{*}$.

While these constraints may appear strict, they fit problems where $g^{*}$ identifies small local patterns in the input—e.g. motifs such as the individual digits in DigitCircle—and $h^{*}$ computes something using all the information in those motifs. In these settings, we argue
that Motif Identifiability is possible. Specifically, we claim that if $g^{*}$ and $\hat{g}$ both satisfy sparsity, locality, and necessity, and $\hat{f}\approx f^{*}$, we can then conclude that $\hat{g}\approx_{m}g^{*}$. This claim implies that, for certain kinds of functions, it is possible to recover the underlying motifs with just end-to-end data.
This is an empirical claim, which we validate in our experiments.

### 3.2 Motif Model Equivalence and Evaluation Metrics

Evaluating Motif Identifiability requires a definition of approximate equivalence between motif models—i.e., what $\hat{g}\approx_{m}g^{*}$ means. In particular, the definition of equivalence needs to account for
channel permutations and motif alignment. For permutations, the learned motifs model should be deemed equivalent to the ground truth model—which is known when we test—if there exists a channel permutation for which they are equivalent.
Motif alignment is the problem that the exact “position” of a motif is arbitrary. To ensure we account for this flexibility when evaluating models, we only check that the predicted point be within the *footprint* of the true motif, which we define as the smallest cuboid(^1^11For images, the cuboid is a rectangle, as drawn in Figure [1](#S1.F1), for audio the cuboid is a temporal interval.) covering the points in the motif.

Next, we describe the metrics we use to evaluate different models $\hat{f}=\hat{g}\circ\hat{h}$. First, we use edit (Levenshtein) distance divided by length as our reported metric of end-to-end error:

$$ $\displaystyle\textsc{E2EE}_{\mathcal{D}}(\hat{f})=\mathbb{E}_{x\sim\mathcal{D} }\left[\frac{\textsc{EditDistance}(f^{*}(x),\hat{f}(x))}{\max(|f^{*}(x)|,|\hat {f}(x)|)}\right].$ $$

This error metric can be calculated given only end-to-end supervision in the form of $(x,y)$ pairs.
We then define three motif error metrics to evaluate $\hat{g}\approx_{m}g^{*}$; these metrics are only used for testing purposes, since they assume knowledge of the true motifs.

First, the *false positive error (FPE)* is the percentage of motifs that are false positive motifs.

$$ $\displaystyle\mathrm{FPE}_{\mathcal{D}}(\hat{g})=\frac{\sum_{x\in\mathcal{D}}| \mathrm{FPM}(\hat{g}(x),g^{*}(x))|}{\sum_{x\in\mathcal{D}}|P(\hat{g}(x))|}.$ $$

We define $P(\hat{m})$ as the set of all predicted motifs (PMs), and $\mathrm{FPM}(\hat{m},m^{*})$ is the set of PMs that do not overlap the footprints of any true motifs.
Second, the *false negative error (FNE)* is the percentage of true sites that are not covered by any motif.
Finally, the *confusion error (CE)* is defined as follows: (i) permute $\hat{g}$’s channels to best align them with $g^{*}$, (ii) compute the percentage of maximal motifs in footprint of a true motif that do not correspond to the true motif’s channel:

$$ $\displaystyle\mathrm{CE}_{\mathcal{D}}(\hat{g})=\min_{\sigma\in\Sigma_{C}} \frac{\sum_{x\in\mathcal{D}}|\mathrm{conf}_{\sigma}(\hat{g}(x),g^{*}(x))|}{ \sum_{x\in\mathcal{D}}|\mathrm{MM}(\hat{g}(x),g^{*}(x))|},$ $$

where
$\mathrm{MM}(\hat{m},m^{*})$ is the set of PMs that overlap a footprint of a true motif and have greater activation value than all other motifs overlapping the same footprint.(^2^22We ignore motifs not maximal in a footprint as these could be filtered by a user of the motif predictions.)
$\mathrm{conf}_{\sigma}(\hat{m},m^{*})$ represents the motifs that do not match ground truth under permutation $\sigma$

$$ $\displaystyle\mathrm{conf}_{\sigma}(\hat{m},m^{*})=\{t\in\mathrm{MM}(\hat{m},m ^{*}):\neg\mathrm{mat}_{\sigma}(t,C(t,m^{*}))\}|,$ $$

$\mathrm{mat}_{\sigma}(\hat{t},t^{*})$ is a function that checks whether the two motif index tuples match under channel permutation $\sigma$, and
$C((\hat{\mathbf{i}},\hat{c}),m^{*})$ is the footprint that the predicted motif at location $\hat{\mathbf{i}},\hat{c}$ matches, or $\emptyset$ if it does not match any.

A low FPE/FNE implies that the model is identifying relevant portions of the input, while a low CE implies that the model classifies these components as motifs correctly. Appendix [A](#A1)
contains formal definitions of the functions not defined formally here.

### 3.3 Connection to Information Bound

Sparsity induces an information bound by limiting the amount of information in the intermediate representation. Specifically, if we let $\mathcal{X}$ be a random variable for the input, and $\mathcal{M}=g(\mathcal{X})$ be the motif layer, we have that we can bound the mutual information between inputs and motifs as $I(\mathcal{X},\mathcal{M})\leq H(\mathcal{M})$, where $H(\cdot)$ is entropy.
Thus, to bound mutual information, it is sufficient to bound $H(\mathcal{M})$. We first can break it into per-channel components:
$H(\mathcal{M})\leq\sum_{\mathbf{i},c}H(\mathcal{M}[\mathbf{i},c]),$Then, let $\delta_{\mathbf{i},c}$
denote the density of channel $c$ at position $\mathbf{i}$, and $\eta\geq H(\mathcal{M}[\mathbf{i},c]|\mathcal{M}[\mathbf{i},c]\neq 0)$ be a bound on the amount of entropy in each nonzero activation (see Appendix [B](#A2)).
Then we apply the chain rule to get
$H(\mathcal{M}[\mathbf{i},c])\leq H(B(\delta_{\mathbf{i},c}))+\eta\delta_{
\mathbf{i},c}$
where $B(\cdot)$ is the Bernoulli distribution. Thus,
$H(\mathcal{M})\leq\sum_{\mathbf{i},c}H(B(\delta_{\mathbf{i},c}))+SC\eta\delta,$where $S$ is the size of the image in pixels and $C$ is the number of channels, and $\delta$ is defined as in section [3.1](#S3.SS1). Finally, using Jensen’s inequality (as $H(B(t))$ is concave):

$$ $\displaystyle I(\mathcal{X},\mathcal{M})\leq H(\mathcal{M})\leq SC(H(B(\delta) )+\eta\delta).$ $$

This demonstrates that a sparsity bound can be used as an information bound and thus that Sparling operates as a kind of informational bottleneck.

Figure: Algorithm 1 Train Loop $(\hat{f},\mathcal{D},M,B,d_{T},\delta_{\mathrm{update}})$

## 4 Methods

In this section, we introduce Sparling, which is composed of two parts: the Spatial Sparsity Layer and the Adaptive Sparsity Algorithm. The Spatial Sparsity Layer is designed to achieve the extreme sparsity levels described in Section [3](#S3). This layer is the last step in the computation of $\hat{g}$ and enforces the sparsity of $\hat{g}$; we compose $\hat{g}$ out of convolutional layers to enforce locality. The Adaptive Sparsity Algorithm is designed to ensure the Spatial Sparsity Layer can be effectively trained.

### 4.1 Spatial Sparsity Layer

We define a spatial sparsity layer to be a layer with a parameter $t$ whose forward pass is computed

$$ $\mathrm{Sparse}_{t}(z)=\mathrm{ReLU}(z-t)$ $$

Importantly, $t$ is treated as a constant in backpropagation and is thus not updated by gradient descent. Instead, we update $t$ using an exponential moving average of the quantiles of batches(^3^33For numerical stability, we accumulate batches such that $|z_{n}|\delta\geq 10C$ before running this update):

$$ $\displaystyle t_{n}=\mu t_{n-1}+(1-\mu)q(z_{n},1-\delta),$ $$

where $t_{n}$ is the value of $t$ on the $n$th iteration, $z_{n}$ is the nth batch of inputs to this layer, $\mu$ is the momentum (we use $\mu=0.9$), $\delta$ is the target density, and $q:\mathbb{R}^{B\times d_{1}\times\ldots\times d_{k}\times C}\times\mathbb{R}
\to\mathbb{R}^{C}$ is the standard torch.quantile function. $q$ is applied across all dimensions except the last: it produces a value for each channel that represents the threshold $u$ for which the proportion of elements above $u$ in the tensor at that channel is $\delta$. We describe an alternative in Appendix [D](#A4).
Since $t_{n}$ is fit to the data distribution, we can treat this as a layer that enforces that $\hat{g}$ has a sparsity of $1-\delta$.

Finally, we always include an affine batch normalization before this layer to increase training stability.
We provide an analysis on the necessity of this addition in Section [1](#S5.T1).

### 4.2 Adaptive Sparsity

In practice, we find that applying an extreme sparsity requirement (very low $\delta$) upon initial training of the network leads to bad local minima, with the network being unable to gain any learning signal on the vast majority of inputs. Instead, we use a technique inspired by simulated annealing and learning rate decay, and reduce $\delta$ slowly over time. Annealing hyperparameters is a known technique Sønderby et al. (), but we tie this annealing to validation accuracy (we use exact match between $y$ and $\hat{y}$) in order to automatically tune it and avoid introducing an additional hyperparameter.

Specifically, we add a step to our training loop that periodically checks validation accuracy $A_{t}$ and reduces the density whenever it exceeds a target $T_{t}$. The process is as described in Algorithm [1](#alg1), with the target accuracy dropping slowly. When the validation accuracy reaches the target accuracy, we reduce density and increase the accuracy bar to whatever our model achieved. Our experiments use evaluation frequency $M=2\times 10^{5}$, batch size $B=10$, $d_{T}=10^{-7}$, and $\delta_{\mathrm{update}}=0.75$.

## 5 Experiments

### 5.1 Experimental Setup

Figure: Figure 2: Examples of input/output pairs of our domains, along with the model’s motif predictions. The inputs are the images, and outputs are the sequences in the titles. For LaTeX-OCR, we provide the output twice, first as the sequence of commands generated by the network and second as the translation of those commands into LaTeX. We annotate in dots the maximal motifs produced by the $\hat{g}$ of the model with seed=1. We label our activations A through J or with number signs to distinguish them from digits. Stars indicate sites where there are non-maximal motifs present as well. Note that in the LaTeX domain, the symbols +() are not always recognized and that the fraction bar is never recognized: this is because these motifs are not needed to infer the LaTeX output.
Refer to caption: extracted/5186096/demo_with_dots.png

We have three domains, as described below. See Figure [2](#S5.F2) for examples of each domain.

DigitCircle domain. To evaluate Sparling we construct the DigitCircle domain. The input $X$ is a $100\times 100$ monochrome image with 3-6 unique digits placed in a rough circular pattern, with some noise being applied to the image both before and after the numbers are placed. The output $Y$ is the sequence of digits in counterclockwise order, starting with the smallest number. The latent motifs layer $M$ is the position of each digit: we can conceptualize this space as a $100\times 100\times 10$ tensor with 3-6 nonzero entries. Note that the model during training and validation has no access to the concept of a digit as an image, nor to the concept of a digit’s position.

LaTeX-OCR domain. To provide a more realistic test of our model’s capabilities we use the task of synthesizing LaTeX code from images. This task is similar to DigitCircle in that the motifs are digits, but these digits vary in size and pixel-level rendering, and the motif-to-output relationship is also more complex. This task is inspired by Deng et al. ().

AudioMnistSequence domain. In this domain, we synthesize short clips of audio representing sequences of 5-10 digits over a bed of noise. The task is to predict the sequence of characters spoken. Here, we test if motif models can generalize: we train and validate with AudioMNIST (Becker et al. ()) samples from Speakers 1-51 and test with samples from Speakers 52-60.

Architecture and training.
Our neural architecture is adapted from that of Deng et al. (). For DigitCircle, we make $\hat{g}$ have a $17\times 17$ overall window, by layering four residual units (He et al. ()), each containing two $3\times 3$ convolutional layers. We then map to a 10-channel bottleneck where our Spatial Sparsity layer is placed. (We choose 10 channels to match the 10 digits.) Our $\hat{h}$ architecture is a max pooling, followed by a similar architecture to Deng. We keep the LSTM row-encoder, but replace the attention decoder with a column-based positional encoding followed by a Transformer (Vaswani et al. ()) whose encoder and decoder have 8 heads and 6 layers. Throughout, except in the bottleneck layer, we use a width of 512 for all units. For LaTeX-OCR we use the same architecture but with 32 motifs (to account for the additional characters) and a $65\times 65$ overall window (to account for the larger characters)(^4^44In practice we find that using $33\times 33$ does not substantially change the results). For AudioMnistSequence we use a modification of this architecture designed for 1-dimensional data, processing the audio via a spectrogram with a sample rate of 8000 and 64 channels, and treating the signal as a 1-dimensional signal from there. We use a 33-wide 1D convolutional filter for the motifs and remove the LSTM from the post-sparse model, making it entirely a transformer. For comparisons to baselines and ablations we keep the model architecture fixed and only modify the Sparse layer.

We generate training datasets randomly, with seeds 1 through 9 for the 9 different training runs of each model, and seeds -1 and -2 being reserved for validation and testing. For efficiency, LaTeX-OCR is limited to $10^{7}$ training samples, after which it repeats. We use a batch size of 10 samples and a learning rate of $10^{-5}$. Our validation and test sets both contain $10^{4}$ examples.

Baselines. We consider two other approaches to ensuring the creation of sparse motifs, both taking the form of auxiliary regularization losses. In both cases, we vary loss weight to analyze how that affects error and sparsity. First, we consider $L_{1}$ loss. In our implementation, we use an affine batch normalization layer followed by a ReLU. The output of the ReLU is then used in an auxiliary $L_{1}$ loss(^5^55This approach parameterizes the same model class as Sparling; both act as a ReLU in a forward pass). This approach is discussed in Jiang et al. (). We also consider using $KL$-divergence loss as in Jiang et al. (). The approach is to apply a sigmoid, then compute a KL-divergence between the Bernoulli implied by the mean activation of the sigmoid and a target sparsity value (we use 99.995% to perform a direct comparison). While this usually is done across the training data Ng (), we instead enforce the loss across all positions and channels, but per-batch (the mean sparsity should be similar in each batch). Our other modification, in order to induce true sparsity, is to, after the sigmoid layer (where the loss is computed), subtract 0.5 and apply a ReLU layer.

Ablations. We consider two ablations: First, is the batch normalization we place before our sparse layer necessary? Second, is the adaptive sparsity algorithm we use necessary? These ablations are only evaluated on DigitCircle as it is the domain where simpler techniques would work best.

### 5.2 Results

Figure: Figure 3: Motif Error. Bar height depicts the mean across 9 seeds, while individual dots represent the individual values and the error bar represents a 95% bootstrap CI of the mean. AudioMnistSequence has an FPE of exactly 0, so it does not appear on the graph. High FNE on LaTeX-OCR is due to fraction bars, parentheses, and plus signs not being recognized in all cases since it is possible to infer the LaTeX code without access to these.
Refer to caption: extracted/5186096/all_motif_error.png

Motif error. We show our metrics of motif error, FNE, FPE, and CE in Figure [3](#S5.F3) for each of our models on each domain. Motif errors for our model average below 10% for all our domains, except in the case of FNE on LaTeX-OCR. The generally low motif errors, despite only training and validating end-to-end, demonstrate that our algorithm achieves Motif Identifiability on all three domains. This property even holds when generalizing to unseen samples in the AudioMnistSequence experiment, providing evidence that Sparling is genuinely learning the motif features rather than memorizing. The one case where our model has high error, FNE on LaTeX-OCR, demonstrates the importance of the Necessity Assumption: recognizing LaTeX text in the space we generated does not require identification of fraction bars or all of ()+. For more details, see Figures [2](#S5.F2) and [4](#S5.F4).

Examples. Figure [2](#S5.F2) shows a few examples for one of our models’ intermediate layers. As can be seen, all digits are appropriately identified by our intermediate layer, with very few dots (in these examples, none) falling away from a digit. Note that the activations are consistent from sample to sample—for example, in DigitCircle, motif C is used for digit 6 in both images.

Figure: Figure 4: Confusion Matrix of 10k unseen samples computed for seed=1 across all domains. False positive and false negative motifs are placed into the none rows and columns, respectively. Each row is labeled by the percentage of motifs falling into the row, and each row’s cells are then normalized to add to 1. We then permute to align along the diagonal. For LaTeX-OCR, we use more channels than there are symbol types so we merge channels together for display and analysis.
Refer to caption: extracted/5186096/confusion_all.png

Confusion matrices. Figure [4](#S5.F4), depicts appropriately permuted confusion matrices for each domain. Our model generally assigns each true motif to a channel or set of channels in the sparse layer. The main exception is that in LaTeX-OCR, the fraction bar is never recognized, and () are only sometimes recognized. In other seeds, + exhibits similar behavior to ().

Figure: Figure 5: Motif and end-to-end error metrics versus $\delta$. Note that the $x$ axis is reversed, this is to indicate training progression, which starts with high density and narrows it over time.
Refer to caption: extracted/5186096/error-vs-sparsity.png

Necessity of Extreme Sparsity
Figure [5](#S5.F5) shows our error metrics plotted against the sparsity, with the $x$-axis reversed to show progression in training time as we anneal $\delta$. As expected, as $\delta$ decreases, FPE decreases and FNE increases. More interestingly, we note a tradeoff between E2EE and CE: as $\delta$ decreases, E2EE increases and CE decreases substantially. This demonstrates a tradeoff between a more accurate overall model, which benefits from greater information present and a more accurate motif model, which benefits from a tighter entropy bound. Furthermore, CE is often substantially higher for even a 2-3$\times$ increase in $\delta$, demonstrating the need for extreme sparsity.

Baselines. Table [1](#S5.T1) shows the results of using $L_{1}$ as a method for encouraging sparsity. There are two weight regimes, where when $\lambda\leq 1$, we end up with high density (relative to the theoretical minimum) but low error, and when $\lambda\geq 2$, we end up with high-error model. Even in the latter case, the $L_{1}$ loss does not consistently push density down to the level of Sparling, suggesting it might be insufficiently strong as a learning signal. In our experiments, the $KL$-divergence was unable to achieve a density below 0.1%, even when we used a loss weight as high as $\lambda=10^{5}$ and $3\times 10^{6}$ steps (much more than was necessary for convergence of the $L_{1}$ model). Thus, we conclude that it is unsuitable for encouraging the kind of sparsity we are interested in.

**Table 1: Results of $L_{1}$ experiment on DigitCircle. As $L_{1}$ increases, the density decreases, but end-to-end error becomes $>50$%, and CE/FPE never improve to the level of Sparling. Sparling is able to keep error low while achieving lower density than $L_{1}$ with any $\lambda$ value we tried.**
|  | $L_{1}$ | Sparling |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
|  | $\lambda=0.1$ | $\lambda=1$ | $\lambda=2$ | $\lambda=5$ | $\lambda=10$ | $\mathrm{MT}$ |
| FPE [%] | 99.99 | 99.90 | 91.25 | 95.99 | 97.63 | 1.48 [0.07-4.23] |
| FNE [%] | 0.00 | 0.00 | 58.09 | 73.12 | 84.51 | 0.42 [0.25-0.67] |
| CE [%] | 50.34 | 47.84 | 45.65 | 50.85 | 33.82 | 1.16 [0.03-3.39] |
| E2EE [%] | 0.68 | 2.85 | 70.31 | 75.00 | 73.20 | 0.74 [0.47-1.15] |
| Density [%] | 37 | 4.7 | 0.023 | 0.032 | 0.028 | 0.005 |

Ablation We compare our approach to ablations to evaluate our design decisions. First, including a batch normalization before the sparsity layer is crucial. Without a batch normalization layer, over 9 runs, the best model gets an E2EE of 71%, in essence, it is not able to learn the task at all. Additionally, annealing (Algorithm [1](#alg1)) is clearly necessary: when started with the annealing algorithm’s final and penultimate $\delta$ values, the model converged to E2EE values of 68% and 71% respectively.

Figure: Figure 6: *Retrained* tends to perform as well as or slightly worse than *Non-Sparse*, making up most of the gap from Sparling
Refer to caption: extracted/5186096/all_e2e_error.png

End-to-End error As seen in Figure [6](#S5.F6), Sparling tends to produce higher end-to-end errors than a baseline Non-Sparse model. This is to be expected as we are imposing a constraint on the information flow that requires, the model to “commit” to a choice on whether or not a given site is a true motif. To control for this effect, we present the *Retrained* setting, in which we remove the bottleneck, freeze the motif model $\hat{g}$, and finetune $\hat{h}$ on the training set until convergence. The Retrained setting tends to perform similarly to or only slightly worse than the Non-Sparse setting. We thus demonstrate that we are not losing an unacceptable amount of performance end-to-end even as we are able to substantially improve the interpretability of the model.

## 6 Conclusion

Sparling is a novel spatial sparsity layer and adaptive sparsity training technique that has the ability to learn a highly sparse latent motifs layer for dimensional data using only an end-to-end training signal. Similar levels of activation sparsity are unachievable by existing strategies. We demonstrate that Sparling achieves interpretable and accurate motifs with zero direct supervision on the motifs. Finally, we demonstrate that Sparling is not specific to any particular domain: it works well across three different domains.

## 7 Acknowledgements

This material is based upon work supported by the National Science Foundation under Grant Nos. CCF-1918839 & CCF-1917852. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. This work was enriched by conversations with Christopher Burge, Phillip A. Sharp, Kayla McCue, and Chenxi Yang.

## Appendix A Evaluation Metric Details

We now define our $\mathrm{FPM}$ and $\mathrm{MM}$ motif sets, along with the $C$ function.

Predicted motifs. For a given predicted motif tensor $\hat{m}$, we define $P(\hat{m})=\{(\hat{\mathbf{i}},\hat{c}):\hat{m}[\hat{\mathbf{i}},\hat{c}]>0\}$ to be the set of motifs predicted in $\hat{m}$, where $\mathbf{i}$ is over all sequences of spatial indices (e.g., for images $\mathbf{i}:\mathbb{N}^{2}$) and $c$ is over the channel indices.
Typically, we are interested in the set of motifs $P(\hat{g}(x))$ for our estimated motif model $\hat{g}$.

Footprint. We can formally define the footprint of a motif as follows: Let a motif with $\mathbf{i}$ in channel $c$ have footprint $\mathbf{i}+F_{c}$. Note that $F_{c}$ depends on the channel of the true motif—e.g., in the DigitCircle domain, some digits are slightly larger than others.

Footprint identification.
First, we define a way to determine which footprint a motif belongs to.
Define the footprint motif function $S(\hat{\mathbf{i}},m^{*})$ to be the set of true motifs whose footprints contain $\hat{\mathbf{i}}$—i.e.,

$$ $\displaystyle S(\hat{\mathbf{i}},m^{*})=\{(\mathbf{i},c):m^{*}[\mathbf{i},c] \wedge\hat{\mathbf{i}}-\mathbf{i}\in F_{c}\}.$ $$

As a simplification, since motif footprints typically do not heavily overlap, we define $C(\hat{\mathbf{i}},m^{*})$ to be our classification function that gives a relevant true motif center for the input $\hat{\mathbf{i}}$.

$$ $\displaystyle C(\hat{\mathbf{i}},m^{*})=u(S(\hat{\mathbf{i}},m^{*})),$ $$

where $u$ is a choice function that picks an arbitrary element of its input if there are multiple and returns the empty set if there are no entries.

False Positive Motifs. We now have the ability to define our first class of motifs: *false positive motifs*. These are predicted motifs that do not correspond to any real motifs:

$$ $\displaystyle\mathrm{FPM}(\hat{m},m)=\{(\hat{\mathbf{i}},\hat{c})\in P(\hat{m} ):C(\hat{\mathbf{i}},g(x))=\emptyset\}.$ $$

We denote the remaining motifs by

$$ $\displaystyle P_{1}(\hat{m},m^{*})=P(\hat{m})\setminus\mathrm{FPM}(\hat{m},m^{ *}).$ $$

Maximal Motifs
First, we need to define the set of all predicted motifs that cover the same footprint as a given predicted motif. We do so via the $A_{\hat{m},m^{*}}$ function, which takes a given predicted motif (assumed to overlap some footprint) and returns all others covering the same footprint:

$$ $\displaystyle A_{\hat{m},m^{*}}(\hat{\mathbf{i}},c)=\{(\hat{\mathbf{i}}^{ \prime},\hat{c}^{\prime})\in P(\hat{m}):C(\hat{\mathbf{i}}^{\prime},m^{*})=C( \hat{\mathbf{i}},m^{*})\}$ $$

Now we can define *maximal motifs* are predicted motifs that are maximal in the footprint they cover:

$$ $\displaystyle\mathrm{MM}(\hat{m},m^{*})=\{t\in P_{1}(\hat{m},m^{*}):\hat{m}[t] =\max_{t^{\prime}\in A_{\hat{m},m^{*}}(t)}\hat{m}[t^{\prime}]\}$ $$

We can also define *non-maximal motifs* are predicted motifs that are non-maximal in the footprint they cover:

$$ $\displaystyle\mathrm{NMM}(\hat{m},m^{*})=\{t\in P_{1}(\hat{m},m^{*}):\hat{m}[t ]\neq\max_{t^{\prime}\in A_{\hat{m},m^{*}}(t)}\hat{m}[t^{\prime}]\}$ $$

However, we ignore non-maximal motifs entirely for the purposes of our analysis, under the reasoning that these are trivially removable in practice.

## Appendix B Entropy upper bound

Figure: Figure 7: Increase in error when binning. Each series represents a different bin count, as annotated in the legend. Density is log-scaled and reversed to indicate training progress. MT is the model tracked in the rest of the paper, ST is the model as defined in Appendix [D](#A4)
Refer to caption: extracted/5186096/bits-in-postsparse.png

To compute our entropy upper bound, we must first compute $\eta$, as defined in Section [3.3](#S3.SS3). To compute this, we bin the nonzero activations into $2^{k}$ bins by quantile. We set $\eta$ to be the smallest value of $k$ that does not substantially affect the accuracy of the model (we consider 0.1% to be a reasonable threshold for this purpose). Figure [7](#A2.F7) shows the result of this experiment, averaged across 9 seeds. The general downward trend in error caused by binning as density decreases demonstrates that reducing the number of motifs reduces the importance of the precise magnitudes. For the purposes of entropy bounding, we can use $\eta=\log(16)=4$b.

## Appendix C Predicting motif error.

Figure: Figure 8: Model error versus FPE and CE, at 1.1$\times$ the minimum sparsity. All are log-scaled to highlight the low-error region. Each dot represents a single model training seed.
Refer to caption: extracted/5186096/pixel_art_acc_vs_interp.png

Figure [8](#A3.F8) shows the relationship between the motif errors and the overall end-to-end error for DigitCircle. There is no relationship for FPE, but there is a positive relationship for CE, implying that a strategy where one trains several models and then chooses the one with the best validation error is a good way to reduce CE and thereby improve motif quality. This provides further evidence for Motif Identifiability (though the primary evidence for this remains that this model is able to achieve low FPE and CE in general, as training itself focuses on reducing end-to-end error via the loss function). While this may seem to contradict the result in Appendix [5](#S5.F5), it in fact does not. Within a single model, tightening the density has inverse effects on end-to-end error and CE, but separately, some models are in general more or less accurate.

## Appendix D Single Threshold

Figure: Figure 9: Sparling using MT (as in the main figures) vs ST
Refer to caption: extracted/5186096/st-vs-mt.png

In this section, we consider a variation to the quantile function. We call this the *single threshold (ST)* sparsity approach, as opposed to the *multiple thresholds (MT)* technique described in Section [4.1](#S4.SS1), where we take the quantile across the entire input (batch axis, dimensional axes, channel axis). In this case, the channels can have differing resulting densities that average together to the target $\delta$. More precisely, we use the quantile function $q_{\mathrm{ST}}:\mathbb{R}^{B\times d_{1}\times\ldots\times d_{k}\times C}
\times\mathbb{R}\to\mathbb{R}$, implemented such that

$$ $p\approx\frac{1}{BSC}\sum_{b,\mathbf{i},c}\mathbf{1}(z[b,\mathbf{i},c]\leq q_{ \mathrm{ST}}(z,p)).$ $$

As seen in Figure [9](#A4.F9), ST performs substantially worse in terms of CE and E2EE, while performing better with respect to FPE. Without the constraint that the motifs have equivalent density across each channel, some motifs are being used to represent multiple digits, which substantially increases confusion error, but also reduces false positives. In general, the MT model is superior as it has reasonable FPE and substantially lower CE/E2EE.

## Appendix E Comparison to Directly Learning the Motifs

**Table 2: Error [%] and ratios between errors. All are computed as a mean across 9 seeds**
|  | Sparling [mean] | Direct [mean] | Ratio [of means] |
| --- | --- | --- | --- |
| DigitCircle | 1.24 | 0.01 | 0.01 |
| LaTeX-OCR | 6.55 | 0.12 | 0.02 |
| LaTeX-OCR [without +()] | 2.96 | 0.10 | 0.03 |
| AudioMNISTSequence/train | 5.41 | 0.61 | 0.11 |
| AudioMNISTSequence/test | 8.01 | 4.28 | 0.53 |

The purpose of Sparling is to be able to learn intermediate state without having to have access to any training data on the intermediate state. In this section, we analyze how well it does at this goal, by comparing it to Direct, a setting where we train and evaluate on the intermediate state directly. Specifically, we construct datasets for each task of single motifs and train and test models on these datasets, then also test Sparling on these datasets.

In the case of DigitCircle and LaTeX-OCR, Direct is a trivial task as there is no distributional shift in the motif samples used to train and evaluate the model – effectively, Direct is tested on the training set. Thus, Direct gets $\sim$0% error.

However, on the AudioMnistSequence task, the Direct has non-negligible error, with 0.61% error on the training sample distribution but a much higher 4.28% error on the testing sample distribution. Meanwhile, Sparling increases substantially less, from 5.41% to 8.01%. This is becaus ethe error in Sparling comes from two sources: the underlying uncertainty in prediction it shares with the Direct technique, and epistemic uncertainty related to the problem of identifying motifs from end-to-end data. This latter error evidently does not scale linearly with the difficulty of the underlying task.

## Peer Reviews

confidence: 2
contribution: 3
initial_rating: 3
presentation: 1
questions: 1.	Could you provide a figure describing the network architecture used in Section 5.1? This would significantly help readers understand the network architecture. Besides, many parts of the architecture follow Deng et al. (2016). Could you explain why these specific design choices are made?

2.	There are some works studying the *decision sparsity* or *sparsity of concepts* encoded by neural networks [c1, c2, c3], without requiring the network itself (e.g., parameters or activations) to be sparse. They have not been discussed in the related work, and I wonder whether/how these works are related to and different from the *sparsity* in this paper.

3.	Most tasks described in this paper have noises in the input, and it seems that the model needs to do denoising when it outputs the correct result. Is the input noise a necessary setting for motif identification?

[c1] Enouen and Liu. Sparse Interaction Additive Networks via Feature Interaction Detection and Sparse Selection. NeurIPS 2022.

[c2] Sun et al. Sparse and Faithful Explanations Without Sparse Models. AISTATS 2024.

[c3] Ren et al. Where We Have Arrived in Proving the Emergence of Sparse Interaction Primitives in DNNs. ICLR 2024.
soundness: 2
strengths: 1.	The paper seems to focus on an interesting problem, i.e., can a neural network automatically identify motifs (latent variables) of a task under the end-to-end training scheme.

2.	The paper theoretically formalizes several sufficient conditions (assumptions) for motif identifiability, and quantifies the motif error in terms of end-to-end error. I really appreciate this kind of theoretical effort.
summary: This paper theoretically proves that under certain assumptions, the motifs (or latent variables) of a task can be accurately identified by a neural network that is trained end-to-end. More specifically, it provides an upper bound for the motif error when the end-to-end error is low. The paper shows that this kind of motif identifiability can be achieved by enforcing extremely sparse activations in the training process, and validates it on several example tasks.
weaknesses: 1.	The presentation of the paper needs to be improved. It is not clear from the beginning what a “motif” is. I didn't see a concrete description of the motifs until the experiments section on Page 7, e.g., the latent motifs layer $m^*$ is the *position of each digit*. I strongly recommend taking one of the tasks in the experiments as an illustrating example at the beginning of the paper. Try to use figures to explain what are the ground-truth motifs the model is expected to learn, and what is the intermediate output that is considered as the model’s encoding of a motif (Is it a tensor? If so, plot the shape of the tensor). This illustrating example can also help readers better understand the physical meaning of the assumptions in Section 3.3.

2.	The claim that the motif error is small according to Figure 3 is not very convincing, because the experiment lacks comparison with properly designed baselines. There should be some comparisons against a certain baseline, e.g., when $\hat{g}$ is a random mapping, which is a very weak baseline. I encourage the authors to come up with stronger baselines to make the result more convincing.

3.	The practical implication of the paper is still limited. The current paper mainly focuses on special tasks that exhibit certain structures (e.g., input noise, sparse input signals). Is it possible to validate the assumptions and the theory on more common tasks such as image classification, e.g., the digit classification on MNIST? If not, I also encourage the authors to discuss why it is the case in a Limitations section.

4. Minor.

(a) Could you add the equation numbers and the line numbers, so that we can refer to specific contents more easily?

(b) In the equation $v_{\hat{m}}(i)=\sum_{i’ \in p_2(i)} \boldsymbol{1}(\hat{m}[i] \neq 0)$, should the $\hat{m}[i]$ on the right hand side be $\hat{m}[i’]$?

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: * The SPARLING algorithm is presented as a contribution in the main text but then in appendix A it is said to exist in prior work [1] - can the authors please clarify? do the 2 statements refer to the same algorithm, what are the differences between them and what is the contribution of this work? statements in the main text and the appendix should be consistent.

* I found the definitions of error metrics, section 3.2, and of $\alpha$-MOTIF-IMPORTANCE to be confusing - do you think an intuitive explanation through one of the synthetic tasks can be helpful?

[1] Improved modeling of rna-binding protein motifs in an interpretable neural model of rna splicing, Gupta et. al.
soundness: 3
strengths: * The motivation, goals and contributions of the work are clearly stated and are easy to follow.

* Studying theoretical aspects of recovering latent variables, and more generally interpretability, is important and less explored. The work clearly demonstrates a scenario where interpretable latents can be recovered via a sparsity assumption and further provide evidence where the assumptions break and sparsity is insufficient (LaTeX-OCR).

* The suggested algorithm to induce sparsity seems to be efficient ,simple and applicable in a more general setting than suggested in the present work.
summary: The paper studies the extent to which sparsity alone can be used to identify latent variables determining an input-output mapping. They provide a theoretical result on sufficient conditions for recovery of the latents, based on extreme sparsity, low end to end error and properties of the data distribution. To enable training models with extreme sparsity the SPARLING algorithm is presented, which is shown to recover latent variables on several synthetic tasks.
weaknesses: * Some of the notation and formal statements are unclear and hard to follow:
    * In section 2 paragraph 2, square brackets ([d]) denote a set but are then also used to denote dimensions of tensors in the domain of X - why is a tensor not denoted in standard notation? $X \in \mathbb{R}^{N_1\times N_2 \times d}$  
    * The definition of locality, although made intuitive via description with graph convolutions, is hard to understand, partially due to mixing spatial and channel indices. Additionally, the notation for footprint function and motif cell is abused with $p_i$ introduced before.
    * The definitions in section 3.2 are unclear: $v_{\hat{g}(x)}$ is interchanged with $v_{\hat{n}}$ , summation is over $i’$ that doesn’t exist in the summands - can you please clarify?

* The main results, in figure 3, are displayed without any reference baseline. If a simple baseline from any one of the relevant methods in the related work section can be added it can highlight the significance of the method.

---

confidence: 2
contribution: 2
initial_rating: 6
presentation: 3
questions: Would the method work with more complicated model structures such as with more layers? How would one know which layer should be the one to extract specific latent motifs?
soundness: 3
strengths: The paper identifies an interesting setting for making progress on the interpretability of end-to-end neural networks. While the tasks in the paper are synthetic, they were designed with a long-term research objective in mind, such as being able to identify motifs in difficult problems like RNA splicing. The main strains of the paper are in the originality of this setting and in having theoretical guarantees that it is possible to be addressed. The paper is overall well-written and clear even to a reader who is not deeply familiar with the sub-area.
summary: This paper addresses problems in representation learning and interpretability, toward understanding when and how black box models can correctly learn sparse intermediate activations, or "motifs". The central modeling assumption is that many real-world problems can be modeled by a generative process whereby the data come from first identifying a sparse set of higher-level somatic motifs, which is then used to create higher resolution raw data. This paper makes theoretical progress through its Motif Identifiability Theorem.
weaknesses: The main weaknesses of the paper are that it is the first step on a longer-term research problem, and the particular tasks that are able to be addressed now are highly synthetic and unrealistic.

Meta-review: This paper investigates the identifiability of sparse and local latent variables, referred to as motifs, that represent intermediate states in real-world processes. The paper presents the Motif Identifiability Theorem, proving that, under certain conditions, these motifs can be precisely identified by reducing end-to-end error. The Sparling algorithm is then introduced, which enforces activation sparsity through a novel informational bottleneck, achieving over 90% accuracy in localizing intermediate states on synthetic and real-world domains like DigitCircle, LaTeXOCR, and AudioMNISTSequence.

The paper addresses an important problem, and formalizes several sufficient conditions for motif identifiability.  The tasks in the experiment are synthetic.  As all the reviewers appear to agree, the overall presentation leaves a lot of room to be improved, such as the formal definitions.  So another round of revision seems necessary.

Decision: Reject