Changeset 15993

Timestamp:

07/11/18 10:34:21 (6 years ago)

Author:

bburlacu

Message:

#2886: refactor code

Location:

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

Files:

• Analysis/RSquaredEvaluator.cs (modified) (7 diffs)
• GrammarEnumeration/Grammar.cs (modified) (1 diff)
• GrammarEnumeration/GrammarEnumerationAlgorithm.cs (modified) (14 diffs)
• GrammarEnumeration/SearchDataStructure.cs (modified) (7 diffs)

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

@@ -2 +2 @@
 using System.Diagnostics;
 using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
+using HeuristicLab.Analysis;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -20 +21 @@
     public static readonly string BestTrainingSolutionResultName = "Best solution (Training)";
     public static readonly string BestComplexityResultName = "Best solution complexity";
+    public static readonly string BestSolutions = "Best solutions";
 
     private static readonly ISymbolicDataAnalysisExpressionTreeInterpreter expressionTreeLinearInterpreter = new SymbolicDataAnalysisExpressionTreeLinearInterpreter();
-
-    public bool OptimizeConstants { get; set; }
 
     public RSquaredEvaluator() { }
@@ -31 +31 @@
 
     protected RSquaredEvaluator(RSquaredEvaluator original, Cloner cloner) : base(original, cloner) {
-      this.OptimizeConstants = original.OptimizeConstants;
     }
 
@@ -52 +51 @@
     private void AlgorithmOnDistinctSentenceGenerated(object sender, PhraseAddedEventArgs phraseAddedEventArgs) {
       GrammarEnumerationAlgorithm algorithm = (GrammarEnumerationAlgorithm)sender;
-      EvaluateSentence(algorithm, phraseAddedEventArgs.NewPhrase);
+      EvaluateSentence(algorithm, phraseAddedEventArgs.NewPhrase, algorithm.OptimizeConstants);
     }
 
@@ -70 +69 @@
     }
 
-    private void EvaluateSentence(GrammarEnumerationAlgorithm algorithm, SymbolString symbolString) {
+    private void EvaluateSentence(GrammarEnumerationAlgorithm algorithm, SymbolString symbolString, bool optimizeConstants) {
       var results = algorithm.Results;
       var grammar = algorithm.Grammar;
@@ -78 +77 @@
       Debug.Assert(SymbolicRegressionConstantOptimizationEvaluator.CanOptimizeConstants(tree));
 
-      double r2 = Evaluate(problemData, tree, OptimizeConstants);
+      double r2 = Evaluate(problemData, tree, optimizeConstants);
       double bestR2 = results.ContainsKey(BestTrainingQualityResultName) ? GetValue<double>(results[BestTrainingQualityResultName].Value) : 0.0;
       if (r2 < bestR2)
@@ -90 +89 @@
         results.AddOrUpdateResult(BestComplexityResultName, new IntValue(complexity));
         algorithm.BestTrainingSentence = symbolString;
+
+        // record best sentence quality & length
+        DataTable dt;
+        if (!results.ContainsKey(BestSolutions)) {
+          var names = new[] { "Quality", "Relative Length", "Complexity", "Timestamp" };
+          dt = new DataTable();
+          foreach (var name in names) {
+            dt.Rows.Add(new DataRow(name) { VisualProperties = { StartIndexZero = true } });
+          }
+          results.AddOrUpdateResult(BestSolutions, dt);
+        }
+        dt = (DataTable)results[BestSolutions].Value;
+        dt.Rows["Quality"].Values.Add(r2);
+        dt.Rows["Relative Length"].Values.Add((double)symbolString.Count() / algorithm.MaxSentenceLength);
+        dt.Rows["Complexity"].Values.Add(complexity);
+        dt.Rows["Timestamp"].Values.Add(algorithm.ExecutionTime.TotalMilliseconds / 1000d);
       }
     }

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

@@ -243 +243 @@
     }
 
