Tractable Learning for Complex Probability Queries
Tractable learning aims to learn probabilistic models where inference is guaranteed to be efficient. However, the particular class of queries that is tractable depends on the model and underlying representation. Usually this class is MPE or conditional probabilities Pr(x|y) for joint assignments x, y. We propose a tractable learner that guarantees efficient inference for a broader class of queries. It simultaneously learns a Markov network and its tractable circuit representation, in order to guarantee and measure tractability. Our approach differs from earlier work by using Sentential Decision Diagrams (SDD) as the tractable language instead of Arithmetic Circuits (AC). SDDs have desirable properties, which more general representations such as ACs lack, that enable basic primitives for Boolean circuit compilation. This allows us to support a broader class of complex probability queries, including counting, threshold, and parity, in polytime.
Summary of paper: The paper deals with learning SDDs (from previous work) that can be used to infer complex queries. Inference for these type of queries could not be done efficiently in previous models like the ACMNs. The paper provides details about the learning algorithm (which is similar to the ACMN learning algorithm based on greedy selection), different types of complex queries (symmetric and asymmetric that can be converted to symmetric), and experimental evaluation on real data to answer how well SDDs do and how fast they are. Complexity bounds on the inference complexity are also provided. Quality: The paper is of high quality and is well written. Did not find any errors in text or any equations. Clarity: Along with the supplemental text (description of SDDs and WMC), the paper is quite clear to follow. Suggestion but not required would be to provide similar summary text in the supplemental material for ACMN especially since you have the figure in 1(c).Originality: To the best of my knowledge, this is a novel method to learn SDDs from queries and trying to infer more difficult queries than was previously done using tractable models. Significance: Given that the paper provides another step in the direction of use of tractable models to solve even more difficult queries, there could be other ideas that could build on what is provided here.  Questions, clarifications and suggestions to improve paper:1) Are sum-product networks any better than ACMNs to solve these complex queries? If so, how would they compare against use of SDDs ?2) You use the work conjoin at multiple places, it might be help define the operator.3) In the supplementary text you mention additional unary parameters w_A and w_B ? Is there any reason they are not included in the tree 1b and 1c ? Are they not needed to be included in the SDD ?4) In Algorithm 1, you pass \alpha as a parameter. You should pass \alpha as a parameter to score(M, T) since score depends on it.5) What step of the algorithm are you doing dynamic SDD minimization ? Is it done in M.add(f) step ?6) Is it possible that the minimization or compressing can reduce the size of the SDD more in step t+2 by selecting features f1 and f2 combined compared to when you would have selected f3 and f4 sequentially in a greedy way ? i.e. does selecting features in a greedy fashion cause generating a SDD that might not be optimally minimized ?7) It would be good to have example queries where ACMN does similar to SDDs as well as asymmetric queries that are not tractable by SDDs for completeness.8) It might be better to use func() instead of # in Table 1.9) Fix opening double quotes on page 7. ... vote "yes" on a bill ...10) In the positive, negative movie review question, is there any reason you don't use all characters instead of restricting to first 750 characters ? does it affect performance and how ?11) While answering the second question posed and using complex queries on the voting and movie dataset, is there any reason you do not look at the accuracy as well as the time especially for queries that do not time out. It seemed like the Mutex queries and Complex queries you had are quite different and you didn't test for the accuracy in terms of log-likelihood on the complex queries.12) Complete the references with details (i.e. for example put in page numbers for references 3, 6, 8, 12 etc)