論文の概要: A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence
Classes with the same Skeleton
- arxiv url: http://arxiv.org/abs/2310.04218v2
- Date: Fri, 23 Feb 2024 10:57:57 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-26 17:56:20.335915
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。