Representing formal languages: A comparison between finite automata and recurrent neural networks

Joshua J. Michalenko; Ameesh Shah; Abhinav Verma; Richard G. Baraniuk; Swarat Chaudhuri; Ankit B. Patel

Representing formal languages: A comparison between finite automata and recurrent neural networks

Joshua J. Michalenko, Ameesh Shah, Abhinav Verma, Richard G. Baraniuk, Swarat Chaudhuri, Ankit B. Patel

Research output: Contribution to conference › Paper › peer-review

Abstract

We investigate the internal representations that a recurrent neural network (RNN) uses while learning to recognize a regular formal language. Specifically, we train a RNN on positive and negative examples from a regular language, and ask if there is a simple decoding function that maps states of this RNN to states of the minimal deterministic finite automaton (MDFA) for the language. Our experiments show that such a decoding function indeed exists, and that it maps states of the RNN not to MDFA states, but to states of an abstraction obtained by clustering small sets of MDFA states into “superstates”. A qualitative analysis reveals that the abstraction often has a simple interpretation. Overall, the results suggest a strong structural relationship between internal representations used by RNNs and finite automata, and explain the well-known ability of RNNs to recognize formal grammatical structure.

Original language	English (US)
State	Published - 2019
Event	7th International Conference on Learning Representations, ICLR 2019 - New Orleans, United States Duration: May 6 2019 → May 9 2019

Conference

Conference	7th International Conference on Learning Representations, ICLR 2019
Country/Territory	United States
City	New Orleans
Period	5/6/19 → 5/9/19

All Science Journal Classification (ASJC) codes

Education
Computer Science Applications
Linguistics and Language
Language and Linguistics

Cite this

@conference{8b87fc02ccd24f6490edd51b72ce0078,

title = "Representing formal languages: A comparison between finite automata and recurrent neural networks",

abstract = "We investigate the internal representations that a recurrent neural network (RNN) uses while learning to recognize a regular formal language. Specifically, we train a RNN on positive and negative examples from a regular language, and ask if there is a simple decoding function that maps states of this RNN to states of the minimal deterministic finite automaton (MDFA) for the language. Our experiments show that such a decoding function indeed exists, and that it maps states of the RNN not to MDFA states, but to states of an abstraction obtained by clustering small sets of MDFA states into “superstates”. A qualitative analysis reveals that the abstraction often has a simple interpretation. Overall, the results suggest a strong structural relationship between internal representations used by RNNs and finite automata, and explain the well-known ability of RNNs to recognize formal grammatical structure.",

author = "Michalenko, {Joshua J.} and Ameesh Shah and Abhinav Verma and Baraniuk, {Richard G.} and Swarat Chaudhuri and Patel, {Ankit B.}",

note = "Publisher Copyright: {\textcopyright} 7th International Conference on Learning Representations, ICLR 2019. All Rights Reserved.; 7th International Conference on Learning Representations, ICLR 2019 ; Conference date: 06-05-2019 Through 09-05-2019",

year = "2019",

language = "English (US)",

}

TY - CONF

T1 - Representing formal languages

T2 - 7th International Conference on Learning Representations, ICLR 2019

AU - Michalenko, Joshua J.

AU - Shah, Ameesh

AU - Verma, Abhinav

AU - Baraniuk, Richard G.

AU - Chaudhuri, Swarat

AU - Patel, Ankit B.

PY - 2019

Y1 - 2019

N2 - We investigate the internal representations that a recurrent neural network (RNN) uses while learning to recognize a regular formal language. Specifically, we train a RNN on positive and negative examples from a regular language, and ask if there is a simple decoding function that maps states of this RNN to states of the minimal deterministic finite automaton (MDFA) for the language. Our experiments show that such a decoding function indeed exists, and that it maps states of the RNN not to MDFA states, but to states of an abstraction obtained by clustering small sets of MDFA states into “superstates”. A qualitative analysis reveals that the abstraction often has a simple interpretation. Overall, the results suggest a strong structural relationship between internal representations used by RNNs and finite automata, and explain the well-known ability of RNNs to recognize formal grammatical structure.

AB - We investigate the internal representations that a recurrent neural network (RNN) uses while learning to recognize a regular formal language. Specifically, we train a RNN on positive and negative examples from a regular language, and ask if there is a simple decoding function that maps states of this RNN to states of the minimal deterministic finite automaton (MDFA) for the language. Our experiments show that such a decoding function indeed exists, and that it maps states of the RNN not to MDFA states, but to states of an abstraction obtained by clustering small sets of MDFA states into “superstates”. A qualitative analysis reveals that the abstraction often has a simple interpretation. Overall, the results suggest a strong structural relationship between internal representations used by RNNs and finite automata, and explain the well-known ability of RNNs to recognize formal grammatical structure.

UR - http://www.scopus.com/inward/record.url?scp=85083950333&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85083950333&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:85083950333

Y2 - 6 May 2019 through 9 May 2019

ER -

Representing formal languages: A comparison between finite automata and recurrent neural networks

Abstract

Conference

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this