Generalizing Tree Probability Estimation via Bayesian Networks
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.
The paper proposes to model the distribution over phylogenetic trees using a special kind of Bayesian networks called subsplit Bayesian networks(SBNs). SBN nodes can be considered as categorical random variables taking on values over possible subsplits which are partitions of the labels in the domain. Conditional probabilities in SBNs model the probability of a child node taking on a subsplit value conditioned on its parent(s) subsplit value(s). Given an SBN structure and a sample of rooted or unrooted trees, the authors use standard procedures (closed form MLE estimations for rooted trees and EM for unrooted trees) to estimate the parameters (conditional probabilities) of the SBN. The authors adopt a similar method of weight sharing in convolutional neural networks to share parameters in SBNs. The probabilities of phylogenetic trees approximated using SBNs have been shown to be more accurate compared to other methods on both synthetic and real data. I am not an expert on phylogenetics. I am familiar with Bayesian network representation, inference and learning (both with observed and latent variables). Hence, I could understand the idea of modeling the probability distribution over possible trees using SBNs. There is still room for improvements (see comments below), but compared to current methods like SRF and CCD, SBNs are more flexible and general. Hence, I am voting for an accept.  Quality: The more challenging and interesting task of structure learning of SBNs is yet to be explored. Simple tree like SBNs have been considered in the paper although it has been mentioned in section 3 that more complicated dependencies may be introduced.   More recent works than [LeCun et al. 1998] which aims to reduce the number of parameters in a model by parameter tying are by Chou, Li, et al. "On Parameter Tying by Quantization." (AAAI. 2016), and "Automatic Parameter Tying: A New Approach for Regularized Parameter Learning in Markov Networks." (AAAI 2018). I would suggest the authors to explore such works on parameter sharing in pgms. Also, no experimental evaluation was done to see the reduction in the number of parameters through sharing in the learned models.  The paper lacks a related works section. The authors might consider adding one to SM.  Clarity: Overall, the paper was not very difficult to understand. The following questions are related to the experimental section. It is not clear why \alpha was fixed in experiments with real datasets. Is any smoothing performed when estimating the parameters in the CCD/SBN CPTs? Also, what was the average number of iterations performed during EM? The reason behind the very low number of sampled trees for DS2 and DS3 should be explained. In [Larget, 2013] a much greater number of samples were generated for both the datasets.  General comments regarding notations: Subscript k missing for parent assignment in L(T_k) in line 130 Superscript (n) in EM subsection not clearly introduced.  Originality and significance: Learning the distribution over trees using a generative probabilistic model like SBN has advantages over simple SRF and CCDs. I believe other interesting probabilistic queries can be carried out on these distributions besides computing tree probabilities.    ---------------------------------------------------------------------------------------------------------- I thank the authors for answering to the reviewers questions. The authors have tried to answer all the questions, based on which I am updating the score for the paper. I would suggest the authors to include experimental results on parameter sharing in the current paper.