Lecture
The bag-of-words model is a simplified representation used in natural language processing and information retrieval (IR). In this model, a text (for example, a sentence or a document) is represented as a bag (multiset) of its words, disregarding grammar and even word order, but keeping multiplicity . The bag-of-words model has also been used for computer vision .
The bag-of-words model is commonly used in document classification methods, where the (frequency of) occurrence of each word is used as a feature for training a classifier .
An early mention of «bag of words» in a linguistic context can be found in Zellig Harris's 1954 article on distributional structure .
The bag-of-words model is a way of representing text data when modeling text with machine learning algorithms.
The «bag of words» model is simple to understand and implement and has had great success in problems such as language modeling and document classification.
In this tutorial you will discover the bag-of-words model for feature extraction in natural language processing.
After completing this tutorial, you will know:
The problem with modeling text is that it is messy, and techniques such as machine learning algorithms prefer well-defined, fixed-length inputs and outputs.
Machine learning algorithms cannot work with raw text directly; the text must be converted into numbers. Specifically, vectors of numbers.
In language processing, vectors x are extracted from textual data, to reflect various linguistic properties of the text.
- Page 65,Neural Network Methods in Natural Language Processing, 2017
This is called feature extraction, or feature encoding.
A popular and simple method of extracting features from text data is called the bag-of-words model of text.
The bag-of-words model, or BoW for short, is a way of extracting features from text for use in modeling, such as in machine learning algorithms.
The approach is very simple and flexible, and can be used in a multitude of ways for extracting features from documents.
A bag of words is a representation of text that describes the occurrence of words within a document. It involves two things:
It is called a «bag of words, because any information about the order or structure of words in the document is discarded. The model is only concerned with whether known words occur in the document, not where in the document.
A very common feature extraction procedure for sentences and documents is the «bag of words» (BOW) approach. In this approach, we look at the histogram of words in the text, that is, we consider each word as a feature.
- Page 69,Neural Network Methods in Natural Language Processing, 2017
The intuition is that documents are similar if they have similar content. Further, that from the content alone we can learn something about the meaning of the document.
A bag of words can be as simple or complex as you like. The complexity lies both in deciding how to design the vocabulary of known words (or tokens), and how to score the presence of known words.
We will look at both of these concerns in more detail.
Let's make the bag-of-words model concrete with a worked example.
Below is a snippet of the first few lines of text from the book «A Tale of Two Cities» by Charles Dickens, taken from Project Gutenberg.
It was the best of times,
it was the worst of times,
it was the age of wisdom,
it was the age of foolishness,
For this small example, let's treat each line as a separate «document», and the 4 lines as our entire corpus of documents.
Now we can make a list of all of the words in our model vocabulary.
The unique words here (ignoring case and punctuation) are:
That is a vocabulary of 10 words from a corpus containing 24 words.
The next step is to score the words in each document.
The objective is to turn each document of free text into a vector that we can use as input or output for a machine learning model.
Because we know the vocabulary has 10 words, we can use a fixed-length document representation of 10, with one position in the vector to score each word.
The simplest scoring method is to mark the presence of words as a boolean value, 0 for absent, 1 for present.
Using the arbitrary ordering of words listed above in our vocabulary, we can step through the first document ("It was the best of times") and convert it into a binary vector
The scoring of the document would look as follows:
As a binary vector, this would look as follows:
[1, 1, 1, 1, 1, 1, 0, 0, 0, 0]
The other three documents would look as follows:
"it was the worst of times" = [1, 1, 1, 0, 1, 1, 1, 0, 0, 0] "it was the age of wisdom" = [1, 1, 1, 0, 1, 0, 0, 1, 1, 0] "it was the age of foolishness" = [1, 1, 1, 0, 1, 0, 0, 1, 0, 1]
All ordering of the words is nominally discarded, and we have a consistent way of extracting features from any document in our corpus, ready for use in modeling.
New documents that overlap with the vocabulary of known words, but may contain words outside of the vocabulary, can still be encoded, where only the occurrence of known words is scored and unknown words are ignored.
You can see how this might naturally scale to large vocabularies and larger documents.
The following models a text document using bag-of-words. Here are two simple text documents:
(1) John likes to watch movies. Mary likes movies too.
(2) Mary also likes to watch football games.
Based on these two text documents, a list is constructed for each document as follows:
"John" , "likes" , "to" , "watch" , "movies" , "Mary" , "likes" , "movies" , "too" «Mary» , «also» , «likes» , «to» , «watch» , «football» , games»
Representing each bag of words as a JSON object and assigning it to a corresponding JavaScript variable :
BoW1 = { "John" : 1 , "likes" : 2 , " to " : 1 , "watch" : 1 , "movies" : 2 , "Mary" : 1 , "too" : 1 };
BoW2 = { "Mary" : 1 , "also" : 1 , "likes" : 1 , " to " : 1 , "watch" :: 1 , «games» : 1 };
Each key is a word, and each value is the count of occurrences of that word in the given text document.
The order of elements is free, so, for example {"too":1,"Mary":1,"movies":2,"John":1,"watch":1,"likes":2,"to":1}, is also equivalent to BoW1 . This is what we would expect from the strict representation of a JSON object .
Note: if another document is like the union of these two,
(3) John likes to watch movies. Mary likes movies too. Also Mary likes to watch football games.
its representation in JavaScript would be:
BoW3 = { "John" : 1 , "likes" : 3 , " to " : 2 , "watch" : 2 , "movies" : 2 , "Mary" : 2 , "too" : 1 , "also" : 1 , "football" : 1 , "games" : 1 };
So, as we see in bag algebra , the «union» of two documents in the bag-of-words representation is formally a disjoint union , summing the multiplicities of each element.
.
As the vocabulary size increases, so does the vector representation of documents.
In the previous example, the length of the document vector equals the number of known words.
You can imagine that for a very large corpus, such as thousands of books, the length of the vector might be thousands or millions of positions. Furthermore, each document may contain very few of the known words in the vocabulary.
This results in a vector with lots of zero scores, called a sparse vector or sparse representation.
Sparse vectors require more memory and computational resources when modeling, and the vast number of positions or dimensions can make the modeling process very challenging for traditional algorithms.
As such, there is pressure to decrease the size of the vocabulary when using a bag-of-words model.
There are simple text cleaning techniques that can be used as a first step, such as:
A more sophisticated approach is to create a vocabulary of grouped words. This both changes the scope of the vocabulary and allows the bag of words to capture a little bit more meaning from the document.
In this approach, each word or token is called a «gram». Creating a vocabulary of two-word pairs is, in turn, called a bigram model. Again, only the bigrams that appear in the corpus are modeled, not all possible bigrams.
An n-gram is a sequence of N tokens (words): a 2-gram (more commonly called a bigram) is a two-word sequence of words, such as «please turn», «turn your», or «your homework», and a 3-gram (more commonly called a trigram) is a three-word sequence of words, such as «please turn your», or «turn your homework».
- page 85,Speech and Language Processing, 2009.
For example, the bigrams in the first line of text from the previous section: «It was the best of times»:
Then the vocabulary tracks triplets of words, this is called a trigram model, and the general approach is called the n-gram model, where n refers to the number of grouped words.
Often a simple bigram approach is better than a 1-gram bag-of-words model for tasks like documentation classification.
bag-of-bigrams representation is much more powerful than bag-of-words, and in many cases proves very hard to beat.
- page 75,Neural Network Methods in Natural Language Processing, 2017
Once a vocabulary has been chosen, the occurrence of words in example documents needs to be scored.
In the worked example, we have already seen one very simple approach to scoring: a binary scoring of the presence or absence of words.
Some additional simple scoring methods include:
You may remember from computer science that a hash function is a bit of math that maps data to a fixed-size set of numbers.
For example, we use them in hash tables for programming, where perhaps names are converted to numbers for fast lookups.
We can use a hash representation of known words in our vocabulary. This addresses the problem of having a very large vocabulary for a large text corpus because we can choose the size of the hash space, which is, in turn, the size of the vector representation of the document.
Words are hashed deterministically to the same integer index in the target hash space. A binary score or count can then be used to score the word.
This is called the «hash trick" or "feature hashing».
The challenge is to choose a hash space to accommodate the chosen vocabulary size to minimize the probability of collisions and trade-offs.
A problem with scoring word frequency is that highly frequent words start to dominate in the document (e.g. larger score), but may not contain as much «informational content» to the model as rarer, but perhaps domain-specific words.
One approach is to rescale the frequency of words by how often they appear in all documents, so that the scores for frequent words like «the» that are also frequent across all documents are penalized.
This approach to scoring is called Term Frequency - Inverse Document Frequency, or TF-IDF for short, where:
Scores are weights in which not all words are equally important or interesting.
Scores have the effect of highlighting words that are distinctive (contain useful information) in a given document.
Thus, the idf of a rare term is high, whereas the idf of a frequent term is likely to be low.
– page 118, Introduction to Information Retrieval, 2008.
The bag-of-words model is very simple to understand and implement and offers a great deal of flexibility for customizing it to your specific text data.
It has been used with great success for prediction tasks such as language modeling and document classification.
Nevertheless, it suffers from several drawbacks, such as:
In practice, the bag-of-words model is mainly used as a tool for feature generation. After transforming the text into a «bag of words», we can calculate various measures to characterize the text. The most common type of characteristics, or features, calculated from the bag-of-words model is term frequency, namely, the number of times a term appears in the text. In the example above, we can construct the following two lists to record the term frequencies of all the distinct words (BoW1 and BoW2, ordered as in BoW3):
( 1 ) [ 1 , 2 , 1 , 1 , 2 , 1 , 1 , 0 , 0 , 0 ] ( 2 ) [ 0 , 1 , 1 , 1 , 0 , 1 , 0 , 1 , 1 , 1 ]
Each entry in the lists refers to the count of the corresponding entry in the list (this is also a histogram representation). For example, in the first list (which represents document 1), the first two entries are «1,2»:
This list (or vector) representation does not preserve the order of the words in the original sentences. This is merely the main feature of the «bag of words» model. Such a representation has had several successful applications, such as email filtering.
However, term frequency is not necessarily the best representation for the text. Common words such as «the», «a», «to» are almost always the terms that occur most frequently in the text. Thus, having a high raw count does not necessarily mean that the corresponding word is more important. To address this problem, one of the most popular ways to «normalize» the term frequencies is to weight a term by the inverse of its document frequency, or tf–idf. Additionally, for the specific purpose of classification, supervised alternatives have been developed to take the document's class label into account. Finally, for some tasks binary (presence/absence, or 1/0) weighting is used instead of frequencies (for example, in a machine learning software system).
The bag-of-words model is an orderless representation of the document — only the count of the words matters. For example, in the example above «John likes to watch movies. Mary likes movies too», the bag of words does not show that the verb «likes» always follows a person's name in this text. As an alternative, the n-gram model can store this spatial information. Applied to the same example above, a bigram model will parse the text into the following units and store the term frequency of each unit, as before.
[
«John likes» ,
«likes to» ,
«to watch» ,
«watch movies» ,
«Mary likes» ,
«likes movies» ,
«movies too» ,
]
Conceptually, we can view the bag-of-words model as a special case of the n-gram model with n = 1. For n>1 the model is called w-shingling (where w is equivalent to n, denoting the number of grouped words). See the language model for a more detailed discussion.
A common alternative to using a dictionary is the hashing trick, in which words are mapped directly to indices by means of a hashing function. Thus, no memory is required to store the dictionary. Hash collisions are typically resolved by freeing up memory to increase the number of hash buckets. In practice, hashing simplifies the implementation of bag-of-words models and improves scalability.
In Bayesian spam filtering, an email message is modeled as an unordered collection of words drawn from one of two probability distributions: one represents spam, and the other represents legitimate email («ham»). Imagine there are two literal bags filled with words. One bag is filled with words found in spam messages, and the other with words found in legitimate email messages. While any given word is probably found in both bags somewhere, the «spam» bag will contain words related to spam, such as «stock», «Viagra», and «buy», significantly more often, while the «ham» bag will contain more words related to the user's friends or work.
To classify an email message, the Bayesian spam filter assumes that the message is a pile of words that was randomly poured out of one of the two bags, and uses Bayesian probability to determine which bag it is more likely to be from.
Comments