Seminaire: Expose Brian Roark, Jeudi 19 mars

[Thierry Hamon]

Date: Tue, 10 Mar 2009 18:03:26 +0100
From: bcrabbe at linguist.jussieu.fr
Message-ID: <1236704606.49b69d5e8cae0 at kmail.linguist.univ-paris-diderot.fr>


Bonjour,

lors de son passage à Paris la semaine prochaine,

Brian Roark

fera un exposé jeudi prochain de 10.00 à 12.00
à l'UFRL Paris 7
30 rue du Chateau des rentiers,
75013 Paris
salle 134

toute personne intéressée est la bienvenue.


Titre:
Finite-state chart constraints for reduced complexity context-free
parsing pipelines

Abstract:
The cubic complexity of context-free inference limits the
applicability of syntactic parsers when applications have either
strong time constraints (e.g., real-time requirements) or deal with
very large data sets. Reducing the complexity of these algorithms is
key to leveraging syntactic information in such applications. In the
first part of this talk, we consider classifying word positions by
whether or not they can either start or end multi-word constituents.
This provides a mechanism for "closing" chart cells during
context-free inference, which is demonstrated to improve efficiency
and accuracy when used to constrain the well-known Charniak parser.
Additionally, we present a method for "closing" a sufficient number of
chart cells to ensure quadratic worst-case complexity of context-free
inference. Empirical results show that this O(n^2) bound can be
achieved without impacting parsing accuracy. In the last part of this
talk, we consider the impact of these constraints on exhaustive CYK
parsing, and demonstrate that the quadratic complexity methods
discussed earlier yield observed linear time performance. This
suggests an alternate method for applying these constraints that can
achieve linear or O(N log N) parsing pipeline complexity. Empirical
results demonstrate the utility of the new methods.

-------------------------------------------------------------------------
Message diffuse par la liste Langage Naturel <LN at cines.fr>
Informations, abonnement : http://www.atala.org/article.php3?id_article=48
English version       : 
Archives                 : http://listserv.linguistlist.org/archives/ln.html
                                http://liste.cines.fr/info/ln

La liste LN est parrainee par l'ATALA (Association pour le Traitement
Automatique des Langues)
Information et adhesion  : http://www.atala.org/
-------------------------------------------------------------------------