Learning DNF through Generalized Fourier Representations
Mohsen Heidari, Roni Khardon · 2025
Read Learning DNF through Generalized Fourier Representations by Mohsen Heidari, Roni Khardon (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-01075.txt.
Introduction
Mohsen Heidari and Roni Khardon tackle a long open problem in machine learning theory in this 2025 paper. They study how computers can learn rules written as sums of AND blocks, known as DNF formulas. Classic methods use a wave-like encoding of yes-no data, but they work mainly when inputs are free of links.
Real data often has linked inputs, and past methods stalled there. The pair build a broader encoding based on a network that maps how the inputs depend on each other. They show the old tricks still work with small changes. Their proofs bound the size of key parts under the new encoding.
Catalog record
| CREATOR | Mohsen Heidari, Roni Khardon |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-01075
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning DNF through Generalized Fourier Representations Mohsen Heidari, Roni Khardon Abstract The Fourier representation for the uniform distribution over the Boolean cube has found numerous applications in algorithms and complexity analysis. Notably, in learning theory, learnability of Disjunctive Normal Form (DNF) under uniform as well as product distributions has been established through such representations. This paper makes five main contributions. First, it introduces a generalized Fourier expansion that can be used with any distribution D D through the representation of the distribution as a Bayesian network (BN). Second, it shows that the main algorithmic tools for learning with the Fourier representation, that use membership queries to approximate functions by recovering their heavy Fourier coefficients, can be used with slight modifications with the generalized expansion. These results hold for any distribution. Third, it analyzes the L 1 L_{1} spectral norm of conjunctions under the new expansion, showing that it is bounded for a class of distributions which can be represented by difference bounded tree BN, where a parent node in the BN representation can change the conditional expectation of a child node by at most α < 0.5 \alpha<0.5 . Lower bounds are presented to show that such constraints are necessary. The fourth contribution uses these results to show the learnability of DNF with membership queries under difference bounded tree BN. The final contribution is to develop an algorithm for learning difference-bounded tree BN distributions, thus extending the DNF learnability result to cases where the distribution is not known in advance. 1 Introduction The problem of learning Disjunctive Normal Form (DNF) expressions from examples has been a major open problem since its introduction by Valiant1984 . Significant progress has been made by considering subclasses of expressions (e.g., Valiant1985 ; BshoutyTamon96 ; SakaiMuroka00 ) or making distribution assumptions Verbeurgt90 ; Servedio04 , and the best-known algorithm for the general problem is not polynomial time KlivansS04 . A potentially less demanding model allows for an additional source of information through membership queries (MQ). In this model, in addition to random examples, the learner can ask for the label of the target function on any input. Valiant1984 gave an efficient MQ learning algorithm for Monotone DNF. Since then, several subclasses of DNF have been shown to be learnable in this model (e.g. ( Bshouty95 ; Kushilevitz96 ; ABKKPR1998 ; HellersteinKSS12 ) ). AngluinK95 have shown that (under cryptographic assumptions) the general distribution free case for general DNF is not easier with MQ. On the other hand, positive results have been obtained for specific distributions. Jackson1997 gave the first polynomial time MQ learning algorithm for DNF over c -bounded product distributions. This result was based on the Fourier representation of functions over the Boolean cube linial1993constant and combines the algorithm by KM1993 (henceforth KM algorithm) for finding the heavy Fourier coefficient of a boolean function Goldreich1989 ; KM1993 with Boosting. The approach was elaborated and improved by several authors BshoutyJT04 ; Feldman07 ; Kalai2009 ; Feldman2012 . However, to date, the Fourier approach has been largely limited to product distributions and implications for DNF learnability are restricted to such distributions. In this paper, we provide a significant extension of these results to a broad class of distributions. To achieve this the paper makes several distinct contributions. First, we develop a novel generalized Fourier representation induced by any distribution D , by using the Bayesian Network (BN) representation of D . A BN specifies a distribution using a DAG ( DAG ) and conditional probability distributions where each node is conditioned on its parents Pearl1989 ; KollerFriedman2009 . The generalized Fourier expansion constructs basis functions \phi_{S} for S\subseteq\{1,\ldots,n\} using the graph structure and conditional probabilities that specify the BN, yielding an orthonormal basis so that for any function we have f(\mathbf{x})=\sum_{S}\hat{f}_{\mathcal{S}}\phi_{S}(\mathbf{x}) . While the new basis preserves some important properties, unlike the standard construction, it does not impose sparsity. That is, if f depends only on a subset of variables T and S\setminus T\not=\emptyset , the value of the coefficient \hat{f}_{\mathcal{S}} may not be zero. The second contribution is showing that the KM algorithm can be extended for the new basis and with high probability it recovers all the large coefficients, |\hat{f}_{\mathcal{S}}|\geq\theta , of a function f . The algorithm does not require inference with the BN (e.g. calculating marginal or conditional probabilities) that can be computationally hard but only requires forward sampling which is always feasible. Our third contribution is in analyzing the Fourier representation of conjunctions g with d literals, specifically providing bounds for its spectral norm L_{1}(g)=\sum_{S}|\hat{g}_{S}| . This type of analysis is easy for the uniform case (where L_{1}=1 BlumFJKMR94 ; Khardon94 ) and the product case (where L_{1}=O(2^{d/2}) Feldman2012 ), but is nontrivial for general distributions due to the fact that sparsity does not hold. We show that the values of the coefficients are determined in a combinatorial manner by the values of the corresponding BN parameters. We then derive bounds for a broad class of difference bounded tree BN distributions, where the value of a parent can change the conditional probability of a child by at most \alpha<0.5 (noting that product distributions satisfy this with \alpha=0 ). In particular, in chain BNs we have L_{1}(g)=O((\frac{2}{1-2\alpha})^{d}) and for tree BN we have L_{1}(g)=O((\frac{2}{1-2\alpha})^{2d}) . The upper bounds are complemented by showing that without boundedness or without a tree structure the spectral norm can be exponentially large even for d=1 . As a byproduct, our analysis also provides an exact value for the spectral norm in the product case. Finally, in addition to tree distributions, we analyze the spectral norm of conjunctions under k -junta distributions AliakbarpourBR16 showing that L_{1}(g)=O(2^{(k+d)/2}) . Our fourth contribution includes the main results of this paper, showing that the extended KM algorithm can be directly used to learn decision trees and the algorithm PTFconstruct of Feldman2012 can be used with a slight modification (removing the filtering of large degree coefficients, which is only suitable with sparsity) to learn DNF, under the corresponding families of distributions. Finally, note that the discussion so far assumed that a BN representation of the distribution is given to the learner. While learning general distributions is computationally hard, it is well known that tree BN are learnable Chow1968 ; Hoffgen93 ; BhattacharyyaGPTV23 . Our fifth contribution is a learnability analysis for difference-bounded tree distributions. We develop two variants of the base algorithm, one for the realizable case where the target is known to be a bounded tree distribution and a slightly more complex algorithm for the unrealizable case, showing polynomial learnability in both cases. Combined with the results above this shows the learnability of DNF even when the distribution is not known in advance. Summary of the contributions: To summarize, the paper develops a generalized Fourier basis and shows that major algorithmic tools from learning theory can be used with this basis. Using these and an analysis of the spectral norm for conjunctions, the paper shows the learnability of DNF under difference-bounded tree distributions, significantly extending previous results to a broad class of distributions. We emphasize that the basis and the extended KM algorithm are valid for any distribution and they do not require a tree structure or boundedness. These conditions are required