1 of 7

Distributional Semantics

Distributional semantics represents the meaning of words based on their distributional properties in large corpora of text. It follows the distributional hypothesis, which states that "words with similar meanings tend to occur in similar contexts".

Distributional Hypothesis
Word Representations
Latent Semantic Analysis
Neural Networks
Word2Vec
Homework

Distributional Hypothesis

The distributional hypothesis suggests that words that occur in similar contexts tend to have similar meanings [1]. Let us examine the following two sentences with blanks:

A: I sat on a __
B: I played with my __

The blank for A can be filled with words such as {bench, chair, sofa, stool}, which convey the meaning "something to sit on" in this context. On the other hand, the blank for B can be filled with words such as {child, dog, friend, toy}, carrying the meaning of "someone/thing to play with." However, these two sets of words are not interchangeable, as it is unlikely that you would sit on a "friend" or play with a "sofa".

This hypothesis provides a potent framework for understanding how meaning is encoded in language and has become a cornerstone of modern computational linguistics and natural language processing.

Assuming that your corpus has only the following three sentences, what context would influence the meaning of the word "chair" according to the distributional hypothesis?

I sat on a chair.
I will chair the meeting.
I am the chair of my department.

References

Distributional Structure, Zellig S. Harris, Word, 10 (2-3): 146-162, 1954.

Word Representations

One-hot Encoding

One-hot encoding represents words as binary vectors such that each word is represented as a vector where all dimensions are zero except for one, which is set to one, indicating the presence of that word.

Consider the following vocabulary:

V = [
    'king',    # 0
    'man',     # 1
    'woman',   # 2
    'queen'    # 3
]

Given a vocabulary size of 4, each word is represented as a 4-dimensional vector as illustrated below:

 king = [1, 0, 0, 0]
  man = [0, 1, 0, 0]
woman = [0, 0, 1, 0]
queen = [0, 0, 0, 1]

One-hot encoding has been largely adopted in traditional NLP models due to its simple and efficient representation of words in sparse vectors.

What are the drawbacks of using one-hot encoding to represent word vectors?

Word Embeddings

Word embeddings are dense vector representations of words in a continuous vector space. Each word is represented in a high-dimensional space, where the dimensions correspond to different contextual features of the word's meaning.

Consider the embeddings for three words, 'king', 'male', and 'female':

 king = [0.5, 0.0, 0.5, 0.0]
  man = [0.0, 0.5, 0.5, 0.0]
woman = [0.0, 0.5, 0.0, 0.5]

Based on these distributions, we can infer that the four dimensions in this vector space represent royalty, gender, male, and female respectively, such that the embedding for the word 'queen' can be estimated as follows:

 queen = king - man + woman
       = [0.5, 0.0, 0.0, 0.5]

The key idea is to capture semantic relationships between words by representing them in a way that similar words have similar vector representations. These embeddings are learned from large amounts of text data, where the model aims to predict or capture the context in which words appear.

In the above examples, each dimension represents a distinct type of meaning. However, in practice, a dimension can encapsulate multiple types of meanings. Furthermore, a single type of meaning can be depicted by a weighted combination of several dimensions, making it challenging to precisely interpret what each dimension implies.

Latent Semantic Analysis

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 $D$ of all documents in the corpus and a dictionary $T$ whose keys and values are terms and their unique indices, respectively:

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

We then define a function that takes $D$ and $T$ , and returns the document-term matrix $X \in \mathbb{R}^{|D| \times |T|}$ such that $X_{i,j}$ indicates the frequency of the $j$ 'th term in $T$ within the $i$ 'th document:

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])

L1: The numpy package.
L3: numpy.array

Let us create a document-term matrix from the corpus, dat/chronicles_of_narnia.txt:

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))

L1: Basic date and time types.
L3: time.time()

|D| = 22603, |T| = 12361, Process Time (sec) = 17.87

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:

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

Using this updated function, we see a noticeable enhancement in speed, about 0.5 seconds, to create the document-term matrix:

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

Why is the performance of document_term_matrix() significantly slower than document_term_matrix_np()?

Dimensionality Reduction

Singular values 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:

dat/latent_semantic_analysis.txt

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)

L3: numpy.linalg.svd()
L4: numpy.diag()

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)

(8, 6)
 -0.3536  -0.4969  -0.0552   0.3536  -0.6648  -0.0396
 -0.3536  -0.4969  -0.0552  -0.3536   0.3750   0.5911
 -0.3536  -0.0552   0.4969   0.3536   0.4847  -0.3598
 -0.3536  -0.0552   0.4969  -0.3536  -0.1949  -0.1917
 -0.3536   0.0552  -0.4969   0.3536   0.3187  -0.1450
 -0.3536   0.0552  -0.4969  -0.3536  -0.0289  -0.4065
 -0.3536   0.4969   0.0552   0.3536  -0.1386   0.5444
 -0.3536   0.4969   0.0552  -0.3536  -0.1512   0.0071

(6, 6)
  3.4641   0.0000   0.0000   0.0000   0.0000   0.0000
  0.0000   2.0000   0.0000   0.0000   0.0000   0.0000
  0.0000   0.0000   2.0000   0.0000   0.0000   0.0000
  0.0000   0.0000   0.0000   2.0000   0.0000   0.0000
  0.0000   0.0000   0.0000   0.0000   0.0000   0.0000
  0.0000   0.0000   0.0000   0.0000   0.0000   0.0000

