Bigrams for Natural Language Processing
What is a word?
Really and seriously, what is a word? Are words simply a collection of characters spaced out by spaces/seperators? But what about other languages that have really short words like Chinese or words in Turkish that are really long. What about things that we don’t really consider are words like punctuation, commas, and exclaimations? When we speak we usually put some sort of filler word like ums or uhs. When training a language model, we typically don’t include these Fillers. If we consider the number of words in a language and the number of word instances to be then their relationship can be found to be
The issue here is that some types of words, especially those that are not Function Words such as nouns tend to grow indefinitely. We can not expect a language model to ever hold the entire vocabulary corpus of a language like this! That is, our model is bound to see words it has never ever seen before, which is an issue when we think of simplistic tokenization algorithms that simply split characters by some sort of delimiter.
Morphemes
Words are often composed of morphemes, the smallest possible unit that bears any meaning in a particular language. We typically can distinguish these morphemes into two categories, the root and the affixes. The root is what gives the primary meaning to the word while the affixes give additional meaning.
Unicode
We can also tokenize words based on their Unicode encoding. For english, we represent the latin characters of our language based off of ASCII. For each character in our alphabet it is given a single byte as its unique representation. This is not going to be sufficient when representing characters in other languages, which is where unicode encodings come into play. We represent the unicode encoding of a character by a hexidecimal number ranging from to .
Byte Pair Encoding
The Byte Pair Encoding algorithm is as follows:
- Obtain the set of all unique characters in the training corpus.
- Check every single “pair” of adjacent characters/words, and finds the pair that occurs the most frequently in the text.
- Replace all occurrences of most frequent pairs with the new merged token found above.
The algorithm is really quite simple, if we consider the following walkthrough
A B C B C A // Start out with the following characters
A BC BC A // Observe that the pair (B,C) are the most frequent so we merge them
... tie breaking and continue merging for some arbitrary constant k.N-Grams
Simply put, an n-gram is a sequence of words. What we want to do is to be able to produce a probability distribution of the most likely words to occur proceeding a history of text. That is to predict the th word of a text given that we have observed the preceeding words. Say for example we wanted to predict the following
If we want to be able to know what is the probability of the word “blue” given this history of text, we can formalize it to be
A really simple way to predict this probability (given a large enough training corpus) is to literally count the occurences of this sentence and check also the occurrences of the sentence “Roses are Red, Violets are Blue”. This is obviously not feasible with arbitrary sentences, words are emergent and we can easily produce new sentences that likely have never been said in the history of humanity if we so choose to.
Picking back up where we left off, we can represent a sequence of words as just . We can represent the probability of a particular word (in this case “the”) in a sequence of words occurring to be . Naturally it follows that the joint probability of a sequence of words is to be represented as such…
There are a few ways to compute this probability, but neither are really appealing. The chain rule of probability involves computing a bunch of conditional probabilities together which isn’t very practical. We can however make an assumption to give an approximate probability. That is we can assume the markov assumption. That is, instead of computing this monstrosity:
We can approximate it by assuming that each word in the sequence only depends only the previous word.
Maximum Likelihood Estimation
An intuitive way to compute the probabilities of words from a n-gram language model is to use maximum likelihood estimation. To compute the probability of a particular word given a word before it we simply take that sequence and then ask what are the counts in our corpus that match this word sequence exactly vs what is the count of our words that match for any word proceeding . That is to say
The book postulates that
In other words, if we sum all the bigrams that start with the word in a corpus, it must be equal to the occurrences of in our corpus.
For this particular implementation of the bigram, I will be training a bigram language model on my website corpus. As I am currently writing the top words and their occurrences are as follows…
Using this table, we can easily compute the conditional probabilities for any sequence found in our training sequence. For example: