Changeset 15734

Timestamp:

02/07/18 17:30:02 (6 years ago)

Author:

gkronber

Message:

#2886 worked on grammar enumeration

Location:

branches/2886_SymRegGrammarEnumeration

Files:

• . (modified) (1 prop)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs (modified) (4 diffs)
• Test/GrammarEnumerationTest.cs (modified) (3 diffs)

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

@@ -158 +158 @@
     public int CalcHashCode(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!");
-
-      Stack<TerminalSymbol> parseStack = new Stack<TerminalSymbol>(sentence.OfType<TerminalSymbol>());
-
-      TerminalSymbol peek = parseStack.Peek();
+      // Debug.Assert(sentence.All(s => s is TerminalSymbol), "Trying to evaluate symbol sequence with nonterminalsymbols!");
+
+      Stack<Symbol> parseStack = new Stack<Symbol>(sentence);
+
+      Symbol peek = parseStack.Peek();
       int[] subtreeHashes = GetSubtreeHashes(parseStack);
       return AggregateHashes(peek, subtreeHashes);
     }
 
-    private int[] GetSubtreeHashes(Stack<TerminalSymbol> parseStack) {
-      TerminalSymbol currentSymbol = parseStack.Pop();
+    private int[] GetSubtreeHashes(Stack<Symbol> parseStack) {
+      Symbol currentSymbol = parseStack.Pop();
 
       // VARIABLE
-      if (Var.VariableTerminalSymbols.Contains(currentSymbol)) {
-        return currentSymbol.StringRepresentation.GetHashCode().ToEnumerable().ToArray();
-      }
+      // if (Var.VariableTerminalSymbols.Contains(currentSymbol)) {
+      //   return currentSymbol.StringRepresentation.GetHashCode().ToEnumerable().ToArray();
+      // }
 
       // MULTIPLICATION
@@ -220 +220 @@
         return result.ToArray();
       }
-      throw new ArgumentException("Trying to hash malformed sentence!");
-    }
-
-    private int AggregateHashes(TerminalSymbol rule, IEnumerable<int> hashes) {
+
+      // var
+      return currentSymbol.StringRepresentation.GetHashCode().ToEnumerable().ToArray();
+
+
+      // throw new ArgumentException("Trying to hash malformed sentence!");
+    }
+
+    private int AggregateHashes(Symbol operatorSym, IEnumerable<int> hashes) {
       // If multiple subtrees are "merged" (e.g. added, multiplied, etc.), consider the executed operation
       var hashesArray = hashes.ToArray();
-      int start = hashesArray.Length > 1 ? rule.StringRepresentation.GetHashCode() : 0;
+      int start = hashesArray.Length > 1 ? operatorSym.StringRepresentation.GetHashCode() : 0;
       return hashesArray.Aggregate(start, (result, ti) => ((result << 5) + result) ^ ti.GetHashCode());
     }

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

@@ -57 +57 @@
     public SymbolString BestTestSentence;
 
-    public List<Tuple<SymbolString, int>> DistinctGenerated;
-    public List<Tuple<SymbolString, int>> AllGenerated;
+    public List<Tuple<SymbolString, int>> distinctSentences;
+    public List<Tuple<SymbolString, int>> sentences;
     #endregion
 
