論文の概要: A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the same Skeleton
- arxiv url: http://arxiv.org/abs/2310.04218v5
- Date: Wed, 3 Jul 2024 04:41:05 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-04 20:33:17.039983
- Title: A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the same Skeleton
- Title（参考訳）: 同じ骨格を持つマルコフ等価クラスを数える固定パラメータトラクタブルアルゴリズム
- Authors: Vidya Sagar Sharma,
- Abstract要約: 因果DAG(Bayesian Network)は、確率変数間の条件依存を符号化する一般的なツールである。
しかし、同じ確率変数の集合上の2つの異なる因果DAGに対して、全く同じ条件依存の集合をエンコードすることが可能である。
そのような因果DAGはマルコフ同値であり、マルコフ同値DAGの同値類はマルコフ同値類(Markov Equivalent Classs、MECs)として知られている。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Causal DAGs (also known as Bayesian networks) are a popular tool for encoding conditional dependencies between random variables. In a causal DAG, the random variables are modeled as vertices in the DAG, and it is stipulated that every random variable is independent of its ancestors conditioned on its parents. It is possible, however, for two different causal DAGs on the same set of random variables to encode exactly the same set of conditional dependencies. Such causal DAGs are said to be Markov equivalent, and equivalence classes of Markov equivalent DAGs are known as Markov Equivalent Classes (MECs). Beautiful combinatorial characterizations of MECs have been developed in the past few decades, and it is known, in particular that all DAGs in the same MEC must have the same "skeleton" (underlying undirected graph) and v-structures (induced subgraph of the form $a\rightarrow b \leftarrow c$). These combinatorial characterizations also suggest several natural algorithmic questions. One of these is: given an undirected graph $G$ as input, how many distinct Markov equivalence classes have the skeleton $G$? Much work has been devoted in the last few years to this and other closely related problems. However, to the best of our knowledge, a polynomial time algorithm for the problem remains unknown. In this paper, we make progress towards this goal by giving a fixed parameter tractable algorithm for the above problem, with the parameters being the treewidth and the maximum degree of the input graph $G$. The main technical ingredient in our work is a construction we refer to as shadow, which lets us create a "local description" of long-range constraints imposed by the combinatorial characterizations of MECs.
- Abstract（参考訳）: 因果DAG(Bayesian Network)は、確率変数間の条件依存を符号化する一般的なツールである。
因果的DAGでは、ランダム変数はDAGの頂点としてモデル化され、全てのランダム変数は両親に条件付けられた祖先から独立していることが規定されている。
しかし、同じ確率変数の集合上の2つの異なる因果DAGに対して、全く同じ条件依存の集合をエンコードすることが可能である。
そのような因果DAGはマルコフ同値であるとされ、マルコフ同値DAGの同値類はマルコフ同値類(Markov Equivalent Classs、MECs)として知られている。
MECの美しい組合せ的特徴はここ数十年で開発され、特に同じMEC内のすべてのDAGは、同じ「スケルトン」と v-構造($a\rightarrow b \leftarrow c$ という形に誘導される部分グラフ)を持つ必要があることが知られている。
これらの組合せ的特徴は、いくつかの自然なアルゴリズム的問題も示唆している。
入力として無向グラフ$G$を与えられたとき、マルコフ同値類がスケルトン$G$を持つものはいくつあるか?
ここ数年、多くの研究がこの問題や他の密接に関連する問題に注がれている。
しかし、我々の知る限りでは、この問題に対する多項式時間アルゴリズムはいまだに不明である。
本稿では、上記の問題に対してパラメータを木幅とし、入力グラフの最大度を$G$とすることで、この目標に向かって前進する。
我々の研究の主な技術的要素は、私たちがシャドウと呼ぶ構造であり、MECの組合せ的特徴によって課される長距離制約の「局所的な記述」を作成することができる。
関連論文リスト
- Linear Transformer Topological Masking with Graph Random Features [52.717865653036796]
重み付き隣接行列の学習可能な関数としてトポロジカルマスクをパラメータ化する方法を示す。
私たちの効率的なマスキングアルゴリズムは、画像およびポイントクラウドデータのタスクに対して、強力なパフォーマンス向上を提供します。
論文 参考訳（メタデータ） (2024-10-04T14:24:06Z) - Learning High-Dimensional Differential Graphs From Multi-Attribute Data [12.94486861344922]
類似構造を持つことが知られている2つのガウス図形モデル(GGM)の違いを推定する問題を考える。
差分グラフ推定の既存の方法は単一属性(SA)モデルに基づいている。
本稿では,多属性データから差分グラフ学習のためのグループラッソペナル化Dトレース損失関数手法を解析する。
論文 参考訳（メタデータ） (2023-12-05T18:54:46Z) - Identification for Tree-shaped Structural Causal Models in Polynomial
Time [1.5151556900495786]
ノード間の相関から因果パラメータを同定することは、人工知能におけるオープンな問題である。
本稿では,木を配向成分とするSCMについて検討する。
本稿では,木形SCMの同定問題を解くランダム時間アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-11-23T15:26:29Z) - iSCAN: Identifying Causal Mechanism Shifts among Nonlinear Additive
Noise Models [48.33685559041322]
本稿では,同一変数集合上の2つ以上の関連するデータセットにおける因果メカニズムシフトの同定に焦点をあてる。
提案手法を実装したコードはオープンソースであり、https://github.com/kevinsbello/iSCAN.comで公開されている。
論文 参考訳（メタデータ） (2023-06-30T01:48:11Z) - Discrete Graph Auto-Encoder [52.50288418639075]
離散グラフオートエンコーダ(DGAE)という新しいフレームワークを導入する。
まず、置換同変オートエンコーダを用いてグラフを離散潜在ノード表現の集合に変換する。
2番目のステップでは、離散潜在表現の集合をソートし、特別に設計された自己回帰モデルを用いてそれらの分布を学習する。
論文 参考訳（メタデータ） (2023-06-13T12:40:39Z) - Generalized Precision Matrix for Scalable Estimation of Nonparametric
Markov Networks [11.77890309304632]
マルコフネットワークは、確率変数の集合の中で条件独立構造またはマルコフ特性を特徴づける。
本研究では,すべてのデータ型に対する一般分布における条件独立構造を特徴付ける。
また,変数間の一般関数関係を許容し,マルコフネットワーク構造学習アルゴリズムを考案する。
論文 参考訳（メタデータ） (2023-05-19T01:53:10Z) - Efficient Enumeration of Markov Equivalent DAGs [6.288056740658763]
本稿では,最初の線形時間遅延アルゴリズムを提案する。
理論的には、我々のアルゴリズムは、背景知識を組み込んだモデルで表されるDAGを列挙するために一般化できることが示される。
また、マルコフ同値性自体に興味深い洞察を与える。
論文 参考訳（メタデータ） (2023-01-28T14:35:39Z) - Causal Inference Despite Limited Global Confounding via Mixture Models [4.721845865189578]
そのようなモデルの有限$k$-mixtureは、図式的により大きなグラフで表される。
空でないDAGの混合を学習するための最初のアルゴリズムを与える。
論文 参考訳（メタデータ） (2021-12-22T01:04:50Z) - Benchmarking Multivariate Time Series Classification Algorithms [69.12151492736524]
時系列分類(TSC)は、順序付き、実値付き、属性から離散的なターゲット変数の予測モデルを構築することを含む。
近年,従来の技術よりも大幅に改良された新しいTSCアルゴリズムが開発されている。
本稿では, 深層学習, シェープレット, 単語の袋を用いた MTSC アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-07-26T15:56:40Z) - Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。
アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。
ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
論文 参考訳（メタデータ） (2020-02-20T10:50:58Z) - Fast and Robust Comparison of Probability Measures in Heterogeneous
Spaces [62.35667646858558]
本稿では, アンカー・エナジー (AE) とアンカー・ワッサースタイン (AW) 距離を紹介する。
我々の主な貢献は、素案実装が立方体となる対数四重項時間でAEを正確に計算するスイープラインアルゴリズムを提案することである。
AE と AW は,一般的な GW 近似の計算コストのごく一部において,様々な実験環境において良好に動作することを示す。
論文 参考訳（メタデータ） (2020-02-05T03:09:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。