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

Timestamp:

10/20/17 12:38:06 (7 years ago)

Author:

gkronber

Message:

#2796 made several changes for debugging

Location:

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

Files:

• MctsSymbolicRegressionStatic.cs (modified) (14 diffs)
• Policies/EpsGreedy.cs (modified) (3 diffs)
• Policies/GreedyUcbTuned.cs (added)
• Policies/IActionStatistics.cs (modified) (1 diff)
• Policies/Ucb.cs (modified) (4 diffs)
• Policies/UcbTuned.cs (modified) (3 diffs)

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

@@ -56 +56 @@
     //    
 
-    // 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: The samples of x1*... or x2*... do not give any information about the relevance of the interaction term x1*x2 in general!
+    //       --> E.g. if x1, x2 ~ N(0, 1) or U(-1, 1) this is trivial to show
+    //       --> Therefore, looking at rollout statistics for arm selection is useless in the general case!
+    //       --> It is necessary to rely on other features for the arm selection. 
+    //       --> TODO: Which heuristics can we apply? 
     // TODO: Solve Poly-10
     // TODO: After state unification the recursive backpropagation of results takes a lot of time. How can this be improved?
@@ -72 +74 @@
     // TODO: improve memory usage
     // TODO: support empty test partition
+    // TODO: the algorithm should be invariant to linear transformations of the space (y = f(x') = f( Ax ) ) for invertible transformations A --> unit tests
     #region static API
 
@@ -143 +146 @@
       // calculate for each level the number of alternatives the average 'inequality' of tries and 'inequality' of quality over the alternatives for each trie
       // inequality can be calculated using the Gini coefficient
-      internal readonly double[] giniCoeffs = new double[100];
-      
+      internal readonly double[] pathGiniCoeffs = new double[100];
+      internal readonly double[] pathQs = new double[100];
+      internal readonly double[] levelBestQ = new double[100];
+      // internal readonly double[] levelMaxTries = new double[100];
+      internal readonly double[] pathBestQ = new double[100]; // as long as pathBestQs = levelBestQs we are following the correct path
+      internal readonly string[] levelBestAction = new string[100];
+      internal readonly string[] curAction = new string[100];
+      internal readonly double[] pathSelectedQ = new double[100];
 
       public State(IRegressionProblemData problemData, uint randSeed, int maxVariables, bool scaleVariables,
@@ -448 +457 @@
 #if DEBUG
       internal void ClearStats() {
-        for (int i = 0; i < giniCoeffs.Length; i++) giniCoeffs[i] = -1;
-      }
-      internal void WriteStats() {
-        Console.WriteLine(string.Join("\t", giniCoeffs.TakeWhile(x => x >= 0).Select(x => string.Format("{0:N3}", x))));
-      }
+        for (int i = 0; i < pathGiniCoeffs.Length; i++) pathGiniCoeffs[i] = -1;
+        for (int i = 0; i < pathQs.Length; i++) pathGiniCoeffs[i] = -99;
+        for (int i = 0; i < pathBestQ.Length; i++) pathBestQ[i] = -99;
+        for (int i = 0; i < pathSelectedQ.Length; i++) pathSelectedQ[i] = -99;
+      }
+      internal void WriteGiniStats() {
+        Console.WriteLine(string.Join("\t", pathGiniCoeffs.TakeWhile(x => x >= 0).Select(x => string.Format("{0:N3}", x))));
+      }
+      internal void WriteQs() {
+        // Console.WriteLine(string.Join("\t", pathQs.TakeWhile(x => x >= -100).Select(x => string.Format("{0:N3}", x))));
+        var sb = new StringBuilder();
+        // length
+        int i = 0;
+        while (i < pathBestQ.Length && pathBestQ[i] > -99 && pathBestQ[i] == levelBestQ[i]) {
+          i++;
+        }
+        sb.AppendFormat("{0,-3}",i);
+
+        i = 0;
+        // sb.AppendFormat("{0:N3}", levelBestQ[0]);
+        while (i < pathSelectedQ.Length && pathSelectedQ[i] > -99) {
+          sb.AppendFormat("\t{0:N3}", pathSelectedQ[i]);
+          i++;
+        }
+        Console.WriteLine(sb.ToString());
+        sb.Clear();
+        i = 0;
+        // sb.AppendFormat("{0:N3}", levelBestQ[0]);
+        while (i < pathBestQ.Length && pathBestQ[i] > -99) {
+          sb.AppendFormat("\t{0:N3}", pathBestQ[i]);
+          i++;
+        }
+        Console.WriteLine(sb.ToString());
+        sb.Clear();
+        i = 0;
+        while (i < pathBestQ.Length && pathBestQ[i] > -99) {
+          sb.AppendFormat("\t{0:N3}", levelBestQ[i]);
+          i++;
+        }
+        Console.WriteLine(sb.ToString());
+        
+        sb.Clear();
+        i = 0;
+        while (i < pathBestQ.Length && pathBestQ[i] > -99) {
+          sb.AppendFormat("\t{0,-5}", (curAction[i] != null && curAction[i].Length > 5) ? curAction[i].Substring(0, 5) : curAction[i]);
+          i++;
+        }
+        Console.WriteLine(sb.ToString());
+        sb.Clear();
+        i = 0;
+        while (i < pathBestQ.Length && pathBestQ[i] > -99) {
+          sb.AppendFormat("\t{0,-5}", (levelBestAction[i] != null && levelBestAction[i].Length > 5) ? levelBestAction[i].Substring(0, 5) : levelBestAction[i]);
+          i++;
+        }
+        Console.WriteLine(sb.ToString());
+        
+        Console.WriteLine();
+      }
+
 
 #endif
