Jump to content

Semidefinite embedding

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by 198.53.109.35 (talk) at 00:27, 6 September 2020 (first, i'm going to randomly insert important articles that should be *inline* citations. later on i will try to mass-ahj them into the article. the lazy reference to the weinberger saul papers is just horawful). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Semidefinite embedding (SDE) or maximum variance unfolding (MVU) is an algorithm in computer science that uses semidefinite programming to perform non-linear dimensionality reduction of high-dimensional vectorial input data.[1][2][3] It was motivated by the observation that kernel Principal Component Analysis (kPCA) did not reduce the data dimensionality.[4]

Non-linear dimensionality reduction algorithms attempt to map high-dimensional data onto a low-dimensional Euclidean vector space. Maximum variance Unfolding is a member of the manifold learning family, which also include algorithms such as isomap and locally linear embedding. In manifold learning, the input data is assumed to be sampled from a low dimensional manifold that is embedded inside of a higher-dimensional vector space. The main intuition behind MVU is to exploit the local linearity of manifolds and create a mapping that preserves local neighbourhoods at every point of the underlying manifold.

MVU creates a mapping from the high dimensional input vectors to some low dimensional Euclidean vector space in the following steps:

A neighbourhood graph is created. Each input is connected with its k-nearest input vectors (according to Euclidean distance metric) and all k-nearest neighbors are connected with each other. If the data is sampled well enough, the resulting graph is a discrete approximation of the underlying manifold.

The neighbourhood graph is "unfolded" with the help of semidefinite programming. Instead of learning the output vectors directly, the semidefinite programming aims to find an inner product matrix that maximizes the pairwise distances between any two inputs that are not connected in the neighbourhood graph while preserving the nearest neighbors distances.

The low-dimensional embedding is finally obtained by application of multidimensional scaling on the learned inner product matrix.

The steps of applying semidefinite programming followed by a linear dimensionality reduction step to recover a low-dimensional embedding into a Euclidean space were first proposed by Linial, London, and Rabinovich.

Optimization Formulation

Let be the original input and be the embedding. If are two neighbors, then the local isometry constraint that needs to be satisfied is:

Let be the Gram matrices of and (i.e.: ). We can express the above constraint for every neighbor points in term of :

In addition, we also want to constrain the embedding to center at the origin:

As described above, except the distances of neighbor points are preserved, the algorithm aims to maximize the pairwise distance of every pair of points. The objective function to be maximized is:

Intuitively, maximizing the function above is equivalent to pulling the points as far away from each other as possible and therefore "unfold" the manifold. The local isometry constraint prevents the objective function from going to infinity. Proof:

Let where if i and j are neighbors and otherwise.

Since the graph has N points, the distance between any two points . We can then bound the objective function as follow:

The objective function can be rewritten purely in the form of the Gram matrix:

Finally, the optimization can be formulated as:

Maximize

Subject to and where

After the Gram matrix is learned by semidefinite programming, the output can be obtained via Cholesky decomposition. In particular, the Gram matrix can be written as where is the i-th element of eigenvector of the eigenvalue .

It follows that the -th element of the output is .

See also

References

  1. ^ Weinberger, Kilian Q.; Sha, Fei; Saul, Lawrence K. (4 July 2004). Learning a kernel matrix for nonlinear dimensionality reduction. Proceedings of the Twenty First International Conference on Machine Learning (ICML 2004). Banff, Alberta, Canada.
  2. ^ Weinberger, Kilian Q.; Saul, Lawrence K. (27 June 2004). Unsupervised learning of image manifolds by semidefinite programming. 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Vol. 2.
  3. ^ Weinberger, Kilian Q.; Saul, Lawrence K. (1 May 2006). "Unsupervised learning of image manifolds by semidefinite programming" (PDF). International Journal of Computer Vision. 70. doi:10.1007/s11263-005-4939-z.
  4. ^ Lawrence, Neil D (2012). "A unifying probabilistic perspective for spectral dimensionality reduction: insights and new models". Journal of Machine Learning Research. 13 (May): 1612. arXiv:1010.4830. Bibcode:2010arXiv1010.4830L.

Additional material