Your History

Menu

Probability of Setting a Unit to 1 in a BM

Prerequisites

Description

When a unit si\htmlClass{sdt-0000000091}{\mathbf{s}}_{\htmlClass{sdt-0000000018}{i}} is chosen for an update from iteration n \htmlClass{sdt-0000000117}{n} to n+1\htmlClass{sdt-0000000117}{n} + 1 this equation describes the probability that selected unit is set to 1, no matter what value it had at iteration n \htmlClass{sdt-0000000117}{n} . It is an instantiation of the Boltzmann acceptance function as seen in the derivation below.

Paccept(sin+1=1∣sn)=11+e−ΔEi/T\htmlClass{sdt-0000000135}{P_{\text{accept}}}(\htmlClass{sdt-0000000091}{\mathbf{s}}_{\htmlClass{sdt-0000000018}{i}}^{\htmlClass{sdt-0000000117}{n} + 1} = 1 | \mathbf{\htmlClass{sdt-0000000091}{\mathbf{s}}}^{\htmlClass{sdt-0000000117}{n}}) = \frac{1}{1 + \htmlClass{sdt-0000000035}{e}^{- \Delta \htmlClass{sdt-0000000100}{E}_{\htmlClass{sdt-0000000018}{i}} /\htmlClass{sdt-0000000029}{T}}}

Symbols Used:

This is the symbol for an iterator, a variable that changes value to refer to a sequence of elements.

T T

This symbol represents the temperature in a system.
e e

This symbol represents Euler's constant. It is approximately 2.7182.718.
s \mathbf{s}

This symbol represents a full description of the system taken at molecular level.
E E

This symbol represents the energy.
n n

This symbol represents any given whole number, n∈W n \in \htmlClass{sdt-0000000014}{\mathbb{W}}.
Paccept P_{\text{accept}}

This symbol represents the probability of accepting a proposal for the next state.

Derivation

Let us begin by considering the Boltzmann Acceptance Function:

Paccept(x∗ ∣  xn)=Paccept(x∗)Pacceptx∗)+Paccept(xn)\htmlClass{sdt-0000000135}{P_{\text{accept}}}(\htmlClass{sdt-0000000081}{\mathbf{x}^*} \,\vert\; \htmlClass{sdt-0000000046}{\mathbf{x}}_n) = \frac{ \htmlClass{sdt-0000000135}{P_{\text{accept}}}(\htmlClass{sdt-0000000081}{\mathbf{x}^*}) }{ \htmlClass{sdt-0000000135}{P_{\text{accept}}}\htmlClass{sdt-0000000081}{\mathbf{x}^*}) + \htmlClass{sdt-0000000135}{P_{\text{accept}}}(\htmlClass{sdt-0000000046}{\mathbf{x}}_n) }

In our situation, our probability distribution (Paccept \htmlClass{sdt-0000000135}{P_{\text{accept}}} ) will be a Boltzmann Distribution:

p(s)=1Zexp⁡{−E(s)T}p(\htmlClass{sdt-0000000091}{\mathbf{s}}) = \frac{1}{\htmlClass{sdt-0000000077}{Z}} \exp\left\{ - \frac{ \htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}) }{ \htmlClass{sdt-0000000029}{T} } \right\}

Noting that exp⁡{x}\exp\{\htmlClass{sdt-0000000003}{x}\} is equivalent to ex\htmlClass{sdt-0000000035}{e}^{\htmlClass{sdt-0000000003}{x}}, we can substitute in our equation for the Boltzmann Distribution into our Boltzmann Acceptance Function:

Paccept(sin+1∣sn)=1Zexp⁡{−E(sn+1)T}1Zexp⁡{−E(sn+1)T}+1Zexp⁡{−E(sn)T}\htmlClass{sdt-0000000135}{P_{\text{accept}}}(\htmlClass{sdt-0000000091}{\mathbf{s}}_{\htmlClass{sdt-0000000018}{i}}^{\htmlClass{sdt-0000000117}{n} + 1} |\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n}})=\frac{\frac{1}{\htmlClass{sdt-0000000077}{Z}}\exp\{-\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n} + 1})}{\htmlClass{sdt-0000000029}{T}}\}}{\frac{1}{\htmlClass{sdt-0000000077}{Z}}\exp\{-\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n} + 1})}{\htmlClass{sdt-0000000029}{T}}\} + \frac{1}{\htmlClass{sdt-0000000077}{Z}}\exp\{-\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n}})}{\htmlClass{sdt-0000000029}{T}}\}}

