# Kernel Deformed Exponential Families for Sparse Continuous Attention

Alexander Moreno & Supriya Nagesh
Georgia Institute of Technology
Atlanta, GA
<EMAIL_ADDRESS>
&Zhenke Wu & Walter Dempsey
University of Michigan
Ann Arbor, MI
<EMAIL_ADDRESS>
James M. Rehg
Georgia Institute of Technology
Atlanta, GA
<EMAIL_ADDRESS>corresponding author

###### 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 (Canu
& Smola, 2006) 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 multiple compact
regions of the data domain.

##  1 Introduction

Attention mechanisms take weighted averages of data representations (Bahdanau
et al., 2015), 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. (2020; 2021) extended attention to
continuous settings, 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 of their formulation.

Martins et al. (2020; 2021) explored unimodal attention densities: these only
give high importance to one region of data. Farinhas et al. (2021) 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 families, 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: a region of time has no effect on class
probabilities, or a region of an image is not some object. We would like to
use multimodal exponential and deformed exponential family attention
densities, and understand how Farinhas et al. (2021) relates to the
optimization problem of Martins et al. (2020; 2021).

This paper makes three contributions: 1) we introduce kernel deformed
exponential families, a 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 kernel, 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-partition 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.

The paper is organized as follows: we review continuous attention (Martins et
al., 2020; 2021). We then describe how mixture of Gaussian attention
densities, used in Farinhas et al. (2021), solve a different optimization
problem. We next describe kernel exponential families and give novel
normalization 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; 2021); Farinhas
et al. (2021); Tsai et al. (2019); Shukla & Marlin (2021). Martins et al.
(2020; 2021) 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 a deformed counterpart.
Farinhas et al. (2021) proposed a multi-modal continuous attention mechanism
via a mixture of Gaussians approach. We show that this solves a slightly
different optimization problem from Martins et al. (2020; 2021), and extend to
two further general density classes. Shukla & Marlin (2021) 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 a 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 (Tsai et al., 2019;
Choromanski et al., 2020). Also relevant are temporal transformer papers,
including Xu et al. (2019); Li et al. (2019; 2020); Song et al. (2018).
However none have continuous attention densities.

Kernel Exponential Families Canu & Smola (2006) proposed kernel exponential
families: Sriperumbudur et al. (2017) analyzed theory for density estimation.
Wenliang et al. (2019) parametrized the kernel with a deep neural network.
Other density estimation papers include Arbel & Gretton (2018); Dai et al.
(2019); Sutherland et al. (2018). We apply kernel exponential families as
attention densities to weight a 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 a condition for an 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) characterizing Farinhas et
al. (2021) in terms of the framework of Martins et al. (2020; 2021).

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

$\displaystyle c$ $\displaystyle=\mathbb{E}_{T\sim p}[V(T)].$ (1)

Here $V(t)$ the value function approximates a data representation, $T\sim
p(t)$ is the random variable or vector for locations (temporal, spatial, etc),
and $p(t)$ is the attention density.

To choose the attention density $p$, one takes a data representation $f$ and
finds $p$ ’similar’ to $f$ and thus to a data representation, but regularizing
$p$. Martins et al. (2020; 2021) did this, providing a rigorous formulation of
attention mechanisms. Given a probability space $(S,\mathcal{A},Q)$, let
$\mathcal{M}^{1}_{+}(S)$ be the set of densities with respect to $Q$. Assume
that $Q$ is dominated by a measure $\nu$ (i.e. Lebesgue) and that it has
density $q_{0}=\frac{dQ}{d\nu}$ with respect to $\nu$. Let
$S\subseteq\mathbb{R}^{D}$, $\mathcal{F}$ be a function class, and
$\Omega:\mathcal{M}_{+}^{1}(S)\rightarrow\mathbb{R}$ be a lower semi-
continuous, proper, strictly convex functional.

Given $f\in\mathcal{F}$, an attention density (Martins et al., 2020)
$\hat{p}:\mathcal{F}\rightarrow\mathbb{R}_{\geq 0}$ solves

$\displaystyle\hat{p}[f]$
$\displaystyle=\arg\max_{p\in\mathcal{M}_{+}^{1}(S)}\langle
p,f\rangle_{L^{2}(Q)}-\Omega(p).$ (2)

This maximizes regularized $L^{2}$ similarity between $p$ and a data
representation $f$. If $\Omega(p)$ is the negative differential entropy, the
attention density is Boltzmann Gibbs

$\displaystyle\hat{p}[f](t)$ $\displaystyle=\exp(f(t)-A(f)),$ (3)

where $A(f)$ ensures $\int_{S}\hat{p}[f](t)dQ=1$. If $f(t)=\theta^{T}\phi(t)$
for parameters and statistics
$\theta\in\mathbb{R}^{M},\phi(t)\in\mathbb{R}^{M}$ respectively, Eqn. 3
becomes an exponential family density. For $f$ in a reproducing kernel Hilbert
space $\mathcal{H}$, it becomes a 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 $\Omega(p)$ be the
$\alpha$-Tsallis negative entropy $\Omega_{\alpha}(p)$ (Tsallis, 1988),

$\displaystyle\Omega_{\alpha}(p)$
$\displaystyle=\begin{cases}\frac{1}{\alpha(\alpha-1)}\left(\int_{S}p(t)^{\alpha}dQ-1\right),\alpha\neq
1;\\\ \int_{S}p(t)\log p(t)dQ,\alpha=1,\end{cases}$

then $\hat{p}[f]$ for $f(t)=\theta^{T}\phi(t)$ lies in the deformed
exponential family (Tsallis, 1988; Naudts, 2004)

$\displaystyle\hat{p}_{\Omega_{\alpha}}[f](t)$
$\displaystyle=\exp_{2-\alpha}(\theta^{T}\phi(t)-A_{\alpha}(f)),$ (4)

where $A_{\alpha}(f)$ again ensures normalization and the density uses the
$\beta$-exponential

$\displaystyle\exp_{\beta}(t)$
$\displaystyle=\begin{cases}[1+(1-\beta)t]_{+}^{1/(1-\beta)},\beta\neq 1;\\\
\exp(t),\beta=1.\end{cases}$ (5)

For $\beta<1$, Eqn. 5 and thus deformed exponential family densities for
$1<\alpha\leq 2$ can return $0$ values. Values $\alpha>1$ (and thus $\beta<1$)
give thinner tails than the exponential family, while $\alpha<1$ gives fatter
tails. Setting $\beta=0$ is called sparsemax (Martins & Astudillo, 2016). In
this paper, we assume $1<\alpha\leq 2$, which is the sparse case studied in
Martins et al. (2020). We again propose to replace $f(t)=\theta^{T}\phi(t)$
with $f\in\mathcal{H}$, which leads to the novel kernel deformed exponential
families.

Computing Eqn. 1’s context vector requires parametrizing $V(t)$. Martins et
al. (2020) obtain a value function $V:S\rightarrow\mathbb{R}^{D}$ parametrized
by $\textbf{B}\in\mathbb{R}^{D\times N}$ by applying regularized multivariate
linear regression to estimate $V(t;\textbf{B})=\textbf{B}\Psi(t)$, where
$\Psi=\\{\psi_{n}\\}_{n=1}^{N}$ is a set of basis functions. Let $L$ 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 $\textbf{H}\in\mathbb{R}^{O\times L}$ on a
matrix $\textbf{F}\in\mathbb{R}^{N\times L}$ of basis functions
$\\{\psi_{n}\\}_{n=1}^{N}$ evaluated at observation locations
$\\{t_{l}\\}_{l=1}^{L}$

$\displaystyle\textbf{B}^{*}$
$\displaystyle=\arg\min_{\textbf{B}}\|\textbf{B}\textbf{F}-\textbf{H}\|_{F}^{2}+\lambda\|\textbf{B}\|_{F}^{2}.$
(6)

###  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; 2021). In fact their attention densities solve a related
but different optimization problem. Martins et al. (2020; 2021) show that
exponential family attention densities maximize a regularized linear predictor
of the expected sufficient statistics of locations. In contrast, Farinhas et
al. (2021) find a joint density over locations and latent states, and maximize
a regularized linear predictor of the expected joint sufficient statistics.
They then take the marginal location densities to be the attention densities.

Let $\Omega(p)$ be Shannon entropy and consider two optimization problems:

$\displaystyle\arg\max_{p\in\mathcal{M}_{+}^{1}(S)}\langle\theta,\mathbb{E}_{p}[\phi(T)]\rangle_{l^{2}}-\Omega(p)$
$\displaystyle\arg\max_{p\in\mathcal{M}_{+}^{1}(S)}\langle\theta,\mathbb{E}_{p}[\phi(T,Z)]\rangle_{l^{2}}-\Omega(p)$

The first is Eqn. 2 with $f=\theta^{T}\phi(t)$ and rewritten to emphasize
expected sufficient statistics. If one solves the second with variables $Z$,
we recover an Exponential family joint density

$\displaystyle\hat{p}_{\Omega_{\alpha}}[f](t,z)=\exp(\theta^{T}\phi(t,z)-A(\theta)).$

This encourages the joint density of $T,Z$ to be similar to a complete data
representation $\theta^{T}\phi(t,z)$ of both location variables $T$ and latent
variables $Z$, instead of encouraging the density of $T$ to be similar to an
observed data representation $\theta^{T}\phi(t)$. The latter optimization is
equivalent to

$\displaystyle\arg\max_{p\in\mathcal{M}_{+}^{1}(S)}\Omega(p)$ s.t.
$\displaystyle\mathbb{E}_{p(T,Z)}[\phi_{m}(T,Z)]=c_{m},m=1,\cdots,M.$

The constraint terms $c_{m}$ are determined by $\theta$. Thus, this maximizes
the joint entropy of $Z$ and $T$, subject to constraints on the expected joint
sufficient statistics.

