/*
* Copyright (C) 2016 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 java.util.concurrent.ExecutorService;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.logging.Level;
import java.util.logging.Logger;
import jsat.DataSet;
import jsat.classifiers.DataPoint;
import jsat.datatransform.DataTransform;
import jsat.distributions.Uniform;
import jsat.linear.DenseVector;
import jsat.linear.Vec;
import jsat.linear.distancemetrics.DistanceMetric;
import jsat.linear.distancemetrics.EuclideanDistance;
import jsat.utils.FakeExecutor;
import jsat.utils.SystemInfo;
import jsat.utils.concurrent.ParallelUtils;
import jsat.utils.random.RandomUtil;
import jsat.utils.random.XORWOW;
/**
* LargeViz is an algorithm for creating low dimensional embeddings for
* visualization. It is meant to be faster and better quality than
* {@link TSNE t-SNE} without requiring any parameter tuning to get good
* results. LargeViz is related to t-SNE in how the neighbor graph is
* constructed, and the {@link #setPerplexity(double) perplexity} parameter for
* LargeViz has the same meaning and impact as the perplexity parameter in
* t-SNE.
*
* NOTE: The origina LargeViz paper includes a faster scheme for approximately
* constructing the nearest neighbor graph. This is not yet implemented, but has
* no negative impact on the quality of the result.
*
* See: Tang, J., Liu, J., Zhang, M., & Mei, Q. (2016). Visualizing Large-scale
* and High-dimensional Data. In Proceedings of the 25th International
* Conference on World Wide Web (pp. 287–297). Republic and Canton of Geneva,
* Switzerland: International World Wide Web Conferences Steering Committee.
* doi:10.1145/2872427.2883041
* @author Edward Raff
*/
public class LargeViz implements VisualizationTransform
{
private DistanceMetric dm_source = new EuclideanDistance();
private DistanceMetric dm_embed = new EuclideanDistance();
private double perplexity = 50;
private int dt = 2;
/**
* This is the number of negative samples to take for each vertex
* "number of negative samples is set as 5"
*/
private int M = 5;
/**
* "γ is set as 7 by default"
*/
private double gamma = 7;
/**
* 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, 100] 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 distance metric to use for the original space. This will
* determine the target nearest neighbors to keep close to each other in
* the embedding space
*
* @param dm the distance metric to use
*/
public void setDistanceMetricSource(DistanceMetric dm)
{
this.dm_source = dm;
}
/**
* Sets the distance metric to use for the embedded space. This will
* determine the actual nearest neighbors as the occur in the embedded space.
*
* @param dm the distance metric to use
*/
public void setDistanceMetricEmbedding(DistanceMetric dm)
{
this.dm_embed = dm;
}
/**
* Sets the number of negative neighbor samples to obtain for each data
* point. The default recommended value is 5.
*
* @param M the number of negative samples to use for each update
*/
public void setNegativeSamples(int M)
{
if(M < 1)
throw new IllegalArgumentException("Number of negative samples must be positive, not " + M);
this.M = M;
}
/**
*
* @return the number of negative samples to use for each update
*/
public int getNegativeSamples()
{
return M;
}
/**
* Gamma controls the negative weight assigned to negative edges in the
* optimization problem. Large values will place a higher emphasis on
* separating non-neighbors in the embedded space. The default recommend
* value is 7.
*
* @param gamma the weight for negative edge samples
*/
public void setGamma(double gamma)
{
if(Double.isInfinite(gamma) || Double.isNaN(gamma) || gamma <= 0)
throw new IllegalArgumentException("Gamma must be positive, not " + gamma);
this.gamma = gamma;
}
/**
*
* @return the weight for negative edge samples
*/
public double getGamma()
{
return gamma;
}
@Override
public int getTargetDimension()
{
return dt;
}
@Override
public boolean setTargetDimension(int target)
{
if(target < 2)
return false;
dt = target;
return true;
}
@Override
public Type transform(DataSet d, boolean parallel)
{
Random rand = RandomUtil.getRandom();
final ThreadLocal local_rand = ThreadLocal.withInitial(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.
* Would be W_ij in notation of LargeViz paper, but P_ij form TSNE paper
*/
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];
TSNE.computeP(d, parallel, rand, knn, nearMe, nearMePij, dm_source, perplexity);
final double[][] nearMeSample = new double[N][knn];
/**
* Array of the sample weights used to perform the negative sampling.
*
* Initial value is out-degree defined in LINE paper, section 4.1.2.
*/
final double[] negSampleWeight = new double[N];
double negSum = 0;
for(int i = 0; i < N; i++)
{
double sum = DenseVector.toDenseVec(nearMePij[i]).sum();
sum += nearMePij[i].length*Double.MIN_VALUE;
negSampleWeight[i] = sum;
nearMeSample[i][0] = nearMePij[i][0];
for(int j = 1; j < knn; j++)//make cumulative
nearMeSample[i][j] = Math.ulp(nearMePij[i][j]) + nearMePij[i][j] + nearMeSample[i][j-1];
for(int j = 1; j < knn; j++)//normalize
nearMeSample[i][j] /= sum;
negSampleWeight[i] = Math.pow(negSampleWeight[i], 0.75);
negSum += negSampleWeight[i];
if(i > 0)
negSampleWeight[i] += negSampleWeight[i-1];
}
//normalize to [0, 1] range
for(int i = 0; i < N; i++)
negSampleWeight[i]/= negSum;
final List embeded = new ArrayList<>();
Uniform initDistribution = new Uniform(-0.00005/dt, 0.00005/dt);
for(int i = 0; i < N; i++)
embeded.add(initDistribution.sampleVec(dt, rand));
/**
* Number of threads to use. Paper suggests asynch updates and just
* ignore unsafe alters b/c diff should be minor. Adding some extra
* logic so that we have at least a good handful of points per thread to
* avoid excessive edits on small datasets.
*/
final int threads_to_use = Math.max(Math.min(N/(200*M), SystemInfo.LogicalCores), 1);
final CountDownLatch latch = new CountDownLatch(threads_to_use);
/*
* Objective is
* w*(log(1/(1+g(x)^2)) + y log(1−1/(1+g(x)^2 )))
* where g(x) is the euclidean distance adn G(x) is g(x)^2
* d/x of ||x-y|| = (x-y)/||x-y||
* d/y of ||x-y|| = -(x-y)/||x-y||
* left hand side derivative of log(1/(1+g(x))) =
* = -(2 g(x) g'(x))/(g(x)^2+1)
* = -(2 ||x-y|| (x-y)/||x-y||)/(||x-y||^2+1)
* = -(2 (x-y))/(||x-y||^2+1)
* for d/y
* = -(2 (y-x))/(||x-y||^2+1)
*
* Right hand side portion
* derivative of z* log(1-1/(1+g(x)^2))
* = (2 z g'(x))/(g(x) (g(x)^2+1))
* = (2 z (x-y))/(||x-y||^2 (||x-y||^2+1))
* or for d/y
* = (2 z (y-x))/(||x-y||^2 (||x-y||^2+1))
* NOTE: My derivative dosn't work. But adding
* an extra multiplication by ||x-y|| seems to fix everything? Want to
* come back and figure this out better.
*/
final double eta_0 = 1.0;
final long iterations = 1000L*N;
final ThreadLocal local_grad_i = ThreadLocal.withInitial(()->new DenseVector(dt));
final ThreadLocal local_grad_j = ThreadLocal.withInitial(()->new DenseVector(dt));
final ThreadLocal local_grad_k = ThreadLocal.withInitial(()->new DenseVector(dt));
AtomicLong curIteration = new AtomicLong();
ParallelUtils.run(parallel, N, (start, end)->
{
Random l_rand = local_rand.get();
//b/c indicies are selected at random everyone can use same iterator order
//more important is to make sure the range length is the same so that
//eta has the same range and effect in aggregate
//To avoid issues with large datests, we want 1000 * N iterations
//so do an iteration of our N/P 1000 times to get the correct amount
for(int moreTimes = 0; moreTimes < 1000; moreTimes++)
for(int iter = start; iter < end; iter++ )
{
double eta = eta_0*(1-curIteration.getAndIncrement()/(double)iterations);
eta = Math.max(eta, 0.0001);
int i = l_rand.nextInt(N);
//sample neighbor weighted by distance
int j = Arrays.binarySearch(nearMeSample[i], l_rand.nextDouble());
if (j < 0)
j = -(j) - 1;
if(j >= knn)///oops. Can be hard to sample / happen with lots of near by near 0 dists
{
//lets fall back to picking someone at random
j = l_rand.nextInt(knn);
}
j = nearMe[i][j];
Vec y_i = embeded.get(i);
Vec y_j = embeded.get(j);
//right hand side update for the postive sample
final double dist_ij = dm_embed.dist(i, j, embeded, null);
final double dist_ij_sqrd = dist_ij*dist_ij;
if(dist_ij <= 0 )
continue;//how did that happen?
Vec grad_i = local_grad_i.get();
Vec grad_j = local_grad_j.get();
Vec grad_k = local_grad_k.get();
y_i.copyTo(grad_j);
grad_j.mutableSubtract(y_j);
grad_j.mutableMultiply(-2*dist_ij/(dist_ij_sqrd+1));
grad_j.copyTo(grad_i);
//negative sampling time
for(int k = 0; k < M; k++)
{
int jk = -1;
do
{
jk = Arrays.binarySearch(negSampleWeight, l_rand.nextDouble());
if (jk < 0)
jk = -(jk) - 1;
if(jk == i || jk == j)
jk = -1;
//code to reject neighbors for sampling if too close
//Not sure if this code helps or hurts... not mentioned in paper
for(int search = 0; search < nearMe[i].length; search++)
if(nearMe[i][search] == jk && nearMeSample[i][search] < 0.98)
{
jk = -1;//too close to me!
break;
}
}
while(jk < 0);
//(2 z (y-x))/(||x-y||^2 (||x-y||^2+1))
Vec y_k = embeded.get(jk);
final double dist_ik = dm_embed.dist(i, jk, embeded, null);//dist(y_i, y_k);
final double dist_ik_sqrd = dist_ik*dist_ik;
if (dist_ik < 1e-12)
continue;
y_i.copyTo(grad_k);
grad_k.mutableSubtract(y_k);
grad_k.mutableMultiply(2*gamma/(dist_ik*(dist_ik_sqrd+1)));
grad_i.mutableAdd(grad_k);
y_k.mutableSubtract(eta, grad_k);
}
y_i.mutableAdd( eta, grad_i);
y_j.mutableAdd(-eta, grad_j);
}
});
DataSet toRet = d.shallowClone();
final IdentityHashMap indexMap = new IdentityHashMap<>(N);
for(int i = 0; i < N; i++)
indexMap.put(d.getDataPoint(i), i);
toRet.applyTransform(new DataTransform()
{
@Override
public DataPoint transform(DataPoint dp)
{
int i = indexMap.get(dp);
return new DataPoint(embeded.get(i), dp.getCategoricalValues(), dp.getCategoricalData(), dp.getWeight());
}
@Override
public void fit(DataSet data)
{
}
@Override
public DataTransform clone()
{
return this;
}
});
return (Type) toRet;
}
}
Ads help maintain this website.