<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="deutsch-etal-2019-general">
    <titleInfo>
        <title>A General-Purpose Algorithm for Constrained Sequential Inference</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Daniel</namePart>
        <namePart type="family">Deutsch</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Shyam</namePart>
        <namePart type="family">Upadhyay</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Dan</namePart>
        <namePart type="family">Roth</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2019-11</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <relatedItem type="host">
        <titleInfo>
            <title>Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL)</title>
        </titleInfo>
        <name type="personal">
            <namePart type="given">Mohit</namePart>
            <namePart type="family">Bansal</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Aline</namePart>
            <namePart type="family">Villavicencio</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <originInfo>
            <publisher>Association for Computational Linguistics</publisher>
            <place>
                <placeTerm type="text">Hong Kong, China</placeTerm>
            </place>
        </originInfo>
        <genre authority="marcgt">conference publication</genre>
    </relatedItem>
    <abstract>Inference in structured prediction involves finding the best output structure for an input, subject to certain constraints. Many current approaches use sequential inference, which constructs the output in a left-to-right manner. However, there is no general framework to specify constraints in these approaches. We present a principled approach for incorporating constraints into sequential inference algorithms. Our approach expresses constraints using an automaton, which is traversed in lock-step during inference, guiding the search to valid outputs. We show that automata can express commonly used constraints and are easily incorporated into sequential inference. When it is more natural to represent constraints as a set of automata, our algorithm uses an active set method for demonstrably fast and efficient inference. We experimentally show the benefits of our algorithm on constituency parsing and semantic role labeling. For parsing, unlike unconstrained approaches, our algorithm always generates valid output, incurring only a small drop in performance. For semantic role labeling, imposing constraints using our algorithm corrects common errors, improving F1 by 1.5 points. These benefits increase in low-resource settings. Our active set method achieves a 5.2x relative speed-up over a naive approach.</abstract>
    <identifier type="citekey">deutsch-etal-2019-general</identifier>
    <identifier type="doi">10.18653/v1/K19-1045</identifier>
    <location>
        <url>https://aclanthology.org/K19-1045</url>
    </location>
    <part>
        <date>2019-11</date>
        <extent unit="page">
            <start>482</start>
            <end>492</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Conference Proceedings
%T A General-Purpose Algorithm for Constrained Sequential Inference
%A Deutsch, Daniel
%A Upadhyay, Shyam
%A Roth, Dan
%Y Bansal, Mohit
%Y Villavicencio, Aline
%S Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL)
%D 2019
%8 November
%I Association for Computational Linguistics
%C Hong Kong, China
%F deutsch-etal-2019-general
%X Inference in structured prediction involves finding the best output structure for an input, subject to certain constraints. Many current approaches use sequential inference, which constructs the output in a left-to-right manner. However, there is no general framework to specify constraints in these approaches. We present a principled approach for incorporating constraints into sequential inference algorithms. Our approach expresses constraints using an automaton, which is traversed in lock-step during inference, guiding the search to valid outputs. We show that automata can express commonly used constraints and are easily incorporated into sequential inference. When it is more natural to represent constraints as a set of automata, our algorithm uses an active set method for demonstrably fast and efficient inference. We experimentally show the benefits of our algorithm on constituency parsing and semantic role labeling. For parsing, unlike unconstrained approaches, our algorithm always generates valid output, incurring only a small drop in performance. For semantic role labeling, imposing constraints using our algorithm corrects common errors, improving F1 by 1.5 points. These benefits increase in low-resource settings. Our active set method achieves a 5.2x relative speed-up over a naive approach.
%R 10.18653/v1/K19-1045
%U https://aclanthology.org/K19-1045
%U https://doi.org/10.18653/v1/K19-1045
%P 482-492

Markdown (Informal)

[A General-Purpose Algorithm for Constrained Sequential Inference](https://aclanthology.org/K19-1045) (Deutsch et al., CoNLL 2019)

• A General-Purpose Algorithm for Constrained Sequential Inference (Deutsch et al., CoNLL 2019)

ACL

• Daniel Deutsch, Shyam Upadhyay, and Dan Roth. 2019. A General-Purpose Algorithm for Constrained Sequential Inference. In Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL), pages 482–492, Hong Kong, China. Association for Computational Linguistics.