source: branches/symbreg-factors-2650/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeInterpreter.cs @ 14232

Last change on this file since 14232 was 14232, checked in by gkronber, 3 years ago

created a feature branch for #2650 (support for categorical variables in symb reg) with a first set of changes

work in progress...

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