To recover EM learned Gaussian mixture densities, one must select $\phi_{m}$
so that the marginal distribution of $T$ will be a mixture of Gaussians, and
relate $c_{m}$ to the EM algorithm used to learn the mixture model parameters.
For the first, assume that $Z$ is a multinomial random variable with a single
trial taking $|Z|$ possible values and let
$\phi(t,z)=(I(z=1),\cdots,I(z=|Z|-1),I(z=1)t,I(z=1)t^{2},\cdots,I(z=|Z|)t,I(z=|Z|)t^{2})$.
These are multinomial sufficient statistics with a single trial, followed by
the sufficient statistics of $|Z|$ Gaussians multiplied by indicators for each
$z$. Then $p(T|Z)$ will be Gaussian, $p(Z)$ will be multinomial, and $p(T)$
will be a Gaussian mixture. For contraints, Farinhas et al. (2021) have

$\displaystyle\mathbb{E}_{p(T,Z)}[\phi_{m}(T,Z)]=\sum_{l=1}^{L}w_{l}\sum_{k=1}^{|Z|}p_{\textrm{old}}(Z=k|t_{l})\phi_{m}(t_{l},k),m=1,\cdots,M$
(7)

at each EM iteration. Here $p_{\textrm{old}}(Z|t_{l})$ is the previous
iteration’s latent state density conditional on the observation value, $w_{l}$
are discrete attention weights, and $t_{l}$ is a 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 $z$ and
$t_{l}$ given by old model parameters. An alternative is simply to let
$\theta$ be the output of a neural network. While the constraints lack the
intuition of 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 a new deformed counterpart to
obtain flexible attention densities solving Eqn. 2 with the same regularizers.
We first review kernel exponential families. We then give a novel theoretical
result describing when an unnormalized kernel exponential family density 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. We show similar normalization results based
on 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, replacing $f(t)=\theta^{T}\phi(t)$ with $f$ in a reproducing
kernel Hilbert space $\mathcal{H}$ (Aronszajn, 1950) with kernel $k:S\times
S\rightarrow\mathbb{R}$. Densities can be written as

$\displaystyle p(t)$ $\displaystyle=\exp(f(t)-A(f))$
$\displaystyle=\exp(\langle f,k(\cdot,t)\rangle_{\mathcal{H}}\rangle-A(f)),$

where the second equality follows from the reproducing property. A challenge
is to choose $\mathcal{H},Q$ so that a normalizing constant exists, i.e.,
$\int_{S}\exp(f(t))dQ<\infty$. Kernel exponential family distributions can
approximate any continuous density over a compact domain arbitrarily well in
KL divergence, Hellinger, and $L^{p}$ distance (Sriperumbudur et al., 2017).
However relevant integrals including the normalizing constant generally
require numerical integration.

To avoid infinite dimensionality one generally assumes a representation of the
form

$\displaystyle f$ $\displaystyle=\sum_{i=1}^{I}\gamma_{i}k(\cdot,t_{i}),$

where for density estimation (Sriperumbudur et al., 2017) the $t_{i}$ are the
observation locations. However, this requires using one 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_{i}\\}_{i=1}^{I}$ where $I$ is less than the number of observation
locations.

For a given pair $\mathcal{H},k$, how can we choose $Q$ to ensure that the
normalization constant exists? We first give a simple example of
$\mathcal{H},f$ and $Q$ where the normalizing constant does not exist.

######  Example 1.

Let $Q$ be the law of a $\mathcal{N}(0,1)$ distribution and $S=\mathbb{R}$.
Let $\mathcal{H}=\textrm{span}\\{t^{3},t^{4}\\}$ with
$k(x,y)=x^{3}y^{3}+x^{4}y^{4}$ and $f(t)=t^{3}+t^{4}=k(t,1)$. Then

$\displaystyle\int_{S}\exp(f(t))dQ$
$\displaystyle=\int_{\mathbb{R}}\exp(\frac{t^{2}}{2}+t^{3}+t^{4})dt$ (8)

where the integral diverges.

Figure 1: Attention densities for kernel deformed exponential families for the
first attention head of the uWave 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.

###  4.1 Theory for Kernel Exponential Families

We provide sufficient conditions for $Q$ and $\mathcal{H}$ so that $A(f)$ the
log-partition function exists. We relate $\mathcal{H}$’s kernel growth rate to
the tail decay of the random variable or vector $T_{Q}$ with law $Q$.

######  Proposition 1.

Let $\tilde{p}(t)=\exp(f(t))$ where $f\in\mathcal{H}$ an RKHS with kernel $k$.
Assume $k(t,t)\leq L_{k}\|t\|^{\xi}_{2}+C_{k}$ for constants
$L_{k},C_{k},\xi>0$. Let $Q$ be the law of a random vector $T_{Q}$, so that
$Q(A)=P(T_{Q}\in A)$. Assume $\forall u$ s.t. $\|u\|_{2}=1$,

$\displaystyle P(|u^{T}T_{Q}|\geq z)\leq C_{q}\exp(-vz^{\eta})$ (9)

for some constants $\eta>\frac{\xi}{2},C_{Q},v>0$. Then

$\displaystyle\int_{S}\tilde{p}(t)dQ<\infty.$

###### Proof.

See Appendix A.1 ∎

Based on $k(t,t)$’s growth, we can vary what tail decay rate for $T_{Q}$
ensures we can normalize $\tilde{p}(t)$. Wenliang et al. (2019) also proved
normalization conditions, but focused on random variables with exponential
power density for a specific growth rate of $k(t,t)$ rather than relating tail
decay to growth rate. By focusing on tail decay, our result can be applied to
non-symmetric base densities. Specific kernel bound growth rate terms $\xi$
lead to allowing different tail decay rates.

######  Corollary 1.

For $\xi=4$, $T_{Q}$ can be any sub-Gaussian random vector. For $\xi=2$ it can
be any sub-exponential. For $\xi=0$ it can have any density.

###### Proof.

See Appendix A.2 ∎

###  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 in the deformed exponential term. This mirrors kernel
exponential families. We write

$\displaystyle p(t)$ $\displaystyle=\exp_{2-\alpha}(f(t)-A_{\alpha}(f)),$

where $f\in\mathcal{H}$ with kernel $k$. Fig. 1b shows that they can have
support over disjoint intervals.

####  4.2.1 Normalization Theory

We construct a valid kernel deformed exponential family density from $Q$ and
$f\in\mathcal{H}$. We first discuss the deformed log normalizer. In
exponential family densities, the log-normalizer is the log of the normalizer.
For deformed exponentials, the following holds.

######  Lemma 1.

Let $Z>0$ be a constant. Then for $1<\alpha\leq 2$,

$\displaystyle\frac{1}{Z}\exp_{2-\alpha}(Z^{\alpha-1}f(t))$
$\displaystyle=\exp_{2-\alpha}(f(t)-\log_{\alpha}Z)$

where

$\displaystyle\log_{\beta}t$
$\displaystyle=\begin{cases}\frac{t^{1-\beta}-1}{1-\beta}\textrm{ if
}t>0,\beta\neq 1;\\\ \log(t)\textrm{ if }t>0,\beta=1;\\\ \textrm{undefined if
}t\leq 0.\end{cases}$

###### Proof.

See Appendix B.1 ∎

We describe a normalization sufficient condition analagous to Proposition 1
for the sparse deformed kernel exponential family. With Lemma 1, we can take
an unnormalized $\exp_{2-\alpha}(\tilde{f}(t))$ and derive a valid normalized
kernel deformed exponential family density. We only require that an affine
function of the terms in the deformed-exponential are negative for large
magnitude $t$.

######  Proposition 2.

For $1<\alpha\leq 2$ assume $\tilde{p}(t)=\exp_{2-\alpha}(\tilde{f}(t))$ with
$\tilde{f}\in\mathcal{H}$, $\mathcal{H}$ is a RKHS with kernel $k$. If
$\exists C_{t}>0$ s.t. for $\|t\|_{2}>C_{t}$, $(\alpha-1)\tilde{f}(t)+1\leq 0$
and $k(t,t)\leq L_{k}\|t\|^{\xi}_{2}+C_{k}$ for some $\xi>0$, then
$\int_{S}\exp_{2-\alpha}(\tilde{f}(t))dQ<\infty$.

###### 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 2, assume
$\exp_{2-\alpha}(\tilde{f}(t))>0$ on a set $A\subseteq S$ such that $Q(A)>0$,
then $\exists$ constants $Z>0$, $A_{\alpha}(f)\in\mathbb{R}$ such that for
$f(t)=\frac{1}{Z^{\alpha-1}}\tilde{f}(t)$, the following holds

$\displaystyle\int_{S}\exp_{2-\alpha}(f(t)-A_{\alpha}(f))dQ=1.$

###### Proof.

See Appendix B.3. ∎

We thus estimate $\tilde{f}(t)=(Z)^{\alpha-1}f(t)$ and normalize to obtain a
density of the desired form.

####  4.2.2 Approximation Theory

Under certain kernel conditions, kernel deformed exponential family densities
can approximate densities of a similar form where the RKHS function is
replaced with a $C_{0}(S)$ 111continuous function on domain $S$ vanishing at
infinity function.

######  Proposition 3.

Define

$\displaystyle\mathcal{P}_{0}$
$\displaystyle=\\{\pi_{f}(t)=\exp_{2-\alpha}(f(t)-A_{\alpha}(f)),t\in S:f\in
C_{0}(S)\\}$

where $S\subseteq\mathbb{R}^{d}$. Suppose $k(x,\cdot)\in C_{0}(S),\forall x\in
S$ and

$\displaystyle\int\int k(x,y)d\mu(x)d\mu(y)>0,\forall\mu\in
M_{b}(S)\backslash\\{0\\}.$ (10)

here $M_{b}(S)$ is the space of bounded measures over $S$. Then the set of
deformed exponential families is dense in $\mathcal{P}_{0}$ wrt $L^{r}(Q)$
norm and Hellinger distance.

