# Top leaves in a tree with probabilities on edges

Suppose I had a tree, where each edge had a probability assigned to it, and the probabilities all of the edges coming from a node sum up to 1. You could consider these probabilities to come a machine learning model that's trying to recommend items in a hierarchy (say for an online liquor and snacks shop).

One way to choose what to show a customer would be to at each node, traverse the edge with the highest probability, and end when you're at a leaf node. In the example below, that would suggest you recommend the customer "chips."

My question is, given such a hierarchy, how would you determine what the 2nd or 3rd best choices are? As in, if you wanted to show the customer 3 items, what would you show? I'm not sure how to formulate that mathematically, and if there is some graph-theory concept that covers this. I'm also not sure this is well defined.

Thank you!

• I think that you are right, that the problem is that you haven't defined what is meant by "second best choice" (or "$n$th best choice" in general). It may be that once you've defined that, the algorithm for finding it is trivial, or it could be something that requires some thought. It's hard to say in general. – Brian Tung Apr 23 at 21:54
• I'm not convinced that your "best choice" algorithm is correct in general. In this tree, if "chips" splits further into 100 brands of chips each with 0.01 probability, then it may be best to recommend "wine" (with probability 0.2) rather than any brand of chips (with probability 0.0063). – Misha Lavrov Apr 24 at 5:06

All items can be identified with nodes with out-degree equal to $$0$$ in your model. Let us call these nodes item-nodes $$i_j$$. For each item-node $$i_j$$, there is a unique path $$(r,...,i_j)$$ from the root node $$r$$ to $$i_j$$. By "walking" along such a path and consecutively multyplying the probabilities associated with the path egdes, one can assign a probability $$p_{i_j}$$to each item-node $$i_j$$. For example, in the case of "chips", this probability would be $$0.7*0.9 = 0.63$$. The probabilities $$p_{i_j}$$ can then be used to rank-order the item-nodes $$i_j$$.