Lecture Notes in Computer Science
Local Coordinates Alignment and Its Linearization
Download 12.42 Mb. Pdf ko'rish
|
- Bu sahifa navigatsiya:
- Keywords
- 2 LCA: Local Coordinates Alignment
- 2.1 Local Representations
- 2.2 Global Alignment
- 3 LLCA: Linear Local Coordinates Alignment
Local Coordinates Alignment and Its Linearization Tianhao Zhang 1,3 , Xuelong Li 2 3 , and Jie Yang 1 1 Institute of IP & PR, Shanghai Jiao Tong Univ., P.R. China 2 Sch. of Comp. Sci. and Info. Sys., Birkbeck, Univ. of London, U.K. 3 Dept. of Computing, Hong Kong Polytechnic Univ., Hong Kong {z.tianhao,dacheng.tao}@gmail.com, xuelong@dcs.bbk.ac.uk, jieyang@sjtu.edu.cn Abstract. Manifold learning has been demonstrated to be an effective way to discover the intrinsic geometrical structure of a number of samples. In this paper, a new manifold learning algorithm, Local Coordinates Alignment (LCA), is developed based on the alignment technique. LCA first obtains the local coordinates as representations of a local neighborhood by preserving the proximity relations on the patch which is Euclidean; and then the extracted local coordinates are aligned to yield the global embeddings. To solve the out of sample problem, the linearization of LCA (LLCA) is also proposed. Empirical studies on both synthetic data and face images show the effectiveness of LCA and LLCA in comparing with existing manifold learning algorithms and linear subspace methods.
reduction. 1 Introduction Manifold learning addresses the problem of discovering the intrinsic structure of the manifold from a number of samples. The generic problem of manifold learning can be described as following. Consider a dataset X , which consists of N samples i x ( 1 i N ≤ ≤
) in a high dimensional Euclidean space m . That is [ ]
, ,
N X x x × = ∈ . The sample i x is obtained by embedding a sample i z , which is drawn from d M (a low
dimensional nonlinear manifold) to m (a higher dimensional Euclidean space, d m < ),
i.e., :
m M ϕ → and ( )
i i x z ϕ = . A manifold learning algorithm aims to find the corresponding low-dimensional representation i y in a low dimensional Euclidean space d of
i x to preserve the geometric property of d M . Recently, a number of manifold learning algorithms have been developed for pattern analysis, classification, clustering, and dimensionality reduction. Each algorithm detects a specific intrinsic, i.e., geometrical, structure of the underlying manifold of the raw data. The representative ones include ISOMAP [6], locally linear embedding (LLE) [7], Laplacian eigenmaps (LE) [1], local tangent space alignment (LTSA) [3], etc. 644 T. Zhang et al. ISOMAP is a variant of MDS [13]. Unlike MDS, the distance measure between two samples is not the Euclidean distance but the geodesic distance, which is the shortest path from one sample to another computed by the Dijkstra’s algorithm. ISOMAP is intrinsically a global approach since it attempts to preserve the global geodesic distances of all pairs of samples. Different from ISOMAP, LLE, LE and LTSA are all local methods, which preserve the geometrical structure of every local neighborhood. LLE uses the linear coefficients, which reconstruct the given point by its neighbors, to represent the local structure, and then seeks a low-dimensional embedding, in which these coefficients are still suitable for reconstructions. LE is developed based on the Laplace Beltrami operator in the spectral graph theory [1,4]. This operator provides an optimal embedding for a manifold. The algorithm preserves proximity relationships by the manipulations on the undirected weighted graph, which indicates the neighbor relations of the pairwise points. LTSA exploits the local tangent information as a representation of the local structure and this local information is then aligned to give the global coordinates. Inspired by LTSA [3], we propose a new manifold learning algorithm, i.e., Local Coordinates Alignment (LCA). LCA obtains the local coordinates as representations of a local neighborhood by preserving the proximity relations on the patch. The extracted local coordinates are then aligned by the alignment trick [3] to yield the global embeddings. In LCA, the local representation and the global alignment are explicitly implemented as two steps for intrinsic structure discovery. In addition, to solve the out of sample problem, the linear approximation is applied to LCA, called Linear LCA or LLCA. Experimental results show that LCA discovers the manifold structure, and LLCA outperforms representative subspace methods for the face recognition. The rest of the paper is organized as follows: Section 2 describes LCA and its linearization is given in Section 3. Section 4 shows the empirical studies over synthetic data and face databases. Section 5 concludes.
The proposed algorithm is based on the assumption that each local neighborhood of the manifold
is intrinsically Euclidean, i.e., it is homeomorphic to an open subset of the Euclidean space with dimension d . The proposed LCA extracts local coordinates by preserving the neighbor relationships of the raw data, and then obtains the optimal embeddings by aligning these local coordinates in globality.
Given an arbitrary sample m i x ∈ and its k nearest neighbors 1 , , k i i x x , measured in terms of Euclidean distance, we let ( ) 0 1 1 [ , , , ]
m k i i i i X x x x × +
= ∈ denote a neighborhood in the manifold d M , where
0 i i x x = . For i X , we have the local map :
d i ψ → , i.e., ( ) 0 1 1 : [ , , , ] k d k i i i i i i X Y y y y ψ × + = ∈ . Here, i Y is the local coordinates to parameterize the corresponding points in i X . To yield the faithful maps, Local Coordinates Alignment and Its Linearization 645 we expect that the nearby points remain nearby, that is, the point 0 d i y ∈ is close to 1 , , k i i y y , i.e.,
0 0 2 1 arg min
j i k i i y j y y = − ∑ . (1) To capture the geometrical structure of the neighborhood, the weighting vector k i w ∈ is introduce to (1) as ( ) 0 0 2 1 arg min j i k i i i j y j y y w = − ∑ , (2) where the j th element of i w is obtained by the heat kernel [4] with parameter t ∈ , i.e.,
( ) 0 2 exp /
i i i j w x x t ⎛ ⎞ = − − ⎜ ⎟ ⎝ ⎠ . (3) Vector i w is a natural measure of distances between 0
and its neighbors. The larger the value ( )
i j w is (the closer the point 0
is to the j th neighbor), the more important is the corresponding neighbor. In setting t = ∞
, Eq. (2) reduces to Eq. (1). To make further deduction, Eq. (2) is transformed to ( )
) ( )
0 1 0 1 0 0 0 arg min tr , ,
k i k T i i i i i i i y T i i y y y y y y w y y ⎛ ⎞ ⎡ ⎤ − ⎜ ⎟ ⎢ ⎥ ⎜ ⎟ ⎢ ⎥ ⎡
⎤ − − ⎣ ⎦ ⎜ ⎟ ⎢ ⎥ ⎜ ⎟ ⎢ ⎥ ⎜ ⎟ − ⎣ ⎦ ⎝ ⎠ , (4) where
( ) tr ⋅ denotes the trace operator, and ( )
diag ⋅ denotes the diagonal matrix whose diagonal entries are the corresponding components of the given vector. Let [ ] ( ) 1 T k k i k k M e I + ×
= − ∈ , where [ ] 1, ,1 T k k e = ∈ and k I is the k k × identity matrix. Then, Eq. (4) reduces to: ( ) ( ) ( ) ( ) ( ) ( ) arg min tr diag arg min tr diag arg min tr , i i i T T T i i i i i i i i i i Y Y T i i i Y Y M Y M w Y M w M Y Y L Y = = (5)
where ( )
diag T i i i i L M w M = , which encapsulates the local geometric information. The matrix i L is equivalent to: ( ) [
( ) ( )
1 diag
diag k T i i k j j i i k k k i i w w e L w e I I w w = ⎡ ⎤ − − ⎡ ⎤ ⎢ ⎥ = − = ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎢ ⎥ − ⎣ ⎦ ∑ . (6) 646 T. Zhang et al. Therefore, according (5), the local coordinates
th neighborhood can be expressed. 2.2 Global Alignment According to Section 2.1, local coordinates are obtained for all local neighborhoods respectively, namely 1 2 , , , N Y Y Y . In this section, these local coordinates are aligned to yield the global one. Let [
1 , , N Y y y =
denote the embedding coordinates which are faithful representations for [ ]
, ,
X x x = sampled from a manifold. Define the selection matrix ( )
1 N k i S × +
∈ : ( ) ( ) 1 0 i q i pq if p h S else ⎧ = ⎪ = ⎨ ⎪⎩ , (7) where, [ ] 1 0 1 , , ,
i k h i i i + = ∈
(8) denotes the set of indices for the i th point and the corresponding neighbors. Then we can express the local coordinates i Y as the selective combinations of the embedding coordinates Y by using the selection matrix i S : i i Y YS = . (9) Now, we can write Eq. (5) as follows: ( )
T T i i i Y YS L S Y . (10) For all samples, we have the global optimization: ( ) ( ) 1 1 arg min
tr arg min tr arg min tr
= = ⎛ ⎞ = ⎜ ⎟ ⎝ ⎠ = ∑ ∑ , (11) where 1
T i i i i L S L S = = ∑ . The matrix L can be termed by the alignment matrix [3] which is symmetric, positive semi-definite, and sparse. We can form the matrix L by the iterative procedure: ( ) ( ) ,
i i i i i L h h L h h L ← + , (12)
for 1 i N ≤ ≤
with the initialization 0
= .
Local Coordinates Alignment and Its Linearization 647 To uniquely determine Y , we impose the constraint T d YY I = , where d I is the d d × identity matrix. Now, the objective function is: ( ) arg min tr s.t. .
T d Y YLY YY I =
(13) The above minimization problem can be converted to solving an eigenvalue decomposition problem as follows:
λ = . (14)
The column vectors 1 2 , ,
f f f in N are eigenvectors associated with ordered nonzero eigenvalues, 1 2 d λ λ
λ < < < . Therefore, we obtain the embedding coordinates as: 1 2 , ,
d Y f f f ⎡ ⎤ = ⎣ ⎦ . (15) 3 LLCA: Linear Local Coordinates Alignment LCA aims to detect the intrinsic features of nonlinear manifolds, but it fails in the out of sample problem. To solve this problem, the linearization approximation of LCA, i.e., Linear LCA (LLCA), is developed in this Section. LLCA finds the transformation matrix
× ∈ that maps the dataset X to the dataset Y , i.e., T Y A X = . Thus, the linearized objective function (11) is: ( ) arg min tr T T A A XLX A . (16)
Impose the column orthonormal constraint to A , i.e. T d A A I = , we have: ( ) arg min tr s.t. .
T T d A A XLX A A A I =
(17) The solution of (17) is given by the eigenvalue decomposition: T XLX α λα
= . (18) The transformation matrix A is [ ] 1 2 , , d A α α
α = , (19) where
1 2 , , d α α
α are eigenvectors of T XLX associated with the first d smallest eigenvalues. LLCA can be implemented in either an unsupervised or a supervised mode. In the later case, the label information is utilized, i.e., each neighborhood is replaced by points which have identical class label information. For a given point i x and its same-class 648 T. Zhang et al. points 1
, ,
i i x x − , where ni denotes the number of samples in this class, one can construct the vector 1
i w − ∈ as follows: ( )
0 2 exp / j i i i j w x x t ⎛ ⎞ = − − ⎜ ⎟ ⎝ ⎠ , 1, , 1
ni = − . (20)
Furthermore, to denote new indices set for the i th point and its same-class points, one need reset [ ] 0 1 1 , , ,
i ni h i i i − = ∈ . (21) Download 12.42 Mb. Do'stlaringiz bilan baham: |
ma'muriyatiga murojaat qiling