論文の概要: Learning and Sampling of Atomic Interventions from Observations
- arxiv url: http://arxiv.org/abs/2002.04232v2
- Date: Wed, 5 Aug 2020 06:11:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 00:59:51.523299
- Title: Learning and Sampling of Atomic Interventions from Observations
- Title（参考訳）: 観察からの原子介入の学習とサンプリング
- Authors: Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy, Ashwin Maran,
N. V. Vinodchandran
- Abstract要約: 本研究では, 因果ベイズネットワークにおける観測サンプルを用いて, 介入が単一変数(原子介入)に与える影響を効率的に推定する問題について検討した。
我々のゴールは、非パラメトリックな設定で時間とサンプルの複雑さの両方で効率的なアルゴリズムを提供することです。
- 参考スコア（独自算出の注目度）: 11.522442415989818
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of efficiently estimating the effect of an intervention
on a single variable (atomic interventions) using observational samples in a
causal Bayesian network. Our goal is to give algorithms that are efficient in
both time and sample complexity in a non-parametric setting.
Tian and Pearl (AAAI `02) have exactly characterized the class of causal
graphs for which causal effects of atomic interventions can be identified from
observational data. We make their result quantitative. Suppose P is a causal
model on a set $\vec{V}$ of n observable variables with respect to a given
causal graph G with observable distribution $P$. Let $P_x$ denote the
interventional distribution over the observables with respect to an
intervention of a designated variable X with x. Assuming that $G$ has bounded
in-degree, bounded c-components ($k$), and that the observational distribution
is identifiable and satisfies certain strong positivity condition, we give an
algorithm that takes $m=\tilde{O}(n\epsilon^{-2})$ samples from $P$ and $O(mn)$
time, and outputs with high probability a description of a distribution
$\hat{P}$ such that $d_{\mathrm{TV}}(P_x, \hat{P}) \leq \epsilon$, and:
1. [Evaluation] the description can return in $O(n)$ time the probability
$\hat{P}(\vec{v})$ for any assignment $\vec{v}$ to $\vec{V}$
2. [Generation] the description can return an iid sample from $\hat{P}$ in
$O(n)$ time.
We also show lower bounds for the sample complexity showing that our sample
complexity has an optimal dependence on the parameters $n$ and $\epsilon$, as
well as if $k=1$ on the strong positivity parameter.
- Abstract（参考訳）: 本研究では,因果ベイズネットワークにおける観測サンプルを用いて,単一変数(原子間介入)に対する介入の効果を効率的に推定する問題について検討する。
我々のゴールは、非パラメトリックな設定で時間とサンプルの複雑さの両方で効率的なアルゴリズムを提供することです。
Tian and Pearl (AAAI `02) は、原子間相互作用の因果効果を観測データから特定できる因果グラフの分類を正確に特徴付けている。
結果を定量的にします
P を与えられた因果グラフ G に対する n 個の可観測変数の集合 $\vec{V}$ 上の因果モデルとし、可観測分布 $P$ とする。
P_x$ は、指定された変数 X と x との干渉に関して可観測空間上の干渉分布を表す。
Assuming that $G$ has bounded in-degree, bounded c-components ($k$), and that the observational distribution is identifiable and satisfies certain strong positivity condition, we give an algorithm that takes $m=\tilde{O}(n\epsilon^{-2})$ samples from $P$ and $O(mn)$ time, and outputs with high probability a description of a distribution $\hat{P}$ such that $d_{\mathrm{TV}}(P_x, \hat{P}) \leq \epsilon$, and: 1. [Evaluation] the description can return in $O(n)$ time the probability $\hat{P}(\vec{v})$ for any assignment $\vec{v}$ to $\vec{V}$ 2. [Generation] the description can return an iid sample from $\hat{P}$ in $O(n)$ time.
また、サンプル複雑性の限界を低くすることで、サンプル複雑性がパラメータ$n$と$\epsilon$に最適依存していることを示し、また、もし$k=1$が強いポジティビティパラメータに依存していることを示した。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Transfer Operators from Batches of Unpaired Points via Entropic
Transport Kernels [3.099885205621181]
そこで我々は,最大形推論関数を導出し,計算可能な近似を提案し,それらの特性を解析する。
我々は、ブロック数$N$が無限に近づくと、経験的近似から真の密度を回復できることを示す$Gamma$-convergenceの結果を証明する。
論文 参考訳（メタデータ） (2024-02-13T12:52:41Z) - Estimation and Inference in Distributional Reinforcement Learning [28.253677740976197]
サイズ$widetilde Oleft(frac|mathcalS||mathcalA|epsilon2 (1-gamma)4right)$ suffices to ensure the Kolmogorov metric and total variation metric between $hatetapi$ and $etapi$ is below $epsilon$ with high probability。
以上の結果から,多種多様な統計的汎関数の統計的推測への統一的アプローチがもたらされた。
論文 参考訳（メタデータ） (2023-09-29T14:14:53Z) - Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
本稿では、パラメータ法と非パラメトリック法の両方を用いて、Rp$における$p$次元ランダムベクトル$Xのグラフィカル構造を学習する。
温和な条件下では、グラフ構造推定器が正しい構造を得ることができることを示す。
論文 参考訳（メタデータ） (2022-05-06T19:24:44Z) - Optimal Sublinear Sampling of Spanning Trees and Determinantal Point
Processes via Average-Case Entropic Independence [3.9586758145580014]
強いレイリー分布から繰り返しサンプリングする高速アルゴリズムを設計する。
グラフ $G=(V, E)$ に対して、$G$ in $widetildeO(lvert Vrvert)$ time per sample から一様にランダムに散らばる木を概算する方法を示す。
$n$要素の基底集合の$k$のサブセット上の決定的点プロセスに対して、$widetildeO(komega)$ time の最初の $widetildeO(nk) の後に、$widetildeO(komega)$ time のサンプルを概算する方法を示す。
論文 参考訳（メタデータ） (2022-04-06T04:11:26Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳（メタデータ） (2020-12-31T18:24:41Z) - The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。
加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
論文 参考訳（メタデータ） (2020-07-16T04:23:57Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。