# Do We Price Happiness? Evidence from Korean Stock Market

HyeonJun Kim∗
School of Finance, Soongsil University
<EMAIL_ADDRESS>or<EMAIL_ADDRESS>
###### Abstract

This study explores the potential of internet search volume data, specifically
Google Trends, as an indicator for cross-sectional stock returns. Unlike
previous studies, our research specifically investigates the search volume of
the topic ’happiness’ and its impact on stock returns in the aspect of risk
pricing rather than as sentiment measurement. Empirical results indicate that
this ’happiness’ search exposure (HSE) can explain future returns,
particularly for big and value firms. This suggests that HSE might be a
reflection of a firm’s ability to produce goods or services that meet societal
utility needs. Our findings have significant implications for institutional
investors seeking to leverage HSE-based strategies for outperformance.
Additionally, our research suggests that, when selected judiciously, some
search topics on Google Trends can be related to risks that impact stock
prices.

keywords: [Asset Pricing], [Sentiment], [Google Trend]

##  1 Introduction

Market sentiment is shown to be regraded as the predictor for cross-sectional
stock return, even when adjusted by size, value, and momentum effect. [1] This
initial way of measuring market sentiment by Baker et al. (2006) was based on
market-based measures, while others used suvey-based indicies. [2] Later an
alternative is suggested that use internet search volume such as Google Trends
[5]. This method is quite appealing for financial economists because of its
transparency of models built upon it, while also obtaining high frequency
data. There was some concerns about the quality of Google Trend data [3],
however it is certain that Google Trend data could be used as ”early warning
signs of stock market moves” [8]. Here the natural question arises; could
google search queries detect fundamentals and risk associated with it?

Usually, search volume or related metrics (like return sensitivity) is far
from fundamental information, and rather a sentiment proxy. This is because
search volume, by its nature, is about collective social attention. However,
it is shown that exposure, or factor loading to this sentiment proxy can be
used for variety of asset pricing application. There are attempts to use this
exposure by Chen, Kumar and Zhang (2020), but the study focused on
relationship between the factor loading of a search volume and abnormal
return[4], which is within the area of mispricing or irrational asset pricing.
In this paper we suggest the possibility that internet search volume data
could be used for rational asset pricing by extracting the common risk across
assets. Empirical analysis show that stock return’s exposure to the search
volume of topic ’happiness’(or HSE) have explanatory power to future return
even when BE/ME and size is controlled. By subsampling the firms by size and
BE/ME, the predictive power of HSE is higher in big and value firms,
supporting the theory that HSE is a proxy for firm’s capacity to generate
goods or service that satisfies society’s utility, or happiness.

##  2 What is Fundamental about Sentiment?

As any search query could be chosen to be used as demand pressure, at least it
will be interesting, if not useful, to measure the demand pressure regarding
abstract subject. Fundamentally, the search engines are for searching
information or solution of some needs. For example, query volume for ’jobs’
will have thorough economic explanation. Whereas search queries like
”Happiness” do not have clear economic meaning. Usually users could not use
the search engine to relief its demand about abstract concepts. Rather it
should be interpreted as general sentiment about those concepts. Then we can
intuitively interpret the high or low sentiment for these concepts in its own
context of society, and check whether or not the sentiment proxies to certain
economic activities. High sentiment for ”Happiness”, for instance, means there
is overall lack of happiness in the society. Therefore, search volume for
”Happiness” could be regarded as demand for happiness.

The time series format of this search volume intensity enables to measure
quantity of exposure for these sentiments using Ross (1976)’s method. [9] The
discussion that should be address is whether or not this this exposure (or
Happiness Sentiment Exposure, HSE) could be considered as risk. This question
could be solved by empirical evidence that will be presented later in this
paper, but that do not give confidence in theoretical level. Here we focus on
the fact that as customer utility is generated by happiness, the overall
demand of happiness in the society influence the customer demand of the
product that the some company serves, thus influence the fundamental of the
company. Therefore, we hypothesized that Happiness Sentiment Exposure measured
as the factor loading for search volume intensity for ”Happiness(행복)” is
somewhat theoretically adequate to be regarded as risk variables. We used a
exposure to the search volume intensity of the subject ’happiness’ that Google
Trend provide to estimate the risk proxy for each stock. This risk proxy will
quantify the tendency of the firm to be more related to society’s utility
supply processing.

