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

Timestamp:

10/06/17 17:52:36 (7 years ago)

Author:

gkronber

Message:

#2796 worked on MCTS (removing constraint handling and introducing state unification instead)

File:

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

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

@@ -22 +22 @@
 using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Diagnostics.Contracts;
 using System.Linq;
@@ -54 +55 @@
     //    
 
+    // TODO: Taking averages of R² values is probably not ideal as an improvement of R² from 0.99 to 0.999 should 
+    //       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: After state unification the recursive backpropagation of results takes a lot of time. How can this be improved?
     // TODO: check if transformation of y is correct and works (Obj 2)
     // TODO: The algorithm is not invariant to location and scale of variables. 
@@ -172 +179 @@
         this.testEvaluator = new ExpressionEvaluator(testY.Length, lowerEstimationLimit, upperEstimationLimit);
 
-        this.automaton = new Automaton(x, maxVariables, allowProdOfVars, allowExp, allowLog, allowInv, allowMultipleTerms);
+        this.automaton = new Automaton(x, new SimpleConstraintHandler(100), allowProdOfVars, allowExp, allowLog, allowInv, allowMultipleTerms);
         this.treePolicy = treePolicy ?? new Ucb();
-        this.tree = new Tree() { state = automaton.CurrentState, actionStatistics = treePolicy.CreateActionStatistics() };
+        this.tree = new Tree() {
+          state = automaton.CurrentState,
+          actionStatistics = treePolicy.CreateActionStatistics(),
+          expr = ""
+        };
 
         // reset best solution
@@ -481 +492 @@
       do {
         automaton.Reset();
-        success = TryTreeSearchRec(rand, tree, automaton, eval, treePolicy, out q);
+        success = TryTreeSearchRec2(rand, tree, automaton, eval, treePolicy, out q);
         mctsState.totalRollouts++;
       } while (!success && !tree.Done);
       mctsState.effectiveRollouts++;
+
+      if (mctsState.effectiveRollouts % 10 == 1) Console.WriteLine(WriteTree(tree));
       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,
+      out double q) {
+      // ROLLOUT AND EXPANSION
+      // We are navigating a graph (states might be reached via different paths) instead of a tree.
+      // State equivalence is checked through ExprHash (based on the generated code through the path).
+
+      // We switch between rollout-mode and expansion mode
+      // Rollout-mode means we are navigating an existing path through the tree (using a rollout policy, e.g. UCB)
+      // Expansion mode means we expand the graph, creating new nodes and edges (using an expansion policy, e.g. shortest route to a complete expression)
+      // In expansion mode we might re-enter the graph and switch back to rollout-mode
+      // We do this until we reach a complete expression (final state)
+
+      // Loops in the graph are possible! (Problem?)
+      // 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.
+
+      while (!automaton.IsFinalState(automaton.CurrentState)) {
+        if (children.ContainsKey(tree)) {
+          // ROLLOUT INSIDE TREE
+          // 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];
+
+          // move the automaton forward until reaching the state
+          // all steps where no alternatives are possible are immediately taken
+          // TODO: simplification of the automaton 
+          int[] possibleFollowStates;
+          int nFs;
+          automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
+          while (nFs == 1 && !automaton.IsEvalState(possibleFollowStates[0])) {
+            automaton.Goto(possibleFollowStates[0]);
+            automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
+          }
+          Debug.Assert(possibleFollowStates.Contains(tree.state));
+          automaton.Goto(tree.state);
+        } else {
+          // EXPAND 
+          int[] possibleFollowStates;
+          int nFs;
+          automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
+          while (nFs == 1 && !automaton.IsEvalState(possibleFollowStates[0])) {
+            // no alternatives -> just go to the next state
+            automaton.Goto(possibleFollowStates[0]);
+            automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
+          }
+          if (nFs == 0) {
+            // stuck in a dead end (no final state and no allowed follow states)
+            tree.Done = true;
+            break;
+          }
+          var newChildren = new List<Tree>(nFs);
+          children.Add(tree, newChildren);
+          for (int i = 0; i < nFs; i++) {
+            Tree child = null;
+            // for selected states we introduce state unification (detection of equivalent states)
+            if (automaton.IsEvalState(possibleFollowStates[i])) {
+              var hc = Hashcode(automaton);
+              if (!nodes.TryGetValue(hc, out child)) {
+                child = new Tree() {
+                  children = null,
+                  state = possibleFollowStates[i],
+                  actionStatistics = treePolicy.CreateActionStatistics(),
+                  expr = ExprStr(automaton)
+                };
+                nodes.Add(hc, child);
+              } else {
+                // 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 {
+              child = new Tree() {
+                children = null,
+                state = possibleFollowStates[i],
+                actionStatistics = treePolicy.CreateActionStatistics(),
+                expr = ExprStr(automaton)
+              };
+            }
+            newChildren.Add(child);
+          }
+
+          foreach (var ch in newChildren) {
+            if (!parents.ContainsKey(ch)) {
+              parents.Add(ch, new List<Tree>());
+            }
+            parents[ch].Add(tree);
+          }
+
+          // follow one of the children
+          tree = SelectFinalOrRandom2(automaton, tree, rand);
+          automaton.Goto(tree.state);
+        }
+      }
+
+      bool success;
+
+      // EVALUATE TREE
+      if (automaton.IsFinalState(automaton.CurrentState)) {
+        tree.Done = true;
+        byte[] code; int nParams;
+        automaton.GetCode(out code, out nParams);
+        q = eval(code, nParams);
+        q = TransformQuality(q);
+        success = true;
+      } else {
+        // we got stuck in roll-out (not evaluation necessary!)
+        q = 0.0;
+        success = false;
+      }
+
+      // RECURSIVELY BACKPROPAGATE RESULTS TO ALL PARENTS
+      // Update statistics
+      // Set branch to done if all children are done.
+      BackpropagateQuality(tree, q, treePolicy);
+
+      return success;
+    }
+
+
+    private static double TransformQuality(double q) {
+      // no transformation
+      return q;
+
+      // 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);
+    }
+
+    // backpropagate existing statistics to all parents
+    private static void BackpropagateStatistics(IActionStatistics stats, Tree tree) {
+      tree.actionStatistics.Add(stats);
+      if (parents.ContainsKey(tree)) {
+        foreach (var parent in parents[tree]) {
+          BackpropagateStatistics(stats, parent);
+        }
+      }
+    }
+
+    private static ulong Hashcode(Automaton automaton) {
+      byte[] code;
+      int nParams;
+      automaton.GetCode(out code, out nParams);
+      return ExprHash.GetHash(code, nParams);
+    }
+
+    private static void BackpropagateQuality(Tree tree, double q, IPolicy policy) {
+      if (q > 0) policy.Update(tree.actionStatistics, q);
+      if (children.ContainsKey(tree) && 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)) {
+          selectedChildIdx = i;
+          break;
+        }
+      }
+      // no final state -> select the first child
+      if (selectedChildIdx == -1) {
+        selectedChildIdx = 0;
+      }
+      return children[selectedChildIdx];
     }
 
