LaplacianEigenmapsforDimensionalityReductionandDataRepresenation

manifold

learning

需积分: 9 194 浏览量更新于2023-06-04 评论收藏 798KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

LETTER Communicated by Joshua B. Tenenbaum

Laplacian Eigenmaps for Dimensionality Reduction and Data

Representation

Mikhail Belkin

misha@math.uchicago.edu

Department of Mathematics, University of Chicago, Chicago, IL 60637, U.S.A.

Partha Niyogi

niyogi@cs.uchicago.edu

Department of Computer Science and Statistics, University of Chicago,

Chicago, IL 60637 U.S.A.

One of the central problems in machine learning and pattern recognition

is to develop appropriate representations for complex data. We consider

the problem of constructing a representation for data lying on a low-

dimensional manifold embedded in a high-dimensional space. Drawing

on the correspondence between the graph Laplacian, the Laplace Beltrami

operator on the manifold, and the connections to the heat equation, we

propose a geometrically motivated algorithm for representing the high-

dimensional data. The algorithm provides a computationally efﬁcient ap-

proach to nonlinear dimensionality reduction that has locality-preserving

properties and a natural connection to clustering. Some potential appli-

cations and illustrative examples are discussed.

1 Introduction

In many areas of artiﬁcial intelligence, information retrieval, and data min-

ing, one is often confronted with intrinsically low-dimensional data lying in

a very high-dimensional space. Consider, for example, gray-scale images of

an object taken under ﬁxed lighting conditions with a moving camera. Each

such image would typically be represented by a brightness value at each

pixel. If there were n

pixels in all (corresponding to an n × n image), then

each image yields a data point in

. However, the intrinsic dimensional-

ity of the space of all images of the same object is the number of degrees of

freedom of the camera. In this case, the space under consideration has the

natural structure of a low-dimensional manifold embedded in

Recently, there has been some renewed interest (Tenenbaum, de Silva,

& Langford, 2000; Roweis & Saul, 2000) in the problem of developing low-

dimensional representations when data arise from sampling a probabil-

ity distribution on a manifold. In this letter, we present a geometrically

Neural Computation 15, 1373–1396 (2003)

 2003 Massachusetts Institute of Technology

1374 M. Belkin and P. Niyogi

motivated algorithm and an accompanying framework of analysis for this

problem.

The general problem of dimensionality reduction has a long history. Clas-

sical approaches include principal components analysis (PCA) and multi-

dimensional scaling. Various methods that generate nonlinear maps have

also been considered. Most of them, such as self-organizing maps and other

neural network–based approaches (e.g., Haykin, 1999), set up a nonlin-

ear optimization problem whose solution is typically obtained by gradient

descent that is guaranteed only to produce a local optimum; global op-

tima are difﬁcult to attain by efﬁcient means. Note, however, that the re-

cent approach of generalizing the PCA through kernel-based techniques

(Sch¨olkopf, Smola, & M¨uller, 1998) does not have this shortcoming. Most of

these methods do not explicitly consider the structure of the manifold on

which the data may possibly reside.

In this letter, we explore an approach that builds a graph incorporating

neighborhood information of the data set. Using the notion of the Laplacian

of the graph, we then compute a low-dimensional representation of the data

set that optimally preserves local neighborhood information in a certain

sense. The representation map generated by the algorithm may be viewed

as a discrete approximation to a continuous map that naturally arises from

the geometry of the manifold.

It is worthwhile to highlight several aspects of the algorithm and the

framework of analysis presented here:

• The core algorithm is very simple. It has a few local computations and

one sparse eigenvalue problem. The solution reﬂects the intrinsic geo-

metric structure of the manifold. It does, however, require a search for

neighboring points in a high-dimensional space. We note that there are

several efﬁcient approximate techniques for ﬁnding nearest neighbors

(e.g., Indyk, 2000).

• The justiﬁcation for the algorithm comes from the role of the Laplace

Beltrami operator in providing an optimal embedding for the mani-

fold. The manifold is approximated by the adjacency graph computed

from the data points. The Laplace Beltrami operator is approximated

by the weighted Laplacian of the adjacency graph with weights cho-

sen appropriately. The key role of the Laplace Beltrami operator in the

heat equation enables us to use the heat kernel to choose the weight

decay function in a principled manner. Thus, the embedding maps for

the data approximate the eigenmaps of the Laplace Beltrami operator,

which are maps intrinsically deﬁned on the entire manifold.

• The framework of analysis presented here makes explicit use of these

connections to interpret dimensionality-reduction algorithms in a ge-

ometric fashion. In addition to the algorithms presented in this letter,

we are also able to reinterpret the recently proposed locally linear em-

Laplacian Eigenmaps 1375

bedding (LLE) algorithm of Roweis and Saul (2000) within this frame-

work.

The graph Laplacian has been widely used for different clustering and

partition problems (Shi & Malik, 1997; Simon, 1991; Ng, Jordan, &

Weiss, 2002). Although the connections between the Laplace Beltrami

operator and the graph Laplacian are well known to geometers and

specialists in spectral graph theory (Chung, 1997; Chung, Grigor’yan,

& Yau, 2000), so far we are not aware of any application to dimen-

