- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper studies the problem of Bayesian Network structure learning under the setting of polytree structure restriction and submodular scoring function. This leads to a greedy algorithm (as many submodular optimization problems do) where the structure is guaranteed to be a 2-approximation of the optimal structure. The paper provides both theoretical results and empirical evaluation. Theoretical results are supported by proofs included in the appendix.
Critical strengths
The paper is very well written and easy to follow despite the deeply technical material.
While the problem of Bayesian Network structure learning is well studied, the authors present a novel view of the problem under specific restrictions of the structure (polytree) and score function (submodular). The former is further constrained to bounded in-degree and the latter is relaxed as an extension of the main result.
Critical weaknesses
My main concern relates to the c-approximation on the submodular score function. A well known problem with the c-approximation is that it is multiplicative and so not shift-invariant. The score function, however, is submodular. A submodular function shifted by an additive constant remains submodular. So given any scoring function satisfying the bound we can construct a new score function which does not satisfy the c-approximation bound, e.g., set to some large negative number. How is this resolved in the algorithm and Theorem 3.1?
Questions for authors
Please address the question raised above.
3 comments
My concern is less about the experiments and more about Theorem 3.1.
Thanks for responding!
We are confused by this comment: If we interpret it correctly, f is the scoring function and D_opt is an optimal solution with regard to this scoring function. Of course we can change the scoring function after running our algorithm and then the approximation factor would not necessarily hold anymore. But then our algorithm would have output something else for this modified scoring function and this output would indeed satisfy the approximation guarantee.
If you want to point out that the function could be negative in practice, indeed, this is true. As is customary in theoretical analyses of algorithms for structure learning, we deal with 0-based scoring functions in the theoretical part of the paper (see the Preliminaries, Line 124). That is, all scores are nonnegative (note that this follows from the assumption that the empty set has score 0 as all scores of supersets are wlog. larger). In this regime, the approximation guarantee holds regardless of the scoring function in the input as long as it satisfies submodularity or closeness to it. What this implies for practice is analysed in our previous comment and the appendix.
Shifting had no bad influence in our experiments
Thanks for your review!
Your concern that shifting does not preserve approximation factors is valid and we had considered it. Note that shifting to 0-based scores, as they are treated in theory, from negative scores, as they often occur in practice, can both improve or worsen approximation factors, depending on the magnitude of the shift. The short answer is that in the instances we have looked at, shifting indeed yields drastically improved approximation factors for the real (unshifted) scores from practice. This to our mind validates the prevalent theoretical point of view of 0-based scores because both the objective for approximation is stated in a cleaner way and it empirically implies guarantees for the real scores. In particular, in Appendix C we have computed what approximation factors our results and algorithms imply for the original, unshifted (negative) scores. For instance, on the adult dataset, our factor-3.36 approximation yields a factor-1.5 approximation for the original scores.