Kernel Deformed Exponential Families for Sparse Continuous Attention
Authors: Alexander Moreno
Supriya Nagesh
Zhenke Wu
Walter Dempsey
James Matthew Rehg
Venue: ICLR 2022 Submitted (2022)
Keywords: kernel methods
attention mechanism
theory
exponential families
deformed exponential families

Abstract: Attention mechanisms take an expectation of a data representation with respect to probability weights. This creates summary statistics that focus on important features. Recently, Martins et al. (2020, 2021) proposed continuous attention mechanisms, focusing on unimodal attention densities from the exponential and deformed exponential families: the latter has sparse support. Farinhas et al. (2021) extended this to use Gaussian mixture attention densities, which are a flexible class with dense support. In this paper, we extend this to two general flexible classes: kernel exponential families and our new sparse counterpart kernel deformed exponential families. Theoretically, we show new existence results for both kernel exponential and deformed exponential families, and that the deformed case has similar approximation capabilities to kernel exponential families. Experiments show that kernel deformed exponential families can attend to non-overlapping intervals of time.

Under review as a conference paper at ICLR 2022
KERNEL DEFORMED EXPONENTIAL FAMILIES FOR SPARSE CONTINUOUS ATTENTION
Anonymous authors
Paper under double-blind review
ABSTRACT
Attention mechanisms take an expectation of a data representation with respect to probability weights. This creates summary statisties that focus on important features. Recently, MMrtins et al. (2200 202I) proposed continuous attention mechanisms, focusing on unimodal attention densities from the exponential and deformed exponential families: the latter has sparse support. Farinhas et al. (202T) extended this to use Gaussian mixture attention densities, which are a flexible class with dense support. In this paper, we extend this to two general flexible classes: kernel exponential families (Canu & Smola 2006) and our new sparse counterpart kernel deformed exponential families. Theoretically, sults for both kernel exponential and deformed exponential families, and that the deformed case has similar approximation capabilities kernel exponential fam- ilies. Experiments show that kernel deformed exponential families can attend to multiple compact regions of the data domain.
show new existence re-
INTRODUCTION
Attention mechanisms take weighted averages of data representations (Bahdanau et al. (015), where the weights are a function of input objects. These are then used as inputs for prediction. Discrete attention 1) cannot easily handle data where observations are irregularly spaced 2) attention maps may be scattered, lacking focus. Martins et al.] (2200 (02T) extended attention to continuous set- tings, showing that attention densities maximize the regularized expectation of a function of the data location (i.e. time). Special case solutions lead to exponential and deformed exponential families: the latter has sparse support. They form a continuous data representation and take expectations with respect to attention densities. Using measure theory to unify discrete and continuous approaches, they show transformer self-attention (Vaswani et al. 2017 is a special case their formulation.
Martins et al. (2020 2021) explored unimodal attention densities: these only give high importance to one region of data. Farinhas et al.] (202T) extended this to use multi-modal mixture of Gaussian attention densities. However 1) mixture of Gaussians do not lie in either the exponential or deformed
exponential familics, and are difficult to study in the context of Martins et al. (2020) 2021) 2) they have dense support. Sparse support can say that certain regions of data do not matter: region of time has no effect on class probabilities, or a region of an image is nof some object. We would like use multimodal exponential and deformed exponential family attention densities, and understand how Farinhas et al. (2021) relates to the optimization problem Martins et al. (2000) 2021).
This paper makes three contributions: 1) we introduce kernel deformed exponential families, multimodal class of densities with sparse support and apply it along with the multimodal kernel exponential families (Canu & Smola 2006) to attention mechanisms. The latter have been used for density estimation, but not weighting data importance 2) we theoretically analyze normalization for both kernel exponential and deformed exponential families in terms of a base density and ker- nel, and show approximation properties for the latter 3) we apply them to real world datasets and show that kernel deformed exponential families learn flexible continuous attention densities with sparse support. Approximation properties for the kernel deformed are challenging: similar kernel exponential family results (Sriperumbudur et al. 2017) relied on standard exponential and logarithm properties to bound the difference of the log- perr-itttionn functional at two functions: these do not hold for deformed analogues. We provide similar bounds via the functional mean value theorem along with bounding the Frechet derivative of the deformed log-partition functional.

---