sionality reduction or data representation. We note, however, recent

work on using diffusion kernels on graphs and other discrete struc-

tures (Kondor & Lafferty, 2002).

• The locality-preserving character of the Laplacian eigenmap algorithm

makes it relatively insensitive to outliers and noise. It is also not prone

to short circuiting, as only the local distances are used. We show that by

trying to preserve local information in the embedding, the algorithm

implicitly emphasizes the natural clusters in the data. Close connec-

tions to spectral clustering algorithms developed in learning and com-

puter vision (in particular, the approach of Shi & Malik, 1997) then

become very clear. In this sense, dimensionality reduction and cluster-

ing are two sides of the same coin, and we explore this connection in

some detail. In contrast, global methods like that in Tenenbaum et al.

(2000), do not show any tendency to cluster, as an attempt is made to

preserve all pairwise geodesic distances between points.

However, not all data sets necessarily have meaningful clusters. Other

methods such as PCA or Isomap might be more appropriate in that

case. We will demonstate, however, that at least in one example of such

a data set ( the “swiss roll”), our method produces reasonable results.

• Since much of the discussion of Seung and Lee (2000), Roweis and

Saul (2000), and Tenenbaum et al. (2000) is motivated by the role that

nonlinear dimensionality reduction may play in human perception

and learning, it is worthwhile to consider the implication of the pre-

vious remark in this context. The biological perceptual apparatus is

confronted with high-dimensional stimuli from which it must recover

low-dimensional structure. If the approach to recovering such low-

dimensional structure is inherently local (as in the algorithm proposed

here), then a natural clustering will emerge and may serve as the basis

for the emergence of categories in biological perception.

• Since our approach is based on the intrinsic geometric structure of the

manifold, it exhibits stability with respect to the embedding. As long

as the embedding is isometric, the representation will not change. In

the example with the moving camera, different resolutions of the cam-

era (i.e., different choices of n in the n × n image grid) should lead to

embeddings of the same underlying manifold into spaces of very dif-

1376 M. Belkin and P. Niyogi

ferent dimension. Our algorithm will produce similar representations

independent of the resolution.

The generic problem of dimensionality reduction is the following. Given

a set x

,...,x

of k points in

, ﬁnd a set of points y

,...,y

(m  l)

such that y

“represents” x

. In this letter, we consider the special case where

,...,x

∈ M and M is a manifold embedded in R

We now consider an algorithm to construct representative y

’s for this

special case. The sense in which such a representation is optimal will become

clear later in this letter.

2 The Algorithm

Given k points x

,...,x

in R

, we construct a weighted graph with k nodes,

one for each point, and a set of edges connecting neighboring points. The

embedding map is now provided by computing the eigenvectors of the

graph Laplacian. The algorithmic procedure is formally stated below.

1. Step 1 (constructing the adjacency graph). We put an edge between

nodes i and j if x

and x

are “close.” There are two variations:

(a) -neighborhoods (parameter  ∈

R). Nodes i and j are con-

nected by an edge if x

−x



<where the norm is the usual

Euclidean norm in

. Advantages: Geometrically motivated,

the relationship is naturally symmetric. Disadvantages: Often

leads to graphs with several connected components, difﬁcult

to choose .

(b) n nearest neighbors (parameter n ∈

N). Nodes i and j are con-

nected by an edge if i is among n nearest neighbors of j or j is

among n nearest neighbors of i. Note that this relation is sym-

metric. Advantages: Easier to choose; does not tend to lead to

disconnected graphs. Disadvantages: Less geometrically intu-

itive.

2. Step 2 (choosing the weights).

Here as well, we have two variations

for weighting the edges:

(a) Heat kernel (parameter t ∈

R). If nodes i and j are connected,

put

= e

−

x

−



;

otherwise, put W

= 0. The justiﬁcation for this choice of

weights will be provided later.

In a computer implementation of the algorithm, steps 1 and 2 are executed

simultaneously.

剩余24页未读，继续阅读

YURI_YEP

粉丝: 1
资源: 4

会员权益专享

Laplacian Eigenmaps for Dimensionality Reduction and Data Repres...

评论0

会员权益专享

最新资源

Laplacian Eigenmaps for Dimensionality Reduction and Data Repres...

评论0

论文研究-Out-of-sample algorithm of Laplacian Eigenmaps Applied to Dimensionality Reduction.pdf

四大机器学习降维算法：PCA、LDA、LLE、Laplacian Eigenmaps.pdf

Laplacian Eigenmaps + Demo

Laplacian Eigenmaps

sklearn.manifold

拉普拉斯特征映射代码

刚才提到的等距映射和拉普拉斯特征映射又分别是什么呢

拉普拉斯特征映射 matlab代码

signless Laplacian

drafting and revision: laplacian pyramid network for fast high-quality artistic style transfer

matlab实现块状 Laplacian 矩阵

matlab数据降维工具箱

LPP python

可以介绍下拉普拉斯特征映射吗

graph laplacian matrix

适合地球化学数据降纬的流形学习算法有哪些

laplacian_pyramid函数拉普拉斯差分matlab代码

半监督 matlab

推荐几篇入门变形网格的文献

会员权益专享

最新资源