{"id":825,"date":"2024-12-16T18:26:11","date_gmt":"2024-12-16T23:26:11","guid":{"rendered":"https:\/\/brian.digitalmaddox.com\/blog\/?p=825"},"modified":"2024-12-16T18:26:11","modified_gmt":"2024-12-16T23:26:11","slug":"some-background-on-natural-language-processing-part-2-older-methods-and-techniques","status":"publish","type":"post","link":"https:\/\/brian.digitalmaddox.com\/blog\/?p=825","title":{"rendered":"Some Background on Natural Language Processing – Part 2: Older Methods and Techniques"},"content":{"rendered":"

Last time we learned why English is a hard language, both for humans and especially for computers.\u00a0 <\/span>For this time I think we will look at the past of NLP to understand the present. It actually has been an interesting history to get to where we are now.<\/p>\n

Historic NLP methods relied on approaches that focused more on linguistics and statistical analysis.\u00a0 <\/span>Computers were not as powerful as they are now, and definitely did not have GPUs with the crazy amount of processing capability that they have now.\u00a0 <\/span>They can be broadly grouped into six categories: rule-based systems, bag of words, term frequency-inverse document frequency, n-grams, Hidden Markov Models, and Support Vector Machines.\u00a0 <\/span>Let us explore these methods to see how they worked and led to today\u2019s more powerful systems. \u00a0This post will have a lot of links to other sources of information as it is intended to be more of a gentle introduction than an exhaustive analysis.<\/p>\n

Rule-Based Systems<\/h2>\n

Rule-Based Systems<\/a> are perhaps the oldest method of trying to get a computer to be able to process a language.\u00a0 <\/span>These systems were built on predefined linguistic rules and handcrafted grammars.\u00a0 <\/span>Grammar<\/a> in this case is not about usage, such as matching nouns and verbs and what not.\u00a0 <\/span>In this case the grammar is known as a formal grammar that is a mathematical structure of a sentence.\u00a0 <\/span>One specific method is a context-free grammar<\/a> that has a set of rules of how to form sentences from smaller words and phrases.<\/p>\n

Rule-based systems explicitly encode language in a series of rules so that text can be parsed.\u00a0 <\/span>This parsing would then be able to identify parts of speech and identify sentence structure.\u00a0 <\/span>These rules were typically created by linguists and software developers working together to try to codify language as a series of mathematical rules.<\/p>\n

The rules they would create were simple so that they could be combined together for more complex sentences. \u00a0 <\/span>For example, one rule could be \u201cany word that ends in ing<\/strong> is likely a verb\u201d, while another could be \u201ca noun follows determiner words such as a<\/strong>, then<\/strong>, and an<\/strong>.\u201d\u00a0 <\/span>The developer would then take these rules to create a parser to take in sentences and break them down into their syntactic components using the mathematically-defined grammars.<\/p>\n

Since I am a cat person, let us look at this very simple example sentence: \u201cMy cat is playing with a toy.\u201d\u00a0 <\/span>In this case, the<\/strong> would be tagged as a determiner words, so cat<\/strong> would be tagged as a noun.\u00a0 <\/span>Is playing<\/strong> would be identified as a verb.\u00a0 <\/span>A<\/strong> is another determiner word, so toy would be tagged as another noun.<\/p>\n

While this sounds simple, these systems were complex and labor intensive.\u00a0 <\/span>They required the work of expert linguists and developers to build the parsing systems.\u00a0 <\/span>They required a lot of maintenance as problems were found and the rules needed to be modified.\u00a0 <\/span>As they were based on formal mathematics, they were not very flexible when it comes to something sloppy like English.\u00a0 <\/span>This meant that rules after rules would have to be developed and stacked on top of one another.<\/p>\n

Bag of Words<\/h2>\n

The Bag of Words<\/a> (BoW) method was an early attempt at applying statistical processing to NLP.\u00a0 <\/span>It sought to represent text in a numerical form so that statistical algorithms could be applied.\u00a0 <\/span>These algorithms could then do things like classify documents or determine the similarity of two different documents.<\/p>\n

The BoW method works by treating the input text as an unordered collection of words.\u00a0 <\/span>In this case, however, neither the order of words nor the sentence grammar are used.\u00a0 <\/span>The document is tokenized<\/a>, where the words are converted into tokens.\u00a0 <\/span>A list of each unique token is then created.\u00a0 <\/span>The input text is analyzed and each word is counted to determine the frequency of occurrence in the document.\u00a0 <\/span>The document is then converted into a vector of word frequencies that is the same size as the number of unique words in the document.<\/p>\n

You may know vectors from geometry where they represent lines and their direction.\u00a0 <\/span>It is still similar in this case where it is a mathematical array of numbers<\/a>.\u00a0 <\/span>In the case of a frequency representation, the array could look something like [10, 5, 3, 9] and so on, where each number represents the frequency a word appears.<\/p>\n

For computing document similarity, both documents would be turned into frequency vectors by enumerating their unique words and then creating a vector that is the same length as the total number of unique words.\u00a0 <\/span>The frequencies of each word are inserted into the array, with a zero placed in locations where a word occurs in one document but not in the other.\u00a0 <\/span>The order of the word frequencies of the array can be sorted so each array entry corresponds to the same one in the other document.<\/p>\n

The comparison is easier to think of back in terms of geometry.\u00a0 <\/span>There are two methods to compute the distance between the vectors: cosine similarity<\/a> and Euclidean Distance<\/a>.\u00a0 <\/span>For cosine similarity, the cosine of the angle between the two vectors in multidimensional space<\/a> is calculated with the result being between -1 and 1.\u00a0 <\/span>A value of 1 means the vectors are identical, 0 means they are orthogonal to each other (not similar), and a -1 means they are very different from each other, and other values are between one of the three.<\/p>\n

Euclidean Distance calculates the straight-line distance between each point in the vectors in Euclidean space (told you geometry would come into it).\u00a0 <\/span>The distance metric is actually based on the Pythagorean Theorem that you may remember from high school.\u00a0 <\/span>The output of this is a vector that is the same length as the document vectors and each entry is the distance between the corresponding points.\u00a0 <\/span>The smaller the distances, the more similar the documents are.<\/p>\n

While BoW is good for things like document similarity, it has several drawbacks when compared to other NLP techniques.\u00a0 <\/span>For one, since it just deals with statistical frequencies, it ignores things such as order of words and their context.\u00a0 <\/span>This means there is no real semantic information that is carried over.\u00a0 <\/span>The other drawback is that for large documents that are very different, the generated vectors can be largely empty and become cumbersome for distance computation algorithms.<\/p>\n

Term Frequency-Inverse Document Frequency<\/h2>\n

Term Frequency-Inverse Document Frequency<\/a> (TF-IDF) came about as an improvement on the BoW concept by weighing words based on importance in a document relative to a larger group of documents.\u00a0 <\/span>It attempts to identify significant words in a document while ignoring common words that frequently occur, such as the, and, but, and so on.<\/p>\n

To understand how it works, let us break down the various parts of how it works.\u00a0 <\/span>The first part is the Term Frequency<\/a> (TF).\u00a0 <\/span>As it sounds, this is a measure of how frequently a word appears in a document.\u00a0 <\/span>Thus words that occur more will have a higher score. \u00a0<\/span><\/p>\n

\"\"<\/a><\/p>\n

 <\/p>\n

 <\/p>\n

The next part of the calculation is the Inverse Document Frequency<\/a> (IDF).\u00a0 <\/span>This equation is a measure of how often a word occurs across the entire set of documents.\u00a0 <\/span>Words that do not appear often are assigned a higher score.<\/p>\n

\"\"<\/a><\/p>\n

 <\/p>\n

 <\/p>\n

Now we multiply the two values together to come up with the TF-IDF value.<\/p>\n

\"\"<\/a><\/p>\n

 <\/p>\n

 <\/p>\n

This value reflects how \u201cimportant\u201d a word is in a document relative to the total number of documents.\u00a0 <\/span>Word that occur often in one document but not in the total number of documents would end up with a high TF-IDF score.\u00a0 <\/span>This can be use to filter out the common words I mentioned above.<\/p>\n

TF-IDF also has several drawbacks when it comes to NLP.\u00a0 <\/span>For one, it still ignores word order and the context in which words are used.\u00a0 <\/span>As previously mentioned, word order and context are very important when attempting to determine the actual meaning of a word and how it is used.<\/p>\n

This leads into the next issue with TF-IDF.\u00a0 <\/span>Without context, it fails to account for words that mean the same thing.\u00a0 <\/span>Consider something like dog and puppy.\u00a0 <\/span>TF-IDF would treat them as different words instead of recognizing they are similar.<\/p>\n

N-Grams<\/h2>\n

N-Grams<\/a> were created to try to address the limitations of lack of word context.\u00a0 <\/span>They consider sequences of words to preserve word order versus looking solely at single words. \u00a0This consideration made N-Grams popular for modeling textual language and actual text generation.<\/p>\n

An N-Gram is defined as a contiguous sequence<\/a> of N items that are in text.\u00a0 <\/span>Consider the example sentence of \u201cThe cat sleeps on the chair\u201d.\u00a0 <\/span>A unigram (1-Gram) would be a single word such as \u201cThe\u201d and \u201ccat\u201d.\u00a0 <\/span>A bigram (2-Gram) is a sequence of two words, such as \u201cThe cat\u201d and \u201ccat sleeps\u201d.\u00a0 <\/span>A trigram (3-Gram) is then a sequence of three words, such as \u201cThe cat sleeps\u201d or \u201ccat sleeps on\u201d.\u00a0 <\/span>This continues on for larger numbers of N and counts the frequency that these sequences occur in a text.\u00a0 <\/span>As such, the higher the value of N, the more context is captured from the text.<\/p>\n

You might immediately see a problem with N-Grams.\u00a0 <\/span>As the value of N increases, the number of possible word sequences goes up nearly exponentially.\u00a0 <\/span>For example, a vocabulary of V<\/em> would have approximately VN<\/sup><\/em> N-Grams.\u00a0 <\/span>This makes the model much harder to train when there is a limited amount of text.\u00a0 <\/span>Higher values of N also can cause a smaller number of matches across documents.\u00a0 <\/span>N-Grams still fail to capture dependencies across sentences as they only capture localized context.<\/p>\n

Hidden Markov Models<\/h2>\n

Hidden Markov Models (HMMs) were used quite a bit (and periodically used today) for NLP tasks like part-of-speech tagging<\/a> and named entity recognition<\/a> (NER).\u00a0 <\/span>They are probability models that represent the sequence of hidden states that exist in systems that are based on observable events.<\/p>\n

A HMM consists of several parts:<\/p>\n