Finding Statistically Significant Interactions
between Continuous Features

Mahito Sugiyama (National Institute of Informatics), Karsten Borgwardt (ETH Zürich)
The 28th International Joint Conference on Artificial Intelligence (IJCAI-19), August 10–16, 2019

Tarone’s Testability Trick

Our Proposal: C-Tarone• Find all feature interactions that are significantly associated withclass labels from multivariate data with controlling the FWER
– Existing methods (significant pattern mining) work
only for binary (or discrete) data [1]xInput:F1ID1ID2ID3ID4F2yF3F4F5... Class–0.96 –3.03 3.38 2.57 –6.06–1.80 4.45 –4.35 0.82 8.90
–3.29 1.39 –4.44 –0.77 2.78
–0.53 –1.96 –3.43 –4.42 –3.92

...
...
...
...

0110m ψ(ℱm) < α and (m + 1)ψ(ℱm+1) ≥ αℱ1 , ℱ2 , ℱ3 ,..., ℱm–1 , ℱm , ℱm+1 ,..., ℱ2d
Testablecombinations

Untestablecombinationsℱi is significant if: p-value(ℱi) < α / m

Output:{F1}, {F3},{F2, F5},{F2, F5, F6}, ...

(ψ(ℱi) ≤ ψ(ℱi+1))
Prune without testing
Correction factor

...

...

...

Enumeration Based on Apriori

Significance Test for Feature Combination• Our task: Test the null hypothesis XF ⊥⊥ Y for all F ∈ 2V– XF : The binary random variable of joint occurrence for F• Copula Support [2] for Pr(XF = 1):
F1 F2 F3
R(F1) R(F2) R(F3)
π(F1) π(F2) π(F3)x1 –0.96 –3.03 3.38
2 0 30.67 0.00 1.00
x2 –1.80 4.45 –4.35 Rank 1 3 1 Norm. 0.34 1.00 0.34
x3 –3.29 1.39 –4.44
0 2 00.00 0.67 0.00
x4 –0.53 –1.96 –3.43
3 1 21.00 0.34 0.67
0.00
Prod. 0.11
0.00
0.22

Sum / 4

F1,F2Threshold for η F1 F2 F3Smaller η

Fd–1,FdFdLarger ψ

Testablecombinations

Experimental Results• Synthetic Data:

0.083 = Pr(X{F1,F2,F3} = 1) = η({F1,F2,F3})• The independence XF ⊥⊥ Y is translated into the condition:
H 0 ∶ D KL (pO , pE ) = 0, H 1 ∶ D KL (pO , pE ) =/0F-measure

1e−01

2

Expected (under null) for pE

XF = 1

XF = 0Total

Y =1Y =0

η(F ) r1
η(F ) r0r1 − η(F ) r1r0 − η(F ) r0

r1r0

1 − η(F )1

XF = 1

XF = 0Total

Y =1Y =0η(F , Y = 1)
η(F , Y = 0)

r1 − η(F , Y = 1)
r0 − η(F , Y = 0)

r1r0

Total

η(F )

1 − η(F )1

Multiple Testing Correction• The FWER should be controlled– Probability that at least one feature combination is a false positived– If we naïvely test all combinations, α 2 false positives could occur!!

• We use Tarone’s testability trick [3], which requires
the minimum achievable p-value ψ(F ) for F• Theorem (tight upper bound of KL divergence):1b−a
1+ (1 − b) log
D KL (p, pE ) < a log + (b − a) logb(1 − a)b(1 − a)– pE = (ab, a(1 − b), (1 − a)b, (1 − a)(1 − b))– p ∈ P (a, b) = { p ∈ P ∣ p 1 + p 2 = a, p 1 + p 3 = b }

1e−03

1e−03

1e−05

1e−05

1e−07

1e−07

1e+04

1e+04

1e+03

1e+03

1e+02

1e+02

1e+01

1e+01

Statistics of real data

C-Tarone
Binarization1e+00
1e+00
1e+03 1e+04
1e+05
20
40 60 80 100
Number of data points
Number of features

N d942 22316 27
9,706 22
13,376 10660 19356 43,314 21424 303,198 11
308 6

Data
ctg
faultsijcnn
magic
segmenttransfusion
waveform
wdbc
wine
yacht

• Real data:
C-Tarone (proposed)
F-measure

Observed for pO

Running time (sec.)

η(F )

Total

Running time (sec.)– We apply G-test: λ = 2ND KL (pO , pE ) follows χ -dist. with d.f. 1

1e−01

Binarization

1e−02
1e−04
1e−06

ctgfaults

ijcnn

magic segment transfusionwaveform wdbc

wine

yacht

ctg

faultsijcnn

magic segment transfusionwaveform wdbc

wine

yacht

1e+01
1e−01
1e−03

Reference• [1] Llinares-López, F., Sugiyama, M., Papaxanthos, L., Borgwardt, K.M.: Fast andMemory-Efficient Significant Pattern Mining via Permutation Testing, KDD 2015

• [2] Tatti, N.: Itemsets for Real-Valued Datasets, ICDM 2013
• [3] Tarone, R.: A modified Bonferroni method for discrete data, Biometrics, 1990