<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="qian-liu-2013-branch">
    <titleInfo>
        <title>Branch and Bound Algorithm for Dependency Parsing with Non-local Features</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Xian</namePart>
        <namePart type="family">Qian</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Yang</namePart>
        <namePart type="family">Liu</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2013</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <genre>journal article</genre>
    <relatedItem type="host">
        <titleInfo>
            <title>Transactions of the Association for Computational Linguistics</title>
        </titleInfo>
        <originInfo>
            <issuance>continuing</issuance>
            <publisher>MIT Press</publisher>
            <place>
                <placeTerm type="text">Cambridge, MA</placeTerm>
            </place>
        </originInfo>
        <genre authority="marcgt">periodical</genre>
        <genre>academic journal</genre>
    </relatedItem>
    <abstract>Graph based dependency parsing is inefficient when handling non-local features due to high computational complexity of inference. In this paper, we proposed an exact and efficient decoding algorithm based on the Branch and Bound (B&amp;B) framework where non-local features are bounded by a linear combination of local features. Dynamic programming is used to search the upper bound. Experiments are conducted on English PTB and Chinese CTB datasets. We achieved competitive Unlabeled Attachment Score (UAS) when no additional resources are available: 93.17% for English and 87.25% for Chinese. Parsing speed is 177 words per second for English and 97 words per second for Chinese. Our algorithm is general and can be adapted to non-projective dependency parsing or other graphical models.</abstract>
    <identifier type="citekey">qian-liu-2013-branch</identifier>
    <identifier type="doi">10.1162/tacl_a_00208</identifier>
    <location>
        <url>https://aclanthology.org/Q13-1004</url>
    </location>
    <part>
        <date>2013</date>
        <detail type="volume"><number>1</number></detail>
        <extent unit="page">
            <start>37</start>
            <end>48</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Journal Article
%T Branch and Bound Algorithm for Dependency Parsing with Non-local Features
%A Qian, Xian
%A Liu, Yang
%J Transactions of the Association for Computational Linguistics
%D 2013
%V 1
%I MIT Press
%C Cambridge, MA
%F qian-liu-2013-branch
%X Graph based dependency parsing is inefficient when handling non-local features due to high computational complexity of inference. In this paper, we proposed an exact and efficient decoding algorithm based on the Branch and Bound (B&B) framework where non-local features are bounded by a linear combination of local features. Dynamic programming is used to search the upper bound. Experiments are conducted on English PTB and Chinese CTB datasets. We achieved competitive Unlabeled Attachment Score (UAS) when no additional resources are available: 93.17% for English and 87.25% for Chinese. Parsing speed is 177 words per second for English and 97 words per second for Chinese. Our algorithm is general and can be adapted to non-projective dependency parsing or other graphical models.
%9 journal article
%R 10.1162/tacl_a_00208
%U https://aclanthology.org/Q13-1004
%U https://doi.org/10.1162/tacl_a_00208
%P 37-48

Markdown (Informal)

[Branch and Bound Algorithm for Dependency Parsing with Non-local Features](https://aclanthology.org/Q13-1004) (Qian & Liu, TACL 2013)

• Branch and Bound Algorithm for Dependency Parsing with Non-local Features (Qian & Liu, TACL 2013)

ACL

• Xian Qian and Yang Liu. 2013. Branch and Bound Algorithm for Dependency Parsing with Non-local Features. Transactions of the Association for Computational Linguistics, 1:37–48.