Changeset 17726 for branches/3040_VectorBasedGP/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/VectorUnrollingTreeToAutoDiffTermConverter.cs

Timestamp:

08/26/20 16:43:25 (4 years ago)

Author:

pfleck

Message:

#3040 Added a constant opt evaluator for vectors that uses the existing AutoDiff library by unrolling all vector operations.

File:

• branches/3040_VectorBasedGP/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/VectorUnrollingTreeToAutoDiffTermConverter.cs (copied) (copied from branches/3040_VectorBasedGP/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/TreeToAutoDiffTermConverter.cs) (15 diffs)

branches/3040_VectorBasedGP/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/VectorUnrollingTreeToAutoDiffTermConverter.cs

@@ -25 +25 @@
 using System.Runtime.Serialization;
 using AutoDiff;
+using HeuristicLab.Common;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
-  public class TreeToAutoDiffTermConverter {
+  public class VectorUnrollingTreeToAutoDiffTermConverter {
     public delegate double ParametricFunction(double[] vars, double[] @params);
 
@@ -38 +39 @@
       public readonly string variableValue; // for factor vars
       public readonly int lag;
-
-      public DataForVariable(string varName, string varValue, int lag) {
+      public readonly int index; // for vectors
+
+      public DataForVariable(string varName, string varValue, int lag, int index) {
         this.variableName = varName;
         this.variableValue = varValue;
         this.lag = lag;
+        this.index = index;
       }
 
@@ -50 +53 @@
         return other.variableName.Equals(this.variableName) &&
                other.variableValue.Equals(this.variableValue) &&
-               other.lag == this.lag;
+               other.lag == this.lag &&
+               other.index == this.index;
       }
 
       public override int GetHashCode() {
-        return variableName.GetHashCode() ^ variableValue.GetHashCode() ^ lag;
+        return variableName.GetHashCode() ^ variableValue.GetHashCode() ^ lag ^ index;
       }
     }
@@ -101 +105 @@
     #endregion
 
-    public static bool TryConvertToAutoDiff(ISymbolicExpressionTree tree, bool makeVariableWeightsVariable, bool addLinearScalingTerms,
+    public static bool TryConvertToAutoDiff(ISymbolicExpressionTree tree,
+      IDictionary<ISymbolicExpressionTreeNode, SymbolicDataAnalysisExpressionTreeVectorInterpreter.EvaluationResult> evaluationTrace,
+      bool makeVariableWeightsVariable, bool addLinearScalingTerms,
       out List<DataForVariable> parameters, out double[] initialConstants,
       out ParametricFunction func,
@@ -107 +113 @@
 
       // use a transformator object which holds the state (variable list, parameter list, ...) for recursive transformation of the tree
-      var transformator = new TreeToAutoDiffTermConverter(makeVariableWeightsVariable, addLinearScalingTerms);
-      AutoDiff.Term term;
+      var transformator = new VectorUnrollingTreeToAutoDiffTermConverter(evaluationTrace,
+        makeVariableWeightsVariable, addLinearScalingTerms);
+      Term term;
       try {
-        term = transformator.ConvertToAutoDiff(tree.Root.GetSubtree(0));
+        term = transformator.ConvertToAutoDiff(tree.Root.GetSubtree(0)).Single();
         var parameterEntries = transformator.parameters.ToArray(); // guarantee same order for keys and values
         var compiledTerm = term.Compile(transformator.variables.ToArray(),
@@ -128 +135 @@
     }
 
+    private readonly IDictionary<ISymbolicExpressionTreeNode, SymbolicDataAnalysisExpressionTreeVectorInterpreter.EvaluationResult> evaluationTrace;
     // state for recursive transformation of trees 
-    private readonly
-    List<double> initialConstants;
+    private readonly List<double> initialConstants;
     private readonly Dictionary<DataForVariable, AutoDiff.Variable> parameters;
     private readonly List<AutoDiff.Variable> variables;
@@ -136 +143 @@
     private readonly bool addLinearScalingTerms;
 
-    private TreeToAutoDiffTermConverter(bool makeVariableWeightsVariable, bool addLinearScalingTerms) {
+    private VectorUnrollingTreeToAutoDiffTermConverter(IDictionary<ISymbolicExpressionTreeNode, SymbolicDataAnalysisExpressionTreeVectorInterpreter.EvaluationResult> evaluationTrace,
+      bool makeVariableWeightsVariable, bool addLinearScalingTerms) {
+      this.evaluationTrace = evaluationTrace;
       this.makeVariableWeightsVariable = makeVariableWeightsVariable;
       this.addLinearScalingTerms = addLinearScalingTerms;
@@ -144 +153 @@
     }
 
-    private AutoDiff.Term ConvertToAutoDiff(ISymbolicExpressionTreeNode node) {
-      if (node.Symbol is Constant) {
+    private IList<AutoDiff.Term> ConvertToAutoDiff(ISymbolicExpressionTreeNode node) {
+      IList<Term> BinaryOp(Func<Term, Term, Term> binaryOp, Func<Term, Term> singleElementOp, params IList<Term>[] terms) {
+        if (terms.Length == 1) return terms[0].Select(singleElementOp).ToList();
+        return terms.Aggregate((acc, vectorizedTerm) => acc.Zip(vectorizedTerm, binaryOp).ToList());
+      }
+      IList<Term> BinaryOp2(Func<Term, Term, Term> binaryOp, params IList<Term>[] terms) {
+        return terms.Aggregate((acc, vectorizedTerm) => acc.Zip(vectorizedTerm, binaryOp).ToList());
+      }
+      IList<Term> UnaryOp(Func<Term, Term> unaryOp, IList<Term> term) {
+        return term.Select(unaryOp).ToList();
+      }
+
+      var evaluationResult = evaluationTrace[node];
+
+      if (node.Symbol is Constant) { // assume scalar constant
         initialConstants.Add(((ConstantTreeNode)node).Value);
         var var = new AutoDiff.Variable();
         variables.Add(var);
-        return var;
+        return new Term[] { var };
       }
       if (node.Symbol is Variable || node.Symbol is BinaryFactorVariable) {
@@ -156 +178 @@
         // factor variable values are only 0 or 1 and set in x accordingly
         var varValue = factorVarNode != null ? factorVarNode.VariableValue : string.Empty;
-        var par = FindOrCreateParameter(parameters, varNode.VariableName, varValue);
+        var pars = evaluationResult.IsVector
+          ? Enumerable.Range(0, evaluationResult.Vector.Count).Select(i => FindOrCreateParameter(parameters, varNode.VariableName, varValue, index: i))
+          : FindOrCreateParameter(parameters, varNode.VariableName, varValue).ToEnumerable();
 
         if (makeVariableWeightsVariable) {
@@ -162 +186 @@
           var w = new AutoDiff.Variable();
           variables.Add(w);
-          return AutoDiff.TermBuilder.Product(w, par);
+          return pars.Select(par => AutoDiff.TermBuilder.Product(w, par)).ToList();
         } else {
-          return varNode.Weight * par;
+          return pars.Select(par => varNode.Weight * par).ToList();
         }
       }
@@ -179 +203 @@
           products.Add(AutoDiff.TermBuilder.Product(wVar, par));
         }
-        return AutoDiff.TermBuilder.Sum(products);
-      }
-      if (node.Symbol is LaggedVariable) {
-        var varNode = node as LaggedVariableTreeNode;
-        var par = FindOrCreateParameter(parameters, varNode.VariableName, string.Empty, varNode.Lag);
-
-        if (makeVariableWeightsVariable) {
-          initialConstants.Add(varNode.Weight);
-          var w = new AutoDiff.Variable();
-          variables.Add(w);
-          return AutoDiff.TermBuilder.Product(w, par);
-        } else {
-          return varNode.Weight * par;
-        }
-      }
+        return new[] { AutoDiff.TermBuilder.Sum(products) };
+      }
+      //if (node.Symbol is LaggedVariable) {
+      //  var varNode = node as LaggedVariableTreeNode;
+      //  var par = FindOrCreateParameter(parameters, varNode.VariableName, string.Empty, varNode.Lag);
+
+      //  if (makeVariableWeightsVariable) {
+      //    initialConstants.Add(varNode.Weight);
+      //    var w = new AutoDiff.Variable();
+      //    variables.Add(w);
+      //    return AutoDiff.TermBuilder.Product(w, par);
+      //  } else {
+      //    return varNode.Weight * par;
+      //  }
+      //}
       if (node.Symbol is Addition) {
-        List<AutoDiff.Term> terms = new List<Term>();
-        foreach (var subTree in node.Subtrees) {
-          terms.Add(ConvertToAutoDiff(subTree));
-        }
-        return AutoDiff.TermBuilder.Sum(terms);
+        var terms = node.Subtrees.Select(ConvertToAutoDiff).ToArray();
+        return BinaryOp((a, b) => a + b, a => a, terms);
       }
       if (node.Symbol is Subtraction) {
-        List<AutoDiff.Term> terms = new List<Term>();
-        for (int i = 0; i < node.SubtreeCount; i++) {
-          AutoDiff.Term t = ConvertToAutoDiff(node.GetSubtree(i));
-          if (i > 0) t = -t;
-          terms.Add(t);
-        }
-        if (terms.Count == 1) return -terms[0];
-        else return AutoDiff.TermBuilder.Sum(terms);
+        var terms = node.Subtrees.Select(ConvertToAutoDiff).ToArray();
+        return BinaryOp((a, b) => a - b, a => -a, terms);
       }
       if (node.Symbol is Multiplication) {
-        List<AutoDiff.Term> terms = new List<Term>();
-        foreach (var subTree in node.Subtrees) {
-          terms.Add(ConvertToAutoDiff(subTree));
-        }
-        if (terms.Count == 1) return terms[0];
-        else return terms.Aggregate((a, b) => new AutoDiff.Product(a, b));
+        var terms = node.Subtrees.Select(ConvertToAutoDiff).ToArray();
+        return BinaryOp((a, b) => a * b, a => a, terms);
       }
       if (node.Symbol is Division) {
-        List<AutoDiff.Term> terms = new List<Term>();
-        foreach (var subTree in node.Subtrees) {
-          terms.Add(ConvertToAutoDiff(subTree));
-        }
-        if (terms.Count == 1) return 1.0 / terms[0];
-        else return terms.Aggregate((a, b) => new AutoDiff.Product(a, 1.0 / b));
+        var terms = node.Subtrees.Select(ConvertToAutoDiff).ToArray();
+        return BinaryOp((a, b) => a / b, a => 1.0 / a, terms);
       }
       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));
-      }
+        var term = node.Subtrees.Select(ConvertToAutoDiff).Single();
+        return UnaryOp(abs, term);
+      }
+      //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(
-          ConvertToAutoDiff(node.GetSubtree(0)));
+        var term = node.Subtrees.Select(ConvertToAutoDiff).Single();
+        return UnaryOp(TermBuilder.Log, term);
       }
       if (node.Symbol is Exponential) {
-        return AutoDiff.TermBuilder.Exp(
-          ConvertToAutoDiff(node.GetSubtree(0)));
+        var term = node.Subtrees.Select(ConvertToAutoDiff).Single();
+        return UnaryOp(TermBuilder.Exp, term);
       }
       if (node.Symbol is Square) {
-        return AutoDiff.TermBuilder.Power(
-          ConvertToAutoDiff(node.GetSubtree(0)), 2.0);
+        var term = node.Subtrees.Select(ConvertToAutoDiff).Single();
+        return UnaryOp(t => TermBuilder.Power(t, 2.0), term);
       }
       if (node.Symbol is SquareRoot) {
-        return AutoDiff.TermBuilder.Power(
-          ConvertToAutoDiff(node.GetSubtree(0)), 0.5);
+        var term = node.Subtrees.Select(ConvertToAutoDiff).Single();
+        return UnaryOp(t => TermBuilder.Power(t, 0.5), term);
       }
       if (node.Symbol is Cube) {
-        return AutoDiff.TermBuilder.Power(
-          ConvertToAutoDiff(node.GetSubtree(0)), 3.0);
+        var term = node.Subtrees.Select(ConvertToAutoDiff).Single();
+        return UnaryOp(t => TermBuilder.Power(t, 3.0), term);
       }
       if (node.Symbol is CubeRoot) {
-        return cbrt(ConvertToAutoDiff(node.GetSubtree(0)));
+        var term = node.Subtrees.Select(ConvertToAutoDiff).Single();
+        return UnaryOp(cbrt, term);
       }
       if (node.Symbol is Sine) {
-        return sin(
-          ConvertToAutoDiff(node.GetSubtree(0)));
+        var term = node.Subtrees.Select(ConvertToAutoDiff).Single();
+        return UnaryOp(sin, term);
       }
       if (node.Symbol is Cosine) {
-        return cos(
-          ConvertToAutoDiff(node.GetSubtree(0)));
+        var term = node.Subtrees.Select(ConvertToAutoDiff).Single();
+        return UnaryOp(cos, term);
       }
       if (node.Symbol is Tangent) {
-        return tan(
-          ConvertToAutoDiff(node.GetSubtree(0)));
+        var term = node.Subtrees.Select(ConvertToAutoDiff).Single();
+        return UnaryOp(tan, term);
       }
       if (node.Symbol is HyperbolicTangent) {
-        return tanh(
-          ConvertToAutoDiff(node.GetSubtree(0)));
+        var term = node.Subtrees.Select(ConvertToAutoDiff).Single();
+        return UnaryOp(tanh, term);
       }
       if (node.Symbol is Erf) {
-        return erf(
-          ConvertToAutoDiff(node.GetSubtree(0)));
+        var term = node.Subtrees.Select(ConvertToAutoDiff).Single();
+        return UnaryOp(erf, term);
       }
       if (node.Symbol is Norm) {
-        return norm(
-          ConvertToAutoDiff(node.GetSubtree(0)));
+        var term = node.Subtrees.Select(ConvertToAutoDiff).Single();
+        return UnaryOp(norm, term);
       }
       if (node.Symbol is StartSymbol) {
@@ -291 +299 @@
           variables.Add(alpha);
           var t = ConvertToAutoDiff(node.GetSubtree(0));
-          return t * alpha + beta;
+          if (t.Count > 1) throw new InvalidOperationException("Tree Result must be scalar value");
+          return new[] { t[0] * alpha + beta };
         } else return ConvertToAutoDiff(node.GetSubtree(0));
       }
