The bag-of-words model is a simplifying representation used in natural language processing and information
retrieval. In this model, a text is represented as the bag of its words, disregarding grammar
and even word order but keeping multiplicity. Recently, the bag-of-words model has also
been used for computer vision. The bag-of-words model is commonly used in
methods of document classification, where the occurrence of each word is used as a feature
for training a classifier. An early reference to "bag of words" in a
linguistic context can be found in Zellig Harris's 1954 article on Distributional Structure.
Example implementation The following models a text document using
bag-of-words. Here are two simple text documents:
Based on these two text documents, a dictionary is constructed as:
which has 10 distinct words. And using the indexes of the dictionary, each document is
represented by a 10-entry vector:
where each entry of the vectors refers to count of the corresponding entry in the dictionary.
For example, in the first vector, the first two entries are "1,2". The first entry corresponds
to the word "John" which is the first word in the dictionary, and its value is "1" because
"John" appears in the first document 1 time. Similarly, the second entry corresponds to
the word "likes" which is the second word in the dictionary, and its value is "2" because
"likes" appears in the first document 2 times. This vector representation does not preserve
the order of the words in the original sentences. This kind of representation has several successful
applications, for example email filtering. Term weighting
In the example above, the document vectors contain term frequencies. In both IR and text
classification, it is common to weigh terms by various schemes, the most popular of which
is tf–idf. For the specific purpose of classification, supervised alternatives have been developed
that take into account the class label of a document. Additionally, binary weighting
is used in place of frequencies for some problems. ...
Hashing trick A common alternative to the use of dictionaries
is the hashing trick, where words are directly mapped to indices with a hashing function.
By mapping words to indices directly with a hash function, no memory is required to
store a dictionary. Hash collisions are typically dealt with by using freed-up memory to increase
the number of hash buckets. In practice, hashing greatly simplifies the implementation of bag-of-words
models and improves their scalability. Example usage: spam filtering
In Bayesian spam filtering, an e-mail message is modeled as an unordered collection of words
selected from one of two probability distributions: one representing spam and one representing
legitimate e-mail. Imagine that there are two literal bags full of words. One bag is
filled with words found in spam messages, and the other bag is filled with words found
in legitimate e-mail. While any given word is likely to be found somewhere in both bags,
the "spam" bag will contain spam-related words such as "stock", "Viagra", and "buy" much
more frequently, while the "ham" bag will contain more words related to the user's friends
or workplace. To classify an e-mail message, the Bayesian
spam filter assumes that the message is a pile of words that has been poured out randomly
from one of the two bags, and uses Bayesian probability to determine which bag it is more
likely to be. See also
w-shingling n-gram
Vector space model Natural language processing
Additive smoothing Document classification
Machine learning Document-term matrix
Bag-of-words model in computer vision Hashing trick
MinHash Feature extraction
References ^ a b Sivic, Josef. "Efﬁcient visual search
of videos cast as text retrieval". "IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,
VOL. 31, NO. 4". IEEE. pp. 591–605. ^ Harris, Zellig. "Distributional Structure".
Word 10: 146–62. "And this stock of combinations of elements becomes a factor in the way later
choices are made ... for language is not merely a bag of words but a tool with particular
properties which have been fashioned in the course of its use"
^ Youngjoong Ko. "A study of term weighting schemes using class information for text classification".
"SIGIR'12". ACM. ^ Weinberger, K. Q.; Dasgupta A., Langford
J., Smola A., Attenberg, J.. "Feature hashing for large scale multitask learning,". Proceedings
of the 26th Annual International Conference on Machine Learning: 1113–1120.