Embedding Lookup

easyFREEWord EmbeddingsNLP 1: Foundations

Given a simple embedding table (word-to-vector mapping) and a list of words, look up each word's embedding vector and return the average embedding.

Implement embedding_lookup(table, words):

table: a dict mapping each word to its embedding vector (a list of floats; all vectors have the same length)
words: a list of words to look up

In the example, the table is displayed as its entry count followed by one entry per line (word, then comma-separated floats, e.g. "cat 0.1,0.2,0.3"), and the last line lists the lookup words.

If a word is not in the table, skip it. Return the average as a list of floats, rounding each dimension to 4 decimal places.

Example

Input

3
cat 1.0,0.0
dog 0.0,1.0
fish 0.5,0.5
cat dog

Output

[0.5, 0.5]

Reasoning

Inputs: table maps three words to 2-dimensional vectors: cat $\to (1.0, 0.0)$ , dog $\to (0.0, 1.0)$ , fish $\to (0.5, 0.5)$ . words is the query: cat and dog.
Lookup: both query words are in the table, so $k = 2$ vectors take part. Fish is in the table but not in the query, so it plays no role.
Average: each dimension is averaged on its own, $\bar{e}_d = \frac{1}{k}\sum_{j=1}^{k} e_{j,d}$ $\overset{e}{ˉ}_{d} = \frac{1}{k} \sum_{j = 1}^{k} e_{j, d}$ :
- dimension 1: $\frac{1.0 + 0.0}{2} = 0.5$
- dimension 2: $\frac{0.0 + 1.0}{2} = 0.5$
Output: [0.5, 0.5], a list with one float per embedding dimension (here 2), each rounded to 4 decimal places.
Notice: a missing word is skipped entirely, so it changes the divisor $k$ rather than adding a zero vector. Querying cat and bird would give $(1.0, 0.0)$ , cat's own vector, not $(0.5, 0.0)$ .

Constraints

1 ≤ n ≤ 20
Embedding dimensions are consistent
At least one lookup word will be in the table
Output: List of floats rounded to 4 decimal places

Learn this in

NLP FundamentalsML Study Plan Introduction to NLPNLP Study Plan Text RepresentationNLP Study Plan Word EmbeddingsNLP Study Plan

More from NLP 1: Foundations

Concept primer

Background Knowledge

Word Embeddings are a fundamental concept in Natural Language Processing (NLP) that allows words to be represented as vectors in a high-dimensional space. This enables words with similar meanings to be mapped to nearby points in the vector space, capturing their semantic relationships. Embedding tables, also known as word-to-vector mappings, are data structures that store these vector representations for each word in a vocabulary.

The idea behind word embeddings is to learn a dense vector representation for each word, where semantically similar words are closer together in the vector space. This is typically achieved through techniques like word2vec or GloVe, which train neural networks to predict word co-occurrences in large text corpora. The resulting vector representations can be used as input features for various NLP tasks, such as text classification, sentiment analysis, or language modeling.

In the context of this problem, we are given a simple embedding table and a list of words to look up. Our goal is to retrieve the corresponding vector representations for each word and compute their average. This requires understanding how to work with word embeddings, perform vector operations, and handle missing words in the embedding table.

Algorithm/Approach

The general approach to solving this problem involves the following steps:

Parse the input data to construct the embedding table and extract the list of words to look up.
Iterate through the list of words and retrieve their corresponding vector representations from the embedding table.
Compute the average vector representation by summing up the individual vectors and dividing by the number of valid words.
Round each dimension of the result to the specified precision.

This problem can be solved using basic data structures and vector operations, without requiring any advanced NLP techniques or machine learning algorithms.

Step-by-Step Strategy

To implement the solution, follow these steps:

Read the number of entries in the embedding table and construct the table by parsing each word-vector pair.
Read the list of words to look up and split them into individual words.
Initialize a variable to store the sum of vector representations and a counter for the number of valid words.
Iterate through the list of words and check if each word exists in the embedding table. If it does, add its vector representation to the sum and increment the counter.
Compute the average vector representation by dividing the sum by the number of valid words.
Round each dimension of the result to the specified precision (4 decimal places).

Common Pitfalls

When implementing the solution, watch out for the following:

Make sure to handle missing words in the embedding table by skipping them and not including their vectors in the sum.
Be careful when parsing the input data to avoid errors in constructing the embedding table or extracting the list of words.
Use the correct data structures and vector operations to efficiently compute the average vector representation.

Time & Space Complexity

The time complexity of this problem is O(n + m), where n is the number of entries in the embedding table and m is the number of words to look up. This is because we need to iterate through the embedding table to construct it and then iterate through the list of words to compute the average vector representation.

The space complexity is O(n + m), as we need to store the embedding table and the list of words to look up. The space required to store the sum of vector representations and the result is relatively small and can be considered constant.

solution.py

Python 3.13

Test results