Heuristic algorithms for obtaining Polynomial Threshold Functions with low densities.

Can Eren Sezener, Erhan Öztop

TL;DR

This paper introduces and compares several heuristic algorithms for finding compact representations of Boolean functions called Polynomial Threshold Functions (PTFs). The authors demonstrate that their proposed heuristic methods, particularly the "L-Heuristic" and "B-Heuristic," significantly outperform a genetic algorithm and a previous non-heuristic method in finding PTFs with fewer terms, making them more efficient for representing complex Boolean logic.

What Problem Does This Paper Address?

Boolean functions, which are fundamental in computer science and logic, can be represented in various ways. One such representation is a Polynomial Threshold Function (PTF), where a polynomial's sign matches the Boolean function's output. The challenge lies in finding a PTF with the minimum number of terms (monomials), as this leads to more efficient and parsimonious representations. While exact algorithms exist, they are computationally infeasible for even moderately sized problems. This paper tackles the problem of finding efficient PTF representations by developing and evaluating heuristic algorithms that aim to minimize the number of monomials without guaranteeing optimality, but offering practical solutions.

Methods

The paper explores three main algorithmic approaches:

  • L-Heuristic (Algorithm 2): This is a fast heuristic algorithm that sorts monomials based on their spectral coefficients. It iteratively attempts to eliminate "easier" monomials first, then progresses to harder ones in a single pass.
  • B-Heuristic (Algorithm 3): A modification of the L-Heuristic, this algorithm aims to increase speed by using a binary search-like approach to determine the number of monomials to consider for elimination, rather than a linear scan. This significantly reduces the number of calls to the eliminability check subroutine.
  • Genetic Algorithm (GA): The authors frame the problem as an optimization task where a binary vector represents a subset of monomials to be eliminated. A standard binary GA is employed to search for genotypes (vectors) that lead to eliminable subsets, aiming for higher fitness values.

These heuristic methods are compared against each other and against a non-heuristic algorithm by Oztop [1].

Datasets

The paper evaluates the algorithms on 4-variable Boolean functions. The authors state they found PTFs for "4-variable BFs" and present results based on these. No new benchmark datasets are introduced; rather, existing 4-variable Boolean functions are used for evaluation.

Key Insights and Ideas

  • Heuristics Outperform GA for Parsimony: Surprisingly, the proposed heuristic algorithms (L-Heuristic and B-Heuristic) consistently found PTFs with fewer monomials than a Genetic Algorithm, despite GAs being generally powerful optimization tools.
  • B-Heuristic: A Sweet Spot: The B-Heuristic offers an impressive balance between performance (finding PTFs with few monomials) and computational speed, making it a strong candidate for high-dimensional Boolean functions.
  • Spectral Coefficients as a Guide: The intuition that monomials with certain spectral coefficient properties are "easier" to eliminate proves effective in guiding the heuristic search towards parsimonious representations.
  • GA's Struggle with Domain Specificity: The paper suggests that standard GAs may not be well-suited for this specific problem without domain-specific crossover and mutation parameters, highlighting an open area for research in evolutionary computation.

Key Results

  • L-Heuristic: Achieved the lowest average number of monomials (4.9678) for 4-variable BFs, with a very low computation time (0.0654 s).
  • B-Heuristic: Came very close to the L-Heuristic in terms of monomial count (5.8115) but was significantly faster (0.0199 s), making it a highly efficient choice.
  • GA: Produced PTFs with a higher average number of monomials (7.9941) and took considerably longer to compute (4.2678 s).
  • 3-Quarters Algorithm: Performed comparably to the GA in monomial count (8.2720) but was much faster (0.0007 s), suggesting it's a non-heuristic approach that offers some efficiency.
  • Figure 1 shows that the B-Heuristic successfully solved a significant portion of problems with a small number of monomials (e.g., around 10³ problems with 4 monomials).

Limitations and Future Work

  • No Optimality Guarantee: The heuristic algorithms do not guarantee finding the absolute minimum number of monomials.
  • GA Performance: The paper notes the surprising underperformance of GAs and suggests that future work could focus on developing domain-specific crossover and mutation parameters to improve their effectiveness for sign-representation problems.
  • High Dimensionality: While the B-Heuristic is presented as a good choice for "high dimensional BFs," the current experiments are limited to 4-variable functions. Further investigation into scalability for larger numbers of variables would be valuable.

Summary updated

Abstract

In this paper we present several heuristic algorithms, including a Genetic Algorithm (GA), for obtaining polynomial threshold function (PTF) representations of Boolean functions (BFs) with small number of monomials. We compare these among each other and against the algorithm of Oztop via computational experiments. The results indicate that our heuristic algorithms find more parsimonious representations compared to the those of non-heuristic and GA-based algorithms.
BibTeX
@inproceedings{sezener2015heuristic,
  author = {Can Eren Sezener and Erhan Öztop},
  title = {{Heuristic algorithms for obtaining Polynomial Threshold Functions with low densities.}},
  booktitle = {Cologne},
  year = {2015},
}
Figure