University of Cambridge > Talks.cam > NLIP Seminar Series >  Mildly non-projective dependency parsing: algorithms and applications

Mildly non-projective dependency parsing: algorithms and applications

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Johanna Geiss.

Although non-projective syntactic constructions occur in natural languages, many practical implementations of dependency parsing are restricted to projective structures for efficiency reasons, since the problem of unrestricted non-projective dependency parsing is intractable in the general case. However, it has been observed that most non-projective structures appearing in practice are close to being projective. This has led researchers to study sets of mildly non-projective dependency structures, i.e., classes of dependency structures that lie between projective and unrestricted non-projective structures, in the search for a balance between coverage and efficiency.

In the first part of this talk, I will define a deductive formalism to describe dependency parsers, based on Sikkel’s parsing schemata for constituency parsers; and show examples of how it can be used to describe, analyse and compare well-known projective and non-projective parsers. I will then use this formalism to define polynomial-time parsing algorithms for several classes of mildly non-projective dependency structures, including that of well-nested structures with gap degree bounded by a constant k, and a new class of structures with gap degree up to k (including some ill-nested structures) which contains all the structures in a number of dependency treebanks. Finally, I will show how a variant of the latter algorithm can be employed to solve a non-parsing problem: binarising linear context-free rewriting systems without increasing their fan-out in all the cases where this is possible.

The research presented in this talk is joint work with David Weir, John Carroll, Marco Kuhlmann and Giorgio Satta.

This talk is part of the NLIP Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2024 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity