Markov Chains: The right way to Prepare Textual content Era to Write Like George R. R. Martin



Markov chains have been round for some time now, and they’re right here to remain. From predictive keyboards to purposes in buying and selling and biology, they’ve confirmed to be versatile instruments.

Listed below are some Markov Chains trade purposes:

  • Textual content Era (you’re right here for this).
  • Monetary modelling and forecasting (together with buying and selling algorithms).
  • Logistics: modelling future deliveries or journeys.
  • Search Engines: PageRank can seen as modelling a random web surfer with a Markov Chain.

Up to now, we are able to inform this algorithm is helpful, however what precisely are Markov Chains?


What are Markov Chains?

A Markov Chain is a stochastic course of that fashions a finite set of states, with fastened conditional possibilities of leaping from a given state to a different.

What this implies is, we can have an “agent” that randomly jumps round totally different states, with a sure chance of going from every state to a different one.

To point out what a Markov Chain seems to be like, we are able to use a digraph, the place every node is a state (with a label or related information), and the load of the sting that goes from node a to node b is the chance of leaping from state a to state b.

Right here’s an instance, modelling the climate as a Markov Chain.

A diagram showing a Markov Chain as a weather model example.

We will specific the chance of going from state to state b as a matrix part, the place the entire matrix characterizes our Markov chain course of, similar to the digraph’s adjacency matrix.

The adjacency Matrix for the graph in the previous picture.

Then, if we symbolize the present state as a one-hot encoding, we are able to get hold of the conditional possibilities for the following state’s values by taking the present state, and its corresponding row.

After that, if we repeatedly pattern the discrete distribution described by the n-th state’s row, we might mannequin a succession of states of arbitrary size.


Markov Chains for Textual content Era

As a way to generate textual content with Markov Chains, we have to outline a number of issues:

  • What are our states going to be?
  • What possibilities will we assign to leaping from every state to a distinct one?

We may do a character-based mannequin for textual content era, the place we outline our state because the final n characters we’ve seen, and attempt to predict the following one.

I’ve already gone in-depth on this for my LSTM for Text Generation article, to combined outcomes.

On this experiment, I’ll as an alternative select to make use of the earlier okay phrases as my present state, and mannequin the chances of the following token.

As a way to do that, I’ll merely create a vector for every distinct sequence of okay phrases, having N parts, the place N is the overall amount of distinct phrases in my corpus.

I’ll then add 1 to the j-th part of the i-th vector, the place i is the index of the i-th k-sequence of phrases, and j is the index of the following phrase.

If I normalize every phrase vector, I’ll then have a chance distribution for the following phrase, given the earlier okay tokens.

Complicated? Let’s see an instance with a small corpus.


Coaching our chain: toy instance.

Let’s think about my corpus is the next sentence.

This sentence has 5 phrases

We’ll first select okay: the amount of phrases our chain will think about earlier than sampling/predicting the following one. For this instance, let’s use okay=1.

Now, what number of distinct sequences of 1 phrase does our sentence have? It has 5, one for every phrase. If it had duplicate phrases, they wouldn’t add to this quantity.

We’ll first initialize a 5×5 matrix of zeroes.

After that, we’ll add 1 to the column similar to ‘sentence’ on the row for ‘this’. Then one other 1 on the row for ‘sentence’, on the column for ‘has’. We’ll proceed this course of till we’ve gone by means of the entire sentence.

This could be the ensuing matrix:

A diagonal matrix of 5x5.

The diagonal sample comes from the ordering of the phrases.

Since every phrase solely seems as soon as, this mannequin would merely generate the identical sentence time and again, however you possibly can see how including extra phrases may make this fascinating.

I hope issues are clearer now. Let’s bounce to some code!


Coding our Markov Chain in Python

Now for the enjoyable half! We’ll practice a Markov chain on the entire A Track of Ice and Hearth corpus (Ha! You thought I used to be going to reference the present? Too unhealthy, I’m a ebook man!).

We’ll then generate sentences with various values for okay.

For this experiment, I made a decision to deal with something between two areas as a phrase or token.

Conventionally, in NLP we deal with punctuation marks (like ‘,’ or ‘.’) as tokens as effectively. To resolve this, I’ll first add padding within the type of two areas to each punctuation mark.

Right here’s the code for that small preprocessing, plus loading the corpus:

corpus = ""
for file_name in file_names:
    with open(file_name, 'r') as f:
