# (参考訳) 段階木を用いた分類データのコンテキスト特異的因果探索 [全文訳有]

Context-Specific Causal Discovery for Categorical Data Using Staged Trees ( http://arxiv.org/abs/2106.04416v1 )

ライセンス: CC BY 4.0
Manuele Leonelli and Gherardo Varando(参考訳) 因果発見アルゴリズムは、観測データのみを用いた複雑な因果関係の解消を目的としている。 本稿では,複雑かつ非対称な因果効果を表現できる段階木モデルに基づく新しい因果発見アルゴリズムを提案する。 提案アルゴリズムの有効性を示すために, 広く使用されている構造的介入距離から着想を得た新しい距離を導入し, 対応する因果推論文を用いて2つの木間の近接性を定量化する。 シミュレーション研究は、データからの非対称因果関係を明らかにする際に、ステージ木の有効性を強調し、実際の因果解析におけるそれらの利用を例示する。

Causal discovery algorithms aims at untangling complex causal relationships using observational data only. Here, we introduce new causal discovery algorithms based on staged tree models, which can represent complex and non-symmetric causal effects. To demonstrate the efficacy of our algorithms, we introduce a new distance, inspired by the widely used structural interventional distance, to quantify the closeness between two staged trees in terms of their corresponding causal inference statements. A simulation study highlights the efficacy of staged trees in uncovering complex, asymmetric causal relationship from data and a real-world data application illustrates their use in a practical causal analysis.
公開日: Tue, 8 Jun 2021 14:46:15 GMT

※ 翻訳結果を表に示しています。PDFがオリジナルの論文です。翻訳結果のライセンスはCC BY-SA 4.0です。詳細はトップページをご参照ください。


    Page: /      
1 2 0 2 n u J 1 2 0 2 n u J 0.85
8 ] E M . t a t s [ 8 ]EM . t a t s [ 0.75
1 v 6 1 4 4 0 1 v 6 1 4 4 0 0.85
. 6 0 1 2 : v i X r a . 6 0 1 2 : v i X r a 0.85
Context-Specific Causal Discovery for Categorical カテゴリーのコンテキスト特異的因果発見 0.55
Data Using Staged Trees School of Human Sciences and Technology 段木を用いたデータ 人文科学研究科 0.51
manuele.leonelli@ie. edu manuele.leonelli@ie. edu 0.59
Manuele Leonelli マヌエル・レオネッリ 0.54
IE University Madrid, Spain スペイン・マドリードのIE大学 0.79
Gherardo Varando ゲラルド・ヴァランド(Gherardo Varando) 0.47
Image Processing Laboratory Universitat de València 画像処理研究室 ヴァレンシア大学 0.63
València, Spain スペイン・バレンシア 0.64
gherardo.varando@uv. es gherardo.varando@uv. es 0.59
Abstract Causal discovery algorithms aims at untangling complex causal relationships using observational data only. 概要 因果発見アルゴリズムは、観測データのみを用いた複雑な因果関係の解消を目的としている。 0.50
Here, we introduce new causal discovery algorithms based on staged tree models, which can represent complex and non-symmetric causal effects. 本稿では,複雑かつ非対称な因果効果を表現できる段階木モデルに基づく新しい因果発見アルゴリズムを提案する。 0.78
To demonstrate the efficacy of our algorithms, we introduce a new distance, inspired by the widely used structural interventional distance, to quantify the closeness between two staged trees in terms of their corresponding causal inference statements. 提案アルゴリズムの有効性を示すために, 広く使用されている構造的介入距離から着想を得た新しい距離を導入し, 対応する因果推論文を用いて2つの木間の近接性を定量化する。 0.75
A simulation study highlights the efficacy of staged trees in uncovering complex, asymmetric causal relationship from data and a real-world data application illustrates their use in a practical causal analysis. シミュレーション研究は、データからの非対称因果関係を明らかにする際に、ステージ木の有効性を強調し、実際の因果解析におけるそれらの利用を例示する。
訳抜け防止モード: 実生木の有効性に関するシミュレーション研究 データと実世界データアプリケーションからの複雑な非対称因果関係を明らかにする 実践的な因果分析に使われています
1 Introduction One of the major tasks in all areas of science is to uncover causal relationships between variables of interest. 1 はじめに 科学のあらゆる分野における主要な課題の1つは、興味のある変数間の因果関係を明らかにすることである。 0.67
Since experimental data is in many cases unavailable, this task often comes down to discover such relationships using observational data only. 実験データは利用できない場合が多いため、観測データのみを用いてそのような関係を発見することがしばしばある。 0.81
This is usually referred to as causal discovery. これは通常、因果発見と呼ばれる。 0.74
One of the most common approaches in causal discovery, as well as in causal analysis, is to represent causal relationships via directed acyclic graphs (DAGs). 因果発見における最も一般的なアプローチの1つは、有向非巡回グラフ(DAG)を通して因果関係を表現することである。 0.68
In such graphs if there is an edge pointing from a variable to another, then the former is a direct cause of the other [Pearl, 2009]. そのようなグラフでは、ある変数から別の変数へのエッジがある場合、前者は後者 [pearl, 2009] の直接の原因となる。 0.78
The literature on causal discovery using DAGs is now extensive [see Glymour et al , 2019, for a rewiev]. DAGによる因果関係の発見に関する文献は、現在広く研究されている[Glymour et al , 2019, for a rewiev]。 0.74
The most common approaches are the PC-algorithm [Spirtes et al , 2000], greedy equivalence search [Chickering, 2002] and functional causal models [Hoyer et al , 2008, Shimizu et al , 2006]. 最も一般的なアプローチはpc-algorithm [spirtes et al , 2000], greedy equivalence search [chickering, 2002], 関数因果モデル [hoyer et al , 2008 shimizu et al , 2006] である。 0.79
Although more efficient and scalable causal discovery algorithms are still developed [e g Monti et al , 2020, Viinikka et al , 2020], most of the recent literature has focused on continuous random variables only. より効率的でスケーラブルな因果発見アルゴリズム(monti et al , 2020, viinikka et al , 2020)はまだ開発されているが、最近の文献のほとんどは連続確率変数のみに焦点を当てている。 0.78
Attention to causal discovery for observational discrete data has been lately very limited [see e g Cai et al , 2018, Cowell and Smith, 2014, Huang et al , 2018, Peters et al , 2010, for exceptions]. 観測的な離散データに対する因果発見への関心は、最近非常に限られている(例: e g Cai et al , 2018, Cowell and Smith, 2014, Huang et al , 2018, Peters et al , 2010)。 0.79
The aim of this paper is to discuss flexible and powerful causal discovery algorithms for categorical data embedding complex and non-symmetric variable relationships and to highlight their efficacy. 本研究の目的は,複雑および非対称な変数関係を埋め込んだ分類データの柔軟な因果探索アルゴリズムについて検討し,その有効性を明らかにすることである。 0.70
Whilst most causal discovery is carried out via DAG models, here we consider staged tree models [Collazo et al , 2018, Smith and Anderson, 2008] which, differently to DAGs, can represent a wide array of non-symmetric causal effects between discrete variables. もっとも因果的発見はDAGモデルを用いて行われているが, 離散変数間の非対称因果的影響を広範囲に表すことができる実生木モデル (Collazo et al , 2018, Smith and Anderson, 2008) を考察する。 0.72
Bayesian MAP structural learning algorithms for this model class have been introduced [Collazo and Smith, 2016, Cowell and Smith, 2014, Freeman and Smith, 2011] as well as score-based ones [Leonelli and Varando, 2021, Silander and Leong, 2013]. このモデルクラスのベイズMAP構造学習アルゴリズム(Collazo and Smith, 2016, Cowell and Smith, 2014, Freeman and Smith, 2011)とスコアベースアルゴリズム(Leonelli and Varando, 2021, Silander and Leong, 2013)が導入された。 0.77
The latter have been implemented in the open-source stagedtreees R package [Carli et al , 2020] and are used henceforth. 後者はオープンソースのStadtreees Rパッケージ[Carli et al , 2020]で実装されており、それ以降使用されている。 0.73
Whilst there has been an extensive effort in determining causal effects [Genewein et al , 2020, Görgen et al , 2015, Thwaites et al , 2010, Thwaites, 2013] and equivalence classes [Duarte and Solus, 因果効果(genewein et al , 2020, görgen et al , 2015 thwaites et al , 2010, thwaites, 2013)と等価クラス [duarte and solus,] を決定することには、多大な努力があった。 0.72
Preprint. Under review. プレプリント。 レビュー中。 0.63
v0 0 = X 2 v0 0 = X 2 0.83
0 = X 1 v1 0 = X 1 v1 0.83
X2 = 1 v3 v4 X2 = 1 v3 v4 0.84
X 1= 1 v2 X 2 = 0 X 1= 1 v2 X 2 = 0 0.82
v5 X 2= 1 v6 v5 X 2= 1 v6 0.81
X 3 = 0 X3 = 1 X 3 = 0 X 3 = 0 X3 = 1 X 3 = 0 0.90
X3 = 1 X 3 = 0 X3 = 1 X 3 = 0 0.96
X3 = 1 X 3 = 0 X3 = 1 X 3 = 0 0.96
X3 = 1 w0 0 X3 = 1 w0 0 0.86
= X 3 w3 0 = X 3 w3 0 0.83
= X 1 w1 X3 = 1 = X 1 W1 X3 = 1 0.81
w4 X 1= 1 w2 w4 X 1= 1 w2 0.81
X 3 = 0 w5 X 3 = 0 w5 0.82
X 3= 1 w6 X 2 = 0 X 3= 1 W6 X 2 = 0 0.80
X2 = 1 X 2 = 0 X2 = 1 X 2 = 0 0.96
X2 = 1 X 2 = 0 X2 = 1 X 2 = 0 0.96
X2 = 1 X 2 = 0 X2 = 1 X 2 = 0 0.96
X2 = 1 Figure 1: An example of an (X1, X2, X3)-compatible (left) and an (X1, X3, X2)-compatible (right) staged trees. X2 = 1 図1:(X1, X2, X3)互換木(左)と(X1, X3, X2)互換木(右)の例。 0.86
2020, Görgen and Smith, 2018, Görgen et al , 2018], only one causal discovery algorithm has been proposed by Cowell and Smith [2014]. 2020, Görgen and Smith, 2018, Görgen et al , 2018], 1つの因果発見アルゴリズムがCowellとSmithによって提案されている[2014]。 0.88
Here we provide a first free implementation of the dynamic programming algorithm of Cowell and Smith [2014] based on the stagedtrees R package as well as a first extensive simulation study to assess its effectiveness. ここでは、stagedtrees rパッケージに基づいたcowell and smith [2014] の動的プログラミングアルゴリズムの最初の無料実装と、その効果を評価するための最初の広範囲なシミュレーション研究を提供する。 0.87
We demonstrate that staged trees are extremely powerful in discovering complex dependence structures and in general outperform DAGs for discrete data. 本研究では,複雑な依存構造を発見し,離散データに対してDAGよりも優れることを示す。 0.70
We do this by introducing and studying a new measure of dissimilarity between causal models tailored to the topology of staged trees and inspired by the widely-used structural intervention distance (SID) of Peters and Bühlmann [2015] which we henceforth call context-specific intervention discrepancy (CID). 我々は,ステージ木のトポロジーに合わせた因果モデルと,ピータースとビュールマン [2015] の広く使われている構造的介入距離 (sid) に触発された因果モデル間の相似性の新たな尺度を導入し,検討する。 0.67
Differently to SID which only accounts for symmetric causal relationships, our CID can more generally consider the difference between two causal models by accounting for complex, non-symmetric causal effects. 対称因果関係のみを考慮に入れているSIDとは異なり、我々のCIDはより一般的に2つの因果モデルの違いを複雑で非対称因果効果を考慮に入れることができる。 0.66
The code with the implemented methods and the simulation experiments is available at https: //github.com/gherard ovarando/context_spe cific_causal_discove ry. 実装されたメソッドとシミュレーション実験のコードは、https: //github.com/gherard ovarando/context_spe cific_causal_discove ryで入手できる。 0.54
2 Staged trees Let [p] = {1, . 2 段階木は [p] = {1, とする。 0.72
. . , p} and X = (Xi)i∈[p] be categorical random variables with joint mass function P and sample space X = ×i∈[p]Xi. . . , p} と X = (Xi)i・[p] は、結合質量関数 P とサンプル空間 X = ×i・[p]Xi を持つ圏変数である。 0.84
For A ⊂ [p], we let XA = (Xi)i∈A and xA = (xi)i∈A where xA ∈ XA = ×i∈AXi. A に対して、XA = (Xi)i・A と xA = (xi)i・A を xA ∈ XA = ×i・AXi とする。 0.83
We also let X−A = (Xi)i∈[p]\A. また、X−A = (Xi)i∂[p]\A とする。 0.84
Let (V, E) be a directed, finite, rooted tree with vertex set V , root node v0 and edge set E. For each v ∈ V , let E(v) = {(v, w) ∈ E} be the set of edges emanating from v and C be a set of labels. V, E) を頂点集合 V ,根ノード v0 および辺集合 E を持つ有向有限根木とし、各 v ∈ V に対して、E(v) = {(v, w) ∈ E} を v から発する辺の集合とし、C をラベルの集合とする。 0.76
Definition 1. An X-compatible staged tree is a triple (V, E, θ), where (V, E) is a rooted directed tree and: 定義1。 X 互換のステージ木は三重木(V, E, θ)であり、(V, E) はルート有向木であり、 0.70
1. V = v0 ∪(cid:83) 1. V = v0 > (cid:83) 0.84
i∈[p] X[i]; I--[p] X[i]; 0.65
2. For all v, w ∈ V , (v, w) ∈ E if and only if w = x[i] ∈ X[i] and v = x[i−1], or v = v0 and 2. すべての v に対し、w ∈ V , (v, w) ∈ E は w = x[i] ∈ X[i] および v = x[i−1] または v = v0 であることと一致する。 0.89
w = x1 for some x1 ∈ X1; ある x1 ∈ X1 に対して w = x1 である。 0.59
3. η : E → L = C × ∪i∈[p]Xi is a labelling of the edges such that η(v, x[i]) = (κ(v), xi) for 3. η : E → L = C × シュイ・[p]Xi は η(v, x[i]) = (κ(v, xi) となるような辺のラベルリングである。 0.79
some function κ : V → C. ある関数 κ : V → C である。 0.85
If η(E(v)) = η(E(w)) then v and w are said to be in the same stage. η(E(v)) = η(E(w)) ならば、v と w は同じ段階にあると言える。 0.66
Therefore, the equivalence classes induced by η(E(v)) form a partition of the internal vertices of the tree in stages. したがって、η(e(v)) によって誘導される同値類は、段階的に木の内部頂点の分割を形成する。 0.71
2 2 0.85
Definition 1 first constructs a rooted tree where each root-to-leaf path, or equivalently each leaf, is associated to an element of the sample space X. 定義1は、まず、各根対葉経路、または同値な各葉がサンプル空間Xの要素に関連付けられた根木を構築する。 0.79
Then a labeling of the edges of such a tree is defined where labels are pairs with one element from a set C and the other from the sample space Xi of the corresponding variable Xi in the tree. すると、そのような木の縁のラベル付けは、木内の対応する変数 Xi のサンプル空間 Xi からの1つの要素と1つの要素とのペアであるラベルを定義する。 0.72
By construction, X-compatible staged trees are such that two vertices can be in the same stage if and only if they correspond to the same sample space. 構成上、X 互換のステージ木は、2つの頂点が同一のサンプル空間に対応する場合に限って同じ段階にあるようなものである。 0.75
Although staged trees can be more generally defined without imposing this condition [see e g Collazo et al , 2018], henceforth, and as common in practice, we focus on X-compatible staged trees only [see Leonelli, 2019, for an example of a non X-compatible tree]. ステージ木は、この条件を課すことなく、より一般的に定義することができるが(例えばcollazo et al , 2018)、それゆえ、実際、一般的には、x互換ステージ木のみに焦点を当てている(leonelli、2019年、例えば、非x互換木)。
訳抜け防止モード: ステージ木は、より一般的に定義できるが、 この条件を暗示します [ e g Collazo et al, 2018] そのため、実際には、X-互換のステージツリーのみに焦点を当てています [Leonelli氏、2019年、例えば、非X-互換のツリー ]。
Figure 1 (left) reports an (X1, X2, X3)-compatible stratified staged tree over three binary variables. 図1(左)は、3つのバイナリ変数上の(X1, X2, X3)互換の成層木を報告します。 0.67
The coloring given by the function κ is shown in the vertices and each edge (·, (x1, . 函数 κ によって与えられる彩色は頂点と各辺 (·, (x1, ) で示される。 0.72
. . , xi)) is labeled with Xi = xi. . . xi) を Xi = xi とラベル付けする。 0.81
The edge labeling η can be read from the graph combining the text label and the color of the emanating vertex. エッジラベリングηは、テキストラベルと発散する頂点の色を組み合わせたグラフから読み取ることができる。 0.68
The staging of the staged tree in Figure 1 is given by the partition {v0}, {v1, v2}, {v3, v4}, {v5} and {v6}. 図1のステージ化ツリーのステージングは、パーティション {v0}, {v1, v2}, {v3, v4}, {v5}, {v6} によって与えられる。 0.85
The parameter space associated to an X-compatible staged tree T = (V, E, η) with labeling η : E → L is defined as X 互換のステージ木 T = (V, E, η) に関連するパラメータ空間は η : E → L とラベル付けされている。 0.84
ΘT = θ ∈ Rη(E) | ∀e ∈ E, θη(e) ∈ (0, 1) and ∀v θt = θ ∈ rη(e) | θe ∈ e, θη(e) ∈ (0, 1) および θv 0.77
θη(e) = 1 (1) θη(e) = 1 (1) 0.91
(cid:110) (cid:88) (cid:110) (cid:88) 0.78
e∈E(v) (cid:111) e- + E(v) (cid:111) 0.66
Let lT denote the leaves of a staged tree T . lt をステージ化された木 t の葉を表す。 0.70
Given a vertex v ∈ V , there is a unique path in T from the root v0 to v, denoted as λ(v). 頂点 v ∈ V が与えられたとき、T の根 v0 から v への一意な経路が存在し、λ(v) と表される。 0.73
For any path λ in T , let E(λ) = {e ∈ E : e ∈ λ} denote the set of edges in the path λ. Definition 2. t の任意の経路 λ に対して、e(λ) = {e ∈ e : e ∈ λ} を経路 λ 内の辺の集合とする。 0.74
The staged tree model MT associated to the X-compatible staged tree (V, E, η) is the image of the map x互換の段階木(v, e, η)に付随する段階木モデルmtは、地図のイメージである 0.67
φT : ΘT → ∆|lT |−1 φT : >T → >|lT |−1 0.63
(cid:55)→(cid:16)(cid:81) (cid:55)→(cid:16)(cid:81) 0.76
θ e∈E(λ(l)) θη(e) θ ehtmle(λ(l)) θη(e) 0.77
(cid:17) l∈lT (cid:17) l・l・l・l・l 0.45
(2) An element of M(T ) in Definition (2) identifies a joint probability Pθ with conditional distributions (2) 定義 (2) における M(T ) の元は条件分布を伴う合同確率 Pθ を識別する 0.84
Pθ(Xi = xi|X[i−1] = x[i−1]) = θη(x[i−1],x[i]) ∀x ∈ X and i ∈ [p]. Pθ(Xi = xi|X[i−1] = x[i−1]) = θη(x[i−1],x[i]) は x ∈ X と i ∈ [p] である。 0.88
In the staged tree in Figure 1 the staging {v1, v2} implies that the conditional distribution of X2 given X1 = 0, represented by the edges emanating from v1, is equal to the conditional distribution of X2 given X1 = 1. 図1の段階木において、ステージング {v1, v2} は、与えられた x1 = 0 の条件分布が、v1 から発する辺によって表され、x1 = 1 の与えられた x2 の条件分布と等しいことを意味する。 0.77
It is apparent now that the vertex staging represents conditional independence: the fact that v1 and v2 are in the same stage implies that X1 ⊥⊥ X2. v1 と v2 が同じ段階にあるという事実は、x1 が x2 であることを意味する。
訳抜け防止モード: 頂点ステージングが条件付き独立を表すことは、現在明らかである。 v1 と v2 が同じ段階にあるという事実から、X1 は X2 である。
The staging given by the blue vertices implies the context-specific independence [Boutilier et al , 1996] X3 ⊥⊥ X2|X1 = 0: the independence between X3 and X2 holds only for one of the two levels of X1. blue vertices によって与えられる演出は、文脈固有の独立性 [boutilier et al , 1996] x3 と x2|x1 = 0: x3 と x2 の間の独立性は、x1 の2つのレベルのうちの1つしか持たない。 0.67
For such a staged tree there is no equivalent DAG representation, since it embeds non-symmetric conditional independences [Varando et al , 2021]. そのようなステージ木に対しては、非対称な条件独立性(Varando et al , 2021]を埋め込むため、等価なDAG表現は存在しない。 0.64
Two staged trees T and S are said to be statistically equivalent if they induce the same models, that is MT = MS. Definition 3. 2つの段階木 T と S は、同じモデル、すなわち MT = MS を誘導すると統計的に同値であると言われる。 0.79
Let T = (V, E, η) be an X-compatible staged tree. T = (V, E, η) を X 互換のステージ木とする。 0.74
The depth of a vertex v ∈ V equals the number of edges in λ(v). 頂点 v ∈ V の深さは λ(v) の辺の数と等しい。 0.68
The staged tree T is called stratified if every two vertices in the same stage have the same depth. ステージ木 T が成層化と呼ばれるのは、同じステージの2つの頂点が同じ深さを持つときである。
訳抜け防止モード: ステージ化された木 t は 成層 同じ段階にある2つの頂点が同じ深さを持つ場合。
The staged tree in Figure 1 is stratified. 図1の段木は階層化されている。 0.63
Henceforth, and as common in practice, we focus on stratified X-compatible staged trees. それゆえ、実際よく見られるように、階層化されたx互換のステージ木に焦点を合わせます。 0.45
2.1 Causal models based on staged trees 2.1 段階木に基づく因果モデル 0.78
We can define a causal staged tree model as a collection of interventional distributions in the intuitive way: the joint distribution of x in the intervened model is obtained by the product of the parameters in the corresponding root-to-leaf path where we replace parameters corresponding to intervened variables. 因果段階木モデル(causal staged tree model)を、直観的に介入分布の集まりとして定義することができる: 介入モデルにおけるxのジョイント分布は、介入変数に対応するパラメータを置換する対応するルート-リーフ経路におけるパラメータの積によって得られる。
訳抜け防止モード: 我々は因果木モデルを直感的に介入分布の集合として定義することができる The joint distribution of x in the intervened model is obtained by the product of the parameters in the corresponding root - to - leaf path where we replaced parameters corresponding to intervened variables 。
3 3 0.85
Definition 4. A staged tree causal model induced by an X-compatible staged tree T = (V, E, η) is the class of interventional distributions defined, for each parameter vectors θ ∈ ΘT , as follows: 定義4。 x-互換の段階木 t = (v, e, η) によって誘導される段階木因果モデルは、各パラメータベクトル θ ∈ θt に対して次のように定義される介入分布のクラスである。 0.74
Pθ (X = x| do(XI = zI )) = Pθ (X = x| do(XI = zI )) = 0.97
(cid:89) (cid:89) (cid:40) (cid:81) i∈I Pθ (Xi=xi|X[i−1]=x[i−1]) (cid:89) (cid:89) (cid:40) (cid:81) ihtmli pθ (xi=xi|x[i−1]=x[i−1]) 0.73
i∈I Pθ (X=x) ihtmli pθ (x=x) 0.56
θη(x[i],x[i−1]) θη(x[i],x[i−1]) 0.92
δ(xk, zk) i(cid:54)∈I δ(xk, zk) i(cid:54)servleti 0.76
= 0 if xI = zI otherwise = 0 xI = zI でなければ 0.86
(3) In particular under the empty intervention we recover the observational distribution Pθ. (3) 特に、空の介入の下で観測分布 pθ を回復する。 0.75
We say that two staged trees T and S are causally equivalent if they induce the same class of interventional distributions as in Definition 4. 2つの段階木 t と s が因果同値であるとは、それらが定義4と同じ干渉分布のクラスを誘導するときに言う。 0.70
Obviously two causally equivalent staged trees are also statistically equivalent but not viceversa. 明らかに2つの因果同値木も統計的に等価であるが、逆ではない。 0.56
We have that, as for DAGs, intervening on a variable, only affects downstream variables, DAGの場合、変数をインターベンションすることは、下流変数にのみ影響します。 0.70
P (Xi| do(XI = zI )) = P(cid:0)Xi| do(XI = zI∩[i−1])(cid:1) P(Xi| do(XI = zI )) = P(cid:0)Xi| do(XI = zI)[i−1])(cid:1) 0.92
P(cid:0)Xi = xi| do(X[i−1] = z[i−1])(cid:1) = P(cid:0)Xi = xi|X[i−1] = z[i−1] P(cid:0)Xi = xi| do(X[i−1] = z[i−1])(cid:1) = P(cid:0)Xi = xi|X[i−1] = z[i−1] 0.85
(cid:1) . P(cid:0)Xi|X−I∩[i−1] = x−I∩[i−1], XI∩[i−1] = zI∩[i−1] (cid:1) = θη(x[i−1],x[i]). (cid:1)。 P(cid:0)Xi|X-I>[i−1] = x−I>[i−1], XI>[i−1] = zI>[i−1] (cid:1) = θη(x[i−1],x[i])。 0.68
Thus, in particular, (cid:88) ですから特に (cid:88) 0.61
x−I∩[i−1] (4) x−In[i−1] (4) 0.67
= 3 Causal discovery algorithms = 3 因果発見アルゴリズム 0.78
Causal discovery with staged tree models has been discussed by Cowell and Smith [2014] and in Collazo et al [2018]. 段木モデルによる因果発見は、Cowell and Smith (2014) と Collazo et al (2018) で議論されている。 0.70
In particular, Cowell and Smith [2014] used the order search introduced by Silander and Leong [2013] together with an exhaustive search for the best stages structures (the labelling η). 特に、cowell と smith [2014] は silander と leong [2013] によって導入された順序探索を用いて、最良段構造(η のラベル)の徹底的な探索を行った。 0.82
In general, the dynamic programming approach for order search of Silander and Leong [2013] can be coupled with every score that can be decomposed across the depth of the staged tree and with algorithms that estimate the stages structure of a variable given the set of preceding ones. 一般に、silander と leong [2013] の順序探索のための動的プログラミングアプローチは、ステージ化された木の深さで分解できる全てのスコアと、前述した値の集合が与えられた変数のステージ構造を推定するアルゴリズムと結合することができる。 0.88
This method effectively finds the best scoring order, reducing the needed computations compared to the naive procedure that would score all possible ordering of the variables. この方法は最適なスコアの順序を効果的に見つけ、変数の全ての可能な順序をスコアするナイーブな手順と比較して必要な計算量を削減します。 0.66
Collazo et al [2018] correctly reports that causal discovery with staged trees can be effectively carried only if coupled with a method to compute the statistical equivalence class of a model. collazo et al [2018] は、モデルの統計同値クラスを計算する方法と組み合わさった場合にのみ、段階木による因果発見が効果的に実行されることを正しく報告している。 0.72
While an algebraic characterization of equivalence classes [Görgen and Smith, 2018] and an algorithm to compute them have been defined [Görgen et al , 2018], at the moment a practical implementation is not available. 同値類(Görgen and Smith, 2018)の代数的特徴付けとそれらを計算するアルゴリズムが定義されている(Görgen et al , 2018)が、現時点では実践的な実装は利用できない。 0.72
We thus propose to use the dynamic programming algorithm of Silander and Leong [2013] together with two heuristic algorithms for stages structures discovery under a given order: (1) a backward hillclimbing algorithm to minimize BIC score and (2) a k-means clustering of square root probabilities (similar to Silander and Leong [2013]). そこで本研究では,Silander と Leong [2013] の動的プログラミングアルゴリズムと2つのヒューリスティックアルゴリズムを用いて,BIC スコアを最小化するための後方ヒルクライミングアルゴリズム,および (Silander と Leong [2013] に類似した)平方根確率の k-平均クラスタリングアルゴリズムを提案する。 0.80
In both cases we use the BIC score as criteria for selecting the best ordering of the variables [see Görgen et al , 2020, for details]. どちらの場合も、BICスコアを変数の最適な順序付けの基準として使用します(詳細はGörgen et al , 2020 を参照)。 0.59
We implement the dynamic programming order search in the framework of the stagedtrees R package [Carli et al , 2020]. 我々は,Stadtrees Rパッケージのフレームワーク[Carli et al , 2020]で動的プログラミング順序探索を実装した。 0.74
In particular our implementation can be coupled with all the staging recovery algorithms available in the stagedtrees package. 特に当社の実装は,Stagedtreesパッケージで利用可能なステージングリカバリアルゴリズムと組み合わせることができる。 0.67
We refer to the Appendix for a detailed description of the methods used. 使用するメソッドの詳細な説明については、付録を参照。 0.68
4 Context-specific interventional discrepancy 4 文脈特異的介入の相違 0.50
Similarly to the structural interventional distance (SID) for DAGs [Peters and Bühlmann, 2015], which counts the number of wrongly estimated interventional distributions, we can define a context interventional discrepancy, with respect to a reference staged tree (T ). DAGs [Peters and Bühlmann, 2015] の構造的介入距離 (SID) と同様に、基準木 (T) に関して文脈的介入距離を定義できる。
訳抜け防止モード: DAG用構造干渉距離(SID)に準ずる[Peters] 不正に見積もられた介入分布の数を数えているBühlmann, 2015] 参照ステージドツリー(T)に関して、コンテキスト干渉の相違を定義することができる。
Such a discrepancy measures the extent of the errors done in computing context-specific interventions using a different staged tree (S). このような不一致は、異なるステージツリー(S)を用いてコンテキスト固有の介入を計算する際に発生するエラーの程度を測定する。 0.60
4 4 0.85
Definition 5. Let T = (V, E, η) be an X-compatible staged event tree and S = (W, F, ν) an Xπcompatible staged event tree, where π is a permutation of [p]. 定義5。 T = (V, E, η) を X 互換のステージ付きイベントツリーとし、S = (W, F, ν) を Xπ互換のステージ付きイベントツリーとし、π を [p] の置換とする。 0.77
We define the context interventional discrepancy CID(T, S) as, 我々は文脈干渉差CID(T, S)を次のように定義する。 0.67
CID(T, S) = CID(T, S) = 0.85
CIDi(T, S), CIDi(T, S) 0.72
(cid:88) i∈[p] (cid:88) I--[p] 0.68
where CIDi (T, S) is the proportion of contexts x[i−1] ∈ X[i−1] for which the interventional distribution P (Xi| do(X[i−1] = x[i−1])) is wrongly inferred by S with respect to T . ここで CIDi (T, S) は文脈 x[i−1] ∈ X[i−1] の比率であり、介入分布 P(Xi| do(X[i−1] = x[i−1])) は T に関して S によって誤って推測される。 0.83
Precisely, P (Xi| do(X[i−1] = x[i−1])) is wrongly inferred by S with respect to T if there exists P ∈ MT such that 正確には、P(Xi| do(X[i−1] = x[i−1])) は P ∈ MT が存在する場合、T に関して S によって誤って推論される。 0.82
(cid:1) (cid:54)= P (Xi = xi|XI ∈ {yI ∈ XI : ν(yK, w) = ν(xK, u)}), (cid:1) (cid:54) = P (Xi = xi|XI ∈ {yI ∈ XI : ν(yK, w) = ν(xK, u)}) 0.96
P(cid:0)Xi = xi|X[i−1] = x[i−1] P(cid:0)Xi = xi|X[i−1] = x[i−1] 0.78
where J = {j : j > i and π(j) < π(i)}, I = {j : j < i and π(j) < π(i)} and K = I ∪ J. ここで J = {j : j > i と π(j) < π(i)} と I = {j : j < i と π(j) < π(i)} と K = I は J である。 0.88
We detail in the Appendix the algorithm to compute the CID between two staged trees. 二段木間のCIDを計算するアルゴリズムについて,Appendixで詳述する。 0.81
Intuitively, CID measures how much a different staged trees S can be used to compute interventional distributions of the type P (Xi| do(X[i−1] = x[i−1])). 直感的には、CID は P 型の介入分布 (Xi| do(X[i−1] = x[i−1])) を計算するのにどれだけ異なる段階木 S を使えるかを測定する。 0.77
We choose to consider only marginal distributions under interventions on the preceding variables in the true model T , instead of pairwise interventional distributions of the form P (Xi| do(Xj = xj)) as in the definition of SID [Peters and Bühlmann, 2015]. 我々は、sid [peters and bühlmann, 2015]の定義のように、p (xi| do(xj = xj)) 形式のペアリーな介入分布の代わりに、真のモデル t における前の変数に対する介入の下での限界分布のみを考えることを選ぶ。 0.72
This is because our goal is to quantify the effect context-specific interventions. 私たちの目標は、コンテキスト固有の介入の効果を定量化することです。 0.45
However, other measures of discrepancy between staged tree causal models could not be alternatively defined. しかし、立木因果モデル間の相違の他の尺度は、代替的に定義できなかった。 0.63
As an example of the computation of CID(T, S), consider the two staged trees in Figure 1, where the left tree is T and the right one is S. We need to determine which interventional distributions for the left staged tree are wrongly inferred by the right one. CID(T, S) の計算の例として、左木が T で右木が S である図1の2つの段階木を考える。
訳抜け防止モード: cid(t, s ) の計算の例として 左の木がtである図1の2つの段階木を考える 正しいのは「s」です 左段木に対する介入分布を右段木により誤って推定する。
For example, consider the intervention do(X1 = 0, X2 = 1) and the distribution P (X3| do(X1 = 0, X2 = 1)) for P ∈ MT . 例えば、介入 do(X1 = 0, X2 = 1) と P ∈ MT に対する分布 P(X3| do(X1 = 0, X2 = 1)) を考える。 0.89
We have that, 我々はそれを持っている。 0.48
P (X3| do(X1 = 0, X2 = 1)) = P (X3|X1 = 0, X2 = 1), P(X3| do(X1 = 0, X2 = 1)) = P(X3|X1 = 0, X2 = 1) 0.90
and, J = ∅, I = {1}, thus, because v3 and v4 belong to the same stage in T : したがって、v3 と v4 は T : の同じ段階に属するからである。
訳抜け防止モード: そして、J = s である。 I = { 1 } したがって v3 と v4 は T の同じ段階に属するからである。
P (X3|X1 = 0) = P (X3|X1 = 0, X2 = 0) = P (X3|X1 = 0, X2 = 1), P (X3|X1 = 0) = P (X3|X1 = 0, X2 = 0) = P (X3|X1 = 0, X2 = 1) 0.82
and P (X3| do(X1 = 0, X2 = 1)) is then correctly inferred by S. On the other hand, we have that P (X3| do(X1 = 1, X2 = 1)) is wrongly inferred by S because P (X3,|X1 = 1, X2 = 1) (cid:54)= P (X3|X1 = 1) in general. 一方、P (X3,|X1 = 1, X2 = 1) は一般に P (X3,|X1 = 1, X2 = 1) (cid:54) = P (X3|X1 = 1) であるため、P (X3| do(X1 = 1, X2 = 1)) は S によって誤って推論される。 0.89
To see this, notice that P (X3|X1 = 1) = これを見るには P(X3|X1 = 1) = 0.62
P (X3|X1 = 1, X2 = x2)P (X2 = x2|X1 = 1), P(X3|X1 = 1, X2 = x2)P(X2 = x2|X1 = 1) 0.78
(cid:88) x2=0,1 (cid:88) x2=0,1 0.56
and P (X3,|X1 = 1, X2 = 1) (cid:54)= P (X3|X1 = 1) if, for example, we choose P (X2 = x2|X1 = 1) = 0.5 and P (X3|X1 = 1, X2 = 0) (cid:54)= P (X3|X1 = 1, X2 = 1). そして P (X3,|X1 = 1, X2 = 1) (cid:54) = P (X3|X1 = 1) を、例えば P (X2 = x2|X1 = 1) = 0.5 と P (X3|X1 = 1, X2 = 0) (cid:54) = P (X3|X1 = 1, X2 = 1) を選択する。 0.82
As another example, consider the interventional distribution P (X2| do(X1 = 1)). 別の例として、介入分布 P (X2| do(X1 = 1)) を考える。 0.81
In this case we have I = {1} and J = {3}, and since vertices v1, v2 are in the same stage (and so are {w5, w4} and {w3, w6}), we have that この場合、i = {1} と j = {3} があり、頂点 v1, v2 は同じ段階にある(そして {w5, w4} と {w3, w6} も同様である)ので、それを持つ。 0.87
P (X2|X1 = 1) = P (X2) = P (X2|X1 ∈ {0, 1}), P(X2|X1 = 1) = P(X2) = P(X2|X1 ∈ {0, 1}) 0.87
that is, S correctly infers the interventional distribution P (X2| do(X1 = 1)) for every P ∈ MT . すなわち、S は任意の P ∈ MT に対して介入分布 P (X2| do(X1 = 1)) を正しく推論する。 0.83
Similar to SID, the context-specific intervention discrepancy is not symmetric. SIDと同様に、文脈特異的な介入の相違は対称ではない。 0.60
The following proposition collects some properties of the newly defined measure. 以下の命題は、新しく定義された測度のいくつかの性質を収集する。 0.54
Proposition 1. The following properties hold for CID. 命題1。 以下はCIDの属性である。 0.60
i. CID(T, S) = 0 for every pair of causally equivalent staged trees S, T . CID(T, S) = 0 はすべての因果同値なステージ木 S, T に対して成立する。 0.84
ii. If CID(T, S) = 0 then for every P ∈ M(T ) we have that P (Xi|do(X[i−1] = x[i−1])) is 私は... CID(T, S) = 0 であれば、すべての P ∈ M(T ) に対して P (Xi|do(X[i−1] = x[i−1])) が成り立つ。 0.59
correctly computed in S. Sで正しく計算される。 0.72
iii. If M(T ) ⊆ M(S) and π is the identity, then CID(T, S) = 0. iv. iii M(T) と M(S) と π が恒等式であれば、CID(T, S) = 0. iv となる。 0.68
If MT is the fully independence model then CID(T, S) = 0 for every Xπ-compatible MT が完全独立モデルであれば、すべての Xπ 互換の CID(T, S) = 0 となる。 0.80
staged tree S. 5 S期木。 5 0.69
Figure 2: CID and SID between randomly generated DAGs over 5 binary variables. 図2: 5変数以上のランダムに生成されたDAG間のCIDとSID。 0.68
The proof of the above proposition can be found in the Appendix and follows directly from Definition 5. 上記の命題の証明はAppendixで確認でき、定義5から直接従うことができる。 0.69
As described Collazo et al [2018] and detailed in Varando et al [2021], every DAG model over a categorical random vector can be written as a staged tree with variables ordered as one of the topological orders of the DAG. Collazo et al [2018] を記述し、Varando et al [2021] で詳述したように、分類的確率ベクトル上のすべてのDAGモデルは、DAGの位相的順序の1つとして順序付けられた変数を持つ段階木として書ける。 0.69
We can thus always transform DAGs into statistically equivalent staged trees and compute the CID between the two equivalent staged trees as explained above. したがって、DAGを統計的に等価なステージ木に変換して、2つの等価なステージ木の間のCIDを計算することができる。 0.61
In order to compare CID and SID we perform a simulation study where we sample uniformly DAGs over 5 binary variables and compute their CID and SID. CIDとSIDを比較するために, 5変数以上のDAGを一様にサンプリングし, CIDとSIDを計算したシミュレーション研究を行う。 0.84
The results are reported in the two dimensional density and scatter plot in Figure 2. 結果は、図2の2次元密度と散乱プロットで報告されます。 0.82
We can see that there is a high correlation between the two measures thus highlighting that CID is a sensible measure that could be used not only for non-symmetric models, but also for symmetric ones based on DAGs. この2つの測度の間には高い相関関係があることから、CIDは非対称モデルだけでなく、DAGに基づく対称モデルにも使える合理的な測度であることを強調できる。 0.83
5 Simulation experiments 5 シミュレーション実験 0.80
We perform a simulation study to evaluate the feasibility of the proposed approach and to demonstrate its superiority with respect to the classical DAG algorithms under the assumption that the true model is a staged tree. 本研究は,提案手法の有効性を評価するためのシミュレーション研究を行い,実モデルが実木であるという仮定の下で,従来のDAGアルゴリズムに対してその優位性を示す。 0.76
We simulate data from randomly generated staged trees model with different degrees of complexity: number of stages per variables (k ∈ {2, 3, 4}) and number of possible levels per categorical variable (l ∈ {2, 3, 4}). ランダムに生成されたステージ木モデルから得られたデータを,変数毎のステージ数 (k ∈ {2, 3, 4}) とカテゴリ変数毎のレベル数 (l ∈ {2, 3, 4}) でシミュレートする。
訳抜け防止モード: 複雑度が異なるランダムに生成された段木モデルのデータをシミュレートする : 変数毎のステージ数(k ∈ { 2, 3, 4 }) そして、分類変数 (l ∈ { 2, 3, 4 } ) あたりの可能なレベルの数である。
We consider models with 2, 3, 4 and 5 variables, and sample sizes ranging from 100 to 10000 observations. 2,3,4,5変数のモデルについて検討し,サンプルサイズは100~10000である。 0.66
For each parameters’ combination we perform 100 repetition of the experiment each time randomly shuffling the order of the variables to eliminate any possible bias of the search heuristics. 各パラメータの組み合わせに対して、探索ヒューリスティックスのバイアスを取り除くために変数の順序をランダムにシャッフルするたびに、実験を100回繰り返し実行します。 0.80
We run the staged trees approach described in Section 3 using the backward hill-climbing search (best_bhc) and the k-means heuristic (best_kmeans) with the number of clusters fixed to 2. 我々は,第3節で述べた段階木アプローチを,クラスタ数を2に固定した後方ヒルクライミング探索(best_bhc)とk平均ヒューリスティック(best_kmeans)を用いて行った。 0.73
Our two routines are compared to two classical DAG learning algorithms such as tabu search (tabu) and max-min hill-climbing (mmhc) [Tsamardinos et al , 2006], both implemented in the bnlearn R package [Scutari, 2010]. 我々の2つのルーチンは、bnlearn Rパッケージに実装されたタブサーチ(tabu)とマックスミンヒルクライミング(mmhc)[Tsamardinos et al , 2006]の2つの古典的DAG学習アルゴリズムと比較される。 0.71
Results are displayed in Figure 3, where the average CID and Kendall tau distance between the variable orderings are plotted as a function of the sample size N for the case of 5 variables with maximum 4 levels. 結果が図3に示され、最大4レベルの5変数の場合のサンプルサイズNの関数として、変数順序間の平均CIDとケンダルタウ距離がプロットされる。 0.71
Additional results and computational time of the different algorithms are reported in the Appendix. 異なるアルゴリズムのさらなる結果と計算時間はAppendixに報告されている。 0.84
We can observe that, as expected, methods based on staged trees are able to better recover the causal structure of the true model. 予想通り、ステージ木に基づく手法が真のモデルの因果構造をよりよく回復することができることが観察できる。 0.74
Since the true models are randomly generated staged trees we can expect that algorithms which search for the best DAG are not able to recover the true relationships between the variables. 真のモデルはランダムに生成されたステージ木であるため、最良のdagを探索するアルゴリズムは変数間の真の関係を回復できないと期待できる。 0.71
More specifically, we observe that the method based on the k-means algorithm works very well when the number of stages per variable matches the number of clusters (k = 2), while, with respect to CID, its performance degrades for k = 3, 4. より具体的には、k-meansアルゴリズムに基づく手法は、変数当たりのステージ数とクラスタ数(k = 2)が一致した場合に非常にうまく機能し、一方CIDに関しては、その性能は k = 3, 4 に対して低下する。 0.82
The backward hill-climbing methods, 6 02405101520SIDCID 後方登山法 6 02405101520SIDCID 0.67
Figure 3: Context interventional discrepancy (CID) and Kendall tau distance (KD) between the estimated and true model. 図3: 推定モデルと真のモデルの間のコンテキスト干渉差(CID)とケンドールタウ距離(KD)。 0.79
instead, requires a bigger sample size, but it is able to perform well even when the true model is more complex. 代わりに、より大きなサンプルサイズを必要とするが、真のモデルがより複雑である場合でもうまく機能することができる。 0.78
Additionally, it is interesting to notice that both staged tree approaches are able to recover well the causal order of the variables in all considered scenarios. さらに、両方のステージツリーアプローチが、考慮されたすべてのシナリオにおいて変数の因果順序を十分に回復できることに注目することは興味深い。 0.69
This is especially interesting for the k-means algorithm which performs better than the backward hill-climbing method with respect to the Kendall distance even when it is misspecified (k > 2). これはケンドール距離に対して後方ヒルクライミング法よりも優れた性能を持つ k-means アルゴリズムにとって特に興味深い(k > 2)。 0.67
For completeness, in the Appendix, we report results for a simulation study where the true model is a randomly generated DAG: as expected, in this case DAG methods perform better than the proposed staged trees algorithms. 完全性について、Appendixでは、真のモデルがランダムに生成されたDAGであるシミュレーション研究の結果を報告する。
訳抜け防止モード: 完全性については、Appendixでシミュレーション研究の結果を報告する。 真のモデルはランダムに生成されたDAGです この場合、DAG法は、提案したステージ木アルゴリズムよりも優れた性能を発揮する。
6 Real-world data We next illustrate the use of staged trees to uncover causal relationships using data from the 2014 survey “Aspects on everyday life" collected by ISTAT (the Italian National Institute of Statistics) [ISTAT, 2014]. 6実世界データ 次に,イタリア国立統計研究所 (istat, 2014) が収集した2014年調査 "aspects on everyday life" のデータを用いて,ステージ化された木を用いて因果関係を明らかにする。 0.81
The survey collects information from the Italian population on a variety of aspects of their daily lives. この調査は、イタリアの人々の日常生活の様々な側面に関する情報を集めている。 0.78
For the purpose of this analysis we consider five of the many questions asked in the survey: do you practice sports regularly? この分析のために,調査で質問された多くの質問のうち,5つについて考察する。 0.58
(S = yes/no); do you have friends you can count on? (s = yes/no); 数えられる友達はいますか? 0.64
(F = yes/no); do you believe in people? (f = yes/no); 人を信じますか? 0.72
(B = yes/no); do you feel your neighborhood is degraded (D = yes/no); do you watch TV? (b = yes/no); 近所が劣化していると感じるか(d = yes/no); テレビを見るか? 0.72
(T = yes/no). (T = yes/no) 0.91
Instances with a missing answer were dropped, resulting in 35870 answers to the survey. 回答が不足している例が欠落し、35870の回答が得られた。 0.65
For each of the possible variable orderings (120 in total), a staged tree is learned with a backward hill-climbing algorithm optimizing the BIC score. 各変数順序(合計120)について、BICスコアを最適化する後方丘登頂アルゴリズムを用いてステージ木を学習する。 0.73
In Figure 4 the BIC of the best model for each order is reported. 図4では、各注文に最適なモデルのBICが報告される。 0.76
There are six models having the same BIC and belonging to the same equivalence class. 6つのモデルが同じBICを持ち、同じ同値クラスに属している。 0.80
Therefore in the data there is no information to favour one of these orders over the others. したがって、データにはこれらの命令の1つを他の命令よりも好む情報がない。 0.62
For each BIC-minimizing staged tree, we construct a DAG representation of the tree using the methodology of Varando et al [2021]: an edge between two variables represents the presence of (non-)symmetric dependence and the lack of an edge is interpreted as a symmetric conditional independence statement (as in standard DAG models). 各BIC最小化木に対して、Varando et al[2021]の手法を用いて、木をDAG表現する: 2変数間のエッジは(非)対称依存の存在を表し、エッジの欠如は(標準DAGモデルのように)対称条件独立性ステートメントとして解釈される。 0.73
It can be shown that for all six orders the resulting DAG is complete. 6つの順序すべてにおいて、DAGは完備であることを示すことができる。 0.62
Given these six DAGs we then construct a partial DAG (PDAG) as follows: if in all six DAGs two variables are connected by an edge according to the same direction, the PDAG has that directed edge; otherwise, two variables are joined by an undirected edge. これら6つのDAGが与えられたとき、我々は以下の部分DAG (PDAG) を構築する: もし6つのDAGの2つの変数が同じ方向でエッジで接続されている場合、PDAGは有向エッジを持ち、そうでなければ2つの変数は無向エッジで結合される。 0.70
The resulting PDAG is reported in Figure 5 (left). 結果のPDAGは図5(左)で報告される。 0.64
7 k=2k=3k=4CIDKD10025050010003 00010000100250500100 03000100001002505001 00030001000012345612 3456Nvaluealgorithmb est_kmeansbest_bhcbn _tabubn_mmhc 7 k=3k=4CIDK100250500100030 00100001005001000300 01000010050050010003 0001000012345656Nval uealgorithmbest_kmea nsbest_bhcbn_tabubn_ mmhc 0.44
Figure 4: BICs of the best staged tree for every possible order of the ISTAT dataset. 図4: ISTATデータセットの任意の順序に対して、最高のステージツリーのBIC。 0.77
T T B D B D T T B D B D 0.85
S F S F Figure 5: PDAGs for the ISTAT dataset, constructed from staged trees (left) and from standard DAG algorithms (right). S F S F 図5: ISTATデータセットのPDAGは、ステージツリー(左)と標準DAGアルゴリズム(右)で構成されています。 0.84
From the PDAG in Figure 5 (left) we can deduce that there is a dependence between whether an individual practice sports (S), has friends to count on (F), and believes in others (B), but no causal statements about them can be made. 図5(左)のpdagから、個別の練習スポーツ(s)、友人が(f)を数え、他人を信じているかどうか(b)には依存性があるが、それらについて因果的な主張はできないと推測できる。 0.70
The PDAG includes three edges into the vertex D. Therefore the data supports the hypothesis that S, F and B have a causal effect on whether an individual feels their neighborhood is degraded. PDAGは頂点Dに3つのエッジを含むため、データはS、F、Bが近傍が劣化していると感じているかどうかに因果関係があるという仮説を支持する。 0.64
Similarly, all previous variables have a causal effect on whether an individual watches TV. 同様に、以前の変数はすべて、個人がテレビを見るかどうかに因果効果がある。 0.62
Although the PDAG tells us that such causal effects exist, it does not report the specific form of non-symmetric dependence they entertain. PDAGは、そのような因果効果は存在するが、彼らが楽しむ非対称依存の特定の形態を報告していない。 0.62
In order to understand how the variables causally depend on each other, we can refer to one of the BIC-minimizing staged trees. 変数が相互に因果的にどのように依存するかを理解するために、bicを最小化するステージツリーの1つを参照することができる。
訳抜け防止モード: 変数がどのように相互に因果関係を持つかを理解するために。 BIC - ステージツリーの最小化。
Figure 6 reports the learned staged tree for the order (S,F,B,D,T). 図6は、学習した順のステージ木(S,F,B,D,T)を報告する。 0.81
The staging over the variables D and T (vertices v7 to v30) shows an highly asymmetric dependence structure which could not be represented by a DAG model. 変数 D と T のステージング (頂点 v7 から v30) は、DAG モデルでは表現できない高度に非対称な依存構造を示す。 0.77
For instance, the staging {v7, v11, v13} and {v8, v12, v14} implies that, in the context S = no, F has no causal effect on D. Furthermore, it implies that, in the context F = yes, S has no causal effect on D. The fact that the vertices v15, v16, v19 and v20 are in the same stage implies that, in the context S = yes and B = yes, F and D have no causal effect on T. In words, for individuals that practice sports and believe in others, whether or not they have friends and live in degraded neighborhoods does not affect whether or not they watch television. For instance, the staging {v7, v11, v13} and {v8, v12, v14} implies that, in the context S = no, F has no causal effect on D. Furthermore, it implies that, in the context F = yes, S has no causal effect on D. The fact that the vertices v15, v16, v19 and v20 are in the same stage implies that, in the context S = yes and B = yes, F and D have no causal effect on T. In words, for individuals that practice sports and believe in others, whether or not they have friends and live in degraded neighborhoods does not affect whether or not they watch television. 0.93
Due to space constraints we do not discuss the full causal interpretation of the staged tree in Figure 6, but it is apparent that the flexibility of the staging enables for the intuitive representation of complex non-symmetric causal relationships learned from data. 空間制約のため、図6のステージツリーの完全な因果解釈は議論しないが、ステージ化の柔軟性がデータから学習した複雑な非対称因果関係の直感的な表現を可能にすることは明らかである。 0.79
Figure 5 (right) further reports the PDAG learned using standard DAG learning algorithms implemented in bnlearn [Scutari, 2010]. 図5(右)は、bnlearnで実装された標準DAG学習アルゴリズムを用いて学習したPDAGをさらに報告します [Scutari, 2010]。
訳抜け防止モード: 図5(右) PDAGはbnlearnで実装された標準DAG学習アルゴリズムを用いて学習した[Scutari, 2010 ]。
Since DAGs cannot represent non-symmetric types of dependence, the model embeds conditional independences which are not supported by the data: the BIC of the best staged tree is 169754, whilst the one of the learned DAG is 169789. DAGは非対称型の依存を表現できないため、このモデルはデータによって支えられていない条件付き独立性を埋め込む:最高のステージツリーのBICは169754、学習されたDAGのBICは169789である。 0.78
Furthermore, notice that all the edges of the PDAG on the right are undirected and therefore standard DAG algorithms do not actually find any causal relationship in this dataset. さらに、右側のPDAGのすべてのエッジが無向的であることに気付くため、標準DAGアルゴリズムはこのデータセットに因果関係が見つからない。 0.66
7 Conclusions We introduced and implemented causal discovery algorithms based on staged trees which extend classic DAG models to account for complex, non-symmetric causal relationships. 結論7 そこで我々は,従来のDAGモデルを拡張し,複雑な非対称因果関係を考慮した因果探索アルゴリズムを導入した。 0.69
In order to assess the effectiveness of staged trees in causal reasoning, we defined a new discrepancy that measures the agreement between the interventional distributions of two staged trees. 因果推論における段落木の有効性を評価するため,2つの段落木の介入分布の一致を計測する新たな相違性を定義した。 0.77
Our simulation experiments demonstrate that if the data is simulated from a staged tree model, and therefore embeds nonsymmetric relationships between variables, staged trees outperform DAG models. シミュレーション実験により, 木モデルからデータをシミュレートし, 変数間の非対称関係を埋め込んだ場合, 木はDAGモデルより優れることを示した。 0.83
Our real-world 8 現実世界 8 0.72
F = yes F = F = yes F = 0.85
no F = yes いや F = yes 0.74
v0 yes = S v0 yes = S 0.82
S = n o v1 S = n おお v1 0.80
v2 F = no v3 v2 F = いや v3 0.78
v4 v5 v6 s v4 v5 v6 s 0.80
e y = B B=no E y = B B=no 0.77
s e y = B B=no s E y = B B=no 0.78
s e y = B B=no s E y = B B=no 0.78
s e y = B B=no s E y = B B=no 0.78
v7 v8 v9 v10 v7 v8 v9 v10 0.78
v11 v12 v13 v11 v12 v13 0.78
v14 D = y e s v14 D = y e s 0.82
D=no D = y e s D=no D = y e s 0.72
D=no D = y e s D=no D = y e s 0.72
D=no D = y e s D=no D = y e s 0.72
D=no D = y e s D=no D = y e s 0.72
D=no D = y e s D=no D = y e s 0.72
D=no D = y e s D=no D = y e s 0.72
D=no D = y e s D=no D = y e s 0.72
D=no v15 v16 D=no v15 v16 0.72
v17 v18 v19 v17 v18 v19 0.78
v20 v21 v22 v20 v21 v22 0.78
v23 v24 v25 v23 v24 v25 0.78
v26 v27 v28 v26 v27 v28 0.78
v29 v30 T = yes V29 v30 T =はい 0.78
T = no T = yes T = no T = yes 0.85
T = no T = yes T = no T = yes 0.85
T = no T = yes T = no T = yes 0.85
T = no T = yes T = no T = yes 0.85
T = no T = yes T = no T = yes 0.85
T = no T = yes T = no T = yes 0.85
T = no T = yes T = no T = yes 0.85
T = no T = yes T = no T = yes 0.85
T = no T = yes T = no T = yes 0.85
T = no T = yes T = no T = yes 0.85
T = no T = yes T = no T = yes 0.85
T = no T = yes T = no T = yes 0.85
T = no T = yes T = no T = yes 0.85
T = no T = yes T = no T = yes 0.85
T = no T = yes T = no T = yes 0.85
T = no Figure 6: Staged tree maximizing the BIC for the order (S,F,B,D,T). T = no 図6: BICの順序(S,F,B,D,T)を最大化する段木。 0.79
application further highlights the need for non-symmetric models since staged trees, despite of their complexity, outperform DAGs in terms of penalized model fit. アプリケーションはさらに、ステージ化された木から非対称なモデルの必要性を強調している。
訳抜け防止モード: アプリケーションはさらに非対称モデルの必要性を強調している。 ステージ木はその複雑さにもかかわらず、ペナル化モデル適合の点でDAGよりも優れている。
In general we demonstrated that staged tree models can be a valuable tool for causal discovery and various directions for future work are possible. 一般に,段階樹モデルは因果発見に有用なツールであり,今後の作業への様々な方向性が期待できることを示した。 0.73
As showed in the Appendix due to space constraints, the proposed methods obtain good results also in the bivariate case which usually is impossible to tackle with standard DAGs since the two possible directions belong to the same Markov equivalence class. 空間制約によるアペンディックスで示されるように、提案手法は2つの可能な方向が同じマルコフ同値類に属するため、通常標準DAGに対処できない双変数の場合においても良い結果が得られる。 0.76
We are currently focusing on the derivation of theoretical results about the identifiability of the causal order when non-symmetric relationships between two variables are present. 現在,2変数間の非対称関係が存在する場合,因果関係の同定可能性に関する理論的結果の導出に着目している。 0.78
Additional heuristics to learn the stages structures are currently being developed, and similarly different strategies for learning variable ordering. ステージ構造を学ぶためのさらなるヒューリスティックが現在開発されており、同様に変数順序を学習するための戦略も異なる。 0.71
While the methods described in the present work obtain good results, they are lacking in scalability and new heuristics are needed to tackle a larger number of variables efficiently. 本研究で述べる手法は良好な結果を得たが,スケーラビリティに欠けており,より多くの変数に効率的に取り組むためには新たなヒューリスティックスが必要である。 0.70
Acknowledgments and Disclosure of Funding 資金調達の承認と開示 0.77
Gherardo Varando’s work was partly funded by the European Research Council (ERC) Synergy Grant “Understanding and Modelling the Earth System with Machine Learning (USMILE)” under Grant Agreement No 855187. Gherardo Varandoの研究は、Grant Agreement No 855187の下で、欧州研究評議会(ERC)のSynergy Grant “Understanding and Modelling the Earth System with Machine Learning (USMILE)”によって部分的に資金提供された。 0.80
9 9 0.85
References C. Boutilier, N. Friedman, M. Goldszmidt, and D. Koller. 参照: C. Boutilier、N. Friedman、M. Goldszmidt、D. Koller。 0.80
Context-specific independence in Bayesian networks. ベイズネットワークにおけるコンテキスト固有の独立性。 0.50
In Proceedings of the 12th Conference on Uncertainty in Artificial Intelligence, pages 115–123, 1996. 第12回人工知能の不確実性会議の議事録115-123頁、1996年。 0.65
R. Cai, J. Qiao, K. Zhang, Z. Zhang, and Z. Hao. R. Cai, J. Qiao, K. Zhang, Z. Zhang, Z. Hao 0.96
Causal discovery from discrete data using hidden compact representation. 隠れコンパクト表現を用いた離散データからの因果発見 0.78
Advances in Neural Information Processing Systems, 2018:2666, 2018. Neural Information Processing Systems, 2018:2666, 2018。 0.77
F. Carli, M. Leonelli, E. Riccomagno, and G. Varando. F. Carli、M. Leonelli、E. Riccomagno、G. Varando。 0.88
The R package stagedtrees for structural 構造のためのRパッケージステージツリー 0.77
learning of stratified staged trees. arXiv:2004.06459, 2020. 成層樹の学習です arXiv:2004.06459, 2020 0.59
D. M. Chickering. Optimal structure identification with greedy search. D.M.チッカー。 グリーディ探索による最適構造同定 0.64
Journal of machine learning research, 3(Nov):507–554, 2002. 機械学習の日誌 3(Nov):507–554, 2002。 0.71
R. A. Collazo and J. Q. Smith. R・A・コラゾとJ・Q・スミス。 0.48
A new family of non-local priors for chain event graph model selection. 連鎖イベントグラフモデル選択のための新しい非局所前駆体のファミリー。 0.82
Bayesian Analysis, 11(4):1165–1201, 2016. Bayesian Analysis, 11(4):1165–1201, 2016 0.95
R. A. Collazo, C. Görgen, and J. Q. Smith. R. A. Collazo, C. Görgen, J. Q. Smith 0.90
Chain Event Graphs. チェーンイベントグラフ。 0.74
Chapmann & Hall, 2018. 2018年、チャップマン&ホール。 0.60
R. G. Cowell and J. Q. Smith. R・G・コーウェルとJ・Q・スミス。 0.57
Causal discovery through MAP selection of stratified chain event 成層連鎖イベントのMAP選択による因果発見 0.83
graphs. Electronic Journal of Statistics, 8(1):965–997, 2014. グラフ。 Electronic Journal of Statistics, 8(1):965–997, 2014 0.82
E. Duarte and L. Solus. E. DuarteとL. Solus。 0.85
Algebraic geometry of discrete interventional models. 離散的介入モデルの代数幾何学 0.77
arXiv:2012.03593, arXiv:2012.03593, 0.50
2020. G. Freeman and J. Q. Smith. 2020. G・フリーマンとJ・Q・スミス。 0.72
Bayesian MAP model selection of chain event graphs. 連鎖イベントグラフのベイズMAPモデル選択 0.63
Journal of Multivariate Analysis, 102(7):1152–1165, 2011. 日誌 多変量解析 102(7):1152–1165, 2011 0.62
T. Genewein, T. McGrath, G. Déletang, V. Mikulik, M. Martic, S. Legg, and P. A. Ortega. T. Genewein、T. McGrath、G. Déletang、V. Mikulik、M. Martic、S. Legg、P. A. Ortega。 0.83
Algorithms for causal reasoning in probability trees. アルゴリズム 確率木の因果推論に役立ちます 0.67
arXiv:2010.12237, 2020. arXiv:2010.12237, 2020 0.70
C. Glymour, K. Zhang, and P. Spirtes. C. Glymour、K. Zhang、P. Spirtes。 0.81
Review of causal discovery methods based on graphical グラフィカルに基づく因果発見法の検討 0.69
models. Frontiers in Genetics, 10:524, 2019. モデル。 The Frontiers in Genetics, 10:524, 2019。 0.79
C. Görgen and J. Q. Smith. c. görgenとj. q. smith。 0.65
Equivalence classes of staged trees. ステージ化された木の等価クラス。 0.53
Bernoulli, 24(4A):2676–2692, 2018. Bernoulli, 24(4A):2676–2692, 2018 0.86
C. Görgen, M. Leonelli, and J. Q. Smith. C.Görgen、M.Leonelli、J.Q. Smith。 0.60
A differential approach for staged trees. ステージ木に対する微分的アプローチ 0.52
In European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty, pages 346–355, 2015. European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty, pages 346–355, 2015 0.82
C. Görgen, A. Bigatti, E. Riccomagno, and J. Q. Smith. C.Görgen, A. Bigatti, E. Riccomagno, J. Q. Smith 0.81
Discovery of statistical equivalence classes using computer algebra. 統計的同値類の発見 コンピュータ代数を使います 0.71
International Journal of Approximate Reasoning, 95:167–184, 2018. International Journal of Approximate Reasoning, 95:167–184, 2018 0.87
C. Görgen, M. Leonelli, and O. Marigliano. C.Görgen、M.Leonelli、O.Marigliano。 0.65
The curved exponential family of a staged tree. ステージ化された木の曲がった指数関数的な族。 0.38
arXiv:2010.15515, 2020. arXiv:2010.15515, 2020 0.70
P. Hoyer, D. Janzing, J. M. Mooij, J. Peters, and B. Schölkopf. P. Hoyer, D. Janzing, J. M. Mooij, J. Peters, B. Schölkopf 0.93
Nonlinear causal discovery with additive noise models. 付加雑音モデルによる非線形因果発見 0.77
Advances in Neural Information Processing Systems, 21:689–696, 2008. Neural Information Processing Systems, 21:689-696, 2008 0.79
B. Huang, K. Zhang, Y. Lin, B. Schölkopf, and C. Glymour. B. Huang, K. Zhang, Y. Lin, B. Schölkopf, C. Glymour 0.96
Generalized score functions for causal discovery. 因果発見のための一般スコア関数 0.70
In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1551–1560, 2018. 第24回ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, page 1551–1560, 2018 に参加して 0.86
ISTAT. Multiscopo istat – aspetti della vita quotidiana. ISTAT multiscopo istat - aspetti della vita quotidiana の略。 0.63
UniData - Bicocca Data Archive, Milano. UniData - ビコッカのデータアーカイブ、ミラノ。 0.81
Codice indagine SN147. Codice indagine SN147。 0.91
Versione del file di dati 2.0, 2014. 2014年、バージョン2.0をリリース。 0.71
M. Leonelli. Sensitivity analysis beyond linearity. M.レオネッリ。 線形性を超えた感度解析 0.66
International Journal of Approximate Reasoning, International Journal of Approximate Reasoning (英語) 0.72
113:106–118, 2019. 113:106–118, 2019. 0.65
M. Leonelli and G. Varando. M.レオネッリとG.ヴァランド。 0.56
Structural learning of simple staged trees. 2021. 単純な木の構造学習 2021. 0.72
R. P. Monti, K. Zhang, and A. Hyvärinen. R. P. Monti、K. Zhang、A. Hyvärinen。 0.85
Causal discovery with general non-linear relationships 一般非線形関係による因果発見 0.72
using non-linear ica. 非線形icaを使用する。 0.59
In Uncertainty in Artificial Intelligence, pages 186–195. In Uncertainty in Artificial Intelligence, page 186–195。 0.92
PMLR, 2020. PMLR、2020年。 0.88
J. Pearl. Causality. J・パール。 因果性。 0.48
Cambridge University Press, 2009. 2009年ケンブリッジ大学出版局。 0.71
10 10 0.85
J. Peters and P. Bühlmann. j. petersとp. bühlmann。 0.62
Structural intervention distance for evaluating causal graphs. 因果グラフ評価のための構造的介入距離 0.78
Neural Computation, 27(3):771–799, 2015. 神経 計算, 27(3):771-799, 2015 0.72
J. Peters, D. Janzing, and B. Schölkopf. J. Peters、D. Janzing、B. Schölkopf。 0.92
Identifying cause and effect on discrete data using additive noise models. 付加雑音モデルを用いた離散データに対する原因と効果の同定 0.80
In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics, pages 597–604. 第13回人工知能・統計国際会議の議事録597-604頁。 0.63
JMLR Workshop and Conference Proceedings, 2010. JMLR Workshop and Conference Proceedings, 2010 (英語) 0.84
M Scutari. Learning Bayesian networks with the bnlearn R package. M Scutari bnlearn Rパッケージでベイズネットワークを学習する。 0.70
Journal of Statistical Software, journal of statistical software(英語) 0.70
35(3):1–22, 2010. 35(3):1–22, 2010. 0.88
S. Shimizu, P. O. Hoyer, A. Hyvärinen, A. Kerminen, and M. Jordan. S. Shimizu, P. O. Hoyer, A. Hyvärinen, A. Kerminen, M. Jordan 0.93
A linear non-Gaussian acyclic model for causal discovery. 線形非ガウス環 因果発見のモデル。 0.63
Journal of Machine Learning Research, 7(10), 2006. Journal of Machine Learning Research, 7(10, 2006)。 0.75
T. Silander and T. Y. Leong. t. silanderとt. y. leong。 0.69
A dynamic programming algorithm for learning chain event graphs. 連鎖イベントグラフ学習のための動的プログラミングアルゴリズム 0.73
In Proceedings of the International Conference on Discovery Science, pages 201–216, 2013. 院 International Conference on Discovery Science, page 201–216, 2013 (英語) 0.63
J. Q. Smith and P. E. Anderson. J・Q・スミスとP・E・アンダーソン。 0.52
Conditional independence and chain event graphs. 条件付き独立およびチェーンイベントグラフ。 0.81
Artificial Intelligence, 172(1):42 – 68, 2008. 人工物 インテリジェンス、172(1):42 - 2008年68。 0.68
P. Spirtes, C. N. Glymour, R. Scheines, and D. Heckerman. P. Spirtes、C. N. Glymour、R. Scheines、D. Heckerman。 0.83
Causation, prediction, and search. 因果関係、予測、探索。 0.58
MIT press, 2000. MIT 2000年出版。 0.69
P. Thwaites. P.Thwaites 0.73
Causal identifiability via chain event graphs. 連鎖イベントグラフによる因果同定可能性 0.67
Artificial Intelligence, 195:291–315, 2013. 人工知能、2013年:195:291–315。 0.52
P. Thwaites, J.Q. p. thwaites, j.q. 0.54
Smith, and E. Riccomagno. Smith, and E. Riccomagno 0.79
Causal analysis with chain event graphs. 連鎖イベントグラフを用いた因果解析 0.81
Artificial Intelligence, 174(12-13):889–909, 2010. 人工物 インテリジェンス、174(12-13):889-909, 2010。 0.64
I. Tsamardinos, L. E. Brown, and C. F. Aliferis. I. Tsamardinos、L. E. Brown、C. F. Aliferis。 0.83
The max-min hill-climbing Bayesian network 最高峰登山ベイズネットワーク 0.62
structure learning algorithm. 構造学習アルゴリズム。 0.77
Machine learning, 65(1):31–78, 2006. 機械学習, 65(1):31–78, 2006 0.86
G. Varando, F. Carli, and M. Leonelli. G. Varando、F. Carli、M. Leonelli。 0.90
Staged trees and asymmetry-labeled DAGs. 段木と非対称性のDAG。 0.54
2021. J. Viinikka, A. Hyttinen, J. Pensar, and M. Koivisto. 2021. J. Viinikka、A. Hyttinen、J. Pensar、M. Koivisto。 0.85
Towards scalable Bayesian learning of causal 因果関係のスケーラブルベイズ学習に向けて 0.61
DAGs. In Advances in Neural Information Processing Systems, volume 33, 2020. DAG。 In Advances in Neural Information Processing Systems, Volume 33, 2020 0.75
11 11 0.85
A Structural learning of stratified staged trees 階層化段木の構造学習 0.72
We report here the two algorithms to search the space of X-compatible staged trees available in the stagedtrees R package [Carli et al , 2020]. ここでは、stagedtrees rパッケージ(carli et al , 2020)で利用可能なx互換のステージツリーの空間を探索する2つのアルゴリズムについて報告する。 0.67
Moreover we review the dynamic programming approach to learn the best variable ordering. さらに、最適な変数順序付けを学ぶために、動的プログラミングアプローチをレビューする。 0.69
A.1 Learning the stage structure with a fixed order a.1 一定の順序でステージ構造を学ぶ 0.85
The space of possible X-compatible staged event tree is considerably larger than the space of possible DAGs. X 互換のステージ化イベントツリーの空間は DAG の空間よりもかなり大きい。 0.67
Even if we fix the order of the variables, exploring all possible combinations of stages structure becomes rapidly infeasible [Collazo et al , 2018]. 変数の順序を固定しても、ステージ構造のすべての組み合わせを探索することは急速に不可能になる[Collazo et al , 2018]。 0.72
We thus use two of the possible heuristic searches available in the stagedtrees package [Carli et al , 2020]. そこで我々は,Stagedtreesパッケージ[Carli et al , 2020]で利用可能なヒューリスティック検索を2つ使用した。 0.78
The backward hill-climbing method consist in starting from the saturated model and, for each variable, iteratively try to join stages. 後方斜面クライミング法は飽和モデルから始まり,各変数に対して反復的に段階を組もうとする。 0.71
At each step of the algorithm all possible combination of two stages are tried and the best move is chosen. アルゴリズムの各ステップで、2つのステージの組み合わせが試され、最良の動きが選択される。
訳抜け防止モード: アルゴリズムの各ステップで、2つのステージの可能な組み合わせが試される 最高の行動が選択されます
The BIC score is used as guiding criterion; and since the loglikelihood decomposes across the depth of the tree, the stages search can be performed independently for each stratum. BICスコアは指示基準として使用され、対数線は木の深さにわたって分解されるので、各層に対して独立してステージ探索を行うことができる。 0.70
The use of the k-means clustering of probabilities to learn staged event tree was firstly introduced by Silander and Leong [2013] as a fast alternative to backward hill-climbing algorithms. ステージ化イベントツリーの学習にk-meansクラスタリングを用いることで,まずSilander と Leong [2013] が,後方登頂アルゴリズムの高速な代替手段として導入した。 0.77
The default version implemented in the stagedtrees package perform k-means clustering over the square-root of the probabilities of a given variable given all the possible contexts. stagedtreesパッケージに実装されたデフォルトバージョンは、すべての可能なコンテキストが与えられた変数の確率の平方根上でk平均クラスタリングを実行する。 0.74
Both algorithms operate over the stage structures of each variable Xi independently of the other variable stages. どちらのアルゴリズムも、各変数 Xi のステージ構造を他の変数ステージとは独立に操作する。 0.73
Furthermore, the estimated stages structure of a given variable is independent of the order of the preceding variables and depends only on which variables precede Xi. さらに、与えられた変数の推定段階構造は、前の変数の順序とは独立であり、どの変数が Xi に先行するかにのみ依存する。 0.77
A.2 Learning an optimal variable ordering a.2 最適変数順序付けの学習 0.74
The methods described in the previous section output an Xπ-compatible staged tree for each possible ordering π of the variables. 前節で記述された方法は変数の任意の順序 π に対して Xπ 互換のステージ木を出力する。 0.74
For a small number of variables, it is possible to simply enumerate all possible n! 少数の変数に対して、可能なすべての n を単純に列挙することができる。 0.72
staged trees for all possible orders, and select the best one(s) according to a chosen criterion (e g BIC). 可能なすべての順序に木を配置し、選択された基準(例えばBIC)に従って最適な木を選択する。 0.76
Silander and Leong [2013] proposed a dynamic programming algorithm which still obtains the global optimum, but with a substantial reduction in computational complexity. Silander と Leong [2013] は、まだ大域的な最適化を得られるが、計算複雑性を大幅に減らした動的プログラミングアルゴリズムを提案した。 0.78
The method can be coupled with every algorithm which operates independently on every variable and using as guiding score every function which can be decomposed across the variables of the model. この方法は、各変数に対して独立に動作し、モデルの変数をまたいで分解可能なすべての関数を導くスコアとして使用するアルゴリズムと結合することができる。 0.75
The search algorithm is based on the following assumptions: 探索アルゴリズムは以下の仮定に基づいている。 0.76
1. The estimated stages structures of a variable Xi does not depend on the order of the preceding variables. 1. 変数 Xi の推定段階構造は、前の変数の順序に依存しない。 0.76
For example, the stage structure obtained for variable X3 (by one of the two methods in Section A.1) is the same for the orderings X1, X2, X3 and X2, X1, X3. 例えば、変数 X3 に対して得られるステージ構造(セクション A.1 の2つの方法の1つ)は、順序 X1, X2, X3 と X2, X1, X3 とは同じである。 0.78
2. The estimated stages structure of a variable is independent of the estimated stages structures 2. 変数の推定段階構造は、推定段階構造とは無関係である 0.86
for the remaining variables. 残りの変数に対してです 0.65
3. The selection criterion to be optimized decomposes across the variables. 3. 最適化される選択基準は変数間で分解される。 0.80
We refer to Silander and Leong [2013] and Cowell and Smith [2014] for the specifics of the dynamic programming approach. 動的プログラミングアプローチの詳細については、Silander と Leong [2013] と Cowell と Smith [2014] を参照する。 0.72
B Proof of Proposition 1 If two staged tree T, S are causally equivalent then for every P ∈ MT = MS we have B 命題 1 の証明 2 つの段階木 T, S が因果同値であれば、すべての P ∈ MT = MS が成り立つ。 0.82
P (Xi| do(X[i−1] = x[i−1])) = P (Xi| do(XI = xI )), P(Xi| do(X[i−1] = x[i−1])) = P(Xi| do(XI = xI )) 0.92
thus, P (Xi = xi|X[i−1] = x[i−1]) = P (Xi = xi| do(XI = xI )) だから P(Xi = xi|X[i−1] = x[i−1]) = P(Xi = xi| do(XI = xI )) 0.81
= P (Xi = xi|XI ∈ {yI ∈ XI : ν(yK, w) = ν(xK, u)}) P(Xi = xi|XI ∈ {yI ∈ XI : ν(yK, w) = ν(xK, u)}) 0.86
12 12 0.85
which proves point (i). 点 (i) を証明する。 0.69
Point (ii) follows directly from the definition of CID. 点 (ii) は CID の定義から直接従う。 0.68
To prove point (iii), observe that, since π is the identity both T = (V, E, η) and S = (V, E, ν) are X-compatible staged event trees and thus MT ⊆ MS implies that ν(u, v) = ν(u(cid:48), v(cid:48)) ⇒ η(u, v) = η(u(cid:48), v(cid:48)) (the stage structure of T is coarser than the one of S). 点 (iii) を証明するために、π は T = (V, E, η) と S = (V, E, ν) の両方が X 互換のステージ付きイベントツリーであり、したがって MT > MS は ν(u, v) = ν(u(cid:48), v(cid:48)) > η(u, v) = η(u(cid:48), v(cid:48)) を意味する(T のステージ構造は S よりも粗い)。 0.81
Since P ∈ MT , we have, P (Xi = xi|X[i−1] = x[i−1]) = P (Xi = xi|X[i−1] ∈ {y[i−1] ∈ X[i−1] : ν(y[i−1], w) = ν(x[i−1], u)}). P ∈ MT であるため、P (Xi = xi|X[i−1] = x[i−1]) = P (Xi = xi|X[i−1] ∈ {y[i−1] ∈ X[i−1] : ν(y[i−1], w) = ν(x[i−1], u)} となる。 0.94
Finally, point (iv) follows from points (i) and (iii) by observing that if T is the completely independent model then T is causally equivalent to any completely independent Xπ-compatible staged tree, for any permutation π. 最後に、点 (iv) が点 (i) と (iii) から従うと、t が完全独立なモデルであれば、t は任意の置換 π に対して任意の完全独立な xπ-互換段木と因果同値である。 0.69
C Algorithm for CID CIDのためのCアルゴリズム 0.76
The algorithm to compute the context-specific interventional discrepancy is reported in Algorithm 1. 文脈固有の介入不一致を計算するアルゴリズムをアルゴリズム1に報告する。 0.73
In the pseudo-code for the algorithm we use the following notation, for a staged event tree S = (W, F, ν) we denote with ∼S the equivalence relation over V defined by u ∼S v if and only if ν(E(v)) = ν(E(v)). アルゴリズムの擬符号では、次の記法を用いる: ステージ化されたイベントツリー S = (W, F, ν) に対して、 ν(E(v)) = ν(E(v)) が ν(E(v)) で定義されるときと、u と S で定義される V 上の同値関係を表す。 0.74
Thus the equivalence classes with respect to the above-defined relation are the stages of S. したがって、上記の関係に関する同値類は S の段階である。 0.69
Algorithm 1 Compute context interventional discrepancy Require: T = (V, E, η) an X-compatible staged event tree and S = (W, F, ν) an Xπ-compatible staged event tree. t = (v, e, η) x 互換のステージ付きイベントツリーと s = (w, f, ν) と xπ 互換のステージ付きイベントツリーである。
訳抜け防止モード: アルゴリズム1 文脈干渉の相違を求める : T = (V, V) E, η ) X 互換のステージ付きイベントツリー そして S = ( W, F, ν ) は Xπ-互換のステージ付きイベントツリーである。
Ensure: The CID between T and S. 保証:TとSの間のCID。 0.70
initialize CID = 0 for i = 1 to p do k = π−1(i) I = {j : j < i & π−1(j) < k} J = {i : j > i & π−1(j) < k} A = Xπ([k−1])/ ∼S wrong = ∅ for A ∈ A do 初期化 cid = 0 for i = 1 to p do k = π−1(i) i = {j : j < i & π−1(j) < k} j = {i : j > i & π−1(j) < k} a = xπ([k−1])/ を a ∈ a do とする。 0.90
BA = {x[i−1] ∈ X[i−1] : xI = yI for some y ∈ A} if |η(E(BA))| > 1 then wrong = wrong ∪ BA BA = {x[i−1] ∈ X[i−1] : xI = yI for some y ∈ A} if |η(E(BA))| > 1 then wrong = wrong ~ BA 0.95
end if CID = CID + 終了 if cid = cid + 0.66
|wromg| |X [i−1]| |wromg| |X [i−1]| 0.75
# the position of variable Xi in staged tree S # ステージツリーSにおける変数 Xi の位置 0.83
# the stages of S at depth i # 深さ i における S のステージ 0.80
end for end for We prove now that Algorithm 1 correctly computes the CID. 終止符 終止符 我々はアルゴリズム1がCIDを正しく計算していることを証明する。 0.64
Proposition 2. For each pair of X and Xπ compatible staged event trees, T and S, the output of Algorithm 1 is equal to CID(T, S). 命題2。 x と xπ の対応する各組のステージ付きイベントツリー t と s に対して、アルゴリズム 1 の出力は cid(t, s) に等しい。 0.57
Proof. We need only to prove that the procedure in the first loop effectively identifies wrongly inferred interventional distribution of the type P (Xi| do(X[i−1] = x[i−1])). 証明。 第1ループの手順が、タイプ P(Xi| do(X[i−1] = x[i−1]))の誤った推論された介入分布を効果的に特定することを証明する必要がある。 0.68
That is, at the end of i-th iteration of the first for loop, the variable wrong contains the set of contexts x[i−1] ∈ X[i−1] such that the corresponding interventional distribution for Xi is wrongly inferred by S with respect to T . すなわち、第一のループのi-次反復の最後に、変数の誤りは文脈 x[i−1] ∈ X[i−1] の集合を含み、対応する Xi の介入分布は T に関して S によって誤って推測される。 0.80
If x[i−1] ∈ wrong then, by construction, there exists A ∈ A such that x[i−1] ∈ BA, and [i−1])). x[i−1] ∈ が間違っていれば、構成上、x[i−1] ∈ BA, [i−1]) が成り立つような A ∈ A が存在する。 0.87
Thus, there exists P ∈ MT such that there exists x(cid:48) P (Xi|X[t−1] = x[i−1]) (cid:54)= P (Xi|X[t−1] = x(cid:48) したがって、x(cid:48) P (Xi|X[t−1] = x[i−1]) (cid:54) = P (Xi|X[t−1] = x(cid:48) が存在するような P ∈ MT が存在する。 0.78
[i−1] ∈ BA with η(E(x[i−1])) (cid:54)= η(E(x(cid:48) [i−1] ∈ BA with η(E(x[i−1])) (cid:54)= η(E(x(cid:48)) 0.94
[i−1]) and moreover Viceversa, if x[i−1] (cid:54)∈ wrong, for every P ∈ MT we have that, η(E(BA)) is a singleton and thus, [i−1]) など 逆数、x[i−1] (cid:54)∂ wrong, for every P ∈ MT we have that, η(E(BA)) is a singleton, so。 0.74
P (Xi|X[t−1] = x[i−1]) (cid:54)= P (Xi|Xi ∈ BA). P (Xi|X[t−1] = x[i−1]) (cid:54) = P (Xi|Xi ∈ BA)。 0.83
P (Xi|X[t−1] = x[i−1]) = P (Xi|Xi ∈ BA), P(Xi|X[t−1] = x[i−1]) = P(Xi|Xi ∈ BA) 0.90
for every A ∈ A such that x[i−1] ∈ BA. すべての A ∈ A に対して x[i−1] ∈ BA である。 0.82
And thus S correctly infers P (Xi|X[i−1] = x[i−1]). したがって、S は P(Xi|X[i−1] = x[i−1]) を正しく推論する。 0.66
D Additional simulation results D 追加シミュレーション結果 0.80
For completeness we report here additional simulation results, which for space constraints could not fit in the main paper. 完全性については,本論文では空間制約に適合しない追加のシミュレーション結果について報告する。 0.69
We report the CID and Kendall tau distance between the true model and 我々はCIDとKendall tauの真のモデルとの距離を報告する。 0.61
13 13 0.85
Figure 7: Computational time in seconds for different algorithms. 図7: 異なるアルゴリズムに対する数秒の計算時間。 0.89
the estimated ones. The Kendall tau distance is the computed between the true causal order and the estimated order with the implementation in the PerMallows R package [?]. 推定値だ ケンドールタウ距離 (kendall tau distance) は、真因果順序と推定順序の間の計算であり、パーマロマ r パッケージ [?] に実装されている。 0.53
The full simulations can be replicated following the instructions available at https://github.com/g herardovarando/ context_specific_cau sal_discovery. 完全なシミュレーションはhttps://github.com/g herardovarando/ context_specific_cau sal_discovery.comで公開されている命令に従って複製できる。 0.46
Figure 7 reports the computational times of the algorithms. 図7はアルゴリズムの計算時間を報告します。 0.85
As expected, algorithms for DAGs are faster since the searched model space is much smaller. 予想通り、探索されたモデル空間がはるかに小さいため、DAGのアルゴリズムは高速である。 0.70
The k-means algorithm for staged trees is comparable to those for DAGs in terms of speed and its complexity does not seem to exponentially increase as in the case of the backward hill-climbing. ステージ付き木に対するk-meansアルゴリズムは、速度の点でdagと同等であり、その複雑さは後方のヒルクライミングのように指数関数的に増加するとは思えない。 0.69
In Figure 8 we can see results of simulation where the true model is a randomly generated DAG. 図8では、真のモデルがランダムに生成されたDAGであるシミュレーションの結果を見ることができる。 0.73
As expected the tabu search over DAGs and the Max-Min Hill-Climbing algorithm (mmhc) [Scutari, 2010] obtain better results then the staged trees methods. 予想通り, DAG 上のタブ検索と Max-Min Hill-Climbing アルゴリズム (mmhc) [Scutari, 2010] は, ステージ木法でより良い結果を得た。 0.77
Still, we noticed in the paper that the causal order is retrieved poorly by DAGs algorithms when the true model is a staged event tree. しかし,本論文では,真のモデルがイベントツリーである場合,DAGアルゴリズムによって因果順序が不適切に検索されることに気付いた。 0.68
We can thus hypothesise that the asymmetric conditional independence statements present in a random staged event tree model are helpful to retrieve the causal structure. したがって、ランダムなステージ付きイベントツリーモデルに存在する非対称条件付き独立ステートメントは因果構造を取得するのに役立つと仮定することができる。 0.73
Interestingly, when the true model is a randomly generated staged event tree, even in the bivariate case, we observe that the proposed staged trees methods outperform classical DAG methods 9. 興味深いことに、実モデルがランダムに生成されたイベントツリーである場合、二変量の場合においても、提案手法が古典DAG法9より優れていることが観察された。 0.59
This suggests that the asymmetrical stages structure in a staged event tree can be sufficient to have identifiability of the causal order. これは、ステージ化イベントツリーの非対称ステージ構造が因果順序の識別性を持つのに十分であることを示唆している。 0.69
In the next section we report a concrete example where such identifiability is explicit. 次の節では、このような識別性が明確である具体的な例を報告する。 0.54
E An example of identifiability of the causal order E 因果順序の識別可能性の例 0.69
As an instructive example we report here a bivariate staged tree model compatible with (X1, X2) where the causal order can be identified by choosing the simpler model. インストラクティブな例として、より単純なモデルを選択することで因果順序を識別できる (x1, x2) と互換性のある2変数のステージ付き木モデルについて報告する。 0.67
Consider the two staged tree depicted in Figure 10. 図10に示す2つのステージツリーを考えてみましょう。 0.62
Let T be the staged tree on the right and S the one on the left. T を右の段木とし、S を左の段木とする。 0.66
14 l=2l=3l=4k=2k=3k=43453453451e−021e−011e+001e+011e+021e−021e−011e+001e+011e+021e−021e−011e+001e+011e+02ptime (s)algorithmbest_kme ansbest_bhcbn_tabubn _mmhc 14 l=2l=3k=2k=4345451e−021e−011e+001e+011e+021e−021e−021e−011e+011e+021e−021e−021e−011e+001e+011e+02ptime (s)algorithmbest_kme ansbest_bhcbn_tabubn _mmhc 0.47
Figure 8: Simulation results for data sampled from randomly generated DAGs (p = 4). 図8: ランダムに生成されたDAGからサンプリングされたデータのシミュレーション結果(p = 4)。 0.76
It is easy to see that if the data are generated from a joint probability distribution P ∈ MT , S is the only (X1, X2)-compatible staged tree such that P ∈ MS. データが合同確率分布 P ∈ MT から生成されると、S が P ∈ MS であるような唯一の (X1, X2) 互換のステージ木であることが容易に分かる。 0.80
Indeed, since MS is the saturated model we have that MS is equal to the entire probability simplex. 実際、MS は飽和モデルであるため、MS は確率単純度全体と等しい。 0.59
But we can see that MT (cid:40) MS, since P (X1|X2 = 2) = P (X1|X2 = 3) in MT , and thus the causal order is here identified by choosing the simplest model which describes the data generating process. しかし、mt (cid:40) ms は、mt において p (x1|x2 = 2) = p (x1|x2 = 3) であるため、データ生成過程を記述する最も単純なモデルを選択することで因果順序が特定できる。 0.74
Even if this is a very simple example, it is instructive to see that non-symmetrical conditional independence statements can be leveraged by staged event trees to discover causal structure in categorical data. たとえこれが非常に単純な例であっても、非対称条件付き独立性ステートメントを段階的イベントツリーで活用して、カテゴリデータ内の因果構造を発見することができることは指示的である。 0.70
15 CIDKD100250500100030 00100001. . 3.5Navgalgorithmbest _kmeansbest_bhcbn_ta bubn_mmhc 15 CIDKD100250500100010 0001. 53.53.5Navgalgorithm best_kmeansbest_bhcb n_tabubn_mmhc 0.47
Figure 9: Simualtion results for the bivariate case (p = 2). 図9: 2変数の場合(p = 2)のシミュアル結果。 0.67
Data sampled from randomly generated staged event trees (with k stages per variable). ランダムに生成されたイベントツリーからサンプリングされたデータ(変数毎にkステージ)。 0.64
= 0 1 X v0 = 0 1 X v0 0.83
X 1 = 1 v1 X 1 = 1 v1 0.84
v2 X 2 X2 = 2 v2 X 2 X2 = 2 0.89
X 2 X2 = 2 X 2 X2 = 2 0.99
1 1 = = X 2= 1 1 = = X 2= 0.84
3 w0 1 = 2 3 w0 1 = 2 0.84
X X2 = 2 X X X2 = 2 X 0.92
2 = 3 w1 w2 2 = 3 w1 w2 0.82
w3 X 1 = 0 w3 X 1 = 0 0.82
X1 = 1 X 1 = 0 X1 = 1 X1 = 0 0.95
X1 = 1 X 1 = 0 X1 = 1 X1 = 0 0.95
X1 = 1 Figure 10: An example of an (X1, X2)-compatible (left) and an (X2, X1)-compatible (right) staged trees. X1 = 1 図10:(X1, X2)互換の(左)および(X2, X1)互換の(右)ステージツリーの例。 0.86
X 2= 3 16 k=2k=3k=4CIDKD10025050010003 00010025050010003000 100250500100030000.2 rithmbest_kmeansbest _bhcbn_tabubn_mmhc X 2= 3 16 k=2k=3k=4CIDKD10025050010001 00050050050050010003 0000. 5Nalgorithmbest_kmea nsbest_bhcbn_tabubn_ mmhc 0.68

翻訳にはFugu-Machine Translatorを利用しています。