We could restrict the features to local scope on the candidate parses, allowing dynamic-programming to be used to train the model with a packed representation.
even with these restrictions, finding arg max t h p(t, h | s, Θ) is NP-hard, and the Viterbi approximation arg max t,h p(t, h | s, Θ) -or other approximations -would have to be used (see Matsuzaki et al.