Problem 371521 · medium · Level 03 Linear Management & Searching

Sort the Tickets by Topic

Naive Bayes · Laplace smoothing · log probabilities · text normalisation · classification

The help desk now wants every new ticket routed automatically. Train on labelled tickets and label new ones.

Write nb_classify(examples, messages), where examples is a list of (text, label) pairs and messages a list of texts, and return one label per message:

  1. Normalise every text (training and new): convert it to lower case, delete the characters . , ! ?, and split it on whitespace into words.
  2. The vocabulary is the set of all words of all training texts, V its size; N_c is the number of words in the training texts of label c and count_c(w) how often w occurs among them.
  3. The score of label c for a message is log(prior_c) plus, for every word w of the message (with repeats) that is in the vocabulary, log((count_c(w) + 1) / (N_c + V)). Words not in the vocabulary are skipped. prior_c is the share of training examples labelled c.
  4. The label with the highest score wins. Scores within 1e-9 of the highest count as tied, and among tied labels the alphabetically first wins.

The setup provides support_tickets(n, seed) (clean text) and noisy_tickets(n, seed) (with capitals and punctuation), each returning n random (text, label) pairs with labels "billing", "technical" and "delivery".

Examples

Input:  examples = [("Win cash now!", "spam"), ("free prize, win", "spam"), ("lunch at noon", "ham"),
                    ("meeting at noon?", "ham"), ("free lunch", "ham")]
        messages = ["WIN free lunch", "win cash prize", "hello"]
Output: ["ham", "spam", "ham"]
Explanation: V = 9, the spam texts have 6 words and the ham texts 8. For "WIN free lunch" spam
scores log(2/5) + log(3/15) + log(2/15) + log(1/15) = -7.249 and ham log(3/5) + log(1/17) +
log(2/17) + log(3/17) = -7.219, a narrow win for ham. "hello" is unknown, so only the priors count.

Constraints

  • 1 <= len(examples) <= 5000, 0 <= len(messages) <= 2000; every training text has at least one word
  • use math.log; the tests have no near-ties between different labels other than messages with no known words and equal priors

Goals

  • Train a Naive Bayes text classifier by counting words per class
  • Score a message by adding log prior and log word probabilities
  • Normalise text so that 'Refund!' and 'refund' are the same word
  • Skip words the model has never seen and break ties by a stated rule
Starting Python…