📘

Token Embedding Lookup

EasyEmbeddings & Positional Encoding 📚 LLM 1: Foundations

Implement a token embedding lookup table.

Given a vocabulary size V, embedding dimension D, and a sequence of token IDs, create a random embedding matrix (using numpy seed 42) and return the embeddings for each token.

Input:

Line 1: V D (vocab size, embedding dimension)
Line 2: space-separated token IDs

Output: The embedding matrix for the input tokens, one row per token, values rounded to 4 decimal places.

Example:

Input:

5 3
0 2 4

Output:

[[ 0.4967 -0.1383  0.6477]
 [ 0.5426 -0.4634 -0.4657]
 [-0.2349  0.2767 -0.3539]]

Reasoning:

We create a random embedding matrix of size $V \times D$ (5 x 3 in this case) using numpy with seed 42.
The input token IDs are used to index into this embedding matrix: tokens 0, 2, and 4 correspond to rows 0, 2, and 4 of the matrix.
Since token ID 4 is out of range for the given vocabulary size 5, we consider the actual indexing to be modulo V, so token ID 4 corresponds to row 4 % 5 = 4, which is the last row of the matrix.
The embeddings for the input tokens are retrieved from the embedding matrix and rounded to 4 decimal places, resulting in the output [[ 0.4967 -0.1383 0.6477], [ 0.5426 -0.4634 -0.4657], [-0.2349 0.2767 -0.3539]].

Constraints:

Use numpy with seed 42: np.random.seed(42); embeddings = np.random.randn(V, D)
1 <= V <= 100, 1 <= D <= 10
Token IDs are in range [0, V-1]
Round output to 4 decimal places

More from LLM 1: Foundations

Transformer Block Forward PassHard Feed-Forward NetworkEasy Layer NormalizationEasy KV-Cache AttentionHard Multi-Head AttentionMedium

Background Knowledge

The problem revolves around token embedding lookup, a fundamental concept in natural language processing (NLP) and machine learning. In NLP, tokens refer to the basic units of text, such as words or characters. Embeddings are a way to represent these tokens as dense vectors in a high-dimensional space, capturing their semantic meaning. The embedding dimension (D) determines the size of this vector space, while the vocabulary size (V) is the number of unique tokens in the language model.

Token embeddings are typically learned during the training process of a language model, but in this problem, we are tasked with creating a random embedding matrix. This matrix will have a size of $V \times D$ , where each row represents the embedding vector for a particular token. The embedding lookup process involves retrieving the corresponding embedding vector for a given token ID from this matrix. This is a crucial step in many NLP tasks, as it allows the model to understand the context and relationships between different tokens.

The use of numpy with a fixed seed (42) ensures that the random embedding matrix generated will be reproducible, which is important for debugging and testing purposes. The output will be the embedding matrix for the input tokens, with each row representing the embedding vector for a token, and the values rounded to 4 decimal places.

Algorithm/Approach

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

Create a random embedding matrix with the specified size ( $V \times D$ ) using numpy.
Parse the input token IDs and retrieve the corresponding embedding vectors from the matrix.
Round the embedding values to 4 decimal places and output the resulting matrix.

This problem can be seen as a simple application of array indexing and matrix operations, which are fundamental concepts in linear algebra and machine learning.

Step-by-Step Strategy

To implement the solution, follow these steps:

Import the necessary libraries, including numpy, and set the seed for reproducibility.
Read the input values for vocabulary size (V) and embedding dimension (D).
Create a random embedding matrix with size $V \times D$ using numpy.
Read the input token IDs and parse them into a list or array.
Use array indexing to retrieve the corresponding embedding vectors for each token ID from the matrix.
Round the embedding values to 4 decimal places.
Output the resulting embedding matrix.

Common Pitfalls

Some common pitfalls to watch out for include:

Forgetting to set the numpy seed, resulting in non-reproducible results.
Incorrectly parsing the input token IDs or vocabulary size.
Using the wrong data type or precision for the embedding matrix.
Failing to round the embedding values to the correct number of decimal places.

Time & Space Complexity

The time complexity of this problem is expected to be $O(V \times D + n)$ , where $n$ is the number of input token IDs. This is because we need to create the random embedding matrix (which takes $O(V \times D)$ time) and then retrieve the corresponding embedding vectors for each token ID (which takes $O(n)$ time). The space complexity is $O(V \times D)$ , as we need to store the entire embedding matrix in memory.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.