(6, 6)
 -0.4082  -0.4082  -0.4082  -0.4082  -0.4082  -0.4082
  0.0000  -0.5522   0.5522   0.4417  -0.4417   0.0000
  0.0000   0.4417  -0.4417   0.5522  -0.5522   0.0000
 -0.7071  -0.0000  -0.0000  -0.0000  -0.0000   0.7071
 -0.2614  -0.3151  -0.3151   0.5765   0.5765  -0.2614
 -0.5148   0.4838   0.4838   0.0310   0.0310  -0.5148

k = 4
U = U[:, :k]
S = S[:k, :k]
Vt = Vt[:k, :]

What is the maximum number of topics that LSA can identify? What are the limitations associated with discovering topics using this approach?

Document Embedding

for i, document in enumerate(D):
    t = np.dot(U[i], S)
    print('{}: {}'.format(' '.join(document), ['{:5.2f}'.format(f) for f in t]))

numpy.dot()

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]

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.

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

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]))

black: [-1.41,  0.00,  0.00, -1.41]
  cat: [-1.41, -1.10,  0.88, -0.00]
  dog: [-1.41,  1.10, -0.88, -0.00]
 hate: [-1.41,  0.88,  1.10, -0.00]
 love: [-1.41, -0.88, -1.10, -0.00]
white: [-1.41,  0.00,  0.00,  1.41]

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.

References

Source: latent_semantic_analysis.py

Latent Semantic Analysis, Wikipedia.
Singular Value Decomposition, Wikipedia.

Neural Networks

Logistic Regression

Let $\mathrm{x} = [x_1, \ldots, x_n]$ be a vector representing an input instance, where $x_i$ denotes the $i$ 'th feature of the input and $y \in \{0, 1\}$ be its corresponding output label. Logistic regression uses the logistic function, aka. the sigmoid function, to estimate the probability that $\mathrm{x}$ belongs to $y$ :

\begin{align*} P(y=1|\mathrm{x}) &= \frac{1}{1 + e^{-(\mathrm{x}\cdot\mathrm{w}^T+b)}}\\ P(y=0|\mathrm{x}) &= 1 - P(y=1|\mathrm{x}) \end{align*}

The weight vector $\mathrm{w}=[w_1, \ldots, w_n]$ assigns weights to each dimension of the input vector $\mathrm{x}$ for the label $y=1$ such that a higher magnitude of weight $w_i$ indicates greater importance of the feature $x_i$ . Finally, $b$ represents the bias of the label $y=1$ within the training distribution.

What role does the sigmoid function play in the logistic regression model?

Consider a corpus consisting of two sentences:

D1: I love this movie
D2: I hate this movie

The input vectors $\mathrm{x}_1$ and $\mathrm{x}_2$ can be created for these two sentences using the bag-of-words model:

V = {0: "I", 1: "love", 2: "hate", 3: "this", 4: "movie"}
x1 = [1, 1, 0, 1, 1]
x2 = [1, 0, 1, 1, 1]

Let $y_1 =1$ and $y_2 = 0$ be the output labels of $\mathrm{x}_1$ and $\mathrm{x}_2$ , representing postive and negative sentiments of the input sentences, respectively. Then, a weight vector $\mathrm{w}$ can be trained using logistic regression:

w = [0.0, 1.5, -1.5, 0.0, 0.0]
b = 0

Softmax Regression

What is the role of the softmax function in the softmax regression model? How does it differ from the sigmoid function?

Consider a corpus consisting of three sentences:

D1: I love this movie
D2: I hate this movie
D3: I watched this movie

V = {0: "I", 1: "love", 2: "hate", 3: "this", 4: "movie", 5: "watched"}
x1 = [1, 1, 0, 1, 1, 0]
x2 = [1, 0, 1, 1, 1, 0]
x3 = [1, 0, 0, 1, 1, 1]

w1 = [0.0,  1.5, -1.0, 0.0, 0.0, 0.0]
w2 = [0.0, -1.0,  1.5, 0.0, 0.0, 0.0]
w3 = [0.0, -1.0, -1.0, 0.0, 0.0, 1.5]
b1 = b2 = b3 = 0

What are the limitations of the softmax regression model?

Multilayer Perceptron

Notice that the above equation for MLP does not include bias terms. How are biases handled in light of this formulation?

X = {0: "I", 1: "love", 2: "hate", 3: "this", 4: "movie", 5: "watched", 6: "truly"}
Y = {0: "positive", 1: "negative", 2: "neutral", 3: "very positive", 4: "very negative"}

x1 = [1, 1, 0, 1, 1, 0, 0]
x2 = [1, 0, 1, 1, 1, 0, 0]
x3 = [1, 0, 0, 1, 1, 1, 0]
x4 = [1, 1, 0, 1, 1, 0, 1]
x5 = [1, 0, 1, 1, 1, 0, 1]

y1, y2, y3, y4, y5 = 0, 1, 2, 3, 4

What would be the weight assigned to the feature "truly" learned by softmax regression for the above example?

Wx = [
  [0.0, 0.0, 0.0, 0.0, 0.0],
  [1.0, 0.0, 0.0, 0.5, 0.0],
  [0.0, 1.0, 0.0, 0.0, 0.5],
  [0.0, 0.0, 0.0, 0.0, 0.0],
  [0.0, 0.0, 0.0, 0.0, 0.0],
  [0.0, 0.0, 1.0, 0.0, 0.0],
  [0.0, 0.0, 0.0, 0.5, 0.5]
]

