論文の概要: Efficient Enumeration of Markov Equivalent DAGs

• arxiv url: http://arxiv.org/abs/2301.12212v1
• Date: Sat, 28 Jan 2023 14:35:39 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-31 18:30:10.396412
• Title: Efficient Enumeration of Markov Equivalent DAGs
• Title（参考訳）: マルコフ等価DAGの効率的な列挙
• Authors: Marcel Wien\"obst and Malte Luttermann and Max Bannach and Maciej Li\'skiewicz
• Abstract要約: 本稿では,最初の線形時間遅延アルゴリズムを提案する。 理論的には、我々のアルゴリズムは、背景知識を組み込んだモデルで表されるDAGを列挙するために一般化できることが示される。 また、マルコフ同値性自体に興味深い洞察を与える。
• 参考スコア（独自算出の注目度）: 6.910717733870574
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Enumerating the directed acyclic graphs (DAGs) of a Markov equivalence class (MEC) is an important primitive in causal analysis. The central resource from the perspective of computational complexity is the delay, that is, the time an algorithm that lists all members of the class requires between two consecutive outputs. Commonly used algorithms for this task utilize the rules proposed by Meek (1995) or the transformational characterization by Chickering (1995), both resulting in superlinear delay. In this paper, we present the first linear-time delay algorithm. On the theoretical side, we show that our algorithm can be generalized to enumerate DAGs represented by models that incorporate background knowledge, such as MPDAGs; on the practical side, we provide an efficient implementation and evaluate it in a series of experiments. Complementary to the linear-time delay algorithm, we also provide intriguing insights into Markov equivalence itself: All members of an MEC can be enumerated such that two successive DAGs have structural Hamming distance at most three.
• Abstract（参考訳）: マルコフ同値類(MEC)の有向非巡回グラフ(DAG)を列挙することは因果解析において重要な原始的である。 計算複雑性の観点からの中心的なリソースは、クラスのすべてのメンバーをリストアップするアルゴリズムが2つの連続した出力の間に必要となる遅延である。 このタスクによく使われるアルゴリズムは、Meek (1995) が提案した規則や Chickering (1995) による変換特性を利用しており、どちらも超線形遅延をもたらす。 本稿では,最初の線形時間遅延アルゴリズムを提案する。 理論的には,MPDAGなどの背景知識を組み込んだモデルで表現されたDAGを列挙するために,我々のアルゴリズムを一般化できることが示される。 線形時間遅延アルゴリズムの補完として、マルコフ等価性自体に興味深い洞察を与える: MECのすべてのメンバーを列挙して、2つの連続DAGが少なくとも3つの構造的ハミング距離を持つようにすることができる。

関連論文リスト

• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For Hidden Markov Models [70.26374282390401]
  ノイズの多い観測から元の信号(すなわち隠れ鎖)を復号することは、ほぼすべてのHMMに基づくデータ分析の主要な目標の1つである。 本稿では,多対数計算複雑性において隠れた列を復号化するための分法であるQuick Adaptive Ternary(QATS)を提案する。
  論文  参考訳（メタデータ） (2023-05-29T19:37:48Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  ニューラルネットワーク推論タスクのOOD一般化について検討する。 目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
  論文  参考訳（メタデータ） (2022-11-01T18:33:20Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。 本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。 3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
  論文  参考訳（メタデータ） (2022-09-27T09:06:37Z)
• Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for Scalar Data -- An Algorithm and A Benchmark [8.648433479399857]
  本稿では,d-次元単純複素数 K 上で定義される入力片方向線形スカラー場 f を与えられた永続図計算の効率的なアルゴリズムを提案する。 我々はこのアルゴリズムを離散モース理論の設定内で表現し、考慮すべき入力単純さの数を著しく削減する。 また、この問題に対して「サンドウィッチ」と呼ばれる階層化アプローチを導入する。
  論文  参考訳（メタデータ） (2022-06-27T10:54:24Z)
• Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs with Applications [6.03124479597323]
  マルコフ同値類からの有向非巡回グラフの数え上げとサンプリングは因果解析の基本的な課題である。 これらのタスクはグラフィカルな時間で実行可能であることを示す。 我々のアルゴリズムは効果的で容易に実装できる。
  論文  参考訳（メタデータ） (2022-05-05T13:56:13Z)
• DAGs with No Curl: An Efficient DAG Structure Learning Approach [62.885572432958504]
  近年のDAG構造学習は連続的な非巡回性制約を伴う制約付き連続最適化問題として定式化されている。 本稿では,DAG空間の重み付き隣接行列を直接モデル化し,学習するための新しい学習フレームワークを提案する。 本手法は, 線形および一般化された構造方程式モデルにおいて, ベースラインDAG構造学習法よりも精度が高いが, 効率がよいことを示す。
  論文  参考訳（メタデータ） (2021-06-14T07:11:36Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Temporal Parallelization of Inference in Hidden Markov Models [0.0]
  本稿では隠れマルコフモデル(hmms)における推論の並列化アルゴリズムを提案する。 パラレル・バックワード型フィルタ・スムージングアルゴリズムとパラレル・ビタビ型max-a-posteriori(MAP)を提案する。 高並列処理ユニット(GPU)における提案手法の性能と古典的手法とを実証的に比較する。
  論文  参考訳（メタデータ） (2021-02-10T21:26:09Z)
• Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs [6.252236971703546]
  因果解析において、有向非巡回グラフ(DAG)の計数と一様サンプリングが基本である。 本稿では,これらのタスクをグラフィカルな時間から実行し,この領域における長年にわたるオープンな課題を解決できることを示す。 我々のアルゴリズムは効果的で容易に実装できる。
  論文  参考訳（メタデータ） (2020-12-17T15:47:15Z)

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

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