PaperlayerView exact revision on arXiv

Source-linked AI summary

Syntax-Directed Variational Autoencoder for Structured Data

Hanjun Dai, Yingtao Tian, Bo Dai, Steven Skiena, Le Song

arXiv:1802.08786v1cs.LGcs.CL

TL;DR

Generating discrete structured data that is both syntactically and semantically correct remains challenging. SD-VAE uses stochastic lazy attributes to convert offline semantic checking into on-the-fly decoder guidance, and reports consistent improvements across program and molecule tasks at similar computational cost.

  • Problem

    Deep generative models often produce invalid discrete structures because they lack explicit formal syntax and semantic constraints.

  • Method

    SD-VAE introduces stochastic lazy attributes that convert offline semantic checking into online guidance during syntax-tree generation.

  • Results

    The model consistently and significantly improves generation, reconstruction, and optimization evaluations for Python programs and molecules.

  • Takeaways & Limitations

    SD-VAE constrains the decoder to address both syntax and semantic constraints while retaining computational cost O(n).

  • Takeaways & Limitations

    The evaluated program and molecule semantics cover specified subsets, including defined-before-reference programs and selected SMILES constraints.

Abstract

from arXiv · show

Deep generative models have been enjoying success in modeling continuous data. However it remains challenging to capture the representations for discrete structures with formal grammars and semantics, e.g., computer programs and molecular structures. How to generate both syntactically and semantically correct data still remains largely an open problem. Inspired by the theory of compiler where the syntax and semantics check is done via syntax-directed translation (SDT), we propose a novel syntax-directed variational autoencoder (SD-VAE) by introducing stochastic lazy attributes. This approach converts the offline SDT check into on-the-fly generated guidance for constraining the decoder. Comparing to the state-of-the-art methods, our approach enforces constraints on the output space so that the output will be not only syntactically valid, but also semantically reasonable. We evaluate the proposed model with applications in programming language and molecules, including reconstruction and program/molecule optimization. The results demonstrate the effectiveness in incorporating syntactic and semantic constraints in discrete generative models, which is significantly better than current state-of-the-art approaches.

1 INTRODUCTION

Generating discrete structured data remains difficult because valid outputs must satisfy formal syntax and semantics. SD-VAE incorporates semantic guidance during generation, constraining outputs while retaining linear computational cost and improving evaluations across programs and molecules.

  • Motivation: Discrete structured-data generators often produce invalid graphs, molecules, and programs without explicit syntax and semantic constraints.The challenge contrasts with successful deep generative modeling of continuous data.
  • Existing approaches: String-based approaches and CFG-constrained decoders formalize structure, but CFGs do not capture all semantic restrictions.GVAE generates SMILES parse trees using production rules, while semantic checking may still require separate validation.
  • SD-VAE: SD-VAE advances semantic restriction into the syntax-tree generator, enabling joint syntactic and semantic validation during tree generation.Its attribute-grammar mechanism replaces repeated offline checking with guidance integrated into decoding.
  • Efficiency: SD-VAE has computational cost O(n), where n is structured-data length, matching methods such as CVAE and GVAE that do not enforce semantics during generation.Semantic guidance runs on the fly instead of generating many candidates for later semantic checking.
  • Empirical evaluation: Across Python programs and molecules, SD-VAE consistently and significantly improves generation, reconstruction, and optimization evaluations.The paper presents these results as evidence of strong empirical performance across both application domains.

2 BACKGROUND

Variational autoencoders model structured observations through latent variables, while context-free and attribute grammars formalize syntax and semantics. Bottom-up attribute checking creates a mismatch with top-down tree generation because synthesized attributes depend on children not yet generated.

  • 2.1 VARIATIONAL AUTOENCODER: A VAE jointly learns an encoder and decoder by maximizing the evidence lower bound of the marginal likelihood.The decoder models pθ(x|z), while the encoder qψ(z|x) approximates the posterior over latent representations.
  • 2.2 CONTEXT FREE GRAMMAR AND ATTRIBUTE GRAMMAR: A CFG separates nonterminal and terminal symbols, with production rules expanding nonterminals into terminal and nonterminal sequences.The grammar is defined by G = ⟨V, Σ, R, s⟩, including a start symbol and production-rule set.
  • 2.2 CONTEXT FREE GRAMMAR AND ATTRIBUTE GRAMMAR: Attribute grammars attach semantic attributes to CFG symbols, distinguishing inherited attributes from synthesized attributes.Inherited attributes depend on parent and sibling information, whereas synthesized attributes are computed from children.
  • 2.2.1 A MOTIVATIONAL EXAMPLE: The motivating SMILES grammar uses attributes to check whether paired ring bonds agree in bond type, bond index, and set membership.The example expresses a non-context-free cross-serial dependency through attribute matching and an ok constraint.
  • 2.2.1 A MOTIVATIONAL EXAMPLE: Bottom-up semantic checking cannot directly guide top-down generation because synthesized attributes require information from children that have not yet been generated.Offline acceptance-rejection checking is introduced as the straightforward alternative, but the supplied passage identifies the resulting procedural dilemma.

