Comments (6)
丁寧なご説明、ご返信ありがとうございます。
念の為確認させてください。
元論文の
Adjacencies(C,A) be the set of vertices adjacent to A in directed acyclic graph C
という定義から「Adjacencies(C,A)はグラフCにおいて、Aと隣接している頂点集合」という意味なのかなと考えておりました。
そのため、Adjacencies(C,X)\{Y} = 「グラフCにおいてXと隣接している頂点集合からYを除いた集合」という意味にとっておりました。
Adjacencies(C,X)\{Y} は「調整する条件C」との理解で問題ないでしょうか。
from causal_book.
@sabi2345 さま
非常に重要な質問をありがとうございます。
多くの読者の方も気になる点だと思いました。
こちら、非常にややこしく、私の説明も不足気味で困惑を招き、誠に申し訳ございません。
引用いただいているPCアルゴリズム論文の手続きの最後の部分、
until for each ordered pair of adjacent vertices X, Y, Adjacencies(C,X){Y} is of
cardinality less than n.
日本語では
”隣接する頂点XとYについて、調整する条件Cがn未満になるまで”、
PCアルゴリズムはnを増やしながら実施します。
と記載されています。
そして手続き途中の文面、
until all ordered pairs of adjacent variables X and Y such that
Adjacencies(C,X){Y} has cardinality greater than or equal to n
がポイントです。
”nを増やしていく過程で、隣接する頂点XとYについて、調整する条件C(Adjacencies(C,X){Y})がn未満になるまで続ける”
という意味になります。
今本書のp.175の2次の独立性検定では、
CI(Y, x | Z, Y3)、CI(Y, Z | x, Y3)、CI(Y, Y3 | x, Z)の3つの条件付き確率が計算できる状態です。
ですが、特定の頂点ペアに対しては、どれも、調整する条件は1つしかありません。
2次なので2つ以上欲しいところです。
そのため、
引用途中の、
until all ordered pairs of adjacent variables X and Y such that
Adjacencies(C,X){Y} has cardinality greater than or equal to n
を満たさず、PCアルゴリズムがここで終了しています。
(PCアルゴリズムの2次以降について、
この調整する可能条件数の制限概念を丁寧に扱っている書籍や論文が少なく、
実は私も完全に100%の自信を持てていない状況ではあります。)
大変申し訳ございませんが、
以上が解説となります。
どうぞよろしくお願い致します。
from causal_book.
@sabi2345 さま
早速のご返信をありがとうございます。
[1]
Adjacencies(C,X)\{Y} = 「グラフCにおいてXと隣接している頂点集合からYを除いた集合」という意味にとっておりました。
私が、
書籍「ベイジアンネットワーク」槙野, コロナ社,
https://www.amazon.co.jp/dp/4339061034
を見て、PCアルゴリズムの記載が若干違っているため混乱していました。
(上記書籍ではCはCIテストの条件部と記載され、PCアルゴリズムの表現も元と異なる)
ですが、
Adjacencies(C,X)\{Y} = 「グラフCにおいてXと隣接している頂点集合からYを除いた集合」
で良いと思います。
[2]
Adjacencies(C,X)\{Y} は「調整する条件C」との理解で問題ないでしょうか。
私が、Cは条件部と捉えていたのですが、Cは対象としているグラフととらえ、
上記[1] の
Adjacencies(C,X)\{Y} = 「グラフCにおいてXと隣接している頂点集合からYを除いた集合」
で良いと思います。
また、この後、投稿を続けますが、 @sabi2345 さまのおっしゃる通りで、2次も検定する必要があり、書籍の結果が変わらないようにするために、修正と判明しました。
非常に重要なご指摘をありがとうございます!
from causal_book.
ここで元のPCアルゴリズムの整理し直します。
n = 0.
repeat
repeat
select an ordered pair of variables X and Y that are adjacent in C such that
Adjacencies(C,X)\{Y} has cardinality greater than or equal to n, and a subset S
of Adjacencies(C,X)\{Y} of cardinality n, and if X and Y are d-separated given S
delete edge X - Y from C and record S in Sepset(X,Y) and Sepset(Y,X);
Let Adjacencies(C, A) be the set of vertices adjacent to A in directed acyclic graph C.
(In the algorithm, the graph C is continually updated, so Adjacencies(C, A) is constantly
changing as the algorithm progresses.)
until all ordered pairs of adjacent variables X and Y such that
Adjacencies(C,X)\{Y} has cardinality greater than or equal to n and all subsets S of
Adjacencies(C,X)\{Y} of cardinality n have been tested for d-separation;
n = n + 1;
until for each ordered pair of adjacent vertices X, Y, Adjacencies(C,X)\{Y} is of
cardinality less than n.
日本語
========
n=0からはじめます。
繰り返し1
繰り返し2
グラフCのなかで隣接している変数XとYのペアを選択します、
ただし、「グラフCにおいてXと隣接している頂点集合からYを除いた集合」(Adjacencies(C,X)\{Y})で
n以上のcardinality:濃度、を持つものを選びます(※cardinality:濃度≒「集合」が持ってる「要素」の個数)。
そして「グラフCにおいてXと隣接している頂点集合からYを除いた集合」の部分集合Sを取り出し
部分集合Sで条件付けされた状態でXとYがd分離であれば、XとYをつなぐ辺を消去します。
そして、SをSepset(X,Y) and Sepset(Y,X)に記録します(※Sepset:Separating set)。
ここで、Adjacencies(C, A) は「グラフC内で、Aに隣接する頂点の集合」です。
このアルゴリズムではCは常に変化するので、Adjacencies(C, A)も変化します。
繰り返し2の繰り返し条件
頂点XとYについて、Adjacencies(C,X)\{Y} がn以上、そしてその部分集合Sもn以上であれば、d分離をテストします。
その後、nを1つ大きくします。
繰り返し1の繰り返し条件
頂点X,Yの隣接集合の要素数がn以下になるまでnを増やします。
========
私が、このsubset S(部分集合S)の捉え方を誤っていました。
部分集合なので1つ要素を減らすべきだと早とちりしました。
正しくは、元の集合もまたその集合の部分集合です。
Le, Thuc, et al. "A fast PC algorithm for high dimensional causal discovery with multi-core PCs." IEEE/ACM transactions on computational biology and bioinformatics (2016).
https://arxiv.org/pdf/1502.02454.pdf
の、5ページ目の左上
Algorithm 1: Step 1 of the original-PC algorithm: learning the skeleton
のPCアルゴリズムの解説や、
4ページ目右下のZ(サブセット)の説明も参考になります。
結論として、 @sabi2345 さまのおっしゃる通り、2次の独立性検定を実施しないのは不自然(というか誤り)であり、
実施すべきです。
それに伴う変更について、
Issueの【第7章5節】PCアルゴリズムの2次の独立性検定を実施するべき
#10
に記載いたしました。
ここまで、非常に重要なご指摘を賜り、誠にありがとうございます。
誤った説明で混乱と時間の浪費を与えてしまい、誠に申し訳ございません。
今後とも宜しくいただければ幸いです。
本Issue、誠にありがとうございました。
from causal_book.
YutaroOgawaさま
早急にご対応いただきありがとうございました。
内容を深く理解することができました。
こちらこそ、感謝申し上げます。
こちらで一度closedさせていただきましたが、必要に応じてステータス変更ください
from causal_book.
@sabi2345 さま
早速のご対応、ご確認をありがとうございます。
IssueのステータスはOpenでもCloseでもとくに問題ありません。
読者の皆さまがIssueを一覧し気になるものを見つけやすいという意味では
解決したIssueもOpenのままが良いのかな?と、個人的には思っています、
ですが、まあ、このあたりはIssueを立てた方のご判断にいつもお任せしています。
ですので、いつでもステータス変更を実施くださいませ。
どうぞよろしくお願い致します。
from causal_book.
Related Issues (20)
- 【第7章5節P.175】下から10行目は、Y2ではなく、Y3
- P82での数式についての質問です。【訂正範囲:p. 82 4行目~18行目の数式展開】 HOT 2
- P84についての質問です。【訂正:0.1、-1、-4 にほぼ近い係数が求まっており、】 HOT 4
- P84【訂正:0.1、-1、-4 にほぼ近い係数が求まっており、】
- P82【訂正範囲:p. 82 4行目~18行目の数式展開】
- p133のLinGAMの導出部分について質問させてください。 HOT 2
- p144のパラメータ数について質問させてください。 HOT 5
- P150,151のBICについて質問させてください。【訂正:BICの良さの大小が逆になっています】 HOT 3
- p76の式に出てくる数値について HOT 3
- 【第4刷が発行されます】ここ以下のIssueはほぼ修正しております
- 【第3刷の第4章・第1節】回帰分析について HOT 2
- 【質問】因果推論の際に中間変数を入れるべきではないということについての質問 HOT 7
- 第6章LiNGAM 6_3_lingamコードについて HOT 3
- 【第四刷 修正提案】p.113のプログラムコードとp.114のグラフについて HOT 3
- 【第5章 P.108】Z==0を介入無集団、Z==1を介入有と考えることについて HOT 1
- 【第4章2節】p. 84 1行目の誤植(正しい答えである、0.1、-1、-4 にほぼ近い係数が求まっており、)
- 【オリエンテーションルールによる方向づけその1】および【独立性検定の手順】 HOT 3
- 【質問】p53の確率を期待値表記にする妥当性について HOT 2
- 誤植でしょうか?初版第1刷P.52について
- [第5刷]第五章 図5.1.1について(pp.95)
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from causal_book.