Bag-of-words

1.1 Definition and Basic Concept

The bag-of-words (BoW) model is a simplifying representation used in natural language processing (NLP) and information retrieval. In this model, a text (such as a sentence or a document) is represented as an unordered collection of words, disregarding grammar and word order but keeping multiplicity. It is commonly used for feature extraction in text classification, clustering, and search. The model’s key assumption—that word frequencies alone carry sufficient meaning—makes it computationally efficient, though it loses semantic context and syntactic relationships.

1.2 Historical Context

1.2.1 Origins in Information Retrieval

The concept of representing documents by word counts dates to early information retrieval systems of the mid‑20th century. Researchers such as Hans Peter Luhn and Calvin Mooers proposed using term frequency as a basis for indexing and searching. The bag-of-words model emerged as a practical way to convert free text into numerical vectors that could be compared and ranked.

1.2.2 Adoption in Machine Learning

With the rise of machine learning in the 1990s, bag-of-words became a standard feature extraction method for text classification. Algorithms such as Naive Bayes and support vector machines (SVMs) relied on BoW vectors to process textual data. The model’s simplicity and effectiveness contributed to its widespread adoption before the advent of dense vector representations.

2.1 Vocabulary Construction

The first step in building a bag-of-words representation is to define a vocabulary—a set of unique terms that appear in the corpus. Each document is then represented by counting how many times each vocabulary term occurs. The size of the vocabulary determines the dimensionality of the resulting vectors.

2.2 Document-Term Matrix

A document-term matrix (DTM) is a two‑dimensional array where rows correspond to documents and columns to vocabulary terms. Each cell contains a value representing the occurrence of that term in that document. The DTM is typically sparse, as most terms appear in only a few documents.

2.2.1 Term Frequency (TF) Representation

In the basic TF representation, each cell contains the raw count of how many times the term appears in the document. For example, if the word “cat” appears three times in document five, the entry at row five, column “cat” is 3.

2.2.2 Binary (Presence/Absence) Representation

An alternative to raw counts is binary representation, where each cell is 1 if the term appears at least once in the document and 0 otherwise. This approach disregards multiplicity and is used when only the presence or absence of a term is considered informative.

2.3 Vectorization Process

2.3.1 Tokenization

Tokenization splits a text into individual words or tokens, typically by whitespace and punctuation. The resulting tokens are the basic units for building the vocabulary and counting frequencies.

2.3.2 Stemming and Lemmatization

Stemming reduces words to their root form by removing affixes (e.g., “running” → “run”). Lemmatization uses a dictionary to map words to their base form (e.g., “better” → “good”). Both techniques aim to consolidate variant forms of the same word, reducing vocabulary size and improving generalization.

2.3.3 Stop Word Removal

Stop words are common words (e.g., “the”, “and”, “is”) that are often removed before vectorization because they carry little discriminative information. Their removal reduces dimensionality and noise, though in some contexts they may be retained for specific tasks.

3.1 Term Frequency–Inverse Document Frequency (TF-IDF)

3.1.1 Mathematical Definition

TF‑IDF is a numerical statistic that reflects how important a word is to a document in a corpus. It is calculated as the product of term frequency (TF) and inverse document frequency (IDF). A common variant uses tf(t,d) * log(N / df(t)), where tf(t,d) is the raw count of term t in document d, N is the total number of documents, and df(t) is the number of documents containing t.

3.1.2 Practical Significance

TF‑IDF downweights terms that appear frequently across many documents (e.g., “the”) and upweights terms that appear in only a few documents, thereby emphasizing distinctive words. It is widely used in information retrieval and text mining for ranking and feature selection.

3.2 Other Weighting Methods

3.2.1 Log-Normalized Frequency

Log normalization applies a logarithmic transformation to raw term frequencies: log(1 + tf(t,d)). This reduces the impact of very frequent terms and is often combined with IDF.

3.2.2 Binary Frequency with IDF

In this scheme, the term frequency component is replaced by a binary indicator (1 if present, 0 otherwise), and the weight becomes 1 * IDF(t). It is useful when only the presence of a term is relevant, and multiple occurrences are not considered meaningful.

4.1 Text Classification

4.1.1 Spam Detection

Bag-of-words features are used to train classifiers that distinguish spam emails from legitimate ones. Common spam‑related words (e.g., “free”, “win”) become strong indicators. The model’s efficiency allows processing of large email corpora.

4.1.2 Sentiment Analysis

In sentiment analysis, BoW vectors capture the frequency of positive and negative words in a review or social media post. Despite ignoring word order, the model has been successfully applied to polarity classification (e.g., positive vs. negative).

4.2 Document Clustering

4.2.1 Topic Modeling with Latent Dirichlet Allocation (LDA)

LDA is a generative probabilistic model that uses bag-of-words as its input. Each document is treated as a mixture of topics, and each topic as a distribution over words. BoW’s lack of order aligns with LDA’s exchangeability assumption (the “bag‑of‑words” assumption).

