Machine learning; Boltzmann machines

Machine learning

Machine learning is the branch of AI in which a program improves its performance at a task through experience (data) rather than explicit programming. Main kinds: supervised, unsupervised and reinforcement learning.

Boltzmann machine

A Boltzmann machine (Hinton and Sejnowski, 1985) is a stochastic recurrent neural network of binary units (0/1 or ±1) joined by symmetric weights (wij = wji, wii = 0). Units are of two kinds: visible units (input/output) and hidden units. It is the stochastic version of the Hopfield network; simulated annealing lets it escape local minima. It is named after the Boltzmann distribution of statistical mechanics.

   hidden:   (h1)---(h2)---(h3)
              | \  /  | \  /  |
   visible:  (v1)---(v2)---(v3)

Energy and probability

• Energy of a state s: E = −Σ_{i<j} w_ij s_i s_j − Σ_i θ_i s_i
• Energy gap for unit i: ΔE_i = Σ_j w_ij s_j + θ_i
• Unit turns on with probability p(s_i = 1) = 1 / (1 + e^(−ΔE_i / T)), T = temperature.
• At high T the units behave almost randomly (exploration); as T→0 the rule becomes the deterministic Hopfield threshold.
• At equilibrium, P(state) ∝ e^(−E/T): low-energy states are more probable.

Algorithm

A. Recall / optimisation (simulated annealing)

1. Initialise weights, set the visible units to the input, start with a high temperature T.
2. Pick a unit at random; compute ΔE_i and set it on with probability 1/(1 + e^(−ΔE_i/T)).
3. Repeat for many updates until equilibrium at this T.
4. Lower T gradually (annealing schedule, e.g. T ← 0.9T) and repeat from step 2.
5. Stop when the state stops changing at low T; the final state is a low-energy (best) solution.

B. Learning

1. Positive phase: clamp the visible units to a training pattern, let the hidden units reach equilibrium, and measure the average co-activation p⁺_ij = ⟨s_i s_j⟩ clamped.
2. Negative phase: run the network freely (nothing clamped) to equilibrium and measure p⁻_ij.
3. Update each weight: Δw_ij = η (p⁺_ij − p⁻_ij).
4. Repeat over all patterns until the model distribution matches the data distribution (the weights stop changing).

Remarks

• Can learn internal representations and solve constraint satisfaction and optimisation problems.
• Training is very slow because equilibrium sampling is needed; restricted Boltzmann machines (RBM), which remove the connections within a layer, make it practical.