# Learning from Small Samples: Transformation-Invariant SVMs with Composition
and Locality at Multiple Scales

Tao Liu, P. R. Kumar, and Xi Liu  Texas A&M University
Email: {tliu, prk<EMAIL_ADDRESS>
###### Abstract

Motivated by the problem of learning when the number of training samples is
small, this paper shows how to incorporate into support-vector machines (SVMs)
those properties that have made convolutional neural networks (CNNs)
successful. Particularly important is the ability to incorporate domain
knowledge of invariances, e.g., translational invariance of images. Kernels
based on the minimum distance over a group of transformations, which
corresponds to defining similarity as the best over the possible
transformations, are not generally positive definite. Perhaps it is for this
reason that they have neither previously been experimentally tested for their
performance nor studied theoretically. Instead, previous attempts have
employed kernels based on the average distance over a group of
transformations, which are trivially positive definite, but which generally
yield both poor margins as well as poor performance, as we show. We address
this lacuna and show that positive definiteness indeed holds with high
probability for kernels based on the minimum distance in the small training
sample set regime of interest, and that they do yield the best results in that
regime. Another important property of CNNs is their ability to incorporate
local features at multiple spatial scales, e.g., through max pooling. A third
important property is their ability to provide the benefits of composition
through the architecture of multiple layers. We show how these additional
properties can also be embedded into SVMs. We verify through experiments on
widely available image sets that the resulting SVMs do provide superior
accuracy in comparison to well-established deep neural network (DNN)
benchmarks for small sample sizes.

##  I Introduction

With the goal of learning when the number of training samples is small, and
motivated by the success of CNNs [1], we wish to endow SVMs with as much a
priori domain knowledge as possible.

One such important domain property for image recognition is translational
invariance. An image of a dog remains an image of the same dog if the image is
shifted to the left. Similarly, if the image is rotated it is still an image
of the dog; so it is also rotation-invariant. More generally, given a group of
transformations under which the classification of images is invariant, we show
how to endow SVMs with the knowledge of such invariance.

One common approach is data augmentation [2], where several transformations of
each training sample are added to the training set. This corresponds to a
kernel that defines the similarity between two vectors $X_{1}$ and $X_{2}$ as
the average similarity between $X_{1}$ and all transformations of $X_{2}$.
However the average also includes transformations that are maximally
dissimilar, and we show that it leads to poor margins and poor classification
results. Much more appealing is to define a kernel that defines similarity as
the greatest similarity between $X_{1}$ and all transformations of $X_{2}$. We
show that this kernel is positive definite with high probability in the small
sample regime of interest to us, under a probabilistic model for features. We
verify this property on widely available datasets and show that the
improvement obtained by endowing SVMs with this transformation invariance
yields considerably better test accuracy.

Another important domain property for image recognition is “locality" of
features, e.g., an edge depends only on a sharp gradient between neighboring
pixels. Moreover, through operations such as max-pooling, CNNs exploit
locality at multiple spatial scales. We show how one may incorporate such
locality into polynomial SVMs.

Finally, their multi-layer architecture provides CNNs the benefits of
composition [3]. We show how one can iteratively introduce multiple layers
into SVMs too to facilitate composition. The introduction of multiple layers
increases computational complexity, and we show how this can be alleviated by
parallel computation so as to achieve a reduction of computation time by
increasing memory.

We show experimentally that the resulting SVMs provide significantly improved
performance for small datasets. Translational and rotational invariance
embedded into SVMs allows them to recognize objects that have not already been
centered in images or oriented in upright positions; we refer to these as
transformed datasets in the sequel. The transformation-invariant SVMs provide
significant improvements over SVMs as well as CNN benchmarks without data
augmentation when the training set is small. For 100/200/500 training samples,
the recognition accuracy of the MNIST dataset [4] is increased, respectively,
from the figures of 68.33%/86.96%/91.33% reported by the CNNs optimized over
architectures and dimensions [5] to, respectively, 81.55%/89.23%/93.11%.
Similar improvements are also obtained in the EMNIST Letters dataset [6] and
the Transformed MNIST datasets. The computational results reported here are
restricted to small datasets, which can be handled efficiently by LIBSVM [7].

###  I-A Background

In the early 2000s, SVMs [8] were one of the most popular and effective
methods for image classification [9]. They also had a firm theoretical
foundation [10, 11] of margin maximization that is especially important in
high dimensions, a kernel method to make high-dimensional computation
tractable, and a loose upper bound on the expected generalization performance
as the expected proportion of samples that are support vectors. Importantly,
SVMs employed a reliable computational scheme based on quadratic programming.

However, with the advent of CNNs and the enhancement of computing power
through graphics processing units (GPUs), SVMs were gradually replaced in
image classification. One of the reasons for the success of CNNs was that they
were able to incorporate prior knowledge into the neural network. Indeed, the
pioneering paper of CNNs [12] makes the point that “It is usually accepted
that good generalization performance on real-world problems cannot be achieved
unless some a priori knowledge about the task is built into the system. Back-
propagation networks provide a way of specifying such knowledge by imposing
constraints both on the architecture of the network and on its weights. In
general, such constraints can be considered as particular transformations of
the parameter space." It further mentions specifically that, “Multilayer
constrained networks perform very well on this task when organized in a
hierarchical structure with shift-invariant feature detectors." Indeed, CNNs
have successfully incorporated several important characteristics of images.
One, mentioned above (called shift-invariance), is translational invariance,
which is exploited by the constancy, i.e., location independence, of the
convolution matrices. A second is locality. For example, an “edge" in an image
can be recognized from just the neighboring pixels. This is exploited by the
low dimensionality of the kernel matrix. A third characteristic is the
multiplicity of spatial scales, i.e., a hierarchy of spatial “features" of
multiple sizes in images. These are captured in modern CNNs through the
“pooling" operation at the $(\ell+1)$-th layer, where the features of the
$\ell$-th layer are effectively low-pass filtered through operations such as
max-pooling. More recently, it has been shown that depth in neural networks
(NNs) of rectified linear units (ReLUs) permits composition, and enhances
expressivity for a given number of parameters, as well as reducing the number
of parameters needed for approximations of given accuracy [3].

With the wide availability of datasets such as CIFAR-10 [13] and ImageNet [14]
for testing, there has been continued success in the empirical engineering of
several high-performance CNN architectures, such as AlexNet [15], VGG16 [16],
GoogLeNet [17], and ResNet [18, 19]. Generally, neural networks have tended to
become larger over time with the number of parameters ranging into hundreds of
millions. Concomitantly they have also become increasingly data-hungry. Such
data-hungry NNs may be inappropriate for several applications where data is
expensive or scarce. For these reasons, there is an interest in methodologies
for learning efficiently from very few samples, which is the focus of this
paper.

###  I-B Related Work

There are mainly two studies related to our work: invariant kernels and local
correlations.

##### Invariant Kernels

To guarantee invariance over all transformations, Haasdonk et al. [20, 21]
proposed two invariant kernels. One, which they call “invariant integration,"
takes an average over a transformation group. Although this kernel is
trivially positive definite, it appears to produce poor results in our
testing, as we will see in Section IV. Recently, Mei et al. [22] considered
this in the context of kernel ridge regression (KRR) in the reproducing kernel
Hilbert space (RKHS). Another kernel considered by [20] consists of
transformations such as adding a constant value to the brightness values of
all pixels, which is not relevant to the subject of this paper.

##### Local Correlations

Since “local correlations," i.e., dependencies between nearby pixels, are more
pronounced than long-range correlations in natural images, Scholkopf et al.
[23] defined a two-layer kernel utilizing dot product in a polynomial space
which is mainly spanned by local correlations between pixels. We extend the
structure of such a two-layer local correlation to multilayer architectures by
introducing further compositions, which gives the flexibility to consider the
locality at multiple spatial scales. We also analyze the corresponding time
and space complexity of multilayer architectures.

##  II Kernels with Transformational Invariance

To fix notation, let $\mathcal{S}=\\{(X_{1},y_{1}),\dots,(X_{n},y_{n})\\}$ be
a set of labelled samples with
$X_{i}=(X^{(1)}_{i},X^{(2)}_{i},\ldots,X^{(m)}_{i})^{T}\in\mathcal{X}\subset\mathbb{R}^{m}$
and $\ y_{i}\in\mathcal{Y}$. Here, $\mathcal{X}$ and $\mathcal{Y}$ represent
the sample and label spaces respectively, with the number of samples $n$ and
the number of features $m$. We desire to fit a mapping $h$ from $\mathcal{X}$
to $\mathcal{Y}$.

###  II-A Transformation Groups and Transformation-Invariant Best-Fit Kernels

We wish to endow the kernel of the SVM with the domain knowledge that the
sample classification is invariant under certain transformations of the sample
vector. Let ${\cal{G}}$ be a transformation group that acts on $\mathcal{X}$,
i.e., for all $S,T,U\in{\cal{G}}$: (i) $T$ maps $\mathcal{X}$ into
$\mathcal{X}$; (ii) the identity map $I\in{\cal{G}}$; (iii) $ST\in{\cal{G}}$;
(iv) $(ST)U=S(TU)$; (v) there is an inverse $T^{-1}\in{\cal{G}}$ with
$TT^{-1}=T^{-1}T=I$.

We start with a base kernel
$K_{base}(\cdot,\cdot):\mathcal{X}\times\mathcal{X}\to\mathcal{R}$ that
satisfies the following properties:

  1. 1.

symmetric, i.e., $K_{base}(X_{i},X_{j})=K_{base}(X_{j},X_{i})$,

  2. 2.

positive definite, i.e., $\alpha^{T}K_{base}\alpha>0$ for all $\alpha\neq 0$,
where $K_{base}$ is the matrix with $ij$-th element $K_{base}(X_{i},X_{j})$,
and

  3. 3.

which satisfies

$\displaystyle K_{base}(TX_{i},X_{j})=K_{base}(X_{i},T^{-1}X_{j}),\ \ \forall
T\in{\cal{G}}.$ (1)

Define the kernel with the “best-fit" transformation over ${\cal{G}}$ by

$K_{{\cal{G}},best,base}(X_{i},X_{j}):=\sup_{T\in{\cal{G}}}K_{base}(TX_{i},X_{j}).$
(2)

######  Lemma 1.

$K_{{\cal{G}},best,base}$ is a symmetric kernel that is also transformation-
invariant over the group ${\cal{G}}$, i.e., $\forall T\in{\cal{G}}$,

$\displaystyle
K_{{\cal{G}},best,base}(TX_{i},X_{j})=K_{{\cal{G}},best,base}(X_{i},X_{j}).$
(3)

###### Proof.

The symmetry follows since

$\displaystyle
K_{{\cal{G}},best,base}(X_{i},X_{j})=\sup_{T\in{\cal{G}}}K_{base}(TX_{i},X_{j})$
$\displaystyle=$
$\displaystyle\sup_{T\in{\cal{G}}}K_{base}(X_{i},T^{-1}X_{j})=\sup_{T\in{\cal{G}}}K_{base}(T^{-1}X_{j},X_{i})$
$\displaystyle=$
$\displaystyle\sup_{T^{-1}\in{\cal{G}}}K_{base}(T^{-1}X_{j},X_{i})=K_{{\cal{G}},best,base}(X_{j},X_{i}).$

The transformational invariance follows since

$\displaystyle
K_{{\cal{G}},best,base}(TX_{i},X_{j})=\sup_{S\in{\cal{G}}}K_{base}(STX_{i},X_{j})$
$\displaystyle=$
$\displaystyle\sup_{UT^{-1}\in{\cal{G}}}K_{base}(UX_{i},X_{j})=\sup_{U\in{\cal{G}}}K_{base}(UX_{i},X_{j})$
$\displaystyle=$ $\displaystyle K_{{\cal{G}},best,base}(X_{i},X_{j}).$

∎

The Translation Group: Of particular interest in image classification is the
group of translations. Let $X_{i}=\\{X_{i}^{p,q}:p\in[m_{1}],q\in[m_{2}]\\}$
denote a two-dimensional $m_{1}\times m_{2}$ array of pixels, with
$m=m_{1}m_{2}$. Let
$T_{rs}X_{i}:=\\{X_{i}^{((p+r)\operatorname{mod}m_{1},(q+s)\operatorname{mod}m_{2})}:r\in[m_{1}],s\in[m_{2}]\\}$
denote the transformation that translates the array by $r$ pixels in the
x-direction, and by $s$ pixels in the y-direction. The translation group is
${\cal{G}}_{trans}:=\\{T_{rs}:r\in[m_{1}],s\in[m_{2}]\\}$. For notational
simplicity, we will denote the resulting kernel
$K_{{\cal{G}}_{trans},best,base}$ by $K_{TI,best,base}$.

###  II-B Positive Definiteness of Translation-Invariant Best-Fit Kernels

There are two criteria that need to be met when trying to embed
transformational invariance into SVM kernels. (i) The kernel will need to be
invariant with respect to the particular transformations of interest in the
application domain. (ii) The kernel will need to be positive definite to have
provable guarantees of performance.

$K_{TI,best,base}$ satisfies property (i) as established in Lemma 1.
Concerning property (ii) though, in general, $K_{TI,best,base}$ is an
indefinite kernel. We now show that when the base kernel is a normalized
linear kernel, $K_{linear}(X_{i},X_{j}):=\frac{1}{m}X_{i}^{T}X_{j}$, then it
is indeed positive definite, in a random model, in the small sample regime of
interest. Subsequently, in Theorem 2, we show that this also holds polynomial
kernels that are of importance in practice.

######  Theorem 1.

Let

$\displaystyle K_{TI,best,linear}(X_{i},X_{j})$
$\displaystyle:=\sup_{T\in{\cal{G}}_{trans}}\frac{1}{m}(TX_{i})^{T}X_{j}$

be the best-fit translation invariant kernel with the base kernel chosen as
the normalized linear kernel. Suppose
$\\{X^{(p,q)}_{i}:p\in[m_{1}],q\in[m_{2}],i\in[n]\\}$ are i.i.d., and
$\mathcal{N}(0,1)$. If $n=O(m^{\frac{1}{2}-\beta})$, for some
$\beta\in(0,\frac{1}{2})$, then $K_{TI,best,linear}$ is positive definite with
probability approaching one, as $m\to\infty$.

###### Proof.

For brevity, we denote $K_{TI,best,linear}(X_{i},X_{j})$ and
$K_{linear}(X_{i},X_{j})$ by $K_{TI,ij}$ and $K_{ij}$, respectively. From
Gershgorin’s circle theorem [24] every eigenvalue of $K_{TI,best,linear}$ lies
within at least one of the Gershgorin discs
$\mathcal{D}(K_{TI}$${}_{,ii},r_{i}):=\\{\lambda\in\mathbb{R}\ |\ |\lambda-
K_{TI}$${}_{,ii}|\leq r_{i}\\}$, where $r_{i}:=\sum_{j\neq
i}|K_{TI}$${}_{,ij}|$. . Hence if $K_{TI}$${}_{,ii}>\sum_{j\neq
i}|K_{TI}$${}_{,ij}|,\ \forall i$, then $K_{TI}$ is a positive definite
kernel.

Note that the dimension of the vector $X_{i}$ is $m=m_{1}\times m_{2}$ in the
case of a two dimensional array. The diagonal entry $K_{ii}$ is distributed as
Gamma $(\frac{m}{2},\frac{m}{2})$ (mean and variance are $1$ and
$\frac{2}{m}$, respectively). Invoking Lemma 4 in the Appendix with
$t=\frac{1}{4}$, we have

$\displaystyle\mathbb{P}(K_{ii}\leq\frac{3}{4})\leq\frac{2}{2+m/16},\ \
\forall i.$

Noting that $K_{TI,ii}=\max_{T\in\mathcal{G}}K_{linear}(TX_{i},X_{i})\geq
K_{ii},\forall i$,

$\displaystyle\mathbb{P}(K_{TI,ii}\leq\frac{3}{4})$
$\displaystyle\leq\mathbb{P}(K_{ii}\leq\frac{3}{4}).$

Hence

$\displaystyle\lim_{m\to\infty}\mathbb{P}(K_{TI,ii}\leq\frac{3}{4},\ \exists
i\in[n])$
$\displaystyle\leq\lim_{m\to\infty}n\mathbb{P}(K_{ii}\leq\frac{3}{4})$
$\displaystyle\leq\lim_{m\to\infty}\frac{2n}{2+m/16}=0.$ (4)

Now we turn to the off-diagonal terms $K_{TI,ij}$ for $i\neq j$. For
$k\in[m]$, one can write
$X_{i}^{(k)}X_{j}^{(k)}=\frac{1}{2}(Y_{+,ij}^{(k)}-Y_{-,ij}^{(k)})(Y_{+,ij}^{(k)}+Y_{-,ij}^{(k)})$,
where $Y_{+,ij}^{(k)}:=\frac{1}{\sqrt{2}}(X_{j}^{(k)}+X_{i}^{(k)})$ and
$Y_{-,ij}^{(j)}:=\frac{1}{\sqrt{2}}(X_{j}^{(k)}-X_{i}^{(k)})$. Note that
$Y_{+,ij}^{(k)}$ and $Y_{-,ij}^{(k)}$ are independent $N(0,1)$ random
variables. Hence $(Y_{+,ij}^{(k)})^{2}$ and $(Y_{-,ij}^{(k)})^{2}$ are chi-
squared random variables, and their moment generating functions are
$\mathbb{E}[e^{\lambda(Y_{+,ij}^{(k)})^{2}}]=\mathbb{E}[e^{\lambda(Y_{-,ij}^{(k)})^{2}}]=\frac{1}{\sqrt{1-2\lambda}}$
for $\lambda<\frac{1}{2}$. Hence

$\displaystyle\mathbb{E}[e^{\lambda(mK_{ij})}]$
$\displaystyle=\mathbb{E}\left[\exp\left(\frac{\lambda}{2}\sum_{k=1}^{m}\left((Y_{+,ij}^{(k)})^{2}-(Y_{-,ij}^{(k)})^{2})\right)\right)\right]$
$\displaystyle=\left(\mathbb{E}[\exp(\frac{\lambda}{2}(Y_{+,ij}^{(k)})^{2})]\mathbb{E}[\exp(-\frac{\lambda}{2}(Y_{-,ij}^{(k)})^{2})]\right)^{m}$
$\displaystyle=\left(\frac{1}{\sqrt{1-\lambda^{2}}}\right)^{m},\ \text{for
}\lambda^{2}<1.$