##  3 Empirical Analysis

We use the cross-sectional analysis method of Fama and French (1992) [7] for
identifying cross-sectional excess return pattern related to HSE. Although
later studies did identified few more market anomalies like momentum,
profitability and investment,

###  3.1 Data Preparation

Daily return including dividends, daily market cap of common stocks, equity,
preferred stock data was collected from DataGuide. Return data is changed from
daily to monthly frequency, and BE/ME at year $t$ was calculated by dividing
equity minus preferred stock last trading day market cap of December of year
$t$

The model for extracting the exposure $\beta_{SVI}$ is presented in equation
1.

$R_{t}^{(i)}=\alpha+\beta_{SVI}\Delta SVI_{t}+\epsilon_{t}$ (1)

Where $R_{t}^{(i)}$ is monthly return of a stock $i$ at time $t$ and $\Delta
SVI_{t}$ is log difference between monthly search volume intensity of query
related to ”happiness” between time $t$ and $t-1$. Also, although we mentioned
the model of Ross (1976), equation 1 does not include market proxy for a few
reasons. First, as we assumed that Happiness Sentiment Exposure is
systematical but noisy, we had a concern that Happiness Sentiment Exposure
will be misestimated due to market proxy, which have stronger relationship
with the returns and is noise-free independent variable. Second, if the market
proxy is added to the analysis, then the factor loading for Happiness
Sentiment will measure the relationship with Happiness Sentiment with abnormal
returns, which is not this paper’s topic. The returns are winsorized by
99percentile and 1percentile threshold values, and estimation data range is 72
months, but data length down to 24 month was also accepted.

For portfolio analysis and Fama-Macbeth regression, the return was
symmetrically trimmed by one observation each month to exclude extreme
returns.

###  3.2 Preliminary

Here we will address the local characteristics of Korean stock market. While
it is not thoroughly researched, the two main stock market in Korea, KOSPI
market and KOSDAQ seem less likely to be stochastically segmented or equally
valuated. Unlike NYSE and NASDAQ, KOSDAQ stocks tends to transfer to KOSPI if
possible, and index value of KOSDAQ, which started at 1000 in year 1997, still
didn’t fully recovered its initial value, while KOSPI market grow more than
200%. Considering these facts, it will be wise to choose one of the two
markets for researching asset pricing that will avoid inconsistent results. We
choose KOSPI, which has more larger market capitalization.

###  3.3 Informal Tests

Here we first report portfolio analysis results for presenting non-parametric
results and finding some discussion points. The result is shown in Table 1

|  HSE |  BE/ME(+) |  Size |  Excess Return
---|---|---|---|---
Unhappy |  -0.19 |  1.25 |  847.3 |  | -1.04
---
(-1.81)
2 |  -0.11 |  1.76 |  1094.46 |  | 0.25
---
(0.54)
3 |  -0.07 |  1.81 |  1464.26 |  | 0.26
---
(0.62)
4 |  -0.05 |  1.94 |  1931.27 |  | 0.47
---
(1.09)
5 |  -0.03 |  1.76 |  1839.11 |  | 0.37
---
(0.78)
6 |  -0.01 |  1.75 |  1362.77 |  | -0.10
---
(-0.23)
7 |  0 |  1.71 |  2167.74 |  | 0.65
---
(1.54)
8 |  0.03 |  1.69 |  1576.52 |  | 0.27
---
(0.63)
9 |  0.05 |  1.47 |  1262.08 |  | 0.89
---
(2.09)
Happy |  0.12 |  1.37 |  1446.29 |  | 0.86
---
(1.84)
Happy-Unhappy |  0.31 |  0.12 |  598.99 |  | 1.90
---
(3.65)
Table 1: Univariate sort result of Happiness Sentiment Exposure(HSE). The
portfolio is formed by sorting the stocks with cross-sectional decile of HSE
for each year. we report time-series average for average BE/ME and market
capitalization(market cap) of each stock in the portfolio, in which market cap
is reported in 1 billion Korean won. Portfolio return is calculated by value-
weighting the returns with market cap and subtracting with risk-free rate. We
used monthly investment return of 1-year Korean Government treasury bill for
risk-free rate. The portfolio is formed in June of year $t$ using the HSE data
from July of year $t-4$ to June of year $t$(with at least 24 observation) and
reblanced that July of year $t+1$.

