Pure Interaction Terms for Random-Feature Additive Models

Additive models predict by summing one curve per input feature. A loan model, for example, adds a "debt-to-income" curve to an "age" curve. People can read each curve directly, which is why these models are a standard answer to the accuracy-interpretability trade-off. Recent work replaced the per-feature neural networks of Neural Additive Models with random Fourier features, which are fixed random cosine projections that approximate a smooth kernel. With frozen projections, training becomes a convex linear fit. The resulting curves are smooth, and the parameter count drops sharply. The weakness is that these models are strictly one feature at a time, so they cannot express effects like "high utilization matters only for short credit histories." The obvious fix is to add two-feature terms. Doing so creates an interpretability problem that most of the literature ignores: a pairwise term can quietly absorb part of each feature's own curve. When that happens, both the one-feature plots and the two-feature heatmap stop meaning what a reader assumes.

This note proposes a random-feature interaction model with two properties. Each pairwise term is constrained to contain only what neither single-feature curve can explain; we call such a term pure. And the plotted explanations are provably stable across random draws of the cosine frequencies. Both properties come cheaply from the random-feature construction. Purity reduces to a linear projection in the explicit feature space, which keeps training convex. Stability follows from known kernel-approximation rates, so explanation variability can be predicted and controlled through the number of random features. The deliverable is an interaction model whose pictures can be trusted. We also measure how much accuracy that trust costs.

Core Claim

Gaussian Process Neural Additive Models (GP-NAM) replaces each deep shape network in Neural Additive Models with a Gaussian-kernel Gaussian process approximated by frozen random Fourier features. On FICO it cut learnable parameters from 262,000 to 3,901. On LCD it cut per-epoch training time from 5.5 s on GPU to 50 ms on CPU. The authors name pairwise extensions as future work, but they do not say how to build them. Graph Neural Additive Models with Random Fourier Features (G-NAMRFF) brings the same construction to graphs and is also strictly univariate. Both papers supply our method and motivate the gap. Neither addresses interactions, and neither asks whether explanations depend on the random frequency draw. Once optimization is convex, that draw is the only remaining source of randomness.

Our claim has two parts. First, pairwise random-feature blocks can be purified by orthogonal projection against the main-effect blocks, with negligible loss of accuracy. Purified pair heatmaps then recover planted interactions without leaking main-effect signal, and unpurified ones do not. Second, the distance between explanations fit with two independent frequency draws shrinks at roughly $m^{-1/2}$, where $m$ is the number of random features per block. This gives practitioners a concrete budget: they can choose $m$ to reach a target level of explanation reproducibility.

Mechanism

For a pair of features $(j,k)$ with Gaussian kernels of bandwidths $\sigma_j,\sigma_k$, the product kernel $k_j(x_j,x_j')\,k_k(x_k,x_k')$ is itself a two-dimensional Gaussian kernel. Its random features are therefore $\sqrt{2/m}\cos(\omega x_j + \nu x_k + b)$, with $\omega\sim\mathcal N(0,\sigma_j^{-2})$, $\nu\sim\mathcal N(0,\sigma_k^{-2})$, and $b\sim\mathrm{Uniform}(0,2\pi)$. This construction follows directly from the Bochner argument behind standard random Fourier features. Stack these features over the training set into an $N\times m$ matrix $Z_{jk}$, and let $Z_j$, $Z_k$, and a column of ones span the main-effect space. The purified pair block is

$$\tilde Z_{jk} = (I - P_{jk})\,Z_{jk},\qquad P_{jk} = M_{jk}(M_{jk}^\top M_{jk} + \epsilon I)^{-1}M_{jk}^\top,\quad M_{jk}=[\mathbf 1, Z_j, Z_k],$$

where $\epsilon$ is a small ridge term for numerical stability. Any function built from $\tilde Z_{jk}$ is empirically orthogonal to everything expressible by the intercept and the two single-feature curves. This is a primal-space version of the functional ANOVA purity condition. The full model is still a linear regression (or logistic regression) on the concatenated blocks, so it stays convex. Because the projection is a fixed linear map, it also applies at test time.

Pair selection is deliberately simple. We fit the purified main-effect GP-NAM. Then we score every candidate pair by how much a small purified pair block, fit to the residual, reduces validation loss. Finally, we keep the top $K$ pairs and refit jointly. We chose this two-stage screen because a skeptical reviewer would rightly argue that a more elaborate convex group-sparse selector is unlikely to beat it. The contribution is the purification and the stability analysis, not the selector.

The stability prediction comes from Optimal Rates for Random Fourier Features. That paper shows kernel approximation error decays as $m^{-1/2}$ in $L^r$ norms on compact domains, and that kernel derivatives decay at the same rate for smooth kernels. Ridge-regularized fits are Lipschitz in the kernel. We therefore expect the $L^2$ distance between two fitted shape functions, or between two pair heatmaps, from independent draws to scale as $m^{-1/2}$. We treat this as a hypothesis to measure, not a theorem we already hold. Proving it for the purified blocks, where the projection itself depends on the draw, is part of the work. The compactness assumption in that paper also constrains the design. We standardize and clip inputs to a bounded box, and we report stability separately for the tails of each feature.

Research Program

