論文の概要: On the Unlikelihood of D-Separation

• arxiv url: http://arxiv.org/abs/2303.05628v2
• Date: Tue, 3 Oct 2023 14:32:11 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-05 10:51:43.483051
• Title: On the Unlikelihood of D-Separation
• Title（参考訳）: D-分離の相違について
• Authors: Itai Feigenbaum, Huan Wang, Shelby Heinecke, Juan Carlos Niebles, Weiran Yao, Caiming Xiong, Devansh Arpit
• Abstract要約: 解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。 PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。 UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
• 参考スコア（独自算出の注目度）: 69.62839677485087
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Causal discovery aims to recover a causal graph from data generated by it; constraint based methods do so by searching for a d-separating conditioning set of nodes in the graph via an oracle. In this paper, we provide analytic evidence that on large graphs, d-separation is a rare phenomenon, even when guaranteed to exist, unless the graph is extremely sparse. We then provide an analytic average case analysis of the PC Algorithm for causal discovery, as well as a variant of the SGS Algorithm we call UniformSGS. We consider a set $V=\{v_1,\ldots,v_n\}$ of nodes, and generate a random DAG $G=(V,E)$ where $(v_a, v_b) \in E$ with i.i.d. probability $p_1$ if $a<b$ and $0$ if $a > b$. We provide upper bounds on the probability that a subset of $V-\{x,y\}$ d-separates $x$ and $y$, conditional on $x$ and $y$ being d-separable; our upper bounds decay exponentially fast to $0$ as $|V| \rightarrow \infty$. For the PC Algorithm, while it is known that its worst-case guarantees fail on non-sparse graphs, we show that the same is true for the average case, and that the sparsity requirement is quite demanding: for good performance, the density must go to $0$ as $|V| \rightarrow \infty$ even in the average case. For UniformSGS, while it is known that the running time is exponential for existing edges, we show that in the average case, that is the expected running time for most non-existing edges as well.
• Abstract（参考訳）: 制約ベースのメソッドは、oracleを介してグラフ内のノードのd分離条件付きコンディショニングセットを検索することによって、それを行う。 本稿では,大きなグラフ上では,グラフが極めてスパースでない限り,d-セパレーションの存在が保証されたとしても,d-セパレーションは稀な現象であることを示す。 次に、因果発見のためのPCアルゴリズムの分析平均ケース分析と、UniformSGSと呼ぶSGSアルゴリズムの変種について述べる。 ノードのセット $v=\{v_1,\ldots,v_n\}$ を考え、ランダムな dag $g=(v,e)$ where $(v_a, v_b) \in e$ with i.i.d. probability $p_1$ if $a<b$ and $0$ if $a > b$。 我々は、$v-\{x,y\}$ d-の部分集合が$x$と$y$を分離し、$x$と$y$がd-分離可能である確率の上限を与える。 PCアルゴリズムでは、その最悪ケース保証が非スパースグラフで失敗することが知られているが、平均ケースでも同じことが正しいことを示し、スパーシティ要件がかなり要求されている: 優れた性能では、密度は平均ケースでも$0$ as $|V| \rightarrow \infty$にされなければならない。 UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。

関連論文リスト

• Improved convergence rate of kNN graph Laplacians [11.93971616098517]
  k$NNグラフの一般クラスで、グラフ親和性は$W_ij = epsilon-d/2 である。 制限多様体作用素に対する$k$NNグラフ Laplacian の点収束性を証明する。
  論文  参考訳（メタデータ） (2024-10-30T17:01:00Z)
• Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
  幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。 これは密度推定のための新しい統計計算トレードオフである。
  論文  参考訳（メタデータ） (2024-10-30T15:03:33Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Estimating Optimal Policy Value in General Linear Contextual Bandits [50.008542459050155]
  多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。 我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。 V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-19T01:09:24Z)
• Repeated Averages on Graphs [2.363388546004777]
  我々は$frac(1-epsilon)2log2nlog n-O(n)$が$n$ノード上のすべての連結グラフに対する一般的な下界であることを証明する。 また、星、膨張星、ダンベル、サイクルなど、いくつかの重要なグラフの族に対して、$t_epsilon,1$の急激な等級も得られる。
  論文  参考訳（メタデータ） (2022-05-09T20:18:31Z)
• Inferring Hidden Structures in Random Graphs [13.031167737538881]
  本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。 我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
  論文  参考訳（メタデータ） (2021-10-05T09:39:51Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Faster DBSCAN via subsampled similarity queries [42.93847281082316]
  DBSCANは密度に基づくクラスタリングアルゴリズムとして人気がある。 本稿では,サブサンプルである$epsilon$-neighborhoodグラフに基づいてクラスタをクラスタ化するSNG-DBSCANを提案する。
  論文  参考訳（メタデータ） (2020-06-11T18:57:54Z)
• Learning and Sampling of Atomic Interventions from Observations [11.522442415989818]
  本研究では, 因果ベイズネットワークにおける観測サンプルを用いて, 介入が単一変数(原子介入)に与える影響を効率的に推定する問題について検討した。 我々のゴールは、非パラメトリックな設定で時間とサンプルの複雑さの両方で効率的なアルゴリズムを提供することです。
  論文  参考訳（メタデータ） (2020-02-11T07:15:32Z)

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

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