diff options
Diffstat (limited to 'microposts/rnn-fsm.org')
| -rw-r--r-- | microposts/rnn-fsm.org | 30 |
1 files changed, 30 insertions, 0 deletions
diff --git a/microposts/rnn-fsm.org b/microposts/rnn-fsm.org new file mode 100644 index 0000000..a1bdf2d --- /dev/null +++ b/microposts/rnn-fsm.org @@ -0,0 +1,30 @@ +#+title: rnn-fsm + +#+date: <2018-05-11> + +Related to [[file:neural-turing-machine][a previous micropost]]. + +[[http://www.cs.toronto.edu/~rgrosse/csc321/lec9.pdf][These slides from +Toronto]] are a nice introduction to RNN (recurrent neural network) from +a computational point of view. It states that RNN can simulate any FSM +(finite state machine, a.k.a. finite automata abbr. FA) with a toy +example computing the parity of a binary string. + +[[http://www.deeplearningbook.org/contents/rnn.html][Goodfellow et. +al.'s book]] (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 +[[https://www.sciencedirect.com/science/article/pii/S0022000085710136][Siegelmann-Sontag]]), +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 +[[https://www.coursera.org/learn/neural-networks/lecture/Fpa7y/modeling-sequences-a-brief-overview][Hinton's +video]]. + +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. |