source: branches/3136_Structural_GP/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/SingleObjective/Evaluators/SymbolicRegressionConstantOptimizationEvaluator.cs @ 18103

Last change on this file since 18103 was 18103, checked in by dpiringe, 8 months ago

#3136

  • refactor the evaluation logic of NMSESingleObjectiveConstraintsEvaluator
  • refactor the new method Evaluate for PearsonRSquaredAverageSimilarityEvaluator
  • change the parameter order of some evaluate/calculate methods
File size: 21.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using HEAL.Attic;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
30using HeuristicLab.Optimization;
31using HeuristicLab.Parameters;
32using HeuristicLab.Random;
33
34namespace HeuristicLab.Problems.DataAnalysis.Symbolic.Regression {
35  [Item("Constant Optimization Evaluator", "Calculates Pearson R² of a symbolic regression solution and optimizes the constant used.")]
36  [StorableType("24B68851-036D-4446-BD6F-3823E9028FF4")]
37  public class SymbolicRegressionConstantOptimizationEvaluator : SymbolicRegressionSingleObjectiveEvaluator {
38    private const string ConstantOptimizationIterationsParameterName = "ConstantOptimizationIterations";
39    private const string ConstantOptimizationImprovementParameterName = "ConstantOptimizationImprovement";
40    private const string ConstantOptimizationProbabilityParameterName = "ConstantOptimizationProbability";
41    private const string ConstantOptimizationRowsPercentageParameterName = "ConstantOptimizationRowsPercentage";
42    private const string UpdateConstantsInTreeParameterName = "UpdateConstantsInSymbolicExpressionTree";
43    private const string UpdateVariableWeightsParameterName = "Update Variable Weights";
44
45    private const string FunctionEvaluationsResultParameterName = "Constants Optimization Function Evaluations";
46    private const string GradientEvaluationsResultParameterName = "Constants Optimization Gradient Evaluations";
47    private const string CountEvaluationsParameterName = "Count Function and Gradient Evaluations";
48
49    public IFixedValueParameter<IntValue> ConstantOptimizationIterationsParameter {
50      get { return (IFixedValueParameter<IntValue>)Parameters[ConstantOptimizationIterationsParameterName]; }
51    }
52    public IFixedValueParameter<DoubleValue> ConstantOptimizationImprovementParameter {
53      get { return (IFixedValueParameter<DoubleValue>)Parameters[ConstantOptimizationImprovementParameterName]; }
54    }
55    public IFixedValueParameter<PercentValue> ConstantOptimizationProbabilityParameter {
56      get { return (IFixedValueParameter<PercentValue>)Parameters[ConstantOptimizationProbabilityParameterName]; }
57    }
58    public IFixedValueParameter<PercentValue> ConstantOptimizationRowsPercentageParameter {
59      get { return (IFixedValueParameter<PercentValue>)Parameters[ConstantOptimizationRowsPercentageParameterName]; }
60    }
61    public IFixedValueParameter<BoolValue> UpdateConstantsInTreeParameter {
62      get { return (IFixedValueParameter<BoolValue>)Parameters[UpdateConstantsInTreeParameterName]; }
63    }
64    public IFixedValueParameter<BoolValue> UpdateVariableWeightsParameter {
65      get { return (IFixedValueParameter<BoolValue>)Parameters[UpdateVariableWeightsParameterName]; }
66    }
67
68    public IResultParameter<IntValue> FunctionEvaluationsResultParameter {
69      get { return (IResultParameter<IntValue>)Parameters[FunctionEvaluationsResultParameterName]; }
70    }
71    public IResultParameter<IntValue> GradientEvaluationsResultParameter {
72      get { return (IResultParameter<IntValue>)Parameters[GradientEvaluationsResultParameterName]; }
73    }
74    public IFixedValueParameter<BoolValue> CountEvaluationsParameter {
75      get { return (IFixedValueParameter<BoolValue>)Parameters[CountEvaluationsParameterName]; }
76    }
77
78
79    public IntValue ConstantOptimizationIterations {
80      get { return ConstantOptimizationIterationsParameter.Value; }
81    }
82    public DoubleValue ConstantOptimizationImprovement {
83      get { return ConstantOptimizationImprovementParameter.Value; }
84    }
85    public PercentValue ConstantOptimizationProbability {
86      get { return ConstantOptimizationProbabilityParameter.Value; }
87    }
88    public PercentValue ConstantOptimizationRowsPercentage {
89      get { return ConstantOptimizationRowsPercentageParameter.Value; }
90    }
91    public bool UpdateConstantsInTree {
92      get { return UpdateConstantsInTreeParameter.Value.Value; }
93      set { UpdateConstantsInTreeParameter.Value.Value = value; }
94    }
95
96    public bool UpdateVariableWeights {
97      get { return UpdateVariableWeightsParameter.Value.Value; }
98      set { UpdateVariableWeightsParameter.Value.Value = value; }
99    }
100
101    public bool CountEvaluations {
102      get { return CountEvaluationsParameter.Value.Value; }
103      set { CountEvaluationsParameter.Value.Value = value; }
104    }
105
106    public override bool Maximization {
107      get { return true; }
108    }
109
110    [StorableConstructor]
111    protected SymbolicRegressionConstantOptimizationEvaluator(StorableConstructorFlag _) : base(_) { }
112    protected SymbolicRegressionConstantOptimizationEvaluator(SymbolicRegressionConstantOptimizationEvaluator original, Cloner cloner)
113      : base(original, cloner) {
114    }
115    public SymbolicRegressionConstantOptimizationEvaluator()
116      : base() {
117      Parameters.Add(new FixedValueParameter<IntValue>(ConstantOptimizationIterationsParameterName, "Determines how many iterations should be calculated while optimizing the constant of a symbolic expression tree (0 indicates other or default stopping criterion).", new IntValue(10)));
118      Parameters.Add(new FixedValueParameter<DoubleValue>(ConstantOptimizationImprovementParameterName, "Determines the relative improvement which must be achieved in the constant optimization to continue with it (0 indicates other or default stopping criterion).", new DoubleValue(0)) { Hidden = true });
119      Parameters.Add(new FixedValueParameter<PercentValue>(ConstantOptimizationProbabilityParameterName, "Determines the probability that the constants are optimized", new PercentValue(1)));
120      Parameters.Add(new FixedValueParameter<PercentValue>(ConstantOptimizationRowsPercentageParameterName, "Determines the percentage of the rows which should be used for constant optimization", new PercentValue(1)));
121      Parameters.Add(new FixedValueParameter<BoolValue>(UpdateConstantsInTreeParameterName, "Determines if the constants in the tree should be overwritten by the optimized constants.", new BoolValue(true)) { Hidden = true });
122      Parameters.Add(new FixedValueParameter<BoolValue>(UpdateVariableWeightsParameterName, "Determines if the variable weights in the tree should be  optimized.", new BoolValue(true)) { Hidden = true });
123
124      Parameters.Add(new FixedValueParameter<BoolValue>(CountEvaluationsParameterName, "Determines if function and gradient evaluation should be counted.", new BoolValue(false)));
125      Parameters.Add(new ResultParameter<IntValue>(FunctionEvaluationsResultParameterName, "The number of function evaluations performed by the constants optimization evaluator", "Results", new IntValue()));
126      Parameters.Add(new ResultParameter<IntValue>(GradientEvaluationsResultParameterName, "The number of gradient evaluations performed by the constants optimization evaluator", "Results", new IntValue()));
127    }
128
129    public override IDeepCloneable Clone(Cloner cloner) {
130      return new SymbolicRegressionConstantOptimizationEvaluator(this, cloner);
131    }
132
133    [StorableHook(HookType.AfterDeserialization)]
134    private void AfterDeserialization() {
135      if (!Parameters.ContainsKey(UpdateConstantsInTreeParameterName))
136        Parameters.Add(new FixedValueParameter<BoolValue>(UpdateConstantsInTreeParameterName, "Determines if the constants in the tree should be overwritten by the optimized constants.", new BoolValue(true)));
137      if (!Parameters.ContainsKey(UpdateVariableWeightsParameterName))
138        Parameters.Add(new FixedValueParameter<BoolValue>(UpdateVariableWeightsParameterName, "Determines if the variable weights in the tree should be  optimized.", new BoolValue(true)));
139
140      if (!Parameters.ContainsKey(CountEvaluationsParameterName))
141        Parameters.Add(new FixedValueParameter<BoolValue>(CountEvaluationsParameterName, "Determines if function and gradient evaluation should be counted.", new BoolValue(false)));
142
143      if (!Parameters.ContainsKey(FunctionEvaluationsResultParameterName))
144        Parameters.Add(new ResultParameter<IntValue>(FunctionEvaluationsResultParameterName, "The number of function evaluations performed by the constants optimization evaluator", "Results", new IntValue()));
145      if (!Parameters.ContainsKey(GradientEvaluationsResultParameterName))
146        Parameters.Add(new ResultParameter<IntValue>(GradientEvaluationsResultParameterName, "The number of gradient evaluations performed by the constants optimization evaluator", "Results", new IntValue()));
147    }
148
149    private static readonly object locker = new object();
150    public override IOperation InstrumentedApply() {
151      var tree = SymbolicExpressionTreeParameter.ActualValue;
152      double quality;
153      if (RandomParameter.ActualValue.NextDouble() < ConstantOptimizationProbability.Value) {
154        IEnumerable<int> constantOptimizationRows = GenerateRowsToEvaluate(ConstantOptimizationRowsPercentage.Value);
155        var counter = new EvaluationsCounter();
156        quality = OptimizeConstants(SymbolicDataAnalysisTreeInterpreterParameter.ActualValue, tree, ProblemDataParameter.ActualValue,
157           constantOptimizationRows, ApplyLinearScalingParameter.ActualValue.Value, ConstantOptimizationIterations.Value, updateVariableWeights: UpdateVariableWeights, lowerEstimationLimit: EstimationLimitsParameter.ActualValue.Lower, upperEstimationLimit: EstimationLimitsParameter.ActualValue.Upper, updateConstantsInTree: UpdateConstantsInTree, counter: counter);
158
159        if (ConstantOptimizationRowsPercentage.Value != RelativeNumberOfEvaluatedSamplesParameter.ActualValue.Value) {
160          var evaluationRows = GenerateRowsToEvaluate();
161          quality = SymbolicRegressionSingleObjectivePearsonRSquaredEvaluator.Calculate(
162            tree, ProblemDataParameter.ActualValue,
163            evaluationRows, SymbolicDataAnalysisTreeInterpreterParameter.ActualValue,
164            ApplyLinearScalingParameter.ActualValue.Value,
165            EstimationLimitsParameter.ActualValue.Lower,
166            EstimationLimitsParameter.ActualValue.Upper);
167        }
168
169        if (CountEvaluations) {
170          lock (locker) {
171            FunctionEvaluationsResultParameter.ActualValue.Value += counter.FunctionEvaluations;
172            GradientEvaluationsResultParameter.ActualValue.Value += counter.GradientEvaluations;
173          }
174        }
175
176      } else {
177        var evaluationRows = GenerateRowsToEvaluate();
178        quality = SymbolicRegressionSingleObjectivePearsonRSquaredEvaluator.Calculate(
179          tree, ProblemDataParameter.ActualValue,
180          evaluationRows, SymbolicDataAnalysisTreeInterpreterParameter.ActualValue,
181          ApplyLinearScalingParameter.ActualValue.Value,
182          EstimationLimitsParameter.ActualValue.Lower,
183          EstimationLimitsParameter.ActualValue.Upper);
184      }
185      QualityParameter.ActualValue = new DoubleValue(quality);
186
187      return base.InstrumentedApply();
188    }
189
190    public override double Evaluate(
191      ISymbolicExpressionTree tree,
192      IRegressionProblemData problemData,
193      IEnumerable<int> rows,
194      ISymbolicDataAnalysisExpressionTreeInterpreter interpreter,
195      bool applyLinearScaling = true,
196      double lowerEstimationLimit = double.MinValue,
197      double upperEstimationLimit = double.MaxValue) {
198
199      var random = RandomParameter.ActualValue;
200      double quality = double.NaN;
201
202      var propability = random.NextDouble();
203      if (propability < ConstantOptimizationProbability.Value) {
204        IEnumerable<int> constantOptimizationRows = GenerateRowsToEvaluate(ConstantOptimizationRowsPercentage.Value);
205        quality = OptimizeConstants(
206          interpreter, tree,
207          problemData, constantOptimizationRows,
208          applyLinearScaling,
209          ConstantOptimizationIterations.Value,
210          updateVariableWeights: UpdateVariableWeights,
211          lowerEstimationLimit: lowerEstimationLimit,
212          upperEstimationLimit: upperEstimationLimit,
213          updateConstantsInTree: UpdateConstantsInTree);
214      }
215      if (double.IsNaN(quality) || ConstantOptimizationRowsPercentage.Value != RelativeNumberOfEvaluatedSamplesParameter.ActualValue.Value) {
216        quality = SymbolicRegressionSingleObjectivePearsonRSquaredEvaluator.Calculate(
217          tree, problemData,
218          rows, interpreter,
219          applyLinearScaling,
220          lowerEstimationLimit,
221          upperEstimationLimit);
222      }
223      return quality;
224    }
225
226    public override double Evaluate(IExecutionContext context, ISymbolicExpressionTree tree, IRegressionProblemData problemData, IEnumerable<int> rows) {
227      SymbolicDataAnalysisTreeInterpreterParameter.ExecutionContext = context;
228      EstimationLimitsParameter.ExecutionContext = context;
229      ApplyLinearScalingParameter.ExecutionContext = context;
230      FunctionEvaluationsResultParameter.ExecutionContext = context;
231      GradientEvaluationsResultParameter.ExecutionContext = context;
232
233      // Pearson R² evaluator is used on purpose instead of the const-opt evaluator,
234      // because Evaluate() is used to get the quality of evolved models on
235      // different partitions of the dataset (e.g., best validation model)
236      double r2 = SymbolicRegressionSingleObjectivePearsonRSquaredEvaluator.Calculate(
237        tree, problemData, rows,
238        SymbolicDataAnalysisTreeInterpreterParameter.ActualValue,
239        ApplyLinearScalingParameter.ActualValue.Value,
240        EstimationLimitsParameter.ActualValue.Lower,
241        EstimationLimitsParameter.ActualValue.Upper);
242
243      SymbolicDataAnalysisTreeInterpreterParameter.ExecutionContext = null;
244      EstimationLimitsParameter.ExecutionContext = null;
245      ApplyLinearScalingParameter.ExecutionContext = null;
246      FunctionEvaluationsResultParameter.ExecutionContext = null;
247      GradientEvaluationsResultParameter.ExecutionContext = null;
248
249      return r2;
250    }
251
252    public class EvaluationsCounter {
253      public int FunctionEvaluations = 0;
254      public int GradientEvaluations = 0;
255    }
256
257    public static double OptimizeConstants(ISymbolicDataAnalysisExpressionTreeInterpreter interpreter,
258      ISymbolicExpressionTree tree, IRegressionProblemData problemData, IEnumerable<int> rows, bool applyLinearScaling,
259      int maxIterations, bool updateVariableWeights = true,
260      double lowerEstimationLimit = double.MinValue, double upperEstimationLimit = double.MaxValue,
261      bool updateConstantsInTree = true, Action<double[], double, object> iterationCallback = null, EvaluationsCounter counter = null) {
262
263      // Numeric constants in the tree become variables for parameter optimization.
264      // Variables in the tree become parameters (fixed values) for parameter optimization.
265      // For each parameter (variable in the original tree) we store the
266      // variable name, variable value (for factor vars) and lag as a DataForVariable object.
267      // A dictionary is used to find parameters
268      double[] initialConstants;
269      var parameters = new List<TreeToAutoDiffTermConverter.DataForVariable>();
270
271      TreeToAutoDiffTermConverter.ParametricFunction func;
272      TreeToAutoDiffTermConverter.ParametricFunctionGradient func_grad;
273      if (!TreeToAutoDiffTermConverter.TryConvertToAutoDiff(tree, updateVariableWeights, applyLinearScaling, out parameters, out initialConstants, out func, out func_grad))
274        throw new NotSupportedException("Could not optimize constants of symbolic expression tree due to not supported symbols used in the tree.");
275      if (parameters.Count == 0) return 0.0; // constant expressions always have a R² of 0.0
276      var parameterEntries = parameters.ToArray(); // order of entries must be the same for x
277
278      // extract inital constants
279      double[] c;
280      if (applyLinearScaling) {
281        c = new double[initialConstants.Length + 2];
282        c[0] = 0.0;
283        c[1] = 1.0;
284        Array.Copy(initialConstants, 0, c, 2, initialConstants.Length);
285      } else {
286        c = (double[])initialConstants.Clone();
287      }
288
289      double originalQuality = SymbolicRegressionSingleObjectivePearsonRSquaredEvaluator.Calculate(
290        tree, problemData, rows,
291        interpreter, applyLinearScaling,
292        lowerEstimationLimit,
293        upperEstimationLimit);
294
295      if (counter == null) counter = new EvaluationsCounter();
296      var rowEvaluationsCounter = new EvaluationsCounter();
297
298      alglib.lsfitstate state;
299      alglib.lsfitreport rep;
300      int retVal;
301
302      IDataset ds = problemData.Dataset;
303      double[,] x = new double[rows.Count(), parameters.Count];
304      int row = 0;
305      foreach (var r in rows) {
306        int col = 0;
307        foreach (var info in parameterEntries) {
308          if (ds.VariableHasType<double>(info.variableName)) {
309            x[row, col] = ds.GetDoubleValue(info.variableName, r + info.lag);
310          } else if (ds.VariableHasType<string>(info.variableName)) {
311            x[row, col] = ds.GetStringValue(info.variableName, r) == info.variableValue ? 1 : 0;
312          } else throw new InvalidProgramException("found a variable of unknown type");
313          col++;
314        }
315        row++;
316      }
317      double[] y = ds.GetDoubleValues(problemData.TargetVariable, rows).ToArray();
318      int n = x.GetLength(0);
319      int m = x.GetLength(1);
320      int k = c.Length;
321
322      alglib.ndimensional_pfunc function_cx_1_func = CreatePFunc(func);
323      alglib.ndimensional_pgrad function_cx_1_grad = CreatePGrad(func_grad);
324      alglib.ndimensional_rep xrep = (p, f, obj) => iterationCallback(p, f, obj);
325
326      try {
327        alglib.lsfitcreatefg(x, y, c, n, m, k, false, out state);
328        alglib.lsfitsetcond(state, 0.0, maxIterations);
329        alglib.lsfitsetxrep(state, iterationCallback != null);
330        alglib.lsfitfit(state, function_cx_1_func, function_cx_1_grad, xrep, rowEvaluationsCounter);
331        alglib.lsfitresults(state, out retVal, out c, out rep);
332      } catch (ArithmeticException) {
333        return originalQuality;
334      } catch (alglib.alglibexception) {
335        return originalQuality;
336      }
337
338      counter.FunctionEvaluations += rowEvaluationsCounter.FunctionEvaluations / n;
339      counter.GradientEvaluations += rowEvaluationsCounter.GradientEvaluations / n;
340
341      //retVal == -7  => constant optimization failed due to wrong gradient
342      //          -8  => optimizer detected  NAN / INF  in  the target
343      //                 function and/ or gradient
344      if (retVal != -7 && retVal != -8) {
345        if (applyLinearScaling) {
346          var tmp = new double[c.Length - 2];
347          Array.Copy(c, 2, tmp, 0, tmp.Length);
348          UpdateConstants(tree, tmp, updateVariableWeights);
349        } else UpdateConstants(tree, c, updateVariableWeights);
350      }
351      var quality = SymbolicRegressionSingleObjectivePearsonRSquaredEvaluator.Calculate(
352        tree, problemData, rows,
353        interpreter, applyLinearScaling,
354        lowerEstimationLimit, upperEstimationLimit);
355
356      if (!updateConstantsInTree) UpdateConstants(tree, initialConstants, updateVariableWeights);
357
358      if (originalQuality - quality > 0.001 || double.IsNaN(quality)) {
359        UpdateConstants(tree, initialConstants, updateVariableWeights);
360        return originalQuality;
361      }
362      return quality;
363    }
364
365    private static void UpdateConstants(ISymbolicExpressionTree tree, double[] constants, bool updateVariableWeights) {
366      int i = 0;
367      foreach (var node in tree.Root.IterateNodesPrefix().OfType<SymbolicExpressionTreeTerminalNode>()) {
368        ConstantTreeNode constantTreeNode = node as ConstantTreeNode;
369        VariableTreeNodeBase variableTreeNodeBase = node as VariableTreeNodeBase;
370        FactorVariableTreeNode factorVarTreeNode = node as FactorVariableTreeNode;
371        if (constantTreeNode != null) {
372          if (constantTreeNode.Parent.Symbol is Power
373              && constantTreeNode.Parent.GetSubtree(1) == constantTreeNode) continue; // exponents in powers are not optimizated (see TreeToAutoDiffTermConverter)
374          constantTreeNode.Value = constants[i++];
375        } else if (updateVariableWeights && variableTreeNodeBase != null)
376          variableTreeNodeBase.Weight = constants[i++];
377        else if (factorVarTreeNode != null) {
378          for (int j = 0; j < factorVarTreeNode.Weights.Length; j++)
379            factorVarTreeNode.Weights[j] = constants[i++];
380        }
381      }
382    }
383
384    private static alglib.ndimensional_pfunc CreatePFunc(TreeToAutoDiffTermConverter.ParametricFunction func) {
385      return (double[] c, double[] x, ref double fx, object o) => {
386        fx = func(c, x);
387        var counter = (EvaluationsCounter)o;
388        counter.FunctionEvaluations++;
389      };
390    }
391
392    private static alglib.ndimensional_pgrad CreatePGrad(TreeToAutoDiffTermConverter.ParametricFunctionGradient func_grad) {
393      return (double[] c, double[] x, ref double fx, double[] grad, object o) => {
394        var tuple = func_grad(c, x);
395        fx = tuple.Item2;
396        Array.Copy(tuple.Item1, grad, grad.Length);
397        var counter = (EvaluationsCounter)o;
398        counter.GradientEvaluations++;
399      };
400    }
401    public static bool CanOptimizeConstants(ISymbolicExpressionTree tree) {
402      return TreeToAutoDiffTermConverter.IsCompatible(tree);
403    }
404  }
405}
Note: See TracBrowser for help on using the repository browser.