August 15, 2019
IJCAI 2019

Finding Statistically Significant
Interactions between
Continuous Features
Mahito Sugiyama (National Institute of Informatics)
Karsten Borgwardt (ETH Zürich)Our Proposal: C-Tarone• Find all feature interactions that are significantly associated withclass labels from multivariate data with controlling the FWERxInput:
F1
ID1
ID2
ID3
ID4

F2F3yF4F5–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... Class...
...
...
...

0110...

...

...

1/14

Our Proposal: C-Tarone• Find all feature interactions that are significantly associated withclass labels from multivariate data with controlling the FWERxInput:
F1ID1
ID2ID3ID4F2F3yF4

F5–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... Class
...
...
...
...

01
10

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

...

...

...

1/14

Existing Method: Significant Pattern Mining• So far only binary (or discrete) data can be used
→ Results obtained by SPM via binarization can be uninformative!

xInput:ID1ID2ID3ID4yF1F2F3F4F5... Class0
110

1
110

100
11
1000
1
1
1

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

0
1
10

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

...

...

...

2/14We solve:
1. How to assess the significance fora multiplicative interaction of continuous features?
2. How to perform multiple testing correction?
– How to control the FWER (family-wise error rate),the probability to detect one or more false positives?

3. How to manage combinatorial explosion of the candidate space?
– The number of possible interactions is 2d for d features

3/14

Problem Formulation• Define XF as the binary random variable of joint occurrence
for a feature combination F = {F i , F i+1 , . . . , F i+k }– XF = 1 if F “occurs”, XF = 0 otherwise• Let Y be an output binary variable• Our task: Test the null hypothesis XF ⊥⊥ Y for all F ∈ 2V– Testing statistical independence between XF and Y• We need to estimate the probability Pr(XF ) from data
4/14

Copula Support [Tatti, 2013] for Pr(XF = 1)
F1 F2 F3R(F1) R(F2) R(F3)
π(F1) π(F2) π(F3)x1 –0.96 –3.03 3.38
2 0 3
0.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 2
1.00 0.34 0.67
0.00
Prod. 0.11
0.00
0.22

Sum / 40.083 = Pr(X{F1,F2,F3} = 1) = η({F1,F2,F3})
5/14

Contingency Tables
Expected (under null) for pE

XF = 1

XF = 0Total

Y =1
Y =0

η(F ) r1
η(F ) r0

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

r1r0Totalη(F )1 − η(F )1

Observed for pO

XF = 1

XF = 0

Total

Y =1
Y =0

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

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

r1r0Totalη(F )1 − η(F )1
6/14

Significance Test
• The independence XF ⊥⊥ Y is translated into the condition:
H 0 ∶ D KL (pO , pE ) = 0, H 1 ∶ D KL (pO , pE ) =/0– pE and pO are vectorized contingency tables:
pE = ( η(F )r1 , η(F )r0 , r1 − η(F )r1 , r0 − η(F )r0 )pO = ( η(F , Y = 1), η(F , Y = 0), r1 − η(F , Y = 1), r0 − η(F , Y = 0) )• We apply G-test: the statistic λ = 2ND KL (pO , pE ) follows the2χ -distribution with the d.f. 1

7/14

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

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

Tarone’s Testability Trickℱ1 , ℱ2 , ℱ3 ,..., ℱm–1 , ℱm , ℱm+1 ,..., ℱ2d(ψ(ℱi) ≤ ψ(ℱi+1))

9/14

Tarone’s Testability Trickm ψ(ℱm) < α and (m + 1)ψ(ℱm+1) ≥ αℱ1 , ℱ2 , ℱ3 ,..., ℱm–1 , ℱm , ℱm+1 ,..., ℱ2d(ψ(ℱi) ≤ ψ(ℱi+1))

9/14

Tarone’s Testability Trickm ψ(ℱ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(ψ(ℱi) ≤ ψ(ℱi+1))
Prune without testing
Correction factor
9/14

Enumeration Algorithm Based on Apriori...
F1,F2F1 F2 F3...
...

Fd–1,Fd
Fd
10/14

Enumeration Algorithm Based on Apriori

...
F1,F2
Threshold for η F1 F2 F3Smaller ηLarger ψ...
...

Fd–1,Fd
Fd
10/14

Enumeration Algorithm Based on Apriori

...
F1,F2
F1 F2 F3
Smaller ηLarger ψ...
...

Fd–1,Fd
Fd
10/14

Enumeration Algorithm Based on Apriori

...
F1,F2
F1 F2 F3
Smaller ηLarger ψ...
...

Fd–1,Fd
Fd
10/14

Enumeration Algorithm Based on Apriori

...
F1,F2
F1 F2 F3
Smaller ηLarger ψ...
...

Fd–1,Fd
Fd

Testablecombinations
10/14

F-measure

Experimental Results on Synthetic Data
1e−01

1e−01

1e−03

1e−03

1e−05

1e−05

1e−07
1e+03 1e+04
1e+05
Number of data points

C-Tarone
Binarization

1e−07
20

40 60 80 100
Number of features
11/14

Running time (sec.)

Experimental Results on Synthetic Data
1e+04

1e+04

1e+03

1e+03

1e+02

1e+02

1e+01

1e+01

C-TaroneBinarization

1e+00
1e+00
1e+03 1e+04
1e+05
20
40 60 80 100
Number of data points
Number of features
12/14

Running time (sec.)

F-measure

Experimental Results on Real Data
C-Tarone (proposed)

Binarization

ctg

faults

ijcnn

magic

segment

ctg

faults

ijcnn

magic

segment13/14

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

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

Running time (sec.)

F-measure

Experimental Results on Real Data
C-Tarone (proposed)

Binarizationtransfusion

waveform

wdbc

wine

yacht

transfusion

waveform

wdbc

wine

yacht 13/14

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

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

Conclusion• We have proposed C-Tarone, a solution to the open problem offinding all multiplicative interactions between continuous features
significantly associated with an output variable– Significance is rigorously controlled for multiple testing• Our work opens the door to many applications of searchingsignificant feature combinations, in which the data is notadequately described by binary features

14/14