Changeset 12979 for branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification

Timestamp:

10/02/15 01:08:30 (9 years ago)

Author:

bburlacu

Message:

#1772:

• added parameters to the SchemaCreator for calculating things in parallel
• added parallel code to the SchemaEvaluator
• implemented quality calculation and saving of estimated values in the scope in the UpdateEstimatedValuesOperator
• small refactoring of QueryMatch (added some useful methods and made NodeInfo internal)
• updated query match unit test

Location:

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification

Files:

• SchemaCreator.cs (modified) (7 diffs)
• SchemaEvaluator.cs (modified) (9 diffs)
• UpdateEstimatedValuesOperator.cs (modified) (3 diffs)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaCreator.cs

@@ -42 +42 @@
     private const string ReplacementRatioParameterName = "ReplacementRatio";
     private const string RandomReplacementParameterName = "RandomReplacement";
+    private const string ExecuteInParallelParameterName = "ExecuteInParallel";
+    private const string MaxDegreeOfParalellismParameterName = "MaxDegreeOfParallelism";
 
     #region parameters
@@ -48 +50 @@
     }
 
+    public IFixedValueParameter<BoolValue> ExecuteInParallelParameter {
+      get { return (IFixedValueParameter<BoolValue>)Parameters[ExecuteInParallelParameterName]; }
+    }
+
+    public IFixedValueParameter<IntValue> MaxDegreeOfParallelismParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[MaxDegreeOfParalellismParameterName]; }
+    }
+
     public IFixedValueParameter<PercentValue> MinimumSchemaFrequencyParameter {
       get { return (IFixedValueParameter<PercentValue>)Parameters[MinimumSchemaFrequencyParameterName]; }
@@ -62 +72 @@
 
     #region parameter properties
-    public int MinimumSchemaLength {
-      get { return MinimumSchemaLengthParameter.Value.Value; }
-    }
+    public int MinimumSchemaLength { get { return MinimumSchemaLengthParameter.Value.Value; } }
+    public int MaxDegreeOfParallelism { get { return MaxDegreeOfParallelismParameter.Value.Value; } }
+    public bool ExecuteInParallel { get { return ExecuteInParallelParameter.Value.Value; } }
     #endregion
 
@@ -72 +82 @@
     private DataTableValuesCollector valuesCollector;
     private ResultsCollector resultsCollector;
+    private UpdateEstimatedValuesOperator updateEstimatedValuesOperator;
 
     private void ParameterizeOperators() {
@@ -89 +100 @@
       resultsCollector = new ResultsCollector();
       resultsCollector.CollectedValues.Add(new LookupParameter<DataTable>("Diversification"));
+
+      updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
     }
 
     public SchemaCreator() {
       Parameters.Add(new FixedValueParameter<IntValue>(MinimumSchemaLengthParameterName, new IntValue(10)));
-      Parameters.Add(new FixedValueParameter<PercentValue>(MinimumSchemaFrequencyParameterName, new PercentValue(0.05)));
-      Parameters.Add(new FixedValueParameter<PercentValue>(MinimumPhenotypicSimilarityParameterName, new PercentValue(0.8)));
-      Parameters.Add(new FixedValueParameter<PercentValue>(ReplacementRatioParameterName, new PercentValue(0.2)));
+      Parameters.Add(new FixedValueParameter<PercentValue>(MinimumSchemaFrequencyParameterName, new PercentValue(0.01)));
+      Parameters.Add(new FixedValueParameter<PercentValue>(MinimumPhenotypicSimilarityParameterName, new PercentValue(0.9)));
+      Parameters.Add(new FixedValueParameter<PercentValue>(ReplacementRatioParameterName, new PercentValue(0.9)));
       Parameters.Add(new FixedValueParameter<BoolValue>(RandomReplacementParameterName, new BoolValue(false)));
+      Parameters.Add(new FixedValueParameter<BoolValue>(ExecuteInParallelParameterName, new BoolValue(false)));
+      Parameters.Add(new FixedValueParameter<IntValue>(MaxDegreeOfParalellismParameterName, new IntValue(-1)));
+
+      ExecuteInParallelParameter.Hidden = true;
+      MaxDegreeOfParallelismParameter.Hidden = true;
 
       ParameterizeOperators();
@@ -116 +134 @@
         return base.Apply();
       // for now, only consider crossover offspring
+
+      var scopes = new ScopeList(this.ExecutionContext.Scope.SubScopes);
       var vertices = GenealogyGraph.GetByRank(gen).Where(x => x.InDegree == 2).Cast<IGenealogyGraphNode<ISymbolicExpressionTree>>();
       var groups = vertices.GroupBy(x => x.Parents.First()).OrderByDescending(g => g.Count()).ToList();
       var anySubtreeSymbol = new AnySubtreeSymbol();
 
-      var scopes = new ScopeList(this.ExecutionContext.Scope.SubScopes);
-
       if (schemaEvaluator == null || schemaCleanupOperator == null || changedTreesReducer == null || valuesCollector == null || resultsCollector == null)
         ParameterizeOperators();
@@ -129 +147 @@
       var collectResults = ExecutionContext.CreateChildOperation(resultsCollector);
 
-      var oc = new OperationCollection();
+      var updateEstimatedValues = new OperationCollection { Parallel = true };
+      foreach (var s in scopes) {
+        if (!s.Variables.ContainsKey("EstimatedValues"))
+          s.Variables.Add(new Core.Variable("EstimatedValues"));
+        updateEstimatedValues.Add(ExecutionContext.CreateChildOperation(updateEstimatedValuesOperator, s));
+      }
+      var oc = new OperationCollection { updateEstimatedValues };
 
       #region create schemas and add subscopes representing the individuals

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaEvaluator.cs

@@ -22 +22 @@
 using System;
 using System.Linq;
+using System.Threading.Tasks;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -50 +51 @@
     private const string RandomReplacementParameterName = "RandomReplacement";
     private const string ChangedTreesParameterName = "ChangedTrees";
+    private const string ExecuteInParallelParameterName = "ExecuteInParallel";
+    private const string MaxDegreeOfParalellismParameterName = "MaxDegreeOfParallelism";
     #endregion
 
     #region parameters
+    public ILookupParameter<BoolValue> ExecuteInParallelParameter {
+      get { return (ILookupParameter<BoolValue>)Parameters[ExecuteInParallelParameterName]; }
+    }
+    public ILookupParameter<IntValue> MaxDegreeOfParallelismParameter {
+      get { return (ILookupParameter<IntValue>)Parameters[MaxDegreeOfParalellismParameterName]; }
+    }
     public ILookupParameter<ISymbolicDataAnalysisSingleObjectiveEvaluator<IRegressionProblemData>> EvaluatorParameter {
       get { return (ILookupParameter<ISymbolicDataAnalysisSingleObjectiveEvaluator<IRegressionProblemData>>)Parameters[EvaluatorParameterName]; }
@@ -98 +107 @@
 
     #region parameter properties
-    public PercentValue MinimumSchemaFrequency {
-      get { return MinimumSchemaFrequencyParameter.ActualValue; }
-    }
-
-    public PercentValue ReplacementRatio {
-      get { return ReplacementRatioParameter.ActualValue; }
-    }
-
-    public PercentValue MinimumPhenotypicSimilarity {
-      get { return MinimumPhenotypicSimilarityParameter.ActualValue; }
-    }
-
-    public BoolValue RandomReplacement {
-      get { return RandomReplacementParameter.ActualValue; }
-    }
+    public PercentValue MinimumSchemaFrequency { get { return MinimumSchemaFrequencyParameter.ActualValue; } }
+    public PercentValue ReplacementRatio { get { return ReplacementRatioParameter.ActualValue; } }
+    public PercentValue MinimumPhenotypicSimilarity { get { return MinimumPhenotypicSimilarityParameter.ActualValue; } }
+    public BoolValue RandomReplacement { get { return RandomReplacementParameter.ActualValue; } }
     #endregion
 
@@ -124 +122 @@
     };
 
-
-    [StorableHook(HookType.AfterDeserialization)]
-    private void AfterDeserialization() {
-      if (!Parameters.ContainsKey(ChangedTreesParameterName))
-        Parameters.Add(new LookupParameter<IntValue>(ChangedTreesParameterName));
-    }
+    [Storable]
+    private readonly UpdateEstimatedValuesOperator updateEstimatedValuesOperator;
 
     public SchemaEvaluator() {
       qm = new QueryMatch(comp) { MatchParents = true };
+      this.updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
 
       Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(SchemaParameterName, "The current schema to be evaluated"));
@@ -148 +143 @@
       Parameters.Add(new LookupParameter<BoolValue>(RandomReplacementParameterName));
       Parameters.Add(new LookupParameter<IntValue>(ChangedTreesParameterName));
-    }
-
+      Parameters.Add(new LookupParameter<BoolValue>(ExecuteInParallelParameterName));
+      Parameters.Add(new LookupParameter<IntValue>(MaxDegreeOfParalellismParameterName));
+    }
 
     [StorableConstructor]
