Fugu-MT 論文翻訳(概要): Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications

論文の概要: Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications

arxiv url: http://arxiv.org/abs/2205.02654v1
Date: Thu, 5 May 2022 13:56:13 GMT
ステータス: 処理完了
システム内更新日: 2022-05-06 13:38:31.359117
Title: Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications
Title（参考訳）: マルコフ等価DAGのカウントとサンプリングのための多項式時間アルゴリズムとその応用
Authors: Marcel Wien\"obst, Max Bannach, Maciej Li\'skiewicz
Abstract要約: マルコフ同値類からの有向非巡回グラフの数え上げとサンプリングは因果解析の基本的な課題である。これらのタスクはグラフィカルな時間で実行可能であることを示す。我々のアルゴリズムは効果的で容易に実装できる。
参考スコア（独自算出の注目度）: 7.766954176188425
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Counting and sampling directed acyclic graphs from a Markov equivalence class are fundamental tasks in graphical causal analysis. In this paper we show that these tasks can be performed in polynomial time, solving a long-standing open problem in this area. Our algorithms are effective and easily implementable. As we show in experiments, these breakthroughs make thought-to-be-infeasible strategies in active learning of causal structures and causal effect identification with regard to a Markov equivalence class practically applicable.
Abstract（参考訳）: マルコフ同値類からの有向非巡回グラフのカウントとサンプリングは、グラフィカル因果解析の基本的なタスクである。本稿では,これらのタスクを多項式時間で実行することができ,この分野における長年のオープンな問題を解く。我々のアルゴリズムは効果的で容易に実装できる。実験で示されたように、これらのブレークスルーは、マルコフ同値類に関する因果構造の活発な学習と因果効果の同定において、事実上適用可能である。

関連論文リスト

On the Markov Property of Neural Algorithmic Reasoning: Analyses and Methods [94.72563337153268]
ForgetNetは歴史的埋め込みを使わないので、タスクのマルコフの性質と一致している。また、G-ForgetNetを導入し、G-ForgetNetは歴史的埋め込みの選択的統合を可能にするゲーティング機構を使用している。我々の実験はCLRS-30アルゴリズム推論ベンチマークに基づいて、ForgetNetとG-ForgetNetの両方が既存の手法よりも優れた一般化を実現することを示した。
論文参考訳（メタデータ） (2024-03-07T22:35:22Z)
Unleashing the Potential of Regularization Strategies in Learning with Noisy Labels [65.92994348757743]
クロスエントロピー損失を用いた単純なベースラインと、広く使われている正規化戦略を組み合わせることで、最先端の手法より優れていることを示す。この結果から,正規化戦略の組み合わせは,ノイズラベルを用いた学習の課題に対処する上で,複雑なアルゴリズムよりも効果的であることが示唆された。
論文参考訳（メタデータ） (2023-07-11T05:58:20Z)
A Tutorial Introduction to Reinforcement Learning [1.9544213396776275]
本稿では,強化学習(Reinforcement Learning, RL)の簡単な調査について述べる。論文の範囲にはMarkov Reward Processes、Markov Decision Processes、近似アルゴリズム、時間差分学習や$Q$-learningといった広く使われているアルゴリズムが含まれる。
論文参考訳（メタデータ） (2023-04-03T08:50:58Z)
Efficient Enumeration of Markov Equivalent DAGs [6.288056740658763]
本稿では,最初の線形時間遅延アルゴリズムを提案する。理論的には、我々のアルゴリズムは、背景知識を組み込んだモデルで表されるDAGを列挙するために一般化できることが示される。また、マルコフ同値性自体に興味深い洞察を与える。
論文参考訳（メタデータ） (2023-01-28T14:35:39Z)
Scalable Intervention Target Estimation in Linear Models [52.60799340056917]
因果構造学習への現在のアプローチは、既知の介入目標を扱うか、仮説テストを使用して未知の介入目標を発見する。本稿では、全ての介入対象を一貫して識別するスケーラブルで効率的なアルゴリズムを提案する。提案アルゴリズムは、与えられた観測マルコフ同値クラスを介入マルコフ同値クラスに更新することも可能である。
論文参考訳（メタデータ） (2021-11-15T03:16:56Z)
Scaling up Continuous-Time Markov Chains Helps Resolve Underspecification [42.97840843148334]
連続時間マルコフ連鎖を学習するための近似的近似法を開発し、数百項目までスケール可能で、従来の方法よりも桁違いに高速である。合成および実がんデータに対するアプローチの有効性を実証する。
論文参考訳（メタデータ） (2021-07-06T21:14:49Z)
Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs [6.252236971703546]
因果解析において、有向非巡回グラフ(DAG)の計数と一様サンプリングが基本である。本稿では,これらのタスクをグラフィカルな時間から実行し,この領域における長年にわたるオープンな課題を解決できることを示す。我々のアルゴリズムは効果的で容易に実装できる。
論文参考訳（メタデータ） (2020-12-17T15:47:15Z)
Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文参考訳（メタデータ） (2020-11-09T01:13:07Z)
Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning [96.78504087416654]
強化学習(RL)問題における効率的な探索に教師なし学習を用い,本パラダイムが有効であるかどうかを考察する。本稿では,教師なし学習アルゴリズムと非線形表RLアルゴリズムという,2つのコンポーネント上に構築された汎用的なアルゴリズムフレームワークを提案する。
論文参考訳（メタデータ） (2020-03-15T19:23:59Z)
Active Model Estimation in Markov Decision Processes [108.46146218973189]
マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
論文参考訳（メタデータ） (2020-03-06T16:17:24Z)

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