@@ -522 +725 @@
           tree.children = new Tree[nFs];
           for (int i = 0; i < tree.children.Length; i++)
-            tree.children[i] = new Tree() { children = null, state = possibleFollowStates[i], actionStatistics = treePolicy.CreateActionStatistics() };
+            tree.children[i] = new Tree() {
+              children = null,
+              state = possibleFollowStates[i],
+              actionStatistics = treePolicy.CreateActionStatistics()
+            };
 
           selectedChild = nFs > 1 ? SelectFinalOrRandom(automaton, tree, rand) : tree.children[0];
@@ -624 +831 @@
       }
     }
+
+    // for debugging only
+
+
+    private static string ExprStr(Automaton automaton) {
+      byte[] code;
+      int nParams;
+      automaton.GetCode(out code, out nParams);
+      return Disassembler.CodeToString(code);
+    }
+
+    private static string WriteStatistics(Tree tree) {
+      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]) {
+          sb.WriteLine("{0} {1:N5}", ch.actionStatistics.Tries, ch.actionStatistics.AverageQuality);
+        }
+      }
+      return sb.ToString();
+    }
+    private static string WriteTree(Tree tree) {
+      var sb = new System.IO.StringWriter(System.Globalization.CultureInfo.InvariantCulture);
+      var nodeIds = new Dictionary<Tree, int>();
+      sb.Write(
+@"digraph {
+  ratio = fill;
+  node [style=filled];
+");
+      foreach(var kvp in children) {
+        var parent = kvp.Key;
+        int parentId;
+        if(!nodeIds.TryGetValue(parent, out parentId)) {
+          parentId = nodeIds.Count + 1;
+          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);
+          nodeIds.Add(parent, parentId);
+        }
+        foreach(var child in kvp.Value) {
+          int childId;
+          if(!nodeIds.TryGetValue(child, out childId)) {
+            childId = nodeIds.Count + 1;
+            nodeIds.Add(child, childId);
+          }
+          var avgNodeQ = child.actionStatistics.AverageQuality;
+          var tries = child.actionStatistics.Tries;
+          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);
+        }
+      }
+
+      sb.Write("}");
+      return sb.ToString();
+    }
   }
 }