Repository files navigation

Welcome to our public repository, implementing the extraction algorithm from our ICML 2018 paper,Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples.

To use the main notebook here without installing anything, you can go straight to google colaboratory:https://drive.google.com/file/d/1tkJK1rJVEg9e-QcWOxErDb3cQq9UR-yR/view?usp=sharing

Open thedfa_from_rnn notebook for a full demonstration and run through of how to use it yourself (we have provided all of the Tomita grammars, but you can also define, train, and extract your own languages!). For the impatient, thedfa_from_rnn_no_documentation notebook is exactly likedfa_from_rnn, only without all the explanation blocks. And if you want to train and keep track of several RNNs, you can usedfa_from_rnn_notebook_for_several_rnns, which is likedfa_from_rnn_no_documentation only it keeps all of your RNNs in neat little wrappers with their target languages and then keeps all of those in a list.

Everything here is implemented in Python 3. To use these notebooks, you will also need to install:

1. DyNet (for working with our LSTM and GRU networks, which are implemented in DyNet)
2. Graphviz (for drawing the extracted DFAs).
3. NumPy and SciPy (for Scikit-Learn)
4. Scikit-Learn (for the SVM classifier)
5. Matplotlib (for plots of our networks' loss during training)
6. Jupyter (for the python notebooks themselves)

If you are on a mac using Homebrew, then NumPy, SciPy, Scikit-Learn, Matplotlib, Graphviz and Jupyter should all hopefully work withbrew install numpy,brew install scipy, etc.

If you don't have Homebrew, or whereverbrew install doesn't work, trypip install instead.

For Graphviz you may first need to download and install the package yourselfGraphviz, after which you can runpip install graphviz. If you're lucky,brew install graphviz might take care of all of this for you by itself. On colab, we got Graphviz usingpip install graphviz and thenapt-get install graphviz.

DyNet is installed bypip install dynet from the command line (for the basic CPU version. For the GPU version, check theirsite).

You can also apply the code directly to your own networks without most of these packages. The main extraction function is inExtraction.py and calledextract. You can run it on any network that implements the API described in ourdfa_from_rnn notebook, which is viewable in-browser in git even if you don't have Jupyter, and reiterated here for completeness.

1. classify_word(word) returns a True or False classification for a word over the input alphabet
2. get_first_RState() returns a tuple (v,c) where v is a continuous vector representation of the network's initial state (an RState), and c is a boolean signifying whether it is an accepting state
3. get_next_RState(state,char) given an RState, returns the next RState the network goes to on input characterchar, in the same format asget_first_RState (i.e., a tuple (v,c) of vector + boolean)

To run only the extraction code you will only need the NumPy, SciPy, Scikit-Learn, and Graphviz packages. If you want, you can also skip the Graphviz package, at the cost of the ability to visualise your DFAs. Remove the graphviz import fromDFA.py and set the body of thedraw_nicely function of theDFA class topass. You only need theDFA,Extraction,Lstar,Helper_Functions,Observation_Table,Quantisations,Teacher, andWhiteboxRNNCounterexampleGenerator modules for extraction.

You can cite this work using:

@InProceedings{weiss-goldberg-yahav,
title = {Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples},
author = {Gail Weiss and Yoav Goldberg and Eran Yahav},
booktitle = {Proceedings of the 35th International Conference on Machine Learning},
year = {2018},
editor = {Jennifer Dy and Andreas Krause},
volume = {80},
series = {Proceedings of Machine Learning Research},
address = {Stockholmsm\"{a}ssan, Stockholm, Sweden},
month = {10--15 Jul},
publisher = {PMLR}
}