Whether or not computers will one day achieve true human-level intelligence or be otherwise able to achieve human-level capabilities is a good topic for a long debate and people have strong feelings on both sides. People opposed to the idea that a machine can be capable of thought will usually appeal to intangible notions that appear to be uniquely human such as love, ability to appreciate music, write poetry, etc… In this post, I want to explore the last point: machine written poetry. I don’t plan to prove anyone wrong but it will be fun to try.
In order to generate poetry, I will use a simple/naive approach that goes by many names including Markov text generation and is also known as the Dissociated Press algorithm. If you want to just see the algorithms and some sample poems, scroll down.
Markov Chains
The idea behind a Markov chain is that you have a system with a number of states and at every time-step you move to a new state. How do you choose the next step? At every state you have a list of outgoing transitions to other states and you pick the next state by picking (at random) from the list of transitions. The transitions have weights so you’re more likely to pick some transitions than others.
Let’s take a look at this simple system that I lifted from Wikipedia. In this system you have just two states A and E. Let’s say you start in A at time t = 0. At time t = 1, you need to choose what to do next. You can pick either of the outgoing transitions out of A. So with a probability of 0.4 you might move to state E and with a probability of 0.6 you might move to state A (i.e., you don’t go anywhere.)
Markov Chain with two states A & E. Source: http://en.wikipedia.org/wiki/Markov_chain
Let’s say you picked the transition that keeps you in A. Now at time t = 2 you have to make a choice again, so you flip a weighted coin and pick the transition out of A to E; now you’re at state E. Now at t=2 you’ve gone through the following sequence of states: A,A,E and are in state E. This system is an order 1 Markov chain. It’s order 1 because the transitions and probabilities available to you are a function of only the state you are in currently. You can extend this idea to be a nth order Markov system, in which case your transition probabilities will be a function of your last n states.
This might look as far from poetry as one can get but we’re getting there: if you think of every possible word in the English language as a possible ‘state’ in a Markov chain, then you can randomly move between words to generate strings of words. In order to build this Markov chain, you need to analyze a lot of English text (in our case poems) and record how often a given word is followed by another word. If word w1 is followed by word w2 10% of the time then draw a transition between w1 and w2 and give it a weight of 0.1, etc… To do this you need a large corpus of “training text”. The machine needs to learn from examples of poetry in order to write poetry. You can even generalize this to create a second-order Markov chain. This method has been used to generate music and other types of texts.
Algorithm
Turns out that you don’t need to explicitly pre-calculate the transition matrix. Instead you can try this algorithm:
- Pick a random n-gram of text from your training corpus. Use this n-gram as the beginning of your text (or poem)
- For some number of iterations, i:
- Take the last n-gram of your poem and find all occurrences of this n-gram in your training corpus
- Pick one of the occurrences at random. Take the first word that follows your picked occurrence and append it to your poem. Repeat.
Let’s say you take n=2 and start with the bigram: “to be”. Then you look into your corpus and find that is followed by the following words: “or”, “that”, “happy”, “happy” again and a few others. You pick one of them at random (let’s say “that”) and append it to your growing poem: “to be that”. At the next iteration you look at the last bigram in your poem “be that” and find words that follow it in your corpus, etc…
Results
To test this idea, I used python’s scrapy to scrape the top 500 poems list from http://poemhunter.com and used that as my training corpus. I picked my starting n-gram at random. Here are some sample poems generated for n=2:
say turn it outdoors into the night
who rounded the earth
and everything that is
all that i may
die i hope you
realise that your brothers
yes i know anger
as black as cain
may be i said
to him ambition s
paths appear and bright
meet in her aspect
and her training bra
pity and terror of
eczema and i answer —————————————- the tears and sighs
of the poor streets
where only a few
children fumbled with bare
red fingers in the
frosty silence tlot tlot
in the darkness and
then and there she
stands as if she
were alive i call
that piece a wonder
now fr pandolf chanced
to say that health
and wealth have missed
me say i love
an earnest soul
whose
I’d say these are not bad — with some editing these could probably earn a passing grade in an intro to poetry class!
Some notes:
- The higher the value of n (i.e. trigram, quadgrams, etc…) the less likely you are to find the n-gram in the corpus which means that you’ll just be copying an existing poem — unless your corpus is huge. The lower your n-gram, the less sense your “poems” will make. I found n=2 to be a good happy ground. If I could get a bigger collection of poems, I could probably go to n=3.
Mike's Lab Notebook 