Manifold Learning [unfinished]

By -

I. What is manifold learning

Dimensionality Reduction

    • The accuracy of the training algorithms is directly proportional to the amount of data we have. However, managing a large number of features is usually a burden to our algorithm. 
    • Some of these features may be irrelevant, so it's important to make sure that the final model doesn't get affected by this. 
    • What is Dimensionality? 
      • Dimensionality refers to the minimum number of coordinates needed to specify any point within a space or an object.
    • Why do we need Dimensionality Reduction?
      • If you keep the dimensionality high, it will be nice and unique but it may not be easy to analyse because of complexity involved.
      • Apart from simplifying data, visualization is also an interesting and challenging application.

Linear Dimensionality Reduction

    Fig 1: PCA illustration (source: http://evelinag.com/blog)

    • Principle Component Analysis 
      • Given a data set, PCA finds the directions along which the data has maximum variance in addition to the relative importance of these directions
      • Example:  Suppose that we feed a set of three-dimensional points that all lie on a two-dimensional plane to PCA. PCA will return two vectors that span the plane along with a third vector that is orthogonal to the plane. The two vectors that span the plane will be given a positive weight, but the third vector will have a weight of zero, since the data does not vary along that direction.
      •  PCA is most useful in the case when data lies on or close to a linear sub-space of the data set.
      • More discussion on PCA can be found here: wiki or here.

What is manifold learning?

    • What is manifold?
      • You can think of it as a surface of any shape. It doesn’t necessarily have to be a plane i.e. it can be shaped like a folded sheet with all the curves. 


Fig 2: data points are distributed in the shape of swiss roll
(source: what-is-manifold-learning )

    • What is manifold learning?
      • The manifold learning algorithms can be viewed as the non-linear version of PCA.
      • If you think about approaches like PCA, you will realize that we are projecting the data onto some low-dimensional surface. But this is restrictive in the sense that those surfaces are all linear. 
      •  Manifold learning comes with the assumption that the best representation lies in some weirdly shaped surface?
    • How do we visualize it? 
      • The assumption is that the data points are actually samples from a low-dimensional manifold that is embedded in a high-dimensional space. 
      •  Although the data points may consist of thousands of features, they may be described as a function of only a few underlying parameters. 
      • There are a lot of approaches to solve this problem such as Isomap, Locally Linear Embedding, etc. I will introduce some in the second part. 

II. Some manifold learning algorithms

  1. Isomap
    • Isomap can be viewed as an extension of Multi-dimensional Scaling (MDS).  
    • Isomap seeks a lower-dimensional embedding which maintains geodesic distances between all points. 
    • [24/10/2015] This link explains the graph-based technique to approximate the geodesic distances from the input matrix ( i.e. dissimilarity matrix).  
       
  2. Locally Linear Embedding
    • Locally linear embedding (LLE) seeks a lower-dimensional projection of the data which preserves distances within local neighborhoods. 
    • [31/10/2015] Here is detailed explanation for LLE. 
    • [31/10/2015] Pseudo code and illustration can be found here. 
  3. Multi-dimensional Scaling
    • Metric MDS
      • Metric MDS tries to preserve the absolute pairwise distance. 
    • Non-metric MDS (NMDS)
      • Non metric MDS focuses on the ordination of the data.
  4. t-distributed Stochastic Neighbor Embedding (t-SNE)
    • t-SNE (TSNE) converts affinities of data points to probabilities. The affinities in the original space are represented by Gaussian joint probabilities and the affinities in the embedded space are represented by Student’s t-distributions.
    • The Kullback-Leibler (KL) divergence of the joint probabilities in the original space and the embedded space will be minimized by gradient descent. 

REFERENCE

Comments

  1. Unknown2 October 2015 at 01:50

    t-SNE is considered the state-of-the-art embedding algorithm.

    ReplyDelete

Post a Comment

Popular posts from this blog

Find all pairs in array of integers whose sum is equal to a given number ?

By -
Problem: Write a program to find all pairs of integers whose sum is equal to a given number. For example if input integer array is {1, 2, 3, 4, 5}, and the given sum is 5, the code should return two pairs {1, 4} and {2, 3}. This is a common interview question related to array structure. A quick search on Google can return several pages discussing the problem, to list but a few [1,2, 3, 4]. Those pages only discuss the solutions at the conceptual level, without supporting comparing numbers, although they also provide the code. In this note I would re-implement all these approaches and compare their efficiency in practice. Common approaches There are four approaches which are often mentioned together: Brute-force, HashSet, sorting with search and sorting with binary search. Each has its own pros and cons. Interested readers can find the details in the list of sources below. Here is a summary of the storage complexity and computational complexity. Approach Storage co...
Read more

Feature scaling

By -
Image
1. What is feature scaling?  Feature scaling is a method used to normalize all independent values of our data. We also call it as data normalization and is generally performed before running machine learning algorithms. 2. Why do we need to use feature scaling?  In practice the range of raw data is very wide and hence the object functions will not work properly (means that it will stuck at local optimum), or they are time-consuming without normalization. For example:  K-Means, might give you totally different solutions depending on the preprocessing methods that you used. This is because an affine transformation implies a change in the metric space: the Euclidean distance between two samples will be different after that transformation. When we apply gradient descent, feature scaling also helps it to converge much faster that without normalized data.  With and without feature scaling in gradient descent 3. Methods in feature scaling? Rescaling The simp...
Read more