論文の概要: On the Completeness and Complexity of the Lifted Dynamic Junction Tree
Algorithm
- arxiv url: http://arxiv.org/abs/2110.09197v2
- Date: Tue, 19 Oct 2021 12:13:08 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-20 11:49:45.969241
- Title: On the Completeness and Complexity of the Lifted Dynamic Junction Tree
Algorithm
- Title(参考訳): lifted dynamic junction treeアルゴリズムの完全性と複雑性について
- 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は現実的な観点からだけでなく、理論的観点からも合理的に推論タスクを解くことができるモデルの数を推し進める。
関連論文リスト
- Making RL with Preference-based Feedback Efficient via Randomization [11.019088464664696]
人間のフィードバックから学習する強化学習アルゴリズムは、統計複雑性、計算複雑性、クエリ複雑性の点で効率的である必要がある。
提案するアルゴリズムは, サンプル効率のよいアルゴリズム(すなわち, ほぼ最適ケースの後悔境界)と実行時間(すなわち, 関連するパラメータに関して計算複雑性が最悪の場合)を提案する。
結果をより一般的な非線形関数近似に拡張するために、トンプソンサンプリングのアイデアに触発されたモデルベースランダム化アルゴリズムを設計する。
論文 参考訳(メタデータ) (2023-10-23T04:19:35Z) - Exploring Viable Algorithmic Options for Learning from Demonstration
(LfD): A Parameterized Complexity Approach [0.0]
本稿では,パラメータ化複雑性解析を用いて,アルゴリズムの選択肢を体系的に探索する方法を示す。
環境、実演、ポリシーに対する多くの(しばしば同時に)制限に対して、我々の問題は、一般的にも、あるいは相対的に、効率的に解決できないことを示す。
論文 参考訳(メタデータ) (2022-05-10T15:54:06Z) - Learning Linear Temporal Properties from Noisy Data: A MaxSAT Approach [22.46055650237819]
雑音の存在下でも簡潔な公式を推測するための2つのアルゴリズムを考案する。
我々の第一のアルゴリズムは、推論問題を満足できる問題に還元することで最小の式を推論する。
第2の学習アルゴリズムは、決定木学習アルゴリズムに基づく公式上の決定木を導出する第1のアルゴリズムに依存している。
論文 参考訳(メタデータ) (2021-04-30T16:06:03Z) - 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) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳(メタデータ) (2020-08-29T14:58:26Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。
この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。
我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文 参考訳(メタデータ) (2020-06-21T15:32:21Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。