論文の概要: Meek Separators and Their Applications in Targeted Causal Discovery

• arxiv url: http://arxiv.org/abs/2310.20075v1
• Date: Mon, 30 Oct 2023 23:15:27 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-01 17:12:30.897675
• Title: Meek Separators and Their Applications in Targeted Causal Discovery
• Title（参考訳）: meekセパレータとその標的因果発見への応用
• Authors: Kirankumar Shiragur and Jiaqi Zhang and Caroline Uhler
• Abstract要約: 我々は、サブセット検索と因果マッチングの2つの問題に焦点をあてる。 小型のMeekセパレータを効率よく見つけるアルゴリズムを提案する。 以上の結果から,両問題に対する既知の平均ケース保証が得られた。
• 参考スコア（独自算出の注目度）: 17.84347390320128
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning causal structures from interventional data is a fundamental problem with broad applications across various fields. While many previous works have focused on recovering the entire causal graph, in practice, there are scenarios where learning only part of the causal graph suffices. This is called $targeted$ causal discovery. In our work, we focus on two such well-motivated problems: subset search and causal matching. We aim to minimize the number of interventions in both cases. Towards this, we introduce the $Meek~separator$, which is a subset of vertices that, when intervened, decomposes the remaining unoriented edges into smaller connected components. We then present an efficient algorithm to find Meek separators that are of small sizes. Such a procedure is helpful in designing various divide-and-conquer-based approaches. In particular, we propose two randomized algorithms that achieve logarithmic approximation for subset search and causal matching, respectively. Our results provide the first known average-case provable guarantees for both problems. We believe that this opens up possibilities to design near-optimal methods for many other targeted causal structure learning problems arising from various applications.
• Abstract（参考訳）: 介入データから因果構造を学習することは、様々な分野にわたる幅広い応用において根本的な問題である。 以前の多くの研究は因果グラフ全体の回復に重点を置いてきたが、実際には因果グラフの一部のみを学習するシナリオがある。 これは$targeted$causal discoveryと呼ばれる。 我々の研究は、サブセット検索と因果マッチングの2つの問題に焦点を当てている。 両症例の介入回数を最小化することを目的としている。 これに対して、$meek~separator$という頂点の部分集合を導入し、介入すると、残りの非向きの辺をより小さな連結されたコンポーネントに分解する。 次に,小型のmeek分離器を見つけるための効率的なアルゴリズムを提案する。 このような手順は、様々な分割型アプローチの設計に有用である。 特に,部分集合探索と因果マッチングの対数近似を実現する2つのランダム化アルゴリズムを提案する。 以上の結果から,両問題に対する既知の平均ケース保証が得られた。 これにより、様々なアプリケーションから発生する多くの目的の因果構造学習問題に対して、近似的手法を設計する可能性が開けると考えている。

関連論文リスト

• Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search [9.01394829787271]
  クラスタリングに基づく最大内部積探索(MIPS)におけるルーティングの問題について検討する。 最大内積を楽観的に推定するために,各シャード内の内積分布のモーメントを組み込んだ新しい枠組みを提案する。
  論文  参考訳（メタデータ） (2024-05-20T17:47:18Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• Subset verification and search algorithms for causal DAGs [13.108039226223793]
  エッジのサブセット(ターゲットエッジ)間の因果関係を学習するために必要な最小の介入セットを特定する問題について検討する。 介入因果グラフのいくつかの興味深い構造的特性を証明し、ここで研究されるサブセット検証・探索問題以外の応用があると信じている。
  論文  参考訳（メタデータ） (2023-01-09T06:25:44Z)
• Verification and search algorithms for causal DAGs [11.038866111306728]
  クレーム因果グラフの正しさを確認するために、最小サイズの原子介入のセットを特徴づける。 我々は,ノード依存の介入コストと境界サイズ介入の設定に対して,その結果を一般化する。 この結果は、一般の未重み付きグラフ上での検証サイズに対する非自明な近似を保証する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2022-06-30T15:52:30Z)
• An Application of a Multivariate Estimation of Distribution Algorithm to Cancer Chemotherapy [59.40521061783166]
  癌に対する化学療法治療は、多数の相互作用する変数と制約を持つ複雑な最適化問題である。 より洗練されたアルゴリズムは、このような複雑な問題に対してより良いパフォーマンスをもたらすことが示される。 我々は、この問題における多数の相互作用によって、より洗練されたアルゴリズムが妨げられていることが原因であると仮定する。
  論文  参考訳（メタデータ） (2022-05-17T15:28:46Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Intervention Efficient Algorithm for Two-Stage Causal MDPs [15.838256272508357]
  本稿では,報酬を生成する因果グラフに対応するマルコフ決定過程(MDP)について検討する。 この設定では、学習者の目標は、各状態の変数に介入することで高い報酬をもたらす原子的介入を特定することである。 最近の因果関係の枠組みを一般化し、この研究は2段階の因果関係のMDPに対する(単純な)後悔の最小化保証を開発する。
  論文  参考訳（メタデータ） (2021-11-01T12:22:37Z)
• Near-Optimal Multi-Perturbation Experimental Design for Causal Structure Learning [0.0]
  因果構造は、興味あるシステムで実験を行うことで学習することができる。 我々は、複数の変数に同時に介入する実験を設計する、ほとんど探索されていない問題に対処する。
  論文  参考訳（メタデータ） (2021-05-28T18:00:00Z)
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams [69.4411417775822]
  逆例は機械学習モデルにおいて広く研究されている現象である。 そこで本研究では,$k$-nearest 近傍分類の逆ロバスト性を評価するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-19T08:49:10Z)
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
  腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。 特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
  論文  参考訳（メタデータ） (2020-10-31T18:19:29Z)
• Multi-task Supervised Learning via Cross-learning [102.64082402388192]
  我々は,様々なタスクを解くことを目的とした回帰関数の集合を適合させることで,マルチタスク学習と呼ばれる問題を考える。 我々の新しい定式化では、これらの関数のパラメータを2つに分けて、互いに近づきながらタスク固有のドメインで学習する。 これにより、異なるドメインにまたがって収集されたデータが、互いのタスクにおける学習パフォーマンスを改善するのに役立つ、クロス・ファーティライズが促進される。
  論文  参考訳（メタデータ） (2020-10-24T21:35:57Z)

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

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