/*
 * Copyright (C) 2015 Edward Raff
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see .
 */
package jsat.datatransform.visualization;

import java.util.*;
import java.util.concurrent.CountDownLatch;
import jsat.DataSet;
import jsat.classifiers.DataPoint;
import jsat.datatransform.*;
import jsat.distributions.Normal;
import jsat.linear.*;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.linear.vectorcollection.DefaultVectorCollection;
import jsat.linear.vectorcollection.VectorCollection;
import jsat.math.FastMath;
import jsat.math.optimization.stochastic.*;
import jsat.math.rootfinding.Zeroin;
import jsat.utils.SystemInfo;
import jsat.utils.concurrent.AtomicDouble;
import jsat.utils.concurrent.ParallelUtils;
import jsat.utils.random.RandomUtil;

/**
 * t-distributed Stochastic Neighbor Embedding is an algorithm for creating low
 * dimensional embeddings of datasets, for the purpose of visualization. It
 * attempts to keep points that are near each other in the original space near
 * each other in the low dimensional space as well, with less emphasis on
 * maintaining far-away relationships in the data. This implementation uses the
 * approximated gradients to learn the embedding in O(n log n) time.
*
* If the input dataset has a dimension greater than 50, it is advisable to * project the data set down to 50 dimensions using {@link PCA} or some similar * technique.
*
* See:
*
    *
  • Maaten, L. Van Der, & Hinton, G. (2008). Visualizing Data using * t-SNE. Journal of Machine Learning Research, 9, 2579–2605.
  • *
  • Van der Maaten, L. (2014). Accelerating t-SNE using Tree-Based * Algorithms. Journal of Machine Learning Research, 15, 3221–3245. * Retrieved from * here
  • *
* * @author Edward Raff */ public class TSNE implements VisualizationTransform { private double alpha = 4; private double exageratedPortion = 0.25; private DistanceMetric dm = new EuclideanDistance(); private int T = 1000; private double perplexity = 30; private double theta = 0.5; /** * The target embedding dimension, hard coded to 2 for now */ private int s = 2; /** * α is the "early exaggeration" constant. It is a multiple applied to * part of the gradient for th first quarter of iterations, and can improve * the quality of the solution found. A value in the range of [4, 20] is * recommended. * * @param alpha the exaggeration constant */ public void setAlpha(double alpha) { if(alpha <= 0 || Double.isNaN(alpha) || Double.isInfinite(alpha)) throw new IllegalArgumentException("alpha must be positive, not " + alpha); this.alpha = alpha; } /** * * @return the "early exaggeration" constant */ public double getAlpha() { return alpha; } /** * Sets the target perplexity of the gaussian used over each data point. The * perplexity can be thought of as a quasi desired number of nearest * neighbors to be considered, but is adapted based on the distribution of * the data. Increasing the perplexity can increase the amount of time it * takes to get an embedding. Using a value in the range of [5, 50] is * recommended. * * @param perplexity the quasi number of neighbors to consider for each data point */ public void setPerplexity(double perplexity) { if(perplexity <= 0 || Double.isNaN(perplexity) || Double.isInfinite(perplexity)) throw new IllegalArgumentException("perplexity must be positive, not " + perplexity); this.perplexity = perplexity; } /** * * @return the target perplexity to use for each data point */ public double getPerplexity() { return perplexity; } /** * Sets the desired number of gradient descent iterations to perform. * @param T the number of gradient descent iterations */ public void setIterations(int T) { if(T <= 1) throw new IllegalArgumentException("number of iterations must be positive, not " + T); this.T = T; } /** * * @return the number of gradient descent iterations to perform */ public int getIterations() { return T; } @Override public Type transform(DataSet d, boolean parallel) { Random rand = RandomUtil.getRandom(); final int N = d.getSampleSize(); //If perp set too big, the search size would be larger than the dataset size. So min to N /** * form sec 4.1: "we compute the sparse approximation by finding the * floor(3u) nearest neighbors of each of the N input objects (recall * that u is the perplexity of the conditional distributions)" */ final int knn = (int) Math.min(Math.floor(3*perplexity), N-1); /** * P_ij does not change at this point, so lets compute these values only * once please! j index matches up to the value stored in nearMe */ final double[][] nearMePij = new double[N][knn]; /** * Each row is the set of 3*u indices returned by the NN search */ final int[][] nearMe = new int[N][knn]; computeP(d, parallel, rand, knn, nearMe, nearMePij, dm, perplexity); Normal normalDIst = new Normal(0, 1e-4); /** * For now store all data in a 2d array to avoid excessive overhead / cache missing */ final double[] y = normalDIst.sample(N*s, rand); final double[] y_grad = new double[y.length]; //vec wraped version for convinence final Vec y_vec = DenseVector.toDenseVec(y); final Vec y_grad_vec = DenseVector.toDenseVec(y_grad); GradientUpdater gradUpdater = new Adam(); gradUpdater.setup(y.length); for (int iter = 0; iter < T; iter++)//optimization { final int ITER = iter; Arrays.fill(y_grad, 0); //First loop for the F_rep forces, we do this first to normalize so we can use 1 work space for the gradient final Quadtree qt = new Quadtree(y); //TODO might not result in even load double Z = ParallelUtils.run(parallel, N, (start, end)-> { double[] workSpace = new double[s]; double local_Z = 0; for (int i = start; i < end; i ++) { Arrays.fill(workSpace, 0.0); local_Z += computeF_rep(qt.root, i, y, workSpace); //should be multiplied by 4, rolling it into the normalization by Z after for (int k = 0; k < s; k++) inc_z_ij(workSpace[k], i, k, y_grad, s); } return local_Z; }, (a,b)->a+b); //normalize by Z final double zNorm = 4.0/(Z+1e-13); for(int i = 0; i < y.length; i++) y_grad[i] *= zNorm; //This second loops computes the F_attr forces final CountDownLatch latch_g1 = new CountDownLatch(SystemInfo.LogicalCores); ParallelUtils.run(parallel, N, (start,end)-> { for (int i = start; i < end; i++)//N { for(int j_indx = 0; j_indx < knn; j_indx ++) //O(u) { int j = nearMe[i][j_indx]; if(i == j)//this should never happen b/c we skipped that when creating nearMe continue; double pij = nearMePij[i][j_indx]; if(ITER < T*exageratedPortion) pij *= alpha; double cnst = pij*q_ijZ(i, j, y, s)*4; for(int k = 0; k < s; k++) { double diff = z_ij(i, k, y, s)-z_ij(j, k, y, s); inc_z_ij(cnst*diff, i, k, y_grad, s); } } } }); //now we have accumulated all gradients double eta = 200; gradUpdater.update(y_vec, y_grad_vec, eta); } DataSet transformed = d.shallowClone(); final IdentityHashMap indexMap = new IdentityHashMap<>(N); for(int i = 0; i < N; i++) indexMap.put(d.getDataPoint(i), i); transformed.applyTransform(new DataTransform() { @Override public DataPoint transform(DataPoint dp) { int i = indexMap.get(dp); DenseVector dv = new DenseVector(s); for(int k = 0; k < s; k++) dv.set(k, y[i*2+k]); return new DataPoint(dv, dp.getCategoricalValues(), dp.getCategoricalData(), dp.getWeight()); } @Override public void fit(DataSet data) { } @Override public DataTransform clone() { return this; } }); return (Type) transformed; } /** * * @param d the dataset to search * @param parallel {@code true} if computation should be done with multiple threads, {@code false} for single threaded * @param rand source of randomness * @param knn the number of neighbors to search for * @param nearMe each row is the set of knn indices returned by the NN search * @param nearMePij the symmetrized neighbor probability * @param dm the distance metric to use for determining closeness * @param perplexity the perplexity value for the effective nearest neighbor search and weighting */ protected static void computeP(DataSet d, boolean parallel, Random rand, final int knn, final int[][] nearMe, final double[][] nearMePij, final DistanceMetric dm, final double perplexity) { @SuppressWarnings("unchecked") final List vecs = d.getDataVectors(); final List accelCache = dm.getAccelerationCache(vecs, parallel); final int N = vecs.size(); final VectorCollection vc = new DefaultVectorCollection<>(); vc.build(parallel, vecs, dm); final List>> neighbors = new ArrayList<>(N); for(int i = 0; i < N; i++) neighbors.add(null); //new scope b/c I don't want to leark the silly vecIndex thing { //Used to map vecs back to their index so we can store only the ones we need in nearMe final IdentityHashMap vecIndex = new IdentityHashMap<>(N); for(int i = 0; i < N; i++) vecIndex.put(vecs.get(i), i); ParallelUtils.run(parallel, N, (i)-> { Vec x_i = vecs.get(i); List> closest = vc.search(x_i, knn+1);//+1 b/c self is closest neighbors.set(i, closest); for (int j = 1; j < closest.size(); j++) { nearMe[i][j - 1] = vecIndex.get(closest.get(j).getVector()); } }); } //Now lets figure out everyone's sigmas final double[] sigma = new double[N]; final AtomicDouble minSigma = new AtomicDouble(Double.POSITIVE_INFINITY); final AtomicDouble maxSigma = new AtomicDouble(0); for(int i = 0; i < N; i++)//first lets figure out a min/max range { List> n_i = neighbors.get(i); double min = n_i.get(1).getPair(); double max = n_i.get(Math.min(knn, n_i.size()-1)).getPair(); minSigma.set(Math.min(minSigma.get(), Math.max(min, 1e-9)));//avoid seting 0 as min maxSigma.set(Math.max(maxSigma.get(), max)); } //now compute the bandwidth for each datum ParallelUtils.run(parallel, N, (i)-> { boolean tryAgain = false; do { tryAgain = false; try { double sigma_i = Zeroin.root(1e-2, 100, minSigma.get(), maxSigma.get(), (double x) -> perp(i, nearMe, x, neighbors, vecs, accelCache, dm) - perplexity); sigma[i] = sigma_i; } catch (ArithmeticException exception)//perp not in search range? { if(maxSigma.get() >= Double.MAX_VALUE/2) { //Why can't we find a range that fits? Just pick a value.. //Not max value, but data is small.. so lets just set someting to break the loop sigma[i] = 1e100; } else { tryAgain = true; minSigma.set(Math.max(minSigma.get() / 2, 1e-6)); maxSigma.set(Math.min(maxSigma.get() * 2, Double.MAX_VALUE / 2)); } } } while (tryAgain); }); ParallelUtils.run(parallel, N, (i)-> { for(int j_indx = 0; j_indx < knn; j_indx++) { int j = nearMe[i][j_indx]; nearMePij[i][j_indx] = p_ij(i, j, sigma[i], sigma[j], neighbors, vecs, accelCache, dm); } }); } /** * * @param node the node to begin computing from * @param i * @param z * @param workSpace the indicies are the accumulated contribution to the * gradient sans multiplicative terms in the first 2 indices. * @return the contribution to the normalizing constant Z */ private double computeF_rep(Quadtree.Node node, int i, double[] z, double[] workSpace) { if(node == null || node.N_cell == 0 || node.indx == i) return 0; /* * Original paper says to use the diagonal divided by the squared 2 * norm. This dosn't seem to work at all. Tried some different ideas * with 0.5 as the threshold until I found one that worked. * Squaring the values would normally not be helpful, but since we are working with tiny values it makes them smaller, making it easier to hit the go */ double x = z[i*2]; double y = z[i*2+1]; // double r_cell = node.diagLen(); double r_cell = Math.max(node.maxX-node.minX, node.maxY-node.minY); r_cell*=r_cell; double mass_x = node.x_mass/node.N_cell; double mass_y = node.y_mass/node.N_cell; double dot = (mass_x-x)*(mass_x-x)+(mass_y-y)*(mass_y-y); if(node.NW == null || r_cell < theta*dot)//good enough! { if(node.indx == i) return 0; double Z = 1.0/(1.0 + dot); double q_cell_Z_sqrd = -node.N_cell*(Z*Z); workSpace[0] += q_cell_Z_sqrd*(x-mass_x); workSpace[1] += q_cell_Z_sqrd*(y-mass_y); return Z*node.N_cell; } else//further subdivide { double Z_sum = 0; for(Quadtree.Node child : node) Z_sum += computeF_rep(child, i, z, workSpace); return Z_sum; } } /** * * @param val the value to add to the array * @param i the index of the data point to add to * @param j the dimension index of the embedding * @param z the storage of the embedded vectors * @param s the dimension of the embedding */ private static void inc_z_ij(double val, int i, int j, double[] z, int s) { z[i*s+j] += val; } private static double z_ij(int i, int j, double[] z, int s) { return z[i*s+j]; } /** * Computes the value of qij Z * @param i * @param j * @param z * @param s * @return */ private static double q_ijZ(int i, int j, double[] z, int s) { double denom =1; for(int k = 0; k < s; k++) { double diff = z_ij(i, k, z, s)-z_ij(j, k, z, s); denom += diff*diff; } return 1.0/denom; } /** * Computes pj|i * @param j * @param i * @param sigma * @param neighbors * @return */ private static double p_j_i(int j, int i, double sigma, List>> neighbors, List vecs, List accelCache, DistanceMetric dm) { /* * "Because we are only interested in modeling pairwise similarities, we * set the value of pi|i to zero" from Visualizing Data using t-SNE */ if(i == j) return 0; //nearest is self, use taht to get indexed values Vec x_j = neighbors.get(j).get(0).getVector(); // Vec x_i = neighbors.get(i).get(0).getVector(); final double sigmaSqrdInv = 1/(2*(sigma*sigma)); double numer = 0; double denom = 0; boolean jIsNearBy = false; final List> neighbors_i = neighbors.get(i); for (int k = 1; k < neighbors_i.size(); k++)//SUM over k != i { VecPaired neighbor_ik = neighbors_i.get(k); final double d_ik = neighbor_ik.getPair(); denom += FastMath.exp(-(d_ik*d_ik)*sigmaSqrdInv); if(neighbor_ik.getVector() == x_j)//intentionally doing object equals check - should be same object { jIsNearBy = true;//yay, dont have to compute the distance ourselves numer = FastMath.exp(-(d_ik*d_ik) * sigmaSqrdInv); } } if(!jIsNearBy) { double d_ij = dm.dist(i, j, vecs, accelCache); numer = FastMath.exp(-(d_ij*d_ij) * sigmaSqrdInv); } return numer/(denom+1e-9); } private static double p_ij(int i, int j, double sigma_i, double sigma_j, List>> neighbors, List vecs, List accelCache, DistanceMetric dm) { return (p_j_i(j, i, sigma_i, neighbors, vecs, accelCache, dm)+p_j_i(i, j, sigma_j, neighbors, vecs, accelCache, dm))/(2*neighbors.size()); } /** * Computes the perplexity for the specified data point using the given sigma * @param i the data point to get the perplexity of * @param sigma the bandwidth to use * @param neighbors the set of nearest neighbors to consider * @return the perplexity 2H(Pi) */ private static double perp(int i, int[][] nearMe, double sigma, List>> neighbors, List vecs, List accelCache, DistanceMetric dm) { //section 2 of Maaten, L. Van Der, & Hinton, G. (2008). Visualizing Data using t-SNE. Journal of Machine Learning Research, 9, 2579–2605. double hp = 0; for(int j_indx =0; j_indx < nearMe[i].length; j_indx++) { double p_ji = p_j_i(nearMe[i][j_indx], i, sigma, neighbors, vecs, accelCache, dm); if (p_ji > 0) hp += p_ji * FastMath.log2(p_ji); } hp *= -1; return FastMath.pow2(hp); } private class Quadtree { public Node root; public Quadtree(double[] z ) { this.root = new Node(); this.root.minX = this.root.minY = Double.POSITIVE_INFINITY; this.root.maxX = this.root.maxY = -Double.POSITIVE_INFINITY; for(int i = 0; i < z.length/2; i++) { double x = z[i*2]; double y = z[i*2+1]; this.root.minX = Math.min(this.root.minX, x); this.root.maxX = Math.max(this.root.maxX, x); this.root.minY = Math.min(this.root.minY, y); this.root.maxY = Math.max(this.root.maxY, y); } //done b/c we have <= on min, so to get the edge we need to be slightly larger this.root.maxX = Math.nextUp(this.root.maxX); this.root.maxY = Math.nextUp(this.root.maxY); //nowe start inserting everything for(int i = 0; i < z.length/2; i++) root.insert(1, i, z); } private class Node implements Iterable { public int indx; public double x_mass, y_mass; public int N_cell; public double minX, maxX, minY, maxY; public Node NW, NE, SE, SW; public Node() { indx = -1; N_cell = 0; x_mass = y_mass = 0; NW = NE = SE = SW = null; } public Node(double minX, double maxX, double minY, double maxY) { this(); this.minX = minX; this.maxX = maxX; this.minY = minY; this.maxY = maxY; } public boolean contains(int i, double[]z) { double x = z[i*2]; double y = z[i*2+1]; return minX <= x && x < maxX && minY <= y && y < maxY; } public void insert(int weight, int i, double[] z) { x_mass += z[i*2]; y_mass += z[i*2+1]; N_cell+=weight; if(NW == null && indx < 0)//was empy, just set indx = i; else { if(indx >=0) { if(Math.abs(z[indx*2]- z[i*2]) < 1e-13 && Math.abs(z[indx*2+1]- z[i*2+1]) < 1e-13) { //near exact same value //just let increase local weight indicate a "heavier" leaf return; } } if(NW == null)//we need to split { double w2 = (maxX-minX)/2; double h2 = (maxY - minY)/2; NW = new Node(minX, minX + w2, minY + h2, maxY); NE = new Node(minX + w2, maxX, minY + h2, maxY); SW = new Node(minX, minX + w2, minY, minY + h2); SE = new Node(minX + w2, maxX, minY, minY + h2); for(Node child : this) if(child.contains(this.indx, z)) { child.insert(this.N_cell, this.indx, z); break; } indx = -1; } //and pass this along to our children for(Node child : this) if(child.contains(i, z)) { child.insert(weight, i, z); break; } } } public double diagLen() { double w = maxX-minX; double h = maxY-minY; return Math.sqrt(w*w+h*h); } @Override public Iterator iterator() { if(NW == null) return Collections.emptyIterator(); else return Arrays.asList(NW, NE, SW, SE).iterator(); } } } //Current implementation only supports 2D, so hard code it. @Override public int getTargetDimension() { return 2; } @Override public boolean setTargetDimension(int target) { return target == 2; } }

Ads help maintain this website.