Exploiting Known Taxonomies in Learning Overlapping Concepts

1 Introduction

Practical algorithms in supervised machine learning degrade in performance (prediction accuracy) when faced with many features that are not necessary for predicting the desired output. An important question in the fields of machine learning, knowledge discovery, computer vision and pattern recognition is how to extract a small number of good features. A common way to attempt to resolve this problem is to use dimensionality reduction techniques. Two of the most popular

∗ The work was supported in part by the U.S. National Science Foundation NSF IIS-03-08215/IIS-05-13678, Specialized Research Fund for the Doctoral Program of Higher Education of China (No. 20030335083) and National Natural Science Foundation of China (No. 60633070). Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the funding agencies.

Xiaofei He

Yahoo! Research Labs hex@yahoo-inc.com

Kun Zhou

Microsoft Research Asia

kunzhou@microsoft.com

Hujun Bao

College of Computer Science Zhejiang University bao@cad.zju.edu.cn

techniques for this purpose are Principal Component Analysis (PCA) and Linear Discriminant Analysis (LDA) [Duda et al., 2000].

PCA is an unsupervised method. It aims to project the data along the direction of maximal variance. LDA is supervised. It searches for the project axes on which the data points of different classes are far from each other while requiring data points of the same class to be close to each other. Both of them are spectral methods, i.e., methods based on eigenvalue decomposition of either the covariance matrix for PCA or the scatter matrices (within-class scatter matrix and betweenclass scatter matrix) for LDA. Intrinsically, these methods try to estimate the global statistics, i.e. mean and covariance. They may fail when there is no sufficient number of samples. Moreover, both PCA and LDA effectively see only the Euclidean structure. They fail to discover the underlying structure, if the data lives on or close to a submanifold of the ambient space.

Recently there has been a lot of interest in geometrically motivated approaches to data analysis in high dimensional spaces. Examples include ISOAMP [Tenenbaum et al., 2000], Laplacian Eigenmap [Belkin and Niyogi, 2001], Locally Linear Embedding [Roweis and Saul, 2000]. These methods have been shown to be effective in discovering the geometrical structure of the underlying manifold. However, they are unsupervised in nature and fail to discover the discriminant structure in the data. In the meantime, manifold based semi-supervised learning has attracted considerable attention [Zhou et al., 2003], [Belkin et al., 2004]. These methods make use of both labeled and unlabeled samples. The labeled samples are used to discover the discriminant structure, while the unlabeled samples are used to discover the geometrical structure. When there is a large amount of unlabeled samples available, these methods may outperform traditional supervised learning algorithms such as Support Vector Machines and regression [Belkin et al., 2004]. However, in some applications such as face recognition, the unlabeled samples may not be available, thus these semi-supervised learning methods can not be applied.

In this paper, we introduce a novel supervised dimensionality reduction algorithm, called Locality Sensitive Discriminant Analysis, that exploits the geometry of the data manifold. We first construct a nearest neighbor graph to model the local geometrical structure of the underlying manifold. This graph is then split into within-class graph and between-class graph by using the class labels. In this way, the geometrical and discriminant structure of the data manifold can be accurately characterized by these two graphs. Using the notion of graph Laplacian [Chung, 1997], we can find a linear transformation matrix which maps the data points to a subspace. This linear transformation optimally preserves the local neighborhood information, as well as discriminant information. Specifically, at each local neighborhood, the margin between data points from different classes is maximized.

The paper is structured as follows: in Section 2, we provide a brief review of Linear Discriminant Analysis. The Locality Sensitive Discriminant Analysis (LSDA) algorithm is introduced in Section 3. In Section 4, we describe how to perform LSDA in Reproducing Kernel Hilbert Space (RKHS) which gives rise to kernel LSDA. The experimental results are presented in Section 5. Finally, we provide some concluding remarks in Section 6.

2 RelatedWorks

The generic problem of linear dimensionality reduction is the following. Given a set x1, x2, · · · , xm in Rn , find a transformation matrix A = (a1, · · · , ad) ∈ Rn×d that maps these m points to a set of points y1 , y2 , · · · , ym in Rd (d ≪ n), such that yi "represents" xi, where yi = AT xi .

Linear Discriminant Analysis (LDA) seeks directions that are efficient for discrimination. Suppose these data points belong to c classes and each point is associated with a label l(xi) ∈ {1, 2, · · · , c}. The objective function of LDA is as follows:

where μ is the total sample mean vector, mi is the number of samples in the i-th class, μi is the average vector of the i-th class, and xij is the j-th sample in the i-th class. We call Sw the within-class scatter matrix and SB the between-class scatter matrix. The basis functions of LDA are the eigenvectors of the following generalized eigen-problem associated with the largest eigenvalues:

