Markov Chain Text Generation | Hacker News Reader

Markov Chain Text Generation

blog.demofox.org

95 pointsingve22 comments

You can use Google search results as a Markov chain (with the ranks translated to probabilities). Then your chain is fitted to all of the visible web.

Another cool use for ML is for categorical and textual data. A fitted Markov Chain can give the probability of a string occuring. Strings that are more random (such as spammy text) get a low probability. Strings that are similar (such as certain user agents) get a similar probability, without having to directly compare these.

Years ago I used Twitter streams as input for markov chain text generation. It’s interesting to recognize your own writing style in what is essentially gibberish: http://yes.thatcan.be/my/next/tweet

really good work !! I had a great laugh reading generated text from Trump and Obama ^^

I did something simliar at university and (amongst other things) ran it over (simple) music scores in Lilypond format. The resulting texts could be converted to MIDI format and played by a synthesizer. It was quite interesting to listen to those. The code is still online at https://github.com/mnagel/markov

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?

In 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.

No, 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.

The 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.

Ah I see, I agree with their equivalence in the mathematical sense.

Am curious about what other sense of 'equivalence' you had in mind when you stated with great authority that RNNs are not Markovian.

In 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.

If 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.

That 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.

> 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.

Looking at this, I'm almost convinced https://nbviewer.jupyter.org/gist/yoavg/d76121dfde2618422139 (but to me it still seems a LSTM can do a better job)

Yup 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.

Maybe 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/MOD201...

This 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

I have a Twitter bot that reads text from random Project Gutenberg books and spits out book passages: https://twitter.com/markovian_lit

In general, it’s a bit all over the place and convoluted, but sometimes it generates true gems. People find it via hashtags, and some folks even interact before realizing it’s a silly bot.

Theres /r/SubredditSimulator/ on Reddit which uses markov chains. Never fails to entertain me.

Ask HN: Markov Chain book recommendations?

Bayesian reasoning and machine learning by Barber (2012) had nice introductory texts on most of the mechanisms at work iirc if you're looking for a lecture oriented resource.

Reply on news.ycombinator.com