PCアルゴリズムの2次の独立性検定を実施しない理由について

[sabi2345]

第1版p175の「2次の独立性検定を実施するには、条件付き部分の組み合わせが２つ以上必要であり、N次の独立性検定を実施する際には条件付き部分の組合わせがN個以上必要です。」の記載は
２次の場合、一つの検定する変数の組み合わせについて例えばもう一つWという変数が存在し、
CI(Y,x|Z,Y3), CI(Y,x|Z,W), CI(Y,x |Y3,W)として２個以上条件部分が必要との意味であっているでしょうか。

ただ、それでもなぜそのように判断するのか、理由が不明だったため、７章の参考図書[8]Causation_Prediction_and_SearchのPCアルゴリズム部分を参照しました。正しく理解できている自信はないのですが、「ある変数と隣接する変数数 - 1」がn未満になるまで繰り返すように意味しているように思え、2次の場合も独立性検定が必要ではないかと考えました。

上述より、内容補足いただけるとありがたいと思い、登録させていただきました。

B.)
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.

[YutaroOgawa]

@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%の自信を持てていない状況ではあります。）

大変申し訳ございませんが、 以上が解説となります。

どうぞよろしくお願い致します。

[sabi2345]

丁寧なご説明、ご返信ありがとうございます。

念の為確認させてください。

元論文の

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」との理解で問題ないでしょうか。

[YutaroOgawa]

@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次も検定する必要があり、書籍の結果が変わらないようにするために、修正と判明しました。

非常に重要なご指摘をありがとうございます！

[YutaroOgawa]

ここで元の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次の独立性検定を実施するべき https://github.com/YutaroOgawa/causal_book/issues/10

に記載いたしました。

ここまで、非常に重要なご指摘を賜り、誠にありがとうございます。 誤った説明で混乱と時間の浪費を与えてしまい、誠に申し訳ございません。 今後とも宜しくいただければ幸いです。

本Issue、誠にありがとうございました。

[sabi2345]

YutaroOgawaさま

早急にご対応いただきありがとうございました。 内容を深く理解することができました。 こちらこそ、感謝申し上げます。

こちらで一度closedさせていただきましたが、必要に応じてステータス変更ください

[YutaroOgawa]

@sabi2345 さま

早速のご対応、ご確認をありがとうございます。

IssueのステータスはOpenでもCloseでもとくに問題ありません。

読者の皆さまがIssueを一覧し気になるものを見つけやすいという意味では 解決したIssueもOpenのままが良いのかな？と、個人的には思っています、

ですが、まあ、このあたりはIssueを立てた方のご判断にいつもお任せしています。

ですので、いつでもステータス変更を実施くださいませ。

どうぞよろしくお願い致します。