Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects

• URL: http://arxiv.org/abs/2501.08297v1
• Date: Tue, 14 Jan 2025 18:28:08 GMT
• Title: Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects
• Authors: Karine Chubarian, Johnny Joyce, Gyorgy Turan,
• Abstract summary: The tree-width of a multivariate is the tree-width of the hypergraph with hyperedges corresponding to its terms. A representation of a Boolean function as the sign of a bounded tree-width is called a threshold representation.
• Score: 0.6554326244334868
• License:
• 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.

Related papers

• Equivariant Graph Network Approximations of High-Degree Polynomials for Force Field Prediction [62.05532524197309]
  equivariant deep models have shown promise in accurately predicting atomic potentials and force fields in molecular dynamics simulations. In this work, we analyze the equivariant functions for equivariant architecture, and introduce a novel equivariant network, named PACE. As experimented in commonly used benchmarks, PACE demonstrates state-of-the-art performance in predicting atomic energy and force fields.
  arXiv  Detail & Related papers  (2024-11-06T19:34:40Z)
• Simple Multigraph Convolution Networks [49.19906483875984]
  Existing multigraph convolution methods either ignore the cross-view interaction among multiple graphs, or induce extremely high computational cost due to standard cross-view operators. This paper proposes a Simple Multi Convolution Networks (SMGCN) which first extracts consistent cross-view topology from multigraphs including edge-level and subgraph-level topology, then performs expansion based on raw multigraphs and consistent topologies. In theory, SMGCN utilizes the consistent topologies in expansion rather than standard cross-view expansion, which performs credible cross-view spatial message-passing, and effectively reduces the complexity of standard expansion.
  arXiv  Detail & Related papers  (2024-03-08T03:27:58Z)
• Polynomial Semantics of Tractable Probabilistic Circuits [29.3642918977097]
  We show that each of these circuit models is equivalent in the sense that any circuit for one of them can be transformed into a circuit for any of the others with only an increase in size. They are all tractable for marginal inference on the same class of distributions.
  arXiv  Detail & Related papers  (2024-02-14T11:02:04Z)
• The Expressibility of Polynomial based Attention Scheme [8.517077915534932]
  Large language models (LLMs) have significantly improved various aspects of our daily lives. The quadratic complexity of attention in transformer poses a challenge when scaling up these models for processing long texts. This paper offers a theoretical analysis of the capabilities of expressive attention.
  arXiv  Detail & Related papers  (2023-10-30T22:16:18Z)
• Revisiting Tropical Polynomial Division: Theory, Algorithms and Application to Neural Networks [40.137069931650444]
  Tropical geometry has recently found several applications in the analysis of neural networks with piecewise linear activation functions. This paper presents a new look at the problem of tropical division and its application to the simplification of neural networks.
  arXiv  Detail & Related papers  (2023-06-27T02:26:07Z)
• State polynomials: positivity, optimization and nonlinear Bell inequalities [3.9692590090301683]
  This paper introduces states in noncommuting variables and formal states of their products. It shows that states, positive over all and matricial states, are sums of squares with denominators. It is also established that avinetengle Kritivsatz fails to hold in the state setting.
  arXiv  Detail & Related papers  (2023-01-29T18:52:21Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function. For an alphabet size, we have a constant versus separation complexity.
  arXiv  Detail & Related papers  (2023-01-22T22:08:28Z)
• CoPE: Conditional image generation using Polynomial Expansions [50.67390290190874]
  We introduce a general framework, called CoPE, that enables an expansion of two input variables and captures their auto- and cross-correlations. CoPE is evaluated in five tasks (class-generation, inverse problems, edges-to-image translation, image-to-image translation, attribute-guided generation) involving eight datasets. The thorough evaluation suggests that CoPE can be useful for tackling diverse conditional generation tasks.
  arXiv  Detail & Related papers  (2021-04-11T19:02:37Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• PDE constraints on smooth hierarchical functions computed by neural networks [0.0]
  An important problem in the theory of deep neural networks is expressivity. We study real infinitely differentiable (smooth) hierarchical functions implemented by feedforward neural networks. We conjecture that such PDE constraints, once accompanied by appropriate non-singularity conditions, guarantee that the smooth function under consideration can be represented by the network.
  arXiv  Detail & Related papers  (2020-05-18T16:34:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.