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 format:

Line 1: Three words (A B C) — the analogy query
Line 2: Number of words in vocabulary N
Lines 3 to N+2: word followed by its embedding vector (space-separated floats)

Output: 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

Step 1: Compute target vector target = queen - king + man = [0.8, 0.6, 0.5] - [1.0, 0.5, 0.0] + [0.9, 0.4, 0.0] = [0.7, 0.5, 0.5]

Step 2: Compute cosine similarity with each candidate Candidates (excluding king, queen, man): woman, child

woman [0.7, 0.5, 0.5]: cos_sim with [0.7, 0.5, 0.5] = 1.0
child [0.2, 0.3, 0.8]: cos_sim is lower

Answer: woman (highest similarity)

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