4.3 Information Retrieval

4.3.1 Search Engine Indexing

Early search engines built inverted indexes from bag-of-words representations. For each term, the index stores a list of documents containing that term, enabling fast retrieval of documents matching a query.

4.3.2 Relevance Ranking

Ranking functions such as Okapi BM25 and vector space model similarity compute relevance scores between a query and a document using term‑weighted vectors derived from BoW.

5.1 N-Gram Representation

5.1.1 Unigrams, Bigrams, Trigrams

Instead of single words, n‑grams are contiguous sequences of n tokens. Bigrams (n=2) and trigrams (n=3) capture local word order (e.g., “not good”). This extension partly addresses the loss of word order while maintaining the bag‑of‑words framework.

5.2 Weighted Bag-of-Words

Weighted BoW assigns different importance to different words based on external knowledge, such as part‑of‑speech tags or domain‑specific dictionaries. For example, nouns may receive higher weight than adjectives in some tasks.

5.3 Hashing Trick (Feature Hashing)

5.3.1 Collision Handling

Feature hashing maps each word to a fixed‑length vector via a hash function, avoiding the need to store a vocabulary. Collisions (different words mapping to the same hash bucket) are handled by summing their counts, which may introduce noise but reduces memory requirements.

6.1 Loss of Word Order and Syntax

BoW ignores the sequence of words, so phrases like “not good” and “good not” are treated identically. This makes the model insensitive to negation, adjective‑noun order, and grammatical relationships, severely limiting its ability to capture meaning.

6.2 Semantic Sparsity

The resulting vectors are high‑dimensional and sparse, with most entries being zero. This sparsity can hinder the performance of machine learning algorithms that rely on dense, low‑dimensional representations.

6.3 High Dimensionality

A corpus vocabulary often contains tens of thousands of unique terms. Models trained on such high‑dimensional vectors are prone to overfitting and require large amounts of data and regularization.

6.4 Handling of Polysemy and Synonymy

BoW cannot distinguish between different senses of a polysemous word (e.g., “bank” as a financial institution vs. a river bank) and treats synonyms (e.g., “car” and “automobile”) as completely unrelated terms. This leads to poor semantic matching.

7.1 Word Embeddings (Word2Vec, GloVe)

Word embeddings are dense, low‑dimensional vectors learned from large corpora that capture semantic similarities through distributional context. Unlike BoW, they can represent analogies and handle synonymy, but they are more computationally intensive to train and require more memory for inference.

7.2 Transformer-Based Models (BERT)

Transformer models like BERT produce contextualized embeddings that consider the entire input sequence, capturing word order and disambiguating polysemy. They outperform BoW on nearly all NLP benchmarks but are orders of magnitude slower and resource‑hungry.

7.3 Sequence Models (RNN, LSTM)

Recurrent neural networks process text sequentially, preserving word order over a sliding window of context. They can model long‑range dependencies but are slower to train than BoW and require more data for effective generalization.

8.1 Memory Usage

A BoW document-term matrix can be very large in memory if stored as a dense array. For a corpus with 1 million documents and 100,000 vocabulary terms, a dense matrix would require 100 billion entries. However, the matrix is extremely sparse.

8.2 Efficient Sparse Matrix Storage

Sparse matrix formats (e.g., compressed sparse row, list of lists) store only non‑zero entries, drastically reducing memory usage. Libraries such as SciPy and scikit‑learn provide efficient sparse structures for BoW vectors.

8.3 Scalability for Large Corpora

BoW scales linearly with the size of the corpus and vocabulary. Its simplicity enables distributed processing (e.g., MapReduce) and streaming updates, making it suitable for very large datasets such as web‑scale collections.

9.1 Bag-of-Concept Models

Instead of raw words, bag‑of‑concept models use higher‑level semantic units such as named entities, topics, or WordNet synsets. This reduces the impact of synonymy and polysemy while retaining the bag‑of‑words framework.

9.2 Multimodal Bag-of-Words (Visual Words)

In computer vision, the bag‑of‑visual‑words model represents images by quantizing local image features (e.g., SIFT descriptors) into a visual vocabulary. This parallels the textual BoW and is used for image classification and retrieval.

9.3 Dynamic Bag-of-Words for Streaming Data

Dynamic or sliding‑window BoW maintains word frequency counts over time for streaming text data. This variant is used in online topic detection and real‑time sentiment monitoring, adapting to evolving vocabularies without full retraining.

10.1 Vector Space Model

The vector space model represents documents and queries as vectors in a high‑dimensional space, with similarity measured by cosine distance. BoW is the most common way to construct these vectors.

10.2 Feature Extraction

Feature extraction is the process of transforming raw data into numerical features for machine learning. BoW is a classic text feature extraction method, often compared with term frequency‑based and embedding‑based approaches.

10.3 Natural Language Processing

Natural language processing (NLP) is the broader field of computer science and artificial intelligence concerned with the interaction between computers and human language. BoW is one of many techniques used within NLP for text representation.