BOSS: Bayesian Optimization over String Spaces

Henry B. Moss, David S. Leslie, Daniel Beck, Javier Gonzalez, Paul Rayson

Introduction

Many high-stakes optimization problems in chemistry, biology, and machine learning involve discrete strings, such as DNA sequences, SMILES representations of molecules, or symbolic arithmetic expressions. These spaces are notoriously difficult for standard Bayesian Optimization (BO) because they are discrete, often of variable length, and subject to strict syntactical constraints.

The standard solution is to train a Variational Autoencoder (VAE) to map strings into a continuous latent space and perform BO there. However, VAEs require massive amounts of unlabeled data to train, are difficult to tune, and often create "dead zones" in the latent space that decode to invalid strings. This paper introduces BOSS (Bayesian Optimization over String Spaces), a novel framework that performs BO directly on raw, discrete strings without needing to map them into a continuous latent space.

Methodology

BOSS removes the latent space encoding step entirely, operating directly on the original strings to avoid the information loss and "warping" introduced by VAEs.

The BOSS optimization loop: (a) GP surrogate model, (b) Genetic algorithm acquisition, (c) Evaluation

1. The Surrogate Model: String Kernels

Instead of a standard continuous kernel, BOSS uses a Gaussian Process (GP) with a Sub-sequence String Kernel (SSK). The SSK measures the similarity between two strings by counting shared non-contiguous sub-sequences (e.g., "genetics" and "genomic" share "gen" and "ic", even with other letters interspersed). This approach effectively "hard-codes" linguistic intuition into the model, capturing contextual and positional information that simple "bag-of-ngrams" approaches miss. It is also incredibly data-efficient, requiring only two hyperparameters (match decay and gap decay) to be tuned.

2. Acquisition Function Maximization: Genetic Algorithms

In BO, finding the next string to evaluate requires maximizing an acquisition function. Since gradients cannot be used on discrete strings, BOSS employs a suite of Genetic Algorithms (GA). The authors designed specific GA operators (mutation and crossover) for different constraint levels: unconstrained, locally constrained (fixed length/positional alphabets), and grammar-constrained.

Mutation and crossover operations performed directly on parse trees to maintain grammatical validity

By performing GA operations on the parse trees of a Context-Free Grammar (CFG) rather than the raw characters, BOSS ensures that every candidate string generated during the optimization loop is syntactically valid.

3. Computational Efficiency

To handle the cubic complexity of string kernels, the authors implemented a vectorized formulation and a "split-and-sum" approximation for long sequences. This allows the model to scale to strings with thousands of characters.

Key Results

The framework was evaluated across four diverse scenarios: synthetic string optimization, protein design, symbolic regression, and molecular design.

  • Sample Efficiency: BOSS consistently found better solutions with far fewer objective evaluations than VAE-based methods, which is critical for expensive real-world applications like drug discovery.
  • Synthetic Tasks: BOSS (SSK + GA) reached global optima significantly faster than random search or standard feature-based BO.
  • Protein Optimization: For long sequences (up to 3,672 characters), the SSK-based approach outperformed domain-specific "Bio-Features" and linear kernels, proving its ability to model long-range dependencies.
  • Symbolic Regression: BOSS significantly outperformed both Grammar VAEs (GVAE) and Character VAEs (CVAE), even though the VAEs were pre-trained on the specific task's data.
  • Internal Representations: Using Kernel PCA, the authors demonstrated that the SSK creates a much "smoother" and more structurally intuitive internal representation of SMILES strings than the latent space of a VAE.

Limitations and Future Work

While highly sample-efficient, calculating string kernels is computationally heavier than standard kernels. The authors' "split-and-sum" method helps, but further scaling for extremely long sequences remains an area for research. Additionally, while the GA is robust, genetic algorithms have their own hyperparameters (population size, mutation rates) that may require oversight in highly complex spaces.

Future work could extend this framework to other convolution kernels, such as tree kernels or graph kernels, to directly optimize even more complex discrete structures like neural network architectures or molecular graphs.

Summary updated

Abstract

This article develops a Bayesian optimization (BO) method which acts directly over raw strings, proposing the first uses of string kernels and genetic algorithms within BO loops. Recent applications of BO over strings have been hindered by the need to map inputs into a smooth and unconstrained latent space. Learning this projection is computationally and data-intensive. Our approach instead builds a powerful Gaussian process surrogate model based on string kernels, naturally supporting variable length inputs, and performs efficient acquisition function maximization for spaces with syntactic constraints. Experiments demonstrate considerably improved optimization over existing approaches across a broad range of constraints, including the popular setting where syntax is governed by a context-free grammar.
BibTeX
@inproceedings{moss2020boss,
  author = {Henry B. Moss and David S. Leslie and Daniel Beck and Javier Gonzalez and Paul Rayson},
  title = {{BOSS: Bayesian Optimization over String Spaces}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=xYme6HI7_qE},
}
Figure