Bird
Raised Fist0

Implement Linear Regression - Gradient Descent from Scratch

CODINGbeginnerInterview freq: very_high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
⚖️
Batch Gradient Descent vs Stochastic Gradient Descent

When implementing linear regression from scratch, would you use batch gradient descent or stochastic gradient descent? Justify your choice.

📊
Comparison
DimensionBatch Gradient DescentStochastic Gradient Descent
Convergence StabilityHighMedium
Training SpeedSlowFast
Memory UsageHighLow
Suitability for Online LearningLowHigh
Handling Noisy DataLowMedium
✅
Verdict
Default to batch gradient descent for datasets under 10,000 samples with ample memory; switch to stochastic gradient descent for datasets over 100,000 samples or when memory is limited.
💡
Key Insight
Choose batch gradient descent for stability and stochastic gradient descent for speed and scalability.
⚠️
Interview Trap
❌ Wrong: Always use stochastic gradient descent for faster convergence.
Ignoring the stability and memory requirements of batch gradient descent for small datasets.
✅ Consider the dataset size and memory constraints; use batch gradient descent for small, clean datasets and stochastic gradient descent for large, noisy datasets.
Batch Gradient Descent
"Convergence stability due to averaging over the entire dataset"
Weaknesses
  • Slow convergence on large datasets due to processing the entire dataset per iteration
  • High memory usage as it requires loading the entire dataset into memory
  • Not suitable for online learning as it processes data in batches
  • Can get stuck in local minima if the dataset is noisy
Ideal When
  • n < 10,000
  • Memory > 16GB
  • Training time < 1 hour
  • Dataset is clean and well-conditioned
Scikit-learn's implementation of linear regression uses batch gradient descent for small datasets due to its stability and simplicity.
Stochastic Gradient Descent
"Faster convergence on large datasets due to processing one sample at a time"
Weaknesses
  • High variance in updates can lead to oscillations around the minimum
  • Less stable convergence compared to batch gradient descent
  • Requires careful tuning of learning rate and other hyperparameters
  • Can be inefficient for very small datasets due to overhead
Ideal When
  • n > 100,000
  • Limited memory < 8GB
  • Need for real-time or online learning
  • Dataset is large and noisy
Google uses stochastic gradient descent in TensorFlow for training large-scale models due to its efficiency with large datasets.
🐍
Batch Gradient Descent - Example
▼ Show
Python
import numpy as np

X = np.array([[1, 2], [3, 4], [5, 6]])
y = np.array([1, 2, 3])
weights = np.zeros(X.shape[1])
learning_rate = 0.01

for _ in range(1000):
    predictions = X.dot(weights)
    errors = predictions - y
    gradient = X.T.dot(errors) / len(y)
    weights -= learning_rate * gradient
🐍
Stochastic Gradient Descent - Example
▼ Show
Python
import numpy as np

X = np.array([[1, 2], [3, 4], [5, 6]])
y = np.array([1, 2, 3])
weights = np.zeros(X.shape[1])
learning_rate = 0.01

for _ in range(1000):
    for i in range(len(y)):
        prediction = X[i].dot(weights)
        error = prediction - y[i]
        gradient = X[i] * error
        weights -= learning_rate * gradient
✅
Use Batch Gradient Descent When
  • •n < 10,000
  • •Memory > 16GB
  • •Dataset is clean
  • •Training time < 1 hour
✅
Use Stochastic Gradient Descent When
  • •n > 100,000
  • •Limited memory < 8GB
  • •Need for online learning
  • •Dataset is noisy
↳
Nuances
  • For very large datasets, batch gradient descent can be impractical due to memory constraints.
  • Stochastic gradient descent can converge faster but may require more epochs to stabilize.
  • Batch gradient descent is more interpretable due to its stable convergence path.
  • In noisy datasets, stochastic gradient descent can escape local minima more effectively.

Practice

