Free cookie consent management tool by TermsFeed Policy Generator

source: branches/3073_IA_constraint_splitting/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/IntervalInterpreter.cs @ 17637

Last change on this file since 17637 was 17637, checked in by chaider, 4 years ago

#3073 Changed variable ranges to readonly at GetIntervals methods
File size: 20.8 KB
Line 
1#region License Information
2
3/* HeuristicLab
4 * Copyright (C) Heuristic and Evolutionary Algorithms Laboratory (HEAL)
5 *
6 * This file is part of HeuristicLab.
7 *
8 * HeuristicLab is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * HeuristicLab is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
20 */
21
22#endregion
23
24using System;
25using System.Collections.Generic;
26using System.Collections.ObjectModel;
27using System.Linq;
28using System.Runtime.Remoting.Contexts;
29using HEAL.Attic;
30using HeuristicLab.Common;
31using HeuristicLab.Core;
32using HeuristicLab.Data;
33using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
34using HeuristicLab.Parameters;
35
36namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
37  [StorableType("DE6C1E1E-D7C1-4070-847E-63B68562B10C")]
38  [Item("IntervalInterpreter", "Interpreter for calculation of intervals of symbolic models.")]
39  public sealed class IntervalInterpreter : ParameterizedNamedItem, IStatefulItem {
40    private const string EvaluatedSolutionsParameterName = "EvaluatedSolutions";
41    private const string MinSplittingWidthParameterName = "MinSplittingWidth";
42    private const string MaxSplittingDepthParameterName = "MaxSplittingDepth";
43    private const string UseIntervalSplittingParameterName = "UseIntervalSplitting";
44
45    public IFixedValueParameter<IntValue> EvaluatedSolutionsParameter =>
46      (IFixedValueParameter<IntValue>) Parameters[EvaluatedSolutionsParameterName];
47
48    public IFixedValueParameter<IntValue> MinSplittingWithParameter =>
49      (IFixedValueParameter<IntValue>) Parameters[MinSplittingWidthParameterName];
50
51    public IFixedValueParameter<IntValue> MaxSplittingDepthParameter =>
52      (IFixedValueParameter<IntValue>) Parameters[MaxSplittingDepthParameterName];
53
54    public IFixedValueParameter<BoolValue> UseIntervalSplittingParameter =>
55      (IFixedValueParameter<BoolValue>) Parameters[UseIntervalSplittingParameterName];
56
57    public int MinSplittingWidth {
58      get => MinSplittingWithParameter.Value.Value;
59      set => MinSplittingWithParameter.Value.Value = value;
60    }
61
62    public int MaxSplittingDepth {
63      get => MaxSplittingDepthParameter.Value.Value;
64      set => MaxSplittingDepthParameter.Value.Value = value;
65    }
66
67    public bool UseIntervalSplitting {
68      get => UseIntervalSplittingParameter.Value.Value;
69      set => UseIntervalSplittingParameter.Value.Value = value;
70    }
71
72    public int EvaluatedSolutions {
73      get => EvaluatedSolutionsParameter.Value.Value;
74      set => EvaluatedSolutionsParameter.Value.Value = value;
75    }
76
77    [StorableConstructor]
78    private IntervalInterpreter(StorableConstructorFlag _) : base(_) { }
79
80    private IntervalInterpreter(IntervalInterpreter original, Cloner cloner)
81      : base(original, cloner) { }
82   
83    public IntervalInterpreter()
84      : base("IntervalInterpreter", "Interpreter for calculation of intervals of symbolic models.") {
85      Parameters.Add(new FixedValueParameter<IntValue>(EvaluatedSolutionsParameterName,
86        "A counter for the total number of solutions the interpreter has evaluated", new IntValue(0)));
87      Parameters.Add(new FixedValueParameter<IntValue>(MinSplittingWidthParameterName, "Minimum interval width until splitting is stopped", new IntValue(0)));
88      Parameters.Add(new FixedValueParameter<IntValue>(MaxSplittingDepthParameterName, "Maximum recursion depth of the splitting", new IntValue(5)));
89      Parameters.Add(new FixedValueParameter<BoolValue>(UseIntervalSplittingParameterName, "", new BoolValue(false)));
90    }
91   
92    public override IDeepCloneable Clone(Cloner cloner) {
93      return new IntervalInterpreter(this, cloner);
94    }
95
96    private readonly object syncRoot = new object();
97
98    #region IStatefulItem Members
99
100    public void InitializeState() {
101      EvaluatedSolutions = 0;
102    }
103
104    public void ClearState() { }
105
106    #endregion
107
108    public Interval GetSymbolicExpressionTreeInterval(
109      ISymbolicExpressionTree tree, IDataset dataset,
110      IEnumerable<int> rows = null) {
111      var variableRanges = DatasetUtil.GetVariableRanges(dataset, rows);
112      return GetSymbolicExpressionTreeInterval(tree, variableRanges);
113    }
114
115    public Interval GetSymbolicExpressionTreeIntervals(
116      ISymbolicExpressionTree tree, IDataset dataset,
117      out IDictionary<ISymbolicExpressionTreeNode, Interval>
118        nodeIntervals, IEnumerable<int> rows = null) {
119      var variableRanges = DatasetUtil.GetVariableRanges(dataset, rows);
120      return GetSymbolicExpressionTreeIntervals(tree, variableRanges, out nodeIntervals);
121    }
122
123    public Interval GetSymbolicExpressionTreeInterval(
124      ISymbolicExpressionTree tree,
125      IReadOnlyDictionary<string, Interval> variableRanges) {
126      lock (syncRoot) {
127        EvaluatedSolutions++;
128      }
129
130      Interval outputInterval;
131
132      if (UseIntervalSplitting) {
133        outputInterval = GetSymbolicExpressionTreeIntervals(tree, variableRanges,
134          out var nodeIntervals);
135      } else {
136        var instructionCount = 0;
137        var instructions = PrepareInterpreterState(tree, variableRanges);
138        outputInterval = Evaluate(instructions, ref instructionCount);
139      }
140
141      return outputInterval.LowerBound <= outputInterval.UpperBound
142        ? outputInterval
143        : new Interval(outputInterval.UpperBound, outputInterval.LowerBound);
144    }
145
146
147    public Interval GetSymbolicExpressionTreeIntervals(
148      ISymbolicExpressionTree tree,
149      IReadOnlyDictionary<string, Interval> variableRanges,
150      out IDictionary<ISymbolicExpressionTreeNode, Interval>
151        nodeIntervals) {
152      lock (syncRoot) {
153        EvaluatedSolutions++;
154      }
155
156      var intervals = new Dictionary<ISymbolicExpressionTreeNode, Interval>();
157      var instructions = PrepareInterpreterState(tree, variableRanges);
158
159      Interval outputInterval;
160      if (UseIntervalSplitting) {
161        var variables = tree.IterateNodesPrefix().OfType<VariableTreeNode>().Select(x => x.VariableName).Distinct()
162                            .ToList();
163        var containsDependencyProblem = ContainsVariableMultipleTimes(tree);
164
165        if (variables.Count > 1 && containsDependencyProblem) {
166          var currIndex = 0;
167          var currDepth = 0;
168          IDictionary<string, Interval> writeableVariableRanges = variableRanges.ToDictionary(kvp => kvp.Key, kvp => kvp.Value);
169          outputInterval = EvaluateRecursive(instructions, intervals, writeableVariableRanges, variables, MinSplittingWidth, MaxSplittingDepth,
170            ref currIndex, ref currDepth, tree);
171        } else {
172          var instructionCount = 0;
173          outputInterval = Evaluate(instructions, ref instructionCount, intervals);
174        }
175      } else {
176        var instructionCount = 0;
177        outputInterval = Evaluate(instructions, ref instructionCount, intervals);
178      }
179
180      nodeIntervals = new Dictionary<ISymbolicExpressionTreeNode, Interval>();
181      foreach (var kvp in intervals) {
182        var interval = kvp.Value;
183        if (interval.IsInfiniteOrUndefined || interval.LowerBound <= interval.UpperBound)
184          nodeIntervals.Add(kvp.Key, interval);
185        else
186          nodeIntervals.Add(kvp.Key, new Interval(interval.UpperBound, interval.LowerBound));
187      }
188
189      // because of numerical errors the bounds might be incorrect
190      if (outputInterval.IsInfiniteOrUndefined || outputInterval.LowerBound <= outputInterval.UpperBound)
191        return outputInterval;
192
193      return new Interval(outputInterval.UpperBound, outputInterval.LowerBound);
194    }
195
196
197    private static Instruction[] PrepareInterpreterState(
198      ISymbolicExpressionTree tree,
199      IReadOnlyDictionary<string, Interval> variableRanges) {
200      if (variableRanges == null)
201        throw new ArgumentNullException("No variablew ranges are present!", nameof(variableRanges));
202
203      //Check if all variables used in the tree are present in the dataset
204      foreach (var variable in tree.IterateNodesPrefix().OfType<VariableTreeNode>().Select(n => n.VariableName).Distinct())
205        if (!variableRanges.ContainsKey(variable))
206          throw new InvalidOperationException($"No ranges for variable {variable} is present");
207
208      var code = SymbolicExpressionTreeCompiler.Compile(tree, OpCodes.MapSymbolToOpCode);
209      foreach (var instr in code.Where(i => i.opCode == OpCodes.Variable)) {
210        var variableTreeNode = (VariableTreeNode) instr.dynamicNode;
211        instr.data = variableRanges[variableTreeNode.VariableName];
212      }
213
214      return code;
215    }
216
217
218
219    public static Interval EvaluateRecursive(
220      Instruction[] instructions,
221      IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals,
222      IDictionary<string, Interval> variableIntervals, IList<string> variables,
223      double minWidth, int maxDepth, ref int currIndex, ref int currDepth,
224      ISymbolicExpressionTree tree) {
225      Interval evaluate() {
226        var ic = 0;
227        IReadOnlyDictionary<string, Interval> readonlyRanges = new ReadOnlyDictionary<string, Interval>(variableIntervals);
228        return Evaluate(instructions, ref ic, nodeIntervals, readonlyRanges);
229      }
230
231      Interval recurse(ref int idx, ref int depth) {
232        return EvaluateRecursive(instructions, nodeIntervals, variableIntervals, variables, minWidth, maxDepth, ref idx,
233          ref depth, tree);
234      }
235
236
237      var v = variables[currIndex];
238      var x = variableIntervals[v];
239      if (x.Width < minWidth || currDepth == maxDepth || !MultipleTimes(tree, v)) {
240        if (currIndex + 1 < variables.Count) {
241          currDepth = 0;
242          currIndex++;
243          var z = recurse(ref currIndex, ref currDepth);
244          currIndex--;
245          return z;
246        }
247
248        return evaluate();
249      }
250
251      var t  = x.Split();
252      var xa = t.Item1;
253      var xb = t.Item2;
254      var d  = currDepth;
255      currDepth            = d + 1;
256      variableIntervals[v] = xa;
257      var ya = recurse(ref currIndex, ref currDepth);
258      currDepth            = d + 1;
259      variableIntervals[v] = xb;
260      var yb = recurse(ref currIndex, ref currDepth);
261      variableIntervals[v] = x; // restore interval
262      return ya | yb;
263    }
264
265    public static Interval Evaluate(
266      Instruction[] instructions, ref int instructionCounter,
267      IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals = null,
268      IReadOnlyDictionary<string, Interval> variableIntervals = null) {
269      var currentInstr = instructions[instructionCounter];
270      //Use ref parameter, because the tree will be iterated through recursively from the left-side branch to the right side
271      //Update instructionCounter, whenever Evaluate is called
272      instructionCounter++;
273      Interval result = null;
274
275      switch (currentInstr.opCode) {
276        //Variables, Constants, ...
277        case OpCodes.Variable: {
278          var variableTreeNode = (VariableTreeNode) currentInstr.dynamicNode;
279          var weightInterval   = new Interval(variableTreeNode.Weight, variableTreeNode.Weight);
280          //var variableInterval = (Interval)currentInstr.data;
281
282          Interval variableInterval;
283          if (variableIntervals != null && variableIntervals.ContainsKey(variableTreeNode.VariableName))
284            variableInterval = variableIntervals[variableTreeNode.VariableName];
285          else
286            variableInterval = (Interval) currentInstr.data;
287
288          result = Interval.Multiply(variableInterval, weightInterval);
289          break;
290        }
291        case OpCodes.Constant: {
292          var constTreeNode = (ConstantTreeNode) currentInstr.dynamicNode;
293          result = new Interval(constTreeNode.Value, constTreeNode.Value);
294          break;
295        }
296        //Elementary arithmetic rules
297        case OpCodes.Add: {
298          //result = Evaluate(instructions, ref instructionCounter, nodeIntervals);
299          result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
300          for (var i = 1; i < currentInstr.nArguments; i++) {
301            //var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals);
302            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
303            result = Interval.Add(result, argumentInterval);
304          }
305
306          break;
307        }
308        case OpCodes.Sub: {
309          //result = Evaluate(instructions, ref instructionCounter, nodeIntervals);
310          result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
311          if (currentInstr.nArguments == 1)
312            result = Interval.Multiply(new Interval(-1, -1), result);
313
314          for (var i = 1; i < currentInstr.nArguments; i++) {
315            //var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals);
316            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
317            result = Interval.Subtract(result, argumentInterval);
318          }
319
320          break;
321        }
322        case OpCodes.Mul: {
323          //result = Evaluate(instructions, ref instructionCounter, nodeIntervals);
324          result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
325          for (var i = 1; i < currentInstr.nArguments; i++) {
326            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
327            //var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals);
328            result = Interval.Multiply(result, argumentInterval);
329          }
330
331          break;
332        }
333        case OpCodes.Div: {
334          //result = Evaluate(instructions, ref instructionCounter, nodeIntervals);
335          result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
336          if (currentInstr.nArguments == 1)
337            result = Interval.Divide(new Interval(1, 1), result);
338
339          for (var i = 1; i < currentInstr.nArguments; i++) {
340            //var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals);
341            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
342            result = Interval.Divide(result, argumentInterval);
343          }
344
345          break;
346        }
347        //Trigonometric functions
348        case OpCodes.Sin: {
349          //var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals);
350          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
351          result = Interval.Sine(argumentInterval);
352          break;
353        }
354        case OpCodes.Cos: {
355          //var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals);
356          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
357          result = Interval.Cosine(argumentInterval);
358          break;
359        }
360        case OpCodes.Tan: {
361          //var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals);
362          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
363          result = Interval.Tangens(argumentInterval);
364          break;
365        }
366        case OpCodes.Tanh: {
367          //var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals);
368          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
369          result = Interval.HyperbolicTangent(argumentInterval);
370          break;
371        }
372        //Exponential functions
373        case OpCodes.Log: {
374          //var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals);
375          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
376          result = Interval.Logarithm(argumentInterval);
377          break;
378        }
379        case OpCodes.Exp: {
380          //var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals);
381          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
382          result = Interval.Exponential(argumentInterval);
383          break;
384        }
385        case OpCodes.Square: {
386          //var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals);
387          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
388          result = Interval.Square(argumentInterval);
389          break;
390        }
391        case OpCodes.SquareRoot: {
392          //var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals);
393          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
394          result = Interval.SquareRoot(argumentInterval);
395          break;
396        }
397        case OpCodes.Cube: {
398          //var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals);
399          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
400          result = Interval.Cube(argumentInterval);
401          break;
402        }
403        case OpCodes.CubeRoot: {
404          //var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals);
405          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
406          result = Interval.CubicRoot(argumentInterval);
407          break;
408        }
409        case OpCodes.Absolute: {
410          //var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals);
411          var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
412          result = Interval.Absolute(argumentInterval);
413          break;
414        }
415        case OpCodes.AnalyticQuotient: {
416          //result = Evaluate(instructions, ref instructionCounter, nodeIntervals);
417          result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
418          for (var i = 1; i < currentInstr.nArguments; i++) {
419            //var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals);
420            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
421            result = Interval.AnalyticalQuotient(result, argumentInterval);
422          }
423
424          break;
425        }
426        default:
427          throw new NotSupportedException($"The tree contains the unknown symbol {currentInstr.dynamicNode.Symbol}");
428      }
429
430      if (!(nodeIntervals == null || nodeIntervals.ContainsKey(currentInstr.dynamicNode)))
431        nodeIntervals.Add(currentInstr.dynamicNode, result);
432
433      return result;
434    }
435
436    private static bool MultipleTimes(ISymbolicExpressionTree tree, string variable) {
437      var varlist = tree.IterateNodesPrefix().OfType<VariableTreeNode>().GroupBy(x => x.VariableName);
438      var group   = varlist.Select(x => x.Key == variable).Count();
439
440      return group > 1;
441    }
442
443    private static bool ContainsVariableMultipleTimes(ISymbolicExpressionTree tree) {
444      var varlist = tree.IterateNodesPrefix().OfType<VariableTreeNode>().GroupBy(x => x.VariableName);
445      return varlist.Any(@group => @group.Count() > 1);
446    }
447
448
449    public static bool IsCompatible(ISymbolicExpressionTree tree) {
450      var containsUnknownSymbols = (
451        from n in tree.Root.GetSubtree(0).IterateNodesPrefix()
452        where
453          !(n.Symbol is Variable) &&
454          !(n.Symbol is Constant) &&
455          !(n.Symbol is StartSymbol) &&
456          !(n.Symbol is Addition) &&
457          !(n.Symbol is Subtraction) &&
458          !(n.Symbol is Multiplication) &&
459          !(n.Symbol is Division) &&
460          !(n.Symbol is Sine) &&
461          !(n.Symbol is Cosine) &&
462          !(n.Symbol is Tangent) &&
463          !(n.Symbol is Logarithm) &&
464          !(n.Symbol is Exponential) &&
465          !(n.Symbol is Square) &&
466          !(n.Symbol is SquareRoot) &&
467          !(n.Symbol is Cube) &&
468          !(n.Symbol is CubeRoot) &&
469          !(n.Symbol is Absolute) &&
470          !(n.Symbol is AnalyticQuotient)
471        select n).Any();
472      return !containsUnknownSymbols;
473    }
474  }
475}
Note: See TracBrowser for help on using the repository browser.