With $\mathbb{E}(mK_{ij})=0$, it can be verified that $mK_{ij}$ is sub-
exponential with parameters $(\sqrt{2m},2)$, as in Definition 1 in the
Appendix. Hence, from Lemma 5 of the Appendix, for $c\geq 1$,

$\displaystyle\mathbb{P}\left(mK_{ij}\geq\frac{m^{\frac{1}{2}+\beta}}{2c}\right)\leq\exp\left(-\frac{m^{2\beta}}{16c^{2}}\right).$
(5)

Now we consider the tail behavior of $\sum_{j\neq i}|K_{TI,ij}|,\forall i$:

$\displaystyle\mathbb{P}\left(\sum_{j\neq i}|K_{TI,ij}|\geq
t\right)\leq\mathbb{P}\left(\max_{j\neq i}|K_{TI,ij}|\geq\frac{t}{n-1}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$
$\displaystyle(n-1)\mathbb{P}\left(|K_{TI,ij}|\geq\frac{t}{n-1}\right)$
$\displaystyle=$
$\displaystyle(n-1)\mathbb{P}\left(|\sup_{T\in\mathcal{G}}K_{linear}(TX_{i},X_{j})|\geq\frac{t}{n-1}\right)$
$\displaystyle\leq$
$\displaystyle(n-1)\mathbb{P}\left(\sup_{T\in\mathcal{G}}|K_{linear}(TX_{i},X_{j})|\geq\frac{t}{n-1}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$
$\displaystyle(n-1)m\mathbb{P}\left(|K_{ij}|\geq\frac{t}{n-1}\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}$ $\displaystyle
2(n-1)m\mathbb{P}\left(K_{ij}\geq\frac{t}{n-1}\right)$ $\displaystyle\leq$
$\displaystyle 2nm\mathbb{P}\left(mK_{ij}\geq\frac{tm}{n}\right).$

Above, (a) holds since the probability distributions of $|K_{TI,ij}|$ are
identical for all $j\neq i$. Likewise, (b) holds since the distributions of
$|K_{ij}|$ are identical for all $j$. The inequality (c) holds since $K_{ij}$
is a symmetric random variable, i.e., $p_{K_{ij}}(y)=p_{K_{ij}}(-y)$. Let
$t=\frac{1}{2}$. Consider $n\leq cm^{\frac{1}{2}-\beta}$ for some $c\geq 1$.
Then,

$\displaystyle\lim_{m\to\infty}\mathbb{P}\left(\sum_{j\neq
i}|K_{TI,ij}|\geq\frac{1}{2},\ \exists i\in[n]\right)$ $\displaystyle\leq$
$\displaystyle\lim_{m\to\infty}n\mathbb{P}\left(\sum_{j\neq
i}|K_{TI,ij}|\geq\frac{1}{2}\right)$ $\displaystyle\leq$
$\displaystyle\lim_{m\to\infty}2c^{2}m^{2-2\beta}\mathbb{P}\left(mK_{ij}\geq\frac{m^{\frac{1}{2}+\beta}}{2c}\right)$
$\displaystyle\leq$
$\displaystyle\lim_{m\to\infty}2c^{2}m^{2-2\beta}\exp\left(-\frac{m^{2\beta}}{16c^{2}}\right)=0.$
(6)

Combining (4) and (6), we have

$\displaystyle\lim_{m\to\infty}\mathbb{P}(K_{TI,ii}>\sum_{j\neq
i}|K_{TI,ij}|,\forall i)$ $\displaystyle\geq$
$\displaystyle\lim_{m\to\infty}\mathbb{P}(\min_{i}K_{TI,ii}>\max_{i}\sum_{j\neq
i}|K_{TI_{i}j}|)$ $\displaystyle\geq$
$\displaystyle\lim_{m\to\infty}\mathbb{P}(\min_{i}K_{TI,ii}>\frac{3}{4}\text{
and }\max_{i}\sum_{j\neq i}|K_{TI,ij}|<\frac{1}{2})$ $\displaystyle=$
$\displaystyle
1-\lim_{m\to\infty}\mathbb{P}(\min_{i}K_{TI,ii}\leq\frac{3}{4}\text{ or
}\max_{i}\sum_{j\neq i}|K_{TI,ij}|\geq\frac{1}{2})$ $\displaystyle\geq$
$\displaystyle
1-\lim_{m\to\infty}(\mathbb{P}(\min_{i}K_{TI,ii}\leq\frac{3}{4})+\mathbb{P}(\max_{i}\sum_{j\neq
i}|K_{Ti,ij}|\geq\frac{1}{2}))$ $\displaystyle\geq$ $\displaystyle
1-\lim_{m\to\infty}(\mathbb{P}(K_{TI,ii}\leq\frac{3}{4},\ \exists
i)+\mathbb{P}(\sum_{j\neq i}|K_{Ti,ij}|\geq\frac{1}{2}),\ \exists i)$
$\displaystyle=$ $\displaystyle 1.$

Therefore, $K_{TI,best,linear}$ is positive definite with probability
approaching one as $m\to\infty$. ∎

We now show that the positive definiteness in the small sample regime also
holds for the polynomial kernels which are of importance in practice:

$\displaystyle K_{poly}(X_{i},X_{j}):=(1+\gamma X_{i}^{T}X_{j})^{d}\mbox{ for
}\gamma\geq 0,\mbox{ and }d\in\mathbb{N}.$

######  Theorem 2.

For any $\gamma\in\mathbb{R}_{+}$ and $d\in\mathbb{N}$, the translation-
invariant kernels,

$\displaystyle K_{TI,best,poly}(X_{i},X_{j})$
$\displaystyle:=\sup_{T\in{\cal{G}}_{trans}}(1+\gamma(TX_{i})^{T}X_{j})^{d}$

are positive definite with probability approaching 1 as $m\to+\infty$, under
the same conditions as in Theorem 1.

###### Proof.

Due to monotonicity,

$\displaystyle K_{TI,best,poly}(X_{i},X_{j})$
$\displaystyle:=\sup_{T\in\mathcal{G}_{trans}}(1+\gamma(TX_{i})^{T}X_{j})^{d}$
$\displaystyle=(1+\gamma\sup_{T\in\mathcal{G}_{trans}}(TX_{i})^{T}X_{j})^{d}$
$\displaystyle=(1+\gamma mK_{TI,best,linear}(X_{i},X_{j}))^{d}.$

Now note that if $K_{1}$ and $K_{2}$ are positive definite kernels, then the
following kernels $K$ obtained by Schur products [25], addition, or adding a
positive constant elementwise, are still positive definite kernels:

  * •

$K_{ij}=\alpha K_{1,ij}+\beta K_{2,ij}$, $\forall\alpha,\beta\geq 0$.

  * •

$K_{ij}=(K_{1,ij})^{\ell_{1}}(K_{2,ij})^{\ell_{2}},\forall\ell_{1},\ell_{2}\in\mathbb{N}$.

  * •

$K_{ij}=K_{1,ij}+\gamma$, $\forall\gamma\geq 0$.

Since $K_{TI,best,poly}$ can indeed be obtained by repeatedly applying the
above operations starting with $K_{TI,best,linear}$, it follows that
$K_{TI,best,poly}$ is positive definite whenever $K_{TI,best,linear}$ is,
which holds with probability approaching one as $m\to+\infty$. ∎

Remark. Since Gershgorin’s circle theorem is a conservative bound for the
eigenvalues of a matrix, the bound of $n=O(m^{\frac{1}{2}-\beta})$ for some
$\beta\in(0,\frac{1}{2})$ on the number of samples is also a conservative
condition for positive definiteness. In practice, larger $n$’s also yield
positive definiteness of $K_{TI,best,linear}$. Even more usefully,
$K_{TI,best,poly}$ is positive definite for a much larger range of $n$’s than
$K_{TI,best,linear}$, which is reported in Table I.

TABLE I: The value of $n$ up to which the kernel is positive definite Datasets | $K_{TI,best,linear}$ |  $K_{TI,best,poly}$(deg=8)
---|---|---
Original MNIST [4] | $\approx 45$ | $\approx 375$
EMNIST [6] | $\approx 35$ | $\approx 395$
Translated MNIST | $\approx 455$ | $\approx 15000$

###  II-C Comparison with the Average-Fit Kernel and Data Augmentation

####  II-C1 Average-Fit Kernel

In [20], the “average-fit kernel"

$\displaystyle K_{{\cal{G}},avg,linear}(X_{i},X_{j})$
$\displaystyle:=\frac{1}{|{\cal{G}}]}\sum_{T\in{\cal{G}}}K_{linear}(TX_{i},X_{j})$
(7)

is considered, which seeks the “average" fit over all transformations. Such a
kernel is trivially positive definite. However, it is not really a desirable
choice for the case of translations when the base kernel is the linear kernel,
since then $K_{{\cal{G}}_{trans},avg,linear}(X_{i},X_{j})$, which we will
denote by $K_{TI,avg,linear}(X_{i},X_{j})$, satisfies
$K_{TI,avg,linear}(X_{i},X_{j})=\left(\frac{1}{|{\cal{G}}_{trans}]}\sum_{T\in{\cal{G}}_{trans}}TX_{i}\right)^{T}X_{j}.$
Now note that
$\frac{1}{|{\cal{G}}_{trans}]}\sum_{T\in{\cal{G}}_{trans}}TX_{i}=\alpha(1,1,\ldots,1)^{T}$,
where
$\alpha=\frac{1}{m}\sum_{k\in[m_{1}],\ell\in[m_{2}]}X^{(k,\ell)}_{i}=\text{Average
brightness level of}X_{i}$. So, it basically blurs out all detail in $X_{i}$
and retains only its average brightness level $\alpha$. Therefore
$K_{TI,avg,linear}(X_{i},X_{j})=m\times\mbox{(Avg brightness level of
$X_{i}$)}\times\mbox{(Avg brightness level of $X_{j}$)}.$ So all this kernel
depends on is the average brightness levels of the samples. In the case of
rotational invariance, it will only depend on the average brightness along
each concentric circle’s circumference. As expected, employing this kernel
produces very poor results, as we will see in the experimental results
reported in Section IV.

