I like to learn about machine and deep learning. So while conversing about LLMs with a friend of mine—who is actually quite famous and whose name rhymes with GPT—he suggested that I try to build its primitive version. A Markov Chain-based n-gram Probabilistic Text Prediction Model. I know that sounds heavy, but it's not that deep. Trust me bro.
Take this sentence:
How are ___?
You probably just filled in the blank without even meaning to. What you just did is a result of thousands of hours of education and reading and exposure to the English language. What you just did is predict the next word in the sentence by considering the ones immediately before it.
That, but its digital and much dumber version, is the Markov Chain-based n-gram Probabilistic Text Prediction Model.
- A Markov chain is a state machine, where only the information about your current position guides what may come next.
- A bigram or 2-gram model uses 1 word as context to predict the next one. The gram count n includes both the number of words used as context as well as the one word that is predicted. That is n-gram. In a trigram or 3-gram model, the last two words are used as context to predict the next one.
- The model is probabilistic because it maps frequencies to the following words in the training phase. The more times B has succeeded A, the higher chance there is that the model will predict B after A is seen. Tying the Markov Chain into this, if the current state is A, there will be a higher chance of moving to state B as opposed to other possible states.
- Finally, this model is able to predict text by using a starting word/phrase as the initial state, then predicting the next word based on patterns it "learnt" during the training phase.
When I started, I decided to break down the problem and only focus on the bigram model. The sole goal was to get only that working somehow. Now, at this point, I had learnt that problem solving started with the data structure. You choose the right one, it makes your life easier. You choose wrong, you have to go to your friend for advice.
Let's try to figure it out. Take this phrase:
get a new friend
Here, there are only 3 pairs that can be formed - (get, a), (a, new) and (new, friend). When the model is trained, it is supposed to read every word as a parent and the following one as its successor (potential successor by the way).
This means that my data structure had to store a collection of all possible parent-successor pairs for any given number of words. At this point, all the hashmap memes started to stream into my head and I decided that the map was the best way to navigate this problem :)
Note that a parent word could have many successors. "new" could be succeeded by "friend", "playstation", "life" etc. in a single text. Which means that our map must store not only all the parent words, but also all of the successors AND how often the successors followed the parents. Since a map only stores unique keys (which would be all of the parent words), the value part will have to store all of successors along with their respective frequencies. At this point, the hashmap memes started flooding my mind again...ok I'll stop.
The point is, the map would have to store all possible parent words as keys and then store another map as the key. The inner map will store all successors as keys and their frequencies as the values. This is what that looks like:
map< parent, map<successor, frequency> >
But I had to take a step back, because it still wasn't clear how the map would be populated. How was I going to prepare the raw text data? In order to break down the problem further, I thought of stripping all the punctuation and capital letters from the text to homogenize it. Then, I could put all the words in a vector where the original order was maintained.
After that, filling up the map was extremely simple:
map<string, map<string, int>> vector2Map(const vector<string>& words)
{
map<string, map<string, int>> fMap;
for (size_t i = 0; i < words.size() - 1; i++)
{
fMap[words[i]][words[i + 1]]++;
}
return fMap;
}
- This snippet
fMap[words[i]][words[i + 1]]++is quite powerful and I love the C++ allows us to do this. Feel free to skip ahead if you already understand what it does.fMap[words[i]]tries to access the string key as inwords[i]. If that doesn't already exist, it creates a new key AND initializes its value with an emptymapbecause that is already defined to be the data type for its value.- Immediately after that, it checks for the key
words[i + 1]in the inner map. If that key doesn't exist, it yet again creates it AND initializes its value with 0, because the value of the inner map is defined to be an integer. - So, it accessed/created parent key, then accessed/created successor key, and finally added 1 to the inner map's value, which automatically started at 0.
After the map had been populated successfully, I was ready to use it for generating sentences. But for that, a predict() function was needed. In essence, the algorithm had to take a parent word as input and choose a successor out of all possible ones.
Since the chance of a certain successor to be chosen increased with the amount of times it actually appeared in the original text, using probability seemed obvious. So that is what I did. Literally, as easy as this:
Frequency of A
P(word A) = ---------------
Total Frequency
Firstly, I made a pass through all the frequencies in the inner map for a given parent word and added up all of them to calculate the total frequency. Then, I generated a random number R between 0 and 1 and made another pass, but this time, I added the probabilities for each until they added up to greater than R. Whichever word pushed the total over the R, was chosen.
At first, this approach may not seem intuitive. Don't let the order of the word probabilities confuse you. The reason why this works is that a word with a larger frequency will naturally have a larger probability, and this larger probability will in turn have a higher chance of pushing the cumulative probability over R.
Here is a better way of understanding this: Imagine a line from 0 to 1 with partitions that all words create using their probabilities. These partitions have different "areas" based on their probabilities. All we are doing is generating a random number and checking in which partition it lands. Since the computer cannot do this at a glance, we use the cumulative probability to check the landing area.
Extremely helpful infographic generated by ChatGPT using the last three paragraphs as the prompt. Note that the probabilities needn't be arranged in a sorted order:
The same logic translated to C++ code:
void predict(string start, unsigned int word_count) override {
auto& fMap = model_data; // this is our map
unsigned int i = 0; string current = start;
cout << start << " ";
while (i < word_count) {
if (fMap.find(current) == fMap.end()) break;
double r = randomNumGenerator();
double cumulative_prob = 0.0;
map<string, int> temp = fMap.at(current);
int total = nextWordsfSum(temp);
for (const auto& [word, count] : temp) {
cumulative_prob += (double)count / total;
if (cumulative_prob >= r) {
cout << word << " ";
i++;
current = word;
break;
}
}
}
cout << "\n\nPrediction terminated!" << endl;
}
I had another friend of mine (this one is more privacy-focused, so no hints :) ) provide the training text. This model design worked surprisingly well. Here are some admittedly cherry-picked results:
the school begins the teacher takes attendance and closes his school after math comes at nine
the playground again science notebook and a house tim mixes colors on the ball back and
Ultimately, I was not satisfied with the output, solely because the next step towards supposedly massive improvement was right in front of me: Trigrams.
Here were some problems with my bigram code that made it quite hard to advance to trigrams:
- The program was hard-coded for bigrammatic predictions. Right from the very data structure used. Using
std::stringas the outer key meant sacrificing abstraction for arbitrary context lengths. I could only fill the map keys with single words that would help predict the next one. In all fairness, this can be solved by usingstd::vectoras the outer key. This would have made the input scalable while keeping the inner map the same. Additionally, my initial goal was just to get bigram working, so code's limitations weren't a nasty surprise for me. - I also read into the performance implications, and it turns out that maps are incredibly inefficient for this kind of work. This is because a map is implemented as a kind of binary tree, whose elements are scattered across memory (heap allocation) which, for lookup, the CPU must then navigate through using pointers, leading to significant overhead and cache misses. This problem is exacerbated through the use of nested maps. Imagine navigating outer keys using pointers, then navigating inner keys using pointers, just to update the frequency count. Now imagine having to do that for thousands of words. And that is just the training phase. The same applies to the prediction phase.
Clearly, my choice for the data structure was suboptimal. Reaching out to my friend became unavoidable.
More on that in the next blog. Stay tuned!