Changeset 17066


Ignore:
Timestamp:
07/04/19 15:15:58 (2 weeks ago)
Author:
mkommend
Message:

#2948: Merged 16206, 16207, 16213, 16216, 16294 to stable.

Location:
stable
Files:
3 edited
2 copied

Legend:

Unmodified
Added
Removed
  • stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/DerivativeCalculator.cs

    r16207 r17066  
    2121
    2222using System;
     23using System.Collections.Generic;
    2324using System.Linq;
    2425using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
     
    2728  public static class DerivativeCalculator {
    2829    public static ISymbolicExpressionTree Derive(ISymbolicExpressionTree tree, string variableName) {
     30      if (tree.Root.SubtreeCount != 1)
     31        throw new NotImplementedException("Derive is not implemented for symbolic expressions with automatically defined functions (ADF)");
     32      if (tree.Root.GetSubtree(0).SubtreeCount != 1)
     33        throw new NotImplementedException("Derive is not implemented for multi-variate symbolic expressions");
    2934      var mainBranch = tree.Root.GetSubtree(0).GetSubtree(0);
    3035      var root = new ProgramRootSymbol().CreateTreeNode();
    3136      root.AddSubtree(new StartSymbol().CreateTreeNode());
    3237      var dTree = TreeSimplifier.GetSimplifiedTree(Derive(mainBranch, variableName));
    33       // var dTree = Derive(mainBranch, variableName);
     38      //var dTree = Derive(mainBranch, variableName);
    3439      root.GetSubtree(0).AddSubtree(dTree);
    3540      return new SymbolicExpressionTree(root);
    3641    }
    3742
    38     private static Constant constantSy = new Constant();
    39     private static Addition addSy = new Addition();
    40     private static Subtraction subSy = new Subtraction();
    41     private static Multiplication mulSy = new Multiplication();
    42     private static Division divSy = new Division();
     43    private static readonly Constant constantSy = new Constant();
     44    private static readonly Addition addSy = new Addition();
     45    private static readonly Subtraction subSy = new Subtraction();
     46    private static readonly Multiplication mulSy = new Multiplication();
     47    private static readonly Division divSy = new Division();
     48    private static readonly Cosine cosSy = new Cosine();
     49    private static readonly Square sqrSy = new Square();
    4350
    4451    public static ISymbolicExpressionTreeNode Derive(ISymbolicExpressionTreeNode branch, string variableName) {
     
    8592          }
    8693          return fgPrime;
    87         } else throw new ArgumentException();
     94        } else
     95          // multiplication with only one argument has no effect -> derive the argument
     96          return Derive(branch.GetSubtree(0), variableName);
    8897      }
    8998      if (branch.Symbol is Division) {
     
    95104          sqrNode.AddSubtree(g);
    96105          return Div(gPrime, sqrNode);
    97         } else if (branch.SubtreeCount == 2) {
     106        } else {
     107          // for two subtrees:
     108          // (f/g)' = (f'g - fg')/g²
     109
     110          // if there are more than 2 subtrees
     111          // div(x,y,z) is interpretered as (x/y)/z
     112          // which is the same as x / (y*z)
     113
     114          // --> make a product of all but the first subtree and differentiate as for the 2-argument case above
    98115          var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
    99           var g = (ISymbolicExpressionTreeNode)branch.GetSubtree(1).Clone();
     116          var g = Product(branch.Subtrees.Skip(1).Select(n => (ISymbolicExpressionTreeNode)n.Clone()));
    100117          var fprime = Derive(f, variableName);
    101118          var gprime = Derive(g, variableName);
    102           var sqrNode = new Square().CreateTreeNode();
    103           sqrNode.AddSubtree((ISymbolicExpressionTreeNode)branch.GetSubtree(1).Clone());
    104           return Div(Subtract(Product(fprime, g), Product(f, gprime)), sqrNode);
    105         } else throw new NotSupportedException();
     119          var gSqr = Square(g);
     120          return Div(Subtract(Product(fprime, g), Product(f, gprime)), gSqr);
     121        }
    106122      }
    107123      if (branch.Symbol is Logarithm) {
     
    113129        return Product(f, Derive(branch.GetSubtree(0), variableName));
    114130      }
    115       if(branch.Symbol is Square) {
     131      if (branch.Symbol is Square) {
    116132        var f = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
    117133        return Product(Product(CreateConstant(2.0), f), Derive(f, variableName));
    118       }     
    119       if(branch.Symbol is SquareRoot) {
     134      }
     135      if (branch.Symbol is SquareRoot) {
    120136        var f = (ISymbolicExpressionTreeNode)branch.Clone();
    121137        var u = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
    122         return Div(CreateConstant(1.0), Product(Product(CreateConstant(2.0), f), Derive(u, variableName)));
     138        return Product(Div(CreateConstant(1.0), Product(CreateConstant(2.0), f)), Derive(u, variableName));
    123139      }
    124140      if (branch.Symbol is Sine) {
     
    134150        return Product(CreateConstant(-1.0), Product(sin, Derive(u, variableName)));
    135151      }
    136       throw new NotSupportedException($"Symbol {branch.Symbol} is not supported.");
     152      if (branch.Symbol is Tangent) {
     153        // tan(x)' = 1 / cos²(x)
     154        var fxp = Derive(branch.GetSubtree(0), variableName);
     155        var u = (ISymbolicExpressionTreeNode)branch.GetSubtree(0).Clone();
     156        return Div(fxp, Square(Cosine(u)));
     157      }
     158      throw new NotSupportedException(string.Format("Symbol {0} is not supported.", branch.Symbol));
    137159    }
    138160
     
    144166      return product;
    145167    }
     168    private static ISymbolicExpressionTreeNode Product(IEnumerable<ISymbolicExpressionTreeNode> fs) {
     169      var product = mulSy.CreateTreeNode();
     170      foreach (var f in fs) product.AddSubtree(f);
     171      return product;
     172    }
    146173    private static ISymbolicExpressionTreeNode Div(ISymbolicExpressionTreeNode f, ISymbolicExpressionTreeNode g) {
    147174      var div = divSy.CreateTreeNode();
     
    163190      return sum;
    164191    }
    165                          
     192    private static ISymbolicExpressionTreeNode Cosine(ISymbolicExpressionTreeNode f) {
     193      var cos = cosSy.CreateTreeNode();
     194      cos.AddSubtree(f);
     195      return cos;
     196    }
     197    private static ISymbolicExpressionTreeNode Square(ISymbolicExpressionTreeNode f) {
     198      var sqr = sqrSy.CreateTreeNode();
     199      sqr.AddSubtree(f);
     200      return sqr;
     201    }
     202
    166203    private static ISymbolicExpressionTreeNode CreateConstant(double v) {
    167204      var constNode = (ConstantTreeNode)constantSy.CreateTreeNode();
     
    186223          !(n.Symbol is Sine) &&
    187224          !(n.Symbol is Cosine) &&
     225          !(n.Symbol is Tangent) &&
    188226          !(n.Symbol is StartSymbol)
    189227        select n).Any();
  • stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/TreeSimplifier.cs

    r15584 r17066  
    11211121        // $ * 1.0 => $
    11221122        return a;
     1123      } else if (IsConstant(b) && ((ConstantTreeNode)b).Value.IsAlmost(0.0)) {
     1124        return MakeConstant(0);
    11231125      } else if (IsConstant(b) && IsVariableBase(a)) {
    11241126        // multiply constants into variables weights
  • stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

    r16436 r17066  
    139139    <Compile Include="Converters\LinearModelToTreeConverter.cs" />
    140140    <Compile Include="Converters\TreeSimplifier.cs" />
     141    <Compile Include="Converters\DerivativeCalculator.cs" />
    141142    <Compile Include="Converters\TreeToAutoDiffTermConverter.cs" />
    142143    <Compile Include="Formatters\InfixExpressionFormatter.cs" />
  • stable/HeuristicLab.Tests/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4/DeriveTest.cs

    r16207 r17066  
    3535      var formatter = new InfixExpressionFormatter();
    3636      var parser = new InfixExpressionParser();
    37       Console.WriteLine(Derive("3", "x"));
    38       Console.WriteLine(Derive("x", "x"));
    39       Console.WriteLine(Derive("10*x", "x"));
    40       Console.WriteLine(Derive("x*10", "x"));
    41       Console.WriteLine(Derive("x*x", "x"));
    42       Console.WriteLine(Derive("x*x*x", "x"));
    43       Console.WriteLine(Derive("10*x", "y"));
    44       Console.WriteLine(Derive("10*x+20*y", "y"));
    45       Console.WriteLine(Derive("2*3*x", "x"));
    46       Console.WriteLine(Derive("10*x*y+20*y", "x"));
    47       Console.WriteLine(Derive("1/x", "x"));
    48       Console.WriteLine(Derive("y/x", "x"));
    49       Console.WriteLine(Derive("(a+b)/(x+x*x)", "x"));
    50       Console.WriteLine(Derive("(a+b)/(x+SQR(x))", "x"));
    51       Console.WriteLine(Derive("exp(x)", "x"));
    52       Console.WriteLine(Derive("exp(3*x)", "x"));
    53       Console.WriteLine(Derive("log(x)", "x"));
    54       Console.WriteLine(Derive("log(3*x)", "x"));
    55       Console.WriteLine(Derive("log(3*x+y)", "x"));
    56       Console.WriteLine(Derive("sqrt(3*x+y)", "x"));
    57       Console.WriteLine(Derive("sin(3*x)", "x"));
    58       Console.WriteLine(Derive("cos(3*x)", "x"));
     37      Assert.AreEqual("0", Derive("3", "x"));
     38      Assert.AreEqual("1", Derive("x", "x"));
     39      Assert.AreEqual("10", Derive("10*x", "x"));
     40      Assert.AreEqual("10", Derive("x*10", "x"));
     41      Assert.AreEqual("(2*'x')", Derive("x*x", "x"));
     42      Assert.AreEqual("((('x' * 'x') * 2) + ('x' * 'x'))", Derive("x*x*x", "x")); // simplifier does not merge (x*x)*2 + x*x  to 3*x*x
     43      Assert.AreEqual("0", Derive("10*x", "y"));
     44      Assert.AreEqual("20", Derive("10*x+20*y", "y"));
     45      Assert.AreEqual("6", Derive("2*3*x", "x"));
     46      Assert.AreEqual("(10*'y')", Derive("10*x*y+20*y", "x"));
     47      Assert.AreEqual("(1 / (SQR('x') * (-1)))", Derive("1/x", "x"));
     48      Assert.AreEqual("('y' / (SQR('x') * (-1)))", Derive("y/x", "x"));
     49      Assert.AreEqual("((((-2*'x') + (-1)) * ('a' + 'b')) / SQR(('x' + ('x' * 'x'))))",
     50        Derive("(a+b)/(x+x*x)", "x"));
     51      Assert.AreEqual("((((-2*'x') + (-1)) * ('a' + 'b')) / SQR(('x' + SQR('x'))))", Derive("(a+b)/(x+SQR(x))", "x"));
     52      Assert.AreEqual("EXP('x')", Derive("exp(x)", "x"));
     53      Assert.AreEqual("(EXP((3*'x')) * 3)", Derive("exp(3*x)", "x"));
     54      Assert.AreEqual("(1 / 'x')", Derive("log(x)", "x"));
     55      Assert.AreEqual("(1 / 'x')", Derive("log(3*x)", "x"));   // 3 * 1/(3*x)
     56      Assert.AreEqual("(1 / ('x' + (0.333333333333333*'y')))", Derive("log(3*x+y)", "x"));  // simplifier does not try to keep fractions
     57      Assert.AreEqual("(1 / (SQRT(((3*'x') + 'y')) * 0.666666666666667))", Derive("sqrt(3*x+y)", "x"));   // 3 / (2 * sqrt(3*x+y)) = 1 / ((2/3) * sqrt(3*x+y))
     58      Assert.AreEqual("(COS((3*'x')) * 3)", Derive("sin(3*x)", "x"));
     59      Assert.AreEqual("(SIN((3*'x')) * (-3))", Derive("cos(3*x)", "x"));
     60      Assert.AreEqual("(1 / (SQR(COS((3*'x'))) * 0.333333333333333))", Derive("tan(3*x)", "x")); // diff(tan(f(x)), x) = 1.0 / cos²(f(x)), simplifier puts constant factor into the denominator
    5961
    60       // special case: Inv(x) using only one argument to the division symbol
    61       var root = new ProgramRootSymbol().CreateTreeNode();
    62       var start = new StartSymbol().CreateTreeNode();
    63       var div = new Division().CreateTreeNode();
    64       var varNode = (VariableTreeNode)(new Variable().CreateTreeNode());
    65       varNode.Weight = 1.0;
    66       varNode.VariableName = "x";
    67       div.AddSubtree(varNode);
    68       start.AddSubtree(div);
    69       root.AddSubtree(start);
    70       var t = new SymbolicExpressionTree(root);
    71       Console.WriteLine(formatter.Format(DerivativeCalculator.Derive(t, "x")));
     62      {
     63        // special case: Inv(x) using only one argument to the division symbol
     64        // f(x) = 1/x
     65        var root = new ProgramRootSymbol().CreateTreeNode();
     66        var start = new StartSymbol().CreateTreeNode();
     67        var div = new Division().CreateTreeNode();
     68        var varNode = (VariableTreeNode)(new Variable().CreateTreeNode());
     69        varNode.Weight = 1.0;
     70        varNode.VariableName = "x";
     71        div.AddSubtree(varNode);
     72        start.AddSubtree(div);
     73        root.AddSubtree(start);
     74        var t = new SymbolicExpressionTree(root);
     75        Assert.AreEqual("(1 / (SQR('x') * (-1)))",
     76          formatter.Format(DerivativeCalculator.Derive(t, "x")));
     77      }
     78
     79      {
     80        // special case: multiplication with only one argument
     81        var root = new ProgramRootSymbol().CreateTreeNode();
     82        var start = new StartSymbol().CreateTreeNode();
     83        var mul = new Multiplication().CreateTreeNode();
     84        var varNode = (VariableTreeNode)(new Variable().CreateTreeNode());
     85        varNode.Weight = 3.0;
     86        varNode.VariableName = "x";
     87        mul.AddSubtree(varNode);
     88        start.AddSubtree(mul);
     89        root.AddSubtree(start);
     90        var t = new SymbolicExpressionTree(root);
     91        Assert.AreEqual("3",
     92          formatter.Format(DerivativeCalculator.Derive(t, "x")));
     93      }
     94
     95      {
     96        // division with multiple arguments
     97        // div(x, y, z) is interpreted as (x / y) / z
     98        var root = new ProgramRootSymbol().CreateTreeNode();
     99        var start = new StartSymbol().CreateTreeNode();
     100        var div = new Division().CreateTreeNode();
     101        var varNode1 = (VariableTreeNode)(new Variable().CreateTreeNode());
     102        varNode1.Weight = 3.0;
     103        varNode1.VariableName = "x";
     104        var varNode2 = (VariableTreeNode)(new Variable().CreateTreeNode());
     105        varNode2.Weight = 4.0;
     106        varNode2.VariableName = "y";
     107        var varNode3 = (VariableTreeNode)(new Variable().CreateTreeNode());
     108        varNode3.Weight = 5.0;
     109        varNode3.VariableName = "z";
     110        div.AddSubtree(varNode1); div.AddSubtree(varNode2); div.AddSubtree(varNode3);
     111        start.AddSubtree(div);
     112        root.AddSubtree(start);
     113        var t = new SymbolicExpressionTree(root);
     114
     115        Assert.AreEqual("(('y' * 'z' * 60) / SQR(('y' * 'z' * 20)))", // actually 3 / (4y  5z) but simplifier is not smart enough to cancel numerator and denominator
     116                                                                      // 60 y z / y² z² 20² == 6 / y z 40 == 3 / y z 20
     117          formatter.Format(DerivativeCalculator.Derive(t, "x")));
     118        Assert.AreEqual("(('x' * 'z' * (-60)) / SQR(('y' * 'z' * 20)))", // actually 3x * -(4 5 z) / (4y 5z)² = -3x / (20 y² z)
     119                                                                         // -3 4 5 x z / 4² y² 5² z² = -60 x z / 20² z² y² ==    -60 x z / y² z² 20²
     120          formatter.Format(DerivativeCalculator.Derive(t, "y")));
     121        Assert.AreEqual("(('x' * 'y' * (-60)) / SQR(('y' * 'z' * 20)))",
     122          formatter.Format(DerivativeCalculator.Derive(t, "z")));
     123      }
    72124    }
    73125
  • stable/HeuristicLab.Tests/HeuristicLab.Tests.csproj

    r16709 r17066  
    594594    <Compile Include="HeuristicLab.Problems.DataAnalysis-3.4\OnlineCalculatorPerformanceTest.cs" />
    595595    <Compile Include="HeuristicLab.Problems.DataAnalysis-3.4\StatisticCalculatorsTest.cs" />
     596    <Compile Include="HeuristicLab.Problems.DataAnalysis.Symbolic-3.4\DeriveTest.cs" />
    596597    <Compile Include="HeuristicLab.Problems.DataAnalysis.Symbolic-3.4\InfixExpressionParserTest.cs" />
    597598    <Compile Include="HeuristicLab.Problems.DataAnalysis.Symbolic-3.4\IntervalInterpreterTest.cs" />
Note: See TracChangeset for help on using the changeset viewer.