ICML2011

Jun. 28-Jul. 2, 2011

On Information-Maximization
Clustering: Tuning Parameter
Selection and Analytic Solution

Masashi Sugiyama, Makoto Yamada,
Manabu Kimura, and Hirotaka Hachiya
Department of Computer Science
Tokyo Institute of Technology

2

Goal of Clustering
Given unlabeled samples
assign cluster labels,
so that

Samples in the same cluster are similar.
Samples in other clusters are dissimilar.

Throughout this talk, we assume

is known.

Contents
1. Problem formulation
2. Review of existing approaches
3. Proposed methodA) ClusteringB) Tuning parameter optimization

4. Experiments

3Model-based Clustering

4Learn a mixture model by maximum-likelihood
or Bayes estimation:

K-means (MacQueen, 1967)
Dirichlet process mixture(Ferguson, 1973)

Pros and cons:☺ No tuning parameters.
Cluster shape depends on pre-definedcluster models ( Gaussian).
Initialization is difficult.

Model-free Clustering
No parametric assumption on clusters:
Spectral clustering: K-means after non-linear
manifold embedding(Shi & Malik, 2000; Ng et al., 2002)

Discriminative clustering: Learn a classifier andcluster labels simultaneously(Xu et al., 2005; Bach & Harchaoui, 2008)

Dependence maximization: Determine labels sothat dependence on samples is maximized(Song et al., 2007; Faivishevsky & Goldberger, 2010)

Information maximization: Learn a classifier sothat some information measure is maximized(Agakov & Barberu, 2006; Gomes et al., 2010)5

Model-free Clustering (cont.)
Pros and cons:☺ Cluster shape is flexible.
Kernel/similarity parameter choice is difficult.
Initialization is difficult.

6

Contents
1. Problem formulation
2. Review of existing approaches
3. Proposed methodA) ClusteringB) Tuning parameter optimization

4. Experiments

7

Goal of Our Research

8We propose a new information-maximization
clustering method:☺ Global analytic solution is available.
☺ Objective tuning-parameter choice is possible.

In the proposed method:
A non-parametric kernel classifier is learned
so that an information measure is maximized.
Tuning parameters are chosen so thatan information measure is maximized.

9Squared-loss Mutual Information(SMI)
As an information measure, we use SMI:

Ordinary MI is the KL divergence.
SMI is the Pearson (PE) divergence.
Both KL and PE are f-divergences(thus they have similar properties).
Indeed, as ordinary MI, SMI satisfies

Contents
1. Problem formulation
2. Review of existing approaches
3. Proposed methodA) ClusteringB) Tuning parameter optimization

4. Experiments

10Kernel Probabilistic Classifier

11

Kernel probabilistic classifier:Learn the classifier so that SMI is maximized.

Challenge: onlyis available for training

SMI Approximation

12

Approximate cluster-posterior by kernel model:

Approximate expectation by sample average:

Assume cluster-prior is uniform:: # clusters

Then we obtain the following SMI approximator:

Maximizing SMI Approximator

13

Under mutual orthonormality of,a solution is given by principal componentsof kernel matrix .
Similar to Ding & He (ICML2004)

SMI-based Clustering (SMIC)

14

Post-processing:
Adjusting sign of principal components:Vector with all ones

Normalization according to.
Rounding-up negative probability estimates to 0.

Final solution (analytically computable):: -th element of a vector:Vector with all zeros:

Contents
1. Problem formulation
2. Review of existing approaches
3. Proposed methodA) ClusteringB) Tuning parameter optimization

4. Experiments

15

Tuning Parameter Choice16

Solution of SMIC depends on kernel functions.
We determine kernels so that SMI is maximized.
We may use the samefor this purpose.

However,
is not accurate enough since
it is an unsupervised estimator of SMI.
In the phase of tuning parameter choice,estimated labels are available!

Supervised SMI Estimator

17

Least-squares mutual information (LSMI):
Directly estimate the density ratio

Suzuki & Sugiyama(AISTATS2010)

without going through density estimation.
Density-ratio estimation is substantially easierthan density estimation (à la Vapnik).
KnowingKnowingDensity-Ratio EstimationKernel density-ratio model:: Kernel function(We use Gaussian kernel)

Least-squares fitting:

18

19

Density-Ratio Estimation (cont.)
Empirical and regularized training criterion:

Global solution can be obtained analytically:

Kernel and regularization parameter can be
determined by cross-validation.

20

Least-Squares Mutual Information(LSMI)
SMI approximator is given analytically as

LSMI achieves a fast non-parametricconvergence rate! Suzuki & Sugiyama (AISTATS2010)
We determine the kernel function in SMIC
so that LSMI is maximized.

Summary of Proposed MethodSMI Clustering with LSMI:

LSMILSMI

