論文の概要: The Limits of Tractable Marginalization

• arxiv url: http://arxiv.org/abs/2506.12020v1
• Date: Thu, 17 Apr 2025 07:54:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-22 23:32:14.581302
• Title: The Limits of Tractable Marginalization
• Title（参考訳）: トラクタブル・マージナライゼーションの限界
• Authors: Oliver Broadrick, Sanyam Agarwal, Guy Van den Broeck, Markus Bläser,
• Abstract要約: マージナライゼーション(Marginalization) -- すべての代入をその入力のサブセットにまとめること -- は、基本的な計算問題である。 関数に対して仮想的なエビデンスを余分に実行する効率的な実RAMが存在する場合、その関数のマルチ線形表現のための小さな回路が存在することを示す。 その結果、関数に対して仮想的なエビデンスを余分に実行する効率的な実RAMが存在する場合、その関数のマルチ線形表現のための小さな回路が存在することを示す。
• 参考スコア（独自算出の注目度）: 23.716205079188608
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Marginalization -- summing a function over all assignments to a subset of its inputs -- is a fundamental computational problem with applications from probabilistic inference to formal verification. Despite its computational hardness in general, there exist many classes of functions (e.g., probabilistic models) for which marginalization remains tractable, and they can be commonly expressed by polynomial size arithmetic circuits computing multilinear polynomials. This raises the question, can all functions with polynomial time marginalization algorithms be succinctly expressed by such circuits? We give a negative answer, exhibiting simple functions with tractable marginalization yet no efficient representation by known models, assuming $\textsf{FP}\neq\#\textsf{P}$ (an assumption implied by $\textsf{P} \neq \textsf{NP}$). To this end, we identify a hierarchy of complexity classes corresponding to stronger forms of marginalization, all of which are efficiently computable on the known circuit models. We conclude with a completeness result, showing that whenever there is an efficient real RAM performing virtual evidence marginalization for a function, then there are small circuits for that function's multilinear representation.
• Abstract（参考訳）: 行列化(英: Marginalization、英: Marginalization)とは、確率論的推論から形式的検証まで、アプリケーションの基本的な計算問題である。 一般に計算の困難さにもかかわらず、余分化が引き起こされる関数のクラス(例えば確率モデル)が多数存在し、多線型多項式を演算する多項式サイズの算術回路で表される。 多項式時間境界化アルゴリズムを持つすべての関数は、そのような回路によって簡潔に表現できるのだろうか? 負の答えを与え、抽出可能な余分化を持つ単純な関数を示すが、既知のモデルによる効率的な表現は、$\textsf{FP}\neq\#\textsf{P}$($\textsf{P} \neq \textsf{NP}$)と仮定する。 この目的のために、より強力な境界化形式に対応する複雑性クラス階層を同定し、これら全ては既知の回路モデル上で効率的に計算可能である。 完全性の結果から、関数に対して仮想的なエビデンスを余分に実行する効率的な実RAMが存在する場合、その関数のマルチ線形表現のための小さな回路が存在することを示す。

関連論文リスト

• Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits [58.63897489864948]
  結果に基づくフィードバックによる強化学習は、根本的な課題に直面します。 適切なアクションにクレジットを割り当てるには? 本稿では,一般関数近似を用いたオンラインRLにおけるこの問題の包括的解析を行う。
  論文  参考訳（メタデータ） (2025-05-26T17:44:08Z)
• Polynomial Semantics of Tractable Probabilistic Circuits [29.3642918977097]
  これらの回路モデルはそれぞれ、その1つの回路を1つの回路に変換できるという意味で等価であることを示す。 それらはすべて、同じ分布のクラスにおける余分な推論のために抽出可能である。
  論文  参考訳（メタデータ） (2024-02-14T11:02:04Z)
• Provable General Function Class Representation Learning in Multitask Bandits and MDPs [58.624124220900306]
  マルチタスク表現学習は、サンプル効率を高めるために強化学習において一般的なアプローチである。 本研究では,解析結果を一般関数クラス表現に拡張する。 バンディットと線形MDPの一般関数クラスにおけるマルチタスク表現学習の利点を理論的に検証する。
  論文  参考訳（メタデータ） (2022-05-31T11:36:42Z)
• On the energy landscape of symmetric quantum signal processing [1.5301252700705212]
  我々は、ある特定の大域的解(「大域的最小」と呼ばれる)が、コスト関数が大域的関数であるような0ドルに属することを証明した。 最適化アルゴリズムの部分的説明について説明する。
  論文  参考訳（メタデータ） (2021-10-11T04:16:48Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  ジャンクションツリーアルゴリズムは、実行時の保証と正確なMAP推論のための最も一般的な解である。 本稿では,ノードのクローン化による新たなグラフ変換手法を提案する。
  論文  参考訳（メタデータ） (2019-12-27T13:30:29Z)

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

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