We can now simplify by factoring 1Z\frac{1}{\htmlClass{sdt-0000000077}{Z}} out of the denominator:

Paccept(sin+1∣sn)=1Zexp⁡{−E(sn+1)T}1Z(exp⁡{−E(sn+1)T}+exp⁡{−E(sn)T})\htmlClass{sdt-0000000135}{P_{\text{accept}}}(\htmlClass{sdt-0000000091}{\mathbf{s}}_{\htmlClass{sdt-0000000018}{i}}^{\htmlClass{sdt-0000000117}{n} + 1}|\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n}})=\frac{\frac{1}{\htmlClass{sdt-0000000077}{Z}}\exp\{-\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n} + 1})}{\htmlClass{sdt-0000000029}{T}}\}}{\frac{1}{\htmlClass{sdt-0000000077}{Z}}(\exp\{-\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n} + 1})}{\htmlClass{sdt-0000000029}{T}}\} + \exp\{-\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n}})}{\htmlClass{sdt-0000000029}{T}}\})}

and simplify further by dividing both the numerator and denominator by 1Z\frac{1}{\htmlClass{sdt-0000000077}{Z}}

Paccept(sin+1∣sn)=exp⁡{−E(sn+1)T}exp⁡{−E(sn+1)T}+exp⁡{−E(sn)T}\htmlClass{sdt-0000000135}{P_{\text{accept}}}(\htmlClass{sdt-0000000091}{\mathbf{s}}_{\htmlClass{sdt-0000000018}{i}}^{\htmlClass{sdt-0000000117}{n} + 1}|\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n}})=\frac{\exp\{-\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n} + 1})}{\htmlClass{sdt-0000000029}{T}}\}}{\exp\{-\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n} + 1})}{\htmlClass{sdt-0000000029}{T}}\} + \exp\{-\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n}})}{\htmlClass{sdt-0000000029}{T}}\}}

We will now factor out the term exp⁡{−E(sn+1)T}\exp\{-\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n} + 1})}{\htmlClass{sdt-0000000029}{T}}\} from the denominator, which gives us:

Paccept(sin+1∣sn)=exp⁡{−E(sn+1)T}exp⁡{−E(sn+1)T}(1+exp⁡{−E(sn)T}exp⁡{−E(sn+1)T})\htmlClass{sdt-0000000135}{P_{\text{accept}}}(\htmlClass{sdt-0000000091}{\mathbf{s}}_{\htmlClass{sdt-0000000018}{i}}^{\htmlClass{sdt-0000000117}{n} + 1}|\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n}})=\frac{\exp\{-\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n} + 1})}{\htmlClass{sdt-0000000029}{T}}\}}{\exp\{-\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n} + 1})}{\htmlClass{sdt-0000000029}{T}}\}( 1 + \frac{\exp\{-\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n}})}{\htmlClass{sdt-0000000029}{T}}\}}{\exp\{-\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n} + 1})}{\htmlClass{sdt-0000000029}{T}}\}})}

The term exp⁡{−E(sn+1)T}\exp\{-\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n} + 1})}{\htmlClass{sdt-0000000029}{T}}\} can now be cancelled out from the numerator and denominator, giving us:

Paccept(sin+1∣sn)=11+exp⁡{−E(sn)T}exp⁡{−E(sn+1)T}\htmlClass{sdt-0000000135}{P_{\text{accept}}}(\htmlClass{sdt-0000000091}{\mathbf{s}}_{\htmlClass{sdt-0000000018}{i}}^{\htmlClass{sdt-0000000117}{n} + 1}|\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n}})=\frac{1}{1 + \frac{\exp\{-\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n}})}{\htmlClass{sdt-0000000029}{T}}\}}{\exp\{-\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n} + 1})}{\htmlClass{sdt-0000000029}{T}}\}}}

We can now use the fact that exp⁡{x}\exp\{\htmlClass{sdt-0000000003}{x}\} is identical to ex\htmlClass{sdt-0000000035}{e}^{\htmlClass{sdt-0000000003}{x}} as well as the formula for the division of exponents:

