論文の概要: Almost Optimal Universal Lower Bound for Learning Causal DAGs with Atomic Interventions

• arxiv url: http://arxiv.org/abs/2111.05070v1
• Date: Tue, 9 Nov 2021 11:58:44 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-10 14:48:02.084313
• Title: Almost Optimal Universal Lower Bound for Learning Causal DAGs with Atomic Interventions
• Title（参考訳）: 原子干渉による因果DAG学習のためのほぼ最適ユニバーサル下界
• Authors: Vibhor Porwal, Piyush Srivastava, Gaurav Sinha
• Abstract要約: 我々は、与えられたMECを指向するためにアルゴリズムが実行するべき原子介入の数に対して、新しい普遍的な下限を証明した。 我々の下限は、以前知られていた下限よりも確実に良い。
• 参考スコア（独自算出の注目度）: 2.750124853532831
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: A well-studied challenge that arises in the structure learning problem of causal directed acyclic graphs (DAG) is that using observational data, one can only learn the graph up to a "Markov equivalence class" (MEC). The remaining undirected edges have to be oriented using interventions, which can be very expensive to perform in applications. Thus, the problem of minimizing the number of interventions needed to fully orient the MEC has received a lot of recent attention, and is also the focus of this work. We prove two main results. The first is a new universal lower bound on the number of atomic interventions that any algorithm (whether active or passive) would need to perform in order to orient a given MEC. Our second result shows that this bound is, in fact, within a factor of two of the size of the smallest set of atomic interventions that can orient the MEC. Our lower bound is provably better than previously known lower bounds. The proof of our lower bound is based on the new notion of CBSP orderings, which are topological orderings of DAGs without v-structures and satisfy certain special properties. Further, using simulations on synthetic graphs and by giving examples of special graph families, we show that our bound is often significantly better.
• Abstract（参考訳）: 因果有向非巡回グラフ(DAG)の構造学習問題において、よく研究されている課題は、観測データを用いて、そのグラフを「マルコフ同値類」(MEC)までしか学習できないことである。 残りの非指向エッジは、アプリケーションで実行するのに非常にコストがかかる介入を使って指向する必要がある。 このように、MECの完全オリエント化に必要な介入数を最小化する問題は、近年注目され、また本研究の焦点となっている。 主な結果は2つある。 1つ目は、任意のMECを指向するために、任意のアルゴリズム(アクティブかパッシブかに関わらず)が実行するべき原子介入の数に基づいた新しい普遍的下界である。 2つ目の結果は、この境界が、実際には、mecをオリエントできる最小の原子干渉の集合の2倍の大きさであることを示している。 我々の下限は、以前知られていた下限よりも確実に良い。 我々の下界の証明は、V構造を持たないDAGのトポロジカル順序であり、特定の特別な性質を満たすCBSP順序付けという新しい概念に基づいている。 さらに,合成グラフ上でのシミュレーションや特別なグラフファミリの例を用いて,境界が著しく優れていることを示す。

関連論文リスト

• Sample Efficient Bayesian Learning of Causal Graphs from Interventions [6.823521786512908]
  本研究では,限られた介入サンプルを用いた因果グラフ学習におけるベイズ的アプローチについて考察する。 我々は,提案アルゴリズムが真の因果グラフを高い確率で返すことを理論的に示す。 本稿では,このアルゴリズムを,グラフ全体を学習することなく,より一般的な因果問題にどう対応できるかを示すケーススタディを提案する。
  論文  参考訳（メタデータ） (2024-10-26T05:47:56Z)
