Naive Bayes
Naive Bayes
Naive Bayes is a probabilistic classifier based on Bayes' Theorem. It makes the 'naive' assumption that features are conditionally independent of each other given the class label, which simplifies joint probability calculation and enables fast training speeds on large datasets.
Complexity Profile
| Case | Complexity |
|---|---|
| Best Case | O(N * D) |
| Average Case | O(N * D) |
| Worst Case | O(N * D) |
| Space Complexity | O(C * D) |
Code Implementation
# Conceptual Naive Bayes Classifier equation
# P(y | X) = [ P(X | y) * P(y) ] / P(X)
# Under independent feature assumption:
# P(y | x1, ..., xn) proportional to P(y) * Prod( P(xi | y) )
def calculate_naive_bayes_posterior(class_prior, feature_likelihoods, input_features):
score = math.log(class_prior)
for idx, feature_val in enumerate(input_features):
# Add logs of conditional likelihoods to prevent underflow
score += math.log(feature_likelihoods[idx].get(feature_val, 1e-6))
return scoreReal-World Applications
- Email spam filtering (e.g. classifying text as spam or ham).
- Sentiment analysis in social feeds.
- Real-time multi-class classification tasks.
Linear Regression
Linear Regression is a supervised learning algorithm that models the relationship between a dependent variable ($Y$) and independent variables ($X$) by fitting a linear equation to observed data. It optimizes the slope coefficients by minimizing the Mean Squared Error (MSE) using Ordinary Least Squares (OLS) or Gradient Descent.
Dynamic Programming
Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler, overlapping subproblems. It solves subproblems once and stores their solutions using Memoization (Top-down) or Tabulation (Bottom-up), trading memory to optimize computational speed.