Part 7: Mastering NLP Word Embeddings – A Deep Dive into Co-Occurrence Matrices
Introduction
Welcome back to our multi-part guide on mastering Natural Language Processing (NLP) word embeddings! In the previous parts, we covered fundamental concepts like distributional similarity and various word embedding techniques.
In part 7, we‘ll take a deep dive into co-occurrence matrices – a powerful yet intuitive method for capturing semantic and syntactic relationships between words. We‘ll cover the mathematical details of constructing co-occurrence matrices, analyze their strengths and weaknesses, and see how they can be used to generate useful dense vector representations of words. Strap in as we continue our journey to becoming word embedding experts!
A Quick Refresher on Distributional Similarity
Before we jump into co-occurrence matrices, let‘s briefly review the key idea that underlies many word embedding techniques – distributional similarity. In a nutshell, it‘s the hypothesis that words that occur in similar contexts tend to have similar meanings. So by analyzing the company a word keeps – its neighboring words in a large body of text – we can infer a lot about the word‘s meaning and relationship to other words.
Methods like co-occurrence matrices operationalize this powerful intuition by capturing and quantifying the context words tend to share. They enable us to go from analyzing unstructured text data to generating structured, mathematically convenient representations of words‘ relationships. With that quick refresher out of the way, let‘s unpack exactly what co-occurrence matrices are and how they work.
Co-Occurrence Matrices: Capturing Word Relationships
A co-occurrence matrix is a way of representing how often words occur together (or "co-occur") within a certain proximity in a text. Imagine we have the following toy corpus:
The quick brown fox jumped over the lazy dog. The lazy dog slept all day long.
To construct a co-occurrence matrix, we first define a context window – let‘s say 5 words before and after each word. For the word "dog", its context words in the first sentence would be: "jumped", "over", "the", "lazy". In the second sentence, its context is: "lazy", "slept", "all", "day", "long".
We can now build a matrix where each row represents a unique word in our vocabulary, each column also represents a word, and the value at row i, column j is the number of times word i occurred in the context of word j. If we set the context window to be the entire corpus, we get a symmetric matrix, since if word i co-occurs with word j, the reverse is also true. Here‘s a snippet of what our matrix M might look like:
| the | quick | brown | … | dog | |
|---|---|---|---|---|---|
| the | – | 1 | 1 | … | 2 |
| quick | 1 | – | 1 | … | 0 |
| brown | 1 | 1 | – | … | 0 |
| … | … | … | … | … | … |
| dog | 2 | 0 | 0 | … | – |
The co-occurrence matrix is a square matrix whose size is the number of unique words (our vocabulary size V). Each cell Mij contains the number of times word i co-occurs with word j within the specified context window, across the entire corpus.
Intuitively, you can think of each row in M as a representation of a word in terms of its context – which other words it tends to hang out with. Words that are semantically and syntactically similar tend to have similar contexts, and that‘s precisely the kind of information the co-occurrence matrix captures and allows us to leverage!
Variations on the Co-Occurrence Matrix
The example above used a symmetric co-occurrence matrix with a fixed-size context window. But there are many variations we can apply:
-
Context window size: Smaller windows tend to emphasize syntactic relationships (like verb-object), while larger windows capture more semantic or topical similarity (like "dog" and "bone"). Typical sizes range from 4 to 10 words on each side.
-
Symmetric vs asymmetric: We can choose to distinguish between words that occur before vs after the target word, resulting in an asymmetric matrix. This may capture useful directional relationships but also increases dimensionality.
-
Weighted co-occurrence: Instead of a simple count, each co-occurrence can be weighted based on factors like the distance between words (e.g. decaying weight for more distant words) or their pointwise mutual information (PMI).
-
Dynamic context window: Instead of a fixed window size, the context can be defined by punctuation marks, sentence boundaries or other delimiters that better capture the relevant context of a word. This leads to variable-sized context windows.
The choice of these hyperparameters allows us to tune the co-occurrence matrix to capture the most salient and informative relationships between words for a given task. However, regardless of these variations, the core idea remains the same – the co-occurrence matrix is a systematic way to capture and quantify the contextual similarity between words in a corpus.
Constructing the Co-Occurrence Matrix
Now that we have an intuitive understanding of co-occurrence matrices, let‘s dive into the mathematics of actually constructing one. We‘ll assume a symmetric matrix with fixed context window of size n for simplicity.
Given a tokenized corpus with N total words, we‘ll store the unique words (our vocabulary) in a list W and construct a V x V matrix M, where V = len(W) is the vocabulary size. We pad each sentence in the corpus with n dummy words on each end.
Then, for each word w_i in the corpus, we:
- Find its index i in the vocabulary W
- Get the indices of the 2n context words surrounding w_i (excluding w_i itself)
- For each context word w_j with index j, increment M[i,j] by 1
In Python, it looks something like this:
def build_cooc_matrix(corpus, n):
vocab = list(set(corpus))
V = len(vocab)
M = np.zeros((V, V))
for i in range(n, len(corpus)-n):
w_i = corpus[i]
i0 = vocab.index(w_i)
context = corpus[i-n:i] + corpus[i+1:i+n+1]
for w_j in context:
j0 = vocab.index(w_j)
M[i0,j0] += 1
M[j0,i0] += 1
return M, vocab
The resulting M is our co-occurrence matrix – a square matrix of size V x V where each cell M[i,j] contains the number of times words w_i and w_j co-occurred within a context window of size n across the corpus.
The diagonal entries M[i,i] are all zero since we don‘t count a word co-occurring with itself. And if M is symmetric, we have M[i,j] = M[j,i] for all i,j, so we only really need to compute the upper (or lower) triangular portion of the matrix.
From Co-Occurrence to Word Embeddings
The co-occurrence matrix M captures rich information about the relationships between words in our corpus. But there are a few challenges with using M directly as word representations:
- M is very high-dimensional (V x V), which makes storage, computation, and learning from it challenging, especially for large vocabularies.
- M is very sparse, since most words only co-occur with a small fraction of the total vocabulary. This sparsity makes it harder to uncover generalizable patterns.
- The raw counts in M don‘t account for the global frequency of words. Very frequent words like "the" will have high counts with many words, but that doesn‘t necessarily imply a strong semantic relationship.
To address these issues, the typical approach is to factorize M to obtain lower-dimensional, dense word vectors. A popular factorization method is Singular Value Decomposition (SVD), which decomposes M into the product of three matrices:
M = U Σ VT
Where U and V are orthogonal matrices of size V x V whose columns are the left and right singular vectors of M, and Σ is a diagonal matrix of singular values. By truncating U to the first D < V columns, we obtain word embeddings of size D that capture the most salient information in M:
W = U:,:D
Each row W[i,:] is a D-dimensional dense vector representation of word w_i that encodes information about which other words it tends to co-occur with. The choice of D (typically in the range of 50-1000) controls the granularity of the representations.
SVD can be seen as a form of dimensionality reduction that projects the high-dimensional rows of M into a lower-dimensional latent space, while preserving the most important co-occurrence patterns. The resulting embeddings W capture the distributional similarity between words in a compact, computationally convenient format.
Here‘s a snippet of Python code to compute SVD embeddings from a co-occurrence matrix M:
from scipy.linalg import svd
U, S, Vt = svd(M)
W = U[:,:D]
The resulting matrix W has size V x D, where each row W[i,:] is a D-dimensional embedding for the i-th word in our vocabulary. We can now use these embeddings as input features for a variety of downstream NLP tasks, like text classification, clustering, or similarity analysis.
Pros and Cons of Co-Occurrence Embeddings
Co-occurrence based word embeddings have several attractive properties:
-
Interpretability: Unlike some other embedding methods (e.g. neural word embeddings), the dimensions of co-occurrence embeddings have a clear interpretation as context words. This makes it easier to understand and debug the model.
-
Efficiency: Constructing the co-occurrence matrix and factorizing it with SVD is computationally efficient and can be easily parallelized. The embeddings can be precomputed once and reused.
-
Scalability: Co-occurrence based methods can handle very large vocabularies (millions of words) and corpora (billions of tokens). The memory footprint can be controlled by adjusting the embedding dimensionality D.
However, there are also some limitations:
-
Fixed vocabulary: The vocabulary and embeddings are fixed based on the training corpus. Embeddings for new or rare words not seen during training are difficult to obtain.
-
Lack of context: The embeddings don‘t account for the specific context and meaning of a word in a given sentence. Each word has a single global representation regardless of its local usage.
-
Hyperparameter sensitivity: The performance of co-occurrence embeddings depends heavily on the choice of context window size, weighting scheme, factorization method, and embedding dimensionality. These hyperparameters need to be carefully tuned.
-
Limited semantics: While co-occurrence captures distributional similarity, it may not fully capture the rich semantic relationships between words, like synonymy, antonymy, hypernymy, etc.
Despite these limitations, co-occurrence based embeddings are a powerful and widely used tool in the NLP practitioner‘s toolkit. They strike a good balance between simplicity, efficiency and performance for many tasks.
Modern Developments and Alternatives
While classic co-occurrence based methods like SVD remain popular, there have been many advancements in word embedding techniques in recent years. Some notable developments include:
-
Word2Vec: A family of neural network based embedding models, including Continuous Bag of Words (CBOW) and Skip-gram, that learn embeddings by predicting a word from its context (CBOW) or vice versa (Skip-gram). These models are more computationally efficient than SVD and can learn from larger unlabeled corpora.
-
GloVe: Global Vectors for word representation, which learns embeddings by factorizing the log of the co-occurrence matrix, scaled by a context-dependent weighting factor. GloVe combines the benefits of global matrix factorization with local context window methods.
-
FastText: An extension of Word2Vec that learns embeddings for character n-grams, allowing it to better handle rare and out-of-vocabulary words. FastText can generate embeddings for words not seen during training by summing the n-gram embeddings.
-
Contextualized embeddings: More recent models like ELMo, BERT, and GPT learn word representations that vary based on the specific context in which a word appears. These models use deep neural networks (e.g. Transformers) to generate dynamic, context-sensitive embeddings that can better capture the nuances of language.
Despite these advancements, co-occurrence based embeddings remain a fundamental building block and a strong baseline for many NLP tasks. Understanding the intuition and mechanics behind them is essential for any NLP practitioner.
Conclusion and Further Reading
In this deep dive, we explored the world of co-occurrence matrices and how they can be used to generate useful word embeddings. We saw how the distributional similarity hypothesis motivates the use of context to represent the meaning of words, and how co-occurrence matrices operationalize this idea by capturing the frequency with which words appear together in a certain context.
We discussed different variations of co-occurrence matrices, and dove into the mathematical details of constructing them from a tokenized corpus. We then saw how techniques like SVD can be used to factorize the co-occurrence matrix and generate lower-dimensional dense vector embeddings that encapsulate the most salient word relationship patterns.
We analyzed the strengths and limitations of co-occurrence based embeddings, and briefly surveyed some modern alternatives and developments in word representation learning.
To learn more about word embeddings and NLP, check out these resources:
- CS224n: Natural Language Processing with Deep Learning (Stanford Course)
- GloVe: Global Vectors for Word Representation (Paper)
- Efficient Estimation of Word Representations in Vector Space (Word2Vec Paper)
- Enriching Word Vectors with Subword Information (FastText Paper)
- Deep Contextualized Word Representations (ELMo Paper)
I hope this guide has given you a deeper understanding and appreciation of co-occurrence based word embeddings. Keep an eye out for the next part in this series, where we‘ll dive into more advanced embedding techniques. Happy learning!
