論文の概要: Efficient Permutation Discovery in Causal DAGs

• arxiv url: http://arxiv.org/abs/2011.03610v1
• Date: Fri, 6 Nov 2020 21:56:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-29 04:30:59.137178
• Title: Efficient Permutation Discovery in Causal DAGs
• Title（参考訳）: 因果DAGの効率的な置換探索
• Authors: Chandler Squires, Joshua Amaniampong, Caroline Uhler
• Abstract要約: 有向非巡回グラフのスパース置換を求めるアルゴリズムを提案する。 We show that our method with depth $w$ run in $O(pw+3) $ time。 また,PC アルゴリズムや GES, GSP などの因果構造学習アルゴリズムと比較し,より短い実行時間で同等の性能が得られることを示す。
• 参考スコア（独自算出の注目度）: 9.22466799504763
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The problem of learning a directed acyclic graph (DAG) up to Markov equivalence is equivalent to the problem of finding a permutation of the variables that induces the sparsest graph. Without additional assumptions, this task is known to be NP-hard. Building on the minimum degree algorithm for sparse Cholesky decomposition, but utilizing DAG-specific problem structure, we introduce an efficient algorithm for finding such sparse permutations. We show that on jointly Gaussian distributions, our method with depth $w$ runs in $O(p^{w+3})$ time. We compare our method with $w = 1$ to algorithms for finding sparse elimination orderings of undirected graphs, and show that taking advantage of DAG-specific problem structure leads to a significant improvement in the discovered permutation. We also compare our algorithm to provably consistent causal structure learning algorithms, such as the PC algorithm, GES, and GSP, and show that our method achieves comparable performance with a shorter runtime. Thus, our method can be used on its own for causal structure discovery. Finally, we show that there exist dense graphs on which our method achieves almost perfect performance, so that unlike most existing causal structure learning algorithms, the situations in which our algorithm achieves both good performance and good runtime are not limited to sparse graphs.
• Abstract（参考訳）: 有向非巡回グラフ(DAG)をマルコフ同値まで学習する問題は、最も広いグラフを誘導する変数の置換を求める問題と同値である。 追加の仮定がなければ、このタスクはNPハードであることが知られている。 スパース・チョレスキー分解の最小次アルゴリズムを基礎として,DAG固有の問題構造を用いて,そのようなスパース置換を求めるアルゴリズムを提案する。 共同ガウス分布では、深さ$w$ の手法は $o(p^{w+3})$ time で実行される。 本手法と$w = 1$との比較により,非方向グラフのスパース除去順序を求めるアルゴリズムを比較し,DAG固有の問題構造を活かすことで,置換の大幅な改善が期待できることを示す。 また,本手法をpcアルゴリズム,ges,gspなどの一貫性のある因果構造学習アルゴリズムと比較し,より短い実行時間で同等の性能が得られることを示す。 したがって,本手法は独自の因果構造発見に利用することができる。 最後に,提案手法がほぼ完全な性能を達成するようなグラフが存在することを示し,既存の因果構造学習アルゴリズムとは異なり,提案アルゴリズムが優れた性能と良好な実行時間を達成する状況はスパースグラフに限らないことを示した。

関連論文リスト

• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。 我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
  論文  参考訳（メタデータ） (2024-03-21T11:57:16Z)
• Fast Approximation of Similarity Graphs with Kernel Density Estimation [12.321755440062732]
  我々は,データポイントのセットである$X$から類似性グラフを構築するための新しいアルゴリズムをmathbbRd$に提示する。 提案アルゴリズムはカーネル密度推定問題に基づいており,任意のカーネル関数に適用可能である。
  論文  参考訳（メタデータ） (2023-10-21T00:32:47Z)
• Optimizing NOTEARS Objectives via Topological Swaps [41.18829644248979]
  本稿では,候補アルゴリズムの集合に有効な手法を提案する。 内部レベルでは、対象が与えられた場合、オフ・ザ・アート制約を利用する。 提案手法は,他のアルゴリズムのスコアを大幅に改善する。
  論文  参考訳（メタデータ） (2023-05-26T21:49:37Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Causal Bandits without Graph Learning [28.021500949026766]
  我々は,原子間干渉を用いた報酬ノードの親ノード探索のための効率的なアルゴリズムを開発した。 報奨ノードが複数の親を持つ場合にアルゴリズムを拡張します。
  論文  参考訳（メタデータ） (2023-01-26T20:27:14Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families [12.936601424755944]
  DAGを学習するための一般的なグリーディスコアに基づくアルゴリズムについて検討する。 DAGモデルを学習するための最近のアルゴリズム時間アルゴリズムが,このアルゴリズムの特別な例であることを示す。 この観測は、ブレグマン発散と指数族との双対性に基づく新しいスコア関数と最適条件を示唆する。
  論文  参考訳（メタデータ） (2021-10-10T06:37:51Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)

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

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