Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.08297 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913649688313856 |
|---|---|
| author | Chubarian, Karine Joyce, Johnny Turan, Gyorgy |
| author_facet | Chubarian, Karine Joyce, Johnny Turan, Gyorgy |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_08297 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects Chubarian, Karine Joyce, Johnny Turan, Gyorgy Machine Learning Artificial Intelligence 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. |
| title | Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2501.08297 |