###### Proof.

See Appendix B.4 ∎

We apply this to approximate fairly general densities with kernel deformed
exponential families.

######  Theorem 1.

Let $q_{0}\in C(S)$, such that $q_{0}(t)>0$ for all $t\in S$, where
$S\subseteq\mathbb{R}^{d}$ is locally compact Hausdorff and $q_{0}(t)$ is the
density of $Q$ with respect to a dominating measure $\nu$. Suppose there
exists $l>0$ such that for any $\epsilon>0,\exists R>0$ satisfying
$|p(t)-l|\leq\epsilon$ for any $t$ with $\|t\|_{2}>R$. Define

$\displaystyle\mathcal{P}_{c}$ $\displaystyle=\\{p\in
C(S):\int_{S}p(t)dQ=1,p(t)\geq 0,\forall t\in S\textrm{ and }p-l\in
C_{0}(S)\\}.$

Suppose $k(t,\cdot)\in C_{0}(S)\forall t\in S$ and the kernel integration
condition (Eqn. 10) holds. Then kernel deformed exponential families are dense
in $\mathcal{P}_{c}$ wrt $L^{r}$ norm, Hellinger distance and Bregman
divergence for the $\alpha$-Tsallis negative entropy functional.

###### Proof.

See Appendix B.5. ∎

For uniform $q_{0}$, 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 is Bregman divergence with the Shannon entropy
functional: we 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 et al. (2017)’s approximation results to
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 computes attention densities and the context vector. The
backwards pass uses automatic differentiation. We assume a vector
representation $v\in\mathbb{R}^{|v|}$ computed from the locations we take an
expectation over. For kernel exponential families we compute kernel weights
$\\{\gamma_{i}\\}_{i=1}^{I}$ for $f(t)=\sum_{i=1}^{I}\gamma_{i}k(t,t_{i})$

$\displaystyle\gamma_{i}$ $\displaystyle=w_{i}^{T}v,$

and compute $Z=\int_{S}\exp(f(t))dQ$ numerically. For the deformed case we
compute $\tilde{\gamma}_{i}=w_{i}^{T}v$ and
$\tilde{f}(t)=(Z)^{\alpha-1}f(t)=\sum_{i=1}^{I}\tilde{\gamma}_{i}k(t,t_{i})$
followed by $Z=\int_{S}\exp_{2-\alpha}(\tilde{f}(t))dQ$. The context

$\displaystyle c$ $\displaystyle=\mathbb{E}_{T\sim
p}[V(T)]=\textbf{B}\mathbb{E}_{p}[\Psi(t)]$

requires taking the expectation of $\Psi(T)$ with respect to a (possibly
deformed) kernel exponential family density $p$. Unlike Martins et 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 1
shows how to compute a continuous attention mechanism for a kernel deformed
exponential family attention density. The kernel exponential family case is
similar.

Algorithm 1 Continuous Attention Mechanism via Kernel Deformed Exponential
Families

Choose base density $q_{0}(t)$ and kernel $k$. Inducing point locations
$\\{t_{i}\\}_{i=1}^{I}$

Input Vector representation $v$ of input object i.e. document representation

Parameters $\\{\tilde{\gamma}_{i}\\}_{i=1}^{I}$ the weights for
$\tilde{f}(t)=(Z)^{\alpha-1}f(t)=\sum_{i=1}^{I}\tilde{\gamma}_{i}k(t,t_{i})$,
matrix B for basis weights for value function $V(t)=\textbf{B}\Psi(t)$. $I$ is
number of inducing points.

Forward Pass

Compute $Z=\int\exp_{2-\alpha}(\tilde{f}(t))dQ(t)$ to obtain
$p(t)=\frac{1}{Z}\exp_{2-\alpha}(\tilde{f}(t))$ via numerical integration

Compute $\mathbb{E}_{T\sim p}[\Psi(T)]$ via numerical integration

Compute $c=\mathbb{E}_{T\sim p}[V(T)]=\textbf{B}\mathbb{E}_{p}[\Psi(T)]$

Backwards Pass use automatic differentiation

##  5 Experiments

For document classification, we follow Martins et al. (2020)’s architecture.
For the remaining, architectures have four parts: 1) an encoder takes a
discrete representation of a time series and outputs attention density
parameters. 2) The value function takes a time series representation (original
or after passing through a neural network) and does (potentially multivariate)
linear regression to obtain parameters B for a function $V(t;\textbf{B})$.
These are combined to compute 3) context $c=\mathbb{E}_{p}[V(T)]$, which is
used in a 4) classifier. Fig. 2 in the Appendices visualizes this.

###  5.1 Document Classification

We extend Martins et al. (2020)’s code222Martins et al. (2020)’s repository
for this dataset is https://github.com/deep-spin/quati for the IMDB sentiment
classification dataset (Maas et al., 2011). This starts with a document
representation $v$ computed from a convolutional neural network and uses an
LSTM attention model. We use a Gaussian base density and kernel, and divide
the interval $[0,1]$ into $I=10$ inducing points where we evaluate the kernel
in $f(t)=\sum_{i=1}^{I}\gamma_{i}k(t,t_{i})$. We set the bandwidth to be
$0.01$ for $I=10$. Table 1 shows 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.

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 attention, continuous sparsemax truncated parabola, and kernel softmax and sparsemax use kernel exponential and deformed exponential family with a Gaussian kernel. The latter has $\alpha=2$ in exponential and multiplication terms. $N$: basis functions, $I=10$ inducing points, bandwidth $0.01$. Attention | N=64 | N=128 | N=256
---|---|---|---
Cts Softmax | 67.78$\pm$1.64 | 67.70$\pm$ 2.49 | 68.00$\pm$ 2.24
Cts Sparsemax | 74.20$\pm$2.72 | 74.69$\pm$3.78 | 74.58$\pm$4.27
Gaussian Mixture | 81.13$\pm$1.76 | 80.99$\pm$2.79 | 79.04$\pm$2.33
Kernel Softmax | 93.85$\pm$0.60 | 94.26$\pm$0.75 | 93.83$\pm$0.60
Kernel Sparsemax | 92.32$\pm$1.09 | 92.15$\pm$0.79 | 92.14$\pm$0.96
Table 2: Accuracy results on uWave gesture classification dataset for the irregularly sampled case. All methods use $100$ attention heads. Gaussian mixture uses $100$ components (and thus $300$ parameters per head), and kernel methods use $256$ inducing points. Attention | Accuracy | F1
---|---|---
Cts Softmax | 96.97 | 83.69
Cts Sparsemax | 96.04 | 73.71
Gaussian Mixture | 97.20 | 84.89
Kernel Softmax | 96.75 | 83.27
Kernel Sparsemax | 96.86 | 84.90
Table 3: Accuracy results on MIT BIH Arrhythmia Classification dataset. For F1
score, kernel softmax and continuous softmax have similar results, while
kernel sparsemax drastically outperforms continuous sparsemax. For accuracy,
the Gaussian mixture slightly beats other methods.

###  5.2 uWave Dataset

We analyze uWave (Liu et al., 2009): accelerometer time series with eight
gesture classes. We follow Li & Marlin (2016)’s 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.
Table 2 shows results. Our highest accuracy is $94.26\%$, the unimodal case’s
best is $74.69\%$, and the mixture’s best is $81.13\%$. Since this dataset is
small, we report $\pm 1.96$ standard deviations from $10$ runs. Fig. 1 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.

##  6 ECG heartbeat classification

We use the MIT Arrhythmia Database’s (Goldberger et al., 2000) Kaggle
333https://www.kaggle.com/mondejar/mitbih-database. 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 is a feedforward neural network with the original data as
input, and our classifier is a feedforward network. Table 3 shows results. All
accuracies are very similar, but the $F1$ score of kernel sparsemax is
drastically higher. Additional details are in Appendix D.

##  7 Discussion

In this paper we extend continuous attention mechanisms to use kernel
exponential and deformed exponential family attention densities. The latter is
a new flexible class of 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 to 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 in the dense case and
drastically better in the sparse case.

###  7.1 Limitations and Future Work

A limitation of this work was the use of numerical integration, which scales
poorly with the dimensionality of the locations. Because of this we restricted
our applications to temporal and text data. This still allows for multiple
observation dimensions at a given location. A future direction 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 to
choose the number of inducing points.

