Safe Pattern Pruning:
An Efficient Approach for
Predictive Pattern Mining(KDD2016)
Ichiro Takeuchi
Nagoya Institute of Technology, Japan

Joint work with
Kazuya Nakagawa, Shinya Suzumura, Masayuki Karasuyama, Koji Tsuda,

1/26Graph miningI

The goal of frequent subgraph mining is to find a set of subgraphsthat frequently appear in a database.

I

Some computational tricks for handling exponentially large numberof subgraphs are needed for graph mining tasks.

I

Many efficient algorithms that exploit anti-monotonicity properties
of subgraph frequencies exist in the literature.

JUDSKGDWD,

VXEJUDSKV

2/26

Itemset miningI

The goal of frequent itemset mining is to find a set of items thatfrequently appear in a database.

I

Some computational tricks for handling exponentially large numberof itemsets are needed for itemset mining tasks.

I

Many efficient algorithms that exploit anti-monotonicity propertiesof itemset frequencies exist in the literature.

LWHPV

,

LWHPVHWV

3/26

Anti-monotonicity property among patterns
I,

The frequency of a pattern in an ancestor node is greater than orequal to the frequency of a pattern in its any descendant node.

4/26

Predictive pattern mining,I

The goal of predictive pattern mining is to learn a classification orregression model f as a function of the existences of patterns.

I

A graph classification/regression model looks likeI

An itemset classification/regression model looks likeI

A classification/regression model f is learned over exponentiallylarge number of patterns: some computational tricks are needed.

5/26

Can we use existing feature selection algorithms in statistics and ML?

IFeature selection for classification/regression models have been
intensively studied in statistics and machine learning.
marginal screening(e.g.) correlations, χ2 statistics
I stepwise selection(e.g.) forward selection / backward elimination
I sparse modeling(e.g.) L1 -norm regularization
II,

Existing feature selection algorithms in statistics and ML cannot bedirectly applied to predictive pattern mining problems because there
are exponentially large number of features (patterns).

6/26

This talk in a nutshell,I

We study predictive pattern mining problems (graph mining anditemset mining) for regression and classification tasks.

IWe select a subset of predictive patterns by using sparse modeling(L1 regularization).

ITo handle exponentially large number of patterns, we propose anovel algorithm called safe pruning rule.

IThe safe pruning rule is an extension of safe screening rules whichhave been recently actively studied in ML literature.

7/26

Problem Setup and Basic Idea,

8/26

Problem setup (dataset)I

Training dataset{(Gi , yi )}ni=1I

Gi is a graph or a set of items

Iyi ∈ R for regression, yi ∈ {±1} for binary classificationIGi is represented as a binary vector xi ∈ RD whose tth -element isdefined as
xit := I(t ⊆ Gi ) for each pattern t in the database,where D is the number of all possible patterns (too huge to handlenaively).

,

9/26

Dataset looks likeyi
-1

1

1

1

⋯

+1

101

⋯

-1

100

⋯

⋮⋮

⋮

⋱

⋮
,

⋯Gi

⋮

10/26

Problem setup (sparse modeling)I

Huge-dimensional linear model for regression or classification:f (xi ) = w1 xi1 + w2 xi2 + . . . + wD xiD

ISparse modeling: introduce a mechanism to make coefficientssparse via L1 -regularization (LASSO)
w∗ := arg min P (w) :=w∈RDInX2(yi − x>i w) + λi=1DX|wj |j=1

Active patterns are defined asA∗ := {j ∈ {1, . . . , D} | wj∗ 6= 0}

,

11/26

Basic idea
I

The difficulty lies in the fact that existing LASSO solvers cannot be
used because D is too huge.

IOur idea is to find a superset of the active set:
A ⊇ A∗ ,and solve the optimization problem over A (assuming A is smallenough).

I

It can be guaranteed that the optimal solution of the problem
defined on A ⊇ A∗ is also optimal for the original problem, i.e., ∗ wAw∗ = P
where P is the permutation matrix,
0and∗wA:= arg minwA,nX
X
2(yi − x>|wj |iA wA ) + λi=1

j∈A

12/26

Safe screening
is a method to find a superset A ⊇ A∗ in ordinal LASSO problem (butcannot be applied to predictive pattern mining problems without tricks).

,

13/26

Safe screening for LASSO (1)IPrimal Problem:w∗ := arg min P (w) :=w∈RDI2(yi − x>i w) + λi=1

DX|wj |

j=1

Dual Problem:1
θ := arg minn
θ∈R2
∗

InX


2nX
1
xij θi ≤ 1, ∀jθ i − yis.t.
λi=1Sparsity Condition:nX

xij θi∗ < 1⇒

wj∗ = 0,i=1|,{zscore}

14/26

Safe screening for LASSO (2)I

Using convex optimization theory, we can find a ball B in the dual
solution space in which the dual optimal solution θ ∗ exists:q∗−1
B := {θ | kθ − ck ≤ r} where c := θ̂, r := 2λP (ŵ) − D(θ̂)

I

Safe screening exploits the fact that θ ∗ ∈ B in order to identify
sparse features:maxθ∈B|nXxij θi < 1 ⇒i=1nX

xij θi∗ < 1 ⇒ wj∗ = 0

i=1{zUB of the score<1}

B|{zthe score<1}| {z }
sparse𝜽∗Non-Activeconstraint →Active constraint →

,

15/26

Safe pruning
is an extension of safe screening for handling exponentially large numberof patterns in predictive pattern mining problems.

,16/26

Safe pruning ruleI

We cannot compute safe feature screening bounds for each of these
exponentially large number of patterns.

IWe develop a safe pruning rule spr(j) for each node j in the treesuch thatspr(j) is true ⇒nX

xij 0 θi∗ < 1 ⇒ wj∗0 = 0 for all j 0 ∈ Des(j),i=1where Des(j) is the set of descendant nodes of the node j.

,

17/26

Safe pruning rule (how it works)
I

Finding a superset A of the active set A∗ := {j | wj∗ 6= 0}:spr(z1 ) = false,,

A = {z1 }18/26

Safe pruning rule (how it works)
I

Finding a superset A of the active set A∗ := {j | wj∗ 6= 0}:
spr(z1 z2 ) = true,,

A = {z1 }18/26

Safe pruning rule (how it works)
I

Finding a superset A of the active set A∗ := {j | wj∗ 6= 0}:
spr(z1 z3 ) = false,,

A = {z1 , z1 z3 }18/26

Safe pruning rule (how it works)
I

Finding a superset A of the active set A∗ := {j | wj∗ 6= 0}:
spr(z1 z3 z4 ) = false,,

A = {z1 , z1 z3 , z1 z3 z4 }18/26

Safe pruning rule (how it works)
I

Finding a superset A of the active set A∗ := {j | wj∗ 6= 0}:
spr(z1 z4 ) = true,,

A = {z1 , z1 z3 , z1 z3 z4 }18/26

Safe pruning rule (how it works)
I

Finding a superset A of the active set A∗ := {j | wj∗ 6= 0}:
spr(z2 ) = true,,

A = {z1 , z1 z3 , z1 z3 z4 }18/26

Safe pruning rule (how it works)
I

Finding a superset A of the active set A∗ := {j | wj∗ 6= 0}:
spr(z3 ) = true,,A = {z1 , z1 z3 , z1 z3 z4 }18/26

Safe pruning rule (how it works)

I

Finding a superset A of the active set A∗ := {j | wj∗ 6= 0}:
spr(z4 ) = false,,

A = {z1 , z1 z3 , z1 z3 z4 , z4 }18/26

Safe pruning rule (how it works)

I

Finding a superset A of the active set A∗ := {j | wj∗ 6= 0}:
A = {z1 , z1 z3 , z1 z3 z4 , z4 }

,

18/26

Experiments

,

19/26

Problem setup in experiments
Computing a sequence of solutions for various λ values
Input:{(Gi , yi )}i∈[n] , {λk }k∈[K]
1. Compute λ0 and w0∗ = 0
2. for k = 1, . . . , K do
3.

Find Aλk ⊇ A∗λk by using the SPP based on∗∗
wk−1 and θk−1

4.

Solve an optimization problem defined only withthe set of patterns in Aλk

