A Chance-Constrained Generative Framework for Sequence Optimization

Xianggen Liu, Qiang Liu, Sen Song, Jian PengICML 2020 · OpenReview

TL;DR

Optimizing discrete sequences—such as molecules or computer code—is notoriously difficult because small changes can lead to "junk" outputs that violate basic grammar or physical rules. This paper introduces the Chance-Constrained Generative Framework (CCGF), which treats validity as a probabilistic constraint. The model learns to satisfy this constraint while simultaneously hunting for sequences with the best possible target properties.

The Challenge: Validity vs. Optimization

In fields like drug discovery or automated programming, the goal is to generate sequences that maximize a specific property, such as a molecule's solubility or a code snippet's accuracy. However, these sequences live in a discrete space where you cannot simply "nudge" a character to smoothly improve the result.

Existing methods typically face a strict trade-off between validity and optimization:

  1. Unconstrained models (e.g., standard GANs or VAEs): These often generate high-scoring sequences that are syntactically "broken" (like a molecule with impossible chemical bonds).
  2. Grammar-constrained models: These use hand-crafted rules to force validity. However, these rules are hard to design for new domains and can restrict the model's "creativity," leading to lower-quality optimization results.

The authors aim to bridge this gap by allowing the model to explore the space freely while mathematically enforcing a high probability (a "chance") that the generated sequences remain valid.

Methods: Chance-Constrained Optimization

The core innovation of CCGF is formulating sequence generation as a Chance-Constrained Optimization (CCO) problem.

  • The Chance Constraint: Instead of a hard rule, the authors set a target: "The probability of generating an invalid sequence must be less than $\epsilon$."
  • Making it Tractable: Probabilistic constraints are notoriously difficult to optimize. The authors use the Chernoff bound to transform this "chance" into a deterministic, differentiable objective function.
  • The Minimax Algorithm: They propose a novel training objective where the model plays a game. It tries to maximize the desired property while a learnable parameter ($\alpha$) adjusts to tighten the bound on validity.
  • Architecture: The generator is a Recurrent Neural Network (specifically a GRU). To prevent the model from simply generating the same "perfect" sequence over and over (mode collapse), they incorporate an adversarial discriminator that rewards diversity.
  • Training: The model is trained using the REINFORCE algorithm, a standard reinforcement learning technique, to handle the non-differentiable nature of discrete sequences.

Datasets and Tasks

The authors evaluated CCGF across three distinct domains to prove its versatility:

  1. Arithmetic Expressions: Searching for mathematical strings that match a target output curve.
Target curve matching for arithmetic expressions
  1. Short Python Programs: Using 130,000 univariate programs where the goal is to generate code that executes correctly and matches a target function.
  2. ZINC Molecular Dataset: Using 250,000 drug-like molecules. The task was to optimize for Solubility (penalized logP) and Druglikeness (QED).

Key Insights

  • The "Simulated Annealing" Effect: One of the most interesting findings is that starting with a loose validity requirement allows the model to explore a wide range of sequences early in training. As training progresses, the "chance constraint" naturally tightens, funneling the model into valid, high-performing regions of the search space. This dynamic helps the agent escape local optima.
  • Grammar Agnosticism: Unlike previous state-of-the-art methods (like GVAE or SD-VAE), CCGF doesn't need grammar rules baked into its architecture. It only needs a "validator" (like a compiler or a chemical software kit) to tell it if a sequence is valid or not.
  • Sequence vs. Graph: Historically, graph-based models have outperformed sequence-based models in chemistry. CCGF shows that by properly handling constraints, sequence-based models—which are often simpler to implement—can actually match or beat graph-based performance.

Key Results

CCGF consistently outperformed existing sequence-based baselines and even challenged specialized graph-based models:

  • Validity: In the Python task, CCGF achieved 99.5% validity, whereas standard VAEs plummeted to near 0%.
  • Optimization: On the ZINC dataset for penalized logP (solubility), CCGF achieved a top score of 12.32, outperforming the previous sequence-based best (4.04) and even the state-of-the-art graph-based model, GraphAF (12.23).
Performance comparison on the ZINC dataset for molecular optimization
  • Diversity: By using an adversarial diversity loss, the model maintained high novelty (100% of generated molecules were new) and better diversity scores than most competitors.

Limitations and Future Work

  • The Diversity Trade-off: The authors acknowledge that as you push for higher property scores, diversity naturally tends to drop. While their discriminator helps, balancing "perfection" with "variety" remains an ongoing challenge.
  • Validator Dependence: The framework requires a binary "valid/invalid" function. In domains where validity is subjective or extremely expensive to compute, this approach might struggle.
  • Future Directions: The authors suggest that this framework could be extended to handle multiple complex constraints simultaneously (e.g., "Make this molecule soluble AND non-toxic AND easy to synthesize").

Summary updated

Abstract

Deep generative modeling has achieved many successes for continuous data generation, such as producing realistic images and controlling their properties (e.g., styles). However, the development of ...
BibTeX
@inproceedings{liu2020chance,
  author = {Xianggen Liu and Qiang Liu and Sen Song and Jian Peng},
  title = {{A Chance-Constrained Generative Framework for Sequence Optimization}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=uR23c25ZWrj},
}
Figure