Changeset 15883

Timestamp:

04/04/18 16:23:55 (6 years ago)

Author:

lkammere

Message:

#2886: Priorize phrases whose (fully expanded) terms result in high R².

Location:

branches/2886_SymRegGrammarEnumeration

Files:

• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/RSquaredEvaluator.cs (modified) (4 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs (modified) (4 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/SearchDataStructure.cs (modified) (7 diffs)
• Test/GrammarEnumerationTest.cs (modified) (2 diffs)

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/RSquaredEvaluator.cs

@@ -13 +13 @@
 namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
   public class RSquaredEvaluator : Item, IGrammarEnumerationAnalyzer {
-    private readonly string BestTrainingQualityResultName = "Best R² (Training)";
-    private readonly string BestTrainingModelResultName = "Best model (Training)";
-    private readonly string BestTrainingSolutionResultName = "Best solution (Training)";
+    public static readonly string BestTrainingQualityResultName = "Best R² (Training)";
+    public static readonly string BestTrainingModelResultName = "Best model (Training)";
+    public static readonly string BestTrainingSolutionResultName = "Best solution (Training)";
 
-    private readonly ISymbolicDataAnalysisExpressionTreeInterpreter expressionTreeLinearInterpreter = new SymbolicDataAnalysisExpressionTreeLinearInterpreter();
+    private static readonly ISymbolicDataAnalysisExpressionTreeInterpreter expressionTreeLinearInterpreter = new SymbolicDataAnalysisExpressionTreeLinearInterpreter();
 
     public bool OptimizeConstants { get; set; }
@@ -73 +73 @@
       Debug.Assert(SymbolicRegressionConstantOptimizationEvaluator.CanOptimizeConstants(tree));
 
-      // TODO: Initialize constant values randomly
-      // TODO: Restarts
+      double r2 = Evaluate(problemData, tree, OptimizeConstants);
 
-      double r2;
+      var bestR2Result = (DoubleValue)algorithm.Results[BestTrainingQualityResultName].Value;
+      bool better = r2 > bestR2Result.Value;
+      bool equallyGood = r2.IsAlmost(bestR2Result.Value);
+      bool shorter = false;
 
-      SymbolicRegressionModel model = new SymbolicRegressionModel(
+      if (!better && equallyGood) {
+        shorter = algorithm.BestTrainingSentence != null &&
+          algorithm.Grammar.GetComplexity(algorithm.BestTrainingSentence) > algorithm.Grammar.GetComplexity(symbolString);
+      }
+      if (better || (equallyGood && shorter)) {
+        bestR2Result.Value = r2;
+
+        SymbolicRegressionModel model = new SymbolicRegressionModel(
           problemData.TargetVariable,
           tree,
           expressionTreeLinearInterpreter);
 
-      if (OptimizeConstants) {
+        algorithm.Results.AddOrUpdateResult(BestTrainingModelResultName, model);
+
+        algorithm.BestTrainingSentence = symbolString;
+      }
+    }
+
+    public static double Evaluate(IRegressionProblemData problemData, SymbolicExpressionTree tree, bool optimizeConstants = true) {
+      double r2;
+
+      // TODO: Initialize constant values randomly
+      // TODO: Restarts
+      if (optimizeConstants) {
         r2 = SymbolicRegressionConstantOptimizationEvaluator.OptimizeConstants(expressionTreeLinearInterpreter,
           tree,
@@ -100 +120 @@
         }
 
-
       } else {
         var target = problemData.TargetVariableTrainingValues;
+
+        SymbolicRegressionModel model = new SymbolicRegressionModel(
+          problemData.TargetVariable,
+          tree,
+          expressionTreeLinearInterpreter);
+
         var estVals = model.GetEstimatedValues(problemData.Dataset, problemData.TrainingIndices);
         OnlineCalculatorError error;
@@ -109 +134 @@
       }
 
-      var bestR2Result = (DoubleValue)algorithm.Results[BestTrainingQualityResultName].Value;
-      bool better = r2 > bestR2Result.Value;
-      bool equallyGood = r2.IsAlmost(bestR2Result.Value);
-      bool shorter = false;
-
-      if (!better && equallyGood) {
-        shorter = algorithm.BestTrainingSentence != null &&
-          algorithm.Grammar.GetComplexity(algorithm.BestTrainingSentence) > algorithm.Grammar.GetComplexity(symbolString);
-      }
-      if (better || (equallyGood && shorter)) {
-        bestR2Result.Value = r2;
-        algorithm.Results.AddOrUpdateResult(BestTrainingModelResultName, model);
-
-        algorithm.BestTrainingSentence = symbolString;
-      }
+      return r2;
     }
   }

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

@@ -4 +4 @@
 using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Problems.DataAnalysis;
 using HeuristicLab.Problems.DataAnalysis.Symbolic;
 
@@ -174 +175 @@
     }
 
+    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));
+      double r2 = RSquaredEvaluator.Evaluate(problemData, tree, optimizeConstants);
+
+      return r2;
+    }
+
     #region Parse to SymbolicExpressionTree
 

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

