Applications of Hessian-Free Deep Learning

Hey all, I also want to put forward some results of Ilya Sutskever that he presented at CIfAR 2010. He basically used James Martens' method to train a recurrent neural network. I will not go into details of the experiment, and I expect a paper to appear soon on this subject. What he did was to train a RNN on wikipedia, where the network got as input a one-hot encoding of a character and was suppose to predict the next character. He used 2000 units ( quite a lot for a RNN) and trained it one month on the GPU ( maybe a year in CPU time or more - that is Ilya prediction ). Note that this is not your ordinary experiment, I for one would not have the patience to let it run for 30 days or so. Anyhow the results are amazing. First of all the RNN seems ( I haven't seen conclusive results in this respect, and Ilya just started playing with this) not to suffer from the vanishing gradient problem any more( he also tested this on a task proposed by Schmidhuber et al. in their first paper about LSTM; the task is known to be solvable only by LSTMs and was meant to show that LSTM can deal with connecting events that are far away in time). But the most amazing thing is that he could use the RNN to generate text which was coherent for a few words ( it would also remember to close brackets in some cases and so on). There are yet no qualitative measures of the network behaviour I think ( or Ilya has not presented any for now), so this are very recent results. But we can of course speculate on how well this training method works. After talking to Ilya I also got a few samples generated by the network ( I will post one here, hope he doesn't mind) :

Shortly thereafter it was purchased by the army attacks on Bill World Service, like many of which recognize the Oscar's liberation of the nobility before he desired anything obey, instead of , I to be flooding during the civil war, has been fell.

I'm currently investigating James Martens' algorithm, as well as going over Yoshua's paper on vanishing gradient trying to make sense out of all this. My intent is also to implement the algorithm with Theano (which should make the GPU stuff transparent). Once and if I manage to do that, I will definitely not mind sharing my thoughts and code.

I had a brief email conversation with James Martens about his paper, and came away with some info that may be useful if you're out to reproduce his algorithm.

The algorithm itself is rather simple in the sense that it doesn't require a ton of code, but wrapping your head around it might be a little more arduous depending on your background.

As reading material to become more familiar with some of the concepts, he recommended "Numerical Optimization" by Stephen Wright (ISBN 0387303030) which, among other things, gives some good background info on line search, trust region, conjugate gradient, and various other optimization techniques. Compared to other technically oriented books I find it rather readable (definitely not for the faint of heart, though; decent exposure to math recommended), though I'll freely admit I've only read through the first 4-5 chapters so far.

Although I wretch to think about the notation used in the book, you might also look at "Numerical Analysis" by Burden & Faires for some background info if you're not ready to jump into Wright's book. There's probably far better books out there than B&F; that's what we used in my numerical analysis class.

As for implementing the algorithm, go to Hinton's home page and download the Matlab source for their MNIST digit classifier (Hinton & Tieleman, ~2006 or 2007). If you open backprop.m, this code is used to do the backprop refining after pre-training with contrastive divergence.

At first glance it might appear somewhat hairy. When you peel back the layers, it's just backprop with a non-linear CG solver (minimize.m) to minimize the weight update using 3 line searches.

Martens' method replaces the code that uses non-linear CG with a quadratic approximation near the current region of the error surface, parameterized by the weights (q(theta)). Then he's using linear conjugate gradient (burden & faires has simple and well-written, albeit poorly described due to notation, CG algorithm at the end of chapter 7) with an n < N step line search to determine how much to 'trust' the given solution.

For those less familiar with conjugate gradient, it's a fairly straightforward method. Chapter 7 of B&F starts out by covering some iterative methods for solving linear systems of the form Ax=b, explaining better heuristics for improving the runtime, finally ending with CG.

At the heart of many iterative methods is the idea of a stationary point of a function. Any parameter satisfying x = f(x) is a stationary point of the function f(x). Many iterative methods exploit this idea by setting up a linear system related to the original Ax=b, taking a form similar to: x = Tx + c.

CG starts out with an initial approximation to the solution, taking a step in some direction that gets even closer. On the 2nd step, a new direction is chosen that is perpendicular to the first parameter update. The method successively chooses new directions to move that are perpendicular to all prior parameter updates.

At worst, with linear CG you're pretty much guaranteed not to lose ground after any given iteration, and in most cases you'll always see large improvements very early on. Early convergence of CG is [usually] extremely rapid even with a very poor estimate of the initial starting point -- also, this highly depends on how poorly conditioned the matrix A is in Ax=b. If it is poorly conditioned -- well, you can look that one up if you're interested.

In a typical Ax=b problem, you want the most accurate estimate for 'x' possible. In this case, we just want to move in a good direction. Provided the problem is conditioned well enough, CG is absolutely guaranteed to converge in N steps (where A is NxN). In a number of steps that can often be much smaller than N, CG can produce a pretty significant improvement particularly considering we don't really care to find the most accurate solution to Ax=b, just an 'x' that moves us in a good direction in our rough, local, quadratic approximation.

That is probably the single biggest win in Martens' method. Non-linear CG, as he and others point out, loses conjugacy after only a few iterations if the problem is highly non-linear. In short, this means that producing a change to the parameters conjugate to prior changes and in the same [rough] direction as the gradient is less effective than in linear CG, so you can't do any early stopping with non-linear CG and have any hope of having a good improvement to your parameters -- whereas in linear CG you can almost always expect a very good improvement after only a few iterations.

I'll quiet down now. Hopefully I haven't made any gross errors in my attempt and helping.

-Brian

Thank you for bringing this article to my attention I find the results and method very interesting. I am sure I share your disappointment at not yet having a reply from the very knowledgable folks here at MO.

It's a pity there is very little actual code to go along with the paper, are you aware of any source that would get us kick started on replicating the findings of the paper.

For the applications I use Hinton's DBMs I particularly like their poperty that unclassified examples can be used to improve results. It appears that this work shares that ability through the application of pretraining. However as of yet I have not seen any effort to quantify the effect of PT beyound improving the convergence rate.

As I said this is extreamly interesting work, I only wish the author was as genorous as Hinton generally is with his code.

On another note, I'm curious to see some hybrid approaches.

Initially, the weights for the entire system are completely random. To some extent, I still expect there to be some issues with the learning signal to be less effective for the earliest layers in a deep net (though I don't have any data to back that up).

There's a myriad of variations on this theme I've mulled over, but I'll point out two or three that seem at least worth thinking over.

With the type of architecture Martens' used in his paper (a number of layers, with sort of 'shadow' copies of those layers used to reconstruct the original data) as an end-goal, start with only 3 layers: inputs, intermediate, and reconstructed input. Using this method, perform enough training to remove some of the randomness from the weights, then add a 2nd hidden layer and repeat the process until the entire 'net has been built.

Another approach could be a hybrid between contrastive divergence learning (on each set of weights in parallel), and the HF optimized approach. This seems less likely to be as beneficial, but I may be overlooking something.

Linear and quadratic programming problems are often stated as "Solve < X > subject to < some list of conditions >". CD learning uses as its objective the minimization of the log probability of the joint probability distribution, possibly subject to some minor constraints (magnitude of the weights are small, sparsity constraints, etc).

We can always add more constraints to the mix, or modify the objective function. For example, rather than minimizing log(P(V,H)), we might produce a quadratic approximation of the objective function and use Martens' HF optimization method to come up with a new variation on contrastive divergence.

For example, one of Yann LeCunn's basic approaches is to minimize two (or more) separate objective functions. Each iteration, the weight update scheme might look like this:

pass 1: update weights in an attempt to improve constraint #1 pass 2: update weights in an attempt to improve constraint #2 pass 3: update weights in an attempt to improve constraint #1 pass 4: update weights in an attempt to improve constraint #2 pass 5: update weights in an attempt to improve constraint #1 pass 6: update weights in an attempt to improve constraint #2 ...

Anyway, it's getting to be bed time.

-Brian