Changeset 15791

Timestamp:

02/20/18 13:43:36 (7 years ago)

Author:

lkammere

Message:

#2886: Replace integer hashing of phrases with simplification to (temporary) string representations.

Location:

branches/2886_SymRegGrammarEnumeration

Files:

• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs (modified) (4 diffs)
• Test/GrammarEnumerationTest.cs (modified) (5 diffs)
• Test/TreeHashingTest.cs (modified) (3 diffs)

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

@@ -120 +120 @@
       SimpleTerm.AddProduction(Var, SimpleTerm, Multiplication);
       SimpleTerm.AddProduction(Var);
-
+  
       InvExpr.AddProduction(InvTerm, InvExpr, Addition);
       InvExpr.AddProduction(InvTerm);
@@ -159 +159 @@
 
       Symbol peek = parseStack.Peek();
-      int[] subtreeHashes = GetSubtreeHashes(parseStack);
-      return AggregateHashes(peek, subtreeHashes);
-    }
-
-    private int[] GetSubtreeHashes(Stack<Symbol> parseStack) {
+      string[] subtreeHashes = GetSubtreeHashes(parseStack);
+      return AggregateHashes(peek, subtreeHashes).GetHashCode();
+    }
+
+    private string[] GetSubtreeHashes(Stack<Symbol> parseStack) {
       Symbol currentSymbol = parseStack.Pop();
 
       // ADDITION
       if (ReferenceEquals(currentSymbol, Addition)) {
-        HashSet<int> uniqueChildHashes = new HashSet<int>();
+        var uniqueChildHashes = new HashSet<string>();
 
         // First subtree
@@ -192 +192 @@
       // MULTIPLICATION
       if (ReferenceEquals(currentSymbol, Multiplication)) {
-        List<int> childHashes = new List<int>();
+        var childHashes = new List<string>();
 
         // First subtree
@@ -227 +227 @@
 
       // var or nonterminal symbol
-      return currentSymbol.StringRepresentation.GetHashCode().ToEnumerable().ToArray();
-    }
-
-    private int AggregateHashes(Symbol operatorSym, IEnumerable<int> hashes) {
+      return currentSymbol.StringRepresentation.ToEnumerable().ToArray();
+    }
+
+    private string AggregateHashes(Symbol operatorSym, IEnumerable<string> hashes) {
       var hashesArray = hashes.ToArray();
 
-      int start;
       if ((ReferenceEquals(operatorSym, Addition) || ReferenceEquals(operatorSym, Multiplication)) && hashesArray.Count() <= 1) {
-        start = 0;
-      } else {
-        start = operatorSym.StringRepresentation.GetHashCode();
-      }
-
-      return hashesArray.Aggregate(start, (result, ti) => ((result << 5) + result) ^ ti.GetHashCode());
+        return hashesArray[0];
+      }
+      if (Var.VariableTerminalSymbols.Contains(operatorSym)) {
+        return operatorSym.StringRepresentation;
+      }
+
+      return "[" + hashesArray.Aggregate(operatorSym.StringRepresentation, (result, ti) => result + " ° " + ti) + "]";
     }
     #endregion

branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs

@@ -75 +75 @@
       int actualSolutionHash = alg.Grammar.CalcHashCode(alg.BestTrainingSentence);
 
-      Assert.IsTrue(alg.DistinctSentences.ContainsKey(actualSolutionHash), "Actual solution was not generated!");
+      Assert.IsTrue(alg.DistinctSentences.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
 
       Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
@@ -112 +112 @@
     public void NoConstants_Nguyen6() {
       // sin(x) + sin(x + x²)
-      alg.MaxTreeSize = 13;
+      alg.MaxTreeSize = 10;
       alg.Problem.ProblemData = new NguyenFunctionSix(Seed).GenerateRegressionData();
 
@@ -130 +130 @@
       int actualSolutionHash = alg.Grammar.CalcHashCode(alg.BestTrainingSentence);
 
-      Assert.IsTrue(alg.DistinctSentences.ContainsKey(actualSolutionHash), "Actual solution was not generated!");
-
+      Assert.IsTrue(alg.DistinctSentences.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
       Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
 
@@ -141 +140 @@
     public void NoConstants_Nguyen9() {
       // sin(x) + sin(y²)
-      alg.MaxTreeSize = 10;
+      alg.MaxTreeSize = 11;
       alg.Problem.ProblemData = new NguyenFunctionNine(Seed).GenerateRegressionData();
 
       alg.Start();
+
+      TerminalSymbol xSymbol = alg.Grammar.Var.VariableTerminalSymbols.First(v => v.StringRepresentation == "X");
+      TerminalSymbol ySymbol = alg.Grammar.Var.VariableTerminalSymbols.First(v => v.StringRepresentation == "Y");
+      TerminalSymbol mulSymbol = alg.Grammar.Multiplication;
+      TerminalSymbol addSymbol = alg.Grammar.Addition;
+      TerminalSymbol sinSymbol = alg.Grammar.Sin;
+
+      SymbolString targetSolution = new SymbolString(new[] {
+        xSymbol, sinSymbol,
+        ySymbol, ySymbol, mulSymbol, sinSymbol, addSymbol
+      });
+
+      int targetSolutionHash = alg.Grammar.CalcHashCode(targetSolution);
+      int actualSolutionHash = alg.Grammar.CalcHashCode(alg.BestTrainingSentence);
+
+      Assert.IsTrue(alg.DistinctSentences.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
+      Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
+
       EvaluateGrammarEnumeration();
     }
@@ -162 +179 @@
     [TestProperty("Goal", "structure search")]
     public void NoConstants_Inverse() {
-      // 1 / (log(x)*x + x)
+      // sin(x) / (log(x)*x + x)
       alg.MaxTreeSize = 12;
 
       var x = Enumerable.Range(0, 100).Select(_ => rand.NextDouble() + 1.1).ToList();
-      var y = x.Select(xi => 1 / (Math.Log(xi) * xi + xi)).ToList();
+      var y = x.Select(xi => xi / (Math.Log(xi) * xi + xi)).ToList();
       alg.Problem.ProblemData = new RegressionProblemData(new Dataset(new List<string>() { "x", "y" }, new List<IList>() { x, y }), "x".ToEnumerable(), "y");
 

branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs

@@ -109 +109 @@
     [TestCategory("TreeHashing")]
     public void InverseFactorCancelationSimple() {
+      // 1/a * b * a * a
       SymbolString s1 = new SymbolString(new Symbol[] { varA, grammar.Inv, varB, grammar.Multiplication, varA, grammar.Multiplication, varA, grammar.Multiplication });
+      // a * b
       SymbolString s2 = new SymbolString(new Symbol[] { varA, varB, grammar.Multiplication });
 
@@ -130 +132 @@
     }
 
+    [TestMethod]
+    [TestCategory("TreeHashing")]
+    public void CompoundInverseCancellationToSingleInverse() {
+      SymbolString s1 = new SymbolString(new Symbol[] { varA, varB, grammar.Addition, grammar.Inv, grammar.Inv, grammar.Inv });
+      SymbolString s2 = new SymbolString(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() {
+      SymbolString s1 = new SymbolString(new Symbol[] { varA, varB, grammar.Addition, grammar.Inv, grammar.Inv });
+      SymbolString s2 = new SymbolString(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 a_UncancelableCompoundInverse() {
+      // 1 / ( 1/b + sin(a*c) )
+      SymbolString s1 = new SymbolString(new Symbol[] { varB, grammar.Inv, varA, varC, grammar.Multiplication, grammar.Sin, grammar.Addition, grammar.Inv });
+      // b + sin(a*c)
+      SymbolString s2 = new SymbolString(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);
+    }
+
     #region parser
 
@@ -144 +184 @@
     [TestCategory("Parser")]
     public void InfixParserComplexTest() {
-      SymbolString postfix = new SymbolString(new[] { varB, varA, varB, varC, grammar.Multiplication, grammar.Addition, grammar.Addition});
+      SymbolString postfix = new SymbolString(new[] { varB, varA, varB, varC, grammar.Multiplication, grammar.Addition, grammar.Addition });
       SymbolString infix = new SymbolString(new[] { varB, grammar.Addition, varA, grammar.Addition, varB, grammar.Multiplication, varC });