Last week we defined a domain X of stochastic variables X={x0,x1,…,xn−1} with a pertinent probability distribution
p(X)=∏xi∈Xp(xi),
where we have assumed that the random varaibles xi are all independent and identically distributed (iid).
We will now assume that we can defined this function in terms of optimization parameters Θ, which could be the biases and weights of deep network, and a set of hidden variables we also assume to be random variables which also are iid. The domain of these variables is H={h0,h1,…,hm−1}.
We define a probability
p(xi,hj;Θ)=f(xi,hj;Θ)Z(Θ),
where f(xi,hj;Θ) is a function which we assume is larger or equal than zero and obeys all properties required for a probability distribution and Z(Θ) is a normalization constant. Inspired by statistical mechanics, we call it often for the partition function. It is defined as (assuming that we have discrete probability distributions)
Z(Θ)=∑xi∈X∑hj∈Hf(xi,hj;Θ).
We can in turn define the marginal probabilities
p(xi;Θ)=∑hj∈Hf(xi,hj;Θ)Z(Θ),
and
p(hi;Θ)=∑xi∈Xf(xi,hj;Θ)Z(Θ).
Note the change to a vector notation. A variable like x represents now a specific configuration. We can generate an infinity of such configurations. The final partition function is then the sum over all such possible configurations, that is
Z(Θ)=∑xi∈X∑hj∈Hf(xi,hj;Θ),
changes to
Z(Θ)=∑x∑hf(x,h;Θ).
If we have a binary set of variable xi and hj and M values of xi and N values of hj we have in total 2M and 2N possible x and h configurations, respectively.
We see that even for the modest binary case, we can easily approach a number of configuration which is not possible to deal with.
At the end, we are not interested in the probabilities of the hidden variables. The probability we thus want to optimize is
p(X;Θ)=∏xi∈Xp(xi;Θ)=∏xi∈X(∑hj∈Hf(xi,hj;Θ)Z(Θ)),
which we rewrite as
p(X;Θ)=1Z(Θ)∏xi∈X(∑hj∈Hf(xi,hj;Θ)).
We simplify further by rewriting it as
p(X;Θ)=1Z(Θ)∏xi∈Xf(xi;Θ),
where we used p(xi;Θ)=∑hj∈Hf(xi,hj;Θ). The optimization problem is then
argmaxΘ∈Rpp(X;Θ).
Computing the derivatives with respect to the parameters Θ is easier (and equivalent) if we compute the logarithm of the probability. We will thus optimize
argmaxΘ∈Rplogp(X;Θ),
which leads to
∇Θlogp(X;Θ)=0.
This leads to the following equation
∇Θlogp(X;Θ)=∇Θ(∑xi∈Xlogf(xi;Θ))−∇ΘlogZ(Θ)=0.
The first term is called the positive phase and we assume that we have a model for the function f from which we can sample values. Below we will develop an explicit model for this. The second term is called the negative phase and is the one which leads to more difficulties.
The partition function, defined above as
Z(Θ)=∑xi∈X∑hj∈Hf(xi,hj;Θ),
is in general the most problematic term. In principle both x and h can span large degrees of freedom, if not even infinitely many ones, and computing the partition function itself is often not desirable or even feasible. The above derivative of the partition function can however be written in terms of an expectation value which is in turn evaluated using Monte Carlo sampling and the theory of Markov chains, popularly shortened to MCMC (or just MC$^2$).
We can rewrite
∇ΘlogZ(Θ)=∇ΘZ(Θ)Z(Θ),
which reads in more detail
∇ΘlogZ(Θ)=∇Θ∑xi∈Xf(xi;Θ)Z(Θ).
We can rewrite the function f (we have assumed that is larger or equal than zero) as f=explogf. We can then reqrite the last equation as
∇ΘlogZ(Θ)=∑xi∈X∇Θexplogf(xi;Θ)Z(Θ).
Taking the derivative gives us
∇ΘlogZ(Θ)=∑xi∈Xf(xi;Θ)∇Θlogf(xi;Θ)Z(Θ),
which is the expectation value of logf
∇ΘlogZ(Θ)=∑xi∈Xp(xi;Θ)∇Θlogf(xi;Θ),
that is
∇ΘlogZ(Θ)=E(logf(xi;Θ)).
This quantity is evaluated using Monte Carlo sampling, with Gibbs sampling as the standard sampling rule. Before we discuss the explicit algorithms, we need to remind ourselves about Markov chains and sampling rules like the Metropolis-Hastings algorithm and Gibbs sampling.
As we will see below, a typical Boltzmann machines employs a probability distribution
p(x,h;Θ)=f(x,h;Θ)Z(Θ),
where f(x,h;Θ) is given by a so-called energy model. If we assume that the random variables xi and hj take binary values only, for example xi,hj={0,1}, we have a so-called binary-binary model where
f(x,h;Θ)=−E(x,h;Θ)=∑xi∈Xxiai+∑hj∈Hbjhj+∑xi∈X,hj∈Hxiwijhj,
where the set of parameters are given by the biases and weights Θ={a,b,W}. Note the vector notation instead of xi and hj for f. The vectors x and h represent a specific instance of stochastic variables xi and hj. These arrangements of x and h lead to a specific energy configuration.
With the above definition we can write the probability as
p(x,h;Θ)=exp(aTx+bTh+xTWh)Z(Θ),
where the biases a and h and the weights defined by the matrix W are the parameters we need to optimize.
Since the binary-binary energy model is linear in the parameters ai, bj and wij, it is easy to see that the derivatives with respect to the various optimization parameters yield expressions used in the evaluation of gradients like
∂E(x,h;Θ)∂wij=−xihj,
and
∂E(x,h;Θ)∂ai=−xi,
and
∂E(x,h;Θ)∂bj=−hj.
A generative model can learn to represent and sample from a probability distribution. The core idea is to learn a parametric model of the probability distribution from which the training data was drawn. As an example
Generative and discriminative models use both gradient-descent based learning procedures for minimizing cost functions
However, in energy based models we don't use backpropagation and automatic differentiation for computing gradients, instead we turn to Markov Chain Monte Carlo methods.
A typical deep neural network has several hidden layers. A restricted Boltzmann machine has normally one hidden layer, however several RBMs can be stacked to make up deep Belief Networks, of which they constitute the building blocks.
A BM is what we would call an undirected probabilistic graphical model with stochastic continuous or discrete units.
It is interpreted as a stochastic recurrent neural network where the state of each unit(neurons/nodes) depends on the units it is connected to. The weights in the network represent thus the strength of the interaction between various units/nodes.
A standard BM network is divided into a set of observable and visible units x and a set of unknown hidden units/nodes h.
Additionally there can be bias nodes for the hidden and visible layers. These biases are normally set to 1.
BMs are stackable, meaning they cwe can train a BM which serves as input to another BM. We can construct deep networks for learning complex PDFs. The layers can be trained one after another, a feature which makes them popular in deep learning
However, they are often hard to train. This leads to the introduction of so-called restricted BMs, or RBMS. Here we take away all lateral connections between nodes in the visible layer as well as connections between nodes in the hidden layer.
The goal of the hidden layer is to increase the model's expressive power. We encode complex interactions between visible variables by introducing additional, hidden variables that interact with visible degrees of freedom in a simple manner, yet still reproduce the complex correlations between visible degrees in the data once marginalized over (integrated out).
The network parameters, to be optimized/learned:
Note that we have specified the lengths of bmx and h. These lengths define the number of visible and hidden units, respectively.
The restricted Boltzmann machine is described by a Boltzmann distribution
Prbm(x,h,Θ)=1Z(Θ)exp−(E(x,h,Θ)),
where Z is the normalization constant or partition function discussed earlier and defined as
Z(Θ)=∫∫exp−E(x,h,Θ)dxdh.
It is common to set the temperature T to one. It is omitted in the equations above. The energy is thus a dimensionless function.
The function E(x,h,Θ) gives the energy of a configuration (pair of vectors) (x,h). The lower the energy of a configuration, the higher the probability of it. This function also depends on the parameters a, b and W. Thus, when we adjust them during the learning procedure, we are adjusting the energy function to best fit our problem.
There are different variants of RBMs, and the differences lie in the types of visible and hidden units we choose as well as in the implementation of the energy function E(x,h,Θ). The connection between the nodes in the two layers is given by the weights wij.
RBMs were first developed using binary units in both the visible and hidden layer. The corresponding energy function is defined as follows:
E(x,h,Θ)=−M∑ixiai−N∑jbjhj−M,N∑i,jxiwijhj,
where the binary values taken on by the nodes are most commonly 0 and 1.
Another varient is the RBM where the visible units are Gaussian while the hidden units remain binary:
E(x,h,Θ)=M∑i(xi−ai)22σ2i−N∑jbjhj−M,N∑i,jxiwijhjσ2i.
This type of RBMs are useful when we model continuous data (i.e., we wish x to be continuous). The paramater σ2i is meant to represent a variance and is foten just set to one.
When working with a training dataset, the most common training approach is maximizing the log-likelihood of the training data. The log likelihood characterizes the log-probability of generating the observed data using our generative model. Using this method our cost function is chosen as the negative log-likelihood. The learning then consists of trying to find parameters that maximize the probability of the dataset, and is known as Maximum Likelihood Estimation (MLE).
Denoting the parameters as Θ=a1,...,aM,b1,...,bN,w11,...,wMN, the log-likelihood is given by
L({Θi})=⟨logPθ(x)⟩data=−⟨E(x;{Θi})⟩data−logZ({Θi}),
where we used that the normalization constant does not depend on the data, ⟨logZ({Θi})⟩=logZ({Θi}) Our cost function is the negative log-likelihood, C({Θi})=−L({Θi})
The training procedure of choice often is Stochastic Gradient Descent (SGD). It consists of a series of iterations where we update the parameters according to the equation
Θk+1=Θk−η∇C(Θk)
at each k-th iteration. There are a range of variants of the algorithm which aim at making the learning rate η more adaptive so the method might be more efficient while remaining stable.
We now need the gradient of the cost function in order to minimize it. We find that
∂C({Θi})∂Θi=⟨∂E(x;Θi)∂Θi⟩data+∂logZ({Θi})∂Θi=⟨Oi(x)⟩data−⟨Oi(x)⟩model.
In order to simplify notation we defined the "operator"
Oi(x)=∂E(x;Θi)∂Θi,
and used the statistical mechanics relationship between expectation values and the log-partition function:
⟨Oi(x)⟩model=TrPΘ(x)Oi(x)=−∂logZ({Θi})∂Θi.
As discussed earlier, the data-dependent term in the gradient is known as the positive phase of the gradient, while the model-dependent term is known as the negative phase of the gradient. The aim of the training is to lower the energy of configurations that are near observed data points (increasing their probability), and raising the energy of configurations that are far from observed data points (decreasing their probability).
The gradient of the negative log-likelihood cost function of a Binary-Binary RBM is then
∂C(wij,ai,bj)∂wij=⟨xihj⟩data−⟨xihj⟩model∂C(wij,ai,bj)∂aij=⟨xi⟩data−⟨xi⟩model∂C(wij,ai,bj)∂bij=⟨hi⟩data−⟨hi⟩model.
To get the expectation values with respect to the data, we set the visible units to each of the observed samples in the training data, then update the hidden units according to the conditional probability found before. We then average over all samples in the training data to calculate expectation values with respect to the data.
When the goal of the training is to approximate a probability distribution, as it is in generative modeling, another relevant measure is the Kullback-Leibler divergence, also known as the relative entropy or Shannon entropy. It is a non-symmetric measure of the dissimilarity between two probability density functions p and q. If p is the unkown probability which we approximate with q, we can measure the difference by
KL(p||q)=∫∞−∞p(x)logp(x)q(x)dx.
Thus, the Kullback-Leibler divergence between the distribution of the training data f(x) and the model distribution p(x|Θ) is
KL(f(x)||p(x|Θ))=∫∞−∞f(x)logf(x)p(x|Θ)dx=∫∞−∞f(x)logf(x)dx−∫∞−∞f(x)logp(x|Θ)dx=⟨logf(x)⟩f(x)−⟨logp(x|Θ)⟩f(x)=⟨logf(x)⟩data+⟨E(x)⟩data+logZ=⟨logf(x)⟩data+CLL.
The first term is constant with respect to Θ since f(x) is independent of Θ. Thus the Kullback-Leibler Divergence is minimal when the second term is minimal. The second term is the log-likelihood cost function, hence minimizing the Kullback-Leibler divergence is equivalent to maximizing the log-likelihood.
To further understand generative models it is useful to study the gradient of the cost function which is needed in order to minimize it using methods like stochastic gradient descent.
The partition function is the generating function of expectation values, in particular there are mathematical relationships between expectation values and the log-partition function. In this case we have
⟨∂E(x;Θi)∂Θi⟩model=∫p(x|Θ)∂E(x;Θi)∂Θidx=−∂logZ(Θi)∂Θi.
Here ⟨⋅⟩model is the expectation value over the model probability distribution p(x|Θ).
Using the previous relationship we can express the gradient of the cost function as
∂CLL∂Θi=⟨∂E(x;Θi)∂Θi⟩data+∂logZ(Θi)∂Θi=⟨∂E(x;Θi)∂Θi⟩data−⟨∂E(x;Θi)∂Θi⟩model
This expression shows that the gradient of the log-likelihood cost function is a difference of moments, with one calculated from the data and one calculated from the model. The data-dependent term is called the positive phase and the model-dependent term is called the negative phase of the gradient. We see now that minimizing the cost function results in lowering the energy of configurations x near points in the training data and increasing the energy of configurations not observed in the training data. That means we increase the model's probability of configurations similar to those in the training data.
The gradient of the cost function also demonstrates why gradients of unsupervised, generative models must be computed differently from for those of for example FNNs. While the data-dependent expectation value is easily calculated based on the samples xi in the training data, we must sample from the model in order to generate samples from which to caclulate the model-dependent term. We sample from the model by using MCMC-based methods. We can not sample from the model directly because the partition function Z is generally intractable.
As in supervised machine learning problems, the goal is also here to perform well on unseen data, that is to have good generalization from the training data. The distribution f(x) we approximate is not the true distribution we wish to estimate, it is limited to the training data. Hence, in unsupervised training as well it is important to prevent overfitting to the training data. Thus it is common to add regularizers to the cost function in the same manner as we discussed for say linear regression.
Because we are restricted to potential functions which are positive it is convenient to express them as exponentials.
The original RBM had binary visible and hidden nodes. They were showned to be universal approximators of discrete distributions. It was also shown that adding hidden units yields strictly improved modelling power.
The common choice of binary values are 0 and 1. However, in some physics applications, -1 and 1 might be a more natural choice. We will here use 0 and 1. We habe the energy function
EBB(x,h,Θ)=−M∑ixiai−N∑jbjhj−M,N∑i,jxiwijhj.
We have the binary-binary marginal probability defined as
pBB(x,h,Θ)=1ZBB(Θ)e∑Miaixi+∑Njbjhj+∑M,Nijxiwijhj=1ZBB(Θ)eaTx+bTh+xTWh
with the partition function
ZBB(Θ)=∑x,heaTx+bTh+xTWh.
In order to find the probability of any configuration of the visible units we derive the marginal probability density function.
pBB(x,Θ)=∑hpBB(x,h,Θ)=1ZBB∑heaTx+bTh+xTWh=1ZBBeaTx∑he∑Nj(bj+xTw∗j)hj=1ZBBeaTx∑hN∏je(bj+xTw∗j)hj=1ZBBeaTx(∑h1e(b1+xTw∗1)h1×∑h2e(b2+xTw∗2)h2×...×∑h2e(bN+xTw∗N)hN)=1ZBBeaTxN∏j∑hje(bj+xTw∗j)hj=1ZBBeaTxN∏j(1+ebj+xTw∗j).
A similar derivation yields the marginal probability of the hidden units
pBB(h,Θ)=1ZBB(Θ)ebThM∏i(1+eai+wTi∗h).
We derive the probability of the hidden units given the visible units using Bayes' rule (we drop the explicit Θ dependence)
pBB(h|x)=pBB(x,h)pBB(x)=1ZBBeaTx+bTh+xTWh1ZBBeaTx∏Nj(1+ebj+xTw∗j)=eaTxe∑Nj(bj+xTw∗j)hjeaTx∏Nj(1+ebj+xTw∗j)=N∏je(bj+xTw∗j)hj1+ebj+xTw∗j=N∏jpBB(hj|x).
From this we find the probability of a hidden unit being "on" or "off":
pBB(hj=1|x)=e(bj+xTw∗j)hj1+ebj+xTw∗j=e(bj+xTw∗j)1+ebj+xTw∗j=11+e−(bj+xTw∗j),
and
pBB(hj=0|x)=11+ebj+xTw∗j.
Similarly we have that the conditional probability of the visible units given the hidden are
pBB(x|h)=M∏ie(ai+wTi∗h)xi1+eai+wTi∗h=M∏ipBB(xi|h).
We have
pBB(xi=1|h)=11+e−(ai+wTi∗h)pBB(xi=0|h)=11+eai+wTi∗h.
Inserting into the expression for ERBM(x,h,Θ) in equation results in the energy
EGB(x,h,Θ)=M∑i(xi−ai)22σ2i−N∑jbjhj−M,N∑ijxiwijhjσ2i=||x−a2σ||2−bTh−(xσ2)TWh.
pGB(x,h,Θ)=1ZGBe−||x−a2σ||2+bTh+(xσ2)TWh=1ZGBe−∑Mi(xi−ai)22σ2i+∑Njbjhj+∑M,Nijxiwijhjσ2i=1ZGBM,N∏ije−(xi−ai)22σ2i+bjhj+xiwijhjσ2i.
The partition function is given by
ZGB=∫˜H∑˜he−||˜x−a2σ||2+bT˜h+(˜xσ2)TW˜hd˜x.
We proceed to find the marginal probability densitites of the Gaussian-binary RBM. We first marginalize over the binary hidden units to find pGB(x)
pGB(x)=˜H∑˜hpGB(x,˜h)=1ZGB˜H∑˜he−||x−a2σ||2+bT˜h+(xσ2)TW˜h=1ZGBe−||x−a2σ||2N∏j(1+ebj+(xσ2)Tw∗j).
We next marginalize over the visible units. This is the first time we marginalize over continuous values. We rewrite the exponential factor dependent on x as a Gaussian function before we integrate in the last step.
pGB(h)=∫pGB(˜x,h)d˜x=1ZGB∫e−||˜x−a2σ||2+bTh+(˜xσ2)TWhd˜x=1ZGBebTh∫M∏ie−(˜xi−ai)22σ2i+˜xiwTi∗hσ2id˜x=1ZGBebTh(∫e−(˜x1−a1)22σ21+˜x1wT1∗hσ21d˜x1×∫e−(˜x2−a2)22σ22+˜x2wT2∗hσ22d˜x2×...×∫e−(˜xM−aM)22σ2M+˜xMwTM∗hσ2Md˜xM)=1ZGBebThM∏i∫e−(˜xi−ai)2−2˜xiwTi∗h2σ2id˜xi=1ZGBebThM∏i∫e−˜x2i−2˜xi(ai+˜xiwTi∗h)+a2i2σ2id˜xi=1ZGBebThM∏i∫e−˜x2i−2˜xi(ai+wTi∗h)+(ai+wTi∗h)2−(ai+wTi∗h)2+a2i2σ2id˜xi=1ZGBebThM∏i∫e−(˜xi−(ai+wTi∗h))2−a2i−2aiwTi∗h−(wTi∗h)2+a2i2σ2id˜xi=1ZGBebThM∏ie2aiwTi∗h+(wTi∗h)22σ2i∫e−(˜xi−ai−wTi∗h)22σ2id˜xi=1ZGBebThM∏i√2πσ2ie2aiwTi∗h+(wTi∗h)22σ2i.
We finish by deriving the conditional probabilities.
pGB(h|x)=pGB(x,h)pGB(x)=1ZGBe−||x−a2σ||2+bTh+(xσ2)TWh1ZGBe−||x−a2σ||2∏Nj(1+ebj+(xσ2)Tw∗j)=N∏je(bj+(xσ2)Tw∗j)hj1+ebj+(xσ2)Tw∗j=N∏jpGB(hj|x).
The conditional probability of a binary hidden unit hj being on or off again takes the form of a sigmoid function
pGB(hj=1|x)=ebj+(xσ2)Tw∗j1+ebj+(xσ2)Tw∗j=11+e−bj−(xσ2)Tw∗jpGB(hj=0|x)=11+ebj+(xσ2)Tw∗j.
The conditional probability of the continuous x now has another form, however.
pGB(x|h)=pGB(x,h)pGB(h)=1ZGBe−||x−a2σ||2+bTh+(xσ2)TWh1ZGBebTh∏Mi√2πσ2ie2aiwTi∗h+(wTi∗h)22σ2i=M∏i1√2πσ2ie−(xi−ai)22σ2i+xiwTi∗h2σ2ie2aiwTi∗h+(wTi∗h)22σ2i=M∏i1√2πσ2ie−x2i−2aixi+a2i−2xiwTi∗h2σ2ie2aiwTi∗h+(wTi∗h)22σ2i=M∏i1√2πσ2ie−x2i−2aixi+a2i−2xiwTi∗h+2aiwTi∗h+(wTi∗h)22σ2i=M∏i1√2πσ2ie−(xi−bi−wTi∗h)22σ2i=M∏iN(xi|bi+wTi∗h,σ2i)⇒pGB(xi|h)=N(xi|bi+wTi∗h,σ2i).
The form of these conditional probabilities explains the name "Gaussian" and the form of the Gaussian-binary energy function. We see that the conditional probability of xi given h is a normal distribution with mean bi+wTi∗h and variance σ2i.
For the quantum mechanical calculations however, there are several ingredients which simplify our calculations.
The wavefunction should be a probability amplitude depending on x. The RBM model is given by the joint distribution of x and h
Frbm(x,h)=1Ze−1T0E(x,h)
To find the marginal distribution of x we set:
Frbm(x)=∑hFrbm(x,h)=1Z∑he−E(x,h)
Now this is what we use to represent the wave function, calling it a neural-network quantum state (NQS)
Ψ(X)=Frbm(x)=1Z∑he−E(x,h)=1Z∑{hj}e−∑Mi(xi−ai)22σ2+∑Njbjhj+∑M,Ni,jxiwijhjσ2=1Ze−∑Mi(xi−ai)22σ2N∏j(1+ebj+∑Mixiwijσ2)
The above wavefunction is the most general one because it allows for complex valued wavefunctions. However it fundamentally changes the probabilistic foundation of the RBM, because what is usually a probability in the RBM framework is now a an amplitude. This means that a lot of the theoretical framework usually used to interpret the model, i.e. graphical models, conditional probabilities, and Markov random fields, breaks down.
If we assume the wavefunction to be positive definite, however, we can use the RBM to represent the squared wavefunction, and thereby a probability. This also makes it possible to sample from the model using Gibbs sampling, because we can obtain the conditional probabilities.
|Ψ(X)|2=Frbm(X)⇒Ψ(X)=√Frbm(X)=1√Z√∑{hj}e−E(X,h)=1√Z√∑{hj}e−∑Mi(Xi−ai)22σ2+∑Njbjhj+∑M,Ni,jXiwijhjσ2=1√Ze−∑Mi(Xi−ai)24σ2√∑{hj}N∏jebjhj+∑MiXiwijhjσ2=1√Ze−∑Mi(Xi−ai)24σ2√N∏j∑hjebjhj+∑MiXiwijhjσ2=1√Ze−∑Mi(Xi−ai)24σ2N∏j√e0+ebj+∑MiXiwijσ2=1√Ze−∑Mi(Xi−ai)24σ2N∏j√1+ebj+∑MiXiwijσ2
This is where we deviate from what is common in machine learning. Rather than defining a cost function based on some dataset, our cost function is the energy of the quantum mechanical system. From the variational principle we know that minimizing this energy should lead to the ground state wavefunction. As stated previously the local energy is given by
EL=1ΨˆHΨ.
Gi=∂⟨EL⟩∂αi=2(⟨EL1Ψ∂Ψ∂αi⟩−⟨EL⟩⟨1Ψ∂Ψ∂αi⟩),
where αi=a1,...,aM,b1,...,bN,w11,...,wMN.
We use that 1Ψ∂Ψ∂αi=∂lnΨ∂αi, and find
lnΨ(X)=−lnZ−M∑m(Xm−am)22σ2+N∑nln(1+ebn+∑MiXiwinσ2).
This gives
∂∂amlnΨ=1σ2(Xm−am)∂∂bnlnΨ=1e−bn−1σ2∑MiXiwin+1∂∂wmnlnΨ=Xmσ2(e−bn−1σ2∑MiXiwin+1).
# 2-electron VMC code for 2dim quantum dot with importance sampling
# Using gaussian rng for new positions and Metropolis- Hastings
# Added restricted boltzmann machine method for dealing with the wavefunction
# RBM code based heavily off of:
# https://github.com/CompPhysics/ComputationalPhysics2/tree/gh-pages/doc/Programs/BoltzmannMachines/MLcpp/src/CppCode/ob
from math import exp, sqrt
from random import random, seed, normalvariate
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from matplotlib import cm
from matplotlib.ticker import LinearLocator, FormatStrFormatter
import sys
# Trial wave function for the 2-electron quantum dot in two dims
def WaveFunction(r,a,b,w):
sigma=1.0
sig2 = sigma**2
Psi1 = 0.0
Psi2 = 1.0
Q = Qfac(r,b,w)
for iq in range(NumberParticles):
for ix in range(Dimension):
Psi1 += (r[iq,ix]-a[iq,ix])**2
for ih in range(NumberHidden):
Psi2 *= (1.0 + np.exp(Q[ih]))
Psi1 = np.exp(-Psi1/(2*sig2))
return Psi1*Psi2
# Local energy for the 2-electron quantum dot in two dims, using analytical local energy
def LocalEnergy(r,a,b,w):
sigma=1.0
sig2 = sigma**2
locenergy = 0.0
Q = Qfac(r,b,w)
for iq in range(NumberParticles):
for ix in range(Dimension):
sum1 = 0.0
sum2 = 0.0
for ih in range(NumberHidden):
sum1 += w[iq,ix,ih]/(1+np.exp(-Q[ih]))
sum2 += w[iq,ix,ih]**2 * np.exp(Q[ih]) / (1.0 + np.exp(Q[ih]))**2
dlnpsi1 = -(r[iq,ix] - a[iq,ix]) /sig2 + sum1/sig2
dlnpsi2 = -1/sig2 + sum2/sig2**2
locenergy += 0.5*(-dlnpsi1*dlnpsi1 - dlnpsi2 + r[iq,ix]**2)
if(interaction==True):
for iq1 in range(NumberParticles):
for iq2 in range(iq1):
distance = 0.0
for ix in range(Dimension):
distance += (r[iq1,ix] - r[iq2,ix])**2
locenergy += 1/sqrt(distance)
return locenergy
# Derivate of wave function ansatz as function of variational parameters
def DerivativeWFansatz(r,a,b,w):
sigma=1.0
sig2 = sigma**2
Q = Qfac(r,b,w)
WfDer = np.empty((3,),dtype=object)
WfDer = [np.copy(a),np.copy(b),np.copy(w)]
WfDer[0] = (r-a)/sig2
WfDer[1] = 1 / (1 + np.exp(-Q))
for ih in range(NumberHidden):
WfDer[2][:,:,ih] = w[:,:,ih] / (sig2*(1+np.exp(-Q[ih])))
return WfDer
# Setting up the quantum force for the two-electron quantum dot, recall that it is a vector
def QuantumForce(r,a,b,w):
sigma=1.0
sig2 = sigma**2
qforce = np.zeros((NumberParticles,Dimension), np.double)
sum1 = np.zeros((NumberParticles,Dimension), np.double)
Q = Qfac(r,b,w)
for ih in range(NumberHidden):
sum1 += w[:,:,ih]/(1+np.exp(-Q[ih]))
qforce = 2*(-(r-a)/sig2 + sum1/sig2)
return qforce
def Qfac(r,b,w):
Q = np.zeros((NumberHidden), np.double)
temp = np.zeros((NumberHidden), np.double)
for ih in range(NumberHidden):
temp[ih] = (r*w[:,:,ih]).sum()
Q = b + temp
return Q
# Computing the derivative of the energy and the energy
def EnergyMinimization(a,b,w):
NumberMCcycles= 10000
# Parameters in the Fokker-Planck simulation of the quantum force
D = 0.5
TimeStep = 0.05
# positions
PositionOld = np.zeros((NumberParticles,Dimension), np.double)
PositionNew = np.zeros((NumberParticles,Dimension), np.double)
# Quantum force
QuantumForceOld = np.zeros((NumberParticles,Dimension), np.double)
QuantumForceNew = np.zeros((NumberParticles,Dimension), np.double)
# seed for rng generator
seed()
energy = 0.0
DeltaE = 0.0
EnergyDer = np.empty((3,),dtype=object)
DeltaPsi = np.empty((3,),dtype=object)
DerivativePsiE = np.empty((3,),dtype=object)
EnergyDer = [np.copy(a),np.copy(b),np.copy(w)]
DeltaPsi = [np.copy(a),np.copy(b),np.copy(w)]
DerivativePsiE = [np.copy(a),np.copy(b),np.copy(w)]
for i in range(3): EnergyDer[i].fill(0.0)
for i in range(3): DeltaPsi[i].fill(0.0)
for i in range(3): DerivativePsiE[i].fill(0.0)
#Initial position
for i in range(NumberParticles):
for j in range(Dimension):
PositionOld[i,j] = normalvariate(0.0,1.0)*sqrt(TimeStep)
wfold = WaveFunction(PositionOld,a,b,w)
QuantumForceOld = QuantumForce(PositionOld,a,b,w)
#Loop over MC MCcycles
for MCcycle in range(NumberMCcycles):
#Trial position moving one particle at the time
for i in range(NumberParticles):
for j in range(Dimension):
PositionNew[i,j] = PositionOld[i,j]+normalvariate(0.0,1.0)*sqrt(TimeStep)+\
QuantumForceOld[i,j]*TimeStep*D
wfnew = WaveFunction(PositionNew,a,b,w)
QuantumForceNew = QuantumForce(PositionNew,a,b,w)
GreensFunction = 0.0
for j in range(Dimension):
GreensFunction += 0.5*(QuantumForceOld[i,j]+QuantumForceNew[i,j])*\
(D*TimeStep*0.5*(QuantumForceOld[i,j]-QuantumForceNew[i,j])-\
PositionNew[i,j]+PositionOld[i,j])
GreensFunction = exp(GreensFunction)
ProbabilityRatio = GreensFunction*wfnew**2/wfold**2
#Metropolis-Hastings test to see whether we accept the move
if random() <= ProbabilityRatio:
for j in range(Dimension):
PositionOld[i,j] = PositionNew[i,j]
QuantumForceOld[i,j] = QuantumForceNew[i,j]
wfold = wfnew
#print("wf new: ", wfnew)
#print("force on 1 new:", QuantumForceNew[0,:])
#print("pos of 1 new: ", PositionNew[0,:])
#print("force on 2 new:", QuantumForceNew[1,:])
#print("pos of 2 new: ", PositionNew[1,:])
DeltaE = LocalEnergy(PositionOld,a,b,w)
DerPsi = DerivativeWFansatz(PositionOld,a,b,w)
DeltaPsi[0] += DerPsi[0]
DeltaPsi[1] += DerPsi[1]
DeltaPsi[2] += DerPsi[2]
energy += DeltaE
DerivativePsiE[0] += DerPsi[0]*DeltaE
DerivativePsiE[1] += DerPsi[1]*DeltaE
DerivativePsiE[2] += DerPsi[2]*DeltaE
# We calculate mean values
energy /= NumberMCcycles
DerivativePsiE[0] /= NumberMCcycles
DerivativePsiE[1] /= NumberMCcycles
DerivativePsiE[2] /= NumberMCcycles
DeltaPsi[0] /= NumberMCcycles
DeltaPsi[1] /= NumberMCcycles
DeltaPsi[2] /= NumberMCcycles
EnergyDer[0] = 2*(DerivativePsiE[0]-DeltaPsi[0]*energy)
EnergyDer[1] = 2*(DerivativePsiE[1]-DeltaPsi[1]*energy)
EnergyDer[2] = 2*(DerivativePsiE[2]-DeltaPsi[2]*energy)
return energy, EnergyDer
#Here starts the main program with variable declarations
NumberParticles = 2
Dimension = 2
NumberHidden = 2
interaction=False
# guess for parameters
a=np.random.normal(loc=0.0, scale=0.001, size=(NumberParticles,Dimension))
b=np.random.normal(loc=0.0, scale=0.001, size=(NumberHidden))
w=np.random.normal(loc=0.0, scale=0.001, size=(NumberParticles,Dimension,NumberHidden))
# Set up iteration using stochastic gradient method
Energy = 0
EDerivative = np.empty((3,),dtype=object)
EDerivative = [np.copy(a),np.copy(b),np.copy(w)]
# Learning rate eta, max iterations, need to change to adaptive learning rate
eta = 0.001
MaxIterations = 50
iter = 0
np.seterr(invalid='raise')
Energies = np.zeros(MaxIterations)
EnergyDerivatives1 = np.zeros(MaxIterations)
EnergyDerivatives2 = np.zeros(MaxIterations)
while iter < MaxIterations:
Energy, EDerivative = EnergyMinimization(a,b,w)
agradient = EDerivative[0]
bgradient = EDerivative[1]
wgradient = EDerivative[2]
a -= eta*agradient
b -= eta*bgradient
w -= eta*wgradient
Energies[iter] = Energy
print("Energy:",Energy)
#EnergyDerivatives1[iter] = EDerivative[0]
#EnergyDerivatives2[iter] = EDerivative[1]
#EnergyDerivatives3[iter] = EDerivative[2]
iter += 1
#nice printout with Pandas
import pandas as pd
from pandas import DataFrame
pd.set_option('max_columns', 6)
data ={'Energy':Energies}#,'A Derivative':EnergyDerivatives1,'B Derivative':EnergyDerivatives2,'Weights Derivative':EnergyDerivatives3}
frame = pd.DataFrame(data)
print(frame)
The potentially most time-consuming part is the evaluation of the gradient and the Laplacian of an N-particle Slater determinant.
We have to differentiate the determinant with respect to all spatial coordinates of all particles. A brute force differentiation would involve N⋅d evaluations of the entire determinant which would even worsen the already undesirable time scaling, making it Nd⋅O(N3)∼O(d⋅N4).
This poses serious hindrances to the overall efficiency of our code.
The efficiency can be improved however if we move only one electron at the time. The Slater determinant matrix ˆD is defined by the matrix elements
dij=ϕj(xi)
where ϕj(ri) is a single particle wave function. The columns correspond to the position of a given particle while the rows stand for the various quantum numbers.
What we need to realize is that when differentiating a Slater determinant with respect to some given coordinate, only one row of the corresponding Slater matrix is changed.
Therefore, by recalculating the whole determinant we risk producing redundant information. The solution turns out to be an algorithm that requires to keep track of the inverse of the Slater matrix.
Let the current position in phase space be represented by the (N⋅d)-element vector rold and the new suggested position by the vector rnew.
The inverse of ˆD can be expressed in terms of its cofactors Cij and its determinant (this our notation for a determinant) |ˆD|:
d−1ij=Cji|ˆD|
Notice that the interchanged indices indicate that the matrix of cofactors is to be transposed.
If ˆD is invertible, then we must obviously have ˆD−1ˆD=1, or explicitly in terms of the individual elements of ˆD and ˆD−1:
N∑k=1dXikd−1kj=δXij
Consider the ratio, which we shall call R, between |ˆD(rnew)| and |ˆD(rold)|. By definition, each of these determinants can individually be expressed in terms of the i-th row of its cofactor matrix
R≡|ˆD(rnew)||ˆD(rold)|=∑Nj=1dij(rnew)Cij(rnew)∑Nj=1dij(rold)Cij(rold)
Suppose now that we move only one particle at a time, meaning that rnew differs from rold by the position of only one, say the i-th, particle . This means that ˆD(rnew) and ˆD(rold) differ only by the entries of the i-th row. Recall also that the i-th row of a cofactor matrix ˆC is independent of the entries of the i-th row of its corresponding matrix ˆD. In this particular case we therefore get that the i-th row of ˆC(rnew) and ˆC(rold) must be equal. Explicitly, we have:
Cij(rnew)=Cij(rold)∀ j∈{1,…,N}
Now by eq. (2) the denominator of the rightmost expression must be unity, so that we finally arrive at:
R=N∑j=1dij(rnew)d−1ji(rold)=N∑j=1ϕj(rnewi)d−1ji(rold)
What this means is that in order to get the ratio when only the i-th particle has been moved, we only need to calculate the dot product of the vector (ϕ1(rnewi),…,ϕN(rnewi)) of single particle wave functions evaluated at this new position with the i-th column of the inverse matrix ˆD−1 evaluated at the original position. Such an operation has a time scaling of O(N). The only extra thing we need to do is to maintain the inverse matrix ˆD−1(xold).
If the new position rnew is accepted, then the inverse matrix can by suitably updated by an algorithm having a time scaling of O(N2). This algorithm goes as follows. First we update all but the i-th column of ˆD−1. For each column j≠i, we first calculate the quantity:
Sj=(ˆD(rnew)׈D−1(rold))ij=N∑l=1dil(rnew)d−1lj(rold)
The new elements of the j-th column of ˆD−1 are then given by:
d−1kj(rnew)=d−1kj(rold)−SjRd−1ki(rold)∀ k∈{1,…,N}j≠i
Finally the elements of the i-th column of ˆD−1 are updated simply as follows:
d−1ki(rnew)=1Rd−1ki(rold)∀ k∈{1,…,N}
We see from these formulas that the time scaling of an update of ˆD−1 after changing one row of ˆD is O(N2).
The scheme is also applicable for the calculation of the ratios involving derivatives. It turns out that differentiating the Slater determinant with respect to the coordinates of a single particle ri changes only the i-th row of the corresponding Slater matrix.
The gradient and the Laplacian can therefore be calculated as follows:
→∇i|ˆD(r)||ˆD(r)|=N∑j=1→∇idij(r)d−1ji(r)=N∑j=1→∇iϕj(ri)d−1ji(r)
and
∇2i|ˆD(r)||ˆD(r)|=N∑j=1∇2idij(r)d−1ji(r)=N∑j=1∇2iϕj(ri)d−1ji(r)
Thus, to calculate all the derivatives of the Slater determinant, we only need the derivatives of the single particle wave functions (→∇iϕj(ri) and ∇2iϕj(ri)) and the elements of the corresponding inverse Slater matrix (ˆD−1(ri)). A calculation of a single derivative is by the above result an O(N) operation. Since there are d⋅N derivatives, the time scaling of the total evaluation becomes O(d⋅N2). With an O(N2) updating algorithm for the inverse matrix, the total scaling is no worse, which is far better than the brute force approach yielding O(d⋅N4).
Important note: In most cases you end with closed form expressions for the single-particle wave functions. It is then useful to calculate the various derivatives and make separate functions for them.
The Slater determinant takes the form
Φ(r1,r2,,r3,r4,α,β,γ,δ)=1√4!|ψ100↑(r1)ψ100↑(r2)ψ100↑(r3)ψ100↑(r4)ψ100↓(r1)ψ100↓(r2)ψ100↓(r3)ψ100↓(r4)ψ200↑(r1)ψ200↑(r2)ψ200↑(r3)ψ200↑(r4)ψ200↓(r1)ψ200↓(r2)ψ200↓(r3)ψ200↓(r4)|.
The Slater determinant as written is zero since the spatial wave functions for the spin up and spin down states are equal. But we can rewrite it as the product of two Slater determinants, one for spin up and one for spin down.
We can rewrite it as
Φ(r1,r2,,r3,r4,α,β,γ,δ)=det↑(1,2)det↓(3,4)−det↑(1,3)det↓(2,4)
−det↑(1,4)det↓(3,2)+det↑(2,3)det↓(1,4)−det↑(2,4)det↓(1,3)
+det↑(3,4)det↓(1,2),
where we have defined
det↑(1,2)=1√2|ψ100↑(r1)ψ100↑(r2)ψ200↑(r1)ψ200↑(r2)|,
and
det↓(3,4)=1√2|ψ100↓(r3)ψ100↓(r4)ψ200↓(r3)ψ200↓(r4)|.
The total determinant is still zero!
We want to avoid to sum over spin variables, in particular when the interaction does not depend on spin.
It can be shown, see for example Moskowitz and Kalos, Int. J. Quantum Chem. 20 1107 (1981), that for the variational energy we can approximate the Slater determinant as
Φ(r1,r2,,r3,r4,α,β,γ,δ)∝det↑(1,2)det↓(3,4),
or more generally as
Φ(r1,r2,…rN)∝det↑det↓,
where we have the Slater determinant as the product of a spin up part involving the number of electrons with spin up only (2 for beryllium and 5 for neon) and a spin down part involving the electrons with spin down.
This ansatz is not antisymmetric under the exchange of electrons with opposite spins but it can be shown (show this) that it gives the same expectation value for the energy as the full Slater determinant.
As long as the Hamiltonian is spin independent, the above is correct. It is rather straightforward to see this if you go back to the equations for the energy discussed earlier this semester.
We will thus factorize the full determinant |ˆD| into two smaller ones, where each can be identified with ↑ and ↓ respectively:
|ˆD|=|ˆD|↑⋅|ˆD|↓
The combined dimensionality of the two smaller determinants equals the dimensionality of the full determinant. Such a factorization is advantageous in that it makes it possible to perform the calculation of the ratio R and the updating of the inverse matrix separately for |ˆD|↑ and |ˆD|↓:
|ˆD|new|ˆD|old=|ˆD|new↑|ˆD|old↑⋅|ˆD|new↓|ˆD|old↓
This reduces the calculation time by a constant factor. The maximal time reduction happens in a system of equal numbers of ↑ and ↓ particles, so that the two factorized determinants are half the size of the original one.
Consider the case of moving only one particle at a time which originally had the following time scaling for one transition:
OR(N)+Oinverse(N2)
For the factorized determinants one of the two determinants is obviously unaffected by the change so that it cancels from the ratio R.
Therefore, only one determinant of size N/2 is involved in each calculation of R and update of the inverse matrix. The scaling of each transition then becomes:
OR(N/2)+Oinverse(N2/4)
and the time scaling when the transitions for all N particles are put together:
OR(N2/2)+Oinverse(N3/4)
which gives the same reduction as in the case of moving all particles at once.
Computing the ratios discussed above requires that we maintain the inverse of the Slater matrix evaluated at the current position. Each time a trial position is accepted, the row number i of the Slater matrix changes and updating its inverse has to be carried out. Getting the inverse of an N×N matrix by Gaussian elimination has a complexity of order of O(N3) operations, a luxury that we cannot afford for each time a particle move is accepted. We will use the expression
d−1kj(xnew)={d−1kj(xold)−d−1ki(xold)R∑Nl=1dil(xnew)d−1lj(xold)if j≠id−1ki(xold)R∑Nl=1dil(xold)d−1lj(xold)if j=i
This equation scales as O(N2). The evaluation of the determinant of an N×N matrix by standard Gaussian elimination requires O(N3) calculations. As there are Nd independent coordinates we need to evaluate Nd Slater determinants for the gradient (quantum force) and Nd for the Laplacian (kinetic energy). With the updating algorithm we need only to invert the Slater determinant matrix once. This can be done by standard LU decomposition methods.
Determining a determinant of an N×N matrix by standard Gaussian elimination is of the order of O(N3) calculations. As there are N⋅d independent coordinates we need to evaluate Nd Slater determinants for the gradient (quantum force) and N⋅d for the Laplacian (kinetic energy)
With the updating algorithm we need only to invert the Slater determinant matrix once. This is done by calling standard LU decomposition methods.
The expectation value of the kinetic energy expressed in atomic units for electron i is
⟨ˆKi⟩=−12⟨Ψ|∇2i|Ψ⟩⟨Ψ|Ψ⟩,
Ki=−12∇2iΨΨ.
∇2ΨΨ=∇2(ΨDΨC)ΨDΨC=∇⋅[∇(ΨDΨC)]ΨDΨC=∇⋅[ΨC∇ΨD+ΨD∇ΨC]ΨDΨC=∇ΨC⋅∇ΨD+ΨC∇2ΨD+∇ΨD⋅∇ΨC+ΨD∇2ΨCΨDΨC
∇2ΨΨ=∇2ΨDΨD+∇2ΨCΨC+2∇ΨDΨD⋅∇ΨCΨC
The second derivative of the Jastrow factor divided by the Jastrow factor (the way it enters the kinetic energy) is
[∇2ΨCΨC]x= 2N∑k=1k−1∑i=1∂2gik∂x2k + N∑k=1(k−1∑i=1∂gik∂xk−N∑i=k+1∂gki∂xi)2
But we have a simple form for the function, namely
ΨC=∏i<jexpf(rij)=exp{∑i<jarij1+βrij},
and it is easy to see that for particle k we have
∇2kΨCΨC=∑ij≠k(rk−ri)(rk−rj)rkirkjf′(rki)f′(rkj)+∑j≠k(f″
Using
f(r_{ij})= \frac{ar_{ij}}{1+\beta r_{ij}},
and g'(r_{kj})=dg(r_{kj})/dr_{kj} and g''(r_{kj})=d^2g(r_{kj})/dr_{kj}^2 we find that for particle k we have
\frac{\nabla^2_k \Psi_C}{\Psi_C }=
\sum_{ij\ne k}\frac{(\mathbf{r}_k-\mathbf{r}_i)(\mathbf{r}_k-\mathbf{r}_j)}{r_{ki}r_{kj}}\frac{a}{(1+\beta r_{ki})^2}
\frac{a}{(1+\beta r_{kj})^2}+
\sum_{j\ne k}\left(\frac{2a}{r_{kj}(1+\beta r_{kj})^2}-\frac{2a\beta}{(1+\beta r_{kj})^3}\right)
The gradient and Laplacian can be calculated as follows:
\frac{\mathbf{\nabla}_i\vert\hat{D}(\mathbf{r})\vert}
{\vert\hat{D}(\mathbf{r})\vert} =
\sum_{j=1}^N \vec\nabla_i d_{ij}(\mathbf{r})\,
d_{ji}^{-1}(\mathbf{r}) =
\sum_{j=1}^N \vec\nabla_i \phi_j(\mathbf{r}_i)\,
d_{ji}^{-1}(\mathbf{r})
and
\frac{\nabla^2_i\vert\hat{D}(\mathbf{r})\vert}
{\vert\hat{D}(\mathbf{r})\vert} =
\sum_{j=1}^N \nabla^2_i d_{ij}(\mathbf{r})\,
d_{ji}^{-1}(\mathbf{r}) =
\sum_{j=1}^N \nabla^2_i \phi_j(\mathbf{r}_i)\,
d_{ji}^{-1}(\mathbf{r})
The gradient for the determinant is
\frac{\mathbf{\nabla}_i\vert\hat{D}(\mathbf{r})\vert}
{\vert\hat{D}(\mathbf{r})\vert} =
\sum_{j=1}^N \mathbf{\nabla}_i d_{ij}(\mathbf{r})\,
d_{ji}^{-1}(\mathbf{r}) =
\sum_{j=1}^N \mathbf{\nabla}_i \phi_j(\mathbf{r}_i)\,
d_{ji}^{-1}(\mathbf{r}).
We have
\Psi_C=\prod_{i < j}g(r_{ij})= \exp{\left\{\sum_{i < j}\frac{ar_{ij}}{1+\beta r_{ij}}\right\}},
the gradient needed for the quantum force and local energy is easy to compute. We get for particle k
\frac{ \nabla_k \Psi_C}{ \Psi_C }= \sum_{j\ne k}\frac{\mathbf{r}_{kj}}{r_{kj}}\frac{a}{(1+\beta r_{kj})^2},
which is rather easy to code. Remember to sum over all particles when you compute the local energy.
We need to compute the ratio between wave functions, in particular for the Slater determinants.
R =\sum_{j=1}^N d_{ij}(\mathbf{r}^{\mathrm{new}})\,
d_{ji}^{-1}(\mathbf{r}^{\mathrm{old}}) =
\sum_{j=1}^N \phi_j(\mathbf{r}_i^{\mathrm{new}})\,
d_{ji}^{-1}(\mathbf{r}^{\mathrm{old}})
What this means is that in order to get the ratio when only the i-th particle has been moved, we only need to calculate the dot product of the vector \left(\phi_1(\mathbf{r}_i^\mathrm{new}),\,\dots,\, \phi_N(\mathbf{r}_i^\mathrm{new})\right) of single particle wave functions evaluated at this new position with the i-th column of the inverse matrix \hat{D}^{-1} evaluated at the original position. Such an operation has a time scaling of O(N) . The only extra thing we need to do is to maintain the inverse matrix \hat{D}^{-1}(\mathbf{x}^{\mathrm{old}}) .
As a starting point we may consider that each time a new position is suggested in the Metropolis algorithm, a row of the current Slater matrix experiences some kind of perturbation. Hence, the Slater matrix with its orbitals evaluated at the new position equals the old Slater matrix plus a perturbation matrix,
\begin{equation}
\tag{14}
d_{jk}(\mathbf{x^{new}}) = d_{jk}(\mathbf{x^{old}}) + \Delta_{jk},
\end{equation}
where
\begin{equation}
\tag{15}
\Delta_{jk} = \delta_{ik}[\phi_j(\mathbf{x_{i}^{new}}) - \phi_j(\mathbf{x_{i}^{old}})] = \delta_{ik}(\Delta\phi)_j .
\end{equation}
Computing the inverse of the transposed matrix we arrive at
\begin{equation}
\tag{16}
d_{kj}(\mathbf{x^{new}})^{-1} = [d_{kj}(\mathbf{x^{old}}) + \Delta_{kj}]^{-1}.
\end{equation}
The evaluation of the right hand side (rhs) term above is carried out by applying the identity (A + B)^{-1} = A^{-1} - (A + B)^{-1} B A^{-1} . In compact notation it yields
\begin{eqnarray*}
[\mathbf{D}^{T}(\mathbf{x^{new}})]^{-1} & = & [\mathbf{D}^{T}(\mathbf{x^{old}}) + \Delta^T]^{-1}\\
& = & [\mathbf{D}^{T}(\mathbf{x^{old}})]^{-1} - [\mathbf{D}^{T}(\mathbf{x^{old}}) + \Delta^T]^{-1} \Delta^T [\mathbf{D}^{T}(\mathbf{x^{old}})]^{-1}\\
& = & [\mathbf{D}^{T}(\mathbf{x^{old}})]^{-1} - \underbrace{{[\mathbf{D}^{T}(\mathbf{x^{new}})]^{-1}}}_{\text{By Eq.}{\ref{invDkj}}} \Delta^T [\mathbf{D}^{T}(\mathbf{x^{old}})]^{-1}.
\end{eqnarray*}
Using index notation, the last result may be expanded by
\begin{eqnarray*}
d^{-1}_{kj}(\mathbf{x^{new}}) & = & d^{-1}_{kj}(\mathbf{x^{old}}) - \sum_{l} \sum_{m} d^{-1}_{km}(\mathbf{x^{new}}) \Delta^{T}_{ml} d^{-1}_{lj}(\mathbf{x^{old}})\\
& = & d^{-1}_{kj}(\mathbf{x^{old}}) - \sum_{l} \sum_{m} d^{-1}_{km}(\mathbf{x^{new}}) \Delta_{lm} d^{-1}_{lj}(\mathbf{x^{cur}})\\
& = & d^{-1}_{kj}(\mathbf{x^{old}}) - \sum_{l} \sum_{m} d^{-1}_{km}(\mathbf{x^{new}}) \delta_{im} (\Delta \phi)_{l} d^{-1}_{lj}(\mathbf{x^{old}})\\
& = & d^{-1}_{kj}(\mathbf{x^{old}}) - d^{-1}_{ki}(\mathbf{x^{new}}) \sum_{l=1}^{N}(\Delta \phi)_{l} d^{-1}_{lj}(\mathbf{x^{old}})\\
& = & d^{-1}_{kj}(\mathbf{x^{old}}) - d^{-1}_{ki}(\mathbf{x^{new}}) \sum_{l=1}^{N}[\phi_{l}(\mathbf{r_{i}^{new}}) - \phi_{l}(\mathbf{r_{i}^{old}})] D^{-1}_{lj}(\mathbf{x^{old}}).
\end{eqnarray*}
Using
\mathbf{D}^{-1}(\mathbf{x^{old}}) = \frac{adj \mathbf{D}}{|\mathbf{D}(\mathbf{x^{old}})|} \, \quad \text{and} \, \quad \mathbf{D}^{-1}(\mathbf{x^{new}}) = \frac{adj \mathbf{D}}{|\mathbf{D}(\mathbf{x^{new}})|},
and dividing these two equations we get
\frac{\mathbf{D}^{-1}(\mathbf{x^{old}})}{\mathbf{D}^{-1}(\mathbf{x^{new}})} = \frac{|\mathbf{D}(\mathbf{x^{new}})|}{|\mathbf{D}(\mathbf{x^{old}})|} = R \Rightarrow d^{-1}_{ki}(\mathbf{x^{new}}) = \frac{d^{-1}_{ki}(\mathbf{x^{old}})}{R}.
We have
d^{-1}_{kj}(\mathbf{x^{new}}) = d^{-1}_{kj}(\mathbf{x^{old}}) - \frac{d^{-1}_{ki}(\mathbf{x^{old}})}{R} \sum_{l=1}^{N}[\phi_{l}(\mathbf{r_{i}^{new}}) - \phi_{l}(\mathbf{r_{i}^{old}})] d^{-1}_{lj}(\mathbf{x^{old}}),
or
\begin{align}
d^{-1}_{kj}(\mathbf{x^{new}}) = d^{-1}_{kj}(\mathbf{x^{old}}) \qquad & - & \frac{d^{-1}_{ki}(\mathbf{x^{old}})}{R} \sum_{l=1}^{N}\phi_{l}(\mathbf{r_{i}^{new}}) d^{-1}_{lj}(\mathbf{x^{old}}) \nonumber\\
& + & \frac{d^{-1}_{ki}(\mathbf{x^{old}})}{R} \sum_{l=1}^{N}\phi_{l}(\mathbf{r_{i}^{old}}) d^{-1}_{lj}(\mathbf{x^{old}})\nonumber\\
= d^{-1}_{kj}(\mathbf{x^{old}}) \qquad & - & \frac{d^{-1}_{ki}(\mathbf{x^{old}})}{R} \sum_{l=1}^{N} d_{il}(\mathbf{x^{new}}) d^{-1}_{lj}(\mathbf{x^{old}}) \nonumber\\
& + & \frac{d^{-1}_{ki}(\mathbf{x^{old}})}{R} \sum_{l=1}^{N} d_{il}(\mathbf{x^{old}}) d^{-1}_{lj}(\mathbf{x^{old}}).\nonumber
\end{align}
In this equation, the first line becomes zero for j=i and the second for j \neq i . Therefore, the update of the inverse for the new Slater matrix is given by
\begin{eqnarray} \boxed{d^{-1}_{kj}(\mathbf{x^{new}}) = \left\{ \begin{array}{l l} d^{-1}_{kj}(\mathbf{x^{old}}) - \frac{d^{-1}_{ki}(\mathbf{x^{old}})}{R} \sum_{l=1}^{N} d_{il}(\mathbf{x^{new}}) d^{-1}_{lj}(\mathbf{x^{old}}) & \mbox{if $j \neq i$}\nonumber \\ \\ \frac{d^{-1}_{ki}(\mathbf{x^{old}})}{R} \sum_{l=1}^{N} d_{il}(\mathbf{x^{old}}) d^{-1}_{lj}(\mathbf{x^{old}}) & \mbox{if $j=i$} \end{array} \right.} \end{eqnarray}