g1 = [1.0, 0.0, 0.0, 0.5, 0.0]
g2 = [0.0, 1.0, 0.0, 0.0, 0.5]
g3 = [0.0, 0.0, 1.0, 0.0, 0.0]
g4 = [1.0, 0.0, 0.0, 1.0, 0.5]
g5 = [0.0, 1.0, 0.0, 0.5, 1.0]

h1 = activation(g1) = [1.0, 0.0, 0.0, 0.0, 0.0]
h2 = activation(g2) = [0.0, 1.0, 0.0, 0.0, 0.0]
h3 = activation(g3) = [0.0, 0.0, 1.0, 0.0, 0.0]
h4 = activation(g4) = [1.0, 0.0, 0.0, 1.0, 0.0]
h5 = activation(g5) = [0.0, 1.0, 0.0, 0.0, 1.0]

Wh = [
  [ 1.0, -1.0, 0.0, -0.5, -1.0],
  [-1.0,  1.0, 0.0, -1.0, -0.5],
  [-1.0, -1.0, 1.0, -1.0, -1.0],
  [ 0.0, -1.0, 0.0,  1.0, -1.0],
  [-1.0,  0.0, 0.0, -1.0,  1.0]
]

o1 = [ 1.0, -1.0, -1.0,  0.0, -1.0]
o2 = [-1.0,  1.0, -1.0, -1.0,  0.0]
o3 = [ 0.0,  0.0,  1.0,  0.0,  0.0]
o4 = [ 0.5, -2.0, -2.0,  1.0, -2.0]
o5 = [-2.0,  0.5, -2.0, -2.0,  1.0]

y1 = softmax(o1) = [0.56, 0.08, 0.08, 0.21, 0.08]
y2 = softmax(o2) = [0.08, 0.56, 0.08, 0.08, 0.21]
y3 = softmax(o3) = [0.15, 0.15, 0.40, 0.15, 0.15]
y4 = softmax(o4) = [0.35, 0.03, 0.03, 0.57, 0.03]
y5 = softmax(o5) = [0.03, 0.35, 0.03, 0.03, 0.57]

What are the limitations of a multilayer perceptron?

References

Neural Network Methodologies and their Potential Application to Cloud Pattern Recognition, J. E. Peak, Defense Technical Information Center, ADA239214, 1991.

Word2Vec

Neural language models leverage neural networks trained on extensive text data, enabling them to discern patterns and connections between terms and documents. Through this training, neural language models gain the ability to comprehend and generate human-like language with remarkable fluency and coherence.

Word2Vec is a neural language model that maps words into a high-dimensional embedding space, positioning similar words closer to each other.

Continuous Bag-of-Words

Consider a sequence of words, $\{w_{k-2}, w_{k-1}, w_{k}, w_{k+1}, w_{k+2}\}$ . We can predict $w_i$ by leveraging its contextual words using a generative model similar to the n-gram models discussed previously ( $V$ : a vocabulary list comprising all unique words in the corpus):

w_k = \arg\max_{\forall. w_* \in V}P(w_*|w_{k-2},w_{k-1},w_{k+1},w_{k+2})

This objective can also be achieved by using a discriminative model such as Continuous Bag-of-Words (CBOW) using a multilayer perceptron. Let $\mathrm{x} \in \mathbb{R}^{1 \times n}$ be an input vector, where $n = |V|$ . $\mathrm{x}$ is created by the bag-of-words model on a set of context words, $I = \{w_{k-2},w_{k-1},w_{k+1},w_{k+2}\}$ , such that only the dimensions of $\mathrm{x}$ representing words in $I$ have a value of $1$ ; otherwise, they are set to $0$ .

Let $\mathrm{y} \in \mathbb{R}^{1 \times n}$ be an output vector, where all dimensions have the value of $0$ except for the one representing $w_k$ , which is set to $1$ .

Let $\mathrm{h} \in \mathbb{R}^{1 \times d}$ be a hidden layer between $\mathrm{x}$ and $\mathrm{y}$ and $\mathrm{W}_x \in \mathbb{R}^{n \times d}$ be the weight matrix between $\mathrm{x}$ and $\mathrm{h}$ , where the sigmoid function is used as the activation function:

\mathrm{h} = \mathrm{sigmoid}(\mathrm{x} \cdot \mathrm{W}_x)

Finally, let $\mathrm{W}_h \in \mathbb{R}^{n \times d}$ be the weight matrix between $\mathrm{h}$ and $\mathrm{y}$ :

\mathrm{y} = \mathrm{softmax}(\mathrm{h} \cdot \mathrm{W}_h^T)

What are the advantages of using discriminative models like CBOW for constructing language models compared to generative models like n-gram models?

Skip-gram

What are the advantages of CBOW models compared to Skip-gram models, and vice versa?

Distributional Embeddings

What limitations does the Word2Vec model have, and how can these limitations be addressed?

References

Efficient Estimation of Word Representations in Vector Space, Tomas Mikolov, Kai Chen, Greg Corrado, Jeffrey Dean, Proceedings of the International Conference on Learning Representations (ICLR), 2013.
GloVe: Global Vectors for Word Representation, Jeffrey Pennington, Richard Socher, Christopher Manning, Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), 2014.
Bag of Tricks for Efficient Text Classification, Armand Joulin, Edouard Grave, Piotr Bojanowski, Tomas Mikolov, Proceedings of the Conference of the European Chapter of the Association for Computational Linguistics (EACL), 2017.

