Changeset 11895 for branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg

Timestamp:

02/05/15 07:03:15 (10 years ago)

Author:

gkronber

Message:

#2283: constant opt, expressioncompiler, autodiff, fixes in GP solvers

Location:

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg

Files:

• ExpressionCompiler.cs (added)
• HeuristicLab.Problems.GrammaticalOptimization.SymbReg.csproj (modified) (3 diffs)
• SymbolicRegressionProblem.cs (modified) (11 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/HeuristicLab.Problems.GrammaticalOptimization.SymbReg.csproj

@@ -31 +31 @@
   </PropertyGroup>
   <ItemGroup>
+    <Reference Include="ALGLIB-3.7.0, Version=3.7.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\sources\bin\ALGLIB-3.7.0.dll</HintPath>
+    </Reference>
+    <Reference Include="AutoDiff-1.0">
+      <HintPath>..\..\..\trunk\sources\bin\AutoDiff-1.0.dll</HintPath>
+    </Reference>
     <Reference Include="HeuristicLab.Common-3.3">
       <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Common-3.3.dll</HintPath>
@@ -39 +46 @@
     <Reference Include="HeuristicLab.Data-3.3">
       <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Data-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll</HintPath>
     </Reference>
     <Reference Include="HeuristicLab.Problems.DataAnalysis-3.4">
@@ -53 +64 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="ExpressionCompiler.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
     <Compile Include="SymbolicRegressionProblem.cs" />

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs

@@ -1 +1 @@
 using System;
+using System.CodeDom.Compiler;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Security;
 using System.Security.AccessControl;
+using System.Security.Authentication.ExtendedProtection.Configuration;
 using System.Text;
+using AutoDiff;
 using HeuristicLab.Common;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Problems.DataAnalysis;
 using HeuristicLab.Problems.Instances;
@@ -12 +17 @@
 namespace HeuristicLab.Problems.GrammaticalOptimization.SymbReg {
   // provides bridge to HL regression problem instances
-  public class SymbolicRegressionProblem : IProblem {
+  public class SymbolicRegressionProblem : ISymbolicExpressionTreeProblem {
 
     private const string grammarString = @"
         G(E):
-        E -> V | V+E | V-E | V*E | V/E | (E) | C | C+E | C-E | C*E | C/E 
+        E -> V | C | V+E | V-E | V*E | V%E | (E) | C+E | C-E | C*E | C%E 
         C -> 0..9
         V -> <variables>
@@ -22 +27 @@
     // C represents Koza-style ERC (the symbol is the index of the ERC), the values are initialized below
 
+    // S .. Sum (+), N .. Neg. sum (-), P .. Product (*), D .. Division (%)
+    private const string treeGrammarString = @"
+        G(E):
+        E -> V | C | S | N | P | D 
+        S -> EE | EEE
+        N -> EE | EEE
+        P -> EE | EEE
+        D -> EE
+        C -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
+        V -> <variables>
+        ";
+
+    // when we use constants optimization we can completely ignore all constants by a simple strategy:
+    // introduce a constant factor for each complete term
+    // introduce a constant offset for each complete expression (including expressions in brackets)
+    // e.g. 1*(2*a + b - 3 + 4) is the same as c0*a + c1*b + c2
+
     private readonly IGrammar grammar;
 
     private readonly int N;
-    private readonly double[][] x;
+    private readonly double[,] x;
     private readonly double[] y;
     private readonly int d;
@@ -40 +62 @@
       this.d = problemData.AllowedInputVariables.Count();
       if (d > 26) throw new NotSupportedException(); // we only allow single-character terminal symbols so far
-      this.x = new double[N][];
+      this.x = new double[N, d];
       this.y = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, problemData.TrainingIndices).ToArray();
 
       int i = 0;
       foreach (var r in problemData.TrainingIndices) {
-        x[i] = new double[d];
         int j = 0;
         foreach (var inputVariable in problemData.AllowedInputVariables) {
-          x[i][j++] = problemData.Dataset.GetDoubleValue(inputVariable, r);
+          x[i, j++] = problemData.Dataset.GetDoubleValue(inputVariable, r);
         }
         i++;
@@ -58 +79 @@
       char lastVar = Convert.ToChar(Convert.ToByte('a') + d - 1);
       this.grammar = new Grammar(grammarString.Replace("<variables>", firstVar + " .. " + lastVar));
+      this.TreeBasedGPGrammar = new Grammar(treeGrammarString.Replace("<variables>", firstVar + " .. " + lastVar));
     }
 
@@ -71 +93 @@
 
     public double Evaluate(string sentence) {
+      return OptimizeConstantsAndEvaluate(sentence);
+    }
+
+    public double SimpleEvaluate(string sentence) {
       var interpreter = new ExpressionInterpreter();
-      return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i], erc)));
+      var rowData = new double[d];
+      return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => {
+        for (int j = 0; j < d; j++) rowData[j] = x[i, j];
+        return interpreter.Interpret(sentence, rowData, erc);
+      }));
     }
 
