Additive kernel

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 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 1112.4394 §3.1 1112.4394 eq. 1–1112.4394 eq. 3. The number of terms in order n is C(D, n) 1112.4394 §3.1.

The invariants all variants keep:

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

The card for the source paper is Additive Gaussian Processes.

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 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 1112.4394 §5.2. Learned order variances show how much of the signal each interaction order carries 1112.4394 §3.2. Card: Additive Gaussian Processes.

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 1112.4394 tab. 2. Across the five regression sets the paper claims no competitor significantly beats it 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 1112.4394 §3.4. The authors note that the first few orders usually matter most, so R can be lowered with little loss 1112.4394 §3.4. The paper caps R at 10 "for speed" 1112.4394 §5.2. Card: Additive Gaussian Processes.

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 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.

When to use which

Hyperparameters are point estimates, and the authors expect integrating them out to help 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 1112.4394 §3.3 1112.4394 eq. 6.

# 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

# 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 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 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] 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 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 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% 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: 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.