Changeset 15907 for branches/2886_SymRegGrammarEnumeration

Timestamp:

04/16/18 15:19:58 (7 years ago)

Author:

lkammere

Message:

#2886: Changes in search heuristic for solving Poly-10 problem. Adapt tree evaluation to cover non-terminal symbols.

Location:

branches/2886_SymRegGrammarEnumeration

Files:

• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs (modified) (5 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/SearchDataStructure.cs (modified) (1 diff)
• Test/GrammarEnumerationTest.cs (modified) (6 diffs)

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs

@@ -176 +176 @@
 
     public double EvaluatePhrase(SymbolString s, IRegressionProblemData problemData, bool optimizeConstants) {
-      // Create sentences without Expression symbols.
-      Symbol[] sEval = new Symbol[s.Count()];
-
-      for (int i = 0; i < sEval.Length; i++) {
-        Symbol currSym = s[i];
-        if (currSym is NonterminalSymbol && currSym != Expr)
-          return 0.0;
-
-        if (currSym == Expr) {
-          sEval[i] = Const;
-        } else {
-          sEval[i] = currSym;
-        }
-      }
-
-      SymbolicExpressionTree tree = ParseSymbolicExpressionTree(new SymbolString(sEval));
+      SymbolicExpressionTree tree = ParseSymbolicExpressionTree(s);
+
       double r2 = RSquaredEvaluator.Evaluate(problemData, tree, optimizeConstants);
 
@@ -208 +194 @@
     public SymbolicExpressionTree ParseSymbolicExpressionTree(SymbolString sentence) {
       Debug.Assert(sentence.Any(), "Trying to evaluate empty sentence!");
-      Debug.Assert(sentence.All(s => s is TerminalSymbol), "Trying to evaluate symbol sequence with nonterminalsymbols!");
 
       var rootNode = rootSy.CreateTreeNode();
@@ -214 +199 @@
       rootNode.AddSubtree(startNode);
 
-      Stack<TerminalSymbol> parseStack = new Stack<TerminalSymbol>(sentence.OfType<TerminalSymbol>());
+      Stack<Symbol> parseStack = new Stack<Symbol>(sentence);
       startNode.AddSubtree(ParseSymbolicExpressionTree(parseStack));
 
@@ -220 +205 @@
     }
 
-    public ISymbolicExpressionTreeNode ParseSymbolicExpressionTree(Stack<TerminalSymbol> parseStack) {
-      TerminalSymbol currentSymbol = parseStack.Pop();
+    public ISymbolicExpressionTreeNode ParseSymbolicExpressionTree(Stack<Symbol> parseStack) {
+      Symbol currentSymbol = parseStack.Pop();
 
       ISymbolicExpressionTreeNode parsedSubTree = null;
@@ -273 +258 @@
         varNode.VariableName = currentSymbol.StringRepresentation;
         parsedSubTree = varNode;
+
+      } else if (currentSymbol is NonterminalSymbol) {
+        ConstantTreeNode constNode = (ConstantTreeNode)constSy.CreateTreeNode();
+        constNode.Value = 0.0;
+        parsedSubTree = constNode;
       }
 

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs

@@ -186 +186 @@
 
               // Is the best solution found? (only if RSquaredEvaluator is activated)
-              if (Results.ContainsKey(RSquaredEvaluator.BestTrainingQualityResultName) && ((DoubleValue)Results[RSquaredEvaluator.BestTrainingQualityResultName].Value).Value == 1.0) {
-                UpdateView(force: true);
-                return;
+              if (Results.ContainsKey(RSquaredEvaluator.BestTrainingQualityResultName)) {
+                double r2 = ((DoubleValue)Results[RSquaredEvaluator.BestTrainingQualityResultName].Value).Value;
+                if (r2.IsAlmost(1.0)) {
+                  UpdateView(force: true);
+                  return;
+                }
               }
 
@@ -210 +213 @@
 
     protected double GetPriority(SymbolString phrase) {
-      return 1.0 - Grammar.EvaluatePhrase(phrase, Problem.ProblemData, OptimizeConstants);
+      double complexity = (double)Grammar.GetComplexity(phrase);
+
+      double length = phrase.Count();
+      double relLength = (length - 2) / (MaxComplexity * 7);
+      double r2 = Grammar.EvaluatePhrase(phrase, Problem.ProblemData, OptimizeConstants);
+      double error = 1.0 - r2;
+
+      double variables = 0;
+      for (int i = 0; i < phrase.Count(); i++) {
+        if (phrase[i] is VariableTerminalSymbol) variables++;
+      }
+
+      double variableRatio = 1.0 - variables / complexity;
+
+      return 1.5*relLength + error;
     }
 

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/SearchDataStructure.cs

@@ -48 +48 @@
 
     private void InitPriorityQueue() {
-      PriorityQueue<double, int> queue = new PriorityQueue<double, int>(double.MaxValue, double.MinValue, (int)Math.Pow(2.0, 20.0) / 4);
+      int capacity = 10000000;
+      PriorityQueue<double, int> queue = new PriorityQueue<double, int>(double.MaxValue, double.MinValue, capacity);
       storeInternal = (hash, prio) => queue.Insert(prio, hash);
       fetchInternal = () => {

branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs

@@ -304 +304 @@
         xSymbol, ySymbol, mulSymbol, ySymbol, mulSymbol, constSymbol, mulSymbol,
         ySymbol, ySymbol, mulSymbol, constSymbol, mulSymbol, addSymbol, constSymbol, addSymbol, invSymbol,
-        constSymbol, addSymbol 
+        constSymbol, addSymbol
       });
 
@@ -339 +339 @@
         ySymbol, ySymbol, mulSymbol, constSymbol, mulSymbol, addSymbol,
         ySymbol, constSymbol, mulSymbol, addSymbol,
-        constSymbol, addSymbol 
+        constSymbol, addSymbol
       });
 
@@ -362 +362 @@
 
       alg.Start();
-      
+
       TerminalSymbol constSymbol = alg.Grammar.Const;
       TerminalSymbol xSymbol = alg.Grammar.VarTerminals.First();
@@ -370 +370 @@
       TerminalSymbol divSymbol = alg.Grammar.Inv;
 
-      
+
       // x x mul c mul y y mul c mul add const add inv const mul const add
       SymbolString targetSolution = new SymbolString(new[] {
-        xSymbol, xSymbol, mulSymbol, constSymbol, mulSymbol,  
+        xSymbol, xSymbol, mulSymbol, constSymbol, mulSymbol,
         ySymbol, ySymbol, mulSymbol, constSymbol, mulSymbol, addSymbol,
         constSymbol, addSymbol, divSymbol,
@@ -410 +410 @@
         xSymbol, xSymbol, mulSymbol, xSymbol, mulSymbol, constSymbol, mulSymbol,
         ySymbol, ySymbol, mulSymbol, ySymbol, mulSymbol, constSymbol, mulSymbol, addSymbol,
-        ySymbol, constSymbol, mulSymbol, addSymbol, 
+        ySymbol, constSymbol, mulSymbol, addSymbol,
         xSymbol, constSymbol, mulSymbol, addSymbol,
         constSymbol, addSymbol
@@ -422 +422 @@
 
       // Evaluate
+      EvaluateGrammarEnumeration();
+    }
+
+    [TestMethod]
+    [TestProperty("Goal", "Poly-10 derivatives")]
+    public void MctsSymbReg_NoConstants_Poly10_Part1() {
+      alg.MaxComplexity = 12; 
+      alg.OptimizeConstants = false;
+      var regProblem = new PolyTen(123).GenerateRegressionData();
+
+      //  Y = X1*X2 + X3*X4 + X5*X6 + X1*X7*X9 + X3*X6*X10
+      //  Y' = X1*X2 + X3*X4 + X5*X6
+      // simplify problem by changing target
+      var ds = ((Dataset)regProblem.Dataset).ToModifiable();
+      var ys = ds.GetDoubleValues("Y").ToArray();
+      var x1 = ds.GetDoubleValues("X1").ToArray();
+      var x2 = ds.GetDoubleValues("X2").ToArray();
+      var x3 = ds.GetDoubleValues("X3").ToArray();
+      var x4 = ds.GetDoubleValues("X4").ToArray();
+      var x5 = ds.GetDoubleValues("X5").ToArray();
+      var x6 = ds.GetDoubleValues("X6").ToArray();
+      var x7 = ds.GetDoubleValues("X7").ToArray();
+      var x8 = ds.GetDoubleValues("X8").ToArray();
+      var x9 = ds.GetDoubleValues("X9").ToArray();
+      var x10 = ds.GetDoubleValues("X10").ToArray();
+      for (int i = 0; i < ys.Length; i++) {
+        //ys[i] -= x1[i] * x7[i] * x9[i];
+        //ys[i] -= x3[i] * x6[i] * x10[i];
+      }
+      ds.ReplaceVariable("Y", ys.ToList());
+
+      alg.Problem.ProblemData = new RegressionProblemData(ds, regProblem.AllowedInputVariables, regProblem.TargetVariable);
+
+      alg.Start();
+
       EvaluateGrammarEnumeration();
     }