Convergence of the Wake-Sleep Algorithm

Shiro Ikeda, Shun-ichi Amari, Hiroyuki NakaharaNeurIPS 1998

Introduction

This paper provides the first theoretical proof of convergence for the Wake-Sleep (W-S) algorithm when applied to factor analysis models. By leveraging information geometry, the authors demonstrate that while the W-S algorithm differs fundamentally from the Expectation-Maximization (EM) algorithm due to the asymmetry of Kullback-Leibler (KL) divergence, it still converges to the Maximum Likelihood Estimator (MLE) as long as the recognition model is "realizable."

The Problem: Wake-Sleep vs. EM

In the late 90s, the Wake-Sleep algorithm gained traction as a biologically plausible, Hebbian-style learning rule for neural networks with hidden variables (such as the Helmholtz machine). While computationally simpler than the standard Expectation-Maximization (EM) algorithm, it lacked a solid theoretical foundation.

Researchers observed that W-S worked well for linear models like Factor Analysis, but no one had proven why it converged or if it would always reach the MLE. The primary challenge lies in the "Sleep" phase: unlike EM, which optimizes a rigorous lower bound on log-likelihood, the Sleep phase in W-S follows a different gradient that does not obviously lead to the same destination.

Methods: An Information Geometry Perspective

The authors use Information Geometry to dissect the algorithm, treating the generative and recognition models as points on two different manifolds:

  1. Model Manifold ($M$): Represents the generative model (how the world creates data).
  2. Data Manifold ($D$): Represents the recognition model (how the brain/machine perceives the data).
Information Geometry of EM

The core of their analysis involves the Kullback-Leibler (KL) divergence, a measure of how one probability distribution differs from another. By modeling the algorithm's updates as continuous-time differential equations (gradient flows), the authors analyze whether the distinct paths of EM and W-S eventually meet at the same point.

(Note: As a theoretical paper focused on mathematical proofs and algorithmic behavior, no empirical datasets were used. The analysis is performed on a generalized Factor Analysis model, serving as a linear proxy for more complex Helmholtz machines.)

Key Insights and Ideas

The KL Asymmetry

The most profound insight is that the W-S algorithm is not just a stochastic version of EM. There is a crucial asymmetry in how they handle KL divergence:

  • EM Algorithm: Effectively minimizes $KL(q \| p)$—adjusting the recognition model ($q$) to match the generative model ($p$).
  • Wake-Sleep Algorithm: The Sleep phase minimizes $KL(p \| q)$—adjusting the recognition model to match samples generated by the "dreaming" generative model.
KL Asymmetry in Wake-Sleep

Because $KL(p \| q) \neq KL(q \| p)$, the Sleep phase moves the recognition model in a direction that is technically "wrong" from the perspective of standard maximum likelihood theory.

Realizability is Key

Despite this "wrong" direction, the authors show that W-S converges to the MLE specifically because, in a linear factor analysis model, the recognition model is "realizable." This means the recognition model has enough flexibility to perfectly represent the true posterior distribution of the generative model.

The "Sleep Well" Strategy

They suggest that if a model "sleeps well" (reaches convergence in the sleep phase before starting the wake phase), it becomes equivalent to a Generalized EM (GEM) algorithm, guaranteeing a path to the MLE.

Key Results

  • Convergence Proof: The authors successfully prove that for a factor analysis model, the W-S algorithm's parameters will converge to the MLE.
  • Condition for General Models: They identify the necessary condition for W-S to work in more complex, non-linear models: the recognition model must be able to realize the generative model's posterior. If the recognition model is too simple (e.g., a linear recognition model for a non-linear generative model), W-S will fail to find the true MLE.

Limitations and Future Work

  • Non-linear Limitations: The paper demonstrates via a simple example that if the recognition model uses a non-linear function that cannot match the generative process, the W-S algorithm and EM will converge to different points. This suggests W-S may be less robust than EM in restricted architectures.
  • Stochasticity: While the paper uses continuous-time flows for the proof, the actual W-S algorithm is stochastic (sampling-based). The authors acknowledge the "stochastic sense" of the wake-phase but focus their proof on the underlying deterministic averages.
  • Future Directions: The work opens the door for designing better recognition models tailored to satisfy the "realizability" condition, ensuring that simple Hebbian learning rules remain mathematically sound.

Summary updated

BibTeX
@inproceedings{ikeda1998convergence,
  author = {Shiro Ikeda and Shun-ichi Amari and Hiroyuki Nakahara},
  title = {{Convergence of the Wake-Sleep Algorithm}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1998},
}
Figure