If I am not mistaken, then a semilattice defines a finite set of trees, for example spanning trees.

Now assume that each semilattice edge is annotated with a transition probability. In addition, let's assume that the probability of a tree over the semilattice is the product of the probabilities of all the edges that the tree uses.

How to find the most likely spanning tree, that is the most likely hypothesis how the nodes came to be? I am unsure whether this amounts to finding a maximum spanning tree of the semilattice.

I guess this has applications in probabilistic graphical models...


The maximum spanning tree is about summing weights; maximizing the probability is about multiplying weights. To convert multiplication to sums, take the logarithm.

Hopefully that's enough for you to work out an algorithm for this task.

| cite | improve this answer | |
  • $\begingroup$ Right this is what I was wondering. Such a nice straightforward answer - I could of known myself. So Just take the log of the edge weights and do maximum spanning tree by always chosing the parent with the maximum edge as described here: cs.stackexchange.com/a/41203/111567 ? $\endgroup$ – Radio Controlled Nov 12 '19 at 12:36
  • $\begingroup$ Although, then should picking the max of the weights not be the same as picking the max of the log-weights? Or is the answer linked above incorrect? $\endgroup$ – Radio Controlled Nov 14 '19 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.