Implement Gradient Checking - Numerical vs Analytical Gradients

CODINGadvancedInterview freq: high

Choose your preparation mode6 modes available

Learn Trace Debug Trade-off Challenge

🤖

Verify backpropagation by comparing numerical and analytical gradients.

codingadvancedFreq: highEvaluation Coding

Prerequisites:BackpropagationBackpropagation implementation

📝

Problem Statement

Implement gradient checking to verify the correctness of backpropagation by comparing numerical gradients with analytical gradients.

I/O Specification

Input:  A function f that computes the loss given parameters, and its analytical gradient function grad_f.
Output: A boolean indicating whether the numerical and analytical gradients are approximately equal.

Example

f = lambda x: (x**2, 2*x); grad_check(f, np.array([1.0])) → True

🎯

Interview Angles

Testing understanding of numerical stability and precision issues in gradient computation.
Evaluating ability to implement vectorized operations for efficiency.
Assessing knowledge of backpropagation and its verification methods.

🔵

Naive Approach

Compute numerical gradients using the finite difference method for each parameter and compare them to the analytical gradients.

Time: O(n) - n parameters, each requiring two function evaluations. Space: O(n) - storage for numerical gradients.

Why Insufficient

O(n) because it requires two function evaluations per parameter, which is inefficient for large parameter spaces.

🐍

Naive Code

Python

import numpy as np

def grad_check(f, x, epsilon=1e-7):
    fx, grad = f(x)  # Evaluate function value at original point
    num_grad = np.zeros_like(x)
    for i in range(x.size):
        x[i] += epsilon
        fx_plus_epsilon, _ = f(x)
        x[i] -= 2 * epsilon
        fx_minus_epsilon, _ = f(x)
        x[i] += epsilon
        num_grad[i] = (fx_plus_epsilon - fx_minus_epsilon) / (2 * epsilon)
    return np.allclose(num_grad, grad, atol=1e-7)

# Driver example
f = lambda x: (np.sum(x**2), 2*x)
print(grad_check(f, np.array([1.0, 2.0])))

💡

Key Insight

Use vectorized operations to compute numerical gradients efficiently, reducing the overhead of multiple function calls.

🐍

Optimized Code

Python

import numpy as np

def grad_check(f, x, epsilon=1e-7):
    fx, grad = f(x)  # Evaluate function value at original point
    num_grad = np.zeros_like(x)
    perturb = np.zeros_like(x)
    for i in range(x.size):
        perturb[i] = epsilon
        fx_plus_epsilon, _ = f(x + perturb)
        fx_minus_epsilon, _ = f(x - perturb)
        num_grad[i] = (fx_plus_epsilon - fx_minus_epsilon) / (2 * epsilon)
        perturb[i] = 0  # Reset perturbation
    return np.allclose(num_grad, grad, atol=1e-7)

# Driver example
f = lambda x: (np.sum(x**2), 2*x)
print(grad_check(f, np.array([1.0, 2.0])))

🔍

Line-by-Line

fx, grad = f(x)

Evaluate the function and its gradient at the original point to compare later.

perturb[i] = epsilon

Create a small perturbation for the i-th parameter to compute numerical gradient.

fx_plus_epsilon, _ = f(x + perturb)

Evaluate function at x + epsilon to get the positive perturbation effect.

fx_minus_epsilon, _ = f(x - perturb)

Evaluate function at x - epsilon to get the negative perturbation effect.

num_grad[i] = (fx_plus_epsilon - fx_minus_epsilon) / (2 * epsilon)

Compute the numerical gradient using central difference.

perturb[i] = 0

Reset the perturbation for the next parameter.

return np.allclose(num_grad, grad, atol=1e-7)

Check if numerical and analytical gradients are approximately equal.

⚡

Complexity

Time: O(n) - n parameters, each requiring two function evaluations. Space: O(n) - storage for numerical gradients and perturbations.

Output

True

🔲

Edge Cases

Zero Gradient

Numerical gradient should be zero, matching the analytical gradient.

np.allclose(num_grad, grad, atol=1e-7)

Single Parameter

Handles single parameter without error.

for i in range(x.size):

⚠️

Common Mistakes

Incorrect epsilon value leading to numerical instability.

Symptom: Large discrepancies between numerical and analytical gradients.

Forgetting to reset perturbation after each parameter.

Symptom: Incorrect numerical gradients due to accumulated perturbations.

Using forward difference instead of central difference.

Symptom: Less accurate numerical gradients.

Practice

(1/5)

import numpy as np
from sklearn.metrics import confusion_matrix

y_true = [0, 1, 0, 1, 0, 1, 1]
y_pred = [0, 0, 0, 1, 1, 1, 1]

cm = confusion_matrix(y_true, y_pred)
print(cm)

What does the code output?

easy

A. [[2, 1], [1, 3]]

B. [[3, 1], [1, 2]]

C. [[2, 2], [1, 2]]

D. [[3, 0], [2, 2]]

Solution

Step 1: Understand confusion matrix structure
The confusion matrix is structured as [[TN, FP], [FN, TP]].
Step 2: Calculate values
TN=2 (true negatives), FP=1 (false positives), FN=1 (false negatives), TP=3 (true positives).
Final Answer:
Option A -> Option A
Quick Check:
Confusion matrix is [[TN, FP], [FN, TP]]. [OK]

Hint: Confusion matrix is [[TN, FP], [FN, TP]]. [OK]

Common Mistakes:

2. What is the time complexity of the K-Means clustering algorithm implemented from scratch using Lloyd's algorithm?

easy

A. O(n * k * d * i)

B. O(k^2)

C. O(n * log n)

D. O(n^2)

Solution

Step 1: Analyze the algorithm
The time complexity is determined by the number of data points (n), clusters (k), dimensions (d), and iterations (i).
Step 2: Eliminate wrong options
O(n^2) and C are incorrect as they don't account for k, d, and i. O(k^2) is incorrect because it doesn't consider n, d, and i.
Final Answer:
Option A -> Option A
Quick Check:
Consider n, k, d, and i for complexity. [OK]

Hint: Consider n, k, d, and i for complexity. [OK]

Common Mistakes:

3. Your mAP implementation is returning unusually high values. What is the most likely cause?

medium

A. Using precision instead of recall in calculations

B. Incorrect IoU threshold for positive matches

C. Not normalizing the precision values

D. Including false negatives in the precision calculation

Solution

Step 1: Identify the Symptom
High mAP values suggest too many matches are considered correct.
Step 2: Analyze Each Option
Incorrect IoU threshold for positive matches: A low IoU threshold can cause false positives to be counted as true positives, inflating mAP. Using precision instead of recall in calculations: Would affect recall, not mAP directly. Not normalizing the precision values: Would affect the scale, not the value. Including false negatives in the precision calculation: Would lower precision, not increase it.
Final Answer:
Option B -> Option B
Quick Check:
Check IoU threshold for false positives [OK]

Hint: Check IoU threshold for false positives [OK]

Common Mistakes:

4. How can you optimize the K-Means implementation to improve its performance on large datasets?

hard

A. Use the Elkan algorithm to reduce distance calculations.

B. Increase the number of iterations.

C. Decrease the number of clusters.

D. Use a smaller subset of data for training.

Solution

Step 1: Identify performance bottlenecks
The Elkan algorithm optimizes K-Means by reducing the number of distance calculations needed.
Step 2: Eliminate wrong options
Increase the number of iterations. increases computation. Decrease the number of clusters. may not be suitable for the data's natural structure. Use a smaller subset of data for training. reduces accuracy.
Final Answer:
Option A -> Option A
Quick Check:
Elkan reduces distance calculations. [OK]

Hint: Elkan reduces distance calculations. [OK]

Common Mistakes:

5. How can you optimize the memory usage of a Random Forest implementation with bagging and feature sampling?

hard

A. Use a single decision tree instead of a forest

B. Use integer data types for feature values

C. Reduce the number of features sampled per tree

D. Store trees as serialized objects on disk

Solution

Step 1: Identify Memory Optimization Techniques
Using smaller data types can significantly reduce memory usage.
Step 2: Evaluate Options
Using a single tree (A) reduces model complexity, not memory; reducing features (B) affects accuracy; serialization (D) affects storage, not runtime memory.
Final Answer:
Option B -> Option B
Quick Check:
Smaller data types save memory [OK]

Hint: Smaller data types save memory [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 Gradient Checking - Numerical vs Analytical Gradients

Practice

Solution

Step 1: Understand confusion matrix structure

Step 2: Calculate values

Final Answer:

Quick Check:

Solution

Step 1: Analyze the algorithm

Step 2: Eliminate wrong options

Final Answer:

Quick Check:

Solution

Step 1: Identify the Symptom

Step 2: Analyze Each Option

Final Answer:

Quick Check:

Solution

Step 1: Identify performance bottlenecks

Step 2: Eliminate wrong options

Final Answer:

Quick Check:

Solution

Step 1: Identify Memory Optimization Techniques

Step 2: Evaluate Options

Final Answer:

Quick Check:

Ready to prove it?