Changeset 15784

Timestamp:

02/16/18 18:36:17 (6 years ago)

Author:

lkammere

Message:

#2886: Add basic implementation for inverse factors.

Location:

branches/2886_SymRegGrammarEnumeration

Files:

• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs (modified) (11 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs (modified) (1 diff)
• Test/GrammarEnumerationTest.cs (modified) (7 diffs)
• Test/TreeHashingTest.cs (modified) (1 diff)

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

@@ -24 +24 @@
     public NonterminalSymbol SinFactor;
 
+    public NonterminalSymbol InvExpr;
+    public NonterminalSymbol InvTerm;
+    public NonterminalSymbol InvFactor;
+
     public NonterminalSymbol SimpleExpr;
     public NonterminalSymbol SimpleTerm;
@@ -32 +36 @@
     public TerminalSymbol Exp;
     public TerminalSymbol Sin;
+    public TerminalSymbol Inv;
 
     // For infix notation
@@ -70 +75 @@
       SinFactor = new NonterminalSymbol("SinFactor");
 
+      InvExpr = new NonterminalSymbol("InvExpr");
+      InvTerm = new NonterminalSymbol("InvTerm");
+      InvFactor = new NonterminalSymbol("InvFactor");
+
       SimpleExpr = new NonterminalSymbol("SimpleExpr");
       SimpleTerm = new NonterminalSymbol("SimpleTerm");
@@ -78 +87 @@
       Exp = new TerminalSymbol("exp");
       Sin = new TerminalSymbol("sin");
+      Inv = new TerminalSymbol("inv");
 
       OpeningBracket = new TerminalSymbol("(");
@@ -94 +104 @@
       Term.AddProduction(Factor, Term, Multiplication);
       Term.AddProduction(Factor);
+      Term.AddProduction(InvExpr, Inv);
 
       Factor.AddProduction(Var);
@@ -109 +120 @@
       SimpleTerm.AddProduction(Var, SimpleTerm, Multiplication);
       SimpleTerm.AddProduction(Var);
+
+      InvExpr.AddProduction(InvTerm, InvExpr, Addition);
+      InvExpr.AddProduction(InvTerm);
+
+      InvTerm.AddProduction(InvFactor, InvTerm, Multiplication);
+      InvTerm.AddProduction(InvFactor);
+
+      InvFactor.AddProduction(Var);
+      InvFactor.AddProduction(LogFactor);
+      InvFactor.AddProduction(SinFactor);
       #endregion
 
@@ -144 +165 @@
     private int[] GetSubtreeHashes(Stack<Symbol> parseStack) {
       Symbol currentSymbol = parseStack.Pop();
-
-      // MULTIPLICATION
-      if (ReferenceEquals(currentSymbol, Multiplication)) {
-        List<int> childHashes = new List<int>();
-
-        // First subtree
-        if (ReferenceEquals(parseStack.Peek(), Multiplication)) {
-          childHashes.AddRange(GetSubtreeHashes(parseStack));
-        } else {
-          childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
-        }
-        // Second subtree
-        if (ReferenceEquals(parseStack.Peek(), Multiplication)) {
-          childHashes.AddRange(GetSubtreeHashes(parseStack));
-        } else {
-          childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
-        }
-
-        // Sort due to commutativity
-        childHashes.Sort();
-        return childHashes.ToArray();
-      }
 
       // ADDITION
@@ -191 +190 @@
       }
 
-      // LOG, EXP, SIN
+      // MULTIPLICATION
+      if (ReferenceEquals(currentSymbol, Multiplication)) {
+        List<int> childHashes = new List<int>();
+
+        // First subtree
+        if (ReferenceEquals(parseStack.Peek(), Multiplication)) {
+          childHashes.AddRange(GetSubtreeHashes(parseStack));
+        } else {
+          childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
+        }
+        // Second subtree
+        if (ReferenceEquals(parseStack.Peek(), Multiplication)) {
+          childHashes.AddRange(GetSubtreeHashes(parseStack));
+        } else {
+          childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
+        }
+
+        // Sort due to commutativity
+        childHashes.Sort();
+
+        // Cancel out inverse factors.
+        var inversChildHashes = childHashes
+          .Select(ch => AggregateHashes(Inv, ch.ToEnumerable()))
+          .ToList();
+
+        return childHashes // If this factor cancels out another one, then remove BOTH. Otherwise, keep the factor.
+          .Where(ch => !inversChildHashes.Remove(ch))
+          .ToArray();
+      }
+
+      // LOG, EXP, SIN, INV
       if (ReferenceEquals(currentSymbol, Log) || ReferenceEquals(currentSymbol, Exp) ||
-          ReferenceEquals(currentSymbol, Sin)) {
+          ReferenceEquals(currentSymbol, Sin) || ReferenceEquals(currentSymbol, Inv)) {
         return AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)).ToEnumerable().ToArray();
       }
