visualizing Similarity Data with a Mixture of Maps: Difference between revisions

From statwiki
Jump to navigation Jump to search
Line 7: Line 7:
== Stochastic Neighbour Embedding ==
== Stochastic Neighbour Embedding ==
The core of SN method lies in converting high-dimensional distance or similarity data into a set of <math> p_{j|i} </math>, each of which represent the probability that one object <math> i </math> pick another object  <math> j </math> as its neighbour if it was only allowed to pick one neighbour. For objects in high dimensional Euclidian space, where our data points consists of the coordinates of the objects,  we can find <math> p_{j|i} </math> for each object <math> i </math> by using a spherical Gaussian distribution centered at the high-dimensional position of <math> i </math>, <math> X_{i} </math> . we will st <math> p_{i|i}  = 0</math> and for <math> j \neq i </math>,
The core of SN method lies in converting high-dimensional distance or similarity data into a set of <math> p_{j|i} </math>, each of which represent the probability that one object <math> i </math> pick another object  <math> j </math> as its neighbour if it was only allowed to pick one neighbour. For objects in high dimensional Euclidian space, where our data points consists of the coordinates of the objects,  we can find <math> p_{j|i} </math> for each object <math> i </math> by using a spherical Gaussian distribution centered at the high-dimensional position of <math> i </math>, <math> X_{i} </math> . we will st <math> p_{i|i}  = 0</math> and for <math> j \neq i </math>,
<center> <math> \mathbf  p_{j|i} = \frac{exp(-||x_i-x_j ||^2/s \sigma_i ^2  )}{\sum_{k \neq i} exp(-||x_i-x_k ||^2/s \sigma_i ^2  }</math> </center>

Revision as of 15:58, 4 July 2009

Introduction

The main idea of this paper is to show how we can utilize several different two-dimensional maps in order to visualize a set of pairwise similarities. Aspect maps resemble both clustering (in modeling pair-wise similarities as a mixture of different types of similarity) and multi-dimensional scaling (in modeling each type of similarity by a two-dimensional map) . While methods such as PCA and MDS (Metric Multi-dimensional Scaling) are simple and fast, their main drawback can be seen in minimizing a cost function that is mainly focused on modelling large dissimilarities rather than small ones. As a result of that they do not provide good visualizations of data that lies on a curved low-dimensional manifold in a high dimensional space. Also methods such as Local MDS, LLE, Maximum Variance Unfolding or Stochastic Neighbour Embedding (SNE) model local distances accurately in the two-dimensional visualization, but modelling of larger distances is done inaccurately.

SNE outweighs methods such as LLE in two ways: Despite difficulty of optimizing the SNE objective function, it leads to much better solutions and since SNE is based on probabilistic model, it is much more efficient in producing better visualization. In the next section, we will explain how SNE works.

Stochastic Neighbour Embedding

The core of SN method lies in converting high-dimensional distance or similarity data into a set of [math]\displaystyle{ p_{j|i} }[/math], each of which represent the probability that one object [math]\displaystyle{ i }[/math] pick another object [math]\displaystyle{ j }[/math] as its neighbour if it was only allowed to pick one neighbour. For objects in high dimensional Euclidian space, where our data points consists of the coordinates of the objects, we can find [math]\displaystyle{ p_{j|i} }[/math] for each object [math]\displaystyle{ i }[/math] by using a spherical Gaussian distribution centered at the high-dimensional position of [math]\displaystyle{ i }[/math], [math]\displaystyle{ X_{i} }[/math] . we will st [math]\displaystyle{ p_{i|i} = 0 }[/math] and for [math]\displaystyle{ j \neq i }[/math],


[math]\displaystyle{ \mathbf p_{j|i} = \frac{exp(-||x_i-x_j ||^2/s \sigma_i ^2 )}{\sum_{k \neq i} exp(-||x_i-x_k ||^2/s \sigma_i ^2 } }[/math]