  Probability estimation is one of the fundamental tasks in statistics and
machine learning. However, standard methods for probability estimation on
discrete objects do not handle object structure in a satisfactory manner. In
this paper, we derive a general Bayesian network formulation for probability
estimation on leaf-labeled trees that enables flexible approximations which can
generalize beyond observations. We show that efficient algorithms for learning
Bayesian networks can be easily extended to probability estimation on this
challenging structured space. Experiments on both synthetic and real data show
that our methods greatly outperform the current practice of using the empirical
distribution, as well as a previous effort for probability estimation on trees.
