Latent Semantic Analysis (LSA) [1] analyzes relationships between a set of documents and the terms they contain. It is based on the idea that words that are used in similar contexts tend to have similar meanings, which is in line with the distributional hypothesis.
Document-Term Matrix
LSA starts with a matrix representation of the documents in a corpus and the terms (words) they contain. This matrix, known as the document-term matrix, has documents as rows and terms as columns, with each cell representing the frequency of a term in a document.
Let us define a function that reads a corpus, and returns a list of all documents in the corpus and a dictionary whose keys and values are terms and their unique indices, respectively:
We then define a function that takes and , and returns the document-term matrix such that indicates the frequency of the 'th term in within the 'th document:
L1: The package.
L3:
Let us create a document-term matrix from the corpus, :
L1: .
L3:
With this current implementation, it takes over 17 seconds to create the document-term matrix, which is unacceptably slow given the small size of the corpus. Let us improve this function by first creating a 2D matrix in NumPy and then updating the frequency values:
Using this updated function, we see a noticeable enhancement in speed, about 0.5 seconds, to create the document-term matrix:
The 'th row of is considered the document vector of the 'th document in the corpus, while the transpose of 'th column of is considered the term vector of the 'th term in the vocabulary.
Q3: Why is the performance of document_term_matrix() significantly slower than document_term_matrix_np()?
Dimensionality Reduction
LSA applies Singular Value Decomposition (SVD) [2] to decompose the document-term matrix into three matrices, , , and , where are orthogonal matrices and is a diagonal matrix containing singular values, such that .
An is a square matrix whose rows and columns are orthogonal such that , where is the identity matrix.
are non-negative values listed in decreasing order that represent the importance of each topic.
For simplicity, let us create a document-term matrix from a small corpus consisting of only eight documents and apply SVD to it:
L3:
L4:
This results , , and such that:
In , each row represents a document and each column represent a topic.
In , each diagonal cell represents the weight of the corresponding topic.
In , each column represents a term and each row represents a topic.
The last two singular values in are actually non-negative values, and , respectively.
The first four singular values in appear to be sufficiently larger than the others; thus, let us reduce their dimensions to such that , , and :
Q4: What is the maximum number of topics that LSA can identify? What are the limitations associated with discovering topics using this approach?
Document Embedding
Given the LSA results, an embedding of the 'th document can be obtained as :
From the output, although interpreting the meaning of the first topic (column) is challenging, we can infer that the second, third, and fourth topics represent "animal", "sentiment", and "color", respectively. This reveals a limitation of LSA, as higher singular values do not necessarily guarantee the discovery of more meaningful topics.
Q5: By discarding the first topic, you can observe document embeddings that are opposite (e.g., documents 4 and 5). What are the characteristics of these documents that are opposite to each other?
Word Embedding
Finally, an embedding of the 'th term can be achieved as :
From the output, we can infer that the fourth topic still represents "color", whereas the meanings of "animal" and "sentiment" are distributed across the second and third topics. This suggests that each column does not necessarily represent a unique topic; rather, it is a combination across multiple columns that may represent a set of topics.
Q6: is not transposed in L3 of the above code. Should we use S.transpose() instead?
from src.types import Document, Vocab
def retrieve(filename: str) -> tuple[list[Document], Vocab]:
documents = [line.split() for line in open(filename)]
t = {word for document in documents for word in document}
terms = {term: j for j, term in enumerate(sorted(list(t)))}
return documents, terms
import numpy as np
def document_term_matrix(documents: list[Document], terms: Vocab) -> np.array:
def doc_vector(document: list[str]) -> list[int]:
v = [0] * len(terms)
for term in document:
v[terms[term]] += 1
return v
return np.array([doc_vector(document) for document in documents])
import time
D, T = retrieve('dat/chronicles_of_narnia.txt')
st = time.time()
X = document_term_matrix(D, T)
et = time.time()
print("|D| = {}, |T| = {}, Process Time (sec) = {:.2f}".format(len(X), len(X[0]), et - st))
|D| = 22603, |T| = 12361, Process Time (sec) = 17.87
def document_term_matrix_np(documents: list[Document], terms: Vocab) -> np.array:
X = np.zeros((len(documents), len(vocab)), dtype=int)
for i, document in enumerate(documents):
for term in document:
X[i, vocab[term]] += 1
return X
st = time.time()
X = document_term_matrix_np(D, T)
et = time.time()
print("|D| = {}, |T| = {}, Process Time (sec) = {:.2f}".format(len(X), len(X[0]), et - st))
|D| = 22603, |T| = 12361, Process Time (sec) = 0.55
love white cat
love black cat
hate white cat
hate black cat
love white dog
love black dog
hate white dog
hate black dog
D, T = retrieve('dat/latent_semantic_analysis.txt')
X = document_term_matrix_np(D, T)
U, S, Vt = np.linalg.svd(X, full_matrices=False)
S = np.diag(S)
def print_np(matrix: np.array):
print(matrix.shape)
for row in matrix:
print(' '.join(['{:8.4f}'.format(c) for c in row]))
print_np(U)
print_np(S)
print_np(Vt)
for i, document in enumerate(D):
t = np.dot(U[i], S)
print('{}: {}'.format(' '.join(document), ['{:5.2f}'.format(f) for f in t]))
love white cat: [-1.22, -0.99, -0.11, 0.71]
love black cat: [-1.22, -0.99, -0.11, -0.71]
hate white cat: [-1.22, -0.11, 0.99, 0.71]
hate black cat: [-1.22, -0.11, 0.99, -0.71]
love white dog: [-1.22, 0.11, -0.99, 0.71]
love black dog: [-1.22, 0.11, -0.99, -0.71]
hate white dog: [-1.22, 0.99, 0.11, 0.71]
hate black dog: [-1.22, 0.99, 0.11, -0.71]
V = Vt.transpose()
for term, j in sorted(T.items(), key=lambda x: x[1]):
t = np.dot(V[j], S)
print('{:>5}: {}'.format(term, ['{:5.2f}'.format(f) for f in t]))