Approaches to bivariate causal discovery based on the minimum description length (MDL) principle approximate the (uncomputable) Kolmogorov complexity of the models in each causal direction, selecting the one with the lower total complexity. The premise is that nature's mechanisms are simpler in their true causal order. Inherently, the description length (complexity) in each direction includes the description of the cause variable and that of the causal mechanism. In this work, we argue that current state-of-the-art MDL-based methods do not correctly address the problem of estimating the description length of the cause variable, effectively leaving the decision to the description length of the causal mechanism. Based on rate-distortion theory, we propose a new way to measure the description length of the cause, corresponding to the minimum rate required to achieve a distortion level representative of the underlying distribution. This distortion level is deduced using rules from histogram-based density estimation, while the rate is computed using the related concept of information dimension, based on an asymptotic approximation. Combining it with a traditional approach for the causal mechanism, we introduce a new bivariate causal discovery method, termed rate-distortion MDL (RDMDL). We show experimentally that RDMDL achieves competitive performance on the Tübingen dataset. All the code and experiments are publicly available at github.com/tiagobrogueira/Causal-Discovery-In-Exchangeable-Data.
Figures & tables
L(X)−L(Y)
full method
bQCD
54.7
71.1
COMIC
55.6
76.0
GPI
49.0
68.1
SLOPE
53.7
80.5
Table 1: AUROC (in %) on the Tübingen dataset, achieved by (L(X)−L(Y)) alone as a prediction score versus the full method, for bQCD, COMIC, GPI, and SLOPE.
Method
AUROC (%)
Accuracy (%)
AUDRC (%)
ANM
61.9
60.4
62.9
bQCD
71.1
69.6
70.1
CAM
46.6
52.3
43.1
CDCI
60.7
61.5
55.0
CDS
59.0
60.5
57.8
CGNN
61.6
61.5
69.6
Table 2: Performance of the 4 RDMDL versions and 17 other methods on the Tübingen benchmarks. The best results in each column are in bold; the second best is underlined.
Method
CE - Cha
CE - Gauss
CE - Multi
CE - Net
AN
AN - s
LS
LS - s
MN - U
SIM
SIM - c
SIM - G
SIM - ln
RDMDL-FD
62.7 ( 60.7 )
64.7 (58.7)
97.0 ( 89.3 )
75.2 (68.3)
51.2 (49.0)
43.3 (45.0)
49.0 (47.0)
13.4 (17.0)
0.9 (6.0)
53.6 (47.0)
59.6 (57.0)
59.4 (55.0)
87.2 (77.0)
RDMDL-R
64.2 (60.3)
64.5 (59.0)
96.5 (88.3)
81.1 (72.0)
84.5 (74.0)
52.3 (51.0)
77.0 (68.0)
6.9 (13.0)
1.3 (7.0)
61.9 (56.0)
66.9 (65.0)
66.2 (57.0)
91.4 (79.0)
RDMDL-Sc
63.7 (59.3)
69.4 (62.7)
96.9 ( 89.0 )
77.5 (69.3)
58.6 (52.0)
34.7 (34.0)
53.5 (51.0)
4.8 (12.0)
0.8 (4.0)
58.1 (53.0)
63.9 (62.0)
60.1 (54.0)
88.6 (78.0)
RDMDL-St
64.0 (60.3)
65.1 (59.0)
96.5 (88.3)
81.7 (72.3)
86.8 (76.0)
53.7 (51.0)
78.5 (69.0)
5.8 (13.0)
1.4 (7.0)
62.8 (56.0)
67.6 (66.0)
66.4 (58.0)
91.6 (79.0)
bQCD
56.3 (55.0)
48.1 (54.3)
53.2 (49.0)
90.7 ( 81.3 )
100.0 ( 100.0 )
90.5 ( 83.0 )
100.0 ( 100.0 )
100.0 ( 100.0 )
100.0 ( 100.0 )
69.9 ( 68.0 )
80.8 ( 77.0 )
71.7 (67.0)
91.9 ( 87.0 )
GPI
64.9 ( 62.4 )
89.1 ( 83.2 )
72.2 (71.5)
88.8 ( 81.3 )
79.2 (85.5)
62.4 (62.5)
72.8 (83.6)
73.8 (70.9)
85.7 (80.7)
88.3 ( 83.7 )
92.4 ( 85.6 )
90.1 ( 80.4 )
92.8 (84.5)
Table 3: Results of the four versions of RDMDL in three collections of synthetic datasets: CE, ANLSMN, and SIM, evaluated using AUROC and accuracy (in parentheses in each cell).The best results for each dataset are in bold and the second-best are underlined.
Figure 1: AUDRC curves in the Tübingen benchmark. Left: RDMDL (green) compared to all other implemented methods (shades of red); right: analysed MDL causal discovery methods.
Predictors-FD
L(Y∣X)
Marginals
correct
incorrect
L(X)
correct
\textcolor green38.2 / \textcolor green16.2
\textcolor green15.8 / \textcolor red4.8
\textcolor green70.2 / \textcolor red4.8
incorrect
\textcolor red8.1 / \textcolor green1.7
\textcolor red8.3 / \textcolor red6.9
\textcolor green1.7 / \textcolor red23.3
Marginals
\textcolor green56.1 / \textcolor red8.1
\textcolor green15.8 / \textcolor red20.0
Table 4: Confusion matrix: in each cell, on the left, the result when taken by (L(X)−L(Y)) and on the right when (L(Y∣X)−L(X∣Y)) dominates. Green indicates a correct decision and red an incorrect decision. Top-left table: RDMDL-FD; top-right table: RDMDL-R; bottom-left table: RDMDL-Sc; bottom-right table: RDMDL-St.
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
LX→Y=LX(X)+LY∣X(X,Y)
Appendix
Algorithm 1 RDMDL
dimX←dim(X).
Appendix
Algorithm 2 LX (from RDMDL)
Hi≈alogϵi+b
Appendix
Algorithm 3 Information Dimension dim(X) (from RDMDL)
LY∣X←min(Lp,Li,Le)
Appendix
Algorithm 5 LY∣X (from RDMDL)
rf,θf←LSf(X,Y),
Appendix
Algorithm 6 fit (from RDMDL)
Method
Source
AN
AN-s
CE-Cha
CE-Multi
CE-Net
LS
LS-s
MN-U
Multi
Net
SIM
SIM-G
SIM-c
SIM-ln
Tübingen
COMIC
COMIC
100
100
43
79
78
100
100
100
57
78
54
89
67
EMD
bQCD
36
33
60
42
83
45
58
40
52
68
GPLVM
GPLVM, COMIC
100
100
100
100
100
83
92
79
90
GRCI
LOCI
100
94
70
98
87
88
77
85
77
70
77
77
82
LiNGAM
bQCD
0
4
7
3
0
42
25
53
31
42
PNL
bQCD
96
63
91
44
66
70
64
65
61
73
Appendix
Table 5: Accuracy (in %) obtained by the different unimplemented methods for all evaluated datasets.
Method
Source
AN
AN-s
CE-Cha
CE-Gauss
CE-Multi
CE-Net
LS
LS-s
MN-U
SIM
SIM-G
SIM-c
SIM-ln
Tübingen
COMIC
COMIC
100
100
47
91
84
100
100
100
58
85
59
95
75
EMD
bQCD
43
GPLVM
GPLVM, COMIC
100
100
82
89
98
99
100
100
100
92
99
91
97
78
LiNGAM
bQCD
30
PNL
bQCD
70
CURE
bQCD
64
Appendix
Table 6: AUROC (in %) obtained by the different unimplemented methods for all evaluated datasets.
Method
Source
AN
AN-s
CE-Cha
LS
LS-s
MN-U
Multi
Net
SIM
SIM-G
SIM-c
SIM-ln
Tübingen
GRCI
LOCI
100
100
71
100
95
97
74
96
90
88
92
92
73
Appendix
Table 7: AUDRC (in %) obtained by the different unimplemented methods for all evaluated datasets.
Method
CE-Cha
CE-Gauss
CE-Multi
CE-Net
AN
AN-s
LS
LS-s
MN-U
SIM
SIM-c
SIM-G
SIM-ln
RDMDL-FD
62.7 (60.7)
64.7 (58.7)
97.0 ( 89.3 )
75.2 (68.3)
51.2 (49.0)
43.3 (45.0)
49.0 (47.0)
13.4 (17.0)
0.9 (6.0)
53.6 (47.0)
59.6 (57.0)
59.4 (55.0)
87.2 (77.0)
RDMDL-R
64.2 (60.3)
64.5 (59.0)
96.5 (88.3)
81.1 (72.0)
84.5 (74.0)
52.3 (51.0)
77.0 (68.0)
6.9 (13.0)
1.3 (7.0)
61.9 (56.0)
66.9 (65.0)
66.2 (57.0)
91.4 (79.0)
RDMDL-Sc
63.7 (59.3)
69.4 (62.7)
96.9 (89.0)
77.5 (69.3)
58.6 (52.0)
34.7 (34.0)
53.5 (51.0)
4.8 (12.0)
0.8 (4.0)
58.1 (53.0)
63.9 (62.0)
60.1 (54.0)
88.6 (78.0)
RDMDL-St
64.0 (60.3)
65.1 (59.0)
96.5 (88.3)
81.7 (72.3)
86.8 (76.0)
53.7 (51.0)
78.5 (69.0)
5.8 (13.0)
1.4 (7.0)
62.8 (56.0)
67.6 (66.0)
66.4 (58.0)
91.6 (79.0)
ANM
34.3 (40.0)
43.3 (45.3)
48.7 (51.0)
56.3 (59.0)
52.8 (51.2)
52.9 (55.8)
59.4 (57.8)
52.3 (57.8)
63.5 (62.2)
49.1 (46.3)
47.8 (43.6)
27.5 (37.2)
60.7 (56.2)
bQCD
56.3 (55.0)
48.1 (54.3)
53.2 (49.0)
90.7 ( 81.3 )
100.0 ( 100.0 )
90.5 (83.0)
100.0 ( 100.0 )
100.0 ( 100.0 )
100.0 ( 100.0 )
69.9 (68.0)
80.8 ( 77.0 )
71.7 (67.0)
91.9 ( 87.0 )
Appendix
Table 8: Performance of the sixteen implemented causal discovery methods, alongside the four versions of RDMDL, in three sets of synthetic benchmarks, evaluated using AUROC (accuracy). The value in bold corresponds to the best result in each column, and those underlined to the second best.
Graduate School of Information Science and Technology, The University of Tokyo, Tokyo, Japan · Graduate School of Arts and Sciences, The University of Tokyo, Tokyo, Japan