Here we can see some expected, and also interesting results. First, as
expected we see a somewhat monotonic increase in average excess return when
the HSE value increases. T-values is not statistically significant (the
highest decile being 1.67 standard deviation away from 0), but we can argue
that this is because of noisy return, not because of the true average return
value. After 8th decile, annualized expected return is over 9.3%, and the
annualized excess return difference between 10th decile(Happy) and 1st
decile(Unhappy) is over 17%. We did not report the equally weighted portfolio
excess return, but we want to note that for the equally weighted portfolio,
the excess return for high decile portfolio is robust and statistically
significant, but the monotonic increase of return in higher decile became less
apparent. We assume that this is due to size effect and value effect that is
observed in the Korean stock market, i.e. the high deciles have low BE/ME and
low decile is small in size thus the monotonic pattern are flatten.
We also can observe unusual results for average stock market cap for each
decile, which is non-linear. Actually the middle deciles (around 4-7th) has
the highest BE/ME and market cap. This leads to interesting interpretation;
low HSE stocks and high HSE stocks are both small cap and low value firms,
while middle HSE stocks are big cap and high value firms. According to
previous studies that argues that KOSPI exchange stocks have little or
reversed size effect[6], the middle HSE portfolio should be the most high
performing portfolios. However the sorting result shows that HSE does have its
own market anomaly phenomenon regardless of pre-existing anomalies. Because of
the previously reported non-linear relationship between BE/ME or size and HSE,
We also report the 5 by 5 size-HSE and BE/ME-HSE double sort result to show
HSE’s predictive power of excess returns when size or BE/ME is controlled.
Specific method is same as beta-size sort of Fama&French(1992) [7]. Stocks in
each size or BE/ME decile portfolio is sorted again according to HSE’s decile
breakpoints. Here, we found that in big firm or high value firms subsample,
the result more strongly supports our hypothesis that HSE is a risk proxy, or
at least a persisting anomaly unrelated to size or BE/ME.

