Seminaire: Expose Brian Roark, Jeudi 19 mars

Thierry Hamon thierry.hamon at LIPN.UNIV-PARIS13.FR
Tue Mar 10 17:08:55 UTC 2009

Date: Tue, 10 Mar 2009 18:03:26 +0100
From: bcrabbe at
Message-ID: <1236704606.49b69d5e8cae0 at>


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.

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

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>
Informations, abonnement :
English version       : 
Archives                 :

La liste LN est parrainee par l'ATALA (Association pour le Traitement
Automatique des Langues)
Information et adhesion  :

More information about the Ln mailing list