(1/5)
1. 
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

  1. Step 1: Understand confusion matrix structure

    The confusion matrix is structured as [[TN, FP], [FN, TP]].

  2. Step 2: Calculate values

    TN=2 (true negatives), FP=1 (false positives), FN=1 (false negatives), TP=3 (true positives).

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Confusion matrix is [[TN, FP], [FN, TP]]. [OK]
Hint: Confusion matrix is [[TN, FP], [FN, TP]]. [OK]
Common Mistakes:
2. 
import numpy as np
from scipy.spatial import distance

X_train = np.array([[1, 2], [3, 4], [5, 6]])
X_test = np.array([[1, 2]])

# Calculate distances
D = distance.cdist(X_test, X_train, 'euclidean')

print(D)
What does the above code output?
easy
A. array([[0., 2.828, 5.656]])
B. array([[0., 2., 4.]])
C. array([[0., 2.236, 4.472]])
D. array([[0., 2.828, 4.472]])

Solution

  1. Step 1: Understand the function

    The cdist function computes the distance between each pair of the two collections of inputs.

  2. Step 2: Calculate the distances

    The Euclidean distance from [1, 2] to each point in X_train is calculated as [0., 2.828, 4.472].

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Euclidean distance formula: √((x2-x1)² + (y2-y1)²) [OK]
Hint: Euclidean distance formula: √((x2-x1)² + (y2-y1)²) [OK]
Common Mistakes:
3. 
import numpy as np

confusion_matrix = np.array([[50, 10], [5, 35]])

precision = confusion_matrix[0, 0] / (confusion_matrix[0, 0] + confusion_matrix[1, 0])
recall = confusion_matrix[0, 0] / (confusion_matrix[0, 0] + confusion_matrix[0, 1])

print(f"Precision: {precision}, Recall: {recall}")
easy
A. Precision: 0.8333, Recall: 0.8333
B. Precision: 0.9091, Recall: 0.9091
C. Precision: 0.8333, Recall: 0.9091
D. Precision: 0.9091, Recall: 0.8333

Solution

  1. Step 1: Calculate Precision

    Precision is calculated as TP / (TP + FP) = 50 / (50 + 5) = 0.9091.

  2. Step 2: Calculate Recall

    Recall is calculated as TP / (TP + FN) = 50 / (50 + 10) = 0.8333.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Precision uses FP, Recall uses FN. [OK]
Hint: Precision uses FP, Recall uses FN. [OK]
Common Mistakes:
4. What does the following Python code output?
import numpy as np

def softmax(x):
    e_x = np.exp(x - np.max(x))
    return e_x / e_x.sum(axis=0)

x = np.array([2.0, 1.0, 0.1])
print(softmax(x))
easy
A. [0.659, 0.242, 0.099]
B. [0.5, 0.3, 0.2]
C. [0.665, 0.244, 0.091]
D. [0.7, 0.2, 0.1]

Solution

  1. Step 1: Calculate softmax

    Compute the exponentials of the input array after subtracting the max value for numerical stability.

  2. Step 2: Normalize

    Divide each exponential by the sum of all exponentials to get probabilities.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Softmax outputs sum to 1 [OK]
Hint: Softmax outputs sum to 1 [OK]
Common Mistakes:
5. How can you optimize the dropout layer implementation to reduce computational overhead during training?
hard
A. Use in-place operations to apply the mask.
B. Use a fixed mask for all training iterations.
C. Precompute masks for all layers before training.
D. Reduce the dropout rate to minimize mask application.

Solution

  1. Step 1: Identify Optimization Opportunities

    In-place operations reduce memory usage and computational overhead by modifying data directly.

  2. Step 2: Eliminate Wrong Options

    Use a fixed mask for all training iterations. reduces randomness, harming model performance. Precompute masks for all layers before training. increases memory usage. Reduce the dropout rate to minimize mask application. changes model behavior, not efficiency.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    In-place operations save memory and time. [OK]
Hint: In-place operations save memory and time. [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