corpus = corpus.change('n',' ')
corpus = corpus.change('t',' ')
corpus = corpus.change('“', ' " ')
corpus = corpus.change('”', ' " ')
for spaced in ['.','-',',','!','?','(','—',')']:
    corpus = corpus.change(spaced, '  '.format(spaced))
len(corpus) #10510355 characters

We’ll begin coaching our Markov Chain straight away, however first let’s have a look at our dataset:

corpus_words = corpus.cut up(' ')
corpus_words= [word for word in corpus_words if word != '']
corpus_words # [...'a', 'wyvern', ',', 'two', 'of', 'the', 'thousand'...]
len(corpus_words) # 2185920

distinct_words = checklist(set(corpus_words))
word_idx_dict = phrase: i for i, phrase in enumerate(distinct_words)
distinct_words_count = len(checklist(set(corpus_words)))
distinct_words_count # 32663

Now we have over 2 million tokens, representing over 32000 distinct phrases! That’s a reasonably large corpus for a single author.

If solely he may add 800okay extra…


Coaching our chain

Shifting on, right here’s how we initialize our “word after k-sequence” counts matrix for an arbitrary okay (on this case, 2).

There are 2185918 phrases within the corpus, and 429582 totally different sequences of 2 phrases, every adopted by considered one of 32663 phrases.

Which means solely barely over zero.zero15% of our matrix’s parts will probably be non-zero.

Due to that, I used scipy’s dok_matrix (dok stands for Dictionary of Keys), a sparse matrix implementation, since we all know this dataset goes to be extraordinarily sparse.

okay = 2 # adjustable
sets_of_k_words = [ ' '.join(corpus_words[i:i+k]) for i, _ in enumerate(corpus_words[:-k]) ]

from scipy.sparse import dok_matrix

sets_count = len(checklist(set(sets_of_k_words)))
next_after_k_words_matrix = dok_matrix((sets_count, len(distinct_words)))

distinct_sets_of_k_words = checklist(set(sets_of_k_words))
k_words_idx_dict = phrase: i for i, phrase in enumerate(distinct_sets_of_k_words)

for i, phrase in enumerate(sets_of_k_words[:-k]):

    word_sequence_idx = k_words_idx_dict[word]
    next_word_idx = word_idx_dict[corpus_words[i+k]]
    next_after_k_words_matrix[word_sequence_idx, next_word_idx] +=1

After initializing our matrix, sampling it’s fairly intuitive.

Right here’s the code for that:

def sample_next_word_after_sequence(word_sequence, alpha = zero):
    next_word_vector = next_after_k_words_matrix[k_words_idx_dict[word_sequence]] + alpha
    likelihoods = next_word_vector/next_word_vector.sum()
    return weighted_choice(distinct_words, likelihoods.toarray())
def stochastic_chain(seed, chain_length=15, seed_length=2):
    current_words = seed.cut up(' ')
    if len(current_words) != seed_length:
        increase ValueError(f'mistaken variety of phrases, anticipated seed_length')
    sentence = seed

    for _ in vary(chain_length):
        sentence+=' '
        next_word = sample_next_word_after_sequence(' '.be a part of(current_words))
        current_words = current_words[1:]+[next_word]
    return sentence
# instance use    
stochastic_chain('the world')

There are two issues that will have caught your consideration right here. The primary is the alpha hyperparameter.

That is our chain’s creativity: a (usually small, or zero) likelihood that it’ll choose a completely random phrase as an alternative of those recommended by the corpus.

If the quantity is excessive, then the following phrase’s distribution will method uniformity. If zero or nearer to it, then the distribution will extra intently resemble that seen within the corpus.

For all of the examples I’ll present, I used an alpha worth of zero.

The second factor is the weighted_choice perform. I needed to implement it since Python’s random package deal doesn’t help weighted selection over an inventory with greater than 32 parts, not to mention 32000.


Outcomes: Generated Sentences

To begin with, as a baseline, I attempted a deterministic method: what occurs if we choose a phrase, use okay=1, and all the time bounce to the most probably phrase after the present one?

The outcomes are underwhelming, to say the least.

I am not have been a person , and the Wall . " " " "
he was a person , and the Wall . " " " " " " "
she had been a person , and the Wall . " " " " " "

Since we’re being deterministic, ‘a’ is all the time adopted by ‘man’, ‘the’ is all the time adopted by ‘Wall’ (hehe) and so forth.

This implies our sentences will probably be boring, predictable and form of nonsensical.

Now for some precise era, I attempted utilizing a stochastic Markov Chain of 1 phrase, and a worth of zero for alpha.