Homework

Create a distributional_semantics.py file in the src/homework/ directory.

Task 1

Your task is to read word embeddings trained by Word2Vec:

Define a function called read_word_embeddings() that takes a path to the file consisting of word embeddings, word_embeddings.txt.
Return a dictionary where the key is a word and the value is its corresponding embedding in numpy.array.

Each line in the file adheres to the following format:

[WORD](\t[FLOAT]){50}

Task 2

Your task is to retrieve a list of the most similar words to a given target word:

Define a function called similar_words() that takes the word embeddings from Task 1, a target word (string), and a threshold (float).
Return a list of tuples, where each tuple contains a word similar to the target word and the cosine similarity between them as determined by the embeddings. The returned list must only include words with similarity scores greater than or equal to the threshold, sorted in descending order based on the similarity scores.

Task 3

Your task is to measure a similarity score between two documents:

Define a function called document_similarity() that takes the word embeddings and two documents (string). Assume that the documents are already tokenized.
For each document, generate a document embedding by averaging the embeddings of all words within the document.
Return the cosine similarity between the two document embeddings.

Submission

Commit and push the distributional_semantics.py file to your GitHub repository.

Latent Semantic Analysis

Document-Term Matrix

Let us define a function that reads a corpus, and returns a list $D$ of all documents in the corpus and a dictionary $T$ whose keys and values are terms and their unique indices, respectively:

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])

L1: The numpy package.
L3: numpy.array

Let us create a document-term matrix from the corpus, dat/chronicles_of_narnia.txt:

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))

L1: Basic date and time types.
L3: time.time()

|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

Using this updated function, we see a noticeable enhancement in speed, about 0.5 seconds, to create the document-term matrix:

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

The $i$ 'th row of $X$ is considered the document vector of the $i$ 'th document in the corpus, while the transpose of $j$ 'th column of $X$ is considered the term vector of the $j$ 'th term in the vocabulary.

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 $X$ into three matrices, $U$ , $\Sigma$ , and $V$ , where $U, V \in \mathbb{R}^{|D| \times \sigma}$ are orthogonal matrices and $\Sigma \in \mathbb{R}^{\sigma \times \sigma}$ is a diagonal matrix containing singular values, such that $X = U\Sigma V^T$ .

An orthogonal matrix is a square matrix whose rows and columns are orthogonal such that $O O^T = O^T O = I$ , where $I$ is the identity matrix.
Singular values 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:

dat/latent_semantic_analysis.txt

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)

L3: numpy.linalg.svd()
L4: numpy.diag()

This results $U \in \mathbb{R}^{8 \times 6}$ , $\Sigma \in \mathbb{R}^{6 \times 6}$ , and $V^T \in \mathbb{R}^{6 \times 6}$ such that:

In $U$ , each row represents a document and each column represent a topic.
In $\Sigma$ , each diagonal cell represents the weight of the corresponding topic.
In $V^T$ , each column represents a term and each row represents a topic.

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)

(8, 6)
 -0.3536  -0.4969  -0.0552   0.3536  -0.6648  -0.0396
 -0.3536  -0.4969  -0.0552  -0.3536   0.3750   0.5911
 -0.3536  -0.0552   0.4969   0.3536   0.4847  -0.3598
 -0.3536  -0.0552   0.4969  -0.3536  -0.1949  -0.1917
 -0.3536   0.0552  -0.4969   0.3536   0.3187  -0.1450
 -0.3536   0.0552  -0.4969  -0.3536  -0.0289  -0.4065
 -0.3536   0.4969   0.0552   0.3536  -0.1386   0.5444
 -0.3536   0.4969   0.0552  -0.3536  -0.1512   0.0071

(6, 6)
  3.4641   0.0000   0.0000   0.0000   0.0000   0.0000
  0.0000   2.0000   0.0000   0.0000   0.0000   0.0000
  0.0000   0.0000   2.0000   0.0000   0.0000   0.0000
  0.0000   0.0000   0.0000   2.0000   0.0000   0.0000
  0.0000   0.0000   0.0000   0.0000   0.0000   0.0000
  0.0000   0.0000   0.0000   0.0000   0.0000   0.0000

(6, 6)
 -0.4082  -0.4082  -0.4082  -0.4082  -0.4082  -0.4082
  0.0000  -0.5522   0.5522   0.4417  -0.4417   0.0000
  0.0000   0.4417  -0.4417   0.5522  -0.5522   0.0000
 -0.7071  -0.0000  -0.0000  -0.0000  -0.0000   0.7071
 -0.2614  -0.3151  -0.3151   0.5765   0.5765  -0.2614
 -0.5148   0.4838   0.4838   0.0310   0.0310  -0.5148

The last two singular values in $\Sigma$ are actually non-negative values, $3.72393692 \times 10^{−16}$ and $2.29674157 \times 10^{−16}$ , respectively.

The first four singular values in $\Sigma$ appear to be sufficiently larger than the others; thus, let us reduce their dimensions to $k = 4$ such that $U' \in \mathbb{R}^{8 \times 4}$ , $\Sigma' \in \mathbb{R}^{4 \times 4}$ , and $V'^{T} \in \mathbb{R}^{4 \times 6}$ :

k = 4
U = U[:, :k]
S = S[:k, :k]
Vt = Vt[:k, :]

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 $i$ 'th document can be obtained as $d_i = U_{i,*} \cdot \Sigma \in \mathbb{R}^{1 \times 4}$ :

