Learning Restricted Boltzmann Machines with Sparse Latent Variables

Abstract

Restricted Boltzmann Machines (RBMs) are a common family of undirected graphical models with latent variables. An RBM is described by a bipartite graph, with all observed variables in one layer and all latent variables in the other. We consider the task of learning an RBM given samples generated according to it. The best algorithms for this task currently have time complexity $\tilde{O}(n^2)$ for ferromagnetic RBMs (i.e., with attractive potentials) but $\tilde{O}(n^d)$ for general RBMs, where $n$ is the number of observed variables and $d$ is the maximum degree of a latent variable. Let the MRF neighborhood of an observed variable be its neighborhood in the Markov Random Field of the marginal distribution of the observed variables. In this paper, we give an algorithm for learning general RBMs with time complexity $\tilde{O}(n^{2^s+1})$, where $s$ is the maximum number of latent variables connected to the MRF neighborhood of an observed variable. This is an improvement when $s<{\log }_2(d-1)$, which corresponds to RBMs with sparse latent variables. Furthermore, we give a version of this learning algorithm that recovers a model with small prediction error and whose sample complexity is independent of the minimum potential in the Markov Random Field of the observed variables. This is of interest because the sample complexity of current algorithms scales with the inverse of the minimum potential, which cannot be controlled in terms of natural properties of the RBM.

arXiv comment33 pages, to appear at NeurIPS 2020

References in corpus (7)

• Latent variable graphical model selection via convex optimization
• Restricted-Boltzmann-Machine Learning for Solving Strongly Correlated Quantum Systems
• Higher order concentration for functions of weakly dependent random variables
• Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models
• Learning loopy graphical models with latent variables: Efficient methods and guarantees
• Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications
• Structure learning of antiferromagnetic Ising models

Cited by in corpus (1)

• Learning Exponential Family Graphical Models with Latent Variables using Regularized Conditional Likelihood