@@ -83 +113 @@
     }
 
-    public IEnumerable<Feature> GetFeatures(string phrase)
-    {
+    public IEnumerable<Feature> GetFeatures(string phrase) {
       throw new NotImplementedException();
     }
 
 
-    /*
-    public static double OptimizeConstants(string sentence) {
-
-      List<AutoDiff.Variable> variables = new List<AutoDiff.Variable>();
-      List<AutoDiff.Variable> parameters = new List<AutoDiff.Variable>();
-      List<string> variableNames = new List<string>();
-
+
+    public double OptimizeConstantsAndEvaluate(string sentence) {
       AutoDiff.Term func;
-      if (!TryTransformToAutoDiff(sentence, 0, variables, parameters, out func))
-        throw new NotSupportedException("Could not optimize constants of symbolic expression tree due to not supported symbols used in the tree.");
-      if (variableNames.Count == 0) return 0.0;
-
-      AutoDiff.IParametricCompiledTerm compiledFunc = AutoDiff.TermUtils.Compile(func, variables.ToArray(), parameters.ToArray());
-
-      List<SymbolicExpressionTreeTerminalNode> terminalNodes = tree.Root.IterateNodesPrefix().OfType<SymbolicExpressionTreeTerminalNode>().ToList();
-      double[] c = new double[variables.Count];
-
-      {
-        c[0] = 0.0;
-        c[1] = 1.0;
-        //extract inital constants
-        int i = 2;
-        foreach (var node in terminalNodes) {
-          ConstantTreeNode constantTreeNode = node as ConstantTreeNode;
-          VariableTreeNode variableTreeNode = node as VariableTreeNode;
-          if (constantTreeNode != null)
-            c[i++] = constantTreeNode.Value;
-          else if (variableTreeNode != null)
-            c[i++] = variableTreeNode.Weight;
-        }
-      }
-      double[] originalConstants = (double[])c.Clone();
-      double originalQuality = SymbolicRegressionSingleObjectivePearsonRSquaredEvaluator.Calculate(interpreter, tree, lowerEstimationLimit, upperEstimationLimit, problemData, rows, applyLinearScaling);
+      int pos = 0;
+
+      var compiler = new ExpressionCompiler();
+      Variable[] variables;
+      Variable[] constants;
+      compiler.Compile(sentence, out func, out variables, out constants);
+
+      // constants are manipulated 
+
+      if (!constants.Any()) return SimpleEvaluate(sentence);
+
+      AutoDiff.IParametricCompiledTerm compiledFunc = func.Compile(constants, variables); // variate constants leave variables fixed to data
+
+      double[] c = constants.Select(_ => 1.0).ToArray(); // start with ones
 
       alglib.lsfitstate state;
@@ -127 +140 @@
       int info;
 
-      Dataset ds = problemData.Dataset;
-      double[,] x = new double[rows.Count(), variableNames.Count];
-      int row = 0;
-      foreach (var r in rows) {
-        for (int col = 0; col < variableNames.Count; col++) {
-          x[row, col] = ds.GetDoubleValue(variableNames[col], r);
-        }
-        row++;
-      }
-      double[] y = ds.GetDoubleValues(problemData.TargetVariable, rows).ToArray();
       int n = x.GetLength(0);
       int m = x.GetLength(1);
@@ -144 +147 @@
       alglib.ndimensional_pgrad function_cx_1_grad = CreatePGrad(compiledFunc);
 
+      const int maxIterations = 10;
       try {
         alglib.lsfitcreatefg(x, y, c, n, m, k, false, out state);
@@ -151 +155 @@
         alglib.lsfitresults(state, out info, out c, out rep);
       } catch (ArithmeticException) {
-        return originalQuality;
+        return 0.0;
       } catch (alglib.alglibexception) {
-        return originalQuality;
+        return 0.0;
       }
 
       //info == -7  => constant optimization failed due to wrong gradient
-      if (info != -7) throw new ArgumentException();
+      if (info == -7) throw new ArgumentException();
+      {
+        var rowData = new double[d];
+        return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => {
+          for (int j = 0; j < d; j++) rowData[j] = x[i, j];
+          return compiledFunc.Evaluate(c, rowData);
+        }));
+      }
     }
 
@@ -175 +186 @@
     }
 
-    private static bool TryTransformToAutoDiff(string phrase, int symbolPos, List<AutoDiff.Variable> variables, List<AutoDiff.Variable> parameters, out AutoDiff.Term term)
-    {
-      var curSy = phrase[0];
-      if () {
-        var var = new AutoDiff.Variable();
-        variables.Add(var);
-        term = var;
-        return true;
-      }
-      if (node.Symbol is Variable) {
-        var varNode = node as VariableTreeNode;
-        var par = new AutoDiff.Variable();
-        parameters.Add(par);
-        variableNames.Add(varNode.VariableName);
-        var w = new AutoDiff.Variable();
-        variables.Add(w);
-        term = AutoDiff.TermBuilder.Product(w, par);
-        return true;
-      }
-      if (node.Symbol is Addition) {
-        List<AutoDiff.Term> terms = new List<Term>();
-        foreach (var subTree in node.Subtrees) {
-          AutoDiff.Term t;
-          if (!TryTransformToAutoDiff(subTree, variables, parameters, variableNames, out t)) {
-            term = null;
-            return false;
-          }
-          terms.Add(t);
+    public IGrammar TreeBasedGPGrammar { get; private set; }
+    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
+      var sb = new StringBuilder();
+
+      TreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);
+
+      return sb.ToString();
+    }
+
+    private void TreeToSentence(ISymbolicExpressionTreeNode treeNode, StringBuilder sb) {
+      if (treeNode.SubtreeCount == 0) {
+        // terminal
+        sb.Append(treeNode.Symbol.Name);
+      } else {
+        string op = string.Empty;
+        switch (treeNode.Symbol.Name) {
+          case "S": op = "+"; break;
+          case "N": op = "-"; break;
+          case "P": op = "*"; break;
+          case "D": op = "%"; break;
+          default: {
+              Debug.Assert(treeNode.SubtreeCount == 1);
+              break;
+            }
         }
-        term = AutoDiff.TermBuilder.Sum(terms);
-        return true;
-      }
-      if (node.Symbol is Subtraction) {
-        List<AutoDiff.Term> terms = new List<Term>();
-        for (int i = 0; i < node.SubtreeCount; i++) {
-          AutoDiff.Term t;
-          if (!TryTransformToAutoDiff(node.GetSubtree(i), variables, parameters, variableNames, out t)) {
-            term = null;
-            return false;
-          }
-          if (i > 0) t = -t;
-          terms.Add(t);
+        // nonterminal
+        if (op == "+" || op == "-") sb.Append("(");
+        TreeToSentence(treeNode.Subtrees.First(), sb);
+        foreach (var subTree in treeNode.Subtrees.Skip(1)) {
+          sb.Append(op);
+          TreeToSentence(subTree, sb);
         }
-        term = AutoDiff.TermBuilder.Sum(terms);
-        return true;
-      }
-      if (node.Symbol is Multiplication) {
-        AutoDiff.Term a, b;
-        if (!TryTransformToAutoDiff(node.GetSubtree(0), variables, parameters, variableNames, out a) ||
-          !TryTransformToAutoDiff(node.GetSubtree(1), variables, parameters, variableNames, out b)) {
-          term = null;
-          return false;
-        } else {
-          List<AutoDiff.Term> factors = new List<Term>();
-          foreach (var subTree in node.Subtrees.Skip(2)) {
-            AutoDiff.Term f;
-            if (!TryTransformToAutoDiff(subTree, variables, parameters, variableNames, out f)) {
-              term = null;
-              return false;
-            }
-            factors.Add(f);
-          }
-          term = AutoDiff.TermBuilder.Product(a, b, factors.ToArray());
-          return true;
-        }
-      }
-      if (node.Symbol is Division) {
-        // only works for at least two subtrees
-        AutoDiff.Term a, b;
-        if (!TryTransformToAutoDiff(node.GetSubtree(0), variables, parameters, variableNames, out a) ||
-          !TryTransformToAutoDiff(node.GetSubtree(1), variables, parameters, variableNames, out b)) {
-          term = null;
-          return false;
-        } else {
-          List<AutoDiff.Term> factors = new List<Term>();
-          foreach (var subTree in node.Subtrees.Skip(2)) {
-            AutoDiff.Term f;
-            if (!TryTransformToAutoDiff(subTree, variables, parameters, variableNames, out f)) {
-              term = null;
-              return false;
-            }
-            factors.Add(1.0 / f);
-          }
-          term = AutoDiff.TermBuilder.Product(a, 1.0 / b, factors.ToArray());
-          return true;
-        }
-      }
-      
-      if (node.Symbol is StartSymbol) {
-        var alpha = new AutoDiff.Variable();
-        var beta = new AutoDiff.Variable();
-        variables.Add(beta);
-        variables.Add(alpha);
-        AutoDiff.Term branchTerm;
-        if (TryTransformToAutoDiff(node.GetSubtree(0), variables, parameters, variableNames, out branchTerm)) {
-          term = branchTerm * alpha + beta;
-          return true;
-        } else {
-          term = null;
-          return false;
-        }
-      }
-      term = null;
-      return false;
-    }
-     */
+        if (op == "+" || op == "-") sb.Append(")");
+      }
+    }
   }
 }