Heuristic algorithms for obtaining Polynomial Threshold Functions with low densities
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Top-down induction of decision trees: rigorous guarantees and inherent limitations
Consider the following heuristic for building a decision tree for a function $f : \{0,1\}^n \to \{\pm 1\}$. Place the most influential variable $x_i$ of $f$ at the root, and recurse on the subfunctions $f_{x_i=0}$ and $f…
Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects
The tree-width of a multivariate polynomial is the tree-width of the hypergraph with hyperedges corresponding to its terms. Multivariate polynomials of bounded tree-width have been studied by Makowsky and Meer as a new s…
Explainable artificial intelligenceExplainable Artificial Intelligence (XAI)Active Learning Polynomial Threshold Functions
We initiate the study of active learning polynomial threshold functions (PTFs). While traditional lower bounds imply that even univariate quadratics cannot be non-trivially actively learned, we show that allowing the lea…
Active LearningChamber geometry and specification numbers of Boolean threshold functions
The specification number $σ_n(f)$ of a Boolean threshold function $f$ on $n$ variables is the least number of points whose $f$-values determine $f$ uniquely among all threshold functions. Its essential points form the un…
Downsampling for Testing and Learning in Product Distributions
We study distribution-free property testing and learning problems where the unknown probability distribution is a product distribution over $\mathbb{R}^d$. For many important classes of functions, such as intersections o…