|
Finite-state chart constraints for reduced complexity context-free
parsing pipelines| old_uid | 6542 |
|---|
| title | Finite-state chart constraints for reduced complexity context-free
parsing pipelines |
|---|
| start_date | 2009/03/19 |
|---|
| schedule | 10h-12h |
|---|
| online | no |
|---|
| location_info | salle 134 |
|---|
| summary | 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. |
|---|
| responsibles | <not specified> |
|---|
| |
|