Bird
Raised Fist0

Implement Naive Bayes - Gaussian and Multinomial

CODINGintermediateInterview freq: medium
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
🤖
Implement Naive Bayes - Gaussian and Multinomial
Master Naive Bayes by implementing Gaussian and Multinomial variants from scratch.
codingintermediateFreq: mediumClassical ML Coding
Prerequisites:Naive Bayes - Conditional Independence
📝
Problem Statement

Implement Naive Bayes classifiers for both Gaussian and Multinomial distributions from scratch. The function should take training data and labels, and predict labels for new data points.

I/O Specification
Input:  X_train: np.ndarray, y_train: np.ndarray, X_test: np.ndarray
Output: np.ndarray (predicted labels for X_test)
Example
X_train = np.array([[1, 2], [2, 3], [3, 4]]), y_train = np.array([0, 1, 0]), X_test = np.array([[1, 2], [3, 3]]) → np.array([0, 0])
🎯
Interview Angles
  • Testing understanding of conditional independence assumptions in Naive Bayes.
  • Evaluating ability to implement probabilistic models from scratch without libraries.
  • Assessing knowledge of handling numerical stability in probability computations.
  • Understanding of vectorization to optimize performance in machine learning algorithms.
🔵
Naive Approach

For Gaussian Naive Bayes, calculate the mean and variance for each feature per class. For Multinomial Naive Bayes, calculate the frequency of each feature per class. Use these statistics to compute the likelihood of each class for a given test point and predict the class with the highest likelihood.

Time complexity: O(n * m * c) where n is the number of samples, m is the number of features, and c is the number of classes. Space complexity: O(m * c) for storing parameters.
Why Insufficient
The naive approach recalculates probabilities for each test instance separately, leading to redundant computations, especially for large datasets.
🐍
Naive Code
Python
import numpy as np

class NaiveBayesNaive:
    def __init__(self, distribution='gaussian'):
        self.distribution = distribution

    def fit(self, X, y):
        self.classes = np.unique(y)
        self.parameters = {}
        for c in self.classes:
            X_c = X[y == c]
            if self.distribution == 'gaussian':
                self.parameters[c] = {'mean': X_c.mean(axis=0), 'var': X_c.var(axis=0), 'prior': X_c.shape[0] / X.shape[0]}
            elif self.distribution == 'multinomial':
                self.parameters[c] = {'prior': X_c.shape[0] / X.shape[0], 'likelihood': (X_c.sum(axis=0) + 1) / (X_c.sum() + X.shape[1])}

    def predict(self, X):
        predictions = [self._predict_single(x) for x in X]
        return np.array(predictions)

    def _predict_single(self, x):
        posteriors = []
        for c in self.classes:
            if self.distribution == 'gaussian':
                mean = self.parameters[c]['mean']
                var = self.parameters[c]['var']
                prior = np.log(self.parameters[c]['prior'])
                likelihood = -0.5 * np.sum(np.log(2. * np.pi * var)) - 0.5 * np.sum(((x - mean) ** 2) / var)
            elif self.distribution == 'multinomial':
                prior = np.log(self.parameters[c]['prior'])
                likelihood = np.sum(x * np.log(self.parameters[c]['likelihood']))
            posteriors.append(prior + likelihood)
        return self.classes[np.argmax(posteriors)]

# Driver example
X_train = np.array([[1, 2], [2, 3], [3, 4]])
y_train = np.array([0, 1, 0])
X_test = np.array([[1, 2], [3, 3]])
model = NaiveBayesNaive(distribution='gaussian')
model.fit(X_train, y_train)
print(model.predict(X_test))
💡
Key Insight
Precompute class-specific statistics and use vectorized operations to evaluate the likelihoods for all test instances simultaneously, reducing redundant calculations.
🐍
Optimized Code
Python
import numpy as np

class NaiveBayesOptimized:
    def __init__(self, distribution='gaussian'):
        self.distribution = distribution

    def fit(self, X, y):
        self.classes = np.unique(y)
        self.parameters = {}
        for c in self.classes:
            X_c = X[y == c]
            if self.distribution == 'gaussian':
                self.parameters[c] = {'mean': X_c.mean(axis=0), 'var': X_c.var(axis=0), 'prior': X_c.shape[0] / X.shape[0]}
            elif self.distribution == 'multinomial':
                self.parameters[c] = {'prior': X_c.shape[0] / X.shape[0], 'likelihood': (X_c.sum(axis=0) + 1) / (X_c.sum() + X.shape[1])}

    def predict(self, X):
        if self.distribution == 'gaussian':
            return self._predict_gaussian(X)
        elif self.distribution == 'multinomial':
            return self._predict_multinomial(X)

    def _predict_gaussian(self, X):
        posteriors = []
        for c in self.classes:
            mean = self.parameters[c]['mean']
            var = self.parameters[c]['var']
            log_prior = np.log(self.parameters[c]['prior'])
            log_likelihood = -0.5 * np.sum(np.log(2. * np.pi * var)) - 0.5 * np.sum(((X - mean) ** 2) / var, axis=1)
            posteriors.append(log_prior + log_likelihood)
        return self.classes[np.argmax(posteriors, axis=0)]

    def _predict_multinomial(self, X):
        posteriors = []
        for c in self.classes:
            prior = np.log(self.parameters[c]['prior'])
            likelihood = np.sum(X * np.log(self.parameters[c]['likelihood']), axis=1)
            posteriors.append(prior + likelihood)
        return self.classes[np.argmax(posteriors, axis=0)]

