Authors: Karine Chubarian, Johnny Joyce, Gyorgy Turan
Abstract: 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 sparsity
condition that allows for polynomial solvability of problems which are
intractable in general. We consider a variation on this theme for Boolean
variables. A representation of a Boolean function as the sign of a polynomial
is called a polynomial threshold representation. We discuss Boolean functions
representable as polynomial threshold functions of bounded tree-width and
present two applications to Bayesian network classifiers, a probabilistic
graphical model. Both applications are in Explainable Artificial Intelligence
(XAI), the research area dealing with the black-box nature of many recent
machine learning models. We also give a separation result between the
representational power of positive and general polynomial threshold functions.
Source: http://arxiv.org/abs/2501.08297v1
