Changeset 15723 for branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration

Timestamp:

02/06/18 13:18:31 (7 years ago)

Author:

lkammere

Message:

#2886: Add simple data analysis tests and further informations about algorithm run.

Location:

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

Files:

• Grammar.cs (modified) (4 diffs)
• GrammarEnumerationAlgorithm.cs (modified) (10 diffs)
• Sentence.cs (modified) (2 diffs)
• Symbol.cs (modified) (1 diff)

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

@@ -59 +59 @@
 
 
-      #region Production ruless
+      #region Production rules
+      // order of production is important, since they are accessed via index
+      // in memoization.
       StartSymbol = Expr;
 
@@ -89 +91 @@
     }
 
+    /*
+    #region Memoize subtrees
+
+    public void MemoizeSubtrees(SymbolString sentence) {
+      Stack<TerminalSymbol> parseStack = new Stack<TerminalSymbol>(sentence.OfType<TerminalSymbol>());
+
+      // Parse root symbol "+"
+      MemoizeSubtreeExpression(parseStack);
+    }
+
+    private SymbolString MemoizeSubtreeExpression(Stack<TerminalSymbol> parseStack) {
+      SymbolString subtree = new SymbolString();
+
+      if (ReferenceEquals(parseStack.Peek(), Addition)) {
+        subtree.Add(parseStack.Pop());
+        subtree.InsertRange(0, MemoizeSubtreeExpression(parseStack));
+        subtree.InsertRange(0, MemoizeSubtreeTerm(parseStack));
+
+        Expr.Alternatives[0].GeneratedSentences.Add(subtree);
+      } else {
+        subtree.InsertRange(0, MemoizeSubtreeTerm(parseStack));
+
+        Expr.Alternatives[1].GeneratedSentences.Add(subtree);
+      }
+
+      return subtree;
+    }
+
+    private SymbolString MemoizeSubtreeTerm(Stack<TerminalSymbol> parseStack) {
+      SymbolString subtree = new SymbolString();
+
+      if (ReferenceEquals(parseStack.Peek(), Multiplication)) {
+        subtree.Add(parseStack.Pop());
+        subtree.InsertRange(0, MemoizeSubtreeTerm(parseStack));
+        subtree.InsertRange(0, MemoizeSubtreeFactor(parseStack));
+
+        Term.Alternatives[0].GeneratedSentences.Add(subtree);
+      } else {
+        subtree.InsertRange(0, MemoizeSubtreeFactor(parseStack));
+
+        Term.Alternatives[1].GeneratedSentences.Add(subtree);
+      }
+
+      return subtree;
+    }
+
+    private SymbolString MemoizeSubtreeFactor(Stack<TerminalSymbol> parseStack) {
+      SymbolString subtree = new SymbolString(MemoizeSubtreeVar(parseStack));
+
+      Factor.Alternatives[0].GeneratedSentences.Add(subtree);
+      return subtree;
+    }
+
+    private SymbolString MemoizeSubtreeVar(Stack<TerminalSymbol> parseStack) {
+      SymbolString subtree = new SymbolString(parseStack.Pop().ToEnumerable());
+
+      // ... not really
+      //Var.Alternatives[0].GeneratedSentences.Add(subtree);
+      return subtree;
+    }
+
+
+    #endregion
+    */
+    
+    #region Hashing
     public int CalcHashCode(SymbolString sentence) {
       Debug.Assert(sentence.Any(), "Trying to evaluate empty sentence!");
@@ -99 +167 @@
     }
 
-    #region Hashing
     private int[] GetSubtreeHashes(TerminalSymbol currentSymbol, Stack<TerminalSymbol> parseStack) {
       List<int> childHashes = null;
@@ -166 +233 @@
       return childHashes.ToArray();
     }