for i, document in enumerate(D):
    t = np.dot(U[i], S)
    print('{}: {}'.format(' '.join(document), ['{:5.2f}'.format(f) for f in t]))

numpy.dot()

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]

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 $j$ 'th term can be achieved as $t_j = \Sigma \cdot V^T_{*,j} = V_{j,*} \cdot \Sigma^T \in \mathbb{R}^{1 \times 4}$ :

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]))

black: [-1.41,  0.00,  0.00, -1.41]
  cat: [-1.41, -1.10,  0.88, -0.00]
  dog: [-1.41,  1.10, -0.88, -0.00]
 hate: [-1.41,  0.88,  1.10, -0.00]
 love: [-1.41, -0.88, -1.10, -0.00]
white: [-1.41,  0.00,  0.00,  1.41]

$\Sigma$ is not transposed in L3 of the above code. Should we use S.transpose() instead?

References

Source: latent_semantic_analysis.py

Latent Semantic Analysis, Wikipedia.
Singular Value Decomposition, Wikipedia.

Word2Vec

Word2Vec is a neural language model that maps words into a high-dimensional embedding space, positioning similar words closer to each other.

Continuous Bag-of-Words

w_k = \arg\max_{\forall. w_* \in V}P(w_*|w_{k-2},w_{k-1},w_{k+1},w_{k+2})

Let $\mathrm{y} \in \mathbb{R}^{1 \times n}$ be an output vector, where all dimensions have the value of $0$ except for the one representing $w_k$ , which is set to $1$ .

\mathrm{h} = \mathrm{sigmoid}(\mathrm{x} \cdot \mathrm{W}_x)

Finally, let $\mathrm{W}_h \in \mathbb{R}^{n \times d}$ be the weight matrix between $\mathrm{h}$ and $\mathrm{y}$ :

\mathrm{y} = \mathrm{softmax}(\mathrm{h} \cdot \mathrm{W}_h^T)

Thus, each dimension in $\mathrm{y}$ represents the probability of the corresponding word being $w_k$ given the set of context words $I$ .

What are the advantages of using discriminative models like CBOW for constructing language models compared to generative models like n-gram models?

Skip-gram

In CBOW, a word is predicted by considering its surrounding context. Another approach, known as Skip-gram, reverses the objective such that instead of predicting a word given its context, it predicts each of the context words in $I$ given $w_k$ . Formally, the objective of a Skip-gram model is as follows:

\begin{align*} w_{k-2} &= \arg\max_{\forall. w_* \in V}P(w_*|w_k)\\ w_{k-1} &= \arg\max_{\forall. w_* \in V}P(w_*|w_k)\\ w_{k+1} &= \arg\max_{\forall. w_* \in V}P(w_*|w_k)\\ w_{k+2} &= \arg\max_{\forall. w_* \in V}P(w_*|w_k) \end{align*}

Let $\mathrm{x} \in \mathbb{R}^{1 \times n}$ be an input vector, where only the dimension representing $w_k$ is set to $1$ ; all the other dimensions have the value of $0$ (thus, $\mathrm{x}$ in Skip-gram is the same as $\mathrm{y}$ in CBOW). Let $\mathrm{y} \in \mathbb{R}^{1 \times n}$ be an output vector, where only the dimension representing $w_j \in I$ is set to $1$ ; all the other dimensions have the value of $0$ . All the other components, such as the hidden layer $\mathrm{h} \in \mathbb{R}^{1 \times d}$ and the weight matrices $\mathrm{W}_x \in \mathbb{R}^{n \times d}$ and $\mathrm{W}_h \in \mathbb{R}^{n \times d}$ , stay the same as the ones in CBOW.

What are the advantages of CBOW models compared to Skip-gram models, and vice versa?

Distributional Embeddings

What does each dimension in the hidden layer $\mathrm{h}$ represent for CBOW? It represents a feature obtained by aggregating specific aspects from each context word in $I$ , deemed valuable for predicting the target word $w_i$ . Formally, each dimension $\mathrm{h}_j$ is computed as the sigmoid activation of the weighted sum between the input vector $\mathrm{x}$ and the column vector such that:

\mathrm{h}_j = \mathrm{sigmoid}(\mathrm{x} \cdot \mathrm{cx}_j)

Then, what does each row vector $\mathrm{rx}_i = \mathrm{W}_x[i,:] \in \mathbb{R}^{1 \times d}$ represent? The $j$ 'th dimension in $\mathrm{rx}_i$ denotes the weight of the $j$ 'th feature in $\mathrm{h}$ with respect to the $i$ 'th word in the vocabulary. In other words, it indicates the importance of the corresponding feature in representing the $i$ 'th word. Thus, $\mathrm{r}_i$ can serve as an embedding for the $i$ 'th word in $V$ .

What about the other weight matrix $\mathrm{W}_h$ ? The $j$ 'th column vector $\mathrm{ch}_j = \mathrm{W}_h[:,j] \in \mathbb{R}^{n \times 1}$ denotes the weights of the $j$ 'th feature in $\mathrm{h}$ for all words in the vocabulary. Thus, the $i$ 'th dimension of $\mathrm{ch}_j$ indicates the importance of $j$ 'th feature for the $i$ 'th word being predicted as the target word $w_k$ .

