📘

Bag of Words

EasyNLP Fundamentals 📚 Machine 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:

The vocabulary is built by splitting each document into words, converting them to lowercase, and combining the results into a sorted list of unique words: ['cat', 'dog', 'sat', 'the'].
For each document, a vector is created where each element is the count of the corresponding vocabulary word. For the first document "the cat sat", this results in [1, 0, 1, 1] because it contains one 'cat', zero 'dog', one 'sat', and one 'the'.
The same process is applied to the remaining documents: the second document "the dog sat" becomes [0, 1, 1, 1], and the third document "the cat" becomes [1, 0, 0, 1].
The final output is a tuple containing the vocabulary list and the Bag of Words matrix: (['cat', 'dog', 'sat', 'the'], [[1, 0, 1, 1], [0, 1, 1, 1], [1, 0, 0, 1]]).

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)

More from Machine Learning 2

Kernel PCAHard PCA via Covariance MatrixMedium Variance Explained RatioEasy Feature ScalingEasy GAN Discriminator LossHard

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

0/0

Run code to see test results.