Changeset 17986

Timestamp:

06/13/21 19:36:59 (3 years ago)

Author:

gkronber

Message:

#3106 Fixed a bug: training data were not resampled in restarts for local search. Made a few minor changes to match the description in the paper (introduced two parameters for local search and changed likelihood of variables to be included.)

Location:

branches/3106_AnalyticContinuedFractionsRegression/HeuristicLab.Algorithms.DataAnalysis/3.4/ContinuedFractionRegression

Files:

• Algorithm.cs (modified) (18 diffs)
• ContinuedFraction.cs (modified) (1 diff)

branches/3106_AnalyticContinuedFractionsRegression/HeuristicLab.Algorithms.DataAnalysis/3.4/ContinuedFractionRegression/Algorithm.cs

@@ -37 +37 @@
     private const string DeltaParameterName = "Delta";
     private const string ScaleDataParameterName = "ScaleData";
+    private const string LocalSearchMinNumSamplesParameterName = "LocalSearchMinNumSamples";
+    private const string LocalSearchSamplesFractionParameterName = "LocalSearchSamplesFraction";
 
 
@@ -84 +86 @@
       get { return ScaleDataParameter.Value.Value; }
       set { ScaleDataParameter.Value.Value = value; }
+    }
+    public IFixedValueParameter<IntValue> LocalSearchMinNumSamplesParameter => (IFixedValueParameter<IntValue>)Parameters[LocalSearchMinNumSamplesParameterName];
+    public int LocalSearchMinNumSamples {
+      get { return LocalSearchMinNumSamplesParameter.Value.Value; }
+      set { LocalSearchMinNumSamplesParameter.Value.Value = value; }
+    }
+    public IFixedValueParameter<PercentValue> LocalSearchSamplesFractionParameter => (IFixedValueParameter<PercentValue>)Parameters[LocalSearchSamplesFractionParameterName];
+    public double LocalSearchSamplesFraction {
+      get { return LocalSearchSamplesFractionParameter.Value.Value; }
+      set { LocalSearchSamplesFractionParameter.Value.Value = value; }
     }
     #endregion
@@ -104 +116 @@
       Parameters.Add(new FixedValueParameter<IntValue>(LocalSearchIterationsParameterName, "Number of iterations for local search (simplex) (default value 250)", new IntValue(250)));
       Parameters.Add(new FixedValueParameter<IntValue>(LocalSearchRestartsParameterName, "Number of restarts for local search (default value 4)", new IntValue(4)));
-      Parameters.Add(new FixedValueParameter<DoubleValue>(LocalSearchToleranceParameterName, "The tolerance value for local search (simplex) (default value: 1e-3)", new DoubleValue(1e-3)));
+      Parameters.Add(new FixedValueParameter<DoubleValue>(LocalSearchToleranceParameterName, "The tolerance value for local search (simplex) (default value: 1e-3)", new DoubleValue(1e-3))); // page 12 of the preprint
       Parameters.Add(new FixedValueParameter<PercentValue>(DeltaParameterName, "The relative weight for the number of variables term in the fitness function (default value: 10%)", new PercentValue(0.1)));
       Parameters.Add(new FixedValueParameter<BoolValue>(ScaleDataParameterName, "Turns on/off scaling of input variable values to the range [0 .. 1] (default: false)", new BoolValue(false)));
