Abstract
Representing Boolean functions (BFs) as sparse Polynomial Threshold Functions (PTFs) is a critical task in neural network theory and hardware optimization. However, finding the parsimonious representation with the minimum number of monomials is computationally expensive. This paper evaluates two new heuristic algorithms—L-Heuristic and B-Heuristic—designed to find low-density PTFs efficiently. Our findings show that these heuristics significantly outperform traditional Genetic Algorithms (GAs) in both speed and sparsity, with the B-Heuristic offering a particularly effective trade-off for high-dimensional applications.
Introduction
A Boolean function $f: \{0,1\}^n \to \{-1, 1\}$ can be represented by a Polynomial Threshold Function (PTF) such that $f(x) = \text{sgn}(P(x))$, where $P(x)$ is a polynomial. The "density" of a PTF is defined by the number of non-zero coefficients (monomials) in $P(x)$. Minimizing this density is highly desirable for simplifying hardware implementations and reducing computational overhead. Since exhaustive search for the minimal PTF is intractable for larger $n$, heuristic methods are required to find sparse representations within reasonable timeframes.
Methodology
We compared four distinct algorithmic approaches for generating sparse PTFs:
- 3-Quarters Algorithm: A deterministic method providing a theoretical upper bound of $0.75 \cdot 2^n$ monomials.
- L-Heuristic (Linear): A greedy approach that sorts monomials by their spectral coefficients and attempts to eliminate them sequentially.
- B-Heuristic (Binary): An optimized version of the L-Heuristic that uses a binary search strategy to eliminate groups of monomials simultaneously, reducing the number of solver calls from $O(2^n)$ to $O(n)$.
- Genetic Algorithm (GA): An evolutionary search strategy utilizing crossover and mutation to navigate the space of possible monomial combinations.
The heuristics leverage spectral coefficients as a guide, prioritizing the elimination of terms that contribute least to the function's output.
Experimental Results
The algorithms were benchmarked using 4-variable Boolean functions. The performance metrics focused on the average number of monomials (sparsity) and the average computation time.
As shown in the results, the L-Heuristic achieved the best overall sparsity, averaging approximately 4.97 monomials. However, the B-Heuristic proved to be the most efficient in terms of the speed-to-sparsity ratio, running roughly three times faster than the L-Heuristic while maintaining a low average monomial count of 5.81.
The distribution analysis reveals that while the 3-Quarters algorithm and GA often result in higher density, the L-Heuristic and B-Heuristic consistently shift the distribution toward fewer monomials. Notably, the Genetic Algorithm performed poorly, likely due to a rugged fitness landscape that hinders standard evolutionary operators.
Discussion and Conclusion
The study demonstrates that spectral-guided heuristics are far more effective than general-purpose evolutionary algorithms for PTF minimization. The L-Heuristic is preferred when absolute sparsity is required, whereas the B-Heuristic is ideal for scenarios where computational resources are limited or the number of variables is large. Future research will explore the scalability of the B-Heuristic for $n > 10$ and its direct application in optimizing threshold logic gates for specialized hardware.
Summary updated