ICML2006, Pittsburgh, USA

June 25-29, 2006

Local Fisher Discriminant
Analysis for Supervised
Dimensionality Reduction
Masashi Sugiyama
Tokyo Institute of Technology, Japan

Dimensionality Reduction
High dimensional data is not easy to handle:
Need to reduce dimensionality
We focus onz Linear dimensionality reduction:z Supervised dimensionality reduction:2

Within-Class Multimodality
One of the classes has several modes

Class 1 (blue)
Class 2 (red)Medical checkup:
hormone imbalance (high/low) vs. normal
Digit recognition:even (0,2,4,6,8) vs. odd (1,3,5,7,9)
Multi-class classification:
one vs. rest3

4

Goal of This ResearchWe want to embed multimodal data so thatz Between-class separability is maximizedz Within-class multimodality is preserved
Separable but within-classmultimodality
lostFDA

Within-class multimodality
preserved LPP
but non-separable

Separable and within-classmultimodality
LFDA preserved
ACB

5

Fisher Discriminant Analysis (FDA)
Within-class scatter matrix:
Between-class scatter matrix:
FDA criterion:z Within-class scatter is made smallz Between-class scatter is made large

Fisher (1936)

Interpretation of FDAPairwise expressions::Number of samples in class:Total number of samples

Samples in the same class are made close
Samples in different classes are made apart

67Examples of FDASimple

Label-mixed cluster

1010105550

close 0close 0−5−5−5apartapart−10−10−50

Multimodal
close

510−10−10−50

apart510−10−10−50510

FDA does not takewithin-class multimodality into account
NOTE: FDA can extract only C-1 features since:Number of classes

Locality Preserving Projection
He & Niyogi (NIPS2003)(LPP)

Locality matrix:Affinity matrix:e.g.,LPP criterion:z Nearby samples in original space are made closez Constraint is to avoid

8

9Examples of LPP
SimpleLabel-mixed cluster

Multimodal

1010105550close 00−5−5−5close

close−10−10−50

510
10−10−10−50

510
10−10−10−50

5

LPP does not take between-class separability
into account (unsupervised)1010

10Our Approach
We combine FDA and LPPNearby samples in thesame class are madecloseFar-apart samples in thesame class are notmade closeSamples in different
classes are made apart

10apart50close−5don’t care−10−10−5051011Local Fisher Discriminent Analysis
Local within-class scatter matrix:

Local between-class scatter matrix:

How to Obtain Solution
Since LFDA has a similar form to FDA,
solution can be obtained just by solving ageneralized eigenvalue problem:

12

13

Examples of LFDA
Simple1010

Label-mixed cluster

10555000−5−5−5−10−10−50510−10−10−50510−10−10Multimodal−505LFDA works well for all three cases!
Note: Usually
so LFDA canextract more than C features (cf. FDA)

10

Neighborhood Component
Analysis (NCA)

14

Goldberger, Roweis, Hinton & Salakhutdinov (NIPS2004)

Minimize leave-one-out error of astochastic k-nearest neighbor classifier
Obtained embedding is separable
NCA involves non-convex optimization
There are local optima
No analytic solution available
Slow iterative algorithm
LFDA has analytic form of global solution

Maximally Collapsing
Metric Learning (MCML)

15

Globerson & Roweis (NIPS2005)

Idea is similar to FDA
z Samples in the same class are close (“one point”)
z Samples in different classes are apart

MCML involves non-convex optimization
There exists a nice convex approximation
Non-global solution
No analytic solution available
Slow iterative algorithm

Simulations
Visualization of UCI data sets:z Letter recognition (D=16)
z Segment (D=18)
z Thyroid disease (D=5)
z Iris (D=4)

Extract 3 classes from original dataMerge 2 classes

Class 1 (blue)

Class 2 (red)16Summary of Simulation Results
Lett Segm Thyr Iris17Comments

FDA

No multi-modal

LPP

No label-separability

LFDA
NCA

Slow, local optima

MCML

Slow, no multi-modal

Separable and multimodality preserved
Separable but no multimodality
Multimodality preserved but no separability

18

Letter Recognition
FDA

LPP

FDA

LFDA
LFDA

LPP

A
C
B

NCA

NCA

Blue
vs.

Red

MCML
MCML

19

Segment
FDA

LPP

FDA

LFDA

LPP

LFDA

BrickfaceSky
Foliage

NCA

NCA

Blue
vs.

Red

MCML

MCML

20

Thyroid Disease
FDA

LPP

FDA

LFDA

LPP

LFDA

Hyper
Hypo
Normal

NCA
NCA

Blue
vs.

Red

MCML

MCML

21

Iris
FDA

LPP

FDA

LFDA
LFDA

LPP

SetosaVirginica
Verisicolour

NCA
NCA

Blue
vs.

RedMCMLMCML

Kernelization

22

LFDA can be non-linearized by kernel trick

Mika et al. (NNSP1999)
FDA: Kernel FDA
LPP: Laplacian eigenmap Belkin & Niyogi (NIPS2001)
MCML: Kernel MCML Globerson & Roweis (NIPS2005)
NCA: not available yet?

Conclusions

23

LFDA effectively combines FDA and LPP.
LFDA is suitable for embedding multimodaldata.
Same as FDA, LFDA has analytic optimal
solution thus computationally efficient.
Same as LPP, LFDA needs to pre-specify
affinity matrix.
We used local scaling method for computingaffinity, which does not include any tuning
Zelnik-Manor & Perona (NIPS2004)
parameter.