@@ -88 +88 @@
 
     protected override void Run(CancellationToken cancellationToken) {
+      Results.Add(new Result("Best R²", new DoubleValue(0.0)));
+      var rand = new System.Random(1234);
       BestTrainingSentence = null;
       BestTrainingSentence = null;
-      AllGenerated = new List<Tuple<SymbolString, int>>();
-      DistinctGenerated = new List<Tuple<SymbolString, int>>();
-
+      this.sentences = new List<Tuple<SymbolString, int>>();
+      this.distinctSentences = new List<Tuple<SymbolString, int>>();
+      var archivedPhrases = new Dictionary<int, SymbolString>();
+      int expansions = 0;
       Dictionary<int, SymbolString> evaluatedHashes = new Dictionary<int, SymbolString>();
 
       Grammar = new Grammar(Problem.ProblemData.AllowedInputVariables.ToArray());
 
-      Stack<SymbolString> remainingTrees = new Stack<SymbolString>();
-      remainingTrees.Push(new SymbolString(new[] { Grammar.StartSymbol }));
-
-      while (remainingTrees.Any()) {
+      var phrases = new Dictionary<int, SymbolString>();
+      var phrase0 = new SymbolString(new[] { Grammar.StartSymbol });
+      phrases.Add(Grammar.CalcHashCode(phrase0), phrase0);
+
+      while (phrases.Any()) {
         if (cancellationToken.IsCancellationRequested) break;
 
-        SymbolString currSymbolString = remainingTrees.Pop();
-
-        if (currSymbolString.IsSentence()) {
-          AllGenerated.Add(new Tuple<SymbolString, int>(currSymbolString, Grammar.CalcHashCode(currSymbolString)));
-
-          int currSymbolStringHash = Grammar.CalcHashCode(currSymbolString);
-          if (!evaluatedHashes.ContainsKey(currSymbolStringHash)
-              || evaluatedHashes[currSymbolStringHash].Count > currSymbolString.Count) {
-            evaluatedHashes[currSymbolStringHash] = currSymbolString;
-
-            DistinctGenerated.Add(new Tuple<SymbolString, int>(currSymbolString, Grammar.CalcHashCode(currSymbolString)));
-            EvaluateSentence(currSymbolString);
+        // FIFO
+        // SymbolString currSymbolString = phrases.First();
+        // phrases.RemoveAt(0);
+
+        
+        // LIFO
+        // SymbolString currSymbolString = phrases.Last();
+        // phrases.RemoveAt(phrases.Count - 1);
+        
+
+        // RANDOM
+        int idx = rand.Next(phrases.Count);
+        var selectedEntry = phrases.ElementAt(idx);  // TODO: Perf von ElementAt ist schlecht.
+        phrases.Remove(selectedEntry.Key);
+        var currPhrase = selectedEntry.Value;
+
+        archivedPhrases.Add(selectedEntry.Key, selectedEntry.Value);
+
+        if (currPhrase.IsSentence()) {
+          int currSymbolStringHash = Grammar.CalcHashCode(currPhrase);
+          this.sentences.Add(new Tuple<SymbolString, int>(currPhrase, currSymbolStringHash));
+
+          if (!evaluatedHashes.ContainsKey(currSymbolStringHash)) {
+            evaluatedHashes[currSymbolStringHash] = currPhrase;
+
+            this.distinctSentences.Add(new Tuple<SymbolString, int>(currPhrase, currSymbolStringHash));
+            EvaluateSentence(currPhrase);
           }
-          UpdateView(AllGenerated, DistinctGenerated);
+          UpdateView(this.sentences, this.distinctSentences);
 
         } else {
           // expand next nonterminal symbols
-          int nonterminalSymbolIndex = currSymbolString.FindIndex(s => s is NonterminalSymbol);
-          NonterminalSymbol expandedSymbol = currSymbolString[nonterminalSymbolIndex] as NonterminalSymbol;
+          int nonterminalSymbolIndex = currPhrase.FindIndex(s => s is NonterminalSymbol);
+          NonterminalSymbol expandedSymbol = currPhrase[nonterminalSymbolIndex] as NonterminalSymbol;
 
           foreach (Production productionAlternative in expandedSymbol.Alternatives) {
-            SymbolString newSentence = new SymbolString(currSymbolString);
+            SymbolString newSentence = new SymbolString(currPhrase);
             newSentence.RemoveAt(nonterminalSymbolIndex);
             newSentence.InsertRange(nonterminalSymbolIndex, productionAlternative);
 
+            expansions++;
             if (newSentence.Count <= MaxTreeSize) {
-              remainingTrees.Push(newSentence);
+              var phraseHash = Grammar.CalcHashCode(newSentence);
+              if(!phrases.ContainsKey(phraseHash) &&
+                !archivedPhrases.ContainsKey(phraseHash))
+              phrases.Add(phraseHash, newSentence);
             }
           }
@@ -135 +158 @@
       }
 
-      UpdateView(AllGenerated, DistinctGenerated, force: true);
-
-      string[,] sentences = new string[AllGenerated.Count, 3];
-      for (int i = 0; i < AllGenerated.Count; i++) {
-        sentences[i, 0] = AllGenerated[i].Item1.ToString();
-        sentences[i, 1] = Grammar.PostfixToInfixParser(AllGenerated[i].Item1).ToString();
-        sentences[i, 2] = AllGenerated[i].Item2.ToString();
+      UpdateView(this.sentences, this.distinctSentences, force: true);
+
+      string[,] sentences = new string[this.sentences.Count, 3];
+      for (int i = 0; i < this.sentences.Count; i++) {
+        sentences[i, 0] = this.sentences[i].Item1.ToString();
+        sentences[i, 1] = Grammar.PostfixToInfixParser(this.sentences[i].Item1).ToString();
+        sentences[i, 2] = this.sentences[i].Item2.ToString();
       }
       Results.Add(new Result("All generated sentences", new StringMatrix(sentences)));
 
-      string[,] distinctSentences = new string[DistinctGenerated.Count, 3];
-      for (int i = 0; i < DistinctGenerated.Count; i++) {
-        distinctSentences[i, 0] = DistinctGenerated[i].Item1.ToString();
-        distinctSentences[i, 1] = Grammar.PostfixToInfixParser(DistinctGenerated[i].Item1).ToString();
-        distinctSentences[i, 2] = DistinctGenerated[i].Item2.ToString();
+      string[,] distinctSentences = new string[this.distinctSentences.Count, 3];
+      for (int i = 0; i < this.distinctSentences.Count; i++) {
+        distinctSentences[i, 0] = this.distinctSentences[i].Item1.ToString();
+        distinctSentences[i, 1] = Grammar.PostfixToInfixParser(this.distinctSentences[i].Item1).ToString();
+        distinctSentences[i, 2] = this.distinctSentences[i].Item2.ToString();
       }
       Results.Add(new Result("Distinct generated sentences", new StringMatrix(distinctSentences)));
@@ -175 +198 @@
         tree,
         new SymbolicDataAnalysisExpressionTreeLinearInterpreter());
-
-      IRegressionSolution newSolution = model.CreateRegressionSolution(Problem.ProblemData);
-
-      IResult currBestTrainingSolutionResult;
-      IResult currBestTestSolutionResult;
-      if (!Results.TryGetValue(BestTrainingSolution, out currBestTrainingSolutionResult)
-           || !Results.TryGetValue(BestTestSolution, out currBestTestSolutionResult)) {
-
-        BestTrainingSentence = symbolString;
-        Results.Add(new Result(BestTrainingSolution, newSolution));
-        Results.Add(new Result(BestTrainingSolutionQuality, new DoubleValue(newSolution.TrainingRSquared).AsReadOnly()));
-
-        BestTestSentence = symbolString;
-        Results.Add(new Result(BestTestSolution, newSolution));
-        Results.Add(new Result(BestTestSolutionQuality, new DoubleValue(newSolution.TestRSquared).AsReadOnly()));
-
-      } else {
-        IRegressionSolution currBestTrainingSolution = (IRegressionSolution)currBestTrainingSolutionResult.Value;
-        if (currBestTrainingSolution.TrainingRSquared <= newSolution.TrainingRSquared) {
-          BestTrainingSentence = symbolString;
-          currBestTrainingSolutionResult.Value = newSolution;
-          Results.AddOrUpdateResult(BestTrainingSolutionQuality, new DoubleValue(newSolution.TrainingRSquared).AsReadOnly());
-        }
-
-        IRegressionSolution currBestTestSolution = (IRegressionSolution)currBestTestSolutionResult.Value;
-        if (currBestTestSolution.TestRSquared <= newSolution.TestRSquared) {
-          BestTestSentence = symbolString;
-          currBestTestSolutionResult.Value = newSolution;
-          Results.AddOrUpdateResult(BestTestSolutionQuality, new DoubleValue(newSolution.TestRSquared).AsReadOnly());
-        }
-      }
+      var probData = Problem.ProblemData;
+      var target = probData.TargetVariableTrainingValues;
+      var estVals = model.GetEstimatedValues(probData.Dataset, probData.TrainingIndices);
+      OnlineCalculatorError error;
+      var r2 = OnlinePearsonsRSquaredCalculator.Calculate(target, estVals, out error);
+      if (error != OnlineCalculatorError.None) r2 = 0.0;
+
+      var bestR2 = ((DoubleValue)(Results["Best R²"]).Value).Value;
+      ((DoubleValue)(Results["Best R²"].Value)).Value = Math.Max(r2, bestR2);
+
+      // IRegressionSolution newSolution = model.CreateRegressionSolution(Problem.ProblemData);
+      // 
+      // IResult currBestTrainingSolutionResult;
+      // IResult currBestTestSolutionResult;
+      // if (!Results.TryGetValue(BestTrainingSolution, out currBestTrainingSolutionResult)
+      //      || !Results.TryGetValue(BestTestSolution, out currBestTestSolutionResult)) {
+      // 
+      //   BestTrainingSentence = symbolString;
+      //   Results.Add(new Result(BestTrainingSolution, newSolution));
+      //   Results.Add(new Result(BestTrainingSolutionQuality, new DoubleValue(newSolution.TrainingRSquared).AsReadOnly()));
+      // 
+      //   BestTestSentence = symbolString;
+      //   Results.Add(new Result(BestTestSolution, newSolution));
+      //   Results.Add(new Result(BestTestSolutionQuality, new DoubleValue(newSolution.TestRSquared).AsReadOnly()));
+      // 
+      // } else {
+      //   IRegressionSolution currBestTrainingSolution = (IRegressionSolution)currBestTrainingSolutionResult.Value;
+      //   if (currBestTrainingSolution.TrainingRSquared <= newSolution.TrainingRSquared) {
+      //     BestTrainingSentence = symbolString;
+      //     currBestTrainingSolutionResult.Value = newSolution;
+      //     Results.AddOrUpdateResult(BestTrainingSolutionQuality, new DoubleValue(newSolution.TrainingRSquared).AsReadOnly());
+      //   }
+      // 
+      //   IRegressionSolution currBestTestSolution = (IRegressionSolution)currBestTestSolutionResult.Value;
+      //   if (currBestTestSolution.TestRSquared <= newSolution.TestRSquared) {
+      //     BestTestSentence = symbolString;
+      //     currBestTestSolutionResult.Value = newSolution;
+      //     Results.AddOrUpdateResult(BestTestSolutionQuality, new DoubleValue(newSolution.TestRSquared).AsReadOnly());
+      //   }
+      // }
     }
   }

branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs

@@ -68 +68 @@
     public void MctsSymbReg_NoConstants_Nguyen1() {
       // x³ + x² + x
-      alg.MaxTreeSize = 30;
+      alg.MaxTreeSize = 3;
       Console.WriteLine(alg.MaxTreeSize);
       var provider = new HeuristicLab.Problems.Instances.DataAnalysis.NguyenInstanceProvider(Seed);
@@ -92 +92 @@
       int actualSolutionHash = alg.Grammar.CalcHashCode(alg.BestTestSentence);
 
-      Assert.IsTrue(alg.DistinctGenerated.Select(tuple => tuple.Item2).Contains(actualSolutionHash));
+      Assert.IsTrue(alg.distinctSentences.Select(tuple => tuple.Item2).Contains(actualSolutionHash));
 
       // last because long sentences are overwritten by short ones.
-      Console.WriteLine(alg.Grammar.PostfixToInfixParser(alg.DistinctGenerated.Last(tuple => tuple.Item2 == targetSolutionHash).Item1));
+      Console.WriteLine(alg.Grammar.PostfixToInfixParser(alg.distinctSentences.Last(tuple => tuple.Item2 == targetSolutionHash).Item1));
 
 
@@ -114 +114 @@
       // Evaluate
       EvaluateGrammarEnumeration();
+    }
+
+    [TestMethod]
+    [TestProperty("Goal", "structure search")]
+    public void MctsSymbReg_NoConstants_Poly10() {
+      alg.MaxTreeSize = 10;
+      var provider = new HeuristicLab.Problems.Instances.DataAnalysis.VariousInstanceProvider(Seed);
+      var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("Poly")));
+      alg.Problem.ProblemData = regProblem;
+
+      alg.Start();
+
+      Assert.AreEqual(alg.distinctSentences.Count(), 110);
+
+      // Evaluate
+      // EvaluateGrammarEnumeration();
+    }
+
+    [TestMethod]
+    [TestProperty("Goal", "structure search")]
+    public void MctsSymbReg_NoConstants_15() {
+      alg.MaxTreeSize = 5;
+      var provider = new HeuristicLab.Problems.Instances.DataAnalysis.KeijzerInstanceProvider(Seed);
+      var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("15")));
+      alg.Problem.ProblemData = regProblem;
+
+      alg.Start();
+
+      Assert.AreEqual(alg.distinctSentences.Count(), 16);
+
+      // Evaluate
+      // EvaluateGrammarEnumeration();
     }