Posterior-Cut Preconditioning for Exact Learning of \(k\)-Term DNFs

1. Exact Learning as Posterior Collapse

Let \(\mathcal X=\{0,1\}^n\), and let \(H_k\) be the class of Boolean functions representable by a DNF with at most \(k\) terms. A transcript \(\tau_t\) of membership and equivalence query responses defines the version space

With any full-support prior on \(H_k\), the noiseless posterior is exactly supported on \(V_t\). The target is learned exactly when every surviving hypothesis computes the same Boolean function, even if several syntactic representations remain.

2. Central Hypotheses

The ideal equivalence-query proposal is the posterior-majority function

This halving fact is information-theoretic. The difficulty for DNF learning is representational: the majority vote over surviving \(k\)-term DNFs need not itself be a compact \(k\)-term DNF. The central task is therefore to construct compact surrogates that are sufficiently central.

Positive-witness peeling and overlap compression should be read as preconditioners for this central-hypothesis problem. They simplify the residual posterior geometry until useful centers are easier to represent.

3. Positive Witnesses and Local Fibers

DNFs are asymmetric: a positive point says that at least one term fired. For \(x\in\mathcal X\), let the agreeing literal in coordinate \(i\) be

Thus each killed neighbor removes one bit of active-term ambiguity. Among all conjunctions satisfied by \(x^+\), requiring the \(s\) killed literals reduces the active term choices by a factor \(2^{-s}\).

4. Certified Term Peeling

The strongest local case occurs when a positive witness isolates a single term from the rest of the DNF.

This is an instance-dependent improvement. The certificate is exact: the peeled DNF has no false positives, and any subsequent residual hypothesis \(\widehat R\) can be proposed as \(G_q\vee\widehat R\).

5. Failure to Peel Forces Overlap

The obstruction to peeling is also informative. Let \(f=T_1\vee\cdots\vee T_m\), define \(R_j=\bigvee_{\ell\ne j}T_\ell\), and let the private region of \(T_j\) be

Thus an unpeelable nonredundant term is not featureless. Its private region is surrounded by other terms along one-bit boundaries.

6. Boundary-Rescue Compression

Represent a term as a subcube \(C_j=\{x:T_j(x)=1\}\), let \(S_j=\mathrm{var}(T_j)\), and define private density \(\rho_j=|P_j|/|C_j|\). The overlap side of the dichotomy gives a quantitative compression statement.

Under bounded width \(w\) and private density lower bound \(\rho\), every unpeelable nonredundant term has a rescuer within radius

This defines a boundary-rescue graph on terms. A cluster described by an anchor plus radius-\(L\) rescue transitions has rough description length

rather than \(m\log N_w\), where \(N_w=\sum_{a=0}^w{n\choose a}2^a\). This does not yet give a worst-case learning improvement, but it isolates the residual structure that a sharper theorem would need to exploit.

7. Certified Overlap Modules

Boundary rescue is a compression certificate, not automatically a learner. One complete setting where it becomes an exact learner is a query-separable module decomposition.

This theorem identifies the missing structural step needed for a worst-case improvement: prove that high rescue-rate residuals organize into query-separable modules, or into another compact representation from which central equivalence hypotheses can be constructed.

8. Relation to the ANPS Enhanced-Feature Learner

The Alman--Nadimpalli--Patel--Servedio exact learner can be translated directly into the present language. It maintains eligible pairs \((T',R_{T'})\), where \(T'\) is a candidate stem and \(R_{T'}\) is an auxiliary variable set. Its feature space contains augmented monomials

If the maintained family is fully expressive, every target term has a valid stem \(T'\) whose missing literals lie in \(R_{T'}\). Then the DNF is represented as an augmented polynomial threshold function of degree and weight

