Oct. 22, 2020
第 41 回 IBISML

統計的に有意な相互作用探索
杉山 麿人（国立情報学研究所）

Significant Pattern Mining• Detect patterns (feature combinations) that are
statistically significantly enriched in a class of a dataset
xInput:ID1ID2ID3ID4yF1F2F3F4F5... Class

0
1
10

1
1
10

100
1

1
10
00
1
1
1

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

0
1
10

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

...

...

...

1/31

Significant Pattern Mining• Detect patterns (feature combinations) that are
statistically significantly enriched in a class of a dataset
xInput:ID1ID2ID3ID4yF1F2F3F4F5... Class01101110100111000111...
...
...
...

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

...

...

...

1/31

Significant Pattern Mining• Detect patterns (feature combinations) that arestatistically significantly enriched in a class of a dataset
xInput:ID1ID2ID3ID4yF1F2F3F4F5... Class01101110

100111000111...
...
...
...

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

...

...

...

1/31

Significant Pattern Mining• Detect patterns (feature combinations) that are
statistically significantly enriched in a class of a dataset
xInput:ID1
ID2ID3ID4yF1F2F3F4

F5... Class

0
1
10

1
1
10

100
1

1
1000
1
1
1...
...
...
...

01
10

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

...

...

...

1/31

Example: Itemset Mining
SNPs (items)
Case ID 1: 0 0 11 0 01 1 100111 001110
ID 2: 1 1 00 1 01 1 110001 010100
ID 3: 1 0 10 0 01 1 101011 000001
ID 4: 1 1 01 1 01 1 111111 010011
Control ID 5: 0 0 11 0 00 1 100011 111000
ID 6: 0 1 01 1 01 1 000011 001010
ID 7: 1 0 11 0 01 0 100000 101000
ID 8: 11 0 01 0 0 10 10100 010101

2/31

Example: Itemset Mining
SNPs (items)
Case ID 1: 0 0 11 0 01 1 100111 001110
ID 2: 1 1 00 1 01 1 11000 1 010100
ID 3: 1 01 0 00 1 1 1010 11 000001
ID 4: 1 10 1 10 1 1 111 111 01001 1Signal
1111

Control ID 5: 00 1 10 0 0 1100 011 1110 00
ID 6: 01 0 11 0 1 100 0011 0010 10ID 7: 1 0 11 0 01 0 1 00000 10 1000
ID 8: 11 0 01 0 0 10 10100 010101

00002/31

Positive

Example: Subgraph Mining
Signiciant
subgraphs

Negative

Support: (4, 0)
p-value = 0.0143
Support: (0, 2)
p-value = 0.214

3/31

Timeline
1990

2000

2010

Tarone’s testability
Itemset mining
Subgraph mining
Data mining
in computer science2020
Significant
pattern mining
LAMP
WY lightFACS
FastCHM
C-Tarone
4/31

Recent Advances• Webb, G.I., Petitjean, F.: A Multiple Test Correction forStreams and Cascades of Statistical Hypothesis Tests,KDD2016• Pellegrina, L., Vandin, F.: Efficient Mining of the Most
Significant Patterns with Permutation Testing, KDD2018• Pellegrina, L., Riondato, M., Vandin, F.: SPuManTE: Significant
Pattern Mining with Unconditional Testing, KDD2019• Tran, T.Q., Fukuchi, K., Akimoto, Y., Sakuma, J.: StatisticallySignificant Pattern Mining with Ordinal Utility, KDD2020
5/31

Libraries• CASMAP– Llinares-Lopez, et al.: CASMAP: Detection of statisticallysignificant combinations of SNPs in association
mapping, Bioinformatics (2019)• MP-LAMP (for parallel computation)– Yoshizoe, K., Terada, A., Tsuda, K.: MP-LAMP: parallel
detection of statistically significant multi-loci markers
on cloud platforms, Bioinformatics (2018)
6/31

Key Challenges:
1. How to assess the significance fora multiplicative interaction of variables?
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𝑑(2 for 𝑑 variables) of the candidate space?
7/31

