---
kind: concept
slug: additive-kernel
title: Additive kernel
summary: >-
  A Gaussian-process kernel that sums products of one-dimensional kernels over all interaction orders, with one learned variance per order. Newton–Girard identities make the full sum O(D²). It captures interactions between input coordinates without the locality of squared-exponential kernels. Trade-off: the order sum grows with D, so it is often truncated.
tags: [kernel-methods, regression, interpretability]
papers: ["1112.4394"]
related: [gaussian-process, interpretable-machine-learning]
status: draft
updated_at: 2026-11-01
---

## Overview

Regression with a Gaussian process (GP) needs a covariance kernel. A kernel
built from one-dimensional base kernels, one per input, is easy to read but
misses interactions. A squared-exponential (SE) kernel over all inputs at once
captures interactions but is local, so it generalizes poorly to input
combinations it has not seen [arxiv:1112.4394 §1].

The shared idea is to sum interaction orders. The kernel is the sum over
orders n = 1..D of an order-n term, which is σ_n² times the sum over all
n-subsets of inputs of the product of their one-dimensional base kernels
[arxiv:1112.4394 §3.1] [arxiv:1112.4394 eq. 1]–[arxiv:1112.4394 eq. 3]. The
number of terms in order n is C(D, n) [arxiv:1112.4394 §3.1].

The invariants all variants keep:

- Each order has its own variance σ_n², learned with the other
  hyperparameters [arxiv:1112.4394 §5.2].
- Only the kernel changes. Everything else in GP inference is unchanged
  [arxiv:1112.4394 §3.1] [arxiv:1112.4394 §3.4].
- The order-D term, with SE base kernels, is the usual multivariate SE kernel
  [arxiv:1112.4394 eq. 5].
- All orders can be summed in O(D²) with Newton–Girard identities
  [arxiv:1112.4394 §3.3] [arxiv:1112.4394 eq. 6].

The card for the source paper is [Additive Gaussian Processes](/papers/1112.4394).

## Variants

### Full additive kernel (all orders 1..D)

Sums every order from 1 to D, each with its own learned variance. The paper
treats this as the main model [arxiv:1112.4394 §3.1]. In the paper's
experiments the maximum order is min(D, 10), so the full sum is used only when
D ≤ 10 [arxiv:1112.4394 §5.2]. Learned order variances show how much of the
signal each interaction order carries [arxiv:1112.4394 §3.2]. Card:
[Additive Gaussian Processes](/papers/1112.4394).

Author-reported: on the concrete regression set the additive GP has MSE 0.089,
against 0.147 for HKL and 0.157 for SE-GP [arxiv:1112.4394 tab. 2]. Across the
five regression sets the paper claims no competitor significantly beats it
[arxiv:1112.4394 §5.3].

### Truncated additive kernel (maximum order R < D)

Sums only orders 1..R. The Gram matrix costs O(N²DR), with R the maximum order
[arxiv:1112.4394 §3.4]. The authors note that the first few orders usually
matter most, so R can be lowered with little loss [arxiv:1112.4394 §3.4]. The
paper caps R at 10 "for speed" [arxiv:1112.4394 §5.2]. Card:
[Additive Gaussian Processes](/papers/1112.4394).

Truncation is a trade-off, not a free saving. Dropped orders take their
variance with them. See Contradictions below.

### First-order additive kernel (GP-GAM)

Sets R = 1: a sum of one-dimensional kernels with no interactions. The paper
uses it as a baseline, named GP-GAM [arxiv:1112.4394 §5.2]. On all five
regression sets it has higher MSE than the additive GP [arxiv:1112.4394
tab. 2]; for example bach 1.259 against 0.045, and servo 0.281 against 0.110.
Card: [Additive Gaussian Processes](/papers/1112.4394).

## When to use which

| Situation | Use | Why |
|---|---|---|
| Interactions likely, D ≤ 10, and you want to read which orders matter | Full additive kernel | Every order is included and each has a learned variance [arxiv:1112.4394 §3.2] [arxiv:1112.4394 tab. 1] |
| D > 10, or a tight compute budget | Truncated additive kernel, R chosen per dataset | Gram cost scales with R [arxiv:1112.4394 §3.4]. Check the order shares first: dropping high orders can drop most of the variance [arxiv:1112.4394 tab. 1] |
| Effects are close to separable and interactions are known to be absent | First-order (GP-GAM) | Simplest additive model. The paper's results show it is worse than the full additive kernel on all five regression sets, so use it only when interactions are truly absent [arxiv:1112.4394 tab. 2] |
| Data covers the relevant input combinations densely and the function is local | SE-GP over all inputs | The SE kernel needs data at all relevant input combinations [arxiv:1112.4394 §1] [arxiv:1112.4394 §4.3]. On housing it has the lowest regression MSE in the paper's table [arxiv:1112.4394 tab. 2] |
| Small or medium dataset, classification | Benchmark the kernel choice | Kernel choice has a large effect on quality for small to medium datasets [arxiv:1112.4394 §2]. On breast the SE-GP has the lowest error (4.734% against 5.566% for the additive GP) [arxiv:1112.4394 tab. 4] |
| Structure is not aligned with the input axes | Rotate the inputs, or use another kernel | Interactions are defined between input coordinates [arxiv:1112.4394 §3.1]. The paper does not test rotated inputs |

