Changeset 13791 for branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common

Timestamp:

04/25/16 12:56:17 (8 years ago)

Author:

abeham

Message:

#2457: working on recommendation algorithms

Location:

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3

Files:

• HeuristicLab.OptimizationExpertSystem.Common-3.3.csproj (modified) (1 diff)
• Interfaces/IAlgorithmInstanceRecommender.cs (modified) (1 diff)
• Interfaces/IRecommendationModel.cs (modified) (1 diff)
• KnowledgeCenter.cs (modified) (8 diffs)
• Recommenders/FixedRankModel.cs (modified) (2 diffs)
• Recommenders/KNearestNeighborModel.cs (modified) (3 diffs)
• Recommenders/KNearestNeighborRecommender.cs (modified) (3 diffs)
• Recommenders/OverallBestRecommender.cs (modified) (4 diffs)

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/HeuristicLab.OptimizationExpertSystem.Common-3.3.csproj

@@ -161 +161 @@
     <Compile Include="Recommenders\KNearestNeighborModel.cs" />
     <Compile Include="Recommenders\OverallBestRecommender.cs" />
-    <Compile Include="Recommenders\DistanceWeightedRecommender.cs" />
     <Compile Include="Interfaces\IAlgorithmInstanceRecommender.cs" />
     <Compile Include="Recommenders\KNearestNeighborRecommender.cs" />

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Interfaces/IAlgorithmInstanceRecommender.cs

@@ -21 +21 @@
 
 using HeuristicLab.Core;
+using HeuristicLab.Optimization;
 
 namespace HeuristicLab.OptimizationExpertSystem.Common {
   public interface IAlgorithmInstanceRecommender : IParameterizedItem {
-    IRecommendationModel TrainModel(KnowledgeCenter kc, string[] characteristics);
+    IRecommendationModel TrainModel(IRun[] problemInstances, KnowledgeCenter kc, string[] characteristics);
   }
 }

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Interfaces/IRecommendationModel.cs

@@ -27 +27 @@
 namespace HeuristicLab.OptimizationExpertSystem.Common {
   public interface IRecommendationModel : IContent {
-    IEnumerable<Tuple<IAlgorithm, double>> GetRanking(KnowledgeCenter kc);
+    IEnumerable<Tuple<IAlgorithm, double>> GetRanking(IRun problemInstance);
   }
 }

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/KnowledgeCenter.cs

@@ -212 +212 @@
       #endregion
       #region PCA
+      double[,] v = null;
       var ds = new double[instances.Count, characteristics.Length];
-      foreach (var instance in instances) {
-        var arr = instance.Value;
-        for (var feature = 0; feature < arr.Length; feature++)
-          ds[key2Idx.GetByFirst(instance.Key), feature] = arr[feature];
-      }
-
-      int info;
-      double[] s2;
-      double[,] v;
-      alglib.pcabuildbasis(ds, ds.GetLength(0), ds.GetLength(1), out info, out s2, out v);
+      if (characteristics.Length > 1) {
+        foreach (var instance in instances) {
+          var arr = instance.Value;
+          for (var feature = 0; feature < arr.Length; feature++)
+            ds[key2Idx.GetByFirst(instance.Key), feature] = arr[feature];
+        }
+
+        int info;
+        double[] s2;
+        alglib.pcabuildbasis(ds, ds.GetLength(0), ds.GetLength(1), out info, out s2, out v);
+      }
       #endregion
       #region SOM
@@ -231 +233 @@
           features[feature, key2Idx.GetByFirst(instance.Key)] = arr[feature];
       }
-      var somCoords = SOM.Map(features, new MersenneTwister(42), somSize: 20, learningRadius: 20, iterations: 200, jittering: true);
+      var somCoords = SOM.Map(features, new MersenneTwister(42), somSize: 10, learningRadius: 20, iterations: 200, jittering: true);
       #endregion
 