Problem Formulation• Define 𝑋ℱ as binary random variable of joint occurrence
for a feature combination ℱ = {𝐹𝑖 }𝑖∈𝐼 , 𝐼 ⊆ {1, … , 𝑑}
– 𝑋ℱ = 1 if ℱ “occurs”, 𝑋ℱ = 0 otherwise• Let 𝑌 be an output binary variable8/31

Problem Formulation• Define 𝑋ℱ as binary random variable of joint occurrence
for a feature combination ℱ = {𝐹𝑖 }𝑖∈𝐼 , 𝐼 ⊆ {1, … , 𝑑}
– 𝑋ℱ = 1 if ℱ “occurs”, 𝑋ℱ = 0 otherwise• Let 𝑌 be an output binary variable• Task: Test the null hypothesis 𝑋ℱ ⟂⟂ 𝑌 for all ℱ ∈ 2𝑉– Testing statistical independence between 𝑋ℱ and 𝑌

8/31

Fisher’s Exact Test
𝑋ℱ = 0Total

𝑌=1
𝑌=0

𝑆(ℱ, 𝑌 = 1)
𝑆(ℱ, 𝑌 = 0)

𝑁1 − 𝑆(ℱ, 𝑌 = 1)
𝑁0 − 𝑆(ℱ, 𝑌 = 0)

𝑁1𝑁0Total

𝑆(ℱ)

𝑁 − 𝑆(ℱ)

𝑁Prob. q

𝑋ℱ = 10p-value
S(𝓕, Y = 1)

q=N0
N1
S(𝓕,Y=1) S(𝓕,Y=0)

NS(𝓕)
9/31

Multiple Testing Correction• In each test, [probability of having a false positive] ≤ 𝛼• If we repeat 𝑚 tests, 𝛼𝑚 patterns can be false positives– Too many if 𝑚 is large! For example in itemset mining:◦ For 100000 items, #patterns = 2100000◦ Set significance level 𝛼 = 0.01
◦ Number of false positives: 0.01 ⋅ 2100000 = 1030101• The FWER should be controlled– Probability at least one ℱ is false positive
10/31

Controlling the FWER
• FWER = Pr(FP > 0)
– FP: Number of false positives• Objective: Maximize FWER(𝛿) subject to FWER(𝛿) ≤ 𝛼– FWER(𝛿): FWER at corrected significance level 𝛿◦ Cannot be evaluated in closed form (simple but not easy!)∗– Bonferroni correction is popular: 𝛿Bon= 𝛼∕𝑚

10/31

Tarone’s Testability Trick• We use Tarone’s testability trick, which requires
the minimum achievable 𝑝-value 𝜓(ℱ) for ℱ( 𝑁 )/( 𝑁 )1
𝜓(ℱ) =in Fisher’s exact test
𝑆(ℱ)
𝑆(ℱ)

11/31

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

12/31

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

12/31

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
12/31

Tarone’s Testability Trick with Apriori• We use Tarone’s testability trick, which requires
the minimum achievable 𝑝-value 𝜓(ℱ) for ℱ( 𝑁 )/( 𝑁 )1
𝜓(ℱ) =in Fisher’s exact test
𝑆(ℱ)
𝑆(ℱ)
• This method is particularly effective if the relationship“Smaller 𝜂(ℱ) → Larger 𝜓(ℱ)” holds– For each pattern ℱ,
𝑆(ℱ): Support (how many times ℱ occurs in a dataset)𝜂(ℱ) = 𝑆(ℱ)∕𝑁: Frequency
13/31

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

Fd–1,Fd
Fd
14/31

Enumeration Based on Apriori
...
F1,F2
Threshold for η F1 F2 F3Smaller ηLarger ψ...
...

Fd–1,Fd
Fd
15/31

Enumeration Based on Apriori...
F1,F2
F1 F2 F3Smaller η

Larger ψ...
...

Fd–1,Fd
Fd
16/31

Enumeration Based on Apriori
...
F1,F2
F1 F2 F3Smaller η

Larger ψ...
...