+    // returns the maximum achievable sentence length below the maximum complexity
+    public int GetMaxSentenceLength(int maxComplexity) {
+      SymbolString s = new SymbolString(StartSymbol);
+
+      while (!s.IsSentence() && GetComplexity(s) <= maxComplexity) {
+        int expandedSymbolIndex = s.NextNonterminalIndex();
+        NonterminalSymbol expandedSymbol = (NonterminalSymbol)s[expandedSymbolIndex];
+
+        var productions = Productions[expandedSymbol];
+        var longestProduction = productions // Find production with most terminal symbols to expand as much as possible...
+          .OrderBy(CountTerminals)          // but with lowest complexity/nonterminal count to keep complexity low.                                                                                     
+          .ThenByDescending(CountNonTerminals)
+          .First();
+
+        s = s.DerivePhrase(expandedSymbolIndex, longestProduction);
+      }
+
+      return s.Count();
+    }
+
+    private int CountTerminals(Production p) {
+      return p.Count(s => s is TerminalSymbol);
+    }
+
+    private int CountNonTerminals(Production p) {
+      return p.Count(s => s is NonterminalSymbol);
+    }
+
     public double EvaluatePhrase(SymbolString s, IRegressionProblemData problemData, bool optimizeConstants) {
       SymbolicExpressionTree tree = ParseSymbolicExpressionTree(s);

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

@@ -21 +21 @@
   public class GrammarEnumerationAlgorithm : FixedDataAnalysisAlgorithm<IRegressionProblem> {
     #region properties and result names
-    private readonly string VariableImportanceWeightName = "Variable Importance Weight";
     private readonly string SearchStructureSizeName = "Search Structure Size";
     private readonly string GeneratedPhrasesName = "Generated/Archived Phrases";
@@ -38 +37 @@
     private readonly string GuiUpdateIntervalParameterName = "GUI Update Interval";
     private readonly string GrammarSymbolsParameterName = "Grammar Symbols";
-    private readonly string SearchCacheSizeParameterName = "Search Cache Size";
     private readonly string SearchDataStructureSizeParameterName = "Search Data Structure Size";
 
@@ -48 +46 @@
     public override bool SupportsPause { get { return true; } }
 
-    protected IFixedValueParameter<DoubleValue> VariableImportanceWeightParameter {
-      get { return (IFixedValueParameter<DoubleValue>)Parameters[VariableImportanceWeightName]; }
-    }
-
-    public double VariableImportanceWeight {
-      get { return VariableImportanceWeightParameter.Value.Value; }
-      set { VariableImportanceWeightParameter.Value.Value = value; }
-    }
-
     protected IFixedValueParameter<BoolValue> OptimizeConstantsParameter {
       get { return (IFixedValueParameter<BoolValue>)Parameters[OptimizeConstantsParameterName]; }
@@ -105 +94 @@
     }
 
-    public IFixedValueParameter<IntValue> SearchCacheSizeParameter {
-      get { return (IFixedValueParameter<IntValue>)Parameters[SearchCacheSizeParameterName]; }
-    }
-
-    public int SearchCacheSize {
-      get { return SearchCacheSizeParameter.Value.Value; }
-    }
-
     public StorageType SearchDataStructure {
       get { return SearchDataStructureParameter.Value.Value; }
@@ -146 +127 @@
     [Storable]
     internal SearchDataStore OpenPhrases { get; private set; }           // Stack/Queue/etc. for fetching the next node in the search tree.  
+
+    [Storable]
+    public int MaxSentenceLength { get; private set; }
 
     #region execution stats
@@ -178 +162 @@
       SearchDataStructureParameter.Value.ValueChanged += (o, e) => Prepare();
       SearchDataStructureSizeParameter.Value.ValueChanged += (o, e) => Prepare();
-      SearchCacheSizeParameter.Value.ValueChanged += (o, e) => Prepare();
     }
 
@@ -188 +171 @@
       SearchDataStructureParameter.Value.ValueChanged -= (o, e) => Prepare();
       SearchDataStructureSizeParameter.Value.ValueChanged -= (o, e) => Prepare();
-      SearchCacheSizeParameter.Value.ValueChanged -= (o, e) => Prepare();
     }
 
@@ -197 +179 @@
 
     public GrammarEnumerationAlgorithm() {
-      Parameters.Add(new FixedValueParameter<DoubleValue>(VariableImportanceWeightName, "Variable Weight.", new DoubleValue(1.0)));
       Parameters.Add(new FixedValueParameter<BoolValue>(OptimizeConstantsParameterName, "Run constant optimization in sentence evaluation.", new BoolValue(false)));
       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>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(5000)));
-      Parameters.Add(new FixedValueParameter<IntValue>(SearchCacheSizeParameterName, "The size of the search node cache.", new IntValue((int)1e5)));
       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.PriorityQueue)));
+      Parameters.Add(new FixedValueParameter<EnumValue<StorageType>>(SearchDataStructureParameterName, new EnumValue<StorageType>(StorageType.SortedSet)));
 
       SearchDataStructureParameter.Value.ValueChanged += (o, e) => Prepare();
       SearchDataStructureSizeParameter.Value.ValueChanged += (o, e) => Prepare();
