Learning restricted Boltzmann machines via influence maximization
Learning restricted Boltzmann machines via influence maximization
复制标题
通过影响力最大化学习受限玻尔兹曼机
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Elchanan Mossel
中科院分区：
文献类型：
--
作者：
Guy Bresler;Frederic Koehler;Ankur Moitra;Elchanan Mossel
图形模型是一种丰富的语言，用于描述其依赖性结构的高维分布。尽管有可证明的保证算法可以在各种设置中学习无向图形模型，但是在有潜在变量时，重要情况下的进展要少得多。在这里，我们研究了受限制的Boltzmann机器（或RBMS），这是一个流行的模型，具有较大的应用程序，可在维度降低，协作过滤，主题建模，功能提取和深度学习方面进行广泛应用。我们论文的主要信息是在学习RBM的可行性中进行的强大二分法，具体取决于变量之间相互作用的性质：铁磁模型可以有效地学习，而通用模型则不能。特别是，我们基于影响最大化的影响，以限制性学习铁磁rbms，给出了一种简单的贪婪算法。实际上，我们了解了观察到的变量上的分布作为马尔可夫随机字段的描述。我们的分析是基于从数学物理学的工具中开发出来的，这些工具是为了显示磁化的凹入性。我们的算法直接扩展到具有潜在变量的一般铁磁模型。相反，我们表明，即使对于具有恒定程度的偏见数量的潜在变量，也没有铁磁性，问题就像与噪声稀疏的奇偶校验一样困难。该硬度结果是基于有限度rbms的代表力的尖锐而令人惊讶的表征：其观察到的变量上的分布可以模拟任何有限的秩序MRF。该结果具有独立的兴趣，因为RBMS是深信网络的基础。
Graphical models are a rich language for describing high-dimensional distributions in terms of their dependence structure. While there are algorithms with provable guarantees for learning undirected graphical models in a variety of settings, there has been much less progress in the important scenario when there are latent variables. Here we study Restricted Boltzmann Machines (or RBMs), which are a popular model with wide-ranging applications in dimensionality reduction, collaborative filtering, topic modeling, feature extraction and deep learning. The main message of our paper is a strong dichotomy in the feasibility of learning RBMs, depending on the nature of the interactions between variables: ferromagnetic models can be learned efficiently, while general models cannot. In particular, we give a simple greedy algorithm based on influence maximization to learn ferromagnetic RBMs with bounded degree. In fact, we learn a description of the distribution on the observed variables as a Markov Random Field. Our analysis is based on tools from mathematical physics that were developed to show the concavity of magnetization. Our algorithm extends straighforwardly to general ferromagnetic Ising models with latent variables. Conversely, we show that even for a contant number of latent variables with constant degree, without ferromagneticity the problem is as hard as sparse parity with noise. This hardness result is based on a sharp and surprising characterization of the representational power of bounded degree RBMs: the distribution on their observed variables can simulate any bounded order MRF. This result is of independent interest since RBMs are the building blocks of deep belief networks.