|  Unhappy |  2 |  3 |  4 |  Happy |  Happy-Unhappy
---|---|---|---|---|---|---
Small |  | 1.74
---
(3.24)
| 2.21
---
(4.22)
| 2.15
---
(4.37)
| 1.69
---
(3.12)
| 1.84
---
(3.51)
| 0.10
---
(0.24)
2 |  | 1.22
---
(2.46)
| 1.33
---
(2.91)
| 0.97
---
(2.11)
| 1.45
---
(3.12)
| 1.15
---
(2.24)
| -0.07
---
(-0.24)
3 |  | 0.71
---
(1.41)
| 0.63
---
(1.37)
| 0.88
---
(1.88)
| 1.12
---
(2.34)
| 0.90
---
(1.82)
| 0.20
---
(0.73)
4 |  | -0.03
---
(-0.05)
| 0.53
---
(1.12)
| 0.86
---
(2.01)
| 0.73
---
(1.81)
| 0.93
---
(1.94)
| 0.96
---
(3.12)
Big |  | 0.09
---
(0.18)
| 0.45
---
(1.01)
| 0.91
---
(2.28)
| 0.64
---
(1.59)
| 0.85
---
(2.07)
| 0.76
---
(2.23)
Table 2: Sort result of stocks in KOSPI with quintiles of Size and HSE variable. For each size quintile, HSE quintile breakpoint is used to form HSE quintile portfolios inside the same size quintile. Size and HSE are observed in June of year $t$. The portfolio is formed and rebalanced on the last day of June of year $t$. |  Unhappy |  2 |  3 |  4 |  Happy |  Happy-Unhappy
---|---|---|---|---|---|---
Low |  | 0.16
---
(0.31)
| 0.54
---
(1.23)
| 0.34
---
(0.78)
| 0.57
---
(1.26)
| 0.57
---
(1.22)
| 0.41
---
(1.18)
2 |  | 0.69
---
(1.48)
| 0.79
---
(1.77)
| 0.95
---
(2.07)
| 0.88
---
(1.98)
| 0.73
---
(1.59)
| 0.03
---
(0.10)
3 |  | 1.11
---
(2.30)
| 1.24
---
(2.80)
| 1.17
---
(2.80)
| 0.91
---
(1.89)
| 1.44
---
(2.89)
| 0.32
---
(1.09)
4 |  | 1.09
---
(2.28)
| 1.28
---
(2.71)
| 1.48
---
(3.08)
| 1.52
---
(3.25)
| 1.44
---
(2.93)
| 0.36
---
(1.25)
High |  | 1.20
---
(2.51)
| 1.39
---
(3.05)
| 1.36
---
(3.05)
| 1.84
---
(3.80)
| 1.66
---
(3.28)
| 0.46
---
(1.51)
Table 3: Sort result of stocks in KOSPI with quintiles of BE/ME and HSE
variable. For each BE/ME quintile, HSE quintile breakpoint is used to form HSE
quintile portfolios inside the same BE/ME quintile. Size and HSE are observed
at June of year $t$,. The portfolio is formed at June of year $t$ and
rebalanced at June of year $t+1$.

###  3.4 Regression Analysis

Table 4 show the Fama-Macbeth Regression result for several variables. The
regression result will show some insights about the HSE’s predictability, and
also the conditional predictability when the other variables are controlled.

a | s | h | $h_{dummy}$ | hs
---|---|---|---|---
3.69 | -0.22 |  |  |
3.49 | -2.79 |  |  |
0.77 |  | 0.70 | -2.22 |
1.84 |  | 6.75 | -2.43 |
0.88 |  |  |  | 2.20
2.13 |  |  |  | 2.01
2.83 | -0.17 | 0.60 | -2.47 |
0.92 | -2.18 | 5.34 | -2.77 |
4.19 | -0.26 |  |  | 2.08
4.05 | -3.94 |  |  | 1.97
0.77 |  | 0.45 | -2.61 | 2.02
1.90 |  | 3.75 | -1.92 | 1.82
3.52 | -0.21 | 0.32 | -2.83 | 2.12
3.41 | -3.17 | 2.68 | -2.07 | 2.00
Table 4: On each month, we conducted the following regression.
$R_{i}-RF=a+s\cdot log(ME_{i})+h\cdot log(BE/ME)_{i}^{+}+h_{dummy}\cdot
BE_{Dummy,i}+hs\cdot HSE_{i}+\epsilon_{i}$.
$log(BE/ME)^{+}_{i}$ is BE/ME value that fills BE/ME with BE less than 0.
$BE_{Dummy,i}$ is 1 when BE is less than 0, else 1. Then we calculated time-
series average and its t-value of coefficients and intercept. Returns are
observed at July, year $t$ to June, year $t+1$, and BE/ME are observed at
December, year $t-1$ and HSE, ME is observed at June, year $t$.

Here we can see that HSE does explain some cross-sectional return in
univariate condition. The t-value of HSE coefficient is statistically
significant by a margin, but considering that HSE has estimation error, this
result can be seen as robust. bivariate regression of HSE and $log(BE/ME)$
(more precisely $log(BE/ME)^{+}_{i}$, HSE, and $BE_{Dummy,i}$) show the
decrease in HSE’s explanatory power by a lot.
Interesting observation is shown when we consider the relationship between HSE
and $log(ME)$. When comparing 4th and 7th regression, the significance of ME
change dramatically, from 2.18 standard deviation away from 0 to 3.17 standard
deviation away from 0, with increase in risk premium as well. This is also
shown in 1st amd 5th regression. This result could be understood by HSE-size
sort result that shown previously. If the HSE can explain big firm’s abnormal
high performance in Korean stock market [6], the size effect become more
apparent. Whereas, HSE seems to not sufficiently explain high value firms’
performance, though the risk premium for BE/ME lessen. The regression that
includes all variables show that HSE does have explanatory power when size and
BE/ME is controlled.

