論文の概要: Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects

• arxiv url: http://arxiv.org/abs/2501.08297v1
• Date: Tue, 14 Jan 2025 18:28:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-15 13:26:36.150021
• Title: Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects
• Title（参考訳）: 境界木幅の多項式閾値関数:説明可能性と複雑さ
• Authors: Karine Chubarian, Johnny Joyce, Gyorgy Turan,
• Abstract要約: 多変量体のツリー幅は、ハイパーグラフのツリー幅であり、その項に対応するハイパーエッジを持つ。 有界木幅の符号としてのブール関数の表現はしきい値表現と呼ばれる。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 多変量多項式のツリー幅は、その項に対応するハイパーエッジを持つハイパーグラフのツリー幅である。 有界木幅の多変量多項式は、Makowsky と Meer によって、一般に難解である問題の多項式可解性を許容する新しい疎性条件として研究されている。 ブール変数に対するこのテーマのバリエーションについて考察する。 多項式の符号としてのブール関数の表現は多項式しきい値表現と呼ばれる。 本稿では,有界木幅の多項式しきい値関数として表現可能なブール関数について論じ,確率的グラフィカルモデルであるベイズネットワーク分類器への2つの応用について述べる。 どちらのアプリケーションも、最近の機械学習モデルのブラックボックスの性質を扱う研究領域である、説明可能な人工知能(XAI)にある。 また、正と一般多項式閾値関数の表現力の分離結果を与える。

関連論文リスト

• Equivariant Graph Network Approximations of High-Degree Polynomials for Force Field Prediction [62.05532524197309]
  同変深部モデルでは、分子動力学シミュレーションにおいて原子ポテンシャルと力場を正確に予測できることが示されている。 本研究では、同変アーキテクチャの同変関数を解析し、PACEと呼ばれる新しい同変ネットワークを導入する。 一般的なベンチマークで実験されたように、PACEは原子エネルギーと力場の予測における最先端のパフォーマンスを示す。
  論文  参考訳（メタデータ） (2024-11-06T19:34:40Z)
• Simple Multigraph Convolution Networks [49.19906483875984]
  既存のマルチグラフ畳み込み法では、複数のグラフ間のクロスビューの相互作用を無視するか、あるいは標準的なクロスビュー演算子によって非常に高い計算コストが生じる。 本稿では,まずエッジレベルやサブグラフレベルのトポロジを含むマルチグラフから一貫したクロスビュートポロジを抽出し,その後,生のマルチグラフと一貫したトポロジに基づいて拡張を行う,シンプルなマルチ畳み込みネットワーク(SMGCN)を提案する。 理論上、SMGCNは標準的なクロスビュー拡張ではなく、一貫した拡張のトポロジを利用して、信頼性の高いクロスビュー空間メッセージパッシングを行い、標準拡張の複雑さを効果的に低減する。
  論文  参考訳（メタデータ） (2024-03-08T03:27:58Z)
• Polynomial Semantics of Tractable Probabilistic Circuits [29.3642918977097]
  これらの回路モデルはそれぞれ、その1つの回路を1つの回路に変換できるという意味で等価であることを示す。 それらはすべて、同じ分布のクラスにおける余分な推論のために抽出可能である。
  論文  参考訳（メタデータ） (2024-02-14T11:02:04Z)
• The Expressibility of Polynomial based Attention Scheme [8.517077915534932]
  大規模言語モデル(LLM)は、私たちの日常生活の様々な側面を著しく改善しました。 変換器における注意の二次的複雑さは、長いテキストを処理するためにこれらのモデルをスケールアップする際の課題である。 本稿では,表現的注意力に関する理論的分析を行う。
  論文  参考訳（メタデータ） (2023-10-30T22:16:18Z)
• Revisiting Tropical Polynomial Division: Theory, Algorithms and Application to Neural Networks [40.137069931650444]
  熱帯幾何学は、最近、一方向線形活性化関数を持つニューラルネットワークの解析にいくつかの応用を見出した。 本稿では,熱帯分断問題に対する新たな考察とニューラルネットワークの単純化への応用について述べる。
  論文  参考訳（メタデータ） (2023-06-27T02:26:07Z)
• State polynomials: positivity, optimization and nonlinear Bell inequalities [3.9692590090301683]
  本稿では,非可換変数の状態とそれらの積の形式状態を紹介する。 これは、すべての正の状態と正の状態が、分母を持つ正方形の和であることを示している。 また、Avinetengle Kritivsatzが状態設定で保持できないことも確認されている。
  論文  参考訳（メタデータ） (2023-01-29T18:52:21Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。 アルファベットのサイズについては、定値対分離の複雑さがある。
  論文  参考訳（メタデータ） (2023-01-22T22:08:28Z)
• CoPE: Conditional image generation using Polynomial Expansions [50.67390290190874]
  入力変数を2つ拡張し,それらの自己相関と相互相関をキャプチャする,copeと呼ばれる汎用フレームワークを導入する。 CoPEは8つのデータセットを含む5つのタスク(クラスジェネレーション、逆問題、エッジ・ツー・イメージ翻訳、イメージ・ツー・イメージ翻訳、属性誘導生成)で評価される。 徹底的な評価は、CoPEが多様な条件生成タスクに取り組むのに役立つことを示唆している。
  論文  参考訳（メタデータ） (2021-04-11T19:02:37Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。 それらの構造的特性について検討する。
  論文  参考訳（メタデータ） (2020-12-01T13:53:23Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• PDE constraints on smooth hierarchical functions computed by neural networks [0.0]
  ディープニューラルネットワーク理論における重要な問題は、表現性である。 フィードフォワードニューラルネットワークによって実装された実無限微分可能(滑らか)階層関数について検討する。 このようなPDE制約は、一旦適切な非特異性条件を伴って、考慮中の滑らかな関数をネットワークで表現できることを保証する。
  論文  参考訳（メタデータ） (2020-05-18T16:34:11Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。