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

• arxiv url: http://arxiv.org/abs/2110.09197v3
• Date: Fri, 31 May 2024 14:15:38 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-03 21:09:19.143640
• Title: On the Completeness and Complexity of the Lifted Dynamic Junction Tree Algorithm
• Title（参考訳）: リフテッド動的ジャンクションツリーアルゴリズムの完全性と複雑さについて
• Authors: Marcel Gehrke,
• Abstract要約: 時空昇降型動的ジャンクションツリーアルゴリズム(LDJT)の最初の完全性および複雑性解析に寄与する。 時間的側面を効率的に扱うため、LDJTは条件付き独立性を使用して時間内に進行し、除去命令に制限を与える。 これらの制限がドメインリフタビリティの結果に影響を及ぼし、時間内に進行する特定のケースがFO12から除外されなければならないことを示す。
• 参考スコア（独自算出の注目度）: 0.2797210504706914
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: For static lifted inference algorithms, completeness, i.e., domain liftability, is extensively studied. However, so far no domain liftability results for temporal lifted inference algorithms exist. In this paper, we close this gap. More precisely, we contribute the first completeness and complexity analysis for a temporal lifted algorithm, the socalled lifted dynamic junction tree algorithm (LDJT), which is the only exact lifted temporal inference algorithm out there. To handle temporal aspects efficiently, LDJT uses conditional independences to proceed in time, leading to restrictions w.r.t. elimination orders. We show that these restrictions influence the domain liftability results and show that one particular case while proceeding in time, has to be excluded from FO12 . Additionally, for the complexity of LDJT, we prove that the lifted width is in even more cases smaller than the corresponding treewidth in comparison to static inference.
• Abstract（参考訳）: 静的昇降推論アルゴリズムでは、完全性(すなわち、ドメインの昇降性)が広く研究されている。 しかし、今のところ時間的持ち上げ推論アルゴリズムのドメインリフト性は存在しない。 本稿では,このギャップを埋める。 より正確には、時間的持ち上げアルゴリズム(LDJT)の最初の完全性および複雑さの解析に貢献する。 時間的側面を効率的に扱うため、LDJTは条件付き独立性を使用して時間内に進行し、除去命令に制限を与える。 これらの制限がドメインのリフタビリティに影響を及ぼし、時間内に進行する特定のケースがFO12から除外されなければならないことを示す。 さらに, 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)

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

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