<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="hong-huang-2018-linear">
    <titleInfo>
        <title>Linear-time Constituency Parsing with RNNs and Dynamic Programming</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Juneki</namePart>
        <namePart type="family">Hong</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Liang</namePart>
        <namePart type="family">Huang</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2018-07</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <relatedItem type="host">
        <titleInfo>
            <title>Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)</title>
        </titleInfo>
        <name type="personal">
            <namePart type="given">Iryna</namePart>
            <namePart type="family">Gurevych</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Yusuke</namePart>
            <namePart type="family">Miyao</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <originInfo>
            <publisher>Association for Computational Linguistics</publisher>
            <place>
                <placeTerm type="text">Melbourne, Australia</placeTerm>
            </place>
        </originInfo>
        <genre authority="marcgt">conference publication</genre>
    </relatedItem>
    <abstract>Recently, span-based constituency parsing has achieved competitive accuracies with extremely simple models by using bidirectional RNNs to model “spans”. However, the minimal span parser of Stern et al. (2017a) which holds the current state of the art accuracy is a chart parser running in cubic time, O(n³), which is too slow for longer sentences and for applications beyond sentence boundaries such as end-to-end discourse parsing and joint sentence boundary detection and parsing. We propose a linear-time constituency parser with RNNs and dynamic programming using graph-structured stack and beam search, which runs in time O(n b²) where b is the beam size. We further speed this up to O(n b log b) by integrating cube pruning. Compared with chart parsing baselines, this linear-time parser is substantially faster for long sentences on the Penn Treebank and orders of magnitude faster for discourse parsing, and achieves the highest F1 accuracy on the Penn Treebank among single model end-to-end systems.</abstract>
    <identifier type="citekey">hong-huang-2018-linear</identifier>
    <identifier type="doi">10.18653/v1/P18-2076</identifier>
    <location>
        <url>https://aclanthology.org/P18-2076/</url>
    </location>
    <part>
        <date>2018-07</date>
        <extent unit="page">
            <start>477</start>
            <end>483</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Conference Proceedings
%T Linear-time Constituency Parsing with RNNs and Dynamic Programming
%A Hong, Juneki
%A Huang, Liang
%Y Gurevych, Iryna
%Y Miyao, Yusuke
%S Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)
%D 2018
%8 July
%I Association for Computational Linguistics
%C Melbourne, Australia
%F hong-huang-2018-linear
%X Recently, span-based constituency parsing has achieved competitive accuracies with extremely simple models by using bidirectional RNNs to model “spans”. However, the minimal span parser of Stern et al. (2017a) which holds the current state of the art accuracy is a chart parser running in cubic time, O(n³), which is too slow for longer sentences and for applications beyond sentence boundaries such as end-to-end discourse parsing and joint sentence boundary detection and parsing. We propose a linear-time constituency parser with RNNs and dynamic programming using graph-structured stack and beam search, which runs in time O(n b²) where b is the beam size. We further speed this up to O(n b log b) by integrating cube pruning. Compared with chart parsing baselines, this linear-time parser is substantially faster for long sentences on the Penn Treebank and orders of magnitude faster for discourse parsing, and achieves the highest F1 accuracy on the Penn Treebank among single model end-to-end systems.
%R 10.18653/v1/P18-2076
%U https://aclanthology.org/P18-2076/
%U https://doi.org/10.18653/v1/P18-2076
%P 477-483

Markdown (Informal)

[Linear-time Constituency Parsing with RNNs and Dynamic Programming](https://aclanthology.org/P18-2076/) (Hong & Huang, ACL 2018)

• Linear-time Constituency Parsing with RNNs and Dynamic Programming (Hong & Huang, ACL 2018)

ACL

• Juneki Hong and Liang Huang. 2018. Linear-time Constituency Parsing with RNNs and Dynamic Programming. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 477–483, Melbourne, Australia. Association for Computational Linguistics.