Experimental note

Sequences of Posterior Cuts for Exact DNF Learning

A compact synthesis of the two posterior-collapse papers, plus a new transcript-level formalism for studying which membership and equivalence query sequences remove large parts of the surviving hypothesis space.

May 2026 Exact learning with membership and equivalence queries Numerical probes on finite \(H_k\)

1. Common Posterior Formalism

Both papers start from the same finite exact-learning geometry. Let \(\mathcal X=\{0,1\}^n\), and let \(H_k\) be the set of Boolean functions representable by a DNF with at most \(k\) terms. A transcript \(\tau_t\) defines the version space

\[ V_t=\{h\in H_k:\ h\text{ is consistent with }\tau_t\}. \]

Under a full-support prior, the noiseless posterior is exactly supported on \(V_t\). Exact learning is therefore not merely posterior concentration. It is posterior collapse: every surviving hypothesis computes the same function on all of \(\mathcal X\).

\[ D_t=\{x:\exists h,g\in V_t,\ h(x)\ne g(x)\},\qquad D_t=\varnothing \Longleftrightarrow \operatorname{diam}(V_t)=0. \]

Membership cuts

A membership query at \(x\) splits the posterior into labels \(0\) and \(1\). With \(p_t(x)=P_t[h(x)=1]\), the best local split has

\[ \alpha(V_t)=\max_x \min\{p_t(x),1-p_t(x)\}. \]

Greedy membership can guarantee retained mass \(1-\alpha(V_t)\).

Equivalence cuts

A proposed hypothesis \(g\) lets the oracle choose a counterexample. The relevant worst-case retained posterior mass is

\[ \Lambda_t(g)=\max_x P_t[h(x)\ne g(x)]. \]

If \(\Lambda_t(g)\le 1-\beta\), every rejected equivalence query cuts at least a \(\beta\) fraction of the posterior.

2. What the Two Papers Add

The first paper gives a DNF-specific local mechanism. An equivalence query to \(g\equiv 0\) either proves the zero function or returns a positive witness \(x^+\). Since \(f(x^+)=1\), some DNF term fired at that point. Querying one-bit perturbations produces the local kill set

\[ K_f(x^+)=\{i\in[n]:f(x^+\oplus e_i)=0\}. \]

Each killed neighbor certifies that every term active at \(x^+\) contains the agreeing literal \(\lambda_i^{x^+}\). Under an isolation condition, these certified literals recover an entire term, which can be peeled from the residual DNF.

\[ x^+\text{ isolated for }T \Longrightarrow T=\bigwedge_{i\in K_f(x^+)}\lambda_i^{x^+}. \]

When this fails, the same paper turns the obstruction into structure. A nonredundant unpeelable term has private points whose one-bit boundary neighbors are rescued by other terms. This is the peel-or-overlap dichotomy.

The second paper gives the global mechanism. The posterior-majority function

\[ g_t^{\mathrm{Maj}}(x)=\mathbf 1[p_t(x)\ge 1/2] \]

is always central: \(\Lambda_t(g_t^{\mathrm{Maj}})\le 1/2\), and often much better. The bottleneck is representational. The majority vote over surviving \(k\)-term DNFs need not itself be a compact \(k\)-term DNF. Positive witnesses, peeling, and overlap compression are therefore preconditioners for the central problem: make a large-cut equivalence hypothesis compact enough to submit.

3. New Transcript-Level Formalism

Instead of analyzing a single query, define a query program as a sequence of the two allowed operations.

\[ \sigma=(a_1,\ldots,a_T), \qquad a_t\in\{\mathrm{MQ}(x_t),\mathrm{EQ}(g_t)\}. \]

The sequence is adaptive: \(x_t\) and \(g_t\) may depend on the transcript so far. Each step induces a posterior-retention ratio

\[ r_t=\frac{P_0(V_{t+1})}{P_0(V_t)},\qquad c_t=1-r_t. \]

For a membership query at \(x\), the retained mass is the side consistent with \(f(x)\). For a rejected equivalence query to \(g\), the retained mass is the counterexample slice

\[ V_{t+1}=V_t\cap\{h:h(x)=f(x)\} =V_t\cap\{h:h(x)\ne g(x)\}. \]

Thus a sequence can be judged in two ways:

Raw cut power

Does the transcript shrink \(|V_t|\) quickly? Numerically, this is measured by \(c_t=1-|V_{t+1}|/|V_t|\) under the uniform finite prior.

Structural cut value

Does the transcript land inside a useful fiber, certify literals, peel a term, or expose an overlap boundary? Large cuts are most useful when they also simplify center construction.

Central EQ Submit \(0\), majority, or a compact surrogate.
Witness A positive counterexample anchors a local DNF fiber.
Star MQs Query \(x^+\oplus e_i\) to certify killed literals.
Peel or Rescue Either recover a term or observe boundary overlap.
Compact Center Use the simplified geometry to build a better EQ proposal.
The useful object is not just a good next query. It is a transcript prefix that both removes mass and reshapes the residual posterior into a geometry where central hypotheses are easier to represent.

4. Numerical Probe: Exact \(H_k\) on \(n=4\)

Distinct truth-table functions in \(H_k\) were enumerated for \(n=4\), with syntactic DNFs deduplicated by truth table. These spaces are small enough to compute exact version-space cuts. The first one-step comparison is especially revealing.

\(k\) \(|H_k|\) Best MQ cut \(\alpha\) Majority-EQ guaranteed cut \(1-\alpha\) Best legal \(H_k\)-EQ retained
1820.1950.8050.195
21,8860.3200.6800.320
315,3580.4180.5820.418
444,2620.4720.5280.472
561,2940.4950.5050.495

