Two Symptoms, Two Answers

A garden centre keeps records of the plants brought to its help desk. Each record is a pair (problem, signs), where problem is the diagnosis (for example "aphids", "mildew" or "healthy") and signs is a tuple of observations such as ("yellow", "sticky", "spots"), each one a string. All tuples have the same length, and position i always means the same observation.

A new plant arrives with the observations query (a tuple of the same length). Write naive_or_joint(records, query) that returns a tuple (joint, naive) of two dictionaries from each problem (every problem in records) to its probability given query:

• joint uses only the records whose signs equal query in every position: the share of each problem among them. If no record matches, joint is None.
• naive treats the observations as independent once the problem is known. For each problem c, multiply P(c) (its share of all records) by P(signs[i] == query[i] | c) for every position i (the share of c's records with that value), then divide the products by their sum. If every product is 0, naive is None.

Examples

Input:  records = [("aphids", ("yellow", "sticky")), ("aphids", ("yellow", "sticky")),
                   ("aphids", ("green", "dry")), ("mildew", ("yellow", "dry")),
                   ("mildew", ("green", "sticky")), ("healthy", ("green", "dry"))],
        query = ("yellow", "sticky")
Output: ({"aphids": 1.0, "mildew": 0.0, "healthy": 0.0},
         {"aphids": 0.7272727272727273, "mildew": 0.2727272727272727, "healthy": 0.0})
Explanation: both records with exactly ("yellow", "sticky") are aphids. The naive
product for aphids is 3/6 · 2/3 · 2/3 = 2/9, for mildew 2/6 · 1/2 · 1/2 = 1/12, for
healthy 0; normalised, 8/11 and 3/11.

Constraints

• 1 <= len(records) <= 5 * 10**4; 1 to 10 observations per record; at most 20 different problems
• floats are compared with a tolerance of 1e-6

The setup provides help_desk(n, seed), which returns n random records with three observations each, in which some observations tend to occur together.

Goals

• Estimate a posterior over classes directly from the records that match every feature
• Estimate it again assuming the features are independent given the class
• See when the independence assumption helps (no matching records) and when it misleads