From ac9007d3cf2a3eabb1c34a6e7f6155372b2bde09 Mon Sep 17 00:00:00 2001 From: Yuchen Pei Date: Fri, 11 May 2018 12:31:36 +0200 Subject: added an mpost. --- microposts/rnn-fsm.md | 14 ++++++++++++++ 1 file changed, 14 insertions(+) create mode 100644 microposts/rnn-fsm.md (limited to 'microposts') diff --git a/microposts/rnn-fsm.md b/microposts/rnn-fsm.md new file mode 100644 index 0000000..38ff333 --- /dev/null +++ b/microposts/rnn-fsm.md @@ -0,0 +1,14 @@ +--- +date: 2018-05-11 +--- +### Some notes on RNN, FSM / FA, TM and UTM + +Related to a previous micropost. + +[The slides from Toronto](http://www.cs.toronto.edu/~rgrosse/csc321/lec9.pdf) is a nice introduction to RNN (recurrent neural network) from a computational point of view. It states the relation between RNN and FSM (finite state machine, a.k.a. finite automata abbr. FA) with a toy example computing the parity of a binary string. + +[Goodfellow et. al.'s book](http://www.deeplearningbook.org/contents/rnn.html) (see page 372 and 374) goes one step further, stating that RNN with a hidden-to-hidden layer can simulate Turing machines, and not only that, but also the *universal* Turing machine abbr. UTM (the book referenced [Siegelmann-Sontag](https://www.sciencedirect.com/science/article/pii/S0022000085710136)), a property not shared by the weaker network where the hidden-to-hidden layer is replaced by an output-to-hidden layer (page 376). + +By the way, the RNN with a hidden-to-hidden layer has the same architecture as the so-called linear dynamical system mentioned in [Hinton's video](https://www.coursera.org/learn/neural-networks/lecture/Fpa7y/modeling-sequences-a-brief-overview). + +From what I have learned, the universality of RNN and feedforward networks are therefore due to different arguments, the former coming from Turing machines and the latter from an analytical view of approximation by step functions. -- cgit v1.2.3