-
 
     private int AggregateHashes(IEnumerable<int> hashes) {

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

@@ -1 @@
-using System;
-using System.Collections.Generic;
-using System.Collections.ObjectModel;
-using System.Diagnostics;
+using System.Collections.Generic;
 using System.Linq;
 using System.Threading;
@@ -23 +20 @@
   public class GrammarEnumerationAlgorithm : FixedDataAnalysisAlgorithm<IRegressionProblem> {
     private readonly string BestTrainingSolution = "Best solution (training)";
+    private readonly string BestTrainingSolutionString = "Best solution string (training)";
     private readonly string BestTrainingSolutionQuality = "Best solution quality (training)";
     private readonly string BestTestSolution = "Best solution (test)";
+    private readonly string BestTestSolutionString = "Best solution string (test)";
     private readonly string BestTestSolutionQuality = "Best solution quality (test)";
 
     private readonly string MaxTreeSizeParameterName = "Max. Tree Nodes";
     private readonly string GuiUpdateIntervalParameterName = "GUI Update Interval";
+    private readonly string UseMemoizationParameterName = "Use Memoization?";
 
 
     #region properties
-    public IValueParameter<IntValue> MaxTreeSizeParameter {
+    protected IValueParameter<IntValue> MaxTreeSizeParameter {
       get { return (IValueParameter<IntValue>)Parameters[MaxTreeSizeParameterName]; }
     }
-
     public int MaxTreeSize {
       get { return MaxTreeSizeParameter.Value.Value; }
+      set { MaxTreeSizeParameter.Value.Value = value; }
     }
 
-    public IValueParameter<IntValue> GuiUpdateIntervalParameter {
-      get { return (IValueParameter<IntValue>)Parameters[MaxTreeSizeParameterName]; }
+    protected IValueParameter<IntValue> GuiUpdateIntervalParameter {
+      get { return (IValueParameter<IntValue>)Parameters[GuiUpdateIntervalParameterName]; }
+    }
+    public int GuiUpdateInterval {
+      get { return GuiUpdateIntervalParameter.Value.Value; }
+      set { GuiUpdateIntervalParameter.Value.Value = value; }
     }
 
-    public int GuiUpdateInterval {
-      get { return GuiUpdateIntervalParameter.Value.Value; }
+    protected IValueParameter<BoolValue> UseMemoizationParameter {
+      get { return (IValueParameter<BoolValue>)Parameters[UseMemoizationParameterName]; }
+    }
+    public bool UseMemoization {
+      get { return UseMemoizationParameter.Value.Value; }
+      set { UseMemoizationParameter.Value.Value = value; }
     }
 
@@ -59 +67 @@
 
     public GrammarEnumerationAlgorithm() {
-      Problem = new RegressionProblem();
 
-      Parameters.Add(new ValueParameter<IntValue>(MaxTreeSizeParameterName, "The number of clusters.", new IntValue(4)));
+      var provider = new HeuristicLab.Problems.Instances.DataAnalysis.VariousInstanceProvider(seed: 1234);
+      var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("Poly-10")));
+
+      Problem = new RegressionProblem() {
+        ProblemData = regProblem
+      };
+
+      Parameters.Add(new ValueParameter<IntValue>(MaxTreeSizeParameterName, "The number of clusters.", new IntValue(6)));
       Parameters.Add(new ValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(4000)));
+      Parameters.Add(new ValueParameter<BoolValue>(UseMemoizationParameterName, "Should already subtrees be reused within a run.", new BoolValue(true)));
     }
 
@@ -72 +87 @@
       List<SymbolString> allGenerated = new List<SymbolString>();
       List<SymbolString> distinctGenerated = new List<SymbolString>();
+
+      int expansions = 0;
+
       HashSet<int> evaluatedHashes = new HashSet<int>();
 
@@ -87 +105 @@
           allGenerated.Add(currSymbolString);
 
-          if (evaluatedHashes.Add(grammar.CalcHashCode(currSymbolString))) {
-            EvaluateSentence(currSymbolString);
-            distinctGenerated.Add(currSymbolString);
-          }
+          //if (evaluatedHashes.Add(grammar.CalcHashCode(currSymbolString))) {
+          EvaluateSentence(currSymbolString);
+          //distinctGenerated.Add(currSymbolString);
+          //}
 
-          UpdateView(allGenerated, distinctGenerated);
+          UpdateView(allGenerated, distinctGenerated, expansions);
 
         } else {
@@ -111 +129 @@
       }
 
+      UpdateView(allGenerated, distinctGenerated, expansions, force: true);
+
       StringArray sentences = new StringArray(allGenerated.Select(r => r.ToString()).ToArray());
       Results.Add(new Result("All generated sentences", sentences));
@@ -118 +138 @@
 
 
-    private void UpdateView(List<SymbolString> allGenerated, List<SymbolString> distinctGenerated) {
+    private void UpdateView(List<SymbolString> allGenerated, List<SymbolString> distinctGenerated, int expansions, bool force = false) {
       int generatedSolutions = allGenerated.Count;
       int distinctSolutions = distinctGenerated.Count;
 
-      if (generatedSolutions % GuiUpdateInterval == 0) {
+      if (force || generatedSolutions % GuiUpdateInterval == 0) {
         Results.AddOrUpdateResult("Generated Solutions", new IntValue(generatedSolutions));
-        Results.Add(new Result("Distinct Solutions", new IntValue(distinctSolutions)));
+        Results.AddOrUpdateResult("Distinct Solutions", new IntValue(distinctSolutions));
 
         DoubleValue averageTreeLength = new DoubleValue(allGenerated.Select(r => r.Count).Average());
-        Results.Add(new Result("Average Tree Length of Solutions", averageTreeLength));
+        Results.AddOrUpdateResult("Average Tree Length of Solutions", averageTreeLength);
+
+        IntValue expansionsValue = new IntValue(expansions);
+        Results.AddOrUpdateResult("Expansions", expansionsValue);
       }
     }
@@ -146 +169 @@
 
         Results.Add(new Result(BestTrainingSolution, newSolution));
+        Results.Add(new Result(BestTrainingSolutionString, new StringValue(symbolString.ToString()).AsReadOnly()));
         Results.Add(new Result(BestTrainingSolutionQuality, new DoubleValue(newSolution.TrainingRSquared).AsReadOnly()));
         Results.Add(new Result(BestTestSolution, newSolution));
+        Results.Add(new Result(BestTestSolutionString, new StringValue(symbolString.ToString()).AsReadOnly()));
         Results.Add(new Result(BestTestSolutionQuality, new DoubleValue(newSolution.TestRSquared).AsReadOnly()));
 
@@ -154 +179 @@
         if (currBestTrainingSolution.TrainingRSquared < newSolution.TrainingRSquared) {
           currBestTrainingSolutionResult.Value = newSolution;
+          Results.AddOrUpdateResult(BestTrainingSolutionString, new StringValue(symbolString.ToString()));
           Results.AddOrUpdateResult(BestTrainingSolutionQuality, new DoubleValue(newSolution.TrainingRSquared).AsReadOnly());
         }
@@ -160 +186 @@
         if (currBestTestSolution.TestRSquared < newSolution.TestRSquared) {
           currBestTestSolutionResult.Value = newSolution;
+          Results.AddOrUpdateResult(BestTestSolutionString, new StringValue(symbolString.ToString()));
           Results.AddOrUpdateResult(BestTestSolutionQuality, new DoubleValue(newSolution.TestRSquared).AsReadOnly());
         }

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

@@ -7 +7 @@
 namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration {
   public class SymbolString : List<Symbol> {
+
+    public SymbolString() { }
 
     public SymbolString(IEnumerable<Symbol> symbols) : base(symbols) { }
@@ -20 +22 @@
     }
 
-    public override string ToString()
-    {
+    public override string ToString() {
       return string.Join(" ", this);
     }

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

@@ -1 +1 @@
 using System.Collections.Generic;
 using System.Linq;
+using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
 
 namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {