0
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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, 2019 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, 2019 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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