Manifold Alignment Based on Sparse Local Structures of More Corresponding Pairs

1 Introduction

Manifold alignment is very useful in many fields, such as machine learning and data mining [Wang and Mahadevan, 2008; 2009a; 2009b; Zhai et al., 2010; Pei et al., 2012]. It is simultaneously a solution to the problem of alignment and a framework for discovering a unifying representation of multiple datasets [Wang et al., 2011]. The problem of aligning multiple data sets is to extract the shared latent semantic structure. Due to different data sets might be represented by different features, it is difficult to find the correspondence in their original high-dimensional space. Thus, extraction of the shared intrinsic structure from multiple high-dimensional data sets becomes more critical.

In order to extract the intrinsic structure from a given data set, many linear and nonlinear dimensionality reduction approaches have been proposed in the literature such as SMCE [Elhamifar and Vidal, 2011], PCA [Jolliffe, 2002; Lv et al., 2010a; 2010b], MDS [Shepard, 1980], ISOMAP

[Tenenbaum et al., 2000], LE [Belkin and Niyogi, 2003], LLE [Roweis and Saul, 2000]. However, this paper focuses on extracting the shared latent semantic structure from multiple manifolds, i.e., manifold alignment.

The current manifold alignment can be classified into supervised and unsupervised algorithms. The supervised algorithms require a small set of corresponding pairs for initial alignments, such as Ham's algorithm [Ham et al., 2004] and Lafon's algorithm [Lafon et al., 2006]. Wang et al. [Wang et al., 2011] proposed an important framework for unsupervised alignment. Based on Wang's framework, there is a growing body of work on unsupervised alignment, such as [Hoa et al., 2012; Pei et al., 2012]. Unfortunately, the adjacency matrix they constructed does not correctly reflect the corresponding pairs across manifolds so that the local structure of shared latent manifold can not be preserved well.

In this paper, to preserve the local geometry of the original data set, the sparse reconstruction weight matrix of each manifold is established by SMCE method. To get more and reliable corresponding pairs, we propose a new method based on the assumption: local structures of a corresponding pair should be corresponding. The sparse correspondence matrices, which play a key role in joining the different manifolds, are constructed by the sparse local structures of corresponding pairs. Clearly, the alignment accuracy can be improved by providing more and reliable corresponding pairs. The adjacency matrix we constructed can effectively preserve the shared intrinsic structure from multiple data sets. Further more, a new energy function for manifold alignment is proposed to simultaneously match the corresponding instances and preserve the local geometry of each manifold. The shared low dimensional embedding, which provides better descriptions for the intrinsic geometry and relations between different manifolds, can be obtained by solving the optimization problem with closed-form solution. Extensive experiments have been performed to demonstrate the superior performance of proposed approach.

The rest of this paper is organized as follows. In Section 2, the preliminaries are presented. Section 3 shows how to construct the joint adjacency matrix. The proposed algorithm is given in Section 4. Simulations and discussions are given in Section 5. Finally, Section 6 provides some concluding remarks.

2 Preliminaries

2.1 Mathematical Formulation

Manifold alignment is to extract the shared latent semantic structure from multiple data sets. Suppose two data sets X(1) and X(2) parameterized by the same intrinsic structure:

where X(1) is a p(1) ×m data matrix with m samples and p(1) features or dimensional spaces (p(1) ≫ 1); X(2) is a p(2) ×n data matrix with n samples and p(2) features or dimensional spaces (p(2) ≫ 1).

DenoteWas the joint adjacency matrix

where W(1) ∈ R(m×m) ,W(2) ∈ R(n×n) ,W(1,2) ∈ R(m×n) , and W(2,1) ∈ R(n×m) . It includes both parts: the reconstruction weight matrix of each manifold W(1) ,W(2) and the correspondence matrix W(1,2) ,W(2,1) , which play a key role in aligning both data sets X(1) and X(2) . Generally, W(1) and W(2) are determined according to the neighborhood of each data point [Wang et al., 2011; Hoa et al., 2012]. They are as follows:

W(1,2) and W(2,1) are constructed in terms of the corresponding pairs. A corresponding pair, denoted by (x(1) i ↔ x(2) j ), means x(1) i and x(2) j have shared the same latent features. Some different methods are proposed to find the corresponding pairs.

Then, the shared intrinsic structure Y can be calculated by solving the following problem:

The new embedded coordinates of both datasets X(1) and X(2) are given by Y(1) and Y(2) , respectively.

where d indicates the latent dimensionality and the mutual embedding space is spanned by the range of Y.