@@ -237 +239 @@
       try {
         foreach (var instance in ProblemInstances) {
-          double x = 0, y = 0;
-          for (var feature = 0; feature < ds.GetLength(1); feature++) {
-            x += ds[key2Idx.GetByFirst(instance), feature] * v[feature, 0];
-            y += ds[key2Idx.GetByFirst(instance), feature] * v[feature, 1];
-          }
-
           IItem item;
-          if (instance.Results.TryGetValue("Projection.PCA.X", out item)) {
-            ((DoubleValue)item).Value = x;
-          } else instance.Results.Add("Projection.PCA.X", new DoubleValue(x));
-          if (instance.Results.TryGetValue("Projection.PCA.Y", out item)) {
-            ((DoubleValue)item).Value = y;
-          } else instance.Results.Add("Projection.PCA.Y", new DoubleValue(y));
+          if (v != null) {
+            double x = 0, y = 0;
+            for (var feature = 0; feature < ds.GetLength(1); feature++) {
+              x += ds[key2Idx.GetByFirst(instance), feature] * v[feature, 0];
+              y += ds[key2Idx.GetByFirst(instance), feature] * v[feature, 1];
+            }
+
+            if (instance.Results.TryGetValue("Projection.PCA.X", out item)) {
+              ((DoubleValue)item).Value = x;
+            } else instance.Results.Add("Projection.PCA.X", new DoubleValue(x));
+            if (instance.Results.TryGetValue("Projection.PCA.Y", out item)) {
+              ((DoubleValue)item).Value = y;
+            } else instance.Results.Add("Projection.PCA.Y", new DoubleValue(y));
+          } else {
+            instance.Results.Remove("Projection.PCA.X");
+            instance.Results.Remove("Projection.PCA.Y");
+          }
 
           if (instance.Results.TryGetValue("Projection.MDS.X", out item)) {
@@ -266 +273 @@
         }
       } finally { ProblemInstances.UpdateOfRunsInProgress = false; }
-    }
-
-    public Dictionary<IRun, double[]> GetProblemCharacteristics(string[] characteristics) {
-      var instances = new Dictionary<IRun, double[]>();
-      var values = new List<double>[characteristics.Length];
-      foreach (var run in ProblemInstances) {
-        var f = 0;
-        instances[run] = new double[characteristics.Length];
-        foreach (var c in characteristics) {
-          if (values[f] == null) values[f] = new List<double>(ProblemInstances.Count);
-          IItem item;
-          if (run.Results.TryGetValue(c, out item)) {
-            var val = (double)((dynamic)item).Value;
-            if (!double.IsNaN(val)) values[f].Add(val);
-            instances[run][f] = val;
-          } else instances[run][f] = double.NaN;
-          f++;
-        }
-      }
-      var median = values.Select(x => x.Count == 0 ? 0.0 : x.Median()).ToList();
-
-      var allValues = instances.Values.Select(x => x.Select((f, i) => new {Idx = i, Val = double.IsNaN(f) ? median[i] : f}).ToList())
-        .SelectMany(x => x)
-        .GroupBy(x => x.Idx, x => x.Val)
-        .OrderBy(x => x.Key).ToList();
-      var avg = allValues.Select(x => x.Average()).ToList();
-      var stdev = allValues.Select(x => x.StandardDeviation()).ToList();
-
-      // normalize characteristic values by transforming them to their z-score
-      foreach (var key in instances.Keys.ToList()) {
-        var arr = instances[key];
-        for (var i = 0; i < arr.Length; i++) {
-          if (double.IsNaN(arr[i])) arr[i] = median[i];
-          if (stdev[i] > 0) arr[i] = (arr[i] - avg[i]) / stdev[i];
-        }
-      }
-      return instances;
     }
 
@@ -579 +549 @@
     }
 