####  II-C2 Data Augmentation

One popular approach to learning how to recognize translated images is to use
data augmentation. This consists of creating several copies of the existing
samples, and augmenting the dataset with them. It turns out that such data
augmentation basically corresponds to using the average-fit kernel as (7).
This can be seen as follows. Let us consider the case where we maximize the
augmented data by including all translates of all images. Then the resulting
dual problem for SVM margin maximization is:

$\displaystyle\max_{\lambda}$
$\displaystyle-\frac{1}{2}\sum_{i,j,T_{1},T_{2}}\lambda_{i,T_{1}}\lambda_{j,T_{2}}y_{i}y_{j}K_{base}(T_{1}X_{i},T_{2}X_{j})+\sum_{i,T}\lambda_{i,T}$
s.t. $\displaystyle\ \lambda_{i,T}\geq 0,\ \forall i\in[n],\forall
T\in\mathcal{G}_{trans};\ \ \sum_{i,T}\lambda_{i,T}y_{i}=0.$

The corresponding classification is
$\text{sign}(\sum_{i,T}\lambda_{i,T}^{*}y_{i}K_{base}(TX_{i},X)+b^{*})$, where
$b^{*}=y_{j}-\sum_{i,T}\lambda_{i,T}^{*}y_{i}K_{base}(TX_{i},T^{\prime}X_{j})$,
for any $j$ and $T^{\prime}$ satisfying the corresponding optimal dual
variable $\lambda_{j,T^{\prime}}^{*}>0$. When no data augmentation is
implemented, i.e., $|\mathcal{G}_{trans}|=1$, we will use $\lambda_{i}$ as
shorthand for $\lambda_{i,1}$. As shown in Theorem 4.1 of [26], this is simply
the dual problem for the SVM with $K_{avg}$, and so:

$\displaystyle\sum_{i}\lambda_{i}K_{TI,avg,base}(X_{i},X_{j})=\sum_{i,T\in\mathcal{G}}\lambda_{i,T}K_{base}(TX_{i},X_{j}),\
\forall j.$

Hence data augmentation is mathematically equivalent to a kernel with the
average similarity over all transformations. As we have seen above, this
yields a poor classifier since it only depends on the average brightness level
of an image. ∎

A simple example illustrates the superiority of $K_{TI,best,linear}$ over data
augmentation or $K_{TI,avg,linear}$.

######  Example 1.

Consider a training set with just two samples $X_{1}=(1,2)$ and $X_{2}=(5,2)$,
shown in red in Fig. 1. Data augmentation generates two new samples
$X_{3}=(2,1)$ and $X_{4}=(2,5)$, shown in green, resulting in the decision
boundary shown by the blue solid line in Fig. 1. One may note that the
decision boundary $X^{(1)}+X^{(2)}=5$ depends only on the total brightness
level $X^{(1)}+X^{(2)}$, since data augmentation is the same as $K_{TI,avg}$.