+      if (node.Symbol is Sum) {
+        var term = node.Subtrees.Select(ConvertToAutoDiff).Single();
+        return new[] { TermBuilder.Sum(term) };
+      }
+      if (node.Symbol is Mean) {
+        var term = node.Subtrees.Select(ConvertToAutoDiff).Single();
+        return new[] { TermBuilder.Sum(term) / term.Count };
+      }
+      if (node.Symbol is StandardDeviation) {
+        var term = node.Subtrees.Select(ConvertToAutoDiff).Single();
+        var mean = TermBuilder.Sum(term) / term.Count;
+        var ssd = TermBuilder.Sum(term.Select(t => TermBuilder.Power(t - mean, 2.0)));
+        return new[] { TermBuilder.Power(ssd / term.Count, 0.5) };
+      }
+      if (node.Symbol is Length) {
+        var term = node.Subtrees.Select(ConvertToAutoDiff).Single();
+        return new[] { TermBuilder.Constant(term.Count) };
+      }
+      //if (node.Symbol is Min) {
+      //}
+      //if (node.Symbol is Max) {
+      //}
+      if (node.Symbol is Variance) {
+        var term = node.Subtrees.Select(ConvertToAutoDiff).Single();
+        var mean = TermBuilder.Sum(term) / term.Count;
+        var ssd = TermBuilder.Sum(term.Select(t => TermBuilder.Power(t - mean, 2.0)));
+        return new[] { ssd / term.Count };
+      }
+      //if (node.Symbol is Skewness) {
+      //}
+      //if (node.Symbol is Kurtosis) {
+      //}
+      //if (node.Symbol is EuclideanDistance) {
+      //}
+      //if (node.Symbol is Covariance) {
+      //}
+
+
       throw new ConversionException();
     }