-    }
+      Parameters.Add(new FixedValueParameter<IntValue>(LocalSearchMinNumSamplesParameterName, "The minimum number of samples for the local search (default 200)", new IntValue(200)));
+      Parameters.Add(new FixedValueParameter<PercentValue>(LocalSearchSamplesFractionParameterName, "The fraction of samples used for local search. Only used when the number of samples is more than " + LocalSearchMinNumSamplesParameterName + " (default 20%)", new PercentValue(0.2)));
+    }
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      // for backwards compatibility
+      if (!Parameters.ContainsKey(LocalSearchMinNumSamplesParameterName))
+        Parameters.Add(new FixedValueParameter<IntValue>(LocalSearchMinNumSamplesParameterName, "The minimum number of samples for the local search (default 200)", new IntValue(200)));
+      if (!Parameters.ContainsKey(LocalSearchSamplesFractionParameterName))
+        Parameters.Add(new FixedValueParameter<PercentValue>(LocalSearchSamplesFractionParameterName, "The fraction of samples used for local search. Only used when the number of samples is more than " + LocalSearchMinNumSamplesParameterName + " (default 20%)", new PercentValue(0.2)));
+    }
+
 
     public override IDeepCloneable Clone(Cloner cloner) {
@@ -116 +140 @@
       var problemData = Problem.ProblemData;
       double[,] xy;
+      var transformations = new List<ITransformation<double>>();
       if (ScaleData) {
+        // TODO: scaling via transformations is really ugly.
         // Scale data to range 0 .. 1
         // 
         // Scaling was not used for the experiments in the paper. Statement by the authors: "We did not pre-process the data."
-        var transformations = new List<Transformation<double>>();
         foreach (var input in problemData.AllowedInputVariables) {
           var values = problemData.Dataset.GetDoubleValues(input, problemData.TrainingIndices);
@@ -129 +154 @@
           linTransformation.Addend = -min / range;
           linTransformation.Multiplier = 1.0 / range;
+          linTransformation.ColumnParameter.ActualValue = linTransformation.ColumnParameter.ValidValues.First(sv => sv.Value == input);
           transformations.Add(linTransformation);
         }
         // do not scale the target 
-        transformations.Add(new LinearTransformation(problemData.AllowedInputVariables) { Addend = 0.0, Multiplier = 1.0 });
+        var targetTransformation = new LinearTransformation(new string[] { problemData.TargetVariable }) { Addend = 0.0, Multiplier = 1.0 };
+        targetTransformation.ColumnParameter.ActualValue = targetTransformation.ColumnParameter.ValidValues.First(sv => sv.Value == problemData.TargetVariable);
+        transformations.Add(targetTransformation);
         xy = problemData.Dataset.ToArray(problemData.AllowedInputVariables.Concat(new[] { problemData.TargetVariable }),
           transformations,
@@ -144 +172 @@
       var seed = new System.Random().Next();
       var rand = new MersenneTwister((uint)seed);
-      CFRAlgorithm(nVars, Depth, MutationRate, xy, out var bestObj, rand, NumGenerations, StagnationGenerations,
-        Delta,
-        LocalSearchIterations, LocalSearchRestarts, LocalSearchTolerance, cancellationToken);
-    }
-
-    private void CFRAlgorithm(int nVars, int depth, double mutationRate, double[,] trainingData,
-      out double bestObj,
-      IRandom rand, int numGen, int stagnatingGens, double evalDelta,
-      int localSearchIterations, int localSearchRestarts, double localSearchTolerance,
-      CancellationToken cancellationToken) {
-      /* Algorithm 1 */
-      /* Generate initial population by a randomized algorithm */
-      var pop = InitialPopulation(nVars, depth, rand, trainingData);
-      bestObj = pop.pocketObjValue;
-      // the best value since the last reset
-      var episodeBestObj = pop.pocketObjValue;
-      var episodeBestObjGen = 0;
-      for (int gen = 1; gen <= numGen && !cancellationToken.IsCancellationRequested; gen++) {
-        /* mutate each current solution in the population */
-        var pop_mu = Mutate(pop, mutationRate, rand, trainingData);
-        /* generate new population by recombination mechanism */
-        var pop_r = RecombinePopulation(pop_mu, rand, nVars, trainingData);
-
-        // Paper:
-        // A period of individual search operation is performed every generation on all current solutions.
-
-        // Statement by authors:
-        // "We ran the Local Search after Mutation and recombination operations. We executed the local-search only on the Current solutions."
-        // "We executed the MaintainInvariant() in the following steps:
-        // - After generating the initial population
-        // - after resetting the root
-        // - after executing the local-search on the whole population.
-        // We updated the pocket/ current automatically after mutation and recombination operation."
-
-        /* local search optimization of current solutions */
-        foreach (var agent in pop_r.IterateLevels()) {
-          LocalSearchSimplex(localSearchIterations, localSearchRestarts, localSearchTolerance, evalDelta, agent, trainingData, rand);
-          Debug.Assert(agent.pocketObjValue < agent.currentObjValue);
-        }
-        foreach (var agent in pop_r.IteratePostOrder()) agent.MaintainInvariant(); // post-order to make sure that the root contains the best model 
-        foreach (var agent in pop_r.IteratePostOrder()) agent.AssertInvariant();
-
-        // for detecting stagnation we track the best objective value since the last reset 
-        // and reset if this does not change for stagnatingGens
-        if (gen > episodeBestObjGen + stagnatingGens) {
-          Reset(pop_r, nVars, depth, rand, trainingData);
-          episodeBestObj = double.MaxValue;
-        }
-        if (episodeBestObj > pop_r.pocketObjValue) {
-          episodeBestObjGen = gen; // wait at least stagnatingGens until resetting again
-          episodeBestObj = pop_r.pocketObjValue;
-        }
-
-        /* replace old population with evolved population */
-        pop = pop_r;
-
-        /* keep track of the best solution */
-        if (bestObj > pop.pocketObjValue) {
-          bestObj = pop.pocketObjValue;
-          Results.AddOrUpdateResult("MSE (best)", new DoubleValue(bestObj));
-          Results.AddOrUpdateResult("Solution", CreateSymbolicRegressionSolution(pop.pocket, trainingData, Problem.ProblemData.AllowedInputVariables.ToArray(), Problem.ProblemData.TargetVariable));
-        }
-
+
+      void iterationCallback(Agent pop) {
         #region visualization and debugging
         DataTable qualities;
@@ -230 +197 @@
         #endregion
       }
+      void newBestSolutionCallback(ContinuedFraction best, double objVal) {
+        Results.AddOrUpdateResult("MSE (best)", new DoubleValue(objVal));
+        Results.AddOrUpdateResult("Solution", CreateSymbolicRegressionSolution(best, problemData, transformations));
+      }
+
+      CFRAlgorithm(nVars, Depth, MutationRate, xy, out var bestObj, rand, NumGenerations, StagnationGenerations,
+        Delta,
+        LocalSearchIterations, LocalSearchRestarts, LocalSearchTolerance, newBestSolutionCallback, iterationCallback, cancellationToken);
+    }
+
+    private void CFRAlgorithm(int nVars, int depth, double mutationRate, double[,] trainingData,
+      out double bestObj,
+      IRandom rand, int numGen, int stagnatingGens, double evalDelta,
+      int localSearchIterations, int localSearchRestarts, double localSearchTolerance,
+      Action<ContinuedFraction, double> newBestSolutionCallback,
+      Action<Agent> iterationCallback,
+      CancellationToken cancellationToken) {
+      /* Algorithm 1 */
+      /* Generate initial population by a randomized algorithm */
+      var pop = InitialPopulation(nVars, depth, rand, trainingData);
+      bestObj = pop.pocketObjValue;
+      // the best value since the last reset
+      var episodeBestObj = pop.pocketObjValue;
+      var episodeBestObjGen = 0;
+      for (int gen = 1; gen <= numGen && !cancellationToken.IsCancellationRequested; gen++) {
+        /* mutate each current solution in the population */
+        var pop_mu = Mutate(pop, mutationRate, rand, trainingData);
+        /* generate new population by recombination mechanism */
+        var pop_r = RecombinePopulation(pop_mu, rand, nVars, trainingData);
+
+        // Paper:
+        // A period of individual search operation is performed every generation on all current solutions.
+
+        // Statement by authors:
+        // "We ran the Local Search after Mutation and recombination operations. We executed the local-search only on the Current solutions."
+        // "We executed the MaintainInvariant() in the following steps:
+        // - After generating the initial population
+        // - after resetting the root
+        // - after executing the local-search on the whole population.
+        // We updated the pocket/ current automatically after mutation and recombination operation."
+
+        /* local search optimization of current solutions */
+        foreach (var agent in pop_r.IterateLevels()) {
+          LocalSearchSimplex(localSearchIterations, localSearchRestarts, localSearchTolerance, LocalSearchMinNumSamples, LocalSearchSamplesFraction, evalDelta, agent, trainingData, rand);
+          Debug.Assert(agent.pocketObjValue < agent.currentObjValue);
+        }
+        foreach (var agent in pop_r.IteratePostOrder()) agent.MaintainInvariant(); // post-order to make sure that the root contains the best model 
+        foreach (var agent in pop_r.IteratePostOrder()) agent.AssertInvariant();
+
+        // for detecting stagnation we track the best objective value since the last reset 
+        // and reset if this does not change for stagnatingGens
+        if (gen > episodeBestObjGen + stagnatingGens) {
+          Reset(pop_r, nVars, depth, rand, trainingData);
+          episodeBestObj = double.MaxValue;
+        }
+        if (episodeBestObj > pop_r.pocketObjValue) {
+          episodeBestObjGen = gen; // wait at least stagnatingGens until resetting again
+          episodeBestObj = pop_r.pocketObjValue;
+        }
+
+        /* replace old population with evolved population */
+        pop = pop_r;
+
+        /* keep track of the best solution */
+        if (bestObj > pop.pocketObjValue) {
+          bestObj = pop.pocketObjValue;
+          newBestSolutionCallback(pop.pocket, bestObj);
+        }
+
+
+        iterationCallback(pop);
+      }
     }
 
@@ -264 +303 @@
     }
 
-    // Reset is not described in detail in the paper.
+    // Our criterion for relevance has been fairly strict: if no
+    // better model has been produced for five(5) straight generations,
+    // then the pocket of the root agent is removed and a new solution is created at random.
+
     // Statement by the authors: "We only replaced the pocket solution of the root with
     // a randomly generated solution. Then we execute the maintain-invariant process.
@@ -270 +312 @@
     private void Reset(Agent root, int nVars, int depth, IRandom rand, double[,] trainingData) {
       root.pocket = new ContinuedFraction(nVars, depth, rand);
-      root.current = new ContinuedFraction(nVars, depth, rand);
-
-      root.currentObjValue = Evaluate(root.current, trainingData, Delta);
       root.pocketObjValue = Evaluate(root.pocket, trainingData, Delta);
 
@@ -348 +387 @@
 
       a.current = ch;
-      LocalSearchSimplex(LocalSearchIterations, LocalSearchRestarts, LocalSearchTolerance, Delta, a, trainingData, rand);
+      LocalSearchSimplex(LocalSearchIterations, LocalSearchRestarts, LocalSearchTolerance, LocalSearchMinNumSamples, LocalSearchSamplesFraction, Delta, a, trainingData, rand);
       return ch;
     }
@@ -364 +403 @@
           // non-zero coefficients. We do not apply mutation on pocket solutions because we consider them as a "collective memory"
           // of good models visited in the past. They influence the search process via recombination only.
-          LocalSearchSimplex(LocalSearchIterations, LocalSearchRestarts, LocalSearchTolerance, Delta, agent, trainingData, rand);
+          LocalSearchSimplex(LocalSearchIterations, LocalSearchRestarts, LocalSearchTolerance, LocalSearchMinNumSamples, LocalSearchSamplesFraction, Delta, agent, trainingData, rand);
         }
       }
