Changeset 13651 for trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/MctsSymbolicRegressionStatic.cs

Timestamp:

03/05/16 08:25:08 (8 years ago)

Author:

gkronber

Message:

#2581:

• added unit tests for the number of different expressions
• fixed problems in Automaton and constraintHandler that lead to duplicate expressions
• added possibility for MCTS to handle dead-ends in the search tree (when it is not possible to construct a valid new expression)
• added statistics on function and gradient evaluations

File:

• trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/MctsSymbolicRegressionStatic.cs (modified) (12 diffs)

trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/MctsSymbolicRegressionStatic.cs

@@ -44 +44 @@
       double BestSolutionTrainingQuality { get; }
       double BestSolutionTestQuality { get; }
+      int TotalRollouts { get; }
+      int EffectiveRollouts { get; }
+      int FuncEvaluations { get; }
+      int GradEvaluations { get; } // number of gradient evaluations (* num parameters) to get a value representative of the effort comparable to the number of function evaluations
+      // TODO other stats on LM optimizer might be interesting here
     }
 
@@ -57 +62 @@
       internal readonly List<Tree> bestChildrenBuf;
       internal readonly Func<byte[], int, double> evalFun;
+      // MCTS might get stuck. Track statistics on the number of effective rollouts
+      internal int totalRollouts;
+      internal int effectiveRollouts;
 
 
@@ -77 +85 @@
       private int bestNParams;
       private double[] bestConsts;
+
+      // stats
+      private int funcEvaluations;
+      private int gradEvaluations;
 
       // buffers
@@ -173 +185 @@
         }
       }
+
+      public int TotalRollouts { get { return totalRollouts; } }
+      public int EffectiveRollouts { get { return effectiveRollouts; } }
+      public int FuncEvaluations { get { return funcEvaluations; } }
+      public int GradEvaluations { get { return gradEvaluations; } } // number of gradient evaluations (* num parameters) to get a value representative of the effort comparable to the number of function evaluations
+
       #endregion
 
@@ -204 +222 @@
         Array.Copy(ones, constsBuf, nParams);
         evaluator.Exec(code, x, constsBuf, predBuf, adjustOffsetForLogAndExp: true);
+        funcEvaluations++;
 
         // calc opt scaling (alpha*f(x) + beta)
@@ -220 +239 @@
           // optimize constants using the starting point calculated above
           OptimizeConstsLm(code, constsBuf, nParams, 0.0, nIters: constOptIterations);
+
           evaluator.Exec(code, x, constsBuf, predBuf);
+          funcEvaluations++;
+
           rsq = RSq(y, predBuf);
           optConsts = constsBuf;
@@ -237 +259 @@
 
       private void OptimizeConstsLm(byte[] code, double[] consts, int nParams, double epsF = 0.0, int nIters = 100) {
-        double[] optConsts = new double[nParams]; // allocate a smaller buffer for constants opt
+        double[] optConsts = new double[nParams]; // allocate a smaller buffer for constants opt (TODO perf?)
         Array.Copy(consts, optConsts, nParams);
 
@@ -247 +269 @@
         alglib.minlmoptimize(state, Func, FuncAndJacobian, null, code);
         alglib.minlmresults(state, out optConsts, out rep);
+        funcEvaluations += rep.nfunc;
+        gradEvaluations += rep.njac * nParams;
 
         if (rep.terminationtype < 0) throw new ArgumentException("lm failed: termination type = " + rep.terminationtype);
@@ -311 +335 @@
       var rand = mctsState.random;
       double c = mctsState.c;
-
-      automaton.Reset();
-      return TreeSearchRec(rand, tree, c, automaton, eval, bestChildrenBuf);
-    }
-
-    private static double TreeSearchRec(IRandom rand, Tree tree, double c, Automaton automaton, Func<byte[], int, double> eval, List<Tree> bestChildrenBuf) {
+      double q = 0;
+      bool success = false;
+      do {
+        automaton.Reset();
+        success = TryTreeSearchRec(rand, tree, c, automaton, eval, bestChildrenBuf, out q);
+        mctsState.totalRollouts++;
+      } while (!success && !tree.done);
+      mctsState.effectiveRollouts++;
+      return q;
+    }
+
+    // tree search might fail because of constraints for expressions
+    // in this case we get stuck we just restart
+    // see ConstraintHandler.cs for more info
+    private static bool TryTreeSearchRec(IRandom rand, Tree tree, double c, Automaton automaton, Func<byte[], int, double> eval, List<Tree> bestChildrenBuf,
+      out double q) {
       Tree selectedChild = null;
-      double q;
       Contract.Assert(tree.state == automaton.CurrentState);
       Contract.Assert(!tree.done);
@@ -332 +365 @@
           tree.visits++;
           tree.sumQuality += q;
-          return q;
+          return true; // we reached a final state
         } else {
           // EXPAND 
@@ -338 +371 @@
           int nFs;
           automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
-
+          if (nFs == 0) {
+            // stuck in a dead end (no final state and no allowed follow states)
+            q = 0;
+            tree.done = true;
+            tree.children = null;
+            return false;
+          }
           tree.children = new Tree[nFs];
-          for (int i = 0; i < tree.children.Length; i++) tree.children[i] = new Tree() { children = null, done = false, state = possibleFollowStates[i], visits = 0 };
+          for (int i = 0; i < tree.children.Length; i++)
+            tree.children[i] = new Tree() { children = null, done = false, state = possibleFollowStates[i], visits = 0 };
 
           selectedChild = SelectFinalOrRandom(automaton, tree, rand);
@@ -351 +391 @@
       // make selected step and recurse
       automaton.Goto(selectedChild.state);
-      q = TreeSearchRec(rand, selectedChild, c, automaton, eval, bestChildrenBuf);
-
-      tree.sumQuality += q;
-      tree.visits++;
+      var success = TryTreeSearchRec(rand, selectedChild, c, automaton, eval, bestChildrenBuf, out q);
+      if (success) {
+        // only update if successful
+        tree.sumQuality += q;
+        tree.visits++;
+      }
 
       // tree.done = tree.children.All(ch => ch.done);
       tree.done = true; for (int i = 0; i < tree.children.Length && tree.done; i++) tree.done = tree.children[i].done;
       if (tree.done) {
-        tree.children = null; // cut of the sub-branch if it has been fully explored
+        tree.children = null; // cut off the sub-branch if it has been fully explored
         // TODO: update all qualities and visits to remove the information gained from this whole branch
       }
-      return q;
+      return success;
     }