Failures of the One-Step Learning Algorithm
David Mackay · 2001
The Hinton network (Hinton, 2001, personal communication) is a deterministic mapping from an observable space x to an energy function E(x; w), parameterized by parameters w. The energy defines a probability P (x|w) = exp(−E(x; w))/Z(w). A maximum likelihood learning algorithm for this density model takes steps ∆w ∝ − 〈g 〉 0 + 〈g 〉 ∞ where 〈g 〉 0 is the average of the gradient g = ∂E/∂w evaluated at points x drawn from the data density, and 〈g 〉 ∞ is the average gradient for points x drawn from P (x|w). If T is a Markov chain in x-space that has P (x|w) as its unique invariant density then we can approximate 〈g 〉 ∞ by taking the data points x and hitting each of them I times with T, where I is a large integer. In the one-step learning algorithm of Hinton (2001), we set I to 1. In this paper I give examples of models E(x; w) and Markov chains T for which the true likelihood is unimodal in the parameters, but the one-step algorithm does not necessarily converge to the maximum likelihood parameters. It is hoped that these negative examples will help pin down the conditions for the one-step algorithm to be a correctly convergent algorithm. The Hinton network (Hinton, 2001, personal communication) is a deterministic mapping from an observable space x of dimension D to an energy function E(x; w), parameterized by parameters w. The energy defines a probability where P (x|w) = exp(−E(x; w))