Bird
Raised Fist0

Implement Word2Vec - Skip-Gram, Negative Sampling

CODINGadvancedInterview freq: medium
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
🤖
Implement Word2Vec - Skip-Gram, Negative Sampling
Efficiently train word embeddings using the Skip-Gram model with Negative Sampling.
codingadvancedFreq: mediumDeep Learning Coding
Prerequisites:Embeddings - Word2Vec to Contextual
📝
Problem Statement

Implement the Word2Vec Skip-Gram model with Negative Sampling from scratch. Given a corpus of text, generate word embeddings by predicting context words for a given target word using negative sampling.

I/O Specification
Input:  A list of sentences (list of list of strings), vocabulary size (int), embedding dimension (int), window size (int), number of negative samples (int).
Output: A numpy array of shape (vocabulary_size, embedding_dimension) representing the learned word embeddings.
Example
{
  "input": "[['the', 'cat', 'sat', 'on', 'the', 'mat']], vocabulary_size=6, embedding_dimension=2, window_size=1, num_negative_samples=2",
  "expected_output": "numpy array of shape (6, 2) with learned embeddings"
}
🎯
Interview Angles
  • Understanding of word embeddings and their training process using Skip-Gram.
  • Ability to optimize naive implementations using vectorized operations.
  • Handling of negative sampling efficiently to reduce computational overhead.
  • Knowledge of edge cases and how to handle them in deep learning models.
🔵
Naive Approach

The naive approach involves iterating over each word in the corpus, generating context-target pairs for each word within the specified window size, and updating the embeddings using gradient descent for each pair. This approach is computationally expensive due to the large number of updates required for each word pair.

Time complexity is O(n * m * k), where n is the number of words in the corpus, m is the average number of context words per target word, and k is the number of negative samples. Each update involves a constant number of operations, making the complexity linear in terms of the number of updates. Space complexity is O(v * d), where v is the vocabulary size and d is the embedding dimension.
Why Insufficient
O(n * m * k) is inefficient for large corpora because it requires updating embeddings for each context-target pair and negative sample, leading to excessive computation.
🐍
Naive Code
Python
import numpy as np

# Naive implementation of Word2Vec Skip-Gram with Negative Sampling

def naive_word2vec_skipgram(sentences, vocab_size, embed_dim, window_size, num_negative_samples):
    # Initialize embeddings
    W = np.random.rand(vocab_size, embed_dim)
    W_prime = np.random.rand(vocab_size, embed_dim)

    # Dummy word to index mapping
    word_to_index = {word: i for i, word in enumerate(set(word for sentence in sentences for word in sentence))}

    # Iterate over each sentence
    for sentence in sentences:
        # Iterate over each word in the sentence
        for i, target_word in enumerate(sentence):
            # Determine context window
            context_start = max(0, i - window_size)
            context_end = min(len(sentence), i + window_size + 1)
            context_words = [sentence[j] for j in range(context_start, context_end) if j != i]

            # Update embeddings for each context-target pair
            for context_word in context_words:
                # Positive sample update
                update_embeddings(W, W_prime, word_to_index[target_word], word_to_index[context_word], positive=True)

                # Negative sampling
                for _ in range(num_negative_samples):
                    negative_word = np.random.choice(vocab_size)
                    update_embeddings(W, W_prime, word_to_index[target_word], negative_word, positive=False)

    return W

# Dummy function to represent the update process
def update_embeddings(W, W_prime, target_index, context_index, positive):
    pass

# Driver example
sentences = [['the', 'cat', 'sat', 'on', 'the', 'mat']]
vocab_size = 6
embed_dim = 2
window_size = 1
num_negative_samples = 2
embeddings = naive_word2vec_skipgram(sentences, vocab_size, embed_dim, window_size, num_negative_samples)
print(embeddings)
💡
Key Insight
Use vectorized operations and efficient sampling techniques to reduce the number of updates and computations. Precompute negative samples and use matrix operations to update embeddings in batches.
🐍
Optimized Code
Python
import numpy as np

# Optimized implementation of Word2Vec Skip-Gram with Negative Sampling

def optimized_word2vec_skipgram(sentences, vocab_size, embed_dim, window_size, num_negative_samples):
    # Initialize embeddings
    W = np.random.rand(vocab_size, embed_dim)
    W_prime = np.random.rand(vocab_size, embed_dim)

    # Dummy word to index mapping
    word_to_index = {word: i for i, word in enumerate(set(word for sentence in sentences for word in sentence))}

    # Precompute negative samples
    negative_samples = np.random.choice(vocab_size, size=(len(sentences), num_negative_samples))

    # Iterate over each sentence
    for sentence_idx, sentence in enumerate(sentences):
        # Iterate over each word in the sentence
        for i, target_word in enumerate(sentence):
            # Determine context window
            context_start = max(0, i - window_size)
            context_end = min(len(sentence), i + window_size + 1)
            context_words = [sentence[j] for j in range(context_start, context_end) if j != i]

            # Vectorized update for context-target pairs
            context_indices = [word_to_index[word] for word in context_words]
            target_index = word_to_index[target_word]
            update_embeddings_vectorized(W, W_prime, target_index, context_indices, negative_samples[sentence_idx])

    return W

# Dummy function to represent the vectorized update process
def update_embeddings_vectorized(W, W_prime, target_index, context_indices, negative_indices):
    pass