5. end for
Output:,{wk∗ }k∈[K] , {θk∗ }k∈[K]

20/26

Competing method in experiments

IWe compared the computational costs of the proposed safe pattern
pruning with g-boost 1 and i-boost 2 .

I

In these boosting-based approaches, the most active feature (themost violating constraint in the dual) is added one by one.

I

These boosting-based approaches also exploit the tree structure
among the patterns when it finds the most active feature.

I

These boosting-based approaches require multiple searches over thetree (every time a new active feature is added).

1

H. Saigo, T. Uno and K. Tsuda. Mining complex genotypic features for predicting hiv-1 drug resistance(Bioinformatics, 2006)

2

H. Saigo, T. Uno and K. Tsuda. Mining complex genotypic features for predicting hiv-1 drug resistance.

(Bioinformatics, 2006)
,

21/26

Results in experiments
6000
traverse
solveTime (sec)Time (sec)

5000
4000
3000
2000
1000
0

5 6 7 8 9 10

5 6 7 8 9 10

5 6 7 8 9 10boosting

SPPboosting

SPP

Graph Data2 (regression)

2500
traverse
solveTime (sec)2000Time (sec)traversesolve

5 6 7 8 9 10

Graph Data1 (classification)

1500
1000
500
0
3

45boosting63456SPP

Item Data1 (classification)
,

2000
1800
1600
1400
1200
1000
800
600
400
200
04500
4000
3500
3000
2500
2000
15001000
500
0traverse
solve

345boosting

63

456SPP

Item Data2 (regression)
22/26

Summary,

I

Predictive pattern mining problems are still challenging, i.e., it isstill difficult to efficiently identify a subset of patterns that are
useful for prediction tasks.

I

Safe screening method recently developed in ML literature is a newpromising approach for making sparse modeling efficient (although
it cannot be directly applied to pattern mining problems).

IThe proposed safe pruning method exploits the tree structure andthe anti-monotonicity property among the patterns in order tohandle exponentially large number of patterns in the database.

23/26

Related studies in our group
I

Selective inference for discovered patterns Suzumura, Nakagawa, Sugiyama,Tsuda, Takeuchi. Selective Inference Approach for Statistically Sound Predictive Pattern Mining (arXiv,2016)

I

Safe screening method for samples in SVM
Ogawa, Suzuki and Takeuchi. Safe screening of non-support vectors in pathwise SVM computation(ICML2013)

I

Simultaneous safe screening for features and samples
Shibagaki, Karasuyama, Hatano, Takeuchi. Simultaneous safe screening of features and sample in doubly
sparse modeling (ICML2016)

I

Quick sensitivity analysis
Okumura, Suzuki and Takeuchi. Quick sensitivity analysis for incremental data modification and its
application to leave-one-out CV in linear classification problems (KDD2015)

I

Approximate model selection
Shibagaki, Suzuki, Karasuyama Takeuchi. Regularization path of cross-Validation error lower bounds(NIPS2015),24/26Other references,I

L. El Ghaoui, V. Viallon and T. Rabbani. Safe feature elimination in sparse supervised learning (PacificJournal of Optimization, 2012)I

J. Liu, Z. Zhao, J. Wang and J. Ye. Safe screening with variational inequalities and its application toLasso (ICML2014)

I

J. Fan and J. Lv. Sure independence screening for ultrahigh dimensional feature space (Journal of The
Royal Statistical Society B, 2008)

I

E. Ndiaye, O. Fercoq, A. Gramfort, and J. Salmon. Gap safe screening rules for sparse multi-task andmulti-class models (NIPS2015)

I

H. Saigo, T. Uno and K. Tsuda. Mining complex genotypic features for predicting hiv-1 drug resistance(Bioinformatics, 2006)

I

H. Saigo, S. Nowozin, T. Kadowaki, T. Kudo, K. Tsuda. gboost: a mathematical programming approachto graph classification and regression (Machine Learning, 2009)I

Hanada, Shibagaki, Sakuma, Takeuchi. Efficiently Bounding Optimal Solutions after Small Data
Modification in Large-Scale Empirical Risk Minimization (arXiv, 2016)25/26

Thank you,

26/26