Implement Positional Encoding - Sinusoidal and Learned

CODINGadvancedInterview freq: high

Choose your preparation mode6 modes available

Learn Trace Debug Trade-off Challenge

🤖

Implement positional encodings for sequence models using both sinusoidal and learned methods.

codingadvancedFreq: highDeep Learning Coding

Prerequisites:Transformer ArchitectureAttention Mechanism implementation

📝

Problem Statement

Implement positional encoding for sequence models using both sinusoidal and learned methods. The function should take the sequence length and the model dimension as inputs and return the positional encodings.

I/O Specification

Input:  sequence_length: int, model_dimension: int
Output: positional_encodings: numpy.ndarray or torch.Tensor

Example

{
  "input": "sequence_length=4, model_dimension=8",
  "expected_output": "numpy.ndarray or torch.Tensor of shape (4, 8)"
}

🎯

Interview Angles

Understanding of positional encoding in transformers and why it's necessary.
Ability to implement vectorized operations for efficiency in deep learning models.
Knowledge of PyTorch's nn.Parameter for creating learnable parameters.
Handling edge cases in sequence models, such as varying sequence lengths.

🔵

Naive Approach

For sinusoidal positional encoding, compute each position's encoding using sine and cosine functions directly in a loop. For learned positional encoding, initialize a learnable matrix and return it.

Time: O(sequence_length * model_dimension) - two nested loops over sequence length and model dimension. Space: O(sequence_length * model_dimension) - storing the positional encodings.

Why Insufficient

O(sequence_length * model_dimension) is inefficient for large sequences and dimensions due to the nested loops.

🐍

Naive Code

Python

import numpy as np

def naive_sinusoidal_positional_encoding(sequence_length, model_dimension):
    position_encodings = np.zeros((sequence_length, model_dimension))
    for pos in range(sequence_length):
        for i in range(model_dimension):
            if i % 2 == 0:
                position_encodings[pos, i] = np.sin(pos / (10000 ** (i / model_dimension)))
            else:
                position_encodings[pos, i] = np.cos(pos / (10000 ** ((i - 1) / model_dimension)))
    return position_encodings

# Driver example
sequence_length = 4
model_dimension = 8
print(naive_sinusoidal_positional_encoding(sequence_length, model_dimension))

💡

Key Insight

Use vectorized operations to compute sinusoidal positional encodings in a single step. For learned encodings, leverage PyTorch's nn.Parameter for automatic differentiation.

🐍

Optimized Code

Python

import numpy as np
import torch
import torch.nn as nn

class SinusoidalPositionalEncoding:
    def __init__(self, sequence_length, model_dimension):
        self.sequence_length = sequence_length
        self.model_dimension = model_dimension

    def get_encoding(self):
        position = np.arange(self.sequence_length)[:, np.newaxis]
        div_term = np.exp(np.arange(0, self.model_dimension, 2) * -(np.log(10000.0) / self.model_dimension))
        encoding = np.zeros((self.sequence_length, self.model_dimension))
        encoding[:, 0::2] = np.sin(position * div_term)
        encoding[:, 1::2] = np.cos(position * div_term)
        return encoding

class LearnedPositionalEncoding(nn.Module):
    def __init__(self, sequence_length, model_dimension):
        super(LearnedPositionalEncoding, self).__init__()
        self.position_embeddings = nn.Parameter(torch.zeros(sequence_length, model_dimension))
        nn.init.normal_(self.position_embeddings, mean=0, std=0.02)

    def forward(self):
        return self.position_embeddings

# Driver example
sequence_length = 4
model_dimension = 8
sinusoidal_encoding = SinusoidalPositionalEncoding(sequence_length, model_dimension)
print(sinusoidal_encoding.get_encoding())

learned_encoding = LearnedPositionalEncoding(sequence_length, model_dimension)
print(learned_encoding())

🔍

Line-by-Line

position = np.arange(self.sequence_length)[:, np.newaxis]

Create a column vector of positions to broadcast with div_term.

div_term = np.exp(np.arange(0, self.model_dimension, 2) * -(np.log(10000.0) / self.model_dimension))

Precompute the scaling factor for sine and cosine functions.

encoding[:, 0::2] = np.sin(position * div_term)

Compute sine for even indices using vectorized operations.

encoding[:, 1::2] = np.cos(position * div_term)

Compute cosine for odd indices using vectorized operations.

self.position_embeddings = nn.Parameter(torch.zeros(sequence_length, model_dimension))

Initialize learnable position embeddings as a PyTorch parameter for gradient updates.

nn.init.normal_(self.position_embeddings, mean=0, std=0.02)

Initialize the embeddings with a normal distribution for better convergence.

⚡

Complexity

Time: O(sequence_length * model_dimension / 2) - vectorized computation halves the operations. Space: O(sequence_length * model_dimension) - storing the positional encodings.

Output

