Bird
Raised Fist0

Implement Word2Vec - Skip-Gram, Negative Sampling

CODINGadvancedInterview freq: medium
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
⚖️
Skip-Gram vs Negative Sampling

When implementing Word2Vec, would you choose Skip-Gram or Negative Sampling for training efficiency and embedding quality? Justify your choice.

📊
Comparison
DimensionSkip-GramNegative Sampling
Training SpeedSlowFast
Embedding QualityHighModerate
Memory UsageHighLow
ScalabilityModerateHigh
Ease of ImplementationModerateComplex
✅
Verdict
Default to Negative Sampling for large datasets (n > 10M) and limited resources; switch to Skip-Gram when embedding quality is paramount and resources allow.
💡
Key Insight
Choose Skip-Gram for quality, Negative Sampling for speed - balance based on dataset size and resource constraints.
⚠️
Interview Trap
❌ Wrong: Always use Negative Sampling because it's faster.
This ignores the importance of embedding quality, especially for smaller datasets where Skip-Gram excels.
✅ Consider the trade-off between training speed and embedding quality, and choose based on dataset size and resource availability.
Skip-Gram
"Produces high-quality embeddings by focusing on predicting context words for a given target word."
Weaknesses
  • Computationally expensive due to the need to update weights for all words in the vocabulary.
  • Requires significant memory for large vocabularies.
  • Slower convergence compared to Negative Sampling.
  • Less efficient for very large datasets without optimization.
Ideal When
  • n < 1M
  • vocabulary_size < 50K
  • high-quality embeddings are prioritized over training speed
  • sufficient computational resources are available
Google's original Word2Vec implementation used Skip-Gram for its ability to produce high-quality embeddings.
Negative Sampling
"Efficiently approximates the full softmax by updating only a small number of negative samples."
Weaknesses
  • May produce lower-quality embeddings if negative samples are not well-chosen.
  • Requires careful tuning of the number of negative samples.
  • Less interpretable due to the stochastic nature of sampling.
  • Potentially less stable training if negative samples are too similar to positive samples.
Ideal When
  • n > 10M
  • vocabulary_size > 100K
  • limited computational resources
  • fast training is prioritized over embedding quality
Facebook uses Negative Sampling in fastText for efficient training on large-scale text data.
🐍
Skip-Gram - Example
▼ Show
Python
import numpy as np

# Simplified Skip-Gram implementation
class SkipGram:
    def __init__(self, vocab_size, embedding_dim):
        self.vocab_size = vocab_size
        self.embedding_dim = embedding_dim
        self.W = np.random.rand(vocab_size, embedding_dim)
        self.W_prime = np.random.rand(embedding_dim, vocab_size)

    def forward(self, target_word_idx):
        h = self.W[target_word_idx]
        u = np.dot(h, self.W_prime)
        return u

    def backward(self, target_word_idx, context_word_idx, learning_rate):
        # Simplified backward pass
        h = self.W[target_word_idx]
        u = np.dot(h, self.W_prime)
        error = u - context_word_idx
        self.W_prime -= learning_rate * np.outer(h, error)
        self.W[target_word_idx] -= learning_rate * np.dot(self.W_prime, error)
🐍
Negative Sampling - Example
▼ Show
Python
import numpy as np

# Simplified Negative Sampling implementation
class NegativeSampling:
    def __init__(self, vocab_size, embedding_dim, num_neg_samples):
        self.vocab_size = vocab_size
        self.embedding_dim = embedding_dim
        self.num_neg_samples = num_neg_samples
        self.W = np.random.rand(vocab_size, embedding_dim)
        self.W_prime = np.random.rand(embedding_dim, vocab_size)

    def sample_negatives(self, target_word_idx):
        return np.random.choice(self.vocab_size, self.num_neg_samples, replace=False)

    def forward(self, target_word_idx, context_word_idx):
        negatives = self.sample_negatives(target_word_idx)
        # Simplified forward pass
        h = self.W[target_word_idx]
        positive_score = np.dot(h, self.W_prime[:, context_word_idx])
        negative_scores = np.dot(h, self.W_prime[:, negatives])
        return positive_score, negative_scores

    def backward(self, target_word_idx, context_word_idx, learning_rate):
        # Simplified backward pass
        h = self.W[target_word_idx]
        positive_score, negative_scores = self.forward(target_word_idx, context_word_idx)
        error = positive_score - 1  # Assuming binary classification
        self.W_prime[:, context_word_idx] -= learning_rate * h * error
        for neg_idx in negatives:
            neg_error = negative_scores[neg_idx] - 0
            self.W_prime[:, neg_idx] -= learning_rate * h * neg_error
        self.W[target_word_idx] -= learning_rate * (self.W_prime[:, context_word_idx] * error + np.sum(self.W_prime[:, negatives] * neg_error, axis=1))
