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

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

arxiv url: http://arxiv.org/abs/2012.09679v1
Date: Thu, 17 Dec 2020 15:47:15 GMT
ステータス: 処理完了
システム内更新日: 2021-05-02 07:42:03.672189
Title: Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs
Title（参考訳）: マルコフ等価DAGのカウントとサンプリングのための多項式時間アルゴリズム
Authors: Marcel Wien\"obst and Max Bannach and Maciej Li\'skiewicz
Abstract要約: 因果解析において、有向非巡回グラフ(DAG)の計数と一様サンプリングが基本である。本稿では,これらのタスクをグラフィカルな時間から実行し,この領域における長年にわたるオープンな課題を解決できることを示す。我々のアルゴリズムは効果的で容易に実装できる。
参考スコア（独自算出の注目度）: 6.252236971703546
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Counting and uniform sampling of directed acyclic graphs (DAGs) 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. Experimental results show that the algorithms significantly outperform state-of-the-art methods.
Abstract（参考訳）: マルコフ同値類からの有向非巡回グラフ(DAG)の計数と一様サンプリングは、グラフィカル因果解析の基本的な課題である。本稿では,これらの課題を多項式時間で実行可能であることを示し,この領域における長年のオープン問題を解く。我々のアルゴリズムは効果的で容易に実装できる。実験結果から, アルゴリズムは最先端手法よりも優れていた。

関連論文リスト

EKM: An exact, polynomial-time algorithm for the $K$-medoids problem [1.9405875431318445]
EKM: 最悪の$Oleft(NK+1right)$複雑性でこの問題を正確に解くための新しいアルゴリズムを提案する。 EKMは、フォーマルなプログラムステップを用いて、変換プログラミングと生成の最近の進歩に従って開発されている。我々は,アルゴリズムのウォールタイム実行時間が,合成データセット上での最悪の時間複雑性解析と一致することを示した。
論文参考訳（メタデータ） (2024-05-16T15:11:37Z)
Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP [81.00800920928621]
部分的に観測可能なマルコフ決定過程(POMDP)における表現学習の研究まず,不確実性(OFU)に直面した最大推定(MLE)と楽観性を組み合わせた復調性POMDPのアルゴリズムを提案する。次に、このアルゴリズムをより広範な$gamma$-observable POMDPのクラスで機能させる方法を示す。
論文参考訳（メタデータ） (2023-06-21T16:04:03Z)
Efficient Enumeration of Markov Equivalent DAGs [6.288056740658763]
本稿では,最初の線形時間遅延アルゴリズムを提案する。理論的には、我々のアルゴリズムは、背景知識を組み込んだモデルで表されるDAGを列挙するために一般化できることが示される。また、マルコフ同値性自体に興味深い洞察を与える。
論文参考訳（メタデータ） (2023-01-28T14:35:39Z)
On the Finite-Time Performance of the Knowledge Gradient Algorithm [1.713291434132985]
知識勾配(KG)アルゴリズムは、ベストアーム識別(BAI)問題に対して人気があり効果的なアルゴリズムである。 KGアルゴリズムの有限時間性能に関する新しい理論的結果を示す。
論文参考訳（メタデータ） (2022-06-14T13:42:05Z)
Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications [6.03124479597323]
マルコフ同値類からの有向非巡回グラフの数え上げとサンプリングは因果解析の基本的な課題である。これらのタスクはグラフィカルな時間で実行可能であることを示す。我々のアルゴリズムは効果的で容易に実装できる。
論文参考訳（メタデータ） (2022-05-05T13:56:13Z)
First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。これらのアルゴリズムに対する漸近的理論的保証を提供する。
論文参考訳（メタデータ） (2022-04-07T00:11:05Z)
Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families [12.936601424755944]
DAGを学習するための一般的なグリーディスコアに基づくアルゴリズムについて検討する。 DAGモデルを学習するための最近のアルゴリズム時間アルゴリズムが,このアルゴリズムの特別な例であることを示す。この観測は、ブレグマン発散と指数族との双対性に基づく新しいスコア関数と最適条件を示唆する。
論文参考訳（メタデータ） (2021-10-10T06:37:51Z)
Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文参考訳（メタデータ） (2021-09-13T18:10:52Z)
Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文参考訳（メタデータ） (2020-11-09T01:13:07Z)
Nearly Linear Row Sampling Algorithm for Quantile Regression [54.75919082407094]
データの次元にほぼ線形なサンプル複雑性を持つ量子化損失関数の行サンプリングアルゴリズムを提案する。行サンプリングアルゴリズムに基づいて、量子レグレッションの最も高速なアルゴリズムと、バランスの取れた有向グラフのグラフスペーシフィケーションアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-06-15T13:40:07Z)
Active Model Estimation in Markov Decision Processes [108.46146218973189]
マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
論文参考訳（メタデータ） (2020-03-06T16:17:24Z)

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