On the other hand, the $i$ 'th row vector $\mathrm{rh}_i = \mathrm{W}_x[i,:] \in \mathbb{R}^{1 \times d}$ denotes the weights of all features for the $i$ 'th word in the vocabulary, enabling it to be utilized as an embedding for $w_i \in V$ . However, in practice, only the row vectors of the first weight matrix $\mathrm{W}_x$ are employed as word embeddings because the weights in $\mathrm{W}_h$ are often optimized for the downstream task, in this case predicting $w_k$ , whereas the weights in $\mathrm{W}_x$ are optimized for finding representations that are generalizable across various tasks.

What are the implications of the weight matrices $\mathrm{W}_x$ and $\mathrm{W}_h$ in the Skip-gram model?

What limitations does the Word2Vec model have, and how can these limitations be addressed?

References

Efficient Estimation of Word Representations in Vector Space, Tomas Mikolov, Kai Chen, Greg Corrado, Jeffrey Dean, Proceedings of the International Conference on Learning Representations (ICLR), 2013.
GloVe: Global Vectors for Word Representation, Jeffrey Pennington, Richard Socher, Christopher Manning, Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), 2014.
Bag of Tricks for Efficient Text Classification, Armand Joulin, Edouard Grave, Piotr Bojanowski, Tomas Mikolov, Proceedings of the Conference of the European Chapter of the Association for Computational Linguistics (EACL), 2017.

Neural Networks

Logistic Regression

\begin{align*} P(y=1|\mathrm{x}) &= \frac{1}{1 + e^{-(\mathrm{x}\cdot\mathrm{w}^T+b)}}\\ P(y=0|\mathrm{x}) &= 1 - P(y=1|\mathrm{x}) \end{align*}

What role does the sigmoid function play in the logistic regression model?

Consider a corpus consisting of two sentences:

D1: I love this movie
D2: I hate this movie

The input vectors $\mathrm{x}_1$ and $\mathrm{x}_2$ can be created for these two sentences using the bag-of-words model:

V = {0: "I", 1: "love", 2: "hate", 3: "this", 4: "movie"}
x1 = [1, 1, 0, 1, 1]
x2 = [1, 0, 1, 1, 1]

w = [0.0, 1.5, -1.5, 0.0, 0.0]
b = 0

Since the terms "I", "this", and "movie" appear with equal frequency across both labels, their weights $w_1$ , $w_4$ , and $w_5$ are neutralized. On the other hand, the terms "love" and "hate" appear only with the positive and negative labels, respectively. Therefore, while the weight $w_1$ for "love" ( $x_1$ ) contributes positively to the label $y=1$ , the weight $w_2$ for "hate" ( $x_2$ ) has a negative impact on the label $y=1$ . Furthermore, as positive and negative sentiment labels are equally presented in this corpus, the bias $b$ is also set to 0.

Given the weight vector and the bias, we have $\mathrm{x}_1 \cdot \mathrm{w}^T + b = 1.5$ and $\mathrm{x}_2 \cdot \mathrm{w}^T + b = -1.5$ , resulting the following probabilities:

\begin{align*} P(y=1|\mathrm{x}_1) \approx 0.82\\ P(y=1|\mathrm{x}_2) \approx 0.18 \end{align*}

As the probability of $x_1$ being $y=1$ exceeds $0.5$ (50%), the model predicts the first sentence to convey a positive sentiment. Conversely, the model predicts the second sentence to convey a negative sentiment as its probability of being $y=1$ is below 50%.

Under what circumstances would the bias $b$ be negative in the above example? Additionally, when might neutral terms such as "this" or "movie" exhibit non-neutral weights?

Softmax Regression

Softmax regression, aka. multinomial logistic regression, is an extension of logistic regression to handle classification problems with more than two classes. Given an input vector $\mathrm{x} \in \mathbb{R}^{1 \times n}$ and its output lable $y \in \{0, \ldots, m-1\}$ , the model uses the softmax function to estimates the probability that $\mathrm{x}$ belongs to each class separately:

P(y=k|\mathrm{x}) = \frac{e^{\mathrm{x}\cdot\mathrm{w}_k^T+b_k}}{\sum_{j=1}^m e^{\mathrm{x}\cdot\mathrm{w}_j^T+b_j}}

The weight vector $\mathrm{w}_k$ assigns weights to $\mathrm{x}$ for the label $y=k$ , while $b_k$ represents the bias associated with the label $y=k$ .

What is the role of the softmax function in the softmax regression model? How does it differ from the sigmoid function?

Consider a corpus consisting of three sentences:

D1: I love this movie
D2: I hate this movie
D3: I watched this movie

Then, the input vectors $\mathrm{x}_1$ , $\mathrm{x}_2$ , and $\mathrm{x}_3$ for the sentences can be created using the bag-of-words model:

V = {0: "I", 1: "love", 2: "hate", 3: "this", 4: "movie", 5: "watched"}
x1 = [1, 1, 0, 1, 1, 0]
x2 = [1, 0, 1, 1, 1, 0]
x3 = [1, 0, 0, 1, 1, 1]

Let $y_1 =1$ , $y_2 = 0$ , and $y=2$ be the output labels of $\mathrm{x}_1$ , $\mathrm{x}_2$ , and $\mathrm{x}_3$ , representing postive, negative, and neutral sentiments of the input sentences, respectively. Then, weight vectors $\mathrm{w}_1$ , $\mathrm{w}_2$ , and $\mathrm{w}_3$ can be trained using softmax regression as follows:

w1 = [0.0,  1.5, -1.0, 0.0, 0.0, 0.0]
w2 = [0.0, -1.0,  1.5, 0.0, 0.0, 0.0]
w3 = [0.0, -1.0, -1.0, 0.0, 0.0, 1.5]
b1 = b2 = b3 = 0

Unlike the case of logistic regression where all weights are oriented to $y = 1$ (both $w_1$ and $w_2$ giving positive and negative weights to $y = 1$ respectively, but not $y=0$ ), the values in each weigh vector are oriented to each corresponding label.

Given the weight vectors and the biases, we can estimate the following probabilities for $\mathrm{x}_1$ :

\begin{align*} \mathrm{x}_1 \cdot \mathrm{w}_1^T + b_1 &=& 1.5  &\Rightarrow & P(y=1|\mathrm{x}_1) &=& 0.86\\ \mathrm{x}_1 \cdot \mathrm{w}_2^T + b_2 &=& -1.0 &\Rightarrow & P(y=0|\mathrm{x}_1) &=& 0.07\\ \mathrm{x}_1 \cdot \mathrm{w}_3^T + b_3 &=& -1.0 &\Rightarrow & P(y=2|\mathrm{x}_1) &=& 0.07 \end{align*}

Since the probabiilty of $y=1$ is the highest among all labels, the model predicts the first sentence to convey a positive sentiment. For $\mathrm{x}_3$ , the following probabilities can be estimated:

\begin{align*} \mathrm{x}_3 \cdot \mathrm{w}_1^T + b_1 &=& 0  &\Rightarrow & P(y=1|\mathrm{x}_3) &=& 0.14\\ \mathrm{x}_3 \cdot \mathrm{w}_2^T + b_2 &=& 0 &\Rightarrow & P(y=0|\mathrm{x}_3) &=& 0.14\\ \mathrm{x}_3 \cdot \mathrm{w}_3^T + b_3 &=& 1.5 &\Rightarrow & P(y=2|\mathrm{x}_3) &=& 0.69 \end{align*}

Since the probabiilty of $y=2$ is the highest among all labels, the model predicts the first sentence to convey a neutral sentiment.

Softmax regression always predicts $m$ values so that it is represented by an output vector $\mathrm{y} \in \mathbb{R}^{1 \times m}$ , wherein the $i$ 'th value in $\mathrm{y}$ contains the probability of the input belonging to the $i$ 'th class. Similarly, the weight vectors for all labels can be stacked into a weight matrix $\mathrm{W} \in \mathbb{R}^{m \times n}$ , where the $i$ 'th row represents the weight vector for the $i$ 'th label.

With this new formulation, softmax regression can be defined as $\mathrm{y} = \mathrm{softmax}(\mathrm{x} \cdot \mathrm{W}^T)$ , and the optimal prediction can be achieved as $\mathrm{argmax}(\mathrm{y})$ , which returns a set of labels with the highest probabilities.

What are the limitations of the softmax regression model?

Multilayer Perceptron

A multilayer perceptron (MLP) is a type of Feedforward Neural Networks consisting of multiple layers of neurons, where all neurons from one layer are fully connected to all neurons in its adjecent layers. Given an input vector $\mathrm{x} \in \mathbb{R}^{1 \times n}$ and an output vector $\mathrm{y} \in \mathbb{R}^{1 \times m}$ , the model allows zero to many hidden layers to generate intermediate representations of the input.

Let $\mathrm{h} \in \mathbb{R}^{1 \times d}$ be a hidden layer between $\mathrm{x}$ and $\mathrm{y}$ . To connect $\mathrm{x}$ and $\mathrm{h}$ , we need a weight matrix $\mathrm{W}_x \in \mathbb{R}^{n \times d}$ such that $\mathrm{h} = \mathrm{activation}(\mathrm{x} \cdot \mathrm{W}_x)$ , where $\mathrm{activation}()$ is an activation function applied to the output of each neuron; it introduces non-linearity into the network, allowing it to learn complex patterns and relationships in the data. Activation functions determine whether a neuron should be activated or not, implying whether or not the neuron's output should be passed on to the next layer.

\mathrm{h} = \mathrm{activation}(\mathrm{x} \cdot \mathrm{W}_x)

Similarly, to connect $\mathrm{h}$ and $\mathrm{y}$ , we need a weight matrix $\mathrm{W}_h \in \mathbb{R}^{m \times d}$ such that $\mathrm{y} = \mathrm{softmax}(\mathrm{h} \cdot \mathrm{W}_h^T)$ . Thus, a multilayer perceptron with one hidden layer can be represented as:

\mathrm{y} = \mathrm{softmax}[\mathrm{activation}(\mathrm{x} \cdot \mathrm{W}_x) \cdot \mathrm{W}_h^T] = \mathrm{softmax}(\mathrm{h} \cdot \mathrm{W}_h^T)

Notice that the above equation for MLP does not include bias terms. How are biases handled in light of this formulation?

Consider a corpus comprising the following five sentences the corresponding labels ( $\Rightarrow$ ):

D1: I love this movie $\Rightarrow$ postive
D2: I hate this movie $\Rightarrow$ negative
D3: I watched this movie $\Rightarrow$ neutral
D4: I truly love this movie $\Rightarrow$ very positive
D5: I truly hate this movie $\Rightarrow$ very negative

The input vectors $\mathrm{x}_{1..5}$ can be created using the bag-of-words model:

X = {0: "I", 1: "love", 2: "hate", 3: "this", 4: "movie", 5: "watched", 6: "truly"}
Y = {0: "positive", 1: "negative", 2: "neutral", 3: "very positive", 4: "very negative"}

