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

Timestamp:

10/27/17 18:42:04 (7 years ago)

Author:

gkronber

Message:

#2796 comments, simplifications, reviewed tests for structure enumeration (not working)

File:

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

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

@@ -63 +63 @@
     // 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
+    // ~~obsolete TODO: Why is the algorithm so slow for rather greedy policies (e.g. low C value in UCB)?
+    // ~~obsolete 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)
@@ -142 +142 @@
       private readonly double[] predBuf, testPredBuf;
       private readonly double[][] gradBuf;
-
-      // debugging stats
-      // 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[] 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,
@@ -200 +188 @@
 
         this.automaton = new Automaton(x, new SimpleConstraintHandler(maxVariables), allowProdOfVars, allowExp, allowLog, allowInv, allowMultipleTerms);
-        this.treePolicy = treePolicy ?? new Ucb();
+        this.treePolicy = treePolicy ?? new EpsilonGreedy();
         this.tree = new Tree() {
           state = automaton.CurrentState,
@@ -455 +443 @@
       #endregion
 
-#if DEBUG
-      internal void ClearStats() {
-        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
 
     }
@@ -578 +503 @@
       bool success = false;
       do {
-#if DEBUG
-        mctsState.ClearStats();
-#endif
+
         automaton.Reset();
         success = TryTreeSearchRec2(rand, tree, automaton, eval, treePolicy, mctsState, out q);
@@ -588 +511 @@
 
 #if DEBUG
-      // mctsState.WriteGiniStats();
       Console.WriteLine(ExprStr(automaton));
-      mctsState.WriteQs();
-      // Console.WriteLine(WriteStatistics(tree, mctsState));
-
 #endif
-      //if (mctsState.effectiveRollouts % 100 == 1) {
-      // Console.WriteLine(WriteTree(tree, mctsState));
-      // Console.WriteLine(TraceTree(tree, mctsState));
-      //}
       return q;
     }
@@ -620 +535 @@
 
       while (!automaton.IsFinalState(automaton.CurrentState)) {
+        Console.WriteLine(automaton.stateNames[automaton.CurrentState]);
         if (state.children.ContainsKey(tree)) {
           if (state.children[tree].All(ch => ch.Done)) {
@@ -631 +547 @@
             selectedIdx = treePolicy.Select(state.children[tree].Select(ch => ch.actionStatistics), rand);
           }
-          
-          // STATS
-          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];
 
           // move the automaton forward until reaching the state
-          // all steps where no alternatives are possible are immediately taken
+          // all steps where no alternatives could be taken immediately (without expanding the tree)
           // TODO: simplification of the automaton 
-          int[] possibleFollowStates;
+          int[] possibleFollowStates = new int[1000];
           int nFs;
-          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);
-          // }
+          automaton.FollowStates(automaton.CurrentState, ref possibleFollowStates, out nFs);
           Debug.Assert(possibleFollowStates.Contains(tree.state));
           automaton.Goto(tree.state);
         } else {
           // EXPAND 
-          int[] possibleFollowStates;
+          int[] possibleFollowStates = new int[1000];
           int nFs;
           string actionString = "";
-          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);
-          // }
+          automaton.FollowStates(automaton.CurrentState, ref possibleFollowStates, out nFs);
+
           if (nFs == 0) {
             // stuck in a dead end (no final state and no allowed follow states)
@@ -676 +576 @@
             // for selected states (EvalStates) we introduce state unification (detection of equivalent states)
             if (automaton.IsEvalState(possibleFollowStates[i])) {
-              var hc = Hashcode(automaton);
+              var hc = Hashcode(automaton); // TODO fix unit test for structure enumeration
               if (!state.nodes.TryGetValue(hc, out child)) {
                 child = new Tree() {
@@ -688 +588 @@
               }
               // 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 
@@ -696 +596 @@
                 Debug.Assert(child.level <= tree.level);
                 child = null;
-              }   
+              }
             } else {
               child = new Tree() {
@@ -740 +640 @@
         q = eval(code, nParams);
         // Console.WriteLine("{0:N4}\t{1}", q*q, tree.expr);
-        q = TransformQuality(q);
         success = true;
-        BackpropagateQuality(tree, q, treePolicy, state);        
+        BackpropagateQuality(tree, q, treePolicy, state);
       } else {
         // we got stuck in roll-out (not evaluation necessary!)
@@ -758 +657 @@
 
       return success;
-    }
-
-    private static double InequalityCoefficient(IEnumerable<double> xs) {
-      var arr = xs.ToArray();
-      var sad = 0.0;
-      var sum = 0.0;
-
-      for(int i=0;i<arr.Length;i++) {
-        for(int j=0;j<arr.Length;j++) {
-          sad += Math.Abs(arr[i] - arr[j]);
-          sum += arr[j];
-        }
-      }
-      return 0.5 * sad / sum;      
-    }
-
-    private static double TransformQuality(double q) {
-      // no transformation
-      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;
-      // // return number of 9s in R²
-      // return -Math.Log10(1 - q);
     }
 
@@ -840 +706 @@
       }
 
-      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;
-      }
     }
 
@@ -855 +714 @@
       Tree minChild = children.First();
       for (int i = 1; i < children.Count; i++) {
-        if(children[i].state < minChild.state)
+        if (children[i].state < minChild.state)
           selectedChildIdx = i;
       }
@@ -883 +742 @@
         } else {
           // EXPAND 
-          int[] possibleFollowStates;
+          int[] possibleFollowStates = new int[1000];
           int nFs;
-          automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
+          automaton.FollowStates(automaton.CurrentState, ref possibleFollowStates, out nFs);
           if (nFs == 0) {
             // stuck in a dead end (no final state and no allowed follow states)
@@ -1062 +921 @@
         }
 
-        foreach(var tup in list) {
+        foreach (var tup in list) {
           var ch = tup.Item3;
           var chId = tup.Item2;
-          if(state.children.ContainsKey(ch) && state.children[ch].Count == 1) {
+          if (state.children.ContainsKey(ch) && state.children[ch].Count == 1) {
             var chch = state.children[ch].First();
             nextId++;