-      SearchCacheSizeParameter.Value.ValueChanged += (o, e) => Prepare();
 
       var availableAnalyzers = new IGrammarEnumerationAnalyzer[] {
@@ -258 +237 @@
       OverwrittenSentencesCount = original.OverwrittenSentencesCount;
       PhraseExpansionCount = original.PhraseExpansionCount;
-
-      if (original.variableImportance != null)
-        variableImportance = new Dictionary<VariableTerminalSymbol, double>(original.variableImportance);
     }
     #endregion
@@ -274 +250 @@
       PhraseExpansionCount = 0;
 
-      Analyzers.OfType<RSquaredEvaluator>().First().OptimizeConstants = OptimizeConstants;
       Grammar = new Grammar(Problem.ProblemData.AllowedInputVariables.ToArray(), GrammarSymbols.CheckedItems.Select(v => v.Value));
-      OpenPhrases = new SearchDataStore(SearchDataStructure, SearchDataStructureSize, SearchCacheSize); // Select search strategy
-
-      CalculateVariableImportances();
-
+      OpenPhrases = new SearchDataStore(SearchDataStructure, SearchDataStructureSize); // Select search strategy
       base.Prepare(); // this actually clears the results which will get reinitialized on Run()
-    }
-
-    private void CalculateVariableImportances() {
-      variableImportance = new Dictionary<VariableTerminalSymbol, double>();
-
-      RandomForestRegression rf = new RandomForestRegression();
-      rf.Problem = Problem;
-      rf.Start();
-      IRegressionSolution rfSolution = (RandomForestRegressionSolution)rf.Results["Random forest regression solution"].Value;
-      var rfImpacts = RegressionSolutionVariableImpactsCalculator.CalculateImpacts(
-        rfSolution,
-        RegressionSolutionVariableImpactsCalculator.DataPartitionEnum.Training,
-        RegressionSolutionVariableImpactsCalculator.ReplacementMethodEnum.Shuffle);
-
-      // save the normalized importances
-      var sum = rfImpacts.Sum(x => x.Item2);
-      foreach (Tuple<string, double> rfImpact in rfImpacts) {
-        VariableTerminalSymbol varSym = Grammar.VarTerminals.First(v => v.StringRepresentation == rfImpact.Item1);
-        variableImportance[varSym] = rfImpact.Item2 / sum;
-      }
     }
 
@@ -313 +265 @@
       }
 
-      int maxSentenceLength = GetMaxSentenceLength();
+      MaxSentenceLength = Grammar.GetMaxSentenceLength(MaxComplexity);
       var errorWeight = ErrorWeight;
-      var variableImportanceWeight = VariableImportanceWeight;
+      var optimizeConstants = OptimizeConstants; // cache value to avoid parameter lookup
       // main search loop
       while (OpenPhrases.Count > 0) {
@@ -375 +327 @@
 
             bool isCompleteSentence = IsCompleteSentence(newPhrase);
-            double r2 = isCompleteSentence ? Grammar.EvaluatePhrase(newPhrase, Problem.ProblemData, OptimizeConstants) : fetchedSearchNode.R2;
-            double phrasePriority = GetPriority(newPhrase, r2, maxSentenceLength, errorWeight, variableImportanceWeight);
+            double r2 = isCompleteSentence ? Grammar.EvaluatePhrase(newPhrase, Problem.ProblemData, optimizeConstants) : fetchedSearchNode.R2;
+            double phrasePriority = GetPriority(newPhrase, r2, MaxSentenceLength);
 
             SearchNode newSearchNode = new SearchNode(phraseHash, phrasePriority, r2, newPhrase);
@@ -386 +338 @@
     }
 
-    protected double GetPriority(SymbolString phrase, double r2, int maxSentenceLength, double errorWeight, double variableImportanceWeight) {
-      var distinctVars = phrase.OfType<VariableTerminalSymbol>().Distinct();
-
-      var sum = 0d;
-      foreach (var v in distinctVars) {
-        sum += variableImportance[v];
-      }
-      var phraseVariableImportance = 1 - sum;
-
-      double relLength = (double)phrase.Count() / maxSentenceLength;
-      double error = 1.0 - r2;
-      return error * relLength;
+    protected static double GetPriority(SymbolString phrase, double r2, int maxSentenceLength) {
+      return (1 - r2) * phrase.Count() / maxSentenceLength;
     }
 
     private bool IsCompleteSentence(SymbolString phrase) {
       return !phrase.Any(x => x is NonterminalSymbol && x != Grammar.Expr);
-    }
-
-    private int GetMaxSentenceLength() {
-      SymbolString s = new SymbolString(Grammar.StartSymbol);
-
-      while (!s.IsSentence() && Grammar.GetComplexity(s) <= MaxComplexity) {
-        int expandedSymbolIndex = s.NextNonterminalIndex();
-        NonterminalSymbol expandedSymbol = (NonterminalSymbol)s[expandedSymbolIndex];
-
-        var productions = Grammar.Productions[expandedSymbol];
-        var longestProduction = productions // Find production with most terminal symbols to expand as much as possible...
-          .OrderBy(CountTerminals)          // but with lowest complexity/nonterminal count to keep complexity low.                                                                                     
-          .ThenByDescending(CountNonTerminals)
-          .First();
-
-        s = s.DerivePhrase(expandedSymbolIndex, longestProduction);
-      }
-
-      return s.Count();
-    }
-
-    private int CountTerminals(Production p) {
-      return p.Count(s => s is TerminalSymbol);
-    }
-
-    private int CountNonTerminals(Production p) {
-      return p.Count(s => s is NonterminalSymbol);
     }
 
@@ -461 +376 @@
       }
 
