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
Proceedings of the Fifteenth International Conference on Grammatical Inference, PMLR 153:113-129, 2021.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v153-barbot21a, title = {Extracting Context-Free Grammars from Recurrent Neural Networks using Tree-Automata Learning and A* Search}, author = {Barbot, Beno\^it and Bollig, Benedikt and Finkel, Alain and Haddad, Serge and Khmelnitsky, Igor and Leucker, Martin and Neider, Daniel and Roy, Rajarshi and Ye, Lina}, booktitle = {Proceedings of the Fifteenth International Conference on Grammatical Inference}, pages = {113--129}, year = {2021}, editor = {Chandlee, Jane and Eyraud, Rémi and Heinz, Jeff and Jardine, Adam and van Zaanen, Menno}, volume = {153}, series = {Proceedings of Machine Learning Research}, month = {23--27 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v153/barbot21a/barbot21a.pdf}, url = {https://proceedings.mlr.press/v153/barbot21a.html}, 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.} }
Endnote
%0 Conference Paper %T Extracting Context-Free Grammars from Recurrent Neural Networks using Tree-Automata Learning and A* Search %A Benoît Barbot %A Benedikt Bollig %A Alain Finkel %A Serge Haddad %A Igor Khmelnitsky %A Martin Leucker %A Daniel Neider %A Rajarshi Roy %A Lina Ye %B Proceedings of the Fifteenth International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2021 %E Jane Chandlee %E Rémi Eyraud %E Jeff Heinz %E Adam Jardine %E Menno van Zaanen %F pmlr-v153-barbot21a %I PMLR %P 113--129 %U https://proceedings.mlr.press/v153/barbot21a.html %V 153 %X 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.
APA
Barbot, B., Bollig, B., Finkel, A., Haddad, S., Khmelnitsky, I., Leucker, M., Neider, D., Roy, R. & Ye, L.. (2021). Extracting Context-Free Grammars from Recurrent Neural Networks using Tree-Automata Learning and A* Search. Proceedings of the Fifteenth International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 153:113-129 Available from https://proceedings.mlr.press/v153/barbot21a.html.

Related Material