Changeset 15860

Timestamp:

03/23/18 18:36:23 (7 years ago)

Author:

lkammere

Message:

#2886: Change complexity measure from number of nodes in tree to number of variable references.

Location:

branches/2886_SymRegGrammarEnumeration

Files:

• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/RSquaredEvaluator.cs (modified) (3 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/SentenceLogger.cs (modified) (1 diff)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs (modified) (9 diffs)
• Test/GrammarEnumerationTest.cs (modified) (23 diffs)

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

@@ -77 +77 @@
         problemData.TrainingIndices,
         applyLinearScaling: false,
-        maxIterations: 200,
+        maxIterations: 50,
         updateVariableWeights: true,
         updateConstantsInTree: true);
@@ -96 +96 @@
       //var estVals = model.GetEstimatedValues(problemData.Dataset, problemData.TrainingIndices);
       //OnlineCalculatorError error;
-      //r2 = OnlinePearsonsRCalculator.Calculate(target, estVals, out error);
+      //double r2 = OnlinePearsonsRCalculator.Calculate(target, estVals, out error);
       //if (error != OnlineCalculatorError.None) r2 = 0.0;
 
@@ -102 +102 @@
       bool better = r2 > bestR2Result.Value;
       bool equallyGood = r2.IsAlmost(bestR2Result.Value);
-      bool shorter = algorithm.BestTrainingSentence != null && symbolString.Count() < algorithm.BestTrainingSentence.Count();
+      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;

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

@@ -45 +45 @@
 
     private void GrammarEnumerationAlgorithmOnStarted(object sender, EventArgs eventArgs) {
-      string datePostfix = $"_{DateTime.Now:yyyy-MM-dd_HH-mm}_TreeSize-{((GrammarEnumerationAlgorithm) sender).MaxTreeSize}.csv";
+      string datePostfix = $"_{DateTime.Now:yyyy-MM-dd_HH-mm}_TreeSize-{((GrammarEnumerationAlgorithm) sender).MaxComplexity}.csv";
       distinctSentencesFileName = workingDir + @"\distinctSentences" + datePostfix;
       allSentencesFileName = workingDir + @"\allSentences" + datePostfix;

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

@@ -24 +24 @@
     private readonly string DistinctSentencesName = "Distinct Sentences";
     private readonly string PhraseExpansionsName = "Phrase Expansions";
-    private readonly string AverageSentenceLengthName = "Avg. Sentence Length among Distinct";
+    private readonly string AverageSentenceComplexityName = "Avg. Sentence Complexity among Distinct";
     private readonly string OverwrittenSentencesName = "Sentences overwritten";
     private readonly string AnalyzersParameterName = "Analyzers";
@@ -31 +31 @@
 
     private readonly string SearchDataStructureParameterName = "Search Data Structure";
-    private readonly string MaxTreeSizeParameterName = "Max. Tree Nodes";
+    private readonly string MaxComplexityParameterName = "Max. Complexity";
     private readonly string GuiUpdateIntervalParameterName = "GUI Update Interval";
 
     public override bool SupportsPause { get { return false; } }
 
-    protected IValueParameter<IntValue> MaxTreeSizeParameter {
-      get { return (IValueParameter<IntValue>)Parameters[MaxTreeSizeParameterName]; }
-    }
-    public int MaxTreeSize {
-      get { return MaxTreeSizeParameter.Value.Value; }
-      set { MaxTreeSizeParameter.Value.Value = value; }
+    protected IValueParameter<IntValue> MaxComplexityParameter {
+      get { return (IValueParameter<IntValue>)Parameters[MaxComplexityParameterName]; }
+    }
+    public int MaxComplexity {
+      get { return MaxComplexityParameter.Value.Value; }
+      set { MaxComplexityParameter.Value.Value = value; }
     }
 
@@ -71 +71 @@
     #endregion
 
-    public Dictionary<int, int> DistinctSentencesLength { get; private set; }  // Semantically distinct sentences and their length in a run.
+    public Dictionary<int, int> DistinctSentencesComplexity { get; private set; }  // Semantically distinct sentences and their length in a run.
     public HashSet<int> ArchivedPhrases { get; private set; }
     internal SearchDataStore OpenPhrases { get; private set; }           // Stack/Queue/etc. for fetching the next node in the search tree.  
@@ -97 +97 @@
       };
 
-      Parameters.Add(new ValueParameter<IntValue>(MaxTreeSizeParameterName, "The number of clusters.", new IntValue(6)));
+      Parameters.Add(new ValueParameter<IntValue>(MaxComplexityParameterName, "The maximum number of variable symbols in a sentence.", new IntValue(5)));
       Parameters.Add(new ValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(100000)));
       Parameters.Add(new ValueParameter<EnumValue<StorageType>>(SearchDataStructureParameterName, new EnumValue<StorageType>(StorageType.Stack)));