• Unraveling the Impact of Heterophilic Structures on Graph Positive-Unlabeled Learning [71.9954600831939]
  実世界の多くのシナリオにおいて、肯定的無ラベル(PU)学習は不可欠であるが、そのグラフデータへの応用は未探索のままである。 グラフ上でのPU学習において重要な課題がエッジヘテロフィリーにあり、クラスプライア推定の既約性前提に直接違反していることを明らかにする。 この課題に対応するために,ラベル伝搬損失(GPL)を用いたグラフPU学習という新しい手法を導入する。
  論文  参考訳（メタデータ） (2024-05-30T10:30:44Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems [46.71914490521821]
  本稿では,非コンケーブなミニマックス問題のクラスに対して,新たな漸進型アルゴリズムを提案する。 提案アルゴリズムは制約付き正規化問題に適用可能である。
  論文  参考訳（メタデータ） (2023-02-20T08:37:08Z)
• OrthoReg: Improving Graph-regularized MLPs via Orthogonality Regularization [66.30021126251725]
  グラフニューラルネットワーク(GNN)は現在、グラフ構造データのモデリングにおいて支配的である。 グラフ正規化ネットワーク(GR-MLP)はグラフ構造情報をモデル重みに暗黙的に注入するが、その性能はほとんどのタスクにおいてGNNとほとんど一致しない。 GR-MLPは,最大数個の固有値が埋め込み空間を支配する現象である次元崩壊に苦しむことを示す。 次元崩壊問題を緩和する新しいGR-MLPモデルであるOrthoRegを提案する。
  論文  参考訳（メタデータ） (2023-01-31T21:20:48Z)
• Subset verification and search algorithms for causal DAGs [13.108039226223793]
  エッジのサブセット(ターゲットエッジ)間の因果関係を学習するために必要な最小の介入セットを特定する問題について検討する。 介入因果グラフのいくつかの興味深い構造的特性を証明し、ここで研究されるサブセット検証・探索問題以外の応用があると信じている。
  論文  参考訳（メタデータ） (2023-01-09T06:25:44Z)
• BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery [97.79015388276483]
  構造方程式モデル(SEM)は、有向非巡回グラフ(DAG)を介して表される因果関係を推論する効果的な枠組みである。 近年の進歩により、観測データからDAGの有効最大点推定が可能となった。 線形ガウス SEM を特徴付ける DAG 上の分布を推定するための変分フレームワークである BCD Nets を提案する。
  論文  参考訳（メタデータ） (2021-12-06T03:35:21Z)
• Intervention Efficient Algorithm for Two-Stage Causal MDPs [15.838256272508357]
  本稿では,報酬を生成する因果グラフに対応するマルコフ決定過程(MDP)について検討する。 この設定では、学習者の目標は、各状態の変数に介入することで高い報酬をもたらす原子的介入を特定することである。 最近の因果関係の枠組みを一般化し、この研究は2段階の因果関係のMDPに対する(単純な)後悔の最小化保証を開発する。
  論文  参考訳（メタデータ） (2021-11-01T12:22:37Z)
• Direction Matters: On the Implicit Bias of Stochastic Gradient Descent with Moderate Learning Rate [105.62979485062756]
  本稿では,中等度学習におけるSGDの特定の正規化効果を特徴付けることを試みる。 SGDはデータ行列の大きな固有値方向に沿って収束し、GDは小さな固有値方向に沿って収束することを示す。
  論文  参考訳（メタデータ） (2020-11-04T21:07:52Z)
• Active Structure Learning of Causal DAGs via Directed Clique Tree [28.637447727749]
  我々は,最大傾きが構造学習の根本的障害であることを示す,単一ノード介入に対する普遍的下位境界を開発する。 具体的には,DAGを直交斜め木を通して独立に向き付け可能な成分に分解する。 また,最大傾き数における乗算対数係数までの最適介入数に一致する2相干渉設計アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-01T23:11:17Z)
• CLUB: A Contrastive Log-ratio Upper Bound of Mutual Information [105.73798100327667]
  本稿では,相互情報の対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物対物 CLUBの特性とその変分近似に関する理論的解析を行う。 この上限に基づいてMI最小化学習手法を導入し、さらに負のサンプリング戦略で加速する。
  論文  参考訳（メタデータ） (2020-06-22T05:36:16Z)

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

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