Hyperparameters are point estimates, and the authors expect integrating them
out to help [arxiv:1112.4394 §5.3]. Treat the table as a starting point, and
measure on your own data.

## Implementation sketch

The sketch below is written from the equations, not from the authors' code.
The repository is GPL-2.0, so copying it is not an option. The
elementary-symmetric step is a direct recurrence, not the paper's Newton–Girard
form. It is equal to the same polynomials [arxiv:1112.4394 §3.3] [arxiv:1112.4394 eq. 6].

```pseudocode
# Additive kernel over D inputs, orders 1..R  [arxiv:1112.4394 eq. 1]
# Inputs:  X1 (N1, D), X2 (N2, D); lengthscales (D,); order_var (R,)
# Output:  K (N1, N2), the Gram matrix

def additive_kernel(X1, X2, lengthscales, order_var):
    D = len(lengthscales)
    R = len(order_var)  # maximum interaction order, R <= D
    # One 1-D SE base kernel per input dimension  [arxiv:1112.4394 §3.1]
    z = [se_1d(X1[:, d], X2[:, d], lengthscales[d])
         for d in range(D)]
    # Elementary symmetric polynomials e_0..e_R of z  [arxiv:1112.4394 §3.3]
    e = elementary_symmetric(z, R)
    # Each order gets its own variance sigma_n^2  [arxiv:1112.4394 eq. 1]
    K = zeros(N1, N2)
    for n in range(1, R + 1):
        K = K + order_var[n - 1] * e[n]
    return K
```

```pseudocode
# e_n = sum over n-subsets of the product of z_d  [arxiv:1112.4394 eq. 1]
# Fold in one dimension at a time: e_n += z_d * e_(n-1).
# Cost O(D * R) per entry. With R = D this is O(D^2), as in the paper.
# No alternating signs, unlike the Newton-Girard form [arxiv:1112.4394 eq. 6]

def elementary_symmetric(z, R):
    # e_0 = 1; all other orders start at zero  [arxiv:1112.4394 eq. 6]
    e = [ones_like(z[0])] + [zeros_like(z[0]) for _ in range(R)]
    for zd in z:
        # Go from high order to low, so each z_d is used once
        for n in range(R, 0, -1):
            e[n] = e[n] + zd * e[n - 1]
    return e
```

Notes for implementers:

- Order-n terms are sums of C(D, n) products [arxiv:1112.4394 §3.1]. Their
  raw scales differ by orders of magnitude, so scale the order variances
  before optimizing. The paper does not discuss this [arxiv:1112.4394 §3.1].
- The paper gives derivatives of an order-n term with respect to a base
  kernel: the order-(n-1) polynomial over the other dimensions [arxiv:1112.4394
  eq. 7] [arxiv:1112.4394 §3.3]. This is what makes the base-kernel
  lengthscales trainable by marginal likelihood.
- The paper fits by maximizing the training marginal likelihood over the
  lengthscales, the order variances and the noise, with a constant mean
  [arxiv:1112.4394 §5.2]. The optimizer budget and initial values are described
  in the card's Paper vs code section.

## Contradictions

- **Which orders matter.** The authors say the first few orders usually matter
  most, so R can be lowered [arxiv:1112.4394 §3.4]. Their own order-variance
  table shows the dominant order is 3, 6 or 8 on four of seven datasets
  (liver, pima, housing, pumadyn-8nh). Heart puts 22.0% of its variance at
  order 10, and housing 12.7% [arxiv:1112.4394 tab. 1]. A small R therefore
  drops real signal on some datasets. Check the shares on your data.
- No disagreements between papers are known: this page cites one paper.

## Papers

- [Additive Gaussian Processes](/papers/1112.4394): introduces the additive
  kernel with one variance per interaction order, and the O(D²) evaluation
  with Newton–Girard identities. Author-reported results on five regression and
  six classification datasets.