acceptodds
Withdrawn from ICLR 2027

Learning the Semantics of Logical Content

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

A learner that induces logic programs from a template of candidate Horn clauses appears to face hypotheses, but most rule-sets deduce the same facts and are indistinguishable to any learner scored on its predictions. The true hypothesis class of a recursive template is therefore not the syntax but the set of realizable deductive closures , the distinct semantic meanings the template can express. Its log-count , the semantic information (capacity) of the template, is its learning complexity: when facts arrive online and the learner predicts whether the theory deduces each, Halving makes at most mistakes in the realizable case, the minimax log-loss (Shtarkov) regret is exactly once the queries separate the contents, and the agnostic minimax regret is . We compute in closed form: bits for the bandwidth- reachability template on , with the -bonacci constant solving , and bits for nonlinear transitive closure on constants. In a probabilistic reading a single content's size undergoes a sharp phase transition at one base fact per constant. One computable number thus governs counting, coding, and learning, realizing the semantic-information program of carnap1952semantic and lastras2026 as a learning rate. Empirically, on Padgett's Florentine families network the clause-sets collapse onto contents and the online code length lands exactly on bits; the same identity holds on WordNet.

Primary area:
learning theory
Keywords:
semantics, logic, learning, information

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_1V2AOpenReview ↗
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
AuthorsOpenReview ↗

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. "2L2^L" or "2N2^N"? Both are correct. 2L2^L is the power set of the template LL, the set of all clause-sets S⊆LS\subseteq L, and it has 2N2^N elements. The revised abstract now opens with "the 2N2^N clause-sets S⊆LS\subseteq L".

