The Words That Give a Ticket Away

The help desk wants to understand its classifier: which words push a ticket most strongly towards one topic? For a topic label, compare the tickets with that label (in) with all the other tickets together (rest).

Normalise nothing: the words of a text are separated by single spaces. The vocabulary is the set of all words of all examples, V its size. N_in and N_rest are the total numbers of words in the two groups, and a(w) and b(w) how often w occurs in them. The evidence of a word is

log( ((a(w) + 1) / (N_in + V)) / ((b(w) + 1) / (N_rest + V)) )

Write telltale_words(examples, label, k) that returns a list of the k vocabulary words with the largest evidence as (word, evidence) pairs, largest first (all words if there are fewer than k). Words whose evidence is mathematically equal are ordered alphabetically; compare evidences exactly, not as rounded floats.

The setup provides support_tickets(n, seed), which returns n random (text, label) pairs with labels "billing", "technical" and "delivery".

Examples

Input:  examples = [("refund my payment", "billing"), ("refund refund please", "billing"),
                    ("my app crashed", "technical")]
        label = "billing", k = 3
Output: [("refund", 1.0986122886681098), ("payment", 0.4054651081081645), ("please", 0.4054651081081645)]
Explanation: V = 6, N_in = 6 and N_rest = 3. "refund" occurs 3 times in and never outside:
log((4/12) / (1/9)) = log 3. "payment" and "please" both give log((2/12) / (1/9)) = log 1.5 and
are ordered alphabetically. "my" gives log((2/12) / (2/9)), which is negative.

Constraints

• 2 <= len(examples) <= 5000; at least one example has the label and at least one does not
• 1 <= k <= 1000; floats are compared with a tolerance of 1e-6

Goals

• Measure how strongly a word points to one class with a smoothed log ratio
• Compare a class with all other classes combined
• Rank words exactly, with a stated tie-break