Problem 316299 · medium · Level 03 Linear Management & Searching

A Filter That Learns and Unlearns

Naive Bayes · online learning · Laplace smoothing · log probabilities · classes

A mail program sorts messages into folders and learns from the user: every time the user files a message, the filter learns from it, and when the user moves a message out of a folder again, the filter forgets that example. Write the class MailFilter:

  • MailFilter() starts with no examples.
  • learn(text, label) adds one example.
  • forget(text, label) removes one earlier example with exactly this text and label (the tests only forget examples that were learnt and not yet forgotten).
  • predict(text) returns the most likely label, or None if there are no examples.
  • probability(text, label) returns the probability of label for text (0.0 if no current example has that label, or if there are no examples).

Both are computed from the current examples only. Words are separated by single spaces. The vocabulary is the set of words occurring in current examples, V its size; for a label c with at least one current example, its score is log(n_c / n) + Σ log((count_c(w) + 1) / (N_c + V)) over the words w of the text (with repeats) that are in the vocabulary, where n_c counts its examples, n all examples, N_c the words in its examples and count_c(w) the occurrences of w among them. Probabilities are the scores turned back into probabilities, normalised over the labels with current examples. predict picks the highest score; scores within 1e-9 of it count as tied, and the alphabetically first tied label wins.

The tests call run_ops(MailFilter, ops, args); mail_session(n_ops, seed) returns a random (ops, args) session.

Examples

Input:  ops  = ["MailFilter", "learn", "learn", "predict", "learn", "forget", "predict", "probability"]
        args = [[], ["win cash", "spam"], ["team meeting", "work"], ["cash meeting meeting"],
                ["win win", "spam"], ["win cash", "spam"], ["win meeting"], ["win meeting", "spam"]]
Output: [None, None, None, "work", None, None, "spam", 0.6]
Explanation: after two examples V = 4 and both labels have 2 words. For "cash meeting meeting",
spam gets 1/2 · 2/6 · 1/6 · 1/6 and work 1/2 · 1/6 · 2/6 · 2/6, so work wins. After learning
"win win" and forgetting "win cash", the examples are "team meeting" and "win win", and "cash"
has left the vocabulary (V = 3). For "win meeting" spam gets 1/2 · 3/5 · 1/5 = 0.06 and work
1/2 · 1/5 · 2/5 = 0.04, so spam wins with probability 0.06 / 0.1 = 0.6.

Constraints

  • at most 20000 operations; texts have 1 to 10 words
  • floats are compared with a tolerance of 1e-6
  • each test must finish in well under a second in your browser: recounting all examples for every question is too slow

Goals

  • See that training Naive Bayes is counting, so it can be updated one example at a time
  • Undo the effect of an example by subtracting its counts, including the vocabulary
  • Answer predictions and probabilities from running totals without recounting
Starting Python…