論文の概要: Verification and search algorithms for causal DAGs
- arxiv url: http://arxiv.org/abs/2206.15374v1
- Date: Thu, 30 Jun 2022 15:52:30 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-01 14:06:23.020396
- Title: Verification and search algorithms for causal DAGs
- Title（参考訳）: 因果DAGの検証と探索アルゴリズム
- Authors: Davin Choo, Kirankumar Shiragur, Arnab Bhattacharyya
- Abstract要約: クレーム因果グラフの正しさを確認するために、最小サイズの原子介入のセットを特徴づける。
我々は,ノード依存の介入コストと境界サイズ介入の設定に対して,その結果を一般化する。
この結果は、一般の未重み付きグラフ上での検証サイズに対する非自明な近似を保証する最初のアルゴリズムである。
- 参考スコア（独自算出の注目度）: 11.038866111306728
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study two problems related to recovering causal graphs from interventional
data: (i) $\textit{verification}$, where the task is to check if a purported
causal graph is correct, and (ii) $\textit{search}$, where the task is to
recover the correct causal graph. For both, we wish to minimize the number of
interventions performed. For the first problem, we give a characterization of a
minimal sized set of atomic interventions that is necessary and sufficient to
check the correctness of a claimed causal graph. Our characterization uses the
notion of $\textit{covered edges}$, which enables us to obtain simple proofs
and also easily reason about earlier results. We also generalize our results to
the settings of bounded size interventions and node-dependent interventional
costs. For all the above settings, we provide the first known provable
algorithms for efficiently computing (near)-optimal verifying sets on general
graphs. For the second problem, we give a simple adaptive algorithm based on
graph separators that produces an atomic intervention set which fully orients
any essential graph while using $\mathcal{O}(\log n)$ times the optimal number
of interventions needed to $\textit{verify}$ (verifying size) the underlying
DAG on $n$ vertices. This approximation is tight as $\textit{any}$ search
algorithm on an essential line graph has worst case approximation ratio of
$\Omega(\log n)$ with respect to the verifying size. With bounded size
interventions, each of size $\leq k$, our algorithm gives an $\mathcal{O}(\log
n \cdot \log \log k)$ factor approximation. Our result is the first known
algorithm that gives a non-trivial approximation guarantee to the verifying
size on general unweighted graphs and with bounded size interventions.
- Abstract（参考訳）: 介入データから因果グラフの復元に関する2つの問題点について検討した。
(i) $\textit{verification}$ ここでは、指定された因果グラフが正しいかどうかをタスクがチェックし、
(ii)$\textit{search}$, ここで、タスクは正しい因果グラフを復元することである。
どちらも、実施される介入の数を最小化したいと考えています。
第1の問題は、主張された因果グラフの正確性をチェックするのに必要かつ十分である、原子サイズの介入の最小セットを特徴付けることである。
我々の特徴付けは $\textit{covered edges}$ という概念を使い、簡単な証明を得ることができ、初期の結果を簡単に推論できる。
また,評価結果を,ノード依存の介入コストと境界サイズ介入の設定に一般化する。
上記のすべての設定に対して、一般グラフ上の(ほぼ)最適検証セットを効率的に計算するための、最初の証明可能なアルゴリズムを提供する。
2つ目の問題に対して、我々は、$\mathcal{O}(\log n)$ を$\textit{verify}$ (verify size) に必要となる介入の最適回数を$n$ vertices の基盤となる DAG の2倍の精度で使用しながら、すべての重要なグラフを向き付ける原子介入セットを生成するグラフ分離器に基づく単純な適応アルゴリズムを与える。
この近似は、本質的な線グラフ上の$\textit{any}$検索アルゴリズムが検証サイズに関して$\Omega(\log n)$の最悪のケース近似比を持つため、厳密である。
境界サイズの介入により、サイズ$\leq k$のそれぞれで、我々のアルゴリズムは$\mathcal{O}(\log n \cdot \log \log k)$ factor approximationを与える。
我々のアルゴリズムは、一般の未重み付きグラフと有界サイズの介入による検証サイズに対する非自明な近似を保証する最初のアルゴリズムである。
関連論文リスト
- Linear Causal Bandits: Unknown Graph and Soft Interventions [18.412177974475526]
因果バンディットのアルゴリズムを 設計するのは 2つの前提に依る
その一般的な形式、すなわち未知グラフと未知の介入モデルにおける問題は、まだ未解決のままである。
本稿は、この問題に対処し、N$ノードを持つグラフにおいて、最大$d$と最大$L$の因果経路長を持つグラフにおいて、$T$相互作用が後悔の上限スケールをラウンド化することを示す。
論文 参考訳（メタデータ） (2024-11-04T18:50:39Z) - On the instance optimality of detecting collisions and subgraphs [7.055459105099637]
グラフや関数における部分構造検出問題のラベルなしインスタンス最適性について検討する。
アルゴリズムが任意の入力に対して満足する$A$を許容すれば、問題は$g(n)$-instanceOptimationである。
この結果から,グラフや関数のサブ構造検出問題において,ラベルなしのインスタンス最適性を三分したことが示唆された。
論文 参考訳（メタデータ） (2023-12-15T20:50:03Z) - Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps [30.06993761032835]
最大$k$-plex問題は、グラフマイニングやコミュニティ検出といったアプリケーションでは重要であるが、計算的に困難である。
我々は、入力グラフのサイズで最悪のランニング時間を持ち、$g_k(G)$で指数関数的な$g_k(G)$でパラメータ化された正確なアルゴリズムを示す。
我々はさらに議論を、より小さなパラメータ$cg_k(G)$、コミュニティの世代境界と最大$k$-plexのサイズの間のギャップにまで拡張します。
論文 参考訳（メタデータ） (2023-06-23T01:28:24Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T16:21:31Z) - Robust Estimation for Random Graphs [47.07886511972046]
我々は、$n$ノード上のErdHos-R'enyiランダムグラフのパラメータ$p$を頑健に推定する問題について検討する。
情報理論の限界であるすべての$gamma 1/2$に対して、同様の精度で非効率なアルゴリズムを与える。
論文 参考訳（メタデータ） (2021-11-09T18:43:25Z) - Random Graph Matching with Improved Noise Robustness [2.294014185517203]
本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。
我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。
これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
論文 参考訳（メタデータ） (2021-01-28T02:39:27Z) - Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。
textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文 参考訳（メタデータ） (2020-12-10T15:40:07Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。