Changeset 16311 for branches/2845_EnhancedProgress/HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE/TSNEStatic.cs

Timestamp:

11/20/18 15:26:57 (5 years ago)

Author:

pfleck

Message:

#2845 Merged trunk changes into branch (15406-15681, 15683-16308)

Location:

branches/2845_EnhancedProgress

Files:

• . (modified) (1 prop)
• HeuristicLab.Algorithms.DataAnalysis (modified) (1 prop)
• HeuristicLab.Algorithms.DataAnalysis/3.4 (modified) (1 prop)
• HeuristicLab.Algorithms.DataAnalysis/3.4/TSNE/TSNEStatic.cs (modified) (28 diffs)

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

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  *
  * This file is part of HeuristicLab.
@@ -65 +65 @@
   [StorableClass]
   public class TSNEStatic<T> {
-
     [StorableClass]
     public sealed class TSNEState : DeepCloneable {
@@ -170 +169 @@
       [StorableConstructor]
       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) {
+
+      public TSNEState(IReadOnlyList<T> data, IDistance<T> distance, IRandom random, int newDimensions, double perplexity,
+        double theta, int stopLyingIter, int momSwitchIter, double momentum, double finalMomentum, double eta, bool randomInit) {
         this.distance = distance;
         this.random = random;
@@ -183 +184 @@
 
         // initialize
-        noDatapoints = data.Length;
+        noDatapoints = data.Count;
         if (noDatapoints - 1 < 3 * perplexity)
           throw new ArgumentException("Perplexity too large for the number of data points!");
@@ -193 +194 @@
         gains = new double[noDatapoints, newDimensions];
         for (var i = 0; i < noDatapoints; i++)
-          for (var j = 0; j < newDimensions; j++)
-            gains[i, j] = 1.0;
+        for (var j = 0; j < newDimensions; j++)
+          gains[i, j] = 1.0;
 
         p = null;
@@ -212 +213 @@
         var rand = new NormalDistributedRandom(random, 0, 1);
         for (var i = 0; i < noDatapoints; i++)
-          for (var j = 0; j < newDimensions; j++)
-            newData[i, j] = rand.NextDouble() * .0001;
+        for (var j = 0; j < newDimensions; j++)
+          newData[i, j] = rand.NextDouble() * .0001;
+
+        if (!(data[0] is IReadOnlyList<double>) || randomInit) return;
+        for (var i = 0; i < noDatapoints; i++)
+        for (var j = 0; j < newDimensions; j++) {
+          var row = (IReadOnlyList<double>) data[i];
+          newData[i, j] = row[j % row.Count];
+        }
       }
       #endregion
 
       public double EvaluateError() {
-        return exact ?
-          EvaluateErrorExact(p, newData, noDatapoints, newDimensions) :
-          EvaluateErrorApproximate(rowP, colP, valP, newData, theta);
+        return exact ? EvaluateErrorExact(p, newData, noDatapoints, newDimensions) : EvaluateErrorApproximate(rowP, colP, valP, newData, theta);
       }
 
       #region Helpers
-      private static void CalculateApproximateSimilarities(T[] data, IDistance<T> distance, double perplexity, out int[] rowP, out int[] colP, out double[] valP) {
+      private static void CalculateApproximateSimilarities(IReadOnlyList<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));
+        ComputeGaussianPerplexity(data, distance, out rowP, out colP, out valP, perplexity, (int) (3 * perplexity));
         // Symmetrize input similarities
         int[] sRowP, symColP;
@@ -235 +241 @@
         valP = sValP;
         var sumP = .0;
-        for (var i = 0; i < rowP[data.Length]; i++) sumP += valP[i];
-        for (var i = 0; i < rowP[data.Length]; i++) valP[i] /= sumP;
-      }
-
-      private static double[,] CalculateExactSimilarites(T[] data, IDistance<T> distance, double perplexity) {
+        for (var i = 0; i < rowP[data.Count]; i++) sumP += valP[i];
+        for (var i = 0; i < rowP[data.Count]; i++) valP[i] /= sumP;
+      }
+      private static double[,] CalculateExactSimilarites(IReadOnlyList<T> data, IDistance<T> distance, double perplexity) {
         // Compute similarities
-        var p = new double[data.Length, data.Length];
+        var p = new double[data.Count, data.Count];
         ComputeGaussianPerplexity(data, distance, p, perplexity);
         // Symmetrize input similarities
-        for (var n = 0; n < data.Length; n++) {
-          for (var m = n + 1; m < data.Length; m++) {
+        for (var n = 0; n < data.Count; n++) {
+          for (var m = n + 1; m < data.Count; m++) {
             p[n, m] += p[m, n];
             p[m, n] = p[n, m];
@@ -251 +256 @@
         }
         var sumP = .0;
-        for (var i = 0; i < data.Length; i++) for (var j = 0; j < data.Length; j++) sumP += p[i, j];
-        for (var i = 0; i < data.Length; i++) for (var j = 0; j < data.Length; j++) p[i, j] /= sumP;
+        for (var i = 0; i < data.Count; i++) {
+          for (var j = 0; j < data.Count; j++) {
+            sumP += p[i, j];
+          }
+        }
+        for (var i = 0; i < data.Count; i++) {
+          for (var j = 0; j < data.Count; j++) {
+            p[i, j] /= sumP;
+          }
+        }
         return p;
       }
-
       private static void ComputeGaussianPerplexity(IReadOnlyList<T> x, IDistance<T> distance, out int[] rowP, out int[] colP, out double[] valP, double perplexity, int k) {
         if (perplexity > k) throw new ArgumentException("Perplexity should be lower than k!");
@@ -290 +302 @@
 
           // Iterate until we found a good perplexity
-          var iter = 0; double sumP = 0;
+          var iter = 0;
+          double sumP = 0;
           while (!found && iter < 200) {
-
             // Compute Gaussian kernel row
             for (var m = 0; m < k; m++) curP[m] = Math.Exp(-beta * distances[m + 1]);
@@ -307 +319 @@
             if (hdiff < tol && -hdiff < tol) {
               found = true;
-            } else {
+            }
+            else {
               if (hdiff > 0) {
                 minBeta = beta;
@@ -314 +327 @@
                 else
                   beta = (beta + maxBeta) / 2.0;
-              } else {
+              }
+              else {
                 maxBeta = beta;
                 if (minBeta.IsAlmost(double.MinValue) || minBeta.IsAlmost(double.MaxValue))
@@ -335 +349 @@
         }
       }
-      private static void ComputeGaussianPerplexity(T[] x, IDistance<T> distance, double[,] p, double perplexity) {
+      private static void ComputeGaussianPerplexity(IReadOnlyList<T> x, IDistance<T> distance, double[,] p, double perplexity) {
         // Compute the distance matrix
         var dd = ComputeDistances(x, distance);
 
-        var n = x.Length;
+        var n = x.Count;
         // Compute the Gaussian kernel row by row
         for (var i = 0; i < n; i++) {
@@ -352 +366 @@
           // Iterate until we found a good perplexity
           var iter = 0;
-          while (!found && iter < 200) {      // 200 iterations as in tSNE implementation by van der Maarten
+          while (!found && iter < 200) { // 200 iterations as in tSNE implementation by van der Maarten
 
             // Compute Gaussian kernel row
@@ -369 +383 @@
             if (hdiff < tol && -hdiff < tol) {
               found = true;
-            } else {
+            }
+            else {
               if (hdiff > 0) {
                 minBeta = beta;
@@ -376 +391 @@
                 else
                   beta = (beta + maxBeta) / 2.0;
-              } else {
+              }
+              else {
                 maxBeta = beta;
                 if (minBeta.IsAlmost(double.MinValue) || minBeta.IsAlmost(double.MaxValue))
@@ -393 +409 @@
         }
       }
-
-      private static double[][] ComputeDistances(T[] x, IDistance<T> distance) {
-        var res = new double[x.Length][];
-        for (var r = 0; r < x.Length; r++) {
-          var rowV = new double[x.Length];
+      private static double[][] ComputeDistances(IReadOnlyList<T> x, IDistance<T> distance) {
+        var res = new double[x.Count][];
+        for (var r = 0; r < x.Count; r++) {
+          var rowV = new double[x.Count];
           // all distances must be symmetric 
           for (var c = 0; c < r; c++) {
@@ -403 +418 @@
           }
           rowV[r] = 0.0; // distance to self is zero for all distances
-          for (var c = r + 1; c < x.Length; c++) {
+          for (var c = r + 1; c < x.Count; c++) {
             rowV[c] = distance.Get(x[r], x[c]);
           }
@@ -411 +426 @@
         // return x.Select(m => x.Select(n => distance.Get(m, n)).ToArray()).ToArray();
       }
-
       private static double EvaluateErrorExact(double[,] p, double[,] y, int n, int d) {
         // Compute the squared Euclidean distance matrix
@@ -425 +439 @@
               q[n1, m] = 1 / (1 + dd[n1, m]);
               sumQ += q[n1, m];
-            } else q[n1, m] = double.Epsilon;
+            }
+            else q[n1, m] = double.Epsilon;
           }
         }
@@ -433 +448 @@
         var c = .0;
         for (var i = 0; i < n; i++)
-          for (var j = 0; j < n; j++) {
-            c += p[i, j] * Math.Log((p[i, j] + float.Epsilon) / (q[i, j] + float.Epsilon));
-          }
+        for (var j = 0; j < n; j++) {
+          c += p[i, j] * Math.Log((p[i, j] + float.Epsilon) / (q[i, j] + float.Epsilon));
+        }
         return c;
       }
-
       private static double EvaluateErrorApproximate(IReadOnlyList<int> rowP, IReadOnlyList<int> colP, IReadOnlyList<double> valP, double[,] y, double theta) {
         // Get estimate of normalization term
@@ -463 +477 @@
       }
       private static void SymmetrizeMatrix(IReadOnlyList<int> rowP, IReadOnlyList<int> colP, IReadOnlyList<double> valP, out int[] symRowP, out int[] symColP, out double[] symValP) {
-
         // Count number of elements and row counts of symmetric matrix
         var n = rowP.Count - 1;
@@ -469 +482 @@
         for (var j = 0; j < n; j++) {
           for (var i = rowP[j]; i < rowP[j + 1]; i++) {
-
             // Check whether element (col_P[i], n) is present
             var present = false;
@@ -497 +509 @@
         var offset = new int[n];
         for (var j = 0; j < n; j++) {
-          for (var i = rowP[j]; i < rowP[j + 1]; i++) {                                  // considering element(n, colP[i])
+          for (var i = rowP[j]; i < rowP[j + 1]; i++) { // considering element(n, colP[i])
 
             // Check whether element (col_P[i], n) is present
@@ -549 +561 @@
     public static double[,] Run(T[] data, IDistance<T> distance, IRandom random,
       int newDimensions = 2, double perplexity = 25, int iterations = 1000,
-      double theta = 0,
-      int stopLyingIter = 0, int momSwitchIter = 0, double momentum = .5,
+      double theta = 0, int stopLyingIter = 0, int momSwitchIter = 0, double momentum = .5,
       double finalMomentum = .8, double eta = 10.0
-      ) {
+    ) {
       var state = CreateState(data, distance, random, newDimensions, perplexity,
         theta, stopLyingIter, momSwitchIter, momentum, finalMomentum, eta);
@@ -565 +576 @@
       int newDimensions = 2, double perplexity = 25, double theta = 0,
       int stopLyingIter = 0, int momSwitchIter = 0, double momentum = .5,
-      double finalMomentum = .8, double eta = 10.0
-      ) {
-      return new TSNEState(data, distance, random, newDimensions, perplexity, theta, stopLyingIter, momSwitchIter, momentum, finalMomentum, eta);
+      double finalMomentum = .8, double eta = 10.0, bool randomInit = true
+    ) {
+      return new TSNEState(data, distance, random, newDimensions, perplexity, theta, stopLyingIter, momSwitchIter, momentum, finalMomentum, eta, randomInit);
     }
 
@@ -580 +591 @@
         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  // +0.2 nd *0.8 are used in two separate implementations of tSNE -> seems to be correct
+            ? 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;
         }
       }
-
 
       // Perform gradient update (with momentum and gains)
       for (var i = 0; i < state.noDatapoints; i++)
-        for (var j = 0; j < state.newDimensions; j++)
-          state.uY[i, j] = state.currentMomentum * state.uY[i, j] - state.eta * state.gains[i, j] * state.dY[i, j];
+      for (var j = 0; j < state.newDimensions; j++)
+        state.uY[i, j] = state.currentMomentum * state.uY[i, j] - state.eta * state.gains[i, j] * state.dY[i, j];
 
       for (var i = 0; i < state.noDatapoints; i++)
-        for (var j = 0; j < state.newDimensions; j++)
-          state.newData[i, j] = state.newData[i, j] + state.uY[i, j];
+      for (var j = 0; j < state.newDimensions; j++)
+        state.newData[i, j] = state.newData[i, j] + state.uY[i, j];
 
       // Make solution zero-mean
@@ -604 +613 @@
         if (state.exact)
           for (var i = 0; i < state.noDatapoints; i++)
-            for (var j = 0; j < state.noDatapoints; j++)
-              state.p[i, j] /= 12.0;
+          for (var j = 0; j < state.noDatapoints; j++)
+            state.p[i, j] /= 12.0;
         else
           for (var i = 0; i < state.rowP[state.noDatapoints]; i++)
@@ -634 +643 @@
       // Compute final t-SNE gradient
       for (var i = 0; i < n; i++)
-        for (var j = 0; j < d; j++) {
-          dC[i, j] = posF[i, j] - negF[i, j] / sumQ;
-        }
+      for (var j = 0; j < d; j++) {
+        dC[i, j] = posF[i, j] - negF[i, j] / sumQ;
+      }
     }