A Variational Bayesian EM Algorithm for Tree Similarity

In recent times, a vast amount of tree-structured data has been generated. For mining, retrieving, and integrating such data, we need a fine-grained tree similarity measure that can be adapted to objective data. To achieve this goal, this paper (1) proposes a probabilistic generative model that generates pairs of similar trees, and (2) derives a learning algorithm for estimating the parameters of the model based on the variational Bayesian expectation maximization (VBEM) method. This method can handle rooted, ordered, and labeled trees. We show that the tree similarity model obtained via the BEM technique performs better than that obtained via maximum likelihood estimation by tuning the hyper parameters.