7

I want to encode finite state machines (specifically DFAs) as output (or input) of a neural network for a supervised learning task.

Are there any ways in the literature for doing this?

I've already found some algorithms being able to extract a DFA from a recurrent neural network, but nothing about DFAs either as input or output of ANN.

timleathart
  • 3,900
  • 20
  • 35
Gabrer
  • 211
  • 2
  • 6
  • Is the purpose to learn an unknown DFA from observation of data, or to encode a known DFA as a RNN, or something else? – Neil Slater Jul 21 '16 at 13:19
  • Mainly, to learn unknown DFA from data; but, unlike the RNN approach which "interprets" RNN as a DFA, I would yield a DFA as output of the network. – Gabrer Jul 21 '16 at 14:49
  • How much of the system do you have observed in your data? Do you have full knowledge of the state and input string at each step? If not, what do you have? – Neil Slater Jul 21 '16 at 19:36
  • I've a structurally complete set of strings with respect to target language/automaton. Then, all the needed states are "observable". – Gabrer Jul 27 '16 at 09:41
  • My knowledge about DFAs is extremely limited but you can encode it as a graph, correct? If that is the case, you could look at Graph Convolutional Neural Networks, which take a graph as input. I think the expressive power might be too limited, but it might be worth a look. – Jan van der Vegt Nov 06 '17 at 15:15
  • I am looking for the same, did you ever find a reference? – Arturo Hernandez Jan 31 '22 at 22:21

3 Answers3

2

https://www.dlsi.ua.es/~mlf/nnafmc/pbook.pdf Neural Networks: Automata and Formal Models of Computation Mikel L. Forcada Universitat d’Alacant, Dept. Llenguatges i Sistemes Inform`atics, E-03071 Alacant (Spain). January 21, 2002

Roman Mishchenko
  • 21
  • 1
  • 1
    While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - [From Review](/review/late-answers/83459) – Ethan Nov 30 '22 at 23:46
  • Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Dec 04 '22 at 16:48
2

The better question might be - Why you do want to mix deep neural networks (DNN) and a finite state machine (FSM)?

There is research showing that a DNN can simulate any FSM. Since there are more frameworks for DNN and DNN can perform more tasks than FSM, it appears to be more useful just to forgo FSM altogether.

More specifically, "Neural network for synthesizing deterministic finite automata" shows how a relatively simple neural network (NN) can quickly and automatically learn the correct deterministic finite automaton (DFA).

There is a strong trend towards end-to-end DNN.

Brian Spiering
  • 20,142
  • 2
  • 25
  • 102
1

Take a look at the neural state machine by Hudson & Manning. It's non-deterministic but it is differentiable, which gives you the same kind of "black box learning power" as neural networks.

Janne
  • 21
  • 3