@@ -525 +588 @@
 
 #if DEBUG
-      mctsState.WriteStats();
+      // mctsState.WriteGiniStats();
+      Console.WriteLine(ExprStr(automaton));
+      mctsState.WriteQs();
+      // Console.WriteLine(WriteStatistics(tree, mctsState));
+
 #endif
       //if (mctsState.effectiveRollouts % 100 == 1) {
@@ -564 +631 @@
             selectedIdx = treePolicy.Select(state.children[tree].Select(ch => ch.actionStatistics), rand);
           }
-
+          
           // STATS
-          state.giniCoeffs[tree.level] = InequalityCoefficient(state.children[tree].Select(ch => (double)ch.actionStatistics.AverageQuality));
+          state.pathGiniCoeffs[tree.level] = InequalityCoefficient(state.children[tree].Select(ch => (double)ch.actionStatistics.AverageQuality));
+          state.pathQs[tree.level] = tree.actionStatistics.AverageQuality;
 
           tree = state.children[tree][selectedIdx];
@@ -576 +644 @@
           int nFs;
           automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
-          while (automaton.CurrentState != tree.state && nFs == 1 && 
-            !automaton.IsEvalState(possibleFollowStates[0]) && !automaton.IsFinalState(possibleFollowStates[0])) {
-            automaton.Goto(possibleFollowStates[0]);
-            automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
-          }
+          // TODO!
+          // while (possibleFollowStates[0] != tree.state && nFs == 1 && 
+          //   !automaton.IsEvalState(possibleFollowStates[0]) && !automaton.IsFinalState(possibleFollowStates[0])) {
+          //   automaton.Goto(possibleFollowStates[0]);
+          //   automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
+          // }
           Debug.Assert(possibleFollowStates.Contains(tree.state));
           automaton.Goto(tree.state);
@@ -589 +658 @@
           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]);
