# Generating Fantasy Titles with a Markov Chain

- Canonical: https://33rdsquare.com/generating-fantasy-titles-with-a-markov-chain/
- Published: 2024-09-03
- Author: Jordan Brown
- Categories: [Artificial Intelligence & Machine Learning & ChatGPT](https://33rdsquare.com/category/tech/ai/)

---

Have you ever noticed how fantasy book titles tend to follow certain patterns and use similar words or phrases? Series like "The Lord of the Rings", "A Song of Ice and Fire", and "The Wheel of Time" have inspired countless other titles in the genre. It‘s not hard to imagine a formula for coming up with fantasy-sounding titles – perhaps something like: "The [Noun] of [Noun]" or "[Adjective] [Noun]: [Subtitle]".

As it turns out, we can actually train a computer to generate novel fantasy titles by learning the patterns in existing titles. One simple yet surprisingly effective approach is to use a Markov chain. In this post, we‘ll walk through the process of building a fantasy title generator using a Markov chain in Python. By the end, you‘ll not only have a fun tool for brainstorming titles, but also gain some insight into how Markov chains and text generation work. Let‘s dive in!

## A Quick Primer on Markov Chains

Before we get into the fantasy title generation, let‘s briefly cover what a Markov chain is. In simple terms, a Markov chain is a mathematical model that describes a sequence of events or states, where the probability of each event depends only on the state of the previous event.

Markov chains have many applications, but they are often used for text and language processing. When it comes to text, we can think of each word as a "state" in the Markov chain. By analyzing a large amount of example text, we can build a model of which words are likely to follow other words. Then, to generate new text, we can start with a word and use the model to pick the next word based on probability – and so on and so forth until we have a full sentence or paragraph.

The key point is that in a Markov chain, each word depends only on the previous word, not on the words that came before it. So while the generated text will capture local patterns and word-to-word dependencies, it won‘t necessarily make sense globally. With that background out of the way, let‘s see how we can apply Markov chains to fantasy titles!

## Step 1: Gathering Fantasy Title Data

The first step in building our fantasy title generator is to gather a large collection of existing titles to use as training data. The more titles we have, the better our Markov chain will be at learning patterns and generating convincing new titles.

One convenient source is Wikipedia‘s list of fantasy novels. Using a web scraping library like Beautiful Soup in Python, we can extract just the titles from the HTML. Here‘s a snippet of code to do that:

```
import requests
from bs4 import BeautifulSoup

url = "https://en.wikipedia.org/wiki/List_of_fantasy_novels"
response = requests.get(url)
soup = BeautifulSoup(response.text, "html.parser")

titles = []
for row in soup.find_all("tr"):
    title = row.find("td")
    if title:
        titles.append(title.text.strip())
```

This gives us a list of several thousand fantasy titles to work with. Some examples:

- The Lord of the Rings
- The Hobbit
- A Wizard of Earthsea
- The Chronicles of Narnia
- A Game of Thrones
- The Colour of Magic
- The Lies of Locke Lamora
- The Name of the Wind

## Step 2: Data Cleaning and Preprocessing

Before we can use our title data to construct a Markov chain, we need to do some light cleaning and preprocessing, like:

- Converting all titles to lowercase
- Removing punctuation and special characters
- Tokenizing each title into a list of words
- Adding start and end tokens to each title (e.g. `<START>` and `<END>`)

Here‘s some Python code to handle the preprocessing:

```
import re
import string

def preprocess_title(title):
    title = title.lower()
    title = re.sub(r"[{}]".format(string.punctuation), "", title)
    title_tokens = title.split()
    title_tokens = ["<START>"] + title_tokens + ["<END>"]
    return title_tokens

title_token_lists = [preprocess_title(title) for title in titles]
```

Now each title in our dataset will be a list of tokens, like:

```
[‘<START>‘, ‘the‘, ‘hobbit‘, ‘<END>‘]
[‘<START>‘, ‘the‘, ‘fellowship‘, ‘of‘, ‘the‘, ‘ring‘, ‘<END>‘]
```

With our data prepared, we‘re ready to build the Markov chain!

## Step 3: Constructing the Markov Chain Transition Matrix

The core of our fantasy title generator will be the Markov chain transition matrix. This matrix essentially represents the probability of transitioning from one word to another based on the training data.

To construct the matrix, we‘ll create a nested dictionary, where each key is a word, and each value is another dictionary mapping the next word to its count. We‘ll also keep track of the total count of each word for normalization.

```
from collections import defaultdict

# Build word transition counts
word_transition_counts = defaultdict(lambda: defaultdict(int))
word_counts = defaultdict(int)

for title_tokens in title_token_lists:
    for i in range(len(title_tokens) - 1):
        word = title_tokens[i]
        next_word = title_tokens[i+1]
        word_transition_counts[word][next_word] += 1
        word_counts[word] += 1
```

Next, we‘ll normalize the word transition counts into probabilities by dividing each count by the total count for that word:

```
word_transition_probs = {}
for word, transition_counts in word_transition_counts.items():
    transition_probs = {}
    for next_word, count in transition_counts.items():
        transition_probs[next_word] = count / word_counts[word]
    word_transition_probs[word] = transition_probs
```

And with that, we have our Markov chain transition matrix stored in `word_transition_probs`! Each key is a word, and each value is a dictionary mapping the next word to its probability.

## Step 4: Generating Titles from the Markov Chain

Now for the fun part – using our Markov chain to generate new fantasy titles! The process is fairly straightforward:

1. Start with the `<START>` token
2. Sample the next word based on the transition probabilities for the current word
3. Append the sampled word to the generated title
4. Repeat steps 2-3 until the `<END>` token is sampled
5. Join the generated words into a title string

Here‘s a Python function to generate a title from the Markov chain:

```
import random

def generate_title(word_transition_probs, max_length=10):
    generated_title = []
    current_word = "<START>"

    while current_word != "<END>" and len(generated_title) < max_length:
        next_word_probs = word_transition_probs[current_word]
        next_word = random.choices(list(next_word_probs.keys()),
                                   list(next_word_probs.values()))[0]
        if next_word != "<END>":
            generated_title.append(next_word)
        current_word = next_word

    return " ".join(generated_title)
```

Let‘s generate some titles and see what we get!

```
for i in range(10):
    print(generate_title(word_transition_probs))
```

Here are some example generated titles:

- the dragon throne
- a wizard of the mist
- the emerald storm
- a crown of blood and sorrow
- shadows of the black blade
- the well of ascension
- mistborn the alloy law
- the lies of saint
- dreamwood tales
- the dark elf king

Not bad! Many of these sound quite plausible as real fantasy titles. Of course, there are some that don‘t quite make sense, and you may notice the model reproducing parts of titles directly from the training data. But overall, the Markov chain does a decent job of capturing the "essence" of fantasy titles.

## Evaluating the Results and Next Steps

So how well does our Markov chain fantasy title generator actually work? Let‘s consider some of its strengths and weaknesses.

On the positive side, the model is able to generate titles that generally follow the common patterns and conventions of the fantasy genre. It picks up on things like:

- Recurring words/phrases: "the", "of", "shadow", "dragon", "throne", etc.
- Title templates: "The X of Y", "X of the Y", "The X Y"
- Mythical/medieval words: "crown", "blood", "ascension", "blade", "elf"

The generated titles are also mostly grammatical, even if they don‘t always make semantic sense.

However, there are some clear limitations. For one, the model has no real understanding of the meaning of words or the relationships between them – it‘s simply stringing together words based on probability. This can lead to nonsensical or contradictory titles.

The Markov chain also tends to get "stuck" generating short or repetitive titles, especially if a certain partial title occurs frequently in the training data. You may have noticed some of the generated titles above directly reproducing parts of real titles.

Lastly, while the model can remix and recombine words from existing titles in new ways, it can‘t introduce any novel words or concepts that weren‘t already in the training data.

To improve on our basic Markov chain title generator, we could try a few things:

- Gather a larger and more diverse training dataset
- Do additional data cleaning to remove very long/short titles, series names, etc.
- Experiment with more sophisticated models like higher-order Markov chains
- Use techniques like smoothing or back-off to handle unseen word transitions
- Filter or post-process generated titles based on heuristics (e.g. removing exact duplicates of real titles)

## Beyond Markov Chains: Neural Text Generation

While Markov chains are a good introduction to text generation, modern approaches typically involve neural networks and deep learning. With large datasets, neural language models like Long Short-Term Memory (LSTM) networks and Transformers can learn to generate impressively fluent and coherent text.

Some state-of-the-art language models like GPT-3 are trained on huge datasets with hundreds of billions of words. They can generate text in many different styles and domains, from news articles to poetry to code.

I suspect we‘ll see more and more applications of AI in assisting creative writing in the near future. Imagine an intelligent brainstorming tool that can not only generate titles, but also character names, plot ideas, worldbuilding details, and more to jumpstart a fantasy story!

## Conclusion and Further Resources

In this post, we walked through the process of building a simple fantasy title generator using a Markov chain:

1. Gathering fantasy title data from Wikipedia
2. Cleaning and preprocessing the title text
3. Building the Markov chain transition matrix
4. Sampling the Markov chain to generate new titles

While the results are far from perfect, the Markov chain is able to capture some of the style and patterns of fantasy titles in an automated way. More importantly, it provides a concrete example of a text generation algorithm, and a stepping stone to more advanced techniques.

If you‘re interested in learning more about text generation and natural language processing, I recommend checking out the following resources:

- Allison Parrish‘s Gutenberg Poetry Corpus: A great dataset for training poetry generators and doing other creative text experiments
- The Unreasonable Effectiveness of Recurrent Neural Networks: Andrej Karpathy‘s classic blog post on using RNNs for text generation
- Jay Alammar‘s Illustrated Guide to Transformers: A very accessible introduction to transformer language models
- GPT-3 Creator Asks AI to Explain Itself: A thought-provoking conversation with GPT-3 on AI and language models

I‘m excited to see where AI-augmented creative writing goes in the future. Until then, happy (neural) daydreaming!

---

Source: [Generating Fantasy Titles with a Markov Chain](https://33rdsquare.com/generating-fantasy-titles-with-a-markov-chain/)