Somewhere between dynamic programming and beam search

Recently forest based reranking has gained more attention. Instead of reranking at the root of N different parse trees, the decoder can rerank local candidates at different nodes that are generated during the dynamic programming process. This method combines some advantages from dp (i.e. memoisation) and beam-search (i.e. faster decoding).

Thinking about the multiple beam decoder I used for joint segmentation and tagging, I find some similarities in thinking. Our decoder is not a reranking algorithm, it can be viewed as a reduced version of building a dynamic programming chart: instead of filling every cell in a chart, we only keep N-best items for each character. This is also somewhere between beam-search and dynamic programming.

There is always a balance between efficiency and accuracy, particularly when we want to use discriminative training with wide-coverage features. The disadvantage of using a beam, as one can argue, is the loss of optimality. But the effectiveness of NLP is not totally dependent on mathematics in decoding; I think the model structure is much more important here. As I always reckon - we don't have to do a full chart parsing to understand sentences anyway.