t-SNE

t-SNE is a non-linear dimensionality reduction technique that is well suited as a visualization technique as its goal is to reduce the dimensionality to 2 or 3 dimensions. The ideal goal of visualization is to build a map in low dimensional space that reflects the similarities in the original space. Popular dimensionality reduction techniques like PCA are not very useful for this purpose because the goal of PCA is to maximize variance which is the same as trying to minimize the squared error between distances in the original data and the map and hence this leads to preserving large pairwise distance in the map. However large pairwise distances are not always reliable and on the other small distances between neighbors is reliable. Techniques relying upon preserving neighboring distance are Isomap, LLE, SNE and t-SNE.

t-SNE is based upon the SNE (stochastic neighbor embedding) algorithm and places a Gaussian around every point in the high dimensional space and then measure the density at all the other points w.r.t the point. In other words it represents a probability distribution over a pair of points which represents the similarity between the points.

The basic idea is as follows:
t-SNE first computes the pairwise affinities between points as -
p ij = pj|i + pi|j where,
pj|i = exp( || xi - xj ||2 /2σi2) / ∑ k≠i exp( || xi - xk ||2 /2σi2)

Note that a different bandwidth σi associated w.r.t every point. The σi is set in such a way that the conditional distribution has a fixed perplexity. This helps in setting the σi to a very low value for dense points. The goal of t-SNE is to learn a low dimensional mapping from y1, ...yN that reflects the similarities pij. The similarities qij between the low dimensional points is obtained using a heavy tailed student-t distribution as
qij = ( 1 + || yi - yj||2) -1 / ∑ k≠l ( 1 + || yk - yl||2) -1
t-SNE aims to minimize the KL divergence between the two distributions P and Q using gradient descent.

Future Work
  1. Scalability is still a major issue with the algorithm. The fastest implementation available takes a couple of hours for a million data points.

References
  1. Van der Maaten, Laurens, and Geoffrey Hinton. "Visualizing data using t-SNE."Journal of Machine Learning Research 9.2579-2605 (2008): 85.
  2. Laurens excellent talk on the topic.


Comments

Post a Comment

Popular posts from this blog

MinHash, Bloom Filters and LSH

Lets talk about some large scale algorithms widely used in the document world. MinHash: Minhash is a really cute algorithm to determine how does a document compare to another. One simple way to compute document similarity is to compute the jaccard similarity between them. The jaccard similarity between the documents is computed as follows: def jaccard_similarity(set1: set, set2: set): if len(set1) == 0 or len(set2) == 0: return 0.0 common = len(set1.intersection(set2)) if common == 0: return 0.0 union = len(set1.union(set2)) return common / union One problem with Jaccard similarity is that it can take a lot of time to compute especially for large scale documents. The idea behind minhashing is to first operate on the space of document shingles. Shingles are basically any combination of k consecutive words of the document. For example, for the sentence "hi i am jaya" the possible 3 shingles are "hi i am" and "i am jaya...
Read more

Perceptron Algorithm

Image
The perceptron algorithm is a linear classifier using a linear function (w'x + b) to classify the points into two classes. The loss function for the perceptron algorithm just counts the points misclassified and then incrementally adjusts the weight vector and thus the decision boundary to appropriately classify the two classes. Perhaps this is the simplest algorithm one can think of to update the weight vector and is shown as follows: w(k+1) = w(k) + yt*xt if yt ≠ f(xt; w) i.e. we cycle through the training points and adjust the weight vector only if the points are misclassified. Note that our class labels are -1 and 1 and hence if the points are misclassified then y_t* f(xt; w) will be negative. In order to understand why the seemingly simple update rule works and leads to a convergence, lets closely examine it. One of the underlying assumption in the perceptron model is that the points are linearly separated hence there exists an w* such that y_t * f(xt; w*) ≥ γ for all...
Read more

Logistic Regression

The logistic regression method even though called regression has a unique ability to give posterior probability values for a data point to belong to a particular class and hence serve as a discriminative function useful for classification. The idea is simple, to use the logistic sigmoid function on the linear function of feature vector. p(y = 1| x) = σ(w'x +b) The likelihood function can be written as p(t|w) = Π y_i^t_i*(1 - y_i)^(1 - t_i) ln p(t|w) = Σ t_i*ln(y_i) + (1 - t_i)*ln(1 - y_i) The error function is computed by taking the negative of the log likelihood function and is computed as follows: E(w) = -ln p(t|w) Now, ∇E(w) is computed as follows: y = 1 / (1 + exp(-w'x) Taking derivative of both sides, ∇y/∇w = exp(-w'x)(x)/(1 + exp(-w'x))^2 ∇y/∇w = xy(1-y) Substituting the value in ∇E(w), we get ∇ E(w) = Σ (y_i - t_i)*x_i The derivative of the error function is similar to the least squares problem, although w...
Read more