Gradients in arbitrary CRF?

Great, thanks! I mentioned loopy L-BFGS just for loopy topologies; on a chain or tree I just run one forward and one backward pass, of course. After a bug fix it's all working now, incl. L-BFGS on chains and trees.

It's probably better to use a variational approximation than loopy bp for precisely these issues.

Another approach is pseudo-likelihood, you can compute gradient exactly and resulting estimator is consistent (unlike variational methods) http://arxiv.org/abs/1003.0691

Thanks, I agree, generating data from the model and then decoding it is a great debugging method. I found that the strange behavior was due to a bug and rounding errors, and the optimization is working now. You write that you can always use L-BFGS if you can compute the gradient. But I think I won't be able to use L-BFGS in the loopy case, since the gradients and the objective value are then approximate and may not exactly match, so I expect L-BFGS to fail in that case. But SGD and RProp may still work, although, like you say, in a highly connected graph it might give bad results.

L-BFGS is really just an improved version of gradient descent. Why do you think SGD will work better with approximate gradients?

Because L-BFGS does not behave very well when the gradient changes a lot---it builds an approximation to the hessian that can be wildly unstable if the gradient varies a lot. Line minimizers also behave really badly in this setting, since for two function evaluations the values can be completely different, so it's hard to find a minimum (and most L-BFGS implementations rely on a line minimizer).

If estimate of the Hessian is wildly unstable, then the gradient must be even more wildly unstable (since the estimated hessian is a kind of average of last few gradients), so it seems like any gradient based method will have a problem there

This doesn't necessarily follow: suppose we're in the middle of training, and some examples are reasonably well classified while others are wrong. If you're doing SGD, some of the time you will make a big update (for the really wrong things) and some of the time you will make a small update (for the almost correct things). SGD just doesn't remember what happened last iteration.

Now assume you're doing just SGD+line minimization (roughly l-bfgs when m=1). The first round gets a function value and a gradient, and steps in the direction of the gradient with some default step size it plans to narrow later. Then it evaluates the function, to see if the reduction is big enough, or if it needs to narrow/increase the step size. However, imagine you picked a very wrong example in the first step, and now you pick a very well-classified example: even if the step didn't change much, L-BFGS thinks it has succeeded and moves on to another iteration. On the other hand, suppose the first iteration picks a mostly correct example and the second picks a really incorrect one: now suddenly the line minimizer thinks that step was really crappy (remember log loss can vary in orders of magnitude between different examples in the beggining of training) and gets another example, which gets a completely different log loss, etc. How can you do reliable line minimization in this setting?

Stochastic second-order optimization methods generally avoid using line searches for this very reason. See james martens' paper on hessian-free methods or http://eprints.pascal-network.org/archive/00003992/01/SchYuGue07.pdf on a stochastic version of l-bfgs for similar issues.