論文の概要: Intervention Efficient Algorithms for Approximate Learning of Causal
Graphs
- arxiv url: http://arxiv.org/abs/2012.13976v1
- Date: Sun, 27 Dec 2020 17:08:46 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-24 20:12:51.592719
- Title: Intervention Efficient Algorithms for Approximate Learning of Causal
Graphs
- Title（参考訳）: 因果グラフの近似学習のための干渉効率の良いアルゴリズム
- Authors: Raghavendra Addanki, Andrew McGregor, Cameron Musco
- Abstract要約: 我々は、潜時の存在下で観察された変数の集合間の因果関係を学習する問題を研究する。
我々の目標は、介入の最小限の費用で、すべての因果関係や祖先関係の方向性を$G$で回収することです。
我々のアルゴリズムは効率的な介入設計と低コストな分離集合系の設計を組み合わせる。
- 参考スコア（独自算出の注目度）: 22.401163479802094
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of learning the causal relationships between a set of
observed variables in the presence of latents, while minimizing the cost of
interventions on the observed variables. We assume access to an undirected
graph $G$ on the observed variables whose edges represent either all direct
causal relationships or, less restrictively, a superset of causal relationships
(identified, e.g., via conditional independence tests or a domain expert). Our
goal is to recover the directions of all causal or ancestral relations in $G$,
via a minimum cost set of interventions. It is known that constructing an exact
minimum cost intervention set for an arbitrary graph $G$ is NP-hard. We further
argue that, conditioned on the hardness of approximate graph coloring, no
polynomial time algorithm can achieve an approximation factor better than
$\Theta(\log n)$, where $n$ is the number of observed variables in $G$. To
overcome this limitation, we introduce a bi-criteria approximation goal that
lets us recover the directions of all but $\epsilon n^2$ edges in $G$, for some
specified error parameter $\epsilon > 0$. Under this relaxed goal, we give
polynomial time algorithms that achieve intervention cost within a small
constant factor of the optimal. Our algorithms combine work on efficient
intervention design and the design of low-cost separating set systems, with
ideas from the literature on graph property testing.
- Abstract（参考訳）: 本研究では,観測変数に対する介入のコストを最小化しつつ,潜伏者の存在下で観測変数の集合間の因果関係を学習する問題を考察する。
エッジがすべての直接的な因果関係を表すか、あるいはより制限の少ない因果関係のスーパーセット(条件付き独立テストやドメインエキスパートなどによって識別される)である観測変数に対して、無向グラフへのアクセスが$g$と仮定する。
我々の目標は、介入の最小限の費用で、すべての因果関係や祖先関係の方向性を$G$で回収することです。
任意のグラフ$G$に対して、正確な最小コストの介入セットを構築することはNPハードであることが知られている。
さらに、近似グラフ色付けの難しさを条件として、多項式時間アルゴリズムは$\theta(\log n)$よりもよい近似係数を達成できないと論じている。
この制限を克服するために、指定されたエラーパラメータの$\epsilon > 0$に対して$G$で$\epsilon n^2$ edges以外のすべての方向を復元する双基準近似の目標を導入する。
この緩和された目標の下で、最適の小さな定数係数内で介入コストを達成する多項式時間アルゴリズムを与える。
提案アルゴリズムは,効率的な介入設計と低コスト分離システムの設計と,グラフ特性試験に関する文献からのアイデアを組み合わせたものである。
関連論文リスト
- Linear Causal Bandits: Unknown Graph and Soft Interventions [18.412177974475526]
因果バンディットのアルゴリズムを 設計するのは 2つの前提に依る
その一般的な形式、すなわち未知グラフと未知の介入モデルにおける問題は、まだ未解決のままである。
本稿は、この問題に対処し、N$ノードを持つグラフにおいて、最大$d$と最大$L$の因果経路長を持つグラフにおいて、$T$相互作用が後悔の上限スケールをラウンド化することを示す。
論文 参考訳（メタデータ） (2024-11-04T18:50:39Z) - Adaptivity Complexity for Causal Graph Discovery [7.424262881242935]
本稿では,アルゴリズム設計者が合計$r$連続ラウンドで因果グラフを復元する,$r$適応性の問題を考察する。
我々は、検証数に関して$O(minr,log n cdot n1/minr,log n)$近似を達成する$r$適応アルゴリズムを提供する。
論文 参考訳（メタデータ） (2023-06-09T09:49:16Z) - Learning Good Interventions in Causal Graphs via Covering [12.512036656559685]
A$の最適介入は、グラフ内の指定された報酬変数の期待値を最大化するものである。
簡単な後悔のために、$widetildeO(sqrtN/T)$の単純な後悔保証を確立する。
また、事前の作業を超えて、観測されていない変数を持つ因果グラフに対する単純な後悔の保証も達成します。
論文 参考訳（メタデータ） (2023-05-08T11:35:22Z) - 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) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T16:21:31Z) - A Near-Optimal Algorithm for Univariate Zeroth-Order Budget Convex
Optimization [4.608510640547952]
我々は、Dy Searchのほぼ最適最適化誤差を保証する。
誤差境界における大域リプシッツ定数への古典的依存は、予算の粒度のアーティファクトであることを示す。
論文 参考訳（メタデータ） (2022-08-13T19:57:04Z) - Instance-optimality in optimal value estimation: Adaptivity via
variance-reduced Q-learning [99.34907092347733]
本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。
局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。
他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
論文 参考訳（メタデータ） (2021-06-28T00:38:54Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳（メタデータ） (2020-12-29T14:06:09Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Efficient Intervention Design for Causal Discovery with Latents [30.721629140295178]
我々は、潜伏変数の存在下で因果グラフを復元することを検討する。
本研究では,(1)変数のサブセットに対する介入のコストが線形なモデルである線形コストモデルと,(2)介入のコストがどの変数であっても同一であるアイデンティティコストモデルとを考察する。
論文 参考訳（メタデータ） (2020-05-24T12:53:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。