📘

Sinusoidal Positional Encoding

MediumEmbeddings & Positional Encoding 📚 LLM 1: Foundations

Implement the sinusoidal positional encoding from "Attention Is All You Need".

For a sequence of length L and model dimension D, compute the positional encoding matrix PE where:

PE(pos, 2i) = sin(pos / 10000^(2i/D))
PE(pos, 2i+1) = cos(pos / 10000^(2i/D))

Input:

Line 1: L D (sequence length, model dimension)

Output: The L x D positional encoding matrix, values rounded to 4 decimal places, one row per position.

Example:

Input:

2 4

Output:

[ 0.0000  1.0000  0.0000  1.0000]
[ 0.8415  0.5403  0.0100  0.9999]

Reasoning:

We calculate the positional encoding matrix PE for a sequence of length L = 2 and model dimension D = 4.
For each position pos in the sequence, we compute the values of PE(pos, 2i) and PE(pos, 2i+1) using the given formulas: $PE(pos, 2i) = \sin(pos / 10000^{2i/D})$ and $PE(pos, 2i+1) = \cos(pos / 10000^{2i/D})$ .
We evaluate these formulas for pos = 0 and pos = 1, and i = 0 and i = 1, to get the values for the first and second positions:
- For pos = 0, we get $PE(0, 0) = \sin(0 / 10000^{0/4}) = \sin(0) = 0$ , $PE(0, 1) = \cos(0 / 10000^{0/4}) = \cos(0) = 1$ , $PE(0, 2) = \sin(0 / 10000^{1/4}) = \sin(0) = 0$ , $PE(0, 3) = \cos(0 / 10000^{1/4}) = \cos(0) = 1$ .
- For pos = 1, we get $PE(1, 0) = \sin(1 / 10000^{0/4}) = \sin(1) \approx 0.8415$ , $PE(1, 1) = \cos(1 / 10000^{0/4}) = \cos(1) \approx 0.5403$ , $PE(1, 2) = \sin(1 / 10000^{1/4}) \approx \sin(0.0100) \approx 0.0100$ , $PE(1, 3) = \cos(1 / 10000^{1/4}) \approx \cos(0.0100) \approx 0.9999$ .
The final output is the matrix with these computed values, rounded to 4 decimal places: [ 0.0000 1.0000

Constraints:

1 <= L <= 20, 2 <= D <= 16 (D is even)
Use base 10000 for the frequency
Round 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 concept of positional encoding is crucial in sequence-to-sequence models, particularly in the Transformer architecture, as it allows the model to understand the position of each element in the input sequence. This is necessary because the self-attention mechanism, a key component of the Transformer, is permutation-invariant, meaning it does not inherently capture the order of the input elements. The sinusoidal positional encoding is one method to incorporate positional information into the input embeddings.

The idea behind sinusoidal positional encoding is to generate a set of vectors that can be added to the input embeddings to convey positional information. These vectors are designed such that they can be learned by the model and are fixed during training, meaning they do not have any learnable parameters. The formula provided in the problem description, $PE(pos, 2i) = \sin(pos / 10000^{2i/D})$ and $PE(pos, 2i+1) = \cos(pos / 10000^{2i/D})$ , is used to compute the positional encoding matrix $PE$ , where $pos$ is the position in the sequence, $i$ is the dimension, $D$ is the model dimension, and $L$ is the sequence length.

Understanding the mathematical properties of the sine and cosine functions is essential for grasping how this encoding works. The use of $10000^{2i/D}$ as the base for the exponential decay allows the model to capture a wide range of positional relationships at different scales. This encoding scheme enables the model to effectively capture long-range dependencies in the input sequence, which is a critical aspect of many natural language processing tasks.

Algorithm/Approach

The general approach to solving this problem involves understanding the mathematical formula provided and implementing it in a programming language. The key steps involve iterating over each position in the sequence and each dimension in the model, applying the given formulas to compute the positional encoding values. This requires a basic understanding of nested loops, array or matrix operations, and trigonometric functions.

Step-by-Step Strategy

To implement the solution:

Read the input values for sequence length $L$ and model dimension $D$ .
Initialize an $L \times D$ matrix to store the positional encoding values.
Iterate over each position $pos$ from 0 to $L-1$ .
For each position, iterate over each dimension $i$ from 0 to $D-1$ .
Apply the formulas $PE(pos, 2i) = \sin(pos / 10000^{2i/D})$ and $PE(pos, 2i+1) = \cos(pos / 10000^{2i/D})$ to compute the positional encoding values.
Store the computed values in the corresponding positions in the matrix.
Round the values in the matrix to 4 decimal places.
Output the matrix, with one row per position.

Common Pitfalls

Incorrect implementation of the formulas, especially regarding the indexing and the application of the exponential decay.
Failure to round the values to the specified precision.
Inadequate handling of the input values, such as not checking for valid sequence lengths and model dimensions.

Time & Space Complexity

Time Complexity: The time complexity of this algorithm is $O(L \times D)$ , where $L$ is the sequence length and $D$ is the model dimension. This is because for each position in the sequence, we are iterating over each dimension.
Space Complexity: The space complexity is also $O(L \times D)$ , as we need to store the positional encoding matrix of size $L \times D$ .

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.