1-word Markov Chain outcomes

Listed below are among the ensuing 15-word sentences, with the seed phrase in daring letters.

'the Seven in entrance of whitefish in an enormous blazes burning flesh . I had been'
 'a squire , slain , they thought . " He bathed in his head . The'
 'Bran stated Melisandre had been in worry I’ve completed . " It should wants you'll'
 'Melisandre would have feared he’d squired for one thing else I put his place of Ser Meryn'
 'Daenerys is useless cat - TOOTH , AT THE GREAT , Asha , which fills our'
 'Daenerys Targaryen after Melara had worn wealthy gray sheep to encircle Stannis . " The deep'

As you possibly can see, the ensuing sentences are fairly nonsensical, although much more fascinating than the earlier ones.

Every particular person pair of phrases makes some sense, however the entire sequence is pure non-sequitur.

The mannequin did be taught some fascinating issues, like how Daenerys is often adopted by Targaryen, and ‘would have feared’ is a fairly good development for less than realizing the earlier phrase.

Nonetheless, on the whole, I’d say that is nowhere close to pretty much as good because it could possibly be.

When growing the worth of alpha for the single-word chain, the sentences I bought began turning much more random.


Outcomes with 2-word Markov chains

The 2-word chain produced some extra fascinating sentences.

Regardless that it too often ends sounding utterly random, most of its output may very well idiot you for a bit at first (emphasis mine).

'the world . And Ramsay beloved the texture of grass welcomed them warmly , the axehead flew'
'Jon Snow . You might be to strike at him . The daring ones have had no sense'
'Eddard Stark had completed his greatest to present her the promise was damaged . By custom the'
'The sport of thrones , so you could inform her the following purchaser who comes operating ,'
'The sport path introduced her messages , unusual spices . The Frey stronghold was not giant sufficient'
'heard the scream of worry . I need to undress correctly . Shae was there , fettered'

The sentences preserve native coherence (You might be to strike at him, or Ramsay beloved the texture of grass), however then be a part of very coherent phrase sequences into a complete mess.

Any sense of syntax, grammar or semantics is clearly absent.

By the way in which, I didn’t cherry-pick these sentences in any respect, these are the primary outputs I sampled.

Be happy to play with the code yourself, and you may share the weirdest sentences you get within the feedback!

Since we’re utilizing two sentences as keys now, we are able to’t let the chain ‘get creative’ as within the earlier one-word case. Due to this fact, the alpha worth needed to be stored on zero.

Instead, I considered setting it a bit greater, after which all the time deciding on the closest FuzzyWuzzy string matching (an approximation of string equality) as an alternative of tangible matching. I’ll strive that sooner or later, although I’m unsure the outcomes will probably be good.

As a final experiment, let’s see what we get with a 3-word Markov Chain.


3-Phrase Chain Outcomes

Listed below are among the sentences the mannequin generated when educated with sequences of 3 phrases.

'I'm a grasp armorer , lords of Westeros , sawing out every bay and peninsula till the'
'Jon Snow is with the Evening’s Watch . I didn't survive a damaged hip , a leathern'
'Jon Snow is with the Hound within the woods . He gained’t do it . " Please don’t'
'The place are the chains , and the Knight of Flowers to deal with with you , Imp . "'
'These have been the similar . Arianne demurred . " So the fishwives say , " It was Tyrion’s'
'He thought that can be good or unhealthy for his or her escape . If they'll really give us'
'I assumed that she was like to recollect a younger crow he’d met briefly years earlier than . "'

Alright, I actually appreciated a few of these, particularly the final one. It kinda seems like an actual sentence you can discover within the books.



Implementing a Markov Chain is lots simpler than it could sound, and coaching it on an actual corpus was enjoyable.

The outcomes have been frankly higher than I anticipated, although I’ll have set the bar too low after my little LSTM fiasco.

Sooner or later, I’ll strive coaching this mannequin with even longer chains, or a very totally different corpus.

On this case, making an attempt a 5-word chain had principally deterministic outcomes once more, since every 5-word sequence was nearly all the time distinctive, so I didn’t think about 5-words and upwards chains to be of curiosity.

Which corpus do you assume would generate extra fascinating outcomes, Particularly for an extended chain? Let me know within the feedback!

Bio: Luciano Strika is a pc science scholar at Buenos Aires College, and a knowledge scientist at MercadoLibre. He additionally writes about machine studying and information on

Original. Reposted with permission.


About the Author

Leave a Reply

Your email address will not be published. Required fields are marked *