Changeset 16157

Timestamp:

09/20/18 11:12:57 (6 years ago)

Author:

bburlacu

Message:

#2886: Update IGrammarEnumerationEvaluator interface (add Evaluate method accepting an ISymbolicExpressionTree for the case when the constants have already been optimized in the tree, add boolean OptimizeConstants flag), small refactor in GrammarEnumeration/GrammarEnumerationAlgorithm.cs, add unit tests

Location:

branches/2886_SymRegGrammarEnumeration

Files:

• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/IGrammarEnumerationEvaluator.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs (modified) (9 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/RSquaredEvaluator.cs (modified) (2 diffs)
• Test/AlgorithmPerformanceTest.cs (added)
• Test/Test.csproj (modified) (1 diff)
• Test/TreeHashingTest.cs (modified) (2 diffs)

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

@@ -21 +21 @@
 
 using HeuristicLab.Core;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Problems.DataAnalysis;
 
@@ -26 +27 @@
   public interface IGrammarEnumerationEvaluator : IItem {
     double Evaluate(IRegressionProblemData problemData, Grammar grammar, SymbolList sentence);
+    double Evaluate(IRegressionProblemData problemData, ISymbolicExpressionTree tree);
+    bool OptimizeConstants { get; set; }
   }
 }

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

@@ -52 +52 @@
 
     private readonly string EvaluatorParameterName = "Evaluator";
-
-    private readonly string ErrorWeightParameterName = "Error Weight";
     private readonly string SearchDataStructureParameterName = "Search Data Structure";
     private readonly string MaxComplexityParameterName = "Max. Complexity";
+    private readonly string MaxLengthParameterName = "Max. Length";
     private readonly string GuiUpdateIntervalParameterName = "GUI Update Interval";
     private readonly string GrammarSymbolsParameterName = "Grammar Symbols";
@@ -67 +66 @@
     public override bool SupportsPause { get { return true; } }
 
-    public IFixedValueParameter<RSquaredEvaluator> EvaluatorParameter {
-      get { return (IFixedValueParameter<RSquaredEvaluator>)Parameters[EvaluatorParameterName]; }
-    }
-
-    public RSquaredEvaluator Evaluator {
+    public IValueParameter<IGrammarEnumerationEvaluator> EvaluatorParameter {
+      get { return (IValueParameter<IGrammarEnumerationEvaluator>)Parameters[EvaluatorParameterName]; }
+    }
+
+    public IGrammarEnumerationEvaluator Evaluator {
       get { return EvaluatorParameter.Value; }
     }
@@ -77 +76 @@
     protected IFixedValueParameter<IntValue> MaxComplexityParameter {
       get { return (IFixedValueParameter<IntValue>)Parameters[MaxComplexityParameterName]; }
+    }
+
+    protected IFixedValueParameter<IntValue> MaxLengthParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[MaxLengthParameterName]; }
     }
 
@@ -84 +87 @@
     }
 
-    protected IFixedValueParameter<DoubleValue> ErrorWeightParameter {
-      get { return (IFixedValueParameter<DoubleValue>)Parameters[ErrorWeightParameterName]; }
-    }
-
-    public double ErrorWeight {
-      get { return ErrorWeightParameter.Value.Value; }
-      set { ErrorWeightParameter.Value.Value = value; }
+    public int MaxLength {
+      get { return MaxLengthParameter.Value.Value; }
+      set { MaxLengthParameter.Value.Value = value; }
     }
 
@@ -200 +199 @@
 
     public GrammarEnumerationAlgorithm() {
-      Parameters.Add(new FixedValueParameter<DoubleValue>(ErrorWeightParameterName, "Defines, how much weight is put on a phrase's r² value when priorizing phrases during search.", new DoubleValue(0.8)));
       Parameters.Add(new FixedValueParameter<IntValue>(MaxComplexityParameterName, "The maximum number of variable symbols in a sentence.", new IntValue(12)));
+      Parameters.Add(new FixedValueParameter<IntValue>(MaxLengthParameterName, "The maximum number of variable symbols in a sentence.", new IntValue(20)));
       Parameters.Add(new FixedValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(5000)));
       Parameters.Add(new FixedValueParameter<IntValue>(SearchDataStructureSizeParameterName, "The size of the search data structure.", new IntValue((int)1e5)));
       Parameters.Add(new FixedValueParameter<EnumValue<StorageType>>(SearchDataStructureParameterName, new EnumValue<StorageType>(StorageType.SortedSet)));
-      Parameters.Add(new FixedValueParameter<RSquaredEvaluator>(EvaluatorParameterName, new RSquaredEvaluator()));
+      Parameters.Add(new ValueParameter<IGrammarEnumerationEvaluator>(EvaluatorParameterName, new RSquaredEvaluator()));
 
       SearchDataStructureParameter.Value.ValueChanged += (o, e) => Prepare();
@@ -283 +282 @@
       }
 