## References

  * Arbel & Gretton (2018) Michael Arbel and Arthur Gretton.  Kernel conditional exponential family.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 1337–1346. PMLR, 2018.
  * Aronszajn (1950) Nachman Aronszajn.  Theory of reproducing kernels.  _Transactions of the American mathematical society_ , 68(3):337–404, 1950.
  * Bahdanau et al. (2015) Dzmitry Bahdanau, Kyung Hyun Cho, and Yoshua Bengio.  Neural machine translation by jointly learning to align and translate.  In _3rd International Conference on Learning Representations, ICLR 2015_ , 2015.
  * Canu & Smola (2006) Stéphane Canu and Alex Smola.  Kernel methods and the exponential family.  _Neurocomputing_ , 69(7-9):714–720, 2006.
  * Choromanski et al. (2020) 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.
  * Dai et al. (2019) 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 on Artificial Intelligence and Statistics_ , pp. 2321–2330. PMLR, 2019.
  * Farinhas et al. (2021) António Farinhas, André FT Martins, and Pedro MQ Aguiar.  Multimodal continuous visual attention mechanisms.  _arXiv preprint arXiv:2104.03046_ , 2021.
  * Goldberger et al. (2000) Ary L Goldberger, Luis AN Amaral, Leon Glass, Jeffrey M Hausdorff, Plamen Ch Ivanov, Roger G Mark, Joseph E Mietus, George B Moody, Chung-Kang Peng, and H Eugene Stanley.  Physiobank, physiotoolkit, and physionet: components of a new research resource for complex physiologic signals.  _circulation_ , 101(23):e215–e220, 2000.
  * Li et al. (2019) 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 on time series forecasting.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), _Advances in Neural Information Processing Systems_ , volume 32, pp. 5243–5253. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/6775a0635c302542da2c32aa19d86be0-Paper.pdf.
  * Li & Marlin (2016) 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 https://proceedings.neurips.cc/paper/2016/file/9c01802ddb981e6bcfbec0f0516b8e35-Paper.pdf.
  * Li et al. (2020) Yikuan Li, Shishir Rao, José Roberto Ayala Solares, Abdelaali Hassaine, Rema Ramakrishnan, Dexter Canoy, Yajie Zhu, Kazem Rahimi, and Gholamreza Salimi-Khorshidi.  Behrt: transformer for electronic health records.  _Scientific reports_ , 10(1):1–12, 2020.
  * Liu et al. (2009) Jiayang Liu, Lin Zhong, Jehan Wickramasuriya, and Venu Vasudevan.  uwave: Accelerometer-based personalized gesture recognition and its applications.  _Pervasive and Mobile Computing_ , 5(6):657–675, 2009.
  * Maas et al. (2011) Andrew Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng, and Christopher Potts.  Learning word vectors for sentiment analysis.  In _Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies_ , pp. 142–150, 2011\.
  * Martins & Astudillo (2016) Andre Martins and Ramon Astudillo.  From softmax to sparsemax: A sparse model of attention and multi-label classification.  In _International Conference on Machine Learning_ , pp. 1614–1623. PMLR, 2016.
  * Martins et al. (2020) 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 Information Processing Systems_ , volume 33, pp. 20989–21001. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/f0b76267fbe12b936bd65e203dc675c1-Paper.pdf.
  * Martins et al. (2021) 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:2108.01988_ , 2021.
  * Naudts (2004) Jan Naudts.  Estimators, escort probabilities, and phi-exponential families in statistical physics.  _arXiv preprint math-ph/0402005_ , 2004.
  * Shukla & Marlin (2021) Satya Narayan Shukla and Benjamin Marlin.  Multi-time attention networks for irregularly sampled time series.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=4c0J6lwQ4_.
  * Song et al. (2018) 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.
  * Sriperumbudur et al. (2017) 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–1888, 2017.
  * Sriperumbudur et al. (2011) 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.
  * Sutherland et al. (2018) Dougal Sutherland, Heiko Strathmann, Michael Arbel, and Arthur Gretton.  Efficient and principled score estimation with nyström kernel exponential families.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 652–660. PMLR, 2018.
  * Titsias (2009) Michalis Titsias.  Variational learning of inducing variables in sparse gaussian processes.  In _Artificial intelligence and statistics_ , pp. 567–574. PMLR, 2009.
  * Tsai et al. (2019) 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.
  * Tsallis (1988) Constantino Tsallis.  Possible generalization of boltzmann-gibbs statistics.  _Journal of statistical physics_ , 52(1):479–487, 1988.
  * 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 _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , pp. 6000–6010, 2017.
  * Wang et al. (2012) Shaojun Wang, Dale Schuurmans, and Yunxin Zhao.  The latent maximum entropy principle.  _ACM Transactions on Knowledge Discovery from Data (TKDD)_ , 6(2):1–42, 2012.
  * Wenliang et al. (2019) 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.
  * Xu et al. (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'Alché-Buc, E. Fox, and R. Garnett (eds.), _Advances in Neural Information Processing Systems_ , volume 32, pp. 15915–15925. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/cf34645d98a7630e2bcca98b3e29c8f2-Paper.pdf.

##  Appendix A Proof Related to Proposition 1

###  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 $T_{Qd}$ of $T_{Q}$. Using the RKHS function bound, we then bound
the integral of the unnormalized density in terms of expectations 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 series, 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 to bound $f$ in terms of two constants and the
absolute value of the point at which it is evaluated.

$\displaystyle|f(t)|$ $\displaystyle=|\langle
f,k(t,\cdot)\rangle_{\mathcal{H}}|\textrm{ reproducing property}$
$\displaystyle\leq\|f\|_{\mathcal{H}}\|k(t,\cdot)\|_{\mathcal{H}}\textrm{
Cauchy Schwarz}$ $\displaystyle=\|f\|_{\mathcal{H}}\sqrt{\langle
k(t,\cdot),k(t,\cdot)\rangle_{\mathcal{H}}}$
$\displaystyle=\|f\|_{\mathcal{H}}\sqrt{k(t,t)}$
$\displaystyle\leq\|f\|_{\mathcal{H}}\sqrt{L_{k}\|t\|^{\xi}+C_{k}}\textrm{ by
assumption}$ $\displaystyle\leq C_{0}+C_{1}\|t\|^{|\xi|/2}\textrm{ for some
$C_{1},C_{2}>0$}.$

We can write $T_{Q}=(T_{Q1},\cdots,T_{QD})$. Let $e_{d}$ be a standard
Euclidean basis vector. Then by the assumption and setting $u=e_{d}$ we have

$\displaystyle P(|T_{Qd}|\geq z)\leq C_{q}\exp(-vz^{\eta})$

Letting $Q_{d}$ be the marginal law,

$\displaystyle\int_{S}\exp(f(t))dQ$
$\displaystyle\leq\int_{S}\exp(C_{0}+C_{1}\|t\|^{\xi/2})dQ$
$\displaystyle=\exp(C_{0})\int_{S}\exp(C_{1}\|t\|^{\xi/2})dQ$
$\displaystyle=\exp(C_{0})\mathbb{E}\exp(C_{1}\|T_{Q}\|^{\xi/2})$
$\displaystyle\leq\exp(C_{0})\mathbb{E}\exp(C_{1}(\sqrt{d}\max_{d=1,\cdots,D}|T_{Qd}|)^{\xi/2})$
$\displaystyle\leq\exp(C_{0})\sum_{d=1}^{D}\mathbb{E}\exp(C_{2}|T_{Qd}|^{\xi/2})$

which will be finite if each $\mathbb{E}\exp(C_{2}|T_{Qd}|^{\xi/2})<\infty$.
Now letting $S_{d}$ be the relevant dimension of $S$,

$\displaystyle\mathbb{E}\exp(C_{2}|T_{Qd}|^{\xi/2})$
$\displaystyle=\int_{S_{d}}\exp(C_{2}|t_{d}|^{\xi/2})dQ_{d}$
$\displaystyle\leq\sum_{j=-\infty}^{-1}\int_{j}^{j+1}\exp(C_{2}|t_{d}|^{\xi/2})dQ_{d}+\sum_{j=0}^{\infty}\int_{j}^{j+1}\exp(C_{2}|t_{d}|^{\xi/2})dQ_{d}$

where the inequality follows since $S_{d}\subseteq\mathbb{R}$, $\exp$ is 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\geq 0$

$\displaystyle Q_{d}([j,j+1))$ $\displaystyle=P(T_{d}\geq j)-P(T_{d}\geq j+1)$
$\displaystyle\leq P(T_{d}\geq j)$ $\displaystyle\leq
C_{q}\exp(-vj^{\eta})\textrm{ by assumption}$

Then

$\displaystyle\sum_{j=0}^{\infty}\int_{j}^{j+1}\exp(C_{2}|t_{d}|^{\xi/2})dQ_{d}$
$\displaystyle\leq\sum_{j=0}^{\infty}\exp(C_{2}|j|^{\xi/2})Q_{d}([j,j+1))$
$\displaystyle\leq\sum_{j=0}^{\infty}C_{Q}\exp(C_{2}|j|^{\xi/2}-vj^{\eta})$

Let $a_{j}=\exp(C_{2}|j|^{\xi/2}-vi^{\eta})$. We will use the ratio test to
show that the RHS converges. We have

$\displaystyle\left|\frac{a_{j+1}}{a_{j}}\right|$
$\displaystyle=\exp(C_{2}((j+1)^{\xi/2}-j^{\xi/2})-v[(j+1)^{\eta}-j^{\eta}]).$
(11)

We want this ratio to be $<1$ for large $j$. We thus need to select $\eta$ so
that for sufficiently large $j$, we have

$\displaystyle\frac{C_{1}}{v}((j+1)^{\xi/2}-j^{\xi/2})<[(j+1)^{\eta}-j^{\eta}].$

Assume that $\eta>\frac{\xi}{2}$. Then

$\displaystyle\frac{(j+1)^{\eta}-j^{\eta}}{(j+1)^{\xi/2}-j^{\xi/2}}$
$\displaystyle=\frac{j^{\eta}[(1+\frac{1}{j})^{\eta}-1]}{j^{\xi/2}[(1+\frac{1}{j})^{\xi/2}-1]}$
$\displaystyle\geq j^{\eta-\xi/2}.$

Since the RHS is unbounded for $\eta>\frac{\xi}{2}$, we have that Eqn. 11
holds for sufficiently large $j$. By the ratio test
$\mathbb{E}_{q_{d}(t)}\exp(C_{2}|T_{d}|^{\xi/2})=\sum_{j=-\infty}^{-1}\int_{j}^{j+1}\exp(C_{2}|t_{d}|^{\xi/2})dQ_{d}+\sum_{j=0}^{\infty}\int_{j}^{j+1}\exp(C_{2}|t_{d}|^{\xi/2})dQ_{d}$
is finite. Thus putting everything together we have

$\displaystyle\int_{S}\exp(f(t))dQ$
$\displaystyle\leq\int_{S}\exp(C_{0}+C_{1}\|t\|^{\xi/2})dQ$
$\displaystyle<\exp(C_{0})\sum_{d=1}^{D}\mathbb{E}\exp(C_{2}|T_{Qd}|^{\xi/2})$
$\displaystyle<\infty$

and $\tilde{p}(t)$ can be normalized.

∎

###  A.2 Proof of Corollary 1

###### Proof.

Let $\xi=4$. Then $\eta>2$ and

$\displaystyle P(|u^{T}T|>t)$ $\displaystyle\leq P(|u^{T}T|\geq t)\textrm{
monotonicity}$ $\displaystyle\leq C_{Q}\exp(-vt^{\eta})$
$\displaystyle<C_{Q}\exp(-vt^{2}).$

The second case is similar. For the uniformly bounded kernel,

$\displaystyle\int_{S}\exp(\langle f,k(\cdot,t)\rangle_{\mathcal{H}})dQ$
$\displaystyle\leq\exp(\|f\|_{\mathcal{H}}\sqrt{C_{k}})\int_{S}dQ$
$\displaystyle=\exp(\|f\|_{\mathcal{H}}\sqrt{C_{k}})$ $\displaystyle<\infty.$

The first line follows from Cauchy Schwarz and $\xi=0$ ∎

##  Appendix B Proofs Related to Kernel Deformed Exponential Family

###  B.1 Proof of Lemma 1

###### Proof.

The high level idea is to express a term inside the deformed exponential
family that becomes $1/Z$ once outside.

$\displaystyle\exp_{2-\alpha}(f(t)-\log_{\alpha}(Z))$
$\displaystyle=[1+(\alpha-1)(f(t)-\log_{\alpha}Z)]^{\frac{1}{\alpha-1}}_{+}$
$\displaystyle=[1+(\alpha-1)f(t)-(\alpha-1)\frac{Z^{1-\alpha}-1}{1-\alpha}]^{\frac{1}{\alpha-1}}_{+}$
$\displaystyle=[1+(\alpha-1)f(t)+Z^{1-\alpha}-1]^{\frac{1}{\alpha-1}}_{+}$
$\displaystyle=[(\alpha-1)f(t)+Z^{1-\alpha}]^{\frac{1}{\alpha-1}}_{+}$
$\displaystyle=[(\alpha-1)f(t)\frac{Z^{\alpha-1}}{Z^{\alpha-1}}+Z^{1-\alpha})]^{\frac{1}{\alpha-1}}_{+}$
$\displaystyle=\frac{1}{Z}[(\alpha-1)f(t)\frac{1}{Z^{\alpha-1}}+1]^{\frac{1}{\alpha-1}}_{+}$
$\displaystyle=\frac{1}{Z}\exp_{2-\alpha}(Z^{\alpha-1}f(t))$

