Changeset 16073

Timestamp:

08/13/18 08:58:58 (6 years ago)

Author:

bburlacu

Message:

#2886: Implement restarts for constant optimization in the RSquaredEvaluator

File:

• branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/RSquaredEvaluator.cs (modified) (7 diffs)

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/RSquaredEvaluator.cs

@@ -20 +20 @@
 #endregion
 
+using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -29 +30 @@
 using HeuristicLab.Problems.DataAnalysis.Symbolic;
 using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
+using HeuristicLab.Random;
 
 namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
@@ -37 +39 @@
     private readonly string ApplyLinearScalingParameterName = "Apply Linear Scaling";
     private readonly string ConstantOptimizationIterationsParameterName = "Constant Optimization Iterations";
+    private readonly string RestartsParameterName = "Restarts";
+    private readonly string SeedParameterName = "Seed"; // seed for the random number generator
+
+    private readonly MersenneTwister random = new MersenneTwister();
 
     #region parameter properties
@@ -49 +55 @@
     public IFixedValueParameter<IntValue> ConstantOptimizationIterationsParameter {
       get { return (IFixedValueParameter<IntValue>)Parameters[ConstantOptimizationIterationsParameterName]; }
+    }
+
+    private IFixedValueParameter<IntValue> RestartsParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[RestartsParameterName]; }
+    }
+
+    private int Restarts {
+      get { return RestartsParameter.Value.Value; }
+      set { RestartsParameter.Value.Value = value; }
     }
 
@@ -72 +87 @@
       Parameters.Add(new FixedValueParameter<BoolValue>(OptimizeConstantsParameterName, "Run constant optimization in sentence evaluation.", new BoolValue(false)));
       Parameters.Add(new FixedValueParameter<BoolValue>(ApplyLinearScalingParameterName, "Apply linear scaling on the tree model during evaluation.", new BoolValue(false)));
-      Parameters.Add(new FixedValueParameter<IntValue>(ConstantOptimizationIterationsParameterName, new IntValue(10)));
+      Parameters.Add(new FixedValueParameter<IntValue>(ConstantOptimizationIterationsParameterName, "Number of gradient descent iterations.", new IntValue(10)));
+      Parameters.Add(new FixedValueParameter<IntValue>(RestartsParameterName, "Number of restarts for gradient descent.", new IntValue(10)));
+
+      var seedParameter = new FixedValueParameter<IntValue>(SeedParameterName, "Seed value for random restarts.", new IntValue(0));
+      seedParameter.Value.ValueChanged += (sender, args) => random.Seed((uint)seedParameter.Value.Value);
+      random.Seed(0u);
+
+      Parameters.Add(seedParameter);
     }
 
@@ -87 +109 @@
     public double Evaluate(IRegressionProblemData problemData, Grammar grammar, SymbolList sentence) {
       var tree = grammar.ParseSymbolicExpressionTree(sentence);
-      return Evaluate(problemData, tree, OptimizeConstants, ConstantOptimizationIterations, ApplyLinearScaling);
+      return Evaluate(problemData, tree);
     }
 
     public double Evaluate(IRegressionProblemData problemData, ISymbolicExpressionTree tree) {
-      return Evaluate(problemData, tree, OptimizeConstants, ConstantOptimizationIterations, ApplyLinearScaling);
+      return Evaluate(problemData, tree, random, OptimizeConstants, ConstantOptimizationIterations, ApplyLinearScaling, Restarts);
     }
 
-    public static double Evaluate(IRegressionProblemData problemData, ISymbolicExpressionTree tree, bool optimizeConstants = true, int maxIterations = 10, bool applyLinearScaling = false) {
-      double r2;
-
-      // TODO: Initialize constant values randomly
-      // TODO: Restarts
-      if (optimizeConstants) {
-        r2 = SymbolicRegressionConstantOptimizationEvaluator.OptimizeConstants(expressionTreeLinearInterpreter,
-          tree,
-          problemData,
-          problemData.TrainingIndices,
-          applyLinearScaling: applyLinearScaling,
-          maxIterations: maxIterations,
-          updateVariableWeights: false,
-          updateConstantsInTree: true);
-
-        foreach (var symbolicExpressionTreeNode in tree.IterateNodesPostfix()) {
-          ConstantTreeNode constTreeNode = symbolicExpressionTreeNode as ConstantTreeNode;
-          if (constTreeNode != null && constTreeNode.Value.IsAlmost(0.0)) {
-            constTreeNode.Value = 0.0;
-          }
-        }
-      } else {
-        r2 = SymbolicRegressionSingleObjectivePearsonRSquaredEvaluator.Calculate(expressionTreeLinearInterpreter,
+    public static double Evaluate(IRegressionProblemData problemData, ISymbolicExpressionTree tree, IRandom random, bool optimizeConstants = true, int maxIterations = 10, bool applyLinearScaling = false, int restarts = 1) {
+      // we begin with an evaluation without constant optimization (relatively small speed penalty compared to const opt)
+      // this value will be used as a baseline to decide if an improvement was achieved via const opt 
+      double r2 = SymbolicRegressionSingleObjectivePearsonRSquaredEvaluator.Calculate(expressionTreeLinearInterpreter,
           tree,
           double.MinValue,
@@ -123 +126 @@
           problemData.TrainingIndices,
           applyLinearScaling: applyLinearScaling);
+
+      // restart const opt and try to obtain an improved r2 value
+      if (optimizeConstants) {
+        int count = 0;
+        double optimized = r2;
+        do {
+          foreach (var constantNode in tree.IterateNodesPrefix().OfType<ConstantTreeNode>()) {
+            constantNode.ResetLocalParameters(random);
+          }
+
+          optimized = SymbolicRegressionConstantOptimizationEvaluator.OptimizeConstants(
+            expressionTreeLinearInterpreter,
+            tree,
+            problemData,
+            problemData.TrainingIndices,
+            applyLinearScaling,
+            maxIterations,
+            false,
+            double.MinValue,
+            double.MaxValue,
+            true);
+        } while (optimized <= r2 && ++count < restarts);
+
+        // do not update constants if quality is not improved
+        if (optimized > r2) {
+          r2 = optimized;
+
+          // is this code really necessary ?
+          foreach (var symbolicExpressionTreeNode in tree.IterateNodesPostfix()) {
+            ConstantTreeNode constTreeNode = symbolicExpressionTreeNode as ConstantTreeNode;
+            if (constTreeNode != null && constTreeNode.Value.IsAlmost(0.0)) {
+              constTreeNode.Value = 0.0;
+            }
+          }
+        }
       }
-      return double.IsNaN(r2) ? 0.0 : r2;
+      return double.IsNaN(r2) || double.IsInfinity(r2) ? 0.0 : r2;
     }
   }