Changeset 15722

Timestamp:

02/05/18 18:16:25 (7 years ago)

Author:

lkammere

Message:

#2886: Add evaluation of sentences.

Location:

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

Files:

• Grammar.cs (modified) (8 diffs)
• GrammarEnumerationAlgorithm.cs (modified) (6 diffs)

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

@@ -6 +6 @@
 using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
 using HeuristicLab.Common;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Problems.DataAnalysis.Symbolic;
 
 namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
@@ -13 +15 @@
 
     #region Symbols
+
     public VariableSymbol Var;
 
@@ -21 +24 @@
     public TerminalSymbol Addition;
     public TerminalSymbol Multiplication;
-    #endregion
-
+
+    #endregion
+
+
+    #region HL Symbols for Parsing ExpressionTrees
+
+    private TypeCoherentExpressionGrammar symbolicExpressionGrammar;
+
+    private ISymbol constSy;
+    private ISymbol varSy;
+
+    private ISymbol addSy;
+    private ISymbol mulSy;
+    private ISymbol logSy;
+    private ISymbol expSy;
+    private ISymbol divSy;
+
+    private ISymbol rootSy;
+    private ISymbol startSy;
+
+    #endregion
 
     public Grammar(string[] variables) {
@@ -48 +70 @@
       Factor.AddProduction(Var);
       #endregion
+
+      #region Parsing to SymbolicExpressionTree
+      symbolicExpressionGrammar = new TypeCoherentExpressionGrammar();
+      symbolicExpressionGrammar.ConfigureAsDefaultRegressionGrammar();
+
+      constSy = symbolicExpressionGrammar.Symbols.OfType<Constant>().First();
+      varSy = symbolicExpressionGrammar.Symbols.OfType<Variable>().First();
+      addSy = symbolicExpressionGrammar.AllowedSymbols.OfType<Addition>().First();
+      mulSy = symbolicExpressionGrammar.AllowedSymbols.OfType<Multiplication>().First();
+      logSy = symbolicExpressionGrammar.AllowedSymbols.OfType<Logarithm>().First();
+      expSy = symbolicExpressionGrammar.AllowedSymbols.OfType<Exponential>().First();
+      divSy = symbolicExpressionGrammar.AllowedSymbols.OfType<Division>().First();
+
+      rootSy = symbolicExpressionGrammar.AllowedSymbols.OfType<ProgramRootSymbol>().First();
+      startSy = symbolicExpressionGrammar.AllowedSymbols.OfType<StartSymbol>().First();
+
+      #endregion
     }
 
@@ -60 +99 @@
     }
 
+    #region Hashing
     private int[] GetSubtreeHashes(TerminalSymbol currentSymbol, Stack<TerminalSymbol> parseStack) {
       List<int> childHashes = null;
@@ -66 +106 @@
         childHashes = currentSymbol.StringRepresentation.GetHashCode().ToEnumerable().ToList();
 
-      } else if (ReferenceEquals(currentSymbol, Multiplication)) { // MULTIPLICATION
+      } else if (ReferenceEquals(currentSymbol, Multiplication)) {
+        // MULTIPLICATION
         childHashes = new List<int>();
 
@@ -94 +135 @@
 
 
-      } else if (ReferenceEquals(currentSymbol, Addition)) { // ADDITION
+      } else if (ReferenceEquals(currentSymbol, Addition)) {
+        // ADDITION
         HashSet<int> uniqueChildHashes = new HashSet<int>();
 
@@ -129 +171 @@
       return hashes.Aggregate(0, (result, ti) => ((result << 5) + result) ^ ti.GetHashCode());
     }
+    #endregion
+
+    #region Parse to SymbolicExpressionTree
+    public SymbolicExpressionTree ParseSymbolicExpressionTree(SymbolString sentence) {
+      Debug.Assert(sentence.Any(), "Trying to evaluate empty sentence!");
+      Debug.Assert(sentence.All(s => s is TerminalSymbol), "Trying to evaluate symbol sequence with nonterminalsymbols!");
+
+      symbolicExpressionGrammar.ConfigureAsDefaultRegressionGrammar();
+
+      var rootNode = rootSy.CreateTreeNode();
+      var startNode = startSy.CreateTreeNode();
+      rootNode.AddSubtree(startNode);
+
+      Stack<TerminalSymbol> parseStack = new Stack<TerminalSymbol>(sentence.OfType<TerminalSymbol>());
+      startNode.AddSubtree(ParseSymbolicExpressionTree(parseStack));
+
+      return new SymbolicExpressionTree(rootNode);
+    }
+
+    public ISymbolicExpressionTreeNode ParseSymbolicExpressionTree(Stack<TerminalSymbol> parseStack) {
+      TerminalSymbol currentSymbol = parseStack.Pop();
+
+      ISymbolicExpressionTreeNode parsedSubTree = null;
+
+      if (ReferenceEquals(currentSymbol, Addition)) {
+        parsedSubTree = addSy.CreateTreeNode();
+        parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack)); // left part
+        parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack)); // right part
+
+      } else if (ReferenceEquals(currentSymbol, Multiplication)) {
+        parsedSubTree = mulSy.CreateTreeNode();
+        parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack)); // left part
+        parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack)); // right part
+
+      } else if (Var.VariableTerminalSymbols.Contains(currentSymbol)) {
+        VariableTreeNode varNode = (VariableTreeNode)varSy.CreateTreeNode();
+        varNode.Weight = 1.0;
+        varNode.VariableName = currentSymbol.StringRepresentation;
+        parsedSubTree = varNode;
+      }
+
+      Debug.Assert(parsedSubTree != null);
+      return parsedSubTree;
+    }
+    #endregion
   }
 }

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