∎

###  B.2 Proof of Proposition 2

###### Proof.

$\displaystyle\int_{S}\exp_{2-\alpha}(\tilde{f}(t))dQ$
$\displaystyle=\int_{S}[1+(\alpha-1)\tilde{f}(t)]_{+}^{\frac{1}{\alpha-1}}dQ$
$\displaystyle=\int_{\|t\|\leq
C_{t}}[1+(\alpha-1)\tilde{f}(t)]_{+}^{\frac{1}{\alpha-1}}dQ$
$\displaystyle\leq\int_{\|t\|\leq
C_{t}}[1+(\alpha-1)(C_{0}+C_{1}|C_{t}|^{\xi/2})]_{+}^{\frac{1}{\alpha-1}}dQ$
$\displaystyle<\infty$

∎

###  B.3 Proof of Corollary 2

###### Proof.

From proposition 2 and the assumption,

$\displaystyle\int_{S}\exp_{2-\alpha}(\tilde{f}(t))dQ$ $\displaystyle=Z$

for some $Z>0$. Then

$\displaystyle\int_{S}\frac{1}{Z}\exp_{2-\alpha}(Z^{\alpha-1}f(t))dQ$
$\displaystyle=1$
$\displaystyle\int_{S}\exp_{2-\alpha}(f(t)-\log_{\alpha}Z)dQ$
$\displaystyle=1$

where the second line follows from lemma 1. Set
$A_{\alpha}(f)=\log_{\alpha}(Z)$ and we are done. ∎

###  B.4 Proof of Proposition 3

###### Proof.

The kernel integration condition tells us that $\mathcal{H}$ is dense in
$C_{0}(S)$ with respect to $L^{\infty}$ norm. This was shown in Sriperumbudur
et al. (2011). For the $L^{r}$ norm, we apply $\|p_{f}-p_{g}\|_{L^{r}}\leq
2M_{\exp}\|f-g\|_{\infty}$ from Lemma 5 with $f\in C_{0}(S)$,
$g\in\mathcal{H}$, and $f_{0}=f$. $L^{1}$ convergence implies Hellinger
convergence. ∎

###  B.5 Proof of Theorem 1

###### Proof.

For any $p\in\mathcal{P}_{c}$, define $p_{\delta}=\frac{p+\delta}{1+\delta}$.
Then

$\displaystyle\|p-p_{\delta}\|_{r}$
$\displaystyle=\frac{\delta}{1+\delta}\|p\|_{r}$ $\displaystyle\rightarrow 0$

for $1\leq r\leq\infty$. Thus for any $\epsilon>0,\exists\delta_{\epsilon}>0$
such that for any $0<\theta<\delta_{\epsilon}$, we have
$\|p-p_{\theta}\|_{r}\leq\epsilon$, where $p_{\theta}(t)>0$ for all $t\in S$.

Define
$f=\left(\frac{1+\theta}{l+\theta}\right)^{1-\alpha}\log_{2-\alpha}p_{\theta}\frac{1+\theta}{l+\theta}$.
Since $p\in C(S)$, so is $f$. Fix any $\eta>0$ and note that

$\displaystyle f(t)$ $\displaystyle\geq\eta$
$\displaystyle\left(\frac{1+\theta}{l+\theta}\right)^{1-\alpha}\log_{2-\alpha}p_{\theta}\frac{1+\theta}{l+\theta}$
$\displaystyle\geq\eta$
$\displaystyle\log_{2-\alpha}p_{\theta}\frac{1+\theta}{l+\theta}$
$\displaystyle\geq\left(\frac{1+\theta}{l+\theta}\right)^{\alpha-1}\eta$
$\displaystyle p_{\theta}\frac{1+\theta}{l+\theta}$
$\displaystyle\geq\exp_{2-\alpha}\left(\left(\frac{1+\theta}{l+\theta}\right)^{\alpha-1}\eta\right)$
$\displaystyle p_{\theta}$
$\displaystyle\geq\frac{l+\theta}{1+\theta}\exp_{2-\alpha}\left(\left(\frac{1+\theta}{l+\theta}\right)^{\alpha-1}\eta\right)$
$\displaystyle p-l$
$\displaystyle\geq(l+\theta)\left(\exp_{2-\alpha}\left(\left(\frac{1+\theta}{l+\theta}\right)^{\alpha-1}\eta\right)-1\right)$

Thus

$\displaystyle A$ $\displaystyle=\\{t:f(t)\geq\eta\\}$
$\displaystyle=\left\\{p-l\geq(l+\theta)\left(\exp_{2-\alpha}\left(\left(\frac{1+\theta}{l+\theta}\right)^{\alpha-1}\eta\right)-1\right)\right\\}$

Since $p-l\in C_{0}(S)$ the set on the second line is bounded. Thus $A$ is
bounded so that $f\in C_{0}(S)$. Further, by Lemma 1

$\displaystyle p_{\theta}$
$\displaystyle=\exp_{2-\alpha}\left(f-\log_{\alpha}\frac{1+\theta}{l+\theta}\right)$

giving us $p_{\theta}\in\mathcal{P}_{0}$. By Proposition 3 there is some
$p_{g}$ in the deformed kernel exponential family so that
$\|p_{\theta}-p_{g}\|_{L^{r}(S)}\leq\epsilon$. Thus $\|p-p_{g}\|_{r}\leq
2\epsilon$ for any $1\leq r\leq\infty$. To show convergence in Helinger
distance, note

$\displaystyle H^{2}(p,p_{g})$
$\displaystyle=\frac{1}{2}\int_{S}(\sqrt{p}-\sqrt{p_{g}})^{2}dQ$
$\displaystyle=\frac{1}{2}\int_{S}(p-2\sqrt{pp_{g}}+p_{g})dQ$
$\displaystyle\leq\frac{1}{2}\int_{S}(p-2\min(p,p_{g})+p_{g})dQ$
$\displaystyle=\frac{1}{2}\int_{S}|p-p_{g}|dQ$
$\displaystyle=\frac{1}{2}\|p-p_{g}\|_{1}$

so that $L^{1}(S)$ convergence, which we showed, implies Hellinger
convergence. Let us consider the Bregman divergence. Note the generalized
triangle inequality444actually an equality, see https://www2.cs.uic.edu/
zhangx/teaching/bregman.pdf for proof for Bregman divergence

$\displaystyle B_{\Omega_{\alpha}}(p,p_{g})$
$\displaystyle=\underbrace{B_{\Omega_{\alpha}}(p,p_{\theta})}_{I}+\underbrace{B_{\Omega_{\alpha}}(p_{\theta},p_{g})}_{II}-\underbrace{\langle
p-p_{\theta},\nabla\Omega_{\alpha}(p_{\theta})-\nabla\Omega_{\alpha}(p_{g})\rangle_{2}}_{III}$
(12)

Term I

$\displaystyle B_{\Omega_{\alpha}}(p,p_{\theta})$
$\displaystyle=\frac{1}{\alpha(\alpha-1)}\int_{S}(p^{\alpha}-p_{\theta}^{\alpha})dQ-\langle\nabla\Omega_{\alpha}(p_{\theta}),p-p_{\theta}\rangle$
$\displaystyle=\frac{1}{\alpha(\alpha-1)}\int_{S}(p^{\alpha}-p_{\theta}^{\alpha})dQ-\frac{1}{\alpha-1}\int
p_{\theta}^{\alpha-1}(p-p_{\theta})dQ$
$\displaystyle\leq\frac{1}{\alpha(\alpha-1)}\int_{S}(p^{\alpha}-p_{\theta}^{\alpha})dQ+\frac{1}{\alpha-1}\|p_{\theta}^{\alpha-1}\|_{1}\|\|p-p_{\theta}\|_{\infty}$