Sub Sample | a | s | h | $h_{dummy}$ | hs
---|---|---|---|---|---
Big | 11.37 | -0.74 | 0.10 | -0.94 | 3.58
| (8.08) | (-8.13) | (0.71) | (-0.60) | (2.42)
Small | 23.40 | -2.06 | 0.69 | -4.23 | 2.08
| (13.06) | (-13.45) | (4.96) | (-4.21) | (1.46)
Table 5: Big and Small subsample of firms are determined by yearly median of
size(log value of market cap) value. If the firm’s size at year $t$ is bigger
than the size median at time $t$, is classified as big firm, and vise versa.
On each month, we conducted the following regression.
$R_{i}-RF=a+s\cdot log(ME_{i})+h\cdot log(BE/ME)_{i}^{+}+h_{dummy}\cdot
BE_{Dummy,i}+hs\cdot HSE_{i}+\epsilon_{i}$.
$log(BE/ME)^{+}_{i}$ is BE/ME value that fills BE/ME with BE less than 0. $BE_{Dummy,i}$ is 1 when BE is less than 0, else 1. Then we calculated time-series average and its t-value of coefficients and intercept. Returns are observed at July, year $t$ to June, year $t+1$, and BE/ME are observed at December, year $t-1$ and HSE, ME is observed at June, year $t$. Sub Sample | a | s | h | $h_{dummy}$ | hs
---|---|---|---|---|---
Value | 5.58 | -0.37 | -0.06 | 0.00 | 3.94
| 4.68 | -4.35 | -0.33 | 1.48 | 2.58
Growth | 2.24 | -0.11 | 0.40 | 0.00 | 0.96
| 1.97 | -1.49 | 2.43 | -0.89 | 0.79
Table 6: Value and Growth subsample of firms are determined by yearly median
of BE/ME value (including negative BE/ME). If the firm’s BE/ME at year $t$ is
bigger than the BE/ME median at time $t$, is classified as big firm, and vise
versa. On each month, we conducted the following regression.
$R_{i}-RF=a+s\cdot log(ME_{i})+h\cdot log(BE/ME)_{i}^{+}+h_{dummy}\cdot
BE_{Dummy,i}+hs\cdot HSE_{i}+\epsilon_{i}$.
$log(BE/ME)^{+}_{i}$ is BE/ME value that fills BE/ME with BE less than 0.
$BE_{Dummy,i}$ is 1 when BE is less than 0, else 1. Then we calculated time-
series average and its t-value of coefficients and intercept. Returns are
observed at July, year $t$ to June, year $t+1$, and BE/ME are observed at
December, year $t-1$ and HSE, ME is observed at June, year $t$.

##  4 Conclusion

Here we conclude the paper by exploring alternative interpretation of the
result, and application of the result to investors.

###  4.1 What is HSE?

Here, we need to considerr other interpretation of HSE other than the proxy of
demand pressure sensitivity for economic demand. We can hypothesize two
theories. First, HSE could be some sort of behavioral error predictor driven
by sentiment, such that the predictor predicts the short-term error or long-
term market correction dynamics. Second theory is that HSE is really
fundamentally related to individual firm, which captures the company’s ability
to satisfy societies’ utility demand. As big firms consist most of the market
and economic activities, the society’s happiness demand will be more dependent
to to big firms than to small firms. The same logic could be applied to value
firms as well. The first hypothesis is questionable because of many reasons.
The most prominent one is that if the theory is correct, the coefficient
should be negative, not positive. Even if the behavioral error cannot be
adjusted immediately, the phenomena is unlikely to persist for a year to make
the coefficient positive. Big and Small firm Subsample and Value and Growth
firm Subsample Fama-Macbeth regression support the latter hypothesis.

