Free cookie consent management tool by TermsFeed Policy Generator

source: branches/DataAnalysis.IslandAlgorithms/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeInterpreter.cs @ 16396

Last change on this file since 16396 was 11646, checked in by mkommend, 10 years ago

#1997: Merged trunk changes to data analysis island GA branch.

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