Winnow2 over this feature space supplies the equivalence-query sequence. Positive counterexamples grow the stem family; negative counterexamples grow \(R_{T'}\) through a noised line-search that filters out variables relevant only to long terms.

More explicitly, after \(q\) certified peels, with \(s=k-q\), the residual augmented-PTF degree and weight become

The feature-count term changes from roughly \(|{\cal F}|\binom{O(k^2\log k)}{\le d_k}\) to \(|{\cal F}_{\mathrm{res}}|\binom{O(s^2\log s)}{\le d_s}\), up to the usual \(\widetilde O(\cdot)\) factors.

9. Sequence-Level View

A transcript can be treated as an adaptive query program

Each step has posterior-retention ratio \(r_t=P_0(V_{t+1})/P_0(V_t)\) and cut \(c_t=1-r_t\). The framework evaluates a sequence not only by \(\prod_t r_t\), but also by the structural information it certifies.

10. Numerical Probes

The experiments below are small-scale geometry probes, not asymptotic evidence. They test whether the transcript mechanisms above produce large cuts and whether failure to peel coincides with boundary-rescue overlap.

Exact \(H_k\) enumeration for \(n=4\)

The majority equivalence proposal inverts the local splitting skew: a point with small minority mass gives a strong counterexample cut.

Adaptive sequence simulation

Sampled over 80 targets with adversarial counterexamples. Majority-style equivalence proposals produce larger average cuts than greedy membership splits in this finite setting.

Positive-witness star cut

The one-bit star around a positive witness leaves only a small posterior fiber and simultaneously certifies active literals.

A small representability check also supports the central-hypothesis view. Across 936 posterior states visited by majority-EQ traces for \(n=4,k=3\), the exact posterior-majority truth table itself belonged to \(H_k\) in about 75.2% of states. When it did not, the best legal \(H_k\)-center was usually close: the mean retained-mass gap was about 0.008, with worst observed gap 0.167.

11. Sequential Peeling and the Residual Parameter

Random fixed-width DNFs were sampled, and a finite-cube routine repeatedly peeled any term with a locally isolated private witness. The purpose is to measure the possible drop from \(k\) to the residual term count \(s\).

120 trials per row. Peeling is strong in sparse and moderately dense regimes. When it collapses, rescue rate rises sharply.

Bars show mean peeled terms \(q\) as a fraction of \(k\).

12. The Density Transition

A phase curve at \(n=12,w=4\) shows the shift from peelable geometry to overlap-heavy geometry.

80 trials per row. As local peeling fails, rescued boundary overlap becomes the dominant observed structure.

13. Artifacts and Reproducibility

The accompanying workspace contains three kinds of artifacts. First, the two source notes develop the posterior-collapse and central-equivalence viewpoints separately. Second, the scripts cut_sequence_experiments.py and anps_witness_preconditioning_experiments.py generate the finite version-space and random syntactic DNF probes. Third, the HTML notes provide a web reading layer with the same numerical tables.

The exact \(n=4\) enumeration is deterministic once \(n\) and \(k\) are fixed. Terms are represented by non-contradictory literal patterns, truth tables are encoded as integers, and syntactic duplicates are removed. The random syntactic probes use explicit seeds and fixed-width terms sampled without replacement.

14. Present Contribution and Open Route

The resulting research program is:

The current note stops short of a worst-case improvement over \(\mathrm{poly}(n)2^{\widetilde O(\sqrt{k})}\). Its value is a certified preconditioning theorem, a structural obstruction theorem, and numerical evidence that the two regimes predicted by the theory are visible in finite DNF geometries.

References

D. Angluin. Queries and concept learning. Machine Learning, 2(4):319--342, 1988.

J. Alman, S. Nadimpalli, S. Patel, and R. A. Servedio. Faster exact learning of \(k\)-term DNFs with membership and equivalence queries. arXiv:2507.20336, 2025.

J. Alman, S. Nadimpalli, S. Patel, and R. A. Servedio. DNF learning via locally mixing random walks. arXiv:2505.18839, 2025.

A. Blum and S. Rudich. Fast learning of \(k\)-term DNF formulas with queries. Journal of Computer and System Sciences, 51(3):367--373, 1995.

N. H. Bshouty. Exact learning Boolean functions via the monotone theory. Information and Computation, 123(1):146--153, 1995.

N. H. Bshouty. A subexponential exact learning algorithm for DNF using equivalence queries. Information Processing Letters, 59(1):37--39, 1996.

N. H. Bshouty. Almost optimal distribution-free junta testing. Computational Complexity, 28:749--783, 2019.

L. Hellerstein and V. Raghavan. Exact learning of DNF formulas using DNF hypotheses. Journal of Computer and System Sciences, 70(4):435--470, 2005.

L. Hellerstein, D. Kletenik, L. Sellie, and R. A. Servedio. Tight bounds for proper equivalence query learning of DNF. COLT, 2012.

A. R. Klivans and R. A. Servedio. Learning DNF in time \(2^{\widetilde O(n^{1/3})}\). Journal of Computer and System Sciences, 68(2):303--318, 2004.

E. Kushilevitz. A simple algorithm for learning \(O(\log n)\)-term DNF. Information Processing Letters, 61(6):289--292, 1997.

N. Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2:285--318, 1988.

X. Liu, X. Chen, R. A. Servedio, Y. Sheng, and J. Xie. Distribution-free junta testing. ACM Transactions on Algorithms, 15(1):1--23, 2018.

L. G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134--1142, 1984.