Under review as a conference paper at ICLR 2022
The paper is organized as follows: review continuous attention (Martins et al.) 2020; 2021) We then describe how mixture of Gaussian attention densities, used in Farinhas et al. (2021) l). solve a different optimization problem. We next describe kernel exponential families and give novel nor- malization condition relating the kernel growth to the base density's tail decay. We then propose kernel deformed exponential families, which can have support over disjoint regions. We describe normalization and prove approximation capabilities. Next we describe use of these densities for continuous attention, including experiments where we show that the kernel deformed case learns multimodal attention densities with sparse support. We conclude with limitations and future work.
2 RELATED WORK
Attention Mechanisms closely related are Martins et al. (2020
2021b; Farinhas al, (2021 Tsai
et al.J (2019); Shukka & Marlin (2021). Martins et al. (2020) (021) frame continuous attention as an expectation of a value function over the domain with respect to a density, where the density solves an optimization problem. They only used unimodal exponential and deformed exponential family densities: we extend this to the multimodal setting by leveraging kernel exponential families and proposing deformed counterpart. [Farihhas et al. (022 proposed multi-modal continuous attention mechanism via a mixture Gaussians approach. We show that this solves a slightly different optimization problem from Martins al.] (2020; 2021), and extend to two further general density classes. (hukka Marlin (202) provide an attention mechanism for irregularly sampled time series by use of a continuous-time kernel regression framework, but do not actually take an expectation of a data representation over time with respect to a continuous pdf, evaluating the kernel regression model at a fixed set of time points to obtain discrete representation. This describes importance of data at a set of points rather than over regions. Other papers connect attention and kernels, but focus on the discrete attention setting (T'sai et al. 2019 Choromanski al. 2020). Also
relevant are temporal transformer papers, including Xu et al. (2019): Li et al. (0019] 2020) Song
al. 2018). However none have continuous attention densities.
Kernel Exponential Families Canu & Smola (2006) proposed kernel exponential families: Sripe- rumbudur et al. (2017) analyzed theory for density estimation. Weeliang et al. (2019) parametrized the kernel with a deep neural network. Other density estimation papers include Arbel & Gretton (2018); Dai et al. (019);; Sutherland et al. (2018). We apply kernel exponential families as atten- tion densities to weight value function which represents the data, rather than to estimate the data density, and extend similar ideas to kernel deformed exponential families with sparse support.
Wenliang et al. 2019) showed condition for unnormalized kernel exponential family density to have a finite normalizer. However, they used exponential power base densities. We instead relate kernel growth rates to the base density tail decay, allowing non-symmetric base densities.
To summarize our theoretical contributions: 1) introducing kernel deformed exponential families with approximation and normalization analysis 2) improved kernel exponential family normalization results.
3 CONTINUOUS ATTENTION MECHANISMS
An attention mechanism involves: 1) the value function approximates a data representation. This may be the original data or a learned representation. 2) the attention density is chosen to be 'similar' to another data representation, encoding it into a density 3) the context combines the two, taking an expectation of the value function with respect to the attention density. Formally, the context is
BT~ppV (V)).
(1)
Here V(() the value function approximates a data representation, T p(() is the random variable or vector for locations (temporal, spatial, etc), and ptt) is the attention density.
To choose the attention density p. one takes a data representation ff and finds p 'similar' to f and thus to data representation, but regularizing p. Martins et al. (2020) 202Th did this, providing a rigorous formulation of attention mechanisms. Given a probability space (S, A, Q), let M (S) be the set of densities with respect to Q. Assume that Q is dominated by a measure v (i.e. Lebesgue) and that
dQ has density go = de with respect to v. Let S C RR,, F be a function class, and Ω M. (S) + R be a lower semi-continuous, proper, strictly convex functional.
2

---

Under review as a conference paper at ICLR 2022
Given f E F, attention density (Martins et al. 2020) P F - R20 solves
P[ʃ] = arg PEML(S)
max
(p,() -((p).
(2)
This maximizes regularized L similarity between p and a data representation f. If a(p) is the negative differential entropy, the attention density is Boltzmann Gibbs
p(((1) exp(s(1) A(f)),
where A(f) ensures (() = 1. If f(t) = 0T (t) for parameters and statistics e RM : ((t) E Rd respectively, Eqn. 3 becomes an exponential family density. For f in repro- ducing kernel Hilbert space H. it becomes kernel exponential family density (Canu & Smola 2006), which we propose to use as an alternative attention density.
One desirable class would be heavy or thin tailed exponential family-like densities, In exponential families, the support, or non-negative region of the density, is controlled by the measure Q. Letting (p)) be the a-Tsallis negative entropy S2 (p) (Tsallis 1988).
o) (fs 1) a aa Is p(t) log p(t)dQ 1,
Pp(())
then plf] for f(t) = 00''0''' ott lies in the deformed exponential family (Tsllis 1988 Naudts
2004
ia. [f](tt = exp2-a Φ(t) Aa(f)), where (f) again ensures normalization and the density uses the 3-exponential
(4)
[1 + (1 3)4 //1 8) 13+1;
e)p
(5)
exp(t), 1.
5 and thus deformed exponential family densities for 1 < S. 2 can return 0 values. Values a (and thus 3 1) give thinner tails than the exponential family, while a gives fatter tails. Setting 3 = 0 is called sparsemax (Martins & Astudillo 2016). In this paper, we assume < a S 2. which is the sparse case studied Martins et al.] (2020). We again propose to replace ((1 0 ((t) with f E H. which leads to the novel kernel deformed exponential families.
For B < 1, Eqn.
Computing Eqn. Is context vector requires parametrizing (t). Martins et al. (2020) obtain a value function V S IR parametrized by B E DxN by applying regularized multivariate linear regression to estimate ((t; (t), where V {wh J set of basis functions. Let be the number of observation locations (times in a temporal setting), O be the observation dimension, and N be the number of basis functions. This involves regressing the observation matrix H E 0 on matrix F E IR N of basis functions { In evaluated at observation locations {t>]/1
B arg min BF
H + A B
3.1 GAUSSIAN MIXTURE MODEL
Farinhas et al. 2021 used mixture of Gaussian attention densities, but did not relate this to the
optimization definition of attention densities in Martins et al. (2020: 202I). In fact their attention densities solve a related but different optimization problem. Martins et al. (2000; 202I) show that exponential family attention densities maximize regularized linear predictor of the expected suffi- cient statistics of locations. In contrast, Farinhas et al. (2021) find a joint density over locations and latent states, and maximize regularized linear predictor of the expected joint sufficient statisties. They then take the marginal location densities to be the attention densities.
Let (p)) be Shannon entropy and consider two optimization problems:
arg max (0, (oTT))) 9(p)) PEM)(S)
arg max (0, (O(T, Z)))2² R(p) (5M
3

---

Under review as a conference paper at ICLR 2022
The first is Eqn. 2 with f = and rewritten to emphasize expected sufficient statistics. If one solves the second with variables Z, we recover an Exponential family joint density
pn. [ft exp(0' (00006ff ptt, 2) A(0)).
This encourages the joint density of T, Z to be similar to complete data representation 6" o(t, 2) of both location variables T and latent variables Z, instead of encouraging the density of T to be similar to an observed data representation 0 6(t). The latter optimization is equivalent to
arg max a(p) (SM
s.t.
E 2) (T, Z)] Cm
M..
The constraint terms Cm are determined by Thus, this maximizes the joint entropy of and T, subject to constraints on the expected joint sufficient statistics.
To recover EM learned Gaussian mixture densities, one must select 6m so that the marginal distribu- tion of T will be mixture of Gaussians, and relate c. to the EM algorithm used to learn the mixture model parameters. For the first, assume that Z a multinomial random variable taking / possi-
ble values and let Φ(t, 2) = (21, 22, - [(= 1)6, T( 1)t², ... T(= | )r 7(= [Z] ) These are multinomial sufficient statistics, followed by the sufficient statistics of |Z| Gaus- sians multiplied by indicators for each x. Then Z) will be Gaussian, p (Z) will be multinomial,
and p(T) will be Gaussian mixture. For contraints, Farinhas et al. (022 have
2) Z)]
Σ
(=/a(2/1)) (4,, 2), 1,,", M
at each EM iteration. Here Pola(2(a)) is the previous iteration's latent state density conditional on the observation value, wy are discrete attention weights, and ti is discrete attention location. That EM has this constraint was shown in Wang et al. (2012). Intuitively, this matches the expected joint sufficient statistics to those implied by discrete attention over locations, taking into account the dependence between and & given by old model parameters. An alternative is simply to let 0 be the output of a neural network. While the constraints lack the intuition Eqn. 7 it avoids the need to select an initialization. We focus on this case and use it for our baselines: both approaches are valid.
4 KERNEL EXPONENTIAL AND DEFORMED EXPONENTIAL FAMILIES
We now use kernel exponential families and new deformed counterpart to obtain flexible attention densities solving Eqn. 2 with the same regularizers. We first review kernel exponential families. We then give novel theoretical result describing when an unnormalized kernel exponential family den- sity can be normalized. Next we introduce kernel deformed exponential families, extending kernel exponential families to have either sparse support or fatter tails: we focus on the former. These can attend to multiple non-overlapping time intervals or spatial regions.
show similar normaliza- tion results based the choice of kernel and base density. Following this we show approximation theory. We conclude by showing how to compute attention densities in practice.
Kernel exponential families (Canu & Smola, 2006) extend exponential family distributions, replac- ing f(t = (tt)(t) with f in a reproducing kernel Hilbert space H. (Aronszajn 1950) with kernel
k: USSxx x S R. Densities can be written
p(t) exp(f(t)-A(f))
- = exp((f, k(-,))))) - A(f)),
where the second equality follows from the reproducing property. A challenge is to choose H, Q so that a normalizing constant exists, i.c., Jg ex)(f(tt)dd < oc. Kernel exponential family dis- tributions can approximate any continuous density over compact domain arbitrarily well in KL divergence, Hellinger, and L distance (Sriperumbudur et al. (017). However relevant integrals including the normalizing constant generally require numerical integration.
4

---

Under review as a conference paper at ICLR 2022
cbec Loeeciio
06
04 04
24
06
Figure 1: Attention densities for kernel deformed exponential families for the first attention head of the uaave experiment and all test set participants for three classes. The densities are sparse and each have support over different non-overlapping time intervals, which cannot be done with either Gaussian mixtures or exponential families. They also attend to similar regions within each class.
To avoid infinite dimensionality generally assumes representation of the form
Σ Tak(;tt)
where for density estimation (Sriperumbudur et al. 2017 the t, are the observation locations. How- this requires using parameter per observation value. This level of model complexity may not be necessary, and often one chooses a set of inducing points (Titsias 2009) {t:) where is less than the number of observation locations.
For given pair H. k. how can we choose Q to ensure that the normalization constant exists? We first give simple example of H. f and Q where the normalizing constant does not exist.
Example 1. Let Q be the law of a (0. 1) distribution and S = R. Let H. = span(t?, tt) with k(x,y) z²y² + x² and (t) = t +t ket, 1). Then
[ exp(I()))dQ
2 exp(
+1 17)dl
2
where the integral diverges.
4.1 THEORY FOR KERNEL EXPONENTIAL FAMILIES
We provide sufficient conditions for Q and H so that A(f) the log-partition function exists. We relate H'' kernel growth rate the tail decay of the random variable or vector To with law Q. Proposition 1. Let p(t) = (t)(f(t)) where f E H an RKHS with kernel k. Assume k(t,t) < Lellt & + Ck for constants Lg, Ck. > O. Let Q be the law of random vector Tq. that Q(A) = P(To E A). Assume Vu s.t. ||u||2 = 1,
P( 2 Cgp exp(-uz")
(9)
for some constants 1) > UQ, >>>>0 0. Then
p())dQ 00.
Proof. See Appendix A.I
Based on ktt, 'ss growth, we can vary what tail decay rate for TQ ensures we can normalize p(t). Wenliang et al. (2019) also proved normalization conditions, but focused on random variables with of k(t, t) rather than relating tail decay growth rate. By focusing tail decay, our result can be applied to non-symmetric base densities. Specific kernel bound growth rate terms & lead to allowing different tail decay rates.
exponential power density for specific growth
Corollary 1. For 4. TQ be any sub- Gau--aassinn random vector. For E 2 it can be any sub-exponential. For { = it can have any density.
Proof. See Appendix A.2
5

---

Under review as a conference paper at ICLR 2022
4.2 KERNEL DEFORMED EXPONENTIAL FAMILIES
We now propose kernel deformed exponential families: flexible sparse non-parametric distributions. These take deformed exponential families and extend them to use kernels the deformed exponen- tial term. This mirrors kernel exponential families. We write
pt) exp3-a A.()))
where f E H. with kernel k. Fig. T shows that they can have support over disjoint intervals.
4.2.1 NORMALIZATION THEORY
We construct valid kernel deformed exponential family density from Q and f E H. We first discuss the deformed log normalizer. In exponential family densities, the log-normalizer the log of the normalizer. For deformed exponentials, the following holds.
Lemma 1. Let Z > 0 be constant. Then for
< S 2,
exp eXP2-a (2a ((1)) exp2 exp2-a(f(t) loog Z)
where
-ー 1-3 log(() 0,100,8=1 undefined $.
log,3 t
Proof. See Appendix B.1
We deseribe normalization sufficient condition analagous to Proposition[] for the sparse deformed kernel exponential family. With Lemma we take unnormalized exp2-o(f(() and derive valid normalized kernel deformed exponential family density. We only require that an affine function of the terms in the deformed-exponentt
negative for large magnitude l.
Proposition 2. For 1 < a S assume p(t) = exp2-a with f E H, H is a RKHS with kernel k. If 0 s.t. for ||t||2 Co (a 1))(t) + 1 S 0 and k(t,t) L |t Cj for some & 0, co.
then Ss exp2=a
Proof. See Appendix B.2
We now construct a valid kernel deformed exponential family density using the finite integral.
Corollary 2. Under the conditions of proposition assume exp2-a exp2-a(f(t)) > 0 on set A C S such
that (A) > 0, then 3 constants 7 > Aa(f) RR such that for f(1) = z ((), the following holds
/
exp2-a Aa(f))QQ=
Proof. See Appendix B.3
We thus estimate f(t) = (Z)--1 f(t) and normalize to obtain density of the desired form.
4.2.2 APPROXIMATION THEORY
Under certain kernel conditions, kernel deformed exponential family densities can approximate den- sities of a similar form where the RKHS function is replaced with (o( function.
continuous function domain vanishing infinity

---

Under review as a conference paper at ICLR 2022
Proposition 3. Define
Po = :0000
where S C R.d. Suppose ((x,,) E Co(S), Ve E and
I (( > 0,0n E Mo(S)
(10)
here (S() is the space of bounded measures over S. Then the set of deformed exponential families dense in Pu wrt L'(Q) norn and Hellinger distance.
Proof. See Appendix B.4
We apply this to approximate fairly general densities with kernel deformed exponential families.
Theorem 1. Let qo E C(S), such that qo(t) > 0 for all E S, where S C I is locally compact Hausdorff and (t) is the density of with respect to dominating measure Suppose there exists 1 1> such that for any > 0, 3R satisfying (p(t) - 1 S for any with ||t||2 > R. Define
/ ((1))Q=1,10) 2 0, and Co(S)).
Pp=
Suppose k(t,,) ColS)VL S and the kernel integration condition (Eqn. T0p holds. Then ker- nel deformed exponential families are dense in Pe wrt L norm, Hellinger distance and Bregman divergence for the a-Tsallis negative entropy functional.
Proof. See Appendix B.5
For uniform qo, kernel deformed exponential families can thus approximate continuous densities on compact domains arbitrarily well. Our Bregman divergence result is analagous to the KL divergence result in (Sriperumbudur et al.] (2017). KL divergence Bregman divergence with the Shannon entropy functional:
show the same for Tsallis entropy. The Bregman divergence here describes how close the uncertainty in a density is to its first order approximation evaluated at another density. Using the Tsallis entropy functional here is appropriate for deformed exponential families: they maximize it given expected sufficient statistics (Naudts) 2004).
These results extend (Sriperumbudur al. (2017)'s 's approximation results the deformed setting, where standard log and exponential rules cannot be applied. The Bregman divergence case requires bounding Frechet derivatives and applying the functional mean value theorem.
4.3 USING KERNELS FOR CONTINUOUS ATTENTION
We apply kernel exponential and deformed exponential families to attention. The forward pass com- putes attention densities and the context vector. The backwards pass uses automatic differentiation. We assume a vector representation v E Ri computed from the locations we take an expectation over. For kernel exponential families we compute kernel weights (w) for f(1) = Eí= Pck(t, 4))
7i == w U,
and compute Z I9 cx)(f(t))dQ numerically. For the deformed case we compute fss = w v and f(t) - f(t) El= ink(t, t4) followed by Js exp2-a (f))=a(((t))dQ The context
c c= (VErpI(((T) = (t)
requires taking the expectation of (T") with respect to a (possibly deformed) kernel exponential family density p. Unlike Martins al. (2020 2021), where they obtained closed form expectations, difficult normalizing constants prevent us from doing so. We thus use numerical integration for the forward pass and automatic differentiation for the backward pass. Algorithm shows how to compute a continuous attention mechanism for kernel deformed exponential family attention density. The kemel exponential family case is similar.

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Continuous Attention Mechanism via Kernel Deformed Exponential Families
Choose base density qo(t) and kernel k. Inducing point locations {44]==1
Input Vector representation of imput object i.e. document representation
Parameters {5 the weights for f(t) = (2)a-1 f(t) = Σ'= K,t(t, t.), matrix B for basis
weights for value function (tt) B (t). I is number of inducing points.
Forward Pass
Compute = J cXP2 (f (t)) to obtain p(t) exp2-a(((t) via numerical integration
Compute Er~p/
via numerical integration Compute e Ep-p[V
[V (T) BE, (T))
Backwards Pass use automatic differentiation
Attention
N=32
N=64
N=128
Mean
Cts Softmax
89.56
90.32
91.08
90.32
Cts Sparsemax
89.50
90.39
89.96
89.95
Kernel Softmax
91.30
91.08
90.44
90.94
Kernel Sparsemax
90.56
90.20
90.41
90.39
Table 1: IMDB sentiment classification dataset accuracy. Continuous softmax uses Gaussian at- tention, continuous sparsemax truncated parabola, and kernel softmax and sparsemax use kernel exponential and deformed exponential family with Gaussian kernel. The latter has a 2 in exponential and multiplication terms. N: basis functions, I = 10 inducing points, bandwidth 0.01.
EXPERIMENTS
For document classification, we follow Martins et al, (2020)'s 's architecture. For the remaining, ar- chitectures have four parts: an encoder takes discrete representation of time series and outputs attention density parameters. 2) The value function takes time series representation (original or after passing through neural network) and does (potentially multivariate) linear regression to ob- tain parameters B for a function (t; These are combined to compute 3) context = (T)V( which is used in a 4) classifier. Fig. the Appendices visualizes this.
DOCUMENT CLASSIFICATION
We extend Martins et al. 2020 's code for the IMDB sentiment classification dataset (Maas al. 2011). This starts with a document representation v computed from a convolutional neural network and uses LSTM attention model. We use Gaussian base density and kernel, and divide the inter- val [0, 1] into
inducing points where we evaluate the kernel in ftt E ki((t, t.). We set the bandwidth to be 0.01 for I = 10. Table sshows results. On average, kernel exponential and deformed exponential family slightly outperforms the continuous softmax and sparsemax, although the results are essentially the same. The continuous softmax/sparsemax results are from their code.
Martins 22020 repository for this dataset http://giituub.ccm/ddeespppgippp
Attention
N=64
N=128
N=256
Cts Softmax
67.78-11.64
67.70+ 2.49
68.00+ 2.24
Cts Sparsemax
74.20+:2.72
74.69+3.78
74.58+14.27
Gaussian Mixture
81.13+1..76
80.99-22.79
79.0442.33
Kernel Softmax
03.65.00.60
94.26.0..7
Kernel Sparsemax
92.32+11009
92.15
92.14
Table Accuracy results on wave gesture classification dataset for the irregularly sampled case.
All methods use 100 attention heads. Gaussian mixture uses 100 components (and thus 300 param- eters per head), and kernel methods use 256 inducing points.
8

---

Under review as a conference paper at ICLR 2022
Attention
Accuracy
Cts Softmax
96.97
83.69
Cts Sparsemax
96.04
73.71
Gaussian Mixture
97.20
84.89
Kernl Softmax
96.75
83.27
Kernel Sparsemax
96.86
84.90
Table Accuracy results on MIT BIH Arrhythmia Classification dataset. For Fl score, kernel soft- max and continuous softmax have similar results, while kernel sparsemax drastically outperforms continuous sparsemax. For accuracy, the Gaussian mixture slightly beats other methods.
5.2 UWVEE DATASET
We analyze Wave (Luu al. 2009): accelerometer time series with eight gesture classes. We follow
Li & Marlin (2066) ss split into 3,582 training observations and 896 test observations: sequences have length 945. We do synthetic irregular sampling and uniformly sample 10% of the observations. shows results. Our highest accuracy is 94.26%, the unimodal case's best is 74.69%, and the mixture's 's best is 81.13%. Since this dataset is small, we report 1..9 standard deviations from 10 runs. Fig. [ shows that attention densities have support over non-overlapping time intervals. This cannot be done with Gaussian mixtures, and the intervals would be the same for each density in the exponential family case. Appendix C describes additional details.
ECG HEARTBEAT CLASSIFICATION
We use the MIT Arrhythmia Database's Goldberger et al. 2000 Kaggle The task is to detect abnormal heart beats from ECG signals. The five different classes are (Normal, Supraventricular premature, Premature ventricular contraction, Fusion of ventricular and normal, Unclassifiable] ). There are 87,553 training samples and 21,891 test samples. Our value function is trained using the output of repeated convolutional layers: the final layer has 256 dimensions and 23 time points. Our encoder a feedforward neural network with the original data as input, and our classifier is a feedforward network. Table 3 shows results. All accuracies very similar, but the F1 score of kernel sparsemax is drastically higher. Additional details are Appendix
7 DISCUSSION
In this paper we extend continuous attention mechanisms to use kernel exponential and deformed exponential family attention densities. The latter is new flexible class of non- non-parametric densities with sparse support. We show novel existence properties for both kernel exponential and deformed exponential families, and prove approximation properties for the latter. We then apply these the framework described in Martins et al. (2020) 2021) for continuous attention. We show results on three datasets: sentiment classification, gesture recognition, and arrhythmia classification. In the first case performance is similar to unimodal attention, for the second it is drastically better, and in the third it is similar the dense case and drastically better in the sparse case.
7.1 LIMITATIONS AND FUTURE WORK
A limitation of this work the of numerical integration, which scales poorly with the di- mensionality the locations. Because of this we restricted our applications to temporal and text data. This still allows for multiple observation dimensions would be to use varianced reduced Monte Carlo to approximate the integral, as well as studying how to choose the number of basis functions in the value function and how choose the number of inducing points.
given location. A future direction

---

Under review as a conference paper at ICLR 2022
REFERENCES
Michael Arbel and Arthur Gretton. Kernel conditional exponential family. In International Confer- ence on Artificial Intelligence and Statistics, pp. 1337-1346. PMLR, 2018.
Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American mathematical society, 68(3)3337-404 1950.
Dzmitry Bahdanau, Kyung Hyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate. In 3rd International Conference on Learning Representations, ICLR 2015, 2015.
Stéphane Canu and Alex Smola. Kernel methods and the exponential family, Nenrocomputing, 69 (7-9):714-720, 2006.
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint arXiv:2009. 14794, 2020.
Bo Dai, Hanjun Dai, Arthur Gretton, Le Song, Dale Schuurmans, and Niao He. Kernel exponential family estimation via doubly dual embedding. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 2321-2330 PMIR, 2019.
António Farinhas, André FT Martins, and Pedro MQ Aguiar. Multimodal continuous visual attention mechanisms. arXiv preprint MxXiv:2104.03000 2021.
Ary L Goldberger, Luis AN Amaral, Leon Glass, Jeffrey M Hausdorff, Plamen Ch Ivanov, Roger G Mark, Joseph Mietus, George Moody, Chung-Kang Peng, and Eugene Stanley. Physiobank, physiotoolkit, and physionet: components of new research resource for complex physiologic signals. circulation, 101(23):e215-e222 2000.
Shiyang Li, Xiaoyong Jin, Yao Xuan, Xiyou Zhou, Wenhu Chen, Yu-Xiang Wang, and Xifeng Yan. Enhancing the locality and breaking the memory bottleneck of transformer time series fore- casting. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché Buc, E. Fox, and R. Gareet (eds.), Advances in Neural Information Processing Systems, volume 32, pp. 2244-5255 Cur- ran Associates, Inc., 2019, URL https: http:///oooeeenngne.eteeee
fil eee
wew.aall1666beeoc 9d86be0-Paper. .f
Steven Cheng-Xian Li and Benjamin M Marlin. A scalable end-to-end gaussian process adapter for irregularly sampled time series classification. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29, pp. 1804 1812. Curran Associates, Inc., 2016. URL ptll:attpss:/prcceeiiii hewp:eeeedddnngs...uu........... paper/201 /ile/ 0tw.:0/0220000eeeeeeeeeeeo11111.
Yikuan Li, Shishir Rao, José Roberto Ayala Solares, Abdelaali Hassaine, Rema Ramakrishnan, Dexter Canoy, Yajie Zhu, Kazem Rahimi, and Gholamreza Salimi-KKorshie Behrt: transformer for electronic health records. Scientific reports, 10(1):1-12, 2020.
Jiayang Liu, Lin Zhong, Jehan Wickramasuriya, and Venu Vasudevan. uwave: Accelerometer- based personalized gesture recognition and its applications. Pervasive and Mobile Computing, (6):657-675, 2009.
Andrew Maas, Raymond Daly, Peter Pham, Dan Huang, Andrew Y Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings the 49th annual meeting of the association for computational linguistics: Human language technologies, pp. 142-150, 2011.
Andre Martins and Ramon Astudillo. From softmax to sparsemax: sparse model of attention and multi-label classification. In International Conference on Machine Learning, pp. 1614-1623. PMLR. 2016.
André Martins, António Farinhas, Marcos Treviso, Vlad Niculae, Pedro Aguiar, and Mario Figueiredo. Sparse and continuous attention mechanisms. In H. Larochelle, M. Ranzato, R. Hadsell. M. F. Balcan, and H. Lin (eds.), Advances in Neural In- formation Processing Systems, volume 33, pp- 20989-21001. Curran Associates,
10

---

Under review as a conference paper at ICLR 2022
Inc., 2020. URL http:///pppeeeel......ee///////s
E0b76267 2tt.eaaa122333332233333363633333
André FT Martins, Marcos Treviso. António Farinhas, Pedro MQ Aguiar, Mário AT Figueiredo, Mathieu Blondel, and Vlad Niculae. Sparse continuous distributions and fenchel-young losses. arXiv preprint arXiv: (0::::2000.00 0/988 2021.
Jan Naudts. Estimators, escort probabilities, and phi-exxonennial families in statistical physics. arXiv preprint math-ph/0402005,, 2004.
Satya Narayan Shukla and Benjamin Marlin. Multi-time attention networks for irregularly sampled
time series. International Conference on Learning Representations, 2021. URL https:
net htter//wwwee.eeeeffoooomoooo---o
Huan Song, Deepta Rajan, Jayaraman Thiagarajan, and Andreas Spanias. Attend and diagnose: Clinical time series analysis using attention models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Bharath Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Aapo Hyvärinen, and Revant Kumar. Density estimation in infinite dimensional exponential families, The Journal of Machine Learning Research, 18(1):1830-18) 1888- 2017.
Bharath K Sriperumbudur, Kenji Fukumizu, and Gert RG Lanckriet. Universality, characteristic kernels and rkhs embedding of measures. Journal of Machine Learning Research, 12(7), 2011.
Dougal Sutherland, Heiko Strathmann, Michael Arbel, and Arthur Gretton. Efficient and princi- pled score estimation with nyström kernel exponential families. In International Conference Artificial Intelligence and Statistics, pp. 652-660. PMLR, 2018.
Michalis Titsias. Variational learning of inducing variables in sparse gaussian processes. In Artificial intelligence and statistics, pp. 567-574. PMLR, 2009.
Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis-Philippe Morency, and Ruslan Salakhutdinov. Transformer dissection: A unified understanding of transformer's attention via the lens of kernel. arXiv preprint arXiv:1908. 11775, 2019.
Constantino Tsallis. Possible generalization of boltzmann-gibbs statistics. Journal of statistical physics, 52(1):479-487, 1988.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the 31st In- ternational Conference on Neural Information Processing Systems, pp. 6000-6010, 2017.
Shaojun Wang, Dale Schuurmans, and Yumxin Zhao. The latent maximum entropy principle. ACM Transactions on Knowledge Discovery from Data (TKDD), 6(2):1 42, 2012.
Li Wenliang, Dougal Sutherland, Heiko Strathmann, and Arthur Gretton. Learning deep kernels for exponential family densities. In International Conference on Machine Learning, pp. 6737-6746. PMLR, 2019.
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Self- attention with functional time representation learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Gareet (eds.), Advances in Neu- ral Information Processing Systems, volume 32, pp. 15915-15925. Curran Associates, Inc., 2019. URL https::/proceeiiingg wwwpiiinnnn.neuiisp..o.. c332ebbbbbss7700ebbbcc3b3b222222 Pap.rer.pppppppppp
11

---

Under review as a conference paper at ICLR 2022
A PROOF RELATED TO PROPOSITION
A.1 PROOF OF PROPOSITION 1
Proof. This proof has several parts. We first bound the RKHS function f and use the general tail bound we assumed to give a tail bound for the one dimensional marginals Tqa of Tq. Using the RKHS function bound, we then bound the integral of the unnormalized density in terms of expec- tations with respect to these finite dimensional marginals. We then express these expectations over finite dimensional marginals as infinite series of integrals. For each integral within the infinite se- ries, we use the finite dimensional marginal tail bound to bound it, and then use the ratio test to show that the infinite series converges. This gives us that the original unnormalized density has a finite integral.
We first note, following Wenliang et al. 2019), that the bound on the kernel in the assumption allows us bound in terms of two constants and the absolute value of the point which it is evaluated.
[t() = ((f, k(t, ml reproducing property
S II 1ax (t,, 1l Cauchy Schwarz
Ilf I / (k<(t, k(t,,,),((tt))) (2xx
II I E(t,t)
$ I1. 11ff Lx|lt|s + Cp by assumption
S C. + ||tt||[S//22 for some C1, C2 > 0.
We can write TQ- = (TQ1... ... TQD). Let ea be a standard Euclidean basis vector. Then by the assumption and setting ea have
P([TQul 2 2) S C.
Letting Qu be the marginal law,
[ exp(
/ e
=ex((Co) / exp(Ci]|t||5/2)
expp([)Eexp(CiIlTT S Exx((C)
max (/2))) d=1,-.,p D
D
S cxp((Co
E Ecxp(CalTqa|(/3) Σ
which will be finite if each Eexp(Ca|Tqa) (/2) < co. Now letting Sa be the relevant dimension of S.
Eexp(Ca|T@ul(12) 4/2)
exp(Cal(a
S4
j+1
(/p(C + exp(C2lta/5/2)dQg)
Σ E/
where the inequality follows since Sa S IR, exp a non-negative function and probability measures are monotonic. We will show that the second sum converges. Similar techniques can be shown for the first sum. Note that for j 20 0
Qa(li.j + 1)) P(Ta 2 - 21+1)
< P(Ta 2 Cg exp(=uj") by assumption
12

---

Under review as a conference paper at ICLR 2022
Then
pt+
exp(C2|la|8/2) 8/2 dQQa S
Σ (xp(Cal)5/2))d((().. + 1))
==
1=0
Cq
exp((CC2)
2=0
Let aj exp(C2l,j1/2 vi7).
We will use the ratio test to show that the RHS converges. We have
aj+1
exp(C2((1 + 1 jE(2) - vl(i + 1)" -)²))-
(11)
We want this ratio to be < 1 for large j. We thus need to select that for sufficiently large have
Ci (1)+
5
Assume that 17> Then
(j 1+1 - 5"
(n[(1 + f)20 - 1]
(j 1)8/2 je/2 j5/2[(1 + f/8/2 1|
E/2 2/2
Since the RHS unbounded for 7) > { large j. By the ratio test Bys(t) exp(C2lTu/5/2)
2' we have that Eqn.
11 holds for sufficiently
Σj
exp(C2)tal5/2))) +
S1 exp(Calku$33)dduu finite. Thus putting everything together have
/ exp(f(t))dQ < / exp(Co + (1llo++Cll)))/))ddd
< <exp(Co)
Cexp(C22 Tou
00
and p(t) can be normalized.
A.2 PROOF OF COROLLARY
Proof. Let & = 4. Then > and
P( [l t) < P(2 T| 2 t) monotonicity
S exp(-ut")
< <o exp(- exp(-ut2).
The second case is similar. For the uniformly bounded kernel,
(xp((J,K(,0))))l)) s exp(IIflla CR. | nQ
cxp((l)flxx/ccc) co.
The first line follows from Cauchy Schwarz and &
13

---

Under review as a conference paper at ICLR 2022
B PROOFS RELATED TO KERNEL DEFORMED EXPONENTIAL FAMILY
B.1 PROOF OF LEMMA !
Proof. The high level idea is express term inside the deformed exponential family that becomes 1 1/Z once outside.
exP2-a loga (2)) [] (a 1)(f(t) log 2)1
-
= [] +1+ (a - 1)f(() - (a 1) Z1
1 α
5-1
= - 11)//(()+'=))))))
= I[a 1)f(t) 20-1
Za-1 +
((a (t)(t) Za-1 + +1+
Z
cxp2-a(Za f(t))
cxp2
B.2 PROOF PROPOSITION 2
Proof.
exp2-a (f))
+ (a (1 dQ
[1+ aQ
11|50,
(a 1)(C. + +G10, dQ
0
B.3 PROOF OF COROLLARY
Proof. From proposition 2 and the assumption,
/ (ft)) Z
for some Z > 0. Then
1
5 7 exp2-a (Za f(t))dQ
cxP2-a (f(t) - log,,, Z)dQ =
where the second line follows from lemma
Set (,) = log., (Z) and we are done.
B.4 PROOF OF PROPOSITION
Proof. The kernel integration condition tells us that H dense in Co(S) with respect to - norm. This was shown in Sriperumbudur et al. (201T). For the L" norm, we apply ||p - Pallt- i- < 2.Mxpp Ilf - gllso from Lemma with f E Co(S), g E H. and fo = f. L' convergence implies Hellinger convergence.
14

---

Under review as a conference paper at ICLR 2022
B.5 PROOF OF THEOREM 1
Proof. For any E Pe. define ps
p+ó Then 148
6
1p
p8l1
|p||-
1+0
+0
for S 00. Thus for any e > 0, 26, such that for any 0 < 0 < 62, we have Ilp - pellr S e,
where po( > 0 for all S.
Define f
11+ C+0
1-a
1+d logg a Po 140
Since p e C(S), so f. Fix any fj > 0 and note that
f(t) 2 1
1+ A
1-a
1+
log2 P8
2 7
1+
1 0
1+ 0
1 + 0
R-1
log2 pa
1+0
1+0
"
1+ 0
(1+0) a-1
P8
cxp2-a
(T+8)
7)
1+ 0
1+0
(1++))
(1+0) a-1
po 2
exp2-a
"
1+
(1=00 a-1
p - 1-12 (1 (1+
(oxp2-a
7) -1
Thus
A= (t: f(t) 2 n
((+00) 1 - }}}
p- p-1z (1+
exp2-a
Since p- E (o(S) the set the second line is bounded. Thus A is bounded that f E Co(S). Further, by Lemma
Po = exP2-a (f log.o
(f-
1 + 0 I
giving us Pa E Po. By Proposition
3 there is some Py in the deformed kernel exponential family
so that [po - Poller(s) S e. Thus Helinger distance, note
Poll- S 2e for any S r S oc. To show convergence in
H² Po) = l (VD RdQ
2
1
(p /PPp + Pg)dQ
2 S
1
< 2 J
(p 2 min(p, po) Pd]
1
{ lp Ps laQ
2 S
Palli
actually an equality, http::/wwwww....cicccccc///cccca for proof
edu/
15

---

Under review as a conference paper at ICLR 2022
that (S) convergence, which showed, implies Hellinger convergence. Let consider the
Bregman divergence. Note the generalized triangle inequality" for Bregman divergence
Bag (p.Pg) Ba_ (p, pa) + Bo, (po.Ps) (p pe, (Pa VQ. (Pa))2
(12)
11
111
Term
1
(p.pe)
(p - -pp)dQ (Va((p)) P-ps)
a(a 1)
1
(p" pa db)
Po 1-11 (p ppp
a(a 1)
S
1
(p Pa dQ
| 1120~11111 ialllpp poll
a(a 1)
The first term on the rhs clearly vanishes as - 0. For the second term, we already showed that lpp Polloo O.
Term II
Fix 0. Then term // converges to 0 by Lemma
Term III
For term III,
(p ps. (po) VΩ, (Pa))2 I poll (Po) VΩ, (Pg)ll
Clearly the first term the rhs converges by L" convergence. The L' term for the gradient given by
(po) (2 1 -
/ //lpll (pg(()=-11dk
(llpolloc + l|p0 - -----olll )a- 2 - Po IQ Eqn. 17
(llpollso + I1po - p2 a - Poll
so that the inner product terms bounded
Kp - po. (pa(po) - (Pg(() & (llpol>>o llpo - po Ipo Polloollp polloo
Lemma 2. (Functional Taylor's Theorem) Let F X R where X is a Banach space. Let f.g E X and let F be k limes Gateaux differentiable. Then we can write
k-1
F(g) = Σ F' -
1=0
for some e E [0, 1].
Proof. This simply a consequence of expressing functional as a function an e [0, 1]. which restricts the functional to take input functions between two functions. We then apply Taylor's the- orem to the function and apply the chain rule for Gateaux derivatives to obtain the resulting Taylor remainder theorem for functionals.
Let G(nr) = F(J - nlg - f)). By Taylor's theorem we have G(1) = G(0) + G0( + ......... +........... (c)
and applying the chain rule gives us
k-1
F(g) = F F* clg f)) f)
16

---

Under review as a conference paper at ICLR 2022
Lemma 3. (Functional Mean Value Theorem) Let F X R be a functional where f.g E X some Banach space with norm ||. Then
F(f) F(9) S (1)l
where h = + - - 9) for some c E [0, 1]. (h) is the Gateaux derivative of F, and || llop is the operator norm Al inf 0: |x S c||=||Va E X..
Proof. Consider G(n) Flg + nf 9))- Apply the ordinary mean value theorem to obtain
G(1) G(O) c' [0.1] F as - 9)) (S -))
and thus
F(f) F()) - (h) all
Claim 1. Consider Poo = (ps exp2-al1 Aa()) : :f (S). Then for Ps E Poo.
Aa(f) S bl
Proof.
pt(() = cxp2-a(((1) Aa(f))
Sexp2 (11llo Aa()) for 1 < <as2
(t(d) < / exp2 (11flx Ao (f)
1 1 exp2-a (1) 11 Aa)))
logg-a 1 < |f ff 00 - Aa(f)
Af)
< |
where for the second line recall that we assumed that throughout the paper 1 < a 2.
Lemma 4. Consider Poo = {py = exp2-a(( A. (f)) : (S)), Then the Frechet derivative of Aa: L + R exists. It given by the map
A'())()
1ppp-0(((T)
- - (t))((()
f 5 (1)dQ
Proof. This proof has several parts. We first derive the Gateaux differential of Py in a direction d E L and as it depends on the Gateaux differential of (a(f) in that direction, we can rearrange latter. We then show that it exists for any f, E L Next we show that the second Gateaux differential of (J) exists, and use that along with functional Taylor expansion to prove that the first Gateaux derivative is in fact Frechet derivative.
terms to recover
In Martins et al. 2020) they show how to compute the gradient of (0) for the finite dimensional case: we extend this to the Gateaux differential. We start by computing the Gateaux differential of Pf.
d
(f) = exp exp2-a +b(() Aalf + m7))
dn
d1j
d
[1 + (a 1)(s(t) (p) Aalf m76)) m()))]/((-11
dn
=[1 (a 1)(f(t) +mb(t) - Aalf -2))) (0(0)
d A. mpb)
dn
d Ar / m8²
(5(1) -
dn
17

---

Under review as a conference paper at ICLR 2022
evaluating gives us
= (b(tt) (bt))) (fa(f:e))
Note that by claim 1
we have
Pf+go (1) = exp2-o (ʃ(1) + mbb(1) An + mv(())
< exp2-o +
S exp2-o ( + 1
We can thus apply the dominated convergence theorem to pull a derivative with respect to r under an integral. We can then recover the Gateaux diferential of A, via
0 dn 1-=0
dp(sis)(()dQ
/ 11(1)=-(((11) dAa(Ji)))dQ
dAn(J:t)) B3 (VTT))
<000
where the last line follows as v E L Thus the Gateaux derivative exists in L directions. The derivative at f maps v : Bpp- (T))) i.e. (f)()) = E3z- (x)(T)). We need to show that
this is Frechet derivative. To do so, we will take take second derivatives of pf (t) with respect y) in order obtain second derivatives of A. (f + mp) with respect 17. We will then construct a functional second order Taylor expansion. By showing that the second order terms converge sufficiently quickly, we will prove that the map v : 5 (TTT) a Frechet derivative.
d dap PTpPi+nol(
drj dyp Pi- (1)2-a
(b(1)
Aals + mo)
dn
(1)2-a) (v(0) ( ( an
d
Aals + +m))
dn
d dnp Aals + mpp)
(t)+ 2-a
d
Aalf + m/)) d
(2 a)pf+n (1)())
dr Py-)
dn
d² Aalf f mp²
(t)
d7p
d
d?
(2 - a2-0a)7-220
3- (b(t)
Aalf + mu))² Ps+ (t)2-a
drp Aa-A Aa m²)
dn
We need show that can again pull the second derivative under the integral. We already showed that we can pull the derivative under once (for the first derivative) and we now need to do it again. We need show an integrable function that dominates p/+ne 2----- (t)2-c(1b(t))
p (T)).
Ips+mo (t)² (t)2--(((()) EE an (T))) S P/+nv (t) 2
S cxP2-o ( + [101
which is in (.) Now applying the dominated convergence theorem d
deL P.P++e (1) (1)QQ
/ (2- (2-a)p3 22
d
Aalf ex))² (14c d² de AalS + cnd) aQ
22 (v(()) (v²(t)
de
18

---

Under review as a conference paper at ICLR 2022
and rearranging gives
d²
Pitte
(v(()) (1)())
d. AAllf + ddQ
(f + Ev) = =2 a)
dea
|psted (1)2-a())2- (t)2-adQ
d
[P] (v(() B3 (T)))
Aa(s)
= (2 a))
de
(ps(1)2-adQ
c=0
since f, v E _ For the functional Taylor expansion, we have from Lemma 2
Aa(J + +b) = Aa(1) + (2(()()))))) +
2 Aa + (x))
for some E [0, 1]. We thus need show that for [0, 11,
(2 (2-a) 11 SDite (v((t) 3 $3 (TT
50 0
J Pstey (t)
It suffices to show that the numerator tends to 0 1p O.
1 (v)(t)
[+(2)))
1
E 13 [x))
(L)
(()
(tt)
21R 19 [M()))
B2g p [x((T))
1
1101
11//
(L)
[0((t) 211 p7+0
[+)
1100
xb())
+ B
E | (T))
11
(t) 23,z-a [x((T]]
+
112- E [M(T)]
1/ 0
and plugging this in we obtain the desired result. Thus the Frechet derivative of (f) exists.
Lemma 5. Define Pox tps exp2-a Aa()) f (S)) where L (S) is the space of almost surely bounded measurable functions with domain S. Fix fo L Then for any fixed and Py. Pj Poe such that f.g B (fo) the - closed ball around fo. there exists constant Mexp > 0 depending only on fo such that
llp/ Poller I 22Mxxpli - gllo0
Further
1 a-1 lp, [llppll + lips - Palloo) + (2pp_a(2)))))xx)))
Br, (p). S
Proof. This Lemma mirrors Lemma A.1 in Sriperumbudur et al. 2017 but the proof is very dif- ferent as they rely on the property that exp(x + y) exp(x) exp(y) y). which does not hold for 3-exponentials. We thus had to strengthen the assumption to include that f and g lie in closed ball, and then use the functional mean value theorem Lemma as the main technique to achieve our result.
Consider that by functional mean value inequality.
|lps - - = ex - - -xp))) A.(g)))
< || ex - (h)) - gloo + (Aa(f) - Aa()))
(13)
where h = cf (1 -)g for some [0, 1]. We need to bound exp Ao (h)) and ([) [o)
19

---

Under review as a conference paper at ICLR 2022
We can show a bound on c
| 0c
||ef + (1 - + follec
< ||c[f - fo) + (1-c)(g fo) + folloo
S cl| f folloe + - c)lgg folloo + fl
E + ll
that h is bounded. Now previously showed in claim | that [Aa s |1/||x I Set Ifoolooo
Since h, Aa (h) are both bounded exp3 (h - (h))) 2 is also
Now note that by Lemma 3
AA, Ao( S (1) glo0o
We need to show that [1'()))l bounded for f.g E Be(fo). Note that in Lemma 4 we showed that
(A)()) - (B())-
$ $1gll0o
Thus ||A/_lop
(t) |mm] 1} S 1. Let Mexp be the bound exp, (h (h)).
Then putting everything together we have the desired result
lpf/ PPlll- < 2.exp - glooo
Now
Bn. (pS.Pp) (p,) Q2 (p,) (V,, (P)..)))PP pg)2 For the inner prodct term, first note that following Martins al. (2020) the gradient is given by
(14)
Vla (Pg)(() = (1)
(15)
Thus
(VPl( -P))22 S VVl )l |1lppl -Pollo
exp (g((t) AA()))dQllpr - Palloo
a
exp2 2xP2-a - Ppol00
where the second line follows from claim Further note that by Taylor's theorem,
== x" +a2a-1yy x)
(16)
for some z between x and y. Then letting y = (t) and r = Pg (t). we have for some 2 h(t) lying between py (f) and py that
(t) = (t) + (a((t)=-((pppppp (t)
Since - then applying Claim D we have that each Ps.Pq E -e and thus h is. Then
(t) (t) = (l)
S <|||||5~~11PP -
s max( 1Il |a- Py ll.0
s allpyll>> + 1epll -gglo
)a -11p Pylloo
(17)
so that
11) / ( (t)
(pr) - Pa(p))
(1lpylox + 1p,, -ooloo) Polloc.
20

---

Under review as a conference paper at ICLR 2022
Cass probabiittees
Classifier
E,(V()
Attention mechanism
parameters for p(t)
V(()
Encoder
Value function
(etucretizea
Figure General architecture for classification using continuous attention mechanisms. The pipeline is trained end-to-end. The encoder takes discretized representation of observation (i.e. a time series) and outputs parameters for an attention density. The value function takes the original (potentially irregularly sampled) time series and outputs parameters for function V(t)- These are then combined in an attention mechanism by computing a context vector c = (T)) For some parametrizations must be done via numerical integration. The context vector is then fed into a classifier.
and (tt) this can be computed in closed form, while for others
Putting all together we obtain
Ba, (p), 2
(119|100 + Ilppy 3a-11
llp, Pylloc
1
+
cxp2-a M1ps Poll
1
1ps Poll~ + llps Pyllxc exp2-a e2 (2]1g]
C UWAVE EXPERIMENTS: ADDITIONAL DETAILS
We experiment with N = 64, 128 and 256 basis functions, and use learning rate of le - 4. We use H 100 attention mechanisms, or heads. Unlike Vaswani et al. (2017). our use multiple heads slightly different
the same value function for each head, and only vary the attention densities, Additional architectural details are given below.
C.I VALUE FUNCTION
The value function uses regularized linear regression the original time series observed random observation times (which are not dependent on the data) to obtain an approximation V(t; B) (t(()) X()). The Hl in Eqn. is the original time series.
C.1.1 ENCODER
In the encoder, the value function interpolate the irregularly sampled time series at the original points. This is then passed through a convolutional layer with 4 filters and filter size followed by max pooling layer with pool size 2. This is followed by hidden layer with 256
21

---

Under review as a conference paper at ICLR 2022
units and output of size 256. The attention densities for each head / 1, H then
μ4 Wh.1
0 = softplus(w (2)
7h w
for vectors Wh,1, wh,2 and matrices 4hth and heads h = 1,..., ,H
C.1.2 ATTENTION MECHANISM
After forming densities and normalizing, have densities pi(t). .PH(t), which we use to com- pute context scalars
C = p.. [V(T]
We compute these expectations using numerical integration to compute basis function expectations Ep, (T)] and a parametrized value function Vtt) (t(() described in section 3
C.1.3 CLASSIFIER
The classifier takes as input the concatenated context scalars as a vector. A linear layer is then followed by softmax activation output class probabilities.
D MIT BIH: ADDITIONAL DETAILS
Note that our architecture takes some inspiration for the H that use in our value function from github repository [ although they used tensorflow and we implemented our method in pytorch.
D.1 VALUE FUNCTION
The value function regresses the output of repeated convolutional and max pool layers on basis functions, where the original time series was the input to these convolutional/max pooling layers. All max pool layers have pool size 2. There are multiple sets of two convolutional layers followed by max pooling layer. The first set of convolutional layers has 16 filters and filter size 5. The second and third each have 32 filters of size 3. The fourth has one with 32 filters and one with 256, each of size The final output has 256 dimensions of length 23. This then used as our H matrix in Eqn 6
D.2 ENCODER
The encoder takes the original time series as input. has one hidden layer with ReLU activation function and 64 hidden units. It outputs the attention density parameters.
D.3 ATTENTION MECHANISM
The attention mechanism takes the parameters from the encoder and forms an attention density, It then computes
(T()(
(18)
for input to the classifier.
D.4 CLASSIFIER
The classifier has two hidden layers with ReLUU activation and outputs class probabilities. hidden layer has 64 hidden units.
Each
http:p///iitiiiccooooo////aaaaaa fication
22


Reviews:
[{"review_id": "soFRhxau__j", "reviewer": "Reviewer_w8oo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work is well-motivated and the authors clearly highlighted differences with previous work (section 3).\nMoreover, the contribution is well founded and the authors conducted detailed theoretical analysis of their approach.\n\nHowever, there are computational limits in the proposed method, as highlighted by the authors: the partition function lacks of a closed form expression (end of page 7).\nTherefore, they rely on numerical integration to compute it.\nAlthough this opens up possible research direction for future work, I would like to have more information about experrimental speed efficiency of kernel deformed exponential families  compared to standard sparsemax/softmax.\n\nMoreover, the benefit of the attention mechanism proposed by the authors is that it allows sparsity and multimodality: the paper would benefit of including experimental evidence that this mechanism is important, beside test-set accuracy. What is the actually sparsity ratio compared to sparsemax? How important is the multimodality property? (i.e. are there many instances where the attention map is *really* multimodal? Is it possible to quantify this?)", "summary_of_the_paper": "Many modern neural architectures, especially in natural language processing, rely heavily on the attention mechanism.\nPrevious work in the literature proposed to extend the softmax-based attention mechanism by using different distribution families.\nIn particular, the authors of this paper focus on variants of the attention mechanism that allow for continuous and sparse attention.\n\nThe authors propose kernel deformed exponential families, an extension of the exponential family that allows sparse and multimodal attention, contrary to most of previous work that focused on unimodal attention.", "summary_of_the_review": "Interesting work, however the experiments section lack of qualitative results regarding the proposed approach (i.e. multimodality benefit is only quickly showed for one dataset in Figure 1)", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Y-wwY5GZ-DF", "reviewer": "Reviewer_eE87", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is clearly written. However, the results are rather a straightforward extension of the existing work by Martins et al. (2020; 2021), in which finite-dimensional exponential families and their deformed variants are used to formulate the continuous attention mechanism. In Section 4, some conditions for the finiteness of integration are introduced for the kernel-based model. These results may be important as a fundamental property of kernel-based models. However, this paper does not reveal the significant advantage of kernel-based modeling as an ingredient of continuous attention mechanism. As the author pointed out, the numerical integration required in the proposed method is the problem that should be resolved. The current form of the proposed method is far from practical usage. \n\n\nSome questions: \n- How can one choose the parameter alpha in the deformed exponential family? It would be nice to show a data-dependent method of selecting the deformation parameter.\n- To compute the context c, Is a resampling method such as the Metropolis-Hastings algorithm an efficient approach? \n\n", "summary_of_the_paper": "The paper studies the continuous attention mechanism using the kernel exponential family and its deformed variant. This is an extension of existing works based on finite-dimensional exponential families. The authors investigated some theoretical conditions such that the RKHS defines the probability density functions. Numerical experiments showed that the proposed method works efficiently for some datasets. \n", "summary_of_the_review": "The proposed model in the paper seems a straightforward extension of existing works by Martins et al. (2020; 2021). Hence, the novelty of the paper is limited. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0GWUUsM4qWg", "reviewer": "Reviewer_wuA4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I think the subject that the manuscript aims to extend is of high current interest. But I think the authors have focused on an overly dry/technical aspect of the problem. The main theoretical contribution seems to be the statement of conditions under which a kernel exponential distribution exists (i.e., the normalization constant is finite).  \nI don't have any technical objections to this development.\nBut an attention mechanism is a means for obtaining improved performance, and I would have expected a clearer demonstration that the theoretical development is worth considering from a practical standpoint (i.e., is computationally light enough to be part of a deep network, and improves performance significantly). \n\nIn that respect, I found the experiments to be thin in terms of demonstrating how and why one should consider the proposed alternative over existing ones.\nInstead of considering three very short experiments, it would be more useful to focus on one experiment with a clear explanation of the computational load, and the steps taken in order to compute the attention vector. \n\nThe improvement obtained by using the proposed mechanism was also not clear to me -- for instance in the IMDB example, the results are close to when the attention mechanism is continuous sparsemax (from previous work). For uWave, the proposed attention mechanism does better than when alternatives are usedm, but the accuracy obtained is around the accuracty reported in the original paper (from 2009, i.e., the pre-deep learning era).\n\nI would suggest the authors to focus more on the experimental section.\nA discussion on computational cost is also welcome. The authors do mention the intention of replacing the (undesired, in my opinion) numerical integration, but even with Monte Carlo techniques, wouldn't this be a bottleneck?", "summary_of_the_paper": "The manuscript considers an extension of the attention mechanism framework developed by others in recent work (by Martins et al.). Specifically this framework allows to break free from the discrete nature of attention that typically consists of a weighted average of a finite set of vectors. This is realized by estimating a probability mass function (PMF) over the finite collection of vectors, and then computing the expected value. The generalization allows one to extend the finite collection to a continuum. This is then handled by using a probability distribution function (pdf) over the collection to compute an expected value. In recent work, various authors considered the probability distribution used in defining the attention mechanism to belong to either a unimodal exponential family, a \"deformed\" exponential family (deformed versions having possibly finite support), or a mixture of Gaussians. Traditional exponential family comprises pdfs that possess a finite set of sufficient statistics. In contrast, the kernel exponential family comprises pdfs that have essentially infinitely many sufficient statistics through the use of a kernel. The current manuscript proposes to employ a kernel exponential family, and a deformed kernel exponential family. This allows them to work with multimodal probability distributions, and/or distributions with compact support. The authors layout conditions under which the kernel versions of the (deformed) exponential family are defined. They also apply the new attention schemes to several datasets.", "summary_of_the_review": "I think the manuscript considers a subject of high current interest. The contribution is mostly theoretical, laying out conditions under which a pdf from a family exists (which is a fair question to consider). While I don't have any technical objections, the attention mechanism looks computationally costly, and I wonder if this is going to be an issue during training in practice. Also, I found the experimental evaluation weak, and hand-wavy. I would have expected a clear demonstration of how the method is used, what its computational cost is, and how it improves upon existing alternatives.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper extends the recent work on continuous-domain sparse attention mechanisms to use kernel parametrizations, and thus allow more flexible multi-modal shapes. Continuous attention extends the standard attention mechanisms to continuous-valued key/value/query functions, involving integrals over probability measures instead of sums over softmax-weighted sums. 

Kernel methods fit very well in the framework and provide great expressivity. Reviewers agree it is an interesting and well-motivated idea. The contribution of incorporating kernel families in continuous attention seems substantially novel in comparison to the previous work on the topic.

The main concern, however, is that the paper focuses too much on the theory and not enough on the modeling benefits  enabled by flexible kernels. I would stress that this isn't a question of *improving performance* purely (although quantitative results would help!) but perhaps more of qualitative results, demonstrating e.g. multimodality, selectivity, interpretability.

I very much look forward to a revised version, which I expect would be a strong paper.
Decision: Reject