Neural Nets for NLP 2020: Advanced Search Algorithms

Explore advanced search algorithms for neural networks in natural language processing through this comprehensive lecture. Delve into search errors and model errors, examining their impact on output optimization. Learn about beam search and its variants, understanding how to determine optimal beam size. Discover the concept of minimum Bayes risk and its application in reranking. Investigate heuristics modification techniques to enhance search performance. Explore sampling-based search methods and their role in improving diversity. Analyze common model errors like length bias and learn strategies to mitigate them, including length normalization and output length prediction. Gain insights into the pros and cons of sampling-based search approaches and alternative methods for achieving diversity in results.

Syllabus

Intro
The Generation Problem
Ancestral Sampling
Why do we Search?
Search Errors, Model Errors example from Neubig (2015) • Search error: the search algorithm fails to find an output that optimizes its search criterion . Model error: the output that optimizes the search criterion does not optimize accuracy
What beam size should I use?
Better Search can Hurt Results! (Koehn and Knowles 2017)
How to Fix Model Errors?
Minimum Bayes Risk Reranking
Improving Diversity in top N Choices
A Typical Model Error: Length Bias
Length Normalization
Predict the output length (Eriguchi et al. 2016)
Cautions about Sampling- based Search · Is sampling necessary for diversity?: questionable, we could do diverse beam search instead