Output details
11 - Computer Science and Informatics
University of Edinburgh
Return to search
Output 0 of 0 in the submission
Output title
Approximate PCFG Parsing Using Tensor Decomposition
Type
E - Conference contribution
DOI
-
Name of conference/published proceedings
Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies
Volume number
-
Issue number
-
First page of article
487
ISSN of proceedings
-
Year of publication
2013
Number of additional authors
2
Additional information
<22> Originality: This paper shows how to improve the asymptotic complexity of a well-known parsing algorithm (Cocke–Younger–Kasami, CYK) with respect to the size of the grammar.
Significance: CYK parsing is used in many applications in NLP and outside of NLP as well. When the grammar is too large, it becomes a problem to use CYK, and many heuristics are necessary. This paper gives a provably correct algorithm, with guarantees on quality of approximation, for this kind of parsing. Two papers were published about this (by Cohen), in top-tier ML/NLP conferences.
Rigour: The paper includes proofs for quality of approximation.
Interdisciplinary
-
Cross-referral requested
-
Research group
D - Institute for Language, Cognition & Computation
Citation count
0
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