@@ -301 +348 @@
     // each binary indicator is only necessary once. So we only create a parameter if this combination is not yet available
     private static Term FindOrCreateParameter(Dictionary<DataForVariable, AutoDiff.Variable> parameters,
-      string varName, string varValue = "", int lag = 0) {
-      var data = new DataForVariable(varName, varValue, lag);
+      string varName, string varValue = "", int lag = 0, int index = -1) {
+      var data = new DataForVariable(varName, varValue, lag, index);
 
       AutoDiff.Variable par = null;
@@ -319 +366 @@
           !(n.Symbol is Variable) &&
           !(n.Symbol is BinaryFactorVariable) &&
-          !(n.Symbol is FactorVariable) &&
-          !(n.Symbol is LaggedVariable) &&
+          //!(n.Symbol is FactorVariable) &&
+          //!(n.Symbol is LaggedVariable) &&
           !(n.Symbol is Constant) &&
           !(n.Symbol is Addition) &&
@@ -338 +385 @@
           !(n.Symbol is StartSymbol) &&
           !(n.Symbol is Absolute) &&
-          !(n.Symbol is AnalyticQuotient) &&
+          //!(n.Symbol is AnalyticQuotient) &&
           !(n.Symbol is Cube) &&
-          !(n.Symbol is CubeRoot)
+          !(n.Symbol is CubeRoot) &&
+          !(n.Symbol is Sum) &&
+          !(n.Symbol is Mean) &&
+          !(n.Symbol is StandardDeviation) &&
+          !(n.Symbol is Length) &&
+          //!(n.Symbol is Min) &&
+          //!(n.Symbol is Max) &&
+          !(n.Symbol is Variance)
+        //!(n.Symbol is Skewness) &&
+        //!(n.Symbol is Kurtosis) &&
+        //!(n.Symbol is EuclideanDistance) &&
+        //!(n.Symbol is Covariance)
         select n).Any();
       return !containsUnknownSymbol;