3 SYNTAX-DIRECTED VARIATIONAL AUTOENCODER

SD-VAE incorporates attribute-grammar semantics into VAE decoding by generating stochastic lazy attributes and using them as online constraints during recursive tree generation. The decoder expands CFG nodes while propagating inherited constraints and lazily linking synthesized attributes when dependent subtrees are available.

  • 3 SYNTAX-DIRECTED VARIATIONAL AUTOENCODER: SD-VAE brings attribute-grammar constraints online into the VAE decoder to address syntactic and semantic validity during generation.The method is explicitly presented as an alternative to applying attribute grammars offline after generation.
  • 3.1 STOCHASTIC SYNTAX-DIRECTED DECODER: Stochastic lazy attributes transform unavailable synthesized attributes into inherited constraints and link their actual values once dependent attributes are ready.This design enables on-the-fly semantic validation despite children being generated later.
  • 3.1 STOCHASTIC SYNTAX-DIRECTED DECODER: The generative process samples stochastic attributes, selects CFG production rules, recursively generates child nodes, and updates attributes through lazy linking.Figure 3 orders these operations from stochastic attribute generation through constrained sampling, subtree calculation, and root-level lazy evaluation.
  • 3.1 STOCHASTIC SYNTAX-DIRECTED DECODER: Stochastic attributes are sampled as Bernoulli predeterminations when synthesized values are unavailable, then passed to children as inherited semantic constraints.In the example, the sampled attribute indicates whether a ringbond should occur and regulates subsequent child generation.
  • 3.1 STOCHASTIC SYNTAX-DIRECTED DECODER: Tree construction repeatedly expands frontier nonterminals with grammar rules until all frontier nodes are terminals, producing syntactically and semantically valid structures.The decoder samples a node and production rule at each step, attaches the rule’s symbols, and recursively generates children.
  • 3.2 ENCODER AND 3.3 MODEL LEARNING: During training, likelihood computation follows the same tree-generation process as sampling, except that the observed structure fixes the computation path.The encoder maps structured inputs into latent space using parse-tree production representations, while VAE learning maximizes the ELBO.

4 RELATED WORK

Prior work applies sequence models or CFG-constrained decoders to structured generation, but semantic constraints remain difficult to enforce. SD-VAE instead uses stochastic lazy attributes to reshape the decoder’s output domain around semantic validity.

  • 4 RELATED WORK: Sequence-based molecule generators are flexible but can produce invalid structures when trained with limited data and without formal syntax or semantic restrictions.An extra validator model was reported as helpful to some degree, but the underlying sequence approach remains constrained by validity concerns.
  • 4 RELATED WORK: Grammar VAE generates parse trees with CFG-constrained decoding, masking invalid syntax so outputs remain within the grammar-defined language.This approach was applied to simple mathematical expressions and SMILES strings.
  • 4 RELATED WORK: SD-VAE captures semantics with stochastic lazy attributes and reshapes the decoder’s output domain for discrete structures.The supplied passage presents this as the paper’s semantic extension beyond syntax-focused generation.

5 EXPERIMENTS