Fd–1,Fd
Fd
17/31

Enumeration Based on Apriori
...
F1,F2
F1 F2 F3Smaller η

Larger ψ...
...

Fd–1,Fd
Fd

Testablecombinations

18/31

Power of Testability
Correction factor
Bonferroni
Ours
107105103510
15 Limitless
Maximum size ofsubgraph nodes

Number of significant
Running time (second)
subgraphs
4Bonferroni
Bonferroni
Ours
Ours
105
3103
211000.151015 Limitless
Maximum size of
subgraph nodes

51015 Limitless
Maximum size of
subgraph nodes

The PTC (Predictive Toxicology Challenge) dataset with 601 chemical compounds

19/31

Summary
1. Formulate significance test for each pattern– Fisher’s exact test is standard,
while there are more possibilities

2. Enumerate testable patterns via
Tarone’s testability + Apriori (DFS)
3. Test each testable pattern
20/31

LAMP and WY light
SNPs (items)
Case ID 1: 0 0 11 0 01 1 100111 001110
ID 2: 1 1 00 1 01 1 11000 1 010100
ID 3: 1 01 0 00 1 1 1010 11 000001
ID 4: 1 10 1 10 1 1 111 111 01001 1Signal
1111Control ID 5: 00 1 10 0 0 1100 011 1110 00
ID 6: 01 0 11 0 1 100 0011 0010 10ID 7: 1 0 11 0 01 0 1 00000 10 1000
ID 8: 11 0 01 0 0 10 10100 010101

000021/31

FACS [Papaxanthos et al. 2016] for Covariates
SNPs (items)
Cov. Signal
Case ID 1: 0 0 11 0 01 1 100111 001110 Europe 1
ID 2: 1 1 00 1 01 1 11000 1 010100 Europe 11ID 3: 1 01 0 00 1 1 1010 11 000001 Asia
1ID 4: 1 10 1 10 1 1 111 111 01001 1 Asia
Control ID 5: 00 1 10 0 0 1100 011 1110 00 Europe
ID 6: 01 0 11 0 1 100 0011 0010 10 Europe
ID 7: 1 0 11 0 01 0 1 00000 10 1000 Asia
ID 8: 11 0 01 0 0 10 10100 010101 Asia

000021/31

FAIS [Llinares-López et al. 2015] for Intervals
SNPs (items)
Case ID 1: 0 0 11 0 01 1 100111 001110
ID 2: 1 1 00 1 01 1 110001 010100
ID 3: 1 0 10 0 01 1 101011 000001
ID 4: 1 1 01 1 01 1 111111 010011

Signal1111Control ID 5: 0 0 11 0 00 1 100011 111000
ID 6: 0 1 01 1 01 1 000011 001010
ID 7: 1 0 11 0 01 0 100000 101000
ID 8: 11 0 01 0 0 10 10100 010101

000121/31

FastCHM for Intervals + Cov.
SNPs (items)
Cov. Signal
Case ID 1: 0 0 11 0 01 1 100111 001110 Europe 1
ID 2: 1 1 00 1 01 1 110001 010100 Europe 11ID 3: 1 0 10 0 01 1 101011 000001 Asia
1ID 4: 1 1 01 1 01 1 111111 010011 Asia
Control ID 5: 0 0 11 0 00 1 100011 111000 EuropeID 6: 0 1 01 1 01 1 000011 001010 Europe
ID 7: 1 0 11 0 01 0 100000 101000 Asia
ID 8: 11 0 01 0 0 10 10100 010101 Asia

0001

21/31

C-Tarone [Sugiyama & Borgwardt, 2019]• Find all feature interactions form continuous datax

Input:
F1
ID1
ID2
ID3
ID4

F2F3yF4

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
1
0...

...

...

22/31

C-Tarone [Sugiyama & Borgwardt, 2019]• Find all feature interactions form continuous datax

Input:
F1ID1ID2ID3ID4F2F3yF4F5–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
10Output:{F1}, {F3},{F2, F5},{F2, F5, F6}, ...

...

