論文の概要: A PC Algorithm for Max-Linear Bayesian Networks

• arxiv url: http://arxiv.org/abs/2508.13967v1
• Date: Tue, 19 Aug 2025 15:57:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-20 15:36:32.004634
• Title: A PC Algorithm for Max-Linear Bayesian Networks
• Title（参考訳）: 最大線形ベイズネットワークのためのPCアルゴリズム
• Authors: Carlos Améndola, Benjamin Hollering, Francesco Nowell,
• Abstract要約: 最大線形ベイズネットワーク(英: Max-linear Bayesian Network、MLBN)は、構造方程式モデルの比較的最近のクラスである。 MLBNはd-セパレーションに忠実ではないため、PCアルゴリズムやグリーディ同値探索のような古典的な因果探索アルゴリズムは真のグラフ構造を正確に復元することができない。 我々は,PCstarと呼ばれる新たな因果発見アルゴリズムを導入し,$Cast$-セパレーションに忠実さを仮定し,d-または$ast$-セパレーションのみで指向できない追加エッジをオリエントすることができる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Max-linear Bayesian networks (MLBNs) are a relatively recent class of structural equation models which arise when the random variables involved have heavy-tailed distributions. Unlike most directed graphical models, MLBNs are typically not faithful to d-separation and thus classical causal discovery algorithms such as the PC algorithm or greedy equivalence search can not be used to accurately recover the true graph structure. In this paper, we begin the study of constraint-based discovery algorithms for MLBNs given an oracle for testing conditional independence in the true, unknown graph. We show that if the oracle is given by the $\ast$-separation criteria in the true graph, then the PC algorithm remains consistent despite the presence of additional CI statements implied by $\ast$-separation. We also introduce a new causal discovery algorithm named "PCstar" which assumes faithfulness to $C^\ast$-separation and is able to orient additional edges which cannot be oriented with only d- or $\ast$-separation.
• Abstract（参考訳）: 最大線形ベイズネットワーク(英: Max-linear Bayesian Network, MLBN)は、確率変数が重み付き分布を持つときに生じる、比較的最近の構造方程式モデルである。 多くの方向付けされたグラフィカルモデルとは異なり、MLBNは一般にd-セパレーションに忠実ではないため、PCアルゴリズムやgreedy同値探索のような古典的な因果探索アルゴリズムは真のグラフ構造を正確に復元することができない。 本稿では,真の未知グラフにおいて条件独立性をテストするためのオラクルを与えられたMLBNに対する制約に基づく探索アルゴリズムの研究を開始する。 オラクルが真のグラフの$\ast$-セパレーション基準によって与えられる場合、PCアルゴリズムは$\ast$-セパレーションによって示される追加のCIステートメントが存在するにもかかわらず、一貫していることを示す。 また、「PCstar」と呼ばれる新たな因果探索アルゴリズムを導入し、$C^\ast$-セパレーションに忠実さを仮定し、d-または$\ast$-セパレーションのみで指向できない追加のエッジを指向することができる。

関連論文リスト

• On the Price of Differential Privacy for Hierarchical Clustering [21.64775530337936]
  本稿では, エッジレベルのDP設定において, 既知の可視性よりもはるかに高い近似性を示す, 重み付きプライバシモデルにおける新しいアルゴリズムを提案する。 以上の結果から,提案アルゴリズムはコストの面では良好に動作し,大規模グラフに対するスケーラビリティも良好であることがわかった。
  論文  参考訳（メタデータ） (2025-04-22T04:39:40Z)
• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。 我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
  論文  参考訳（メタデータ） (2024-03-21T11:57:16Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• On the Unlikelihood of D-Separation [69.62839677485087]
  解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。 PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。 UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
  論文  参考訳（メタデータ） (2023-03-10T00:11:18Z)
• 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)
• Characterization and Learning of Causal Graphs with Small Conditioning Sets [6.52423450125622]
  制約に基づく因果探索アルゴリズムは、条件付き独立性を体系的にテストすることで因果グラフ構造の一部を学習する。 2つの因果グラフ間の$k$-Markov同値をグラフィカルに特徴付ける新しい表現を提案する。 合成および半合成実験を行い、$k$-PCアルゴリズムがより堅牢な因果発見を可能にすることを示す。
  論文  参考訳（メタデータ） (2023-01-22T00:24:22Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。 我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2021-07-12T21:30:41Z)
• A New Minimax Theorem for Randomized Algorithms [1.2284934135116514]
  新しいタイプのミニマックス定理を導入し、全てのバイアスレベルに一度に作用するハード分布の$mu$を提供する。 ランダム化クエリの複雑性,ランダム化通信の複雑性,近似度数,近似対数に対して有効であることを示す。 また、Impagliazzoのハードコアの改良版も証明した。
  論文  参考訳（メタデータ） (2020-02-25T11:46:08Z)

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

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