Consider a rooted ordered labeled tree that is "binary" in that there are at most two children of any vertex and whose leaves are decorated with probabilities (the sum of the leaf probabilities is unity). Is there a good dissimilarity that incorporates all of this information?

I could use a tree edit distance except for the probabilities. I could use something like the paper A Polynomial-Time Metric for Attributed Trees if I had a decent notion of what to use on the leaves. I feel like entropy of subtrees (perhaps conditional/relative) ought to be part of this story but it isn't immediately clear to me how. A literature search has yielded nothing useful.



Your Answer

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