@@ -205 +234 @@
 
       int start;
-      if (ReferenceEquals(operatorSym, Addition) && hashesArray.Count() <= 1) {
+      if ((ReferenceEquals(operatorSym, Addition) || ReferenceEquals(operatorSym, Multiplication)) && hashesArray.Count() <= 1) {
         start = 0;
       } else {
@@ -257 +286 @@
       } else if (ReferenceEquals(currentSymbol, Sin)) {
         parsedSubTree = sinSy.CreateTreeNode();
+        parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));
+
+      } else if (ReferenceEquals(currentSymbol, Inv)) {
+        parsedSubTree = divSy.CreateTreeNode();
+        ConstantTreeNode dividend = (ConstantTreeNode)constSy.CreateTreeNode();
+        dividend.Value = 1.0;
+        parsedSubTree.AddSubtree(dividend);
         parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));
 
@@ -293 +329 @@
         result.AddRange(rightPart);
 
-      } else if (ReferenceEquals(head, Log) || ReferenceEquals(head, Exp) || ReferenceEquals(head, Sin)) {
+      } else if (ReferenceEquals(head, Log) || ReferenceEquals(head, Exp)
+              || ReferenceEquals(head, Sin) || ReferenceEquals(head, Inv)) {
         result.Add(head);
         result.Add(OpeningBracket);

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

@@ -94 +94 @@
       Parameters.Add(new ValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(4000)));
 
-      Parameters.Add(new ValueParameter<EnumValue<StorageType>>(SearchDataStructureParameterName, new EnumValue<StorageType>(StorageType.RandomList)));
+      Parameters.Add(new ValueParameter<EnumValue<StorageType>>(SearchDataStructureParameterName, new EnumValue<StorageType>(StorageType.Stack)));
     }
 

branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs

@@ -1 +1 @@
 using System;
+using System.Collections;
+using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration;
 using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
+using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Problems.DataAnalysis;
@@ -52 +55 @@
     [TestMethod]
     [TestProperty("Goal", "structure search")]
