We propose two algorithms for boosting random Fourier feature models for
approximating high-dimensional functions. These methods utilize the classical
and generalized analysis of variance (ANOVA) decomposition to learn low-order
functions, where there are few interactions between the variables. Our
algorithms are able to find an index set of important input variables and
variable interactions reliably. Furthermore, we generalize already existing
random Fourier feature models to an ANOVA setting, where terms of different
order can be used. Our algorithms have the advantage of interpretability,
meaning that the influence of every input variable is known in the learned
model, even for dependent input variables. We give theoretical as well as
numerical results that our algorithms perform well for sensitivity analysis.
The ANOVA-boosting step reduces the approximation error of existing methods
significantly.

提出了两种算法，用于提升随机傅里叶特征模型以近似高维函数，这些方法利用经典的方差分析和广义方差分析（ANOVA）分解学习低阶函数，其中变量之间的相互作用较少。算法能够可靠地找到重要的输入变量和变量交互的索引集，还将已有的随机傅里叶特征模型推广到 ANOVA 设置，可以使用不同阶数的项。算法具有解释性的优势，即可以了解到学习模型中每个输入变量的影响，甚至对于相关的输入变量。我们提供了理论和数值结果，证明了算法在敏感性分析方面的良好性能。ANOVA 增强步骤大大降低了现有方法的逼近误差。

ANOVA-boosting for 随机傅里叶特征

ANOVA-boosting for Random Fourier Features

In this paper we consider the numerical solution to the soft-margin support
vector machine optimization problem. This problem is typically solved using the
SMO algorithm, given the high computational complexity of traditional
optimization algorithms when dealing with large-scale kernel matrices. In this
work, we propose employing an NFFT-accelerated matrix-vector product using an
ANOVA decomposition for the feature space that is used within an interior point
method for the overall optimization problem. As this method requires the
solution of a linear system of saddle point form we suggest a preconditioning
approach that is based on low-rank approximations of the kernel matrix together
with a Krylov subspace solver. We compare the accuracy of the ANOVA-based
kernel with the default LIBSVM implementation. We investigate the performance
of the different preconditioners as well as the accuracy of the ANOVA kernel on
several large-scale datasets.

本文研究软间隔支持向量机优化问题的数值解，通过使用 NFFT 加速的矩阵向量乘积和 ANOVA 分解特征空间的方法，结合预处理方法和 Krylov 子空间求解器，对线性鞍点形式的线性系统进行求解，比较了 ANOVA 核方法与默认 LIBSVM 实现方法在大规模数据集上的准确性和性能表现。

支持向量机的预条件内点方法利用 ANOVA 分解和 NFFT 基矩阵向量乘法

A Preconditioned Interior Point Method for Support Vector Machines Using  an ANOVA-Decomposition and NFFT-Based Matrix-Vector Products

This paper makes the case for using Shapley value to quantify the importance
of random input variables to a function. Alternatives based on the ANOVA
decomposition can run into conceptual and computational problems when the input
variables are dependent. Our main goal here is to show that Shapley value
removes the conceptual problems. We do this with some simple examples where
Shapley value leads to intuitively reasonable nearly closed form values.

本文介绍了使用 Shapley 值来量化函数中随机输入变量的重要性，并探讨了基于 ANOVA 分解的替代方案在输入变量存在相关性时存在的概念和计算问题。通过一些简单的示例，我们说明 Shapley 值可以消除这些问题并产生直观合理的闭式数值。