Compositional Kernel Grammars for Automated Structure Discovery

18 concepts16 papers1 proposal

When modeling complex data with non-parametric methods like Gaussian Processes (GPs) or Support Vector Machines (SVMs), practitioners often default to a single standard kernel, such as the Radial Basis Function (RBF) or Squared Exponential (SE) kernel. While these standard kernels are universal approximators, they operate as black boxes. They assume a uniform smoothness across the entire input space, failing to capture explicit structural nuances like long-term linear trends combined with changing seasonal cycles, and they offer no explanation as to why a prediction was made.

Early work by Thomas Briggs et al. sought to move past this "one-size-fits-all" limitation by automatically discovering composite kernels tailored to specific datasets. This evolved into a powerful paradigm: compositional kernel grammars. By treating kernel construction as a language syntax, we can systematically discover complex, human-interpretable structures directly from data.

The Intuition of Kernel Algebra

The core insight behind compositional kernel grammars is that complex data patterns can be broken down into a formal algebraic language. By treating simple, atomic kernels—such as Linear ($\text{Lin}$), Periodic ($\text{Per}$), and Squared Exponential ($\text{SE}$)—as the vocabulary, and algebraic operations like addition ($+$) and multiplication ($\times$) as the grammar rules, we can construct an infinite variety of expressive covariance structures.

As explained in a foundational tutorial by Alvaro Nosedal-Sanchez et al., these operations remain mathematically valid because the sum or product of valid reproducing kernels yields another valid positive definite kernel. But what do these operations mean intuitively?

Addition as Superposition

Adding two kernels ($\text{K}_1 + \text{K}_2$) assumes that the underlying data is a sum of two independent processes.

$$\text{Kernel} = \text{Lin} + \text{Per}$$

If we model a time series using a Linear kernel plus a Periodic kernel, the model understands that the data contains a steady, long-term upward trend and a recurring seasonal fluctuation (e.g., international airline passenger numbers over a decade). The two components do not interfere with each other; they simply coexist.

Multiplication as Modulation and Localization

Multiplying two kernels ($\text{K}_1 \times \text{K}_2$) represents an interaction, modulation, or localized effect.

$$\text{Kernel} = \text{SE} \times \text{Per}$$

Multiplying a Squared Exponential kernel by a Periodic kernel models a periodic pattern whose amplitude or shape changes smoothly over time. The $\text{SE}$ kernel acts as an envelope, allowing the model to capture non-stationary behavior where seasonal cycles gradually dampen or intensify.

Similarly, multiplying a kernel by a Linear kernel allows its effects to grow over time, while multiplying two Linear kernels ($\text{Lin} \times \text{Lin}$) yields quadratic patterns, expanding the model's geometric vocabulary.

Searching the Grammar Space

Knowing that a language exists is only half the battle; we must also find the specific "sentence" (the composite kernel expression) that best describes a given dataset. David Duvenaud et al. formalized this as a discrete search problem over a context-free grammar.

Starting from a base kernel, the system iteratively expands the expression by replacing components with algebraic combinations (e.g., replacing a base kernel $K$ with $K + \text{SE}$ or $K \times \text{Per}$). Because this creates an exponentially growing combinatorial space, researchers have developed several distinct strategies to navigate it:

  • Greedy Search and Pruning: Systems like the one proposed by Anh Tong et al. expand the grammar step-by-step, evaluating candidates using model selection criteria (such as marginal likelihood) to greedily retain the most descriptive combinations of trends and noise while pruning unpromising branches.
  • Continuous Latent Spaces: Rather than navigating a discrete graph, Rajalaxmi Rajagopalan et al. mapped discrete kernel structures into a continuous latent space using a Variational Autoencoder (VAE). This allows continuous optimization algorithms to smoothly "hunt" for the ideal kernel configuration.
  • Meta-Learning and Optimization: Gustavo Malkomes et al. integrated this grammar search directly into Bayesian optimization loops, automating the selection and ensembling of surrogate models on the fly as new data points are collected.

Human Alignment and the Automatic Statistician

Why build models using a strict algebraic grammar instead of relying on deep neural networks? The answer lies in human interpretability and cognitive alignment.

Eric Schulz demonstrated that human function learning is inherently compositional. When humans try to make sense of a complex visual pattern, they naturally decompose it into simpler building blocks like linear trends and cycles. Furthermore, Eric Schulz et al. showed that patterns generated via a compositional kernel grammar are significantly easier for humans to communicate and replicate, suggesting that this algebraic grammar closely mirrors our internal "language of thought."

This tight alignment enables the creation of systems like the "Automatic Statistician" project, introduced by David Duvenaud et al. and expanded by Christian Steinruecken et al.. Because each component of the discovered kernel corresponds to a distinct semantic pattern, the system does not just output predictions—it automatically translates the final mathematical structure into a plain-English report, explaining that a dataset contains "an escalating trend that is modulated seasonally, with localized anomalies."

Overcoming Scalability and Domain Boundaries

Historically, the primary bottleneck of this approach was the cubic computational complexity ($O(N^3)$) inherent to Gaussian Processes. To scale these grammars to larger datasets, Hyunjik Kim et al. introduced Scalable Kernel Composition (SKC), which derives a computationally cheap upper bound on the marginal likelihood to accelerate the search process across tens of thousands of data points. Complementing this, Anthony Tompkins et al. developed specialized Fourier feature approximations to handle the periodic components of the grammar efficiently at scale.

The versatility of this framework extends far beyond standard time-series forecasting. In quantum mechanics, John Sous et al. demonstrated that an automated, iterative kernel selection process could extrapolate across quantum phase transitions, identifying hidden boundaries using data from only a single phase. Meanwhile, in geometric data analysis, Alexey Lindo extended the principle of function composition to design mathematically tractable kernels for complex spherical data geometries.

By treating structure discovery as a grammatical problem, compositional kernels bridge the gap between the raw predictive power of non-parametric machine learning and the structured, interpretable insights required for scientific discovery.

Key Foundational Work

Discovering Domain-Specific Composite Kernels (2005) — contributed 1 concept elements to this direction.
Kernel Engineering for Fast and Easy Design of Natural Language Applications (2010) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_compositional_kernel_grammar_faa98a25,
  title = {compositional kernel grammar},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compositional-kernel-grammar/rdr_faa98a25f12c456dbcddd92354b25b32},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_compositional_kernel_grammar_faa98a25_v1,
  title = {compositional kernel grammar},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compositional-kernel-grammar/rdr_faa98a25f12c456dbcddd92354b25b32/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake