Your History

Menu

Ratio Metropolis Acceptance Function

Prerequisites

Boltzmann Distribution of Microstates | \(p(\mathbf{s}) = \frac{1}{Z} \exp\left\{ - \frac{ E(\mathbf{s}) }{ T } \right\}\)
Metropolis Acceptance Function | \(XacceptanceProbability(\mathbf{x}^* \,\vert\; \mathbf{x}_n) = \begin{cases} 1, &\textup{ if } XmeasureFunction(\mathbf{x}^*) \geq XmeasureFunction(\mathbf{x}_n) \\ \frac{XmeasureFunction(\mathbf{x}^*)}{XmeasureFunction(\mathbf{x}_n)}, &\textup{ if } XmeasureFunction(\mathbf{x}^*) < XmeasureFunction(\mathbf{x}_n)\end{cases}\)

Description

If \(\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000081}{\mathbf{x}^*}) > \htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000046}{\mathbf{x}}_{\htmlClass{sdt-0000000117}{n}})\) this equation can be used to calculate the probability of accepting the proposed next state \(\htmlClass{sdt-0000000081}{\mathbf{x}^*}\) in a Boltzmann machine.

\[\exp(\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000046}{\mathbf{x}}_{\htmlClass{sdt-0000000117}{n}}) - \htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000081}{\mathbf{x}^*}))^{\frac{1}{\htmlClass{sdt-0000000029}{T}}}\]

Symbols Used:

This symbol represents the temperature in a system.
\( \mathbf{x} \)

This symbol represents a state of the dynamical system at some time point.
\( \mathbf{x}^* \)

This symbol represents a random proposal for the next state in the sampling sequence.
\( E \)

This symbol represents the energy.
\( n \)

This symbol represents any given whole number, \( n \in \htmlClass{sdt-0000000014}{\mathbb{W}}\).

Derivation

  1. Recall the defintion of the metropolis acceptance function:
    \[\htmlClass{sdt-0000000131}{X}acceptanceProbability(\htmlClass{sdt-0000000081}{\mathbf{x}^*} \,\vert\; \htmlClass{sdt-0000000046}{\mathbf{x}}_n) = \begin{cases} 1, &\textup{ if } \htmlClass{sdt-0000000131}{X}measureFunction(\htmlClass{sdt-0000000081}{\mathbf{x}^*}) \geq \htmlClass{sdt-0000000131}{X}measureFunction(\htmlClass{sdt-0000000046}{\mathbf{x}}_n) \\ \frac{\htmlClass{sdt-0000000131}{X}measureFunction(\htmlClass{sdt-0000000081}{\mathbf{x}^*})}{\htmlClass{sdt-0000000131}{X}measureFunction(\htmlClass{sdt-0000000046}{\mathbf{x}}_n)}, &\textup{ if } \htmlClass{sdt-0000000131}{X}measureFunction(\htmlClass{sdt-0000000081}{\mathbf{x}^*}) < \htmlClass{sdt-0000000131}{X}measureFunction(\htmlClass{sdt-0000000046}{\mathbf{x}}_n)\end{cases}\]
    And recall the definition of the Boltzmann distribution:
    \[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\}\]
    Clearly when \(\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000081}{\mathbf{x}^*}) \leq \htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000046}{\mathbf{x}}_{\htmlClass{sdt-0000000117}{n}})\)
    The proposed state \( \htmlClass{sdt-0000000081}{\mathbf{x}^*} \) is accepted with a probability of 1.
  2. When \(\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000081}{\mathbf{x}^*}) > \htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000046}{\mathbf{x}}_{\htmlClass{sdt-0000000117}{n}})\) the ratio becomes:
    \[\frac{\htmlClass{sdt-0000000131}{X}measureFunction(\htmlClass{sdt-0000000081}{\mathbf{x}^*})}{\htmlClass{sdt-0000000131}{X}measureFunction(\htmlClass{sdt-0000000046}{\mathbf{x}}_n)} = \frac{\exp(-\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000081}{\mathbf{x}^*})/\htmlClass{sdt-0000000029}{T})}{\exp(-\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000046}{\mathbf{x}}_{\htmlClass{sdt-0000000117}{n}})/\htmlClass{sdt-0000000029}{T})} = \exp(\htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000046}{\mathbf{x}}_{\htmlClass{sdt-0000000117}{n}}) - \htmlClass{sdt-0000000100}{E}(\htmlClass{sdt-0000000081}{\mathbf{x}^*}))^{\frac{1}{\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