-            automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
-          }
+          // TODO
+          // 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]);
+          //   automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
+          // }
           if (nFs == 0) {
             // stuck in a dead end (no final state and no allowed follow states)
@@ -672 +742 @@
         q = TransformQuality(q);
         success = true;
+        BackpropagateQuality(tree, q, treePolicy, state);        
       } else {
         // we got stuck in roll-out (not evaluation necessary!)
@@ -682 +753 @@
       // Update statistics
       // Set branch to done if all children are done.
-      BackpropagateQuality(tree, q, treePolicy, state);
+      BackpropagateDone(tree, state);
+      BackpropagateDebugStats(tree, q, state);
+
 
       return success;
@@ -703 +776 @@
     private static double TransformQuality(double q) {
       // no transformation
-      // return q;
+      return q;
 
       // EXPERIMENTAL!
@@ -738 +811 @@
 
     private static void BackpropagateQuality(Tree tree, double q, IPolicy policy, State state) {
-      if (q > 0) policy.Update(tree.actionStatistics, q);
+      policy.Update(tree.actionStatistics, q);
+
+      if (state.parents.ContainsKey(tree)) {
+        foreach (var parent in state.parents[tree]) {
+          BackpropagateQuality(parent, q, policy, state);
+        }
+      }
+    }
+
+    private static void BackpropagateDone(Tree tree, State state) {
       if (state.children.ContainsKey(tree) && state.children[tree].All(ch => ch.Done)) {
         tree.Done = true;
@@ -746 +828 @@
       if (state.parents.ContainsKey(tree)) {
         foreach (var parent in state.parents[tree]) {
-          BackpropagateQuality(parent, q, policy, state);
-        }
+          BackpropagateDone(parent, state);
+        }
+      }
+    }
+
+    private static void BackpropagateDebugStats(Tree tree, double q, State state) {
+      if (state.parents.ContainsKey(tree)) {
+        foreach (var parent in state.parents[tree]) {
+          BackpropagateDebugStats(parent, q, state);
+        }
+      }
+
+      state.pathSelectedQ[tree.level] = tree.actionStatistics.AverageQuality;
+      state.pathBestQ[tree.level] = tree.actionStatistics.BestQuality;
+      state.curAction[tree.level] = tree.expr;
+      if (state.levelBestQ[tree.level] < tree.actionStatistics.BestQuality) {
+        state.levelBestQ[tree.level] = tree.actionStatistics.BestQuality;
+        state.levelBestAction[tree.level] = tree.expr;
       }
     }
@@ -917 +1015 @@
     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);
+      sb.Write("{0}\t{1:N5}\t", tree.actionStatistics.Tries, tree.actionStatistics.AverageQuality);
       if (state.children.ContainsKey(tree)) {
         foreach (var ch in state.children[tree]) {
-          sb.WriteLine("{0} {1:N5}", ch.actionStatistics.Tries, ch.actionStatistics.AverageQuality);
-        }
-      }
+          sb.Write("{0}\t{1:N5}\t", ch.actionStatistics.Tries, ch.actionStatistics.AverageQuality);
+        }
+      }
+      sb.WriteLine();
       return sb.ToString();
     }

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

@@ -18 +18 @@
       public double SumQuality { get; set; }
       public double AverageQuality { get { return SumQuality / Tries; } }
+      public double BestQuality { get; internal set; }
       public int Tries { get; set; }
       public bool Done { get; set; }
@@ -26 +27 @@
         this.Tries += o.Tries;
         this.SumQuality += o.SumQuality;
+        this.BestQuality = Math.Max(this.BestQuality, other.BestQuality);
       }
     }
@@ -60 +62 @@
       var a = action as ActionStatistics;
       a.SumQuality += q;
+      a.BestQuality = Math.Max(a.BestQuality, q);
       a.Tries++;
     }

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

@@ -8 +8 @@
   public interface IActionStatistics {
     double AverageQuality { get; }
+    double BestQuality { get; }
     int Tries { get; }
     bool Done { get; set; }

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

@@ -19 +19 @@
       public double SumQuality { get; set; }
       public double AverageQuality { get { return SumQuality / Tries; } }
+      public double BestQuality { get; internal set; }
       public int Tries { get; set; }
       public bool Done { get; set; }
@@ -26 +27 @@
         this.Tries += o.Tries;
         this.SumQuality += o.SumQuality;
+        this.BestQuality = Math.Max(this.BestQuality, other.BestQuality);
       }
     }
@@ -60 +62 @@
       var a = action as ActionStatistics;
       a.SumQuality += q;
+      a.BestQuality = Math.Max(a.BestQuality, q);
       a.Tries++;
     }
@@ -82 +85 @@
         return buf[rand.Next(buf.Count)];
       }
+
+      Debug.Assert(actions.All(a => a.Done || a.Tries > 0));
                      
       Debug.Assert(totalTries > 0);

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

@@ -19 +19 @@
       public double SumSqrQuality { get; set; }
       public double AverageQuality { get { return SumQuality / Tries; } }
+      public double BestQuality { get; internal set; }
       public double QualityVariance { get { return SumSqrQuality / Tries - AverageQuality * AverageQuality; } }
       public int Tries { get; set; }
@@ -29 +30 @@
         this.SumQuality += o.SumQuality;
         this.SumSqrQuality += o.SumSqrQuality;
+        this.BestQuality = Math.Max(this.BestQuality, other.BestQuality);
       }
     }
@@ -64 +66 @@
       a.SumQuality += q;
       a.SumSqrQuality += q * q;
+      a.BestQuality = Math.Max(a.BestQuality, q);
       a.Tries++;
     }