Machine Learning, vol.78, no.1–2, pp.35–61, 2010.

1

Semi-Supervised Local Fisher Discriminant Analysis
for Dimensionality Reduction∗
Masashi Sugiyama
Department of Computer Science, Tokyo Institute of Technology
2-12-2 O-okayama, Meguro-ku, Tokyo 152-8552, Japansugi@cs.titech.ac.jp
Tsuyoshi Idé
IBM Research, Tokyo Research Laboratory
1623-14 Shimo-tsuruma, Yamato-shi, Kanagawa 242-8502, Japan
goodidea@jp.ibm.com
Shinichi Nakajima
Nikon Corporation
201-9 Oaza-Miizugahara, Kumagaya-shi, Saitama 360-8559, Japan
nakajima.s@nikon.co.jp
Jun Sese
Department of Information Science, Ochanomizu University
2-1-1 Otsuka, Bunkyo, Tokyo 112-8610, Japan
sesejun@is.ocha.ac.jp

Abstract
When only a small number of labeled samples are available, supervised dimensionality reduction methods tend to perform poorly because of overﬁtting. In suchcases, unlabeled samples could be useful in improving the performance. In this paper, we propose a semi-supervised dimensionality reduction method which preserves
the global structure of unlabeled samples in addition to separating labeled samples
in diﬀerent classes from each other. The proposed method, which we call SEmisupervised Local Fisher discriminant analysis (SELF), has an analytic form of the
globally optimal solution and it can be computed based on eigen-decomposition. We
show the usefulness of SELF through experiments with benchmark and real-world
document classiﬁcation datasets.

∗

A preliminary version of this paper was previously published in Sugiyama et al. (2008). A
MATLAB implementation of the proposed dimensionality reduction method SELF is available from‘http://sugiyama-www.cs.titech.ac.jp/~sugi/software/SELF’.

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

1

2

Introduction

The goal of dimensionality reduction is to obtain a low-dimensional representation of highdimensional data samples while preserving most of the ‘intrinsic information’ contained in
the original data (Roweis & Saul, 2000; Tenenbaum et al., 2000; Hinton & Salakhutdinov,2006). If dimensionality reduction is carried out appropriately, the compact representationof the data can be used for various tasks such as visualization and classiﬁcation.
In supervised learning scenarios where data samples are accompanied with class labels, Fisher discriminant analysis (FDA) (Fisher, 1936; Fukunaga, 1990) is a populardimensionality reduction method. FDA seeks an embedding transformation such thatthe between-class scatter is maximized and the within-class scatter is minimized. FDA
works very well if the samples in each class follow Gaussian distributions with a sharedcovariance structure. However, FDA tends to give undesired results if the samples ina class form several separate clusters or there are outliers (Fukunaga, 1990). To overcome this drawback, Local FDA (LFDA) has been proposed (Sugiyama, 2007). LFDA
localizes the evaluation of the within-class scatter, and thus works well even when withinclass multimodality or outliers exist. In addition, LFDA overcomes a critical limitationof the original FDA in dimensionality reduction—the dimension of the FDA embedding
space should be less than the number of classes (Fukunaga, 1990), while LFDA does not
suﬀer from this restriction in general. Moreover, LFDA was shown to compare favorablywith other supervised dimensionality reduction methods through experiments (Sugiyama,2007).
However, the performance of LFDA (and all other supervised dimensionality reduction methods) tends to be degraded when only a small number of labeled samples areavailable. Namely, the supervised dimensionality reduction methods tend to ﬁnd embedding spaces which are overﬁtted to the labeled samples. In such cases, it is eﬀective to
make use of unlabeled samples that are often available abundantly—such a setup is calledsemi-supervised learning (Chapelle et al., 2006). Through extensive experiments, it was
shown that principal component analysis (PCA) (Jolliﬀe, 1986), which is an unsupervised
dimensionality reduction method for preserving the global data structure, works moderately well in semi-supervised learning scenarios (see e.g., Chapter 21 of Chapelle et al.,2006).
Although PCA was reported to work well, it may not be the best possible choicein the semi-supervised situation because of its unsupervised nature. In this paper, we
propose an alternative semi-supervised dimensionality reduction method. Our basic idea
is to smoothly bridge LFDA and PCA so that our reliance on the global structure of
unlabeled samples and information brought by (a small number of) labeled samples canbe controlled. We show experimentally that the proposed method, which we refer to as
semi-supervised LFDA (SELF), compares favorably with other methods. Note that SELF
maintains the same computational advantage of LFDA and PCA, i.e., a global solution
can be analytically computed based on eigen-decomposition. Therefore, SELF is still
computationally as eﬃcient as LFDA and PCA.
The rest of this paper is organized as follows. In Section 2, the linear dimensionality

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

3

reduction problem addressed in this paper is formulated and some mathematical facts usedin the following sections are brieﬂy summarized. In Section 3, existing supervised andunsupervised dimensionality reduction methods are reviewed in a systematic and uniﬁed
manner. This uniﬁed view will be the foundation for developing our new method in thefollowing section. Those who are familiar with the existing methods and interested in
immediately looking at the new method may choose to skip the review materials provided
in Section 3. In Section 4, we propose the new semi-supervised dimensionality reduction
method SELF and show its properties. Section 5 is devoted to experiments showing theusefulness of the proposed approach. Finally, in Section 6, we conclude with a discussion
on possible future directions.

2

Preliminaries

In this section, we formulate the linear dimensionality reduction problem and give somemathematical background.

2.1

Formulation

Let xi ∈ Rd (i = 1, 2, . . . , n) be d-dimensional sample vectors and let X ∈ Rd×n be thematrix of all samples:
X := (x1 |x2 | · · · |xn ).
Let z ∈ Rr (1 ≤ r ≤ d) be a low-dimensional representation of a high-dimensional samplex ∈ Rd , where r is the dimensionality of the reduced space. For the moment, we focus
on linear dimensionality reduction, i.e., using a transformation matrix T ∈ Rd×r , anembedded representation z of the sample x is obtained asz = T ⊤ x,
where ⊤ denotes the transpose of a matrix or a vector. Later, we extend our discussion
to cases where the mapping from x to z is non-linear.

2.2

Generalized Eigenvalue Problem

Many dimensionality reduction techniques developed so far involve an optimization problem of the following form:
)]
[ (
(1)
T (OPT) := argmax tr T ⊤ BT (T ⊤ CT )−1 .
T ∈Rd×r

Roughly speaking, B encodes the quantity that we want to increase (e.g., between-classseparability), and C corresponds to the quantity that we want to decrease (e.g., withinclass scatter). In the next section, we show how B and C are designed in some speciﬁc

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

4

cases. Note that the same solution T (OPT) can also be obtained as follows (see e.g.,
Fukunaga, 1990):[ ()]
T (OPT) = argmax tr T ⊤ BT
subject to T ⊤ CT = I r ,
(2)
d×r
T ∈R
[ (
)]
det T ⊤ BT
(OPT)
(
) ,
T
= argmax
det T ⊤ CT
T ∈Rd×r
where I r is the identity matrix on Rr and det(·) denotes the determinant of a matrix.
Let {φk }dk=1 be the generalized eigenvectors associated with the generalized eigenvalues{λk }dk=1 of the following generalized eigenvalue problem:
Bφ = λCφ.

(3)

The generalized eigenvectors are C-orthogonal (Bai et al., 2000), i.e., for k ̸= k ′ ,φ⊤
k Cφk′ = 0.
We assume that the generalized eigenvalues are sorted in descending order as
λ1 ≥ λ2 ≥ · · · ≥ λd ,(4)and the generalized eigenvectors are normalized asφ⊤k Cφk = 1

for k = 1, 2, . . . , d.

(5)Note that this normalization is often carried out automatically by an eigen-solver. Thena solution T (OPT) is analytically given as follows (e.g., Fukunaga, 1990):(φ1 |φ2 | · · · |φr ).
It can be conﬁrmed that Eq.(1) is invariant under linear transformations (Fukunaga,
1990), i.e., for any r-dimensional invertible matrix U , T (OPT) U is also a global solution.
This implies that the range of the embedding space can be uniquely determined by Eq.(1),but the metric in the embedding space is arbitrary. A practically useful heuristic (e.g.,
Sugiyama, 2007) is to set
√
√ √
(6)
U = diag( λ1 , λ2 , . . . , λr ),where diag(a, b, . . . , c) denotes the diagonal matrix with the diagonal elements a, b, . . . , cand we assume that the generalized eigenvalues {λk }dk=1 are non-negative. Then thesolution is given as√√√
T (OPT) = ( λ1 φ1 | λ2 φ2 | · · · | λr φr ).
(7)
Thus, the minor eigenvectors are deemphasized according to the square root of the eigenvalues. We will use this weighted solution in this paper.

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

2.3

5

Pairwise Expression of Scatter Matrices

When addressing dimensionality reduction problems, we are often dealing with a matrix ofthe following pairwise form (Belkin & Niyogi, 2003; Sugiyama, 2007), since it is convenient
to describe the relation between pairs of features regarding whether pairs are close together
or far apart:n1∑
Wi,j (xi − xj )(xi − xj )⊤ ,(8)S :=2 i,j=1
where W is some n × n matrix. Let D be the n × n diagonal matrix with
Di,i :=

n∑

Wi,j ,

j=1

and let L be
L := D − W .
Then the matrix S can be expressed in terms of L as
S=
=

n
∑

Wi,j xi x⊤
i −

i,j=1
n
∑

n
∑

Wi,j xi x⊤
j

i,j=1

⊤
Di,i xi x⊤
i − XW X

i=1=XLX ⊤ .

(9)

If we regard W as a weight matrix for a graph with n nodes, L can be regarded as agraph Laplacian matrix in spectral graph theory (Chung, 1997). If W is symmetric andits elements are all non-negative, L is known to be positive semi-deﬁnite.
In the following, we frequently use the matrices S (·) , W (·) , D (·) , and L(·) . They are
all deﬁned as above.

3

Review of Existing Dimensionality Reduction
Methods

In this section, we review the existing dimensionality reduction methods. Our review
will be in terms of the pairwise expression (8) in a uniﬁed framework. This uniﬁed
formulation facilitates the development of a new method in the following sections. Those
who are familiar with existing methods of supervised and unsupervised dimensionality
reduction and interested in immediately looking at the new method may skip this section
and go directly to Section 4.

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

3.1

6

Principal Component Analysis (PCA)

A fundamental unsupervised dimensionality reduction method is principal component
analysis (PCA) (Jolliﬀe, 1986), which iteratively ﬁnds the maximum-variance directionof the data points. Below, we formulate PCA in a slightly diﬀerent manner based on the
pairwise expression (8).
Let S (t) be the total scatter matrix :
S

(t)

:=

n
∑

(xi − µ)(xi − µ)⊤ ,i=1where µ is the mean of all of the samples:
1∑
µ :=
xi .
n i=1
n

Note that S (t) can be expressed in a pairwise form as
S

(t)

=

n
∑

⊤
xi x⊤
i − nµµ

i=1
n
n
1 ∑
1 ∑
⊤
xi xi −
xi x⊤=j
n i,j=1
n i,j=1

1 ∑ (t)=W (xi − xj )(xi − xj )⊤ ,2 i,j=1 i,jnwhere W (t) is the n × n matrix with(t)

Wi,j :=1.
n

The PCA transformation matrix T (PCA) is deﬁned as)][ (T (PCA) := argmax tr T ⊤ S (t) T (T ⊤ T )−1 .

(10)

(11)

T ∈Rd×r

If we use the equivalent formulation (2), we see that PCA seeks a transformation matrix
T such that the scatter in the embedding space is maximized. A solution T (PCA) is given
by Eqs.(3) and (7) with
B = S (t) and C = I d .

3.2

Locality-Preserving Projection (LPP)

Another useful unsupervised dimensionality reduction technique is locality-preserving projection (LPP) (He & Niyogi, 2004).

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

7

Let A be an aﬃnity matrix, i.e., an n × n matrix with Ai,j being the aﬃnity between
xi and xj . We assume that Ai,j ∈ [0, 1], where Ai,j is large if xi and xj are ‘close’ and Ai,jis small if xi and xj are ‘far apart’. There are several diﬀerent manners of deﬁning A,
such as using the nearest neighbors (Roweis & Saul, 2000) or the heat kernel (Belkin &Niyogi, 2003). In this paper, we use the local scaling heuristic (Zelnik-Manor & Perona,2005) as the deﬁnition of the aﬃnity matrix A, i.e.,()∥xi − xj ∥2
Ai,j = exp −.
σi σj
The parameter σi represents the local scaling around xi deﬁned by(k)

σi := ∥xi − xi ∥,(k)where xi is the k-th nearest neighbor of xi . A heuristic choice of k = 7 was shown to
be useful through experiments (Zelnik-Manor & Perona, 2005; Sugiyama, 2007).
Let S (n) and S (l) be the normalization matrix and the local scatter matrix deﬁned by
S (n) := XD (n) X ⊤ ,n
1 ∑ (l)(l)
S :=W (xi − xj )(xi − xj )⊤ ,2 i,j=1 i,jwhere D (n) is the n × n diagonal matrix withn1∑
(n)Di,i :=
Ai,j ,
n j=1
and W (l) is the n × n matrix with
1
Ai,j .
n
The LPP transformation matrix T (LP P ) is deﬁned as[ ()](LP P )
⊤ (l)
⊤ (n)
−1
T
:= argmin tr T S T (T S T ).
(l)Wi,j :=

T ∈Rd×r

Taking into account the equivalence between Eqs.(1) and (2), we see that LPP seeks atransformation matrix T such that nearby data pairs in the original space Rd are kept closein the embedding space Rr (with (T ⊤ S (n) T )−1 regarded as a normalization constraint).
Thus, LPP tends to preserve the local structures of the data.
As shown above, LPP is formulated as a minimization problem. To make this consistent with the other methods reviewed here, let us consider an inverted version of LPP.
)]
[ (T (iLPP) := argmax tr T ⊤ S (n) T (T ⊤ S (l) T )−1 .
T ∈Rd×r

When S (n) is an identity, the inverted LPP (iLPP) agrees with the original LPP according
to Eq.(3); otherwise the iLPP solution may be diﬀerent from that of the original LPP.
A solution T (iLPP) is given by Eqs.(3) and (7) with
B = S (n) and C = S (l) .

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

3.3

8

Fisher Discriminant Analysis (FDA) for Dimensionality Reduction

Fisher discriminant analysis (FDA) is a popular supervised dimensionality reduction
technique (Fisher, 1936; Fukunaga, 1990). When discussing supervised learning problems,′
we suppose that we have n′ labeled samples {(xi , yi )}ni=1 , where yi ∈ {1, 2, . . . , c} is a classlabel associated with the sample xi and c is the number of classes. Let n′m be the numberof labeled samples in class m ∈ {1, 2, . . . , c}:
n′ =

c
∑

n′m .

m=1

Let S (b) and S (w) be the between-class scatter matrix and the within-class scatter
matrix :c∑S (b) :=
n′m (µm − µ)(µm − µ)⊤ ,S (w) :=
∑

m=1
c
∑

∑

(xi − µm )(xi − µm )⊤ ,m=1 i:yi =mwhere i:yi =m indicates the summation over i such that yi = m and µm is the mean ofsamples in class m:
1 ∑µm := ′xi .
nm i:y =mi

The FDA transformation matrix T(FDA)

is deﬁned as[ ()]
T (FDA) := argmax tr T ⊤ S (b) T (T ⊤ S (w) T )−1 .
T ∈Rd×r

That is, FDA seeks a transformation matrix T such that the between-class scatter inthe embedding space (i.e., T ⊤ S (b) T ) is ‘maximized’ and the within-class scatter in theembedding space (i.e., T ⊤ S (w) T ) is ‘minimized’. A solution T (FDA) is given by Eqs.(3)and (7) with
B = S (b) and C = S (w) .
It is known (e.g., Fukunaga, 1990) that S (b) and S (w) are related to the total scatter
matrix S (t) as
S (t) = S (b) + S (w) .
(12)This can also be conﬁrmed from the fact that S (b) and S (w) are expressed in the pairwise
form (8) with the following weight matrices (Sugiyama, 2007):{
1/n′ − 1/n′yi if yi = yj ,(b)Wi,j :=
1/n′
if yi ̸= yj ,{1/n′yi if yi = yj ,(w)
Wi,j :=
0if yi ̸= yj ,

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

9

where n′yi denotes the number of labeled samples in class yi ∈ {1, 2, . . . , c}. In this case,
we have
W (t) = W (b) + W (w) ,since Wi,j := 1/n′ in the current setup (cf. Eq.(10)).
The between-class scatter matrix S (b) has at most rank c − 1 (Fukunaga, 1990). Thisimplies that FDA allows us to obtain at most c − 1 meaningful features (or equivalently
the dimensionality r of the embedding space should be at most c − 1), and the remaining
features found by FDA are arbitrary in the null space of S (b) . This is an essential limitationof FDA in dimensionality reduction.
(t)

3.4

Local Fisher Discriminant Analysis (LFDA)

Local Fisher Discriminant Analysis (LFDA) is a supervised dimensionality reduction
method (Sugiyama, 2007) which overcomes the weakness of the original FDA against
within-class multimodality or outliers (Fukunaga, 1990).
Let S (lb) and S (lw) be the local between-class scatter matrix and the local within-classscatter matrix deﬁned by
n′

S

(lb)

1 ∑ (lb):=
W (xi − xj )(xi − xj )⊤ ,2 i,j=1 i,jn′

1 ∑ (lw)
S (lw) :=W (xi − xj )(xi − xj )⊤ ,2 i,j=1 i,jwhere W (lb) and W (lw) are the n′ × n′ matrices with{
Ai,j (1/n′ − 1/n′yi ) if yi = yj ,(lb)Wi,j :=
1/n′
if yi ̸= yj ,{Ai,j /n′yi if yi = yj ,(lw)
Wi,j :=
0if yi ̸= yj .

(13)
(14)

Ai,j is the aﬃnity value between xi and xj based on the local scaling heuristic (see Section 3.2). Note that the local scaling is computed in a classwise manner in LFDA since wewant to preserve the within-class local structure (Sugiyama, 2007). This also contributes
to reducing the computational cost for nearest neighbor search when computing the local
scaling. The LFDA transformation matrix T (LFDA) is deﬁned as)][ (T (LFDA) := argmax tr T ⊤ S (lb) T (T ⊤ S (lw) T )−1 .
T ∈Rd×r

In other words, LFDA seeks a transformation matrix T such that the local between-classscatter in the embedding space (i.e., T ⊤ S (lb) T ) is ‘maximized’ and the local within-classscatter in the embedding space (i.e., T ⊤ S (lw) T ) is ‘minimized’.

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

10

In Eqs.(13) and (14), Ai,j (1/n′ −1/n′yi ) is negative while Ai,j /n′yi and 1/n′ are positive.
Thus LFDA imposes nearby data pairs in the same class to be close together and the data
pairs in diﬀerent classes to be far apart; far apart data pairs within the same class are notimposed to be close together. Samples in diﬀerent classes are separated from each otherirrespective of their aﬃnity values. A solution T (LFDA) is given by Eqs.(3) and (7) with
B = S (lb) and C = S (lw) .
When Ai,j = 1 for all i, j (i.e., no locality), S (lw) and S (lb) are reduced to S (w) andS (b) . Thus, LFDA can be regarded as a localized variant of FDA. The between-classscatter matrix S (b) has at most rank c − 1, while its local counterpart S (lb) usually has
full rank (given n′ ≥ d). Therefore, LFDA can be applied to dimensionality reduction
into spaces of any dimension, which is also a signiﬁcant advantage over the original FDA
when the number of classes is small.
However, the performance of LFDA (and all other supervised dimensionality reduction
methods) tends to be degraded if only a small number of labeled samples are available.
The purpose of this paper is to give a new method that can overcome this weakness.

4

Semi-Supervised LFDA (SELF)

In this section, we propose a new dimensionality reduction method for semi-supervised
learning scenarios. From here on, we consider the case where, among all of the samples′{xi }ni=1 , only {xi }ni=1 (1 ≤ n′ ≤ n) are labeled and the rest are unlabeled.

4.1

Basic Idea

When only a small number of labeled samples are available, supervised dimensionality
reduction methods tend to ﬁnd the embedding spaces overﬁtted to the labeled samples.
In such situations, the use of unlabeled samples can mitigate this problem—indeed, in
Chapter 21 of Chapelle et al. (2006), it was shown through extensive experiments that
PCA works well on the whole. Our experimental results in Section 5.1 also show that
PCA is sometimes better than LFDA. This means that preserving the global structureof all of the samples in an unsupervised manner can be better than relying too much onclass information provided by a small number of labeled samples.
Figure 1 depicts 2-dimensional 2-class examples. The circles and triangles denotethe samples in positive and negative classes and the ﬁlled or unﬁlled symbols denotethe labeled or unlabeled samples. The solid and dashed lines denote the 1-dimensional
embedding spaces (onto which the data samples will be projected) found by LFDA and
PCA, respectively.
For the dataset in Figure 1(a), both LFDA and PCA can ﬁnd good embedding spaces
which clearly separate unlabeled samples in diﬀerent classes from each other. However,for the dataset in Figure 1(b), which contains the same sample points as (a) but in which
the choice of the labeled samples is diﬀerent, LFDA ﬁnds an embedding space that isSemi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

10

10

LFDA
PCA

8

8

6

6

4

4

2

2

0

0

−2

−2

−4

−4

−6

−6

−8

−8

−10
−10

−5

0

5

LFDA
PCA

−10
−10

10

11

−5

(a)

0

5

10

(b)
10

LFDA
PCA

8
6
4
2
0
−2
−4
−6
−8
−10
−10

−5

0

5

10

(c)
Figure 1: Illustrative examples of LFDA and PCA for toy datasets. The circles andtriangles denote the samples in positive and negative classes and the ﬁlled or unﬁlled
symbols denote the labeled or unlabeled samples. The solid and dashed lines denote the1-dimensional embedding spaces (onto which the data samples will be projected) foundby LFDA and PCA, respectively. The dataset is common to (a) and (b), but the choice oflabeled samples is diﬀerent. This only aﬀects the LFDA solution because of its supervised
nature; the PCA solution does not change because of its unsupervised nature. The choiceof labeled samples is common to (a) and (c), but the vertical scaling of the data is doubledin (c). This aﬀects both the LFDA and PCA solutions, but the PCA solution is moreinﬂuenced because of its unsupervised nature.

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

12

overﬁtted to the labeled samples. Note that the choice of labeled samples only aﬀects the
LFDA solution—the PCA solution does not change because of its unsupervised nature.
This illustrates a possible drawback of LFDA which relies strongly on a small number oflabeled samples.
The dataset described in Figure 1(c) has the same choice of labeled samples as (a),but the vertical scaling of the data is doubled. Although this change of scales aﬀects
both the LFDA and PCA solutions, LFDA is not strongly inﬂuenced by the change ofscales because of its supervised nature. In contrast, PCA is signiﬁcantly inﬂuenced by
the change of scales and does not work well for the dataset (c). This illustrates a possible
weakness of PCA arising from its unsupervised nature.
The above result shows that LFDA and PCA have their own drawbacks. However,
the above result also implies that LFDA and PCA can compensate for each other’s weaknesses, i.e., LFDA can utilize label information, while PCA can avoid overﬁtting. Our
experimental results with the benchmark datasets in Section 5.1 also show that LFDA andPCA tend to work in a complementary manner. Motivated by these facts, we propose tobridge LFDA and PCA so that our reliance on the global structure of unlabeled samples
and class information brought by the labeled samples can be smoothly controlled. We
refer to the proposed method as semi-supervised LFDA (SELF).
The embedding transformations of LFDA and PCA can be analytically computed
through eigen-decomposition, as reviewed in the previous section. Based on this fact, we
combine the eigenvalue problems of LFDA and PCA and solve them together. This allows
us to retain the computational eﬃciency of LFDA and PCA.
As described in Section 3.4, LFDA includes FDA as a special case. Therefore, the ideaof combining LFDA and PCA detailed below is also applicable to FDA.

4.2

Definition

More speciﬁcally, we propose to solve the following generalized eigenvalue problem:
S (rlb) φ = λS (rlw) φ,(15)

where S (rlb) and S (rlw) are the regularized local between-class scatter matrix and theregularized local within-class scatter matrix deﬁned by
S (rlb) := (1 − β)S (lb) + βS (t) ,
S

(rlw)

:= (1 − β)S(lw)+ βI d .

(16)
(17)

β ∈ [0, 1] is a trade-oﬀ parameter—SELF is reduced to LFDA when β = 0 and SELF isreduced to PCA when β = 1. In general, SELF with 0 < β < 1 inherits the characteristics
of both LFDA and PCA (discussed in detail in Section 4.3). One may use diﬀerent tradeoﬀ parameters in S (rlb) and S (rlw) to increase the ﬂexibility. However, this in turn makes
the trade-oﬀ parameter choice laborious. For this reason, we focus on using the single
shared trade-oﬀ parameter β for S (rlb) and S (rlw) below.

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

13

The optimization problem of SELF is expressed as[ ()]
T (SELF) := argmax tr T ⊤ S (rlb) T (T ⊤ S (rlw) T )−1 .
T ∈Rd×r

In other words, SELF seeks a transformation matrix T such that the regularized local
between-class scatter in the embedding space (i.e., T ⊤ S (rlb) T ) is ‘maximized’ and theregularized local within-class scatter in the embedding space (i.e., T ⊤ S (rlw) T ) is ‘minimized’. Since this optimization problem is the same form as LFDA and PCA, a solution
T (SELF) can be computed as√√√
T (SELF) = ( λ1 φ1 | λ2 φ2 | · · · | λr φr ),(18)
where {φk }dk=1 are the generalized eigenvectors of Eq.(15) associated with the generalized
eigenvalues {λk }dk=1 . We assume that {λk }dk=1 are sorted in descending order as in Eq.(4)and {φk }dk=1 are normalized as in Eq.(5). In Section 4.3, we will prove that all thegeneralized eigenvalues are non-negative, which guarantees that the solution (18) is always
valid.
In the original LFDA, the nearest neighbor search (involved in the computation of
local scaling σi in the aﬃnity matrix A) is carried out in a classwise manner (Sugiyama,2007). On the other hand, in SELF, we determine the local scaling using all of the samples{xi }ni=1 since the number of labeled samples is typically small in semi-supervised learning.
SELF requires aﬃnity values Ai,j only for the pairs of labeled samples in the same class.
This means that we need to compute local scaling values only for the labeled samples andaﬃnity values only for the labeled sample pairs in the same class. This contributes greatly
to reducing the computational costs. The total scatter matrix S (t) in the original PCA
is computed for unlabeled samples, but we use all of the samples {xi }ni=1 (i.e., both thelabeled and unlabeled samples) in SELF. The pseudo-code for SELF appears in Figure 2.

4.3

Properties

First, we give an interpretation of S (rlb) . The matrix S (rlb) can be expressed in a pairwise
form asn
1 ∑ (rlb)
(rlb)
S
:=
Wi,j (xi − xj )(xi − xj )⊤ ,(19)
2 i,j=1
where W (rlb) is the n × n matrix with′′
 (1 − β)Ai,j (1/n − 1/nyi ) + β/n if yi = yj ,(rlb)
(1 − β)/n′ + β/nif yi ̸= yj ,Wi,j :=

β/notherwise.
The ﬁrst case in Eq.(20) is negative if
β < Bi,j ,(20)

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

Input:

Output:14′

Labeled samples {(xi , yi ) | xi ∈ Rd , yi ∈ {1, 2, . . . , c}}ni=1
Unlabeled samples {xi | xi ∈ Rd }ni=n′ +1
Dimensionality of embedding space r (1 ≤ r ≤ d)
Trade-oﬀ parameter β (0 ≤ β ≤ 1)
d × r transformation matrix T (SELF)

for i = 1, 2, . . . , n′(7)xi ←− 7th nearest neighbor of xi among {xj }nj=1 ;(7)
σi ←− ∥xi − xi ∥;end
for i, j = 1, 2, . . . , n′if yi = yj
Ai,j ←− exp(−∥xi − xj ∥2 /(σi σj ));(lb′ )
Wi,j ←− Ai,j (1/n′ − 1/n′yi );(lw′ )
Wi,j ←− Ai,j /n′yi ;else(lb′ )
Wi,j ←− 1/n′ ;(lw′ )
Wi,j ←− 0;endend
X ′ ←− (x1 |x{2 | · · · |xn′ );}′′S (lb) ←− X ′ diag(W (lb ) 1n′ ) − W (lb ) X ′⊤ ;{}′′S (lw) ←− X ′ diag(W (lw ) 1n′ ) − W (lw ) X ′⊤ ;X ←− (x1 |x2 | · · · |xn );µ ←− X1n /n;S (t) ←− XX ⊤ − nµµ⊤ ;S (rlb) ←− (1 − β)S (lb) + βS (t) ;S (rlw) ←− (1 − β)S (lw) + βI d ;{λk , φk }rk=1 ←− Generalized eigenvalues and eigenvectors of S (rlb) φ = λS (rlw) φ,(rlw)
where λ1 ≥ λ2 ≥ · · · ≥ λd and φ⊤
φk = 1;kS√√√(SELF)T= ( λ1 φ1 | λ2 φ2 | · · · | λr φr );Figure 2: Pseudo-code for SELF. 1n denotes the n-dimensional vector withones and diag(w) denotes the diagonal matrix with the diagonal elements speciﬁed by a vector w.
A MATLAB implementation of SELF is available from‘http://sugiyama-www.cs.titech.ac.jp/~sugi/software/SELF’.

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

whereBi,j :=

15

Ai,j n(n′ − n′yi ).
Ai,j n(n′ − n′yi ) + n′ n′yiNote that 0 ≤ Bi,j < 1. This implies that SELF tries to make sample pairs in the sameclass close together if β is smaller than Bi,j , while it separates them farther from eachother if β is larger than Bi,j . Thus the local data structures in the same class tend to bepreserved when β is small, but are no longer preserved when β is large. Bi,j is reduced
when Ai,j is increased, so Bi,j is smallest in the case of FDA where Ai,j = 1 for all i, j.
The second case in Eq.(20) is always positive for any β ∈ [0, 1], implying that SELF
always tries to make sample pairs in diﬀerent classes farther apart for any β. This would
be natural in (semi-)supervised learning scenarios. The third case in Eq.(20) is always
non-negative, implying that unlabeled samples are separated from each other to preserve
the global data structure.
S (rlb) includes the total scatter matrix S (t) (see Eq.(16)), which is equivalent to thesum of S (b) and S (w) (see Eq.(12)). If samples in diﬀerent classes were highly localized
and clearly separated from each other, S (b) would be dominant in S (t) and thus S (t)and S (b) would be similar to each other. However, since S (b) needs to be computedfrom a small number of labeled samples in semi-supervised learning, it is often unreliable.
In contrast, S (t) can be computed in a more reliable manner using a large number of
unlabeled samples1 . For this reason, including S (t) in S (rlb) will improve the reliability ofthe solution.
Next, we give an interpretation of S (rlw) . When β = 0, S (rlw) (= S (lw) ) could be illconditioned. This is particularly crucial when the dimension d of the original data spaceis larger than the number n′ of labeled samples. In such situations, βI d included in S (rlw)(see Eq.(17)) works as a regularizer and SELF can avoid overﬁtting the labeled samples(cf. Friedman, 1989; Mika et al., 2003). Therefore, SELF is regarded as a regularizedvariant of LFDA and would be more stable and more reliable than the original LFDA,
particularly when the number of labeled samples is small. Note that unlike Eq.(19), S (rlw)does not have a pairwise expression since I d cannot be expressed in a pairwise form.
Finally, we investigate the positive (semi-)deﬁniteness of S (rlb) and S (rlw) . Let
W (∆lb) = W (lb) − W (b) ,which means that W (∆lb) is the n × n matrix with{
(Ai,j − 1)(1/n′ − 1/n′yi ) if yi = yj ,(∆lb)
Wi,j :=
0otherwise.
Note that (Ai,j − 1)(1/n′ − 1/n′yi ) is non-negative. Then taking into account the relation(9), we can express S (lb) as
S (lb) = S (b) + XL(∆lb) X ⊤ ,1This may partially explain why PCA is useful under the cluster assumption—samples in the samecluster are likely to have a common label (Chapelle et al., 2006).

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

16

where L(∆lb) is deﬁned with W (∆lb) (see Section 2.3). Since S (b) and L(∆lb) are both symmetric positive semi-deﬁnite, S (lb) is also symmetric positive semi-deﬁnite. In addition,
since S (t) is symmetric positive semi-deﬁnite and β and 1 − β are non-negative, S (rlb)
is also symmetric positive semi-deﬁnite (see Eq.(16)). On the other hand, since S (lw) issymmetric positive semi-deﬁnite and I d is symmetric positive deﬁnite, S (rlw) is symmetricpositive deﬁnite if β > 0. The facts that S (rlb) is symmetric positive semi-deﬁnite and
S (rlw) is symmetric positive deﬁnite guarantee that the generalized eigenvalues of Eq.(15)
are non-negative (Bai et al., 2000). Thus, the solution (18) is always valid.

4.4

Numerical Examples

To illustrate how SELF behaves, we used the Olivetti face dataset2 . The dataset consistsof 400 gray-scale images of faces (40 people, 10 images per person). Each image consistsof 4096 (= 64 × 64) pixels and each pixel takes an integer value between 0 and 255 as theintensity level. In this experiment, we used the image samples of only 10 subjects (i.e.,
100 images in total) to make the visualization results clear. We experimentally conﬁrmedthat the results do not change signiﬁcantly (though points are more overlapped) when all
400 images are used.
Among the 10 people used for the experiments, 3 subjects are wearing glasses andthe other 7 subjects are without glasses (see Figure 3(a)). Our task was to embed theface images into a two-dimensional space so that the subjects with and without glasses
were separated from each other. We labeled 1 image per person (so 3 faces are labeled aswith glasses and 7 faces as without glasses in total) and the rest are treated as unlabeled.
Since each class contains several diﬀerent subjects, this dataset is thought to possess
within-class multimodality.
The embedded results are depicted in Figure 3, where the circles and triangles denotethe faces with or without glasses and the ﬁlled or unﬁlled symbols denote the labeled
or unlabeled samples. The ﬁgure shows that FDA and LFDA perfectly separate thelabeled samples in the two classes from each other. However, the unlabeled samples tend
to be mixed because of an overﬁtting phenomenon. PCA and iLPP tend to mix thelabeled samples in diﬀerent classes because of their unsupervised natures. As a result,the unlabeled samples in diﬀerent classes are also mixed. In contrast, SELF with β = 0.5
clearly separates the labeled samples in the two classes from each other, and at the sametime, it also eﬀectively separates the unlabeled samples in the two classes. We note that,in this visualization experiment, the result of SELF is not sensitive to the choice of the
trade-oﬀ parameter β. The results are almost unchanged for 0.01 ≤ β ≤ 0.99.

4.5

Discussion

Here we discuss several issues related to SELF.

2

The dataset is available from ‘http://www.cs.toronto.edu/~roweis/data.html’.

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction(a) Olivetti face dataset(b) FDA(c) LFDA(d) PCA(e) iLPP(f) SELF (β = 0.5)

17

Figure 3: Embedded face samples (glasses vs. non-glasses). The circles and triangles are
the faces with or without glasses and the ﬁlled or unﬁlled symbols are the labeled or
unlabeled samples. In the plots of FDA, LFDA, and SELF, all the labeled points in thesame class are concentrated in one point.

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

4.5.1

18

Combination of LFDA and iLPP

Semi-supervised learning is regarded as a situation between supervised learning and unsupervised learning. Similarly, SELF may also be interpreted as a dimensionality reduction
method between supervised and unsupervised methods. This implies that our choice does
not have to be restricted to LFDA and PCA—other powerful supervised and unsupervised methods could also be combined in a similar manner. Sugiyama (2007) showedthat LFDA is a useful supervised dimensionality reduction method through experiments,
so the use of LFDA in the semi-supervised dimensionality reduction method would bereasonable.
On the other hand, the performance of an unsupervised dimensionality reduction
method is heavily dependent on label distributions. Clearly there are situations where
PCA performs poorly (as in Figure 1(c)). An alternative choice of the unsupervisedcounterpart would be iLPP (see Section 3.2), which results in
B = (1 − β)S (lb) + βS (n) ,C = (1 − β)S (lw) + βS (l) .
Although this variant is still computationally as eﬃcient as the original SELF, the combination of LFDA and iLPP was shown to be less useful in our experiments (see Section 5.1).
This was because the global data structure is not taken into account. That is, iLPP tries
to make samples in the same cluster close together, but it does not impose diﬀerent clusters to be separated from each other. Therefore, several clusters may merge without any
penalties and iLPP may lose the global cluster structure.
We also tested a combination of three methods—LFDA, PCA, and iLPP—with two
trade-oﬀ parameters, but this did not improve the performance over the original SELF.
4.5.2

Distance Metric Learning

The performance of distance-based learning methods such as nearest neighbor classiﬁers
depends heavily on the deﬁnition of the distances between samples. The idea of distancemetric learning is to optimize a metric M used for computing the distances between
samples (Xing et al., 2003; Goldberger et al., 2005; Globerson & Roweis, 2006; Weinberger
et al., 2006):
dist(xi , xj ; M ) = (xi − xj )⊤ M (xi − xj ).
By deﬁnition, the metric matrix M is symmetric and positive semi-deﬁnite. For thisreason, metric learning is typically formulated as a semi-deﬁnite programming problem,
which is a convex optimization problem for which the unique global solution can beobtained (Boyd & Vandenberghe, 2004; Weinberger et al., 2006).
If the rank of the d×d matrix M is constrained to r, then the distance metric learning
methods are automatically causing implicit dimensionality reduction. More speciﬁcally,
the symmetricity and positive semi-deﬁniteness of the metric matrix M implies that M
can be decomposed as
M = T T ⊤,

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

19

where T is a d × r matrix. Then T ⊤ xi could be regarded as an explicit expressionof a sample xi after dimensionality reduction. However, simultaneously reducing thedimensionality of samples and learning the distance metric is usually hard since the rank
constraint is non-convex (Boyd & Vandenberghe, 2004). Thus it may not be possible toobtain the global optimal solution.
In contrast, our approach to dimensionality reduction is formulated by Eq.(1), which
is not convex but which still allows us to access the global solution in terms of the rangeof the embedding space. This means that we can obtain the unique solution for the metricmatrix by combining SELF (or any other dimensionality reduction method formulated by
Eq.(1)) with a convex metric learning method (such as Weinberger et al., 2006). That is,a two-stage procedure of ﬁrst reducing the dimensionality (i.e., determining the range ofthe embedding space) with SELF and then learning the metric in the embedding space
without the rank constraint. We expect that this procedure is practically useful.
4.5.3

Kernelization

So far, we focused on linear dimensionality reduction. Using the standard kernel trick(Schölkopf et al., 1998), we can easily obtain a non-linear variant of SELF.
Let
L(rlw) = (1 − β)L(lw) + β(X ⊤ X)† ,where † denotes the Moore-Penrose generalized inverse (Albert, 1972). Recalling thatS = XLX ⊤ (see Eq.(9)), we can express the eigenvalue problem solved in SELF as
XL(rlb) X ⊤ φ = λXL(rlw) X ⊤ φ.

(21)

In the derivation of this expression, we used the fact that I d in Eq.(17) can be replacedwith a projection matrix X(X ⊤ X)† X ⊤ without essentially changing the solution when
X ⊤ X is not invertible.
Since X ⊤ φ in Eq.(21) belongs to the range of X ⊤ , it can be expressed by using some
vector α ∈ Rn as follows3 :X ⊤ φ = X ⊤ Xα = Kα,
where K is the n × n matrix with
Ki,j := x⊤i xj .
Then multiplying Eq.(21) by X ⊤ from the left-hand side yields
KL(rlb) Kα = λKL(rlw) Kα.
Note that one of the properties of the Moore-Penrose generalized inverse implies that
KL(rlw) K can be simply computed as
KL(rlw) K = (1 − β)KL(lw) K + βK.
3Here, we are not equating φ with Xα, but we equate X ⊤ φ with X ⊤ Xα.

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

20

When KL(rlw) K is not of full rank, we may need to regularize it (Schölkopf et al.,1998), i.e., for a small positive scalar ϵ, we replace (21) with
KL(rlb) Kα = λ(KL(rlw) K + ϵI n )α.

(22)

Let {αk }dk=1 be the generalized eigenvectors associated with the generalized eigenvalues{λk }dk=1 of Eq.(22), where they are sorted and normalized as
λ1 ≥ λ2 ≥ · · · ≥ λd
and

(rlw)
K + ϵI n )αk = 1
α⊤
k (KL

for k = 1, 2, . . . , d.

Then the embedded representation z of an original sample x can be computed in termsof {αk }rk=1 as
√
√
√
⊤
⊤
⊤
z = ( λ1 α1 | λ2 α2 | · · · | λr αr )⊤ (x⊤1 x, x2 x, . . . , xn x) .
This implies that the data samples appear only via their inner products. We note thatthe aﬃnity values as well as the local scaling can also be computed in terms of the innerproducts between data samples. Therefore, if the inner product x⊤
i xj is replaced by areproducing kernel K(xi , xj ) (Aronszajn, 1950), we can obtain a non-linear variant of
SELF—linear dimensionality reduction is carried out in an implicit kernel feature space(Schölkopf et al., 1998).
Beyond non-linearization, kernel SELF is also useful in the following two scenarios.
The ﬁrst is that the kernelized variant also allows us to reduce the dimensionality of nonvectorial structured data such as strings, trees, and graphs by employing kernel functions
deﬁned for such structured data (Lodhi et al., 2002; Duﬀy & Collins, 2002; Kashima &Koyanagi, 2002; Kondor & Laﬀerty, 2002; Kashima et al., 2003; Gärtner et al., 2003;
Gärtner, 2003).
Another possible usage of the kernel formulation would be for computational eﬃciency.
The size of matrices to be eigen-decomposed in the kernel formulation depends only on thenumber of samples, not on the input dimensionality. Thus when the number of samples issmaller than the input dimensionality, using the kernel formulation with the linear kernel
could be more eﬃcient in terms of both computation time and memory space consumption
than the original formulation (see also Section 5.2).

5Experiments

In this section, we experimentally evaluate the performance of SELF and other dimensionality reduction methods using standard classiﬁcation benchmark datasets.

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

5.1

21

Benchmark Datasets

In Chapter 21 of Chapelle et al. (2006), systematic experiments were conducted for comparing various semi-supervised learning methods. The results showed that each method
performs very well for a particular type of dataset, but at the same time, it tends to bepoor for other kinds of datasets. Thus, the performance of semi-supervised learning methods is highly dependent on the types of the datasets and there seems to be no single best
method. In contrast, although it may not be the best possible method in semi-supervisedclassiﬁcation, the 1-nearest neighbor classiﬁer has been shown to perform reasonably wellacross various datasets. In order to avoid any bias caused by the choice of the learning
methods, we decided to use the 1-nearest neighbor classiﬁer in our experiments.
The misclassiﬁcation rate is sometimes monotonically decreasing as the dimensionality
is reduced4 (see Figure 4). In such cases, if the best dimensionality is chosen (e.g., by crossvalidation), the largest dimension is mostly chosen (i.e., no dimensionality reduction).
Then we may not be able to compare the performance of the dimensionality reduction
methods in a meaningful way. Fixing the reduced dimensionality r to some numberin advance would be a possible option for avoiding this comparison problem, but theevaluation results can strongly depend on the choice of the dimensionality. For thisreason, we decided to use the average misclassiﬁcation rate over the reduced dimensions(or equivalently the area under the classiﬁcation error curve) as our error metric, which
we believe to be reasonable in the current experiments.
First we use the benchmark datasets used in Chapelle et al. (2006), which consistof 9 semi-supervised learning datasets5 . We refer to them as the SSL datasets. We did
not test the SSL8 and SSL9 datasets since the SSL8 dataset contains too many samples(n is over one million) and the SSL9 dataset has too many dimensions (d is over ten
thousand). The SSL6 dataset contains 6 classes, while the other datasets have 2 classes.
Table 1 describes the means and standard deviations of the misclassiﬁcation rates over
12 repetitions. Since we encountered a numerical problem when computing LFDA, weslightly regularized it and treat SELF with β = 0.001 as LFDA.
The cluster assumption that the samples in the same cluster are likely to have thecommon label is often regarded as an important assumption for the success of semisupervised classiﬁcation (Chapelle et al., 2006). We roughly evaluated the correctness ofthe cluster assumption (denoted as ‘CA’ in Table 1) by the correct classiﬁcation rate of all
the training and test samples using the 1-nearest-neighbor classiﬁer (the cases in which thelabel of the target point is correctly predicted by the label of the nearest sample). Notethat CA is computed before the dimensionality reduction, so it represents the correctnessof the cluster assumption for the original data samples. The larger the value of CA is,
the more reliable the cluster assumption becomes.
When the number of labeled samples is 100 (see the upper half of Table 1), LFDA andPCA tend to work well in a complementary way—LFDA works well if CA is small while
4

Even so, dimensionality reduction is still useful since a compact representation of the data can yield
faster computation in the test phase.
5
The datasets are available from ‘http://www.kyb.tuebingen.mpg.de/ssl-book/’.

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

22

PCA works well if CA is large6 . ‘SELF(0.5)’ (SELF with β = 0.5) tends to compensate forthe weaknesses of each method. It even outperforms both LFDA and PCA in some cases.
We also tested ‘SELF(CV)’, where β in SELF is chosen from {0.001, 0.25, 0.5, 0.75, 1}
by using 10-fold cross-validation. The results in Table 1 show that SELF(CV) further
improves the performance over SELF(0.5). These results also show that iLPP does notwork so well. The combination of LFDA and iLPP (indicated by SELF’(CV) in thetable) also does not perform as well as SELF(CV). We also tested the combination of
LFDA, PCA, and iLPP with two trade-oﬀ parameters, but this did not further improve
the performance over SELF, so we omit these details.
Figure 4 depicts the mean misclassiﬁcation rates as a function of the reduced dimensionality for LFDA, PCA, and SELF(CV). This also shows that LFDA and PCA tend towork well in a complementary way and SELF(CV) tends to compensate for the weaknessesof each method. We note that the curves are almost ﬂat for large dimensions since minor
eigenvectors are deemphasized according to the square root of eigenvalues (see Eq.(7)).
When the number of labeled samples is only 10 (see the lower half of Table 1), theperformance diﬀerences among the methods shrink but SELF(CV) is still slightly better
than the other methods.
We also conducted similar experiments using the IDA datasets7 (Rätsch et al., 2001),
which consist of supervised classiﬁcation tasks. We randomly extracted labeled and unlabeled samples from the pool of all samples, testing n′ = 100 and 30. The results are
summarized in Table 2, showing that SELF(CV) still compares favorably with the alternative methods. From these results, we demonstrated that SELF(CV) performs reasonably
well across various datasets.

5.2

Document Classification

Here, we apply the proposed dimensionality technique, SELF, to real-world documentclassiﬁcation tasks and evaluate its performance. We used the datasets in the Technion
Repository of Text Categorization 8 (TechTC; Davidov et al., 2004). The TechTC repository contains 295 binary document classiﬁcation tasks. Each task contains a few hundred
documents with category labels and a document is expressed by a bag-of-words vector ofterm frequencies, which has an entry in the vector corresponding to each word in the dictionary and its number of occurrences in the document. Following convention (Joachims,
2002), we multiply the term frequency by the logarithm of the inverse ratio of the documents containing the corresponding word. The feature vectors constructed in this way
is called the term frequency-inverse document frequency (TFIDF) vector and TFIDF is
widely used as a standard feature extraction scheme in the document analysis community.
6

The success of PCA depends, of course, on the scaling of the data (see Figure 1 again). However, for
the SSL datasets, it was shown through extensive experiments that PCA works well on the whole (seeChapter 21 of Chapelle et al., 2006). This implies that the scaling of the data is well-conditioned for
PCA in the SSL datasets.
7
The datasets are available from ‘http://ida.first.fhg.de/projects/bench/benchmarks.htm’.
8
The datasets are available from ‘http://techtc.cs.technion.ac.il/techtc300/techtc300.html’.

0.16

0.3

0.14

0.25

0.12

LFDA
PCA

0.1

SELF(CV)
0.08

Missclassification rate

Missclassification rate

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

0.2

0.15

0.1

0.06
0.04

50

0.05

100
150
200
Reduced dimensionality r

2350(a) SSL1

100
150
200
Reduced dimensionality r(b) SSL20.5

0.5

Missclassification rate

Missclassification rate

0.45
0.4
0.35
0.3
0.25
0.2

0.4

0.35

0.15
0.1

0.45

50

100
150
200
Reduced dimensionality r

20

0.32

0.6

0.3

0.55

0.28
0.26
0.24
0.22
0.2
0.18
0.16

100

(d) SSL4
Missclassification rate

Missclassification rate(c) SSL3406080Reduced dimensionality r

0.5
0.45
0.4
0.35
0.3
0.25

50

0.2

100
150
200
Reduced dimensionality r50(e) SSL5

100
150
200
Reduced dimensionality r(f) SSL6

Missclassification rate

0.45

0.4

0.35

0.3

0.25

0.2

50

100
150
200
Reduced dimensionality r(g) SSL7
Figure 4: Mean misclassiﬁcation rates for the SSL datasets as a function of the reduced
dimensionality r when n = 100.

1490
1490
1490
390
1490
1490
1490

12
12
12
12
12
12
12

241
241
241
117
241
241
241

SSL1
SSL2
SSL3
SSL4
SSL5
SSL6
SSL7
# Bests

10
10
10
10
10
10
10

Dim Lab Unlab Rep
241 100 1400 12
241 100 1400 12
241 100 1400 12
117 100
300 12
241 100 1400 12
241 100 1400 12
241 100 1400 12

Data
SSL1
SSL2
SSL3
SSL4
SSL5
SSL6
SSL7
# Bests
0.98
0.97
1.00
0.58
0.64
0.98
0.68

CA
0.98
0.97
1.00
0.58
0.64
0.98
0.68

22.9 (5.1)
22.3 (3.0)
42.7 (2.9)
47.3 (2.9)
45.4 (4.4)
67.7 (4.6)
43.6 (5.2)
5

LFDA
14.9 (1.8)
15.7 (0.9)
21.1 (3.9)
33.4 (3.5)
27.5 (2.3)
38.1 (1.5)
29.4 (2.4)
2
26.3 (6.1)
21.3 (2.9)
42.9 (3.0)
47.7 (2.7)
45.4 (4.4)
67.0 (4.0)
43.6 (5.2)
4

SELF(0.5)
6.0 (1.3)
9.6 (1.1)
14.3 (1.8)
36.6 (2.4)
27.2 (2.3)
35.4 (2.4)
29.1 (2.4)
5
19.2 (4.2)
25.8 (4.2)
42.7 (4.2)
49.9 (2.2)
36.3 (5.5)
67.7 (4.1)
38.9 (5.7)
5PCA
6.2 (1.1)
11.2 (0.8)
15.5 (1.0)
48.7 (2.4)
31.0 (1.9)
27.3 (2.7)
29.3 (1.6)
2
22.3 (5.4)
21.5 (2.5)
43.6 (3.2)
48.3 (3.3)
40.2 (6.9)
67.6 (4.6)
40.1 (7.1)
6

SELF(CV)
6.0 (1.4)
10.3 (2.4)
14.1 (1.4)
33.4 (3.7)
27.3 (2.9)
27.0 (2.7)
27.7 (1.4)
7

45.9 (2.3)
31.2 (7.5)
40.4 (4.1)
49.5 (2.5)
41.2 (3.3)
71.4 (4.0)
40.3 (4.2)
3

iLPP
27.4 (1.4)
24.1 (2.2)
18.0 (2.4)
46.7 (1.7)
37.0 (1.3)
35.2 (1.7)
32.0 (0.9)
048.5 (2.4)
21.4 (0.8)
41.0 (5.2)
48.5 (1.9)
44.5 (3.6)
73.7 (2.9)
42.7 (5.3)
4

SELF’(CV)28.4 (2.6)
21.9 (1.9)
18.5 (2.4)
36.0 (4.7)
35.3 (1.9)
36.9 (3.2)
32.8 (1.5)
1Table 1: Misclassiﬁcation rates for the SSL datasets averaged over reduced dimensions. The numbers in the parentheses
are the standard deviations over repetitions. For each dataset, the best method with the smallest mean and the methods
judged to have no signiﬁcant diﬀerence from the best method based on the t-test at the signiﬁcance level 5% are in bold.
‘Dim’, ‘Lab’, ‘Unlab’, ‘Rep’, and ‘CA’ denote the dimensionality of original samples, the number of labeled samples, thenumber of unlabeled samples, the number of repetitions, and the correctness of the cluster assumption (see the text for
details), respectively. SELF(CV) denotes SELF with β chosen by cross-validation. SELF’ denotes the combination of
LFDA and iLPP in a similar manner.

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction
24

2000
77
300
400
300
100
1010
2000
2000
75
2000
2000
2000

100
100
100
100
100
100
20
100
20
100
100
100
100

2
9
8
9
20
13
18
20
60
5
3
20
21

bananab-cancerdiabetes
f-solargermanheart
image
ringnorm
splicethyroidtitanic
twonorm
waveform# Bests

30
30
30
30
30
30
30
30
30
30
30
30
30

Dim Lab Unlab Rep
2 100 2000 100
9 100
77
100
8 100 300 100
9 100 400 100
20 100 300 100
13 100 100 100
18 100 1010 20
20 100 2000 100
60 100 2000 20
5 100
75
100
3 100 2000 100
20 100 2000 100
21 100 2000 100

Databananab-cancerdiabetes
f-solargermanheart
image
ringnorm
splicethyroidtitanic
twonorm
waveform# Bests
0.87
0.67
0.70
0.63
0.69
0.76
0.81
0.70
0.71
0.94
0.68
0.94
0.85

CA
0.87
0.68
0.70
0.63
0.69
0.77
0.81
0.71
0.71
0.96
0.68
0.94
0.85

31.1 (4.0)
30.6 (3.5)
30.0 (4.1)
36.1 (6.4)
35.4 (6.2)
36.1 (6.3)
35.0 (4.8)
34.7 (4.3)
36.0 (4.1)
41.5 (5.5)
42.6 (5.4)
42.7 (5.1)
36.6 (4.7)
32.8 (3.8)
35.6 (4.1)
25.6 (5.4)
23.7 (4.9)
24.4 (4.1)
24.5 (3.8)
26.2 (3.2)
27.6 (3.8)
35.5 (4.2)
34.0 (3.7)
33.8 (2.8)
34.0 (3.1)
33.1 (3.1)
34.6 (2.5)
9.9 (4.5)
8.3 (4.1)
8.4 (3.6)
33.9 (12.1) 34.0 (12.2) 34.0 (12.1)
15.3 (6.5)
6.3 (2.0)
4.3 (1.3)
27.5 (4.3)
16.6 (3.1)
15.6 (2.3)
6
9
8

LFDA
SELF(0.5)
PCA
27.0 (2.6)
26.6 (2.1)
26.4 (1.9)
34.5 (4.4)
34.4 (4.4)
34.4 (4.1)
32.7 (2.8)
33.0 (2.7)
34.4 (2.7)
39.5 (5.1)
40.1 (5.1)
40.1 (5.2)
31.2 (2.9)
31.2 (3.0)
33.7 (2.8)
22.8 (2.9)
22.6 (2.8)
24.1 (2.7)
17.2 (1.3)
18.8 (1.3)
19.9 (1.5)
28.1 (1.9)
28.9 (1.9)
29.1 (1.6)
29.9 (3.5)
27.8 (3.5)
30.8 (2.3)
4.8 (2.0)
5.3 (2.1)
5.5 (2.1)
33.2 (11.9) 33.2 (11.9) 33.2 (11.9)
4.8 (1.3)
4.5 (1.2)
4.1 (1.1)
15.5 (1.4)
14.5 (1.5)
14.1 (1.4)
9
96
29.6 (3.4)
35.6 (6.4)
34.9 (4.4)
42.0 (5.4)
33.9 (4.3)
24.6 (4.7)
26.0 (3.8)
33.1 (3.2)
33.2 (2.7)
8.7 (4.2)
33.9 (12.1)
6.7 (3.9)
16.9 (3.2)
9

SELF(CV)26.5 (2.1)
34.3 (4.3)
33.0 (2.7)
39.7 (5.2)
31.5 (2.9)
23.1 (2.8)
17.8 (1.7)
28.1 (1.8)
27.7 (3.0)
5.0 (1.9)
33.2 (11.9)
4.3 (1.1)
14.2 (1.7)
1130.0 (4.1)
36.1 (5.8)
35.9 (3.7)
40.6 (5.3)
36.0 (4.0)
24.2 (4.0)
27.9 (4.2)
31.1 (3.3)
45.2 (2.5)
8.2 (3.3)
40.8 (12.3)
4.2 (1.3)
15.3 (2.2)
8

30.3 (3.6)
36.0 (6.2)
35.1 (4.2)
40.4 (5.4)
34.5 (4.1)
24.9 (4.2)
24.5 (3.5)
32.5 (3.8)
39.9 (4.6)
8.9 (4.2)
37.5 (12.9)
6.9 (3.8)
17.8 (3.6)
7

iLPP
SELF’(CV)26.4 (1.9) 26.5 (2.0)
34.8 (4.0) 34.7 (4.1)
34.4 (2.6) 33.2 (2.7)
39.7 (5.4) 39.5 (5.4)
33.7 (2.6)
32.1 (3.0)
23.4 (2.9) 23.1 (2.8)
18.8 (2.1) 16.6 (1.3)
27.1 (1.6) 27.6 (1.8)
42.1 (1.9) 30.1 (4.6)
5.9 (2.1)
5.1 (2.0)
40.0 (12.3) 37.4 (12.5)
4.0 (1.0)
4.5 (1.2)
13.8 (1.4)
14.4 (1.9)
79Table 2: Misclassiﬁcation rates for the IDA datasets averaged over reduced dimensions.

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction25

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

26

The TFIDF vector x usually has a large number of dimensions. In our experiments,
its dimensionality ranged from thousands to tens of thousands (depending on the tasks
since we removed the entries of zero occurrences for all of the documents). In general it is
not possible to directly solve eigenvalue problems in such high dimensional spaces. Here,
we used the kernel formulation (see Section 4.5.3; we used the linear kernel so that SELF
is still a linear dimensionality reduction), relying on the number of samples being muchsmaller than the input dimensionality in our experiments.
We compare the performance of ‘Plain’ (without dimensionality reduction), LFDA,
PCA, ‘SELF(0.5)’ (SELF with β = 0.5), and ‘SELF(CV)’ (SELF with β chosen by using
5-fold cross-validation). In each method, the dimensionality of the reduced space r is
chosen by using 5-fold CV from9 {1, 2, . . . , 10}. For each dataset, we consider 4 conﬁgurations with diﬀerent degrees of supervision. Given n document samples, we randomly
choose 20%, 40%, 60%, and 80% of them as the training data and the rest are treatedas unlabeled data. The 1-nearest neighbor method was again used to evaluate the classiﬁcation accuracy of the unlabeled samples. For each dataset and each training sample
conﬁguration, the experiments were repeated 100 times with randomly selected training
samples.
The means and standard deviations of the misclassiﬁcation rates are summarized inTable 3. The table shows that all of the dimensionality reduction methods perform better
than Plain, so dimensionality reduction evidently contributes to improving the accuracyof document classiﬁcation. Among these methods, SELF consistently works better than
LFDA and PCA.
The mean value of β in SELF(CV) for the four conﬁgurations, 20%, 40%, 60%, and80%, are 0.57, 0.52, 0.48, and 0.46, respectively. This shows that, as the degree ofsupervision increases, the value of β decreases and therefore SELF approaches LFDA.
This agrees well with our intuition. However, since all of the values are rather close to 0.5
in this experiment, SELF(0.5) tends to perform slightly better (and is computationallymore eﬃcient) than SELF(CV). It is also intuitive that LFDA tends to outperform PCA
as the degree of supervision increases.
Overall, SELF—a combination of LFDA and PCA—was shown to be a useful dimensionality reduction method in practical document classiﬁcation tasks.

6

Conclusions, Discussion, and Future Work

Our approach to dimensionality reduction in the current work is called the ﬁlter approach,meaning that the dimensionality reduction procedure is independent of subsequent classiﬁcation algorithms (Guyon & Elisseeﬀ, 2003). Our experimental results showed thatthe proposed method, SELF, works well when it is combined with the 1-nearest-neighborclassiﬁer. On the other hand, it is also important to explore wrapper methods (Ko9

We set the upper limit of r to 10 mainly for computational reasons. However, as shown later, thevalue of r chosen by CV is typically less than 10, so this restriction does not cause a serious performancechange.

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

27

Table 3: Means and standard deviations of the misclassiﬁcation rates of the documentclassiﬁcation tasks over 295 datasets for 100 runs each (i.e., 29, 500 total trials). The
mean value of the reduced dimensionality r chosen by CV was also included in the table.
n′ = 0.2n
Mean error
Std. error# Bests
Mean chosen r

Plain
20.8
3.4
41
—

LFDA
18.4
2.3
76
2.2

SELF(0.5)
16.3
2.1
252
3.3

PCA
18.5
1.7
46
4.6

SELF(CV)
16.4
1.7
242
3.5

n′ = 0.4n
Mean error
Std. error# Bests
Mean chosen r

20.8
3.8
10
—

15.0
1.6
115
3.0

13.8
1.5
239
4.0

17.0
1.6
34
5.3

13.9
1.5
220
3.9

n′ = 0.6n
Mean error
Std. error# Bests
Mean chosen r

21.1
3.4
8
—

13.9
1.5
126
3.5

12.7
1.6
235
4.2

16.2
1.7
50
5.7

12.7
1.6
242
3.9

n′ = 0.8n
Mean error
Std. error# Bests
Mean chosen r

21.5
2.9
9
—

13.6
2.0
134
3.8

12.0
2.2
245
4.1

15.6
2.4
72
6.0

12.1
2.3
240
3.8

havi & John, 1997) for semi-supervised dimensionality reduction, which explicitly takethe properties of subsequent classiﬁcation algorithms into account. A wrapper approach
would be particularly useful in semi-supervised learning scenarios since the performanceof elaborate semi-supervised learning methods is highly dependent on the reliability of theassumptions on the unlabeled samples, such as cluster or manifold structure (Chapelle
et al., 2006).
We showed in Section 4.5.3 that a non-linear variant of SELF can be created by
employing the standard kernel trick. However, a kernelized SELF shares the common
diﬃculty of kernel methods, the question of how to choose the kernel functions. This
must be investigated in the context of semi-supervised dimensionality reduction. In future
work, we will explore semi-supervised dimensionality reduction of structured data using
kernel SELF.
In SELF, we linearly combined the eigenvalue problems of LFDA and PCA since thisapproach allows us to maintain the computational advantages of LFDA and PCA. Thisapproach was demonstrated to be useful through our experiments in Section 5. Although
we examined some properties of the combined method in Section 4.3, it is important toSemi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

28

provide a better understanding of the mechanism of the proposed method. Also, ourproposed approach for combining LFDA and PCA is not the only possibility. A future
direction would be to explore other ways to combine supervised and unsupervised methods
for further performance improvement.
An advantage of SELF is that its solution can be obtained analytically by solving
a generalized eigenvalue problem. When the number of samples is very large, solving
the eigenvalue problem by using the algorithm in Figure 2 would be still computationally tractable as long as the input dimensionality is not too high. On the other hand,when the input dimensionality is very high, the kernel formulation with the linear kernel(see Section 4.5.3) is still computationally tractable as long as the number of samples ismoderate (as demonstrated by the document classiﬁcation experiments in Section 5.2).
However, when the number and dimensionality of the samples are both very large, a naive
implementation may not be computationally tractable. Thus an important future work
along this line is to further investigate the computational aspects of SELF and develop
eﬃcient algorithms that can deal with high-dimensional and large-scale datasets, perhaps
by utilizing the sparsity of the data matrix or the kernel matrix.
A remaining important issue to be discussed, which is common to all semi-supervised
learning techniques, is how to optimize the tuning parameters. We may simply use crossvalidation for this purpose, but that approach has two potential problems. The ﬁrst
problem is that the number of labeled samples is typically small in semi-supervised learning scenarios, so cross-validation is not reliable (Chapelle et al., 2006). Fortunately, ourexperiments showed that SELF is not very sensitive to the choice of the trade-oﬀ parameter β in small sample cases, but there is still room for improvement. The second problem isthat labeled samples and unlabeled samples can have diﬀerent (input) distributions. Sucha situation is referred to as covariate shift (Shimodaira, 2000; Quiñonero-Candela et al.,2009) and ordinary cross-validation is known to be signiﬁcantly biased in such situations(Zadrozny, 2004), while importance-weighted cross-validation is unbiased under covariate
shift (Sugiyama et al., 2007). In future work, we will investigate how such covariate
shift adaptation techniques can be used in the context of semi-supervised dimensionality
reduction.
The properties of a family of linear discriminant analysis algorithms were studied inYe (2005; 2008) and Loog (2007; 2008), but the methods discussed in these papers do
not take the locality of the data into account as LFDA does. Therefore our current work
is essentially diﬀerent from these existing methods. Another alternative to our approach
involves regularized linear discriminant analysis methods for semi-supervised dimensionality reduction based on LPP (Cai et al., 2007) or manifold regularization (Belkin et al.,2006; Song et al., 2008). These methods suﬀer from the weakness of the original FDA, i.e.,the maximum dimension of the reduced subspace is dominated by the number of classes.
In contrast, our method oﬀers advantages for classiﬁcation tasks with rather small numbers of classes. A relevant dimensionality reduction method has also been proposed in
the context of semi-supervised clustering (Zhang et al., 2007). However, the locality ofthe data is still not addressed. Recently, a non-linear dimensionality reduction method
based on a neural network has been proposed (Hinton & Salakhutdinov, 2006). However,Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

29

neural-network-based methods are prone to suﬀer from local optimality because of the
non-convexity of optimization. Also, this optimization is usually carried out via a gradientmethod and is computationally ineﬃcient. Therefore another important research direction
is to extend such neural-network-based methods to semi-supervised setups and compare
their accuracy and computational eﬃciency with discriminant-analysis-based methods.

Acknowledgments
The authors would like to thank the members of the T-PRIMAL (Tokyo PRobabilistic Inference and MAchine Learning) group for their fruitful comments and insights. Our
gratitude also goes to the anonymous reviewers for their valuable comments. MS acknowledges ﬁnancial support from MEXT (20680007 and 1907364) and the Tateishi Science andTechnology Foundation.

References
Albert, A. (1972). Regression and the Moore-Penrose pseudoinverse. New York andLondon: Academic Press.
Aronszajn, N. (1950). Theory of reproducing kernels. Transactions of the American
Mathematical Society, 68, 337–404.
Bai, Z., Demmel, J., Dongarra, J., Ruhe, A., & van der Vorst, H. (Eds.). (2000). Templates
for the solution of eigenvalue problems: A practical guide. Philadelphia, PA, USA:
Society for Industrial and Applied Mathematics.
Belkin, M., & Niyogi, P. (2003). Laplacian eigenmaps for dimensionality reduction anddata representation. Neural Computation, 15, 1373–1396.
Belkin, M., Niyogi, P., & Sindhwani, V. (2006). Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of Machine
Learning Research, 7, 2399–2434.
Boyd, S., & Vandenberghe, L. (2004). Convex optimization. Cambridge: Cambridge
University Press.
Cai, D., He, X., & Han, J. (2007). Semi-supervised discriminant analysis. Proceedingsof the IEEE International Conference on Computer Vision (pp. 1–7). Rio de Janeiro,
Brazil.
Chapelle, O., Schölkopf, B., & Zien, A. (Eds.). (2006). Semi-supervised learning. Cambridge: MIT Press.
Chung, F. R. K. (1997). Spectral graph theory. Providence, R.I.: American MathematicalSociety.

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

30

Davidov, D., Gabrilovich, E., & Markovitch, S. (2004). Parameterized generation oflabeled datasets for text categorization based on a hierarchical directory. The 27th
Annual International ACM SIGIR Conference (pp. 250–257). Sheﬃeld, UK.
Duﬀy, N., & Collins, M. (2002). Convolution kernels for natural language. Advances in
Neural Information Processing Systems 14 (pp. 625–632). Cambridge, MA: MIT Press.
Fisher, R. A. (1936). The use of multiple measurements in taxonomic problems. Annalsof Eugenics, 7, 179–188.
Friedman, J. H. (1989). Regularized discriminant analysis. Journal of the American
Statistical Association, 84, 165–175.
Fukunaga, K. (1990). Introduction to statistical pattern recognition. Boston: Academic
Press, Inc. Second edition.
Gärtner, T. (2003). A survey of kernels for structured data. SIGKDD Explorations, 5,
S268–S275.
Gärtner, T., Flach, P., & Wrobel, S. (2003). On graph kernels: Hardness results andeﬃcient alternatives. Proceedings of the Sixteenth Annual Conference on Computational
Learning Theory (pp. 129–143).
Globerson, A., & Roweis, S. (2006). Metric learning by collapsing classes. Advances in
Neural Information Processing Systems 18 (pp. 451–458). Cambridge, MA: MIT Press.
Goldberger, J., Roweis, S., Hinton, G., & Salakhutdinov, R. (2005). Neighbourhood
components analysis. Advances in Neural Information Processing Systems 17 (pp. 513–
520). Cambridge, MA: MIT Press.
Guyon, I., & Elisseeﬀ, A. (2003). An introduction to variable and feature selection.
Journal of Machine Learning Research, 3, 1157–1182.
He, X., & Niyogi, P. (2004). Locality preserving projections. Advances in Neural Information Processing Systems 16 (pp. 153–160). Cambridge, MA: MIT Press.
Hinton, G. E., & Salakhutdinov, R. R. (2006). Reducing the dimensionality of data withneural networks. Science, 313, 504–507.
Joachims, T. (2002). Learning to classify text using support vector machines: Methods,
theory and algorithms. Boston: Kluwer Academic Publishers.
Jolliﬀe, I. T. (1986). Principal component analysis. New York: Springer-Verlag.
Kashima, H., & Koyanagi, T. (2002). Kernels for semi-structured data. Proceedingsof the Nineteenth International Conference on Machine Learning (pp. 291–298). San
Francisco, CA: Morgan Kaufmann.

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

31

Kashima, H., Tsuda, K., & Inokuchi, A. (2003). Marginalized kernels between labeledgraphs. Proceedings of the Twentieth International Conference on Machine Learning(pp. 321–328). San Francisco, CA: Morgan Kaufmann.
Kohavi, R., & John, G. (1997). Wrappers for feature selection. Artiﬁcial Intelligence, 97,
273–324.
Kondor, R. I., & Laﬀerty, J. (2002). Diﬀusion kernels on graphs and other discrete input
spaces. Proceedings of the Nineteenth International Conference on Machine Learning(pp. 315–322).
Lodhi, H., Saunders, C., Shawe-Taylor, J., Cristianini, N., & Watkins, C. (2002). Textclassiﬁcation using string kernels. Journal of Machine Learning Research, 2, 419–444.
Loog, M. (2007). A complete characterization of a family of solutions to a generalizedﬁsher criterion. Journal of Machine Learning Research, 8, 2121–2123.
Loog, M. (2008). On the equivalence of linear dimensionality-reducing transformations.
Journal of Machine Learning Research, 9, 2489–2490.
Mika, S., Rätsch, G., Weston, J., Schölkopf, B., Smola, A., & Müller, K.-R. (2003).
Constructing descriptive and discriminative nonlinear features: Rayleigh coeﬃcients inkernel feature spaces. IEEE Transactions on Pattern Analysis and Machine Intelligence,
25, 623–628.
Quiñonero-Candela, J., Sugiyama, M., Schwaighofer, A., & Lawrence, N. (Eds.). (2009).
Dataset shift in machine learning. Cambridge, MA: MIT Press.
Rätsch, G., Onoda, T., & Müller, K.-R. (2001). Soft margins for adaboost. Machine
Learning, 42, 287–320.
Roweis, S., & Saul, L. (2000). Nonlinear dimensionality reduction by locally linear embedding. Science, 290, 2323–2326.
Schölkopf, B., Smola, A., & Müller, K.-R. (1998). Nonlinear component analysis as akernel eigenvalue problem. Neural Computation, 10, 1299–1319.
Shimodaira, H. (2000). Improving predictive inference under covariate shift by weighting
the log-likelihood function. Journal of Statistical Planning and Inference, 90, 227–244.
Song, Y., Nie, F., Zhang, C., & Xiang, S. (2008). A uniﬁed framework for semi-supervised
dimensionality reduction. Pattern Recognition, 41, 2789–2799.
Sugiyama, M. (2007). Dimensionality reduction of multimodal labeled data by local Fisher
discriminant analysis. Journal of Machine Learning Research, 8, 1027–1061.

Semi-Supervised Local Fisher Discriminant Analysis for Dimensionality Reduction

32

Sugiyama, M., Ide, T., Nakajima, S., & Sese, J. (2008). Semi-supervised local Fisher
discriminant analysis for dimensionality reduction. Advances in Knowledge Discovery
and Data Mining (pp. 333–344). Berlin: Springer.
Sugiyama, M., Krauledat, M., & Müller, K.-R. (2007). Covariate shift adaptation byimportance weighted cross validation. Journal of Machine Learning Research, 8, 985–
1005.
Tenenbaum, J. B., de Silva, V., & Langford, J. C. (2000). A global geometric frameworkfor nonlinear dimensionality reduction. Science, 290, 2319–2323.
Weinberger, K., Blitzer, J., & Saul, L. (2006). Distance metric learning for large margin
nearest neighbor classiﬁcation. Advances in Neural Information Processing Systems 18(pp. 1473–1480). Cambridge, MA: MIT Press.
Xing, E. P., Ng, A. Y., Jordan, M. I., & Russell, S. (2003). Distance metric learningwith application to clustering with side-information. Advances in Neural Information
Processing Systems 15 (pp. 505–512). Cambridge, MA: MIT Press.
Ye, J. (2005). Characterization of a family of algorithms for generalized discriminant
analysis on undersampled problems. Journal of Machine Learning Research, 6, 483–
502.
Ye, J. (2008). Comments on the complete characterization of a family of solutions to a
generalized ﬁsher criterion. Journal of Machine Learning Research, 9, 517–519.
Zadrozny, B. (2004). Learning and evaluating classiﬁers under sample selection bias.
Proceedings of the Twenty-First International Conference on Machine Learning (pp.
903–910). New York, NY: ACM Press.
Zelnik-Manor, L., & Perona, P. (2005). Self-tuning spectral clustering. Advances in Neural
Information Processing Systems 17 (pp. 1601–1608). Cambridge, MA: MIT Press.
Zhang, D., Zhou, Z.-H., & Chen, S. (2007). Semi-supervised dimensionality reduction.
Proceedings of the 7th SIAM International Conference on Data Mining (pp. 629–634).
Minneapolis, MN, USA.