-      MaxSentenceLength = Grammar.GetMaxSentenceLength(MaxComplexity);
-      var errorWeight = ErrorWeight;
       var evaluator = EvaluatorParameter.Value;
       var problemData = Problem.ProblemData;
+
+      int maxLength = MaxLength;
+      int maxComplexity = MaxComplexity;
 
       // main search loop
@@ -313 +313 @@
 
           SymbolList newPhrase = currPhrase.DerivePhrase(nonterminalSymbolIndex, appliedProductions[i]);
+
+          if (newPhrase.Count > maxLength)
+            continue;
+
           int newPhraseComplexity = newPhrase.Complexity;
-
-          if (newPhraseComplexity > MaxComplexity)
+          if (newPhraseComplexity > maxComplexity)
             continue;
 
@@ -327 +330 @@
             OnSentenceGenerated(fetchedSearchNode.Hash, fetchedSearchNode.SymbolList, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
 
-            // Is the best solution found? (only if RSquaredEvaluator is activated)
-            //if (Results.ContainsKey(RSquaredEvaluator.BestTrainingQualityResultName)) {
-            //  double r2 = ((DoubleValue)Results[RSquaredEvaluator.BestTrainingQualityResultName].Value).Value;
-            //  if (r2.IsAlmost(1.0)) {
-            //    UpdateView(force: true);
-            //    return;
-            //  }
-            //}
-
             if (!DistinctSentencesComplexity.ContainsKey(phraseHash) || DistinctSentencesComplexity[phraseHash] > newPhraseComplexity) {
               if (DistinctSentencesComplexity.ContainsKey(phraseHash)) OverwrittenSentencesCount++; // for analysis only
-
               DistinctSentencesComplexity[phraseHash] = newPhraseComplexity;
               OnDistinctSentenceGenerated(fetchedSearchNode.Hash, fetchedSearchNode.SymbolList, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
             }
             UpdateView();
-
           } else if (!OpenPhrases.Contains(phraseHash) && !ArchivedPhrases.Contains(phraseHash)) {
             double r2 = IsCompleteSentence(newPhrase) ? evaluator.Evaluate(problemData, Grammar, newPhrase) : fetchedSearchNode.R2;
@@ -397 +389 @@
       var tree = Grammar.ParseSymbolicExpressionTree(BestTrainingSentence);
       var model = new SymbolicRegressionModel(Problem.ProblemData.TargetVariable, tree, interpreter);
-
-      var iterations = EvaluatorParameter.Value.ConstantOptimizationIterations;
-      var applyLinearScaling = EvaluatorParameter.Value.ApplyLinearScaling;
-
-      SymbolicRegressionConstantOptimizationEvaluator.OptimizeConstants(
-        interpreter,
-        model.SymbolicExpressionTree,
-        Problem.ProblemData,
-        Problem.ProblemData.TrainingIndices,
-        applyLinearScaling: applyLinearScaling,
-        maxIterations: iterations,
-        updateVariableWeights: false,
-        updateConstantsInTree: true);
+      Evaluator.Evaluate(Problem.ProblemData, tree); // this call will optimize the constants in the tree (if enabled)
 
       model.Scale(Problem.ProblemData);

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

@@ -61 +61 @@
     }
 
+    private IFixedValueParameter<IntValue> SeedParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[SeedParameterName]; }
+    }
+
     private int Restarts {
       get { return RestartsParameter.Value.Value; }
       set { RestartsParameter.Value.Value = value; }
+    }
+
+    private int Seed {
+      get { return SeedParameter.Value.Value; }
+      set { SeedParameter.Value.Value = value; }
     }
 
@@ -113 +122 @@
 
     public double Evaluate(IRegressionProblemData problemData, ISymbolicExpressionTree tree) {
+      random.Seed((uint)Seed); // not the ideal solution for ensuring result consistency
       return Evaluate(problemData, tree, random, OptimizeConstants, ConstantOptimizationIterations, ApplyLinearScaling, Restarts);
     }

branches/2886_SymRegGrammarEnumeration/Test/Test.csproj

@@ -119 +119 @@
     <Compile Include="Properties\AssemblyInfo.cs" />
     <Compile Include="TreeHashingTest.cs" />
+    <Compile Include="AlgorithmPerformanceTest.cs" />
   </ItemGroup>
   <ItemGroup>

branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs

@@ -1 @@
-using System.Linq;
+using System;
+using System.Collections.Generic;
+using System.Linq;
 using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration;
 using Microsoft.VisualStudio.TestTools.UnitTesting;
@@ -146 +148 @@
     }
 