+    public static double[][] GetFeatures(IRun[] problemInstances, string[] characteristics, double[] medianValues = null) {
+      var instances = new double[problemInstances.Length][];
+      for (var p = 0; p < problemInstances.Length; p++) {
+        instances[p] = new double[characteristics.Length];
+        for (var f = 0; f < characteristics.Length; f++) {
+          IItem item;
+          if (problemInstances[p].Results.TryGetValue(characteristics[f], out item)) {
+            double val = 0;
+            var dItem = item as DoubleValue;
+            if (dItem != null) {
+              val = dItem.Value;
+            } else {
+              var iItem = item as IntValue;
+              if (iItem != null) val = iItem.Value;
+              else val = double.NaN;
+            }
+            if (double.IsNaN(val) && medianValues != null)
+              instances[p][f] = medianValues[f];
+            else instances[p][f] = val;
+          } else instances[p][f] = medianValues != null ? medianValues[f] : double.NaN;
+        }
+      }
+      return instances;
+    }
+
+    public static double[] GetMedianValues(IRun[] problemInstances, string[] characteristics) {
+      var values = new List<double>[characteristics.Length];
+      foreach (var problemInstance in problemInstances) {
+        for (var f = 0; f < characteristics.Length; f++) {
+          if (values[f] == null) values[f] = new List<double>(problemInstances.Length);
+          IItem item;
+          if (problemInstance.Results.TryGetValue(characteristics[f], out item)) {
+            var dItem = item as DoubleValue;
+            if (dItem != null) values[f].Add(dItem.Value);
+            else {
+              var iItem = item as IntValue;
+              if (iItem != null) values[f].Add(iItem.Value);
+            }
+          }
+        }
+      }
+      return values.Select(x => x.Count == 0 ? 0.0 : x.Median()).ToArray();
+    }
+
+    public Dictionary<IRun, double[]> GetProblemCharacteristics(string[] characteristics) {
+      var map = ProblemInstances.Select((v, i) => new { Index = i, ProblemInstance = v }).ToDictionary(x => x.Index, x => x.ProblemInstance);
+      var instances = GetFeatures(ProblemInstances.ToArray(), characteristics);
+      var median = GetMedianValues(ProblemInstances.ToArray(), characteristics);
+
+      var allValues = instances.Select(x => x.Select((f, i) => new { Idx = i, Val = double.IsNaN(f) ? median[i] : f }).ToList())
+        .SelectMany(x => x)
+        .GroupBy(x => x.Idx, x => x.Val)
+        .OrderBy(x => x.Key).ToList();
+      var avg = allValues.Select(x => x.Average()).ToList();
+      var stdev = allValues.Select(x => x.StandardDeviation()).ToList();
+
+      // normalize characteristic values by transforming them to their z-score
+      foreach (var features in instances) {
+        for (var i = 0; i < features.Length; i++) {
+          if (double.IsNaN(features[i])) features[i] = median[i];
+          if (stdev[i] > 0) features[i] = (features[i] - avg[i]) / stdev[i];
+        }
+      }
+      return instances.Select((v, i) => new { ProblemInstance = map[i], Features = v }).ToDictionary(x => x.ProblemInstance, x => x.Features);
+    }
+
     public Dictionary<IAlgorithm, double> GetAlgorithmPerformance(IRun problemInstance) {
       if (!problemInstance.Parameters.ContainsKey("BestKnownQuality")) return new Dictionary<IAlgorithm, double>();
@@ -586 +622 @@
                           .ToDictionary(x => x.Key, x => ExpectedRuntimeHelper.CalculateErt(x.ToList(), "QualityPerEvaluations", target, Maximization).ExpectedRuntime);
     }
+
+    public Dictionary<IAlgorithm, List<IRun>> GetAlgorithmRuns(IRun problemInstance) {
+      return knowledgeBase.Where(x => ((StringValue)x.Parameters["Problem Name"]).Value == ((StringValue)problemInstance.Parameters["Problem Name"]).Value)
+                          .GroupBy(x => algorithmId2AlgorithmInstanceMapping.GetByFirst(algorithmId2RunMapping.GetBySecond(x).Single()))
+                          .ToDictionary(x => x.Key, x => x.ToList());
+    } 
 
     public Dictionary<IAlgorithm, List<IRun>> GetKnowledgeBaseByAlgorithm() {
@@ -708 +750 @@
     }
 
-    private double GetTarget(double bestKnownQuality, bool maximization) {
+    public double GetTarget(double bestKnownQuality, bool maximization) {
       return bestKnownQuality * (maximization ? (1 - MinimumTarget.Value) : (1 + MinimumTarget.Value));
     }
@@ -817 +859 @@
 
     public IEnumerable<Tuple<IAlgorithm, double>> GetAlgorithmInstanceRanking() {
-      return RecommendationModel.GetRanking(this);
+      return RecommendationModel.GetRanking(ProblemInstances.Single(IsCurrentInstance));
     }
   }

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/FixedRankModel.cs

