Changeset 14837

Timestamp:

04/10/17 15:50:16 (8 years ago)

Author:

gkronber

Message:

#2700 made some changes while reviewing (comparsion with bh_tsne implementation by van der Maarten)

Location:

branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE

Files:

• TSNEAlgorithm.cs (modified) (3 diffs)
• TSNEStatic.cs (modified) (12 diffs)

branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE/TSNEAlgorithm.cs

@@ -200 +200 @@
       Parameters.Add(new ValueParameter<IDistance<double[]>>(DistanceParameterName, "The distance function used to differentiate similar from non-similar points", new EuclideanDistance()));
       Parameters.Add(new FixedValueParameter<DoubleValue>(PerplexityParameterName, "Perplexity-parameter of tSNE. Comparable to k in a k-nearest neighbour algorithm. Recommended value is floor(number of points /3) or lower", new DoubleValue(25)));
-      Parameters.Add(new FixedValueParameter<DoubleValue>(ThetaParameterName, "Value describing how much appoximated gradients my differ from exact gradients. Set to 0 for exact calculation and in [0,1] otherwise. CAUTION: exact calculation of forces requires building a non-sparse N*N matrix where N is the number of data points. This may exceed memory limitations.", new DoubleValue(0)));
+      Parameters.Add(new FixedValueParameter<DoubleValue>(ThetaParameterName, "Value describing how much appoximated " +
+                                                                              "gradients my differ from exact gradients. Set to 0 for exact calculation and in [0,1] otherwise. " +
+                                                                              "Appropriate values for theta are between 0.1 and 0.7 (default = 0.5). CAUTION: exact calculation of " +
+                                                                              "forces requires building a non-sparse N*N matrix where N is the number of data points. This may " +
+                                                                              "exceed memory limitations. The function is designed to run on large (N > 5000) data sets. It may give" +
+                                                                              " poor performance on very small data sets(it is better to use a standard t - SNE implementation on such data).", new DoubleValue(0)));
       Parameters.Add(new FixedValueParameter<IntValue>(NewDimensionsParameterName, "Dimensionality of projected space (usually 2 for easy visual analysis)", new IntValue(2)));
       Parameters.Add(new FixedValueParameter<IntValue>(MaxIterationsParameterName, "Maximum number of iterations for gradient descent.", new IntValue(1000)));
@@ -207 +212 @@
       Parameters.Add(new FixedValueParameter<DoubleValue>(InitialMomentumParameterName, "The initial momentum in the gradient descent.", new DoubleValue(0.5)));
       Parameters.Add(new FixedValueParameter<DoubleValue>(FinalMomentumParameterName, "The final momentum.", new DoubleValue(0.8)));
-      Parameters.Add(new FixedValueParameter<DoubleValue>(EtaParameterName, "Gradient descent learning rate.", new DoubleValue(200)));
+      Parameters.Add(new FixedValueParameter<DoubleValue>(EtaParameterName, "Gradient descent learning rate.", new DoubleValue(10)));
       Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyParameterName, "If the seed should be random.", new BoolValue(true)));
       Parameters.Add(new FixedValueParameter<IntValue>(SeedParameterName, "The seed used if it should not be random.", new IntValue(0)));
@@ -217 +222 @@
       FinalMomentumParameter.Hidden = true;
       StopLyingIterationParameter.Hidden = true;
-      EtaParameter.Hidden = true;
+      EtaParameter.Hidden = false;
     }
     #endregion

branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE/TSNEStatic.cs

@@ -168 +168 @@
 
       [StorableConstructor]
-      public TSNEState(bool deserializing)  { }
+      public TSNEState(bool deserializing) { }
       public TSNEState(T[] data, IDistance<T> distance, IRandom random, int newDimensions, double perplexity, double theta, int stopLyingIter, int momSwitchIter, double momentum, double finalMomentum, double eta) {
         this.distance = distance;
@@ -205 +205 @@
         else CalculateApproximateSimilarities(data, distance, perplexity, out rowP, out colP, out valP);
 
-        // Lie about the P-values
+        // Lie about the P-values (factor is 4 in the MATLAB implementation)
         if(exact) for(var i = 0; i < noDatapoints; i++) for(var j = 0; j < noDatapoints; j++) p[i, j] *= 12.0;
         else for(var i = 0; i < rowP[noDatapoints]; i++) valP[i] *= 12.0;
@@ -213 +213 @@
         for(var i = 0; i < noDatapoints; i++)
           for(var j = 0; j < newDimensions; j++)
-            newData[i, j] = rand.NextDouble() * .0001;  // TODO const  ?
+            newData[i, j] = rand.NextDouble() * .0001;
       }
 