-    public void MctsSymbReg_NoConstants_Nguyen1() {
+    public void NoConstants_Nguyen1() {
       // x³ + x² + x
-      alg.MaxTreeSize = 15;
-      alg.Problem.ProblemData = new NguyenFunctionOne(Seed).GenerateRegressionData(); 
+      alg.MaxTreeSize = 12;
+      alg.Problem.ProblemData = new NguyenFunctionOne(Seed).GenerateRegressionData();
 
       alg.Start();
@@ -83 +86 @@
     //[TestMethod]
     [TestProperty("Goal", "structure search")]
-    public void MctsSymbReg_NoConstants_Nguyen2() {
+    public void NoConstants_Nguyen2() {
       // x^4 + x³ + x² + x
       alg.MaxTreeSize = 20;
@@ -95 +98 @@
     //[TestMethod]
     [TestProperty("Goal", "structure search")]
-    public void MctsSymbReg_NoConstants_Nguyen3() {
+    public void NoConstants_Nguyen3() {
       // x^5 + x^4 + x^3 + x^2 + x
       alg.MaxTreeSize = 32;
@@ -105 +108 @@
     }
 
-    [TestMethod]                              
-    [TestProperty("Goal", "structure search")]
-    public void MctsSymbReg_NoConstants_Nguyen6() {
+    [TestMethod]
+    [TestProperty("Goal", "structure search")]
+    public void NoConstants_Nguyen6() {
       // sin(x) + sin(x + x²)
-      alg.MaxTreeSize = 15;
+      alg.MaxTreeSize = 13;
       alg.Problem.ProblemData = new NguyenFunctionSix(Seed).GenerateRegressionData();
 
       alg.Start();
-      EvaluateGrammarEnumeration();
-    }
-
-    [TestMethod]
-    [TestProperty("Goal", "structure search")]
-    public void MctsSymbReg_NoConstants_Nguyen9() {
+
+      TerminalSymbol varSymbol = alg.Grammar.Var.VariableTerminalSymbols.First();
+      TerminalSymbol mulSymbol = alg.Grammar.Multiplication;
+      TerminalSymbol addSymbol = alg.Grammar.Addition;
+      TerminalSymbol sinSymbol = alg.Grammar.Sin;
+
+      SymbolString targetSolution = new SymbolString(new[] {
+        varSymbol, sinSymbol,
+        varSymbol, varSymbol, mulSymbol, varSymbol, addSymbol, sinSymbol, addSymbol
+      });
+
+      int targetSolutionHash = alg.Grammar.CalcHashCode(targetSolution);
+      int actualSolutionHash = alg.Grammar.CalcHashCode(alg.BestTrainingSentence);
+
+      Assert.IsTrue(alg.DistinctSentences.ContainsKey(actualSolutionHash), "Actual solution was not generated!");
+
+      Assert.AreEqual(targetSolutionHash, actualSolutionHash, "Actual solution was not recognized as best one.");
+
+      EvaluateGrammarEnumeration();
+    }
+
+    [TestMethod]
+    [TestProperty("Goal", "structure search")]
+    public void NoConstants_Nguyen9() {
       // sin(x) + sin(y²)
       alg.MaxTreeSize = 10;
@@ -133 +154 @@
       alg.MaxTreeSize = 10;
       alg.Problem.ProblemData = new PolyTen(Seed).GenerateRegressionData();
+
+      alg.Start();
+      EvaluateGrammarEnumeration();
+    }
+
+    [TestMethod]
+    [TestProperty("Goal", "structure search")]
+    public void NoConstants_Inverse() {
+      // 1 / (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();
+      alg.Problem.ProblemData = new RegressionProblemData(new Dataset(new List<string>() { "x", "y" }, new List<IList>() { x, y }), "x".ToEnumerable(), "y");
 
       alg.Start();
@@ -210 +245 @@
       var ys = ds.GetDoubleValues("Y").ToArray();
       var x1 = ds.GetDoubleValues("X1").ToArray();
-      var x2 = ds.GetDoubleValues("X2").ToArray();
+      var x2 = ds.GetDoubleValues("X2").ToArray();                                           
       var x3 = ds.GetDoubleValues("X3").ToArray();
       var x4 = ds.GetDoubleValues("X4").ToArray();

branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs

@@ -106 +106 @@
     }
 
+    [TestMethod]
+    [TestCategory("TreeHashing")]
+    public void InverseFactorCancelationSimple() {
+      SymbolString s1 = new SymbolString(new Symbol[] { varA, grammar.Inv, varB, grammar.Multiplication, varA, grammar.Multiplication, varA, grammar.Multiplication });
+      SymbolString s2 = new SymbolString(new Symbol[] { varA, varB, grammar.Multiplication });
+
+      int hash1 = grammar.CalcHashCode(s1);
+      int hash2 = grammar.CalcHashCode(s2);
+
+      Assert.AreEqual(hash1, hash2);
+    }
+
+    [TestMethod]
+    [TestCategory("TreeHashing")]
+    public void InverseFactorCancelationComplex() {
+      SymbolString s1 = new SymbolString(new Symbol[] { varA, grammar.Sin, varA, varA, grammar.Multiplication, varA, grammar.Addition, grammar.Sin, grammar.Addition });
+      SymbolString s2 = new SymbolString(new Symbol[] { varA, varA, varA, grammar.Multiplication, grammar.Addition, grammar.Sin, varA, grammar.Inv, varA, grammar.Sin, varA, grammar.Multiplication, grammar.Multiplication, grammar.Addition });
+
+      int hash1 = grammar.CalcHashCode(s1);
+      int hash2 = grammar.CalcHashCode(s2);
+
+      Assert.AreEqual(hash1, hash2);
+    }
 
     #region parser