Clearly, if (x(1) i ↔ x(2) j ), then manifold alignment should find a map such that y(1) i and y(2) j is closest to each other in terms of Euclidean distance and the local structures of both x(1) i and x(2) j are also preserved. y(1) i = y(2) j if and only if the instances x(1) i and x(2) j are in exact correspondence [Wang et al., 2011].

2.2 Correspondence Matrix

In unsupervised alignment, the most important step is to get some corresponding information across two datasets. Some structure similarity functions f(x(1) i , x(2) j ) have been proposed to compute the similarity between x(1) i ∈ X(1) and x(2) j ∈ X(2) , such as the parameterized curve representation method [Pei et al., 2012] and the local pattern matching approach [Wang et al., 2011]. Pei et al. introduced a parameterized curve representation to describe the local structure, where the points with similar parameterized curves are seen as corresponding pairs. Wang et al. employed a distance matrix of k nearest neighbors to characterize the local structure.

The method employed by Wang et al. has an important role in identifying the corresponding pairs. However , this method cannot preserve the local structures of corresponding pairs well. As shown in [Wang et al., 2011], the supervised and unsupervised methods can be utilized for manifold alignment. The supervised algorithm (called WangS) is used to construct the correspondence matrices as:

where η > 0. Clearly, W(1,2) and W(2,1) constructed by Eq.(1) may not represent the local structures of corresponding pairs.

In Wang's unsupervised algorithm (called WangU), W(1,2) andW(2,1) are constructed by:

tance matrix representing the local geometry of x(1) i . However, a lager number of non-zero elements could violate the principles used to capture information about the corresponding structure [Elhamifar and Vidal, 2011]. Furthermore, the correspondence matrices didn't correctly represent the corresponding pairs across manifolds.

An example is as follows to illustrate the problem. In Figure 1, it is well known that the corresponding pairs should be as follows:

However, by using WangU method,

Due to (W (1,2) (1,1) > W (1,2) (1,j) , W (1,2) (2,2) > W (1,2) (2,j) , W (1,2) (3,3) > W (1,2) (3,j) ) , it means that

Thus, W(1,2) and W(2,1) constructed directly by Eq.(2) cannot preserve the manifold structure very well. In the following section, an approach is proposed to overcome this problem.

3 Sparse Local structural Correspondence

3.1 Constructing the Sparse Reconstruction Weight Matrix of Each Data Set

In order to obtain the intrinsic structure of a given data set, dimensionality reduction methods play an important role in manifold learning, such as SMCE. It automatically finds a small neighborhood around each data point without fixing the neighborhood size k, and simultaneously obtains their weights. However, Sparse Manifold Clustering and Embedding (SMCE)[Elhamifar and Vidal, 2011] is used for clustering and dimensionality reduction not for manifold alignment. Inspired by SMCE, the sparse reconstruction weight matrix of each data set is constructed, i.e.,W(1) , W(2) , which characterizes the geometric property of the original data set.

3.2 Constructing the Sparse Correspondence Matrices between Data Sets

To construct the correspondence matricesW(1,2) , W(2,1) , it is crucial to get more corresponding pairs. In this section, we will introduce a new method to obtain more and reliable corresponding pairs in terms of local structure correspondence. Then, W(1,2) and W(2,1) are constructed using the sparse local structures of corresponding pairs across manifolds.

Given x(1) i (i = 1, 2, · · · ,m), a corresponding pair between two manifolds is chosen by

where δ is the threshold, which depends on the manifolds. In our experiments, let

where H(W(1,2) ) sorts the set

.

{the maximum of every row of W(1,2)}

and gets the top some values. A set of corresponding pairs S initialized to the empty set is obtained by

Clearly, S is just a part of all corresponding pairs. Based on the following assumption, a method is proposed to find the more and reliable corresponding pairs. Denote

where N (1) xi denotes the k nearest neighbors of x(1) i .

Assumption 1 Suppose two data sets parameterized by the same intrinsic structure. If (x(1) i ↔ x(2) c ), then the elements of N (1) xi should be corresponding to that of N (2) xc respectively, i.e, (N (1) xi ↔ N (2) xc ). Conversely, if (N (1) xi ↔ N (2) xc ), then (x(1) i ↔x(2) c ).

Definition 1 For sets A,B, denote the set {A ↔ B} that the elements of A and B can be arbitrarily combined into the complete corresponding set.

Definition 2 x(1) i ↛S means x(1) i is not in any corresponding pair in S.

Suppose

A corresponding pair can be found by

where

Repeat this process until there is no reliable element added to S. Furthermore, the sparse correspondence matrices are constructed by