The first term on the rhs clearly vanishes as $\theta\rightarrow 0$. For the
second term, we already showed that $\|p-p_{\theta}\|_{\infty}\rightarrow 0$.

Term II

Fix $\theta$. Then term $II$ converges to $0$ by Lemma 5.

Term III

For term $III$,

$\displaystyle\langle
p-p_{\theta},\nabla\Omega_{\alpha}(p_{\theta})-\nabla\Omega_{\alpha}(p_{g})\rangle_{2}$
$\displaystyle\leq\|p-p_{\theta}\|_{\infty}\|\nabla\Omega_{\alpha}(p_{\theta})-\nabla\Omega_{\alpha}(p_{g})\|_{1}$

Clearly the first term on the rhs converges by $L^{r}$ convergence. The
$L^{1}$ term for the gradient is given by

$\displaystyle\|\nabla\Omega_{\alpha}(p_{\theta})-\nabla\Omega_{\alpha}(p_{g})\|_{1}$
$\displaystyle=\frac{1}{\alpha-1}\int|p_{\theta}(t)^{\alpha-1}-p_{g}(t)^{\alpha-1}|dQ$
$\displaystyle\leq\int(\|p_{\theta}\|_{\infty}+\|p_{\theta}-p_{g}\|_{\infty})^{\alpha-2}\|p_{\theta}-p_{g}\|_{\infty}dQ\textrm{
Eqn. }\ref{eqn:bounding-diff-power}$
$\displaystyle=(\|p_{\theta}\|_{\infty}+\|p_{\theta}-p_{g}\|_{\infty})^{\alpha-2}\|p_{\theta}-p_{g}\|_{\infty}$

so that the inner product terms are bounded as

$\displaystyle|\langle
p-p_{\theta},\nabla\Omega_{\alpha}(p_{\theta})-\nabla\Omega_{\alpha}(p_{g})\rangle_{2}|$
$\displaystyle\leq(\|p_{\theta}\|_{\infty}+\|p_{\theta}-p_{g}\|_{\infty})^{\alpha-2}\|p_{\theta}-p_{g}\|_{\infty}\|p-p_{\theta}\|_{\infty}$

∎

######  Lemma 2.

(Functional Taylor’s Theorem) Let $F:X\rightarrow\mathbb{R}$ where $X$ is a
Banach space. Let $f,g\in X$ and let $F$ be $k$ times Gateaux differentiable.
Then we can write

$\displaystyle
F(g)=\sum_{i=0}^{k-1}F^{i}(f)(g-f)^{i}+F^{k}(f+c(g-f))(g-f)^{k}$

for some $c\in[0,1]$.

###### Proof.

This is simply a consequence of expressing a functional as a function of an
$\epsilon\in[0,1]$, which restricts the functional to take input functions
between two functions. We then apply Taylor’s theorem to the function and
apply the chain rule for Gateaux derivatives to obtain the resulting Taylor
remainder theorem for functionals.

Let $G(\eta)=F(f+\eta(g-f))$. By Taylor’s theorem we have

$\displaystyle G(1)$ $\displaystyle=G(0)+G^{\prime}(0)+\cdots+G^{k}(c)$

and applying the chain rule gives us

$\displaystyle
F(g)=\sum_{i=0}^{k-1}F^{i}(f)(g-f)^{i}+F^{k}(f+c(g-f))(g-f)^{k}$

∎

######  Lemma 3.

(Functional Mean Value Theorem) Let $F:X\rightarrow\mathbb{R}$ be a functional
where $f,g\in X$ some Banach space with norm $\|\cdot\|$. Then

$\displaystyle|F(f)-F(g)|$
$\displaystyle\leq\|F^{\prime}(h)\|_{\textrm{op}}\|f-g\|$

where $h=g+c(f-g)$ for some $c\in[0,1]$, $F^{\prime}(h)$ is the Gateaux
derivative of $F$, and $\|\cdot\|_{\textrm{op}}$ is the operator norm
$\|A\|_{\textrm{op}}=\inf\\{c>0:\|Ax\|\leq c\|x\|\forall x\in X\\}$.

###### Proof.

Consider $G(\eta)=F(g+\eta(f-g))$. Apply the ordinary mean value theorem to
obtain

$\displaystyle G(1)-G(0)$ $\displaystyle=G^{\prime}(c),c\in[0,1]$
$\displaystyle=F^{\prime}(g+c(f-g))\cdot(f-g)$

and thus

$\displaystyle|F(f)-F(g)|$
$\displaystyle\leq\|F^{\prime}(h)\|_{\textrm{op}}\|f-g\|$

∎

######  Claim 1.

Consider $\mathcal{P}_{\infty}=\\{p_{f}=\exp_{2-\alpha}(f-A_{\alpha}(f)):f\in
L^{\infty}(S)\\}$. Then for $p_{f}\in\mathcal{P}_{\infty}$,
$A_{\alpha}(f)\leq\|f\|_{\infty}$.

###### Proof.

$\displaystyle p_{f}(t)$ $\displaystyle=\exp_{2-\alpha}(f(t)-A_{\alpha}(f))$
$\displaystyle\leq\exp_{2-\alpha}(\|f\|_{\infty}-A_{\alpha}(f))\textrm{ for
}1<\alpha\leq 2$ $\displaystyle\int_{S}p_{f}(t)dQ$
$\displaystyle\leq\int_{S}\exp_{2-\alpha}(\|f\|_{\infty}-A_{\alpha}(f))dQ$
$\displaystyle 1$
$\displaystyle\leq\exp_{2-\alpha}(\|f\|_{\infty}-A_{\alpha}(f))$
$\displaystyle\log_{2-\alpha}1$
$\displaystyle\leq\|f\|_{\infty}-A_{\alpha}(f)$ $\displaystyle A_{\alpha}(f)$
$\displaystyle\leq\|f\|_{\infty}$

where for the second line recall that we assumed that throughout the paper
$1<\alpha\leq 2$. ∎

######  Lemma 4.

Consider $\mathcal{P}_{\infty}=\\{p_{f}=\exp_{2-\alpha}(f-A_{\alpha}(f)):f\in
L^{\infty}(S)\\}$. Then the Frechet derivative of
$A_{\alpha}:L^{\infty}\rightarrow\mathbb{R}$ exists. It is given by the map

$\displaystyle A^{\prime}(f)(g)$
$\displaystyle=\mathbb{E}_{\tilde{p}_{f}^{2-\alpha}}(g(T))$
$\displaystyle=\frac{\int p_{f}^{2-\alpha}(t)g(t)dQ}{\int
p_{f}^{2-\alpha}(t)dQ}$

###### Proof.

This proof has several parts. We first derive the Gateaux differential of
$p_{f}$ in a direction $\psi\in L^{\infty}$ and as it depends on the Gateaux
differential of $A_{\alpha}(f)$ in that direction, we can rearrange terms to
recover the latter. We then show that it exists for any $f,\psi\in
L^{\infty}$. Next we show that the second Gateaux differential of
$A_{\alpha}(f)$ exists, and use that along with a functional Taylor expansion
to prove that the first Gateaux derivative is in fact a Frechet derivative.

In Martins et al. (2020) they show how to compute the gradient of
$A_{\alpha}(\theta)$ for the finite dimensional case: we extend this to the
Gateaux differential. We start by computing the Gateaux differential of
$p_{f}$.

$\displaystyle\frac{d}{d\eta}p_{f+\eta\psi}(t)$
$\displaystyle=\frac{d}{d\eta}\exp_{2-\alpha}(f(t)+\eta\psi(t)-A_{\alpha}(f+\eta\psi))$
$\displaystyle=\frac{d}{d\eta}[1+(\alpha-1)(f(t)+\eta\psi(t)-A_{\alpha}(f+\eta\psi))]^{1/(\alpha-1)}_{+}$
$\displaystyle=[1+(\alpha-1)(f(t)+\eta\psi(t)-A_{\alpha}(f+\eta\psi))]^{(2-\alpha)/(\alpha-1)}_{+}\left(\psi(t)-\frac{d}{d\eta}A_{\alpha}(f+\eta\psi)\right)$
$\displaystyle=p_{f+\eta\psi}^{2-\alpha}(t)\left(\psi(t)-\frac{d}{d\eta}A_{\alpha}(f+\eta\psi)\right)$

evaluating at $\eta=0$ gives us

$\displaystyle dp(f;\psi)(t)$
$\displaystyle=p_{f}^{2-\alpha}\left(\psi(t)+dA_{\alpha}(f;\psi)\right)$

Note that by claim 1 we have

