For sequential search problems, like left-to-right tagging and parsing, beam search has been successfully combined with perceptron variants that accommodate search errors (Collins and Roark, 2004; Huang et al., 2012).
perceptron training with inexact search is less studied for bottom-up parsing and, more generally, inference over hypergraphs.