<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="nowak-etal-2023-representational">
    <titleInfo>
        <title>On the Representational Capacity of Recurrent Neural Language Models</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Franz</namePart>
        <namePart type="family">Nowak</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Anej</namePart>
        <namePart type="family">Svete</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Li</namePart>
        <namePart type="family">Du</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Ryan</namePart>
        <namePart type="family">Cotterell</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2023-12</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <relatedItem type="host">
        <titleInfo>
            <title>Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing</title>
        </titleInfo>
        <name type="personal">
            <namePart type="given">Houda</namePart>
            <namePart type="family">Bouamor</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Juan</namePart>
            <namePart type="family">Pino</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Kalika</namePart>
            <namePart type="family">Bali</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <originInfo>
            <publisher>Association for Computational Linguistics</publisher>
            <place>
                <placeTerm type="text">Singapore</placeTerm>
            </place>
        </originInfo>
        <genre authority="marcgt">conference publication</genre>
    </relatedItem>
    <abstract>This work investigates the computational expressivity of language models (LMs) based on recurrent neural networks (RNNs). Siegelmann and Sontag (1992) famously showed that RNNs with rational weights and hidden states and unbounded computation time are Turing complete. However, LMs define weightings over strings in addition to just (unweighted) language membership and the analysis of the computational power of RNN LMs (RLMs) should reflect this. We extend the Turing completeness result to the probabilistic case, showing how a rationally weighted RLM with unbounded computation time can simulate any deterministic probabilistic Turing machine (PTM) with rationally weighted transitions. Since, in practice, RLMs work in real-time, processing a symbol at every time step, we treat the above result as an upper bound on the expressivity of RLMs. We also provide a lower bound by showing that under the restriction to real-time computation, such models can simulate deterministic real-time rational PTMs.</abstract>
    <identifier type="citekey">nowak-etal-2023-representational</identifier>
    <identifier type="doi">10.18653/v1/2023.emnlp-main.434</identifier>
    <location>
        <url>https://aclanthology.org/2023.emnlp-main.434</url>
    </location>
    <part>
        <date>2023-12</date>
        <extent unit="page">
            <start>7011</start>
            <end>7034</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Conference Proceedings
%T On the Representational Capacity of Recurrent Neural Language Models
%A Nowak, Franz
%A Svete, Anej
%A Du, Li
%A Cotterell, Ryan
%Y Bouamor, Houda
%Y Pino, Juan
%Y Bali, Kalika
%S Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing
%D 2023
%8 December
%I Association for Computational Linguistics
%C Singapore
%F nowak-etal-2023-representational
%X This work investigates the computational expressivity of language models (LMs) based on recurrent neural networks (RNNs). Siegelmann and Sontag (1992) famously showed that RNNs with rational weights and hidden states and unbounded computation time are Turing complete. However, LMs define weightings over strings in addition to just (unweighted) language membership and the analysis of the computational power of RNN LMs (RLMs) should reflect this. We extend the Turing completeness result to the probabilistic case, showing how a rationally weighted RLM with unbounded computation time can simulate any deterministic probabilistic Turing machine (PTM) with rationally weighted transitions. Since, in practice, RLMs work in real-time, processing a symbol at every time step, we treat the above result as an upper bound on the expressivity of RLMs. We also provide a lower bound by showing that under the restriction to real-time computation, such models can simulate deterministic real-time rational PTMs.
%R 10.18653/v1/2023.emnlp-main.434
%U https://aclanthology.org/2023.emnlp-main.434
%U https://doi.org/10.18653/v1/2023.emnlp-main.434
%P 7011-7034

Markdown (Informal)

[On the Representational Capacity of Recurrent Neural Language Models](https://aclanthology.org/2023.emnlp-main.434) (Nowak et al., EMNLP 2023)

• On the Representational Capacity of Recurrent Neural Language Models (Nowak et al., EMNLP 2023)

ACL

• Franz Nowak, Anej Svete, Li Du, and Ryan Cotterell. 2023. On the Representational Capacity of Recurrent Neural Language Models. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 7011–7034, Singapore. Association for Computational Linguistics.