Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeLinearInterpreter.cs @ 16762

Last change on this file since 16762 was 16656, checked in by gkronber, 5 years ago

#2866: merged r16375, r16531, r16655 from branch to trunk (using "Merge two different trees" because I was not able to automatically merge changesets)
File size: 22.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2019 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 HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
29using HeuristicLab.Parameters;
30using HEAL.Attic;
31
32namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
33  [StorableType("EF325166-E03A-44C4-83CE-7F07B836285E")]
34  [Item("SymbolicDataAnalysisExpressionTreeLinearInterpreter", "Fast linear (non-recursive) interpreter for symbolic expression trees. Does not support ADFs.")]
35  public sealed class SymbolicDataAnalysisExpressionTreeLinearInterpreter : ParameterizedNamedItem, ISymbolicDataAnalysisExpressionTreeInterpreter {
36    private const string CheckExpressionsWithIntervalArithmeticParameterName = "CheckExpressionsWithIntervalArithmetic";
37    private const string CheckExpressionsWithIntervalArithmeticParameterDescription = "Switch that determines if the interpreter checks the validity of expressions with interval arithmetic before evaluating the expression.";
38    private const string EvaluatedSolutionsParameterName = "EvaluatedSolutions";
39
40    private readonly SymbolicDataAnalysisExpressionTreeInterpreter interpreter;
41
42    public override bool CanChangeName {
43      get { return false; }
44    }
45
46    public override bool CanChangeDescription {
47      get { return false; }
48    }
49
50    #region parameter properties
51    public IFixedValueParameter<BoolValue> CheckExpressionsWithIntervalArithmeticParameter {
52      get { return (IFixedValueParameter<BoolValue>)Parameters[CheckExpressionsWithIntervalArithmeticParameterName]; }
53    }
54
55    public IFixedValueParameter<IntValue> EvaluatedSolutionsParameter {
56      get { return (IFixedValueParameter<IntValue>)Parameters[EvaluatedSolutionsParameterName]; }
57    }
58    #endregion
59
60    #region properties
61    public bool CheckExpressionsWithIntervalArithmetic {
62      get { return CheckExpressionsWithIntervalArithmeticParameter.Value.Value; }
63      set { CheckExpressionsWithIntervalArithmeticParameter.Value.Value = value; }
64    }
65    public int EvaluatedSolutions {
66      get { return EvaluatedSolutionsParameter.Value.Value; }
67      set { EvaluatedSolutionsParameter.Value.Value = value; }
68    }
69    #endregion
70
71    [StorableConstructor]
72    private SymbolicDataAnalysisExpressionTreeLinearInterpreter(StorableConstructorFlag _) : base(_) {
73      interpreter = new SymbolicDataAnalysisExpressionTreeInterpreter();
74    }
75
76    private SymbolicDataAnalysisExpressionTreeLinearInterpreter(SymbolicDataAnalysisExpressionTreeLinearInterpreter original, Cloner cloner)
77      : base(original, cloner) {
78      interpreter = cloner.Clone(original.interpreter);
79    }
80
81    public override IDeepCloneable Clone(Cloner cloner) {
82      return new SymbolicDataAnalysisExpressionTreeLinearInterpreter(this, cloner);
83    }
84
85    public SymbolicDataAnalysisExpressionTreeLinearInterpreter()
86      : base("SymbolicDataAnalysisExpressionTreeLinearInterpreter", "Linear (non-recursive) interpreter for symbolic expression trees (does not support ADFs).") {
87      Parameters.Add(new FixedValueParameter<BoolValue>(CheckExpressionsWithIntervalArithmeticParameterName, CheckExpressionsWithIntervalArithmeticParameterDescription, new BoolValue(false)));
88      Parameters.Add(new FixedValueParameter<IntValue>(EvaluatedSolutionsParameterName, "A counter for the total number of solutions the interpreter has evaluated", new IntValue(0)));
89      interpreter = new SymbolicDataAnalysisExpressionTreeInterpreter();
90    }
91
92    public SymbolicDataAnalysisExpressionTreeLinearInterpreter(string name, string description)
93      : base(name, description) {
94      Parameters.Add(new FixedValueParameter<BoolValue>(CheckExpressionsWithIntervalArithmeticParameterName, CheckExpressionsWithIntervalArithmeticParameterDescription, new BoolValue(false)));
95      Parameters.Add(new FixedValueParameter<IntValue>(EvaluatedSolutionsParameterName, "A counter for the total number of solutions the interpreter has evaluated", new IntValue(0)));
96      interpreter = new SymbolicDataAnalysisExpressionTreeInterpreter();
97    }
98
99    [StorableHook(HookType.AfterDeserialization)]
100    private void AfterDeserialization() {
101      var evaluatedSolutions = new IntValue(0);
102      var checkExpressionsWithIntervalArithmetic = new BoolValue(false);
103      if (Parameters.ContainsKey(EvaluatedSolutionsParameterName)) {
104        var evaluatedSolutionsParameter = (IValueParameter<IntValue>)Parameters[EvaluatedSolutionsParameterName];
105        evaluatedSolutions = evaluatedSolutionsParameter.Value;
106        Parameters.Remove(EvaluatedSolutionsParameterName);
107      }
108      Parameters.Add(new FixedValueParameter<IntValue>(EvaluatedSolutionsParameterName, "A counter for the total number of solutions the interpreter has evaluated", evaluatedSolutions));
109      if (Parameters.ContainsKey(CheckExpressionsWithIntervalArithmeticParameterName)) {
110        var checkExpressionsWithIntervalArithmeticParameter = (IValueParameter<BoolValue>)Parameters[CheckExpressionsWithIntervalArithmeticParameterName];
111        Parameters.Remove(CheckExpressionsWithIntervalArithmeticParameterName);
112        checkExpressionsWithIntervalArithmetic = checkExpressionsWithIntervalArithmeticParameter.Value;
113      }
114      Parameters.Add(new FixedValueParameter<BoolValue>(CheckExpressionsWithIntervalArithmeticParameterName, CheckExpressionsWithIntervalArithmeticParameterDescription, checkExpressionsWithIntervalArithmetic));
115    }
116
117    #region IStatefulItem
118    public void InitializeState() {
119      EvaluatedSolutions = 0;
120    }
121
122    public void ClearState() { }
123    #endregion
124
125    private readonly object syncRoot = new object();
126    public IEnumerable<double> GetSymbolicExpressionTreeValues(ISymbolicExpressionTree tree, IDataset dataset, IEnumerable<int> rows) {
127      if (!rows.Any()) return Enumerable.Empty<double>();
128      if (CheckExpressionsWithIntervalArithmetic)
129        throw new NotSupportedException("Interval arithmetic is not yet supported in the symbolic data analysis interpreter.");
130
131      lock (syncRoot) {
132        EvaluatedSolutions++; // increment the evaluated solutions counter
133      }
134
135      var code = SymbolicExpressionTreeLinearCompiler.Compile(tree, OpCodes.MapSymbolToOpCode);
136      PrepareInstructions(code, dataset);
137      return rows.Select(row => Evaluate(dataset, row, code));
138    }
139
140    private double Evaluate(IDataset dataset, int row, LinearInstruction[] code) {
141      for (int i = code.Length - 1; i >= 0; --i) {
142        if (code[i].skip) continue;
143        #region opcode if
144        var instr = code[i];
145        if (instr.opCode == OpCodes.Variable) {
146          if (row < 0 || row >= dataset.Rows) instr.value = double.NaN;
147          else {
148            var variableTreeNode = (VariableTreeNode)instr.dynamicNode;
149            instr.value = ((IList<double>)instr.data)[row] * variableTreeNode.Weight;
150          }
151        } else if (instr.opCode == OpCodes.BinaryFactorVariable) {
152          if (row < 0 || row >= dataset.Rows) instr.value = double.NaN;
153          else {
154            var factorTreeNode = instr.dynamicNode as BinaryFactorVariableTreeNode;
155            instr.value = ((IList<string>)instr.data)[row] == factorTreeNode.VariableValue ? factorTreeNode.Weight : 0;
156          }
157        } else if (instr.opCode == OpCodes.FactorVariable) {
158          if (row < 0 || row >= dataset.Rows) instr.value = double.NaN;
159          else {
160            var factorTreeNode = instr.dynamicNode as FactorVariableTreeNode;
161            instr.value = factorTreeNode.GetValue(((IList<string>)instr.data)[row]);
162          }
163        } else if (instr.opCode == OpCodes.LagVariable) {
164          var laggedVariableTreeNode = (LaggedVariableTreeNode)instr.dynamicNode;
165          int actualRow = row + laggedVariableTreeNode.Lag;
166          if (actualRow < 0 || actualRow >= dataset.Rows)
167            instr.value = double.NaN;
168          else
169            instr.value = ((IList<double>)instr.data)[actualRow] * laggedVariableTreeNode.Weight;
170        } else if (instr.opCode == OpCodes.VariableCondition) {
171          if (row < 0 || row >= dataset.Rows) instr.value = double.NaN;
172          var variableConditionTreeNode = (VariableConditionTreeNode)instr.dynamicNode;
173          if (!variableConditionTreeNode.Symbol.IgnoreSlope) {
174            double variableValue = ((IList<double>)instr.data)[row];
175            double x = variableValue - variableConditionTreeNode.Threshold;
176            double p = 1 / (1 + Math.Exp(-variableConditionTreeNode.Slope * x));
177
178            double trueBranch = code[instr.childIndex].value;
179            double falseBranch = code[instr.childIndex + 1].value;
180
181            instr.value = trueBranch * p + falseBranch * (1 - p);
182          } else {
183            double variableValue = ((IList<double>)instr.data)[row];
184            if (variableValue <= variableConditionTreeNode.Threshold) {
185              instr.value = code[instr.childIndex].value;
186            } else {
187              instr.value = code[instr.childIndex + 1].value;
188            }
189          }
190        } else if (instr.opCode == OpCodes.Add) {
191          double s = code[instr.childIndex].value;
192          for (int j = 1; j != instr.nArguments; ++j) {
193            s += code[instr.childIndex + j].value;
194          }
195          instr.value = s;
196        } else if (instr.opCode == OpCodes.Sub) {
197          double s = code[instr.childIndex].value;
198          for (int j = 1; j != instr.nArguments; ++j) {
199            s -= code[instr.childIndex + j].value;
200          }
201          if (instr.nArguments == 1) s = -s;
202          instr.value = s;
203        } else if (instr.opCode == OpCodes.Mul) {
204          double p = code[instr.childIndex].value;
205          for (int j = 1; j != instr.nArguments; ++j) {
206            p *= code[instr.childIndex + j].value;
207          }
208          instr.value = p;
209        } else if (instr.opCode == OpCodes.Div) {
210          double p = code[instr.childIndex].value;
211          for (int j = 1; j != instr.nArguments; ++j) {
212            p /= code[instr.childIndex + j].value;
213          }
214          if (instr.nArguments == 1) p = 1.0 / p;
215          instr.value = p;
216        } else if (instr.opCode == OpCodes.AnalyticQuotient) {
217          var x1 = code[instr.childIndex].value;
218          var x2 = code[instr.childIndex + 1].value;
219          instr.value = x1 / Math.Sqrt(1 + x2 * x2);
220        } else if (instr.opCode == OpCodes.Average) {
221          double s = code[instr.childIndex].value;
222          for (int j = 1; j != instr.nArguments; ++j) {
223            s += code[instr.childIndex + j].value;
224          }
225          instr.value = s / instr.nArguments;
226        } else if (instr.opCode == OpCodes.Absolute) {
227          instr.value = Math.Abs(code[instr.childIndex].value);
228        } else if (instr.opCode == OpCodes.Tanh) {
229          instr.value = Math.Tanh(code[instr.childIndex].value);
230        } else if (instr.opCode == OpCodes.Cos) {
231          instr.value = Math.Cos(code[instr.childIndex].value);
232        } else if (instr.opCode == OpCodes.Sin) {
233          instr.value = Math.Sin(code[instr.childIndex].value);
234        } else if (instr.opCode == OpCodes.Tan) {
235          instr.value = Math.Tan(code[instr.childIndex].value);
236        } else if (instr.opCode == OpCodes.Square) {
237          instr.value = Math.Pow(code[instr.childIndex].value, 2);
238        } else if (instr.opCode == OpCodes.Cube) {
239          instr.value = Math.Pow(code[instr.childIndex].value, 3);
240        } else if (instr.opCode == OpCodes.Power) {
241          double x = code[instr.childIndex].value;
242          double y = Math.Round(code[instr.childIndex + 1].value);
243          instr.value = Math.Pow(x, y);
244        } else if (instr.opCode == OpCodes.SquareRoot) {
245          instr.value = Math.Sqrt(code[instr.childIndex].value);
246        } else if (instr.opCode == OpCodes.CubeRoot) {
247          instr.value = Math.Pow(code[instr.childIndex].value, 1.0 / 3.0);
248        } else if (instr.opCode == OpCodes.Root) {
249          double x = code[instr.childIndex].value;
250          double y = Math.Round(code[instr.childIndex + 1].value);
251          instr.value = Math.Pow(x, 1 / y);
252        } else if (instr.opCode == OpCodes.Exp) {
253          instr.value = Math.Exp(code[instr.childIndex].value);
254        } else if (instr.opCode == OpCodes.Log) {
255          instr.value = Math.Log(code[instr.childIndex].value);
256        } else if (instr.opCode == OpCodes.Gamma) {
257          var x = code[instr.childIndex].value;
258          instr.value = double.IsNaN(x) ? double.NaN : alglib.gammafunction(x);
259        } else if (instr.opCode == OpCodes.Psi) {
260          var x = code[instr.childIndex].value;
261          if (double.IsNaN(x)) instr.value = double.NaN;
262          else if (x <= 0 && (Math.Floor(x) - x).IsAlmost(0)) instr.value = double.NaN;
263          else instr.value = alglib.psi(x);
264        } else if (instr.opCode == OpCodes.Dawson) {
265          var x = code[instr.childIndex].value;
266          instr.value = double.IsNaN(x) ? double.NaN : alglib.dawsonintegral(x);
267        } else if (instr.opCode == OpCodes.ExponentialIntegralEi) {
268          var x = code[instr.childIndex].value;
269          instr.value = double.IsNaN(x) ? double.NaN : alglib.exponentialintegralei(x);
270        } else if (instr.opCode == OpCodes.SineIntegral) {
271          double si, ci;
272          var x = code[instr.childIndex].value;
273          if (double.IsNaN(x)) instr.value = double.NaN;
274          else {
275            alglib.sinecosineintegrals(x, out si, out ci);
276            instr.value = si;
277          }
278        } else if (instr.opCode == OpCodes.CosineIntegral) {
279          double si, ci;
280          var x = code[instr.childIndex].value;
281          if (double.IsNaN(x)) instr.value = double.NaN;
282          else {
283            alglib.sinecosineintegrals(x, out si, out ci);
284            instr.value = ci;
285          }
286        } else if (instr.opCode == OpCodes.HyperbolicSineIntegral) {
287          double shi, chi;
288          var x = code[instr.childIndex].value;
289          if (double.IsNaN(x)) instr.value = double.NaN;
290          else {
291            alglib.hyperbolicsinecosineintegrals(x, out shi, out chi);
292            instr.value = shi;
293          }
294        } else if (instr.opCode == OpCodes.HyperbolicCosineIntegral) {
295          double shi, chi;
296          var x = code[instr.childIndex].value;
297          if (double.IsNaN(x)) instr.value = double.NaN;
298          else {
299            alglib.hyperbolicsinecosineintegrals(x, out shi, out chi);
300            instr.value = chi;
301          }
302        } else if (instr.opCode == OpCodes.FresnelCosineIntegral) {
303          double c = 0, s = 0;
304          var x = code[instr.childIndex].value;
305          if (double.IsNaN(x)) instr.value = double.NaN;
306          else {
307            alglib.fresnelintegral(x, ref c, ref s);
308            instr.value = c;
309          }
310        } else if (instr.opCode == OpCodes.FresnelSineIntegral) {
311          double c = 0, s = 0;
312          var x = code[instr.childIndex].value;
313          if (double.IsNaN(x)) instr.value = double.NaN;
314          else {
315            alglib.fresnelintegral(x, ref c, ref s);
316            instr.value = s;
317          }
318        } else if (instr.opCode == OpCodes.AiryA) {
319          double ai, aip, bi, bip;
320          var x = code[instr.childIndex].value;
321          if (double.IsNaN(x)) instr.value = double.NaN;
322          else {
323            alglib.airy(x, out ai, out aip, out bi, out bip);
324            instr.value = ai;
325          }
326        } else if (instr.opCode == OpCodes.AiryB) {
327          double ai, aip, bi, bip;
328          var x = code[instr.childIndex].value;
329          if (double.IsNaN(x)) instr.value = double.NaN;
330          else {
331            alglib.airy(x, out ai, out aip, out bi, out bip);
332            instr.value = bi;
333          }
334        } else if (instr.opCode == OpCodes.Norm) {
335          var x = code[instr.childIndex].value;
336          if (double.IsNaN(x)) instr.value = double.NaN;
337          else instr.value = alglib.normaldistribution(x);
338        } else if (instr.opCode == OpCodes.Erf) {
339          var x = code[instr.childIndex].value;
340          if (double.IsNaN(x)) instr.value = double.NaN;
341          else instr.value = alglib.errorfunction(x);
342        } else if (instr.opCode == OpCodes.Bessel) {
343          var x = code[instr.childIndex].value;
344          if (double.IsNaN(x)) instr.value = double.NaN;
345          else instr.value = alglib.besseli0(x);
346        } else if (instr.opCode == OpCodes.IfThenElse) {
347          double condition = code[instr.childIndex].value;
348          double result;
349          if (condition > 0.0) {
350            result = code[instr.childIndex + 1].value;
351          } else {
352            result = code[instr.childIndex + 2].value;
353          }
354          instr.value = result;
355        } else if (instr.opCode == OpCodes.AND) {
356          double result = code[instr.childIndex].value;
357          for (int j = 1; j < instr.nArguments; j++) {
358            if (result > 0.0) result = code[instr.childIndex + j].value;
359            else break;
360          }
361          instr.value = result > 0.0 ? 1.0 : -1.0;
362        } else if (instr.opCode == OpCodes.OR) {
363          double result = code[instr.childIndex].value;
364          for (int j = 1; j < instr.nArguments; j++) {
365            if (result <= 0.0) result = code[instr.childIndex + j].value;
366            else break;
367          }
368          instr.value = result > 0.0 ? 1.0 : -1.0;
369        } else if (instr.opCode == OpCodes.NOT) {
370          instr.value = code[instr.childIndex].value > 0.0 ? -1.0 : 1.0;
371        } else if (instr.opCode == OpCodes.XOR) {
372          int positiveSignals = 0;
373          for (int j = 0; j < instr.nArguments; j++) {
374            if (code[instr.childIndex + j].value > 0.0) positiveSignals++;
375          }
376          instr.value = positiveSignals % 2 != 0 ? 1.0 : -1.0;
377        } else if (instr.opCode == OpCodes.GT) {
378          double x = code[instr.childIndex].value;
379          double y = code[instr.childIndex + 1].value;
380          instr.value = x > y ? 1.0 : -1.0;
381        } else if (instr.opCode == OpCodes.LT) {
382          double x = code[instr.childIndex].value;
383          double y = code[instr.childIndex + 1].value;
384          instr.value = x < y ? 1.0 : -1.0;
385        } else if (instr.opCode == OpCodes.TimeLag || instr.opCode == OpCodes.Derivative || instr.opCode == OpCodes.Integral) {
386          var state = (InterpreterState)instr.data;
387          state.Reset();
388          instr.value = interpreter.Evaluate(dataset, ref row, state);
389        } else {
390          var errorText = string.Format("The {0} symbol is not supported by the linear interpreter. To support this symbol, please use the SymbolicDataAnalysisExpressionTreeInterpreter.", instr.dynamicNode.Symbol.Name);
391          throw new NotSupportedException(errorText);
392        }
393        #endregion
394      }
395      return code[0].value;
396    }
397
398    private static LinearInstruction[] GetPrefixSequence(LinearInstruction[] code, int startIndex) {
399      var s = new Stack<int>();
400      var list = new List<LinearInstruction>();
401      s.Push(startIndex);
402      while (s.Any()) {
403        int i = s.Pop();
404        var instr = code[i];
405        // push instructions in reverse execution order
406        for (int j = instr.nArguments - 1; j >= 0; j--) s.Push(instr.childIndex + j);
407        list.Add(instr);
408      }
409      return list.ToArray();
410    }
411
412    public static void PrepareInstructions(LinearInstruction[] code, IDataset dataset) {
413      for (int i = 0; i != code.Length; ++i) {
414        var instr = code[i];
415        #region opcode switch
416        switch (instr.opCode) {
417          case OpCodes.Constant: {
418              var constTreeNode = (ConstantTreeNode)instr.dynamicNode;
419              instr.value = constTreeNode.Value;
420              instr.skip = true; // the value is already set so this instruction should be skipped in the evaluation phase
421            }
422            break;
423          case OpCodes.Variable: {
424              var variableTreeNode = (VariableTreeNode)instr.dynamicNode;
425              instr.data = dataset.GetReadOnlyDoubleValues(variableTreeNode.VariableName);
426            }
427            break;
428          case OpCodes.BinaryFactorVariable: {
429              var factorVariableTreeNode = instr.dynamicNode as BinaryFactorVariableTreeNode;
430              instr.data = dataset.GetReadOnlyStringValues(factorVariableTreeNode.VariableName);
431            }
432            break;
433          case OpCodes.FactorVariable: {
434              var factorVariableTreeNode = instr.dynamicNode as FactorVariableTreeNode;
435              instr.data = dataset.GetReadOnlyStringValues(factorVariableTreeNode.VariableName);
436            }
437            break;
438          case OpCodes.LagVariable: {
439              var laggedVariableTreeNode = (LaggedVariableTreeNode)instr.dynamicNode;
440              instr.data = dataset.GetReadOnlyDoubleValues(laggedVariableTreeNode.VariableName);
441            }
442            break;
443          case OpCodes.VariableCondition: {
444              var variableConditionTreeNode = (VariableConditionTreeNode)instr.dynamicNode;
445              instr.data = dataset.GetReadOnlyDoubleValues(variableConditionTreeNode.VariableName);
446            }
447            break;
448          case OpCodes.TimeLag:
449          case OpCodes.Integral:
450          case OpCodes.Derivative: {
451              var seq = GetPrefixSequence(code, i);
452              var interpreterState = new InterpreterState(seq, 0);
453              instr.data = interpreterState;
454              for (int j = 1; j != seq.Length; ++j)
455                seq[j].skip = true;
456              break;
457            }
458        }
459        #endregion
460      }
461    }
462  }
463}
Note: See TracBrowser for help on using the repository browser.