Q2. What is bandwidth, and why is it important? In the template Ln,d={rj←ri:0<j−i≤d}L_{n,d}=\{r_j\leftarrow r_i : 0<j-i\le d\}, the bandwidth dd is the largest index distance a single rule can bridge: a rule passes a conclusion from rir_i only to ri+1,…,ri+dr_{i+1},\dots,r_{i+d}. In the running example, students sit in a row and can copy only from someone at most dd seats away. The name comes from banded matrices: the adjacency matrix of the rule graph is zero more than dd places off the diagonal. It matters for two reasons. First, dd is the locality knob of the language bias and sets the semantic rate: log⁡2ρd\log_2\rho_d bits of meaning per atom, strictly fewer than dd syntactic bits (Corollary 1). Second, bounded dd 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)H(S\mid 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 2L2^L, 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.910^{90.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: 23652^{365} clause-sets, 1090.910^{90.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.

Thanks for the response, but I think I will keep my original score.

Reviewer_Xk4gOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies finite Horn templates through their realizable deductive closures \Omega rather than their syntactically distinct clause subsets. It defines semantic capacity C(L)=log|\Omega| and obtains a rational generating function for bandwidth-d reachability, giving C(L)=n log \rho d+O(1) for fixed d≥2. A second construction identifies ordered transitive closures with compatible partial orders and obtains capacity m^2/4+o(m^2). Separately, random base facts exhibit the familiar sparse-graph reachability threshold. Standard online-learning and coding arguments give a Halving upper bound, bounds involving Littlestone dimension, and exact fixed-query Shtarkov regret. Florentine and WordNet examples illustrate semantic collapse, content-uniform coding, and the effect of syntactic priors.

Critical strengths
  • Well-motivated semantic formulation. The paper provides a principled way to characterize the effective hypothesis space of logic programs through realizable deductive closures, rather than syntactically distinct clause sets.
  • Solid theoretical analysis. The paper provides exact counting results and asymptotic characterizations of semantic capacity for different recursive templates. It further connects semantic capacity to established online learning guarantees, including mistake bounds and minimax regret, resulting in a relatively comprehensive theoretical treatment.
  • Empirical validation on real-world datasets. The experiments on the Florentine families network and WordNet demonstrate substantial reductions from syntactic hypothesis spaces to semantic content classes. The comparison with syntax-based learning further illustrates the potential benefits of reasoning over semantic equivalence classes.
Critical weaknesses

The paper presents two largely orthogonal theoretical contributions: the characterization of semantic capacity and its implications for online learning, and the phase transition in the expected extent of randomly generated deductive closures.

While both are formulated through the same closure map, the connection remains primarily conceptual. In particular, the phase-transition result does not appear to yield new implications for semantic capacity, coding redundancy, or learning regret, and the online-learning results do not substantially inform the probabilistic analysis.

Moreover, the phase transition is derived from classical random-graph phenomena under an unrestricted directed-graph model. It is therefore unclear what additional insight the semantic-information framework provides beyond reinterpreting known percolation results.

A more compelling unification would establish how prior-dependent semantic entropy, coding complexity, or learning performance behaves across the critical regime. Without such a connection, Section 4 feels relatively disconnected from the paper's main capacity-to-learning contribution.

Questions for authors

Can the authors characterize how Hπc(R)H_{\pi_c}(R), or the expected coding/learning regret under πc\pi_c, changes as cc crosses the percolation threshold?

2 comments
AuthorsOpenReview ↗

Our Response

We thank the reviewer. The critique is fair: in the submitted version, Section 4 and the capacity results shared a map but not a conclusion. The revised paper answers the reviewer's question with a new result.

The link: semantic compression. By Remark 1 the closure map F↦RF\mapsto R is a deterministic channel, so H(F)=H(R)+H(F∣R)H(F)=H(R)+H(F\mid R). An optimal code for a random program uses H(F)H(F) bits; one for its meaning uses only H(R)H(R). This is not the cost of listing the pairs of the denser graph RR, but of identifying which relation occurred: RR is determined by its strongly connected components and their order, and lengths −log⁡2P(R)-\log_2 P(R) are optimal (App. A.6). Sending FF instead costs exactly H(F∣R)H(F\mid R) more, the redundant syntax the meaning compresses away. We call H(R)/H(F)H(R)/H(F) the semantic compression rate and H(F∣R)/H(F)H(F\mid R)/H(F) the semantic redundancy. The reviewer's question, how Hπc(R)H_{\pi_c}(R) behaves across the threshold, is the question of how much semantics compresses a random program.

The answer (new Theorem 4, complete proof in App. A.6). For F∼D(m,c/m)F\sim D(m,c/m), R=TC(F)R=\mathrm{TC}(F), H(F)=c mlog⁡2m (1+o(1))H(F)=c\,m\log_2 m\,(1+o(1)):

c<1c<1: H(F∣R)=O(log⁡m)H(F\mid R)=O(\log m), so Hπc(R)=H(F)(1−O(1/m))H_{\pi_c}(R)=H(F)(1-O(1/m)); semantics compresses essentially nothing. c>1c>1: H(R)/H(F)≤1−2ζ2(1−ζ)H(R)/H(F)\le 1-2\zeta^2(1-\zeta) asymptotically, 1−ζ=e−cζ1-\zeta=e^{-c\zeta}; a constant fraction is redundant (at least 0.28 at c=1.5c=1.5, 0.26 at c=2c=2). Bandwidth template: H(R)=O(1)H(R)=O(1) while H(S)=Θ(n)H(S)=\Theta(n); the compression is total.

Intuition. Below the threshold the graph is tree-like: each edge is usually the only route between its endpoints, so the meaning determines the program. Above it a giant strongly connected component GG appears, and edges across its boundary become interchangeable: an edge entering GG deduces the same facts whichever vertex of GG it hits, and an edge leaving GG whichever vertex it leaves from. About 2cζ2(1−ζ)m2c\zeta^2(1-\zeta)m edges are of this kind, each worth about log⁡2m\log_2 m bits the meaning does not record. The proof uses only the giant-component size (Karp 1990; Łuczak 1990) and the branching-process approximation for one vertex; App. A.6 opens with an overview. The bound is conservative: edges inside GG are a further source of redundancy it does not count.

The true value. P(R)P(R) has an exact product form: given RR, TC(F)=R\mathrm{TC}(F)=R iff each component is strongly connected, every covering pair of components carries an edge, and no other edges go against the order. Hence H(F∣R)=E[log⁡2P(R)−log⁡2P(F)]H(F\mid R)=\mathbb{E}[\log_2 P(R)-\log_2 P(F)] is computable by Monte Carlo (checked against enumeration for m≤5m\le5). Results (Figure 3, Table 9): redundancy 0.02 at c=1c=1 and decreasing in mm below it; 0.57, 0.85, 0.97 at c=1.5,2,3c=1.5, 2, 3 (m=1000m=1000, rising slightly with mm), i.e. compression rates 0.43, 0.15, 0.03. Semantics compresses most of a random program above the threshold. From the same formula we conjecture that the redundancy tends to ζ2(2−ζ)2\zeta^2(2-\zeta)^2: an edge is redundant exactly when its tail reaches the giant component and its head is reached from it.

Lower bounds (Figure 3, App. C.4). At m=2000m=2000 the proof's witness is 0.22 at c=1.5c=1.5 and 2 (limits 0.28, 0.26), approaching the limit from below; adding edges inside GG gives 0.32, 0.50, 0.61 at c=1.5,2,3c=1.5, 2, 3. Below threshold the upper bound is at most 0.012, and the number of edges not determined by RR stays bounded for mm up to 8000.

What this adds. One threshold governs both extent and semantic compression. A consequence the percolation literature does not state: whether a clause-level prior pays more than a content-level prior depends on which side of the threshold the data-generating process lies; the label-noise experiment (Section 6) shows this in practice.

"Reinterpreting known percolation results." We agree the extent threshold (Theorem 3) is Karp's and cite it so. Our claims are the transfer to deductive closure (with the bounded-reach contrast of Corollary 2) and the semantic compression transition, a statement about the information in a program rather than about reachability alone.

Thank you for the response and the additional theoretical and empirical results. However, I still have reservations about the overall coherence and novelty of the contributions, particularly the reliance on classical random-graph results. While I appreciate the improvements, I will maintain my original score.

Reviewer_bcxCOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper fixes a definite Horn template L of N ground clauses over background BK and studies the image of the least-model map, the set of realizable deductive closures, called contents. Its log-count is named the semantic capacity C(L). Three readings follow. Combinatorial: for the bandwidth-d reachability template the counts satisfy a_n = 2a_{n-1} - a_{n-d-1}, giving C(L) about n log2 of the d-bonacci constant, with a_n = F_{n+3} - 1 for d = 2; for the doubly recursive transitive-closure template the ordered contents are naturally labeled posets and C(L) = m^2/4 to first order via a bipartite lower bound and Kleitman and Rothschild. Probabilistic: with random base facts the reachable set of one constant in D(m, c/m) has a Karp-type threshold at c = 1, while the bandwidth template never percolates for fixed edge probability below 1. Online: Halving makes at most C(L) mistakes, Hedge gives regret of order the square root of C(L) T, a Ben-David, Pal and Shalev-Shwartz style tree argument gives the lower bound in Ldim, and for the bandwidth class VC = n - floor(n/d) + O(1), so the agnostic rate is Theta of the square root of C(L) T; the log-loss minimax regret is the Shtarkov sum, which for deterministic experts is the number of label patterns. Experiments on the Padgett Florentine marriage network and four WordNet subtrees report that a version-space Bayes mixture pays exactly C(L) bits, and an appendix compares it to the same mixture with a uniform prior over clause-sets.

Critical strengths
  1. The math is largely correct and the numbers are real. I reproduced the recurrence, the closed form F_{n+3} - 1, the constants log2 rho_2 = 0.6942 and log2 rho_3 = 0.8791, the constant A_2, the VC formula by brute force, the ordered transitive-closure counts 1, 2, 7, 40, 357, Karp's zeta squared scaling by Monte Carlo, the exact equivalence in law in Step 5 of the Theorem 3 proof, all 15 Florentine content counts in Table 1, all four WordNet capacities in Table 2, the Example 4 fibre sizes and entropy, and the clause-set baseline numbers in Table 3. Only two secondary numbers in Appendix C.1 fail to match my exact recomputation, see the minor issues. A paper whose reported numbers almost all survive an independent rebuild earns real credit.

  2. The bandwidth family gives a clean, fully worked case where a recursive language bias has an explicit content rate below its syntactic rate, with VC, Littlestone and log-cardinality all pinned to linear order, and the transitive-closure family shows the quadratic jump. The exact, tuning-free comparison in Appendix C.3, a Bayes mixture with a content-uniform prior versus one whose prior is the fibre size, is a nice concrete illustration of how a parameter-uniform prior skews the prior on meanings.

Critical weaknesses
  1. The central object is the hypothesis class in the usual sense, and the semantic capacity is log2 of its cardinality. Learning theory already measures a class by the distinct functions it contains, and VC dimension, Littlestone dimension and the Shtarkov sum are the same whether one indexes the class by clause-sets or by contents. So the slack between N and C(L) bits lives only in the naive Occam count over parameterizations. The learning results are standard finite-class facts: Halving makes at most log2 of the class size mistakes, Hedge pays the square root of T ln M over 2, the Shtarkov sum over deterministic experts counts label patterns, and a Bayes mixture's log-loss telescopes to the log ratio of initial to final version-space mass. Remark 1's Shannon capacity is that of a noiseless channel, always log2 of the number of outputs, as Appendix D itself notes. For 0/1 loss C(L) is not in general the learning complexity the abstract's wording suggests. The paper concedes on page 7 near line 353 that matching requires Ldim of the same order as C(L), and Remark 3 on page 17 leaves the Ldim slope for d = 2 between 0.5 and 0.694. My brute force gives Ldim 6 against C(L) of about 7.16 for n = 9, d = 2. Alon, Ben-Eliezer, Dagan, Moran, Naor and Yogev show that optimal online regret is Theta of the square root of Ldim times T, and that paper is not cited. The two families match because VC happens to be comparable to the log count: for transitive closure the bipartite shattered set already gives VC at least floor(m^2/4), so the three measures agree to first order. The baseline called a syntactic learner, page 3 near line 112, is a Bayes mixture with a uniform prior over parameterizations, which is not how the ILP systems the paper cites operate. Cohen's 1995 JAIR papers on PAC-learning recursive logic programs are not cited either. The imported pieces, compositions with bounded parts, Kleitman and Rothschild, Karp's transitive closure, and Ben-David, Pal and Shalev-Shwartz, are cited and correctly used, but they leave the new mathematics thin: essentially Proposition 1, the bandwidth VC lemma, and the identification of ordered contents with naturally labeled posets. The unordered variant is also misstated: page 5 near line 262 and Appendix A.3 say its contents are all transitive relations on [m], but I count 4 contents against 13 transitive relations for m = 2; the contents correspond exactly to preorders, so kappa = 1/4 survives.

  2. The empirical section restates a proved identity rather than testing a hypothesis. Theorem 7(i) gives the mixture's log-loss as log2 of the class size over the final version-space size, and the paper states it for an arbitrary template and query sequence. Contents are distinct atom sets on the queried sub-base, so with a realizable target and every atom queried exactly one content survives. The code length reaching C(L) for every target and order, page 9 near line 448, and agreeing to 13 decimal places, page 22 near line 1167, therefore holds for any finite class under those conditions. The paper itself writes that the identity persists at scale, yet presents it as empirical validation. Mistake counts staying below C(L) is the Halving guarantee. No experiment probes a setting where the content view could change outcomes: generalization to unqueried atoms, partial or noisy labels, positive-only learning, or a comparison with a real ILP or differentiable ILP learner, though the paper names differentiable ILP and the slack in its guarantee on page 2 near lines 94 to 97. The conclusion on page 24 near line 1292 says any capacity, sample-complexity or code-length claim stated over clause-sets is inflated by the collapse factor; that holds for log-cardinality bounds but not for VC or Ldim based claims, which do not depend on the parameterization. The paper says its figures come from accompanying code, page 19 near line 1014, but gives no link.

Questions for authors
  1. Which result in Section 5 would fail, or could not be obtained, by applying the standard finite-class bounds to the set of distinct classifiers the clause-sets induce? If none, please restate the contribution as computing these standard quantities for two template families, rather than as a new learning complexity.
  2. Do you claim C(L) governs agnostic 0/1 online learning for general recursive templates? Given that optimal regret is set by the Littlestone dimension, please give a Horn reachability template where Ldim is much smaller than C(L), or explain why that cannot happen.
  3. Can you show an experiment where working over contents changes a learner's behavior, for example generalization to held-out atoms, label noise, or a head-to-head with a differentiable ILP learner whose capacity bound uses N?
  4. Appendix C.2 says counting contents is #P-hard in general, page 20 near line 1068, with no reference, while Appendix E lists hardness for general DAGs as open, page 25 near line 1307. For which template class is hardness known, and what is the reference or proof?
  5. For Corollary 2, my exact chain computation gives a limiting E|R0| of about 9.9e5 for d = 2 and edge probability 0.99, and about 9.9e11 for d = 3. My conjecture, which fits these values, is that it scales like (1 - theta) to the power -d(d+1)/2, matching the d(d+1)/2 edges that must be off to empty a window. Would you fix the exponent in the proof, add the scaling, and soften the claim that content stays bounded no matter how reliable the rules are?
2 comments
AuthorsOpenReview ↗

Our response

We thank the reviewer for an exceptionally careful review; we are grateful that nearly every number survived an independent rebuild. We accept the framing critique and all corrections.

Central critique. We agree: ΩL\Omega_L is the hypothesis class, VC/Ldim/Shtarkov do not depend on the parameterization, and Section 5 is standard once the class is known. The revised paper no longer claims "a new learning complexity" (new paragraph "What is standard and what is new"). The core is that the learner is given LL, not ΩL\Omega_L; nothing about the class (size, VC, Ldim, or how to run Halving on it) is available until it is constructed. We construct it: Prop. 1, the bandwidth VC lemma and the poset identification (the new mathematics the reviewer identified), plus exact counts, implicit O(n)O(n) learners, and the semantic compression transition (see Xk4g). Following the reviewer, we generalized the VC lemma to all linear templates (new Prop. 2, App. A.9).

Q1. None fails; each is a standard bound applied to ΩL\Omega_L, and Section 5 now says so. What the bounds do not supply is the class: its size, VC, Ldim and an efficient optimal learner. We compute all four for both families.

Q2. No. Optimal agnostic regret is Θ(Ldim T)\Theta(\sqrt{\mathrm{Ldim}\,T}) (Alon et al., STOC 2021, now cited); C(L)C(L) matches only when Ldim=Θ(C(L))\mathrm{Ldim}=\Theta(C(L)), as in both our families. Your values (Ldim=6\mathrm{Ldim}=6 vs. C(L)≈7.16C(L)\approx 7.16 at n=9n=9, d=2d=2) fit our interval [0.5,0.694][0.5, 0.694] for the slope. Whether some Horn template has Ldim=o(C(L))\mathrm{Ldim}=o(C(L)) is now Open Problem 1 (Section 5; exact values in Remark 2, App. A.10).

Syntactic baseline. Agreed that ILP systems do not run a uniform mixture over clause-sets. The baseline models learners with a prior or description length on programs (Bayesian/MDL induction, clause priors in probabilistic ILP, dILP weights). Any such learner is Algorithm 1 with the induced prior π(R)=P(μ−1(R))\pi(R)=P(\mu^{-1}(R)), priced exactly by new Corollary 4 (App. C.3): regret −log⁡2π(R⋆)-\log_2\pi(R^\star), worst case ≥C(L)\ge C(L) (equality only for uniform π\pi), average over contents C(L)+D(unif ∥ π)C(L)+D(\mathrm{unif}\,\|\,\pi), average under its own prior H(π)≤C(L)H(\pi)\le C(L). It is a bet on syntactically redundant targets. Renamed "clause-prior mixture", scope stated, Cohen (1995a,b) cited.

Q3. Agreed; Section 6 now presents the identity as such and adds tests where it fails (Florentine, exact; WordNet carnivore, 1090.910^{90.9} contents, implicit; App. C.4). (a) Label noise (ϵ\epsilon = 0.05–0.2): Halving's version space empties in 100% of runs (43–47% clean error); Hedge over ΩL\Omega_L stays below (ln⁡2/2)C(L)T\sqrt{(\ln 2/2)C(L)T} (35 and 560 mistakes), running implicitly because its weights factorize over atoms. At ϵ=0.1\epsilon=0.1 the content prior's regret ignores how the target arose (21.6 vs. 21.6; 363 vs. 356); the clause prior is a bet (17.8 vs. 25.0; 81 vs. 401, rule- vs. content-generated). (b) Held-out atoms: the prior, invisible to VC/Ldim, decides predictions; neither prior dominates. (c) dILP-style learner (App. C.5): its predictions match Hedge over ΩL\Omega_L, but its extracted program errs 5.4%/13.8% vs. 0.0%/1.6% for the MAP content (ϵ\epsilon=0.1/0.2, T=150T=150), mostly false negatives as evidence splits across equivalent clause-sets; on the tree carnivore (one clause-set per content) the gap vanishes. 30 restarts give 29 distinct programs with the same meaning. A comparison with Popper is listed as future work.

Q4. We have no reference and it contradicts App. E of the submission; withdrawn. Counting ΩL\Omega_L is now stated as open in general, polynomial for our families.

Q5. Correct: emptying the window needs up to d(d+1)/2d(d+1)/2 edges off, so E∣R0∣≤1+d(1−θ)−d(d+1)/2\mathbb{E}|R_0|\le 1+d(1-\theta)^{-d(d+1)/2}, matching your values; the exact chain gives 9.901×1059.901\times10^5 and 9.899×10119.899\times10^{11} at θ=0.99\theta=0.99, so the order is attained. The text now says "bounded for every fixed θ<1\theta<1" (Corollary 2, App. A.5).

Unordered variant. Correct: contents biject with preorders (4 for m=2m=2, not 13); κ=1/4\kappa=1/4 unaffected (Theorem 2, App. A.3).

Other. The conclusion now limits the 2N/∣ΩL∣2^N/|\Omega_L| inflation to log-cardinality/Occam/prior claims. App. C.1 recomputed exactly (SkS_k = 1.9, 3.7, 7.0, …, 2683, 4104; size-prior mean 13.44 bits). Proof of Theorem 1 corrected (pole in (12,1)(\tfrac12,1), Miles 1960, sharper expansion). All code is in the supplement.

Thanks for the rebuttal. I keep my initial score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

General response to all reviewers

We thank the reviewers, especially bcxC, who independently rebuilt nearly every number in the paper. We have uploaded a revised paper implementing every change below.

What we no longer claim. We do not claim a new learning complexity. Once the content class ΩL\Omega_L is known, the results of Section 5 are standard finite-class facts (Halving, Hedge, Shtarkov/NML, the Littlestone/VC sandwich), and VC, Ldim and the Shtarkov sum do not depend on the parameterization. The revised paper says so explicitly.

What we claim: ΩL\Omega_L is never given; it must be constructed. A rule learner is handed a template LL, i.e. the parameterization 2L2^L; the class exists only as the image of a least-fixpoint map μ(S)=lhm(BK∪S)\mu(S)=\mathrm{lhm}(BK\cup S). Nothing in LL reveals ∣ΩL∣|\Omega_L|, VC or Ldim, and brute force means running the fixpoint on all 2N2^N clause-sets (2402^{40} for Florentine, 23652^{365} for WordNet). Even running Halving, NML or Hedge needs a structural description of ΩL\Omega_L. We construct it:

Characterization (Prop. 1): a graph-reachability condition; for transitive closure, posets (ordered) and preorders (unordered, corrected). Exact counting: rational generating function and dd-bonacci rate (Thm. 1); κ=1/4\kappa=1/4 (Thm. 2); VC=n−⌊n/d⌋+O(1)\mathrm{VC}=n-\lfloor n/d\rfloor+O(1). Implicit learners: the optimal predictors run in O(n)O(n) per round over 1090.910^{90.9} contents, never listing one. Where the prior lives: a learner that does not construct ΩL\Omega_L puts its prior on clause-sets; it is Algorithm 1 with prior ∣μ−1(R)∣|\mu^{-1}(R)|, and Theorem 8 prices it exactly (Corollary 4, App. C.3). It pays more on targets with few programs, less on targets with many (Florentine: 14.35 bits on average vs. 12.00; bandwidth-2: 1.01n1.01n average, 43n\tfrac43 n worst vs. 0.694n0.694n). Guarantees stated through the parameterization are loose by 2N/∣ΩL∣2^N/|\Omega_L|; VC/Ldim guarantees are not.

New in the revised paper.

Semantic compression transition (Theorem 4, formerly Prop. 2; new bound, complete proof in App. A.6). An optimal code for a random program uses H(F)H(F) bits, one for its meaning only H(R)H(R); H(F∣R)H(F\mid R) is the syntax the meaning makes redundant. It jumps at c=1c=1, the extent threshold, from O(log⁡m)O(\log m) bits to a fraction ≥2ζ2(1−ζ)\ge 2\zeta^2(1-\zeta) of H(F)H(F). Exact computation gives true redundancy 0.57, 0.85, 0.97 at c=1.5,2,3c=1.5, 2, 3 (Xk4g). Experiments where the content view matters (Section 6, App. C.4). Under label noise, Halving loses the target in 100% of runs; Hedge over ΩL\Omega_L stays within its bound, even on 1090.910^{90.9} contents. Its regret does not depend on how the target arose (21.6 vs. 21.6 on Florentine, 363 vs. 356 on carnivore), while the clause prior wins or loses with the source. Held-out atoms: the prior changes generalization, and neither prior dominates. dILP-style learner (App. C.5): its predictions match Hedge over ΩL\Omega_L, but its extracted program errs more (5.4%/13.8% vs. 0.0%/1.6%), and 30 restarts give 29 different programs with the same meaning. Linear templates in general (Prop. 2, App. A.9): union-closure, exact VC, fibre formula, and a linear-time consistent learner, all from reachability in the rule graph. Corrections of every error bcxC found. A five-page primer for both communities (App. E).

Why it matters for ICLR. Differentiable and neuro-symbolic rule learners (dILP, DeepProbLog) optimize over the parameterization 2L2^L, where many settings express the same function. Our results show when that matters: it does not change VC/Ldim rates, but it changes priors, code lengths, and the program a learner outputs (Section 6, App. C.5).

Where to find the changes. Rewritten abstract and introduction; bandwidth in Section 3; Theorem 2 and App. A.3; Corollary 2 and App. A.5; Theorem 4 in Section 4, proof in App. A.6 (former Theorems 4–8 are now 5–9); Section 5 with Open Problem 1; Section 6; App. A.9 (Prop. 2), B (implicit Hedge), C.3 (Corollary 4), C.4, C.5, E (primer).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.