...

...

22/31

Use Copula Support [Tatti, 2013]
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 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})
23/31

Contingency Tables• For each pattern (variable combination), we construct
two types of contingency tables– One is from the expected situation under null
– The other is from the observed situation from data

• Significance is assessed by comparison of the two tables– Each table is represented as a four-dimensional vector

24/31

Expected for 𝒑E

𝑋ℱ = 1

𝑋ℱ = 0Total

𝑌=1𝑌=0𝜂(ℱ) 𝑟1
𝜂(ℱ) 𝑟0𝑟1 −𝜂(ℱ) 𝑟1𝑟0 −𝜂(ℱ) 𝑟0𝑟1𝑟0Total

𝜂(ℱ)

1−𝜂(ℱ)

1

Observed for 𝒑O

𝑋ℱ = 1

𝑋ℱ = 0Total

𝑌=1
𝑌=0

𝜂(ℱ, 𝑌 = 1)
𝜂(ℱ, 𝑌 = 0)

𝑟1 −𝜂(ℱ, 𝑌 = 1)𝑟0 −𝜂(ℱ, 𝑌 = 0)

𝑟1𝑟0

Total

𝜂(ℱ)

1−𝜂(ℱ)

125/31

Significance Test
• The independence 𝑋ℱ ⟂⟂ 𝑌 is translated into:
𝐻0 ∶ 𝐷KL (𝒑O , 𝒑E ) = 0,𝐻1 ∶ 𝐷KL (𝒑O , 𝒑E ) ≠ 0– 𝒑E and 𝒑O are vectorized contingency tables:()
𝒑E = 𝜂(ℱ)𝑟1 , 𝜂(ℱ)𝑟0 , 𝑟1 −𝜂(ℱ)𝑟1 , 𝑟0 −𝜂(ℱ)𝑟0()
𝒑O = 𝜂(ℱ, 𝑌 = 1), 𝜂(ℱ, 𝑌 = 0), 𝑟1 −𝜂(ℱ, 𝑌 = 1), 𝑟0 −𝜂(ℱ, 𝑌 = 0)

• We apply G-test: the statistic 𝜆 = 2𝑁𝐷KL (𝒑O , 𝒑E )follows the 𝜒 2 -distribution with the d.f. 1
26/31

KL Divergence Bound• Theorem (tight upper bound of KL divergence):
𝐷KL (𝒑, 𝒑E )1𝑏−𝑎1
< 𝑎 log + (𝑏 − 𝑎) log+ (1 − 𝑏) log𝑏(1 − 𝑎)𝑏(1 − 𝑎)– 𝒑E = (𝑎𝑏, 𝑎(1 − 𝑏), (1 − 𝑎)𝑏, (1 − 𝑎)(1 − 𝑏)),𝒑 ∈ { 𝒑 ∈ 𝒫 ∣ 𝑝1 + 𝑝2 = 𝑎, 𝑝1 + 𝑝3 = 𝑏 }• The 𝑝-value for this upper bound is
the minimum achievable 𝑝-value
27/31

F-measure

Exp. 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

28/31

Running time (sec.)Exp. Results on Synthetic Data
1e+04

1e+04

1e+03

1e+03

1e+02

1e+02

1e+01

1e+01

C-Tarone
Binarization

1e+00
1e+00
1e+03 1e+04
1e+05
2040 60 80 100
Number of data points
Number of features

29/31

Running time (sec.)

F-measure

Experimental Results on Real Data
C-Tarone (proposed)

Binarization

ctg

faults

ijcnn

magic

segment

ctg

faults

ijcnn

magic

segment 30/31

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

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

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

30/31

Conclusion• Significant pattern mining is introduced– Find significant interactions while controlling the FWER
– pattern mining (data mining) + multiple testing correction(statistics)• Key to solve the problem is Tarone’s testability trick– This method can be used if the minimum achievable𝑝-value 𝜓 exists– If we have the relationship “Smaller 𝜂 → Larger 𝜓”, Apriori
can be used to efficiently enumerate testable patterns
31/31