@@ -224 +224 @@
       private static void CalculateApproximateSimilarities(T[] data, IDistance<T> distance, double perplexity, out int[] rowP, out int[] colP, out double[] valP) {
         // Compute asymmetric pairwise input similarities
-        ComputeGaussianPerplexity(data, distance, out rowP, out colP, out valP, perplexity, (int)(3 * perplexity));        // TODO: why 3?
+        ComputeGaussianPerplexity(data, distance, out rowP, out colP, out valP, perplexity, (int)(3 * perplexity));
         // Symmetrize input similarities
         int[] sRowP, symColP;
@@ -270 +270 @@
 
         // Build ball tree on data set
-        var tree = new VantagePointTree<IndexedItem<T>>(new IndexedItemDistance<T>(distance), objX);           // do we really want to re-create the tree on each call?
+        var tree = new VantagePointTree<IndexedItem<T>>(new IndexedItemDistance<T>(distance), objX);
 
         // Loop over all points to find nearest neighbors
@@ -343 +343 @@
           var found = false;
           var beta = 1.0;
-          var minBeta = -double.MaxValue;
+          var minBeta = double.MinValue;
           var maxBeta = double.MaxValue;
           const double tol = 1e-5;
@@ -350 +350 @@
           // Iterate until we found a good perplexity
           var iter = 0;
-          while(!found && iter < 200) {       // TODO constant
+          while(!found && iter < 200) {      // 200 iterations as in tSNE implementation by van der Maarten
 
             // Compute Gaussian kernel row
@@ -414 +414 @@
         var dd = new double[n, n];
         var q = new double[n, n];
-        ComputeSquaredEuclideanDistance(y, n, d, dd); // TODO: we use Euclidian distance regardless of the actual distance function
+        ComputeSquaredEuclideanDistance(y, n, d, dd);
 
         // Compute Q-matrix and normalization sum
@@ -455 +455 @@
             for(var j = 0; j < d; j++) buff[j] = y[k, j];
             for(var j = 0; j < d; j++) buff[j] -= y[colP[i], j];
-            for(var j = 0; j < d; j++) q += buff[j] * buff[j];     // TODO: squared error is used here!
-            q = 1.0 / (1.0 + q) / sumQ;
+            for(var j = 0; j < d; j++) q += buff[j] * buff[j];
+            q = (1.0 / (1.0 + q)) / sumQ;
             c += valP[i] * Math.Log((valP[i] + float.Epsilon) / (q + float.Epsilon));
           }
@@ -580 +580 @@
         for(var j = 0; j < state.newDimensions; j++) {
           state.gains[i, j] = Math.Sign(state.dY[i, j]) != Math.Sign(state.uY[i, j])
-            ? state.gains[i, j] + .2
-            : state.gains[i, j] * .8; // 20% up or 20% down // TODO: +0.2?!
-
-          if(state.gains[i, j] < .01) state.gains[i, j] = .01; // TODO why limit the gains?
+            ? state.gains[i, j] + .2  // +0.2 nd *0.8 are used in two separate implementations of tSNE -> seems to be correct
+            : state.gains[i, j] * .8;
+
+          if(state.gains[i, j] < .01) state.gains[i, j] = .01;
         }
       }
@@ -605 +605 @@
           for(var i = 0; i < state.noDatapoints; i++)
             for(var j = 0; j < state.noDatapoints; j++)
-              state.p[i, j] /= 12.0;                                   //XXX why 12?
+              state.p[i, j] /= 12.0;
         else
           for(var i = 0; i < state.rowP[state.noDatapoints]; i++)
-            state.valP[i] /= 12.0;                       // XXX are we not scaling all values? 
+            state.valP[i] /= 12.0;
       }
 
@@ -645 +645 @@
       // Compute the squared Euclidean distance matrix
       var dd = new double[n, n];
-      ComputeSquaredEuclideanDistance(y, n, d, dd); // TODO: we use Euclidian distance regardless which distance function is actually set!
+      ComputeSquaredEuclideanDistance(y, n, d, dd);
 
       // Compute Q-matrix and normalization sum