Word Analogy Solver

mediumFREEWord EmbeddingsNLP 1: Foundations

Solve word analogies using vector arithmetic on word embeddings.

Word analogies take the form: "A is to B as C is to ?"

Using word vectors, the answer is the word whose vector is closest to: $\vec{B} - \vec{A} + \vec{C}$

Input: solve_analogy(a, b, c, embeddings)

a, b, c: the three query words (A, B, C), all present in the vocabulary
embeddings: a dict mapping each vocabulary word to its embedding vector (a list of floats)

Output: Return the word from the vocabulary (excluding A, B, C) whose vector is closest to B - A + C (using cosine similarity).

Example

Input

king queen man
5
king 1.0 0.5 0.0
queen 0.8 0.6 0.5
man 0.9 0.4 0.0
woman 0.7 0.5 0.5
child 0.2 0.3 0.8

Output

woman

Reasoning

Inputs: the query reads "king is to queen as man is to ?", so $A$ = king, $B$ = queen, $C$ = man. Each of the 5 vocabulary words maps to a 3-dimensional vector.
Target vector: $\vec{B} - \vec{A}$ captures the "male to female" offset, and adding it to $\vec{C}$ applies that offset to man: $[0.8-1.0+0.9,\ 0.6-0.5+0.4,\ 0.5-0+0] = [0.7, 0.5, 0.5]$ , with length $\sqrt{0.99} \approx 0.995$ .
Candidates: king, queen and man are excluded, leaving woman and child.
woman $[0.7, 0.5, 0.5]$ : the dot product with the target is $0.99$ , and both lengths are $\sqrt{0.99}$ , so $\cos\theta = 0.99 / 0.99 = 1.0$ .
child $[0.2, 0.3, 0.8]$ : dot product $0.14 + 0.15 + 0.40 = 0.69$ , length $\sqrt{0.77} \approx 0.877$ , so $\cos\theta \approx 0.69 / (0.995 \times 0.877) \approx 0.790$ .
Output: the largest similarity wins, giving woman. Notice that the target is not itself a vocabulary entry in general; here it happens to coincide with woman exactly, which is why its similarity is a perfect 1.0.

Constraints

Exclude the three query words from candidate answers
Use cosine similarity to find the closest word
All vectors have the same dimensionality
There will be a unique best answer

Learn this in

Tokenization & EmbeddingsLLM Study Plan NLP FundamentalsML Study Plan Word EmbeddingsNLP Study Plan Language ModelingNLP Study Plan

More from NLP 1: Foundations

Embedding Lookupeasy Cosine Similarity Calculatoreasy Binary Vectorizereasy Document Term Matrixeasy Character Frequency Countereasy

Concept primer

Background Knowledge

Word Embeddings are a fundamental concept in Natural Language Processing (NLP) that represent words as vectors in a high-dimensional space. This allows words with similar meanings to be mapped to nearby points in the vector space. Word embeddings can be learned using various techniques, such as Word2Vec or GloVe, and are essential for many NLP tasks, including text classification, sentiment analysis, and machine translation.

The idea of using vector arithmetic to solve word analogies is based on the concept of vector space models. In these models, words are represented as vectors, and operations like addition and subtraction can be performed on these vectors to capture semantic relationships between words. For example, the vector $\vec{B} - \vec{A}$ represents the semantic relationship between words A and B. By adding $\vec{C}$ to this result, we can find a word that is related to C in the same way that B is related to A.

The cosine similarity measure is commonly used to compare the similarity between two vectors. It is defined as the dot product of the two vectors divided by the product of their magnitudes. Cosine similarity is useful for comparing the orientation of two vectors, rather than their magnitude. In the context of word embeddings, cosine similarity can be used to find the word that is most similar to a given vector, which is essential for solving word analogies.

Algorithm/Approach

The general approach to solving word analogies using vector arithmetic involves the following steps:

Load the word embeddings for the given vocabulary
Calculate the vector $\vec{B} - \vec{A} + \vec{C}$ using the given words A, B, and C
Compare this vector to the word embeddings in the vocabulary using cosine similarity
Return the word with the highest cosine similarity score, excluding the words A, B, and C

This approach relies on the idea that the vector $\vec{B} - \vec{A} + \vec{C}$ captures the semantic relationship between the words A, B, and C, and that the word with the highest cosine similarity score will be the one that is most similar to this relationship.

Step-by-Step Strategy

To implement the solution, follow these steps:

Read the input words A, B, and C, and the number of words in the vocabulary N
Load the word embeddings for the vocabulary, storing each word and its corresponding vector in a data structure (e.g., a dictionary)
Calculate the vector $\vec{B} - \vec{A} + \vec{C}$ using the word embeddings
Initialize a variable to store the word with the highest cosine similarity score
Iterate over the word embeddings in the vocabulary, excluding the words A, B, and C
For each word, calculate the cosine similarity between its vector and the vector $\vec{B} - \vec{A} + \vec{C}$
Update the variable storing the word with the highest cosine similarity score if a higher score is found
Return the word with the highest cosine similarity score

Common Pitfalls

When implementing the solution, watch out for the following:

Ensure that the word embeddings are loaded correctly and stored in a suitable data structure
Verify that the vector calculations are performed correctly, taking into account the dimensions of the word embeddings
Be careful when iterating over the vocabulary, excluding the words A, B, and C to avoid biasing the results
Consider using a library or framework that provides efficient implementations of cosine similarity and vector operations

Time & Space Complexity

The time complexity of the solution is O(N * d), where N is the number of words in the vocabulary and d is the dimensionality of the word embeddings. This is because we need to iterate over the vocabulary and perform vector operations for each word. The space complexity is O(N * d), as we need to store the word embeddings in memory. Note that the dimensionality of the word embeddings (d) is typically much larger than the number of words in the vocabulary (N), so the space complexity is dominated by the storage of the word embeddings.

solution.py

Python 3.13

Test results