@@ -155 +151 @@
 
     protected SchemaEvaluator(SchemaEvaluator original, Cloner cloner) : base(original, cloner) {
-      this.comp = (ISymbolicExpressionTreeNodeEqualityComparer)original.comp.Clone();
-      this.qm = new QueryMatch(comp) { MatchParents = original.qm.MatchParents };
+      this.comp = original.comp == null ? new SymbolicExpressionTreeNodeEqualityComparer {
+        MatchConstantValues = false,
+        MatchVariableWeights = false,
+        MatchVariableNames = true
+      } : (ISymbolicExpressionTreeNodeEqualityComparer)original.comp.Clone();
+      this.qm = new QueryMatch(comp) { MatchParents = original.qm?.MatchParents ?? true };
+      this.updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
     }
 
@@ -163 +164 @@
     }
 
-    private static double CalculatePhenotypicSimilarity(ScopeList individuals, SymbolicExpressionTreePhenotypicSimilarityCalculator calculator) {
-      double similarity = 0;
-      int count = individuals.Count;
-      for (int i = 0; i < count - 1; ++i) {
-        for (int j = i + 1; j < count; ++j) {
-          similarity += calculator.CalculateSolutionSimilarity(individuals[i], individuals[j]);
-        }
-      }
-      return similarity / (count * (count - 1) / 2.0);
-    }
-
     public override IOperation Apply() {
       var individuals = ExecutionContext.Scope.SubScopes; // the scopes represent the individuals
@@ -179 +169 @@
       var random = RandomParameter.ActualValue;
       var mutator = MutatorParameter.ActualValue;
-      var evaluator = EvaluatorParameter.ActualValue;
-      var updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
 
       var s = SchemaParameter.ActualValue;
-      var matchingIndividuals = new ScopeList();
-      foreach (var ind in individuals) {
-        var t = (ISymbolicExpressionTree)ind.Variables["SymbolicExpressionTree"].Value;
-        if (t.Length >= s.Length && qm.Match(t, s))
-          matchingIndividuals.Add(ind);
-      }
-
-      if (matchingIndividuals.Count < (int)Math.Max(2, Math.Round(MinimumSchemaFrequency.Value * individuals.Count))) {
+      var sRoot = s.Root.GetSubtree(0).GetSubtree(0);
+      int countThreshold = (int)Math.Max(2, Math.Round(MinimumSchemaFrequency.Value * individuals.Count));
+
+      // first apply the length and root equality checks in order to filter the individuals
+      var filtered = (from ind in individuals
+                      let t = (ISymbolicExpressionTree)ind.Variables["SymbolicExpressionTree"].Value
+                      where t.Length >= s.Length && qm.Comparer.Equals(t.Root.GetSubtree(0).GetSubtree(0), sRoot)
+                      select ind).ToList();
+
+      // if we don't have enough filtered individuals, then we are done
+      if (filtered.Count < countThreshold) {
         ChangedTreesParameter.ActualValue = new IntValue(0);
         return base.Apply();
       }
 
-      var similarity = CalculatePhenotypicSimilarity(matchingIndividuals, calculator);
+      // check if the filtered individuals match the schema
+      var sNodes = QueryMatch.InitializePostOrder(sRoot);
+      var matchingIndividuals = new ScopeList();
+      bool executeInParallel = ExecuteInParallelParameter.ActualValue.Value;
+      int maxDegreeOfParallelism = MaxDegreeOfParallelismParameter.ActualValue.Value;
+
+      if (executeInParallel) {
+        var matching = new bool[filtered.Count];
+
+        Parallel.For(0, filtered.Count, new ParallelOptions { MaxDegreeOfParallelism = maxDegreeOfParallelism },
+          i => {
+            var t = (ISymbolicExpressionTree)filtered[i].Variables["SymbolicExpressionTree"].Value;
+            var tNodes = QueryMatch.InitializePostOrder(t.Root.GetSubtree(0).GetSubtree(0));
+            if (qm.Match(tNodes, sNodes)) {
+              matching[i] = true;
+            }
+          });
+
+        for (int i = 0; i < matching.Length; ++i) {
+          if (matching[i])
+            matchingIndividuals.Add(filtered[i]);
+        }
+      } else {
+        for (int i = 0; i < filtered.Count; ++i) {
+
+          // break early if it becomes impossible to reach the minimum threshold
+          if (matchingIndividuals.Count + filtered.Count - i < countThreshold)
+            break;
+
+          var ind = filtered[i];
+          var t = (ISymbolicExpressionTree)ind.Variables["SymbolicExpressionTree"].Value;
+          var tNodes = QueryMatch.InitializePostOrder(t.Root.GetSubtree(0).GetSubtree(0));
+          if (qm.Match(tNodes, sNodes))
+            matchingIndividuals.Add(ind);
+        }
+      }
+
+      if (matchingIndividuals.Count < countThreshold) {
+        ChangedTreesParameter.ActualValue = new IntValue(0);
+        return base.Apply();
+      }
+
+      var similarity = CalculatePhenotypicSimilarity(matchingIndividuals, calculator, executeInParallel, maxDegreeOfParallelism);
       if (similarity < MinimumPhenotypicSimilarity.Value) {
         ChangedTreesParameter.ActualValue = new IntValue(0);
@@ -201 +234 @@
       }
 
-      var oc = new OperationCollection();
       int n = (int)Math.Floor(matchingIndividuals.Count * ReplacementRatio.Value);
       var individualsToReplace = RandomReplacement.Value ? matchingIndividuals.SampleRandomWithoutRepetition(random, n).ToList()
                                                          : matchingIndividuals.OrderBy(x => (DoubleValue)x.Variables["Quality"].Value).Take(n).ToList();
+      var mutationOc = new OperationCollection { Parallel = false }; // cannot be parallel due to the before/after operators which insert vertices in the genealogy graph
+      var updateEstimatedValues = new OperationCollection { Parallel = true }; // evaluation should be done in parallel when possible
       foreach (var ind in individualsToReplace) {
         var mutatorOp = ExecutionContext.CreateChildOperation(mutator, ind);
-        var evaluatorOp = ExecutionContext.CreateChildOperation(evaluator, ind);
-        var updateEstimatedValuesOp = ExecutionContext.CreateChildOperation(updateEstimatedValuesOperator, ind);
-        oc.Add(mutatorOp);
-        oc.Add(evaluatorOp);
-        oc.Add(updateEstimatedValuesOp);
+        var updateOp = ExecutionContext.CreateChildOperation(updateEstimatedValuesOperator, ind);
+        mutationOc.Add(mutatorOp);
+        updateEstimatedValues.Add(updateOp);
       }
       ChangedTreesParameter.ActualValue = new IntValue(individualsToReplace.Count);
-      return new OperationCollection(oc, base.Apply());
+      return new OperationCollection(mutationOc, updateEstimatedValues, base.Apply());
+    }
+
+    private static double CalculatePhenotypicSimilarity(ScopeList individuals, SymbolicExpressionTreePhenotypicSimilarityCalculator calculator, bool parallel = false, int nThreads = -1) {
+      double similarity = 0;
+      int count = individuals.Count;
+      if (parallel) {
+        var parallelOptions = new ParallelOptions { MaxDegreeOfParallelism = nThreads };
+        var simArray = new double[count - 1];
+        Parallel.For(0, count - 1, parallelOptions, i => {
+          double innerSim = 0;
+          for (int j = i + 1; j < count; ++j) {
+            innerSim += calculator.CalculateSolutionSimilarity(individuals[i], individuals[j]);
+          }
+          simArray[i] = innerSim;
+        });
+        similarity = simArray.Sum();
+      } else {
+        for (int i = 0; i < count - 1; ++i) {
+          for (int j = i + 1; j < count; ++j) {
+            similarity += calculator.CalculateSolutionSimilarity(individuals[i], individuals[j]);
+          }
+        }
+      }
+      return similarity / (count * (count - 1) / 2.0);
     }
   }

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/UpdateEstimatedValuesOperator.cs

