論文の概要: On the Completness and Complexity of the Lifted Dynamic Junction Tree Algorithm

• arxiv url: http://arxiv.org/abs/2110.09197v1
• Date: Mon, 18 Oct 2021 11:36:06 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-20 00:31:14.986927
• Title: On the Completness and Complexity of the Lifted Dynamic Junction Tree Algorithm
• Title（参考訳）: リフテッド動的ジャンクションツリーアルゴリズムの完全性と複雑性について
• Authors: Marcel Gehrke
• Abstract要約: 我々は、時間的持ち上げアルゴリズムの第一の完全性と複雑性の分析を、私たちの知識の最大限に活用するために貢献する。 LDJTは,命題時間推定アルゴリズムと比較して,複雑性の観点から多くの利点があることを示す。
• 参考スコア（独自算出の注目度）: 1.1748284119769041
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Lifted inference allows to perform inference in polynomial time w.r.t. domain sizes. For a lifted algorithm, completeness investigates model classes for which the algorithm is guaranteed to compute a lifted solution. We contribute, to the best of our knowledge, the first completeness and complexity analysis for a temporal lifted algorithm, the so-called lifted dynamic junction tree algorithm (LDJT). To treat time as a first class citizen, LDJT introduces some constraints. Given these constraints, we analyse the classes of liftable models. Further, we show that LDJT has many advantages from a complexity point of view compared to a propositional temporal inference algorithm w.r.t. domain sizes. Therefore, LDJT advances the number of models for which inference tasks can be solved in reasonable time not only from a practically point of view, but also from a theoretical point of view.
• Abstract（参考訳）: lifted inferenceは多項式時間 w.r.t. ドメインサイズでの推論を可能にする。 解き上げられたアルゴリズムに対して、完全性は解き上げられた解を計算することが保証されるモデルクラスを調べる。 我々は,時間的昇降アルゴリズム,いわゆる昇降動的ジャンクションツリーアルゴリズム(LDJT)の最初の完全性と複雑性の解析に,私たちの知る限り貢献する。 LDJTは、時間を第一級市民として扱うために、いくつかの制約を導入する。 これらの制約から、持ち上げ可能なモデルのクラスを分析する。 さらに、LDJTは、命題時間推定アルゴリズムw.r.t.ドメインサイズと比較して複雑さの観点から多くの利点があることを示す。 したがって、LDJTは現実的な観点からだけでなく、理論的観点からも合理的に推論タスクを解くことができるモデルの数を推し進める。

関連論文リスト

• Infinite-Resolution Integral Noise Warping for Diffusion Models [16.820996670500357]
  トレーニング不要なノイズ空間操作は、効果的なテクニックであることが証明されている。 課題は、時間的一貫性を付加しながら、ガウスのホワイトノイズ分布を保存することである。 計算コストを桁違いに削減しつつ,無限解像度の精度を実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-11-02T11:05:00Z)
• Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise [9.82187447690297]
  マルコフ雑音を伴う線形2時間スケール近似 (SA) の反復に対して, 厳密な収束を特徴付ける。 この結果は,Polyak平均化を用いたTD学習,GTD,GTD2など,様々なRLアルゴリズムの収束挙動の確立に応用できる。
  論文  参考訳（メタデータ） (2023-12-31T01:30:14Z)
• Provably Efficient Exploration in Constrained Reinforcement Learning:Posterior Sampling Is All You Need [15.113053885573171]
  本稿では,制約付きマルコフ決定過程(CMDP)における学習のための後方サンプリングに基づく新しいアルゴリズムを提案する。 このアルゴリズムは,既存のアルゴリズムと比較して経験的に有利でありながら,ほぼ最適の後悔境界を達成している。
  論文  参考訳（メタデータ） (2023-09-27T15:48:36Z)
• The Adversary Bound Revisited: From Optimal Query Algorithms to Optimal Control [0.0]
  このノートは"One-Way Ticket to Las Vegas and the Quantum Adversary"という論文を補完している。 私は、Barnum-Saks-Szegedyと同じ視点で、逆境界-普遍アルゴリズムの双対性を異なる形で開発する。
  論文  参考訳（メタデータ） (2022-11-29T15:25:45Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。 我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。 これらのアルゴリズムに対する漸近的理論的保証を提供する。
  論文  参考訳（メタデータ） (2022-04-07T00:11:05Z)
• Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
  既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。 提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
  論文  参考訳（メタデータ） (2021-03-03T22:42:15Z)
• Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers [112.23981192818721]
  BaB プロセス中に線形計画法 (LP) を置き換えるために, 逆モード線形緩和に基づく解析法 (LiRPA) を提案する。 LPとは異なり、LiRPAを適用すると、より弱い境界が得られ、分割時にサブドメインのコンフリクトをチェックすることもできない。 既存のLPベースのアプローチと比較して、桁違いのスピードアップを示す。
  論文  参考訳（メタデータ） (2020-11-27T16:42:12Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
  論文  参考訳（メタデータ） (2020-06-08T09:25:47Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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