Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects
Karine Chubarian, Johnny Joyce, György Turán · 2025
Read Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects by Karine Chubarian, Johnny Joyce, György Turán (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-2501-08297.txt.
Introduction
Karine Chubarian, Johnny Joyce, and Gyorgy Turan study a spare way to write yes-no rules in a 2025 paper. A rule can be cast as the sign of a number formula, plus or minus. When the formula's web of terms stays narrow, like a thin tree, hard tasks can turn easy to solve.
The team asks which yes-no rules fit that spare form, and what the form costs to find and read. Two uses land on Bayes net classifiers, a known tool that sorts cases by chance. Both uses serve clear AI, where users must see why a model chose as it did.
Catalog record
| CREATOR | Karine Chubarian, Johnny Joyce, György Turán |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-08297
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects Karine Chubarian, Johnny Joyce, György Turán 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. Dedicated to Janos Makowsky on the occasion of his 75th birthday 1 Introduction 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 [ 32 , 33 ] as a new sparsity condition that allows for polynomial solvability of problems which are intractable in general. The paper is closely related to Courcelle, Makowsky and Rotics [ 7 ] and to Fischer, Makowsky and Ravve [ 14 ] . The topics covered are polynomials, graphs, widths, counting and logic . We discuss a variation on this theme, in the context of Boolean functions. Polynomials, graphs, widths, counting and (propositional) logic all appear, although the context is different. The problems considered are from Explainable Artificial Intelligence (XAI) and complexity theory. Boolean functions f:\{0,1\}^{n}\to\{0,1\} can be represented by multivariate polynomials exactly or approximately in a many different ways over GF(2) or the reals. In this paper we consider polynomials over the reals. As x^{2}=x for 0 and 1, polynomials can be assumed to be multilinear. Let p(x_{1},\ldots,x_{n})=\sum_{I\in{\cal I}}\beta_{I}x_{I} (1) be a multilinear polynomial, where {\cal I} is a family of subsets of [n] , \beta_{I}\in\mathbb{R} and x_{I}=\prod_{i\in I}x_{i} . The degree of the polynomial is the maximal number of variables in a term, and its size is the number of terms. One can consider the Boolean function \text{sgn}(p(x_{1},\ldots,x_{n}))\,:\{0,1\}^{n}\to\{0,1\}, where sgn is the sign function (1 for nonnegative values and 0 otherwise). For example, \text{sgn}(x_{1}+x_{2}+x_{3}+x_{4}-x_{1}x_{2}-x_{3}x_{4}-2) (2) represents the 4-variable Boolean function which has value 1 iff (x_{1},x_{2},x_{3},x_{4}) contains at least three 1s, or both (x_{1},x_{2}) and (x_{3},x_{4}) contain exactly one 1. Every Boolean function can be represented in this form, called a polynomial threshold function (PTF) representation (see Sect. 2.1 ). The smallest degree and size of polynomials representing a Boolean function are important measures of its complexity. A Boolean function is a degree- d polynomial threshold function if it can be written as the sign of a degree- d polynomial. Linear threshold functions (LTF or perceptrons) played an important role since the beginning of machine learning. We consider the minimal tree-width of polynomial sign-representations as a measure of complexity of a Boolean functions. Consider a polynomial p as in ( 1 ). The term-hypergraph H_{p} of polynomial p has vertex set [n] and edge set {\cal I} . The tree-width of polynomial p is the tree-width of its term-hypergraph H_{p} . A Boolean function is a tree-width- k polynomial threshold function if it can be written as the sign of a tree-width- k polynomial. Thus, for example, the Boolean function ( 2 ) has tree-width 1. Polynomial threshold representations are useful in many different areas. One of these is a probabilistic graphical model, the Bayesian network classifier (BNC) [ 15 ] , a generalization of the Naive Bayes classifier. A Bayesian network classifier can be represented by a polynomial threshold function, where the terms reflect the graphical structure of the network (see Sect. 3 ). Polynomials representing the Naive Bayes classifier are linear. Tree Augmented Bayesian network classifiers (TAN) have additional edges forming a forest [ 15 ] 1 1 1 [ 15 ] considers trees only, but here one can use forests as well. . They correspond to quadratic polynomial threshold functions (QTF), where the quadratic terms correspond to the edges of the forest. Bayesian network classifiers with a bounded tree-width network structure correspond to polynomials of bounded tree-width. Bounded tree-width Bayesian networks form a tractable subclass for several inference and learning problems [ 8 , 24 ] . In this paper we consider some aspects of Bayesian network classifiers related to their explainability. Explainability Recent machine learning models, in particular deep neural networks, are often black boxes in the sense that they do not provide an explanation for the output produced, and this hinders the development of trustworthy AI. Standard examples are that a rejected loan applicant needs to know the reason for the rejection, and a physician needs to know reasons for a suggested diagnosis. The need for explanations has a long history in machine learning 2 2 2 For example, the MYCIN expert system contained an “Explanation System, which understands simple English questions and answers them in order to justify its decisions or instruct the user” [ 45 ] . , but the recent developments amplified the relevance of this issue and brought about Explainable AI as a separate field of research [ 35 ] . How to define what is an explanation is a difficult question, which has a long history in the philosophy of science. The type of explanation relevant in a particular machine learning application is context-dependent. A post-hoc explanation provides an explainable model 3 3 3 In the literature an explainable model, such as a decision tree, is usually referred to as an interpretable model. As interpretations are used in logic in a different sense, and also for simplifying terminology, we use explainability for this purpose as well. corresponding (exactly or approximately) to a black-box model. Post-hoc explanations can be global or local , depending on whether the whole model is explained or only its behavior on a specific input. Even if there is an agreed upon notion of explanation, it is usually not clear how to evaluate the explanations provided, one reason being the lack of ground truth (e.g., what is the reason for classifying an image as a cat?). A neural network is usually considered non-explainable and a decision tree is usually considered explainable (but see, for example, [ 28 ] for a discussion of this distinction). Probabilistic graphical models are somewhere in between, having both explainable and non-explainable features. A Bayesian network, on one hand, gives explicit graphical information about conditional independencies. On the other hand, probabilistic inference is hard, and usually not explainable for the user. This holds even for the Naive Bayes classifier. Therefore, explaining Bayesian networks has been studied for a long time [ 27 ] . Explaining Bayesian Network Classifiers by Approximate OBDD A post-hoc approach to global explanations for Naive Bayes classifiers, proposed by [ 5 ] , is to compile them into Ordered Binary Decision Diagrams (OBDD) [ 48 ] . This is an instance of knowledge compilation , transforming