source: trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeInterpreter.cs @ 13248

Last change on this file since 13248 was 13248, checked in by mkommend, 4 years ago

#2442: Reintegrated branch for compiled symbolic expression tree interpreter.

File size: 21.4 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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 HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30
31namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
32  [StorableClass]
33  [Item("SymbolicDataAnalysisExpressionTreeInterpreter", "Interpreter for symbolic expression trees including automatically defined functions.")]
34  public class SymbolicDataAnalysisExpressionTreeInterpreter : ParameterizedNamedItem,
35    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    public override bool CanChangeName {
41      get { return false; }
42    }
43
44    public override bool CanChangeDescription {
45      get { return false; }
46    }
47
48    #region parameter properties
49    public IFixedValueParameter<BoolValue> CheckExpressionsWithIntervalArithmeticParameter {
50      get { return (IFixedValueParameter<BoolValue>)Parameters[CheckExpressionsWithIntervalArithmeticParameterName]; }
51    }
52
53    public IFixedValueParameter<IntValue> EvaluatedSolutionsParameter {
54      get { return (IFixedValueParameter<IntValue>)Parameters[EvaluatedSolutionsParameterName]; }
55    }
56    #endregion
57
58    #region properties
59    public bool CheckExpressionsWithIntervalArithmetic {
60      get { return CheckExpressionsWithIntervalArithmeticParameter.Value.Value; }
61      set { CheckExpressionsWithIntervalArithmeticParameter.Value.Value = value; }
62    }
63
64    public int EvaluatedSolutions {
65      get { return EvaluatedSolutionsParameter.Value.Value; }
66      set { EvaluatedSolutionsParameter.Value.Value = value; }
67    }
68    #endregion
69
70    [StorableConstructor]
71    protected SymbolicDataAnalysisExpressionTreeInterpreter(bool deserializing) : base(deserializing) { }
72
73    protected SymbolicDataAnalysisExpressionTreeInterpreter(SymbolicDataAnalysisExpressionTreeInterpreter original,
74      Cloner cloner) : base(original, cloner) { }
75
76    public override IDeepCloneable Clone(Cloner cloner) {
77      return new SymbolicDataAnalysisExpressionTreeInterpreter(this, cloner);
78    }
79
80    public SymbolicDataAnalysisExpressionTreeInterpreter()
81      : base("SymbolicDataAnalysisExpressionTreeInterpreter", "Interpreter for symbolic expression trees including automatically defined functions.") {
82      Parameters.Add(new FixedValueParameter<BoolValue>(CheckExpressionsWithIntervalArithmeticParameterName, "Switch that determines if the interpreter checks the validity of expressions with interval arithmetic before evaluating the expression.", new BoolValue(false)));
83      Parameters.Add(new FixedValueParameter<IntValue>(EvaluatedSolutionsParameterName, "A counter for the total number of solutions the interpreter has evaluated", new IntValue(0)));
84    }
85
86    protected SymbolicDataAnalysisExpressionTreeInterpreter(string name, string description)
87      : base(name, description) {
88      Parameters.Add(new FixedValueParameter<BoolValue>(CheckExpressionsWithIntervalArithmeticParameterName, "Switch that determines if the interpreter checks the validity of expressions with interval arithmetic before evaluating the expression.", new BoolValue(false)));
89      Parameters.Add(new FixedValueParameter<IntValue>(EvaluatedSolutionsParameterName, "A counter for the total number of solutions the interpreter has evaluated", new IntValue(0)));
90    }
91
92    [StorableHook(HookType.AfterDeserialization)]
93    private void AfterDeserialization() {
94      var evaluatedSolutions = new IntValue(0);
95      var checkExpressionsWithIntervalArithmetic = new BoolValue(false);
96      if (Parameters.ContainsKey(EvaluatedSolutionsParameterName)) {
97        var evaluatedSolutionsParameter = (IValueParameter<IntValue>)Parameters[EvaluatedSolutionsParameterName];
98        evaluatedSolutions = evaluatedSolutionsParameter.Value;
99        Parameters.Remove(EvaluatedSolutionsParameterName);
100      }
101      Parameters.Add(new FixedValueParameter<IntValue>(EvaluatedSolutionsParameterName, "A counter for the total number of solutions the interpreter has evaluated", evaluatedSolutions));
102      if (Parameters.ContainsKey(CheckExpressionsWithIntervalArithmeticParameterName)) {
103        var checkExpressionsWithIntervalArithmeticParameter = (IValueParameter<BoolValue>)Parameters[CheckExpressionsWithIntervalArithmeticParameterName];
104        Parameters.Remove(CheckExpressionsWithIntervalArithmeticParameterName);
105        checkExpressionsWithIntervalArithmetic = checkExpressionsWithIntervalArithmeticParameter.Value;
106      }
107      Parameters.Add(new FixedValueParameter<BoolValue>(CheckExpressionsWithIntervalArithmeticParameterName, CheckExpressionsWithIntervalArithmeticParameterDescription, checkExpressionsWithIntervalArithmetic));
108    }
109
110    #region IStatefulItem
111    public void InitializeState() {
112      EvaluatedSolutions = 0;
113    }
114
115    public void ClearState() { }
116    #endregion
117
118    public IEnumerable<double> GetSymbolicExpressionTreeValues(ISymbolicExpressionTree tree, IDataset dataset,
119      IEnumerable<int> rows) {
120      if (CheckExpressionsWithIntervalArithmetic) {
121        throw new NotSupportedException("Interval arithmetic is not yet supported in the symbolic data analysis interpreter.");
122      }
123
124      lock (EvaluatedSolutionsParameter.Value) {
125        EvaluatedSolutions++; // increment the evaluated solutions counter
126      }
127      var state = PrepareInterpreterState(tree, dataset);
128
129      foreach (var rowEnum in rows) {
130        int row = rowEnum;
131        yield return Evaluate(dataset, ref row, state);
132        state.Reset();
133      }
134    }
135
136    private static InterpreterState PrepareInterpreterState(ISymbolicExpressionTree tree, IDataset dataset) {
137      Instruction[] code = SymbolicExpressionTreeCompiler.Compile(tree, OpCodes.MapSymbolToOpCode);
138      int necessaryArgStackSize = 0;
139      foreach (Instruction instr in code) {
140        if (instr.opCode == OpCodes.Variable) {
141          var variableTreeNode = (VariableTreeNode)instr.dynamicNode;
142          instr.data = dataset.GetReadOnlyDoubleValues(variableTreeNode.VariableName);
143        } else if (instr.opCode == OpCodes.LagVariable) {
144          var laggedVariableTreeNode = (LaggedVariableTreeNode)instr.dynamicNode;
145          instr.data = dataset.GetReadOnlyDoubleValues(laggedVariableTreeNode.VariableName);
146        } else if (instr.opCode == OpCodes.VariableCondition) {
147          var variableConditionTreeNode = (VariableConditionTreeNode)instr.dynamicNode;
148          instr.data = dataset.GetReadOnlyDoubleValues(variableConditionTreeNode.VariableName);
149        } else if (instr.opCode == OpCodes.Call) {
150          necessaryArgStackSize += instr.nArguments + 1;
151        }
152      }
153      return new InterpreterState(code, necessaryArgStackSize);
154    }
155
156    public virtual double Evaluate(IDataset dataset, ref int row, InterpreterState state) {
157      Instruction currentInstr = state.NextInstruction();
158      switch (currentInstr.opCode) {
159        case OpCodes.Add: {
160            double s = Evaluate(dataset, ref row, state);
161            for (int i = 1; i < currentInstr.nArguments; i++) {
162              s += Evaluate(dataset, ref row, state);
163            }
164            return s;
165          }
166        case OpCodes.Sub: {
167            double s = Evaluate(dataset, ref row, state);
168            for (int i = 1; i < currentInstr.nArguments; i++) {
169              s -= Evaluate(dataset, ref row, state);
170            }
171            if (currentInstr.nArguments == 1) { s = -s; }
172            return s;
173          }
174        case OpCodes.Mul: {
175            double p = Evaluate(dataset, ref row, state);
176            for (int i = 1; i < currentInstr.nArguments; i++) {
177              p *= Evaluate(dataset, ref row, state);
178            }
179            return p;
180          }
181        case OpCodes.Div: {
182            double p = Evaluate(dataset, ref row, state);
183            for (int i = 1; i < currentInstr.nArguments; i++) {
184              p /= Evaluate(dataset, ref row, state);
185            }
186            if (currentInstr.nArguments == 1) { p = 1.0 / p; }
187            return p;
188          }
189        case OpCodes.Average: {
190            double sum = Evaluate(dataset, ref row, state);
191            for (int i = 1; i < currentInstr.nArguments; i++) {
192              sum += Evaluate(dataset, ref row, state);
193            }
194            return sum / currentInstr.nArguments;
195          }
196        case OpCodes.Cos: {
197            return Math.Cos(Evaluate(dataset, ref row, state));
198          }
199        case OpCodes.Sin: {
200            return Math.Sin(Evaluate(dataset, ref row, state));
201          }
202        case OpCodes.Tan: {
203            return Math.Tan(Evaluate(dataset, ref row, state));
204          }
205        case OpCodes.Square: {
206            return Math.Pow(Evaluate(dataset, ref row, state), 2);
207          }
208        case OpCodes.Power: {
209            double x = Evaluate(dataset, ref row, state);
210            double y = Math.Round(Evaluate(dataset, ref row, state));
211            return Math.Pow(x, y);
212          }
213        case OpCodes.SquareRoot: {
214            return Math.Sqrt(Evaluate(dataset, ref row, state));
215          }
216        case OpCodes.Root: {
217            double x = Evaluate(dataset, ref row, state);
218            double y = Math.Round(Evaluate(dataset, ref row, state));
219            return Math.Pow(x, 1 / y);
220          }
221        case OpCodes.Exp: {
222            return Math.Exp(Evaluate(dataset, ref row, state));
223          }
224        case OpCodes.Log: {
225            return Math.Log(Evaluate(dataset, ref row, state));
226          }
227        case OpCodes.Gamma: {
228            var x = Evaluate(dataset, ref row, state);
229            if (double.IsNaN(x)) { return double.NaN; } else { return alglib.gammafunction(x); }
230          }
231        case OpCodes.Psi: {
232            var x = Evaluate(dataset, ref row, state);
233            if (double.IsNaN(x)) return double.NaN;
234            else if (x <= 0 && (Math.Floor(x) - x).IsAlmost(0)) return double.NaN;
235            return alglib.psi(x);
236          }
237        case OpCodes.Dawson: {
238            var x = Evaluate(dataset, ref row, state);
239            if (double.IsNaN(x)) { return double.NaN; }
240            return alglib.dawsonintegral(x);
241          }
242        case OpCodes.ExponentialIntegralEi: {
243            var x = Evaluate(dataset, ref row, state);
244            if (double.IsNaN(x)) { return double.NaN; }
245            return alglib.exponentialintegralei(x);
246          }
247        case OpCodes.SineIntegral: {
248            double si, ci;
249            var x = Evaluate(dataset, ref row, state);
250            if (double.IsNaN(x)) return double.NaN;
251            else {
252              alglib.sinecosineintegrals(x, out si, out ci);
253              return si;
254            }
255          }
256        case OpCodes.CosineIntegral: {
257            double si, ci;
258            var x = Evaluate(dataset, ref row, state);
259            if (double.IsNaN(x)) return double.NaN;
260            else {
261              alglib.sinecosineintegrals(x, out si, out ci);
262              return ci;
263            }
264          }
265        case OpCodes.HyperbolicSineIntegral: {
266            double shi, chi;
267            var x = Evaluate(dataset, ref row, state);
268            if (double.IsNaN(x)) return double.NaN;
269            else {
270              alglib.hyperbolicsinecosineintegrals(x, out shi, out chi);
271              return shi;
272            }
273          }
274        case OpCodes.HyperbolicCosineIntegral: {
275            double shi, chi;
276            var x = Evaluate(dataset, ref row, state);
277            if (double.IsNaN(x)) return double.NaN;
278            else {
279              alglib.hyperbolicsinecosineintegrals(x, out shi, out chi);
280              return chi;
281            }
282          }
283        case OpCodes.FresnelCosineIntegral: {
284            double c = 0, s = 0;
285            var x = Evaluate(dataset, ref row, state);
286            if (double.IsNaN(x)) return double.NaN;
287            else {
288              alglib.fresnelintegral(x, ref c, ref s);
289              return c;
290            }
291          }
292        case OpCodes.FresnelSineIntegral: {
293            double c = 0, s = 0;
294            var x = Evaluate(dataset, ref row, state);
295            if (double.IsNaN(x)) return double.NaN;
296            else {
297              alglib.fresnelintegral(x, ref c, ref s);
298              return s;
299            }
300          }
301        case OpCodes.AiryA: {
302            double ai, aip, bi, bip;
303            var x = Evaluate(dataset, ref row, state);
304            if (double.IsNaN(x)) return double.NaN;
305            else {
306              alglib.airy(x, out ai, out aip, out bi, out bip);
307              return ai;
308            }
309          }
310        case OpCodes.AiryB: {
311            double ai, aip, bi, bip;
312            var x = Evaluate(dataset, ref row, state);
313            if (double.IsNaN(x)) return double.NaN;
314            else {
315              alglib.airy(x, out ai, out aip, out bi, out bip);
316              return bi;
317            }
318          }
319        case OpCodes.Norm: {
320            var x = Evaluate(dataset, ref row, state);
321            if (double.IsNaN(x)) return double.NaN;
322            else return alglib.normaldistribution(x);
323          }
324        case OpCodes.Erf: {
325            var x = Evaluate(dataset, ref row, state);
326            if (double.IsNaN(x)) return double.NaN;
327            else return alglib.errorfunction(x);
328          }
329        case OpCodes.Bessel: {
330            var x = Evaluate(dataset, ref row, state);
331            if (double.IsNaN(x)) return double.NaN;
332            else return alglib.besseli0(x);
333          }
334        case OpCodes.IfThenElse: {
335            double condition = Evaluate(dataset, ref row, state);
336            double result;
337            if (condition > 0.0) {
338              result = Evaluate(dataset, ref row, state); state.SkipInstructions();
339            } else {
340              state.SkipInstructions(); result = Evaluate(dataset, ref row, state);
341            }
342            return result;
343          }
344        case OpCodes.AND: {
345            double result = Evaluate(dataset, ref row, state);
346            for (int i = 1; i < currentInstr.nArguments; i++) {
347              if (result > 0.0) result = Evaluate(dataset, ref row, state);
348              else {
349                state.SkipInstructions();
350              }
351            }
352            return result > 0.0 ? 1.0 : -1.0;
353          }
354        case OpCodes.OR: {
355            double result = Evaluate(dataset, ref row, state);
356            for (int i = 1; i < currentInstr.nArguments; i++) {
357              if (result <= 0.0) result = Evaluate(dataset, ref row, state);
358              else {
359                state.SkipInstructions();
360              }
361            }
362            return result > 0.0 ? 1.0 : -1.0;
363          }
364        case OpCodes.NOT: {
365            return Evaluate(dataset, ref row, state) > 0.0 ? -1.0 : 1.0;
366          }
367        case OpCodes.XOR: {
368            //mkommend: XOR on multiple inputs is defined as true if the number of positive signals is odd
369            // this is equal to a consecutive execution of binary XOR operations.
370            int positiveSignals = 0;
371            for (int i = 0; i < currentInstr.nArguments; i++) {
372              if (Evaluate(dataset, ref row, state) > 0.0) { positiveSignals++; }
373            }
374            return positiveSignals % 2 != 0 ? 1.0 : -1.0;
375          }
376        case OpCodes.GT: {
377            double x = Evaluate(dataset, ref row, state);
378            double y = Evaluate(dataset, ref row, state);
379            if (x > y) { return 1.0; } else { return -1.0; }
380          }
381        case OpCodes.LT: {
382            double x = Evaluate(dataset, ref row, state);
383            double y = Evaluate(dataset, ref row, state);
384            if (x < y) { return 1.0; } else { return -1.0; }
385          }
386        case OpCodes.TimeLag: {
387            var timeLagTreeNode = (LaggedTreeNode)currentInstr.dynamicNode;
388            row += timeLagTreeNode.Lag;
389            double result = Evaluate(dataset, ref row, state);
390            row -= timeLagTreeNode.Lag;
391            return result;
392          }
393        case OpCodes.Integral: {
394            int savedPc = state.ProgramCounter;
395            var timeLagTreeNode = (LaggedTreeNode)currentInstr.dynamicNode;
396            double sum = 0.0;
397            for (int i = 0; i < Math.Abs(timeLagTreeNode.Lag); i++) {
398              row += Math.Sign(timeLagTreeNode.Lag);
399              sum += Evaluate(dataset, ref row, state);
400              state.ProgramCounter = savedPc;
401            }
402            row -= timeLagTreeNode.Lag;
403            sum += Evaluate(dataset, ref row, state);
404            return sum;
405          }
406
407        //mkommend: derivate calculation taken from:
408        //http://www.holoborodko.com/pavel/numerical-methods/numerical-derivative/smooth-low-noise-differentiators/
409        //one sided smooth differentiatior, N = 4
410        // y' = 1/8h (f_i + 2f_i-1, -2 f_i-3 - f_i-4)
411        case OpCodes.Derivative: {
412            int savedPc = state.ProgramCounter;
413            double f_0 = Evaluate(dataset, ref row, state); row--;
414            state.ProgramCounter = savedPc;
415            double f_1 = Evaluate(dataset, ref row, state); row -= 2;
416            state.ProgramCounter = savedPc;
417            double f_3 = Evaluate(dataset, ref row, state); row--;
418            state.ProgramCounter = savedPc;
419            double f_4 = Evaluate(dataset, ref row, state);
420            row += 4;
421
422            return (f_0 + 2 * f_1 - 2 * f_3 - f_4) / 8; // h = 1
423          }
424        case OpCodes.Call: {
425            // evaluate sub-trees
426            double[] argValues = new double[currentInstr.nArguments];
427            for (int i = 0; i < currentInstr.nArguments; i++) {
428              argValues[i] = Evaluate(dataset, ref row, state);
429            }
430            // push on argument values on stack
431            state.CreateStackFrame(argValues);
432
433            // save the pc
434            int savedPc = state.ProgramCounter;
435            // set pc to start of function 
436            state.ProgramCounter = (ushort)currentInstr.data;
437            // evaluate the function
438            double v = Evaluate(dataset, ref row, state);
439
440            // delete the stack frame
441            state.RemoveStackFrame();
442
443            // restore the pc => evaluation will continue at point after my subtrees 
444            state.ProgramCounter = savedPc;
445            return v;
446          }
447        case OpCodes.Arg: {
448            return state.GetStackFrameValue((ushort)currentInstr.data);
449          }
450        case OpCodes.Variable: {
451            if (row < 0 || row >= dataset.Rows) return double.NaN;
452            var variableTreeNode = (VariableTreeNode)currentInstr.dynamicNode;
453            return ((IList<double>)currentInstr.data)[row] * variableTreeNode.Weight;
454          }
455        case OpCodes.LagVariable: {
456            var laggedVariableTreeNode = (LaggedVariableTreeNode)currentInstr.dynamicNode;
457            int actualRow = row + laggedVariableTreeNode.Lag;
458            if (actualRow < 0 || actualRow >= dataset.Rows) { return double.NaN; }
459            return ((IList<double>)currentInstr.data)[actualRow] * laggedVariableTreeNode.Weight;
460          }
461        case OpCodes.Constant: {
462            var constTreeNode = (ConstantTreeNode)currentInstr.dynamicNode;
463            return constTreeNode.Value;
464          }
465
466        //mkommend: this symbol uses the logistic function f(x) = 1 / (1 + e^(-alpha * x) )
467        //to determine the relative amounts of the true and false branch see http://en.wikipedia.org/wiki/Logistic_function
468        case OpCodes.VariableCondition: {
469            if (row < 0 || row >= dataset.Rows) return double.NaN;
470            var variableConditionTreeNode = (VariableConditionTreeNode)currentInstr.dynamicNode;
471            double variableValue = ((IList<double>)currentInstr.data)[row];
472            double x = variableValue - variableConditionTreeNode.Threshold;
473            double p = 1 / (1 + Math.Exp(-variableConditionTreeNode.Slope * x));
474
475            double trueBranch = Evaluate(dataset, ref row, state);
476            double falseBranch = Evaluate(dataset, ref row, state);
477
478            return trueBranch * p + falseBranch * (1 - p);
479          }
480        default:
481          throw new NotSupportedException();
482      }
483    }
484  }
485}
Note: See TracBrowser for help on using the repository browser.