axay=ax−y\frac{\htmlClass{sdt-0000000121}{a}^{\htmlClass{sdt-0000000003}{x}}}{\htmlClass{sdt-0000000121}{a}^{\htmlClass{sdt-0000000017}{y}}} = \htmlClass{sdt-0000000121}{a}^{\htmlClass{sdt-0000000003}{x} - \htmlClass{sdt-0000000017}{y}}

and get:

Paccept(sin+1∣sn)=11+exp⁡{−E(sn)T−−E(sn+1)T}\htmlClass{sdt-0000000135}{P_{\text{accept}}}(\htmlClass{sdt-0000000091}{\mathbf{s}}_{\htmlClass{sdt-0000000018}{i}}^{\htmlClass{sdt-0000000117}{n} + 1}| \htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n}})=\frac{1}{1 + \exp\{-\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n}})}{\htmlClass{sdt-0000000029}{T}} - -\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n} + 1})}{\htmlClass{sdt-0000000029}{T}}\}}

Because two negatives make a positive and rules of fraction addition, we can simplify further to

Paccept(sin+1∣sn)=11+exp⁡{−E(sn)+E(sn+1)T}\htmlClass{sdt-0000000135}{P_{\text{accept}}}(\htmlClass{sdt-0000000091}{\mathbf{s}}_{\htmlClass{sdt-0000000018}{i}}^{\htmlClass{sdt-0000000117}{n} + 1}|\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n}})=\frac{1}{1 + \exp\{\frac{-\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n}}) + \htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n} + 1})}{\htmlClass{sdt-0000000029}{T}}\}}

We can now swap around the terms in the exponent in the denominator to get:

Paccept(sin+1∣sn)=11+exp⁡{E(sn+1)−E(sn)T}\htmlClass{sdt-0000000135}{P_{\text{accept}}}(\htmlClass{sdt-0000000091}{\mathbf{s}}_{\htmlClass{sdt-0000000018}{i}}^{\htmlClass{sdt-0000000117}{n} + 1}| \htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n}})=\frac{1}{1 + \exp\{\frac{\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n} + 1}) - \htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n}})}{\htmlClass{sdt-0000000029}{T}}\}}

We can now say:

ΔE=E(sn+1)−E(sn)\htmlClass{sdt-0000000105}{\Delta} \htmlClass{sdt-0000000100}{E} = \htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n} + 1}) - \htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n}})

Meaning that "The change in energy will be the energy at the next state, minus the energy at the current state".

We can now substitute this into our equation to get:

Paccept(sin+1∣sn)=11+exp⁡{−ΔEiT}\htmlClass{sdt-0000000135}{P_{\text{accept}}}(\htmlClass{sdt-0000000091}{\mathbf{s}}_{\htmlClass{sdt-0000000018}{i}}^{\htmlClass{sdt-0000000117}{n} + 1}|\htmlClass{sdt-0000000091}{\mathbf{s}}^{\htmlClass{sdt-0000000117}{n}})=\frac{1}{1 + \exp\{\frac{-\htmlClass{sdt-0000000105}{\Delta} \htmlClass{sdt-0000000100}{E}_{\htmlClass{sdt-0000000018}{i}}}{\htmlClass{sdt-0000000029}{T}}\}}

Finally, we can use the fact that exp⁡{x}\exp\{\htmlClass{sdt-0000000003}{x}\} is identical to ex\htmlClass{sdt-0000000035}{e}^{\htmlClass{sdt-0000000003}{x}} to get:

Paccept(sin+1=1∣sn)=11+e−ΔEi/T\htmlClass{sdt-0000000135}{P_{\text{accept}}}(\htmlClass{sdt-0000000091}{\mathbf{s}}_{\htmlClass{sdt-0000000018}{i}}^{\htmlClass{sdt-0000000117}{n} + 1} = 1 | \mathbf{\htmlClass{sdt-0000000091}{\mathbf{s}}}^{\htmlClass{sdt-0000000117}{n}}) = \frac{1}{1 + \htmlClass{sdt-0000000035}{e}^{- \Delta \htmlClass{sdt-0000000100}{E}_{\htmlClass{sdt-0000000018}{i}} /\htmlClass{sdt-0000000029}{T}}}

as required.

References

  1. Jaeger, H. (n.d.). Neural Networks (AI) (WBAI028-05) Lecture Notes BSc program in Artificial Intelligence. Retrieved June 9, 2024, from https://www.ai.rug.nl/minds/uploads/LN_NN_RUG.pdf