✅
Use Skip-Gram When
  • •n < 1M
  • •vocabulary_size < 50K
  • •high-quality embeddings are critical
  • •sufficient computational resources are available
✅
Use Negative Sampling When
  • •n > 10M
  • •vocabulary_size > 100K
  • •fast training is required
  • •limited computational resources
↳
Nuances
  • For small datasets, Skip-Gram can outperform Negative Sampling in embedding quality despite slower training.
  • Negative Sampling may struggle with rare words if negative samples are not well-distributed.
  • Skip-Gram's computational cost can be mitigated with hierarchical softmax, but this adds complexity.
  • In highly parallel environments, Negative Sampling's efficiency gains are less pronounced.

Practice

(1/5)
1. What is the time complexity of computing the covariance matrix for a dataset with n samples and d features?
easy
A. O(n^2)
B. O(d^2)
C. O(nd^2)
D. O(nd)

Solution

  1. Step 1: Analyze the covariance matrix computation

    Computing the covariance matrix involves calculating pairwise covariances for d features, each requiring O(n) operations.

  2. Step 2: Eliminate wrong options

    O(n^2) is incorrect as it doesn't account for features. O(d^2) is incorrect because it ignores the sample size. O(nd^2) overestimates the complexity.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Covariance: O(nd) for n samples, d features. [OK]
Hint: Covariance: O(nd) for n samples, d features. [OK]
Common Mistakes:
2. 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:
3. You implemented early stopping in your training loop, but the model still overfits. What is the most likely reason?
medium
A. The validation set is too small.
B. The learning rate is too high.
C. The patience parameter is too low.
D. The model architecture is too simple.

Solution

  1. Step 1: Analyze early stopping behavior

    Early stopping relies on validation performance to halt training.

  2. Step 2: Identify the root cause of overfitting

    If the validation set is too small, it may not accurately reflect generalization, leading to overfitting despite early stopping.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Small validation set can mislead early stopping. [OK]
Hint: Small validation set can mislead early stopping. [OK]
Common Mistakes:
4. How would you apply sinusoidal positional encoding in a transformer model for a sequence of variable length?
medium
A. Apply encoding only to the first few positions of each sequence.
B. Apply encoding to each sequence independently, based on its length.
C. Pad all sequences to the maximum length and apply encoding.
D. Use a fixed-length encoding for all sequences, regardless of length.

Solution

  1. Step 1: Consider variable sequence lengths

    Each sequence should have positional encoding applied based on its actual length to maintain positional information.

  2. Step 2: Eliminate wrong options

    Pad all sequences to the maximum length and apply encoding. is inefficient and may introduce unnecessary padding. Apply encoding only to the first few positions of each sequence. ignores the rest of the sequence. Use a fixed-length encoding for all sequences, regardless of length. loses positional information for longer sequences.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Encode based on actual sequence length. [OK]
Hint: Encode based on actual sequence length. [OK]
Common Mistakes:
5. Which optimization would most effectively reduce the computational cost of the scaled dot-product attention mechanism for very large input sequences?
hard
A. Use a smaller batch size.
B. Use half-precision floating point operations.
C. Reduce the dimensionality of queries and keys.
D. Implement attention with sparse matrices.

Solution

  1. Step 1: Identify the bottleneck

    Computational cost is high due to dense matrix operations.

  2. Step 2: Choose the best optimization

    Sparse matrices reduce computation by focusing on non-zero elements.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Sparse matrices for large inputs [OK]
Hint: Sparse matrices for large inputs [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