Unlabeled samples
Kernel candidates
Output: Cluster labels

SMIC
SMIC

Input:

21

Contents
1. Problem formulation
2. Review of existing approaches
3. Proposed methodA) ClusteringB) Tuning parameter optimization

4. Experiments

22

23

Experimental Setup

For SMIC, we use a sparse variant of
the local scaling kernel: (Zelnik-Manor & Perona,NIPS2004): -th neighbor of

Tuning parameter is determined byLSMI maximization.

24

Illustration of SMIC
222

1.5

1.5

1

1

0.5

0.5

0100−0.5

0−0.5−0.5−1−1−1−1−1.5−2−1.5−1.5−2−3−1012−2−2−1012−2.5−10−4

12 −4−202

4

0.4
0.45

0.45

1.2
1.1
1
0.9

0.35
SMI estimate

SMI estimate

1.3
SMI estimate

−2

0.5

1.4

0.4

0.35

0.4
0.35
0.3

0.3
0.25
0.2
0.15
0.1

0.3

0.25

0.8
0.7

2

0.5

0.5

1.5

31

SMI estimate

−2−2

4

1.5

0.05
246t8

10

0.25

246t8

10

0.2

246t8

100246810t

SMIC with model selection by LSMI works well!

Performance Comparison

25(MacQueen, 1967)
KM: K-means clustering
SC: Self-tuning spectral clustering(Zelnik-Manor & Perona, NIPS2004)

MNN: Dependence-maximization clustering
based on mean nearest neighbor approximation(Faivishevsky & Goldberger, ICML2010)

MIC: Information-maximization clustering forkernel logistic models with model selection bymaximum-likelihood mutual information(Gomes, Krause & Perona, NIPS2010)(Suzuki, Sugiyama, Sese & Kanamori, FSDM2008)

Experimental Results
ARITimeDigit (d = 256, n = 5000, and c = 10)
KMSC
MNN
MIC
0.42(0.01) 0.24(0.02)
0.44(0.03) 0.63(0.08)
835.9
973.3
318.5
84.4[3631.7]

SMIC
0.63(0.05)
14.4[359.5]

ARI
Time

Face (d = 4096, n = 100, and c = 10)
KM
SC
MNN
MIC
0.60(0.11) 0.62(0.11) 0.47(0.10)
0.64(0.12)
93.3
2.1
1.0
1.4[30.8]

SMIC
0.65(0.11)
0.0[19.3]

Document (d = 50, n = 700, and c = 7)
KM
SC
MNN
MIC
0.00(0.00) 0.09(0.02)
0.09(0.02)
0.01(0.02)
77.8
9.7
6.4
3.4[530.5]

SMIC
0.19(0.03)
0.3[115.3]

ARI
Time

Word (d = 50, n = 300, and c = 3)
KM
SC
MNN
MIC
0.04(0.05) 0.02(0.01)
0.02(0.02)
0.04(0.04)
6.5
5.9
2.2
1.0[369.6]

SMIC
0.08(0.05)
0.2[203.9]

ARI
Time

Accelerometry (d = 5, n = 300, and c = 3)
KM
SC
MNN
MIC
0.49(0.04) 0.58(0.14) 0.71(0.05)
0.57(0.23)
0.4
3.3
1.9
0.8[410.6]

SMIC
0.68(0.12)
0.2[92.6]

ARI
Time

Speech (d = 50, n = 400, and c = 2)
KM
SC
MNN
MIC
0.00(0.00) 0.00(0.00)
0.04(0.15) 0.18(0.16)
0.9
4.2
1.8
0.7[413.4]

SMIC
0.21(0.25)
0.3[179.7]

20NewsGroup

ARITimeSens
eval2

26

Adjusted Randindex (ARI):
larger is better
Red: Best orcomparable by
1%t-test
SMIC works wellandcomputationallyefficient!

Conclusions

27

Weaknesses of existing clustering methods:
Cluster initialization is difficult.
Tuning parameter choice is difficult.

SMIC: A new information-maximization
clustering method based on squared-loss
mutual information (SMI):
Analytic global solution is available.
Objective tuning parameter choice is possible.

MATLAB code is available fromhttp://sugiyama-www.cs.titech.ac.jp/~sugi/software/SMIC/

Other Usage of SMI
Feature selection
Suzuki, Sugiyama, Sese & Kanamori (BMC Bioinfo. 2009)

Dimensionality reduction
Suzuki & Sugiyama (AISTATS2010)
Yamada, Niu, Takagi & Sugiyama (ArXiv2011)

Independent component analysis
Suzuki & Sugiyama (Neural Comp. 2011)

Independence test
Sugiyama & Suzuki (IEICE-ED2011)

Causal inference
Yamada & Sugiyama (AAAI2010)28