A numpy.ndarray for sinusoidal and a torch.Tensor for learned encodings, both of shape (4, 8).

🔲

Edge Cases

Zero sequence length

Returns an empty array or tensor.

position = np.arange(self.sequence_length)[:, np.newaxis]

Single dimension

Handles correctly by computing only sine values.

div_term = np.exp(np.arange(0, self.model_dimension, 2) * -(np.log(10000.0) / self.model_dimension))

⚠️

Common Mistakes

Using loops instead of vectorized operations.

Symptom: Significantly slower execution time for large inputs.

Incorrect initialization of learned embeddings.

Symptom: Poor model convergence or training instability.

Misalignment of sine and cosine indices.

Symptom: Incorrect positional encodings leading to model performance issues.

Forgetting to handle edge cases like zero sequence length.

Symptom: Runtime errors or unexpected outputs for edge cases.

Practice

(1/5)

1. What is the time complexity of applying a dropout layer to an input of size n during training?

easy

A. O(1)

B. O(log n)

C. O(n^2)

D. O(n)

Solution

Step 1: Analyze Dropout Operation
Applying dropout involves generating a mask and element-wise multiplication, both O(n) operations.
Step 2: Eliminate Wrong Options
O(1) suggests constant time, which is incorrect. O(n^2) suggests quadratic time, which is excessive. O(log n) suggests logarithmic time, which is not applicable.
Final Answer:
Option D -> Option D
Quick Check:
Dropout involves element-wise operations. [OK]

Hint: Dropout involves element-wise operations. [OK]

Common Mistakes:

2. What is the time complexity of updating the learning rate using PyTorch's StepLR scheduler for each epoch?

easy

A. O(n^2)

B. O(n)

C. O(1)

D. O(log n)

Solution

Step 1: Analyze StepLR update mechanism
StepLR updates the learning rate by multiplying it with a constant factor, which is a constant time operation.
Step 2: Determine time complexity
Since the update is a simple multiplication, the time complexity is O(1).
Final Answer:
Option C -> Option C
Quick Check:
StepLR update is a constant time operation. [OK]

Hint: StepLR update is a constant time operation. [OK]

Common Mistakes:

3. In a decision tree, how would you handle a dataset with continuous features?

medium

A. Ignore continuous features.

B. Use one-hot encoding for continuous features.

C. Discretize continuous features into bins.

D. Use continuous features directly without modification.

Solution

Step 1: Consider handling continuous features
Discretizing into bins allows decision trees to handle continuous data effectively.
Step 2: Eliminate wrong options
One-hot encoding (A) is for categorical data; ignoring (C) loses information; using directly (D) can lead to overfitting.
Final Answer:
Option C -> Option C
Quick Check:
Continuous? Discretize into bins [OK]

Hint: Continuous? Discretize into bins [OK]

Common Mistakes:

4. How can you optimize the computation of cosine similarity for a large dataset of vectors?

hard

A. Use a recursive function to handle large datasets.

B. Use a loop to compute each pairwise similarity.

C. Precompute norms and use matrix multiplication.

D. Store vectors as lists to save memory.

Solution

Step 1: Identify computational bottlenecks
Looping over pairs is inefficient for large datasets.
Step 2: Optimize using matrix operations
Precomputing norms and using matrix multiplication reduces redundant calculations.
Final Answer:
Option C -> Option C
Quick Check:
Matrix ops reduce redundancy. [OK]

Hint: Matrix ops reduce redundancy. [OK]

Common Mistakes:

5. How can the calculation of precision, recall, and F1-score be optimized for a large confusion matrix?

hard

A. Use a more efficient data structure than a matrix.

B. Pre-compute and store results for common confusion matrices.

C. Use parallel processing to compute metrics for each class.

D. Approximate metrics using a subset of the data.

Solution

Step 1: Identify bottlenecks
Calculating metrics for each class can be parallelized.
Step 2: Choose the best optimization strategy
Parallel processing allows simultaneous computation, reducing time complexity.
Final Answer:
Option C -> Option C
Quick Check:
Parallelize class-wise computations. [OK]

Hint: Parallelize class-wise computations. [OK]

Common Mistakes:

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Implement Positional Encoding - Sinusoidal and Learned

Practice

Solution

Step 1: Analyze Dropout Operation

Step 2: Eliminate Wrong Options

Final Answer:

Quick Check:

Solution

Step 1: Analyze StepLR update mechanism

Step 2: Determine time complexity

Final Answer:

Quick Check:

Solution

Step 1: Consider handling continuous features

Step 2: Eliminate wrong options

Final Answer:

Quick Check:

Solution

Step 1: Identify computational bottlenecks

Step 2: Optimize using matrix operations

Final Answer:

Quick Check:

Solution

Step 1: Identify bottlenecks

Step 2: Choose the best optimization strategy

Final Answer:

Quick Check:

Ready to prove it?