However, the decision boundary of
$K_{TI,best,linear}(X_{i},X_{j})=\sup_{T\in{\cal{G}}_{trans}}\frac{1}{2}(TX_{i})^{T}X_{j}$
is piecewise linear due to the “sup" operation. Since each piece only needs to
consider the half of the samples that are on the same side of the symmetry
axis (red dashed line), it naturally leads to a larger margin, as shown by the
orange piecewise linear separatrix. For other kernels (e.g., polynomial
kernels), the shape of the decision boundary will be altered correspondingly
(e.g., piecewise polynomial), but a larger margin still results for the TI
best-fit kernel.

Figure 1:  The kernel $K_{TI,best,linear}$ produces the piecewise linear
separatrix shown in orange with a larger margin than the blue separatrix that
data augmentation and $K_{TI,avg}$ yield.

###  II-D Rotation-Invariant Kernels

Define
$T_{\theta}X_{i}=\\{[X_{i}^{(p\cos\theta-q\sin\theta,p\sin\theta+q\cos\theta)}]\\}$,
where $0\leq p\leq m_{1}-1,0\leq q\leq m_{2}-1,-\pi<\theta\leq\pi$. Similarly,
the rotational-invariant (RI) kernel is

$K_{RI,best,base}(X_{i},X_{j}):=\sup_{\theta}K_{base}(T_{\theta}X_{i},X_{j}),\forall
X_{i},X_{j}\in\mathcal{X}.$ (8)

A similar proof as for the RI kernel yields:

######  Lemma 2.

The rotational invariant kernels $K_{RI,best,poly}$ are positive definite with
probability approaching one as $m\to+\infty$, under the same conditions as in
Theorem 1.

In Section IV, we also report on the huge performance gain obtained by using
an SVM with the kernel $K_{RI,best,poly}$.

##  III Incorporating Locality at Multiple Spatial Scales

To describe the property of “locality" and its incorporation into SVMs, we
consider the simple context of a polynomial kernel and a one-dimensional real-
valued pixel sequence.

Let us regard the individual pixel values
$\\{X_{i}^{(1)},X_{i}^{(2)},\ldots,X_{i}^{(m)}\\}$ as the primitive features
at “Layer 0". Consider now a “local" feature dependent only on the nearby
pixels $\\{X_{i}^{(\ell)},X_{i}^{(\ell+1)},\ldots,X_{i}^{(\ell+k_{1})}\\}$
that can be modeled by a polynomial of degree $d_{1}$. We refer to $k_{1}$ as
the locality parameter.

It is a linear combination of monomials of the form
$\prod_{j=\ell}^{\min(\ell+k_{1},m)}(X_{i}^{(j)})^{c_{j}}$ with
$\sum_{j=\ell}^{\min(\ell+k_{1},m)}c_{j}\leq d_{1}$ where each integer
$c_{j}\geq 0$. This gives rise to a kernel

$K_{L,ij}=[\sum_{p=\ell}^{\min{(\ell+k_{1},m)}}X_{i}^{(p)}X_{j}^{(p)}+1]^{d_{1}}.$
(9)

We regard “Layer 1" as comprised of such local features of locality parameter
$k_{1}$ and polynomial degree $d_{1}$.

To define a larger spatial scale of features at “Layer 2", one may consider a
polynomial of degree $d_{2}$ in the contiguous features at Layer 1 that are at
most $k_{2}$ apart. This leads to a two-layer kernel

$K_{L,ij}=[\sum_{\ell=1}^{m-k_{1}}(\sum_{p=\ell}^{\ell+k_{1}}X_{i}^{(p)}X_{j}^{(p)}+1)^{d_{1}}+1]^{d_{2}}.$
(10)

This can be recursively applied to define deeper kernels with locality; the
three-layer kernel is architecture

$K_{L,ij}=\\{\sum_{g=1}^{m-k_{1}-k_{2}}[\sum_{\ell=g}^{g+k_{2}}(\sum_{p=\ell}^{\ell+k_{1}}X_{i}^{(p)}X_{j}^{(p)}+1)^{d_{1}}+1]^{d_{2}}+1\\}^{d_{3}}.$
(11)

One can choose the number of layers so that the final layer’s output depends
on all the features. The techniques of “padding" and “stride" [27] employed in
CNNs can be brought in naturally too. If necessary, one can select
corresponding zero paddings and strides for maintaining the input and output
sizes at each layer the same.

The above procedure extends naturally to two-dimensional images
$\\{X_{i}^{(p,q)}:1\leq p,q\leq m\\}$. Then the kernel at layer 1 is simply
$(\sum_{q=s}^{s+k_{1}}\sum_{p=\ell}^{\ell+k_{1}}X_{i}^{(p,q)}X_{j}^{(p,q)}+1)^{d_{1}}$.
The resulting kernels are always positive definite:

######  Lemma 3.

$K_{L}$ is a positive definite kernel.

###### Proof.

The result follows from the properties of positive definite kernels in Lemma
2, since the kernel $K_{L}$ can be obtained by repeatedly employing the above
operations with $\alpha=\beta=\gamma=1$, starting with a base linear kernel. ∎

One difference from CNNs is that, for the same input layer, one cannot have
multiple output channels. The reason is that if we design multiple channels
with different degrees, then the channel with a larger degree will
automatically subsume all terms generated by the channel with a smaller
degree. Therefore, it is equivalent to having only one output channel with the
largest degree. On the other hand, if the images have multiple channels to
start with (as in R, G, and B, for example), then they can be handled
separately. But after they are combined at a layer, there can only be one
channel at subsequent higher layers.

##### Combining Locality at Multiple Spatial Scales with Transformational
Invariance

To combine both locality at multiple spatial scales and transformational
invariance, a kernel with locality at multiple spatial scales can be
introduced as a base kernel into transformation-invariant kernels.

##### Complexity Analysis and Memory Trade-off

One may trade off between the memory requirement and computation time when it
comes to the depth of the architecture. Supported by adequate memory space,
one can store all kernel values from every layer, with both computation time
and memory space increasing linearly with depth. In contrast, when limited by
memory space, one can store only the kernel values from the final layer. In
that case, although the memory requirement does not increase with depth,
computation time grows exponentially with depth.

The time complexity of computing the polynomial kernel is between $O(n^{2}m)$
and $O(n^{3}m)$ based on LIBSVM implementation [7], while space complexity is
$O(n^{2})$. With sufficient memory $O(n^{2}m)$, the computations of kernel
values can be parallelized so that the time complexity of the locality kernel
is considerably reduced to between $O(n^{2}kd)$ and $O(n^{3}kd)$, where $k$
and $d$ are the locality parameter and the depth respectively with $kd\ll m$.

##  IV Experimental Evaluation

###  IV-A Datasets

We evaluate the performance of the methods developed on four datasets:

  1. 1.

The Original MNIST Dataset [4]

  2. 2.

The EMNIST Letters Dataset [6]

  3. 3.

The Translated MNIST Dataset: Since most generally available datasets appear
to have already been centered or otherwise preprocessed, we transform them to
better verify the accuracy improvement of TI kernels. We place the objects in
a larger (64*64*1) canvas, and then randomly translate them so that they are
not necessarily centered but still maintain their integrity. In addition, we
add a Gaussian noise ($\mu=0,\sigma=0.1$) to avoid being able to accurately
center the image by calculating the center-of-mass. We call the resulting
dataset the “Translated dataset". Fig. 2a shows some samples from different
classes of the Translated MNIST dataset.

  4. 4.

The Rotated MNIST Dataset: Similarly, we also create a “Rotated dataset". (We
skip the digits “6" and “9" since they are equivalent after
$180^{\mbox{\tiny{o}}}$ rotation.) Fig. 2b displays some samples from
different classes of the Rotated MNIST dataset.

(a)

(b)

Figure 2: Transformed MNIST with random translation/rotation and Gaussian
noise ($\mu=0,\sigma=0.1$).

###  IV-B Experimental Results and Observations

Table II and Fig. 3 provide the test accuracy of all methods on the Original
and Transformed MNIST Datasets, respectively, while Table III shows the test
accuracy for the EMNIST Letters Dataset [6]. In the Tables and Fig. 3, the
letters L, TI, RI represent Locality at multiple spatial scales, TI kernels,
and RI kernels, respectively. A combination such as L-TI represents an SVM
that uses both Locality as well as Translational Invariance.

(a)

(b)

Figure 3: Test accuracy vs. Number of training samples for Transformed MNIST
datasets

For the Original MNIST dataset with 100/200/500 training samples (Table II),
after introducing locality and transformational invariance, the classification
accuracy is improved from 68.33%/86.96%/91.33% reported by the best CNNs
optimized over architectures and dimensions [5] to 81.55%/89.23%/93.11%
respectively. The small but tangible improvements indicate that the original
dataset does not center and deskew objects perfectly. Larger improvements can
be observed from the EMNIST Letters dataset [6] in Table III compared with the
original SVM, RI kernel based on Average-Fit, and ResNet. Note that all test
accuracy displayed in the tables is multi-class classification accuracy.

In Fig. 3, we present the obtained test accuracy as a function of the number
of training samples for two different transformed datasets. Experiments are
performed 10 times with mean and standard deviation denoted by the length of
the bars around the mean, for 100/300/500/700/1000 training samples
respectively. (L-)TI-SVM and (L-)RI-SVM outperform ResNet in many cases when
there is no data augmentation since they embed useful domain knowledge for
classifiers, especially for the small size regime of training samples.
However, with the increase in the number of training samples, the benefits
brought by domain knowledge gradually decrease, as shown in Fig. 3.
Additionally, the test accuracy of newly proposed methods has a smaller
variance than ResNet’s in general.

From the experimental results, we see that all SVMs with newly defined kernels
improve upon the test accuracy of the original SVM method, whether they are
original datasets or transformed datasets. They also greatly outperform the
best CNNs in the small training sample regime of interest. For transformed
datasets, improvements are more obvious.

###  IV-C Details of Experimental Evaluation