$\displaystyle p_{f+\eta\psi}(t)$
$\displaystyle=\exp_{2-\alpha}(f(t)+\eta\psi(t)-A_{\alpha}(f+\eta\psi(t))$
$\displaystyle\leq\exp_{2-\alpha}(2\|f\|_{\infty}+2\eta\|\psi\|_{\infty})$
$\displaystyle\leq\exp_{2-\alpha}(2(\|f\|_{\infty}+\|\psi\|_{\infty}))$

We can thus apply the dominated convergence theorem to pull a derivative with
respect to $\eta$ under an integral. We can then recover the Gateaux
diferential of $A_{\alpha}$ via

$\displaystyle 0$ $\displaystyle=\frac{d}{d\eta}\biggr{|}_{\eta=0}\int
p_{f+\eta\psi}(t)dQ$ $\displaystyle=\int dp(f;\psi)(t)dQ$ $\displaystyle=\int
p_{f}(t)^{2-\alpha}(\psi(t)-dA_{\alpha}(f;\psi))dQ$ $\displaystyle
dA_{\alpha}(f;\psi)$
$\displaystyle=\mathbb{E}_{\tilde{p}_{f}^{2-\alpha}}(\psi(T))$
$\displaystyle<\infty$

where the last line follows as $\psi\in L^{\infty}$. Thus the Gateaux
derivative exists in $L^{\infty}$ directions. The derivative at $f$ maps
$\psi:\rightarrow\mathbb{E}_{\tilde{p}_{f}^{2-\alpha}}(\psi(T))$ i.e.
$A^{\prime}_{\alpha}(f)(\psi)=\mathbb{E}_{\tilde{p}_{f}^{2-\alpha}}(\psi(T))$.
We need to show that this is a Frechet derivative. To do so, we will take take
second derivatives of $p_{f+\eta\psi}(t)$ with respect to $\eta$ in order to
obtain second derivatives of $A_{\alpha}(f+\eta\psi)$ with respect to $\eta$.
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 $\psi:\rightarrow\mathbb{E}_{\tilde{p}_{f}^{2-\alpha}}(\psi(T))$ is a
Frechet derivative.

$\displaystyle\frac{d^{2}}{d\eta^{2}}p_{f+\eta\psi}(t)$
$\displaystyle=\frac{d}{d\eta}p_{f+\eta\psi}(t)^{2-\alpha}\left(\psi(t)-\frac{d}{d\eta}A_{\alpha}(f+\eta\psi)\right)$
$\displaystyle=\left(\frac{d}{d\eta}p_{f+\eta\psi}(t)^{2-\alpha}\right)\left(\psi(t)-\frac{d}{d\eta}A_{\alpha}(f+\eta\psi)\right)$
$\displaystyle\quad-
p_{f+\eta\psi}(t)^{2-\alpha}\frac{d^{2}}{d\eta^{2}}A_{\alpha}(f+\eta\psi)$
$\displaystyle=(2-\alpha)p_{f+\eta\psi}(t)(\psi(t)-\frac{d}{d\eta}A_{\alpha}(f+\eta\psi))\frac{d}{d\eta}p_{f+\eta\psi}(t)$
$\displaystyle\quad-
p_{f+\eta\psi}(t)^{2-\alpha}\frac{d^{2}}{d\eta^{2}}A_{\alpha}(f+\eta\psi)$
$\displaystyle=(2-\alpha)p_{f+\eta\psi}^{3-2\alpha}(\psi(t)-\frac{d}{d\eta}A_{\alpha}(f+\eta\psi))^{2}-p_{f+\eta\psi}(t)^{2-\alpha}\frac{d^{2}}{d\eta^{2}}A_{\alpha}(f+\eta\psi)$

We need to show that we 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 to show an
integrable function that dominates
$p_{f+\eta\psi}(t)^{2-\alpha}(\psi(t)-\mathbb{E}_{\tilde{p}_{f+\eta\psi}^{2-\alpha}}\psi(T))$.

$\displaystyle|p_{f+\eta\psi}(t)^{2-\alpha}(\psi(t)-\mathbb{E}_{\tilde{p}_{f+\eta\psi}^{2-\alpha}}\psi(T))|$
$\displaystyle\leq p_{f+\eta\psi}(t)^{2-\alpha}2\|\psi\|_{\infty}$
$\displaystyle\leq\exp_{2-\alpha}(2(\|f\|_{\infty}+\|\psi\|_{\infty}))2\|\psi\|_{\infty}$

which is in $L^{1}(Q)$. Now applying the dominated convergence theorem

$\displaystyle 0$
$\displaystyle=\int\frac{d^{2}}{d\epsilon^{2}}p_{f+\epsilon\psi}(t)dQ$
$\displaystyle=\int\left[(2-\alpha)p_{f+\epsilon\psi}^{3-2\alpha}(\psi(t)-\frac{d}{d\epsilon}A_{\alpha}(f+\epsilon\psi))^{2}-p_{f+\epsilon\psi}(t)^{2-\alpha}\frac{d^{2}}{d\epsilon^{2}}A_{\alpha}(f+\epsilon\psi)\right]dQ$

and rearranging gives

$\displaystyle\frac{d^{2}}{d\epsilon^{2}}A_{\alpha}(f+\epsilon\psi)$
$\displaystyle=(2-\alpha)\frac{\int
p_{f+\epsilon\psi}^{3-2\alpha}(\psi(t)-\frac{d}{d\epsilon}A_{\alpha}(f+\epsilon\psi))^{2}dQ}{\int
p_{f+\epsilon\psi}(t)^{2-\alpha}dQ}$
$\displaystyle\frac{d^{2}}{d\epsilon^{2}}A_{\alpha}(f)\biggr{|}_{\epsilon=0}$
$\displaystyle=(2-\alpha)\frac{\int
p_{f}^{3-2\alpha}(\psi(t)-\mathbb{E}_{\tilde{p}_{f}^{2-\alpha}}[\psi(T)])^{2}dQ}{\int
p_{f}(t)^{2-\alpha}dQ}$

since $f,\psi\in L^{\infty}$. For the functional Taylor expansion, we have
from Lemma 2

$\displaystyle
A_{\alpha}(f+\psi)=A_{\alpha}(f)+A_{\alpha}^{\prime}(f)(\psi)+\frac{1}{2}A^{\prime\prime}_{\alpha}(f+\epsilon\psi)(\psi)^{2}$

for some $\epsilon\in[0,1]$. We thus need to show that for $\epsilon\in[0,1]$,

$\displaystyle(2-\alpha)\frac{\frac{1}{\|\psi\|_{\infty}}\int
p_{f+\epsilon\psi}^{3-2\alpha}(\psi(t)-\mathbb{E}_{\tilde{p}_{f+\epsilon\psi}^{2-\alpha}}[\psi(T)])^{2}dQ}{\int
p_{f+\epsilon\psi}(t)^{2-\alpha}dQ}\overset{\psi\rightarrow 0}{\rightarrow}0$

It suffices to show that the numerator tends to $0$ as $\psi\rightarrow 0$.

$\displaystyle\left|\frac{1}{\|\psi\|_{\infty}}(\psi(t)-\mathbb{E}_{\tilde{p}_{f+\epsilon\psi}^{2-\alpha}}[\psi(T)])^{2}\right|$
$\displaystyle=\left|\frac{\psi(t)}{\|\psi\|_{\infty}}\psi(t)-\frac{\psi(t)}{\|\psi\|_{\infty}}2\mathbb{E}_{\tilde{p}_{f+\epsilon\psi}^{2-\alpha}}[\psi(T)]+\frac{\mathbb{E}_{\tilde{p}_{f+\epsilon\psi}^{2-\alpha}}[\psi(T)]}{\|\psi\|_{\infty}}\mathbb{E}_{\tilde{p}_{f+\epsilon\psi}^{2-\alpha}}[\psi(T)]\right|$
$\displaystyle\leq\left|\frac{\psi(t)}{\|\psi\|_{\infty}}\right|\left|\psi(t)-2\mathbb{E}_{\tilde{p}_{f+\epsilon\psi}^{2-\alpha}}[\psi(T)]\right|$
$\displaystyle\quad+\left|\mathbb{E}_{\tilde{p}_{f+\epsilon\psi}^{2-\alpha}}\frac{\psi(T)}{\|\psi\|_{\infty}}\right|\left|\mathbb{E}_{\tilde{p}_{f+\epsilon\psi}^{2-\alpha}}[\psi(T)]\right|$
$\displaystyle\leq\left|\psi(t)-2\mathbb{E}_{\tilde{p}_{f+\epsilon\psi}^{2-\alpha}}[\psi(T)]\right|+\|p_{f+\epsilon\psi}\|_{2-\alpha}^{2-\alpha}\left|\mathbb{E}_{\tilde{p}_{f+\epsilon\psi}^{2-\alpha}}[\psi(T)]\right|$
$\displaystyle\rightarrow 0\textrm{ as }\psi\rightarrow 0$

and plugging this in we obtain the desired result. Thus the Frechet derivative
of $A_{\alpha}(f)$ exists. ∎

######  Lemma 5.

Define $\mathcal{P}_{\infty}=\\{p_{f}=\exp_{2-\alpha}(f-A_{\alpha}(f)):f\in
L^{\infty}(S)\\}$ where $L^{\infty}(S)$ is the space of almost surely bounded
measurable functions with domain $S$. Fix $f_{0}\in L^{\infty}$. Then for any
fixed $\epsilon>0$ and $p_{g},p_{f}\in\mathcal{P}_{\infty}$ such that
$f,g\in\overline{B}_{\epsilon}^{\infty}(f_{0})$ the $L^{\infty}$ closed ball
around $f_{0}$, there exists constant $M_{\exp}>0$ depending only on $f_{0}$
such that

$\displaystyle\|p_{f}-p_{g}\|_{L^{r}}$ $\displaystyle\leq
2M_{\exp}\|f-g\|_{\infty}$

Further

$\displaystyle B_{\Omega_{\alpha}}(p_{f},p_{g})$
$\displaystyle\leq\frac{1}{\alpha-1}\|p_{f}-p_{g}\|_{\infty}[(\|p_{f}\|_{\infty}+\|p_{f}-p_{g}\|_{\infty})^{\alpha-1}+\exp_{2-\alpha}(2\|g\|_{\infty})]$

###### Proof.

This Lemma mirrors Lemma A.1 in Sriperumbudur et al. (2017), but the proof is
very different as they rely on the property that $\exp(x+y)=\exp(x)\exp(y)$,
which does not hold for $\beta$-exponentials. We thus had to strengthen the
assumption to include that $f$ and $g$ lie in a closed ball, and then use the
functional mean value theorem Lemma 3 as the main technique to achieve our
result.

Consider that by functional mean value inequality,

$\displaystyle\|p_{f}-p_{g}\|_{L^{r}}$
$\displaystyle=\|\exp_{\beta}(f-A_{\alpha}(f))-\exp_{\beta}(g-A_{\alpha}(g))\|_{L^{r}}$
$\displaystyle\leq\|\exp_{\beta}(h-A_{\alpha}(h))^{2-\alpha}\|_{\infty}(\|f-g\|_{\infty}+|A_{\alpha}(f)-A_{\alpha}(g)|)$
(13)

where $h=cf+(1-c)g$ for some $c\in[0,1]$. We need to bound
$\exp_{\beta}(h-A_{\alpha}(h))$ and
$\|A_{\alpha}(f)-A_{\alpha}(g)\|_{\infty}$.

We can show a bound on $\|h\|_{\infty}$

$\displaystyle\|h\|_{\infty}$
$\displaystyle=\|cf+(1-c)g-f_{0}+f_{0}\|_{\infty}$
$\displaystyle\leq\|c(f-f_{0})+(1-c)(g-f_{0})+f_{0}\|_{\infty}$
$\displaystyle\leq
c\|f-f_{0}\|_{\infty}+(1-c)\|g-f_{0}\|_{\infty}+\|f_{0}\|_{\infty}$
$\displaystyle\leq\epsilon+\|f_{0}\|_{\infty}$

so that $h$ is bounded. Now we previously showed in claim 1 that
$|A_{\alpha}(h)|\leq\|h\|_{\infty}\leq\epsilon+\|f_{0}\|_{\infty}$. Since
$h,A_{\alpha}(h)$ are both bounded $\exp_{\beta}(h-A_{\alpha}(h))^{2-\alpha}$
is also.

Now note that by Lemma 3,

$\displaystyle|A_{\alpha}(f)-A_{\alpha}(g)|$
$\displaystyle\leq\|A_{\alpha}^{\prime}(h)\|_{\textrm{op}}\|f-g\|_{\infty}$

We need to show that $\|A_{\alpha}^{\prime}(h)\|_{\textrm{op}}$ is bounded for
$f,g\in\overline{B}_{\epsilon}(f_{0})$. Note that in Lemma 4 we showed that

$\displaystyle|A^{\prime}_{\alpha}(f)(g)|$
$\displaystyle=|\mathbb{E}_{p_{f}^{2-\alpha}}[g(T)]|$
$\displaystyle\leq\|g\|_{\infty}$

Thus
$\|A^{\prime}_{\alpha}\|_{\textrm{op}}=\sup\\{|A^{\prime}_{\alpha}(h)(m)|\
:\|m\|_{\infty}=1\\}\leq 1$. Let $M_{\exp}$ be the bound on
$\exp_{\beta}(h-A_{\alpha}(h))$. Then putting everything together we have the
desired result

$\displaystyle\|p_{f}-p_{g}\|_{L^{r}}$ $\displaystyle\leq
2M_{\exp}\|f-g\|_{\infty}$

Now

$\displaystyle B_{\Omega_{\alpha}}(p_{f},p_{g})$
$\displaystyle=\Omega_{\alpha}(p_{f})-\Omega_{\alpha}(p_{g})-\langle\nabla\Omega_{\alpha}(p_{g}),p_{f}-p_{g}\rangle_{2}$
(14)

For the inner prodct term, first note that following Martins et al. (2020) the
gradient is given by

$\displaystyle\nabla\Omega_{\alpha}(p_{g})(t)$
$\displaystyle=\frac{p_{g}(t)^{\alpha-1}}{\alpha-1}$ (15)

Thus

$\displaystyle|\langle\nabla\Omega_{\alpha}(p_{g}),p_{f}-p_{g}\rangle_{2}|$
$\displaystyle\leq\|\nabla\Omega_{\alpha}(p_{g})\|_{1}\|p_{f}-p_{g}\|_{\infty}$
$\displaystyle=\frac{1}{\alpha-1}\int_{S}\exp_{2-\alpha}(g(t)-A(g))dQ\|p_{f}-p_{g}\|_{\infty}$
$\displaystyle\leq\frac{1}{\alpha-1}\exp_{2-\alpha}(2\|g\|_{\infty})\|p_{f}-p_{g}\|_{\infty}$

where the second line follows from claim 1.

Further note that by Taylor’s theorem,

$\displaystyle y^{\alpha}$ $\displaystyle=x^{\alpha}+\alpha z^{\alpha-1}(y-x)$
(16)

for some $z$ between $x$ and $y$. Then letting $y=p_{f}(t)$ and $x=p_{g}(t)$,
we have for some $z=h(t)$ lying between $p_{f}(t)$ and $p_{g}(t)$ that

$\displaystyle p_{f}(t)^{\alpha}=p_{g}(t)^{\alpha}+\alpha
h(t)^{\alpha-1}(p_{f}(t)-p_{g}(t))$

Since $f\in L^{\infty}$ then applying Claim 1 we have that each
$p_{f},p_{g}\in L^{\infty}$ and thus $h$ is. Then

$\displaystyle|p_{f}(t)^{\alpha}-p_{g}(t)^{\alpha}|$
$\displaystyle=\alpha|h(t)|^{\alpha-1}|p_{f}(t)-p_{g}(t)|$
$\displaystyle\leq\alpha\|h\|_{\infty}^{\alpha-1}\|p_{f}-p_{g}\|_{\infty}$
$\displaystyle\leq\alpha\max\\{\|p_{f}\|_{\infty},\|p_{g}\|_{\infty}\\}^{\alpha-1}\|p_{f}-p_{g}\|_{\infty}$
$\displaystyle\leq\alpha(\|p_{f}\|_{\infty}+\|p_{f}-p_{g}\|_{\infty})^{\alpha-1}\|p_{f}-p_{g}\|_{\infty}$
(17)

so that

$\displaystyle|\Omega_{\alpha}(p_{f})-\Omega_{\alpha}(p_{g})|$
$\displaystyle=\left|\frac{1}{\alpha(\alpha-1)}\int(p_{f}(t)^{\alpha}-p_{g}(t)^{\alpha})dQ\right|$
$\displaystyle\leq\frac{1}{\alpha-1}(\|p_{f}\|_{\infty}+\|p_{f}-p_{g}\|_{\infty})^{\alpha-1}\|p_{f}-p_{g}\|_{\infty}.$

Putting it all together we obtain

$\displaystyle B_{\Omega_{\alpha}}(p_{f},p_{g})$
$\displaystyle\leq\frac{1}{\alpha-1}(\|p_{f}\|_{\infty}+\|p_{f}-p_{g}\|_{\infty})^{\alpha-1}\|p_{f}-p_{g}\|_{\infty}$
$\displaystyle\quad+\frac{1}{\alpha-1}\exp_{2-\alpha}(2\|g\|_{\infty})\|p_{f}-p_{g}\|_{\infty}$
$\displaystyle=\frac{1}{\alpha-1}\|p_{f}-p_{g}\|_{\infty}[(\|p_{f}\|_{\infty}+\|p_{f}-p_{g}\|_{\infty})^{\alpha-1}+\exp_{2-\alpha}(2\|g\|_{\infty})]$

∎

Figure 2: General architecture for classification using continuous attention
mechanisms. The pipeline is trained end-to-end. The encoder takes a
discretized representation of an 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 a
function $V(t)$. These are then combined in an attention mechanism by
computing a context vector $c=\mathbb{E}_{p}[V(T)]$. For some parametrizations
of $p$ and $V(t)$ this can be computed in closed form, while for others it
must be done via numerical integration. The context vector is then fed into a
classifier.

##  Appendix C uWave Experiments: Additional Details

We experiment with $N=64,128$ and $256$ basis functions, and use a learning
rate of $1e-4$. We use $H=100$ attention mechanisms, or heads. Unlike Vaswani
et al. (2017), our use of multiple heads is slightly different as we use the
same value function for each head, and only vary the attention densities.
Additional architectural details are given below.

###  C.1 Value Function

The value function uses regularized linear regression on the original time
series observed at random observation times (which are not dependent on the
data) to obtain an approximation $V(t;\textbf{B})=\textbf{B}\Psi(t)\approx
X(t)$. The $H$ in Eqn. 6 is the original time series.

####  C.1.1 Encoder

In the encoder, we use the value function to interpolate the irregularly
sampled time series at the original points. This is then passed through a
convolutional layer with $4$ filters and filter size $5$ followed by a max
pooling layer with pool size $2$. This is followed by one hidden layer with
$256$ units and an output $v$ of size $256$. The attention densities for each
head $h=1,\cdots,H$ are then

$\displaystyle\mu_{h}$ $\displaystyle=w_{h,1}^{T}v$ $\displaystyle\sigma_{h}$
$\displaystyle=\textrm{softplus}(w_{h,2}^{T}v)$ $\displaystyle\gamma_{h}$
$\displaystyle=W^{(h)}v$

for vectors $w_{h,1},w_{h,2}$ and matrices $W^{h}$ and heads $h=1,\cdots,H$

####  C.1.2 Attention Mechanism

After forming densities and normalizing, we have densities
$p_{1}(t),\cdots,p_{H}(t)$, which we use to compute context scalars

$\displaystyle c_{h}=\mathbb{E}_{p_{h}}[V(T)]$

We compute these expectations using numerical integration to compute basis
function expectations $\mathbb{E}_{p_{h}}[\psi_{n}(T)]$ and a parametrized
value function $V(t)=B\psi(t)$ as 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 a softmax activation to output class
probabilities.

##  Appendix D MIT BIH: Additional Details

Note that our architecture takes some inspiration for the $H$ that we use in
our value function from a github
repository555``https://github.com/CVxTz/ECG_Heartbeat_Classification—,
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 a 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 $3$. The
final output has $256$ dimensions of length $23$. This is then used as our $H$
matrix in Eqn 6.

###  D.2 Encoder

The encoder takes the original time series as input. It has one hidden layer
with a 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

$\displaystyle c$ $\displaystyle=\mathbb{E}_{p}[V(T)]$ (18)

for input to the classifier.

###  D.4 Classifier

The classifier has two hidden layers with ReLU activation and outputs class
probabilities. Each hidden layer has $64$ hidden units.