Finding most likely tree over a semilattice

Question

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...

Answer 1

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.