論文の概要: Characterization and Learning of Causal Graphs with Small Conditioning
Sets
- arxiv url: http://arxiv.org/abs/2301.09028v1
- Date: Sun, 22 Jan 2023 00:24:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-24 15:14:14.100562
- Title: Characterization and Learning of Causal Graphs with Small Conditioning
Sets
- Title（参考訳）: 小条件集合をもつ因果グラフのキャラクタリゼーションと学習
- Authors: Murat Kocaoglu
- Abstract要約: 制約に基づく因果探索アルゴリズムは、条件付き独立性を体系的にテストすることで因果グラフ構造の一部を学習する。
2つの因果グラフ間の$k$-Markov同値をグラフィカルに特徴付ける新しい表現を提案する。
合成および半合成実験を行い、$k$-PCアルゴリズムがより堅牢な因果発見を可能にすることを示す。
- 参考スコア（独自算出の注目度）: 9.31015256355524
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Constraint-based causal discovery algorithms learn part of the causal graph
structure by systematically testing conditional independences observed in the
data. These algorithms, such as the PC algorithm and its variants, rely on
graphical characterizations of the so-called equivalence class of causal graphs
proposed by Pearl. However, constraint-based causal discovery algorithms
struggle when data is limited since conditional independence tests quickly lose
their statistical power, especially when the conditioning set is large. To
address this, we propose using conditional independence tests where the size of
the conditioning set is upper bounded by some integer $k$ for robust causal
discovery. The existing graphical characterizations of the equivalence classes
of causal graphs are not applicable when we cannot leverage all the conditional
independence statements. We first define the notion of $k$-Markov equivalence:
Two causal graphs are $k$-Markov equivalent if they entail the same conditional
independence constraints where the conditioning set size is upper bounded by
$k$. We propose a novel representation that allows us to graphically
characterize $k$-Markov equivalence between two causal graphs. We propose a
sound constraint-based algorithm called the $k$-PC algorithm for learning this
equivalence class. Finally, we conduct synthetic, and semi-synthetic
experiments to demonstrate that the $k$-PC algorithm enables more robust causal
discovery in the small sample regime compared to the baseline PC algorithm.
- Abstract（参考訳）: 制約に基づく因果探索アルゴリズムは、データで観測された条件付き独立性を体系的にテストすることで因果グラフ構造の一部を学習する。
これらのアルゴリズム、例えばPCアルゴリズムとその変種は、パールによって提案されたいわゆる因果グラフの同値クラスのグラフィカルな特徴に依存している。
しかしながら、条件付き独立性テストは、特に条件付きセットが大きい場合には、急速に統計能力を失うため、制約に基づく因果発見アルゴリズムは、データが制限された場合に苦労する。
これに対処するために、条件付き独立性テストを用いることを提案し、条件付き集合のサイズは強固な因果関係の発見のためにいくつかの整数 $k$ で上限される。
因果グラフの同値クラスの既存のグラフィカルな特徴付けは、条件付き独立性ステートメントをすべて活用できない場合は適用できない。
2つの因果グラフが$k$-markov同値であるとは、条件付き集合のサイズが$k$で上限されている場合に同じ条件付き独立性制約を伴っているときである。
2つの因果グラフ間の$k$-Markov同値をグラフィカルに特徴付ける新しい表現を提案する。
本稿では,この等価クラスを学習するための$k$-PCアルゴリズムを提案する。
最後に, 合成および半合成実験を行い, $k$-pc アルゴリズムがベースラインpcアルゴリズムと比較して, 小規模サンプル法においてより強固な因果発見を可能にすることを示す。
関連論文リスト
- A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。
我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
論文 参考訳（メタデータ） (2024-03-21T11:57:16Z) - 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) - Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。
提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文 参考訳（メタデータ） (2022-01-05T13:37:27Z) - Improving Efficiency and Accuracy of Causal Discovery Using a
Hierarchical Wrapper [7.570246812206772]
観測データからの因果発見は、科学の多くの分野において重要なツールである。
大規模なサンプルリミットでは、音と完全な因果探索アルゴリズムが導入されている。
しかし、これらのアルゴリズムが使用する統計的テストのパワーを制限するのは、有限のトレーニングデータのみである。
論文 参考訳（メタデータ） (2021-07-11T09:24:49Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Improved Algorithms for Agnostic Pool-based Active Classification [20.12178157010804]
プールに依存しない環境でのバイナリ分類のためのアクティブラーニングを検討する。
我々のアルゴリズムは、画像分類データセットにおけるアートアクティブな学習アルゴリズムの状況よりも優れている。
論文 参考訳（メタデータ） (2021-05-13T18:24:30Z) - A Single Iterative Step for Anytime Causal Discovery [7.570246812206772]
観測された非介入データから因果グラフを回復するための健全で完全なアルゴリズムを提示する。
我々は因果マルコフと忠実性仮定に依存し、基礎となる因果グラフの同値クラスを回復する。
提案アルゴリズムでは,FCIアルゴリズムと比較して,CIテストと条件セットの大幅な削減が要求される。
論文 参考訳（メタデータ） (2020-12-14T13:46:01Z) - Causal Bandits without prior knowledge using separating sets [3.1000291317725]
カウサル・バンディット(Causal Bandit)は、エージェントがシーケンシャルな意思決定プロセスにおいて最良のアクションを識別しなければならない古典的なバンディット問題の変種である。
これまでの文献で提案されている手法は、完全な因果グラフの正確な事前知識に依存している。
我々は、必ずしも因果知識に依存しない新たな因果バンディットアルゴリズムを定式化する。
論文 参考訳（メタデータ） (2020-09-16T20:08:03Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z) - From Checking to Inference: Actual Causality Computations as
Optimization Problems [79.87179017975235]
本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。
8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
論文 参考訳（メタデータ） (2020-06-05T10:56:52Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。