Towards Maximum Likelihood: Learning Undirected Graphical Models using Persistent Sequential Monte Carlo.

Hanchen Xiong, Sándor Szedmák, Justus H. PiaterACML 2014 · OpenReview

Abstract

Along with the emergence of algorithms such as persistent contrastive divergence (PCD), tempered transition and parallel tempering, the past decade has witnessed a revival of learning undirected graphical models. However, training these models remains difficult when the model distributions become complex or learning rates are high. This paper introduces Persistent Sequential Monte Carlo (PSMC), a robust framework that treats the learning process as an adaptive sequence of tempered distributions. By maintaining a persistent set of particles and adaptively bridging the gap between model updates, PSMC achieves more stable and accurate learning than existing state-of-the-art methods.

Introduction

Undirected Graphical Models (UGMs), also known as Markov Random Fields, are essential for capturing complex dependencies in high-dimensional data. Learning the parameters of these models typically relies on Maximum Likelihood (ML) estimation via gradient ascent. This process is bifurcated into two phases: the positive phase, which lowers the energy of observed data, and the negative phase, which raises the energy of the rest of the configuration space.

The negative phase is notoriously difficult because it requires calculating an expectation over the model distribution, a task hindered by an intractable normalization constant known as the partition function. While Markov Chain Monte Carlo (MCMC) methods are used to approximate this expectation, they often struggle with slow convergence. Persistent Contrastive Divergence (PCD) attempted to solve this by maintaining "persistent" chains across iterations. However, PCD is fragile; it often diverges if the learning rate is too high or if the model becomes multi-modal, causing samples to become trapped in local energy minima.

Persistent Sequential Monte Carlo (PSMC)

This paper proposes Persistent Sequential Monte Carlo (PSMC) to address the limitations of PCD. The core innovation lies in re-interpreting the Stochastic Approximation Procedure (SAP) used in learning as a Sequential Monte Carlo process.

Learning as a Particle Filter

In PSMC, the samples tracked during the negative phase are treated as "particles" evolving through a sequence of changing distributions. As the model parameters $\theta$ are updated from $\theta_t$ to $\theta_{t+1}$, the target distribution shifts. PSMC ensures that the particles accurately represent the new distribution by constructing a path of intermediate "tempered" distributions.

Tempered Intermediary Distributions

The "gap" between $\theta_t$ and $\theta_{t+1}$ can be significant, especially with large learning rates. PSMC bridges this gap using global tempering. By introducing a temperature-like parameter $\beta$, the algorithm smooths the distribution, allowing particles to explore the space more effectively and preventing them from getting stuck in the "energy wells" of the previous iteration's model.

Adaptive Step Sizes and ESS

A critical feature of PSMC is its lack of reliance on fixed hyperparameters for tempering. Instead, it monitors the Effective Sample Size (ESS), a metric that indicates how well the current particles represent the target distribution. If the ESS drops below a certain threshold—indicating particle degeneracy—the algorithm performs a bidirectional search to find an optimal step size ($\Delta \beta$). This adaptive mechanism ensures that the "bridge" between model updates is always sturdy enough to carry the particles across without losing sample quality.

Experimental Evaluation

The authors evaluated PSMC against PCD and Parallel Tempering (PT) using both synthetic and real-world datasets.

Synthetic Fully Visible Boltzmann Machines (VBMs)

Using a 10-variable VBM, the authors could calculate exact log-likelihoods. This provided a ground truth to measure how closely each algorithm approached the true ML solution. PSMC demonstrated superior stability, particularly when using aggressive learning rate schedules that caused PCD to fluctuate wildly or fail to converge.

MNIST and Restricted Boltzmann Machines (RBMs)

On the MNIST handwritten digit dataset, the authors tested RBMs of varying scales. In a large-scale RBM (784 visible units, 500 hidden units), PSMC achieved a training log-likelihood of -161.62. This outperformed PCD-200 (-173.00) and Parallel Tempering (-165.21). Notably, standard SMC failed on this task because its particles were depleted as the distribution grew more complex, whereas PSMC’s persistence and adaptive tempering allowed it to succeed.

Discussion and Conclusion

The primary insight of this work is the "entanglement" of learning and sampling in UGMs. Biased gradients from poor sampling lead to poor models, which in turn make sampling even harder. PSMC breaks this cycle by providing a robust sampling framework that is significantly more resilient to hyperparameter choices, such as the learning rate.

While PSMC introduces additional computational overhead per iteration due to the intermediate steps and ESS calculations, this is offset by its stability and the reduced number of total epochs required for convergence. Future work may involve integrating more sophisticated MCMC transition kernels to further improve particle mixing or extending the framework to Maximum A Posteriori (MAP) learning.

In summary, PSMC represents a significant step toward more reliable Maximum Likelihood learning for complex undirected models, offering a principled way to maintain sample quality throughout the training process.

Summary updated

Abstract

Along with the emergence of algorithms such as persistent contrastive divergence (PCD), tempered transition and parallel tempering, the past decade has witnessed a revival of learning undirected gr...
BibTeX
@inproceedings{xiong2014towards,
  author = {Hanchen Xiong and Sándor Szedmák and Justus H. Piater},
  title = {{Towards Maximum Likelihood: Learning Undirected Graphical Models using Persistent Sequential Monte Carlo.}},
  booktitle = {ACML},
  year = {2014},
  url = {https://openreview.net/forum?id=wqkH6ofM7tX},
}
Figure