The Surprising Variance in Shortest-Derivation Parsing

TitleThe Surprising Variance in Shortest-Derivation Parsing
Publication TypeConference Paper
Year of Publication2011
AuthorsBansal, M., & Klein D.
Other Numbers3270

We investigate full-scale shortest-derivationparsing (SDP), wherein the parser selects ananalysis built from the fewest number of trainingfragments. Shortest derivation parsingexhibits an unusual range of behaviors. Atone extreme, in the fully unpruned case, itis neither fast nor accurate. At the other extreme,when pruned with a coarse unlexicalizedPCFG, the shortest derivation criterionbecomes both fast and surprisingly effective,rivaling more complex weighted-fragment approaches.Our analysis includes an investigationof tie-breaking and associated dynamicprograms. At its best, our parser achieves an


We would like to thank Adam Pauls, Slav Petrovand the anonymous reviewers for their helpful suggestions.This research is supported by BBN underDARPA contract HR0011-06-C-0022 and by theOffice of Naval Research under MURI Grant No.N000140911081. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors or originators and do not necessarily reflect the views of the funders.

Bibliographic Notes

Proceedings of the 49th annual Meeting of the Association for Computational Linguistics (ACL HLT 2011), Portland, Oregon

Abbreviated Authors

M. Bansal and D. Klein

ICSI Research Group


ICSI Publication Type

Article in conference proceedings