A bank's decision tree approves or declines small loans, and every applicant is entitled to an explanation. A tree is either a leaf (a label) or a dictionary {"feature": f, "threshold": t, "left": <tree>, "right": <tree>}: an applicant x goes left if x[f] <= t and right otherwise.
Write explain(tree, x, names) that returns a tuple (label, reasons): the label of the leaf that x reaches, and the list of conditions met on the way from the root, each written as f"{names[f]} <= {t}" when the applicant went left and f"{names[f]} > {t}" when they went right (with t exactly as stored in the tree).
Examples
Input: tree = {"feature": 1, "threshold": 30,
"left": {"feature": 0, "threshold": 2.5, "left": "decline", "right": "approve"},
"right": {"feature": 2, "threshold": 0.4, "left": "approve",
"right": {"feature": 0, "threshold": 6, "left": "review", "right": "approve"}}}
x = [4, 45, 0.55], names = ["years employed", "income k", "debt ratio"]
Output: ("review", ["income k > 30", "debt ratio > 0.4", "years employed <= 6"])
Input: the same tree, x = [1, 22, 0.1]
Output: ("decline", ["income k <= 30", "years employed <= 2.5"])
Input: tree = "approve", x = [3], names = ["age"]
Output: ("approve", [])
Constraints
- the tree has depth at most 30;
len(x) = len(names)
Goals
- Walk a decision tree from the root to a leaf for one example
- Record every question on the way as a readable condition
- See why trees are easy to explain