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

Timestamp:

10/11/17 08:15:19 (5 years ago)

Author:

gkronber

Message:

#2796 worked on MCTS for symbreg

File:

• branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/MctsSymbolicRegressionStatic.cs (modified) (30 diffs)

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

@@ -61 +61 @@
     // TODO: Solve Poly-10
     // TODO: After state unification the recursive backpropagation of results takes a lot of time. How can this be improved?
+    // TODO: Why is the algorithm so slow for rather greedy policies (e.g. low C value in UCB)?
+    // TODO: check if we can use a quality measure with range [-1..1] in policies
     // 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)
@@ -117 +119 @@
       private readonly ExpressionEvaluator evaluator, testEvaluator;
 
+      internal readonly Dictionary<Tree, List<Tree>> children = new Dictionary<Tree, List<Tree>>();
+      internal readonly Dictionary<Tree, List<Tree>> parents = new Dictionary<Tree, List<Tree>>();
+      internal readonly Dictionary<ulong, Tree> nodes = new Dictionary<ulong, Tree>();
+
       // values for best solution
-      private double bestRSq;
+      private double bestR;
       private byte[] bestCode;
       private int bestNParams;
@@ -187 +193 @@
 
         // reset best solution
-        this.bestRSq = 0;
+        this.bestR = 0;
         // code for default solution (constant model)
         this.bestCode = new byte[] { (byte)OpCodes.LoadConst0, (byte)OpCodes.Exit };
@@ -208 +214 @@
         get {
           evaluator.Exec(bestCode, x, bestConsts, predBuf);
-          return RSq(y, predBuf);
+          return Rho(y, predBuf);
         }
       }
@@ -215 +221 @@
         get {
           testEvaluator.Exec(bestCode, testX, bestConsts, testPredBuf);
-          return RSq(testY, testPredBuf);
+          return Rho(testY, testPredBuf);
         }
       }
@@ -248 +254 @@
 
         // single objective best
