Revisiting Reweighted Wake-Sleep for Models with Stochastic Control Flow

Tuan Anh Le, Adam R. Kosiorek, N. Siddharth, Yee Whye Teh, Frank Wood

TL;DR

This paper demonstrates that the classic Reweighted Wake-Sleep (RWS) algorithm is a superior alternative to modern state-of-the-art methods for training generative models with discrete branching, known as Stochastic Control-Flow Models (SCFMs). Unlike the popular Importance Weighted Autoencoder (IWAE), RWS scales effectively with more computational power, leading to better generative models and more accurate inference networks as the number of particles increases.

What Problem Does This Paper Address?

Many powerful generative models involve discrete choices that change the "path" of computation—think of an if/else statement in a program where the condition is a random variable. These are Stochastic Control-Flow Models (SCFMs). Examples include probabilistic programs, models that count objects in a scene, or grammars for natural language.

Training these models is notoriously difficult. The standard "reparameterization trick" used in Variational Autoencoders (VAEs) relies on continuous relaxations (like Gumbel-Softmax). However, in an SCFM, a relaxed variable isn't just 0 or 1; it's a value in between. To compute a gradient, you would have to evaluate every possible branch of the program simultaneously, which leads to an exponential explosion in computation (see Figure 2).

Figure 2: The challenge faced by continuous-relaxation meth- ods on SCFMs—requiring exploration of all branches, in con- trast to exploring only one branch at a time. Stochastic control flow proceeds through discrete choices (ci) yielding values (vi).

Current alternatives usually involve REINFORCE-based gradients with complex "control variates" (like VIMCO) to reduce noise. But these methods have a major flaw: as you increase the number of samples (particles) to get a better estimate, the quality of the inference network can actually degrade.

Methods

The authors revisit Reweighted Wake-Sleep (RWS). Unlike IWAE, which tries to optimize a single objective for both the model ($\theta$) and the inference network ($\phi$), RWS alternates between them:

  1. Wake-phase $\theta$ update: Updates the generative model to better explain the data using importance sampling.
  2. $\phi$ update: Updates the inference network to match the true posterior. This can be done using data from the real world (Wake-Wake or WW) or data generated by the model (Wake-Sleep or WS).

The key technical advantage is that RWS targets the $KL(p || q)$ divergence. This encourages "mean-seeking" behavior, which is ideal for importance sampling because it ensures the inference network covers all the modes of the true posterior.

The authors also introduce $\delta$-WW, a variant that uses "defensive importance sampling" by mixing the inference network's proposal with a uniform distribution. This prevents "branch pruning," a failure mode where the model prematurely decides certain paths have zero probability and never explores them again.

Datasets

The authors evaluate RWS across three distinct types of SCFMs:

  • Probabilistic Context-Free Grammar (PCFG): Using the "Astronomers" grammar to model sentence structures. This is a classic SCFM where recursion can lead to infinite paths, making relaxations impossible.
  • Attend, Infer, Repeat (AIR): A complex vision model trained on multi-digit MNIST images. It must decide how many digits are in an image and where they are located.
  • Gaussian Mixture Model (GMM): A pedagogical 1D example used to precisely analyze failure modes like branch pruning.

Key Insights and Ideas

  • Monotonic Scaling: The most significant finding is that RWS improves monotonically as you add more particles ($K$). In contrast, methods like VIMCO often peak at a small $K$ and then perform worse as $K$ increases (see Figure 5).
  • The "Right" KL Divergence: By targeting $KL(p || q)$ instead of the $KL(q || p)$ used in standard VAEs, RWS creates inference networks that are better suited as importance sampling proposals.
  • Overcoming Branch Pruning: The proposed $\delta$-WW variant is crucial for robustness. By ensuring a baseline level of exploration (via the uniform mixture), it prevents the model from getting stuck in poor local optima during early training.
Figure 5: Training of AIR. (Left) Training curves: training with VIMCO leads to larger variance in training than WW. (Middle) Log evidence values at the end of training: increasing number of particles improves WW monotonically but improves VIMCO only up to a point (K = 10 is the best). (Right) WW results in significantly lower variance and better inference networks than VIMCO. Note that KL is between the inference network and the current generative model.

Key Results

  • PCFG: RWS (specifically the WS variant) significantly outperformed VIMCO and REINFORCE. While VIMCO failed to improve with more particles, RWS achieved much lower errors in both model learning and inference (see Figure 3).
  • AIR: WW achieved higher log-evidence and lower variance than VIMCO. As shown in Figure 5, WW results in significantly better inference networks (lower KL divergence to the posterior).
  • GMM: The experiments showed that while standard RWS can suffer from branch pruning in low-particle regimes, the $\delta$-WW variant consistently finds the global optimum.
Figure 3: PCFG training. (Top) Quality of the generative model: While all methods have the same gradient update for θ, the performance of WS improves and is the best as K is increased. Other methods, including WW, do not yield significantly better model learning as K is increased, since WS’s inference network learns the fastest. (Bottom) Quality of the inference network: VIMCO and REINFORCE do not improve with increasing K. WS performs best as K is increased, and while WW’s performance improves, the improvement is not as significant. This can be attributed to the data-distribution bias being less significant than the bias coming from self-normalized IS (c.f. § 3.3). Median and interquartile ranges from up to 10 repeats shown (see text).

Limitations and Future Work

The primary limitation of RWS is that its gradient estimators for the inference network are biased (though they are "consistent," meaning the bias disappears as you add more particles).

The authors note that the choice between the "Wake-Wake" and "Wake-Sleep" variants depends on the specific model: WW is better when the data distribution is complex, while WS is better when the inference task itself is extremely difficult (like in the PCFG). Future work could involve automated ways to balance these two phases or developing more sophisticated defensive sampling strategies.

Summary updated

Abstract

Stochastic control-flow models (SCFMs) are a class of generative models that involve branching on choices from discrete random variables. Amortized gradient-based learning of SCFMs is challenging as most approaches targeting discrete variables rely on their continuous relaxations---which can be intractable in SCFMs, as branching on relaxations requires evaluating all (exponentially many) branching paths. Tractable alternatives mainly combine REINFORCE with complex control-variate schemes to improve the variance of naive estimators. Here, we revisit the reweighted wake-sleep (RWS) (Bornschein and Bengio, 2015) algorithm, and through extensive evaluations, show that it outperforms current state-of-the-art methods in learning SCFMs. Further, in contrast to the importance weighted autoencoder, we observe that RWS learns better models and inference networks with increasing numbers of particles. Our results suggest that RWS is a competitive, often preferable, alternative for learning SCFMs.
BibTeX
@inproceedings{le2019revisiting,
  author = {Tuan Anh Le and Adam R. Kosiorek and N. Siddharth and Yee Whye Teh and Frank Wood},
  title = {{Revisiting Reweighted Wake-Sleep for Models with Stochastic Control Flow}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=yFaEbwO7mv6},
}
Figure