Source-linked AI summary
Grammar Variational Autoencoder
Matt J. Kusner, Brooks Paige, José Miguel Hernández-Lobato
TL;DR
Structured discrete data can yield invalid outputs when modeled as strings. The paper introduces a parse-tree-based grammar variational autoencoder, which produces more valid outputs, smoother latent spaces, and improved optimization results for arithmetic expressions and molecules.
Problem
Generative modeling of discrete structures remains challenging because string-based representations can decode to invalid or implausible outputs.
Method
The GVAE encodes and decodes directly to and from parse trees defined by a context-free grammar.
Results
The GVAE produces more valid outputs and smoother latent representations, while supporting effective Bayesian optimization for arithmetic expressions and molecular design.
Takeaways & Limitations
Grammar-based representations can improve representation learning, inference, and optimization for domains expressible in context-free languages.
Takeaways & Limitations
The grammar captures syntactic validity but not necessarily chemical validity, and SMILES includes non-context-free constraints.
Abstract
from arXiv · showhide
Deep generative models have been wildly successful at learning coherent latent representations for continuous data such as video and audio. However, generative modeling of discrete data such as arithmetic expressions and molecular structures still poses significant challenges. Crucially, state-of-the-art methods often produce outputs that are not valid. We make the key observation that frequently, discrete data can be represented as a parse tree from a context-free grammar. We propose a variational autoencoder which encodes and decodes directly to and from these parse trees, ensuring the generated outputs are always valid. Surprisingly, we show that not only does our model more often generate valid outputs, it also learns a more coherent latent space in which nearby points decode to similar discrete outputs. We demonstrate the effectiveness of our learned models by showing their improved performance in Bayesian optimization for symbolic regression and molecular synthesis.
1. Introduction
Discrete generative modeling is difficult because string representations can produce invalid or brittle outputs. The GVAE addresses this by encoding and decoding grammar parse trees, improving validity and latent-space smoothness across arithmetic and molecular tasks.
- Motivation: String-based molecule representations are brittle: small changes can alter the molecule or produce invalid structures.A probabilistic decoder may assign high probability to invalid SMILES strings or implausible molecules.
- Motivation: Context-free grammars describe syntactically valid structures such as symbolic expressions, programming languages, and chemical strings.For SMILES, the grammar supports parsing and validation.
- Approach: The GVAE encodes and decodes directly from grammar parse trees, ensuring generated outputs are valid under the grammar.This removes the need to learn syntactic rules implicitly and lets the model focus on other properties.
- Experiments: The model is evaluated on generating arithmetic expressions and valid molecules.These experiments target two discrete-data generation tasks.
- Results: The GVAE produces more valid outputs and smoother latent representations than a character-based autoencoder.Its latent space supports searching for expressions fitting data, finding better drug-like molecules, and predicting target properties.
2. Background
Variational autoencoders learn continuous latent representations through probabilistic encoding and decoding optimized with the ELBO. Context-free grammars define valid parse trees and can provide probabilistic generative models over the corresponding strings.
- Variational autoencoders: A VAE learns an encoder and decoder that map data x to and from a continuous latent variable z.The decoder uses pθ(x|z), while the posterior pθ(z|x) is interpreted as a probabilistic encoder.
- Variational autoencoders: Variational Bayes jointly learns decoder parameters and an approximate posterior qφ(z|x) by maximizing the evidence lower bound.This enables efficient inference while retaining flexible encoder and decoder choices.
- Context-free grammars: A context-free grammar consists of non-terminals, terminals, production rules, and a start symbol.Its production rules rewrite one non-terminal as a sequence of terminals and/or non-terminals.
- Context-free grammars: Applying production rules recursively forms trees whose leaves become terminal symbols, and left-to-right leaf traversal produces strings in the grammar’s language.A parse tree for a valid string is rooted at the start symbol and has that string as its terminal leaves.
- Probabilistic grammars: Assigning probabilities to grammar production rules defines a probabilistic model over parse trees and valid strings.Generation repeatedly samples and applies rules from the start symbol until no non-terminals remain.
3. Methods
The GVAE represents discrete objects as grammar parse trees, then encodes and decodes production-rule sequences while constraining decoding to syntactically valid choices.
- Encoding: The GVAE parses each valid input into a production-rule sequence and converts the rules into 1-hot vectors for encoding.For benzene, the parse tree is traversed in preorder, producing a T(X)×K matrix that a convolutional network maps to latent vector z.
- Decoding: The decoder maps latent vector z through a recurrent network to logits whose dimensions correspond to grammar production rules.The logits form a matrix F ∈ R^Tmax×K for selecting rules across decoding timesteps.
- Decoding: A LIFO stack tracks pending non-terminals, while masks remove production rules whose left-hand side cannot match the current stack symbol.The decoder samples only from the remaining rules, recursively pushing right-hand-side non-terminals until the stack is empty.
- Decoding: The decoder samples production rules until completion, using a no-op rule to pad shorter sequences to the maximum length Tmax.Algorithm 1 initializes the start symbol, repeatedly pops a non-terminal, samples a rule, pushes its right-hand-side non-terminals, and appends the rule.
- Validity: Unlike a character VAE, the grammar decoder cannot sample arbitrary symbols; its stack and masking operations constrain outputs to syntactically valid grammar sequences.This constraint reduces invalid outputs, although grammar validity does not guarantee chemical or semantic validity.
- Training: Training encodes each input as rule indicators, samples z from qφ(z|X), computes masked decoder probabilities, and updates parameters by gradient descent on the ELBO.The encoder distribution is Gaussian with isotropic prior p(z) = N(0, I), and completed parses are padded with a dummy rule.
4. Experiments
Experiments compare grammar- and character-based VAEs on latent-space smoothness, Bayesian optimization for expressions and molecules, and predictive performance. The GVAE produces valid outputs more reliably and supports stronger optimization and prediction results.
- Bayesian optimization: Bayesian optimization searches GVAE latent spaces for arithmetic expressions fitting a fixed dataset and for molecules with improved drug properties.The procedure trains a property predictor and uses Bayesian optimization to select latent points for decoding.
- Latent-space visualization: The GVAE produces smooth latent interpolations while generating valid arithmetic equations throughout, unlike the CVAE’s invalid intermediate strings.The grammar VAE also makes subjectively smaller perturbations between interpolated equations.
- Arithmetic expressions: The GVAE nearly always finds valid arithmetic sequences and achieves better average scores than the CVAE.Invalid outputs are rare and occur when the decoder reaches its timestep limit with non-terminals remaining on the stack.
- Arithmetic expressions: The GVAE’s best expression matches the target function nearly perfectly, whereas the CVAE misses its sinusoidal component.The difference between the GVAE expression and the true function is described as negligible.
- Molecules: For molecular optimization, the GVAE produces about twice more valid sequences than the CVAE, and its valid sequences have higher average scores.The comparison uses repeated Bayesian-optimization trials and reports overall results for finding drug-like molecules.
- Predictive performance: GVAE latent features yield much better sparse-GP predictive performance than CVAE features for both expressions and molecules.Performance is evaluated using average test RMSE and test log-likelihood across ten data splits.
5. Related Work
Related work spans generative sequence models for discrete structures, symbolic-regression search, and molecular design. The cited methods motivate grammar-based representations while distinguishing prior discriminative parse-tree models from generative latent-space learning.
- Parse-tree representations: Parse-tree methods have learned continuous representations for text and recursively combined child-node vectors, but these approaches are discriminative.The cited recursive and autoencoding models minimize reconstruction-related objectives rather than learning a generative latent space.
- Evaluation context: The section also references tables reporting test log-likelihood, RMSE, reconstruction accuracy, and sample validity.The supplied table captions identify these evaluation dimensions without reporting their values.
- Symbolic regression: Symbolic regression commonly uses genetic programming, evolutionary algorithms, or particle MCMC to propose or infer candidate expressions.These approaches include computationally demanding evolutionary search and Bayesian posterior estimation over parse trees.
- Molecular design: Molecular design traditionally searches large databases with virtual screening and domain-specific stochastic algorithms.The cited work notes that the databases are too large for exhaustive enumeration.
6. Discussion
The discussion concludes that parse-tree representations outperform text-based representations for molecules and equations, with potential broader use in context-free-language domains.
- Discussion: Parse-tree representations empirically outperform text-based representations for molecules and equations.The stated comparison concerns the empirical performance of the two representation types.
- Discussion: The approach may be useful for representation learning, inference, and optimization in domains representable as text in a context-free language.This is presented as the authors’ broader belief about the approach’s potential scope.
A. Grammars for equations and SMILES
The paper defines separate grammars for single-variable equations and SMILES molecules. The equation grammar specifies operators, constants, grouping, and bounded training-tree complexity, while the SMILES grammar follows OPENSMILES.
- Equations: The equation grammar contains 3 binary operators, 2 unary operators, 3 constants, grouping symbols, and start symbol S.Training data included 100,000 equations with parse-tree depth below 7, using up to 15 production-rule applications.
- Equations: The displayed equation grammar expands S through addition, multiplication, or division and expands T through grouping, unary functions, x, or constants.The listed productions include sin, exp, x, 1, 2, and 3.
- SMILES: The SMILES grammar is based on the official OPENSMILES specification and begins with the start symbol smiles.The supplied grammar fragment includes productions for chains, atoms, bracket atoms, aromatic atoms, isotopes, chirality, hydrogen counts, charges, and classes.
B. Network structure
The network uses an encoder that maps an input sequence to a distribution over real-valued latent vectors and a decoder that maps a latent vector to a sequence distribution.
- Encoder and decoder: The encoder qφ(z|X) takes a sequence of T timesteps and returns a distribution over real-valued vectors z.The input is written as X = [x1, . . . , xT].
- Encoder and decoder: The decoder pθ(x|z) takes a real-valued vector z and generates a distribution over sequences X.The paper states that the encoder and decoder are based on the architecture used by Gómez-Bombarelli et al., with modifications described later.
- Evaluation: A supplied table caption identifies reconstruction accuracy and sample validity as evaluation measures.The caption does not provide the corresponding values.
C. Additional experiments
The grammar VAE improves molecular reconstruction and prior validity while producing a smoother, more concentrated latent organization of logP values.
- LogP Visualization: Figure 6 compares logP values in two-dimensional character- and grammar-VAE latent spaces.The caption describes the grammar VAE latent space as visually smoother with respect to the property of interest.
- Molecule reconstruction & validity: The grammar VAE achieves higher molecular reconstruction accuracy and prior validity than the character VAE.Reconstruction accuracy is computed over 5,000 hold-out molecules encoded 10 times each; prior validity uses 1,000 latent points decoded 500 times each.
- LogP Visualization: The GVAE concentrates molecules with high logP in a small latent-space region.The CVAE instead places higher-logP molecules mainly in the lower portion of the latent space.