# Driver example
X_train = np.array([[1, 2], [2, 3], [3, 4]])
y_train = np.array([0, 1, 0])
X_test = np.array([[1, 2], [3, 3]])
model = NaiveBayesOptimized(distribution='gaussian')
model.fit(X_train, y_train)
print(model.predict(X_test))
🔍
Line-by-Line
self.classes = np.unique(y)
Identify unique classes in the training labels to iterate over each class.
X_c = X[y == c]
Select samples belonging to the current class to compute class-specific statistics.
mean = self.parameters[c]['mean']
Retrieve precomputed mean for the current class to use in likelihood calculation.
log_likelihood = -0.5 * np.sum(np.log(2. * np.pi * var)) - 0.5 * np.sum(((X - mean) ** 2) / var, axis=1)
Compute the log likelihood for Gaussian distribution using vectorized operations over all test samples.
return self.classes[np.argmax(posteriors, axis=0)]
Select the class with the highest posterior probability for each test sample.
⚡
Complexity
Time complexity: O(n * m * c) - n samples, m features, c classes. Space complexity: O(m * c) for storing parameters. Vectorization reduces constant factors.
Output
[0 0]
🔲
Edge Cases
Empty Training Data
The model should handle empty training data gracefully without crashing.
if len(y) == 0: raise ValueError('Training data is empty')
Single Feature
The model should correctly compute probabilities even with a single feature.
np.sum(((X - mean) ** 2) / var, axis=1)
⚠️
Common Mistakes
Incorrectly computing variance as standard deviation.
Symptom: Results in incorrect likelihood calculations and poor predictions.
Forgetting to add Laplace smoothing in Multinomial Naive Bayes.
Symptom: Zero probabilities for unseen features in test data.
Not using log probabilities, leading to numerical underflow.
Symptom: Probabilities become zero due to multiplication of small numbers.
Misaligning dimensions in vectorized operations.
Symptom: Shape mismatch errors during execution.

Practice

(1/5)
1. 
import numpy as np

X = np.array([[1, 2], [3, 4], [5, 6]])
X_meaned = X - np.mean(X, axis=0)
cov_matrix = np.cov(X_meaned, rowvar=False)
print(cov_matrix)
What does this code output?
easy
A. A 2x3 covariance matrix
B. A 3x3 covariance matrix
C. A 2x2 covariance matrix
D. A 3x2 covariance matrix

Solution

  1. Step 1: Understand the covariance matrix calculation

    The covariance matrix is calculated for the features (columns) of the dataset.

  2. Step 2: Eliminate wrong options

    A 3x3 covariance matrix is incorrect because the covariance matrix is not 3x3 for a 2-feature dataset. A 2x3 covariance matrix and D are incorrect because covariance matrices are square.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Covariance matrix is square, size = features. [OK]
Hint: Covariance matrix is square, size = features. [OK]
Common Mistakes:
2. What does the following Python code output when computing the ROC curve? 
from sklearn.metrics import roc_curve
import numpy as np

y_true = np.array([0, 0, 1, 1])
y_scores = np.array([0.1, 0.4, 0.35, 0.8])
fpr, tpr, thresholds = roc_curve(y_true, y_scores)
print(fpr, tpr, thresholds)
easy
A. array([0. , 0.5, 0.5, 1. ]), array([0. , 0. , 1. , 1. ]), array([1.8, 0.8, 0.4, 0.1])
B. array([0. , 0. , 0.5, 1. ]), array([0. , 0.5, 1. , 1. ]), array([0.8, 0.4, 0.35, 0.1])
C. array([0. , 0.5, 1. ]), array([0. , 0.5, 1. ]), array([0.8, 0.35, 0.1])
D. array([0. , 0.5, 1. ]), array([0. , 1. , 1. ]), array([0.8, 0.35, 0.1])

Solution

  1. Step 1: Understand ROC curve output

    The ROC curve function returns false positive rates (fpr), true positive rates (tpr), and thresholds.

  2. Step 2: Analyze the code

    Given the scores and true labels, the ROC curve is calculated correctly, resulting in fpr, tpr, and thresholds as in array([0. , 0.5, 1. ]), array([0. , 0.5, 1. ]), array([0.8, 0.35, 0.1]).

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    ROC curve outputs fpr, tpr, thresholds [OK]
Hint: ROC curve outputs fpr, tpr, thresholds [OK]
Common Mistakes:
3. In which scenario is gradient checking most useful?
medium
A. When implementing a new custom layer in a neural network.
B. When training a model with a large dataset.
C. When optimizing hyperparameters.
D. When deploying a model to production.

Solution

  1. Step 1: Identify scenarios where gradient checking is applicable

    Gradient checking is crucial when implementing new components to ensure correctness.

  2. Step 2: Eliminate unrelated scenarios

    Options A, C, and D are not directly related to verifying gradient correctness.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Use gradient check for new components. [OK]
Hint: Use gradient check for new components. [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. How can you optimize a KD-Tree implementation for a KNN classifier to handle large datasets more efficiently?
hard
A. Increase the number of dimensions.
B. Use approximate nearest neighbors.
C. Use a balanced KD-Tree.
D. Reduce the number of data points.

Solution

  1. Step 1: Identify optimization strategies

    Approximate nearest neighbors can significantly speed up queries in large datasets.

  2. Step 2: Evaluate other options

    A: Balancing helps but isn't enough for large datasets. B: Increasing dimensions worsens performance. D: Reducing data points isn't always feasible.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Approximate neighbors speed up KD-Tree [OK]
Hint: Approximate neighbors speed up KD-Tree [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