@@ -9 +9 @@
 using HeuristicLab.Core;
 using HeuristicLab.Data;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Optimization;
+using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.Problems.DataAnalysis;
+using HeuristicLab.Problems.DataAnalysis.Symbolic;
+using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
 
 namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
@@ -18 +22 @@
   [Creatable(CreatableAttribute.Categories.DataAnalysisRegression, Priority = 250)]
   public class GrammarEnumerationAlgorithm : FixedDataAnalysisAlgorithm<IRegressionProblem> {
+    private readonly string BestTrainingSolution = "Best solution (training)";
+    private readonly string BestTrainingSolutionQuality = "Best solution quality (training)";
+    private readonly string BestTestSolution = "Best solution (test)";
+    private readonly string BestTestSolutionQuality = "Best solution quality (test)";
+
+    private readonly string MaxTreeSizeParameterName = "Max. Tree Nodes";
+    private readonly string GuiUpdateIntervalParameterName = "GUI Update Interval";
+
+
+    #region properties
+    public IValueParameter<IntValue> MaxTreeSizeParameter {
+      get { return (IValueParameter<IntValue>)Parameters[MaxTreeSizeParameterName]; }
+    }
+
+    public int MaxTreeSize {
+      get { return MaxTreeSizeParameter.Value.Value; }
+    }
+
+    public IValueParameter<IntValue> GuiUpdateIntervalParameter {
+      get { return (IValueParameter<IntValue>)Parameters[MaxTreeSizeParameterName]; }
+    }
+
+    public int GuiUpdateInterval {
+      get { return GuiUpdateIntervalParameter.Value.Value; }
+    }
+
+    #endregion
+
+    private Grammar grammar;
+
+
+    #region ctors
     public override IDeepCloneable Clone(Cloner cloner) {
       return new GrammarEnumerationAlgorithm(this, cloner);
     }
 
-
     public GrammarEnumerationAlgorithm() {
       Problem = new RegressionProblem();
 
+      Parameters.Add(new ValueParameter<IntValue>(MaxTreeSizeParameterName, "The number of clusters.", new IntValue(4)));
+      Parameters.Add(new ValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(4000)));
     }
 
-
     private GrammarEnumerationAlgorithm(GrammarEnumerationAlgorithm original, Cloner cloner) : base(original, cloner) { }
