Unsupervised Program Synthesis for Images using Tree-Structured LSTM

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

TL;DR

This paper introduces the first fully unsupervised algorithm capable of parsing geometric images into human-readable programs without any supervised pretraining. By combining a grammar-constrained tree LSTM with a novel entropy estimator and sampling without replacement, the authors overcome the "sparse reward" problem, allowing the model to learn directly from target images and generalize better than traditional supervised methods.

What Problem Does This Paper Address?

Program synthesis for images—the task of converting a picture into a set of geometric instructions (like "draw a circle at $x,y$")—is traditionally a two-step process. Researchers first train a model on a massive, curated dataset of synthetic images and their corresponding "ground-truth" programs. Then, they fine-tune this model using Reinforcement Learning (RL) on real-world images.

This approach has two major flaws:

  1. Program Aliasing: Supervised learning (via Maximum Likelihood Estimation) penalizes the model for finding a correct program if it doesn't exactly match the one specific program in the training set.
  2. Generalization Gap: Models trained on synthetic distributions often fail when faced with real-world images (like CAD designs) that don't perfectly follow the synthetic rules.

Fully unsupervised learning would solve this, but it’s notoriously difficult. In the massive search space of possible programs (up to $10^{28}$ combinations), finding a program that actually draws something meaningful is like finding a needle in a haystack. Without a "warm start" from supervised data, standard RL agents usually fail to learn anything at all.

Methods

The authors propose a purely RL-driven approach that uses three key ingredients to make unsupervised learning feasible:

  • Grammar-Encoded Tree LSTM: Instead of a standard sequence model, they use a Tree LSTM that follows a Context-Free Grammar (CFG). This ensures that every program the model samples is syntactically valid, drastically shrinking the search space. It uses an internal "image stack" to keep track of intermediate shapes as it builds the program.
Figure 1: This is an example of the grammar encoded tree LSTM at work. The top layer of images demonstrates the image stack and the bottom layer demonstrates the grammar stack. The blue, orange, yellow and green colored LSTM cell generates grammatical tokens according to the CFG rule 1, 2, 3 and 4 respectively. In implementation, we can constrain the output space by adding a mask to the output of the LSTM and render the invalid options with close to zero probability of being sampled.
  • Decomposed Entropy Estimator ($H_D$): To encourage the model to explore new programs, the authors use entropy regularization. They derive a new "stepwise" entropy estimator specifically for syntax trees. They mathematically prove that this estimator has lower variance than standard methods, leading to more stable training.
  • Sampling Without Replacement (SWOR): Standard RL samples programs with replacement, meaning it might waste time evaluating the same program twice. By using a stochastic beam search (the Gumbel-top-k trick), the model samples distinct programs in every batch. This significantly accelerates exploration.

Datasets

The model was evaluated on two main benchmarks:

  1. Synthetic 2D CSG Dataset: Images generated from Constructive Solid Geometry (CSG) primitives (circles, squares, triangles) with program lengths of 5, 7, and 9.
  2. 2D CAD Furniture Dataset: A more challenging dataset of binary images representing real-world furniture. Crucially, these images were not generated by the model's grammar, testing its ability to approximate complex shapes it hasn't seen before.

Key Insights and Ideas

  • Unsupervised > Supervised for Generalization: Because the unsupervised model isn't tethered to a specific "ground truth" program, it can find multiple ways to represent the same shape. This flexibility allows it to generalize much better to novel datasets like CAD furniture.
  • The Power of SWOR: The authors demonstrate that sampling 20 distinct programs (SWOR) is more effective for exploration than sampling 40 programs where duplicates are allowed (SWR). As shown in the entropy plots, SWOR pushes the model toward a uniform distribution (maximum exploration) much faster.
Comparison of entropy increase: Sampling Without Replacement (SWOR) explores the space more efficiently than standard sampling.
  • Ablation Matters: The "aha moment" here is that all three components are necessary. Removing the grammar constraints makes the reward too sparse; removing entropy or SWOR causes the model to get stuck in local optima (Figure 4).

Key Results

  • Synthetic Performance: On the CSG dataset, the unsupervised model achieved near-perfect reconstruction scores (Chamfer rewards of 0.96–0.98), outperforming supervised models which struggled as program complexity increased.
  • CAD Generalization: On the 2D CAD dataset, the unsupervised model significantly outperformed a supervised model trained on 300k programs and achieved results competitive with models that had been extensively fine-tuned.
  • Qualitative Success: The model successfully parsed complex furniture shapes into simple geometric programs, capturing the "essence" of the objects even when the exact primitives didn't exist in its grammar.
Figure 2: The left most image demonstrates the entropy value increases over 700 iterations by sampling 20 distinct samples with and without replacement as well as sampling 40 samples with replacement. The second image shows the initial distribution. The third and fourth images show the final distributions.

Limitations and Future Work

  • Greedy Rewards: The reward function (Chamfer Distance) is a greedy algorithm. The authors noted that it sometimes causes the model to approximate thin lines using triangles rather than more appropriate primitives because it finds the "nearest feature" rather than the global structure.
  • Complexity Scaling: While the model handles search spaces up to $10^{28}$, even larger or more complex 3D environments would likely require even more efficient sampling strategies or hierarchical grammar structures.
  • Renderer Dependency: The model relies on a non-differentiable renderer as a black box. While this is a strength (it works with standard software like Blender), it means the model cannot benefit from gradient information directly from the pixels.

Summary updated

Abstract

Program synthesis has emerged as a successful approach to the image parsing task. Most prior works rely on a two-step scheme involving supervised pretraining of a Seq2Seq model with synthetic programs followed by reinforcement learning (RL) for fine-tuning with real reference images. Fully unsupervised approaches promise to train the model directly on the target images without requiring curated pretraining datasets. However, they struggle with the inherent sparsity of meaningful programs in the search space. In this paper, we present the first unsupervised algorithm capable of parsing constructive solid geometry (CSG) images into context-free grammar (CFG) without pretraining via non-differentiable renderer. To tackle the \emph{non-Markovian} sparse reward problem, we combine three key ingredients -- (i) a grammar-encoded tree LSTM ensuring program validity (ii) entropy regularization and (iii) sampling without replacement from the CFG syntax tree. Empirically, our algorithm recovers meaningful programs in large search spaces (up to $3.8 \times 10^{28}$). Further, even though our approach is fully unsupervised, it generalizes better than supervised methods on the synthetic 2D CSG dataset. On the 2D computer aided design (CAD) dataset, our approach significantly outperforms the supervised pretrained model and is competitive to the refined model.
BibTeX
@inproceedings{zhou2021unsupervised,
  author = {Chenghui Zhou and Chun-Liang Li and Barnabás Póczos},
  title = {{Unsupervised Program Synthesis for Images using Tree-Structured LSTM}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=ZJBE4sOYmjG},
}

Loading related content...

Figure