@@ -20 +20 @@
 #endregion
 
+using System;
 using System.Linq;
 using HeuristicLab.Common;
@@ -51 +52 @@
     }
 
+
     public UpdateEstimatedValuesOperator() {
       Parameters.Add(new LookupParameter<IRegressionProblemData>(ProblemDataParameterName));
@@ -74 +76 @@
       var interpreter = InterpreterParameter.ActualValue;
 
-      var estimatedValues = interpreter.GetSymbolicExpressionTreeValues(tree, problemData.Dataset, problemData.TrainingIndices)
-                                       .LimitToRange(estimationLimits.Lower, estimationLimits.Upper).ToArray();
+      var estimatedValues = interpreter.GetSymbolicExpressionTreeValues(tree, problemData.Dataset, problemData.TrainingIndices).ToArray();
+      var targetValues = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, problemData.TrainingIndices).ToArray();
+
+      if (estimatedValues.Length != targetValues.Length)
+        throw new ArgumentException("Number of elements in target and estimated values enumeration do not match.");
+
+      var linearScalingCalculator = new OnlineLinearScalingParameterCalculator();
+
+      for (int i = 0; i < estimatedValues.Length; ++i) {
+        var estimated = estimatedValues[i];
+        var target = targetValues[i];
+        if (!double.IsNaN(estimated) && !double.IsInfinity(estimated))
+          linearScalingCalculator.Add(estimated, target);
+      }
+      double alpha = linearScalingCalculator.Alpha;
+      double beta = linearScalingCalculator.Beta;
+      if (linearScalingCalculator.ErrorState != OnlineCalculatorError.None) {
+        alpha = 0.0;
+        beta = 1.0;
+      }
+
+      var scaled = estimatedValues.Select(x => x * beta + alpha).LimitToRange(estimationLimits.Lower, estimationLimits.Upper).ToArray();
+      OnlineCalculatorError error;
+      var r = OnlinePearsonsRCalculator.Calculate(targetValues, scaled, out error);
+      if (error != OnlineCalculatorError.None) r = 0;
+
+      var r2 = r * r;
+      if (r2 > 1.0) r2 = 1.0;
 
       var variables = ExecutionContext.Scope.Variables;
-      if (variables.ContainsKey("EstimatedValues"))
-        variables["EstimatedValues"].Value = new DoubleArray(estimatedValues);
-      else
-        variables.Add(new Core.Variable("EstimatedValues", new DoubleArray(estimatedValues)));
+      ((DoubleValue)variables["Quality"].Value).Value = r2;
+
+      if (variables.ContainsKey("EstimatedValues")) {
+        variables["EstimatedValues"].Value = new DoubleArray(scaled);
+      } else {
+        variables.Add(new Core.Variable("EstimatedValues", new DoubleArray(scaled)));
+      }
       return base.Apply();
     }