Extracting Context-Free Grammars from Recurrent Neural Networks using Tree-Automata Learning and A* Search.

Benoît Barbot; Benedikt Bollig; Alain Finkel; Serge Haddad; Igor Khmelnitsky; Martin Leucker; Daniel Neider; Rajarshi Roy; Lina Ye

Extracting Context-Free Grammars from Recurrent Neural Networks using Tree-Automata Learning and A* Search.

Benoît Barbot, Benedikt Bollig, Alain Finkel, Serge Haddad, Igor Khmelnitsky, Martin Leucker, Daniel Neider, Rajarshi Roy, Lina Ye

9 Citations (Scopus)

Abstract

This paper presents (i) an active learning algorithm for visibly pushdown grammars and (ii) shows its applicability for learning surrogate models of recurrent neural networks (RNNs) trained on context-free languages. Such surrogate models may be used for verification or explainability. Our learning algorithm makes use of the proximity of visibly pushdown languages and regular tree languages and builds on an existing learning algorithm for regular tree languages. Equivalence tests between a given RNN and a hypothesis grammar rely on a mixture of A* search and random sampling. An evaluation of our approach on a set of RNNs from the literature shows good preliminary results.

Original language	English
Pages	113-129
Publication status	Published - 2021

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 4 Quality Education
SDG 9 Industry, Innovation, and Infrastructure
SDG 11 Sustainable Cities and Communities
SDG 12 Responsible Consumption and Production
SDG 14 Life Below Water
SDG 15 Life on Land

Research Areas and Centers

Centers: Center for Artificial Intelligence Luebeck (ZKIL)

Access to Document

https://dblp.org/rec/conf/icgi/BarbotBFHKLN0Y21

Cite this

@conference{e15603ea3b6847e8be4814987b5b48d2,

title = "Extracting Context-Free Grammars from Recurrent Neural Networks using Tree-Automata Learning and A* Search.",

abstract = "This paper presents (i) an active learning algorithm for visibly pushdown grammars and (ii) shows its applicability for learning surrogate models of recurrent neural networks (RNNs) trained on context-free languages. Such surrogate models may be used for verification or explainability. Our learning algorithm makes use of the proximity of visibly pushdown languages and regular tree languages and builds on an existing learning algorithm for regular tree languages. Equivalence tests between a given RNN and a hypothesis grammar rely on a mixture of A* search and random sampling. An evaluation of our approach on a set of RNNs from the literature shows good preliminary results.",

author = "Beno{\^i}t Barbot and Benedikt Bollig and Alain Finkel and Serge Haddad and Igor Khmelnitsky and Martin Leucker and Daniel Neider and Rajarshi Roy and Lina Ye",

note = "DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.",

year = "2021",

language = "English",

pages = "113--129",

}

TY - CONF

T1 - Extracting Context-Free Grammars from Recurrent Neural Networks using Tree-Automata Learning and A* Search.

AU - Barbot, Benoît

AU - Bollig, Benedikt

AU - Finkel, Alain

AU - Haddad, Serge

AU - Khmelnitsky, Igor

AU - Leucker, Martin

AU - Neider, Daniel

AU - Roy, Rajarshi

AU - Ye, Lina

N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

PY - 2021

Y1 - 2021

N2 - This paper presents (i) an active learning algorithm for visibly pushdown grammars and (ii) shows its applicability for learning surrogate models of recurrent neural networks (RNNs) trained on context-free languages. Such surrogate models may be used for verification or explainability. Our learning algorithm makes use of the proximity of visibly pushdown languages and regular tree languages and builds on an existing learning algorithm for regular tree languages. Equivalence tests between a given RNN and a hypothesis grammar rely on a mixture of A* search and random sampling. An evaluation of our approach on a set of RNNs from the literature shows good preliminary results.

AB - This paper presents (i) an active learning algorithm for visibly pushdown grammars and (ii) shows its applicability for learning surrogate models of recurrent neural networks (RNNs) trained on context-free languages. Such surrogate models may be used for verification or explainability. Our learning algorithm makes use of the proximity of visibly pushdown languages and regular tree languages and builds on an existing learning algorithm for regular tree languages. Equivalence tests between a given RNN and a hypothesis grammar rely on a mixture of A* search and random sampling. An evaluation of our approach on a set of RNNs from the literature shows good preliminary results.

M3 - Conference Papers

SP - 113

EP - 129

ER -

Extracting Context-Free Grammars from Recurrent Neural Networks using Tree-Automata Learning and A* Search.

Abstract

UN SDGs

Research Areas and Centers

Access to Document

Fingerprint

Cite this