# Driver example
sentences = [['the', 'cat', 'sat', 'on', 'the', 'mat']]
vocab_size = 6
embed_dim = 2
window_size = 1
num_negative_samples = 2
embeddings = optimized_word2vec_skipgram(sentences, vocab_size, embed_dim, window_size, num_negative_samples)
print(embeddings)
🔍
Line-by-Line
W = np.random.rand(vocab_size, embed_dim)
Initialize the word embeddings matrix with random values.
negative_samples = np.random.choice(vocab_size, size=(len(sentences), num_negative_samples))
Precompute negative samples for each sentence to avoid repeated sampling.
for sentence_idx, sentence in enumerate(sentences):
Iterate over each sentence to process context-target pairs.
context_start = max(0, i - window_size)
Determine the start of the context window, ensuring it doesn't go below zero.
context_indices = [word_to_index[word] for word in context_words]
Convert context words to their corresponding indices for vectorized operations.
update_embeddings_vectorized(W, W_prime, target_index, context_indices, negative_samples[sentence_idx])
Perform a vectorized update of embeddings for the target and context words, including negative samples.
⚡
Complexity
Time complexity is O(n * m + n * k), where n is the number of words in the corpus, m is the average number of context words per target word, and k is the number of negative samples. The use of vectorized operations reduces the constant factors involved in each update. Space complexity is O(v * d), where v is the vocabulary size and d is the embedding dimension.
Output
numpy array of shape (6, 2) with learned embeddings
🔲
Edge Cases
Empty Sentence List
The function returns an unmodified embeddings matrix since there are no sentences to process.
for sentence_idx, sentence in enumerate(sentences):
Single Word Sentences
No context-target pairs are generated, so embeddings remain unchanged.
context_words = [sentence[j] for j in range(context_start, context_end) if j != i]
Non-existent Words in Vocabulary
Words not in the vocabulary are ignored during processing.
word_to_index = {word: i for i, word in enumerate(set(word for sentence in sentences for word in sentence))}
⚠️
Common Mistakes
Incorrect handling of co

Practice

(1/5)
1. What is the time complexity of performing K-Fold cross-validation on a dataset with n samples and k folds?
easy
A. O(n^2)
B. O(n)
C. O(kn)
D. O(k^2n)

Solution

  1. Step 1: Analyze K-Fold process

    Each fold requires training on (k-1)/k of the data and testing on 1/k.

  2. Step 2: Eliminate wrong options

    O(n) ignores the k factor. O(n^2) and D overestimate complexity.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    K-Fold complexity is O(kn). [OK]
Hint: K-Fold complexity is O(kn). [OK]
Common Mistakes:
2. 
import numpy as np

def dcg_at_k(r, k):
    r = np.asfarray(r)[:k]
    if r.size:
        return np.sum(r / np.log2(np.arange(2, r.size + 2)))
    return 0.0

relevance_scores = [3, 2, 3, 0, 1, 2]
k = 3
print(dcg_at_k(relevance_scores, k))
What does this code output?
easy
A. 5.2618595071429155
B. 4.2618595071429155
C. 3.2618595071429155
D. 6.2618595071429155

Solution

  1. Step 1: Understand DCG Calculation

    The DCG is calculated as the sum of relevance scores divided by log base 2 of their positions.

  2. Step 2: Calculate for k=3

    For k=3, the scores are [3, 2, 3]. The calculation is 3/1 + 2/log2(3) + 3/log2(4).

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    DCG uses log2 positions. [OK]
Hint: DCG uses log2 positions. [OK]
Common Mistakes:
3. You implemented stratified K-Fold cross-validation but notice class imbalance in some folds. What is the most likely cause?
medium
A. Incorrect stratification parameter
B. Data shuffling before splitting
C. Incorrect number of splits
D. Too many folds for the dataset size

Solution

  1. Step 1: Identify stratification issue

    Stratification ensures class distribution is preserved in each fold.

  2. Step 2: Eliminate wrong options

    Incorrect number of splits and D relate to fold count, not class distribution. Data shuffling before splitting affects randomness, not stratification.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Check stratification parameter for class balance. [OK]
Hint: Check stratification parameter for class balance. [OK]
Common Mistakes:
4. How would you modify the K-Means algorithm to handle a dataset with categorical features?
medium
A. Use Euclidean distance for all features.
B. Use a different clustering algorithm like DBSCAN.
C. Ignore categorical features during clustering.
D. Convert categorical features to numerical using one-hot encoding.

Solution

  1. Step 1: Handle categorical features

    One-hot encoding converts categorical features into a numerical format suitable for K-Means.

  2. Step 2: Eliminate wrong options

    Use Euclidean distance for all features. is incorrect because Euclidean distance isn't suitable for categorical data. Ignore categorical features during clustering. is incorrect as it loses information. Use a different clustering algorithm like DBSCAN. suggests a different algorithm, not a modification.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Use one-hot encoding for categorical data. [OK]
Hint: Use one-hot encoding for categorical data. [OK]
Common Mistakes:
5. How can you optimize the NDCG calculation for large datasets?
hard
A. Use a parallel processing library to compute DCG.
B. Use a more efficient sorting algorithm.
C. Precompute log values for positions.
D. Reduce the number of relevance scores considered.

Solution

  1. Step 1: Identify Bottlenecks

    Calculating log values repeatedly can be computationally expensive.

  2. Step 2: Optimize Calculation

    Precomputing log values for positions reduces redundant calculations.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Precompute logs for efficiency. [OK]
Hint: Precompute logs for efficiency. [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