+      var interpreter = new SymbolicDataAnalysisExpressionTreeLinearInterpreter();
       var tree = Grammar.ParseSymbolicExpressionTree(BestTrainingSentence);
-      var model = new SymbolicRegressionModel(Problem.ProblemData.TargetVariable, tree, new SymbolicDataAnalysisExpressionTreeLinearInterpreter());
-      model.Scale(Problem.ProblemData);
+      var model = new SymbolicRegressionModel(Problem.ProblemData.TargetVariable, tree, interpreter);
+
+      SymbolicRegressionConstantOptimizationEvaluator.OptimizeConstants(
+        interpreter,
+        model.SymbolicExpressionTree,
+        Problem.ProblemData,
+        Problem.ProblemData.TrainingIndices,
+        applyLinearScaling: true,
+        maxIterations: 10,
+        updateVariableWeights: false,
+        updateConstantsInTree: true);
+
       var bestTrainingSolution = new SymbolicRegressionSolution(model, Problem.ProblemData);
       Results.AddOrUpdateResult(BestTrainingModelResultName, model);

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

@@ -52 +52 @@
   class SearchDataStore : DeepCloneable, IEnumerable<SearchNode> {
     [Storable]
-    private LruCache<int, SearchNode> storedValues;
-    //private Dictionary<int, SearchNode> storedValues; // Store hash-references and associated, actual values 
+    private Dictionary<int, SearchNode> storedValues; // Store hash-references and associated, actual values 
 
     [Storable]
@@ -72 +71 @@
     [Storable]
     private int searchDataStructureSize; // storage size for search nodes 
-
-    [Storable]
-    private int cacheSize; // cache for already explored search nodes 
 
     [ExcludeFromObjectGraphTraversal]
@@ -87 +83 @@
     protected SearchDataStore(bool deserializing) : this() { }
 
-    public SearchDataStore(StorageType storageType, int searchDataStructureSize = (int)1e5, int cacheSize = (int)1e5) {
+    public SearchDataStore(StorageType storageType, int searchDataStructureSize = (int)1e5) {
       this.storageType = storageType;
 
       this.searchDataStructureSize = searchDataStructureSize;
-      this.cacheSize = cacheSize;
-
-      storedValues = new LruCache<int, SearchNode>(this.cacheSize);
+
+      storedValues = new Dictionary<int, SearchNode>();
       InitSearchDataStructure();
     }
@@ -142 +137 @@
 
     protected SearchDataStore(SearchDataStore original, Cloner cloner) : base(original, cloner) {
-      storedValues = cloner.Clone(original.storedValues);
+      storedValues = original.storedValues.ToDictionary(x => x.Key, x => cloner.Clone(x.Value));
       storageType = original.storageType;
-      cacheSize = original.cacheSize;
       searchDataStructureSize = original.searchDataStructureSize;
 
@@ -204 +198 @@
               var max = sortedSet.Max;
               sortedSet.Remove(max);
-              storedValues.Remove(max.Item2);
+              storedValues.Remove(max.Item2); // should always be in sync with the sorted set
             }
             sortedSet.Add(Tuple.Create(prio, hash));
@@ -211 +205 @@
             var elem = sortedSet.FirstOrDefault();
             if (elem == null)
-              return 0;
+              return default(int);
             sortedSet.Remove(elem);
             return elem.Item2;
@@ -226 +220 @@
         // size is the 0-based index of the last used element
         if (priorityQueue.Size == capacity - 1) {
-          // if the queue is at capacity we have to replace 
-          return;
+          return; // if the queue is at capacity we have to return 
         }
         priorityQueue.Insert(prio, hash);