MLRG/summer07

From ResearchWiki

Revision as of 19:52, 20 August 2007 by Schizoid (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Jump to: navigation, search

MLRG Home

Time: Wednesdays, 1:30-2:30

Topic: Unsupervised Learning

Location: MEB 3147

Schedule

Date	Papers	Presenter
9 May 07	Overview: Clustering tutorial and Manifold learning tutorial (or Lawrence's ML tutorial).	Hal
16 May 07	Topic: Laplacian Eigenmaps A short version describing the Laplacian Eigenmaps algorithm and a long version containing more detailed proofs and shows how Laplacian Eigenmaps relates to LLE. I recommend to read the long version. Optional: Successive Laplacian Eigenmaps I will use some stuff from this paper to illustrate a problem occurring when using the spectral decomposition of the graph Laplacian for manifold learning. Diffusion Maps An interesting (but math heavy) paper in the context of the graph Laplacian (Laplace-Beltrami operator approximation) that talks about how to separate the geometry from statistics of the data. A lengthier version Diffusion Maps, Spectral Clustering and the Reaction Coordinates of Dynamical Systems, B. Nadler, S. Lafon, R. Coifman, I. G. Kevrekidis. I thought the longer version was easier to grasp. Spectral Methods for Dimensionality Reduction This is is just a general overview over various dimensionality reduction techniques based on spectral methods.	Sam
23 May 07	Dimensionality reduction in the "worst-case": The Johnson-Lindenstrauss result for embedding a Euclidean space into a lower dimensional space. Bourgain's general result on embedding metric spaces into $l p$ spaces.	Suresh
30 May 07	Probabilistic approaches to dimensionality reduction Probabilistic PCA: The Tipping-Bishop paper on probabilistic PCA is a bit old but can be glimpsed over for the original motivation behind probabilistic models for PCA. The GPLVM paper(s) will anyway have the requisite details of PPCA too. Gaussian Process Latent Variable Model: The shorter version describes PPCA, the dual PPCA, and the non-linear extensions. The longer journal version - Probabilistic Non-linear Principal Component Analysis with Gaussian Process Latent Variable Models contains some more details (reading section-2, at least, is advised). Stochastic Neighbor Embedding: The SNE paper describes a model which is based on defining probability distributions over all the potential neighbors of points in original as well as embedded space, and then finding an embedding which makes the two distributions match, as much as possible. Some more details in the papers summary section.	Piyush
04 June 07	Kernel stuff Background material: Everything about RKHS's Main paper: A kernel view of the dimensionality reduction of manifolds	hal
13 June 07	Application Day Language: Hierarchical Distributed Representations for Statistical Language Modeling Systems: Virtual Landmarks for the Internet	Nathan and Eric
15 August 07	Semi-supervised approaches to dimensionality reduction Main paper: Semi-Supervised Nonlinear Dimensionality Reduction (There seems to be a typo below equation-17. It should read $ρ B = \| \| G \| \| / \| \| M 12 \| \|$ instead of $\| \| F \| \| / \| \| M 12 \| \|$ ) This paper discusses the use of prior information on the exact mapping (in form of on-manifold coordinates) of some data points, applied to some manifold learning techniques (LLE, LTSA and ISOMAP). The case of inexact mapping and sensitivity analysis on the ways of prior point selection is also discussed. Optional reading: Semi-Supervised Dimensionality Reduction This paper discusses a semi-supervised technique to dimensionality reduction based on a different approach exploiting pair-wise constraints defined on some of the data instances.	Piyush

Paper Summaries

9 May 07: Intro (Hal)

In my mind, there are basically three types of unsupervised learning problems: dimensionality reduction, clustering and density estimation. Note that there is overlap: to a probabilist, everything is density estimation, including clustering and DR. There are also non-probabilistic "versions" of DE, such as one-class SVMs, outlier detection, noise-reduction, etc. What these problems have in common is that we are handed some data, and we want to discover some underlying structure in the data. Sometimes this is a manifold (manifold = folded low dimensional space embedded into a high dimensional space), sometimes it's a clustering, sometimes it's a representation of where the data is likely to be found.

The basic algorithms that everyone should be familiar with before the ball gets rolling are:

Dimensionality reduction: PCA, LLE, ISOMAP

Clustering: k-means, agglomerative/hierarchical

Density Estimation: mixtures of X (X = Gaussians, multinomials, etc.)

Here's a quick overview of all of these.

PCA: find a linear embedding of the high dimensional space by projecting onto the principle components (components of highest variance). Reduces to an eigen problem. Also minimizes squared reconstruction error, and has a probabilistic interpretation based on Gaussians in low-dimensional space. LLE: assume that within a ball of k neighbors, the manifold is linear ("locally linear"); first, construct weights so that each data point can be represented by a linear combination of its neighbors, then reconstruct a low-dimensional version of the data based on these weights. Isomap: construct neighborhoods and measure shortest distances between points; reconstruct a n-dimensional representation of the data, using multidimensional scaling; finally, throw out all extraneous dimensions (ala PCA). In general: these algorithms work well if the data is densely sampled around the manifold with sufficiently little noise; this may or may not be the case for your problems.

k-means: find clusters by initializing cluster centers, assigning data points to nearest center and then adjusting centers; repeat until convergence. This locally minimizes a distortion measure and typically converges incredibly quickly. Agglomerative clustering being by linking the two closest points, then considering them a mini-cluster, and then recursing. The primary variable is the metric for merging two existing clusters: single-link (min distance), complete-link (max distance), average-link (mean distance) or mean-link (distance between means). There is also divisive clustering, but it is less common. In general: the hardest part in k-means is initialization/choosing k; the hardest part in agglomerative is choosing the linkage; many people use agglomerative and then sever the tree to get hard clusters. There are also many algorithms for "soft clustering" -- mixtures of X can be seen as a soft clustering algorithm...

mixtures of X: similar to k-means in practice; initialize k Xs placed somewhere in space. Estimate the probability that each data point is generated by each mixture component. Re-estimate Xs to maximize expected likelihood (for X in the exponential family, this is a straightforward maximization). Repeat. Again, the hardest thing is initialization/choosing k.

16 Mai 07: Laplacian Eigenmaps (Sam)

The Laplacian Eigenmaps algorithm is very simple:

Compute a (weighted) adjacency graph $W$ from from the input points $X \in R^n$ using nearest neighbors or epsilon balls.
Build the graph Laplacian $L = D - W$ with $D$ being a diagonal matrix with $d i i = \sum w i j j$ .
Compute the d+1 smallest eigenvalues $\lambda_0 = 0 < \lambda_1 < \ldots <\lambda_d$ and the corresponding eigenvectors $ψ i$ from $L$ .
The $d$ dimensional embedding $Y$ is constructed as $y_i = (\psi_1(i), \ldots, \psi_d(i))^T$

That seems (seemed) like black magic to me. What is the reasoning for this algorithm? What this algorithm is trying to do is to place nearby points in the original data to nearby points in the embedding. Namely it is minimizing

\sum w i j (y i - y j) 2 i j

with respect to some constraints. This tells us that points connected by a large weight should be mapped as closed together as possible, whereas we don't care for points that have no edge between them (0 weight).This sounds very similar to LLE and we are in fact minimizing the same objective function (above sum) in Laplacian Eigenmaps as in LLE, the only difference is in how we choose the weights and this leads to a different reasoning for the Laplacian Eigenmaps algorithm.

Why is the algorithm minimizing the above sum? By simple expanding of the square term we can easily see that the above sum corresponds to $2 y T L y$ (the steps are shown in the paper), which can be minimized by solving for the smallest eigenvectors of the graph Laplacian $L$ which we constructed in steps 1 and 2 of the algorithm. In the continuous case this corresponds to finding a function $f: M \to R$ on a manifold $M$ that maps nearby points on $M$ onto nearby points in $R$ . Intuitively we can see that this achieved if we have a small gradient, if we move around point $x$ on $M$ , $f$ of the points arounf $x$ is not going to change much since we have a small gradient at $x$ . The paper shows this more formally with a upper bound on the distance when mapping two points on $M$ using $f$ . The result is that we want to find a function with minimal gradient over $M$ . This can be solved by the eigenfunctions of the Laplace-Beltrami operator, which is the divergence of the gradient of the function on $M$ and gives us a measure on how fast the gradient changes. In the discrete setting the graph Laplacian is an approximation to the Laplace-Beltrami operator (if the manifold is uniformly sampled) and therefore by using the eigenvectors we are solving for a "discrete function" that minimizes above criterion.

A few words about the optional papers I listed:

The Successive Laplacian Eigenmaps paper talks about the problem that the eigenvectors are only required to be orthogonal but not independent. This is sometimes not enough to uncover the low dimensional embedding faithfully. I will illustrate the problem with some examples on Wednesday. The paper talks also about a fix for this problem.

The Diffusion Maps paper is interesting since it shows that by choosing the weights of the adjacency graph appropriately different continuous operators can be approximated. Of importance to Manifold Learning is that they show a better way to approximate the Laplace-Beltrami operator that is capable of capturing the geometric properties of the manifold regardless of non-uniform density. Most of the math in this paper goes over my head so i am not going into any detail in that paper, don't bother reading it except if you feel so inclined...

The Spectral Methods for Dimensionality Reduction paper is a good overview over existing methods for dimensionality reduction based on spectral decomposition.

Discussions

23 May 07: Embeddings

The theory of metric embeddings starts with a metric space (X,d), a target metric space (Y,g), and the following question:

Can we construct a map $f: X \rightarrow Y$ such that distances are preserved ? In other words,

$d (x 1, x 2) = g (f (x 1), f (x 2))$

for all $x_1, x_2 \in X$

Why do this ?

Usually, (Y,g) is an easier space to work in than (X,d), and so we can translate any metric problem in (X,d) to a presumably easier problem in (Y,g)
Maybe it's easier to represent points in (Y,g), and so we can reduce complexity of representation.

In general, it's impossible to achieve the above goal, even if the source metric space consists of a 4-node graph and the target is Euclidean space. So we resort to approximations. Specifically, can we find an r and a distortion D such that $r \cdot d(x_1, x_2) \le g(f(x_1), f(x_2)) \le r \cdot D \cdot d(x_1, x_2)$ for all $x_1, x_2 \in X$

This is called a D-approximate embedding, because D is the "slack factor" in the estimation of distances. Ideally, we'd like D to be a small constant, or even (if we are lucky) something like $1 + ε$ , for any $ε > 0$ .

A dimensionality reduction is a special kind of embedding where the source and target metric spaces have the same metric (typically defined by a norm), and only differ in their dimensionality. The most famous dimensionality reduction result is the Johnson-Lindenstrauss Lemma, which, paraphrased, says that

The intrinsic dimensionality of an n-point Euclidean space is log n

A quick puzzle to ponder: The $l_\infty$ metric, for two d-dimensional points, is the maximum distance between any two coordinates. I.e $l_\infty(p,q) = \max_i |p_i - q_i|$

Show that ANY metric space on n points can be embedded isometrically (distortion D = 1) in  in n-1 dimensions.

Solution attempt

Notes:

The above framework is worst-case, unlike the "average-case" framework in manifold learning. As a consequence, theoretical results are weaker in certain cases: however, the theory is very rich, with lots of structure.
The mapping need not be deterministic. In fact, we will see a randomized construction with the JL Lemma. This will introduce a tiny probability of error, which can be made arbitrarily small. For more on randomized analysis (I won't go over it in the lecture), see these notes.

30 May 07: Probabilistic Embeddings (Piyush)

Probabilistic PCA: PPCA formulates the dimensionality reduction problem based on a latent variable model. It sees the dimensionality reduction as a (kind of "reverse") mapping from a latent ("hidden") space to the observed space, where the objective is to recover the latent space. The probabilistic formulation is attractive since it offers computational benefits - parameter estimation can be done using EM algorithm (alternating/iterative estimation of latent space and the mapping parameter), which avoids evaluation of the data covariance matrix (very expensive for large number of points and high dimension). Apart from various other advantages, such as giving a basic for Bayesian treatment of PCA, the probabilistic interpretation also provides the framework to deal with issues such as the problem of missing data.

Gaussian process latent variable models (GPLVM): There exists a dual probabilistic interpretation for PCA which differs from the original PPCA on how the latent space and the mapping parameter are treated. It is based on placing a gaussian process prior over the mapping from latent space to observed space. Both approaches start by defining likelihood of the variables in observed space, followed by a process of marginalizing ("integrating out") and then optimizing this likelihood. However, they differ in the parameters over which we marginalize and optimize the likelihood. Whereas PPCA marginalizes over the latent variable and optimizes with respect to the mapping, the dual PPCA does it the other way round (i.e. marginalizing over the mapping parameter and optimizing with respect to latent variables). This forms the basic of GPLVMs. The good thing about these models is that, depending on a suitable choice of the prior's covariance function, these can be extended to non-linear settings as well (in fact, PCA turns out to be a special case when the covariance function is linear).

Stochastic Neighbor Embedding (SNE): The fundamental premise behind SNE is based on defining distributions of probabilistic similarities between neighboring points in original as well as embedded space. Then it tries to find a mapping which preserves this similarity, maximally, even after embedding. Essentially, we have similarity distributions over both the spaces and embedding is achieved by minimizing some sort of divergence function (KL divergence, for example) between the two distributions.

If we denote $p i j$ as the probability that point $i$ would choose point $j$ as its neighbor in the original space, and similarly denote $q i j$ as a similar probability defined in the embedded space, then the objective function to be minimized is the sum of KL divergences between distributions over the neighborhoods of each object. Mathematically, the cost to be minimized can be written as:

$C = \sum_{i}\sum_{j}p_{ij}\log \frac{p_{ij}}{q_{ij}}$

The inner summation represents summing over the entire neighborhood of point $i$ , the KL divergences between the distributions in original and embedded space, and the outer summation represents that we are summing over all such points.

The probabilities $p i j$ and $q i j$ are defined in terms of some sort of dissimilarity criteria between pair of objects (which could be scaled Euclidean distance, for example).

SNE also proposes a "multiple image model" which allows a point in some high dimensional space to have multiple images in the embedded space. An example could be the need for automatic disambiguation of homonyms, which may require using such an approach where a single word can have different images in low dimensional space, depending on the context. A correct embedding shouldn't let the images be collapsed. SNE, with its mixture version, does seem to exhibit robustness against such scenarios.

Questions/Discussions

6 June 07: Kernel Methods (Hal)

Brief background on kernels (from the review notes)... A Hilbert space is essentially a vector space endowed with a dot product. From the dot product, we can easily induce a norm, so all Hilbert spaces are normed. D-dimensional Euclidean space (aka "l_2") is the standard Hilbert space, but so is L_2, the space of all functions from R^D to R. The dot product for L_2 is $f \cdot g = \int dx f(x) g(x)$ . A reproducing kernel Hilbert space (RKHS) is a Hilbert space endowed with a reproducing kernel. Duh! The specific meaning of a reproducing kernel is given in the doc. We can revisit this in depth if we choose to move on to kernel methods later in the reading group. For now, what we care about is the following. We say that a function K is positive definite if $\int dx \int dx' f(x) K(x,x') f(x') > 0$ for all L_2 functions $f \neq 0$ . This is equivalent to saying that for a given data set, the kernel matrix for the data set is positive definite (in the usual matrix algebra sense). The first claim (proved in Section 6.4) is that given any p.d. kernel, we can construct a Hilbert space and mapping from our original space to this Hilbert space for which this kernel corresponds to a dot product. In other words, $K(x,x') = \Phi(x) \cdot \Phi(x')$ , where the dot product is taken in the Hilbert space. The converse is also true (but is trivial).

Kernel PCA: Recall that the solution to PCA is given by computing the eigenvectors of the data covariance matrix $S = \frac 1 N \sum_n x_n x_n^T$ . All we do is replace $x$ with its image under the feature mapping and obtain $S_{ij} = \frac 1 N K(x_i,x_j)$ , where $K$ is the corresponding kernel. Now, computing eigenvectors is like doing PCA in blown-up feature space. (Minor point: one must center the data in feature space.)

ISOMAP: Recall that ISOMap is the algorithm that uses distance in a graph. Here, we just do kernel PCA where $S$ is the matrix of half-squared distances in the graph. Note that this kernel is not always positive definite.

Graph Laplacian: Here, we again construct a graph based on local neighborhood and then minimizing a cost function for embedding. Here, the $S$ matrix is given by the pseudo-inverse of the Laplacian (which is already centered). I don't find this relationship particularly surprising, since the Laplacian formulation is essentially an eigen-problem anyway. (We'll skip the interpretation as diffusion.)

LLE: Here, we compute a weight matrix $W$ for reconstructing each point from his neighbors, then embed based on that matrix. To obtain a kernel PCA version, let $M = (I - W T)(I - W)$ and compute the maximal eigenvalue of this matrix, $λ m a x$ . Now, define $K = λ m a x I - M$ . Note that this is still a two-step procedure: we have to compute W as in standard LLE first.

At a high level, the result is that a lot of standard manifold algorithms can be interpreted as kernel PCA. I actually don't find this too surprising. Why? Kernel PCA is basically just solving an eigen-problem on some matrix. Most of the standard manifold learning algorithms are basically some sort of optimization over a quadratic form. Such optimizations often look like eigenproblems if you squint a little.

13 June 07: Application Day (Nathan and Eric)

Language (Nathan)

Main paper: Hierarchical Distributed Representations for Statistical Language Modeling

Auxiliary paper (not necessary, but helpful): Learning a kernel matrix for nonlinear dimensionality reduction - Explains Semidefinite embedding more thoroughly.

Many language tasks require a statistical model that can estimate the probability of a word occurring in a given context. One example of such a context model is an n-gram, which predicts a word given the preceding $n - 1$ words. This model is comparatively easy to understand and compute, but has the key weakness of data sparseness; i.e. that many possible word combinations occur infrequently.

Some common methods to cure the problem of data sparseness involves smoothing which normally involves taking away from the probability mass of frequently occurring events and giving it to less occurring combinations. The main paper makes the argument that smoothing does not take advantage of statistical regularities that may exist between contexts.

Two previous approaches to sharing statistical information across contexts have appeared in AMM and NPLM. The paper argues that both do not solve the problem adequately for they each have a specific ailment. The former does of not generalize to multiword contexts and the later imposes a normalization cost per conditional probability of each context, thus making training and application expensive.

The paper's proposed solution to these problems are where our friends dimensionality reduction and manifold learning come in to play.

Let $C$ be the matrix of bigram counts where element $C i j$ records the number of times word $w i$ precedes word $w j$ .

Let $p_{ij} = \frac{C_{ij}}{\sum_k C_{ik}}$ denote the conditional frequencies of the bigram counts and $\vec{p_i}$ denote the $V$ (vocabulary size) frequency vector of which each $p i j$ is an element of. With the cardinality of $V$ normally being over 50,000, clearly we need to reduce $\vec{p_i}$ dimensions somewhat. More formally, we need to map $\vec{p_i}$ to some $d$ -dimensional vector $\vec{x_i}$ such that $d \ll V$ .

Two ways this was done: PCA and Semidefinite embedding (SDE).

PCA: Works just as we've talked all summer. PCA computes a linear project of $\vec{p_i}$ into a lower dimensional subspace that maximizes their variance. Take the top $d$ eigenvectors of the frequency vector covariance matrix and your is mapping complete.

SDE: This method attempts to map words that are semantically similar closer together, and words that are semantically dissimilar further apart. This can be done using semidefinite programming...

Systems (Eric)

For some Internet applications, it is useful for hosts to be able to locate themselves in relation to others on the network. For example, a node in a peer-to-peer network can benefit by communicating with peers that are "close by" rather than peers that are far away.

In a computer network, distance is often measured in terms of round-trip time (RTT): the time required to get a message there and back again. Thus, a natural notion of position in a network is given by a Lipschitz embedding. The basic idea of a Lipschitz embedding is that distances are used as the components of a node's position. The ith index is an estimate of distance (RTT) to the ith node. The entire network can therefore be represented as a matrix, where the (i,j) element is the measured RTT between node i and node j.

The most naive approach to finding one's "position" is direct measurement. In this method, a node sends a message (or a stream of messages) to every other participating node in the network and measures the RTTs directly. This approach scales poorly in the required amount of measurement traffic, which is O(N^2).

The method described by Tang and Crovella overcomes this difficulties, toward the goal of making network location scalable.

In Tang and Crovella's method, a node need not communicate with all of its peers in order to locate itself. Instead, it only needs to estimate the distances between itself and a known set of so-called virtual landmarks. A virtual landmark is not a real node. Rather, it is an "imaginary" node whose distance from a given node can be estimated through a linear combination of measured distances to actual landmarks (nodes). An important property of a virtual landmark is that its distance can be estimated from measurements against different sets of actual landmarks. This helps prevent measurement "implosion" at any single actual landmark.

Thus, a node that needs to locate itself needs to measure RTTs between itself and relatively small set of actual landmarks, which are chosen at random from a larger set of actual landmarks.

The method relies on dimensionality reduction to make network location computationally efficient. The process is as follows:

To begin, one constructs a matrix M that encodes the distances between a set of m nodes and a set of n landmarks using a Lipschitz embedding. The sets of nodes and landmarks may be the same set, but do not need to be.

One then applies PCA to this matrix to reduce its dimensionality. In the authors' experience, 7 to 9 dimensions are sufficient to encode node positions with reasonable accuracy (~10% mean relative error). The PCA step yields an encoding of diatances to virtual landmarks instead of actual landmarks.

Later work, e.g., Lua et al. in IMC 2005, has criticized the method described above for not yielding sufficiently accurate network locations. Lua et al. write: "The published techniques appear to work very well when accuracy is measured using metrics such as absolute relative error. Our main observation is that absolute relative error tells us very little about the quality of an embedding as experienced by a user."

Network location systems continue to be an active area of systems research.

-- Eric 15:39, 12 June 2007 (MDT)

--nathan 16:42, 12 June 2007 (MDT)

15 August 07: Semi-supervised approaches to dimensionality reduction (Piyush)

Semi-supervised learning is known to help in cases where only little amount of labeled data is available at our disposal. It can help in a supervised learning settings where getting abundant quantity of labeled data is difficult. Semi-supervised learning uses a large amount of unlabeled data combined with a small amount of labeled data, and has been found to perform considerably well in such cases. At the same time, some amount of labeled data can also improve the performance of an unsupervised learning algorithm where essentially none of the data is labeled. An example of the latter is the use of semi-supervised learning for the problem of dimensionality reduction. It has been shown that, in the presence of prior information on the mapping of some of the data points, some of the dimensionality reduction techniques result in improved performances. Prior information can be typically made available by domain experts or from experiments. In manifold learning, for example, the prior information can be specified in form of on-manifold coordinates of some of the data points. Selection of prior points is a crucial aspect and needs careful considerations.

Suggested Papers

Manifold learning Resource page

Hierarchical Distributed Representations for Statistical Language Modeling. John Blitzer, Kilian Weinberger, Lawrence Saul, and Fernando Pereira. 18th annual conference on Neural Information Processing Systems - NIPS 2004.

Unsupervised learning of image manifolds by semidefinite programming. K. Q. Weinberger and L. K. Saul (2006). International Journal of Computer Vision

Learning a kernel matrix for nonlinear dimensionality reduction. K. Q. Weinberger, F. Sha, and L. K. Saul (2004). In Proceedings of the Twenty First International Confernence on Machine Learning (ICML-04)

Neighbourhood Component Analysis. Jacob Goldberger, Sam Roweis, Geoff Hinton, Ruslan Salakhutdinov (2004). Neural Information Processing Systems 17 (NIPS'04)

Hinton, G. E. and Salakhutdinov, R. R Reducing the dimensionality of data with neural networks. Science, Vol. 313. no. 5786, pp. 504 - 507, 28 July 2006.

Regression on manifolds using kernel dimension reduction. J. Nilsson, F. Sha, and M. I. Jordan. Proceedings of the 24th International Conference on Machine Learning (ICML), 2007.

A kernel view of the dimensionality reduction of manifolds. Jihun Ham, Daniel D. Lee, Sebastian Mika, Bernhard Schölkopf

Non-Local Manifold Tangent Learning. Yoshua Bengio, Martin Monperrus. NIPS 2004

Isometric Embedding and Continum ISOMAP. Hongyuan Zha, Zhenyue Zhang.

Analysis and Extension of Spectral Methods for Nonlinear Dimensionality Reduction. Fei Sha, Lawerence K. Saul.

Charting a Manifold. Matthew Brand.

Semi-supervised Nonlinear Dimensionality Reduction. Xin Yang, Haoying Fu, Hongyuan Zha, Jesse Barlow. Proceedings of the 23th International Conference on Machine Learning (ICML), 2006.

Stochastic Neighbor Embedding. Geoffrey Hinton, Sam Roweis.

Incremental Nonlinear Dimensionality Reduction By Manifold Learning. M. H. Law, A. K. Jain. IEEE Transactions of Pattern Analysis and Machine Intelligence.

Semi-Supervised Learning on Riemannian Manifolds. Mikhail Belkin, Partha Niyogi.

Riemannian Manifold Learning for Nonlinear Dimensionality Reduction. Tony Lin, Hongbin Zha, Sang Uk Lee.

Hessian Eigenmaps: new locally linear embedding techniques for high-dimensional data. David L. Donho, Carrie Grimes.

On Manifold Regularization. Mikhail Belkin, Partha Niyogi, Vikas Sindhwani.

Information Diffusion Kernels. John Lafferty, Guy Lebanon.

Nonlinear Projection with the Isotop Method. John A. Lee, Michel Verleysen.