The best membership query cuts only the smaller side. A posterior-majority equivalence query forces the oracle into that smaller side, so the cut is complementary. Early sparse DNF spaces are very skewed, making \(EQ(0)\) and majority-like proposals powerful.

\(k=1\) MQ
0.195
\(k=1\) EQ
0.805
\(k=3\) MQ
0.418
\(k=3\) EQ
0.582
\(k=5\) MQ
0.495
\(k=5\) EQ
0.505

5. Sequence Experiments

Adaptive sequences were then simulated with adversarial equivalence counterexamples. For \(n=4,k=3\), over 80 sampled targets:

Policy Mean queries Median queries Max queries Mean cut/query
Greedy membership15.4415.0170.477
EQ to posterior majority9.5610.0120.583
EQ to best legal \(H_k\) center10.4911.0130.557
Crude one-step hybrid11.1011.0150.555

The hybrid simply chose the better immediate worst-case cut between a membership split and a legal-DNF center. It was not a structural policy, so it did not exploit witness fibers or overlap certificates.

MQ
15.44
Maj-EQ
9.56
\(H_k\)-EQ
10.49
Hybrid
11.10

The second-paper claim also appears in a small representability check. In 936 posterior states visited by majority-EQ traces for \(n=4,k=3\), the exact posterior-majority truth table was itself in \(H_k\) about 75.2% of the time. When it was not, the best legal \(H_k\)-center was usually close: the average retained-mass gap was about 0.008, though the worst observed gap was 0.167.

This supports the central thesis: the information-theoretic center is excellent, and the real problem is representing a compact surrogate for it after the transcript has reshaped the posterior.

6. Positive-Witness Star Cuts

The most informative structural sequence was not a pure center sequence. It was the positive-witness star:

\[ \mathrm{EQ}(0)\to x^+,\qquad \mathrm{MQ}(x^+\oplus e_1),\ldots,\mathrm{MQ}(x^+\oplus e_n). \]

For \(n=4,k=3\), over 80 sampled nonzero targets, this short transcript left only a tiny fraction of the finite \(H_k\) posterior.

Witness choice Mean retained mass Mean cut Mean killed neighbors
Random positive witness0.02580.9742.42
Best positive witness0.02340.9772.79
Random
0.026
Best
0.023

The point is not just that the posterior shrinks. The transcript lands in a DNF-specific fiber. The killed neighbors are certified active literals; if the witness is isolated, the transcript recovers a term. If not, the failed isolation records which one-bit boundaries are rescued by other terms.

7. Random Syntactic DNF Probe

To connect the finite truth-table cuts to the first paper's geometry, random fixed-width DNFs were sampled and each term was classified as peelable, redundant, or nonredundant-unpeelable. The probe also measured how often private boundary edges were rescued by other terms.

\(n,k,r\) Peelable Redundant Unpeelable Private density Rescue rate Best witness peels? Min new vars in rescuer
10,16,40.8300.0020.1680.3840.3221.0001.16
10,32,40.1740.0640.7620.1440.5410.9921.20
12,32,40.5390.0090.4520.1360.4791.0001.31
12,48,40.0940.0670.8390.0510.6400.8751.32
Peelable Redundant Unpeelable
10,16,4
0.322
10,32,4
0.541
12,32,4
0.479
12,48,4
0.640

Stacked bars show peelable/redundant/unpeelable term fractions. The number at right is the rescue rate. As formulas get denser, peeling falls and rescued boundary overlap rises.

8. Interpretation

Equivalence queries can invert skew. If \(H_k\) is label-skewed at every point, membership cuts are weak, but majority-like equivalence proposals force the oracle into the minority side.
Positive witnesses are high-value transcripts. The sequence \(EQ(0)\) plus the one-bit star gives a large cut and exposes certified literals, so it carries more structure than a generic balanced split.
Failed peeling is not noise. Dense random DNFs show rising rescue rates when peeling fails. This is exactly the overlap side of the dichotomy, and rescuers tend to be close in new variables.

The experimental picture ties the papers together as follows:

\[ \text{central EQ} \to \text{positive witness} \to \text{local fiber} \to \text{peel or boundary rescue} \to \text{compact center}. \]

The central claim of the second paper is strengthened by the sequence view: the oracle can supply large posterior cuts, but the learner has to submit a representable center. The positive-witness and peel-or-overlap machinery from the first paper is one plausible way to make those centers representable by simplifying the residual geometry.

9. Next Formal Target

The numerical probes suggest a sharper theorem template. A preconditioning transcript should be evaluated by the pair

\[ \left(\prod_t r_t,\ \mathrm{Geom}(V_T)\right), \]

where the first coordinate is posterior mass retained and the second is a certificate that the residual geometry admits compact centers. A useful theorem would say that if peeling stalls, the rescued-boundary graph compresses the residual enough to construct a \(\beta\)-central hypothesis with \(\beta=\Omega(1)\) or with a reduced effective parameter.

\[ \text{few peelable terms} \Longrightarrow \text{query-separable overlap modules or compact central surrogates}. \]

This is still a conjectural route, but the experiments make the direction concrete: search over adaptive sequences not only for large cuts, but for cuts that produce witnesses, fibers, peel certificates, and compressed overlap graphs.

Reproducibility Note

The exact \(n=4\) experiments and sequence simulations were generated from cut_sequence_experiments.py. The random syntactic probe sampled fixed-width terms and classified terms by private points, isolation, and rescued one-bit boundaries. The numbers are intended as geometry probes, not asymptotic evidence.