x1 = [1, 1, 0, 1, 1, 0, 0]
x2 = [1, 0, 1, 1, 1, 0, 0]
x3 = [1, 0, 0, 1, 1, 1, 0]
x4 = [1, 1, 0, 1, 1, 0, 1]
x5 = [1, 0, 1, 1, 1, 0, 1]

y1, y2, y3, y4, y5 = 0, 1, 2, 3, 4

What would be the weight assigned to the feature "truly" learned by softmax regression for the above example?

The first weight matrix $\mathrm{W}_x \in \mathbb{R}^{7 \times 5}$ can be trained by an MLP as follows:

Wx = [
  [0.0, 0.0, 0.0, 0.0, 0.0],
  [1.0, 0.0, 0.0, 0.5, 0.0],
  [0.0, 1.0, 0.0, 0.0, 0.5],
  [0.0, 0.0, 0.0, 0.0, 0.0],
  [0.0, 0.0, 0.0, 0.0, 0.0],
  [0.0, 0.0, 1.0, 0.0, 0.0],
  [0.0, 0.0, 0.0, 0.5, 0.5]
]

Given the values in $\mathrm{W}_x$ , we can infer that the first, second, and third columns represent "love", 'hate", and "watch", while the fourth and fifth columns learn combined features such as {"truly", "love"} and {"truly", "hate"}, respectively.

Each of $\mathrm{x}_{1..5}$ is multiplied by $\mathrm{W}_x$ to achieve the hiddner layer $\mathrm{h}_{1..5}$ , respectively, where the activation function is designed as follow:

\mathrm{activation}(x) = \left\{ \begin{array}{ll}   x & \text{if}\: x > 0.5\\   0 & \text{otherwise} \end{array} \right.

g1 = [1.0, 0.0, 0.0, 0.5, 0.0]
g2 = [0.0, 1.0, 0.0, 0.0, 0.5]
g3 = [0.0, 0.0, 1.0, 0.0, 0.0]
g4 = [1.0, 0.0, 0.0, 1.0, 0.5]
g5 = [0.0, 1.0, 0.0, 0.5, 1.0]

h1 = activation(g1) = [1.0, 0.0, 0.0, 0.0, 0.0]
h2 = activation(g2) = [0.0, 1.0, 0.0, 0.0, 0.0]
h3 = activation(g3) = [0.0, 0.0, 1.0, 0.0, 0.0]
h4 = activation(g4) = [1.0, 0.0, 0.0, 1.0, 0.0]
h5 = activation(g5) = [0.0, 1.0, 0.0, 0.0, 1.0]

The second weight matrix $\mathrm{W}_h \in \mathbb{R}^{5 \times 5}$ can also be trained by an MLP as follows:

Wh = [
  [ 1.0, -1.0, 0.0, -0.5, -1.0],
  [-1.0,  1.0, 0.0, -1.0, -0.5],
  [-1.0, -1.0, 1.0, -1.0, -1.0],
  [ 0.0, -1.0, 0.0,  1.0, -1.0],
  [-1.0,  0.0, 0.0, -1.0,  1.0]
]

By applying the softmax function to each $\mathrm{h}_i \cdot \mathrm{W}^T_h$ , we achieve the corresponding output vector $\mathrm{y}_i$ :

o1 = [ 1.0, -1.0, -1.0,  0.0, -1.0]
o2 = [-1.0,  1.0, -1.0, -1.0,  0.0]
o3 = [ 0.0,  0.0,  1.0,  0.0,  0.0]
o4 = [ 0.5, -2.0, -2.0,  1.0, -2.0]
o5 = [-2.0,  0.5, -2.0, -2.0,  1.0]

y1 = softmax(o1) = [0.56, 0.08, 0.08, 0.21, 0.08]
y2 = softmax(o2) = [0.08, 0.56, 0.08, 0.08, 0.21]
y3 = softmax(o3) = [0.15, 0.15, 0.40, 0.15, 0.15]
y4 = softmax(o4) = [0.35, 0.03, 0.03, 0.57, 0.03]
y5 = softmax(o5) = [0.03, 0.35, 0.03, 0.03, 0.57]

The prediction can be made by taking the argmax of each $\mathrm{y}_i$ .

What are the limitations of a multilayer perceptron?

References

Neural Network Methodologies and their Potential Application to Cloud Pattern Recognition, J. E. Peak, Defense Technical Information Center, ADA239214, 1991.

Distributional Semantics

Contents

Distributional Hypothesis

References

Word Representations

One-hot Encoding

Word Embeddings

Latent Semantic Analysis

Document-Term Matrix

Dimensionality Reduction

Document Embedding

Word Embedding

References

Neural Networks

Logistic Regression

Softmax Regression

Multilayer Perceptron

References

Word2Vec

Continuous Bag-of-Words

Skip-gram

Distributional Embeddings

References

Homework

Task 1

Task 2

Task 3

Submission

Distributional Hypothesis

References

Distributional Semantics

Contents

Homework

Task 1

Task 2

Task 3

Submission

Word Representations

One-hot Encoding

Word Embeddings

Latent Semantic Analysis

Document-Term Matrix

Dimensionality Reduction

Document Embedding

Word Embedding

References

Word2Vec

Continuous Bag-of-Words

Skip-gram

Distributional Embeddings

References

Neural Networks

Logistic Regression

Softmax Regression

Multilayer Perceptron

References