TABLE II: Original MNIST Dataset (100, 200, 500 training samples): Test accuracy of newly proposed methods compared with the original SVM, RI-SVM based on Average Fit, and the best CNN. Method | 100 | 200 | 500
---|---|---|---
Acc/% | Acc/% | Acc/%
L-TI-RI-SVM | 81.55 | 89.23 | 92.58
TI-RI-SVM | 75.10 | 86.47 | 93.11
L-TI-SVM | 78.86 | 87.02 | 91.01
L-RI-SVM | 77.96 | 83.96 | 89.65
TI-SVM | 69.34 | 82.34 | 91.00
RI-SVM | 73.82 | 83.60 | 90.19
L-SVM | 75.27 | 82.11 | 88.21
1-4[0.8pt/2pt] SVM | 68.16 | 78.67 | 87.14
RI-SVM (Average-Fit) | 68.05 | 78.81 | 87.21
Best CNN 111Since [5] did not provide the test accuracy for 200 training samples, we use a fine-tuned ResNet to fill in the gaps. | 68.33 | 86.96 | 91.33

With consideration of computational speed and memory space, we utilize a two-
layer structure (10) as well as a $\frac{k_{1}-1}{2}$-zero padding and a
stride of 1 to implement locality. In order to compare the test accuracy of
L-SVM, TI-SVM, RI-SVM and further combine them, we select a polynomial kernel
with a fixed degree (8 in our experiments) to realize proposed methods. Note
that degree 8 is not necessarily the optimal degree; one can tune the specific
degree for different datasets.

We compare our results with [5], which adopts a tree building technique to
examine all the possible combinations of layers and corresponding
dimensionalities to find the optimal CNN architecture. As for the DNN
benchmark of the EMNIST Letters and the Transformed MNIST datasets, we select
ResNet [18, 19], a classic CNN architecture, as a DNN benchmark. Plus, for
fairness, we do not implement data augmentation for ResNet and train all
models from scratch.

Note that all experimental results are based on LIBSVM [7] implementation and
are carried out on an Intel Xeon E5-2697A V4 Linux server with a maximum clock
rate of 2.6 GHz and a total memory of 512 GB.

TABLE III: EMNIST Letters Dataset (100, 200, 500 training samples): Test accuracy of newly proposed methods compared with the original SVM, RI-SVM based on Average-Fit, and ResNet. Method | 100 | 200 | 500
---|---|---|---
Acc/% | Acc/% | Acc/%
L-TI-RI-SVM | 44.56 | 55.18 | 66.42
TI-RI-SVM | 43.16 | 52.40 | 67.42
L-TI-SVM | 42.51 | 52.81 | 64.66
L-RI-SVM | 38.39 | 47.29 | 59.76
TI-SVM | 39.94 | 48.12 | 63.52
RI-SVM | 38.03 | 45.02 | 59.04
L-SVM | 37.01 | 45.08 | 58.05
1-4[0.8pt/2pt] SVM | 36.65 | 42.74 | 56.38
RI-SVM (Average-Fit) | 36.82 | 42.41 | 56.22
ResNet | 11.48 | 41.17 | 61.12

##  V Concluding Remarks

In this paper, we develop transformation-invariant kernels that capture domain
knowledge of the invariances in the domain. They can also additionally
incorporate composition and locality at multiple spatial scales. The resulting
kernels provide superior classification performance in the small sample size
regime that is of interest in this paper. Experiments demonstrate that for the
same polynomial kernel, incorporating locality and transformational invariance
improves accuracy, especially for situations where data is scarce. This work
can be applied to fields other than image classification. The problem that
motivates this study on transformation invariance is epileptic seizure
prediction. Features that represent the characteristics of epilepsy in the
electroencephalogram (EEG) signal are translation invariant within the time
range. A hierarchy of features at different time scales can be incorporated by
employing locality at multiple scales.

## Acknowledgement

This material is based upon work partially supported by US National Science
Foundation under CMMI-2038625, HDR Tripods CCF-1934904; US Office of Naval
Research under N00014-21-1-2385; US ARO under W911NF2120064, W911NF1810331;
and U.S. Department of Energy’s Office of Energy Efficiency and Renewable
Energy (EERE) under the Solar Energy Technologies Office Award Number DE-
EE0009031. The views expressed herein and conclusions contained in this
document are those of the authors and should not be interpreted as
representing the views or official policies, either expressed or implied, of
the U.S. NSF, ONR, ARO, Department of Energy or the United States Government.
The U.S. Government is authorized to reproduce and distribute reprints for
Government purposes notwithstanding any copyright notation herein.

## References

  * [1] M. Tan and Q. Le, “Efficientnet: Rethinking model scaling for convolutional neural networks,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 6105–6114.
  * [2] E. D. Cubuk, B. Zoph, D. Mane, V. Vasudevan, and Q. V. Le, “Autoaugment: Learning augmentation policies from data,” _arXiv preprint arXiv:1805.09501_ , 2018.
  * [3] I. Daubechies, R. DeVore, S. Foucart, B. Hanin, and G. Petrova, “Nonlinear approximation and (deep) relu networks,” _Constructive Approximation_ , pp. 1–46, 2021.
  * [4] Y. LeCun and C. Cortes, “MNIST handwritten digit database,” 2010. [Online]. Available: http://yann.lecun.com/exdb/mnist/
  * [5] R. N. Dsouza, P.-Y. Huang, and F.-C. Yeh, “Structural analysis and optimization of convolutional neural networks with a small sample size,” _Scientific Reports_ , vol. 10, no. 1, pp. 1–13, 2020.
  * [6] G. Cohen, S. Afshar, J. Tapson, and A. Van Schaik, “Emnist: Extending mnist to handwritten letters,” in _2017 International Joint Conference on Neural Networks (IJCNN)_. IEEE, 2017, pp. 2921–2926.
  * [7] C.-C. Chang and C.-J. Lin, “Libsvm: A library for support vector machines,” _ACM Transactions on Intelligent Systems and Technology (TIST)_ , vol. 2, no. 3, pp. 1–27, 2011.
  * [8] C. Cortes and V. Vapnik, “Support-vector networks,” _Machine Learning_ , vol. 20, no. 3, pp. 273–297, 1995.
  * [9] D. Lu and Q. Weng, “A survey of image classification methods and techniques for improving classification performance,” _International Journal of Remote Sensing_ , vol. 28, no. 5, pp. 823–870, 2007.
  * [10] V. N. Vapnik, The nature of statistical learning theory.  _Springer_ , 1995.
  * [11] B. E. Boser, I. M. Guyon, and V. N. Vapnik, “A training algorithm for optimal margin classifiers,” in _Proceedings of the Fifth Annual Workshop on Computational Learning Theory_ , 1992, pp. 144–152.
  * [12] Y. le Cun, “Generalization and network design strategies,” _Connectionism in Perspective_ , vol. 19, pp. 143–155, 1989.
  * [13] A. Krizhevsky, G. Hinton et al., “Learning multiple layers of features from tiny images,” 2009.
  * [14] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in _2009 IEEE Conference on Computer Vision and Pattern Recognition_. Ieee, 2009, pp. 248–255.
  * [15] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” in _Advances in Neural Information Processing Systems_ , 2012, pp. 1097–1105.
  * [16] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” _arXiv preprint arXiv:1409.1556_ , 2014.
  * [17] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich, “Going deeper with convolutions,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2015, pp. 1–9.
  * [18] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2016, pp. 770–778.
  * [19] ——, “Identity mappings in deep residual networks,” in _European Conference on Computer Vision_. Springer, 2016, pp. 630–645.
  * [20] B. Haasdonk and H. Burkhardt, “Invariant kernel functions for pattern analysis and machine learning,” _Machine Learning_ , vol. 68, no. 1, pp. 35–61, 2007\.
  * [21] ——, “Classification with invariant distance substitution kernels,” in _Data Analysis, Machine Learning and Applications_. Springer, 2008, pp. 37–44.
  * [22] S. Mei, T. Misiakiewicz, and A. Montanari, “Learning with invariances in random features and kernel models,” _arXiv preprint arXiv:2102.13219_ , 2021\.
  * [23] B. Schölkopf, P. Simard, A. J. Smola, and V. Vapnik, “Prior knowledge in support vector kernels,” in _Advances in Neural Information Processing Systems_ , 1998, pp. 640–646.
  * [24] R. S. Varga, Geršgorin and his circles.  _Springer Science & Business Media_, 2010, vol. 36.
  * [25] J. Schur, “Bemerkungen zur theorie der beschränkten bilinearformen mit unendlich vielen veränderlichen.” 1911.
  * [26] Z. Li, R. Wang, D. Yu, S. S. Du, W. Hu, R. Salakhutdinov, and S. Arora, “Enhanced convolutional neural tangent kernels,” _arXiv preprint arXiv:1911.00809_ , 2019.
  * [27] I. Goodfellow, Y. Bengio, and A. Courville, Deep learning.  _MIT press_ , 2016.
  * [28] B. Ghosh, “Probability inequalities related to markov’s theorem,” _The American Statistician_ , vol. 56, no. 3, pp. 186–190, 2002.
  * [29] M. Wainwright, “Basic tail and concentration bounds,” _URL: https://www. stat. berkeley. edu/…/Chap2_TailBounds_Jan22_2015. pdf (visited on 12/31/2017)_ , 2015.

## Appendix

##  VI Supporting Definitions and Lemmas

######  Lemma 4 (Cantelli inequality [28]).

Let $X$ be a random variable with $\mathbb{E}[X]=\mu$ and
$\operatorname{Var}[X]=\sigma^{2}$, then for all $t>0$,

$\displaystyle\mathbb{P}[X\geq\mu+t]$
$\displaystyle\leq\frac{\sigma^{2}}{\sigma^{2}+t^{2}},$ (12)
$\displaystyle\mathbb{P}[X\leq\mu-t]$
$\displaystyle\leq\frac{\sigma^{2}}{\sigma^{2}+t^{2}}.$ (13)

######  Definition 1.

A random variable X with mean $\mu=\mathbb{E}[X]$ is sub-exponential if there
are non-negative parameters $(\nu,b)$ such that [29]

$\displaystyle\mathbb{E}[\exp{(\lambda(X-\mu))}]\leq\exp(\frac{\nu^{2}\lambda^{2}}{2}),\
\ \forall|\lambda|<\frac{1}{b}.$ (14)

######  Lemma 5 (Sub-exponential tail bound [29]).

Suppose that $X$ is sub-exponential with parameters $(\nu,b)$. Then,

$\displaystyle\mathbb{P}[X\geq\mu+t]\leq\begin{cases}\exp(-\frac{t^{2}}{2\nu^{2}})&\text{if
}0\leq t\leq\frac{\nu^{2}}{b},\\\ \exp(-\frac{t}{2b})&\text{if
}t>\frac{\nu^{2}}{b}.\end{cases}$ (15)


# feather - a Python SDK to share and deploy models

