- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The paper considers ILP by enumeration of programs allowed by a template. The main contributions seem to be
- focus on analyzing the hypothesis space as a space of deductive closures of programs, rather than the programs themselves
- developing ways of counting this space. The main contributions seem to be formal results on learning small logic programs (ie in the Metagol framework, later followed by Evans & Greffenstette) and experiments on small-scale transitive closure type tasks.
Critical strengths
None (that I could identify from reading it)
Critical weaknesses
- The paper is very very dense and looks to me like mostly AI. It's hard to believe a human author would write this way.
- There is terminology that is non-standard (eg "content", "bandwidth"). The "bandwidth" term is central and is never clearly explained.
- The only experiments are on trivial ILP problems - the largest being a tiny subset of Wordnet
- The topic is unlikely to be of interest to a significant number of ICLR attendees.
Questions for authors
- In the abstract first sentence, do you mean "syntax 2^N" instead of "syntax 2^L" ?
- What exactly is bandwidth and why is it important?
2 comments
Thanks for the response, but I think I will keep my original score.
Our Response
We thank the reviewer for reading a paper that, in its submitted form, was hard going. We take the criticism seriously: it was too dense, used terms from two communities without always explaining them, and did not make clear why an ICLR reader should care. We have revised the paper to address each point and hope the reviewer finds it much easier to read.
Q1. "2L" or "2N"? Both are correct. 2L is the power set of the template L, the set of all clause-sets S⊆L, and it has 2N elements. The revised abstract now opens with "the 2N clause-sets S⊆L".
Q2. What is bandwidth, and why is it important? In the template Ln,d={rj←ri:0<j−i≤d}, the bandwidth d is the largest index distance a single rule can bridge: a rule passes a conclusion from ri only to ri+1,…,ri+d. In the running example, students sit in a row and can copy only from someone at most d seats away. The name comes from banded matrices: the adjacency matrix of the rule graph is zero more than d places off the diagonal. It matters for two reasons. First, d is the locality knob of the language bias and sets the semantic rate: log2ρd bits of meaning per atom, strictly fewer than d syntactic bits (Corollary 1). Second, bounded d is exactly what rules out a phase transition (Corollary 2), unlike unbounded reach (Theorem 3). Section 3 now gives this where the template is introduced, and App. E.5 repeats it.
A new primer (Appendix E, five pages) for readers who know one field but not the other:
E.1, logic for learning theorists: atoms are instances, a set of atoms is a classifier, forward chaining is the forward pass (here, breadth-first search), the template is an architecture and a clause-set a binary weight vector; the many-to-one map from programs to meanings is the analogue of parameter symmetry in neural networks.
E.2, learning theory for logicians: online protocol, realizable vs. agnostic (noise-free vs. noisy ILP), version spaces and Halving, VC and Littlestone dimension in terms of atoms, log loss as compression, Bayes mixtures and Hedge.
E.3, one example through every quantity: a three-atom template (8 clause-sets, 4 meanings) from which capacity, VC/Littlestone dimension, mistake bounds, regret under both priors and H(S∣R) are read off one table.
E.4–E.5, dictionary and false friends: hypothesis, model, capacity, content, closure, bandwidth.
A pipeline figure (Figure 9) shows the correspondence at a glance, and the introduction and Section 2 point to the primer. "Content" follows Carnap and Bar-Hillel (1952); E.1 explains why.
Why this matters for ICLR. The paper is about the hypothesis class of rule learners, including differentiable and neuro-symbolic systems (Evans and Grefenstette, 2018; Manhaeve et al., 2018) that optimize over a soft template 2L, where many settings express the same function. A learner whose prior lives on the template behaves differently from one that works with meanings. Section 6 shows this: under label noise, pruning consistent programs loses the target in every run, while exponential weights over meanings keeps its regret bound and runs on 1090.9 meanings of a WordNet taxonomy without listing them. A new dILP-style experiment (App. C.5) shows it from the optimizer's side: its predictions agree with a learner over meanings, but the program it outputs is less accurate, because many weight settings express the same meaning.
Beyond the examples. New Proposition 2 (App. A.9): for every template whose rules have one body atom, the class of meanings, its VC dimension, the number of programs per meaning and an efficient learner all follow from reachability in the rule graph.
Experiments. We chose datasets small enough to enumerate the content class exactly, so every claim can be checked rather than estimated; they are not all tiny (WordNet carnivore: 2365 clause-sets, 1090.9 contents, handled exactly in linear time). The revision adds label-noise (Section 6) and held-out-atom (App. C.4) experiments.
Writing. We rewrote the abstract and introduction, including a paragraph stating which results are standard and which are new, and tightened the main text. Our AI use is disclosed; every proof and number was checked by the authors, and several were independently reproduced by Reviewer bcxC.
We would be grateful if the reviewer could look at the revised version, and we are happy to answer further questions.