Bag of Words

easyFREENLP FundamentalsMachine Learning 2

Build a Bag of Words (BoW) representation from a list of documents.

Build a vocabulary of unique words across all documents (sorted alphabetically)
For each document, create a vector where each element is the count of the corresponding vocabulary word

Words are split by spaces and converted to lowercase. Return the vocabulary list and the BoW matrix.

Example

Input

documents = ["the cat sat", "the dog sat", "the cat"]

Output

(['cat', 'dog', 'sat', 'the'], [[1, 0, 1, 1], [0, 1, 1, 1], [1, 0, 0, 1]])

Reasoning

Input: documents holds 3 sentences of space-separated words; case is ignored, so "The" and "the" are one word.
Vocabulary: the distinct words across all three documents are cat, dog, sat and the. In alphabetical order this gives ['cat', 'dog', 'sat', 'the'], so every document becomes a vector of length $V = 4$ , and position $j$ always means the same word.
Counting: entry $x_{ij}$ is how many times vocabulary word $j$ occurs in document $i$ . "the cat sat" has one cat, no dog, one sat, one the, giving [1, 0, 1, 1]. "the dog sat" gives [0, 1, 1, 1], and "the cat" has no sat, giving [1, 0, 0, 1].
Output: a tuple of the vocabulary and a $3 \times 4$ matrix (one row per document, one column per word).
Notice that each row sums to its document's length ( $3, 3, 2$ ), and that word order inside a document is lost: "sat cat the" would map to the same row. A repeated word counts more than once: "a a b" gives $2$ for a.

Constraints

documents: list of strings
Split on spaces, convert to lowercase
Vocabulary is sorted alphabetically
Return tuple (vocabulary, bow_matrix)
bow_matrix: 2D list (n_docs x vocab_size)

Learn this in

NLP FundamentalsML Study Plan

More from Machine Learning 2

Kernel PCAhard PCA via Covariance Matrixmedium Variance Explained Ratioeasy Feature Scalingeasy GAN Discriminator Losshard

Concept primer

Background Knowledge

The Bag of Words (BoW) model is a fundamental concept in Natural Language Processing (NLP), used for text representation. It represents a document as a bag, or a set, of its word occurrences, without considering grammar or word order. This model is based on a simple idea: a document is represented by a vector where each element in the vector corresponds to the frequency of a particular word in the document. The vocabulary is the set of unique words across all documents.

In the context of NLP, the BoW model is often used as a baseline for more complex text representation techniques, such as Term Frequency-Inverse Document Frequency (TF-IDF). The BoW model has its limitations, as it does not capture the semantic meaning of words or their relationships. However, it provides a simple and efficient way to represent text data, making it a useful tool for many NLP applications. The BoW model is also closely related to the concept of tokenization, which is the process of splitting text into individual words or tokens.

The mathematical representation of the BoW model can be thought of as a matrix, where each row represents a document, and each column represents a word in the vocabulary. The cell at row $i$ and column $j$ contains the frequency of word $j$ in document $i$ . This matrix is often referred to as the document-term matrix. The vocabulary list can be thought of as the column headers of this matrix, and the BoW matrix is the matrix itself.

Algorithm/Approach

The general approach to solving this problem involves the following steps:

Tokenize the documents into individual words
Build a vocabulary of unique words across all documents
Create a matrix where each row represents a document, and each column represents a word in the vocabulary
Populate the matrix with the frequency of each word in each document

This approach can be implemented using a variety of techniques, including the use of hash tables or dictionaries to store the vocabulary and the document-term matrix.

Step-by-Step Strategy

To implement the solution, follow these steps:

Tokenize the documents: Split each document into individual words, and convert them to lowercase.
Build the vocabulary: Create a set of unique words across all documents, and sort them alphabetically.
Create the document-term matrix: Initialize a matrix with the correct number of rows (documents) and columns (vocabulary words).
Populate the matrix: Iterate over each document, and for each word, increment the corresponding cell in the matrix.

Common Pitfalls

Some common pitfalls to watch out for include:

Not handling punctuation properly, which can lead to incorrect tokenization
Not converting words to lowercase, which can lead to duplicate words in the vocabulary
Not sorting the vocabulary alphabetically, which can lead to inconsistent results

Time & Space Complexity

The time complexity of this algorithm is $O(n \cdot m)$ , where $n$ is the number of documents, and $m$ is the average number of words per document. The space complexity is also $O(n \cdot m)$ , as we need to store the document-term matrix. The vocabulary list has a space complexity of $O(v)$ , where $v$ is the number of unique words across all documents.

solution.py

Python 3.13

Test results