-    /* DEPRECATED; SINCE WE DO NOT ALLOW COMPOUND DIVISIONS
-    [TestMethod]
-    [TestCategory("TreeHashing")]
-    public void CompoundInverseCancellationToSingleInverse() {
-      SymbolList s1 = new SymbolList(new Symbol[] { varA, varB, grammar.Addition, grammar.Inv, grammar.Inv, grammar.Inv });
-      SymbolList s2 = new SymbolList(new Symbol[] { varA, varB, grammar.Addition, grammar.Inv });
-
-      int hash1 = grammar.CalcHashCode(s1);
-      int hash2 = grammar.CalcHashCode(s2);
-
-      Assert.AreEqual(hash1, hash2);
-    }
-
-    [TestMethod]
-    [TestCategory("TreeHashing")]
-    public void CompoundInverseCancellationToDivisor() {
-      SymbolList s1 = new SymbolList(new Symbol[] { varA, varB, grammar.Addition, grammar.Inv, grammar.Inv });
-      SymbolList s2 = new SymbolList(new Symbol[] { varA, varB, grammar.Addition });
-
-      int hash1 = grammar.CalcHashCode(s1);
-      int hash2 = grammar.CalcHashCode(s2);
-
-      Assert.AreEqual(hash1, hash2);
-    }
-
-    [TestMethod]
-    [TestCategory("TreeHashing")]
-    public void UncancelableCompoundInverse() {
-      // 1 / ( 1/b + sin(a*c) )
-      SymbolList s1 = new SymbolList(new Symbol[] { varB, grammar.Inv, varA, varC, grammar.Multiplication, grammar.Sin, grammar.Addition, grammar.Inv });
-      // b + sin(a*c)
-      SymbolList s2 = new SymbolList(new Symbol[] { varB, varA, varC, grammar.Multiplication, grammar.Sin, grammar.Addition });
-
-      int hash1 = grammar.CalcHashCode(s1);
-      int hash2 = grammar.CalcHashCode(s2);
-
-      Assert.AreNotEqual(hash1, hash2);
-    }*/
+    [TestMethod]
+    [TestCategory("TreeHashing")]
+    public void EnumerateGrammarTest() {
+      //const int nvars = 1;
+      //var variables = Enumerable.Range(1, nvars).Select(x => $"x{x}").ToArray();
+      var variables = new[] { "b", "a" };
+      var grammar = new Grammar(variables, Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>());
+
+      int hash(SymbolList s) => grammar.Hasher.CalcHashCode(s);
+
+      List<SymbolList> sentences = EnumerateGrammarBreadth(grammar, length: 20, hashPhrases: false).ToList();
+      Console.WriteLine($"Breadth: {sentences.Count};{sentences.Select(hash).Distinct().Count() }");
+
+      sentences = EnumerateGrammarBreadth(grammar, length: 20, hashPhrases: true).ToList();
+      Console.WriteLine($"Breadth (hashed): {sentences.Count};{sentences.Select(hash).Distinct().Count() }");
+
+      sentences = EnumerateGrammarDepth(grammar, length: 20, hashPhrases: false).ToList();
+      Console.WriteLine($"Depth: {sentences.Count};{sentences.Select(hash).Distinct().Count() }");
+
+      sentences = EnumerateGrammarDepth(grammar, length: 20, hashPhrases: true).ToList();
+      Console.WriteLine($"Depth (hashed): {sentences.Count};{sentences.Select(hash).Distinct().Count() }");
+    }
+
+    private static IEnumerable<SymbolList> EnumerateGrammarBreadth(Grammar grammar, int length, bool hashPhrases = true) {
+      var phrases = new Queue<SymbolList>();
+      phrases.Enqueue(new SymbolList(grammar.StartSymbol));
+      var sentences = new List<SymbolList>();
+      var archive = new HashSet<int>();
+
+      while (phrases.Any()) {
+        var phrase = phrases.Dequeue();
+
+        if (phrase.Count > length)
+          continue;
+
+        if (phrase.IsSentence()) {
+          sentences.Add(phrase);
+          continue;
+        }
+
+        if (hashPhrases && !archive.Add(grammar.Hasher.CalcHashCode(phrase))) {
+          continue;
+        }
+
+        var idx = phrase.NextNonterminalIndex();
+        var productions = grammar.Productions[phrase[idx]];
+        var derived = productions.Select(p => phrase.DerivePhrase(idx, p)).Where(p => p.Count <= length);
+        foreach (var d in derived)
+          phrases.Enqueue(d);
+      }
+      return sentences;
+    }
+
+    private static IEnumerable<SymbolList> EnumerateGrammarDepth(Grammar grammar, int length, bool hashPhrases = true) {
+      return Expand(new SymbolList(grammar.StartSymbol), grammar, length, hashPhrases ? new HashSet<int>() : null);
+    }
+
+    private static IEnumerable<SymbolList> Expand(SymbolList phrase, Grammar grammar, int maxLength, HashSet<int> visited) {
+      if (phrase.Count > maxLength) {
+        yield break;
+      }
+
+      if (phrase.IsSentence()) {
+        yield return phrase;
+        yield break;
+      }
+
+      if (visited != null && !visited.Add(grammar.Hasher.CalcHashCode(phrase))) {
+        yield break;
+      }
+
+      var i = phrase.NextNonterminalIndex();
+      var productions = grammar.Productions[phrase[i]];
+
+      foreach (var s in productions.SelectMany(p => Expand(phrase.DerivePhrase(i, p), grammar, maxLength, visited)))
+        yield return s;
+    }
   }
 }