Changeset 15414 for branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression

Timestamp:

10/09/17 18:53:34 (7 years ago)

Author:

gkronber

Message:

#2796 worked on MCTS

Location:

branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression

Files:

• ApproximateDoubleEqualityComparer.cs (added)
• Automaton.cs (modified) (1 diff)
• Disassembler.cs (modified) (1 diff)
• ExprHash.cs (modified) (6 diffs)
• MctsSymbolicRegressionStatic.cs (modified) (18 diffs)
• Policies/Ucb.cs (modified) (2 diffs)
• SimpleConstraintHandler.cs (modified) (1 diff)
• Tree.cs (modified) (1 diff)

branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Automaton.cs

@@ -398 +398 @@
         v == StateLogTFEnd ||
         v == StateInvTFEnd ||
-        v == StateExpFEnd;
+        v == StateExpFEnd
+        ;
     }
 

branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Disassembler.cs

@@ -58 +58 @@
         switch (op) {
           case (byte)OpCodes.Add: sb.Append(" + "); break;
-          case (byte)OpCodes.Mul: sb.Append(" * "); break;
-          case (byte)OpCodes.LoadConst1: sb.Append(" 1 "); break;
-          case (byte)OpCodes.LoadConst0: sb.Append(" 0 "); break;
-          case (byte)OpCodes.LoadParamN: sb.AppendFormat(" c "); break;
+          case (byte)OpCodes.Mul: sb.Append(""); break;
+          case (byte)OpCodes.LoadConst1: break;
+          case (byte)OpCodes.LoadConst0: break;
+          case (byte)OpCodes.LoadParamN: break;
           case (byte)OpCodes.LoadVar: {
               short arg = (short)((code[pc] << 8) | code[pc + 1]);
               pc += 2;
-              sb.AppendFormat(" var{0} ", arg); break;
+              sb.AppendFormat("{0}", (char)('a'+arg)); break;
             }
           case (byte)OpCodes.Exp: sb.Append(" exp "); break;

branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/ExprHash.cs

@@ -20 +20 @@
 #endregion
 using System;
+using System.Collections.Generic;
 using System.Diagnostics.Contracts;
 using HeuristicLab.Random;
+using System.Linq;
 
 namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression {
@@ -40 +42 @@
   // We only need to identify equivalent structures. The numeric constants are irrelevant.
   // Therefore, equivalent structures with different numeric constants map to the same hash code.
-  
+
   public static class ExprHash {
     const int MaxStackSize = 100;
     const int MaxVariables = 1000;
-    private static double[] varSymbValues; 
+    private static double[] varSymbValues;
     static ExprHash() {
       var rand = new MersenneTwister();
       varSymbValues = new double[MaxVariables];
-      for(int i = 0;i < MaxVariables;i++) {
+      for (int i = 0; i < MaxVariables; i++) {
         varSymbValues[i] = rand.NextDouble();
       }
@@ -54 +56 @@
 
     public static ulong GetHash(byte[] code, int nParams) {
-      var bits = (ulong)BitConverter.DoubleToInt64Bits(Exec(code, nParams));
+      var bits = (ulong)BitConverter.DoubleToInt64Bits(Eval(code, nParams));
       // clear last five bits (insignificant?)
       bits = bits & 0xFFFFFFFFFFFFFFE0;
@@ -60 +62 @@
     }
 
-    private static double Exec(byte[] code, int nParams) {
-      var stack = new double[MaxStackSize];
+    private static double Eval(byte[] code, int nParams) {
+      // The hash code calculation already preserves commutativity, associativity and distributivity of operations.
+      // However, we also need to hash c1*x1 + c2*x1 to the same value as c3*x1.
+      // Similarly for x1*x2 + x1*x2 or log(x1) + log(x1)!
+
+      // Calculate sums lazily. Keep all terms and only when the actual sum is necessary remove duplicate terms and calculate sum
+      // think about speed later (TODO)
+
+      var stack = new ISet<double>[MaxStackSize];
+      var terms = new HashSet<double>(new ApproximateDoubleEqualityComparer()); // the set of arguments for the current operator (+, *)
       int topOfStack = -1;
       int pc = 0;
@@ -73 +83 @@
           case OpCodes.LoadConst0: {
               ++topOfStack;
-              stack[topOfStack] = 0.0;
+              stack[topOfStack] = new HashSet<double>( new[] { 0.0 });
+
+              // terms.Add(0.0); // ignore numeric constants in expr-hash
+
               break;
             }
           case OpCodes.LoadConst1: {
               ++topOfStack;
-              stack[topOfStack] = 1.0;
+              stack[topOfStack] = new HashSet<double>(new[] { 1.0 });
+
+              // args.Add(1.0); ignore numeric constants in expr-hash
+
               break;
             }
           case OpCodes.LoadParamN: {
               ++topOfStack;
-              stack[topOfStack] = 1.0;
+              stack[topOfStack] =  new HashSet<double>(new[] { 1.0 });
               break;
             }
           case OpCodes.LoadVar: {
               ++topOfStack;
-              stack[topOfStack] = varSymbValues[arg];
+              stack[topOfStack] = new HashSet<double>(new[] { varSymbValues[arg] });
+
+              // args.Add(varSymbValues[arg]);
+
               break;
             }
           case OpCodes.Add: {
-              var t1 = stack[topOfStack - 1];
-              var t2 = stack[topOfStack];
+              // take arguments from stack and put both terms into the set of terms
+              // for every other operation we need to evaluate the sum of terms first and put it onto the stack (lazy eval of sums)
+
+              stack[topOfStack - 1].UnionWith(stack[topOfStack]);
               topOfStack--;
-              stack[topOfStack] = t1 + t2;
+
+              // stack[topOfStack] = t1 + t2; (later)
               break;
             }
@@ -102 +124 @@
               var t2 = stack[topOfStack];
               topOfStack--;
-              stack[topOfStack] = t1 * t2;
+              stack[topOfStack] = new HashSet<double>(new double[] { t1.Sum() * t2.Sum() });
               break;
             }
           case OpCodes.Log: {
               var v1 = stack[topOfStack];
-              stack[topOfStack] = Math.Log(v1);
+              stack[topOfStack] = new HashSet<double>(new double[] { Math.Log( v1.Sum()) });
               break;
             }
           case OpCodes.Exp: {
               var v1 = stack[topOfStack];
-              stack[topOfStack] = Math.Exp(v1);
+              stack[topOfStack] = new HashSet<double>(new double[] { Math.Exp(v1.Sum()) });
               break;
             }
           case OpCodes.Inv: {
               var v1 = stack[topOfStack];
-              stack[topOfStack] = 1.0 / v1;
+              stack[topOfStack] = new HashSet<double>(new double[] { 1.0 / v1.Sum() });
               break;
             }
           case OpCodes.Exit:
             Contract.Assert(topOfStack == 0);
-            return stack[topOfStack];
+            return stack[topOfStack].Sum();
         }
       }
+    }
+
+    private static void EvalTerms(HashSet<double> terms, double[] stack, ref int topOfStack) {
+      ++topOfStack;
+      stack[topOfStack] = terms.Sum();
+      terms.Clear();
     }
 

branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/MctsSymbolicRegressionStatic.cs

@@ -25 +25 @@
 using System.Diagnostics.Contracts;
 using System.Linq;
+using System.Text;
 using HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression.Policies;
 using HeuristicLab.Core;
@@ -58 +59 @@
     //       weight more than an improvement from 0.98 to 0.99. Also, we are more interested in the best value of a 
     //       branch and less in the expected value. (--> Review "Extreme Bandit" literature again)
-    // TODO: Constraint handling is too restrictive!  E.g. for Poly-10, if MCTS identifies the term x3*x4 first it is 
-    //       not possible to add the term x1*x2 later on. The same is true for individual terms after x2 it is not 
-    //       possible to multiply x1. It is easy to get stuck. Why do we actually need the current way of constraint handling?
-    //       It would probably be easier to use some kind of hashing to identify equivalent expressions in the tree.
-    // TODO: State unification (using hashing) is partially done. The hashcode calculation should be improved to also detect that 
-    //       c*x1 + c*x1*x1 + c*x1 is the same as c*x1 + c*x1*x1
+    // TODO: Solve Poly-10
     // TODO: After state unification the recursive backpropagation of results takes a lot of time. How can this be improved?
+    // TODO: unit tests for benchmark problems which contain log / exp / x^-1 but without numeric constants 
     // TODO: check if transformation of y is correct and works (Obj 2)
     // TODO: The algorithm is not invariant to location and scale of variables. 
@@ -71 +68 @@
     // TODO: support e(-x) and possibly (1/-x) (Obj 1)
     // TODO: is it OK to initialize all constants to 1 (Obj 2)?
+    // TODO: improve memory usage
     #region static API
 
@@ -179 +177 @@
         this.testEvaluator = new ExpressionEvaluator(testY.Length, lowerEstimationLimit, upperEstimationLimit);
 
-        this.automaton = new Automaton(x, new SimpleConstraintHandler(100), allowProdOfVars, allowExp, allowLog, allowInv, allowMultipleTerms);
+        this.automaton = new Automaton(x, new SimpleConstraintHandler(maxVariables), allowProdOfVars, allowExp, allowLog, allowInv, allowMultipleTerms);
         this.treePolicy = treePolicy ?? new Ucb();
         this.tree = new Tree() {
           state = automaton.CurrentState,
           actionStatistics = treePolicy.CreateActionStatistics(),
-          expr = ""
+          expr = "",
+          level = 0
         };
 
@@ -497 +496 @@
       mctsState.effectiveRollouts++;
 
-      if (mctsState.effectiveRollouts % 10 == 1) Console.WriteLine(WriteTree(tree));
+      if (mctsState.effectiveRollouts % 10 == 1) {
+        //Console.WriteLine(WriteTree(tree));
+        //Console.WriteLine(TraceTree(tree));
+      }
       return q;
     }
@@ -520 +522 @@
       // We do this until we reach a complete expression (final state)
 
-      // Loops in the graph are possible! (Problem?)
+      // Loops in the graph are prevented by checking that the level of a child must be larger than the level of the parent
       // Sub-graphs which have been completely searched are marked as done.
       // Roll-out could lead to a state where all follow-states are done. In this case we call the rollout ineffective.
@@ -526 +528 @@
       while (!automaton.IsFinalState(automaton.CurrentState)) {
         if (children.ContainsKey(tree)) {
+          if (children[tree].All(ch => ch.Done)) {
+            tree.Done = true;
+            break;
+          }
           // ROLLOUT INSIDE TREE
           // UCT selection within tree
@@ -540 +546 @@
           int nFs;
           automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
-          while (nFs == 1 && !automaton.IsEvalState(possibleFollowStates[0])) {
+          while (nFs == 1 && !automaton.IsEvalState(possibleFollowStates[0]) && !automaton.IsFinalState(possibleFollowStates[0])) {
             automaton.Goto(possibleFollowStates[0]);
             automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
@@ -551 +557 @@
           int nFs;
           automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
-          while (nFs == 1 && !automaton.IsEvalState(possibleFollowStates[0])) {
+          while (nFs == 1 && !automaton.IsEvalState(possibleFollowStates[0]) && !automaton.IsFinalState(possibleFollowStates[0])) {
             // no alternatives -> just go to the next state
             automaton.Goto(possibleFollowStates[0]);
@@ -565 +571 @@
           for (int i = 0; i < nFs; i++) {
             Tree child = null;
-            // for selected states we introduce state unification (detection of equivalent states)
+            // for selected states (EvalStates) we introduce state unification (detection of equivalent states)
             if (automaton.IsEvalState(possibleFollowStates[i])) {
               var hc = Hashcode(automaton);
@@ -573 +579 @@
                   state = possibleFollowStates[i],
                   actionStatistics = treePolicy.CreateActionStatistics(),
-                  expr = ExprStr(automaton)
+                  expr = string.Empty, // ExprStr(automaton),
+                  level = tree.level + 1
                 };
                 nodes.Add(hc, child);
-              } else {
+              }
+              // only allow forward edges (don't add the child if we would go back in the graph)
+              else if (child.level > tree.level) {
                 // whenever we join paths we need to propagate back the statistics of the existing node through the newly created link
                 // to all parents 
                 BackpropagateStatistics(child.actionStatistics, tree);
+              } else {
+                // prevent cycles
+                Debug.Assert(child.level <= tree.level);
+                child = null;
               }
             } else {
@@ -586 +599 @@
                 state = possibleFollowStates[i],
                 actionStatistics = treePolicy.CreateActionStatistics(),
-                expr = ExprStr(automaton)
+                expr = string.Empty, // ExprStr(automaton),
+                level = tree.level + 1
               };
             }
-            newChildren.Add(child);
+            if (child != null)
+              newChildren.Add(child);
+          }
+
+          if (!newChildren.Any()) {
+            // stuck in a dead end (no final state and no allowed follow states)
+            tree.Done = true;
+            break;
           }
 
@@ -599 +620 @@
           }
 
+
           // follow one of the children
           tree = SelectFinalOrRandom2(automaton, tree, rand);
@@ -610 +632 @@
       if (automaton.IsFinalState(automaton.CurrentState)) {
         tree.Done = true;
+        tree.expr = ExprStr(automaton);
         byte[] code; int nParams;
         automaton.GetCode(out code, out nParams);
@@ -636 +659 @@
       // EXPERIMENTAL!
       // optimal result: q = 1 -> return huge value
-      if (q >= 1.0) return 1E16;
-      // return number of 9s in R²
-      return -Math.Log10(1 - q);
+      // if (q >= 1.0) return 1E16;
+      // // return number of 9s in R²
+      // return -Math.Log10(1 - q);
     }
 
@@ -852 +875 @@
       return sb.ToString();
     }
+
+    private static string TraceTree(Tree tree) {
+      var sb = new StringBuilder();
+      sb.Append(
+@"digraph {
+  ratio = fill;
+  node [style=filled];
+");
+      int nodeId = 0;
+
+      TraceTreeRec(tree, 0, sb, ref nodeId);
+      sb.Append("}");
+      return sb.ToString();
+    }
+
+    private static void TraceTreeRec(Tree tree, int parentId, StringBuilder sb, ref int nextId) {
+      var avgNodeQ = tree.actionStatistics.AverageQuality;
+      var tries = tree.actionStatistics.Tries;
+      if (double.IsNaN(avgNodeQ)) avgNodeQ = 0.0;
+      var hue = (1 - avgNodeQ) / 360.0 * 240.0; // 0 equals red, 240 equals blue
+
+      sb.AppendFormat("{0} [label=\"{1:N3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", parentId, avgNodeQ, tries, hue).AppendLine();
+
+      var list = new List<Tuple<int, int, Tree>>();
+      if (children.ContainsKey(tree)) {
+        foreach (var ch in children[tree]) {
+          nextId++;
+          avgNodeQ = ch.actionStatistics.AverageQuality;
+          tries = ch.actionStatistics.Tries;
+          if (double.IsNaN(avgNodeQ)) avgNodeQ = 0.0;
+          hue = (1 - avgNodeQ) / 360.0 * 240.0; // 0 equals red, 240 equals blue
+          sb.AppendFormat("{0} [label=\"{1:N3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", nextId, avgNodeQ, tries, hue).AppendLine();
+          sb.AppendFormat("{0} -> {1}", parentId, nextId, avgNodeQ).AppendLine();
+          list.Add(Tuple.Create(tries, nextId, ch));
+        }
+        foreach (var tup in list.OrderByDescending(t => t.Item1).Take(1)) {
+          TraceTreeRec(tup.Item3, tup.Item2, sb, ref nextId);
+        }
+      }
+    }
+
     private static string WriteTree(Tree tree) {
       var sb = new System.IO.StringWriter(System.Globalization.CultureInfo.InvariantCulture);
@@ -860 +924 @@
   node [style=filled];
 ");
-      foreach(var kvp in children) {
+      int threshold = nodes.Count > 500 ? 10 : 0;
+      foreach (var kvp in children) {
         var parent = kvp.Key;
         int parentId;
-        if(!nodeIds.TryGetValue(parent, out parentId)) {
+        if (!nodeIds.TryGetValue(parent, out parentId)) {
           parentId = nodeIds.Count + 1;
-          var avgNodeQ = parent.actionStatistics.AverageQuality; 
+          var avgNodeQ = parent.actionStatistics.AverageQuality;
           var tries = parent.actionStatistics.Tries;
           if (double.IsNaN(avgNodeQ)) avgNodeQ = 0.0;
-          var hue = (1 - avgNodeQ) / 255.0 * 240.0; // 0 equals red, 240 equals blue
-          sb.Write("{0} [label=\"{1:N3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", parentId, avgNodeQ, tries, hue);
+          var hue = (1 - avgNodeQ) / 360.0 * 240.0; // 0 equals red, 240 equals blue
+          if (parent.actionStatistics.Tries > threshold)
+            sb.Write("{0} [label=\"{1:N3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", parentId, avgNodeQ, tries, hue);
           nodeIds.Add(parent, parentId);
         }
-        foreach(var child in kvp.Value) {
+        foreach (var child in kvp.Value) {
           int childId;
-          if(!nodeIds.TryGetValue(child, out childId)) {
+          if (!nodeIds.TryGetValue(child, out childId)) {
             childId = nodeIds.Count + 1;
             nodeIds.Add(child, childId);
@@ -882 +948 @@
           if (tries < 1) continue;
           if (double.IsNaN(avgNodeQ)) avgNodeQ = 0.0;
-          var hue = (1 - avgNodeQ) / 255.0 * 240.0; // 0 equals red, 240 equals blue
-          sb.Write("{0} [label=\"{1:N3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", childId, avgNodeQ, tries, hue);
-          var edgeLabel = child.expr;
-          if (parent.expr.Length > 0) edgeLabel = edgeLabel.Replace(parent.expr, "");
-          sb.Write("{0} -> {1} [label=\"{3}\"]", parentId, childId, avgNodeQ, edgeLabel);
+          var hue = (1 - avgNodeQ) / 360.0 * 240.0; // 0 equals red, 240 equals blue
+          if (tries > threshold) {
+            sb.Write("{0} [label=\"{1:N3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", childId, avgNodeQ, tries, hue);
+            var edgeLabel = child.expr;
+            // if (parent.expr.Length > 0) edgeLabel = edgeLabel.Replace(parent.expr, "");
+            sb.Write("{0} -> {1} [label=\"{3}\"]", parentId, childId, avgNodeQ, edgeLabel);
+          }
         }
       }

branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/Ucb.cs

@@ -1 +1 @@
 using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Diagnostics.Contracts;
 using System.Linq;
@@ -81 +82 @@
         return buf[rand.Next(buf.Count)];
       }
-      Contract.Assert(totalTries > 0);
+      Debug.Assert(totalTries > 0);
       double logTotalTries = Math.Log(totalTries);
       var bestQ = double.NegativeInfinity;

branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/SimpleConstraintHandler.cs

@@ -31 +31 @@
 
     public bool IsAllowedFollowState(int currentState, int followState) {
-      return numVariables < maxVariables || (
-        followState != Automaton.StateExpFactorStart &&
-        followState != Automaton.StateFactorStart &&
-        followState != Automaton.StateTermStart &&
-        followState != Automaton.StateLogTStart &&
-        followState != Automaton.StateLogTFStart &&
-        followState != Automaton.StateInvTStart &&
-        followState != Automaton.StateInvTFStart);
+      return numVariables < maxVariables ||
+        // going to the final state is always allowed (smaller states are closer to the final state)
+        currentState > followState;
+        // (
+        // followState != Automaton.StateExpFactorStart &&
+        // followState != Automaton.StateFactorStart &&
+        // followState != Automaton.StateTermStart &&
+        // followState != Automaton.StateLogTStart &&
+        // followState != Automaton.StateLogTFStart &&
+        // followState != Automaton.StateInvTStart &&
+        // followState != Automaton.StateInvTFStart);
     }
 

branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Tree.cs

@@ -26 +26 @@
   internal class Tree {
     public int state;
+    public int level;
     public string expr;
     public bool Done {