論文の概要: Counting Markov Equivalent Directed Acyclic Graphs Consistent with Background Knowledge

• arxiv url: http://arxiv.org/abs/2206.06744v1
• Date: Tue, 14 Jun 2022 10:45:43 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-15 22:26:13.479892
• Title: Counting Markov Equivalent Directed Acyclic Graphs Consistent with Background Knowledge
• Title（参考訳）: 背景知識に整合したマルコフ等価非巡回グラフの計数
• Authors: Vidya Sagar Sharma
• Abstract要約: いくつかの辺の向きも固定されているとき、マルコフ同値類における非巡回グラフの数を数えるというより一般的な問題を考える。 特に、我々のアルゴリズムは入力として提供される追加のエッジの数に依存しない。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A polynomial-time exact algorithm for counting the number of directed acyclic graphs in a Markov equivalence class was recently given by Wien\"obst, Bannach, and Li\'skiewicz (AAAI 2021). In this paper, we consider the more general problem of counting the number of directed acyclic graphs in a Markov equivalence class when the directions of some of the edges are also fixed (this setting arises, for example, when interventional data is partially available). This problem has been shown in earlier work to be complexity-theoretically hard. In contrast, we show that the problem is nevertheless tractable in an interesting class of instances, by establishing that it is ``fixed-parameter tractable''. In particular, our counting algorithm runs in time that is bounded by a polynomial in the size of the graph, where the degree of the polynomial does \emph{not} depend upon the number of additional edges provided as input.
• Abstract（参考訳）: マルコフ同値類における有向非巡回グラフの数を計算する多項式時間正確なアルゴリズムは、最近Wien\obst, Bannach, Li\'skiewicz (AAAI 2021) によって与えられた。 本稿では,マルコフ同値類における有向非巡回グラフの数を数えるというより一般的な問題について考察する(例えば,介入データが部分的に利用可能である場合など)。 この問題は、初期の研究で複雑性理論上難しいことが示されている。 対照的に、この問題は興味深いインスタンスのクラスにおいて、 ``fixed-parameter tractable'' であることを示すことによって、トラクタブルであることが示される。 特に、我々のカウントアルゴリズムは、多項式の次数が入力として提供される追加エッジの数に依存するようなグラフの大きさの多項式によって境界付けられた時間で実行される。

関連論文リスト

• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras [0.0]
  連結グラフ上の最大カット(最大カット)問題に対する3つの QAOA ans" の根底となる代数的性質について検討する。 任意の連結グラフに対して、多角アンザッツのリー代数を完全に特徴づけることができる。
  論文  参考訳（メタデータ） (2024-10-07T16:46:20Z)
• Linear Transformer Topological Masking with Graph Random Features [52.717865653036796]
  重み付き隣接行列の学習可能な関数としてトポロジカルマスクをパラメータ化する方法を示す。 私たちの効率的なマスキングアルゴリズムは、画像およびポイントクラウドデータのタスクに対して、強力なパフォーマンス向上を提供します。
  論文  参考訳（メタデータ） (2024-10-04T14:24:06Z)
• Random walks on simplicial complexes [0.9937132009954994]
  マルコフ連鎖の生成元は、離散構造に対する代数トポロジーの文脈で定義される上ラプラシアンであることが示される。 本研究は, 単体錯体が平坦なトーラスの再精製三角形の列である場合の拡散限界について検討する。
  論文  参考訳（メタデータ） (2024-04-12T20:37:34Z)
• Sequence graphs realizations and ambiguity in language models [1.4732811715354455]
  計算的観点から,シーケンスグラフの実現可能性とあいまいさについて検討する。 大きさが 3 の窓に対して、w が定数であるとしても、すべての不変量の硬さを証明する。 本稿では、実現可能性問題を解く整数プログラムと、列挙問題の解法を動的プログラミングで結論付ける。
  論文  参考訳（メタデータ） (2024-02-13T22:22:51Z)
• The Complexity of Envy-Free Graph Cutting [44.58084909019557]
  我々は,異なる選好を持つエージェント間で,不均一なリソースの集合を公平に分割する問題を考察する。 我々は、リソースが連結グラフのエッジに対応するような設定に集中し、すべてのエージェントがこのグラフの連結片を割り当てなければならない。 問題はNP完全であり、エージェントの数とグラフ内のエッジの数という2つの自然な複雑さの尺度に関して、その複雑さを分析する。
  論文  参考訳（メタデータ） (2023-12-12T07:54:30Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  グラフ埋め込みの信頼性は、連続空間の幾何がグラフ構造とどの程度一致しているかに依存する。 我々は、この問題を解決することができる、ソフト多様体と呼ばれる新しい多様体のクラスを導入する。 グラフ埋め込みにソフト多様体を用いることで、複雑なデータセット上のデータ解析における任意のタスクを追求するための連続空間を提供できる。
  論文  参考訳（メタデータ） (2023-11-29T12:48:33Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Correlation Clustering in Constant Many Parallel Rounds [42.10280805559555]
  相関クラスタリングは教師なし学習において中心的なトピックであり、MLやデータマイニングに多くの応用がある。 本研究では,従来よりもかなり高速な超並列計算(MPC)アルゴリズムを提案する。 我々のアルゴリズムは,ノード数にメモリサブリニアを持つマシンを使用し,一定回数のラウンドでのみ実行しながら,一定の近似を返す。
  論文  参考訳（メタデータ） (2021-06-15T21:45:45Z)
• Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs [45.87981728307819]
  異種空間に居住する関連するデータセットを比較して整列する能力は、機械学習においてますます重要な役割を担っている。 グロモフ・ワッサーシュタイン (Gromov-Wasserstein, GW) 形式主義はこの問題に対処するのに役立つ。
  論文  参考訳（メタデータ） (2021-06-02T12:50:56Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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