Neural DNF models are small networks built to be read as logic. A hidden layer of soft AND gates feeds a soft OR gate, and training is by gradient descent. To turn the trained model into human-readable rules of the form "(A and not B) or (C and D)", every continuous weight must be snapped to a few discrete values. That snapping is a form of extreme quantization, and it can destroy accuracy. Disentangling Neural Disjunctive Normal Form Models reports a 31.6% accuracy drop on the Mushroom dataset under plain thresholding. Their fix splits each tangled AND node into one clean node per input pattern that activates it, which cuts the drop to 2.9%. The fix has two stated limits. It enumerates input patterns, so its cost grows exponentially with a node's number of inputs, and heuristic sparsification is needed for dense models. It also leaves the OR layer untouched, because the OR gate's inputs are continuous.
We propose to replace heuristic sparsification with a measured quantity from Boolean function analysis. The influence of an input on a gate is the probability, over real data, that flipping that input flips the gate's output. For threshold gates, theory says influence splits the inputs into a small "head" that must be kept exactly and a "regular" tail of many individually weak inputs. The tail's combined effect behaves like smooth noise and survives coarse rounding. The recipe that follows is to enumerate patterns only over the head, round or drop the tail with an error we can measure, and rebuild the OR layer from the now-crisp AND outputs using a junta learner with agnostic guarantees. If it works, rule extraction becomes tractable for wide nodes, and the OR-layer problem left open by the disentanglement paper is solved.
Core Claim
Each soft AND and OR gate in a neural DNF computes a linear threshold function (LTF), $f(x)=\mathrm{sign}(w\cdot x-\theta)$, of its inputs. Improved Approximation of Linear Threshold Functions proves that every LTF is $\epsilon$-close to an LTF on only $\mathrm{Inf}(f)^2\cdot\mathrm{poly}(1/\epsilon)$ variables, far fewer than the $2^{O(\mathrm{Inf}(f)/\epsilon)}$ that Friedgut's theorem gives for general functions. The proof works by separating a few large-influence coordinates from a regular remainder. The same paper shows that a margin around the threshold keeps coarse integer weights from flipping the output. Our claim is that this head/tail split is the right unit for discretizing neural DNF gates. The head is kept symbolically and enumerated at cost $2^k$ with $k$ small. The tail is rounded to the ternary grid or removed, and it contributes a translation error that can be estimated before discretization.
We measure influence on the training distribution, not the uniform cube:
$$\widehat{\mathrm{Inf}}_i(g)=\frac{1}{N}\sum_{j=1}^{N}\mathbf{1}\big[g(x^{(j)})\neq g(x^{(j),\oplus i})\big],$$
Here $g$ is the gate thresholded at its current weights, $x^{(j)}$ are the $N$ training inputs, and $x^{\oplus i}$ flips input $i$. The input is flipped only if the flipped value is feasible under the encoding. For a one-hot group, flipping means moving to another category. This choice matters. The theory above is proved under uniform, biased-product, or $K$-wise independent inputs. Tabular data with one-hot encodings is strongly correlated, and Learning DNF through Generalized Fourier Representations shows that Fourier-style guarantees can degrade sharply under dependent inputs. Their spectral bounds hold only for tree-structured Bayesian networks with bounded parent-child variation. So we use the theory to justify the shape of the algorithm, not to supply guarantees on real data. On correlated data the empirical estimate of translation error is what we trust.
Research Program
The work has three components.
The first is head-restricted disentanglement for AND gates. For each AND node we rank inputs by $\widehat{\mathrm{Inf}}_i$ and choose the smallest head $H$ whose excluded tail keeps an estimated disagreement below a budget $\epsilon$. The disagreement is between the original gate and the gate with its tail zeroed or ternarized, measured on held-out data. We then run the disentanglement step of Gu Baugh et al. over $H$ only. We reuse their method but change the enumeration set, so the cost becomes $2^{|H|}$ rather than exponential in fan-in. One analysis goal is to characterize, on planted problems, how the chosen $|H|$ scales with the gate's total influence. The $\mathrm{Inf}^2$ scaling from Diakonikolas and Servedio is the prediction under near-uniform inputs, and we expect deviations under correlation.
The second is rebuilding the OR layer as an agnostic junta. The OR layer could not be disentangled because its inputs were continuous. Once the AND layer is discretized, those inputs are binary conjunction indicators. We then fit the OR output as a $k$-junta over them using the square-loss polynomial regression of Agnostic PAC Learning of k-juntas Using L2-Polynomial Regression. That method proves error $\mathrm{opt}+\epsilon$ for binary inputs without distributional assumptions, using the sign of the least-squares predictor. We keep only degree-1 and small-degree terms whose signs read as a disjunction or a small exception structure, and we prune conjunctions of negligible influence on the fitted OR. This supplies the missing guarantee exactly where the disentanglement paper stopped. It relies only on the binary-input case of the Heidari–Szpankowski result, not the weaker $2\cdot\mathrm{opt}+\epsilon$ real-valued case.
The third is a tail-error certificate. For each gate we report the estimated head/tail translation error before discretizing. We test whether the sum of per-gate certificates predicts the end-to-end accuracy drop. This turns the "performance cliff" from something discovered after snapping into something forecast before it.
Baselines
The do-nothing reference is plain thresholding of the trained neural DNF to the discrete weight set. Gu Baugh et al. report a 31.6% Mushroom translation drop for it in Disentangling Neural Disjunctive Normal Form Models. We rerun it from the same trained checkpoints so every method starts from identical continuous weights.
The strongest existing method is full node disentanglement with the authors' heuristic sparsification, reported at a 2.9% Mushroom drop. On Monk it produces 4 rules of average length 2.0, versus 49 branches of average depth 7.8 for a decision tree, in the same paper. We run it with its default sparsification and with a sparsification threshold tuned on validation data under the same wall-clock budget as our method. We count a win as either of two outcomes. One is matching its translation drop within one standard deviation over seeds while cutting the number of enumerated patterns on wide nodes by at least an order of magnitude. The other is a smaller translation drop at equal enumeration cost. On OR-entangled datasets, beating it means reducing the residual drop that their method cannot address.
The key ablation replaces empirical influence with weight magnitude as the ranking used to choose the head, keeping everything else fixed. A second ablation computes influence under a uniform input distribution instead of the data. These two isolate whether the data-measured quantity, and not merely "keep big weights", is doing the work. For the OR layer, the ablation keeps our AND-layer procedure but thresholds the OR layer directly instead of refitting it by junta regression.
As an external reference we train a random forest and CART on the same splits. Gu Baugh et al. report that neural DNF beats Random Forests, SVMs, and Decision Trees on 7 of 10 datasets. We include these to confirm that the recovered rules remain competitive, not as the main comparison.
Why not just…?
Why not just prune by weight magnitude before disentangling? This is the most serious threat. For a regular LTF under uniform inputs, influence is roughly proportional to weight magnitude, so on near-independent binary features the two rankings may coincide and our contribution on the AND layer would collapse to "magnitude pruning with a stopping rule." The two should diverge when features are correlated or one-hot encoded. There, a large weight on a rarely-active or redundant input can have near-zero influence on the data, which is the regime flagged by the dependent-distribution analysis of Heidari and Khardon. The magnitude ablation settles this directly. If it matches influence on the real datasets, we will say so. The contribution would then rest on the OR-layer refit and the error certificate, which magnitude pruning does not provide.
Why not just enumerate only the input patterns that actually occur in training data? This bounds cost by the number of distinct observed patterns rather than $2^{\text{fan-in}}$, and on small tabular datasets it may already be cheap. It does not help when observed patterns are numerous, as with wide nodes on larger datasets. It also keeps every input in every rule, so rules stay long, and it offers no way to predict error from dropping an input. We include it as a second enumeration baseline and report both runtime and rule length. If it dominates on all ten datasets, the AND-layer half of this proposal is unnecessary at this scale. The synthetic scaling study below is where it should fail.
Why not skip the neural network and learn a junta or DNF directly? Running the Heidari–Szpankowski regression on raw features gives agnostic guarantees without any quantization step. However, a direct degree-$d$ fit over $n$ raw features has cost growing like $n^{d}$, and DNF learning from random examples alone is stuck at quasipolynomial time in general (Learning Disjunction of Conjunctions). Our method applies the junta learner only to the OR layer, over tens of binary conjunction features the network has already found, where it is cheap. We run direct junta regression on raw features as a reference to show where the neural stage earns its place.
Proposed Experiments
Synthetic planted DNFs. Inputs have dimension $n$ from 20 to 200. The planted DNF has 3–8 terms, each depending on a small set of relevant variables, plus many irrelevant or weakly correlated inputs. Inputs are drawn either independently or from a tree Bayesian network with controlled parent-child variation. Ground truth is known, so we measure rule recovery (exact term match) as well as translation drop. We plot enumerated patterns and runtime against node fan-in for full disentanglement, observed-pattern enumeration, and our method. The prediction is that our cost is flat in irrelevant fan-in while the first two grow. We also plot chosen $|H|$ against measured gate influence to test the $\mathrm{Inf}^2$ prediction and how correlation bends it.
Real tabular data. We use the ten classification datasets of Gu Baugh et al., including Mushroom and Monk. We report accuracy before and after translation, rule count, and average rule length over five seeds. The two headline comparisons are the Mushroom translation drop against 2.9% and Monk rule compactness against 4 rules of length 2.0.
Decisive checks. Three results decide whether the core claim holds. The first is whether the summed tail-error certificates rank-correlate with the observed end-to-end translation drop across datasets and seeds. If they do not, the certificate claim fails. The second is whether influence beats magnitude in head selection on the datasets with one-hot or correlated features. The third is whether the junta-refit OR layer reduces translation drop on the datasets where the original paper's residual loss comes from OR entanglement.
A positive outcome on the first and third, even with a null result on the second, would still deliver a tractable, predictable rule-extraction pipeline and close the OR-layer gap. A null on all three would indicate that LTF head/tail structure does not describe what neural DNF gates learn on real data. That finding would be useful for anyone hoping to explain discretization cliffs with influence theory.