@@ -483 +522 @@
 
 
-    private static void LocalSearchSimplex(int iterations, int restarts, double tolerance, double delta, Agent a, double[,] trainingData, IRandom rand) {
-      double uniformPeturbation = 1.0;
+    // The authors used the Nelder Mead solver from https://direct.mit.edu/evco/article/25/3/351/1046/Evolving-a-Nelder-Mead-Algorithm-for-Optimization
+    // Using different solvers (e.g. LevMar) is mentioned but not analysed
+
+
+    private static void LocalSearchSimplex(int iterations, int restarts, double tolerance, int minNumRows, double samplesFrac, double delta, Agent a, double[,] trainingData, IRandom rand) {
       int maxEvals = iterations;
       int numSearches = restarts + 1;
       var numRows = trainingData.GetLength(0);
-      int numSelectedRows = numRows / 5; // 20% of the training samples
+      int numSelectedRows = numRows;
+      if (numRows > minNumRows)
+        numSelectedRows = (int)(numRows * samplesFrac);
 
       var ch = a.current;
@@ -499 +543 @@
       var bestCoeff = origCoeff;
 
-      var fittingData = SelectRandomRows(trainingData, numSelectedRows, rand);
+      double[,] fittingData = null;
 
       double objFunc(double[] curCoeff) {
@@ -507 +551 @@
 
       for (int count = 0; count < numSearches; count++) {
+        fittingData = SelectRandomRows(trainingData, numSelectedRows, rand);
 
         SimplexConstant[] constants = new SimplexConstant[origCoeff.Length];
         for (int i = 0; i < origCoeff.Length; i++) {
-          constants[i] = new SimplexConstant(origCoeff[i], uniformPeturbation);
+          constants[i] = new SimplexConstant(origCoeff[i], initialPerturbation: 1.0);
         }
 
@@ -518 +563 @@
         SetCoeff(ch, optimizedCoeff);
 
+        // the result with the best guiding function value (on the entire dataset) is chosen.
         var newQuality = Evaluate(ch, trainingData, delta);
 
@@ -524 +570 @@
           bestQuality = newQuality;
         }
-      } // reps
+      }
 
       SetCoeff(a.current, bestCoeff);
@@ -585 +631 @@
     Symbol varSy = new Problems.DataAnalysis.Symbolic.Variable();
 
-    private ISymbolicRegressionSolution CreateSymbolicRegressionSolution(ContinuedFraction cfrac, double[,] trainingData, string[] variables, string targetVariable) {
+    private ISymbolicRegressionSolution CreateSymbolicRegressionSolution(ContinuedFraction cfrac, IRegressionProblemData problemData, List<ITransformation<double>> transformations) {
+      var variables = problemData.AllowedInputVariables.ToArray();
       ISymbolicExpressionTreeNode res = null;
       for (int i = cfrac.h.Length - 1; i > 1; i -= 2) {
@@ -611 +658 @@
       start.AddSubtree(h0Term);
 
-      var model = new SymbolicRegressionModel(targetVariable, new SymbolicExpressionTree(progRoot), new SymbolicDataAnalysisExpressionTreeBatchInterpreter());
-      var ds = new Dataset(variables.Concat(new[] { targetVariable }), trainingData);
-      var problemData = new RegressionProblemData(ds, variables, targetVariable);
-      var sol = new SymbolicRegressionSolution(model, problemData);
+      ISymbolicRegressionModel model = new SymbolicRegressionModel(problemData.TargetVariable, new SymbolicExpressionTree(progRoot), new SymbolicDataAnalysisExpressionTreeBatchInterpreter());
+      if (transformations != null && transformations.Any()) {
+        var backscaling = new SymbolicExpressionTreeBacktransformator(new TransformationToSymbolicTreeMapper());
+        model = (ISymbolicRegressionModel)backscaling.Backtransform(model, transformations, problemData.TargetVariable);
+      }
+      var sol = new SymbolicRegressionSolution(model, (IRegressionProblemData)problemData.Clone());
       return sol;
     }

branches/3106_AnalyticContinuedFractionsRegression/HeuristicLab.Algorithms.DataAnalysis/3.4/ContinuedFractionRegression/ContinuedFraction.cs

@@ -9 +9 @@
     public ContinuedFraction(int nVars, int depth, IRandom rand) {
       this.vars = new bool[nVars];
-      for (int i = 0; i < nVars; i++) vars[i] = rand.NextDouble() < 0.5;
+      for (int i = 0; i < nVars; i++) vars[i] = rand.NextDouble() < 0.3; // page 12 of the preprint. Each input variable then has a probability p = 1/3 to be present in the whitelist
 
       this.h = new Term[depth * 2 + 1];