@@ -26 +26 @@
 namespace HeuristicLab.OptimizationExpertSystem.Common {
   public class FixedRankModel : IRecommendationModel {
-    private List<Tuple<IAlgorithm, double>> ranking;
+    private readonly List<Tuple<IAlgorithm, double>> ranking;
 
     public FixedRankModel(IEnumerable<Tuple<IAlgorithm, double>> ranking) {
@@ -33 +33 @@
     }
  
-    public IEnumerable<Tuple<IAlgorithm, double>> GetRanking(KnowledgeCenter kc) { 
-      if (kc.Problem.ProblemId == -1) return new Tuple<IAlgorithm, double>[0];
+    public IEnumerable<Tuple<IAlgorithm, double>> GetRanking(IRun problemInstance) {
       return ranking;
     }

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/KNearestNeighborModel.cs

@@ -20 +20 @@
 #endregion
 
-using HeuristicLab.Common;
+using HeuristicLab.Collections;
 using HeuristicLab.Optimization;
 using System;
@@ -30 +30 @@
     private readonly int K;
     private readonly string[] characteristics;
+    private readonly Dictionary<IRun, Dictionary<IAlgorithm, double>> performance;
+    private readonly BidirectionalDictionary<int, IRun> problemInstanceMap; 
+    private readonly double[] medianValues;
 
-    public KNearestNeighborModel(int k, string[] characteristics) {
+    public KNearestNeighborModel(int k, Dictionary<IRun, Dictionary<IAlgorithm, double>> perfData, string[] characteristics) {
       this.K = k;
+      this.performance = perfData;
       this.characteristics = characteristics;
+      problemInstanceMap = new BidirectionalDictionary<int, IRun>();
+      var i = 0;
+      foreach (var pi in perfData.Keys) {
+        problemInstanceMap.Add(i++, pi);
+      }
+      this.medianValues = KnowledgeCenter.GetMedianValues(perfData.Keys.OrderBy(problemInstanceMap.GetBySecond).ToArray(), characteristics);
     }
 
-    public IEnumerable<Tuple<IAlgorithm, double>> GetRanking(KnowledgeCenter kc) {
-      var distances = kc.GetProblemDistances(characteristics);
+    public IEnumerable<Tuple<IAlgorithm, double>> GetRanking(IRun problemInstance) {
+      var features = KnowledgeCenter.GetFeatures(performance.Keys.OrderBy(problemInstanceMap.GetBySecond).ToArray(), characteristics, medianValues);
+      var feature = KnowledgeCenter.GetFeatures(new [] { problemInstance }, characteristics, medianValues)[0];
+      var nearestK = features.Select((f, i) => new { ProblemInstanceIndex = i, Feature = f })
+                             .OrderBy(x => x.Feature.Select((f, i) => (f - feature[i]) * (f - feature[i])).Sum())
+                             .Take(K);
+      
       var performances = new Dictionary<IAlgorithm, List<double>>();
-      for (var k = 0; k < K; k++) {
-        if (distances.Count == 0) break;
-        var min = distances.MinItems(x => x.Value).First();
-        // lookup algorithm performances in min
-        var perfs = kc.GetAlgorithmPerformance(min.Key);
-        if (perfs.Count == 0) {
-          k--;
-          continue;
-        }
+      foreach (var next in nearestK) {
+        var perfs = performance[problemInstanceMap.GetByFirst(next.ProblemInstanceIndex)];
+        if (perfs.Count == 0) continue;
+        
         foreach (var p in perfs) {
           var ert = p.Value;
@@ -56 +66 @@
           } else erts.Add(ert);
         }
-        distances.Remove(min.Key);
       }
 

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/KNearestNeighborRecommender.cs

@@ -23 +23 @@
 using HeuristicLab.Core;
 using HeuristicLab.Data;
+using HeuristicLab.Optimization;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using System.Linq;
 
 namespace HeuristicLab.OptimizationExpertSystem.Common {
@@ -37 +39 @@
     [StorableConstructor]
     private KNearestNeighborRecommender(bool deserializing) : base(deserializing) { }
-    private KNearestNeighborRecommender(KNearestNeighborRecommender original, Cloner cloner)
-      : base(original, cloner) { }
+    private KNearestNeighborRecommender(KNearestNeighborRecommender original, Cloner cloner) : base(original, cloner) { }
     public KNearestNeighborRecommender() {
-      Parameters.Add(new FixedValueParameter<IntValue>("K", "The number of nearest neighbors to consider.", new IntValue(5)));
+      Parameters.Add(new FixedValueParameter<IntValue>("K", "The number of nearest neighbors to consider.", new IntValue(3)));
     }
 
@@ -47 +48 @@
     }
 
-    public IRecommendationModel TrainModel(KnowledgeCenter kc, string[] characteristics) {
-      return new KNearestNeighborModel(KParameter.Value.Value, characteristics);
+    public IRecommendationModel TrainModel(IRun[] problemInstances, KnowledgeCenter kc, string[] characteristics) {
+      var perfData = problemInstances.Select(pi => new { ProblemInstance = pi, Performance = kc.GetAlgorithmPerformance(pi) })
+                                     .ToDictionary(x => x.ProblemInstance, x => x.Performance);
+      return new KNearestNeighborModel(KParameter.Value.Value, perfData, characteristics);
     }
   }

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/OverallBestRecommender.cs

@@ -25 +25 @@
 using HeuristicLab.Data;
 using HeuristicLab.Optimization;
-using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using System;
@@ -39 +38 @@
       get { return (IFixedValueParameter<DoubleValue>)Parameters["NeighborhoodFactor"]; }
     }
-
-    public double NeighborhoodFactor {
-      get { return NeighborhoodFactorParameter.Value.Value; }
-      set { NeighborhoodFactorParameter.Value.Value = value; }
-    }
     
     [StorableConstructor]
     private OverallBestRecommender(bool deserializing) : base(deserializing) { }
-    private OverallBestRecommender(OverallBestRecommender original, Cloner cloner)
-      : base(original, cloner) { }
-    public OverallBestRecommender() {
-      Parameters.Add(new FixedValueParameter<DoubleValue>("NeighborhoodFactor", "Penalize neighbors that are far away.", new DoubleValue(5)));
-    }
+    private OverallBestRecommender(OverallBestRecommender original, Cloner cloner) : base(original, cloner) { }
+    public OverallBestRecommender() { }
 
     public override IDeepCloneable Clone(Cloner cloner) {
@@ -57 +48 @@
     }
 
-    public IRecommendationModel TrainModel(KnowledgeCenter kc, string[] characteristics) {
+    public IRecommendationModel TrainModel(IRun[] problemInstances, KnowledgeCenter kc, string[] characteristics) {
       var instances = new List<Tuple<IAlgorithm, double>>();
       foreach (var relevantRuns in kc.GetKnowledgeBaseByAlgorithm()) {
         var algorithm = relevantRuns.Key;
         var pis = relevantRuns.Value.Select(x => ((StringValue)x.Parameters["Problem Name"]).Value).Distinct()
-                              .Select(x => Tuple.Create(x, kc.ProblemInstances.SingleOrDefault(y => ((StringValue)y.Parameters["Problem Name"]).Value == x)))
+                              .Select(x => Tuple.Create(x, problemInstances.SingleOrDefault(y => ((StringValue)y.Parameters["Problem Name"]).Value == x)))
                               .Where(x => x.Item2 != null)
                               .Select(x => Tuple.Create(x.Item1, ((DoubleValue)x.Item2.Parameters["BestKnownQuality"]).Value))
@@ -70 +61 @@
         foreach (var problemRuns in relevantRuns.Value.GroupBy(x => ((StringValue)x.Parameters["Problem Name"]).Value)) {
           var bkq = pis[problemRuns.Key];
-          var ert = ExpectedRuntimeHelper.CalculateErt(problemRuns.ToList(), "QualityPerEvaluations", (kc.Maximization ? (1 - kc.MinimumTarget.Value) : (1 + kc.MinimumTarget.Value)) * bkq, kc.Maximization).ExpectedRuntime;
+          var ert = ExpectedRuntimeHelper.CalculateErt(problemRuns.ToList(), "QualityPerEvaluations", kc.GetTarget(bkq, kc.Maximization), kc.Maximization).ExpectedRuntime;
           if (double.IsNaN(ert)) ert = int.MaxValue;
           avgERT += ert;