論文の概要: Improving the Efficiency of the PC Algorithm by Using Model-Based
Conditional Independence Tests
- arxiv url: http://arxiv.org/abs/2211.06536v1
- Date: Sat, 12 Nov 2022 00:54:53 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-15 19:00:15.457497
- Title: Improving the Efficiency of the PC Algorithm by Using Model-Based
Conditional Independence Tests
- Title（参考訳）: モデルに基づく条件付き独立性テストによるpcアルゴリズムの効率向上
- Authors: Erica Cai, Andrew McGregor, David Jensen
- Abstract要約: PC利用条件独立(CI)テストのような制約に基づく構造学習アルゴリズムは因果構造を推論する。
従来、制約ベースのアルゴリズムは、より小さな条件セットを優先してCIテストを実行する。
本稿では,CIテストの実施回数を削減できる制約ベースのアルゴリズムの新しい手法を提案する。
- 参考スコア（独自算出の注目度）: 11.33674514817655
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Learning causal structure is useful in many areas of artificial intelligence,
including planning, robotics, and explanation. Constraint-based structure
learning algorithms such as PC use conditional independence (CI) tests to infer
causal structure. Traditionally, constraint-based algorithms perform CI tests
with a preference for smaller-sized conditioning sets, partially because the
statistical power of conventional CI tests declines rapidly as the size of the
conditioning set increases. However, many modern conditional independence tests
are model-based, and these tests use well-regularized models that maintain
statistical power even with very large conditioning sets. This suggests an
intriguing new strategy for constraint-based algorithms which may result in a
reduction of the total number of CI tests performed: Test variable pairs with
large conditioning sets first, as a pre-processing step that finds some
conditional independencies quickly, before moving on to the more conventional
strategy that favors small conditioning sets. We propose such a pre-processing
step for the PC algorithm which relies on performing CI tests on a few randomly
selected large conditioning sets. We perform an empirical analysis on directed
acyclic graphs (DAGs) that correspond to real-world systems and both empirical
and theoretical analyses for Erd\H{o}s-Renyi DAGs. Our results show that
Pre-Processing Plus PC (P3PC) performs far fewer CI tests than the original PC
algorithm, between 0.5% to 36%, and often less than 10%, of the CI tests that
the PC algorithm alone performs. The efficiency gains are particularly
significant for the DAGs corresponding to real-world systems.
- Abstract（参考訳）: 因果構造を学ぶことは、計画、ロボット工学、説明など、人工知能の多くの領域で有用である。
PC利用条件独立(CI)テストのような制約に基づく構造学習アルゴリズムは因果構造を推論する。
従来のCIテストの統計力は、条件セットのサイズが大きくなるにつれて急速に低下するため、制約ベースのアルゴリズムはより小さな条件セットを優先してCIテストを実行する。
しかし、現代の条件付き独立性テストの多くはモデルベースであり、これらのテストは、非常に大きな条件付き集合でも統計力を維持するよく規則化されたモデルを使っている。
これは、制約ベースのアルゴリズムに対する興味深い新しい戦略であり、実行されたciテストの総数を減少させる可能性がある: 大きな条件付き変数ペア まず、条件付き無依存を素早く発見する前処理ステップとして、小さな条件付きセットを好むより伝統的な戦略に移行する。
ランダムに選択された大規模条件集合上でCIテストを実行することに依存するPCアルゴリズムの事前処理ステップを提案する。
我々は,実世界のシステムに対応する有向非巡回グラフ(DAG)と,Erd\H{o}s-Renyi DAGの実証的および理論的解析を行う。
以上の結果から,PCアルゴリズム単独で行うCIテストのうち,0.5%から36%,そして10%未満で,PC前処理プラスPC(P3PC)が従来のPCアルゴリズムよりもはるかに少ないCIテストを実行することがわかった。
実世界のシステムに対応するDAGにとって、効率向上は特に重要である。
関連論文リスト
- Testing Causal Models with Hidden Variables in Polynomial Delay via Conditional Independencies [49.99600569996907]
観測データに対して仮説化された因果モデルをテストすることは、多くの因果推論タスクにとって重要な前提条件である。
モデルは指数関数的に多くの条件付き独立関係(CI)を仮定できるが、これら全てをテストすることは実用的でなく不必要である。
隠れ変数を持つ因果グラフのc-LMPを導入し、これらのCIを多時間間隔でリストする遅延アルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-09-22T21:05:56Z) - Hyperparameters in Continual Learning: A Reality Check [53.30082523545212]
連続学習(CL)は、可塑性(新しいタスクを学ぶ)と安定性(事前知識を保持する)のトレードオフをバランスしながら、一連のタスクでモデルを訓練することを目的としている。
CLアルゴリズムの従来の評価プロトコルは、与えられたシナリオで最適なハイパーパラメータを選択し、同じシナリオでアルゴリズムを評価する。
このプロトコルには大きな欠点があり、アルゴリズムのCL能力を過大評価し、非現実的なハイパーパラメータチューニングに依存している。
CLアルゴリズムの評価は,予測できないシナリオに対するCL能力の一般化性を評価することに集中すべきである,と我々は主張する。
論文 参考訳（メタデータ） (2024-03-14T03:13:01Z) - Precise Error Rates for Computationally Efficient Testing [75.63895690909241]
本稿では,計算複雑性に着目した単純な対数-単純仮説テストの問題を再考する。
線形スペクトル統計に基づく既存の試験は、I型とII型の誤差率の間の最良のトレードオフ曲線を達成する。
論文 参考訳（メタデータ） (2023-11-01T04:41:16Z) - A Stable, Fast, and Fully Automatic Learning Algorithm for Predictive
Coding Networks [65.34977803841007]
予測符号化ネットワークは、ベイズ統計学と神経科学の両方にルーツを持つ神経科学にインスパイアされたモデルである。
シナプス重みに対する更新規則の時間的スケジュールを変更するだけで、元の規則よりもずっと効率的で安定したアルゴリズムが得られることを示す。
論文 参考訳（メタデータ） (2022-11-16T00:11:04Z) - A Simple Unified Approach to Testing High-Dimensional Conditional
Independences for Categorical and Ordinal Data [0.26651200086513094]
条件独立テスト(CI)は、因果推論におけるモデルテストと構造学習に多くのアプローチをとる。
分類データと順序データのための既存のCIテストは、条件変数によってサンプルを階層化し、各層で単純な独立テストを実行し、結果を組み合わせる。
本稿では,高次元における適切なキャリブレーションとパワーを維持するための,順序データと分類データに対する簡易な統合CIテストを提案する。
論文 参考訳（メタデータ） (2022-06-09T08:56:12Z) - Recursive Causal Structure Learning in the Presence of Latent Variables
and Selection Bias [27.06618125828978]
本稿では,潜伏変数と選択バイアスの存在下での観測データからシステムの因果MAGを学習する問題を考察する。
本稿では,音と完全性を備えた計算効率のよい制約ベースの新しい手法を提案する。
提案手法と人工と実世界の両方の構造に関する技術の現状を比較した実験結果を提供する。
論文 参考訳（メタデータ） (2021-10-22T19:49:59Z) - Recovering Causal Structures from Low-Order Conditional Independencies [6.891238879512672]
与えられた順序の条件付き不依存性の集合に対するアルゴリズムを提案し、$k$と等しいか、あるいは、$k$は小さい固定数である。
本研究の結果は, 対の辺縁関係から学ぶことに関するこれまでの研究を完全化し, 一般化したものである。
論文 参考訳（メタデータ） (2020-10-06T12:47:20Z) - Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent [29.684442397855197]
我々は,高次元仮説テストの文脈において,最も普及している2つの制限された計算モデル,統計クエリフレームワークと低次コローラについて検討した。
テスト問題に関する穏やかな条件下では、2種類のアルゴリズムは本質的にはパワーで等価である。
提案手法では, スパースPCA, テンソルPCA, および植木クリッド問題のいくつかの変種に対して, 新たな統計的クエリローバウンドを求める。
論文 参考訳（メタデータ） (2020-09-13T22:55:18Z) - A Constraint-Based Algorithm for the Structural Learning of
Continuous-Time Bayesian Networks [70.88503833248159]
連続時間ベイズネットワークの構造を学習するための制約に基づく最初のアルゴリズムを提案する。
我々は,条件付き独立性を確立するために提案した,異なる統計的テストと基礎となる仮説について論じる。
論文 参考訳（メタデータ） (2020-07-07T07:34:09Z) - Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。
スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。
本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-23T04:25:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。