Nihir Vedd  Paul Riga

###### Abstract

At its core, feather was a tool that allowed model developers to build
shareable user interfaces for their models in under 20 lines of code. Using
the Python SDK, developers specified visual components that users would
interact with. (e.g. a FileUpload component to allow users to upload a file).
Our service then provided 1) a URL that allowed others to access and use the
model visually via a user interface; 2) an API endpoint to allow programmatic
requests to a model.

In this paper, we discuss feather’s motivations and the value we intended to
offer AI researchers and developers. For example, the SDK can support multi-
step models and can be extended to run automatic evaluation against held out
datasets. We additionally provide comprehensive technical and implementation
details.

N.B. feather is presently a dormant project. We have open sourced our code for
research purposes: https://github.com/feather-ai/

Machine Learning, ICML

##  1 Introduction

Over the last decade or so, research and interest in machine learning (ML) has
grown exponentially. This growth has led to the development and adoption of
specialized tools which provide a significantly better development experience.
Typically, these tools target one part of the multi-part modelling pipeline.
For example, PyTorch (Paszke et al., 2019) targets the model building itself;
Weights & Biases (Biewald, 2020) targets experiment tracking and model
versioning.

Until 2021, very few popular tools existed that allowed model developers (MDs)
to easily share their models with other people (model consumer; MC). The most
common way of doing so was to upload code to a public repository (e.g. GitHub)
and provide instructions to technical MCs in order to recreate a published
model. Another alternative is for the MD to create a front-end that enables
both technical and non-technical MCs to interact with the model.
Unfortunately, in either case, the incentives for MDs are not clear. From the
perspective of the MD, the former case is considerably less work. However,
there are multiple drawbacks. It: 1) makes the model inaccessible to those
without coding ability; 2) places a responsibility on the MD to maintain the
repository; 3) requires an MC to have the relevant hardware to use the model.

Additionally, anecdotal evidence has shown that for a technical MC to
qualitatively use and test the model, hours of setup may be required. These
problems can largely be solved with a custom front-end, but: 1) it requires
the MD (or their team) to understand front-end and back-end technologies; 2)
requires maintainers to ensure the quality of service (including scaling
infrastructure when necessary); 3) is out-of-scope based on current
conventions for ML research; 4) requires a financial commitment from the MD or
their affiliated lab for hosting models.

Figure 1: Left: An example feather script that deploys an image classifier.
Right: The UI rendered by the feather script. ‘my_classifier’ (line 11) is an
inference function that runs a classification model. It is regular Python code
that can call any library (e.g. PyTorch, Tensorflow etc.)

The overarching effect of the above points is two-fold: 1) AI research in
general loses transparency as it becomes (unnecessarily) harder to verify
results; 2) MDs who are ideating may be deterred from diving deeper into their
ideas as practical or technical barriers prevent them from using a model for
small-sample inference, let alone training a model from scratch. Both of these
points ultimately lead to a slower rate of production and adoption of AI.

At the time of feather’s inception, we were able to find only 2 tools which
allowed MDs to visually share their code via a component-based SDK: Gradio
(Abid et al., 2019) and Streamlit (Treuille & Teixeira, 2018). We discuss
these further in Section 2. Both tools faced restrictive drawbacks. A common
drawback was the lack of support for multi-step models. That is, a model which
is composed of multiple sub-models within it, where each sub-model requires
human interaction. For example, a guided image captioning system (e.g. Ng et
al. (2020) may require a human to explicitly select objects they want captions
for before generating a caption. That is, after inputting an image, an object
detector outputs a list of detected objects for a human to control the caption
generation upon. A human then selects a subset of objects as input to a
conditional caption generation model. Otherwise, Gradio used to only allow MDs
to share their models for 6 hours at a time. These models were hosted directly
on the MDs machine - thus exposing a myriad of security issues. Long
lived/Gradio hosted models required a premium subscription levied on the MD.
HuggingFace Spaces (Wolf et al., 2020) was released during feather’s
development process. These largely solved the aforementioned issues.

Despite this, feather was envisioned to be more than a place to simply share
your models via a UI. Within the direct scope of our SDK, we can:

  * •

Run models through a UI

  * •

Execute these models programmatically via an API. feather can also
automatically generate documentation for these APIs.

  * •

Deploy multi-step models (with built in state management that allows users to
re-run or refresh steps)

  * •

Automatically model versioning

feather was designed to have natural extensions that could ease the deployment
workflow for an MD and further democratize AI research. Specifically, we
developed our SDK such that the following features could be supported. +
indicates a research-based feature (we refer to these often through the
paper):

  * •

Automatic evaluation against held out datasets +

  * •

Provide a ModelOps like experience, where the MD can visualise incoming data
to counter-act model/concept drift.

  * •

Fine-tuning as a service. That is, allow MCs to upload data to fine-tune a
model that an MD has published.

  * •

For UI based execution, enable MCs to provide feedback on the model
predictions per sample uploaded. MDs may then be able to use this now-labelled
data to augment their dataset or model. Future extensions could have first-
party support for RLHF (Christiano et al., 2017).

  * •

Optionally require MCs to pay per execution (thus financially incentivizing
MDs to maintain and upkeep their models).

  * •

Group models by task and/or dataset to allow easy access. Coupled with the
aforementioned automatic evaluation point, this allows us to build
leaderboards for different tasks and/or datasets. +

  * •

Embedding models on different websites

  * •

Permission sharing of models (e.g. Private/Unlisted/Public) and team-oriented
features

The rest of this paper is structured as follows. In Section 2 we provide an
overview of the alternate approaches to solve the aforementioned problems. In
Section 4 we dive into technical and implementation details on our system.
Section 5 discusses improvements directly related to the SDK.

##  2 Related Work

As hinted at in Section 1, there are solutions of varying level of difficulty
which allow an MD to share a model. Here, we introduce these solutions and
discuss key differences where possible. Between 2021 and early-2022, when
feather was actively being developed, we found only 3 tools that had
considerable community adoption: Gradio, Streamlit, and Replicate.

###  2.1 Gradio

Gradio’s (Abid et al., 2019) core contribution is similar to feather’s - a
simple-to-use SDK that allows researchers to build shareable
interfaces/webpages for their models. At the time of feather’s development,
Gradio lacked support for features that feather provided out of the box:
Server-based hosting (N.B. this was a paid feature); multi-step execution;
API-based execution. In order, server-based execution allows an MD to upload
their models to an external server as opposed to hosting the model on their
own machine. This solves an array of security flaws and enables a model to be
accessed at any time, instead of the temporary 6 hours connection provided by
Gradio. Examples of security flaws may involve a malicious MD storing personal
information uploaded by an MC. They may also involve a malicious MC entering
eval statements in the MDs code; since the models are not executed in a
sandboxed environment, this may pose a threat to the MDs machine. However,
HuggingFace Spaces now solves the problem of self-hosting. (discussed further
in Section 2.3). Multi-step execution enables deploying models that require at
least 1 human interaction in the model pipeline. Examples may include Vedd et
al. (2021) and Jiang et al. (2022). API-based execution allows a model to be
used programmatically for high-throughput inference.

###  2.2 Streamlit

Streamlit (Treuille & Teixeira, 2018) is a product for sharing data apps.
Similar to Gradio and feather, Streamlit allows you to define components in
Python code to be rendered onto a webpage. Streamlit focuses its effort on
single-step execution. At some point during feather’s development, Streamlit
released its “state” feature. The state feature enables MDs to run callback
functions upon an input change. Thus, it may be utilized execute models which
require multiple steps.

Streamlit’s value as a place to build web interfaces and share models is
clear. However, it lacks the support for programmatic execution of models via
an API. As a result, you cannot automatically evaluate models against a
dataset. Additionally, it positions itself as a product and has shows no
intention to support the research based features outlined in the features in
Section 1.

###  2.3 HuggingFace Spaces

Around mid 2021, HuggingFace Spaces (Wolf et al., 2020) (henceforth Spaces)
was released. Spaces allows hosting and sharing of ML apps made by community
members or organisations. Crucially, it itself is not an SDK used to create
interfaces for models. Rather, it is a service that allows MDs to upload their
models which have interfaces created by Streamlit or Gradio. Spaces alleviates
the self-hosting deployment procedure of Gradio (see Section 2.1) and provides
a user with a clean URL to their model (e.g.
huggingface.co/spaces/<username>/<modelname>). With respect to UI-based
execution, feather = Spaces + Gradio.

Spaces allows execution on CPU or GPU. CPU execution is always free, however
GPU execution levies a cost on the MD. One difference between feather and
Spaces is that we attempt to reverse this cost by levying a cost on the MC.
Another difference is that Spaces only allows UI-based execution of models.
Similar to the drawbacks of Streamlit, this means that many of the research
based features outlined in Section 1 are not supported by Spaces.

###  2.4 Replicate

Replicate (organisation) (Jansson & Firshman, 2021) consists of 2 different
sub-products: Cog and the web-based tool Replicate. Cog is an open-source tool
that allows MDs to containerize ML models. Cog attempts to simplify the
deployment process of an ML model through multiple means. Alongside the
containerisation process, an MD can define the inputs and outputs of their
model in Python, from which Cog automatically creating an OpenAPI schema. Cog
will then use this to automatically create a RESTful API. Cog additionally
provides some deployment features, such as queue workers and cloud storage.
Though their roadmap does not indicate support for the research based features
we outlined in Section 1, their API-first philosophy means their product may
be extended to support these. Finally, Cog does not support multi-step models.

Recently, Replicate (organisation) released their web-based product,
Replicate. Replicate enables UI-based execution of a Cog container. We omit
further discussion about Replicate as during feather’s development and
release, the web-based Replicate did not exist.

###  2.5 Self deployment

The most flexible approach of deploying a model is self-deployment and
hosting. This allows an MD to create interfaces which are fully bespoke to the
model at hand. Though this category of deployment does both allow API and UI-
based execution of models, there are drawbacks to this approach from both a
product perspective and an MDs perspective. From a product perspective, it is
non-trivial to compare the model the MD has created to other models across
different websites. Hence research based features such as leaderboards and
discoverability of models is severely limited.

From the MD perspective, there is a significant trade-off in flexibility vs
development time. Ignoring any financial costs, the time cost of building an
interface from scratch is lengthy, and many use different technologies than
what an MD is familiar with already. Management and scalability of models and
infrastructure is now also the MDs responsibility. Additionally, many features
which feather planned to support (e.g. data visualisation for the MD; model
feedback from the MC to MD) are features that would need to explicitly be
built by the MD.

From an MCs perspective, they now have to discover the different websites that
are create by MDs - a central place to find models would not exist. Additional
friction is also placed on the MC to register and enter payment details for
each different custom website/product/service they use.

##  3 User Research

feather’s feature set was developed after conducting a dozen 1 hour interviews
with ML practitioners. Strictly, practitioners are MDs, however our research
uncovered that many MDs may also be MCs. The practitioners ranged a variety of
professions. Some were researchers, some hobbyists, and others worked in
industry settings. They had varying use-cases for a deployment tool such as
feather, however one common pain point that was highlighted was that of
accessing and using models that have been shared by others. Solving this
problem was a core motivation for feather.

The rest of this section compiles the findings we made during our research
process. We structure our learnings as follows. We find segmenting the
practitioners by profession is most natural. For each segment, we present
general learnings for the following questions: 1) Under what context do you
share your models; 2) How do you share them; 3) How do you maintain them; 4)
Does your work entail you using models that others have developed; 5) What
problems do you face when using other peoples models.

Researchers typically share their models alongside paper publications, despite
this not being a strict requirement for accepted work. They are motivated by
encouraging innovation in the scientific community, and value open source
access because this is normally something that they have benefited from as
well. Their models are normally publicly shared on a version control website
such as GitHub, where source files and training instructions are provided.
Researchers may or may not release model weights. They often have intentions
to maintain their code, but find that unless someone opens an issue, the code
will stay as-is. Researchers often utilise models developed by other
researchers to either extend the previous researchers contributions, or to
test the models capabilities. In other words, they are both MDs and MCs.
Typically, researchers are frustrated at the disproportionate time it takes to
run inference on models that other researchers have released. This
‘disproportionate’ time exists for 2 reasons: 1) Issues with environments; 2)
Lack of README and/or documentation in the released code.

Hobbyists are individuals who explore and utilise machine learning models out
of personal interest or for smaller-scale projects. They often share their
models by building a custom interface and hosting the binaries on a cloud-
based service such as AWS. MCs may find these models through the blogs,
forums, or social media platforms that the hobbyists share them on. Hobbyists
also leverage existing open-source models and libraries and contribute to them
when possible. The motivation of up-keeping a model for a hobbyists varies on
a person-to-person case. However, the following reasons seem to be emerge as
possible motivations: financial returns; being part of a technical community;
personal learning. Hobbyists frequently use models developed by others, as
they often seek inspiration and learn from existing projects. They may modify
or extend these models to suit their own use-cases or simply experiment with
them to gain a deeper understanding. Similar to researchers, they often
experience problems setting up environments or lack of documentation.
Additionally, hobbyists may not have the same levels of resources as
researchers or industry professionals. Thus, executing larger models often
proves challenging.

Industry Professionals work in various sectors, including healthcare, finance,
and technology, and they utilise machine learning models to solve real-world
problems. These professionals typically share their models internally within
their organization or with clients. Whilst in the development process, the
most common way MDs ‘share’ their model with other internal stakeholders is
screen sharing and interacting with the model via CLI. If multiple people are
working on the model code, version control software such as GitHub is
utilised. Once developed, MDs in industry use either proprietary platforms or
cloud-based services for model sharing and deployment. Industry professionals
have a strong focus on maintaining and updating their models to ensure optimal
performance and to meet business requirements. Some businesses also invest in
ModelOps, ensuring that consumer facing models remain at an adequate quality.
At the time of conducting these interviews, they often used models developed
by others, either from research, other companies, or even internally. Some
professionals in this category did write custom model code themselves. Where
possible, maintained services were preferred because these types of models
have been empirically validated by other clients. Their largest concern with
other peoples models were the lack of robustness, and potential real world
failure cases which have not been identified in the associated research paper.

As seen above, the problems these three segments of practitioners face when
using other people’s models are diverse, yet some common themes emerge.
Environment setup issues and lack of documentation are prevalent across all
three groups, indicating that more streamlined methods for sharing models and
clearer instructions on usage could significantly improve the user experience.
Additionally, concerns about robustness, resource requirements, and real-world
applicability of shared models were noted.

By understanding these common pain points, feather’s feature set was designed
to address the specific needs of each user segment while also tackling the
broader issues that affect the entire machine learning community. feather was
thus motivated to be a tool that simplified model sharing, deployment, and
maintenance.

##  4 Methodology

In this section we discuss underlying implementation details of feather. To be
explicit, feather is library agnostic. It is a system that publishes and
executes code. Any framework (e.g. PyTorch, Tensorflow, SKlearn etc.) may be
utilised in the publisher’s code. In other words, feather’s architecture
facilitates 2 key functions: model creation/publishing and model execution. To
achieve this, our system requires 4 components: an SDK (Section 4.1), a front-
end web application and a model runner (Section 4.5), and a back-end service
(Section 4.4) which ties the system components together. A diagram of how the
different components interact with each other can be seen in Figure 2.

Reader’s are likely aware that ML models are based on mapping an input to an
output. For example, an input of a handwritten digit can be mapped to a class
label of the digit, or an input of a random noise vector can be mapped to some
high-dimensional image. Some models may also require multiple steps of
execution before generating a final output. For example, Jiang et al. (2022),
Ng et al. (2020) and Vedd et al. (2021). In the latter, the authors devise a
visual question generation (VQG) algorithm that has three steps: 1) Input an
image; 2) An object detector outputs a set of detected objects in the image;
3) A question generator uses a selected subset of these detected objects to
generate a natural language question. Aside from self deployment, the tools we
outlined in Section 2 do not support such a multi-step use case. Hence, we
motivate the sub-sections below with this example.

Figure 2: The feather architecture is centred around 2 key functions: model
creation/publishing and model execution. The high level system diagram is
shown here and comprises the following key components:
The Python SDK is a client-facing python library. It implements feather’s
component APIs which allows MCs to quickly create multi-step models. Rich
metadata about the model is generated, and this information is later used when
executing the model.
The Web Portal is single page application which allows unauthenticated users
to browse and execute available models. Authenticated users can use the portal
to manage their published models. The execution requires utilising the per-
model metadata (created by the SDK during publishing) to generate the UI
dynamically for each model.
feather’s back end associated database, provides server-side functionality via
a REST API. Both the SDK and the Web Portal talk directly with this service
(for authentication, data validation, etc) to perform all actions on the
feather platform.
The model runner is an AWS Lambda image that is dynamically created from a
Base Image for each model + dependencies type. The runner is loaded as needed
to execute an MDs model. During execution, the image is loaded and executed by
the Lambda runtime in a sandbox environment for safe execution of user-
provided code.

###  4.1 SDK

This component is a client-facing Python library that is publicly available.
The SDK implements feather’s component APIs which allows MDs to quickly
share/deploy (multi-step) models. The SDK is a core component of feather, as
it is responsible for gathering rich metadata about the model, its stages and
its input and output bindings. It is additionally responsible for publishing
the model online. The gathered information is later used when executing the
model.

Fundamentally, the Python SDK allows MDs to declaratively define the desired
inputs of their model with an object based component API. An MD will define a
function for each step, and within each function, will define the components
they wish to be rendered on a web-page. Each of these sequential functions
will receive the input that an MC has provided via the interface.
Additionally, the components also dictate the type of input that is expected
from an MC. Knowing these types enables us to use the code defined by the SDK
to create an API with input type definitions that can be programmatically
executed.

