source: trunk/sources/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Converters/TreeToAutoDiffTermConverter.cs @ 15447

Last change on this file since 15447 was 15447, checked in by mkommend, 23 months ago

#2852: Adapted constants optimization and auto diff converter to not add linear scaling terms.

File size: 12.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using System.Runtime.Serialization;
26using AutoDiff;
27using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
28
29namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
30  public class TreeToAutoDiffTermConverter {
31    public delegate double ParametricFunction(double[] vars, double[] @params);
32
33    public delegate Tuple<double[], double> ParametricFunctionGradient(double[] vars, double[] @params);
34
35    #region helper class
36    public class DataForVariable {
37      public readonly string variableName;
38      public readonly string variableValue; // for factor vars
39      public readonly int lag;
40
41      public DataForVariable(string varName, string varValue, int lag) {
42        this.variableName = varName;
43        this.variableValue = varValue;
44        this.lag = lag;
45      }
46
47      public override bool Equals(object obj) {
48        var other = obj as DataForVariable;
49        if (other == null) return false;
50        return other.variableName.Equals(this.variableName) &&
51               other.variableValue.Equals(this.variableValue) &&
52               other.lag == this.lag;
53      }
54
55      public override int GetHashCode() {
56        return variableName.GetHashCode() ^ variableValue.GetHashCode() ^ lag;
57      }
58    }
59    #endregion
60
61    #region derivations of functions
62    // create function factory for arctangent
63    private static readonly Func<Term, UnaryFunc> arctan = UnaryFunc.Factory(
64      eval: Math.Atan,
65      diff: x => 1 / (1 + x * x));
66
67    private static readonly Func<Term, UnaryFunc> sin = UnaryFunc.Factory(
68      eval: Math.Sin,
69      diff: Math.Cos);
70
71    private static readonly Func<Term, UnaryFunc> cos = UnaryFunc.Factory(
72      eval: Math.Cos,
73      diff: x => -Math.Sin(x));
74
75    private static readonly Func<Term, UnaryFunc> tan = UnaryFunc.Factory(
76      eval: Math.Tan,
77      diff: x => 1 + Math.Tan(x) * Math.Tan(x));
78
79    private static readonly Func<Term, UnaryFunc> erf = UnaryFunc.Factory(
80      eval: alglib.errorfunction,
81      diff: x => 2.0 * Math.Exp(-(x * x)) / Math.Sqrt(Math.PI));
82
83    private static readonly Func<Term, UnaryFunc> norm = UnaryFunc.Factory(
84      eval: alglib.normaldistribution,
85      diff: x => -(Math.Exp(-(x * x)) * Math.Sqrt(Math.Exp(x * x)) * x) / Math.Sqrt(2 * Math.PI));
86
87    #endregion
88
89    public static bool TryConvertToAutoDiff(ISymbolicExpressionTree tree, bool makeVariableWeightsVariable, bool addLinearScalingTerms,
90      out List<DataForVariable> parameters, out double[] initialConstants,
91      out ParametricFunction func,
92      out ParametricFunctionGradient func_grad) {
93
94      // use a transformator object which holds the state (variable list, parameter list, ...) for recursive transformation of the tree
95      var transformator = new TreeToAutoDiffTermConverter(makeVariableWeightsVariable, addLinearScalingTerms);
96      AutoDiff.Term term;
97      try {
98        term = transformator.ConvertToAutoDiff(tree.Root.GetSubtree(0));
99        var parameterEntries = transformator.parameters.ToArray(); // guarantee same order for keys and values
100        var compiledTerm = term.Compile(transformator.variables.ToArray(),
101          parameterEntries.Select(kvp => kvp.Value).ToArray());
102        parameters = new List<DataForVariable>(parameterEntries.Select(kvp => kvp.Key));
103        initialConstants = transformator.initialConstants.ToArray();
104        func = (vars, @params) => compiledTerm.Evaluate(vars, @params);
105        func_grad = (vars, @params) => compiledTerm.Differentiate(vars, @params);
106        return true;
107      } catch (ConversionException) {
108        func = null;
109        func_grad = null;
110        parameters = null;
111        initialConstants = null;
112      }
113      return false;
114    }
115
116    // state for recursive transformation of trees
117    private readonly
118    List<double> initialConstants;
119    private readonly Dictionary<DataForVariable, AutoDiff.Variable> parameters;
120    private readonly List<AutoDiff.Variable> variables;
121    private readonly bool makeVariableWeightsVariable;
122    private readonly bool addLinearScalingTerms;
123
124    private TreeToAutoDiffTermConverter(bool makeVariableWeightsVariable, bool addLinearScalingTerms) {
125      this.makeVariableWeightsVariable = makeVariableWeightsVariable;
126      this.addLinearScalingTerms = addLinearScalingTerms;
127      this.initialConstants = new List<double>();
128      this.parameters = new Dictionary<DataForVariable, AutoDiff.Variable>();
129      this.variables = new List<AutoDiff.Variable>();
130    }
131
132    private AutoDiff.Term ConvertToAutoDiff(ISymbolicExpressionTreeNode node) {
133      if (node.Symbol is Constant) {
134        initialConstants.Add(((ConstantTreeNode)node).Value);
135        var var = new AutoDiff.Variable();
136        variables.Add(var);
137        return var;
138      }
139      if (node.Symbol is Variable || node.Symbol is BinaryFactorVariable) {
140        var varNode = node as VariableTreeNodeBase;
141        var factorVarNode = node as BinaryFactorVariableTreeNode;
142        // factor variable values are only 0 or 1 and set in x accordingly
143        var varValue = factorVarNode != null ? factorVarNode.VariableValue : string.Empty;
144        var par = FindOrCreateParameter(parameters, varNode.VariableName, varValue);
145
146        if (makeVariableWeightsVariable) {
147          initialConstants.Add(varNode.Weight);
148          var w = new AutoDiff.Variable();
149          variables.Add(w);
150          return AutoDiff.TermBuilder.Product(w, par);
151        } else {
152          return varNode.Weight * par;
153        }
154      }
155      if (node.Symbol is FactorVariable) {
156        var factorVarNode = node as FactorVariableTreeNode;
157        var products = new List<Term>();
158        foreach (var variableValue in factorVarNode.Symbol.GetVariableValues(factorVarNode.VariableName)) {
159          var par = FindOrCreateParameter(parameters, factorVarNode.VariableName, variableValue);
160
161          initialConstants.Add(factorVarNode.GetValue(variableValue));
162          var wVar = new AutoDiff.Variable();
163          variables.Add(wVar);
164
165          products.Add(AutoDiff.TermBuilder.Product(wVar, par));
166        }
167        return AutoDiff.TermBuilder.Sum(products);
168      }
169      if (node.Symbol is LaggedVariable) {
170        var varNode = node as LaggedVariableTreeNode;
171        var par = FindOrCreateParameter(parameters, varNode.VariableName, string.Empty, varNode.Lag);
172
173        if (makeVariableWeightsVariable) {
174          initialConstants.Add(varNode.Weight);
175          var w = new AutoDiff.Variable();
176          variables.Add(w);
177          return AutoDiff.TermBuilder.Product(w, par);
178        } else {
179          return varNode.Weight * par;
180        }
181      }
182      if (node.Symbol is Addition) {
183        List<AutoDiff.Term> terms = new List<Term>();
184        foreach (var subTree in node.Subtrees) {
185          terms.Add(ConvertToAutoDiff(subTree));
186        }
187        return AutoDiff.TermBuilder.Sum(terms);
188      }
189      if (node.Symbol is Subtraction) {
190        List<AutoDiff.Term> terms = new List<Term>();
191        for (int i = 0; i < node.SubtreeCount; i++) {
192          AutoDiff.Term t = ConvertToAutoDiff(node.GetSubtree(i));
193          if (i > 0) t = -t;
194          terms.Add(t);
195        }
196        if (terms.Count == 1) return -terms[0];
197        else return AutoDiff.TermBuilder.Sum(terms);
198      }
199      if (node.Symbol is Multiplication) {
200        List<AutoDiff.Term> terms = new List<Term>();
201        foreach (var subTree in node.Subtrees) {
202          terms.Add(ConvertToAutoDiff(subTree));
203        }
204        if (terms.Count == 1) return terms[0];
205        else return terms.Aggregate((a, b) => new AutoDiff.Product(a, b));
206      }
207      if (node.Symbol is Division) {
208        List<AutoDiff.Term> terms = new List<Term>();
209        foreach (var subTree in node.Subtrees) {
210          terms.Add(ConvertToAutoDiff(subTree));
211        }
212        if (terms.Count == 1) return 1.0 / terms[0];
213        else return terms.Aggregate((a, b) => new AutoDiff.Product(a, 1.0 / b));
214      }
215      if (node.Symbol is Logarithm) {
216        return AutoDiff.TermBuilder.Log(
217          ConvertToAutoDiff(node.GetSubtree(0)));
218      }
219      if (node.Symbol is Exponential) {
220        return AutoDiff.TermBuilder.Exp(
221          ConvertToAutoDiff(node.GetSubtree(0)));
222      }
223      if (node.Symbol is Square) {
224        return AutoDiff.TermBuilder.Power(
225          ConvertToAutoDiff(node.GetSubtree(0)), 2.0);
226      }
227      if (node.Symbol is SquareRoot) {
228        return AutoDiff.TermBuilder.Power(
229          ConvertToAutoDiff(node.GetSubtree(0)), 0.5);
230      }
231      if (node.Symbol is Sine) {
232        return sin(
233          ConvertToAutoDiff(node.GetSubtree(0)));
234      }
235      if (node.Symbol is Cosine) {
236        return cos(
237          ConvertToAutoDiff(node.GetSubtree(0)));
238      }
239      if (node.Symbol is Tangent) {
240        return tan(
241          ConvertToAutoDiff(node.GetSubtree(0)));
242      }
243      if (node.Symbol is Erf) {
244        return erf(
245          ConvertToAutoDiff(node.GetSubtree(0)));
246      }
247      if (node.Symbol is Norm) {
248        return norm(
249          ConvertToAutoDiff(node.GetSubtree(0)));
250      }
251      if (node.Symbol is StartSymbol) {
252        if (addLinearScalingTerms) {
253          var alpha = new AutoDiff.Variable();
254          var beta = new AutoDiff.Variable();
255          variables.Add(beta);
256          variables.Add(alpha);
257          return ConvertToAutoDiff(node.GetSubtree(0)) * alpha + beta;
258        } else return ConvertToAutoDiff(node.GetSubtree(0));
259      }
260      throw new ConversionException();
261    }
262
263
264    // for each factor variable value we need a parameter which represents a binary indicator for that variable & value combination
265    // each binary indicator is only necessary once. So we only create a parameter if this combination is not yet available
266    private static Term FindOrCreateParameter(Dictionary<DataForVariable, AutoDiff.Variable> parameters,
267      string varName, string varValue = "", int lag = 0) {
268      var data = new DataForVariable(varName, varValue, lag);
269
270      AutoDiff.Variable par = null;
271      if (!parameters.TryGetValue(data, out par)) {
272        // not found -> create new parameter and entries in names and values lists
273        par = new AutoDiff.Variable();
274        parameters.Add(data, par);
275      }
276      return par;
277    }
278
279    public static bool IsCompatible(ISymbolicExpressionTree tree) {
280      var containsUnknownSymbol = (
281        from n in tree.Root.GetSubtree(0).IterateNodesPrefix()
282        where
283          !(n.Symbol is Variable) &&
284          !(n.Symbol is BinaryFactorVariable) &&
285          !(n.Symbol is FactorVariable) &&
286          !(n.Symbol is LaggedVariable) &&
287          !(n.Symbol is Constant) &&
288          !(n.Symbol is Addition) &&
289          !(n.Symbol is Subtraction) &&
290          !(n.Symbol is Multiplication) &&
291          !(n.Symbol is Division) &&
292          !(n.Symbol is Logarithm) &&
293          !(n.Symbol is Exponential) &&
294          !(n.Symbol is SquareRoot) &&
295          !(n.Symbol is Square) &&
296          !(n.Symbol is Sine) &&
297          !(n.Symbol is Cosine) &&
298          !(n.Symbol is Tangent) &&
299          !(n.Symbol is Erf) &&
300          !(n.Symbol is Norm) &&
301          !(n.Symbol is StartSymbol)
302        select n).Any();
303      return !containsUnknownSymbol;
304    }
305    #region exception class
306    [Serializable]
307    public class ConversionException : Exception {
308
309      public ConversionException() {
310      }
311
312      public ConversionException(string message) : base(message) {
313      }
314
315      public ConversionException(string message, Exception inner) : base(message, inner) {
316      }
317
318      protected ConversionException(
319        SerializationInfo info,
320        StreamingContext context) : base(info, context) {
321      }
322    }
323    #endregion
324  }
325}
Note: See TracBrowser for help on using the repository browser.