<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="weiss-etal-2018-practical">
    <titleInfo>
        <title>On the Practical Computational Power of Finite Precision RNNs for Language Recognition</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Gail</namePart>
        <namePart type="family">Weiss</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Yoav</namePart>
        <namePart type="family">Goldberg</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Eran</namePart>
        <namePart type="family">Yahav</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>While Recurrent Neural Networks (RNNs) are famously known to be Turing complete, this relies on infinite precision in the states and unbounded computation time. We consider the case of RNNs with finite precision whose computation time is linear in the input length. Under these limitations, we show that different RNN variants have different computational power. In particular, we show that the LSTM and the Elman-RNN with ReLU activation are strictly stronger than the RNN with a squashing activation and the GRU. This is achieved because LSTMs and ReLU-RNNs can easily implement counting behavior. We show empirically that the LSTM does indeed learn to effectively use the counting mechanism.</abstract>
    <identifier type="citekey">weiss-etal-2018-practical</identifier>
    <identifier type="doi">10.18653/v1/P18-2117</identifier>
    <location>
        <url>https://aclanthology.org/P18-2117</url>
    </location>
    <part>
        <date>2018-07</date>
        <extent unit="page">
            <start>740</start>
            <end>745</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Conference Proceedings
%T On the Practical Computational Power of Finite Precision RNNs for Language Recognition
%A Weiss, Gail
%A Goldberg, Yoav
%A Yahav, Eran
%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 weiss-etal-2018-practical
%X While Recurrent Neural Networks (RNNs) are famously known to be Turing complete, this relies on infinite precision in the states and unbounded computation time. We consider the case of RNNs with finite precision whose computation time is linear in the input length. Under these limitations, we show that different RNN variants have different computational power. In particular, we show that the LSTM and the Elman-RNN with ReLU activation are strictly stronger than the RNN with a squashing activation and the GRU. This is achieved because LSTMs and ReLU-RNNs can easily implement counting behavior. We show empirically that the LSTM does indeed learn to effectively use the counting mechanism.
%R 10.18653/v1/P18-2117
%U https://aclanthology.org/P18-2117
%U https://doi.org/10.18653/v1/P18-2117
%P 740-745

Markdown (Informal)

[On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://aclanthology.org/P18-2117) (Weiss et al., ACL 2018)

• On the Practical Computational Power of Finite Precision RNNs for Language Recognition (Weiss et al., ACL 2018)

ACL

• Gail Weiss, Yoav Goldberg, and Eran Yahav. 2018. On the Practical Computational Power of Finite Precision RNNs for Language Recognition. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 740–745, Melbourne, Australia. Association for Computational Linguistics.