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.

In this paper the authors propose an efficient method for tree probability estimation (given a collection of trees) that relies on the description of trees as subsplit Bayesian networks. Through this representation, the authors relax the classic conditional clade distribution - which assumes that given their parent, sister clades are independent - and assume instead that given their parent subsplit, sister subsplits are independent, thus allowing more dependence structure on sister clades. The authors first present a simple maximum likelihood estimation algorithm for rooted trees, and then propose two alternatives to generalize their work to unrooted trees. They finally illustrate their method on both simulated and real-data experiments. I think this paper is very well written, in particular I have greatly appreciated the Background and SBN description sections that make use of a simple though not trivial example to introduce new notions and provide useful insights on the assumptions.

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. Papers published at the Neural Information Processing Systems Conference.