Clearly, LDA aims to preserve the global class relationship between data points, while it fails to discover the intrinsic local geometrical structure of the data manifold. In many real world applications such as face recognition, there may not be sufficient training samples. In this case, it may not be able to accurately estimate the global structure and the local structure becomes more important.

Besides LDA, there is recently a lot of interests in graph based linear dimensionality reduction. The typical algorithms includes Locality Preserving Projections (LPP, [He and Niyogi, 2003]), Local Discriminant Embedding (LDE, [Chen et al., 2005]), Marginal Fisher Analysis (MFA, [Yan et al., 2005]), etc. LPP uses one graph to model the geometrical structure in the data. LDE and MFA are essentially the same. Both of them uses two graphs to model the discriminant structure in the data. However, these two algorithms implicitly consider that the within-class and between-class relations are equally important. This reduces the flexibility of the algorithms.

3 Locality Sensitive Discriminant Analysis

In this section, we introduce our Locality Sensitive Discriminant Analysis algorithm which respects both discriminant and geometrical structure in the data. We begin with a description of the locality sensitive discriminant objective function.

3.1 The Locality Sensitive Discriminant Objective Function for Dimensionality Reduction

As we described previously, naturally occurring data may be generated by structured systems with possibly much fewer degrees of freedom than the ambient dimension would suggest. Thus we consider the case when the data lives on or close to a submanifold of the ambient space. One hopes then to estimate geometrical and discriminant properties of the submanifold from random points lying on this unknown submanifold. In this paper, we consider the particular question of maximizing local margin between different classes.

Given m data points {x1, x2, · · · , xm} ⊂ Rn sampled from the underlying submanifold M, one can build a nearest neighbor graph G to model the local geometrical structure of M. For each data point xi, we find its k nearest neighbors and put an edge between xi and its neighbors. Let N (xi) = {x1i , · · · , xki } be the set of its k nearest neighbors. Thus, the weight matrix of G can be defined as follows:

The nearest neighbor graph G with weight matrix W characterizes the local geometry of the data manifold. It has been frequently used in manifold based learning techniques, such as [Belkin and Niyogi, 2001], [Tenenbaum et al., 2000], [Roweis and Saul, 2000], [He and Niyogi, 2003]. However, this graph fails to discover the discriminant structure in the data.

In order to discover both geometrical and discriminant structure of the data manifold, we construct two graphs, i.e. within-class graph Gw and between-class graph Gb. Let l(xi) be the class label of xi. For each data point xi, the set N (xi) can be naturally split into two subsets, Nb(xi) and Nw(xj). Nw(xi) contains the neighbors sharing the same label with xi, while Nb(xi) contains the neighbors having different labels. Specifically,

Clearly, Nb(xi) ∩ Nw(xi) = ∅ and Nb(xi) ∪ Nw(xi) = N (xi). Let Ww and Wb be the weight matrices of Gw and Gb, respectively. We define:

It is clear to see W = Wb + Ww and the nearest neighbor graph G can be thought of as a combination of within-class graph Gw and between-class graph Gb.

Now consider the problem of mapping the within-class graph and between-class graph to a line so that connected points of Gw stay as close together as possible while connected points of Gb stay as distant as possible. Let y = (y1, y2, · · · , ym)T be such a map. A reasonable criterion for choosing a "good" map is to optimize the following two objective functions:

under appropriate constraints. The objective function (8) on within-class graph incurs a heavy penalty if neighboring points xi and xj are mapped far apart while they are actually in the same class. Likewise, the objective function (9) on between-class graph incurs a heavy penalty if neighboring points xi and xj are mapped close together while they actually belong to different classes. Therefore, minimizing (8) is an attempt to ensure that if xi and xj are close and sharing the same label then yi and yj are close as well. Also, maximizing (9) is an attempt to ensure that if xi and xj are close but have different labels then yi and yj are far apart. The learning procedure is illustrated in Figure 1.

3.2 Optimal Linear Embedding

In this subsection, we describe our Locality Sensitive Discriminant Analysis algorithm which solves the objective functions (8) and (9). Suppose a is a projection vector, that is, yT = aT X, where X = (x1, · · · , xm) is a n×mmatrix.

By simple algebra formulation, the objective function (8) can be reduced to1

where Dw is a diagonal matrix; its entries are column (or row, since Ww is symmetric) sum of Ww, Dw,ii = ∑j Ww,ij. Similarly, the objective function (9) can be reduced to

