Paper: Structured Perceptron with Inexact Search

ACL ID N12-1015
Title Structured Perceptron with Inexact Search
Venue Annual Conference of the North American Chapter of the Association for Computational Linguistics
Session Main Conference
Year 2012

Most existing theory of structured prediction assumes exact inference, which is often in- tractable in many practical problems. This leads to the routine use of approximate infer- ence such as beam search but there is not much theory behind it. Based on the structured perceptron, we propose a general framework of ?violation-fixing? perceptrons for inexact search with a theoretical guarantee for conver- gence under new separability conditions. This framework subsumes and justifies the pop- ular heuristic ?early-update? for perceptron with beam search (Collins and Roark, 2004). We also propose several new update meth- ods within this framework, among which the ?max-violation? method dramatically reduces training time (by 3 fold as compared to early- update) on state-of-the-art part-of-speech...