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 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):