Experiments compare SD-VAE with CVAE and GVAE on programs and molecules, evaluating reconstruction, validity, optimization, latent prediction, diversity, and interpolation. Across these evaluations, SD-VAE generally improves validity, reconstruction, optimization, and latent-space quality while retaining diversity.

  • Experimental setup: SD-VAE is compared with CVAE and GVAE on Python programs and molecules using matched experimental protocols.CVAE uses character sequences, whereas GVAE incorporates context-free grammar.
  • Datasets: 130,000 valid programs and 250,000 ZINC SMILES strings support the experiments, with 2,000 and 5,000 held-out test examples respectively.Program examples contain 1–5 statements; the molecule split follows Kusner et al. (2017).
  • Reconstruction and validity: SD-VAE achieves near-perfect program reconstruction and perfect valid prior decoding, while maintaining high reconstruction rates as program size increases.The reported improvement is attributed to using program semantics that previous work ignores.
  • Reconstruction and validity: SD-VAE produces much higher SMILES reconstruction and valid-prior rates; using kekulized SMILES raises valid prior to 97.3%.The main reported results exclude semantics specific to aromaticity.
  • Bayesian optimization: For Bayesian optimization, SD-VAE finds programs closer to ground truth and molecules with better drug-likeness scores than previous methods.Program distance is log(1 + MSE); molecule optimization targets penalized log P, and SD-VAE finds richer structures than baselines.
  • Latent representations and diversity: SD-VAE yields more discriminative latent representations for property regression, smoother valid program interpolation, and similar molecular diversity to baselines.Its restricted decoding space does not sacrifice diversity in the reported molecule experiment.

6 CONCLUSION

The paper introduces a method for handling both syntax and semantic constraints in structured-data generation. Stochastic lazy attributes convert offline checking into online guidance, with consistent improvement over previous models at similar computational cost.

  • Stochastic lazy attributes convert offline syntax and semantic checking into online guidance for stochastic generation.
  • The method shows consistent and significant improvement over previous models while requiring similar computational cost.
  • Future work includes refining the formalization theoretically and applying it to more diverse data modalities.

A GRAMMAR

The program syntax is defined by a generative context-free grammar beginning with the nonterminal ⟨program⟩.

  • The program grammar is a generative context-free grammar starting from ⟨program⟩.
  • The grammar defines ⟨digit⟩ using the alternatives ‘1’ through ‘9’.
  • A separate ⟨digit⟩ production includes the alternatives ‘0’ through ‘9’.

A.2 GRAMMAR FOR MOLECULE SYNTAX

The molecule syntax grammar is based on OpenSMILES and uses a context-free grammar beginning with ⟨s⟩. The section also specifies semantic constraints and assumes a noncircular attribute-dependency graph for top-down decoding.

  • Molecule syntax: The molecule syntax grammar follows the OpenSMILES standard as a context-free grammar starting with ⟨s⟩.
  • Molecule syntax: Its ⟨aliphatic organic⟩ production includes elemental symbols and structured alternatives involving brackets, isotopes, and symbols.
  • Molecule syntax: The molecule grammar defines ⟨digit⟩ with the alternatives ’1’ through ’8’.
  • Molecule semantics: The addressed SMILES semantic constraints include matching ringbond pairs and controlling atom valence.
  • Attribute dependencies: Attribute dependencies form a graph over attributes and their computation relationships within partial or complete syntax-tree instantiations.
  • Attribute dependencies: The decoder assumes this dependency graph is noncircular, enabling its use during top-down generation.

B TRAINING DETAILS

Training uses the same neural architecture as prior CVAE and GVAE work for fair comparison, with validation-based hyperparameter tuning and a reconstruction-plus-KL loss.

  • Architecture: The model uses the same deep neural network architecture as CVAE and GVAE for fair comparison.
  • Training procedure: Hyperparameters are tuned on a 10% validation set, and test results use the setting with the best validation loss.
  • Objective: Training minimizes ReconstructLoss + αKLDivergence while exploring α = 1 and α = 1/LatentDimension.

C MORE EXPERIMENT DETAILS

The experiments use latent-space Bayesian optimization to search for structures with desired properties, with repeated decoding to regulate stochastic proposals.

  • Reconstruction: Figure 8 visualizes reconstruction by placing target molecules in the first column and sampling reconstructed molecules from their encoded posteriors.
  • Bayesian optimization: Bayesian optimization searches latent vectors for programs fitting input-output pairs or molecules with maximum drug likeness.The comparison follows the settings used in Kusner et al. (2017).
  • Bayesian optimization: The workflow trains an unsupervised variational autoencoder, encodes structures into latent space, and fits a sparse Gaussian process with 500 inducing points.The Gaussian process uses latent vectors and corresponding property values to predict properties in latent space.
  • Bayesian optimization: Each iteration performs 100 decoding rounds and selects the most frequent decoded structures to regulate randomness and increase the chance of valid proposals.

C.2 RECONTRUCTION

SMILES reconstruction usually recovers the exact input, although decoder stochasticity can produce small variations.

  • Reconstruction: In most cases, the decoder successfully recovers the exact origin input during SMILES reconstruction.
  • Reconstruction: Decoder stochasticity can produce small variations in reconstructed SMILES.
Loading 1802.08786v1…