Unsupervised Program Synthesis for Images By Sampling Without Replacement

Chenghui Zhou, Chun-Liang Li, Barnabás Póczos

TL;DR

This paper introduces the first purely unsupervised method for parsing images into programs (specifically, Constructive Solid Geometry or CSG programs) without needing any pre-training data. By combining a grammar-aware neural network with novel sampling and exploration techniques, the model can learn to generate valid programs directly from target images, outperforming supervised methods in generalization and achieving competitive results on complex datasets.

What Problem Does This Paper Address?

Parsing images into programs, particularly for tasks like generating 3D models from 2D representations (e.g., CSG), has shown great promise. However, existing methods typically rely on a two-stage process: first, training a model on a large dataset of synthetic image-program pairs, and then fine-tuning it with reinforcement learning (RL) on real images. This pre-training step is data-intensive and can limit the model's ability to generalize to new, unseen image types. Furthermore, purely RL-based approaches have struggled due to the vast and sparse search space of valid programs, making it difficult for the model to discover good solutions. This paper tackles the challenge of achieving effective program synthesis for images in a completely unsupervised manner, eliminating the need for pre-training and directly learning from the target domain.

Methods

The core of the proposed method lies in a novel combination of techniques designed to overcome the sparsity and exploration challenges in unsupervised program synthesis:

  • Grammar-Encoded Tree LSTM: To ensure that generated programs are syntactically valid, the authors employ a Tree-LSTM architecture that is explicitly conditioned on the grammar rules of the target language. This constrains the model's output space, guiding it to produce well-formed programs.
  • Entropy Regularization: To encourage exploration of the vast program search space, the model incorporates an entropy regularization term into its objective function. This incentivizes the model to explore diverse program structures rather than getting stuck in local optima.
  • Sampling Without Replacement (SWOR): Instead of standard Monte Carlo sampling, the paper proposes using sampling without replacement from the grammar's syntax tree. This technique, combined with a Gumbel trick for stochastic beam search, leads to more efficient and accurate entropy estimation and a more stable RL objective, ultimately accelerating convergence.
  • Non-Differentiable Renderer: The system uses a non-differentiable renderer to translate generated programs back into images for comparison with the target image. This is a crucial aspect as many real-world design tools are non-differentiable, making gradient-based optimization challenging. The reward signal is derived from the difference between the rendered and target images.

Datasets

The paper evaluates its approach on two main types of datasets:

  • Synthetic 2D CSG Dataset: This dataset is generated using the defined context-free grammar (CFG) for Constructive Solid Geometry. It includes images of varying complexity based on program length.
  • 2D CAD Furniture Dataset: This dataset consists of real-world 2D CAD images of furniture items. Importantly, these images are not generated by the specific CFG used in the synthetic dataset, making it a more challenging testbed for generalization.

Key Insights and Ideas

  • Unsupervised Program Synthesis is Feasible: The most significant insight is that effective program synthesis for images can be achieved without any supervised pre-training, challenging previous assumptions.
  • Grammar as a Constraint is Powerful: Explicitly encoding grammar rules into the neural network architecture (Grammar-Encoded Tree LSTM) is crucial for generating valid programs and significantly prunes the search space.
  • Exploration is Key for Sparse Rewards: In the context of program synthesis with non-differentiable renderers, the inherent sparsity of meaningful programs necessitates robust exploration strategies, which entropy regularization and SWOR effectively provide.
  • Sampling Without Replacement Improves RL: The proposed SWOR technique, when applied to program generation, leads to better entropy estimates and a more stable RL optimization process, outperforming standard sampling methods.
  • Generalization Beyond Training Data: The unsupervised approach demonstrates superior generalization capabilities compared to supervised methods, especially on datasets that deviate from the pre-training distribution.

Key Results

  • Synthetic Dataset Performance: The unsupervised algorithm generalizes better than supervised methods on the synthetic 2D CSG dataset.
  • 2D CAD Dataset Performance: On the 2D CAD furniture dataset, the unsupervised approach significantly outperforms a supervised pre-trained model and is competitive with refined models. Specifically, the unsupervised model achieves a Chamfer Distance reward of 1.48-1.51 across different beam search configurations, outperforming supervised models which range from 1.50-3.64 depending on the pre-training data size.
  • Ablation Studies: Removing any of the three key components (grammar-encoded tree LSTM, entropy regularization, or SWOR) significantly degrades performance, highlighting the importance of each element.
  • Entropy Estimation Variance: The paper empirically verifies that their proposed stepwise entropy estimator (ĤD) has lower variance than the naive estimator (Ĥ), as theoretically proven.

Limitations and Future Work

  • Approximation on CAD Data: While competitive, the model's reconstructions on the CAD dataset sometimes approximate thin lines with triangles, suggesting that the Chamfer Distance reward function, which relies on nearest features, might not perfectly capture all geometric nuances.
  • Future Work: The authors suggest that further improvements could be made by exploring more sophisticated reward functions or by incorporating additional information about the target domain. The current work focuses on 2D images, and extending it to 3D program synthesis would be a natural next step. The paper also hints at the potential for this approach in other domains where program synthesis from visual input is relevant.

Summary updated

Abstract

Program synthesis has recently emerged as a promising approach to the image parsing task. Most prior work has followed a two-step pipeline that involves supervised pretraining of a sequence-to-sequence model on synthetic programs, followed by reinforcement learning to fine-tune the model on real reference images. A purely RL-driven approach without supervised pretraining has never proven successful, since useful programs are too sparse in the program space to sample from. In this paper, we present the first purely unsupervised learning algorithm that parses constructive solid geometry (CSG) images into context-free grammar (CFG) without pretraining. The key ingredients of our approach include entropy regularization and sampling without replacement from the CFG syntax tree, both of which encourage exploration of the search space, and a grammar-encoded tree LSTM that enforces valid outputs. We demonstrate that our unsupervised method can generalize better than supervised training on a synthetic 2D CSG dataset. Additionally, we find that training in this way naturally optimizes the quality of the top-$k$ programs, leading our model to outperform existing method on a 2D computer aided design (CAD) dataset under beam search.
BibTeX
@inproceedings{zhou2021unsupervised,
  author = {Chenghui Zhou and Chun-Liang Li and Barnabás Póczos},
  title = {{Unsupervised Program Synthesis for Images By Sampling Without Replacement}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=ZJBE4sOYmjG},
}
Figure