@@ -153 +153 @@
       #endregion
 
-      OpenPhrases.Store(phrase0Hash, phrase0);
+      OpenPhrases.Store(phrase0Hash, 0.0, phrase0);
       while (OpenPhrases.Count > 0) {
         if (cancellationToken.IsCancellationRequested) break;
@@ -185 +185 @@
               OnSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
 
+              // 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 (!DistinctSentencesComplexity.ContainsKey(phraseHash) || DistinctSentencesComplexity[phraseHash] > newPhraseComplexity) {
                 if (DistinctSentencesComplexity.ContainsKey(phraseHash)) OverwrittenSentencesCount++; // for analysis only
@@ -194 +200 @@
 
             } else if (!OpenPhrases.Contains(phraseHash) && !ArchivedPhrases.Contains(phraseHash)) {
-              OpenPhrases.Store(phraseHash, newPhrase);
+              double phrasePriority = GetPriority(newPhrase);
+              OpenPhrases.Store(phraseHash, phrasePriority, newPhrase);
             }
           }
@@ -200 +207 @@
       }
       UpdateView(force: true);
+    }
+
+    protected double GetPriority(SymbolString phrase) {
+      return 1.0 - Grammar.EvaluatePhrase(phrase, Problem.ProblemData, OptimizeConstants);
     }
 

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

@@ -16 +16 @@
 
   public enum StorageType {
-    Stack, Queue, RandomList
+    PriorityQueue, Stack, Queue, RandomList
   }
 
@@ -22 +22 @@
 
     private Dictionary<int, SymbolString> storedValues; // Store hash-references and associated, actual values 
-    private Action<int> storeInternal; // Store hash-references 
+    private Action<int, double> storeInternal; // Store hash-references 
     private Func<int> fetchInternal; // Fetch hash-reference
 
@@ -29 +29 @@
 
       switch (storageType) {
+        case StorageType.PriorityQueue:
+          InitPriorityQueue();
+          break;
         case StorageType.Stack:
           InitStack();
@@ -44 +47 @@
     #region SearchStrategies
 
+    private void InitPriorityQueue() {
+      PriorityQueue<double, int> queue = new PriorityQueue<double, int>(double.MaxValue, double.MinValue, (int)Math.Pow(2.0, 20.0) / 4);
+      storeInternal = (hash, prio) => queue.Insert(prio, hash);
+      fetchInternal = () => {
+        int ret = queue.PeekMinValue();
+        queue.RemoveMin();
+        return ret;
+      };
+    }
+
     private void InitStack() {
       Stack<int> stack = new Stack<int>();
 
-      storeInternal = hash => stack.Push(hash);
+      storeInternal = (hash, prio) => stack.Push(hash);
       fetchInternal = () => stack.Pop();
     }
@@ -54 +67 @@
       Queue<int> queue = new Queue<int>();
 
-      storeInternal = hash => queue.Enqueue(hash);
+      storeInternal = (hash, prio) => queue.Enqueue(hash);
       fetchInternal = () => queue.Dequeue();
     }
@@ -62 +75 @@
       System.Random rand = new System.Random(999);
 
-      storeInternal = hash => list.Add(hash);
+      storeInternal = (hash, prio) => list.Add(hash);
       fetchInternal = () => {
         int indexOfHash = rand.Next(list.Count);
         int result = list[indexOfHash];
-        list.RemoveAt(indexOfHash);  // TODO: beware this is O(n), at some point in time we should fix this
+        list.RemoveAt(indexOfHash);  // TODO: beware this is O(n), at some point in time we should fix this. Maybe change to priority queue with random key.
         return result;
       };
@@ -82 +95 @@
     }
 
-    public void Store(int hash, SymbolString s) {
-      storeInternal(hash);
+    public void Store(int hash, double priority, SymbolString s) {
+      storeInternal(hash, priority);
       storedValues[hash] = s;
     }

branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs

@@ -34 +34 @@
         alg.Analyzers.SetItemCheckedState(grammarEnumerationAnalyzer, grammarEnumerationAnalyzer is RSquaredEvaluator);
       }
+      alg.SearchDataStructure = StorageType.PriorityQueue;
     }
 
@@ -250 +251 @@
 
     [TestMethod]
-    [TestProperty("Goal", "structure search + const op")]
+    [TestProperty("Goal", "sinnus const op")]
     public void Constants_Keijzer3() {
       // 0.3*x*sin(2*pi*x)