Learning Restricted Boltzmann Machines with Few Latent Variables
Learning Restricted Boltzmann Machines with Few Latent Variables
复制标题
学习具有很少潜在变量的受限玻尔兹曼机
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Rares
中科院分区：
文献类型：
--
作者：
Guy Bresler;Rares
受限玻尔兹曼机（RBM）是一种常见的带有潜变量的无向图模型。RBM由二分图描述，所有观测变量在一层，所有潜变量在另一层。我们考虑学习RBM的任务，给出根据它生成的样本。 对于铁磁RBM的ilde{O}（n^2）$（即，有吸引力的潜力），但$ ilde{O}（n^d）$，其中$n$是观察变量的数量，$d$是潜变量的最大程度。设观测变量的MRF邻域是其在观测变量的边际分布的马尔可夫随机场中的邻域。本文给出了一个具有时间复杂度的一般RBM学习算法。 ilde{O}（n^{2^s+1}）$，其中$s$是连接到观测变量的MRF邻域的潜在变量的最大数量。这表示当$s<log_2（d-1）$时的改进，这被具有“很少潜在变量”的许多类别的RBM所满足。此外，我们给出了这个学习算法的一个版本，该算法可以恢复具有小预测误差的模型，并且其样本复杂度与观测变量的马尔可夫随机场中的最小势无关。这是感兴趣的，因为当前算法的样本复杂度与最小势的倒数成比例，这不能根据RBM的自然属性来控制。
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 $ ilde{O}(n^2)$ for ferromagnetic RBMs (i.e., with attractive potentials) but $ ilde{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 $ ilde{O}(n^{2^s+1})$, where $s$ is the maximum number of latent variables connected to the MRF neighborhood of an observed variable. This represents an improvement when $s<log_2 (d-1)$, which is satisfied by many classes of RBMs with"few 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.