3 ms·
Considering RNNs have completely taken over text generation with language models, are there any papers that comprehensively compare the power of RNN and Markov
by nafizh 7y ago
Considering RNNs have completely taken over text generation with language models, are there any papers that comprehensively compare the power of RNN and Markov models?
- xapata 7y agoIn a sense, they're equivalent. RNN's create models of probabilistic state transitions. In other words, they create Markov chain models. You might argue that a Markov chain doesn't have memory, but it's easy to incorporate "memory" by expanding the definition of a "state" to include recent history or any function of the past.
- raverbashing 7y agoNo, they're not. And if it was "that easy" to incorporate memory RNNs would not have replaced Markov Chains As an example try to build a character level Markov chain for text generation and see how that goes.
- aesthesia 7y agoThe point is that an RNN or other language model describes a stochastic process which can be seen as a Markov process with state space given by the internal state of the RNN. This doesn't say anything about the ease of implementing or learning such a model. Just that from a purely mathematical perspective, they are equivalent in power.
- raverbashing 7y agoAh I see, I agree with their equivalence in the mathematical sense.
- srean 7y agoAm curious about what other sense of 'equivalence' you had in mind when you stated with great authority that RNNs are not Markovian.
- raverbashing 7y agoIn the practical sense, implementing a RNN is easier than a Markov Chain (libraries, etc) Also RNNs can "evolve" (or be adapted) more easily to other architectures like LSTMs.
- srean 7y agoThat line of argument does not hold as RNNs are are just special cases of hidden Markov models. If RNNs are easy to implement it means some hidden Markov models are as well. In any case by ease of implementation I think you men availability of libraries rather than something fundamental to the approach. Anyway we have strayed from your claim that RNNs are not Markovian. I was struck by the confidence in the claim especially so because it isnt true by a long shot.
- mratsim 7y agoIf you try implementing a RNN from scratch with the same base as the OP N-order Markov Chain and without Numpy or a deep-learning frame work, I guarantee you that you will not find it so easy. For reference his code his 400 lines and this is what he is importing: #include <stdio.h> #include <vector> #include <string> #include <unordered_map> #include <random> #include <algorithm> #include <array> We can assume that <math.h> import is reasonable for comparison To implement RNNs for text you need to implement tensors/ndarrays of 3 dimensions with slicint and all that jazz, efficient matrix multiplication, implement the RNN, implement the RNN backprop properly. RNNs stands on the shoulder of giants.
- srean 7y ago> As an example try to build a character level Markov chain for text generation. It does appear that you would benefit from such an excercise yourself. No really, just try it. A well trained higher order hidden Markov model would function no less impressively than an RNN and with good reason.
- raverbashing 7y agoLooking at this, I'm almost convinced https://nbviewer.jupyter.org/gist/yoavg/d76121dfde2618422139 https://nbviewer.jupyter.org/gist/yoavg/d76121dfde2618422139 (but to me it still seems a LSTM can do a better job)
- srean 7y agoYup LSTMs can capture distant context, but they arent generic RNNs though. A significant part of "Deep" fanboyism comes from lack of knowledge about capabilities of conventional methods. I dont blame them entirely, there is a lot of diengenuous marketing that should claim partial credit.
- amai 7y agoThis is not a paper, but an interesting blog post nevertheless: The unreasonable effectiveness of Character-level Language Models (and why RNNs are still cool) https://nbviewer.jupyter.org/gist/yoavg/d76121dfde2618422139 https://nbviewer.jupyter.org/gist/yoavg/d76121dfde2618422139
- amai 7y agoMaybe this paper is of interest: Panzner (2016): "Comparing hidden markov models and long short term memory neural networks for learning action representations" https://pub.uni-bielefeld.de/download/2903474/2907910/MOD2016.pdf https://pub.uni-bielefeld.de/download/2903474/2907910/MOD201...