where Db is a diagonal matrix; its entries are column (or row, since Wb is symmetric) sum of Wb, Db,ii = ∑j Wb,ij . Lb = Db -Wb is the Laplacian matrix of Gb.

Note that, the matrix Dw provides a natural measure on the data points. If Dw,ii is large, then it implies that the class containing xi has a high density around xi. Therefore, the bigger the value of Dw,ii is, the more "important" is xi. Therefore, we impose a constraint as follows:

Thus, the objective function (8) becomes the following:

or equivalently,

And the objective function (9) can be rewritten as follows:

Finally, the optimization problem reduces to finding:

where α is a suitable constant and 0 ≤ α ≤ 1. The projection vector a that minimizes (13) is given by the maximum eigenvalue solution to the generalized eigenvalue problem:

Let the column vector a1, a2, · · · , ad be the solutions of equation (14), ordered according to their eigenvalues, λ1 > · · · > λd. Thus, the embedding is as follows:

where yi is a d-dimensional vector, and A is a n × d matrix.

Note that, if the number of samples (m) is less than the number of features (n), then rank(X ) ≤ m. Consequently, rank(XDwX T ) ≤ m and rank(X (αLb + (1 - α)Ww)X T ) ≤ m. The fact that XDwX T and X (αLb + (1 -α)Ww)X T are n×nmatrices implies that both of them are singular. In this case, one may first apply Principal Component Analysis to remove the components corresponding to zero eigenvalues.

4 Kernel LSDA

LSDA is a linear algorithm. It may fail to discover the intrinsic geometry when the data manifold is highly nonlinear. In this section, we discussion how to perform LSDA in Reproducing Kernel Hilbert Space (RKHS), which gives rise to kernel LSDA.

Suppose X = {x1, x2, · · · , xm} ∈ X is the training sample set. We consider the problem in a feature space F induced by some nonlinear mapping

For a proper chosen φ, an inner product 〈, 〉 can be defined on F which makes for a so-called reproducing kernel Hilbert space (RKHS). More specifically,

holds where K(., .) is a positive semi-definite kernel function. Several popular kernel functions are: Gaussian kernel K(x, y) = exp(-‖x - y‖2/σ2 ); polynomial kernel K(x, y) = (1 + 〈x, y〉)d ; Sigmoid kernel K(x, y) = tanh(〈x, y〉 + α).

Given a set of vectors {vi ∈ F|i = 1, 2, · · · , d} which are orthonormal (〈vi, vj〉 = δi,j), the projection of φ(xi) ∈ F to these v1, · · · , vd leads to a mapping fromX to Euclidean space Rd through

We look for such {vi ∈ F|i = 1, 2, · · · , d} that helps {yi |i = 1, · · · ,m} preserve local geometrical and discriminant structure of the data manifold. A typical scenario is X = Rn, F = Rθ with d << n < θ.

Let Φ denote the data matrix in RKHS:

Now, the eigenvector problem in RKHS can be written as follows:

Because the eigenvector of (15) are linear combinations of φ(x1), φ(x2), · · · , φ(xm), there exist coefficients αi, i = 1, 2, · · · ,m such that

where α = (α1, α2, · · · , αm)T ∈ Rm.

Following some algebraic formulations, we get:

where K is the kernel matrix, Kij = K(xi, xj). Let the column vectors α1 ,α2 , · · · ,αm be the solutions of equation (16). For a test point x, we compute projections onto the eigenvectors vk according to

where αki is the ith element of the vector αk . For the original training points, the map can be obtained by y = Kα, where the ith element of y is the one-dimensional representation of xi .

5 Experimental Results

In this Section, we investigate the use of LSDA on face recognition. We compare our proposed algorithm with Eigenface (PCA, [Turk and Pentland, 1991]), Fisherface (LDA, [Belhumeur et al., 1997]) and Marginal Fisher Analysis (MFA, [Yan et al., 2005]). We begin with a brief discussion about data preparation.

5.1 Data Preparation

Two face databases were tested. The first one is the Yale database 1 , and the second one is the ORL database 2 . In all the experiments, preprocessing to locate the faces was applied. Original images were normalized (in scale and orientation) such that the two eyes were aligned at the same position. Then, the facial areas were cropped into the final image for matching. The size of each cropped image in all the experiments is 32 × 32 pixels, with 256 gray levels per pixel. Thus, each image can be represented by a 1024-dimensional vector in image space. No further preprocessing is done. Different pattern classifiers have been applied for face recognition, including nearest neighbor [Turk and Pentland, 1991], Bayesian [Moghaddam, 2002], and Support Vector Machines [Phillips, 1998], etc. In this paper, we apply nearest neighbor classifier for its simplicity. In our experiments, the number of nearest neighbors (k) is taken to be 5. The parameter α is estimated by leave one out cross validation.

1 http://cvc.yale.edu/projects/yalefaces/ yalefaces.html

2 http://www.cl.cam.ac.uk/Research/DTG/ attarchive/facesataglance.html

In short, the recognition process has three steps. First, we calculate the face subspace from the training set of face images; then the new face image to be identified is projected into d-dimensional subspace; finally, the new face image is identified by nearest neighbor classifier.

5.2 Face Recognition on Yale Database

The Yale face database is constructed at the Yale Center for Computational Vision and Control. It contains 165 grayscale images of 15 individuals. The images demonstrate variations in lighting condition (left-light, center-light, right-light), facial expression (normal, happy, sad, sleepy, surprised, and wink), and with/without glasses. Figure 2 shows some sample images of one individual.

For each individual, l(= 2, 3, 4, 5) images were randomly selected as training samples, and the rest were used for testing. The training set was used to learn a face subspace using the LSDA, Eigenface, and Fisherface methods. Recognition was then performed in the subspaces. We repeated this process 20 times and calculate the average recognition rate. In general, the recognition rates varies with the dimension of the face subspace. The best performance obtained by these algorithms as well as the corresponding dimensionality of the optimal subspace are shown in Table 1. For the baseline method, we simply performed face recognition in the original 1024-dimensional image space. Note that, the upper bound of the dimensionality of Fisherface is c - 1 where c is the number of individuals [Duda et al., 2000].

As can be seen, our algorithm outperformed all other three methods. The Eigenface method performs the worst in all cases. It does not obtain any improvement over the baseline method. It would be interesting to note that, when there are only two training samples for each individual, the best performance of Fisherface is no longer obtained in a c - 1(= 14) dimensional subspace, but a 10-dimensional subspace. LSDA

reaches the best performance almost always at c - 1 dimensions. This property shows that LSDA does not suffer from the problem of dimensionality estimation which is a crucial problem for most of the subspace learning based face recognition methods.

5.3 Face Recognition on ORL Database

The ORL (Olivetti Research Laboratory) face database is used in this test. It consists of a total of 400 face images, of a total of 40 people (10 samples per person). The images were captured at different times and have different variations including expressions (open or closed eyes, smiling or nonsmiling) and facial details (glasses or no glasses). The images were taken with a tolerance for some tilting and rotation of the face up to 20 degrees. 10 sample images of one individual are displayed in Figure 3. For each individual, l(= 2, 3, 4, 5) images are randomly selected for training and the rest are used for testing.

The experimental design is the same as before. For each given l, we average the results over 20 random splits. The best result obtained in the optimal subspace and the corresponding dimensionality for each method are shown in Table 2.

As can be seen, our LSDA algorithm performed the best for all the cases. The Fisherface method performed comparatively to LSDA as the size of the training set increases. Moreover, the optimal dimensionality obtained by LSDA and Fisherface is much lower than that obtained by Eigenface.

5.4 Discussion

Several experiments on two standard face databases have been systematically performed. These experiments have revealed a number of interesting points:

1. All the three algorithms (LSDA, MFA, and Fisherface) performed better in the optimal face subspace than in the original image space. This indicates that dimensionality reduction can discover the intrinsic structure of the face manifold and hence improve the recognition rate.
2. In all the experiments, our LSDA algorithmconsistently outperformed the Eigenface, Fisherface and MFA methods. Especially when the size of the training set is small, LSDA significantly outperformed Fisherface. This is probably due to the fact that Fisherface fails to accurately estimate the within-class scatter matrix from only a small number of training samples.

1. Eigenface fails to gain improvement over the baseline. This is probably because that Eigneface does not encode the discriminating information.
2. In all the experiments, the optimal dimensionality obtained by LSDA is always c-1, where c is the number of classes. In practice, when the computational complexity is a major concern, one can simply project the face images into a c-1 dimensional subspace.

6 Conclusion

We have introduced a novel linear dimensionality reduction algorithm called Locality Sensitive Discriminant Analysis (LSDA). For the class of spectrally based dimensionality reduction techniques, it optimizes a fundamentally different criterion compared to classical dimensionality reduction approaches based on Fisher's criterion (LDA) or Principal Component Analysis. The most prominent property of LSDA is the complete preservation of both discriminant and local geometrical structure in the data. For LDA, on the other hand, it can only preserve the global discriminant structure, while the local geometrical structure is ignored. We have applied our algorithm to face recognition. Experiments on Yale and ORL databases have been conducted to demonstrate the effectiveness of our algorithm.