論文の概要: Lower Bounds on the Size of Markov Equivalence Classes

• arxiv url: http://arxiv.org/abs/2506.20933v1
• Date: Thu, 26 Jun 2025 01:44:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-27 19:53:09.939293
• Title: Lower Bounds on the Size of Markov Equivalence Classes
• Title（参考訳）: マルコフ同値類のサイズに関する下界
• Authors: Erik Jahn, Frederick Eberhardt, Leonard J. Schulman,
• Abstract要約: マルコフ同値クラスの期待値に対して指数関数的に大きな下界を3つの設定で証明する。 これらの仮定が緩和された場合、もはやそうではないことを示す。
• 参考スコア（独自算出の注目度）: 3.5584529568201386
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Causal discovery algorithms typically recover causal graphs only up to their Markov equivalence classes unless additional parametric assumptions are made. The sizes of these equivalence classes reflect the limits of what can be learned about the underlying causal graph from purely observational data. Under the assumptions of acyclicity, causal sufficiency, and a uniform model prior, Markov equivalence classes are known to be small on average. In this paper, we show that this is no longer the case when any of these assumptions is relaxed. Specifically, we prove exponentially large lower bounds for the expected size of Markov equivalence classes in three settings: sparse random directed acyclic graphs, uniformly random acyclic directed mixed graphs, and uniformly random directed cyclic graphs.
• Abstract（参考訳）: 因果発見アルゴリズムは通常、追加のパラメトリック仮定が作成されない限り、マルコフ同値類のみが因果グラフを復元する。 これらの同値類のサイズは、純粋な観測データから基礎となる因果グラフについて学べることの限界を反映している。 非巡回性、因果補足性、およびそれ以前の一様モデルという仮定の下で、マルコフ同値類は平均して小さいことが知られている。 本稿では、これらの仮定が緩和された場合、もはやそうではないことを示す。 具体的には、マルコフ同値類の期待値に対して指数関数的に大きな下界を、3つの設定で証明する:スパースランダム非巡回グラフ、一様ランダム非巡回混合グラフ、一様ランダム非巡回グラフ。

関連論文リスト

• Violation of Bell's inequalities in uniform random graphs [0.0]
  ランダム離散モデルの統計的相関から量子相関が生まれることを実証する。 エルドス・レーニ一様ランダムグラフにおける頂点対の近傍数(次数)の相関について検討する。
  論文  参考訳（メタデータ） (2023-05-04T12:46:26Z)
• Parametric Classification for Generalized Category Discovery: A Baseline Study [70.73212959385387]
  Generalized Category Discovery (GCD)は、ラベル付きサンプルから学習した知識を用いて、ラベルなしデータセットで新しいカテゴリを発見することを目的としている。 パラメトリック分類器の故障を調査し,高品質な監視が可能であった場合の過去の設計選択の有効性を検証し,信頼性の低い疑似ラベルを重要課題として同定する。 エントロピー正規化の利点を生かし、複数のGCDベンチマークにおける最先端性能を実現し、未知のクラス数に対して強いロバスト性を示す、単純で効果的なパラメトリック分類法を提案する。
  論文  参考訳（メタデータ） (2022-11-21T18:47:11Z)
• Rethinking Knowledge Graph Evaluation Under the Open-World Assumption [65.20527611711697]
  ほとんどの知識グラフ(KG)は不完全であり、知識グラフを自動補完する重要な研究トピックの動機となっている。 すべての未知の三つ子を偽として扱うことは、閉世界仮定(close-world assumption)と呼ばれる。 本稿では,KGCの評価を,より現実的な条件,すなわちオープンワールドの仮定の下で研究する。
  論文  参考訳（メタデータ） (2022-09-19T09:01:29Z)
• Characterization of causal ancestral graphs for time series with latent confounders [1.6317061277457001]
  本稿では,時間ラグ特定因果関係を表すグラフィカルモデルについて紹介する。 現在使用されているモデルクラスの適切なサブセットを構成することを示す。 さらに、新しいグラフのマルコフ同値クラスのグラフィカル表現を導入する。
  論文  参考訳（メタデータ） (2021-12-15T19:04:46Z)
• Typing assumptions improve identification in causal discovery [123.06886784834471]
  観測データからの因果発見は、正確な解を常に特定できない難しい課題である。 そこで本研究では,変数の性質に基づいた因果関係を制約する仮説を新たに提案する。
  論文  参考訳（メタデータ） (2021-07-22T14:23:08Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• Conditions and Assumptions for Constraint-based Causal Structure Learning [2.741266294612776]
  この論文は、観測データから「真の」因果グラフの制約に基づく構造学習を定式化する。 分布が真の因果グラフに対するマルコヴィアンであるという仮定の下で、モデルの一般クラスに対する理論を提供する。
  論文  参考訳（メタデータ） (2021-03-24T23:08:00Z)
• Structure Learning for Cyclic Linear Causal Models [5.567377163246147]
  観測データに基づく線形因果モデルにおける構造学習の問題点を考察する。 循環型混成グラフによって与えられるモデルを扱うことで、フィードバックループと潜伏した共同設立者の影響を可能とします。
  論文  参考訳（メタデータ） (2020-06-10T17:47:28Z)

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

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