論文の概要: Linear-Time Algorithms for Front-Door Adjustment in Causal Graphs
- arxiv url: http://arxiv.org/abs/2211.16468v2
- Date: Thu, 18 May 2023 17:54:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-19 20:31:05.965800
- Title: Linear-Time Algorithms for Front-Door Adjustment in Causal Graphs
- Title（参考訳）: 因果グラフにおけるフロントドア調整のための線形時間アルゴリズム
- Authors: Marcel Wien\"obst, Benito van der Zander, Maciej Li\'skiewicz
- Abstract要約: 観測データから因果効果を推定することは経験科学の基本的な課題である。
フロントドア調整(英語: Front-door adjust)とは、観測されたメディエーターを用いて、観測されていないコンバウンドの存在下でも因果関係を識別する技術である。
最近、Jeong、Tian、Barenboimは、フロントドア基準を満たす集合を見つけるための最初のアルゴリズムを発表した。
- 参考スコア（独自算出の注目度）: 5.190207094732672
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Causal effect estimation from observational data is a fundamental task in
empirical sciences. It becomes particularly challenging when unobserved
confounders are involved in a system. This paper focuses on front-door
adjustment -- a classic technique which, using observed mediators allows to
identify causal effects even in the presence of unobserved confounding. While
the statistical properties of the front-door estimation are quite well
understood, its algorithmic aspects remained unexplored for a long time.
Recently, Jeong, Tian, and Barenboim [NeurIPS 2022] have presented the first
polynomial-time algorithm for finding sets satisfying the front-door criterion
in a given directed acyclic graph (DAG), with an $O(n^3(n+m))$ run time, where
$n$ denotes the number of variables and $m$ the number of edges of the causal
graph. In our work, we give the first linear-time, i.e., $O(n+m)$, algorithm
for this task, which thus reaches the asymptotically optimal time complexity.
This result implies an $O(n(n+m))$ delay enumeration algorithm of all
front-door adjustment sets, again improving previous work by Jeong et al.\ by a
factor of $n^3$. Moreover, we provide the first linear-time algorithm for
finding a minimal front-door adjustment set. We offer implementations of our
algorithms in multiple programming languages to facilitate practical usage and
empirically validate their feasibility, even for large graphs.
- Abstract（参考訳）: 観測データから因果効果を推定することは経験科学の基本的な課題である。
保守されていない共同ファウンダーがシステムに関わると、特に困難になる。
本論文は, 観測メディエータを用いて, 未観測のコンバウンドの存在下においても因果関係を識別できる古典的な手法である, 正面調整に焦点を当てたものである。
フロントドア推定の統計的特性はかなりよく理解されているが、アルゴリズム的な側面は長い間解明されていない。
最近、Jeong, Tian, and Barenboim [NeurIPS 2022] は、与えられた有向非巡回グラフ (DAG) におけるフロントドア基準を満たす集合を、$O(n^3(n+m))$ run time で見つけるための最初の多項式時間アルゴリズムを提示した。
我々の研究では、このタスクに対する最初の線形時間、すなわち$O(n+m)$のアルゴリズムを与え、漸近的に最適な時間複雑性に達する。
この結果は全てのフロントドア調整セットの$o(n(n+m))$遅延列挙アルゴリズムを意味し、jeongらによる以前の作業も改善された。
は$n^3$である。
さらに, 最小のフロントドア調整セットを求める最初の線形時間アルゴリズムを提案する。
提案するアルゴリズムを複数のプログラミング言語に実装することで,実使用を容易にし,その実現性を実証的に検証する。
関連論文リスト
- Almost linear time differentially private release of synthetic graphs [6.076406622352115]
本稿では,指数関数的メカニズムから,ほぼ線形時間と空間のアルゴリズムをサンプリングする。
直接的な結果として、差分入力を指数関数的に大きな$G$mエッジとして定義する。
これらは合成グラフを公開するためのプライベートファーストのプライベートアルゴリズムである。
論文 参考訳（メタデータ） (2024-06-04T09:44:24Z) - Learning-Based Algorithms for Graph Searching Problems [6.923787372512553]
本稿では,Banerjeeらによって最近導入された予測付きグラフ探索の問題点について考察する。
この問題では、ある$r$から始まるエージェントは、隠れたゴールノード$g$を見つけるために、(潜在的に未知の)グラフ$G$をトラバースしなければならない。
我々は未知のグラフ上でこの探索タスクのアルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-02-27T18:12:58Z) - Learning Regularized Graphon Mean-Field Games with Unknown Graphons [155.38727464526923]
グラフィック平均フィールドゲーム(GMFG)のための強化学習アルゴリズムを設計する。
我々は、正規化されたGMFGのナッシュ平衡(NE)を、グラフンが未知のときに学習することを目指している。
これらのアルゴリズムは、サンプルエージェントからグラモンを学習するために設計された最初のものである。
論文 参考訳（メタデータ） (2023-10-26T16:19:24Z) - The First Proven Performance Guarantees for the Non-Dominated Sorting
Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem [6.793248433673384]
NSGA-II(Non-Maninated Sorting Genetic Algorithm-II)は、多目的最適化問題を解くアルゴリズムの1つである。
従来の最適化問題であるNP完全二目的最小スパンニングツリー問題に対して、初めて証明された性能保証を与える。
論文 参考訳（メタデータ） (2023-05-22T19:59:19Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - 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) - Efficient Mean Estimation with Pure Differential Privacy via a
Sum-of-Squares Exponential Mechanism [16.996435043565594]
純微分プライバシーを受ける独立サンプルの共分散で$d$正確率分布の平均を推定するアルゴリズムを初めて与える。
我々の主な手法は、強力なSum of Squares法(SoS)を用いて微分プライベートアルゴリズムを設計する新しいアプローチである。
論文 参考訳（メタデータ） (2021-11-25T09:31:15Z) - Sublinear Time and Space Algorithms for Correlation Clustering via
Sparse-Dense Decompositions [9.29659220237395]
本稿では,相関クラスタリングの解法を提案する。
我々は高効率な時間と空間の複雑さを持つサブ線形アルゴリズムを得る。
提案手法の主な要素はスパース線グラフ分解への新規な接続である。
論文 参考訳（メタデータ） (2021-09-29T16:25:02Z) - Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。
文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。
我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
論文 参考訳（メタデータ） (2021-06-01T19:51:55Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。