# Learning Algorithm of Boltzmann Machine Based on Spatial Monte Carlo Integration Method
## 2 Boltzmann Machine Learning  
Consider an undirected and connected graph, \(G=(V,E)\), with \(n\) nodes, where \(V:=\{1,2,\ldots,n\}\) is the set of labels of nodes and \(E\) is the set of labels of undirected links; an undirected link between nodes \(i\) and \(j\) is labeled \((i,j)\). Since an undirected graph is now considered, labels \((i,j)\) and \((j,i)\) indicate the same link. On undirected graph \(G\), we define a Boltzmann machine with random variables \(\mathbf{x}:=\{x_{i}\in\mathcal{X}\mid i\in V\}\), where \(\mathcal{X}\) is the sample space of the variable. It is expressed as [7; 9]  
\[P_{\text{BM}}(\mathbf{x}\mid\mathbf{w}):=\frac{1}{Z(\mathbf{w})}\exp\Big{(} \sum_{(i,j)\in E}w_{ij}x_{i}x_{j}\Big{)}, \tag{1}\]  
where \(Z(\mathbf{w})\) is the partition function defined by  
\[Z(\mathbf{w}):=\sum_{\mathbf{x}}\exp\Big{(}\sum_{(i,j)\in E}w_{ij}x_{i}x_ {j}\Big{)},\]  
where \(\sum_{\mathbf{x}}\) is the multiple summation over all the possible realizations of \(\mathbf{x}\); i.e., \(\sum_{\mathbf{x}}=\prod_{i\in V}\sum_{x_{i}\in\mathcal{X}}\). Here and in the following, if \(x_{i}\) is continuous, \(\sum_{x_{i}\in\mathcal{X}}\) is replaced by integration. \(\mathbf{w}:=\{w_{ij}\in(-\infty,\infty)\mid(i,j)\in E\}\) represents the symmetric coupling parameters (\(w_{ij}=w_{ji}\)). Although a Boltzmann machine can include a bias term, e.g., \(\sum_{i\in V}b_{i}x_{i}\), in its exponent, it is ignored in this paper for the sake of the simplicity of arguments. Suppose that a set of \(N\) data points corresponding to \(\mathbf{x}\), \(\mathcal{D}:=\{\mathbf{x}^{(\mu)}\mid\mu=1,2,\ldots,N\}\) where \(\mathbf{x}^{(\mu)}:=\{x_{i}^{(\mu)}\in\mathcal{X}\mid i\in V\}\), is obtained. The goal of Boltzmann machine learning is to maximize the log-likelihood  
\[l(\mathbf{w};\mathcal{D}):=\frac{1}{N}\sum_{\mu=1}^{N}\ln P_{\text{ BM}}(\mathbf{x}^{(\mu)}\mid\mathbf{w}) \tag{2}\]  
with respect to \(\mathbf{w}\), that is, the maximum likelihood estimation (MLE). The Boltzmann machine, with \(\mathbf{w}\) that maximizes Equation (2), yields the distribution most similar to the data distribution (also referredto as the empirical distribution) in the perspective of the measure based on Kullback-Leibler divergence (KLD). This fact can be easily seen in the following. The empirical distribution of \(\mathcal{D}\) is expressed as  
\[Q_{\mathcal{D}}(\mathbf{x}):=\frac{1}{N}\sum_{\mu=1}^{N}\prod_{i\in V}\delta(x_{i},x_{i}^{(\mu)}), \tag{3}\]  
where \(\delta(a,b)\) is the Kronecker delta function: \(\delta(a,b)=1\) when \(a=b\), and \(\delta(a,b)=0\) when \(a\
eq b\). The KLD between the empirical distribution and the Boltzmann machine in Equation (1),  
\[D_{\text{KL}}[Q_{\mathcal{D}}\parallel P_{\text{BM}}]:=\sum_{\mathbf{x}}Q_{ \mathcal{D}}(\mathbf{x})\ln\frac{Q_{\mathcal{D}}(\mathbf{x})}{P_{\text{BM}}(\mathbf{x} \mid\mathbf{w})}, \tag{4}\]  
can be rewritten as \(D_{\text{KL}}[Q_{\mathcal{D}}\parallel P_{\text{BM}}]=-l(\mathbf{w};\mathcal{D})+C\), where \(C\) is the constant unrelated to \(\mathbf{w}\). From this equation, we determine that \(\mathbf{w}\) that maximizes the log-likelihood in Equation (2) minimizes the KLD. Since the log-likelihood in Equation (2) is the concave function with respect to \(\mathbf{w}\)[8], in principle, we can optimize the log-likelihood using a gradient ascent method. The gradient of the log-likelihood with respect to \(w_{ij}\) is  
\[\Delta_{ij}^{\text{MLE}}(\mathbf{w};\mathcal{D}):=\frac{\partial l(\mathbf{w}; \mathcal{D})}{\partial w_{ij}}=\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{5}\]  
where \(\text{E}_{\text{BM}}[\cdots\mid\mathbf{w}]:=\sum_{\mathbf{x}}(\cdots)P_{\text{BM}}( \mathbf{x}\mid\mathbf{w})\) is the expectation of the assigned quantity over the Boltzmann machine in Equation (1).