A ferry company logs every crossing: the wind, the tide, the visibility and the kind of day, and whether the ferry left on time, was delayed or was cancelled. Passengers want a probability for tomorrow's crossing.
records[i] is a tuple of category values (strings) and outcomes[i] its outcome. For an outcome c, let n_c be its number of records; for feature j, let K_j be the number of different values of feature j among all the records, and count_c(j, v) the number of records of outcome c whose feature j equals v.
Write nb_categories(records, outcomes, queries) that returns one dictionary per query tuple, from every outcome in outcomes to its probability. The probability of c is proportional to
(n_c / n) · Π over features j of (count_c(j, query[j]) + 1) / (n_c + K_j)
and the probabilities of one query add up to 1. A query value never seen in the log simply has count 0 for every outcome.
The setup provides ferry_log(n, seed), which returns (records, outcomes) for n random crossings with 4 features.
Examples
Input: records = [("strong", "high"), ("strong", "low"), ("calm", "low"), ("calm", "high"), ("calm", "low")]
outcomes = ["delayed", "delayed", "on time", "on time", "on time"]
queries = [("strong", "low")]
Output: [{"delayed": 0.6756756756756757, "on time": 0.32432432432432434}]
Explanation: K = 2 for both features. "delayed": 2/5 · (2+1)/(2+2) · (1+1)/(2+2) = 0.15;
"on time": 3/5 · (0+1)/(3+2) · (2+1)/(3+2) = 0.072. Divided by their sum 0.222.
Constraints
1 <= len(records) == len(outcomes) <= 10**4,0 <= len(queries) <= 1000, every record and query has the same number of features (1 to 300)- with many features the unnormalised products become extremely small; your probabilities must still be correct. Floats are compared with a tolerance of
1e-6
Goals
- Apply Naive Bayes to categorical features with add-one smoothing per feature
- Turn class scores into posterior probabilities that sum to 1
- Handle a category value never seen with a class, or never seen at all