- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The paper takes advantage of the chain graph structure of Logical Credal Networks (LCNs) to reformulate inference as a credal network problem. Specifically, three approximate inference algorithms are put forth based on variable elimination, interval-valued message passage, and coordinate descent for computing posterior probability bounds. An exact inference method based on junction tree propagation (JTP) can solve substantially smaller nonlinear programs. Some theoretical results are obtained and experimental results are promising.
Critical strengths
As only one approximate inference algorithm (ARIEL) exists for Logical Credal Networks, studying and proposing new exact and approximate inference algorithms is a worthy direction. The paper puts for not one, but multiple methods for LCN inference.
Critical weaknesses
Major Concerns
- The paper does not provide a single formal algorithm specification or a proof of any theoretical claim in the main text, making it difficult to assess the novelty, correctness, and technical contributions of the proposed methods.
In S3.4 Credal Variable Elimination, no formal algorithm is provided. Instead, the proposed method is described using two paragraphs on p5.
In S3.5, Interval Belief Propagation, no formal algorithm is provided. Instead, the proposed method is described with one half of p6.
In S3.6, Coordinate Descent with Variable Elimination (CDVE), no formal algorithm is presented. Only one paragraph is used to describe the new approach.
In S4, Credal Junction Tree (CJT) is introduced without a formal algorithm. Instead, one half of a page is used to describe the method on p7.
Some of these appear incremental. For example, CDVE only requires one paragraph to describe. Similarly, CJT reads just like classical JTP. CJTP moralizes and then triangulates, producing a chordal graph. It constructs a junction tree satisfying the running intersection property. It assigns distributions over the cliques.
Likewise, no formal proofs of Theorems 1–6 are provided in the main text.
Experimental Evaluation
On p7, only Random LCNs with a moralized treewidth less than or equal to 3 (at most two parents per atom) are considered. While the text continues by stating that topologies both large and small are constructed, the critical issue is treewidth. Thus, having a "large" network but capping the treewidth at 3 is not interesting. Does this method scale to cases where the treewidth is larger than 3?
In [Darwiche, 2009], it is argued that treewidth can be overcome in some cases when the network involves a lot of determinism. In these cases, a network can be compiled into an arithmetic circuit even when the treewidth is high. How does the proposed method relate to this arithmetic circuit approach?
- Weak Writing
The writing is not always precise. For instance, the Abstract simply states that the paper establishes theoretical properties of the proposed methods and shows substantial speedups over existing methods.
The organization could be better. It is strange to have Section S3.1 Credal Networks on p4, yet earlier have Section S2.1 Logical Credal Networks on p2. Perhaps it would be better to first define Credal Networks and then later define Logical Credal Networks.
Proposition 2 just appears. It is never introduced.
Similarly, there is no introduction to Theorem 1, which also just appears. There is no connecting sentence leading from Theorem 1 to Theorem 2. Instead, Theorem 2 just appears in the text after Theorem 1.
In fact, no formal theorem is ever introduced (Theorems 1-6). They all just appear in the text.
Should Credal Junction Tree (CJT) not instead be called Credal Junction Tree Propagation (CJTP)? The issue is that a junction tree is a type of graph, while junction tree propagation is a class of inference algorithms. The paper introduces CJT, which sounds like a type of graph, yet says it is for probabilistic inference.
Why is the complexity of CJT not given a numbered theorem like IBP and CVE?
The writing in S5 Experiments is choppy and unnatural. I counted 10 colons, not to mention the many semicolons and dashes.
I don't quite follow the significance of the lack of an acyclicity requirement mentioned on p1. In Fig 1, the cyclicity is between a pair of nodes C and D. Maybe it would be better to show a longer cycle. Then in the experimental results reported in Table 1, three of the six networks are classical Bayesian networks where acyclicity holds.
On p2, I find the phrases \psi to \psi and \phi to \phi strange. Maybe it would be clearer to introduce notation to represent formula nodes such as v_{\psi}.
Some citations are lacking or misattributed. For instance, while variable elimination (VE) is attributed to Dechter 2003, it is perhaps better to add (Zhang and Poole, 1996) at the very least. For example, (Zhang and Poole, 1996) is the sole citation for VE in the Koller and Friedman reference. Similarly, the running intersection property (RIP) was also attributed to Dechter 2003, whereas it could have been attributed to a number of references published in the 1980s.
References are listed inconsistently. Compare the first two references and you notice that even papers published in the same journal (IJAR) are shown differently. More generally, journal papers are listed differently (compare IJAR versus JMLR). Conference papers are listed inconsistently. Once again, two IJCAI papers are presented differently.
On a lesser note, calling the new method Interval Belief Propagation (IBP) will cause confusion in the community, since Iterative Belief Propagation (IBP) is already used in the literature [Darwiche, 2009].
Undefined Notation
p2 undefined notation: P
p2 undefined notation: l
p2 undefined notation: u
p2 undefined notation: (X \perp !!! \perp Y | Z)
p2 undefined notation: atoms(s)
p3 undefined notation: C
p3 undefined terminology: projection
Notation Drift
Boldface X is defined as a set of binary variables in S2.1 on p2, redefined as a set of random variables in S2.2 on p3, and changed again as a set of discrete variables with finite domains in S3.1 on p4.
G is a primal graph in S2.1 on p2, redefined as another type of graph in S2.2 on p3, and changed again as a DAG in S3.1 on p4.
pa(X_i) is defined as the parents of a propositional node in S2.1 on p2, then redefined as the parents of a node corresponding to a variable in S2.2 on p3, and then defined as the parents of a node in a DAG in S3.1 on p4.
Typos
- missing period in Eq. (4)
Questions for authors
- How does the proposed method relate to Darwiche's arithmetic circuit approach? In particular, discuss how your approach is better than the arithmetic circuit approach for overcoming high treewidth.
Rebuttal
No formal algorithms or proofs in the main text. Formal pseudocode is given for every method: Alg. 1 (CJT, App. B), Alg. 2 (CVE, App. F.5), Alg. 3 (IVBP, App. G.2) and Alg. 4 (CDVE, App. H). Full proofs are in Apps. C.2 (CJT), E (compilation), F.8, G.4 and H.2. Within the 10-page limit, the main text gives the key results with proof sketches:
App. A.1 adds a dependency map of all results.
Incrementality; CJT reads like classical junction-tree propagation. CVE, IVBP and CDVE are adaptations, and §4.3 now presents them as such. CJT shares the junction-tree structure with classical JTP but differs in what it computes.
Treewidth capped at 3; does the method scale beyond it? The
ktreesets have treewidth exactly 3, and the DAG sets ≤3. CJT's largest clusters have 2–8 atoms (§5). These sets were designed to separate the dependence on n from the 2n joint, and they show that CJT certifies exact bounds at n=100, where the joint formulation fails beyond n≈6. The dependence on treewidth is the one stated by Thm. 2: O(n2w+1) variables. We agree that a treewidth sweep is informative, and we will add one to App. I: k-trees with k∈{2,…,6} at fixed n, which our generator already produces.Relation to arithmetic circuits (Darwiche, 2009). Arithmetic circuits (ACs) compile the network polynomial of a precise network and exploit determinism and context-specific independence to evaluate it beyond the treewidth bound. LCN inference is different: it optimizes over a nonconvex set of distributions. An AC can therefore at best represent the objective inside the optimizer, not replace the optimization. The approaches are complementary, and we do not claim CJT is better.
Writing and organization.
Acyclicity. LCNs allow a sentence such as P(¬(C⊕D)∣A) to tie C and D symmetrically. The structure then has an undirected chain component rather than a DAG edge, and this is not expressible as a Bayesian network over atoms. Our methods treat such components as compound nodes, with exact local sets (§4.1). Larger cyclic dependencies become larger components and are handled identically.
Notation.