Learning from Few Samples: Transformation-Invariant SVMs with Composition and Locality at Multiple Scales
Authors: Tao Liu
Panganamala Kumar
Ruida Zhou
Xi Liu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Support-Vector Machines
Kernel Methods
Learning from Few Samples

Abstract: Motivated by the problem of learning with small sample sizes, 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 \textit{maximum} similarity over a group of transformations are not generally positive definite. Perhaps it is for this reason that they have not been studied theoretically. We address this lacuna and show that positive definiteness indeed holds \textit{with high probability} for kernels based on the maximum similarity in the small training sample set regime of interest, and that they do yield the best results in that regime. We also show how additional properties such as their ability to incorporate local features at multiple spatial scales, e.g., as done in CNNs through max pooling, and to provide the benefits of composition through the architecture of multiple layers, 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 benchmarks for small sample sizes.

Learning from Few Samples: Transformation-lnvariall SVMs with Composition and Locality at Multiple Scales
Tao Liu', P. R. Kumar', Ruida Zhou', Xi Liu Texas A&M University, College Station, TX, USA Applied Machine Learning, Facebook AI, Menlo Park, CA, USA (tliu, prk, ruida]@tamu. Eda, Allu1meta.ccom com
Abstract
Motivated by the problem of learning with small sample sizes, 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 maximum similarity over a group of transformations are not generally positive definite. Perhaps it is for this reason that they have not been studied theoretically. We address this lacuna and show that positive definiteness indeed holds with high probability for kernels based on the maximum similarity in the small training sample set regime of interest, and that they do yield the best results in that regime. We also show how additional properties such as their ability to incorporate local features at multiple spatial scales, e.g., done in CNNs through max pooling, and to provide the benefits of composition through the architecture of multiple layers, can also be embedded widely available image sets that the
into SVMs. We verify through experiments resulting SVMs do provide superior accuracy in comparison to well-established deep neural network benchmarks for small sample sizes.
1 Introduction
With the goal of learning when the number of training samples is small, and motivated by the success of CNNs [35,31] 31], 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 shifted to the left. Similarly, it is also rotation-invaria More generally, given 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 29 6 where several transformations of each training sample are added to the training set. When applying SVMs on this augmented training set, corre- sponds to a kernel that defines the similarity between two vectors X1 and X₂ as the average similarity between X2 and all transformations of X2. However the average also includes transformations that maximally dissimilar, and we show that it leads to poor margins and poor classification results. More appealing is to construct kernel that defines similarity as the maximum similarity between Xi and all transformations of X2. We show that this kernel is positive definite with high probability in the small sample size regime of interest to us, under a probabilistic model for features. We verify this property widely available datasets and show that the improvement obtained by endowing SVMs with this transformation invariance yields considerably better test accuracy.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Another important domain property for image recognition is the "locality" of features, e.g., an edge depends only on a sharp gradient between neighboring pixels. 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 77. We show how one can iteratively introduce multiple layers into SVMs 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 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; referred SVMs provide significant
to transformed datasets in the sequel. The mansformationninvariii 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 17 is increased, respectively, from the figures of 68. 15,333%/83 3...0000911.... 1.33% reported by the CNNs optimized over architectures and dimensions [0] to, respectively, 81.55%/89 2/%3%% 1%. Similar improvements are also obtained in the EMNIST Letters 4 and Transformed MNIST datasets. Computational results reported here are for small datasets, handled efficiently by LIBSVM 2
1.1 Background
In the early 2000s, SVMs were one of the most effective methods for image classification [1]]. They had a firm theoretical foundation of margin maximization [32 I that is especially important in high dimensions. and a kernel method to make nigh-dimensional computation tractable. However, with the advent of CNNs and the enhanced computing power of GPUs, SVMs were replaced in image classification. One reason was that CNNs were able to incorporate prior knowledge. The pioneering paper (35] emphasizes 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- propppropagttion networks provide a way of specifying such knowledge by imposing constraints both on the architecture 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 a hierarchical structure with ihifttinvariant feature detectors." Indeed, CNNs have successfully incorporated several important characteristics of images. One, mentioned above (called shift- hhitt-invariance). is translational invariance, which is exploited by the constancy, i.c., location independence, of the convolution matrices. A second is locality. For example, an "cdge" 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 three properties are captured in modern CNNs through the "pooling" operation the (e + 1)-th layer, where the features of the ε-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 (ReL.s)) permits composition, enhances expressivity for a given number of parameters, and reduces the number needed for accurate approximations
Generally, neural networks have become larger over time with the number of parameters ranging into hundreds of millions, concomitantly also data-hungry and therefore inapplicable in applications where data is expensive or scarce, e.g., medical data [20]. For these reasons, there is an interest in methodologies for learning efficiently from very few samples, which is the focus of this paper.
1.2
Related Work
There are mainly two sets of studies: transformation cannformaaioonnnvaaiant kernels and on local correlations.
Transformation-Inaaiin Kernels. There are two major routes to explore transformation invariant kernels [26] [6]. The most widely used is based on Haarrintegration kernels, called "average-fii fit"
Although trivially positive definite, they appear to produce poor results in our testing (Section 4 Mairal et al.
kernels in this paper, which average over a transformation group 227 12
II
23
21 22
21 reported some good results when a large dataset is available for pre-training bottom network
layers unsupervised (24), but our focus is data-scarce situations where such large dataset is

---

available. This paper concentrates on "best-fit" kernels, which are based on the maximum similarity over transformations. "Jittering kernels" g calculate the minimum distance between one sample and all jittered forms of another sample, analogous to this paper. Instead of measuring the minimum distance between samples, tangent distance kernels [0 H
use linear approximation to measure the minimum distance between sets generated by the transformation group, which can only guarantee local invariance. comparison, our "best-fit" kernel is defined as the maximum inner product between one sample and all transformed forms of another sample, which enjoys global invariance and transformations (e.g., scaling transformations). Although "besstfit" kernels enjoy a good performance, they not guaranteed to be positive definite, thus the global optimality of the SVM solution cannot be guaranteed theoretically. We address this lacuna and show that positive definiteness indeed holds with high probability in the small training sample set regime for the "best-fit" kernel. Additionally, we show that locality at multiple scales can further improve the performance of "best-fit" kernels. We note that there treat an indefinite kernel matrix as a noisy observation of some unknown positive semidefinite matrix 3 36., but goal is to analyze conditions that make the "best-fit" kernel positive definite.
differs from jittering kernels for eee---ooo----eeeee
also some works that
Local Correlations. Since "local correlations," i.e., dependencies between nearby pixels, are more pronounced than long-range correlations in natural images, Scholkopf et al. [ 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 two-layer local correlation to multilayer architectures by introducing further compositions, which gives the flcxibility to consider the locality at multiple spatial scales. We also analyze the corresponding time and space complexity of multilayer architectures.
2 Kernels with Transformational Invariance
To fix notation, let S = {(Xx( M,).,...................... (X yn)} set of n labeled samples with m-ddimensional feature vectors X; = (x(") ....,, ((m")²" E EX C RT and labels y/ ).
2.1 Transformation Groups and Transformation-Ilvariie
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 vectors. Let G be transformation group that acts on X, i.c., for all S, U G: (i) I maps X into X; (ii) the identity map 1 G: (iii) ST G; (iv) (ST)U = STTU); (v) there is an inverse 7' E G with 7T = T-T = 1.
We start with a base kernel Kbose X x X R that satisfies the following properties:
1. Symmetry, i.e., Kbase(X (X,, X,) = Koase Xi):
2. Positive definiteness, i.e., positive semi-definiteness of its Gram matrix:
Σi=1 Σ/=1 a,ja,KK (X,, X,) 2 0 for all a1..... an R;
3. Khase XT) = Krnse (X,, T X;), VT EG
Define the kernel with the "best-fit" transformation over by Kg,best, base (X,, X,) = sup Kbase TEg
(1)
Lemma 1. Kg,best, base is a symmetric kernel that is also cunsformation-invariaa over the group G. i.e., Kg,best, base (T X2, X3)= Kg basee (X,, Xz).
Proof. The symmetry follows since
bastest X,, Xj)= = sup K Kbase (,X,, Xj) = sup K Kbase (X,, xx)) TES
TES
sup Krase (T X Xz)
sup Koase (T Xi, Kg.best,base (X Xi). T-
TEG The transformational invariance follows since
Ke.best,base (TX,, (T),, = sup Kbase (STX,, = sup Kbase Kbase seg
UT leg
= sup Krase (U Xy)= = Kg best bese Xy), Veg
3

---

The Translation Group: Of particular interest in image classification is the group of transla-
tions, a subgroup of the group of transformations. Let X; {x! P [mil. [m²]] denote a two-dimensional my x m2 array of pixels, with m = m,m.. Let TraX; ==
(x, (X((p-r) mod (q-ss)) mod me). :p [mi]. q E [ma]] denote the transformation that translates the array by pixels in the z-direction, and by pixels in the y-direction. The translation group is Gtrons (Tio r [mi], [ma]]. For notational simplicity, we will denote the resulting kernel Keetand by KTT, best
2.2 Positive Definiteness of Translation-Invarian 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 be positive definite to have provable guarantees of performance.
best satisfies property (i) established in Lemma I Concerning property (ii) though, in general, KTI,best is an indefinite kernel. We now show that when the base kernel is normalized linear kernel, Kisnear (X,, X3) == X Xj, then it is indeed positive definite in the small sample regime of interest under probabilistic model for dependent features.
Assumption 1. Suppose that samples (X1, X2,..., X,) are i..dd. with X; (x.") x ....,x!!!) x(") being a normal random vector with X; ~ (0, Σ), Vi E [n]. Suppose also that |x|l2/||All> (Inm) " /2 for some (0, 1], where À ==
is comprised of the eigenvalues of 2. Note that x(")) may be correlated with x! for p $.
Example When = In iee, x(() ~ N(O, 1), Vp E [m], the condition ||Ale//|||| Z (Ium) 1/2 /2 holds trivially since |Aall2 /m and |A = 1. We note that for independent features, we can relax the normality (Assumption]] to sub-Gaussianity.
Theorem 1. Let
1 (TX,)"xX
STIIbestt,iieee (x, sup TEGerans m
be the best-fit translation invariant kernel with the base kernel chosen as the normalized linear kernel. Under Assumption if n S ||Al|s
then KTI best is a positive definite kernel with
2|]a||a(In 4 probability approaching one, as m +
Outline of proof. We briefly explain ideas behind the proof, with details presented in Appendix For brevity, we denote KTI Nese [X Xj) and Kiinear (Xt, X2) by KTLØ and Kij, respectively. From Gershgorin's circle theorem 33 every eigenvalue of Ker lies within least one
of the Gershgorin discs D(KrI.i: TT)
{h R | Kri,sa| S ri), where := Ejzs [Kr,,jl- Hence if KTI, > Ejps [Kriij Vi, then KrI is positive definite kernel. Accordingly. we study tail bound Ejts [Krssyl and upper bound on KrI,i respectiell. to complete the proof. O
Note that |||l1 < /mil|ila for an m-length vector X, which implies that Ö(Vm).
We now show that positive definiteness in the small sample regime also holds for the polynomial kernels which are of importance in practice:
Kpoty (X,, X3) (1 _xTx,)x for 2 0 and d e N.
m
Theorem 2. For any 7 R., and d N, the translation-imvarian kernels,
KTI KTt.best.poty (X,, (x,x =
sup (1+ 2 (+X.) X,
(3)
TeGrvans m
are positive definite with probability approaching one as m - 400, under Assumption 7 when ||||| S 1, and n S [|l]]
(l) 44c

---

Table The value of up which the kernel is positive definite. Positive definiteness continues to hold for moderate sample sizes, indicating that the theorem is conservative.
Datasets
KTI linea
KTI bestbost.pol
Original MNIST
R 45
2: 375
EMNIST
R2 35
23 395
Translated MNIST
455
R3 15000
Proof. Note that a < 1 can be satisfied simply by dividing all entries of the X,s by v M The detailed proof is presented in Appendix C
Remark. Since Gershgorin's 's circle theorem is a conservative bound on the eigenvalues of a matrix, the bound n Ō(vm) the number of samples for positive definiteness is also conservative. In practice, positive definiteness of KTI,best.Ke linerr holds for larger n. Even more usefully. Ky Kyy.best.po pest. is positive definite for a much larger range of n than KTI beat leaerr reported in Table] [
2.3
Comparison with the Average-Fit Kernel and Data Augmentation
2.3.1
Average-Fit Kernel
In 12 the following "average-fit kernel" kernel is considered
Rog (X, X,) =
Klinear (T X;, Xz),
(4)
TEC
which seeks the "average" fit over all transformations. We denote by KTI.ang.lincar Xx) for short. It is trivially invariant with respect to the transformations in 9 and positive definite. However, it is not really a desirable choice for translations when the base kernel is the linear kernel. Note that Geronal Ereg. TX, a(1, 1)), where = 1 [pt(m.))e((ma) ((1-1) is the average brightness level of X.. Therefore Kvr,avg, /inear (X;, Xx) mx (Avg brightness level of X;) x (Avg brightness level of X,). The kernel solely depends on the average brightness levels of the samples, basically blurring out all details in the samples. In the case of rotational invariance, depends only on the average brightness along each concentric circumference. As expected, it produces very poor results, as seen in the experimental results Section 4
2.3.2 Data Augmentation
Data augmentation is a popular approach to learn how to recognize translated images. It augments the dataset by creating several translated copies of the existing samples. (A special case is the virtual support vectors method which augments the data with transformations of the support vectors and retrains (26].) SVM with kernel Khose applied to the augmented data is equivalent to employing the average-fit kernel as (4). Consider the case where the augmented data consists of all translates of each image. The resulting dual problem for SVM margin maximization (5 is:
Σ
T2X,) NE.. K.T.WiMiKKaae Krase (TiX,, (TXxi,T2X)) + E>ET
max-
1.1.7i.72
1.7
s.t. AO. 2 0, Vi [n], E Gtrans;
EA.Ty= =
1.T
The corresponding classifier is sign Sig((E,, Mi Kbase (TX,, X) + b*), where X" is the optimal dual variable and b* y, -E.r Ki (TX,, Xy), for any j and T" satisfying Aj.r. > 0. When data augmentation is implemented, i.e., 1Stranal = 1, we use X as shorthand for 2 As shown in Theorem 4.1 (18), this is simply the dual problem for the SVM with KTI, avg.ev baser and E; KKKT,,ag.bbs.. (X;, X,) ExTEc Krase (T Xj) Hence data augmentation is mathematically equivalent kernel with average similarity over all transformations. This yields poor classifier since it only leverages the average brightness level of an image.
A simple example illustrates superiority of KTI be st, linear over KTI, ong, or data augmentation.
5

---

Decinion Gounday under enperroratoon Inrrrnnatioon 40
Originel:
Originel
6
7
Augriented
5
4
8
9
Secieon botrodurs under
50
50
50
50
50
12
(b) Translated MNIST (T-MNIST)
2
1
3
J
1
50
50
50
50
5
(c) Rotated MNIST (R-MNIST)
X(1)
(a)
Figure 1: (a) The kernel best, best, produces the piecewise linear separatrix shown in red. yields larger margin than the blue linear separatrix, i.e., decision boundary, that data augmentation and KTr,aw, anng yield; (b) & (c) Transformed MNIST with random translation/rotation and Gaussian noise (p 0, 0.1).
Example 2. Consider special case of the translation group with m1 = 2 and m2 1. Consider training set with just two samples X1 = (1,2) 2) and X2 = (5, 2). shown in red in Figure 7 Note that translation in the image space is right shift of vector elements. (So translation of X1 (1, yields the augmented datum X3 = (2, 1) in this two-dimensional context because of wraparound.) Two new samples X3 = (2, 1) and X4 = (2, 5) are therefore generated through data augmentation, shown in green. The decision boundary of the base kernel with augmented data (equivalent to the average-fit kernel KTI, (vg) ) shown by the blue solid line in Figure 7 Note that the linear decision depends solely on the brightness level X + (()).
boundary x() (2)
However, the decision boundary of the best-fit kernel KTI, bistter (X,,)) supregvaas 2 (TX,) is piecewise linear due to the "sup" operation. Each piece fo- cuses only the half of the samples that are the same side of the symmetry axis (black dashed line), leading to the red piecewise linear separatrix with a larger margin. (The red margin is 2/10 which is larger than the blue margin V2.) The best-fit kernels thereby maximize the margin over the larger class of piecewise linear separatrices by exploiting the invariances. Even when data augmentation is used, it only produces linear separatrices and thus still has smaller margins. Benefits will even more pronounced higher dimensions. For other kernels (e.g-, polynomial kernels), the shape of the decision boundary will be altered correspondingly (e.g., piecewise polynomial), but the TI best-fit ft kernel will still provide a larger margin.
2.4 Rotation-Invariant Kernels
To mathematically treat rotation-invarianl kernels, consider images that are circular, of radius r, with each concentric annulus from radius (p-1)r to pr. for E [m.). comprised of m2 pixels spanning the sectors [2km m22, 2(k + 1)t/m2) for k = O. m2 1. Denote the element in the p-th annulus and q-th sector as "pixel" x(n-)), and define the rotation group Grotate := {Ti, T2. ... T
where X ((natt'), The rotation-invaria (RI) best-fit kernel is
KRI best
base base (X,,
sup TEGrotate
Kbase (T X3)).
Lemma Under Assumption 7. the rotational invariant kernel K RI boll. positive definite with probability approaching one as m - +0c, under the same conditions as in Theorem
In Section 4 report the large performance gain of KRJ Reebbett.poly

---

3 Incorporating Locality at Multiple Spatial Scales
To better illustrate the property of "locality" and its incorporation into SVMs, consider the simple context of a polynomial kernel and a one-dimensional real-valued pixel sequence.
Let us regard the individual pixel values in the sequence tive features at "Layer 0". Consider now "local" feature depending only on the nearby pixels
....,.,".) as the primi-
(x!") (((+), ,, x((tt))) } that can be modeled by a polynomial of degree d1. We refer to k as the locality parameter.
Such local feature is a linear combination of monomials of the form [=== ( (x(()) (x(0) with
-)= (mminettk.m Cj S di where each integer Cj 2 O. This gives rise to kernel
k
t+ X
K (1) L,g
X x + 1)th 1]42.
(5)
p=t
We regard "Layer as comprised of such local features of locality parameter k1, at most kı apart. "Layer 2" allows the composition of local features at Layer 1 that are at most k apart:
ki
g+
E+ly
K
Σ
x x + 1) + 1)d
(6)
g=1
p=t
This can be recursively applied to define deeper kernels with locality at several coarser spatial scales.
The above procedure extends naturally to two-dimensional images (x((2-)) p E [ma]. q E [m²]]- -h
Then the kernel at Layer 1 is simply (Eeer kk EmaT (Eath Eptee x(P-4) x((00) + +1)d + 1)dd, The resulting kernels are always positive definite: Lemma 3. Kg is a positive definite kernel.
Proof. Note that K₃ and K₂ are positive definite kernels, then the following kernels K obtained by Schur products (28). addition, or adding a positive constant elementwise, are still positive
definite kernels: (i) K,j = 1.ij + K22... (ii) K₂ = (K1,)) (K2,,)) f2, (iii) K, = Ki,ij + 7, Va, 2 0, L1, l2 E N, 7 2 0. The kernel K can be obtained by repeatedly employing the above operations with a = 8 = 7 = 1, starting with a base linear kernel which is positive definite with
high probability under the conditions of Theorem 2
L
One difference from CNNs that, for the same input layer, one cannot have multiple output channels. If we design multiple channels with different degrees, then the channel with larger degree will automatically subsume all terms generated by the channel with smaller degree. Therefore, is equivalent to having only one output channel with the largest degree. However, 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 base kernel into transformationninvariann kernels.
Complexity Analysi 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 store only the kernel values from the final layer. 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 between O(n'm m) and O(z²m) based on LIBSVM [2), while space complexity is O(n²). With sufficient memory of order O(n²m). the computations of kernel values can be parallelized so that the time complexity considerably reduced to between O(n2kd) and (n²)d)) where h and d are the locality parameter and the depth, respectively, with kd & m. Note that since our focus is on small sample sizes, the Onn²) complexity is acceptable.
the locality kernel
7

---

Table 2: Original MNIST Dataset and EMNIST Letters Dataset (100, 200, 500 training samples):
Test accuracy of newly proposed methods compared with the original SVM, the tangent distance (TD) nearest neighbors (two-sided), the RI-SVM based on Average Fit, and the best CNN. Based on the same training set, our fine-tuned ResNet achieves similar performance as in [10]
Original MNIST
EMNIST
Letters
Method
100
200
500
100
200
500
Acc/%
Acc/%
Acc/%
Acc/%
Acc/%
Acc/%
L-TI-RI-SVM
81.55
89.23
92.58
44.56
55.18
66.42
TI-RI-SVM
75.10
86.47
93.11
43.16
52.40
67.42
L-TI-SVM
78.86
87.02
91.01
42.51
52.81
64.66
L-RI-SVM
77.96
83.96
89.65
38.39
47.29
59.76
TI-SVM
69.34
82.34
91.00
39.94
48.12
63.52
RI-SVM
73.82
83.60
90.19
38.03
45.02
59.04
L-SVM
75.27
82.11
88.21
37,01
45.08
58.05
SVM
68.16
78.67
87.14
36.65
42.74
56.38
TD (two-sided)
30
73.04
81.68
88.15
37.99
45.31
57.63
RI-SVM (Average-Fit)
68.05
78.81
87.21
36.82
42.41
56.22
Best CNN [10 ResNet
68.33
83.20
91.33
33.82
53.17
57.06
Experimental Evaluation
4.1 Datasets
We evaluate the performance of the methods developed on four datasets:
1. The Original MNIST Dataset 17
2. The EMNIST Letters Dataset 4
3. The Translated MNIST Dataset: Since most generally available datasets appear to have already been centered or otherwise preprocessed, we "uncenter" them to better verify the accuracy improvement of TI kernels. We place the objects in 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 (p 0, a 0.1) to avoid being able accurately center the image by calculating the center-of of-ser. mass. We call the resulting dataset the "Translated dataset". Figure [ shows some samples from different classes of the Translated MNIST dataset.
4. The Rotated MNIST Dataset: We place the original image in the middle of larger canvas and rotate it, with the blank area after rotation filled with Gaussian noise. kernels are not designed
to and cannot distinguish between equivalent elements (e.g., 6 versus 9), and we skip them. Figure c)) displays samples from different classes of the Rotated MNIST datasct.
4.2 Experimental Results and Observations
Table and Figure provide the test accuracy of all methods on the Original and Transformed MNIST Datasets, respectively, while Table shows the test accuracy for the EMNIST Letters Dataset The letters L, TI, and represent Locality at multiple spatial scales, kernels, and kernels, respectively. A combination such as L-TI represents an SVM with both Locality and Translational Invariance. Note that the intended application of our proposed methods is to learn when data is scarce and there is no large database of similar data, which precludes the possibility of pre-training. We provide code at htttps//ggituu.coom///
(997/TI-SMM
For the Original MNIST dataset with 100/200/500 training samples (Table after intro- ducing locality and transformational invariance, the classification accuracy improved from R1t.//9.33... 1..3% reported by the best CNNs optimized over architectures and dimensions [IO]
68.33% 2.088 to //.99 29....9..9...... 1 respectively. The improvements indicate that the original dataset does not center and deskew objects perfectly. Larger improvements can be observed the EMNIST Letters dataset compared with the original SVM, two-sided tangent distance (TD) nearest neighbors 30). RI kernel based on Average-Fit and ResNet. (Since find that the test accuracy of TD-based

---

90
80
Accuracy/%
70
Test Accuracy/8
70
60
50
LSVM
S/M
40
T1-SVM
TD
40
30
30
20
LSVM R15VM
-
9/N
10
10
200
400
600
800
1000
200
400
600
800
1000
Number of Training Samples
Number of Training Samples
(a) Translated MNIST.
(b) Rotated MNIST.
Test accuracy vs. Number of training samples, for Transformed MNIST datasets. L- TI-SVM yields considerable improvement small sizes in the case of translated samples, while, similarly, L-RI-SVM does so in the case of rotated samples.
Figure 2:
nearest neighbors 30 is better than that of TD-based SVMs 15], we only report results of TDDbased nearest neighbors as one of the baselines.) All results are multi-class classification accuracies.
In Figure 2 we present the obtained test accuracy as function of the number of training samples, for two different transformed datasets. Experiments are performed 5 times with mean and standard deviation denoted by the length of the bars around the mean, for 000/300/500/700/100 100000000 training samples respectively. (L-)TI-SVM and (L-)RI-SVA, outperform ResNet in many cases when there 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 Figure 2 Additionally, the test accuracy of the newly proposed methods has 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 significant. Note that the performance improvement of proposed methods comes at the cost of longer computation time. When computation time is critical, we may simply use new single methods, i.e., L-SVM, TI-SVM, and RI-SVM, which enjoy relatively good performance at small cost of additional computation time.
4.3 Details of Experimental Evaluation
With consideration of computational speed and memory space, we utilize two-layer structure as well as قー- -zero padding and a stride of 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 fixed degree (8 in our experiments) to realize the 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 10, which adopts a tree building technique to examine all the possible combinations of layers and corresponding dimensionalities find the optimal CNN architecture. As for the DNN benchmark of the EMNIST Letters and the Transformed MNIST datasets, we select ResNet 14 [5], classic CNN architecture,
DNN benchmark. Plus, for fairness, do not implement data augmentation for any models and train all from scratch.
Note that all experimental results are based on LIBSVM [ and are carried out an Intel Xeon E5-2697A V4 Linux server with a maximum clock rate of 2.6 GHz and a total memory of 512 GB.
5 Concluding Remarks
In this paper, we have developed cunsformattonninvariinn 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 appear to provide significantly 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.
Acknowledgement
This material based upon work by Texas A&M University that is partially supported by the US Army Contracting Command under 1911NF-22-1-013 US Office of Naval Research under N00014-21-I: 2385, 4/21-22 DARES: Army Research Office W91 INF-21--24006, US National Science Foundation under CMMI-203866 The views expressed herein and conclusions contained in this document those of the authors and should not be interpreted as representing the views or official policies, either expressed implied, of the U.S. Army Contracting Command, ONR, ARO, NSF, or the United States Government. The U.S. Government authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
References
[1] Bernhard E Boser, Isabelle M Guyon, and Vladimir N Vapnik. A training algorithm for optimal margin classifiers, In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, pages 144-152, 1992.
[2] Chih-Chung Chang and Chih-Jen Lin. Libsvm: A library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3): 2011.
[3] Jianhui Chen and Jieping Ye. Training svm with indefinite kernels. In Proceedings of the 25th international conference on Machine learning, pages 136-143, 2008
[4] Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. In 2017 International Joint Conference on Neural Networks (ICNN), pages 2921-2926. IEEE, 2017.
[5] Corinna Cortes and Vladimir Vapnik. Support- vector networks. Machine learning, 20(3):273- 297, 1995.
[6] Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V Le. Autoaug- ment: Learning augmentation policies from data. Conference on Computer Vision and Pattern Recognition, 2019.
[7] Ingrid Daubechies, Ronald DeVore, Simon Foucart, Boris Hanin, and Guergana Petrova. Non- linear approximation and (deep) relu networks. Constructive Approximation, pages 1-46, 2021.
[8] Dennis DeCoste and Michael C Burl. Eestortion-invarien recognition via jittered queries. In Proceedings IEEE Conference on Computer Vision and Pattern Recognition. CVPR 2000 (Cat. No. PR00662), volume 1, pages 732-737. IEEE, 2000.
[9] Dennis DeCoste and Bernhard Schölkopf. Training invariant support vector machines. Machine learning, 46( 46(1):166) 161- 2002.
[10] Rhett N D' Souza, Po-Yao Huang, and Fang-Cheng Yeh. Structural analysis and optimization of convolutional neural networks with small sample size. Scientific Reports, 10(1):1-13, Nature Publishing Group, 2020.
[11] Kamaledin Ghiasi-Shirazi, Reza Safabakhsh, and Mostafa Shamsi. Learning translation invariant kernels for classification. Journal of Machine Learning Research, 14)) 2010.
[12] Bernard Haasdonk and Hans Burkhardt. Invariant kernel functions for pattern analysis and machine learning. Machine learning, 68(1):35-61 2007.
[13] Bernard Haasdonk and Daniel Keysers. Tangent distance kernels for support vector machines. In Object recognition supported by user interaction for service robots, volume pages 864-868. IEEE, 2002.
10

---

[14] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. European conference on computer vision, pages 630-645. Springer, 2016.
[16] Fabien Lauer and Gérard Bloch. Incorporating prior knowledge in support vector machines for classification: A review. Neurocomputing, (laiiinnnn....77 71(7-9):157--1599 2008.
[17] Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010.
[18] Zhiyuan Li, Ruosong Wang, Dingli Yu, Simon S Du, Wei Hu, Ruslan Salakhutdinov, and Sanjeev Arora. Enhanced convolutional neural tangent kemnlls. arXiv preprint arXiv: 1911 1. 100809, 2019.
[19] Dengsheng Lu and Qihao Weng. A survey of image classification methods and techniques for improving classification performance. International journal of Remote sensing. 28(5):233 870, 2007.
[20] Andreas Maier.
Will
we
ever
solve
the shortage of data in http:://oovrrddddttssleee..e com/
medical applications?
will- weeerre-eee---ee so www.--oo-eeeeeeeeeeeeeeeeeeeeeee
2020. Accessed: 2022-01-22.
[21] Julien Mairal, Piotr Koniusz, Zaid Harchaoui, and Cordelia Schmid. Convolutional kernel networks. Advances in neural information processing systems. 27, 2014.
[22] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Learning with invariances in random features and kernel models. Conference on Learning Theory, 2021.
[23] Youssef Mroueh, Stephen Voinea, and Tomaso Poggio. Learning with group invariant features: A kernel perspective. Advances in Neural Information Processing Systems, 28, 2015.
[24] Marc' Aurelio Ranzato, Fu Jie Huang, Y-Lan Boureau, and Yann LeCun. Unsupervised learning of invariant feature hierarchies with applications to object recognition. 2007 IEEE conference on computer vision and pattern recognition, pages 1-8. IEEE, 2007.
[25] Bernhard Schölkopf. Patrice Simard, Alex J Smola, and Vladimir Vapnik. Prior knowledge in support vector kernels. In Advances neural information processing systems, pages 640-646, 1998.
[26] Bernhard Schölkopf. Alexander J Smola, Francis Bach, et al. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
[27] Hanns Schulz-Mirbach. Constructing invariant features by averaging techniques. In Proceedings of the 12th IAPR International Conference Pattern Recognition, Vol. 3-Conference C: Signal Processing (Cat. No. 94CH3440-5), volume 2, pages 387-390. IEEE, 1994.
[28] Jssai Schur. Bemerkungen zur theorie der beschränkten bilinearformen mit unendlich vielen veränderlichen. 1911.
[29] Connor Shorten and Taghi M Khoshgoftaar. A survey on image data augmentation for deep learning. Journal of Big Data, 6(1):1-48, 2019.
[30] Patrice Y Simard, Yann A LeCun, John S Denker, and Bernard Victorri. Transformation invariance in pattern recognition craattiionttnggettt distance and tangent propagation. In Neural networks: tricks of the trade, pages 239-274. Springer, 1998.
[31] Mingxing Tan and Quoc Le. Efficientnet: Rethinking model scaling for convolutional neural networks. International Conference on Machine Learning, pages 6105-61 14. PMLR, 2019.
[32] Vladimir N Vapnik. The nature of statistical learning theory. springer, 1995.
[33] Richard Varga. Geršgorin and his circles, volume 36. Springer Science & Business Media, 2010.
11

---

[34] Martin J Wainwright. Cambridge University Press, 2019.
statistics: A non-asympiotic viewpoint, volume 48.
[35] Y. le Cun. Generalization and network design strategies. Connectionism in perspective, 19:143- 155, 1989.
[36] Yiming Ying, Colin Campbell, and Mark Girolami. Analysis of svm with indefinite kernels. Advances in neural information processing systems, 22, 2009.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No]. or [N/A] You are strongly encouraged to include a justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license the code and datasets? [Yes] See Section ??.
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do modify the questions and only the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 2.2 (conserva- tive bound caused by Gershgorin's circle theorem) and Section 4.2 (possibly longer computation time).
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 2.2
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix B and
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] See
https://ittub.com//lul htt.://bb.ooomnnn//9//////// 197//1-SVM
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4.3
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] See Figure
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 4.3
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] See https://github..cm//in 199.//1-99999//S
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
12

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "vS_WIRVwXzG", "reviewer": "Reviewer_gSiY", "summary": "The authors propose a novel approach to incorporate into SVMs several properties seen in CNNs. In a specific way, authors introduce domain knowledge of invariances (i.e. image recognition), maximum similarity on a group of transformation (kernel based), incorporating local features at multiple spatial scales, as well as composition through the architecture of multiple layers. This characteristics are shown in a set of experiments wit the polynomial kernel and the L-TI-RI-SVM (and variants), CNN and ResNet applied into MNIST, EMNIST and translated MNIST.", "questions": "•\tThe manuscript section organization is missing from the introduction, it should be included.\n•\tIs it possible to consider to show results in table 2 in a visual manneer (i.e. figure 2)?\n•\tIs it possible to extend the work on future directions as, per example, other kernels?\n", "limitations": "The authors address the problem and found that polynomial kernels, under certain conditions can address the problem in image recognition. It will be nice to have the code in order to reproduce results and the corresponding architectures.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The core idea of the work is original in the sense of incorporating main characteristics involved in CNNs, into the construction of SVMs. Taking advantage of kernels, authors established the conditions for a symmetric kernel that is positive-definite transformation-invariant (polynomial kernel). The locality at multiple special spaces is introduced as well in the kernel with these characteristics. Figure  2 explains the advantages of the L-TI-SVM and L-RI-SVM in the T-MNIST and R-MINST\n\nWeaknesses: the contribution on the is, at this stage, involved in problems related to image recognition, involved with the structure of pixels (and all the inner related characteristics). It is important to remark that authors use a very well-known dataset; MNIST and some variants. It is also important to consider that other datasets are also used as benchmarks, tackling few shot learning in images. It should be nice to offer a github link in order to reproduce the results.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "REKhb1aAkJD", "reviewer": "Reviewer_wPUn", "summary": "The paper proposes a novel formulation of SVM to tackle the problem of learning in scarce data regime. it is inspired by the properties of CNNs, namely translation invariance and locality at different scales.", "questions": "1/ What is the training and inference time of the proposed method? it could be interesting to add a column mentioning the training time & inference time and the number of parameters when comparing with related works and DL methods.\n\n2/ For the sake of comparison and a better understanding of the formulation of the proposed method, could you make some visualizations of the learned kernel as in CNNs to show the learned filters? (figure 3 in ImageNet Classification with Deep Convolutional\nNeural Networks https://proceedings.neurips.cc/paper/2012/file/c399862d3b9d6b76c8436e924a68c45b-Paper.pdf)", "limitations": "This work doesn't have any negative societal impact.\nThe authors didn't mention the limitations of their works.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The success of CNNs is related to the availability of large-scale data and the development of hardware. Moreover, the properties of CNNs such as compositionality, translation & rotation invariance,  locality, and multi-scale representations have made CNNs successful in a large scope of applications. However, CNN's are data hungrier. In this paper, the authors tackle the problem of learning in a small data regime by reformulating SVMs to take into consideration the translation invariance, locality, and compositional structure properties of CNNs. \nOne of the strengths of the paper is in the modeling of the proposed SVM and the mathematical validations,  including the verification of the satisfactions of the positive-semi definiteness of the proposed kernel.  The claims are well supported and the mathematical variables are well defined which makes the paper easy to follow.\n\nThe methodological part includes two theorems and three lemmas that are validated empirically considering different experimental protocols. However, the experimental part could have included other applications (video, speech, physical data) where the data are rare and tasks (regression, etc) to show the versatility of the methods.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "G0AQDGrFwY1", "reviewer": "Reviewer_R7kt", "summary": "** I thank the reviewers for their answers **\n\nThe paper analysis theoretically the best fit kernel under transformational invariance. Such kernel is not necessarily definite positive. The authors prove some bounds for which it is with hight probability as long as the sample size is small enough.\n\nThe authors also incorporate into the kernel the knowledge of locality.\n\nThis strategy is inspired from the success of deep convolutional neural networks.\n\nTo my understanding, the paper focuses on small samples mainly as a limitation rather than as a specific objective (this is not a critic).\n\nThe experiments confirme the benefit of the method on small samples.", "questions": "I understand that in the experiments L is locality, TI is translational invariance and RI rotational invariance but I think that it would improve readability to introduces the notations.\n\nCould you provide an empirical curve of probability to be positive definite given the sample size, maybe on a syntetic dataset ?\n\nCould you provide std on your experiments. Small samples might be linked to large variance in the experiments.", "limitations": "Some limitations are given in the core of the paper but not specifically addressed.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strengths\nThe paper provides some theoretical and practical elements about the use of such kernels for small samples. They show that even though such kernels are not always positive definite, they can be as such on small samples.\n\n- Weaknesses\nThe paper is a succession of many elements that I found some time difficult to ingest.\nExperiments do show std which might be large on small samples.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept