Changeset 16386 for branches/2925_AutoDiffForDynamicalModels/HeuristicLab.Problems.DataAnalysis.Symbolic

Timestamp:

12/15/18 12:07:16 (6 years ago)

Author:

gkronber

Message:

#2925 merged changes r15972:16382 from trunk to branch

Location:

branches/2925_AutoDiffForDynamicalModels

Files:

• . (modified) (1 prop)
• HeuristicLab.Problems.DataAnalysis.Symbolic (modified) (1 prop)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Analyzers/SymbolicDataAnalysisBuildingBlockAnalyzer.cs (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Analyzers/SymbolicDataAnalysisBuildingBlockAnalyzer.cs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/DerivativeCalculator.cs (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/DerivativeCalculator.cs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/LinearModelToTreeConverter.cs (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/TreeSimplifier.cs (modified) (16 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/TreeToAutoDiffTermConverter.cs (modified) (4 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionDiversityPreservingCrossover.cs (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionDiversityPreservingCrossover.cs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Formatters/InfixExpressionFormatter.cs (modified) (2 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Grammars/FullFunctionalExpressionGrammar.cs (modified) (3 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Grammars/TypeCoherentExpressionGrammar.cs (modified) (7 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj (modified) (6 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Importer/InfixExpressionParser.cs (modified) (9 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Importer/SymbolicExpressionImporter.cs (modified) (3 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/BatchInstruction.cs (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/BatchInstruction.cs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/BatchOperations.cs (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/BatchOperations.cs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/OpCodes.cs (modified) (4 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionCompiledTreeInterpreter.cs (modified) (5 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeBatchInterpreter.cs (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeBatchInterpreter.cs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeILEmittingInterpreter.cs (modified) (5 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeInterpreter.cs (modified) (4 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeLinearInterpreter.cs (modified) (4 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeNativeInterpreter.cs (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeNativeInterpreter.cs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Plugin.cs.frame (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisModel.cs (modified) (3 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Symbols/Absolute.cs (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Symbols/Absolute.cs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Symbols/AnalyticQuotient.cs (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Symbols/AnalyticQuotient.cs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Symbols/Cube.cs (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Symbols/Cube.cs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Symbols/CubeRoot.cs (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Symbols/CubeRoot.cs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeBottomUpSimilarityCalculator.cs (modified) (7 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/packages.config (copied) (copied from trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/packages.config)

branches/2925_AutoDiffForDynamicalModels/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/LinearModelToTreeConverter.cs

@@ -37 +37 @@
       string[] variableNames, double[] coefficients,
       double @const = 0) {
+
       if (factorCoefficients.Length == 0 && coefficients.Length == 0) throw new ArgumentException();
-      ISymbolicExpressionTree p1 = null;
+
+      // Create tree for double variables
+      ISymbolicExpressionTree tree = null;      
       if (coefficients.Length > 0) {
-        p1 = CreateTree(variableNames, new int[variableNames.Length], coefficients, @const);
-        if (factorCoefficients.Length == 0)
-          return p1;
+        tree = CreateTree(variableNames, new int[variableNames.Length], coefficients, @const);
+        if (factorCoefficients.Length == 0) return tree;
       }
+
+      // Create tree for string variables
+      ISymbolicExpressionTree factorTree = null;      
       if (factorCoefficients.Length > 0) {
-        var p2 = CreateTree(factors, factorCoefficients);
-        if (p1 == null) return p2;
+        factorTree = CreateTree(factors, factorCoefficients, @const);
+        if (tree == null) return factorTree;  
+      }
 
-        // combine
-        ISymbolicExpressionTreeNode add = p1.Root.GetSubtree(0).GetSubtree(0);
-        foreach (var binFactorNode in p2.IterateNodesPrefix().OfType<BinaryFactorVariableTreeNode>())
-          add.AddSubtree(binFactorNode);
-        return p1;
-      }
+      // Combine both trees
+      ISymbolicExpressionTreeNode add = tree.Root.GetSubtree(0).GetSubtree(0);
+      foreach (var binFactorNode in factorTree.IterateNodesPrefix().OfType<BinaryFactorVariableTreeNode>())
+        add.InsertSubtree(add.SubtreeCount - 1, binFactorNode);
+      return tree;
+
       throw new ArgumentException();
     }

branches/2925_AutoDiffForDynamicalModels/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/TreeSimplifier.cs

@@ -37 +37 @@
     private static readonly Division divSymbol = new Division();
     private static readonly Constant constSymbol = new Constant();
+    private static readonly Absolute absSymbol = new Absolute();
     private static readonly Logarithm logSymbol = new Logarithm();
     private static readonly Exponential expSymbol = new Exponential();
@@ -42 +43 @@
     private static readonly Square sqrSymbol = new Square();
     private static readonly SquareRoot sqrtSymbol = new SquareRoot();
+    private static readonly AnalyticQuotient aqSymbol = new AnalyticQuotient();
+    private static readonly Cube cubeSymbol = new Cube();
+    private static readonly CubeRoot cubeRootSymbol = new CubeRoot();
     private static readonly Power powSymbol = new Power();
     private static readonly Sine sineSymbol = new Sine();
@@ -131 +135 @@
     }
 
+    private static bool IsAbsolute(ISymbolicExpressionTreeNode node) {
+      return node.Symbol is Absolute;
+    }
+
     // exponential
     private static bool IsLog(ISymbolicExpressionTreeNode node) {
@@ -152 +160 @@
     }
 
+    private static bool IsCube(ISymbolicExpressionTreeNode node) {
+      return node.Symbol is Cube;
+    }
+
+    private static bool IsCubeRoot(ISymbolicExpressionTreeNode node) {
+      return node.Symbol is CubeRoot;
+    }
+
     private static bool IsPower(ISymbolicExpressionTreeNode node) {
       return node.Symbol is Power;
@@ -167 +183 @@
     private static bool IsTangent(ISymbolicExpressionTreeNode node) {
       return node.Symbol is Tangent;
+    }
+
+    private static bool IsAnalyticalQuotient(ISymbolicExpressionTreeNode node) {
+      return node.Symbol is AnalyticQuotient;
     }
 
@@ -243 +263 @@
       if (IsConstant(original) || IsVariableBase(original)) {
         return (ISymbolicExpressionTreeNode)original.Clone();
+      } else if (IsAbsolute(original)) {
+        return SimplifyAbsolute(original);
       } else if (IsAddition(original)) {
         return SimplifyAddition(original);
@@ -261 +283 @@
       } else if (IsSquareRoot(original)) {
         return SimplifySquareRoot(original);
+      } else if (IsCube(original)) {
+        return SimplifyCube(original);
+      } else if (IsCubeRoot(original)) {
+        return SimplifyCubeRoot(original);
       } else if (IsPower(original)) {
         return SimplifyPower(original);
@@ -271 +297 @@
       } else if (IsTangent(original)) {
         return SimplifyTangent(original);
+      } else if (IsAnalyticalQuotient(original)) {
+        return SimplifyAnalyticalQuotient(original);
       } else if (IsIfThenElse(original)) {
         return SimplifyIfThenElse(original);
@@ -380 +408 @@
     }
 
+    private static ISymbolicExpressionTreeNode SimplifyAbsolute(ISymbolicExpressionTreeNode original) {
+      return MakeAbs(GetSimplifiedTree(original.GetSubtree(0)));
+    }
+
     private static ISymbolicExpressionTreeNode SimplifyNot(ISymbolicExpressionTreeNode original) {
       return MakeNot(GetSimplifiedTree(original.GetSubtree(0)));
@@ -432 +464 @@
       return MakeSquareRoot(GetSimplifiedTree(original.GetSubtree(0)));
     }
+    private static ISymbolicExpressionTreeNode SimplifyCube(ISymbolicExpressionTreeNode original) {
+      return MakeCube(GetSimplifiedTree(original.GetSubtree(0)));
+    }
+
+    private static ISymbolicExpressionTreeNode SimplifyCubeRoot(ISymbolicExpressionTreeNode original) {
+      return MakeCubeRoot(GetSimplifiedTree(original.GetSubtree(0)));
+    }
 
     private static ISymbolicExpressionTreeNode SimplifyLog(ISymbolicExpressionTreeNode original) {
@@ -443 +482 @@
     private static ISymbolicExpressionTreeNode SimplifyPower(ISymbolicExpressionTreeNode original) {
       return MakePower(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
+    }
+
+    private static ISymbolicExpressionTreeNode SimplifyAnalyticalQuotient(ISymbolicExpressionTreeNode original) {
+      return MakeAnalyticalQuotient(GetSimplifiedTree(original.GetSubtree(0)), GetSimplifiedTree(original.GetSubtree(1)));
     }
 
@@ -730 +773 @@
       } else if (IsSquareRoot(node)) {
         return node.GetSubtree(0);
+      } else if (IsMultiplication(node)) {
+        // sqr( x * y ) = sqr(x) * sqr(y)
+        var mulNode = mulSymbol.CreateTreeNode();
+        foreach (var subtree in node.Subtrees) {
+          mulNode.AddSubtree(MakeSquare(subtree));
+        }
+        return mulNode;
+      } else if (IsAbsolute(node)) {
+        return MakeSquare(node.GetSubtree(0)); // sqr(abs(x)) = sqr(x)
+      } else if (IsExp(node)) {
+        return MakeExp(MakeProduct(node.GetSubtree(0), MakeConstant(2.0))); // sqr(exp(x)) = exp(2x)
+      } else if (IsCube(node)) {
+        return MakePower(node.GetSubtree(0), MakeConstant(6));
       } else {
         var sqrNode = sqrSymbol.CreateTreeNode();
         sqrNode.AddSubtree(node);
         return sqrNode;
+      }
+    }
+
+    private static ISymbolicExpressionTreeNode MakeCube(ISymbolicExpressionTreeNode node) {
+      if (IsConstant(node)) {
+        var constT = node as ConstantTreeNode;
+        return MakeConstant(constT.Value * constT.Value * constT.Value);
+      } else if (IsFactor(node)) {
+        var factNode = node as FactorVariableTreeNode;
+        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => w * w * w));
+      } else if (IsBinFactor(node)) {
+        var binFactor = node as BinaryFactorVariableTreeNode;
+        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, binFactor.Weight * binFactor.Weight * binFactor.Weight);
+      } else if (IsCubeRoot(node)) {
+        return node.GetSubtree(0); // NOTE: not really accurate because cuberoot(x) with negative x is evaluated to NaN and after this simplification we evaluate as x
+      } else if (IsExp(node)) {
+        return MakeExp(MakeProduct(node.GetSubtree(0), MakeConstant(3)));
+      } else if (IsSquare(node)) {
+        return MakePower(node.GetSubtree(0), MakeConstant(6));
+      } else {
+        var cubeNode = cubeSymbol.CreateTreeNode();
+        cubeNode.AddSubtree(node);
+        return cubeNode;
+      }
+    }
+
+    private static ISymbolicExpressionTreeNode MakeAbs(ISymbolicExpressionTreeNode node) {
+      if (IsConstant(node)) {
+        var constT = node as ConstantTreeNode;
+        return MakeConstant(Math.Abs(constT.Value));
+      } else if (IsFactor(node)) {
+        var factNode = node as FactorVariableTreeNode;
+        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Abs(w)));
+      } else if (IsBinFactor(node)) {
+        var binFactor = node as BinaryFactorVariableTreeNode;
+        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Abs(binFactor.Weight));
+      } else if (IsSquare(node) || IsExp(node) || IsSquareRoot(node) || IsCubeRoot(node)) {
+        return node; // abs(sqr(x)) = sqr(x), abs(exp(x)) = exp(x) ...
+      } else if (IsMultiplication(node)) {
+        var mul = mulSymbol.CreateTreeNode();
+        foreach (var st in node.Subtrees) {
+          mul.AddSubtree(MakeAbs(st));
+        }
+        return mul;
+      } else if (IsDivision(node)) {
+        var div = divSymbol.CreateTreeNode();
+        foreach (var st in node.Subtrees) {
+          div.AddSubtree(MakeAbs(st));
+        }
+        return div;
+      } else {
+        var absNode = absSymbol.CreateTreeNode();
+        absNode.AddSubtree(node);
+        return absNode;
+      }
+    }
+
+    // constant folding only
+    private static ISymbolicExpressionTreeNode MakeAnalyticalQuotient(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
+      if (IsConstant(b)) {
+        var c = b as ConstantTreeNode;
+        return MakeFraction(a, MakeConstant(Math.Sqrt(1.0 + c.Value * c.Value)));
+      } else if (IsFactor(b)) {
+        var factNode = b as FactorVariableTreeNode;
+        return MakeFraction(a, MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Sqrt(1.0 + w * w))));
+      } else if (IsBinFactor(b)) {
+        var binFactor = b as BinaryFactorVariableTreeNode;
+        return MakeFraction(a, MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Sqrt(1.0 + binFactor.Weight * binFactor.Weight)));
+      } else {
+        var aqNode = aqSymbol.CreateTreeNode();
+        aqNode.AddSubtree(a);
+        aqNode.AddSubtree(b);
+        return aqNode;
       }
     }
@@ -748 +877 @@
         return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Sqrt(binFactor.Weight));
       } else if (IsSquare(node)) {
-        return node.GetSubtree(0);
+        return node.GetSubtree(0); // NOTE: not really accurate because sqrt(x) with negative x is evaluated to NaN and after this simplification we evaluate as x
       } else {
         var sqrtNode = sqrtSymbol.CreateTreeNode();
         sqrtNode.AddSubtree(node);
         return sqrtNode;
+      }
+    }
+
+    private static ISymbolicExpressionTreeNode MakeCubeRoot(ISymbolicExpressionTreeNode node) {
+      if (IsConstant(node)) {
+        var constT = node as ConstantTreeNode;
+        return MakeConstant(Math.Pow(constT.Value, 1.0 / 3.0));
+      } else if (IsFactor(node)) {
+        var factNode = node as FactorVariableTreeNode;
+        return MakeFactor(factNode.Symbol, factNode.VariableName, factNode.Weights.Select(w => Math.Pow(w, 1.0 / 3.0)));
+      } else if (IsBinFactor(node)) {
+        var binFactor = node as BinaryFactorVariableTreeNode;
+        return MakeBinFactor(binFactor.Symbol, binFactor.VariableName, binFactor.VariableValue, Math.Sqrt(Math.Pow(binFactor.Weight, 1.0 / 3.0)));
+      } else if (IsCube(node)) {
+        return node.GetSubtree(0);
+      } else {
+        var cubeRootNode = cubeRootSymbol.CreateTreeNode();
+        cubeRootNode.AddSubtree(node);
+        return cubeRootNode;
       }
     }
@@ -927 +1075 @@
         // a / (b1 / b2) => (a * b2) / b1
         return MakeFraction(MakeProduct(a, b.GetSubtree(1)), b.GetSubtree(0));
+      } else if (IsAnalyticalQuotient(a)) {
+        return MakeAnalyticalQuotient(a.GetSubtree(0), MakeProduct(a.GetSubtree(1), b));
       } else {
         var div = divSymbol.CreateTreeNode();
@@ -1121 +1271 @@
         // $ * 1.0 => $
         return a;
+      } else if (IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(0.0)) {
+        return MakeConstant(0);
       } else if (IsConstant(b) && IsVariableBase(a)) {
         // multiply constants into variables weights
@@ -1153 +1305 @@
         MergeVariablesAndConstantsInProduct(a);
         return a;
+      } else if (IsAbsolute(a) && IsAbsolute(b)) {
+        return MakeAbs(MakeProduct(a.GetSubtree(0), b.GetSubtree(0)));
+      } else if (IsAbsolute(a) && IsConstant(b)) {
+        var constNode = b as ConstantTreeNode;
+        var posF = Math.Abs(constNode.Value);
+        if (constNode.Value > 0) {
+          return MakeAbs(MakeProduct(a.GetSubtree(0), MakeConstant(posF)));
+        } else {
+          var mul = mulSymbol.CreateTreeNode();
+          mul.AddSubtree(MakeAbs(MakeProduct(a.GetSubtree(0), MakeConstant(posF))));
+          mul.AddSubtree(MakeConstant(-1.0));
+          return mul;
+        }
+      } else if (IsAnalyticalQuotient(a)) {
+        return MakeAnalyticalQuotient(MakeProduct(a.GetSubtree(0), b), a.GetSubtree(1));
       } else {
         var mul = mulSymbol.CreateTreeNode();

branches/2925_AutoDiffForDynamicalModels/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/TreeToAutoDiffTermConverter.cs

@@ -85 +85 @@
       diff: x => -(Math.Exp(-(x * x)) * Math.Sqrt(Math.Exp(x * x)) * x) / Math.Sqrt(2 * Math.PI));
 
+    private static readonly Func<Term, UnaryFunc> abs = UnaryFunc.Factory(
+      eval: Math.Abs,
+      diff: x => Math.Sign(x)
+      );
+
     #endregion
 
@@ -213 +218 @@
         else return terms.Aggregate((a, b) => new AutoDiff.Product(a, 1.0 / b));
       }
+      if (node.Symbol is Absolute) {
+        var x1 = ConvertToAutoDiff(node.GetSubtree(0));
+        return abs(x1);
+      }
+      if (node.Symbol is AnalyticQuotient) {
+        var x1 = ConvertToAutoDiff(node.GetSubtree(0));
+        var x2 = ConvertToAutoDiff(node.GetSubtree(1));
+        return x1 / (TermBuilder.Power(1 + x2 * x2, 0.5));
+      }
       if (node.Symbol is Logarithm) {
         return AutoDiff.TermBuilder.Log(
@@ -228 +242 @@
         return AutoDiff.TermBuilder.Power(
           ConvertToAutoDiff(node.GetSubtree(0)), 0.5);
+      }
+      if (node.Symbol is Cube) {
+        return AutoDiff.TermBuilder.Power(
+          ConvertToAutoDiff(node.GetSubtree(0)), 3.0);
+      }
+      if (node.Symbol is CubeRoot) {
+        return AutoDiff.TermBuilder.Power(
+          ConvertToAutoDiff(node.GetSubtree(0)), 1.0/3.0);
       }
       if (node.Symbol is Sine) {
@@ -301 +323 @@
           !(n.Symbol is Erf) &&
           !(n.Symbol is Norm) &&
-          !(n.Symbol is StartSymbol)
+          !(n.Symbol is StartSymbol) &&
+          !(n.Symbol is Absolute) &&
+          !(n.Symbol is AnalyticQuotient) &&
+          !(n.Symbol is Cube) &&
+          !(n.Symbol is CubeRoot)
         select n).Any();
       return !containsUnknownSymbol;

branches/2925_AutoDiffForDynamicalModels/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Formatters/InfixExpressionFormatter.cs

@@ -62 +62 @@
       if (node.SubtreeCount > 1) {
         var token = GetToken(node.Symbol);
-        if (token == "+" || token == "-" || token == "OR" || token == "XOR") {
-          strBuilder.Append("(");
-          FormatRecursively(node.Subtrees.First(), strBuilder);
-
-          foreach (var subtree in node.Subtrees.Skip(1)) {
-            strBuilder.Append(" ").Append(token).Append(" ");
-            FormatRecursively(subtree, strBuilder);
-          }
-          strBuilder.Append(")");
-
-        } else if (token == "*" || token == "/" || token == "AND") {
+        // operators
+        if (token == "+" || token == "-" || token == "OR" || token == "XOR" ||
+            token == "*" || token == "/" || token == "AND" ||
+            token == "^") {
           strBuilder.Append("(");
           FormatRecursively(node.Subtrees.First(), strBuilder);
@@ -184 +177 @@
 
     private string GetToken(ISymbol symbol) {
-      var tok = InfixExpressionParser.knownSymbols.GetBySecond(symbol).SingleOrDefault();
+      var tok = InfixExpressionParser.knownSymbols.GetBySecond(symbol).FirstOrDefault();
       if (tok == null)
         throw new ArgumentException(string.Format("Unknown symbol {0} found.", symbol.Name));

branches/2925_AutoDiffForDynamicalModels/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Grammars/FullFunctionalExpressionGrammar.cs

@@ -48 +48 @@
       var mul = new Multiplication();
       var div = new Division();
+      var aq = new AnalyticQuotient();
       var mean = new Average();
       var sin = new Sine();
@@ -53 +54 @@
       var tan = new Tangent();
       var log = new Logarithm();
+      var abs = new Absolute();
       var pow = new Power();
       pow.InitialFrequency = 0.0;
       var square = new Square();
       square.InitialFrequency = 0.0;
+      var cube = new Cube();
+      cube.InitialFrequency = 0.0;
       var root = new Root();
       root.InitialFrequency = 0.0;
       var sqrt = new SquareRoot();
       sqrt.InitialFrequency = 0.0;
+      var cubeRoot = new CubeRoot();
+      cubeRoot.InitialFrequency = 0.0;
       var airyA = new AiryA();
       airyA.InitialFrequency = 0.0;
@@ -123 +129 @@
       autoregressiveVariable.Enabled = false;
 
-      var allSymbols = new List<Symbol>() { add, sub, mul, div, mean, sin, cos, tan, log, square, pow, sqrt, root, exp,
+      var allSymbols = new List<Symbol>() { add, sub, mul, div, aq, mean, abs, sin, cos, tan, log, square, cube, pow, sqrt, cubeRoot, root, exp,
         airyA, airyB, bessel, cosineIntegral, dawson, erf, expIntegralEi, fresnelCosineIntegral, fresnelSineIntegral, gamma, hypCosineIntegral, hypSineIntegral, norm, psi, sineIntegral,
         @if, gt, lt, and, or, not,xor, timeLag, integral, derivative, constant, variableSymbol, binFactorVariable, factorVariable, laggedVariable,autoregressiveVariable, variableCondition };
-      var unaryFunctionSymbols = new List<Symbol>() { square, sqrt, sin, cos, tan, log, exp, not, timeLag, integral, derivative,
+      var unaryFunctionSymbols = new List<Symbol>() { abs, square, sqrt, cube, cubeRoot, sin, cos, tan, log, exp, not, timeLag, integral, derivative,
         airyA, airyB, bessel, cosineIntegral, dawson, erf, expIntegralEi, fresnelCosineIntegral, fresnelSineIntegral, gamma, hypCosineIntegral, hypSineIntegral, norm, psi, sineIntegral
       };
 
-      var binaryFunctionSymbols = new List<Symbol>() { pow, root, gt, lt, variableCondition };
+      var binaryFunctionSymbols = new List<Symbol>() { pow, root, gt, lt, aq, variableCondition };
       var ternarySymbols = new List<Symbol>() { add, sub, mul, div, mean, and, or, xor };
       var terminalSymbols = new List<Symbol>() { variableSymbol, binFactorVariable, factorVariable, constant, laggedVariable, autoregressiveVariable };

branches/2925_AutoDiffForDynamicalModels/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Grammars/TypeCoherentExpressionGrammar.cs

@@ -69 +69 @@
       var root = new Root();
       var sqrt = new SquareRoot();
+      var cube = new Cube();
+      var cubeRoot = new CubeRoot();
       var exp = new Exponential();
+      var abs = new Absolute();
 
       var airyA = new AiryA();
@@ -86 +89 @@
       var psi = new Psi();
       var sineIntegral = new SineIntegral();
+      var analyticalQuotient = new AnalyticQuotient();
 
       var @if = new IfThenElse();
@@ -114 +118 @@
       var trigonometricSymbols = new GroupSymbol(TrigonometricFunctionsName, new List<ISymbol>() { sin, cos, tan });
       var exponentialAndLogarithmicSymbols = new GroupSymbol(ExponentialFunctionsName, new List<ISymbol> { exp, log });
-      var specialFunctions = new GroupSymbol(SpecialFunctionsName, new List<ISymbol> { airyA, airyB, bessel, cosineIntegral, dawson, erf, expIntegralEi,
-        fresnelCosineIntegral,fresnelSineIntegral,gamma,hypCosineIntegral,hypSineIntegral,norm, psi, sineIntegral});
+      var specialFunctions = new GroupSymbol(SpecialFunctionsName, new List<ISymbol> { abs, airyA, airyB, bessel, cosineIntegral, dawson, erf, expIntegralEi,
+        fresnelCosineIntegral,fresnelSineIntegral,gamma,hypCosineIntegral,hypSineIntegral,norm, psi, sineIntegral, analyticalQuotient});
       var terminalSymbols = new GroupSymbol(TerminalsName, new List<ISymbol> { constant, variableSymbol, binFactorVariable, factorVariable });
       var realValuedSymbols = new GroupSymbol(RealValuedSymbolsName, new List<ISymbol>() { arithmeticSymbols, trigonometricSymbols, exponentialAndLogarithmicSymbols, specialFunctions, terminalSymbols });
 
-      var powerSymbols = new GroupSymbol(PowerFunctionsName, new List<ISymbol> { square, pow, sqrt, root });
+      var powerSymbols = new GroupSymbol(PowerFunctionsName, new List<ISymbol> { square, pow, sqrt, root, cube, cubeRoot });
 
       var conditionSymbols = new GroupSymbol(ConditionsName, new List<ISymbol> { @if, variableCondition });
@@ -140 +144 @@
       SetSubtreeCount(root, 2, 2);
       SetSubtreeCount(square, 1, 1);
+      SetSubtreeCount(cube, 1, 1);
       SetSubtreeCount(sqrt, 1, 1);
+      SetSubtreeCount(cubeRoot, 1, 1);
       SetSubtreeCount(exponentialAndLogarithmicSymbols, 1, 1);
-      SetSubtreeCount(specialFunctions, 1, 1);
+      foreach(var sy in specialFunctions.Symbols.Except(new[] { analyticalQuotient})) {
+        SetSubtreeCount(sy, 1, 1);
+      }
+      SetSubtreeCount(analyticalQuotient, 2, 2);
+
       SetSubtreeCount(terminalSymbols, 0, 0);
 
@@ -231 +241 @@
     public void ConfigureAsDefaultRegressionGrammar() {
       Symbols.First(s => s is Average).Enabled = false;
+      Symbols.First(s => s is Absolute).Enabled = false;
       Symbols.First(s => s.Name == TrigonometricFunctionsName).Enabled = false;
       Symbols.First(s => s.Name == PowerFunctionsName).Enabled = false;
@@ -242 +253 @@
       Symbols.First(s => s is VariableCondition).Enabled = false;
       Symbols.First(s => s is Xor).Enabled = false;
+      Symbols.First(s => s is Absolute).Enabled = false;
       Symbols.First(s => s.Name == TrigonometricFunctionsName).Enabled = false;
       Symbols.First(s => s.Name == ExponentialFunctionsName).Enabled = false;
@@ -251 +263 @@
     public void ConfigureAsDefaultTimeSeriesPrognosisGrammar() {
       Symbols.First(s => s is Average).Enabled = false;
+      Symbols.First(s => s is Absolute).Enabled = false;
       Symbols.First(s => s.Name == TrigonometricFunctionsName).Enabled = false;
       Symbols.First(s => s.Name == PowerFunctionsName).Enabled = false;

branches/2925_AutoDiffForDynamicalModels/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

@@ -107 +107 @@
       <Private>False</Private>
     </Reference>
+    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.NativeInterpreter-0.1, Version=0.0.0.1, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\bin\HeuristicLab.Problems.DataAnalysis.Symbolic.NativeInterpreter-0.1.dll</HintPath>
+      <Private>False</Private>
+    </Reference>
     <Reference Include="System" />
     <Reference Include="System.Core">
@@ -123 +128 @@
   <ItemGroup>
     <Compile Include="Analyzers\SymbolicDataAnalysisBottomUpDiversityAnalyzer.cs" />
+    <Compile Include="Analyzers\SymbolicDataAnalysisBuildingBlockAnalyzer.cs" />
     <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectivePruningAnalyzer.cs" />
     <Compile Include="Analyzers\SymbolicDataAnalysisSingleObjectiveValidationParetoBestSolutionAnalyzer.cs" />
@@ -139 +145 @@
     <Compile Include="Converters\LinearModelToTreeConverter.cs" />
     <Compile Include="Converters\TreeSimplifier.cs" />
+    <Compile Include="Converters\DerivativeCalculator.cs" />
     <Compile Include="Converters\TreeToAutoDiffTermConverter.cs" />
+    <Compile Include="Crossovers\SymbolicDataAnalysisExpressionDiversityPreservingCrossover.cs" />
     <Compile Include="Formatters\InfixExpressionFormatter.cs" />
     <Compile Include="Formatters\TSQLExpressionFormatter.cs" />
     <Compile Include="Formatters\SymbolicDataAnalysisExpressionMathematicaFormatter.cs" />
     <Compile Include="Formatters\SymbolicDataAnalysisExpressionCSharpFormatter.cs" />
+    <Compile Include="Hashing\HashExtensions.cs" />
+    <Compile Include="Hashing\HashUtil.cs" />
+    <Compile Include="Hashing\SymbolicExpressionTreeHash.cs" />
     <Compile Include="Importer\InfixExpressionParser.cs" />
     <Compile Include="Importer\SymbolicExpressionImporter.cs" />
@@ -150 +161 @@
     <Compile Include="Interfaces\IVariableTreeNode.cs" />
     <Compile Include="Interfaces\IVariableSymbol.cs" />
+    <Compile Include="Interpreter\BatchInstruction.cs" />
+    <Compile Include="Interpreter\BatchOperations.cs" />
     <Compile Include="Interpreter\SymbolicDataAnalysisExpressionCompiledTreeInterpreter.cs" />
+    <Compile Include="Interpreter\SymbolicDataAnalysisExpressionTreeBatchInterpreter.cs" />
+    <Compile Include="Interpreter\SymbolicDataAnalysisExpressionTreeNativeInterpreter.cs" />
     <Compile Include="SymbolicDataAnalysisExpressionTreeSimplificationOperator.cs" />
     <Compile Include="SymbolicDataAnalysisModelComplexityCalculator.cs" />
@@ -198 +213 @@
     <Compile Include="SymbolicDataAnalysisSolutionImpactValuesCalculator.cs" />
     <Compile Include="Symbols\Addition.cs" />
+    <Compile Include="Symbols\AnalyticQuotient.cs" />
     <Compile Include="Symbols\And.cs" />
     <Compile Include="Symbols\AutoregressiveVariable.cs" />
@@ -208 +224 @@
     <Compile Include="Symbols\BinaryFactorVariable.cs" />
     <Compile Include="Symbols\BinaryFactorVariableTreeNode.cs" />
+    <Compile Include="Symbols\Cube.cs" />
     <Compile Include="Symbols\FactorVariableTreeNode.cs" />
     <Compile Include="Symbols\FactorVariable.cs" />
+    <Compile Include="Symbols\Absolute.cs" />
+    <Compile Include="Symbols\CubeRoot.cs" />
     <Compile Include="Symbols\VariableBase.cs" />
     <Compile Include="Symbols\VariableTreeNodeBase.cs" />

branches/2925_AutoDiffForDynamicalModels/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Importer/InfixExpressionParser.cs

@@ -42 +42 @@
   /// Expr          = ['-' | '+'] Term { '+' Term | '-' Term }
   /// Term          = Fact { '*' Fact | '/' Fact }
-  /// Fact          = '(' Expr ')' 
-  ///                 | 'LAG' '(' varId ',' ['+' | '-' ] number ')' 
-  ///                 | funcId '(' ArgList ')' 
-  ///                 | VarExpr | number
+  /// Fact          = SimpleFact [ '^' SimpleFact ]
+  /// SimpleFact    = '(' Expr ')'
+  ///                 | '{' Expr '}'
+  ///                 | 'LAG' '(' varId ',' ['+' | '-' ] number ')
+  ///                 | funcId '(' ArgList ')'
+  ///                 | VarExpr
+  ///                 | number
   /// ArgList       = Expr { ',' Expr }
   /// VarExpr       = varId OptFactorPart
@@ -95 +98 @@
         { "*", new Multiplication()},
         { "-", new Subtraction()},
+        { "^", new Power() },
+        { "ABS", new Absolute() },
         { "EXP", new Exponential()},
         { "LOG", new Logarithm()},
-        { "POW", new Power()},
+        { "POW", new Power() },
         { "ROOT", new Root()},
         { "SQR", new Square() },
         { "SQRT", new SquareRoot() },
+        { "CUBE", new Cube() },
+        { "CUBEROOT", new CubeRoot() },
         { "SIN",new Sine()},
         { "COS", new Cosine()},
@@ -119 +126 @@
         { "DAWSON", new Dawson()},
         { "EXPINT", new ExponentialIntegralEi()},
+        { "AQ", new AnalyticQuotient() },
         { "MEAN", new Average()},
         { "IF", new IfThenElse()},
@@ -167 +175 @@
             && str[pos] != '*'
             && str[pos] != '/'
+            && str[pos] != '^'
             && str[pos] != ')'
             && str[pos] != ']'
+            && str[pos] != '}'
             && str[pos] != ',') {
             sb.Append(str[pos]);
@@ -227 +237 @@
           pos++;
           yield return new Token { TokenType = TokenType.Operator, strVal = "*" };
+        } else if (str[pos] == '^') {
+          pos++;
+          yield return new Token { TokenType = TokenType.Operator, strVal = "^" };
         } else if (str[pos] == '(') {
           pos++;
@@ -239 +252 @@
           pos++;
           yield return new Token { TokenType = TokenType.RightBracket, strVal = "]" };
+        } else if (str[pos] == '{') {
+          pos++;
+          yield return new Token { TokenType = TokenType.LeftPar, strVal = "{" };
+        } else if (str[pos] == '}') {
+          pos++;
+          yield return new Token { TokenType = TokenType.RightPar, strVal = "}" };
         } else if (str[pos] == '=') {
           pos++;
@@ -360 +379 @@
     }
 
-    /// Fact          = '(' Expr ')' 
-    ///                 | 'LAG' '(' varId ',' ['+' | '-' ] number ')' 
-    ///                 | funcId '(' ArgList ')' 
-    ///                 | VarExpr | number
+    // Fact = SimpleFact ['^' SimpleFact]
+    private ISymbolicExpressionTreeNode ParseFact(Queue<Token> tokens) {
+      var expr = ParseSimpleFact(tokens);
+      var next = tokens.Peek();
+      if (next.TokenType == TokenType.Operator && next.strVal == "^") {
+        tokens.Dequeue(); // skip;
+
+        var p = GetSymbol("^").CreateTreeNode();
+        p.AddSubtree(expr);
+        p.AddSubtree(ParseSimpleFact(tokens));
+        expr = p;
+      }
+      return expr;
+    }
+
+
+    /// SimpleFact   = '(' Expr ')' 
+    ///                 | '{' Expr '}'
+    ///                 | 'LAG' '(' varId ',' ['+' | '-' ] number ')'
+    ///                 | funcId '(' ArgList ')
+    ///                 | VarExpr
+    ///                 | number
     /// ArgList       = Expr { ',' Expr }
     /// VarExpr       = varId OptFactorPart
@@ -370 +407 @@
     /// varVal        =  ident | ' ident ' | " ident "
     /// ident         =  '_' | letter { '_' | letter | digit }
-    private ISymbolicExpressionTreeNode ParseFact(Queue<Token> tokens) {
+    private ISymbolicExpressionTreeNode ParseSimpleFact(Queue<Token> tokens) {
       var next = tokens.Peek();
       if (next.TokenType == TokenType.LeftPar) {
-        tokens.Dequeue();
+        var initPar = tokens.Dequeue(); // match par type
         var expr = ParseExpr(tokens);
         var rPar = tokens.Dequeue();
         if (rPar.TokenType != TokenType.RightPar)
-          throw new ArgumentException("expected )");
+          throw new ArgumentException("expected closing parenthesis");
+        if (initPar.strVal == "(" && rPar.strVal == "}")
+          throw new ArgumentException("expected closing )");
+        if (initPar.strVal == "{" && rPar.strVal == ")")
+          throw new ArgumentException("expected closing }");
         return expr;
       } else if (next.TokenType == TokenType.Identifier) {
@@ -424 +465 @@
           if (rPar.TokenType != TokenType.RightPar)
             throw new ArgumentException("expected )");
+
 
           return funcNode;

branches/2925_AutoDiffForDynamicalModels/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Importer/SymbolicExpressionImporter.cs

@@ -41 +41 @@
         {"*", new Multiplication()},
         {"-", new Subtraction()},
+        {"ABS", new Absolute() },
         {"EXP", new Exponential()},
         {"LOG", new Logarithm()},
@@ -47 +48 @@
         {"SQR", new Square()},
         {"SQRT", new SquareRoot()},
+        {"CUBE", new Cube()},
+        {"CUBEROOT", new CubeRoot()},
         {"SIN",new Sine()},
         {"COS", new Cosine()},
@@ -65 +68 @@
         {"DAWSON", new Dawson()},
         {"EXPINT", new ExponentialIntegralEi()},
+        {"AQ", new AnalyticQuotient() },
         {"MEAN", new Average()},
         {"IF", new IfThenElse()},

branches/2925_AutoDiffForDynamicalModels/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/OpCodes.cs

@@ -46 +46 @@
     public const byte OR = 14;
     public const byte NOT = 15;
-    public const byte XOR = 45;
 
 
@@ -83 +82 @@
     public const byte Erf = 43;
     public const byte Bessel = 44;
+    public const byte XOR = 45;
     public const byte FactorVariable = 46;
     public const byte BinaryFactorVariable = 47;
+    public const byte Absolute = 48;
+    public const byte AnalyticQuotient = 49;
+    public const byte Cube = 50;
+    public const byte CubeRoot = 51;
 
 
@@ -113 +117 @@
       { typeof(Power),OpCodes.Power},
       { typeof(Root),OpCodes.Root},
-      { typeof(TimeLag), OpCodes.TimeLag}, 
+      { typeof(TimeLag), OpCodes.TimeLag},
       { typeof(Integral), OpCodes.Integral},
       { typeof(Derivative), OpCodes.Derivative},
@@ -135 +139 @@
       { typeof(Bessel), OpCodes.Bessel},
       { typeof(FactorVariable), OpCodes.FactorVariable },
-      { typeof(BinaryFactorVariable), OpCodes.BinaryFactorVariable }
+      { typeof(BinaryFactorVariable), OpCodes.BinaryFactorVariable },
+      { typeof(Absolute), OpCodes.Absolute },
+      { typeof(AnalyticQuotient), OpCodes.AnalyticQuotient },
+      { typeof(Cube), OpCodes.Cube },
+      { typeof(CubeRoot), OpCodes.CubeRoot }
     };
 

branches/2925_AutoDiffForDynamicalModels/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionCompiledTreeInterpreter.cs

@@ -41 +41 @@
 
     #region method info for the commonly called functions
+    private static readonly MethodInfo Abs = typeof(Math).GetMethod("Abs", new[] { typeof(double) });
     private static readonly MethodInfo Sin = typeof(Math).GetMethod("Sin", new[] { typeof(double) });
     private static readonly MethodInfo Cos = typeof(Math).GetMethod("Cos", new[] { typeof(double) });
@@ -207 +208 @@
             return Expression.Divide(result, Expression.Constant((double)node.SubtreeCount));
           }
+        case OpCodes.Absolute: {
+            var arg = MakeExpr(node.GetSubtree(0), variableIndices, row, columns);
+            return Expression.Call(Abs, arg);
+          }
         case OpCodes.Cos: {
             var arg = MakeExpr(node.GetSubtree(0), variableIndices, row, columns);
@@ -222 +227 @@
             var arg = MakeExpr(node.GetSubtree(0), variableIndices, row, columns);
             return Expression.Power(arg, Expression.Constant(2.0));
+          }
+        case OpCodes.Cube: {
+            var arg = MakeExpr(node.GetSubtree(0), variableIndices, row, columns);
+            return Expression.Power(arg, Expression.Constant(3.0));
           }
         case OpCodes.Power: {
@@ -231 +240 @@
             var arg = MakeExpr(node.GetSubtree(0), variableIndices, row, columns);
             return Expression.Call(Sqrt, arg);
+          }
+        case OpCodes.CubeRoot: {
+            var arg = MakeExpr(node.GetSubtree(0), variableIndices, row, columns);
+            return Expression.Power(arg, Expression.Constant(1.0 / 3.0));
           }
         case OpCodes.Root: {
@@ -493 +506 @@
                 Expression.Assign(result, Expression.Call(Bessel, arg))),
               result);
+          }
+        case OpCodes.AnalyticQuotient: {
+            var x1 = MakeExpr(node.GetSubtree(0), variableIndices, row, columns);
+            var x2 = MakeExpr(node.GetSubtree(1), variableIndices, row, columns);
+            return Expression.Divide(x1, 
+              Expression.Call(Sqrt, 
+              Expression.Add(
+                Expression.Constant(1.0),
+                Expression.Multiply(x2, x2))));
           }
         case OpCodes.IfThenElse: {

branches/2925_AutoDiffForDynamicalModels/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeILEmittingInterpreter.cs

@@ -50 +50 @@
     private static MethodInfo round = typeof(Math).GetMethod("Round", new Type[] { typeof(double) });
     private static MethodInfo sqrt = typeof(Math).GetMethod("Sqrt", new Type[] { typeof(double) });
+    private static MethodInfo abs = typeof(Math).GetMethod("Abs", new Type[] { typeof(double) });
 
     private static MethodInfo airyA = thisType.GetMethod("AiryA", new Type[] { typeof(double) });
@@ -264 +265 @@
             return;
           }
+        case OpCodes.Absolute: {
+            CompileInstructions(il, state, ds);
+            il.Emit(System.Reflection.Emit.OpCodes.Call, abs);
+            return;
+          }
         case OpCodes.Cos: {
             CompileInstructions(il, state, ds);
@@ -311 +317 @@
             return;
           }
+        case OpCodes.Cube: {
+            CompileInstructions(il, state, ds);
+            il.Emit(System.Reflection.Emit.OpCodes.Ldc_R8, 3.0);
+            il.Emit(System.Reflection.Emit.OpCodes.Call, power);
+            return;
+          }
         case OpCodes.SquareRoot: {
             CompileInstructions(il, state, ds);
@@ -316 +328 @@
             return;
           }
+        case OpCodes.CubeRoot: {
+            CompileInstructions(il, state, ds);
+            il.Emit(System.Reflection.Emit.OpCodes.Ldc_R8, 1.0 / 3.0);
+            il.Emit(System.Reflection.Emit.OpCodes.Call, power);
+            return;
+          }
         case OpCodes.AiryA: {
             CompileInstructions(il, state, ds);
@@ -389 +407 @@
             CompileInstructions(il, state, ds);
             il.Emit(System.Reflection.Emit.OpCodes.Call, sinIntegral);
+            return;
+          }
+        case OpCodes.AnalyticQuotient: {
+            CompileInstructions(il, state, ds); // x1
+            CompileInstructions(il, state, ds); // x2
+
+            il.Emit(System.Reflection.Emit.OpCodes.Dup);
+            il.Emit(System.Reflection.Emit.OpCodes.Mul); // x2*x2
+            il.Emit(System.Reflection.Emit.OpCodes.Ldc_R8, 1.0);
+            il.Emit(System.Reflection.Emit.OpCodes.Mul); // 1+x2*x2
+            il.Emit(System.Reflection.Emit.OpCodes.Call, sqrt);
+            il.Emit(System.Reflection.Emit.OpCodes.Div);
             return;
           }

branches/2925_AutoDiffForDynamicalModels/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeInterpreter.cs

@@ -203 +203 @@
             return sum / currentInstr.nArguments;
           }
+        case OpCodes.Absolute: {
+            return Math.Abs(Evaluate(dataset, ref row, state));
+          }
         case OpCodes.Cos: {
             return Math.Cos(Evaluate(dataset, ref row, state));
@@ -214 +217 @@
         case OpCodes.Square: {
             return Math.Pow(Evaluate(dataset, ref row, state), 2);
+          }
+        case OpCodes.Cube: {
+            return Math.Pow(Evaluate(dataset, ref row, state), 3);
           }
         case OpCodes.Power: {
@@ -223 +229 @@
             return Math.Sqrt(Evaluate(dataset, ref row, state));
           }
+        case OpCodes.CubeRoot: {
+            return Math.Pow(Evaluate(dataset, ref row, state), 1.0 / 3.0);
+          }
         case OpCodes.Root: {
             double x = Evaluate(dataset, ref row, state);
@@ -340 +349 @@
             if (double.IsNaN(x)) return double.NaN;
             else return alglib.besseli0(x);
+          }
+
+        case OpCodes.AnalyticQuotient: {
+            var x1 = Evaluate(dataset, ref row, state);
+            var x2 = Evaluate(dataset, ref row, state);
+            return x1 / Math.Pow(1 + x2 * x2, 0.5);
           }
         case OpCodes.IfThenElse: {

branches/2925_AutoDiffForDynamicalModels/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/SymbolicDataAnalysisExpressionTreeLinearInterpreter.cs

@@ -215 +215 @@
           if (instr.nArguments == 1) p = 1.0 / p;
           instr.value = p;
+        } else if (instr.opCode == OpCodes.AnalyticQuotient) {
+          var x1 = code[instr.childIndex].value;
+          var x2 = code[instr.childIndex + 1].value;
+          instr.value = x1 / Math.Sqrt(1 + x2 * x2);
         } else if (instr.opCode == OpCodes.Average) {
           double s = code[instr.childIndex].value;
@@ -221 +225 @@
           }
           instr.value = s / instr.nArguments;
+        } else if (instr.opCode == OpCodes.Absolute) {
+          instr.value = Math.Abs(code[instr.childIndex].value);
         } else if (instr.opCode == OpCodes.Cos) {
           instr.value = Math.Cos(code[instr.childIndex].value);
@@ -229 +235 @@
         } else if (instr.opCode == OpCodes.Square) {
           instr.value = Math.Pow(code[instr.childIndex].value, 2);
+        } else if (instr.opCode == OpCodes.Cube) {
+          instr.value = Math.Pow(code[instr.childIndex].value, 3);
         } else if (instr.opCode == OpCodes.Power) {
           double x = code[instr.childIndex].value;
@@ -235 +243 @@
         } else if (instr.opCode == OpCodes.SquareRoot) {
           instr.value = Math.Sqrt(code[instr.childIndex].value);
+        } else if (instr.opCode == OpCodes.CubeRoot) {
+          instr.value = Math.Pow(code[instr.childIndex].value, 1.0 / 3.0);
         } else if (instr.opCode == OpCodes.Root) {
           double x = code[instr.childIndex].value;

branches/2925_AutoDiffForDynamicalModels/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Plugin.cs.frame

@@ -37 +37 @@
   [PluginDependency("HeuristicLab.Data", "3.3")]
   [PluginDependency("HeuristicLab.Encodings.SymbolicExpressionTreeEncoding", "3.4")]
+  [PluginDependency("HeuristicLab.NativeInterpreter", "0.1")]
   [PluginDependency("HeuristicLab.Operators", "3.3")]
   [PluginDependency("HeuristicLab.Optimization", "3.3")]

branches/2925_AutoDiffForDynamicalModels/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisModel.cs

@@ -34 +34 @@
   /// </summary>
   [StorableClass]
-  public abstract class SymbolicDataAnalysisModel : NamedItem, ISymbolicDataAnalysisModel {
+  public abstract class SymbolicDataAnalysisModel : DataAnalysisModel, ISymbolicDataAnalysisModel {
     public static new Image StaticItemImage {
       get { return HeuristicLab.Common.Resources.VSImageLibrary.Function; }
@@ -59 +59 @@
     }
 
-    public IEnumerable<string> VariablesUsedForPrediction {
+    public override IEnumerable<string> VariablesUsedForPrediction {
       get {
         var variables =
@@ -118 +118 @@
       ConstantTreeNode alphaTreeNode = null;
       ConstantTreeNode betaTreeNode = null;
-      // check if model has been scaled previously by analyzing the structure of the tree
+      // check if model has a structure that can be re-used for scaling
       var startNode = SymbolicExpressionTree.Root.GetSubtree(0);
-      if (startNode.GetSubtree(0).Symbol is Addition) {
-        var addNode = startNode.GetSubtree(0);
-        if (addNode.SubtreeCount == 2 && addNode.GetSubtree(0).Symbol is Multiplication && addNode.GetSubtree(1).Symbol is Constant) {
-          alphaTreeNode = addNode.GetSubtree(1) as ConstantTreeNode;
-          var mulNode = addNode.GetSubtree(0);
-          if (mulNode.SubtreeCount == 2 && mulNode.GetSubtree(1).Symbol is Constant) {
-            betaTreeNode = mulNode.GetSubtree(1) as ConstantTreeNode;
-          }
+      var addNode = startNode.GetSubtree(0);
+      if (addNode.Symbol is Addition && addNode.SubtreeCount == 2) {
+        alphaTreeNode = (ConstantTreeNode)addNode.Subtrees.LastOrDefault(n => n is ConstantTreeNode);
+        var mulNode = addNode.Subtrees.FirstOrDefault(n => n.Symbol is Multiplication);
+        if (mulNode != null) {
+          betaTreeNode = (ConstantTreeNode)mulNode.Subtrees.LastOrDefault(n => n is ConstantTreeNode);
         }
       }

branches/2925_AutoDiffForDynamicalModels/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/SymbolicExpressionTreeBottomUpSimilarityCalculator.cs

@@ -22 +22 @@
 using System;
 using System.Collections.Generic;
-using System.Diagnostics;
 using System.Globalization;
 using System.Linq;
@@ -31 +30 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
+using NodeMap = System.Collections.Generic.Dictionary<HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode>;
+
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
   [StorableClass]
@@ -40 +41 @@
     protected override bool IsCommutative { get { return true; } }
 
+    public bool MatchConstantValues { get; set; }
+    public bool MatchVariableWeights { get; set; }
+
     [StorableConstructor]
     protected SymbolicExpressionTreeBottomUpSimilarityCalculator(bool deserializing)
@@ -53 +57 @@
     }
 
+    #region static methods
+    private static ISymbolicExpressionTreeNode ActualRoot(ISymbolicExpressionTree tree) {
+      return tree.Root.GetSubtree(0).GetSubtree(0);
+    }
+
+    public static double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, bool strict = false) {
+      return CalculateSimilarity(ActualRoot(t1), ActualRoot(t2), strict);
+    }
+
+    public static double CalculateSimilarity(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2, bool strict = false) {
+      var calculator = new SymbolicExpressionTreeBottomUpSimilarityCalculator { MatchConstantValues = strict, MatchVariableWeights = strict };
+      return CalculateSimilarity(n1, n2, strict);
+    }
+
+    public static Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, bool strict = false) {
+      return ComputeBottomUpMapping(ActualRoot(t1), ActualRoot(t2), strict);
+    }
+
+    public static Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2, bool strict = false) {
+      var calculator = new SymbolicExpressionTreeBottomUpSimilarityCalculator { MatchConstantValues = strict, MatchVariableWeights = strict };
+      return calculator.ComputeBottomUpMapping(n1, n2);
+    }
+    #endregion
+
     public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
-      if (t1 == t2)
+      return CalculateSimilarity(t1, t2, out Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> map);
+    }
+
+    public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, out NodeMap map) {
+      if (t1 == t2) {
+        map = null;
         return 1;
-
-      var map = ComputeBottomUpMapping(t1.Root, t2.Root);
-      return 2.0 * map.Count / (t1.Length + t2.Length);
+      }
+      map = ComputeBottomUpMapping(t1, t2);
+      return 2.0 * map.Count / (t1.Length + t2.Length - 4); // -4 for skipping root and start symbols in the two trees
     }
 
@@ -78 +111 @@
     }
 
+    public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
+      return ComputeBottomUpMapping(t1.Root.GetSubtree(0).GetSubtree(0), t2.Root.GetSubtree(0).GetSubtree(0));
+    }
+
     public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) {
-      var comparer = new SymbolicExpressionTreeNodeComparer(); // use a node comparer because it's faster than calling node.ToString() (strings are expensive) and comparing strings
       var compactedGraph = Compact(n1, n2);
 
-      var forwardMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t1 => nodes of t2
-      var reverseMap = new Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode>(); // nodes of t2 => nodes of t1
-
-      // visit nodes in order of decreasing height to ensure correct mapping
-      var nodes1 = n1.IterateNodesPrefix().OrderByDescending(x => x.GetDepth()).ToList();
-      var nodes2 = n2.IterateNodesPrefix().ToList();
-      for (int i = 0; i < nodes1.Count; ++i) {
-        var v = nodes1[i];
-        if (forwardMap.ContainsKey(v))
+      IEnumerable<ISymbolicExpressionTreeNode> Subtrees(ISymbolicExpressionTreeNode node, bool commutative) {
+        var subtrees = node.IterateNodesPrefix();
+        return commutative ? subtrees.OrderBy(x => compactedGraph[x].Hash) : subtrees;
+      }
+
+      var nodes1 = n1.IterateNodesPostfix().OrderByDescending(x => x.GetLength()); // by descending length so that largest subtrees are mapped first
+      var nodes2 = (List<ISymbolicExpressionTreeNode>)n2.IterateNodesPostfix();
+
+      var forward = new NodeMap();
+      var reverse = new NodeMap();
+
+      foreach (ISymbolicExpressionTreeNode v in nodes1) {
+        if (forward.ContainsKey(v))
           continue;
+
         var kv = compactedGraph[v];
-        ISymbolicExpressionTreeNode w = null;
-        for (int j = 0; j < nodes2.Count; ++j) {
-          var t = nodes2[j];
-          if (reverseMap.ContainsKey(t) || compactedGraph[t] != kv)
+        var commutative = v.SubtreeCount > 1 && commutativeSymbols.Contains(kv.Label);
+
+        foreach (ISymbolicExpressionTreeNode w in nodes2) {
+          if (w.GetLength() != kv.Length || w.GetDepth() != kv.Depth || reverse.ContainsKey(w) || compactedGraph[w] != kv)
             continue;
-          w = t;
+
+          // map one whole subtree to the other
+          foreach (var t in Subtrees(v, commutative).Zip(Subtrees(w, commutative), Tuple.Create)) {
+            forward[t.Item1] = t.Item2;
+            reverse[t.Item2] = t.Item1;
+          }
+
           break;
         }
-        if (w == null) continue;
-
-        // at this point we know that v and w are isomorphic, however, the mapping cannot be done directly
-        // (as in the paper) because the trees are unordered (subtree order might differ). the solution is 
-        // to sort subtrees from under commutative labels (this will work because the subtrees are isomorphic!)
-        // while iterating over the two subtrees
-        var vv = IterateBreadthOrdered(v, comparer).ToList();
-        var ww = IterateBreadthOrdered(w, comparer).ToList();
-        int len = Math.Min(vv.Count, ww.Count);
-        for (int j = 0; j < len; ++j) {
-          var s = vv[j];
-          var t = ww[j];
-          Debug.Assert(!reverseMap.ContainsKey(t));
-
-          forwardMap[s] = t;
-          reverseMap[t] = s;
-        }
-      }
-
-      return forwardMap;
+      }
+
+      return forward;
     }
 
@@ -132 +162 @@
       var nodeMap = new Dictionary<ISymbolicExpressionTreeNode, GraphNode>(); // K
       var labelMap = new Dictionary<string, GraphNode>(); // L
-      var childrenCount = new Dictionary<ISymbolicExpressionTreeNode, int>(); // Children
 
       var nodes = n1.IterateNodesPostfix().Concat(n2.IterateNodesPostfix()); // the disjoint union F
-      var list = new List<GraphNode>();
-      var queue = new Queue<ISymbolicExpressionTreeNode>();
-
-      foreach (var n in nodes) {
-        if (n.SubtreeCount == 0) {
-          var label = GetLabel(n);
+      var graph = new List<GraphNode>();
+
+      IEnumerable<GraphNode> Subtrees(GraphNode g, bool commutative) {
+        var subtrees = g.SymbolicExpressionTreeNode.Subtrees.Select(x => nodeMap[x]);
+        return commutative ? subtrees.OrderBy(x => x.Hash) : subtrees;
+      }
+
+      foreach (var node in nodes) {
+        var label = GetLabel(node);
+
+        if (node.SubtreeCount == 0) {
           if (!labelMap.ContainsKey(label)) {
-            var z = new GraphNode { SymbolicExpressionTreeNode = n, Label = label };
-            labelMap[z.Label] = z;
-          }
-          nodeMap[n] = labelMap[label];
-          queue.Enqueue(n);
+            labelMap[label] = new GraphNode(node, label);
+          }
+          nodeMap[node] = labelMap[label];
         } else {
-          childrenCount[n] = n.SubtreeCount;
-        }
-      }
-      while (queue.Any()) {
-        var n = queue.Dequeue();
-        if (n.SubtreeCount > 0) {
+          var v = new GraphNode(node, label);
           bool found = false;
-          var label = n.Symbol.Name;
-          var depth = n.GetDepth();
-
-          bool sort = n.SubtreeCount > 1 && commutativeSymbols.Contains(label);
-          var nSubtrees = n.Subtrees.Select(x => nodeMap[x]).ToList();
-          if (sort) nSubtrees.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
-
-          for (int i = list.Count - 1; i >= 0; --i) {
-            var w = list[i];
-            if (!(n.SubtreeCount == w.SubtreeCount && label == w.Label && depth == w.Depth))
+          var commutative = node.SubtreeCount > 1 && commutativeSymbols.Contains(label);
+
+          var vv = Subtrees(v, commutative);
+
+          foreach (var w in graph) {
+            if (v.Depth != w.Depth || v.SubtreeCount != w.SubtreeCount || v.Length != w.Length || v.Label != w.Label) {
               continue;
-
-            // sort V and W when the symbol is commutative because we are dealing with unordered trees
-            var m = w.SymbolicExpressionTreeNode;
-            var mSubtrees = m.Subtrees.Select(x => nodeMap[x]).ToList();
-            if (sort) mSubtrees.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
-
-            found = nSubtrees.SequenceEqual(mSubtrees);
+            }
+
+            var ww = Subtrees(w, commutative);
+            found = vv.SequenceEqual(ww);
+
             if (found) {
-              nodeMap[n] = w;
+              nodeMap[node] = w;
               break;
             }
           }
-
           if (!found) {
-            var w = new GraphNode { SymbolicExpressionTreeNode = n, Label = label, Depth = depth };
-            list.Add(w);
-            nodeMap[n] = w;
+            nodeMap[node] = v;
+            graph.Add(v);
           }
         }
-
-        if (n == n1 || n == n2)
-          continue;
-
-        var p = n.Parent;
-        if (p == null)
-          continue;
-
-        childrenCount[p]--;
-
-        if (childrenCount[p] == 0)
-          queue.Enqueue(p);
-      }
-
+      }
       return nodeMap;
     }
 
-    private IEnumerable<ISymbolicExpressionTreeNode> IterateBreadthOrdered(ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNodeComparer comparer) {
-      var list = new List<ISymbolicExpressionTreeNode> { node };
-      int i = 0;
-      while (i < list.Count) {
-        var n = list[i];
-        if (n.SubtreeCount > 0) {
-          var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(x => x, comparer) : n.Subtrees;
-          list.AddRange(subtrees);
-        }
-        i++;
-      }
-      return list;
-    }
-
-    private static string GetLabel(ISymbolicExpressionTreeNode node) {
+    private string GetLabel(ISymbolicExpressionTreeNode node) {
       if (node.SubtreeCount > 0)
         return node.Symbol.Name;
 
-      var constant = node as ConstantTreeNode;
-      if (constant != null)
-        return constant.Value.ToString(CultureInfo.InvariantCulture);
-
-      var variable = node as VariableTreeNode;
-      if (variable != null)
-        return variable.Weight + variable.VariableName;
+      if (node is ConstantTreeNode constant)
+        return MatchConstantValues ? constant.Value.ToString(CultureInfo.InvariantCulture) : constant.Symbol.Name;
+
+      if (node is VariableTreeNode variable)
+        return MatchVariableWeights ? variable.Weight + variable.VariableName : variable.VariableName;
 
       return node.ToString();
@@ -232 +222 @@
 
     private class GraphNode {
-      public ISymbolicExpressionTreeNode SymbolicExpressionTreeNode;
-      public string Label;
-      public int Depth;
+      private GraphNode() { }
+
+      public GraphNode(ISymbolicExpressionTreeNode node, string label) {
+        SymbolicExpressionTreeNode = node;
+        Label = label;
+        Hash = GetHashCode();
+        Depth = node.GetDepth();
+        Length = node.GetLength();
+      }
+
+      public int Hash { get; }
+      public ISymbolicExpressionTreeNode SymbolicExpressionTreeNode { get; }
+      public string Label { get; }
+      public int Depth { get; }
       public int SubtreeCount { get { return SymbolicExpressionTreeNode.SubtreeCount; } }
+      public int Length { get; }
     }
   }