Changeset 15723

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

Files:

• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs (modified) (4 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs (modified) (10 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Sentence.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Symbol.cs (modified) (1 diff)
• Test/GrammarEnumerationTest.cs (modified) (6 diffs)

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 {

branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs

@@ -1 +1 @@
 using System;
-using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration;
@@ -10 +9 @@
 
 namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression {
-  //[TestClass()]
+  [TestClass()]
   public class MctsSymbolicRegressionTest {
     private const int Seed = 1234;
     private IRandom rand;
 
-    private const double SuccessThreshold = 0.99999;
+    private const double SuccessThreshold = 0.9999999;
+
+    private GrammarEnumerationAlgorithm alg;
+    private RegressionProblem problem;
 
     [TestInitialize]
@@ -21 +23 @@
       Console.Write("init called... ");
       rand = new FastRandom(Seed);
-    }
+
+      alg = new GrammarEnumerationAlgorithm();
+      problem = new RegressionProblem();
+      alg.Problem = problem;
+      alg.GuiUpdateInterval = int.MaxValue;
+    }
+
+
+    private void TestGrammarEnumeration(IRegressionProblemData problemData) {
+      alg.Problem.ProblemData = problemData;
+
+      // Run
+      alg.Start();
+
+      // Evaluate results
+      var eps = 1.0 - SuccessThreshold;
+
+      // Check if algorithm terminated correctly
+      Assert.IsTrue(alg.Results.ContainsKey("Best solution quality (training)"), "No training solution returned!");
+      Assert.IsTrue(alg.Results.ContainsKey("Best solution quality (test)"), "No test solution returned!");
+
+      // Check resultss
+      Assert.AreEqual(1.0, ((DoubleValue)alg.Results["Best solution quality (training)"].Value).Value, eps, "Training quality too low!");
+      Assert.AreEqual(1.0, ((DoubleValue)alg.Results["Best solution quality (test)"].Value).Value, eps, "Test quality too low!");
+
+      // Check overfitting
+      Assert.AreEqual(alg.Results["Best solution string (training)"].Value.ToString(),
+                      alg.Results["Best solution string (test)"].Value.ToString());
+    }
+
 
     #region test structure search (no constants)
     [TestMethod]
-    [TestCategory("Algorithms.DataAnalysis")]
-    [TestProperty("Time", "short")]
+    [TestProperty("Goal", "structure search")]
     public void MctsSymbReg_NoConstants_Nguyen1() {
       // x³ + x² + x
+      alg.MaxTreeSize = 15;
       var provider = new HeuristicLab.Problems.Instances.DataAnalysis.NguyenInstanceProvider(Seed);
       var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("F1 ")));
       TestGrammarEnumeration(regProblem);
-    }
-    [TestMethod]
-    [TestCategory("Algorithms.DataAnalysis")]
-    [TestProperty("Time", "short")]
+
+      Console.WriteLine("Nguyen1: " + alg.Results["Best solution string (training)"].Value);
+    }
+
+    [TestMethod]
+    [TestProperty("Goal", "structure search")]
     public void MctsSymbReg_NoConstants_Nguyen2() {
       // x^4 + x³ + x² + x
+      alg.MaxTreeSize = 20;
       var provider = new HeuristicLab.Problems.Instances.DataAnalysis.NguyenInstanceProvider(Seed);
       var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("F2 ")));
       TestGrammarEnumeration(regProblem);
-    }
-    [TestMethod]
-    [TestCategory("Algorithms.DataAnalysis")]
-    [TestProperty("Time", "short")]
+
+      Console.WriteLine("Nguyen2: " + alg.Results["Best solution string (training)"].Value);
+    }
+
+    /*  NEXT UP
+    [TestMethod]
+    [TestProperty("Goal", "structure search")]
     public void MctsSymbReg_NoConstants_Nguyen3() {
       // x^5 + x^4 + x³ + x² + x
+      alg.MaxTreeSize = 25;
       var provider = new HeuristicLab.Problems.Instances.DataAnalysis.NguyenInstanceProvider(Seed);
       var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("F3 ")));
@@ -52 +90 @@
     }
     [TestMethod]
-    [TestCategory("Algorithms.DataAnalysis")]
-    [TestProperty("Time", "short")]
+    [TestProperty("Goal", "structure search")]
     public void MctsSymbReg_NoConstants_Nguyen4() {
+
       // x^6 + x^5 + x^4 + x³ + x² + x
+      alg.MaxTreeSize = 30;
       var provider = new HeuristicLab.Problems.Instances.DataAnalysis.NguyenInstanceProvider(Seed);
       var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("F4 ")));
       TestGrammarEnumeration(regProblem);
-    }
-
+    } */
+
+
+    #endregion
+
+    #region TODO
+
+#if false
     [TestMethod]
     [TestCategory("Algorithms.DataAnalysis")]
@@ -357 +402 @@
       TestGrammarEnumeration(problemData);
     }
-    #endregion
 
     #region restricted structure but including numeric constants
@@ -557 +601 @@
     #endregion
 
-    private void TestGrammarEnumeration(IRegressionProblemData problemData)
-    {
-      // Configure algorithm and problem
-      var alg = new GrammarEnumerationAlgorithm();
-      var problem = new RegressionProblem();
-      alg.Problem = problem;
-      problem.ProblemData = problemData;
-      
-      // Run
-      alg.Start();
-
-      // Evaluate results
-      var eps = 1.0 - SuccessThreshold;
-
-      // Check if algorithm terminated correctly
-      Assert.IsTrue(alg.Results.ContainsKey("Best solution quality (training)"), "No training solution returned!");
-      Assert.IsTrue(alg.Results.ContainsKey("Best solution quality (test)"), "No test solution returned!");
-
-      // Check resultss
-      Assert.AreEqual(1.0, ((DoubleValue)alg.Results["Best solution quality (training)"].Value).Value, eps, "Training quality too low!");
-      Assert.AreEqual(1.0, ((DoubleValue)alg.Results["Best solution quality (test)"].Value).Value, eps, "Test quality too low!");
-    }
+#endif
+    #endregion
   }
 }