whereW(1,2) andW(2,1) are constructed by the sparse local structures of corresponding pairs, which play a key role in aligning different manifolds.

More and reliable corresponding pairs can be obtained by using our method. See the example in Figure 1. Let

then by Eq.(4),

By definition 2, {x(1) 4 , x(1) 5 , x(2) 4 , x(2) 5 } ↛S. From section 3.1, it holds that

thus, (x(1) 4 ↔ x(2) 4 ) can be obtained from the sparse local structure correspondence. Similarly, (x(1) 5 ↔ x(2) 5 ) can be obtained. Then, constructW(1,2) andW(2,1) by Eq.(6).

Remark 1 Obviously, W(2,1) and W(1,2) are sparse matrices, since W(1) and W(2) are sparse. The sparse matrix W characterizes geometric properties and reflects the joint manifold constructed from the two original manifolds and the corresponding pairs.

Remark 2 Based on simple geometric intuitions, nearby points in the high dimensional space remain nearby and similarly co-located with respect to one another in the low dimensional space. That means that the neighbors of x(1) i should be the neighbors of x(2) c , and the neighbors of x(2) c should be the neighbors of x(1) i after alignment.

In the following section, the SLSA algorithm will be used to learn low-dimensional embeddings based on the joint adjacency matrix W.

4 Sparse Local Structural Alignment (SLSA) Algorithm

4.1 Loss Function

To extract the shared intrinsic structure from multiple manifolds in terms of the joint adjacency matrix constructed, a loss function C(Y) is designed to simultaneously match the corresponding pairs and preserve the local structure of each manifold. Suppose a corresponding pair (x(1) i ↔ x(2) c ), C(y(1) i ) includes two parts:

where N (1) yi = { k nearest neighbors of y(1) i }, N (2) yc = { k nearest neighbors of y(2) c }. The first part is to compute the reconstruction residual with fixed weights W(1) (i) , which is used to preserve the local geometric structure of each original data set [Roweis and Saul, 2000]. The second part is to compute the distance between y(1) i and y(2) c . That means that y(1) i is close to y(2) c by minimizing this term, i.e., the instances x(1) i and x(2) c have been aligned in the mutual embedding space spanned by the range of Y. Then, the loss function is as follows:

where the sum is taken over all instances from both data sets. yi is reconstructed by its 2k joint nearest neighbors from two manifolds. The shared intrinsic structure Y can be obtained by minimizing the loss function C(Y).

4.2 Optimization Solution

To optimize the embedding loss function C(Y), we can rewrite it as the quadratic form:

where I(i) denotes the ith row of identity matrix and I ∈ R(m+n)×(m+n) ; M = (I - W)T (I - W) ∈ R(m+n)×(m+n) is sparse, symmetric and semipositive definite, M(i,j)=β(i,j) - W(i,j) - W(j,i) + ∑2k W(2k,i)W(2k,j) (i, j = 1, 2, · · · ,m+ n), and

To avoid the trivial solution of minimizing C(Y), the following constraint is required:

where I ∈ Rd×d , D ∈ R(m+n)×(m+n) is a full rank diagonal matrix formed by D(i,i) = ∑m+n j=1 W(i,j).

The Lagrange multiplier method is adopted to solve the optimization problem in Eq.(8):

(10)

Then,

Clearly, it holds that D-1MY = λY. The embedded coordinates Y are formed by eigenvectors of D-1M corresponding to the d smallest non-zero eigenvalues.

4.3 The SLSAAlgorithm

The whole SLSA method is summarized in Algorithm 1 and the following theorem will prove the algorithm is valid to simultaneously match the corresponding pairs and preserve the local structure of each manifold.

Theorem 1 Given x(1) i (i = 1, 2, · · · ,m), if (x(1) i ↔x(2) c ) ∈ S, then there exists a small constant ϵ, such that ‖y(1) i - y(2) c ‖2 ≤ 2ϵ.

Proof: Since (x(1) i ↔x(2) c ) ∈ S, we have:

whereW(i) denotes the ith row ofW. By Eq.(6), it follows that:

Algorithm 1 The SLSA Algorithm

Input: Two data sets X(1) ∈ Rp(1)×m, X(2) ∈ Rp(2)×n .

Output: The new unified embedded coordinates Y.

Step 1: Initialize W ← 0, S ← ∅.

Step 2: Inspired by SMCE, construct W(1) , W(2) .

Step 3: Compute the corresponding pairs set S.

end for

Step 4: Based on S, construct the correspondence matrices W(2,1) andW(1,2) by Eq.(6).

Step 5: Compute the embedded coordinates by Eq.(10).

Then, by minimizing of Eq.(7), there exist two vectors ϵ1 and ϵ2, it follows that:

where ‖ϵ1‖2 ≤ ϵ and ‖ϵ2‖2 ≤ ϵ. Thus,

From Eq.(8), it is easy to get that y(1) i is much closer to y(2) c than other points in Y(2) . The proof is complete.

Furthermore, it is easy to see that if (x(1) i ↔ x(2) c ), then y(1) i should share the same nearest neighbors of y(2) c inY(2) , and vice versa.

5 Simulations and Discussions

In this section, two databases are used in our experiments: the COIL-20 database [Samneer et al., 1996] and the Glutaredoxin protein structure database PDB-1G7O [J. and Bystroff, 2008]. The performance of the proposed algorithm (SLSA)

Z

is compared with that of the related alignment algorithm, such as Wang's method: WangS and WangU [Wang et al., 2011]. In our experiments, the different sets of corresponding pairs with different cardinalities are selected randomly. Under the ideal condition, the low-dimensional coordinates of corresponding pairs should be overlap [Wang et al., 2011; Pei et al., 2012].

5.1 Databases

The Columbia Object Image Library (COIL-20) is a grayscale image database of 20 objects. With a fixed camera, the objects were rotated through 360 degrees and 72 images per object were taken at pose intervals of 5 degrees. In our experiments, each image is resized to 32 × 32 and becomes a point in 1024-dimensional space. Some images are shown in Figure 2 (left).

Proteins are flexible molecules, which may appear in different conformations. Due to that proteins are structurally similar in each family and a little similarity in different family, thus analysis of protein structure is expected, which can lead to a deep insight into protein function. More importantly, it has many applications in the studies of protein evolution and classification. We perform the alignment experiments with the 1 and 21 protein models. Each model has 215 amino acids and is represented in 3D spaces (Figure 2 (right)).

5.2 The Role of Alignment: (W(1) andW(2) ) or (W(1,2) andW(2,1) )?

Set W(1,2) = 0 and W(2,1) = 0. Eq.(10) can be viewed as dimensionality reduction on two data sets respectively. In Figure 3, the left figure illustrates the alignment result by our method. the right figure illustrates the alignment result by Wang's method. The alignment accuracies of both methods are equal to zero. Therefore, a conclusion is arrived at that the correspondence matrices W(1,2) and W(2,1) play an important role in manifold alignment.

5.3 Experiments with Prior Correspondence

Based on prior corresponding pairs, WangS constructs W(1,2) andW(2,1) by Eq.(1), our method by Eq.(6). Under the different sets of corresponding pairs with different cardinalities, Figure 4 and Figure 5 illustrate the best and average alignment accuracies of both methods on two databases respectively. It can be seen that SLSA has better performance than that of WangS method. Under the same conditions of prior corresponding pairs, sparse reconstruction weight matrices and loss function, different correspondence matrices constructed have different alignment results. Figure 6 illustrates the alignment results of the proposed algorithm with different correspondence matrices constructed by Eq.(1) and Eq.(6). It can be see that the manifold structure is not preserved well in the left Figure.

5.4 Experiments without Prior Correspondence

When there is no prior corresponding pairs, we need to use the function f to find them. WangU is done by local pattern matching approach (LPM) to find correspondence information [Wang et al., 2011]. They construct W(1,2) andW(2,1) by Eq.(2). Based on the set of corresponding pairs found, some more corresponding pairs can be got by section 3.2. As shown in Table 1, LPM with 2 nearest neighbors to characterize local geometry just found only one pairwise correspondence in COIL-20 database. No more corresponding pairs can be found. However, in the synthetic datasets, Two more corresponding pairs can be found based on the three pairwise correspondences found. Our method construct the correspondence matrices by Eq.(6). It can be seen that SLSA has better performance than that of WangU method.

6 Conclusions

This paper proposed a sparse local structural alignment (SLSA) algorithm for manifold alignment. A sparse optimization problem is formulated with a closed-form solution which extract the shared intrinsic structure from manifolds. We proposed an approach to obtain more and reliable corresponding pairs in terms of local structure correspondence. Then, the joint adjacency matrix is constructed using the sparse local structures of corresponding pairs. Experimental results demonstrate our method can get better performance than other related alignment methods. Furthermore, our method could be easily extended to align multiple data sets.

Acknowledgments

This work was supported by Specialized Research Fund for the Doctoral Program of Higher Education under Grant 2010081110053 and Program for New Century Excellent Talents in University under Grant NCET-10-0568, partially supported by National Program on Key Basic Research Project (973 Program) under Grant 2011CB302201.