source: branches/TSNE/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/MctsSymbolicRegressionAlgorithm.cs @ 14558

Last change on this file since 14558 was 14558, checked in by bwerth, 3 years ago

#2700 made TSNE compatible with the new pausible BasicAlgs, removed rescaling of scatterplots during alg to give it a more movie-esque feel

File size: 15.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 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.Linq;
24using System.Threading;
25using HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression.Policies;
26using HeuristicLab.Analysis;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.Optimization;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.Problems.DataAnalysis;
34
35namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression {
36  [Item("MCTS Symbolic Regression", "Monte carlo tree search for symbolic regression. Useful mainly as a base learner in gradient boosting.")]
37  [StorableClass]
38  [Creatable(CreatableAttribute.Categories.DataAnalysisRegression, Priority = 250)]
39  public class MctsSymbolicRegressionAlgorithm : BasicAlgorithm {
40    public override Type ProblemType
41    {
42      get { return typeof(IRegressionProblem); }
43    }
44    public new IRegressionProblem Problem
45    {
46      get { return (IRegressionProblem)base.Problem; }
47      set { base.Problem = value; }
48    }
49    public override bool SupportsPause
50    {
51      get { return false; }
52    }
53
54    #region ParameterNames
55    private const string IterationsParameterName = "Iterations";
56    private const string MaxVariablesParameterName = "Maximum variables";
57    private const string ScaleVariablesParameterName = "Scale variables";
58    private const string AllowedFactorsParameterName = "Allowed factors";
59    private const string ConstantOptimizationIterationsParameterName = "Iterations (constant optimization)";
60    private const string PolicyParameterName = "Policy";
61    private const string SeedParameterName = "Seed";
62    private const string SetSeedRandomlyParameterName = "SetSeedRandomly";
63    private const string UpdateIntervalParameterName = "UpdateInterval";
64    private const string CreateSolutionParameterName = "CreateSolution";
65    private const string PunishmentFactorParameterName = "PunishmentFactor";
66
67    private const string VariableProductFactorName = "product(xi)";
68    private const string ExpFactorName = "exp(c * product(xi))";
69    private const string LogFactorName = "log(c + sum(c*product(xi))";
70    private const string InvFactorName = "1 / (1 + sum(c*product(xi))";
71    private const string FactorSumsName = "sum of multiple terms";
72    #endregion
73
74    #region ParameterProperties
75    public IFixedValueParameter<IntValue> IterationsParameter
76    {
77      get { return (IFixedValueParameter<IntValue>)Parameters[IterationsParameterName]; }
78    }
79    public IFixedValueParameter<IntValue> MaxVariableReferencesParameter
80    {
81      get { return (IFixedValueParameter<IntValue>)Parameters[MaxVariablesParameterName]; }
82    }
83    public IFixedValueParameter<BoolValue> ScaleVariablesParameter
84    {
85      get { return (IFixedValueParameter<BoolValue>)Parameters[ScaleVariablesParameterName]; }
86    }
87    public IFixedValueParameter<IntValue> ConstantOptimizationIterationsParameter
88    {
89      get { return (IFixedValueParameter<IntValue>)Parameters[ConstantOptimizationIterationsParameterName]; }
90    }
91    public IValueParameter<IPolicy> PolicyParameter
92    {
93      get { return (IValueParameter<IPolicy>)Parameters[PolicyParameterName]; }
94    }
95    public IFixedValueParameter<DoubleValue> PunishmentFactorParameter
96    {
97      get { return (IFixedValueParameter<DoubleValue>)Parameters[PunishmentFactorParameterName]; }
98    }
99    public IValueParameter<ICheckedItemList<StringValue>> AllowedFactorsParameter
100    {
101      get { return (IValueParameter<ICheckedItemList<StringValue>>)Parameters[AllowedFactorsParameterName]; }
102    }
103    public IFixedValueParameter<IntValue> SeedParameter
104    {
105      get { return (IFixedValueParameter<IntValue>)Parameters[SeedParameterName]; }
106    }
107    public FixedValueParameter<BoolValue> SetSeedRandomlyParameter
108    {
109      get { return (FixedValueParameter<BoolValue>)Parameters[SetSeedRandomlyParameterName]; }
110    }
111    public IFixedValueParameter<IntValue> UpdateIntervalParameter
112    {
113      get { return (IFixedValueParameter<IntValue>)Parameters[UpdateIntervalParameterName]; }
114    }
115    public IFixedValueParameter<BoolValue> CreateSolutionParameter
116    {
117      get { return (IFixedValueParameter<BoolValue>)Parameters[CreateSolutionParameterName]; }
118    }
119    #endregion
120
121    #region Properties
122    public int Iterations
123    {
124      get { return IterationsParameter.Value.Value; }
125      set { IterationsParameter.Value.Value = value; }
126    }
127    public int Seed
128    {
129      get { return SeedParameter.Value.Value; }
130      set { SeedParameter.Value.Value = value; }
131    }
132    public bool SetSeedRandomly
133    {
134      get { return SetSeedRandomlyParameter.Value.Value; }
135      set { SetSeedRandomlyParameter.Value.Value = value; }
136    }
137    public int MaxVariableReferences
138    {
139      get { return MaxVariableReferencesParameter.Value.Value; }
140      set { MaxVariableReferencesParameter.Value.Value = value; }
141    }
142    public IPolicy Policy
143    {
144      get { return PolicyParameter.Value; }
145      set { PolicyParameter.Value = value; }
146    }
147    public double PunishmentFactor
148    {
149      get { return PunishmentFactorParameter.Value.Value; }
150      set { PunishmentFactorParameter.Value.Value = value; }
151    }
152    public ICheckedItemList<StringValue> AllowedFactors
153    {
154      get { return AllowedFactorsParameter.Value; }
155    }
156    public int ConstantOptimizationIterations
157    {
158      get { return ConstantOptimizationIterationsParameter.Value.Value; }
159      set { ConstantOptimizationIterationsParameter.Value.Value = value; }
160    }
161    public bool ScaleVariables
162    {
163      get { return ScaleVariablesParameter.Value.Value; }
164      set { ScaleVariablesParameter.Value.Value = value; }
165    }
166    public bool CreateSolution
167    {
168      get { return CreateSolutionParameter.Value.Value; }
169      set { CreateSolutionParameter.Value.Value = value; }
170    }
171    #endregion
172
173    [StorableConstructor]
174    protected MctsSymbolicRegressionAlgorithm(bool deserializing) : base(deserializing) { }
175
176    protected MctsSymbolicRegressionAlgorithm(MctsSymbolicRegressionAlgorithm original, Cloner cloner)
177      : base(original, cloner) {
178    }
179
180    public override IDeepCloneable Clone(Cloner cloner) {
181      return new MctsSymbolicRegressionAlgorithm(this, cloner);
182    }
183
184    public MctsSymbolicRegressionAlgorithm() {
185      Problem = new RegressionProblem(); // default problem
186
187      var defaultFactorsList = new CheckedItemList<StringValue>(
188        new string[] { VariableProductFactorName, ExpFactorName, LogFactorName, InvFactorName, FactorSumsName }
189        .Select(s => new StringValue(s).AsReadOnly())
190        ).AsReadOnly();
191      defaultFactorsList.SetItemCheckedState(defaultFactorsList.First(s => s.Value == FactorSumsName), false);
192
193      Parameters.Add(new FixedValueParameter<IntValue>(IterationsParameterName,
194        "Number of iterations", new IntValue(100000)));
195      Parameters.Add(new FixedValueParameter<IntValue>(SeedParameterName,
196        "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
197      Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyParameterName,
198        "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
199      Parameters.Add(new FixedValueParameter<IntValue>(MaxVariablesParameterName,
200        "Maximal number of variables references in the symbolic regression models (multiple usages of the same variable are counted)", new IntValue(5)));
201      // Parameters.Add(new FixedValueParameter<DoubleValue>(CParameterName,
202      //   "Balancing parameter in UCT formula (0 < c < 1000). Small values: greedy search. Large values: enumeration. Default: 1.0", new DoubleValue(1.0)));
203      Parameters.Add(new ValueParameter<IPolicy>(PolicyParameterName,
204        "The policy to use for selecting nodes in MCTS (e.g. Ucb)", new Ucb()));
205      PolicyParameter.Hidden = true;
206      Parameters.Add(new ValueParameter<ICheckedItemList<StringValue>>(AllowedFactorsParameterName,
207        "Choose which expressions are allowed as factors in the model.", defaultFactorsList));
208
209      Parameters.Add(new FixedValueParameter<IntValue>(ConstantOptimizationIterationsParameterName,
210        "Number of iterations for constant optimization. A small number of iterations should be sufficient for most models. " +
211        "Set to 0 to disable constants optimization.", new IntValue(10)));
212      Parameters.Add(new FixedValueParameter<BoolValue>(ScaleVariablesParameterName,
213        "Set to true to scale all input variables to the range [0..1]", new BoolValue(false)));
214      Parameters[ScaleVariablesParameterName].Hidden = true;
215      Parameters.Add(new FixedValueParameter<DoubleValue>(PunishmentFactorParameterName, "Estimations of models can be bounded. The estimation limits are calculated in the following way (lb = mean(y) - punishmentFactor*range(y), ub = mean(y) + punishmentFactor*range(y))", new DoubleValue(10)));
216      Parameters[PunishmentFactorParameterName].Hidden = true;
217      Parameters.Add(new FixedValueParameter<IntValue>(UpdateIntervalParameterName,
218        "Number of iterations until the results are updated", new IntValue(100)));
219      Parameters[UpdateIntervalParameterName].Hidden = true;
220      Parameters.Add(new FixedValueParameter<BoolValue>(CreateSolutionParameterName,
221        "Flag that indicates if a solution should be produced at the end of the run", new BoolValue(true)));
222      Parameters[CreateSolutionParameterName].Hidden = true;
223    }
224
225    [StorableHook(HookType.AfterDeserialization)]
226    private void AfterDeserialization() {
227    }
228
229    protected override void Run(CancellationToken cancellationToken) {
230      // Set up the algorithm
231      if (SetSeedRandomly) Seed = new System.Random().Next();
232
233      // Set up the results display
234      var iterations = new IntValue(0);
235      Results.Add(new Result("Iterations", iterations));
236
237      var bestSolutionIteration = new IntValue(0);
238      Results.Add(new Result("Best solution iteration", bestSolutionIteration));
239
240      var table = new DataTable("Qualities");
241      table.Rows.Add(new DataRow("Best quality"));
242      table.Rows.Add(new DataRow("Current best quality"));
243      table.Rows.Add(new DataRow("Average quality"));
244      Results.Add(new Result("Qualities", table));
245
246      var bestQuality = new DoubleValue();
247      Results.Add(new Result("Best quality", bestQuality));
248
249      var curQuality = new DoubleValue();
250      Results.Add(new Result("Current best quality", curQuality));
251
252      var avgQuality = new DoubleValue();
253      Results.Add(new Result("Average quality", avgQuality));
254
255      var totalRollouts = new IntValue();
256      Results.Add(new Result("Total rollouts", totalRollouts));
257      var effRollouts = new IntValue();
258      Results.Add(new Result("Effective rollouts", effRollouts));
259      var funcEvals = new IntValue();
260      Results.Add(new Result("Function evaluations", funcEvals));
261      var gradEvals = new IntValue();
262      Results.Add(new Result("Gradient evaluations", gradEvals));
263
264
265      // same as in SymbolicRegressionSingleObjectiveProblem
266      var y = Problem.ProblemData.Dataset.GetDoubleValues(Problem.ProblemData.TargetVariable,
267        Problem.ProblemData.TrainingIndices);
268      var avgY = y.Average();
269      var minY = y.Min();
270      var maxY = y.Max();
271      var range = maxY - minY;
272      var lowerLimit = avgY - PunishmentFactor * range;
273      var upperLimit = avgY + PunishmentFactor * range;
274
275      // init
276      var problemData = (IRegressionProblemData)Problem.ProblemData.Clone();
277      if (!AllowedFactors.CheckedItems.Any()) throw new ArgumentException("At least on type of factor must be allowed");
278      var state = MctsSymbolicRegressionStatic.CreateState(problemData, (uint)Seed, MaxVariableReferences, ScaleVariables, ConstantOptimizationIterations,
279        Policy,
280        lowerLimit, upperLimit,
281        allowProdOfVars: AllowedFactors.CheckedItems.Any(s => s.Value.Value == VariableProductFactorName),
282        allowExp: AllowedFactors.CheckedItems.Any(s => s.Value.Value == ExpFactorName),
283        allowLog: AllowedFactors.CheckedItems.Any(s => s.Value.Value == LogFactorName),
284        allowInv: AllowedFactors.CheckedItems.Any(s => s.Value.Value == InvFactorName),
285        allowMultipleTerms: AllowedFactors.CheckedItems.Any(s => s.Value.Value == FactorSumsName)
286        );
287
288      var updateInterval = UpdateIntervalParameter.Value.Value;
289      double sumQ = 0.0;
290      double bestQ = 0.0;
291      double curBestQ = 0.0;
292      int n = 0;
293      // Loop until iteration limit reached or canceled.
294      for (int i = 0; i < Iterations && !state.Done; i++) {
295        cancellationToken.ThrowIfCancellationRequested();
296
297        var q = MctsSymbolicRegressionStatic.MakeStep(state);
298        sumQ += q; // sum of qs in the last updateinterval iterations
299        curBestQ = Math.Max(q, curBestQ); // the best q in the last updateinterval iterations
300        bestQ = Math.Max(q, bestQ); // the best q overall
301        n++;
302        // iteration results
303        if (n == updateInterval) {
304          if (bestQ > bestQuality.Value) {
305            bestSolutionIteration.Value = i;
306          }
307          bestQuality.Value = bestQ;
308          curQuality.Value = curBestQ;
309          avgQuality.Value = sumQ / n;
310          sumQ = 0.0;
311          curBestQ = 0.0;
312
313          funcEvals.Value = state.FuncEvaluations;
314          gradEvals.Value = state.GradEvaluations;
315          effRollouts.Value = state.EffectiveRollouts;
316          totalRollouts.Value = state.TotalRollouts;
317
318          table.Rows["Best quality"].Values.Add(bestQuality.Value);
319          table.Rows["Current best quality"].Values.Add(curQuality.Value);
320          table.Rows["Average quality"].Values.Add(avgQuality.Value);
321          iterations.Value += n;
322          n = 0;
323        }
324      }
325
326      // final results
327      if (n > 0) {
328        if (bestQ > bestQuality.Value) {
329          bestSolutionIteration.Value = iterations.Value + n;
330        }
331        bestQuality.Value = bestQ;
332        curQuality.Value = curBestQ;
333        avgQuality.Value = sumQ / n;
334
335        funcEvals.Value = state.FuncEvaluations;
336        gradEvals.Value = state.GradEvaluations;
337        effRollouts.Value = state.EffectiveRollouts;
338        totalRollouts.Value = state.TotalRollouts;
339
340        table.Rows["Best quality"].Values.Add(bestQuality.Value);
341        table.Rows["Current best quality"].Values.Add(curQuality.Value);
342        table.Rows["Average quality"].Values.Add(avgQuality.Value);
343        iterations.Value = iterations.Value + n;
344
345      }
346
347
348      Results.Add(new Result("Best solution quality (train)", new DoubleValue(state.BestSolutionTrainingQuality)));
349      Results.Add(new Result("Best solution quality (test)", new DoubleValue(state.BestSolutionTestQuality)));
350
351
352      // produce solution
353      if (CreateSolution) {
354        var model = state.BestModel;
355
356        // otherwise we produce a regression solution
357        Results.Add(new Result("Solution", model.CreateRegressionSolution(problemData)));
358      }
359    }
360  }
361}
Note: See TracBrowser for help on using the repository browser.