Weighted Automata Extraction from Recurrent Neural Networks via Regression on State Spaces

Takamasa Okudono, Masaki Waga, Taro Sekiyama, Ichiro Hasuo

AAAI 2020 pp. 5306-5314

doi:10.1609/AAAI.V34I04.5977 /aaai/2020/okudono2020aaai-weighted/

Abstract

We present a method to extract a weighted finite automaton (WFA) from a recurrent neural network (RNN). Our method is based on the WFA learning algorithm by Balle and Mohri, which is in turn an extension of Angluin's classic L* algorithm. Our technical novelty is in the use of regression methods for the so-called equivalence queries, thus exploiting the internal state space of an RNN to prioritize counterexample candidates. This way we achieve a quantitative/weighted extension of the recent work by Weiss, Goldberg and Yahav that extracts DFAs. We experimentally evaluate the accuracy, expressivity and efficiency of the extracted WFAs.

PDF AAAI Semantic Scholar

Cite

Text

Okudono et al. "Weighted Automata Extraction from Recurrent Neural Networks via Regression on State Spaces." AAAI Conference on Artificial Intelligence, 2020. doi:10.1609/AAAI.V34I04.5977

Markdown

[Okudono et al. "Weighted Automata Extraction from Recurrent Neural Networks via Regression on State Spaces." AAAI Conference on Artificial Intelligence, 2020.](https://mlanthology.org/aaai/2020/okudono2020aaai-weighted/) doi:10.1609/AAAI.V34I04.5977

BibTeX

@inproceedings{okudono2020aaai-weighted,
  title     = {{Weighted Automata Extraction from Recurrent Neural Networks via Regression on State Spaces}},
  author    = {Okudono, Takamasa and Waga, Masaki and Sekiyama, Taro and Hasuo, Ichiro},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2020},
  pages     = {5306-5314},
  doi       = {10.1609/AAAI.V34I04.5977},
  url       = {https://mlanthology.org/aaai/2020/okudono2020aaai-weighted/}
}