Fast and interpretable Support Vector Classification based on the
  truncated ANOVA decomposition
Kseniya Akhalaya Franziska Nestler Daniel Potts
Support Vector Machines (SVMs) are an important tool for performing
classification on scattered data, where one usually has to deal with many data
points in high-dimensional spaces. We propose solving SVMs in primal form using
feature maps based on trigonometric functions or wavelets. In small dimensional
settings the Fast Fourier Transform (FFT) and related methods are a powerful
tool in order to deal with the considered basis functions. For growing
dimensions the classical FFT-based methods become inefficient due to the curse
of dimensionality. Therefore, we restrict ourselves to multivariate basis
functions, each one of them depends only on a small number of dimensions. This
is motivated by the well-known sparsity of effects and recent results regarding
the reconstruction of functions from scattered data in terms of truncated
analysis of variance (ANOVA) decomposition, which makes the resulting model
even interpretable in terms of importance of the features as well as their
couplings. The usage of small superposition dimensions has the consequence that
the computational effort no longer grows exponentially but only polynomially
with respect to the dimension. In order to enforce sparsity regarding the basis
coefficients, we use the frequently applied $\ell_2$-norm and, in addition,
$\ell_1$-norm regularization. The found classifying function, which is the
linear combination of basis functions, and its variance can then be analyzed in
terms of the classical ANOVA decomposition of functions. Based on numerical
examples we show that we are able to recover the signum of a function that
perfectly fits our model assumptions. We obtain better results with
$\ell_1$-norm regularization, both in terms of accuracy and clarity of
interpretability.