Here we can see that there is nonlinar relationship between size or BE/ME and
HSE, where HSE explains big and value firm’s cross-sectional return difference
more better than small and growth firms. This supported by the fact that most
of societies utility demand is processed by big firms and mature industries.

###  4.2 Application

As HSE shows explanatory power to big and value firms, this have substantial
implication to institutional investors. As institutional investors have out-
performance demand and liquidity constraints, they are drawn to big and value
firms. Here by applying HSE related strategies, institutional investors can
seek for out-performance while maintaining its investment portfolio style.
Although because of technical issues, current HSE based on Google Trend data
is unstable and have some estimation errors. For applying to real world
problems, there should be a robust way of estimating HSE. In academic
perspective, this research has shown that google trend could be more than
sentiment proxy. When chosen wisely, some search topics could be related to
risk that will be priced.

## References

  * [1] Malcolm Baker and Jeffrey Wurgler.  Investor sentiment and the cross-section of stock returns.  The journal of Finance, 61(4):1645–1680, 2006.
  * [2] Gregory W Brown and Michael T Cliff.  Investor sentiment and asset valuation.  The Journal of Business, 78(2):405–440, 2005.
  * [3] Eduardo Cebrián and Josep Domenech.  Is google trends a quality data source?  Applied Economics Letters, 30(6):811–815, 2023.
  * [4] Yao Chen, Alok Kumar, and Chendi Zhang.  Dynamic esg preferences and asset prices.  Available at SSRN 3331866, 2020.
  * [5] Zhi Da, Joseph Engelberg, and Pengjie Gao.  The sum of all fears investor sentiment and asset prices.  The Review of Financial Studies, 28(1):1–32, 2015.
  * [6] Cheoljun Eom, Woo-Baik Lee, and Jong Won Park.  A reexamination of the size effect in the korean stock market.  Korean Journal of Financial Management, 31(3):113–151, 2014.
  * [7] Eugene F Fama and Kenneth R French.  The cross-section of expected stock returns.  the Journal of Finance, 47(2):427–465, 1992.
  * [8] Tobias Preis, Helen Susannah Moat, and H Eugene Stanley.  Quantifying trading behavior in financial markets using google trends.  Scientific reports, 3(1):1684, 2013.
  * [9] Stephen A Ross.  The arbitrage theory of capital asset pricing.  Journal of Economic Theory, 13(3):341–360, 1976.


#  Sparling: Learning Latent Representations with Extremely Sparse Activations

Kavi Gupta
Massachusetts Institute of Technology
<EMAIL_ADDRESS>
&Osbert Bastani
University of Pennsylvania
<EMAIL_ADDRESS>
&Armando Solar-Lezama
Massachusetts Institute of Technology
<EMAIL_ADDRESS>
###### 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\%$ 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. (2020)), and information bottlenecks
require that that the mutual information between the representation and the
input be bounded (Bourlard & Kamp (1988)). 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 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.

Example. Figure 1 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. (2020)) and Concept Embedding
Models (Zarlenga et al. (2022)), involve additional supervision with existing
feature labels. Other techniques, such as Cross-Model Scene Networks (Aytar et
al. (2017)), 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. (2013); Selvaraju et al. (2016)), 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. (2014)), only works with a single layer of attention and does not
necessarily produce valid or complete explanations (Serrano & Smith (2019)).
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 (2009)), 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. (2012); Higgins et al. (2016)). 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. (2019)). 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 (1988)), or adding
noise—e.g., variational autoencoders (Kingma & Welling (2014)). 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 (1996); Scardapane et al. (2017); Ma et al. (2019);
Lemhadri et al. (2021)); 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. (2015)). However, these techniques typically only
achieve 50%-90% sparsity, whereas Sparling can achieve $>99.9\%$. We directly
compare with these in Section 5.1. Additionally, Bizopoulos & Koutsouris
(2020) uses a quantile-based activation limit equivalent to both of our
ablations (see Section 1) 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 cuboid111For images, the cuboid is a
rectangle, as drawn in Figure 1, 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.222We 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 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). 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. 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.

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

$T_{0}\leftarrow 1$

for $t=1$ to $\ldots$ do

TrainStep$(\hat{f},\mathcal{D}_{Bt:B(t+1)})$

$T_{t}\leftarrow T_{t-1}-Bd_{T}$

if $bt\bmod M=0$ then

$A_{t}\leftarrow$ Validate$(\hat{f})$

if $A_{t}>T_{t}$ then

$\hat{f}.\delta\leftarrow\hat{f}.\delta\times\delta_{\mathrm{update}}$

$T_{t}\leftarrow A_{t}$

##  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. 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 batches333For 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. 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.

###  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. (2016), 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, 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 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.

We have three domains, as described below. See Figure 2 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. (2016).

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. (2018))
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. (2016). For DigitCircle, we make $\hat{g}$ have a $17\times 17$
overall window, by layering four residual units (He et al. (2016)), 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. (2017)) 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)444In 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}$ loss555This 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. (2015). We also consider using $KL$-divergence loss as in
Jiang et al. (2015). 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 (2011), 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 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.

Motif error. We show our metrics of motif error, FNE, FPE, and CE in Figure 3
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 and 4.

Examples. Figure 2 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 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.

Confusion matrices. Figure 4, 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 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.

Necessity of Extreme Sparsity Figure 5 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 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.

| $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
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.

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) 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 6: _Retrained_ tends to perform as well as or slightly worse than _Non-
Sparse_ , making up most of the gap from Sparling

End-to-End error As seen in Figure 6, 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.

