|COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring.|
Mildly non-projective dependency parsing: algorithms and applications
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:
Note that ex-directory lists are not shown.
Other listsCambridge Assessment Network CSSA-Cambridge Abcam meetings
Other talksExcitability MYC and Metabolic Vulnerabilities of Cancer Making Waves and Sea to Shore Images inspired by the sea across five centuries, from the Fitzwilliam Museum and Kettle’s Yard '"Chantez la vie, l'amour, et la mort": the French 'chanson' in context' Galaxy clusters at sub-millimeter wavelengths Family reading and praying in the Italian Renaissance home