Learning from Small Samples: Transformation-Invariant SVMs with
  Composition and Locality at Multiple Scales
  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.
