Methods for learning to search for structured prediction typically imitate a reference policy, with existing theoretical guarantees demonstrating low regret compared to that reference. This is unsatisfactory in many applications where the reference policy is suboptimal and the goal of learning is to improve upon it. Can learning to search work even when the reference is poor? We provide a new learning to search algorithm, LOLS, which does well relative to the reference policy, but additionally guarantees low regret compared to deviations from the learned policy: a local-optimality guarantee. Consequently, LOLS can improve upon the reference policy, unlike previous algorithms. This enables us to develop structured contextual bandits, a partial information structured prediction setting with many potential applications.
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
> IMO RNNs do need some kind of structured loss (more than per step likelihood) to be competitive with HMM approaches using Viterbi decoding
This is exactly what they do with the dependency parser I've cited, so your opinion is definitely valid. Although their approach is not general, given the fact that they approximate hamming loss with log-loss and again make it work only on sequences.
http://arxiv.org/abs/1502.02206
paper above also has a very good analysis on how to remove the search component of the inference and allow linear time complexity with competitive results.
consistent (as it is used in the machine learning theory of reductions) reduction from structured…
Read the full comment
learning to multiclass classification seems to be possible. I just haven't seen anyone couple the learning procedure with neural networks. (Daume did mention they trained RNNs with the reductionist approach but seems that the code didn't make it to vowpal wabbit).
the approach above works with any loss you want (from F-score to any weird thing you might think of), the loss doesn't have to decompose over the structure (one can just announce the loss after the labelling is done and learn from that loss), it can work on any kind of structure, from images to sequences to documents for translation. it can also use a O(log n) consistent reduction of multiclass classification if speed is of the issue and if number of classes is large. It can easily work as an online method too, not requiring the full structured input.
for example, simple sequence tagging works (depending on the number of possible labels) around 500k tokens per second :D word count is only 2-4 times faster than that :D
there still aren't any papers using the above consistent reduction in the framework of NNs but I guess they'll soon be coming.
http://arxiv.org/abs/1603.06042
this is the paper.
the idea is based on the incredible incremental perceptron coupled with beam search for having different hypotheses at the same time trying to find a policy which will build them and select the best one
http://dl.acm.org/citation.cfm?id=1218970
The approach to structured prediction that was the fastest at the time was that incremental perceptron and the implementation extremely simple.
Some other approaches includes conditional random fields, hidden markov models, maximum margin markov networks, maximum entropy markov model and the approach they cite called SEARN (learning to search method - DAgger (Ross et al., 2011) and…
Read the full comment
AggreVaTe (Ross & Bagnell, 2014) and LOLS (Chang et al., 2015)).
http://arxiv.org/abs/1502.02206
Although, the syntaxnet team incorrectly dismisses SEARN (implying it suffers from label bias) but it isn't justified.
Their approach approximates 0/1 (hamming) loss with log-loss and works only on problems where the output decomposes over a sequence of decisions where each decision can have that incremental loss.
LOLS can work on arbitrary loss functions. For example, lets say you are translating a text from english to chinese, how can you say what the loss is when you've translated half a document? It's hard if not impossible to decompose the loss over decisions. (It's easy for part-of-speech tagging, the tag is either correct or not, or for dependency parsing, either the parent word is correct or not)
LOLS is a much superior method. It can also be combined with any binary classifier - SVM with any kernel, perceptron, logistic regression, to guide the decisions.
SyntaxNet uses a non-recurrent network to find the best parsing policy and the same network can be used on the LOLS approach.
Problem of structured prediction is incredible and extremely interesting. For example, doing POS tagging and dependency parsing at the same time can increase the performance on both task, same would be accomplished if one recognizes the named entities and at the same time tries to extract relationship between them.
It's very nice to see past insights applied with heavier machinery. Exciting times!
Checkout Dagger [2], SEARN [3] and LOLS [1] (LOLS is available in vowpal wabbit search capabilities). A lot of interesting stuff on mimicking optimal policies, local optimality, joint learning and similar stuff :D
The whole point of playing is doing your decisions jointly, dependent on the previous decisions. If you learn your model that way it'll make its decisions trying to minimize future regret.
Local optimality is a very nice property. It means that if you play out a game, not a single change of any of the previous moves could lead you to a better result. Of course, local optimality is hard but for some problems it's pretty easy to achieve if your optimal policy is…
Read the full comment
good, and your features are adequate (which they will be if you use neural networks).
Of course, flappy bird is pretty local game and all of this might be an overkill :D
AlphaGo wasn't trained jointly over Go games, so it's lacking in that regard. But the power of neural networks is compensating. Who can imagine what AlphaGo would be like if they trained their policy networks jointly? :D
A nice introduction to LSTMs:
http://colah.github.io/posts/2015-08-Understanding-LSTMs/
[1]: http://arxiv.org/pdf/1502.02206.pdf
[2]: http://arxiv.org/pdf/1011.0686.pdf
[3]: http://searn.hal3.name
What you are talking about here is called "label bias". [2] It is present only if training is done badly.
When you have a game of Go, or Super Mario level. You don't want to make your decisions by just checking the local features and doing them, because it can be the case that by compounding errors you end up in a state you never saw, and all of the future decisions won't be good.
One can avoid these situations by training jointly over the whole game.
For example, maximum entropy models can work for decision making problems but their training leaves them in a "label bias" state because the training is trying to minimize loss of local decisions, instead of trying to…
Read the full comment
minimize the future regret of current local decision.
The solution to these label bias problems are Conditional Random Fields, or Hidden Markov Models. You could accomplish the same with Recursive Neural Networks if you trained them properly. For example, there is no search part (monte carlo tree search, or dynamic programming [viterbi] like it is in CRFs or HMMs) in RNNs but they are completely adequate for decision based problems (sequence labeling etc.). Why is that the case? Because search results are present in the data, there's no need to search if you can just learn to search from the data.
If DeepMind open-sourced the hundreds of millions of games that AlphaGo played, it is quite possible to train a model that wouldn't need a Monte Carlo search and would work quite well, because you would learn the model to make local decisions to minimize future regret, not to minimize its local loss. [1]
The only reason why reinforcement learning is used is because there are too few human games of Go available for the model to generalize well. Reinforcement learning can be used in the setting of joint learning because you play out the whole game before you do the learning. This means that you can try to learn a classifier that will minimize the regret by making a proper local decision. Although, as far as I know, and can see from the paper, they didn't train AlphaGo jointly over the game sequence.
But! Now they have a lot of data and they can repeat the process.
[1]: http://arxiv.org/abs/1502.02206
[2]: http://repository.upenn.edu/cgi/viewcontent.cgi?article=1162...
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
The author presents two tricks to accelerate depth-first search algorithms for a class of combinatorial puzzle problems, such as tiling a tray by a fixed set of polyominoes.
Jon Kleinberg, Sendhil Mullainathan, Manish Raghavan
Recent discussion in the public sphere about algorithmic classification has involved tension between competing notions of what it means for a probabilistic classification to be fair to different groups.