# Learning Algorithm of Boltzmann Machine Based on Spatial Monte Carlo Integration Method
## 2 Boltzmann Machine Learning
In the optimal point of the MLE, all the gradients are zero, and therefore, from Equation (5), the optimal \(\mathbf{w}\) is the solution to the simultaneous equations  
\[\frac{1}{N}\sum_{\mu=1}^{N}x_{i}^{(\mu)}x_{j}^{(\mu)}=\text{E}_{\text{BM}}[x_{ i}x_{j}\mid\mathbf{w}]. \tag{6}\]  
When the data points are generated independently from a Boltzmann machine, \(P_{\text{BM}}(\mathbf{x}\mid\mathbf{w}^{\text{gen}})\), defined on the same graph as the Boltzmann machine we use in the learning, i.e., the case without the model error, the solution to the MLE, \(\mathbf{w}^{\text{MLE}}\), converges to \(\mathbf{w}^{\text{gen}}\) as \(N\to\infty\)[23]. In other words, the MLE is asymptotically consistent. However, it is difficult to compute the second term in Equation (5), because the computations of these expectations need the summation over \(O(2^{n})\) terms. Thus, the exact Boltzmann machine learning, i.e., the MLE, cannot be performed. As mentioned in Section 1, various approximations for Boltzmann machine learning were proposed by many authors, such as the mean-field learning methods [10; 11; 12; 13; 14; 15] and the MPLE [16; 17], CD [18], RM [19], MPF [20; 21] and SMCI [22] methods. In the following, we briefly review the MPLE method. In MPLE, we maximize the following pseudo-likelihood [16; 17; 24] instead of the true log-likelihood in Equation (2). \[l_{\text{MPLE}}(\mathbf{w};\mathcal{D}):=\frac{1}{N}\sum_{\mu=1}^{N}\sum_{i\in \mathcal{V}}\ln P_{\text{BM}}(x_{i}^{(\mu)}\mid\mathbf{x}_{-\{i\}}^{(\mu)},\mathbf{w}), \tag{7}\]  
where \(\mathbf{x}_{\mathcal{A}}:=\{x_{i}\mid i\in\mathcal{A}\subseteq V\}\) is the variables in \(\mathcal{A}\) and \(-\mathcal{A}:=V\setminus\mathcal{A}\); i.e., \(\mathbf{x}_{-\{i\}}=\mathbf{x}\setminus\{x_{i}\}\). The conditional distribution in the above equation is the conditional distribution in the Boltzmann machine expressed by  
\[P_{\text{BM}}(x_{i}\mid\mathbf{x}_{-\{i\}},\mathbf{w})=\frac{P_{\text{BM}}(\mathbf{x}\mid \mathbf{w})}{\sum_{x_{i}\in\mathcal{X}}P_{\text{BM}}(\mathbf{x}\mid\mathbf{w})}=\frac{ \exp\big{(}l_{i}(\mathbf{x}_{\partial(i)},\mathbf{w})x_{i}\big{)}}{\sum_{x_{i}\in \mathcal{X}}\exp\big{(}l_{i}(\mathbf{x}_{\partial(i)},\mathbf{w})x_{i}\big{)}}, \tag{8}\]where  
\[U_{i}(\mathbf{x}_{\partial(i)},\mathbf{w}):=\sum_{j\in\partial(i)}w_{ij}x_{j}, \tag{9}\]  
where \(\partial(i)\subseteq V\) is the set of labels of nodes directly connected to node \(i\); i.e., \(\partial(i):=\{j\mid(i,j)\in E\}\). The derivative of the pseudo-likelihood with respect to \(w_{ij}\) is  
\[Z(\mathbf{w}):=\sum_{\mathbf{x}}\exp\Big{(}\sum_{(i,j)\in E}w_{ij}x_{i}x_ {j}\Big{)},\]0  
\(m_{ij}^{\text{MPLE}}(\mathbf{w};\mathcal{D})\) is defined by  
\[Z(\mathbf{w}):=\sum_{\mathbf{x}}\exp\Big{(}\sum_{(i,j)\in E}w_{ij}x_{i}x_ {j}\Big{)},\]1  
where  
\[Z(\mathbf{w}):=\sum_{\mathbf{x}}\exp\Big{(}\sum_{(i,j)\in E}w_{ij}x_{i}x_ {j}\Big{)},\]2  
and where, for a set \(\mathcal{A}\subseteq V\), \(\mathbf{\mathrm{x}}_{\mathcal{A}}^{(\mu)}\) is the \(\mu\)-th data point corresponding to \(\mathbf{x}_{\mathcal{A}}\); i.e., \(\mathbf{\mathrm{x}}_{\mathcal{A}}^{(\mu)}=\{\mathrm{x}_{i}^{(\mu)}\mid i\in \mathcal{A}\subseteq V\}\). When \(\mathcal{X}=\{-1,+1\}\), \(M_{i}(\mathbf{x}_{\partial(i)},\mathbf{w})=\tanh U_{i}(\mathrm{x}_{\partial(i)},\mathbf{ w})\). In order to fit the magnitude of the gradient to that of the MLE, we use half of Equation (10) as the gradient of the MPLE  
\[Z(\mathbf{w}):=\sum_{\mathbf{x}}\exp\Big{(}\sum_{(i,j)\in E}w_{ij}x_{i}x_ {j}\Big{)},\]3  
The order of the total computational complexity of the gradients in Equation (11) is \(O(N|E|)\), where \(|E|\) is the number of links in \(G(V,E)\). The pseudo-likelihood is also the concave function with respect to \(\mathbf{w}\), and therefore, one can optimize it using a gradient ascent method. The typical performance of the MPLE method is almost the same as or slightly better than that of the CD method in Boltzmann machine learning [24].