Consider the VQG example listed above. Here, the MD will specify 3 functions.
In the first function, the MD can use a File.Upload component to accept a
specified number of image files (e.g. File.Upload(max=5, accept=[".jpg",
".png"]). This component will be rendered to a webpage. The MC then interacts
with the component by uploading up to 5 image files. These files are now sent
as input to the second function - accessible by the code the MD has written.
In the second function, the MD will consume these images and run an object
detector model on them. The object detector outputs a set of detected_objects
in the image. The MD can now specify an Image.WithSelectMulti(images:
List[np.array], detected_objects: List[List[string]], max=2) component to
render a component which shows the N images alongside the n’th relevant
sublist from detected_objects. Once rendered, the MC can then select up to 2
detected objects per image. The selected objects are then sent to the 3rd
step, where the MD will feed these objects to a language generator, finally
returning the outputs with an questions = model(images, selected_objects);
Image.View(images: List[array], questions: List[string]) component.

A full example of the components we support thus-far are shown in Appendix A.
Now that we have motivated how users interact with the SDK, we discuss how we
use the component specification to publish a model.

⬇

1{"steps": [

2 {

3 "name": "upload_images",

4 "inputs": [

5 {

6 "component": "File.Upload",

7 "props": {

8 "max_files": 5,

9 "min_files": 1,

10 "title": "Upload images",

11 "types": [

12 ".jpg",

13 ".png"

14 ]

15 },

16 "schema": {...}

17 }

18 ]

19 },

20 {

21 "name": "select_objects",

22 "inputs": [

23 {

24 "component": "Image.WithSelectMulti",

25 "props": {...},

26 "schema": {

27 "images": [

28 {

29 "attributes": [

30 {

31 "item": "string",

32 "selected": "bool"

33 }

34 ],

35 "data": "b64",

36 "name": "string"

37 }

38 ]

39 }

40 }

41 ]

42 },

43 {...}

44]}

Listing 1: Example JSON metadata produced by the feather SDK. In the first
step, we have a ‘File.Upload’ component. The ‘props’ attribute contains meta-
information that the API and front-end will enforce. This information either
comes from default values, or are specified by the MD as parameters for a
component they use via the SDK. The ‘schema’ attribute is the expected return
type of that component. For the ‘Image.WithSelectMulti’ component, we expect
to recevie an object called ‘images’. Each image in images has a base64 string
and filename assoicated to it, alongside an array of ‘attributes’ which
indicates the items that have been selected by the MC. {…} indicates
information omitted for space reasons.

###  4.2 Metadata

The SDK generates JSON which contains the metadata of the MD’s model. The
metadata includes, for each model state/step, the inputs and outputs types for
each step, alongside component-specific configurations (e.g. number of files
required for a ‘File.Upload’ input). With the exception of the first step, the
actual input and output data is dynamically communicated between the SDK and
interface and thus not included in the metadata. Example metadata can be seen
in Listing LABEL:lst:metadata. The SDK captures model metadata about a model’s
inputs and outputs via Pythons’s object introspection coupled with the
strongly typed feather components defined in the SDK. The metadata captured is
then used to generate the interactive UI for each input and output, as well as
for data validation on the server side during model execution.

###  4.3 Publishing

Publishing is the process of uploading a model to the feather service, making
it available in a user’s library and for cloud based execution. An MD
publishes their model using the feather SDK, which communicates with the
feather service transparently. The following steps are executing during a
publish:

  1. 1.

The SDK begins running the model locally at the first step. As the model
executes, the metadata is generated for each step.

  2. 2.

The SDK retrieves a publishing token from the feather service. This step both
validates the user’s credentials and registers the model and model version if
required.

  3. 3.

The SDK uploads the metadata JSON and the list of binary files to upload. The
binary files are any files needed to run the model (eg. weights, data files,
etc…). For each binary file the service returns a signed AWS S3 upload URL.

  4. 4.

The SDK uploads each binary file to the provided upload URL

  5. 5.

The SDK informs the feather service that upload is complete. The service
validates each file against the metadata, and then transfers the model and
binary files from the staging to the published storage.

###  4.4 Service

The feather service runs as an AWS ECS container and provides support for user
and model management, model publishing, as well as model execution. This small
Go service exposes a REST API that is used by the Python SDK during publishing
and by the feather web app during model execution. The bulk of the service
comprises validation code for both the publishing and the execution path. It
is vital that all code is validated, all dependencies are tracked for the user
uploaded python code, and all inputs are validated against the model metadata.
Without this, the service cannot return precise error information to the MD,
and multiple security vulnerabilities may be exploited.

Model versioning is also performed automatically by the service. As the MD
publishes their model, the service automatically creates new versions (based
on a ‘name’ parameter the MD specifies during the publishing process) and
preserves the previous version and all uploaded artifacts. This provides a
rudimentary version control for MDs with simple roll-back and tagging. The MD
can promote a specific version to the the live version visible by MCs while
continuing to iterate on the model without fear of breaking anything. The
versioning system is built on the fact that all resources published by MDs are
immutable.

###  4.5 Running the model

Once a model has been published to the feather service, it can be executed via
the feather web app. On the back-end, execution happens in an AWS Lambda in a
security sandbox, as executing the model involves executing user provided
Python code (which was uploaded during the publish phase).

In most cases, executing a multi-step model requires human interaction. Thus
it cannot be achieved in one-shot. Hence we design the system such that each
step in the model defines its inputs and outputs. Inputs are provided by the
user, the model runs, and then outputs are returned. There is no requirement
to execute steps in order or straight away; each step runs as a completely new
AWS Lambda instance relying solely on its inputs & compiled-in dependencies to
function. In fact, this is exactly how feather supports API execution of
models. Since the data transferred to and from the front-end calls an
underlying API, we can simply expose this API to end users.

Figure 3 further details how our front-end interacts with users and the SDK.
To be explicit, the front-end is where MCs will typically interact with the
model (though they may also use the API). An example UI can be seen in Figure
1. To render this UI, we require a method which maps the components specified
by the MD to web components. We achieve this by receiving the metadata from
feather’s back-end. As mentioned in Section 4.2, the metadata contains an
object which contains the components required for each step. Each component in
each step additionally has metadata associated with it (e.g. ‘max: 5’ for a
File.Upload component). Our front-end loops over each step object in the
metadata, and then loops over the components in each step, rendering each in
the order specified. Once a user finishes interacting with a step, the data
they enter is submitted and subsequently executed by the feather service.

Figure 3: Sequence diagram for a multi-step model execution highlighting how
user interaction is involved after each step.

##  5 Areas for Improvement and Extensions

In this section we discuss the shortcomings of our SDK as a whole. We provide
details on how these shortcomings can be mitigated. Additionally, we outline
extensions related to the SDK that could provide desired features.

###  5.1 Dependencies

Through the Python code, an MD can import any package their model needs. The
set of all directly and indirectly imported packages comprise the code
dependencies of the model. After publishing, the MDs code is uploaded to
feather’s backend and needs to be able to run successfully in an AWS Lambda.
As such the execution environment needs to contain the correct packages as
well as versions. The current implementation of feather uses a baked Model
Runner Lambda Image constructed manually to include a number of common Python
packages. During model creation, the MD must only use the set of packages
feather supports - although during our initial release, we often updated our
image to include any new requested packages.

This is obviously not ideal and a better approach is to scan the packages used
by a model during the publishing phase, subsequently uploading the dependency
list and versions as part of the model metadata. The feather service could
then maintain a registry of AWS Images, all created dynamically. Upon
publishing a model, we could hash the package dependencies, and then look in
the registry for a matching Execution Image. If one is found, then it can be
used for the model any time it’s executed. If one is not found, then once
could be created dynamically and added to the registry.

The act of baking the dependencies into the Lambda image is to avoid
downloading and installing anything during step execution. Avoiding this
allows feather to execute a step in about 1 second.

###  5.2 GPU Inference

A worthwhile improvement is the support for GPUs during model
execution/inference. The initial implementation of the feather model runner
relied on executing Docker Containers on AWS Lambdas. Disregarding financial
cost, there is technically nothing stopping a model runner using GPU Instances
which would make inference much faster for large models. We envision that
feather would support both CPU and GPU model runners, and allow MDs to specify
at model publishing time via the SDK, what execution profile to use: low,
medium or high performance; with high performance mapping to GPUs. This would
then be factored into any future pricing model when executing the models.

###  5.3 Richer Model Definitions

Currently, models which are defined by our SDK can only be executed in a
linear fashion for the number of steps that have been defined. This prevents
programs that may want to conditionally execute a model-step, or those that
run a model-step recursively. One example may be a multi-step image in-
painting model where an MC in-paints a background before moving on to in-paint
the foreground. Here, the user may want to iteratively regenerate the
background. Once they are satisfied, the conditional branch the MD specified
will allow them start generating the foreground.

Enabling this may be achieved in multiple ways. We could provide a flowchart-
like visual interface for MDs to create the execution logic of each step.
Alternatively we can we could introduce new types of model steps: a
conditional step which switches between different functions based on the
input, and a recursive step which either allows the user to specify either the
number of iterations, or a break condition.

###  5.4 Fine-tuning as a Service

A further extension to the SDK can enable automatic fine-tuning of a base
model. In this example, the MD can specify the code to continue training their
model alongside a schema of accepted data. feather’s UI/API endpoint can then
accept training data from the MC in the format of the defined schema. The
model runner can then generate a new fine-tuned model by training the base
model against the provided dataset.

##  6 Conclusion

In this paper we introduced feather: an SDK that allows model developers to
declaratively share and deploy their models. This was motivated by the lack of
reproducibility in machine learning, and the pragmatic difficulties of a model
developer exposing their model for easy inference. We outlined the
implementation details of our SDK, and how the deployed models may be executed
either via a UI or an API. Finally, we discussed additional improvements that
could be made to the SDK.

## References

  * Abid et al. (2019) Abid, A., Abdalla, A., Abid, A., Khan, D., Alfozan, A., and Zou, J.  Gradio: Hassle-Free Sharing and Testing of ML Models in the Wild.  6 2019.  doi: 10.48550/arxiv.1906.02569.  URL https://arxiv.org/abs/1906.02569v1.
  * Biewald (2020) Biewald, L.  Experiment Tracking with Weights and Biases, 2020.  URL https://www.wandb.com/.
  * Christiano et al. (2017) Christiano, P. F., Leike, J., Brown, T. B., Martic, M., Legg, S., and Amodei, D.  Deep reinforcement learning from human preferences.  _Advances in Neural Information Processing Systems_ , 2017-December:4300–4308, 6 2017.  ISSN 10495258.  doi: 10.48550/arxiv.1706.03741.  URL https://arxiv.org/abs/1706.03741v3.
  * Jansson & Firshman (2021) Jansson, A. and Firshman, B.  Run open-source models with a cloud API, 2021.  URL https://replicate.com/.
  * Jiang et al. (2022) Jiang, Y., Yang, S., Qju, H., Wu, W., Loy, C. C., and Liu, Z.  Text2Human: Text-Driven Controllable Human Image Generation.  _ACM Transactions on Graphics_ , 41(4):2022, 5 2022.  ISSN 15577368.  doi: 10.48550/arxiv.2205.15996.  URL https://arxiv.org/abs/2205.15996v1.
  * Ng et al. (2020) Ng, E. G., Pang, B., Sharma, P., and Soricut, R.  Understanding Guided Image Captioning Performance across Domains.  _CoNLL 2021 - 25th Conference on Computational Natural Language Learning, Proceedings_ , pp. 183–193, 12 2020.  doi: 10.48550/arxiv.2012.02339.  URL https://arxiv.org/abs/2012.02339v3.
  * Paszke et al. (2019) Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S.  PyTorch: An Imperative Style, High-Performance Deep Learning Library.  In _Advances in Neural Information Processing Systems 32_ , pp. 8024–8035. Curran Associates, Inc., 2019.
  * Treuille & Teixeira (2018) Treuille, A. and Teixeira, T.  Streamlit • the fastest way to build and share data apps, 2018.  URL https://streamlit.io/.
  * Vedd et al. (2021) Vedd, N., Wang, Z., Rei, M., Miao, Y., and Specia, L.  Guiding Visual Question Generation.  _NAACL 2022 - 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Proceedings of the Conference_ , pp. 1640–1654, 10 2021.  doi: 10.48550/arxiv.2110.08226.  URL https://arxiv.org/abs/2110.08226v3.
  * Wolf et al. (2020) Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, A., Cistac, P., Rault, T., Louf, R., Funtowicz, M., Davison, J., Shleifer, S., von Platen, P., Ma, C., Jernite, Y., Plu, J., Xu, C., Le Scao, T., Gugger, S., Drame, M., Lhoest, Q., and Rush, A.  Transformers: State-of-the-Art Natural Language Processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pp. 38–45, Online, 10 2020\. Association for Computational Linguistics.  doi: 10.18653/v1/2020.emnlp-demos.6.  URL https://aclanthology.org/2020.emnlp-demos.6.

##  Appendix A feather’s component API

The SDK exposes a Object Based Component API. Components allow MCs to
declaratively define what types of data they are working with, along with easy
semantics for controlling the UI behaviour for each component. Each Component
in the SDK maps to UI controls, which allows models created through the
feather SDK to be interacted with both programatically (via Python) or
visually via the Web Portal.

Below are the components that are currently supported by feather:

⬇

class File

def Upload()

def Download()

class Text

def In()

def View()

class List

def SelectOne()

def SelectMulti()

class Image

def WithSelectOne()

def WithSelectMulti()

def WithTextIn()

def View()

class Document

def WithTextIn()

def View()