Bird
Raised Fist0

Implement Cosine Similarity and Euclidean Distance

CODINGbeginnerInterview freq: very_high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
⚖️
Cosine Similarity vs Euclidean Distance

When comparing two high-dimensional vectors, would you use cosine similarity or Euclidean distance? Justify your choice.

📊
Comparison
DimensionCosine SimilarityEuclidean Distance
Accuracy on high-dimensional dataHighLow
Sensitivity to magnitudeLowHigh
Computational efficiencyModerateHigh
InterpretabilityModerateHigh
ScalabilityHighLow
✅
Verdict
Default to cosine similarity for high-dimensional, sparse data where direction matters more than magnitude. Switch to Euclidean distance when dealing with low-dimensional, dense data where absolute differences are crucial.
💡
Key Insight
Cosine similarity excels in high-dimensional spaces by focusing on direction, while Euclidean distance is better for low-dimensional spaces where magnitude matters.
⚠️
Interview Trap
❌ Wrong: Always use cosine similarity for any vector comparison.
This ignores the importance of magnitude in certain contexts, such as physical measurements.
✅ Consider the nature of the data and whether magnitude differences are meaningful before choosing between cosine similarity and Euclidean distance.
Cosine Similarity
"Measures orientation rather than magnitude, making it ideal for text and high-dimensional data."
Weaknesses
  • Ignores magnitude differences, which can be crucial in some contexts.
  • Less intuitive for small datasets where magnitude matters.
  • Can be computationally expensive for very large datasets due to normalization.
Ideal When
  • n > 10,000
  • d > 100
  • When vector magnitudes are not meaningful
  • When comparing text embeddings
Spotify uses cosine similarity to recommend songs based on user listening history, focusing on the direction of user preferences rather than the magnitude.
Euclidean Distance
"Captures absolute differences in magnitude, making it suitable for spatial and physical measurements."
Weaknesses
  • Sensitive to scale and magnitude differences.
  • Not ideal for high-dimensional data due to the curse of dimensionality.
  • Can be misleading when data is sparse.
Ideal When
  • n < 10,000
  • d < 50
  • When absolute differences are meaningful
  • When data is dense and well-scaled
Google Maps uses Euclidean distance to calculate the shortest path between two points on a map, where absolute distances are crucial.
🐍
Cosine Similarity - Example
▼ Show
Python
import numpy as np

def cosine_similarity(a, b):
    dot_product = np.dot(a, b)
    norm_a = np.linalg.norm(a)
    norm_b = np.linalg.norm(b)
    return dot_product / (norm_a * norm_b)

# Example usage
vec1 = np.array([1, 2, 3])
vec2 = np.array([4, 5, 6])
print(cosine_similarity(vec1, vec2))
🐍
Euclidean Distance - Example
▼ Show
Python
import numpy as np

def euclidean_distance(a, b):
    return np.linalg.norm(a - b)

# Example usage
vec1 = np.array([1, 2, 3])
vec2 = np.array([4, 5, 6])
print(euclidean_distance(vec1, vec2))
✅
Use Cosine Similarity When
  • •n > 10,000 and d > 100
  • •When comparing text or document embeddings
  • •When vector magnitudes are not meaningful
✅
Use Euclidean Distance When
  • •n < 10,000 and d < 50
  • •When absolute differences are meaningful
  • •When data is dense and well-scaled
↳
Nuances
  • For high-dimensional text data, cosine similarity often outperforms Euclidean distance due to its focus on direction.
  • In low-dimensional, dense datasets, Euclidean distance provides more intuitive results by considering magnitude.
  • Cosine similarity can be misleading if vector magnitudes carry significant meaning, such as in physical measurements.

Practice

(1/5)
1. What is the time complexity of a single update step in Mini-Batch SGD with Momentum for a model with n parameters?
easy
A. O(n)
B. O(n log n)
C. O(n^2)
D. O(1)

Solution

  1. Step 1: Identify operations involved

    Each update step involves computing the gradient and updating the velocity and parameters, all of which are linear operations with respect to the number of parameters.

  2. Step 2: Determine the complexity

    Since each operation is linear, the overall complexity is O(n).

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Each parameter update is linear in complexity [OK]
Hint: Each parameter update is linear in complexity [OK]
Common Mistakes:
2. A decision tree implementation is producing only one node. What is the most likely cause?
medium
A. The stopping criteria are too strict.
B. The information gain threshold is too low.
C. The dataset is too small.
D. The tree depth is set too high.

Solution

  1. Step 1: Identify stopping criteria issue

    Strict stopping criteria prevent further splits, causing a single node.

  2. Step 2: Eliminate wrong options

    Small dataset (A) or low threshold (C) would still allow splits; high depth (D) is irrelevant here.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Single node? Check stopping criteria [OK]
Hint: Single node? Check stopping criteria [OK]
Common Mistakes:
3. 
import numpy as np

# Backpropagation for a single neuron
inputs = np.array([1.0, 2.0, 3.0])
weights = np.array([0.2, 0.8, -0.5])
bias = 2.0
learning_rate = 0.01

d_output = np.array([1.0])  # Gradient of loss w.r.t output

# Incorrect gradient calculation
weights_gradient = d_output * inputs
weights -= learning_rate * weights_gradient
print(weights)
medium
A. Weights are updated correctly.
B. Weights are updated incorrectly due to incorrect learning rate.
C. Weights are not updated; learning rate is too small.
D. Weights are updated incorrectly due to missing chain rule.

Solution

  1. Step 1: Identify error in gradient calculation

    The code incorrectly applies the gradient directly without considering the chain rule.

  2. Step 2: Correct approach

    Should multiply by the derivative of the activation function.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Always apply chain rule in backpropagation [OK]
Hint: Always apply chain rule in backpropagation [OK]
Common Mistakes:
4. In the context of implementing linear regression with gradient descent, how would you handle a dataset with missing values?
medium
A. Impute missing values using the mean of each feature.
B. Ignore missing values during training.
C. Replace missing values with zeros.
D. Remove any samples with missing values.

Solution

  1. Step 1: Consider impact of missing values

    Ignoring or zero-filling can bias results; removing samples reduces data.

  2. Step 2: Choose appropriate imputation

    Mean imputation is a common strategy that maintains dataset size and reduces bias.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Mean imputation balances bias and data retention. [OK]
Hint: Mean imputation balances bias and data retention. [OK]
Common Mistakes:
5. A logistic regression model is not converging during training. Which line in the code is most likely causing the issue?
import numpy as np

# Initialize weights
weights = np.zeros((m, 1))

# Training loop
for epoch in range(epochs):
    # Compute predictions
    predictions = 1 / (1 + np.exp(-np.dot(X, weights)))
    
    # Compute gradient
    gradient = np.dot(X.T, (predictions - y)) / n
    
    # Update weights
    weights -= learning_rate * gradient
medium
A. weights -= learning_rate * gradient
B. predictions = 1 / (1 + np.exp(-np.dot(X, weights)))
C. weights = np.zeros((m, 1))
D. gradient = np.dot(X.T, (predictions - y)) / n

Solution

  1. Step 1: Identify potential issues

    Convergence issues often arise from incorrect weight updates or learning rate problems.

  2. Step 2: Analyze weight update line

    If learning_rate is too high, weights update too aggressively, causing divergence.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Check learning rate in weight updates [OK]
Hint: Check learning rate in weight updates [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