Your question is Naive Bayes From Scratch. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
Moloco's ad-ranking systems may use compact categorical features such as device type, traffic source, and placement. Implement a categorical Naive Bayes classifier from scratch to predict a label for each test example.
Given training feature rows train_X, training labels train_y, and unlabeled rows test_X, return one predicted label for every test row. Assume feature columns are categorical and represented by hashable Python values.
Use maximum a posteriori classification:
P(class | features) ∝ P(class) × ∏ P(feature_i | class)
Estimate conditional probabilities with Laplace smoothing:
P(value | class, feature_i) = (count(value, class, feature_i) + 1) / (count(class) + number_of_training_values_in_feature_i)
Perform calculations in log space to avoid numerical underflow. If a test value was never observed in a feature column, treat its count as zero while using that column's training vocabulary size in the denominator. Preserve the order of first appearance when breaking prediction ties.
Implement train_predict_naive_bayes(train_X, train_y, test_X). train_X is a non-empty list of equal-length rows, train_y contains one hashable label per training row, and test_X contains rows with the same number of features. Return a list of predicted labels.
def train_predict_naive_bayes(train_X, train_y, test_X):