@@ -127 +127 @@
       ArchivedPhrases = new HashSet<int>();
 
-      DistinctSentencesLength = new Dictionary<int, int>();
+      DistinctSentencesComplexity = new Dictionary<int, int>();
       AllGeneratedSentencesCount = 0;
       OverwrittenSentencesCount = 0;
@@ -159 +159 @@
 
           SymbolString newPhrase = currPhrase.DerivePhrase(nonterminalSymbolIndex, appliedProductions[i]);
-
-          if (newPhrase.Count() <= MaxTreeSize) {
+          int newPhraseComplexity = Grammar.GetComplexity(newPhrase);
+
+          if (newPhraseComplexity <= MaxComplexity) {
             var phraseHash = Grammar.Hasher.CalcHashCode(newPhrase);
 
@@ -170 +171 @@
               OnSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
 
-              if (!DistinctSentencesLength.ContainsKey(phraseHash) || DistinctSentencesLength[phraseHash] > newPhrase.Count()) {
-                if (DistinctSentencesLength.ContainsKey(phraseHash)) OverwrittenSentencesCount++; // for analysis only
-
-                DistinctSentencesLength[phraseHash] = newPhrase.Count();
+              if (!DistinctSentencesComplexity.ContainsKey(phraseHash) || DistinctSentencesComplexity[phraseHash] > newPhraseComplexity) {
+                if (DistinctSentencesComplexity.ContainsKey(phraseHash)) OverwrittenSentencesCount++; // for analysis only
+
+                DistinctSentencesComplexity[phraseHash] = newPhraseComplexity;
                 OnDistinctSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
               }
@@ -196 +197 @@
       Results.Add(new Result(PhraseExpansionsName, new IntValue(0)));
       Results.Add(new Result(OverwrittenSentencesName, new IntValue(0)));
-      Results.Add(new Result(AverageSentenceLengthName, new DoubleValue(1.0)));
+      Results.Add(new Result(AverageSentenceComplexityName, new DoubleValue(1.0)));
       Results.Add(new Result(ExpansionsPerSecondName, "In Thousand expansions per second", new IntValue(0)));
     }
@@ -209 +210 @@
         ((IntValue)Results[SearchStructureSizeName].Value).Value = OpenPhrases.Count;
         ((IntValue)Results[GeneratedSentencesName].Value).Value = AllGeneratedSentencesCount;
-        ((IntValue)Results[DistinctSentencesName].Value).Value = DistinctSentencesLength.Count;
+        ((IntValue)Results[DistinctSentencesName].Value).Value = DistinctSentencesComplexity.Count;
         ((IntValue)Results[PhraseExpansionsName].Value).Value = PhraseExpansionCount;
-        ((DoubleValue)Results[AverageSentenceLengthName].Value).Value = DistinctSentencesLength.Select(pair => pair.Value).Average();
+        ((DoubleValue)Results[AverageSentenceComplexityName].Value).Value = DistinctSentencesComplexity.Select(pair => pair.Value).Average();
         ((IntValue)Results[OverwrittenSentencesName].Value).Value = OverwrittenSentencesCount;
         ((IntValue)Results[ExpansionsPerSecondName].Value).Value = (int)((PhraseExpansionCount /

branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs

@@ -60 +60 @@
     public void NoConstants_Nguyen1() {
       // x³ + x² + x
-      alg.MaxTreeSize = 20;
+      alg.MaxComplexity = 6;
       alg.Problem.ProblemData = new NguyenFunctionOne(Seed).GenerateRegressionData();
 
@@ -80 +80 @@
       int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence);
 
-      Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
+      Assert.IsTrue(alg.DistinctSentencesComplexity.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
 
       Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
@@ -93 +93 @@
     public void NoConstants_Nguyen2() {
       // x^4 + x³ + x² + x
-      alg.MaxTreeSize = 30;
+      alg.MaxComplexity = 11;
       alg.Problem.ProblemData = new NguyenFunctionTwo(Seed).GenerateRegressionData();
 
@@ -105 +105 @@
     public void NoConstants_Nguyen3() {
       // x^5 + x^4 + x^3 + x^2 + x
-      alg.MaxTreeSize = 32;
+      alg.MaxComplexity = 32;
       alg.Problem.ProblemData = new NguyenFunctionThree(Seed).GenerateRegressionData();
 
@@ -117 +117 @@
     public void NoConstants_Nguyen6() {
       // sin(x) + sin(x + x²)
-      alg.MaxTreeSize = 25;
+      alg.MaxComplexity = 4;
       alg.Problem.ProblemData = new NguyenFunctionSix(Seed).GenerateRegressionData();
 
@@ -138 +138 @@
       int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence);
 
-      Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
+      Assert.IsTrue(alg.DistinctSentencesComplexity.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
       Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
 
@@ -148 +148 @@
     public void NoConstants_Nguyen9() {
       // sin(x) + sin(y²)
-      alg.MaxTreeSize = 22;
+      alg.MaxComplexity = 3;
       alg.Problem.ProblemData = new NguyenFunctionNine(Seed).GenerateRegressionData();
 
@@ -170 +170 @@
       int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence);
 
-      Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
+      Assert.IsTrue(alg.DistinctSentencesComplexity.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
       Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
 
@@ -180 +180 @@
     [TestProperty("Goal", "structure search")]
     public void MctsSymbReg_NoConstants_Poly10() {
-      alg.MaxTreeSize = 10;
+      alg.MaxComplexity = 10;
       alg.Problem.ProblemData = new PolyTen(Seed).GenerateRegressionData();
 
@@ -191 +191 @@
     public void NoConstants_Inverse() {
       // x / (log(x)*x + x)
-      alg.MaxTreeSize = 23;
+      alg.MaxComplexity = 4;
 
       var x = Enumerable.Range(0, 100).Select(_ => rand.NextDouble() + 1.1).ToList();
@@ -205 +205 @@
     public void Constants_Nguyen7() {
       // log(x+1) + log(x*x + 1)
-      alg.MaxTreeSize = 22;
+      alg.MaxComplexity = 3;
       alg.Problem.ProblemData = new NguyenFunctionSeven().GenerateRegressionData();
 
@@ -225 +225 @@
       int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence);
 
-      Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
+      Assert.IsTrue(alg.DistinctSentencesComplexity.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
       Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
-
 
       // Evaluate
@@ -237 +236 @@
     public void Constants_Nguyen12() {
       // x*x*x*x - x*x*x + y*y/2 -y
-      alg.MaxTreeSize = 28;
+      alg.MaxComplexity = 10;
       alg.Problem.ProblemData = new NguyenFunctionTwelve().GenerateRegressionData();
 
@@ -250 +249 @@
     public void Constants_Keijzer3() {
       // 0.3*x*sin(2*pi*x)
-      alg.MaxTreeSize = 20;
+      alg.MaxComplexity = 2;
       alg.Problem.ProblemData = new KeijzerFunctionThree().GenerateRegressionData();
 
@@ -270 +269 @@
       int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence);
 
-      Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
-
+      Assert.IsTrue(alg.DistinctSentencesComplexity.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
       Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
 
@@ -282 +280 @@
     public void Constants_Keijzer5() {
       // (30*x*z) / ((x - 10)*y*y)
-      alg.MaxTreeSize = 24;
+      alg.MaxComplexity = 5;
       alg.Problem.ProblemData = new KeijzerFunctionFive().GenerateRegressionData();
 
@@ -307 +305 @@
       int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence);
 
-      Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
+      Assert.IsTrue(alg.DistinctSentencesComplexity.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
 
       Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
@@ -320 +318 @@
     public void Constants_Keijzer12() {
       // x*x*x*x - x*x*x + y*y/2 - y
-      alg.MaxTreeSize = 29;
+      alg.MaxComplexity = 10;
       alg.Problem.ProblemData = new KeijzerFunctionTwelve().GenerateRegressionData();
 
@@ -344 +342 @@
       int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence);
 
-      Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
+      Assert.IsTrue(alg.DistinctSentencesComplexity.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
       Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
 
@@ -355 +353 @@
     public void Constants_Keijzer14() {
       // 8 / (2 + x*x + y*y
-      alg.MaxTreeSize = 19;
+      alg.MaxComplexity = 4;
       alg.Problem.ProblemData = new KeijzerFunctionFourteen().GenerateRegressionData();
 
@@ -380 +378 @@
       int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence);
 
-      Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
+      Assert.IsTrue(alg.DistinctSentencesComplexity.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
       Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
 
@@ -392 +390 @@
     public void Constants_Keijzer15() {
       // x*x*x / 5 + y*y*y / 2 - y - x
-      alg.MaxTreeSize = 25;
+      alg.MaxComplexity = 8;
       alg.Problem.ProblemData = new KeijzerFunctionFifteen().GenerateRegressionData();
 
@@ -415 +413 @@
       int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence);
 
-      Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
+      Assert.IsTrue(alg.DistinctSentencesComplexity.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
       Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");