<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="svete-cotterell-2023-recurrent">
    <titleInfo>
        <title>Recurrent Neural Language Models as Probabilistic Finite-state Automata</title>
    </titleInfo>
    <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">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>Studying language models (LMs) in terms of well-understood formalisms allows us to precisely characterize their abilities and limitations. Previous work has investigated the expressive power of recurrent neural network (RNN) LMs in terms of their capacity to recognize unweighted formal languages. However, LMs do not describe unweighted formal languages—rather, they define probability distributions over strings. In this work, we study what classes of such probability distributions RNN LMs can represent, which allows us to make more direct statements about their capabilities. We show that simple RNNs are equivalent to a subclass of probabilistic finite-state automata, and can thus model a strict subset of probability distributions expressible by finite-state models. Furthermore, we study the space complexity of representing finite-state LMs with RNNs. We show that, to represent an arbitrary deterministic finite-state LM with N states over an alphabet Σ, an RNN requires Ømegałeft(N |Σ|\right) neurons. These results present a first step towards characterizing the classes of distributions RNN LMs can represent and thus help us understand their capabilities and limitations.</abstract>
    <identifier type="citekey">svete-cotterell-2023-recurrent</identifier>
    <identifier type="doi">10.18653/v1/2023.emnlp-main.502</identifier>
    <location>
        <url>https://aclanthology.org/2023.emnlp-main.502</url>
    </location>
    <part>
        <date>2023-12</date>
        <extent unit="page">
            <start>8069</start>
            <end>8086</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Conference Proceedings
%T Recurrent Neural Language Models as Probabilistic Finite-state Automata
%A Svete, Anej
%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 svete-cotterell-2023-recurrent
%X Studying language models (LMs) in terms of well-understood formalisms allows us to precisely characterize their abilities and limitations. Previous work has investigated the expressive power of recurrent neural network (RNN) LMs in terms of their capacity to recognize unweighted formal languages. However, LMs do not describe unweighted formal languages—rather, they define probability distributions over strings. In this work, we study what classes of such probability distributions RNN LMs can represent, which allows us to make more direct statements about their capabilities. We show that simple RNNs are equivalent to a subclass of probabilistic finite-state automata, and can thus model a strict subset of probability distributions expressible by finite-state models. Furthermore, we study the space complexity of representing finite-state LMs with RNNs. We show that, to represent an arbitrary deterministic finite-state LM with N states over an alphabet Σ, an RNN requires Ømegałeft(N |Σ|\right) neurons. These results present a first step towards characterizing the classes of distributions RNN LMs can represent and thus help us understand their capabilities and limitations.
%R 10.18653/v1/2023.emnlp-main.502
%U https://aclanthology.org/2023.emnlp-main.502
%U https://doi.org/10.18653/v1/2023.emnlp-main.502
%P 8069-8086

Markdown (Informal)

[Recurrent Neural Language Models as Probabilistic Finite-state Automata](https://aclanthology.org/2023.emnlp-main.502) (Svete & Cotterell, EMNLP 2023)

• Recurrent Neural Language Models as Probabilistic Finite-state Automata (Svete & Cotterell, EMNLP 2023)

ACL

• Anej Svete and Ryan Cotterell. 2023. Recurrent Neural Language Models as Probabilistic Finite-state Automata. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 8069–8086, Singapore. Association for Computational Linguistics.