Mildly non-projective dependency parsing: algorithms and applications

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

• Carlos Gómez - University of Corunna
• Friday 29 May 2009, 12:00-13:00
• SW01, Computer Laboratory.

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.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge Forum of Science and Humanities
• Cambridge Language Sciences
• Cambridge talks
• Chris Davis' list
• Computer Education Research
• Computing Education Research
• Department of Computer Science and Technology talks and seminars
• Graduate-Seminars
• Guy Emerson's list
• Interested Talks
• Language Sciences for Graduate Students
• NLIP Seminar Series
• PMRFPS's
• SW01, Computer Laboratory
• Simon Baker's List
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• rp587

Note that ex-directory lists are not shown.