論文の概要: A Compositional Atlas for Algebraic Circuits

• arxiv url: http://arxiv.org/abs/2412.05481v1
• Date: Sat, 07 Dec 2024 00:51:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-10 14:59:10.183346
• Title: A Compositional Atlas for Algebraic Circuits
• Title（参考訳）: 代数回路のための合成アトラス
• Authors: Benjie Wang, Denis Deratani Mauá, Guy Van den Broeck, YooJung Choi,
• Abstract要約: クエリの大規模なクラスは、半環上の基本演算子(アグリゲーション、製品、および要素ワイドマッピング)の組み合わせに対応することを示す。 分析を応用して、このような多くの合成クエリに対して、新しいトラクタビリティ条件を導出する。
• 参考スコア（独自算出の注目度）: 35.95450187283255
• License:
• Abstract: Circuits based on sum-product structure have become a ubiquitous representation to compactly encode knowledge, from Boolean functions to probability distributions. By imposing constraints on the structure of such circuits, certain inference queries become tractable, such as model counting and most probable configuration. Recent works have explored analyzing probabilistic and causal inference queries as compositions of basic operators to derive tractability conditions. In this paper, we take an algebraic perspective for compositional inference, and show that a large class of queries - including marginal MAP, probabilistic answer set programming inference, and causal backdoor adjustment - correspond to a combination of basic operators over semirings: aggregation, product, and elementwise mapping. Using this framework, we uncover simple and general sufficient conditions for tractable composition of these operators, in terms of circuit properties (e.g., marginal determinism, compatibility) and conditions on the elementwise mappings. Applying our analysis, we derive novel tractability conditions for many such compositional queries. Our results unify tractability conditions for existing problems on circuits, while providing a blueprint for analysing novel compositional inference queries.
• Abstract（参考訳）: 和積構造に基づく回路は、ブール関数から確率分布まで、知識をコンパクトに符号化するためのユビキタス表現となっている。 このような回路の構造に制約を課すことで、モデルカウントや最も確率の高い構成など、特定の推論クエリがトラクタブルになる。 近年, トラクタビリティ条件を導出するための基本演算子の構成として, 確率的および因果推論クエリの解析が検討されている。 本稿では,構成推論の代数的視点を考察し,限界MAP,確率的応答セットプログラミング推論,因果的バックドア調整などを含む多数のクエリが,半環上の基本演算子(アグリゲーション,積,要素対応マッピング)の組合せに対応していることを示す。 この枠組みを用いて、回路特性(例えば、限界決定性、互換性)と要素写像の条件から、これらの作用素の抽出可能な合成のための単純で一般的な条件を明らかにする。 分析を応用して、このような多くの合成クエリに対して、新しいトラクタビリティ条件を導出する。 本結果は,回路上の既存の問題に対するトラクタビリティ条件を統一するとともに,新しい構成推論クエリを解析するためのブループリントを提供する。

関連論文リスト

• The Computational Complexity of Circuit Discovery for Inner Interpretability [0.30723404270319693]
  我々は古典的およびパラメータ化された計算複雑性理論を用いて回路発見を研究する。 私たちの発見は、難しい複雑さの風景を明らかにします。 このフレームワークは、解釈可能性クエリの範囲と限界を理解するのに役立ちます。
  論文  参考訳（メタデータ） (2024-10-10T15:22:48Z)
• Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability [8.618430843854048]
  接続的クエリに対する回答の数をカウントすることは、標準的な仮定では効率的な解を持たないデータベースの基本的な問題である。 固有インスタンスの構造特性を調べ、#-ハイパーツリー分解という新しい概念を導入することにより、抽出可能なクラスをピンポイントする。
  論文  参考訳（メタデータ） (2023-11-24T16:09:12Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。 最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。 シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
  論文  参考訳（メタデータ） (2023-10-05T07:10:40Z)
• Compositional Probabilistic and Causal Inference using Tractable Circuit Models [20.07977560803858]
  我々は、構造化分解可能なPCにおける(マルジナル)決定性の新規な定式化であるmd-vtreesを紹介する。 我々は,PC上でのバックドア調整などの因果推論クエリに対して,最初のpolytimeアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2023-04-17T13:48:16Z)
• ConE: Cone Embeddings for Multi-Hop Reasoning over Knowledge Graphs [73.86041481470261]
  Cone Embeddings (ConE) は、接続、解離、否定を扱える最初の幾何学ベースのクエリ埋め込みモデルである。 ConEは、ベンチマークデータセットの既存の最先端メソッドを大幅に上回る。
  論文  参考訳（メタデータ） (2021-10-26T14:04:02Z)
• Structural Learning of Probabilistic Sentential Decision Diagrams under Partial Closed-World Assumption [127.439030701253]
  確率感性決定図は構造化分解可能な回路のクラスである。 本稿では,回路の論理的基盤を暗黙的に提供する部分閉世界仮定に基づく新しいスキームを提案する。 予備実験では、提案手法がトレーニングデータに適切に適合し、基礎となる論理的基盤と整合性を維持した上で、テストデータによく適合することを示した。
  論文  参考訳（メタデータ） (2021-07-26T12:01:56Z)
• A Compositional Atlas of Tractable Circuit Operations: From Simple Transformations to Complex Information-Theoretic Queries [44.36335714431731]
  本稿では,回路上のモジュラー操作において,機械学習の複雑な推論シナリオがいかに表現できるかを示す。 文献におけるいくつかの結果を一般化し,新たな抽出可能な推論シナリオを開放する,抽出可能なモデルについて推論するための統一的な枠組みを導出する。
  論文  参考訳（メタデータ） (2021-02-11T17:26:32Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  データから制約をマイニングするための一般的なフレームワークを提案する。 特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。 提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-18T20:09:53Z)
• A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings [113.15416137912399]
  構造化予測のための理論的・アルゴリズム的な枠組みを提案し,解析する。 問題に対して適切な幾何を暗黙的に定義する、損失関数の大規模なクラスについて検討する。 出力空間を無限の濃度で扱うとき、推定子の適切な暗黙の定式化が重要であることが示される。
  論文  参考訳（メタデータ） (2020-02-13T10:30:04Z)

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

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