-        if (q > bestRSq) {
-          bestRSq = q;
+        if (q > bestR) {
+          bestR = q;
           bestNParams = nParams;
           this.bestCode = new byte[code.Length];
@@ -266 +272 @@
       }
 
-      private void Eval(byte[] code, int nParams, out double rsq, out double[] optConsts) {
+      private void Eval(byte[] code, int nParams, out double rho, out double[] optConsts) {
         // we make a first pass to determine a valid starting configuration for all constants
         // constant c in log(c + f(x)) is adjusted to guarantee that x is positive (see expression evaluator)
@@ -280 +286 @@
           // if we don't need to optimize parameters then we are done
           // changing scale and offset does not influence r²
-          rsq = RSq(y, predBuf);
+          rho = Rho(y, predBuf);
           optConsts = constsBuf;
         } else {
@@ -289 +295 @@
           funcEvaluations++;
 
-          rsq = RSq(y, predBuf);
+          rho = Rho(y, predBuf);
           optConsts = constsBuf;
         }
@@ -297 +303 @@
 
       #region helpers
-      private static double RSq(IEnumerable<double> x, IEnumerable<double> y) {
+      private static double Rho(IEnumerable<double> x, IEnumerable<double> y) {
         OnlineCalculatorError error;
         double r = OnlinePearsonsRCalculator.Calculate(x, y, out error);
-        return error == OnlineCalculatorError.None ? r * r : 0.0;
+        return error == OnlineCalculatorError.None ? r : 0.0;
       }
 
@@ -491 +497 @@
       do {
         automaton.Reset();
-        success = TryTreeSearchRec2(rand, tree, automaton, eval, treePolicy, out q);
+        success = TryTreeSearchRec2(rand, tree, automaton, eval, treePolicy, mctsState, out q);
         mctsState.totalRollouts++;
       } while (!success && !tree.Done);
       mctsState.effectiveRollouts++;
 
-      if (mctsState.effectiveRollouts % 10 == 1) {
-        //Console.WriteLine(WriteTree(tree));
-        //Console.WriteLine(TraceTree(tree));
-      }
+      //if (mctsState.effectiveRollouts % 100 == 1) {
+        // Console.WriteLine(WriteTree(tree, mctsState));
+        // Console.WriteLine(TraceTree(tree, mctsState));
+      //}
       return q;
     }
-
-    private static Dictionary<Tree, List<Tree>> children = new Dictionary<Tree, List<Tree>>();
-    private static Dictionary<Tree, List<Tree>> parents = new Dictionary<Tree, List<Tree>>();
-    private static Dictionary<ulong, Tree> nodes = new Dictionary<ulong, Tree>();
-
 
 
     // search forward
     private static bool TryTreeSearchRec2(IRandom rand, Tree tree, Automaton automaton, Func<byte[], int, double> eval, IPolicy treePolicy,
+      State state,
       out double q) {
       // ROLLOUT AND EXPANSION
@@ -527 +529 @@
 
       while (!automaton.IsFinalState(automaton.CurrentState)) {
-        if (children.ContainsKey(tree)) {
-          if (children[tree].All(ch => ch.Done)) {
+        if (state.children.ContainsKey(tree)) {
+          if (state.children[tree].All(ch => ch.Done)) {
             tree.Done = true;
             break;
@@ -535 +537 @@
           // UCT selection within tree
           int selectedIdx = 0;
-          if (children[tree].Count > 1) {
-            selectedIdx = treePolicy.Select(children[tree].Select(ch => ch.actionStatistics), rand);
-          }
-          tree = children[tree][selectedIdx];
+          if (state.children[tree].Count > 1) {
+            selectedIdx = treePolicy.Select(state.children[tree].Select(ch => ch.actionStatistics), rand);
+          }
+          tree = state.children[tree][selectedIdx];
 
           // move the automaton forward until reaching the state
@@ -556 +558 @@
           int[] possibleFollowStates;
           int nFs;
+          string actionString = "";
           automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
           while (nFs == 1 && !automaton.IsEvalState(possibleFollowStates[0]) && !automaton.IsFinalState(possibleFollowStates[0])) {
+            actionString += " " + automaton.GetActionString(automaton.CurrentState, possibleFollowStates[0]);
             // no alternatives -> just go to the next state
             automaton.Goto(possibleFollowStates[0]);
@@ -568 +572 @@
           }
           var newChildren = new List<Tree>(nFs);
-          children.Add(tree, newChildren);
+          state.children.Add(tree, newChildren);
           for (int i = 0; i < nFs; i++) {
             Tree child = null;
@@ -574 +578 @@
             if (automaton.IsEvalState(possibleFollowStates[i])) {
               var hc = Hashcode(automaton);
-              if (!nodes.TryGetValue(hc, out child)) {
+              if (!state.nodes.TryGetValue(hc, out child)) {
                 child = new Tree() {
                   children = null,
                   state = possibleFollowStates[i],
                   actionStatistics = treePolicy.CreateActionStatistics(),
-                  expr = string.Empty, // ExprStr(automaton),
+                  expr = actionString + automaton.GetActionString(automaton.CurrentState, possibleFollowStates[i]),
                   level = tree.level + 1
                 };
-                nodes.Add(hc, child);
+                state.nodes.Add(hc, child);
               }
               // only allow forward edges (don't add the child if we would go back in the graph)
-              else if (child.level > tree.level) {
+              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);
+                BackpropagateStatistics(child.actionStatistics, tree, state);
               } else {
                 // prevent cycles
                 Debug.Assert(child.level <= tree.level);
                 child = null;
-              }
+              }   
             } else {
               child = new Tree() {
@@ -599 +603 @@
                 state = possibleFollowStates[i],
                 actionStatistics = treePolicy.CreateActionStatistics(),
-                expr = string.Empty, // ExprStr(automaton),
+                expr = actionString + automaton.GetActionString(automaton.CurrentState, possibleFollowStates[i]),
                 level = tree.level + 1
               };
@@ -614 +618 @@
 
           foreach (var ch in newChildren) {
-            if (!parents.ContainsKey(ch)) {
-              parents.Add(ch, new List<Tree>());
+            if (!state.parents.ContainsKey(ch)) {
+              state.parents.Add(ch, new List<Tree>());
             }
-            parents[ch].Add(tree);
-          }
-
-
-          // follow one of the children
-          tree = SelectFinalOrRandom2(automaton, tree, rand);
+            state.parents[ch].Add(tree);
+          }
+
+
+          // follow one of the children 
+          tree = SelectStateLeadingToFinal(automaton, tree, rand, state);
           automaton.Goto(tree.state);
         }
@@ -636 +640 @@
         automaton.GetCode(out code, out nParams);
         q = eval(code, nParams);
+        // Console.WriteLine("{0:N4}\t{1}", q*q, tree.expr);
         q = TransformQuality(q);
         success = true;
       } else {
         // we got stuck in roll-out (not evaluation necessary!)
+        // Console.WriteLine("\t" + ExprStr(automaton) + " STOP");
         q = 0.0;
         success = false;
@@ -647 +653 @@
       // Update statistics
       // Set branch to done if all children are done.
-      BackpropagateQuality(tree, q, treePolicy);
+      BackpropagateQuality(tree, q, treePolicy, state);
 
       return success;
@@ -655 +661 @@
     private static double TransformQuality(double q) {
       // no transformation
-      return q;
+      // return q;
 
       // EXPERIMENTAL!
+
+      // Fisher transformation
+      // (assumes q is Correl(pred, target)
+
+      q = Math.Min(q,  0.99999999);
+      q = Math.Max(q, -0.99999999);
+      return 0.5 * Math.Log((1 + q) / (1 - q));
+
       // optimal result: q = 1 -> return huge value
       // if (q >= 1.0) return 1E16;
@@ -665 +679 @@
 
     // backpropagate existing statistics to all parents
-    private static void BackpropagateStatistics(IActionStatistics stats, Tree tree) {
+    private static void BackpropagateStatistics(IActionStatistics stats, Tree tree, State state) {
       tree.actionStatistics.Add(stats);
-      if (parents.ContainsKey(tree)) {
-        foreach (var parent in parents[tree]) {
-          BackpropagateStatistics(stats, parent);
+      if (state.parents.ContainsKey(tree)) {
+        foreach (var parent in state.parents[tree]) {
+          BackpropagateStatistics(stats, parent, state);
         }
       }
@@ -681 +695 @@
     }
 
-    private static void BackpropagateQuality(Tree tree, double q, IPolicy policy) {
+    private static void BackpropagateQuality(Tree tree, double q, IPolicy policy, State state) {
       if (q > 0) policy.Update(tree.actionStatistics, q);
-      if (children.ContainsKey(tree) && children[tree].All(ch => ch.Done)) {
+      if (state.children.ContainsKey(tree) && state.children[tree].All(ch => ch.Done)) {
         tree.Done = true;
         // children[tree] = null; keep all nodes
       }
 
-      if (parents.ContainsKey(tree)) {
-        foreach (var parent in parents[tree]) {
-          BackpropagateQuality(parent, q, policy);
-        }
-      }
-    }
-
-    private static Tree SelectFinalOrRandom2(Automaton automaton, Tree tree, IRandom rand) {
-      // if one of the new children leads to a final state then go there
-      // otherwise choose a random child
-      int selectedChildIdx = -1;
-      // find first final state if there is one
-      var children = MctsSymbolicRegressionStatic.children[tree];
-      for (int i = 0; i < children.Count; i++) {
-        if (automaton.IsFinalState(children[i].state)) {
+      if (state.parents.ContainsKey(tree)) {
+        foreach (var parent in state.parents[tree]) {
+          BackpropagateQuality(parent, q, policy, state);
+        }
+      }
+    }
+
+    private static Tree SelectStateLeadingToFinal(Automaton automaton, Tree tree, IRandom rand, State state) {
+      // find the child with the smallest state value (smaller values are closer to the final state)
+      int selectedChildIdx = 0;
+      var children = state.children[tree];
+      Tree minChild = children.First();
+      for (int i = 1; i < children.Count; i++) {
+        if(children[i].state < minChild.state)
           selectedChildIdx = i;
-          break;
-        }
-      }
-      // no final state -> select the first child
-      if (selectedChildIdx == -1) {
-        selectedChildIdx = 0;
       }
       return children[selectedChildIdx];
@@ -865 +872 @@
     }
 
-    private static string WriteStatistics(Tree tree) {
+    private static string WriteStatistics(Tree tree, State state) {
       var sb = new System.IO.StringWriter();
       sb.WriteLine("{0} {1:N5}", tree.actionStatistics.Tries, tree.actionStatistics.AverageQuality);
-      if (children.ContainsKey(tree)) {
-        foreach (var ch in children[tree]) {
+      if (state.children.ContainsKey(tree)) {
+        foreach (var ch in state.children[tree]) {
           sb.WriteLine("{0} {1:N5}", ch.actionStatistics.Tries, ch.actionStatistics.AverageQuality);
         }
@@ -876 +883 @@
     }
 
-    private static string TraceTree(Tree tree) {
+    private static string TraceTree(Tree tree, State state) {
       var sb = new StringBuilder();
       sb.Append(
@@ -885 +892 @@
       int nodeId = 0;
 
-      TraceTreeRec(tree, 0, sb, ref nodeId);
+      TraceTreeRec(tree, 0, sb, ref nodeId, state);
       sb.Append("}");
       return sb.ToString();
     }
 
-    private static void TraceTreeRec(Tree tree, int parentId, StringBuilder sb, ref int nextId) {
+    private static void TraceTreeRec(Tree tree, int parentId, StringBuilder sb, ref int nextId, State state) {
       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();
+      hue = 0.0;
+
+      sb.AppendFormat("{0} [label=\"{1:E3} {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]) {
+      if (state.children.ContainsKey(tree)) {
+        foreach (var ch in state.children[tree]) {
           nextId++;
           avgNodeQ = ch.actionStatistics.AverageQuality;
@@ -906 +914 @@
           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();
+          hue = 0.0;
+          sb.AppendFormat("{0} [label=\"{1:E3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", nextId, avgNodeQ, tries, hue).AppendLine();
+          sb.AppendFormat("{0} -> {1} [label=\"{3}\"]", parentId, nextId, avgNodeQ, ch.expr).AppendLine();
           list.Add(Tuple.Create(tries, nextId, ch));
         }
+
+        foreach(var tup in list) {
+          var ch = tup.Item3;
+          var chId = tup.Item2;
+          if(state.children.ContainsKey(ch) && state.children[ch].Count == 1) {
+            var chch = state.children[ch].First();
+            nextId++;
+            avgNodeQ = chch.actionStatistics.AverageQuality;
+            tries = chch.actionStatistics.Tries;
+            if (double.IsNaN(avgNodeQ)) avgNodeQ = 0.0;
+            hue = (1 - avgNodeQ) / 360.0 * 240.0; // 0 equals red, 240 equals blue
+            hue = 0.0;
+            sb.AppendFormat("{0} [label=\"{1:E3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", nextId, avgNodeQ, tries, hue).AppendLine();
+            sb.AppendFormat("{0} -> {1} [label=\"{3}\"]", chId, nextId, avgNodeQ, chch.expr).AppendLine();
+          }
+        }
+
         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) {
+          TraceTreeRec(tup.Item3, tup.Item2, sb, ref nextId, state);
+        }
+      }
+    }
+
+    private static string WriteTree(Tree tree, State state) {
       var sb = new System.IO.StringWriter(System.Globalization.CultureInfo.InvariantCulture);
       var nodeIds = new Dictionary<Tree, int>();
@@ -924 +950 @@
   node [style=filled];
 ");
-      int threshold = nodes.Count > 500 ? 10 : 0;
-      foreach (var kvp in children) {
+      int threshold = /* state.nodes.Count > 500 ? 10 : */ 0;
+      foreach (var kvp in state.children) {
         var parent = kvp.Key;
         int parentId;
@@ -934 +960 @@
           if (double.IsNaN(avgNodeQ)) avgNodeQ = 0.0;
           var hue = (1 - avgNodeQ) / 360.0 * 240.0; // 0 equals red, 240 equals blue
+          hue = 0.0;
           if (parent.actionStatistics.Tries > threshold)
-            sb.Write("{0} [label=\"{1:N3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", parentId, avgNodeQ, tries, hue);
+            sb.Write("{0} [label=\"{1:E3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", parentId, avgNodeQ, tries, hue);
           nodeIds.Add(parent, parentId);
         }
@@ -949 +976 @@
           if (double.IsNaN(avgNodeQ)) avgNodeQ = 0.0;
           var hue = (1 - avgNodeQ) / 360.0 * 240.0; // 0 equals red, 240 equals blue
+          hue = 0.0;
           if (tries > threshold) {
-            sb.Write("{0} [label=\"{1:N3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", childId, avgNodeQ, tries, hue);
+            sb.Write("{0} [label=\"{1:E3} {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, "");