## References

  * Aytar et al. (2017) Yusuf Aytar, Lluis Castrejon, Carl Vondrick, Hamed Pirsiavash, and Antonio Torralba.  Cross-modal scene networks.  _IEEE transactions on pattern analysis and machine intelligence_ , 40(10):2303–2314, 2017.
  * Becker et al. (2018) Sören Becker, Marcel Ackermann, Sebastian Lapuschkin, Klaus-Robert Müller, and Wojciech Samek.  Interpreting and explaining deep neural networks for classification of audio signals.  _CoRR_ , abs/1807.03418, 2018.
  * Bizopoulos & Koutsouris (2020) Paschalis Bizopoulos and Dimitrios Koutsouris.  Sparsely activated networks.  _IEEE Transactions on Neural Networks and Learning Systems_ , 32(3):1304–1313, 2020.
  * Bourlard & Kamp (1988) Hervé Bourlard and Yves Kamp.  Auto-association by multilayer perceptrons and singular value decomposition.  _Biological cybernetics_ , 59(4):291–294, 1988.
  * Deng et al. (2016) Yuntian Deng, Anssi Kanervisto, and Alexander M Rush.  What you get is what you see: A visual markup decompiler.  _arXiv preprint arXiv:1609.04938_ , 10:32–37, 2016.
  * Desjardins et al. (2012) Guillaume Desjardins, Aaron Courville, and Yoshua Bengio.  Disentangling factors of variation via generative entangling.  _arXiv preprint arXiv:1210.5474_ , 2012.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Identity mappings in deep residual networks.  In _European conference on computer vision_ , pp. 630–645. Springer, 2016.
  * Higgins et al. (2016) Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner.  beta-vae: Learning basic visual concepts with a constrained variational framework.  In _International conference on learning representations_ , 2016.
  * Jiang et al. (2015) Nan Jiang, Wenge Rong, Baolin Peng, Yifan Nie, and Zhang Xiong.  An empirical analysis of different sparse penalties for autoencoder in unsupervised feature learning.  In _2015 international joint conference on neural networks (IJCNN)_ , pp. 1–8. IEEE, 2015.
  * Kingma & Welling (2014) Diederik P Kingma and Max Welling.  Stochastic gradient vb and the variational auto-encoder.  In _Second International Conference on Learning Representations, ICLR_ , volume 19, pp. 121, 2014.
  * Koh et al. (2020) Pang Wei Koh, Thao Nguyen, Yew Siang Tang, Stephen Mussmann, Emma Pierson, Been Kim, and Percy Liang.  Concept bottleneck models.  In _International Conference on Machine Learning_ , pp. 5338–5348. PMLR, 2020.
  * Lemhadri et al. (2021) Ismael Lemhadri, Feng Ruan, Louis Abraham, and Robert Tibshirani.  Lassonet: A neural network with feature sparsity.  _The Journal of Machine Learning Research_ , 22(1):5633–5661, 2021.
  * Locatello et al. (2019) Francesco Locatello, Stefan Bauer, Mario Lucic, Gunnar Raetsch, Sylvain Gelly, Bernhard Schölkopf, and Olivier Bachem.  Challenging common assumptions in the unsupervised learning of disentangled representations.  In _international conference on machine learning_ , pp. 4114–4124. PMLR, 2019.
  * Ma et al. (2019) Rongrong Ma, Jianyu Miao, Lingfeng Niu, and Peng Zhang.  Transformed l1 regularization for learning sparse deep neural networks.  _Neural Networks_ , 119:286–298, 2019.  ISSN 0893-6080.  doi: https://doi.org/10.1016/j.neunet.2019.08.015.  URL https://www.sciencedirect.com/science/article/pii/S0893608019302321.
  * Mnih et al. (2014) Volodymyr Mnih, Nicolas Heess, Alex Graves, et al.  Recurrent models of visual attention.  _Advances in neural information processing systems_ , 27, 2014.
  * Ng (2011) Andrew Ng.  Cs294a lecture notes: Sparse autoencoder, Winter 2011.  URL https://web.stanford.edu/class/cs294a/sparseAutoencoder.pdf.
  * Scardapane et al. (2017) Simone Scardapane, Danilo Comminiello, Amir Hussain, and Aurelio Uncini.  Group sparse regularization for deep neural networks.  _Neurocomputing_ , 241:81–89, 2017.  ISSN 0925-2312.  doi: https://doi.org/10.1016/j.neucom.2017.02.029.  URL https://www.sciencedirect.com/science/article/pii/S0925231217302990.
  * Selvaraju et al. (2016) Ramprasaath R Selvaraju, Abhishek Das, Ramakrishna Vedantam, Michael Cogswell, Devi Parikh, and Dhruv Batra.  Grad-cam: Why did you say that?  _arXiv preprint arXiv:1611.07450_ , 2016.
  * Serrano & Smith (2019) Sofia Serrano and Noah A Smith.  Is attention interpretable?  _arXiv preprint arXiv:1906.03731_ , 2019.
  * Simonyan et al. (2013) Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman.  Deep inside convolutional networks: Visualising image classification models and saliency maps.  _arXiv preprint arXiv:1312.6034_ , 2013.
  * Sønderby et al. (2016) Casper Kaae Sønderby, Tapani Raiko, Lars Maaløe, Søren Kaae Sønderby, and Ole Winther.  Ladder variational autoencoders.  _Advances in neural information processing systems_ , 29, 2016.
  * Tibshirani (1996) Robert Tibshirani.  Regression shrinkage and selection via the lasso.  _Journal of the Royal Statistical Society: Series B (Methodological)_ , 58(1):267–288, 1996.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.  URL https://proceedings.neurips.cc/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf.
  * Yoon (2009) Byung-Jun Yoon.  Hidden markov models and their applications in biological sequence analysis.  _Current genomics_ , 10(6):402–415, 2009.
  * Zarlenga et al. (2022) Mateo Espinosa Zarlenga, Pietro Barbiero, Gabriele Ciravegna, Giuseppe Marra, Francesco Giannini, Michelangelo Diligenti, Zohreh Shams, Frederic Precioso, Stefano Melacci, Adrian Weller, et al.  Concept embedding models.  _arXiv preprint arXiv:2209.09056_ , 2022.

##  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 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

To compute our entropy upper bound, we must first compute $\eta$, as defined
in Section 3.3. 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 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 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.

Figure 8 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, 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 9: Sparling using MT (as in the main figures) vs ST

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, 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, 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

|  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
Table 2: Error [%] and ratios between errors. All are computed as a mean
across 9 seeds

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.