-
-
-
+    #endregion
 
 
     protected override void Run(CancellationToken cancellationToken) {
+      List<SymbolString> allGenerated = new List<SymbolString>();
+      List<SymbolString> distinctGenerated = new List<SymbolString>();
+      HashSet<int> evaluatedHashes = new HashSet<int>();
 
-      IntValue generatedSolutions = new IntValue();
-      Results.Add(new Result("Generated Solutions", generatedSolutions));
-
-      DoubleValue averageTreeLength = new DoubleValue();
-      Results.Add(new Result("Average Tree Length of Solutions", averageTreeLength));
-
-      int maxStringLength = 4;
-
-
-      List<SymbolString> results = new List<SymbolString>();
-
-      Grammar grammar = new Grammar(new[] { "a", "b" });
+      grammar = new Grammar(Problem.ProblemData.AllowedInputVariables.ToArray());
 
       Stack<SymbolString> remainingTrees = new Stack<SymbolString>();
@@ -54 +80 @@
 
       while (remainingTrees.Any()) {
+        if (cancellationToken.IsCancellationRequested) break;
+
         SymbolString currSymbolString = remainingTrees.Pop();
 
         if (currSymbolString.IsSentence()) {
-          results.Add(currSymbolString);
+          allGenerated.Add(currSymbolString);
 
-          generatedSolutions.Value++;
-          averageTreeLength.Value = results.Select(r => r.Count).Average();
+          if (evaluatedHashes.Add(grammar.CalcHashCode(currSymbolString))) {
+            EvaluateSentence(currSymbolString);
+            distinctGenerated.Add(currSymbolString);
+          }
+
+          UpdateView(allGenerated, distinctGenerated);
 
         } else {
           // expand next nonterminal symbols
           int nonterminalSymbolIndex = currSymbolString.FindIndex(s => s is NonterminalSymbol);
-
           NonterminalSymbol expandedSymbol = currSymbolString[nonterminalSymbolIndex] as NonterminalSymbol;
 
@@ -73 +104 @@
             newSentence.InsertRange(nonterminalSymbolIndex, productionAlternative);
 
-            if (newSentence.Count <= maxStringLength) {
+            if (newSentence.Count <= MaxTreeSize) {
               remainingTrees.Push(newSentence);
             }
@@ -80 +111 @@
       }
 
-
-      StringArray sentences = new StringArray(results.Select(r => r.ToString()).ToArray());
-      Results.Add(new Result("All sentences", sentences));
+      StringArray sentences = new StringArray(allGenerated.Select(r => r.ToString()).ToArray());
+      Results.Add(new Result("All generated sentences", sentences));
+      StringArray distinctSentences = new StringArray(distinctGenerated.Select(r => r.ToString()).ToArray());
+      Results.Add(new Result("Distinct generated sentences", distinctSentences));
+    }
 
 
+    private void UpdateView(List<SymbolString> allGenerated, List<SymbolString> distinctGenerated) {
+      int generatedSolutions = allGenerated.Count;
+      int distinctSolutions = distinctGenerated.Count;
 
-      /*
-      addSy = grammar.AllowedSymbols.OfType<Addition>().First();
-      mulSy = grammar.AllowedSymbols.OfType<Multiplication>().First();
-      logSy = grammar.AllowedSymbols.OfType<Logarithm>().First();
-      expSy = grammar.AllowedSymbols.OfType<Exponential>().First();
-      divSy = grammar.AllowedSymbols.OfType<Division>().First();
+      if (generatedSolutions % GuiUpdateInterval == 0) {
+        Results.AddOrUpdateResult("Generated Solutions", new IntValue(generatedSolutions));
+        Results.Add(new Result("Distinct Solutions", new IntValue(distinctSolutions)));
 
-      progRootSy = grammar.AllowedSymbols.OfType<ProgramRootSymbol>().First();
-      startSy = grammar.AllowedSymbols.OfType<StartSymbol>().First();
+        DoubleValue averageTreeLength = new DoubleValue(allGenerated.Select(r => r.Count).Average());
+        Results.Add(new Result("Average Tree Length of Solutions", averageTreeLength));
+      }
+    }
 
-
-
-      var rootNode = progRootSy.CreateTreeNode();
-
-      var startNode = startSy.CreateTreeNode();
-      rootNode.AddSubtree(startNode);
-
-      startNode.AddSubtree(const0);
-
-
-
-      SymbolicExpressionTree tree = new SymbolicExpressionTree(rootNode);
-
+    private void EvaluateSentence(SymbolString symbolString) {
+      SymbolicExpressionTree tree = grammar.ParseSymbolicExpressionTree(symbolString);
       SymbolicRegressionModel model = new SymbolicRegressionModel(
         Problem.ProblemData.TargetVariable,
@@ -114 +138 @@
         new SymbolicDataAnalysisExpressionTreeLinearInterpreter());
 
-      IRegressionSolution solution = model.CreateRegressionSolution(Problem.ProblemData);
-      Results.Add(new Result("Best solution (training)", solution));
-      Results.Add(new Result("Best solution quality (training)", new DoubleValue(solution.TrainingRSquared).AsReadOnly()));
+      IRegressionSolution newSolution = model.CreateRegressionSolution(Problem.ProblemData);
 
-      Results.Add(new Result("Best solution (test)", solution));
-      Results.Add(new Result("Best solution quality (test)", new DoubleValue(solution.TestRSquared).AsReadOnly()));
-      */
+      IResult currBestTrainingSolutionResult;
+      IResult currBestTestSolutionResult;
+      if (!Results.TryGetValue(BestTrainingSolution, out currBestTrainingSolutionResult)
+           || !Results.TryGetValue(BestTestSolution, out currBestTestSolutionResult)) {
+
+        Results.Add(new Result(BestTrainingSolution, newSolution));
+        Results.Add(new Result(BestTrainingSolutionQuality, new DoubleValue(newSolution.TrainingRSquared).AsReadOnly()));
+        Results.Add(new Result(BestTestSolution, newSolution));
+        Results.Add(new Result(BestTestSolutionQuality, new DoubleValue(newSolution.TestRSquared).AsReadOnly()));
+
+      } else {
+        IRegressionSolution currBestTrainingSolution = (IRegressionSolution)currBestTrainingSolutionResult.Value;
+        if (currBestTrainingSolution.TrainingRSquared < newSolution.TrainingRSquared) {
+          currBestTrainingSolutionResult.Value = newSolution;
+          Results.AddOrUpdateResult(BestTrainingSolutionQuality, new DoubleValue(newSolution.TrainingRSquared).AsReadOnly());
+        }
+
+        IRegressionSolution currBestTestSolution = (IRegressionSolution)currBestTestSolutionResult.Value;
+        if (currBestTestSolution.TestRSquared < newSolution.TestRSquared) {
+          currBestTestSolutionResult.Value = newSolution;
+          Results.AddOrUpdateResult(BestTestSolutionQuality, new DoubleValue(newSolution.TestRSquared).AsReadOnly());
+        }
+      }
     }
   }