The work has three parts. First, we build the purified interaction model and release it as an extension of GP-NAM's convex solver. Second, we analyze explanation stability theoretically, aiming for a bound on draw-to-draw explanation distance in terms of $m$, the ridge strength, and the conditioning of the main-effect blocks. Third, we run a controlled empirical study. It separates three effects: the gain from adding interactions, the gain from purity, and the gain from a larger $m$. For each method, the study reports three things at once: accuracy, interaction recovery, and explanation reproducibility.

We place this against two other lines of work. Fast kernel methods: Sobolev, physics-informed, and additive models computes additive kernel models exactly with non-uniform fast Fourier transforms. The method is limited to roughly three or fewer dimensions and currently fits only one-dimensional slices. That limit constrains us rather than ruling us out, because pairwise terms are two-dimensional and so lie inside the regime where exact computation is possible. How to Scale Up Kernel Methods to Be As Good As Deep Neural Nets shows that a full random-feature kernel over all inputs can rival deep networks. Such a model is accurate but cannot be read, so it serves as our accuracy ceiling.

Baselines

The naive reference point is GP-NAM itself: univariate, purely additive, with no interaction terms. Any interaction model has to beat it on accuracy to justify the extra plots. The file reports GP-NAM's parameter and runtime numbers on FICO and LCD, but no reported result was found on Lacuna for GP-NAM's predictive accuracy (AUC or error) on FICO or LCD. We will therefore rerun it with the authors' configuration on our own splits.

The strongest competitor on the question we care about is the same two-stage interaction model without purification. It uses identical pair features, the same screen, and the same $K$, but omits the projection. It isolates our key ingredient. It should match us on accuracy, because the purified and unpurified models span nearly the same function space. If our claim is right, it should lose clearly on interaction recovery and main-effect leakage.

The accuracy ceiling is a single random-feature Gaussian kernel over all features, in the style of How to Scale Up Kernel Methods, given the same total feature budget as our model. We also run a deep NAM with added pairwise sub-networks, which tests the non-convex route.

For fairness, all methods use the same standardized and clipped inputs, the same train/validation/test splits, and the same 50-configuration random search over bandwidths and ridge strength (and over width and depth for the neural baselines). Each method is run with ten seeds that cover both frequency draws and initializations. We count our model as beating the unpurified version if it is within one standard error on test accuracy while showing lower main-effect leakage and higher planted-pair recovery on synthetic data. We count it as beating deep NA²M if it reaches comparable accuracy with lower seed-to-seed explanation variance.

Why not just…?

Why not just fit an accurate kernel model and explain it with SHAP? That model would be accurate, but the explanation would be a surrogate for the model, not the model itself. The file's evidence from G-NAMRFF is that built-in additive structure recovered known mutagenic groups more precisely than a post-hoc explainer. The full-kernel baseline also tells us exactly how much accuracy the interpretable model gives up. If that gap is large on real data, we will report it plainly.

Why not just add pairwise terms the obvious way and skip purification? This is the real threat on accuracy, and we expect it to tie us there. The case for purification is about meaning. When a pair heatmap contains part of $f_j$, a reader double-counts that effect. The synthetic experiments with planted, known decompositions measure this directly. If unpurified pair terms do not in fact absorb measurable main-effect energy, then purification is unnecessary and the proposal reduces to the stability study.

Why not just use deep pairwise NAMs? GP-NAM documents that deep shape networks are non-convex, sensitive to initialization, and produce jagged curves. They also use about 60 times more parameters. Adding $K$ pair networks compounds all three problems. Our seed-stability measurement tests whether this matters for interaction plots as it does for single-feature curves.

Why not just compute pair terms exactly with non-uniform FFTs? Two-dimensional terms are within that method's reach, so for the selected pairs exact computation is a legitimate alternative to random features, and it has no frequency-draw variance at all. We will implement it for the final selected pairs as a reference. If it matches our accuracy and purity at similar cost, we will say so. The random-feature version remains necessary for screening all $d^2/2$ candidates cheaply and for the closed-form purification projection.

Proposed Experiments

The decisive experiments use synthetic regression and classification data with known functional ANOVA decompositions. Each dataset has 10 to 50 features and 2 to 5 planted pairs, and some planted pairs share features with strong main effects. That overlap is the setting where leakage should be worst. On this data we measure four things: recovery of the planted pairs (precision and recall of the selected set), main-effect leakage (the fraction of each pair term's variance explainable by $x_j$ or $x_k$ alone, which is zero in truth), the $L^2$ error of each recovered shape function, and draw-to-draw explanation distance as $m$ ranges from 16 to 2048. The stability hypothesis predicts a slope near $-1/2$ on a log-log plot of distance against $m$.

On the real tabular benchmarks used by GP-NAM, FICO and LCD, we report test AUC for every method. We also report seed stability of the top-$K$ selected pairs (Jaccard overlap across ten draws), stability of the plotted curves, and parameter count and runtime alongside GP-NAM's reported 3,901 parameters and 50 ms per epoch. As a check on scale, we add ogbn-arxiv node features through G-NAMRFF's graph filters to test whether purified pairs remain affordable when $d$ is in the hundreds.

The proposal fails if any of three things happens. First, purified and unpurified models leak equally on synthetic data. Second, purification costs more than one standard error of AUC on FICO or LCD. Third, explanation distance does not shrink with $m$, which would mean the theory does not carry over to practice.